# Tag Info

Accepted

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

### 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$$
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\...
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 ...
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 ...

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

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

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 ...
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:...
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 ...
Accepted

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 ... 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 ... 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 ... 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, ... 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$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 ...
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{...