Questions tagged [binary-variable]

For questions that involve variables than can only take on one of two values, usually 0 or 1.

Filter by
Sorted by
Tagged with
32 votes
2 answers
8k views

How to linearize the product of two binary variables?

Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
user avatar
31 votes
1 answer
6k views

How to linearize the product of a binary and a non-negative continuous variable?

Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
user avatar
18 votes
3 answers
1k views

What are some real-world applications of QUBO?

QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables. It has been used for computer vision, Ramsey numbers, factoring numbers, the ...
user avatar
  • 1,246
13 votes
2 answers
1k views

How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$. Is ...
user avatar
  • 141
7 votes
1 answer
190 views

How to construct my mixed integer programming problem with constraint of minimum consecutive ones

My target is to formulate a binary sequence with fixed size $N$ = 10, such as $[1, 0, 0, 0 ,1, 1, 0, 1, 0, 0]$. However, I want to constrain this sequence so that when 1 appears, it has to appear at ...
user avatar
8 votes
1 answer
1k views

How to linearize the multiplication of an integer and a binary integer variable?

I have the following constraints \begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
user avatar
5 votes
1 answer
348 views

Polynomially solvable cases of zero-one programming

I am dealing with a problem having two types of variables: binary variables, and continuous variables. In some cases, the continuous variables are not used, and so the problem contains those binary ...
user avatar
  • 2,034
4 votes
3 answers
245 views

How to couple a binary variable to a continuous variable to indicate values greater 0

I have a continuous variable $x_t$. A binary variable $b_t$ should be coupled to $x_t$ such that $b_t$ has the value $1$ if $x_t$ has a value greater than $0$ and $b_t$ has the value $0$ if $x_t$ has ...
user avatar
  • 1,546
14 votes
4 answers
403 views

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

Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers, $$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
user avatar
7 votes
2 answers
405 views

How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint. $\max \eta$ subject to ${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$ here $\bf{A}$ is a Binary ...
user avatar