# Tag Info

Accepted

• 12.9k

### 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

### 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
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
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
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

### 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

### 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
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
Accepted

• 30.4k
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
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
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
Accepted

• 12.9k

### 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
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{...