Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
74
questions
1
vote
0answers
48 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 ...
3
votes
1answer
83 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
votes
1answer
288 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 <...
3
votes
3answers
112 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
2answers
119 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 ...
2
votes
0answers
89 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 ...
3
votes
1answer
80 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 ...
7
votes
1answer
131 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, ...
6
votes
2answers
72 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$ ...
3
votes
0answers
93 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
0answers
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?
5
votes
1answer
91 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.
3
votes
1answer
102 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
3answers
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 ...
4
votes
1answer
170 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
0answers
68 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 \...
4
votes
3answers
146 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
65 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 ...
1
vote
1answer
161 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 ...
3
votes
1answer
103 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, ...
3
votes
1answer
77 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
183 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$?
6
votes
2answers
341 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
433 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}=...
3
votes
1answer
57 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 ...
7
votes
1answer
147 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
68 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?
6
votes
3answers
939 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
84 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
253 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
67 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
85 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
45 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
69 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
140 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
238 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
81 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
115 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
62 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
337 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
207 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
151 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
153 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
135 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
140 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
87 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
176 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
466 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
56 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 ...