Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
50
questions
6
votes
1answer
121 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(...
1
vote
1answer
54 views
$i \neq j$ as a linear constraint where variables are binary
Let $i$ and $j$ be two binary variables.
How can I express $i \neq j$ as a linear constraint?
5
votes
3answers
910 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 ...
1
vote
1answer
66 views
How to model this chain of logical implication II
I would like to seek some advice on modeling the following (chain of) logical implication:
For instance $\omega_{xz}$ might indicate precedence, i.e., $x$, $z$ being the nodes $x$ and $z$, ...
3
votes
2answers
132 views
How to get an extreme ray of an LP from Gurobi
I am working on a problem of form
\begin{equation}
\begin{array}{l @{\quad} l}
\mathrm{max}_{x, u} & p^{\top} u
\\
\text{st.} & A u + a x \leq 0
\\
& x \in \{0, 1\...
1
vote
1answer
57 views
How to model this chain of logical implication
I would like to seek some advice on modeling the following (chain of) logical implication:
For instance $\omega_{xy}$ might indicate precedence, i.e., $x$, $y$ being the nodes $x$ and $y$, ...
3
votes
0answers
65 views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
2
votes
0answers
34 views
Interger programming using gray encoding
Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
0
votes
0answers
36 views
Linearizing max constraint Problem [duplicate]
I want to linearize a max constraint as below:
In which x_(i,t),are binary decision variables and T is a constant.
How can I linearize this constraint?
2
votes
1answer
55 views
Formulating indicator constraint set
I am having difficulty formulating the indicator constraints for the following:
Consider a set of $A_{n}$ decision variables such that $A_{1},A_{2},⋯,A_{n}<A$. While all of them are integers that ...
3
votes
1answer
114 views
Logical constraint in ILP
I want to write the following constraint:
Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows:
if $z \...
5
votes
2answers
145 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 ...
4
votes
1answer
54 views
Linearizing separable functions: SOS2 sets or binary variables
When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?
6
votes
1answer
104 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 ...
4
votes
1answer
53 views
Maximizing 1-norm: using binary variables to relax non-convexity
It is well-known that when we maximize a 1-norm, e.g., $\|Ax\|_1$, we can use binary variables and obtain a mixed-integer convex problem (otherwise maximizing 1-norm is non-convex). I am mentioning ...
5
votes
1answer
322 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 ...
4
votes
2answers
168 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 \ \ \...
3
votes
1answer
115 views
Modeling the sum of binary variables
Suppose $x_{1},x_{2}, \cdots ,x_{n}$ are binaries.
I would like to model the following:
IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 2$ THEN $x_{1} + x_{2} = 2$
IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 3$ ...
3
votes
1answer
103 views
How to define hybrid variables without using additional binary variables?
I am working on a large NLP model with equilibrium equations in which the variables are defined in the following form:
$$x_i \in [L_B, U_B] \cup\{0\} \quad \text{where} \quad L_B \ \& \ U_B \in\...
2
votes
1answer
76 views
Same values constraint and grouping of variables
In a linear program, I would like some variables to:
1. Take the same values
2. Group some variables i.e. some variables should take same values or lie within certain percentage.
3. All different ...
2
votes
1answer
77 views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
5
votes
3answers
80 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_{...
3
votes
1answer
158 views
Approximation methods for a mixed integer convex optimization problem
I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.
I am currently aware of AIMMS'...
9
votes
3answers
459 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 ...
4
votes
1answer
54 views
Find the number of idle intervals with weights
We have one job $i$ and one machine. Let $\mathbf{x}_i=[x_{i,1},x_{i,2},\ldots,x_{i,T}]$ be a binary vector where $x_{i,t}=1\iff$ job $i$ is scheduled at time $t$. Let $u$ be a positive number. I ...
6
votes
2answers
2k 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 ...
5
votes
2answers
264 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 ...
-4
votes
2answers
100 views
How can I model this binary logic?
I am looking for a constraint to express the following:
IF W1 = 0 AND W2 = 0 THEN Y = 0
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
2answers
207 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
...
5
votes
1answer
520 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}...
8
votes
1answer
115 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 ...
13
votes
2answers
810 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 ...
8
votes
2answers
299 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 ...
12
votes
0answers
160 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&\...
10
votes
3answers
444 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 ...
7
votes
1answer
129 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 $\...
8
votes
1answer
516 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 ...
6
votes
2answers
315 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'}}_{,...
14
votes
4answers
258 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 ...
9
votes
1answer
107 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
1answer
213 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....
8
votes
1answer
773 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 ...
9
votes
1answer
95 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$...
6
votes
1answer
128 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 ...
12
votes
1answer
435 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\...
7
votes
2answers
361 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 ...
16
votes
3answers
684 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 ...
16
votes
2answers
199 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 ...
27
votes
1answer
3k 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$?
30
votes
2answers
4k 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$?
