57
votes
Accepted
How to linearize the product of two binary variables?
This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, ...
- 2,551
40
votes
Accepted
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we can give a finite upper bound for $y$ called $M$. Then this constraint can easily be linearized by using the so-called big $M$ method. We introduce a new variable $z$ that should take the ...
- 2,551
25
votes
How to linearize the product of two binary variables?
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 \...
- 33.5k
20
votes
Accepted
How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?
I learned very early (this may not be generally true) that I should always prefer binary over integer variables. A reason is that from binary values you can infer logical information, branching on a ...
- 5,949
15
votes
How can we write a binary variable as a power to a constant number?
If you check the two cases for $x_{i,j}$, you will see that you can rewrite the expression as a linear function of $x_{i,j}$:
$x_{i,j}=0$ yields $1-0.3^0=0$
$x_{i,j}=1$ yields $1-0.3^1=0.7$
So $1-0....
- 33.5k
14
votes
Does this $0-1$ integer program have any speciality?
In general no, these problems are hard. BUT: You might want to look into totally unimodular matrices and total dual integrality but this requires additional assumptions on the matrix or the problem ...
- 2,767
13
votes
Accepted
Polynomially solvable cases of zero-one programming
First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases.
...
- 5,949
12
votes
Accepted
11
votes
Accepted
Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?
Instead of
$$\frac{\textrm{Total school income}}{\textrm{Number of areas}} \ge \$ 85000$$
you could have a constraint
$$\textrm{Total school income} \ge \$ 85000 \times \textrm{Number of areas}.$$
In ...
- 6,362
11
votes
Accepted
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
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 ...
- 33.5k
11
votes
Accepted
Is there a better way to formulate this constraint?
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.
- 33.5k
11
votes
How do you take into account order in linear programming?
Presumably you have binary decision variables like $x_{ik} = 1$ if marble #$i$ is in slot #$k$. Then you can write a constraint like
$$x_{ik} \le 1 - x_{jl} \qquad \forall \text{$i < j$ and $k > ...
- 13.2k
11
votes
Accepted
Formulating two non-negative variables without binary and/or big-M
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$, ...
- 33.5k
11
votes
Accepted
How to represent an integer variable via binary variables?
I'm not entirely sure if this is the most elegant way to model things, but here's how integer numbers are represented in a computer:
Let's take an integer variable $x \in \mathbb{Z}$ with $L \leq x \...
- 1,572
11
votes
Constraint for two binary vectors to be different
Let binary decision variable $x_{ijk}$ indicate whether columns $j$ and $k$ (with $j<k$) differ in row $i$, and impose linear constraints
\begin{align}
\sum_i x_{ijk} &\ge 1 &&\text{for ...
- 33.5k
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$$
- 242
9
votes
Accepted
Does this $0-1$ integer program have any speciality?
With binary $b$, it is called a set packing problem: https://en.m.wikipedia.org/wiki/Set_packing
With integer $b$, it is called a generalized set packing problem.
- 33.5k
9
votes
Is there a better way to formulate this constraint?
Same idea, but typically formulated as
$$\sum_j x_r^j \leq 1, \: \forall r$$
For binary $x$
- 525
9
votes
How to represent an integer variable via binary variables?
You can stay in base $10$ with a similar approach as @joni:
introduce $m=U-L+1$ binary variables $y_i$, one for each integer value in the range $[L,U]$, and write $x$ as follows:
$$
x= L y_1 + (L+1)...
- 13.7k
9
votes
How to construct my mixed integer programming problem with constraint of minimum consecutive ones
Define a two sets of binary variables : variables $x_i$ take value $1$ if and only if the $i^{th}$ term of the sequence equals $1$, and variable $y$ that takes value $1$ if and only if one of the ...
- 13.7k
9
votes
How to model this binary constraint?
Let $x_{i,j}$ be your binary decision variable. The “at most 20 resources” constraint is $\sum_j x_{i,j} \le 20$ for each row $i$. One way to enforce contiguity is to introduce another binary decision ...
- 33.5k
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\...
- 13.7k
8
votes
How can I transform this MILP into an LP problem?
These conflict constraints can be replaced with clique constraints of the form $$\sum_{n\in C} z_{n,m}\le 1 \quad \text{for all $m$},$$ where each $C$ is a clique in the graph with nodes $1,\dots,N$ ...
- 33.5k
8
votes
Binary variable to count appearances
As LarrySnyder610 said, you cannot do exactly what you want when $x_i$ is continuous. (You can if it is an integer variable.) I discussed how to model this particular issue here: Flagging a Specific ...
- 40.1k
8
votes
How can I linearize or convexify this binary quadratic optimization problem?
Kevin Dalmeijer's answer is correct for the general case. Since $A$ is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a ...
- 40.1k
8
votes
Accepted
How can I linearize or convexify this binary quadratic optimization problem?
The constraints
$${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$
can be rewritten as
$$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$
Next, you can linearize each of the $U(i,...
- 6,362
8
votes
What are some real-world applications of QUBO?
1QBit published a white paper "Optimal feature selection in credit scoring and classification using a quantum annealer". The authors compare their feature selecting QUBO model to mainstream recursive ...
- 333
8
votes
Accepted
How can I deal with a possibly undefined constraint?
Multiply both sides of your $d_k \ge$ constraint by the denominator and then linearize $d_k y_{ijk}^+$ and $d_k y_{ijk}^-$ as described in this thread.
- 33.5k
8
votes
Faster implementation of "or" constraints in ILP
Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are ...
- 33.5k
8
votes
Accepted
Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously
How about
$$\omega_1 + \cdots + \omega_n \le n-1 $$
This way, at most all variables but one of them can take value $1$ simultaneously.
In the context of knapsack problems, if each variable models the ...
- 13.7k
Only top scored, non community-wiki answers of a minimum length are eligible