Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
116
questions
2
votes
1
answer
93
views
Conditional constraint for binary
Could you please check where I might be wrong?
Task is:
If $z=1$, then either $x=1$ or $y=1$
My approach:
If $z=1$, then $x+y=1$
$\implies x+y\le1$
$\implies x+y\ge1$
If $z=0$, then $x+y\ge0 - M\cdot(...
2
votes
1
answer
36
views
Expressing inner product of binary variables in MIP
I have a $m$ by $n$ matrix $X$ of binary variables in my MIP which represents a list of $m$ items each belonging to one of $n$ categories. $m$ is usually around $1,000$ while $n$ is much lower at ...
- 123
3
votes
2
answers
141
views
Can we use continuous variables instead of binary variables in this NLP problem?
The following problem is defined with binary variables $a_{i1}, a_{i2}, a_{i3}, k_1$ and $k_2$.
Is it possible to avoid binary variables and to only work with continuous variables? How would we ought ...
1
vote
1
answer
81
views
ILP program to find a centrosymmetric Hadamard matrix
A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36.
An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if:
$$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
- 351
7
votes
3
answers
447
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, ...
- 83
2
votes
1
answer
146
views
Binary variable constraint for condition
I am trying to solve the following task:
If $x=1$ or $y=0$ then $z=0$
My approach:
If $z=0$ then $x+y \le 2 + Mz \implies x+y \le 2+2z \quad$
where $M = 2$
If $z=1$ then $x+y=1 \\
\implies
x+y \le 1, ...
0
votes
1
answer
32
views
Conditional constraint for binary variables
I would appreciate any help to solve the following task:
If $y=1$ then $x_i=1$ for at least $k$ of the possible indices $i\in\{1,\cdots,n\}$ where $k$ and $n$ are parameters, $x$ is a binary variable ...
2
votes
2
answers
37
views
How to model: If $c_{ij}\cdot y_{j} \ge c_{ik}\cdot y_{k}$ then $x_{ij} \ge x_{ik}$?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ and $y_{j}$ are binary variables.
How to model: If
$$c_{ij}\...
- 191
4
votes
1
answer
139
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, ...
3
votes
1
answer
213
views
Binary variables constraint
What constraints would you write to ensure that if $x = 1$ then $y = 0$ where $x, y$ are binary variables?
Until now I only learnt how to build the constraint with 3 binary variables, therefore the ...
4
votes
1
answer
60
views
Another difficult constraint for an ILP
How can I add to this ILP with all binary variables (again related to this question):
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} \ge \lfloor (n-1)/2\rfloor \qquad \...
- 351
5
votes
3
answers
534
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 ...
- 351
4
votes
1
answer
169
views
Difficult linearization of a constraint
My previous question was about this ILP with all binary variables:
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$
$$...
- 351
3
votes
2
answers
68
views
How to model: If $c_{ij}\cdot x_{ij} \ge c_{ik}$ then $x_{ij} \ge x_{ik}$?
$i$ is a set $1$ to $n$.
$j$ is a set $1$ to $m$.
$j$ and $k$ are from the same set such that $j\neq k$.
$c_{ij}$ is a parameter.
$x_{ij}$ is a binary variable.
How to model: If
$$c_{ij}\cdot x_{ij} \...
- 191
4
votes
2
answers
298
views
Expected ILP solving time and how to improve speed
I am trying to solve this ILP with all binary variables:
$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$
$$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$
$$a_{k,i} + ...
- 351
2
votes
1
answer
90
views
Linearize a product of binary variables with 2 indexes
I have the following inequality that I would want to linearize.
Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $...
7
votes
1
answer
240
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 ...
- 137
2
votes
1
answer
61
views
Modelling not evenly distributed discrete levels of a decision variable
I have a decision variable for the power of a heating device $P$ that can have the following levels: 0, 900, 1300, 2000 (Unit is Watt [W]).
Now I would like to know if and how I can model in an ...
- 1,648
2
votes
1
answer
73
views
Lifting a 3rd order polynomial into a higher dimensional space
An MINLP from a paper I am reading has the following expression in its constraints:
Where from left to right:
$p_{l,s}$: continuous variable
$z_l$: binary variable
$b_l$: constant
$\Delta \theta_{l,s}...
- 81
-4
votes
1
answer
170
views
Methods for binary linear programming
I have an LP problem (linear objective with eq and ineq constraints) in binary variables.
Except for the objective, all the coefficients are integer, mostly in {-1,0,1}. Maybe the objective coeff ...
- 137
1
vote
0
answers
61
views
Multi-Stage Stochastic Decomposition
I have a multi-stage model with both binary and continuous first-stage investment variables and continuous operational next-stage variables:
$$
\sum_{s} \rho_{s} \left[ x_{s} + y_{s} + \sum_{t}(y^{op}...
- 81
3
votes
1
answer
115
views
Modeling a special case of conservation of flow
At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e
The first requirement is that only one of the two inflow ...
- 695
3
votes
1
answer
133
views
Transfer an integer model to binary
I have a minimization problem with integer variables and would like to transform it to binary variables. The problem is, that my objective is to minimize the overall waiting time, which consists of ...
- 51
1
vote
0
answers
124
views
How to make unconstrained variables non-negative (as in excel solver) in AMPL?
This is a sequencing problem.
I've got this variables
...
- 11
3
votes
1
answer
189
views
Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?
I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning):
Given $n$ tasks, with times $\{t_i\}_{i\in I_n}$, and $m$ ...
- 656
3
votes
1
answer
93
views
Disjunctive Constraint , Using Binary Variable to Replace a If or condition
I am trying to use a binary variable based on an inequality.
The value of binary variable $q $ is 1 or 0 based on the following equation.
[
$q $ =
\begin{cases}
0,& \text{if } b \geq \pi ,\\
1,...
-1
votes
1
answer
78
views
Assignment Problem with continuous decision variable
I have to solve a problem from industry where there are a number of machines which should be assigned to a number of tasks. The difference from the general assignment problem is tough, that the ...
- 49
4
votes
2
answers
532
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 ...
user9659
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}} $$
- 307
3
votes
1
answer
237
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 ...
- 351
2
votes
1
answer
173
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 ...
- 437
5
votes
1
answer
125
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,786
2
votes
1
answer
88
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
81
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
160
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 ...
- 682
1
vote
1
answer
92
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 ...
- 403
2
votes
1
answer
59
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 ...
- 439
6
votes
1
answer
230
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
286
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 ...
- 323
2
votes
1
answer
262
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
153
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
344
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
114
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
132
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,893
3
votes
1
answer
326
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 <...
- 179
4
votes
3
answers
127
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 ...
- 1,044
3
votes
2
answers
145
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 ...
- 695
2
votes
0
answers
177
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
107
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
289
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