RobPratt
  • Member for 2 years, 7 months
  • Last seen this week
  • NC, USA
How to linearize the product of two binary variables?
19 votes

It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \...

View answer
Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?
17 votes

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

View answer
TSP with revenue maximization
17 votes

Search for orienteering problem or prize-collecting TSP.

View answer
How to linearize membership in a finite set
Accepted answer
16 votes

First, some special cases: If $S=\{c\}$, fix $x=c$. If $S=\{0,1\}$, declare $x$ to be binary. If $S=\{a,b\}\not=\{0,1\}$, introduce binary variable $y$ and impose linear constraint $x=a(1-y)+by$. If $...

View answer
Expressing a chain of boolean ORs using ILP
Accepted answer
16 votes

Derivation via conjunctive normal form: \begin{equation} x_1 \implies \underset{i=2}{\overset n{\lor}} x_i \\ \neg x_1 \bigvee \underset{i=2}{\overset n{\lor}} x_i \\ 1 - x_1 + \sum_{i=2}^n x_i \ge 1 \...

View answer
Bin Packing with Relational Penalization
Accepted answer
14 votes

Here is a simpler symmetry-less formulation based on the one proposed by @RenaudM. For $i \le j$, let binary variable $r_{i,j}$ indicate that the bin represented by item $i$ contains item $j$. (Here,...

View answer
Why isn't $x_2+x_3+x_4\le 2$ a cutting plane?
Accepted answer
13 votes

It is a cutting plane, but it is implied by $x_2+x_4\le 1$ and $x_3\le 1$ so not very useful.

View answer
MILP - stronger models
Accepted answer
12 votes

Version (1) arises from conjunctive normal form as follows: $$ y \implies (x_1 \land x_2 \land x_3) \\ \lnot y \lor (x_1 \land x_2 \land x_3) \\ (\lnot y \lor x_1) \land (\lnot y \lor x_2) \land (\...

View answer
Standard cumulative distribution function with optimization model variable
Accepted answer
12 votes

For strictly increasing CDFs, you can invert: $$x \le \Phi^{-1}(b)$$

View answer
Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem? (ILP)?
11 votes

Equivalently, you want to remove the smallest number of constraints so that the resulting problem is feasible. You can do this implicitly, without enumerating all Irreducible Infeasible Sets, by ...

View answer
Name for this ILP problem type
Accepted answer
11 votes

This is called the budgeted maximum coverage problem.

View answer
Gurobi: how to add a constraint to make there be only one non-integer value
11 votes

Let $x_{p,\ell}$ be the continuous variables in your table. Introduce integer variables $y_{p,\ell}$ and binary variables $z_{p,\ell}$, and impose linear constraints \begin{align} -z_{p,\ell} \le x_{...

View answer
How to linearize a constraint with a maximum of a linear function
Accepted answer
11 votes

You can model the logical implication $$Cx < d \implies \bigvee_{i=1}^m \left(a_i^T x \ge b_i\right)$$ by introducing $m+1$ binary variables $y_i$, where $i\in\{0,\dots,m\}$, and linear constraints ...

View answer
Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only
Accepted answer
11 votes

Rather than solving this directly as MIQCQP, you might consider linearizing the products $y_{ij} x_{ij}$, as shown here, yielding instead an MILP problem.

View answer
How to partition a graph with optimal number of groups?
Accepted answer
11 votes

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ ...

View answer
Linearize x different of y in ILP
Accepted answer
11 votes

I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint $(1)$ enforces $z=0 \implies x + ...

View answer
How to model bicycle sharing scheme?
Accepted answer
11 votes

Daniel Freund, Shane G. Henderson, Eoin O'Mahony, and David B. Shmoys won the 2018 Wagner Prize for their work on this problem. This link gives lots of info, including a video presentation: https://...

View answer
Is there a better way to formulate this constraint?
Accepted answer
11 votes

You can strengthen your "conflict" constraint to a "clique" constraint: $$\sum_j x_r^j \le 1$$ for all $r$. There are fewer of these, and they dominate the conflict constraints.

View answer
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
Accepted answer
11 votes

Your second if-then statement is always true because $Y$ is binary. For your first if-then statement, rewrite as its contrapositive $Y=0 \implies tS \ge \epsilon$. The following big-M constraint ...

View answer
MIP: If integer variable $>0$ it should be equal to other integer variables $>0$
Accepted answer
11 votes

Let $b_n$ be a binary indicator variable, and let integer variable $y$ be the common value of the positive $x_n$. Then you want to enforce $x_n=b_n y$, which you can linearize using the formulation ...

View answer
Help with formulating an implication
Accepted answer
11 votes

$x_i \le y$ for $i\in I \setminus \tilde{I}$

View answer
Expressing a chain of boolean ORs using ILP involving different variables
Accepted answer
11 votes

Let $P$ be the set of $(i,j)$ pairs. Here’s a derivation via conjunctive normal form: \begin{equation} \bigvee_{(i,j)\in P} \left(x_i \implies x_j\right) \\ \bigvee_{(i,j)\in P} \left(\neg x_i \vee ...

View answer
Best model for precedence constraints within scheduling problem
11 votes

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_{j_1,t_1}+s_{j_2,t_2}\le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$\sum_{t\ge t_1}s_{j_1,t}...

View answer
Tightness of an LP relaxation without using objective function
11 votes

If the integer feasible set is finite and the LP polyhedron is bounded (a polytope), you could compare the volumes of the integer hull and this polytope.

View answer
When is a formulation with min function an ILP problem?
Accepted answer
10 votes

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

View answer
How to model: If $X\ge\epsilon$ then $X\ge Y$
Accepted answer
10 votes

Introduce binary variable $Z$ and linear constraints \begin{align} X - \epsilon &\le (\bar{X} - \epsilon) Z \tag1 \\ Y - X &\le (\bar{Y} - 0) (1-Z) \tag2 \\ \end{align} Constraint $(1)$ ...

View answer
Which linearisation technique is correct?
Accepted answer
10 votes

They are equivalent except when $x_{i,g}=x_{j,g}=0$, in which case the second linearization incorrectly contributes $-d_{ij}$ to the objective. Assuming $d_{ij} \ge 0$, I recommend a third ...

View answer
How can I strengthen a family of constraints in the presence of a clique constraint?
Accepted answer
10 votes

Consider the only two possible cases: If $x_i=0$ for all $i$, then $(1)$ and $(3)$ both reduce to $\sum_j a_j y_j \le b$. If $x_i=1$ for some $i$, then $(2)$ implies that $x_k=0$ for all other $k \...

View answer
What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?
10 votes

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with ...

View answer
Formulating two non-negative variables without binary and/or big-M
Accepted answer
10 votes

The big-M values need not be the same. You should choose $M_1$ in $(1)$ to be a small upper bound on $q$ and $M_2$ in $(2)$ to be a small upper bound on $p$. An alternative formulation is $p q = 0$, ...

View answer
1
2 3 4 5
10