Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
89
questions
2
votes
2
answers
29
views
Modeling an either-or-constraint
We would like to model a constraint for an assignment problem that dictates that either assign a specific subset of nodes $I\subset\mathcal{I}$ to a specific subset of nodes $J\subset\mathcal{J}$, or ...
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}} $$
- 149
3
votes
1
answer
182
views
Meaning of infeasible model: unsuccessful solving for an IP model with binary variables
For fun, I have modeled the Union-closed sets conjecture for a universe of a given size into a problem with binary variables.
Each binary variable $x_k$ is the indicator of the set with elements ...
- 133
2
votes
1
answer
76
views
Binary/integer variables get real values in docplex
I have an MILP model, in which I am handling all Big M constraints with add_if_then constraints (following this topic). I generate this model only once (to save time) and solve it iteratively with ...
- 293
5
votes
1
answer
101
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 ...
- 3,776
2
votes
1
answer
78
views
Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary
I am formulating a MILP in which there is a continuous variable x and a binary variable $y$.
In the program formulation there are the following constraints:
$Ay\leq x \leq By$ (with $0\leq A\leq B$). ...
- 414
3
votes
1
answer
73
views
Are there examples where introducing clusters of binary variables provides a benefit for solving?
I have a larger model with a large number of binary variables among many others. For the purpose of this question, consider the effect that the binary variables impose on the model to be similar to ...
- 303
5
votes
1
answer
136
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 ...
- 533
1
vote
1
answer
74
views
Taking derivatives of objective function with a binary variable to find minimum
I transform my minimization problem into one with only an objective function (no constraints). I only have one variable, which is binary.
Can I derivate the objective and make it equal to 0 to find ...
- 313
2
votes
1
answer
52
views
Ensure that scheduled repeating maintenance has to be completed
I'm trying to model the scheduling of maintenance in some machines, and was wondering how I could ensure that, if maintenance is planned to start in period $t$, then it has to be carried out until ...
- 315
6
votes
1
answer
151
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 ...
- 63
3
votes
1
answer
228
views
Constraint on groups of variables
Assume a LP/MILP with a large number of variables.
It is easy to formulate constraints to group variables such that each variable in a group takes the same value, if we know which variables are in a ...
- 223
2
votes
1
answer
240
views
mixed integer programming with if then statement for two binary sequences
I have two random binary sequences of the same size, denoted as P1 and P2 respectively here. Let's say they are both the size of ten, like P1 = [1,0,1,1,0,0,0,1,1,1], P2 = [0,1,1,0,0,1,0,0,1,1]. I ...
- 121
2
votes
0
answers
89
views
How to make a constraint for consecutive zeros in the mixed integer programming problems
I intend to generate a binary sequence with a size of $N = 10$, for example, $[1, 0, 0, 0, 0, 1, 1, 1, 0, 0]$. The constraint is that when zero appears, it must appear for at least two consecutive ...
- 121
7
votes
1
answer
187
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 ...
- 121
3
votes
0
answers
100
views
Sources of Min-Cost Flow Models That Utilize Binary Variables for Transportation Networks
I am looking for articles that include min-cost flow models with binary variables for flow transportation like gas networks, traffic systems, heating systems. Is there any specific place(like OR ...
- 105
5
votes
1
answer
128
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 ...
- 3,321
3
votes
1
answer
301
views
Implement if-else without then part using int variables {0,1}
I have 6 binary variables $a_i$ for $i$ from 0 to 5. I would like to model the next if-else statement using only MILP constraints
if $(a_0+a_1+a_2)\mod 2=1$ then $(a_3+a_4+a_5) \mod 2 = 0$
I tried <...
- 139
4
votes
3
answers
120
views
How to find the point on the exterior of a given set of points?
Suppose we do have a set of points (all on a plane ).
How to find the smallest hull containing all these points ?
How to find the points (among these given points) that are at the exterior layers of ...
3
votes
2
answers
139
views
Assistance in formulating binary constraint(s)
I would like to seek some advice on modeling the following logical condition:
Given two groups of binary decision variables $A_{i}, i=1...n,$ and $B_{j}, j=1...m$.
$A_{i}=1- B_{j}, \forall i, \forall ...
- 663
2
votes
0
answers
127
views
About combinatorial Benders Cuts
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 321
3
votes
1
answer
94
views
A tricky Bi-Level Location Problem using VISUM
I'm writing my thesis on the optimal location of Air-Taxi Stations. I'm using PTV VISUM for the transport model where I'll inherit the Origin-Destination demand matrix. I come from transportation ...
- 31
7
votes
1
answer
183
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, ...
- 173
6
votes
2
answers
76
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$ ...
- 1,936
3
votes
0
answers
123
views
In binary linear programming, what's the relationship between the dual solution and the lagrangian multipliers?
In my optimization problem the objective function and all the constraints are linear. The decision variables are binary. [so, it's BLP] Some of the hard constraints are very time-consuming to be ...
3
votes
0
answers
40
views
MIP: Do binary variables perform better that integers? [duplicate]
I have a model where investments can be done in blocks. Now I could model this with integer or binary variables. Does anybody know which one is the better choice in terms of computational performance?
- 31
5
votes
1
answer
99
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.
- 153
3
votes
1
answer
112
views
How do I arrive at the form given in this paper, for the QUBO version of the number partitioning problem?
In this article A new modeling and solution approach for the number partitioning problem1, it transforms the number partition problem into a QUBO form like equation (2.1) on page 2. $$\text{diff}=\...
5
votes
3
answers
2k
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 ...
- 325
4
votes
1
answer
228
views
Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?
I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf
One of the steps is to transform the inequalities ...
1
vote
0
answers
89
views
Binary variable with two criteria in Gurobi (Java)
I have the following problem in Gurobi (Java).
I have a binary variable $b$ that is supposed to be $1$ or $0$ depending on my optimisation variable $x$. It should be true that $b = 1$ if $c_1 \le x \...
- 191
4
votes
3
answers
226
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 ...
- 1,546
2
votes
1
answer
67
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 ...
- 663
1
vote
1
answer
166
views
References to publications on representation of any boolean function as a system of linear inequalities
It is known that any boolean function may be represented, in some sense, as a system of linear inequalities. But my rather intensive literature search brought a little references. I will appreciate ...
- 79
3
votes
1
answer
111
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, ...
- 65
3
votes
1
answer
191
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 ...
- 133
1
vote
1
answer
460
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$?
- 1,129
6
votes
2
answers
544
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
2
answers
445
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}=...
- 663
3
votes
1
answer
64
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 ...
- 261
7
votes
1
answer
174
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(...
- 2,034
1
vote
1
answer
71
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?
- 389
6
votes
3
answers
984
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 ...
- 61
1
vote
1
answer
89
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$, ...
- 663
3
votes
2
answers
412
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\...
- 3,776
1
vote
1
answer
81
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$, ...
- 663
2
votes
0
answers
98
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}_+$ ...
- 201
0
votes
0
answers
51
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
1
answer
77
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 ...
- 663
3
votes
1
answer
175
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 \...
- 117