# Tag Info

## Hot answers tagged integer-programming

10

Your constraint is equivalent to $$x_i \le f(x_j) \quad \text{for j<i},$$ so it is linear if $f$ is linear.

9

Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of ...

8

An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume ...

4

Try adding valid constraints $$y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for (i,j) such that \hat{y}_i = 0 and j \in \tilde{V}\setminus\{i\}}$$ that enforce the logical implications $$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,... 4 Let us introduce binary variables y_{ij} along with the constraint y_{ij} + y_{ji} \le 1 for all i\neq j. Add the constraints$$x_j - x_i \le My_{ij}\quad \forall i\neq j, where $M$ is an upper bound on the difference between largest and smallest $x$ value. This ensures that $y_{ij}=1$ if $x_j > x_i$. The question does not indicate whether ties in ...

4

If you are looking for a way to ensure (in a MILP model) that a graph with $p$ nodes is connected, a common approach is to treat each edge as a pair of directed edges (adding flow variables $x_{ij}$ and $x_{ji}$ for each edge $(i,j)$, choose one node arbitrarily to have supply $p-1$ of a phantom commodity, and assign a demand of $1$ to every other node. You ...

3

Extending Robs answer slightly, taking into account that you asked about ILP (which I interpret as mixed-integer linear program), the constraint is MILP-representable as long as $f$ is MILP-representable (thus allowing you to have piecewise affine functions such as min/max/abs/general pwa etc)

1

Your question prompted me to suggest multiple answers, if you would like me to elaborate on one of them please tell me which one in a comment. Would be fine with $A_{ij}$ matrix which tells you if $x_i$ is before $x_j$ or otherwise, that would be a lot simpler to implement. If you don't have individual constraints on $x_1$, $x_2$ (they can be any employee, ...

Only top voted, non community-wiki answers of a minimum length are eligible