Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
339
questions
4
votes
1
answer
637
views
Can sensitivity analysis and limits report be done on an BILP problem?
I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel.
I know that they can only ...
- 205
1
vote
2
answers
238
views
Capacitated Maximum Coverage Location Problem, Python and Gurobi
I am trying to solve a capacitated MCLP problem with two additional constraints.
Non-overlapping circles
Minimum and Maximum value for the capacity for a circle.
for 2nd constraint, I am able to add ...
- 13
1
vote
1
answer
178
views
How to write this logical expression with Gurobi + Java, or express it as a big-m formulation
I am trying to write the following expression in Gurobi+Java or Gurobi+python, if it is more practical It could be expressed as a big-M formulation.
\begin{equation} \label{const4}
\text{D}_{uv} =
...
- 11
2
votes
4
answers
451
views
How to approach this shifts problem with Excel Solver?
I am trying to find a way to solve the following problem of mine by using Solver but I get stuck right at the end of it.
I have a table of 14 companies each of which want to work on a project. I will ...
- 205
5
votes
1
answer
668
views
How many variables and constraints can modern mixed integer programming solvers handle?
I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there:
"I know ...
- 153
1
vote
0
answers
56
views
How to avoid complementarity constraints in continuous nonlinear program?
In my two-stage continuous NLP problem, I have a constraint in second stage:
$X_{g,k}$ = $X_{g,0} + a_{g} d_{g} $, if $X_{g,k} \in [X_g^u,X_g^l]$
$X_{g,k} = X_g^u$, if $X_{g,k} \geq X_g^u$
$X_{g,k} ...
1
vote
2
answers
176
views
How to express this constraint efficiently?
Let, $\mathcal{C}=\{1,2,\cdots,C\}$,
$\mathcal{U}=\{1,2,\cdots,U\}$
$\mathcal{S}_u$ is a subset of $\mathcal{C}$ with $u\in \mathcal{U}$
$d_{u,c}$ is a binary variable with $u=1,2,\cdots,U$ and $c=1,2,...
- 2,211
3
votes
2
answers
228
views
Modifying and re-optimizing a model using CPLEX Python API
I came across the following functionality that is offered by CPLEX for modifying and re-optimizing a model based on previous computations: https://perso.ensta-paris.fr/~diam/ro/online/cplex/cplex1271/...
- 392
1
vote
1
answer
106
views
How to model and solve such a 0-1 programming problem
My problem is described in this picture(It's like a Pyramid structure):
The objective function is below: $$\min\sum_{k=1}^\ell\sum_{i=0}^{2^k-1}\sum_{j=0}^{2^k-1}\left(A_{i,j}^k-A_{i,j+1}^k\cdot\frac{...
- 63
2
votes
1
answer
127
views
Conditional constraint for binary
Could you please check where I might be wrong?
Task is:
If $z=1$, then either $x=1$ or $y=1$
My approach:
If $z=1$, then $x+y=1$
$\implies x+y\le1$
$\implies x+y\ge1$
If $z=0$, then $x+y\ge0 - M\cdot(...
6
votes
2
answers
217
views
Breaking symmetry of permutations in LIP
Setup
I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using ...
- 73
2
votes
1
answer
85
views
Expressing inner product of binary variables in MIP
I have a $m$ by $n$ matrix $X$ of binary variables in my MIP which represents a list of $m$ items each belonging to one of $n$ categories. $m$ is usually around $1,000$ while $n$ is much lower at ...
- 123
2
votes
3
answers
538
views
How to find the index of the item, the first time appears?
How to formulate this problem as MIP:
For example, we have the following vector of binary variables:
$$
x= [0, 0, 0, 1, 0, 1, 1]
$$
How to find out when the first "1" is recorded? For ...
- 391
4
votes
3
answers
433
views
How to transform a logical constraint with integer variables?
Consider the binary variables $x_1, x_2 \in \{0,1\}$ and the integer variable $y \in \mathbb{Z}$ with $0 \leq y \leq 3$.
I'd like to formulate the following logical constraint:
$$
x_1 = 1 \wedge y \...
- 385
1
vote
1
answer
109
views
ILP program to find a centrosymmetric Hadamard matrix
A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36.
An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if:
$$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
- 393
1
vote
1
answer
243
views
Create constraint when variable is within a given range MILP
What is the best way to specify whether a given variable is within a given range in Pyomo? Here I have a binary decision variable assign[t, e] which I want to ...
- 392
2
votes
1
answer
49
views
How to get the fractional solution of a node in a MIP model using JuMP package?
I'm coding in Julia and use the JuMP package. My IP solver stops by a fixed node limitation. I noticed that I can only get the feasible primal and dual solution if has any, however I would like to get ...
- 173
3
votes
1
answer
73
views
Can we turn a Binary IP model into a problem solvable using Local search?
I am new to the fields of operations research. I have a Binary IP model for solving a scheduling problem and I am seeking to find information whether I can somehow transform it to a problem that can ...
- 392
2
votes
2
answers
73
views
How to model this?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ and $y_{j}$ are binary variables.
How to model: If
$$c_{ij}\...
user5245
4
votes
1
answer
75
views
Another difficult constraint for an ILP
How can I add to this ILP with all binary variables (again related to this question):
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} \ge \lfloor (n-1)/2\rfloor \qquad \...
- 393
5
votes
3
answers
679
views
Constraint for two binary vectors to be different
If I have a matrix $A$ of binary variables $a_{i,j}$, $1 \le i \le n$, $1 \le j \le m$, how can I enforce in an Integer Linear Program with binary variables, the condition that every two columns must ...
- 393
4
votes
1
answer
187
views
Difficult linearization of a constraint
My previous question was about this ILP with all binary variables:
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$
$$...
- 393
3
votes
2
answers
100
views
How to model if-then?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ is a binary variable.
How to model: If
$$c_{ij}\cdot x_{ij} \...
user5245
4
votes
2
answers
479
views
Expected ILP solving time and how to improve speed
I am trying to solve this ILP with all binary variables:
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$
$$a_{k,i} + ...
- 393
3
votes
2
answers
236
views
Simple Integer Optimization Problem: docplex CP model works but equivalent PuLP+CBC model is infeasible?
I have an integer optimization problem with one constraint per decision variable and no objective function. It can be coded and solved using docplex, however I am ...
- 145
3
votes
0
answers
87
views
Minimize total cost to buy unique products over timespan
I am looking for some guidance on how to better state my problem formally and practically (e.g., relevant Python libraries).
Let's assume I have a set of $X$ unique products to buy. I have $Y$ days in ...
- 31
3
votes
1
answer
182
views
Assignment problem with mutually exclusive constraints has an integral polyhedron?
I have the following problem
$\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $
$s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$
$\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $
$\...
- 33
1
vote
1
answer
96
views
convert x=min(x, N) function into a constraint, integer programming python
In this case, the shop want to maximise the profit that is there $n$ products the shop can procure, but the shop only has $w$ budget. The cost of each product $x_i$ is $c_i$.
I used prediction model ...
- 21
5
votes
2
answers
103
views
Is there an efficient/polynomial way to detect/determine whether a polyhedon contains at least an integer point?
How to determine whether a convex polyhedron described by a set of linear inequalities contains at least a or no integer point in polynomial time, which is to say detecting the IP feasibility ?
...
- 173
2
votes
2
answers
101
views
Is there a name for this type of integer programming?
Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$.
An integer programming problem is where the goal is to:
$\text{maximize} \quad \sum_i c_ix_i$
$\text{...
- 133
1
vote
0
answers
40
views
Is there a name for this type of integer programming? [duplicate]
Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$.
An integer programming problem is where the goal is to:
$\text{maximize} \quad \sum_i c_ix_i$
$\text{...
- 133
-2
votes
1
answer
86
views
constraints for a zero-one integer programming problem
We want to arrange 8 tables in 2 rooms. How to write the following constraints?
Either table 3 or table 6 must be in room 1 (or both).
Exactly one of tables 7 and 8 must be in room 2.
- 115
5
votes
1
answer
108
views
Identifying the variant of such a knapsack-like problem
I am not too familiar with variants of knapsack problems (or variants of possibly other classical OR problems), but I would like to identify the following Integer Programming problem:
$$\min_{x_i,y_{i,...
- 51
3
votes
2
answers
304
views
How to model logic constraint: $y=1$ if $a\le x\le b$ and $y=0$ otherwise?
I am trying to formulate indicator-type of constraints. $y$ is binary $0$ or $1$ and $x$ is a continuous variable.
$$ y =
\begin{cases}
1, & \text{ if } a \leq x \leq b \\
0, & \...
- 53
2
votes
1
answer
87
views
Could non-supported efficient solutions in multi-objective optimization problem be an optimal solution of a parameterized single-objective problem?
Since all supported efficient solutions in a multi-objective optimization problem are actually the optimal solutions for some weighted sum scalarization single-objective optimization problem with the ...
- 173
2
votes
1
answer
118
views
Linearize a product of binary variables with 2 indexes
I have the following inequality that I would want to linearize.
Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $...
4
votes
1
answer
469
views
Is this a non-linear integer model?
Let's say if I have two decision variables, $f$ and $g$ respectively, where $f$ is continuous, and $g$ is binary.
If I have a constraint like this,
$$ f\cdot g \le C$$
Does this make my model ...
- 593
2
votes
1
answer
207
views
How to write constraint with sum of absolutes in Integer Programming?
I found a solution for just one term here
How can we formulate constraints of the form
$$ \sum_{i=1}^n |x_i -a_i| \ge K $$
in Mixed Integer Linear Programming ?
- 203
1
vote
1
answer
98
views
What is the meaning of this multi commodity formulation VRP in LINGO
Can someone tell me what is the meaning of this multi commodity flow formulation that I got in LINGO ? I have the brief explanation about the model but don't quite understand the logic behind, here is ...
- 593
7
votes
2
answers
866
views
Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value
So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$
I was interested in posing a constraint so that in the collection $...
- 205
3
votes
1
answer
102
views
How to pose the constraint for binary variable to indicate if quantity is zero or greater than zero
So if I have some quantity bounded i.e
$ 1-N \leq (p^i-p^{i+1}) \leq N-1,$ for $N\ge1 $. The quantity $p^i-p^{i+1}$ will be an integer as well.
I was trying to figure out how to pose the constraint so ...
- 205
4
votes
1
answer
220
views
Accelerating an integer programming model
I am working on a scheduling problem, where I am solving it through column generation. The pricing problem of this algorithm is an integer programming model as follows:
\begin{equation}
F_1 \Big\{V^...
- 573
2
votes
0
answers
68
views
Multi Commodity VRP Time Windows Paper
I have been wondering is there any paper that who discuss multi commodity with four index/indices like this formulation below:
$$
\begin{gathered}
\sum_{k} \sum_{c} F_{j, j, c, k}=1 \quad \forall j \\
...
- 593
3
votes
1
answer
120
views
Modeling a special case of conservation of flow
At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e
The first requirement is that only one of the two inflow ...
- 707
3
votes
1
answer
195
views
Integer programming books
I would like to know which books are best to study integer programming. I can see similar questions on this website, such as this one:
Books for integer and mixed integer programming
Integer and ...
- 333
0
votes
1
answer
59
views
What is the meaning of this math formulation?
I have been wondering what is the meaning of this sigma with delta negative or plus in there (if my read is correct).
$$
\sum_{i \in \Delta^{-}(j)} x_{i j k}-\sum_{i \in \Delta^{+}(j)} x_{j i k}=0 \...
- 593
4
votes
3
answers
203
views
Is this ILP formulation for Group Closeness Centrality a column generation approach?
I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
1
vote
2
answers
154
views
Include dataframe linear optimization in r
For a linear optimization problem I want to include a dataframe (d_ij) which has binary variables,
1 if customer i is located within the assignable distance of facility j, 0 otherwise. So unless d_ij =...
- 99
9
votes
2
answers
1k
views
Gurobi finishes with 'infeasible' although optimal solution exists
I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs.
I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
- 153
3
votes
1
answer
199
views
Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?
I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning):
Given $n$ tasks, with times $\{t_i\}_{i\in I_n}$, and $m$ ...
- 676