Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
59
questions
2
votes
1answer
62 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 ...
2
votes
1answer
57 views
Finding the minimum of a group of timings
I would like to seek some modeling advice on the following:
Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two ...
0
votes
1answer
105 views
Is it known that any boolean function is equivalent, in some sense, to a system of linear inequalities?
I cannot believe that below is a "fresh result" in mathematical programming as my rather intensive literature search did not bring references to any similar assertions. I will appreciate any ...
2
votes
1answer
92 views
How to deal with log0 in optimization problem
I am adding some constraints to my model described in my previous post, where a discontinuous piecewise-quadratic functions is the objective to be minimized in cvx.
Here I have an additional terms, ...
2
votes
1answer
51 views
Constraints that set values to binary variables depending on other binaries
I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on ...
1
vote
1answer
126 views
How to linearize the product of a binary and a continuous variable? [duplicate]
Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
3
votes
0answers
102 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 ...
4
votes
2answers
425 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}=...
2
votes
1answer
48 views
Logical equivalencies to modeling an indicator decision variable in transportation problem
I am formulating a model that seeks to minimize the cost of shipping goods from factories to warehouses, where the cost of shipping is independent of the type or amount of goods being shipped (except ...
6
votes
1answer
130 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
58 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
922 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
75 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
169 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
60 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$, ...
2
votes
0answers
75 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}_+$ ...
0
votes
0answers
36 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
39 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
62 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
123 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 \...
4
votes
3answers
195 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 ...
3
votes
1answer
66 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?
5
votes
1answer
105 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
58 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
329 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
182 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
129 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
120 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
92 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
95 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
86 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
169 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
461 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
55 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
268 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
101 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
209 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
531 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
133 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
829 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
335 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
168 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&\...
9
votes
3answers
456 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
130 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
629 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 ...
5
votes
2answers
393 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
279 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
110 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
214 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....
