Questions tagged [binary-variable]

For questions that involve variables than can only take on one of two values, usually 0 or 1.

Filter by
Sorted by
Tagged with
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 ...
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, ...
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}\...
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} \...
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}...
-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 ...
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}...
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 ...
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$ ...
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 ...
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 ...
user avatar
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 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 ...
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 ...
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 ...
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