Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
161
questions
37
votes
3
answers
16k
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$?
36
votes
2
answers
11k
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$?
18
votes
3
answers
3k
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 ...
17
votes
2
answers
498
views
Can we replace a binary variable with a continuous variable using a quadratic equality constraint?
Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$?
The function $f(x) = x^2 -x$ is not a convex function. Can ...
14
votes
4
answers
682
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 ...
14
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 ...
14
votes
1
answer
296
views
Integrality gap in bilevel binary linear programming problem
I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is
$$
\begin{alignat}2
\min\limits_x&\...
13
votes
1
answer
888
views
Representing an indicator function: binary variables and "indicator constraints"
I want to represent the indicator function:
$$ \mathbb{1}_{(y=j)}$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =\begin{cases}
1 \qquad\...
9
votes
3
answers
483
views
Is there a better way to formulate this constraint?
Let $x_{r}^{j}=1\iff$ the machine schedules job $j$ using resource $r$. My constraint says that: a resource cannot be used twice, i.e., if $x_{r}^{j}=1$, then $x_{r}^{j'}=0$ for $j'\neq j$. I write ...
9
votes
3
answers
788
views
Interval variables in MIP
In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example.
Is there ...
9
votes
2
answers
925
views
How can I transform this MILP into an LP problem?
I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
9
votes
1
answer
201
views
Binary variable to count appearances
Let $x \in \mathbb{R}^n$ be an optimization variable. Now, at a constraint, I would like to count how many times a value, say $2$, appears in $x$ decision.
I think we can have a binary variable $y_i$...
9
votes
1
answer
182
views
Constraint to state the relation between 2 binary variables
I'm trying to deal with a process planning and machine layout allocation simultaneously.
I have the following variables:
$X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a ...
9
votes
1
answer
282
views
Should I factor in time as a parameter or a variable in a scheduling problem with MILP?
I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
9
votes
1
answer
680
views
Complexity comparision between purely BLP and MILP problems?
Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)?
In MILP, we have both binary and continuous variables ...
8
votes
1
answer
317
views
Formulating two non-negative variables without binary and/or big-M
There are two non-negative integer variables $q$ and $p$, where only one of them can take a positive value. To impose this relation, I write:
\begin{align}
q &\leq M(1 - y) \tag1 \\
p &\leq M(...
8
votes
1
answer
2k
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 ...
7
votes
3
answers
738
views
Binary logical constraint dependent on indices
I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.
I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to ...
7
votes
2
answers
489
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 ...
7
votes
3
answers
492
views
Profit Maximization LP and Incentives Scenarios
I wrote a profit maximization LP with inventory, component usage, production, and machine hours constraints. When I optimize the model, it solves as expected. When applied towards a business case, ...
7
votes
1
answer
153
views
Help with formulating an implication
I have a binary variable $y$ and a set of binary variables $x_i$, where $i\in I$.
My problem requires that $$\sum\limits_{i\in I}x_i = b.$$
What I want to formulate is the following implication: if $\...
7
votes
1
answer
2k
views
Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?
I'm trying to create an assignment optimization model where the areas are assigned to either the south or north school districts so that the total distance is minimized. Each school must have at least ...
7
votes
1
answer
640
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 ...
7
votes
1
answer
480
views
Bilinear programming vs Mixed integer linear programming performance comparison
I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, ...
7
votes
1
answer
626
views
How can one model a binary variable?
I am looking for the formulation of a constraint that does the following. I want to introduce a new binary variable $\kappa_{it}$ that takes the value 1 if the sum of the other binary variable $\...
7
votes
1
answer
304
views
BIP for Sudoku naturally integral?
I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program
https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf
The formulation is straightforward ...
6
votes
3
answers
2k
views
How do you take into account order in linear programming?
How do you write order in a linear program?
For instance, you want to arrange red and blue marbles labelled 1 ā 30 each, and you would want to arrange it in ascending order, you cannot have red ...
6
votes
2
answers
4k
views
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
I'm trying to model the following
IF $tS = 0$ THEN $Y = 1$, IF $tS \gt 0$ THEN $Y \ge 0$
$tS$ is a positive real number and $Y$ is binary.
I tried the following:
$tS - \epsilon \ge -M Y$ but ...
6
votes
2
answers
273
views
How can this be expressed as a MILP constraint?
I am looking for a constraint to express the following:
IF W1 = 0 AND W2 = 0 THEN Y = 1
IF W1 = 0 AND W2 = 1 THEN Y = 1
IF W1 = 1 AND W2 = 0 THEN Y = 0
IF W1 = 1 AND W2 = 1 THEN Y <= 1
...
6
votes
1
answer
392
views
Binary variable switch constraints
I have a set of binary variables $X = \{ x_1, x_2, x_3, ... x_N \}$ which are connect and used with the rest of the model.
I want to define a set of binary variables which represents the change ...
6
votes
2
answers
99
views
If $t\le0$ then $P=1$, if $t > 0$ then $P =0$ or $P=1$
I am trying to model $t \leq 0.0 \implies P = 1.0$ else $P=1$ or $P=0$ where $0 \leq t \leq H$ is a bounded nonnegative real, and $P$ is binary.
I can use the expression $t + \epsilon P \ge \epsilon$ ...
6
votes
2
answers
2k
views
0 1 solution of linear programming problem with only equality constraints
I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
6
votes
1
answer
213
views
Obtaining the intermediate solutions in AMPL
I know that for some solvers, for example, the constraint programming solver in Google OR-Tools, it is possible to see all the intermediate solutions that the solver finds while it searches for an ...
5
votes
3
answers
3k
views
How to represent an integer variable via binary variables?
Suppose we have a model with $N$ integer variables, i.e. $x \in \mathbb{Z}^{N}$ with $L \leq x \leq U$.
How can we represent the integer variables via binary variables? Or in other words: how can we ...
5
votes
3
answers
708
views
Constraint for two binary vectors to be different
If I have a matrix $A$ of binary variables $a_{i,j}$, $1 \le i \le n$, $1 \le j \le m$, how can I enforce in an Integer Linear Program with binary variables, the condition that every two columns must ...
5
votes
1
answer
385
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 ...
5
votes
3
answers
93
views
Requiring exactly $n_j$ slots for job $j$ (if scheduled)
Let $x_{j}(t)=1$ iff job $j$ is scheduled at time $t$. I want to say that if the job is scheduled at all, then it is scheduled at $n_j$ slots. I wrote this as:
$$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{...
5
votes
2
answers
401
views
Binary variable constraint
The task is to ensure that if $x_i = 1$ for at least $k$ of the possible indices $i$ in $\{1,...,n\}$ then $y = 1$, where $k$ and $n$ are parameters, $x$ is a binary variable vector with $n$ elements, ...
5
votes
2
answers
296
views
How can this relationship be modelled?
I declare an array of binary variables as $y(i), i = 1, ..., N$
I would like to model the following:
If $y(i-1) + y(i) = 1$ then $y(k) = 0$ for $k < i$ and $y(m) = 1$ for $m \geq i$
To make ...
5
votes
1
answer
619
views
How can I deal with a possibly undefined constraint?
I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal.
$$\min_{\mathbf{d}...
5
votes
1
answer
146
views
if $x = 0$ then $y \ne b$
I'm trying to model the following:
if $x=0$ then $y \ne b$
$y$ is a positive integer number( $y\le U$) and $x$ is binary and $b$ is a constant.
5
votes
1
answer
228
views
Constraints like "max(column a + column b) == 2" are not DCP
I am struggling with the following constraint on a minimization problem
cvx.max(z[:, i] + z[:, j]) == 2
where z is a Boolean ...
5
votes
2
answers
1k
views
How to establish constraint between variables with multiple indexes using CPLEX in Python
I am new in CPLEX and I am using docplex in Python to solve an ILP.
I would like to translate the following constraint in docplex:
$$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,...
5
votes
1
answer
152
views
Binary variable to indicate zero probabilities
I have a finite probability distribution $p_1, p_2, \ldots, p_n$ (but these are variables of an optimization problem). Moreover, we have monotonicity, $p_1 \geq p_2 \geq \cdots \geq p_n$.
Assume we ...
5
votes
1
answer
159
views
Minimize binary variable's distance with respect to the index values
For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values:
$d ...
5
votes
1
answer
136
views
What fraction of the search space has been searched for ILP?
Is there a way to make Gurobi output (an estimate of) how much of the search space has already been cut off as infeasible?
If not with Gurobi are you aware of any binary only (912 of them) ILP solver ...
4
votes
2
answers
1k
views
How can we write a binary variable as a power to a constant number?
Let $x_{i,j}$ be a two-dimensional binary variable.
Is it possible to write $x_{i,j}$ as a power to a number?
For example:
$$1- 0.3^{x_{i,j}} $$
4
votes
2
answers
480
views
Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously
I would like to seek some advice on modeling the following logical condition:
I would like to ensure that a group of binary variables do not equate to 1 simultaneously, i.e., $\omega_{1}=1, \omega_{2}=...
4
votes
2
answers
296
views
Conditional Constraint in MIP
I need to formulate a conditional constraint for a binary variable z defined as:
$z_{i,j,k}$, $\ \ i=1:10 \ , \ j=1:5 \ , \ k=1:3$
If any $z_{i,j,3} = 1$ then $z_{i,j,1} + z_{i,j,2} = 0 \ \ \...
4
votes
3
answers
806
views
Faster implementation of "or" constraints in ILP
I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...