13
votes
Accepted
Rewriting if-then constraints of binary summations
In conjunctive normal form, you want to enforce:
\begin{align}
&\quad \quad \quad\bigvee_b x_{i,j}^{a,b} \implies \bigwedge_{u,v}\neg y_{u,v}^{a} \quad&\forall a,i,j\\
&\equiv \quad\neg \...
- 12.9k
10
votes
MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$
Assuming $x_i$ variables are binary, the contraposition reads as follows:
$$
\delta = 0 \implies \left( \sum_{i=1}^n x_i \le 1 \right)\vee \left( \sum_{i=1}^n x_i \ge 3 \right)
$$
Define a binary ...
- 12.9k
10
votes
Binary logical constraint dependent on indices
You could convert to CNF.
$$(a = b) \implies (c = d)$$ can be expressed by:
$$0 \le a + b + c - d \le 2$$
$$0 \le a + b + d - c \le 2$$
- 232
9
votes
Accepted
Binary logical constraint dependent on indices
You can enforce $X_t=X_{t-1}\implies Y_{it}=Y_{it-1}$ with additional binary variables $\omega_{0t},\omega_{1t},\omega_{2t}$ as follows:
\begin{align}
X_t+X_{t-1}&=0\omega_{0t}+1\omega_{1t}+2\...
- 12.9k
9
votes
Accepted
How to reduce an LP problem already in its standard form?
Concept
The tools you are referring to are commonly called presolvers.
Resources (Implementation) / Availability
Every optimization software makes use of those (to improve performance, but also ...
- 446
8
votes
Accepted
Doubles Round Robin Sorting Algorithm
You can solve this with an integer programming model. I will omit the objective function, since any feasible solution produces a viable schedule. You might give some thought to whether there is a ...
- 37.8k
8
votes
Runtime of LP vs MILP
At the risk of offending someone by oversimplifying, NP-hard basically means that the amount of time to solve a model instance can grow faster than any polynomial function of the model size (number of ...
- 37.8k
8
votes
How can I find the shortest path visiting all nodes in a connected graph as MILP?
You can solve this problem by transforming to a TSP in a complete graph where the edge weights are the shortest-path distances in the original graph. So it is three steps:
Compute all-pairs shortest ...
- 30.4k
7
votes
Accepted
Summation of Binary Variables Pushing a Binary Variable
\begin{align}
\sum_k n_{jk} &= 1 &&\text{for all $j$} \tag1\label1 \\
\sum_k k n_{jk} &= \sum_i x_{ij} &&\text{for all $j$} \tag2\label2
\end{align}
Constraint \eqref{1} ...
- 30.4k
7
votes
Accepted
How to model $C_1=C_2$ implies $b_1 = b_2$
Equivalently, you want to enforce the contrapositive
$$b_1 \not= b_2 \implies C_1 \not= C_2$$
Because the $b_i$ are binary, this is the same as
$$b_1 + b_2 = 1 \implies C_1 \not= C_2$$
Let $\epsilon&...
- 30.4k
7
votes
Accepted
Writing a constraint of an integer programming in a linear form
Introduce a binary decision variable $y_j$ to represent the product $t_j x_j$. The usual linearization would use three linear constraints to enforce this relationship. But here, because $T\ge 0$, we ...
- 30.4k
7
votes
Rewriting if-then constraints of binary summations
@Kuifje gave a correct formulation without introducing additional variables. To answer your question about the indicator variable approach, what you proposed is not correct.
To enforce $$\sum_b x_{i,j}...
- 30.4k
7
votes
Is Benders decomposition and the L-shaped method the same algorithm?
In the paper that proposed L-shaped method, you can find
In section 2, an algorithm which is essentially the same as the
algorithm developed by Benders[3] is described and a geometric
interpretation ...
- 702
6
votes
pseudocode to convert english to constraint
I tried chatGPT with my Zoo, bus and optimization example.
and I got
and then
- 3,990
6
votes
Accepted
MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$
Assuming you also want to enforce the converse, here’s another approach that uses the same additional binary variables $y_1$ and $y_2$ as in @Kuifje’s answer.
$$
y_1+\delta+y_2=1\\
0y_1+2\delta+3y_2\...
- 30.4k
6
votes
Implementing Heuristic Callback in CPLEX C++ API for MILP
Disclaimer: It's been a while since I used Cplex' C++ API.
According to your question, you probably rather want to use a generic callback and inject a feasible (heuristic) solution through ...
- 1,477
6
votes
Is this constraint with an indicator function nonlinear?
Indicator constraints are not linear constraints, but here’s a linearization with binary variables $z_i$:
\begin{align}
\sum_i z_i &= 1 \\
\sum_i i z_i &= y \\
\sum_i c_i z_i &= x
\end{...
- 30.4k
6
votes
Accepted
How to partition a giant tour into feasible routes?
Here’s a MILP formulation to partition an Eulerian graph into $K$ Eulerian subgraphs, with an objective of minimizing the maximum cost. Let binary decision variable $x_{ijk}$ indicate whether edge $(...
- 30.4k
6
votes
Accepted
Of what size should I expect to be able to solve an integer linear program with Pyomo?
This very much depends on the solver (glpk) and not so much on the modelling language (Pyomo). In my experience, glpk is not among the best free ILP solvers. You may try cbc, which I think is somewhat ...
- 6,352
6
votes
Accepted
Linearize conditional constraint
It might help to consider the contrapositives:
\begin{align}
x=0 &\implies c\le 0 \\
x=1 &\implies c\ge 1
\end{align}
Both of these are indicator constraints, which you can linearize via big-M:...
- 30.4k
6
votes
Accepted
Quantifying a measure of standard deviation in MILP
A couple of options come to mind. Let $w_s$ be a variable representing the number of workers during shift $s.$ You can introduce nonnegative variables $y$ and $z$ to represent the minimum and maximum ...
- 37.8k
6
votes
Accepted
How can I formulate this 'if-then' constraint problem?
Here is one option: first define $x_i$ with binaries:
\begin{align}
x_i&=y_i^1+2y_i^2+3y_i^3 \\
1&=y_i^1+y_i^2+y_i^3 \\
y_i^j &\in \{0,1\}
\end{align}
You can enforce $x_0=2 \implies 1 \in ...
- 12.9k
6
votes
Accepted
Graph coloring problem redundant constraints
Search for symmetry breaking constraints. Here's a small but common example: https://math.stackexchange.com/questions/4415333/assymetric-graph-coloring-formulation
Fix some variables. E.g. Greedily ...
- 3,396
6
votes
Accepted
How can I find the shortest path visiting all nodes in a connected graph as MILP?
My first thought was Rob's model, but for what it's worth here is an alternative formulation that does not require solving a bunch of shortest path problems at the outset. Whether it is faster or not ...
- 37.8k
5
votes
Accepted
Implementing Heuristic Callback in CPLEX C++ API for MILP
As @Joni notes, there is a parameter that controls how much (if any) effort CPLEX spends checking solutions you supply.
You can freely mix integer and continuous variables in the call to setSolution, ...
- 37.8k
5
votes
Accepted
Expressing $\{0,1\}$ assignment across a matrix in MILP?
Okay...
$\sum_{i=1}^n V_{seat,i} \le seatvars_{seat} \quad \forall seat \in\ $seatVars
Looping 'for' in done by $\forall$
- 3,343
5
votes
How to model not-met demand to next period?
An easy approach is the following. Assuming $X_t$ the production at period $t$ and $d_t$ the demand at period $t$, create a new variable $F_t$ to store how much demand cannot be satisfied. Then, ...
5
votes
Accepted
Is this constraint with an indicator function nonlinear?
Since the constraint includes binaries, it does not define a convex set, and is therefore not linear.
For example, if $x=c_11_{A}$, $x$ can take values either $0$ or $c_1$. But $\frac{0+c_1}{2} \notin ...
- 12.9k
5
votes
Robust optimization for IP formulation
I think this is a relatively easy but still general paper to start with: https://arxiv.org/pdf/1501.02634.pdf
- 191
5
votes
Accepted
Modelling if elif else conditions as MIP
For the first part, let $Ul6$ and $Us6$ be upper bounds on $Pl6$ and $Ps6$, respectively, and impose linear constraints:
\begin{align}
Xl6 \le Pl6 &\le Ul6 Xl6 \\
Xs6 \le Ps6 &\le Us6 Xs6
\end{...
- 30.4k
Only top scored, non community-wiki answers of a minimum length are eligible