Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
340
questions
3
votes
1
answer
217
views
How can I linearise this nonlinear proportional relation constraint?
My optimisation problem has a constraint in the form
\begin{equation}
\begin{array}{*{35}{l}}
\text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
- 2,211
2
votes
1
answer
153
views
Can I solve the separation problem efficiently, when I have access to an optimization oracle?
Assume I have given a convex feasible set $X$ and I have an oracle that can optimize some linear objective function $c$ over $X$. Assume that I have given a point $r$.
I want to solve the separation ...
- 3,635
6
votes
1
answer
501
views
What underlies intlinprog in MATLAB?
When a paper says they used the intlinprog in MATLAB to solve an integer program, what system actually does the solving? I have seen documentation about Gurobi and MATLAB: does Gurobi always provide ...
- 2,362
4
votes
2
answers
479
views
Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously
I would like to seek some advice on modeling the following logical condition:
I would like to ensure that a group of binary variables do not equate to 1 simultaneously, i.e., $\omega_{1}=1, \omega_{2}=...
- 707
7
votes
4
answers
2k
views
What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?
I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity.
I also have a fixed number of objects each of which ...
- 543
1
vote
0
answers
48
views
Unifying constraint matrices in sparse situations
$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...
- 11
4
votes
3
answers
215
views
How can I find the optimal assignments for this MILP problem heuristically?
I have an assignment problem as follows
$\begin{equation}
\begin{array}{*{35}{l}}
\underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\
\text{}\text{...
- 2,211
5
votes
0
answers
88
views
Bounding the size of the dual solution
Given an primal optimization with bounded feasible set: $\max \{cx: Ax \leq b\}$.
The feasible region of the dual is $D = \{y:y^\top A = c^\top, y \geq 0\}$.
If the primal feasbile region is a ...
- 3,635
6
votes
1
answer
534
views
ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied
Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $x_i$'s. Consider an ILP constraint $x_1 + x_2 + x_3 \geq 1$ and another constraint $x_4 + x_5 + x_6 \geq 1$. I would like to ...
- 897
11
votes
3
answers
1k
views
Are there explainability approaches in optimization?
In the machine learning community there is the big topic of explainability, where you want to make the solution of ML models explainable or derive explainable models.
This is also interesting for ...
- 3,635
2
votes
1
answer
157
views
Minimizing a quadratic binary nonconvex function by CPLEX
I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX.
In particular, my function is the following:
$$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{...
4
votes
2
answers
516
views
How to improve relative mip GAP using CPLEX in a MIP
Supose that I have an integer feasible solution for a MIP and I provide this one for CPLEX. I have tested this situation in a problem and CPLEX have reported the following:
...
3
votes
1
answer
395
views
Problems finding a feasible solution in a MIP
I am using CPLEX with Julia using the package JuMP to solve a MIP problem.
In a small instance, I have tested my problem but, after 10 minutes, nothing happens. I have defined the following parameters ...
0
votes
1
answer
1k
views
Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree
I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie,
I need Miller-Tucker-Zemlin formulation ...
- 409
2
votes
1
answer
120
views
Has the concept of TU other application than proving convex hull characterizations?
If a matrix is totally unimodular (TU), then we know that $\text{\{}x| Ax\leq b \text{\}}$ is integral for all integral $b$'s. This is often used for convex hull proofs, but does the concept of TU has ...
- 3,635
3
votes
2
answers
311
views
Modeling in integer programming vs modeling in constraint programming
I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams).
Now I am trying to learn how to model with constraint programming. ...
- 147
4
votes
1
answer
196
views
Contiguous service area constraint
Background: I have a set of ZIP codes (e.g., all of the state of Wisconsin), and am trying to figure out an optimization-based approach to identify a subset of these ZIP codes for a logistics service ...
- 743
10
votes
2
answers
549
views
How to maximize "contrast" between nodes on a graph?
I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
- 273
3
votes
1
answer
255
views
In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?
I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices.
I have trouble ...
- 181
3
votes
1
answer
178
views
Strict inclusion for facility location formula and aggregate facility location formula
I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
- 33
2
votes
2
answers
125
views
Constraint to handle the machine-configuration's change between initial position and its first occurrence in the process
I am working with a kind of a reconfigurable process planning, meaning that the same machine can have different configurations and perform multiple operations. Each machine has an initial ...
- 1,133
1
vote
1
answer
453
views
Priority Constraint
Suppose I have the following set of binary variables:
$X_i$: $I$ ranges from {1,..,4} Highest priority among the three variables $X$ , $Y$ and $Z$
$Y_j$: $J$ ranges from {1,..,3}
$Z_k$: $K$ ranges ...
- 21
8
votes
4
answers
420
views
Understanding integer programming solvers
I would like to verify if I understand the nature or workings of integer programming solvers.
My understanding is that for integer programming problems like the knapsack problem or the traveling ...
- 249
3
votes
2
answers
935
views
How to get an extreme ray of an LP from Gurobi
I am working on a problem of form
\begin{equation}
\begin{array}{l @{\quad} l}
\mathrm{max}_{x, u} & p^{\top} u
\\
\text{st.} & A u + a x \leq 0
\\
& x \in \{0, 1\...
- 3,980
0
votes
2
answers
278
views
How can I formulate this specific if-then constraint?
IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly)
AND
IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly)
$X$ and $Y$ are binary variables.
What I'm actually trying to do is to charge the ...
- 21
4
votes
2
answers
222
views
How to solve this convex problem heuristically?
I have the following problem
$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$
$$\text{subject to}$$
$$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$
$...
- 2,211
3
votes
0
answers
81
views
Flexible Job Shop with Preemption
I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
1
vote
1
answer
148
views
Constraint programming and scheduling issues
I have a constraint problem that I need to resolve, but I did not how know to model the problem:
I have 11 employees, I will name them from $a$ to $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.
I have a small ...
- 19
2
votes
1
answer
611
views
Divisibility constraint in Integer programming
I have a simple question regarding the divisibility in integer programming
suppose the objective function is
$\text{max}\quad x_1 + x_2$
where the constraint is that the sum of $x_1$ and $x_2$ are ...
- 123
2
votes
1
answer
89
views
confusing results of two models with different complexity
i have two models that address the same problem.
the first one is :
the second one is:
for different instances for the same size (n=30) i found the following results ( the first column on the left ...
- 413
4
votes
1
answer
266
views
How to determine the size of a model?
I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....).
Is the number of variables $\mathcal O(n^3)$ because we have ...
- 413
6
votes
1
answer
165
views
Literature on "simcity-like" problems
As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.
I have a set of "buildings" that I want to place on a small 2d ...
- 211
-2
votes
1
answer
124
views
Any references to the ROADEF 2020 Challenge?
The problem description of the challenge is given here.
Does anyone has some references to similar problem. I would like to participate but I don't know where to start.
- 567
2
votes
0
answers
120
views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
- 251
2
votes
1
answer
49
views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
user4156
4
votes
1
answer
425
views
Issue in solving a large scale MIQP problem
I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below.
\begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
- 41
2
votes
0
answers
119
views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
- 21
3
votes
2
answers
782
views
What are the solvers that give a feasible solution within a given time?
What are the solvers that take the maximal computation time as a parameter and gives the best found feasible solution within this time.
- 567
3
votes
2
answers
121
views
Modelling a data-sensitivity scenario as an ILP problem
I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive ...
user4156
0
votes
0
answers
74
views
Linearizing max constraint Problem [duplicate]
I want to linearize a max constraint as below:
In which x_(i,t),are binary decision variables and T is a constant.
How can I linearize this constraint?
3
votes
0
answers
87
views
How to find all covers and minimal covers?
Consider a constraint of type
$$c_1x_1+c_2x_2+\cdots+c_nx_n\leq C$$
with $x_i$ binary.
We call a cover a subset of the $n$ indices such that the sum of the corresponding coefficients is higher than ...
- 1,641
1
vote
2
answers
106
views
How this problem can be defined as MultiObjective optimisation
I need to optimize the end-to-end latency of a multi-component application.
Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
- 75
5
votes
0
answers
147
views
When is there at least an integral point in a polyhedron?
This problem comes from a problem of economics. Let $x\in [0,1]^n$. $\{x_1,x_2,\ldots,x_n\}$ is partitioned into ${S_1, S_2,\ldots,S_k}$ such that $\sum_{x_i\in S_j}x_i\leq 1$ for each $1\leq j\leq k$....
- 137
1
vote
2
answers
416
views
Switching of decision variables to be larger than or equal to a decision variable according to an indicator variable value
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a ...
- 707
4
votes
1
answer
260
views
Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is to be equated to a third ...
- 707
7
votes
1
answer
280
views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
- 173
4
votes
2
answers
520
views
Formulating the conditional constraint
I want to develop a model extension of capacitated location problem.
The variables are a binary $x_i$ and a continuous $Q_i$. The following condition must be satisfied:
if $x_i = 0$, $Q_i$ must be ...
3
votes
1
answer
133
views
Integer decision variables as index
The following problem has only two integer variables; however, they appear in the index of the parameters. Appreciate it if anyone has any efficient idea to transform it into a canonical integer ...
3
votes
0
answers
71
views
Theoretical aspect of using extended formulation
If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
- 31
5
votes
0
answers
169
views
Are there any good models for min-max vehicle routing problem?
I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
- 253