47 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, ...
user avatar
32 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 ...
user avatar
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 ...
user avatar
19 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 \...
user avatar
  • 22.2k
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....
user avatar
  • 22.2k
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 ...
user avatar
  • 2,667
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. ...
user avatar
11 votes
Accepted

Help with formulating an implication

$x_i \le y$ for $i\in I \setminus \tilde{I}$
user avatar
  • 22.2k
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 ...
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 ...
user avatar
  • 22.2k
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.
user avatar
  • 22.2k
11 votes
Accepted

How to represent an integer variable via binary variables?

I'm not sure if this is the most elegant modelling way. However, this is exactly how integer numbers are represented in the computer: Let's consider one integer variable $x \in \mathbb{Z}$ with $L \...
user avatar
  • 1,192
10 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 > ...
user avatar
10 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$, ...
user avatar
  • 22.2k
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.
user avatar
  • 22.2k
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$
user avatar
  • 433
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$ ...
user avatar
  • 22.2k
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 ...
user avatar
  • 29.7k
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 ...
user avatar
  • 29.7k
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,...
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 ...
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.
user avatar
  • 22.2k
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 ...
user avatar
  • 10.2k
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 - \...
user avatar
  • 22.2k
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}...
user avatar
  • 22.2k
8 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)...
user avatar
  • 10.2k
8 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 ...
user avatar
  • 10.2k
7 votes

What are some real-world applications of QUBO?

In chapter 10 of his dissertation [1], Gabriel Tavares, talked about some real-world applications of QUBO. He also proposed a new approach to solve QUBOs by modifying some of the previously existed ...
user avatar
  • 8,290
7 votes
Accepted

Representing an indicator function: binary variables and "indicator constraints"

First question: Yes, your algebraic formulation is correct. Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader ...
user avatar
  • 29.7k
7 votes

Does this $0-1$ integer program have any speciality?

While this class of problems is still hard to solve (see the other answers for details), one speciality is that it has a trivial feasible solution $x=0$, which is not the case in general integer ...
user avatar

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