56 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, ...
Michiel uit het Broek's user avatar
38 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 ...
Michiel uit het Broek's user avatar
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 \...
RobPratt's user avatar
  • 32k
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 ...
Marco Lübbecke's user avatar
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....
RobPratt's user avatar
  • 32k
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 ...
JakobS's user avatar
  • 2,757
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. ...
Marco Lübbecke's user avatar
12 votes
Accepted

Help with formulating an implication

$x_i \le y$ for $i\in I \setminus \tilde{I}$
RobPratt's user avatar
  • 32k
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 ...
Kevin Dalmeijer's user avatar
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 ...
RobPratt's user avatar
  • 32k
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.
RobPratt's user avatar
  • 32k
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 > ...
LarrySnyder610's user avatar
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$, ...
RobPratt's user avatar
  • 32k
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 \...
joni's user avatar
  • 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 ...
RobPratt's user avatar
  • 32k
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$$
user1502040's user avatar
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.
RobPratt's user avatar
  • 32k
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$
Mason's user avatar
  • 515
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)...
Kuifje's user avatar
  • 13.3k
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 ...
RobPratt's user avatar
  • 32k
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\...
Kuifje's user avatar
  • 13.3k
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$ ...
RobPratt's user avatar
  • 32k
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 ...
prubin's user avatar
  • 39.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 ...
prubin's user avatar
  • 39.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,...
Kevin Dalmeijer's user avatar
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 ...
brentertainer's user avatar
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.
RobPratt's user avatar
  • 32k
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 ...
Kuifje's user avatar
  • 13.3k
8 votes

Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$ \lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \...
RobPratt's user avatar
  • 32k
8 votes

References to publications on representation of any boolean function as a system of linear inequalities

If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}...
RobPratt's user avatar
  • 32k

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