Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
152
questions
-1
votes
2
answers
103
views
Need help with integer programming exercise
This is an exercise from Wolsey that I can't solve. Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3):
$$
\begin{align}
X &= \{ x \in \{0, 1\}^4~\mid~97x_1 + 32x_2 + ...
1
vote
0
answers
40
views
How to linearize a product and ratio of $x$ and $y$ where $x$ is binary and $y$ is a continuous variable?
I am an electrical engineer who is currently learning about optimization. From this post, they have shown how to linearize the product of two binary variables.
But in my case, I have a product $x \...
0
votes
2
answers
63
views
What is the best way to constrain a binary matrix so that at most one row has positive values?
I have a binary variable $x_{i,j}$ for $i\in\{1,\ldots,m\}$ and $j\in\{1,\ldots,n\}$ and the constraint is to have at most one row that has ones. I wrote this as: $$x_{i,j}+x_{i',j'}\leqslant1,\forall ...
- 101
2
votes
2
answers
89
views
How to linearize the product of a binary and a negative continuous variable?
Suppose we have a binary variable $x$ and a negative continuous variable $y$. How can we linearize the product $u=xy$?
- 31
0
votes
1
answer
144
views
Production scheduling
I'm formulating a scheduling problem with the following decision variables:
$$X_t \space \text{is power sold to market in time period t} \\
Y_t \space \text{is power used for production in time period ...
3
votes
1
answer
211
views
Formulation of binary constraint with the least binary variables for linear programming
I am currently working on a formulation for a linear program of a complex problem. At the moment I am facing to formulate the following logical condition:
There are two binary variables. Let's name ...
0
votes
1
answer
173
views
Gurobi founds optimal solution but it is not feasible
I'm currently solving a MIP model with pyomo using gurobi and I am facing strange results.
I have one constraint that looks like this:
...
- 1
3
votes
2
answers
232
views
Binary Integer Programming Problem - Enforce Zeros on Certain Groups
I'm working on a binary integer programming problem using pulp. I have a vector X = [x_1, x_2, x_3, . . . , x_n]. I have enforced a number of simple constraints. I ...
- 33
0
votes
1
answer
111
views
Using binary variable or integer variable in Constraint Programming (CP)?
I am trying to solve an assignment problem by Constraint Programming (CP). Let us consider a task assignment problem that have $|M|$ tasks and $|N|$ machines, each task has different processing time ...
- 712
2
votes
1
answer
279
views
How to do one octomino?
Here are all the 369 octominoes: https://en.wikipedia.org/wiki/Octomino
If I have an 8x8 area, how to create one octomino, any of those 369 and any rotation and mirroring is allowed?
I have tried ...
- 119
7
votes
3
answers
731
views
Binary logical constraint dependent on indices
I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.
I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to ...
- 517
3
votes
1
answer
157
views
Assignment Problem - Students and teachers
I ran across this problem at work and I'm sure that we can optimize it with OR.
I have $n(T) = 4$ teachers and $n(S) = 7$ students that should have a weekly individual class.
If a student $s$ has a ...
- 133
1
vote
2
answers
145
views
Efficient ways to do pairwise/multiplicative variables in integer linear programming on PuLP / Python
I'm trying to formulate an LP that is in essence a variant of the sudoku problem, and I've repurposed the code from https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html.
The differences ...
- 21
7
votes
1
answer
613
views
How can one model a binary variable?
I am looking for the formulation of a constraint that does the following. I want to introduce a new binary variable $\kappa_{it}$ that takes the value 1 if the sum of the other binary variable $\...
- 121
2
votes
1
answer
129
views
Conditional constraints in MILPs
I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP
$$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
0
votes
2
answers
105
views
Modelling a binary variable in LPs
I need your help.
I'm setting up an LP and I'm trying to find constraints to introduce the binary varibale $b_{ij}$. So it should take the value 0 if the sum of all $a_{ij}$ values to the period t are ...
- 11
0
votes
1
answer
184
views
LP - How to model binary variable that indicates a switch
I have the following question / concern. I have a modeling problem with the decision variable $d_{ptm}$ which indicates whether product $p$ was serviced by machine $m$ in period $t$. It takes the ...
-1
votes
1
answer
93
views
creating individual Variables in pyomo with different length
I am new to pyomo and I do have some smaller (or bigger) problems and hope someone can help me. How can you create this variable in pyomo? I wanted to create it with pyo.Varlist() in which I pass ...
-1
votes
3
answers
163
views
Multi objective optimization is giving wrong results
I am trying to solve a multi objective optimization problem. I have a set of nodes belonging to different counties and each node is associated with some cost and some priority. I want to select the ...
- 111
0
votes
0
answers
45
views
How to linearize such a constraint?
My original content was like this:
Assuming that server $k$ can only allocate corresponding computing functions to MU $i$ after receiving their tasks. Let
$$ y_{i,k,t} = \begin{cases} 1 & \text{if ...
- 1
3
votes
2
answers
386
views
How to model a binary variable?
I am trying to find a constraint for the following relationship, but am failing a bit at it right now. I want to find a linear constraint that does the following. The binary variable $switch_{ot}$ is ...
- 31
1
vote
2
answers
82
views
Grouping variables to take same value
Assume we have 50 variables that we want to split into 3 groups and each group should have at least 5 variables. How to formulate that all variables in the same group take the same values? I used the ...
- 21
1
vote
1
answer
54
views
Assistance in formulating implication constraints for inequalities
I would like to seek some advice on modeling the following logical implications, where $\delta$ is a binary variable, $D_{j}$ and $A_{j}$ are nonnegative discrete variables, and $p_{j}$ are ...
- 707
3
votes
2
answers
373
views
How to model this binary constraint?
I have an optimization problem that has a variable in the matrix form. The variable is a binary matrix. It has size $M \times N = 10 \times 50$ where $M$ is the number of machines and $N$ is the ...
2
votes
3
answers
169
views
Linearization the product of three variables (two binary & one continuous)
Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$.
I am trying to model the following conditional equations as constraints:
\begin{cases}
...
- 103
3
votes
2
answers
246
views
Reformulate bilinear binary constraint
I'm a solving a model that has the following constraint:
$$
c_{p,n} = \sum_{s\in S}\sum_{i \in \{1,2,3\} } x_{p,s,i-1} x_{n,s,i}, \forall (p,n) \in C
$$
where both the $c$ and $x$ variables are binary,...
- 223
2
votes
2
answers
59
views
How to restrict the amount of consecutive assignments
I'm working on a scheduling/rostering problem. In this scenario the shifts are predefined with a starting and ending date and time.
The problem basically assigns people to shifts with a binary ...
- 169
2
votes
1
answer
146
views
Reduced cost fixing for binary programs
Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
- 66
2
votes
0
answers
57
views
Is it useful to consider metaheuristics for power flow optimization involving binary variables?
I want to optimize the power flow in a low voltage grid, with respect to customer requests for electric vehicle (EV) charging, but also avoid grid overload (basically, the formulation can be seen in ...
- 293
1
vote
2
answers
491
views
Pyomo: Value assignment for binary variables through constraints
I am currently working on a cost minimisation model for multi-product, multi-period supplier selection with Pyomo. It is a linear model described below.
**Problem statement**
I have no idea how to ...
- 33
4
votes
2
answers
222
views
how to ensure minimum output of a generator (else zero output) in linear programming?
I want to ensure, that a generator (in my case a heat generator, for example a boiler) first starts to output thermal energy, when a certain minimum output can be realized. Otherwise the output should ...
- 293
3
votes
1
answer
102
views
Modelling Question
Let $W^C_t$, $W_t$ be binary variables and $p$ an integer variable with $1 \leq p \leq 3$
The variables are related through the following equation:
$$W^C_t = \sum_{\theta=1}^{p} W_{t-\theta}$$
I can ...
- 2,180
3
votes
3
answers
298
views
Set null the next set of N values
I'm dealing with a problem I already modelled by using linear programming. The already existing constraints set at 1 groups of contiguous variables (for ex: ...
- 33
2
votes
0
answers
73
views
Branching the product of binary and continuous variable in Gurobi
I have a binary variable (X) multiplying a continuous variable (Y). I know I can linearize by adding an auxiliary variable (I have that model working), but I now want to do my own branching in the ...
- 517
4
votes
1
answer
713
views
Can sensitivity analysis and limits report be done on an BILP problem?
I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel.
I know that they can only ...
- 205
3
votes
1
answer
128
views
Expressing $\{0,1\}$ assignment across a matrix in MILP?
I have a MILP (Xpress) constraint, which is doing what I want it to, but I'm struggling to translate it into a LaTeX friendly mathematical expression.
The below code enforces that in the matrix $V$, ...
- 501
2
votes
1
answer
128
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
87
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
297
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,043
1
vote
1
answer
109
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,\...
- 393
7
votes
3
answers
486
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, ...
- 105
2
votes
1
answer
179
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
75
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
73
views
How to model this?
$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}\...
user5245
5
votes
2
answers
345
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
286
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
75
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 \...
- 393
5
votes
3
answers
685
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 ...
- 393
4
votes
1
answer
188
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];$$
$$...
- 393
3
votes
2
answers
100
views
How to model if-then?
$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} \...
user5245