Skip to main content

Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
3 votes
1 answer
72 views

How to reformulate the BigM constraints into its equivalent Convex-hull formulation?

I am trying to work on a scheduling problem based on its polyhedron reformulations. For that, I would like to reformulate a BigM model into its equivalent C-hull formulation. The transforming map is ...
0 votes
1 answer
43 views

Linearization of two constraints: one with a conditional max and one with a sum with a variable as index

I have these two quite nasty constraints I have tried to linearize. I am trying to dynamically control if you are allowed to plan producing product p. You are allowed to do it if the product arrived (...
0 votes
0 answers
36 views

Mixed integer optimization: what if X has to be a rounded multiple of a fixed value? [duplicate]

I am working on a Mosek project. The utility function is to maximize u^{t} x where x is a vector of N There is a tricky constraint: the first 3 items of X must be ...
0 votes
1 answer
185 views

Production scheduling

I'm formulating a scheduling problem with the following decision variables: $$X_t \space \text{is power sold to market in time period t} \\ Y_t \space \text{is power used for production in time period ...
0 votes
1 answer
93 views

What is the best open-source solver for large-scale MILP optimization?

Currentlly, I am using ortools with SCIP/CBC solvers for a large scale optimization problem, which turned out to be quite slow. The integer part of my problem is due to a piece-wise linear function in ...
23 votes
10 answers
818 views

Reference for column generation applications

When talking about column generation algorithms, the main example is the cutting stock problem. I'm aware that variations of vehicle routing problem (VRP) can be solved using a column generation ...
0 votes
0 answers
36 views

Getting solution status as Unknown status value in callback (lazyconstraints) for docplex with Python to solve MILP

from docplex.mp.model import Model from cplex.callbacks import LazyConstraintCallback from docplex.mp.callbacks.cb_mixin import * p_id is the list of lists of customers, n is the set of vehicles, dth ...
2 votes
2 answers
127 views

constraint set for a scheduling problem with machine availability

I have a set of tasks $I$ with processing times $p_i, \forall i \in I$. There exists a set of machines $M$ and each machine has availability time ranges in a given time horizon. For instance, given a ...
1 vote
1 answer
135 views

How to avoid division by zero with a binary variable at the denominator in a network assignment problem?

I am currently working with some network assignment problem as a network engineer. My engineering application can be stated as follows: There are $M$ users that needs to be assign to $N$ servers. This ...
0 votes
0 answers
45 views

Cost Function in a Gas Market Model

I am trying to formulate the correct objective function for the following problem: Minimize the total cost in a gas market from the perspective of the consumer. There are storage from which you can ...
1 vote
1 answer
51 views

MILP Model for Assigning Unique Number for Each Point

I am trying to solve a problem which is smilar to sudoku. I have a specific device location on map I need to gave them a unique integer numbers. However, as in the sudoku I can assign up to 9 and ...
0 votes
1 answer
75 views

Minimize Expenses For Workers

My goal is to minimize the labor expenses. Say we have 3 types of workers: $x_1$ = Permanent Driver, rate = 693.875/day $x_2$ = Reliever Drivers rate = 435/day $x_3$ = Crews rate = 400/day There are 6 ...
4 votes
1 answer
252 views

"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\...
2 votes
2 answers
488 views

Can I tell a MILP solver to prefer solutions with fewer fractions?

I have a linear program $$\max c^T x \text{ s.t. } A x\leq b, x\geq 0.$$ I would like a solution that, among all optimal solutions, has the largest number of integer variables. For example, if the ...
2 votes
1 answer
61 views

Optimization under cardinality constraint

When we consider the following optimization problem: \begin{equation}\label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ &...
0 votes
1 answer
36 views

Adding additional coordinating constraint to a decomposed model

As suggested by @RobPratt, here is the new opened question. I have these decomposed master and subproblems: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{...
1 vote
1 answer
54 views

The first reference which formulated k-means problem as MIQCP using big-M constraint

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $P_1, P_2, \dots, P_N$ in $\mathbb{R}^d$, the problem is to find $K$ centres $Q_1, ...
0 votes
0 answers
52 views

Limit the time in the root node

I have a hard problem where I fix some variables to solve it. However, the time elapsed in the root node is high. Is there a way to limit this time anf force the Gurobi start the ramification? I have ...
2 votes
1 answer
58 views

Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the ...
8 votes
1 answer
135 views

Is there any way to use Lazy constraints in Pyomo?

I would like to know if there is any way to implement a Lazy constraint in the Pyomo package. (As far as I know, the only way to implement such a constraint is by ...
4 votes
0 answers
43 views

Total Unimodularity of constraint matrix

Given a directed graph $G=(V,E)$, I have the following integer program- \begin{align} \max & \sum_{(u,v) \in E} \sum_{s \in S} w_{uv} z_{uv,s} + \sum_{v \in V} \sum_{s \in S} b_{v,s} x_{v,s} \\ \...
3 votes
1 answer
87 views

Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
1 vote
1 answer
47 views

Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
1 vote
1 answer
126 views

How to linearize the waiting time

My question is this: I want to express the time it takes for multiple servers to complete tasks for multiple users. I divide the time into $t$ time slots, and each task may occupy multiple time slots. ...
0 votes
0 answers
28 views

What are the "cutoff values" in Hybrid Branching?

In "Hybrid Branching" by Achterberg and Berthold, we have this line: the number of subproblems that could be pruned due to branching on this variable, called the cutoff values Can you ...
3 votes
0 answers
38 views

To "fix" continuous variables in Benders decomposition

In nearly all applications I have seen, the master problem variables $x$ that define the subproblem are binary. (Logic-based) Benders decomposition can applied to a problem of the form: $$\min_{x,y} f(...
0 votes
0 answers
35 views

Reformulations for a linear program with absolute values in the objective function

I am looking for suggestions on improving the formulation of the following problem: $\max_{\vec{x} \in \mathbb{R}^{2^n}} \sum_{i=1}^{2^n}\lvert x_i \rvert$ such that $\vec{x}$ is in the feasible ...
2 votes
1 answer
123 views

Avoid double counting in objective function for a maintenance scheduling problem

I have a problem to do with machine maintenance scheduling which I have formulated as a MIP where I have a binary variable $x_{ijt}$ which is 1 if the maintenance job j is scheduled on the same ...
6 votes
2 answers
1k views

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
2 votes
2 answers
87 views

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
1 vote
0 answers
37 views

Using the Alternative Cut Generation Problem in Benders, why do I get different results?

I am using Benders' Decomposition to solve a stochastic MIP. To improve cut selection, I implemented the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010). I will summarize the ...
1 vote
0 answers
84 views

what should I do to avoid scipy.minimize solver from computing infeasible models as much as possible

Python==3.9.5, scipy==1.13.0 My model has some variable coefficients in each round of calculation. for example, for a four-dimensional decision variable ...
1 vote
1 answer
30 views

Traverse discrete approximations to a continuous system

I have a system of equations looking like $$ \frac{2.8 R_{6}}{R_{4} + R_{6}} = \frac{5.2}{\left(\frac{1}{R_{2}} + \frac{1}{R_{1}}\right) \left(R_{7} + \frac{1}{\frac{1}{R_{2}} + \frac{1}{R_{1}}}\right)...
0 votes
2 answers
108 views

Extracting a sequence as a decision variable from a matrix (PuLP)

I am solving a sequencing problem x[i][j], i.e. a binary matrix indicating that product i is followed by ...
0 votes
1 answer
42 views

Column Generation for non/single capacitated routing problems

Introduction The strategy here documented was applied before for the TSP: Column generation for TSP https://coin-or.github.io/jorlib/manual/manual.pdf (Section 4, page 18); And https://www.jstor.org/...
3 votes
1 answer
199 views

How to linearize the following logical constraints?

I am having trouble linearizing the following logical constraints. $x,y,z$ are non negative continuous variables such that $x=y+z$, and $A$ is a positive parameter. I would like to linearize $$ y= \...
3 votes
2 answers
834 views

How to avoid similar solutions?

I have a problem like this $x_1 +x_2 +x_3 =10$ let's assume $0 \leq x_i \leq 10$ It is obvious that this problem has more than one solution For example : Solution 1 : $x_1 =0 , x_2= 1 , x_3 =9$ ...
8 votes
1 answer
1k views

Why do I get a binary solution even when I solve an LP problem with continuous variables?

I have a MILP in the following form maximize $${\bf c}^T{\bf x}$$ subject to $${\bf Ax}\le {\bf b}$$ Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 ...
2 votes
2 answers
91 views

Optimizing calls to a separation problem in branch and cut

I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code ...
2 votes
1 answer
76 views

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters: $$ l, m, n \...
1 vote
0 answers
70 views

Getting error in callback (lazy constraints) for docplex with Python to solve MILP

I am trying to use lazy constraints to solve my MILP problem. The details are given as follows. ...
1 vote
3 answers
219 views

Formulating a constraint to select the minimum value of an index

To provide a clear description of my problem, let me outline the scenario. I have a binary variable $\phi_{k,c}$ where $k$ is an index belonging to the set $\{1, 2, 3, ..., 9\}$. As an example, for a ...
1 vote
2 answers
102 views

In a routing and scheduling problem with break consideration, How can I determine whether a node is met before a break or after it?

I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some ...
5 votes
0 answers
58 views

Gurobi - Is finding a feasible solution when optimizing a lot harder than finding a feasible solution?

The code is working fine but I feel as my intuition could be wrong. I first set up my problem as: $$\min_{f(x)\leq F} g(x) $$ and gurobi was unable to find a feasible solution. I then relaxed ...
3 votes
1 answer
111 views

Restrict the number of non-zero variables to any constant in MILP

I am designing an MILP in which given a set $[n]$ of $n$ agents, we create for each $i \in [n]$ a real variable $x_i$. The variables $x_i$ are between 0 and 1 ($0 \leq x_i < 1$). I would like to ...
5 votes
1 answer
162 views

Numerically stable way to optimize a lexicographical preference between two objective functions?

I am solving a mixed-integer program whose decision variables are $x \in \{0, 1\}^n$ and $y \in \mathbb{R}^m$, where $0 \leq y_j \leq u_j$ for constant upper bounds. My primary objective function is ...
1 vote
2 answers
185 views

Help with Mathematical Formulation for VRP with Specific Constraints

I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers ...
1 vote
1 answer
97 views

Conditional binary programming

I am currently trying to model the relationship that if the binary variables $b_{it}=0$ and $c_{it}=1$, and for the integer non-negative variable $b^{n}_{i(t-1)}=0$, then the new binary variable $a_{...
0 votes
0 answers
97 views

Tightening a specific constraint

I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
1 vote
1 answer
85 views

How to achieve recording the change of objective or primal gap in solving MILP by SCIP?

I am a solver beginner, would like to ask you how to call the solver to achieve second-level recording, as documented in many articles, as shown below.

1
2 3 4 5
21