Questions tagged [logical-constraints]
For questions about constraints that can be expressed in (usually propositional) logic.
129
questions
31
votes
3
answers
18k
views
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like
If $x \gtreqless b$, then $y = 1$.
How can we write this ...
- 13.1k
29
votes
3
answers
7k
views
What is the difference between integer programming and constraint programming?
At first glance both approaches appear to be very similar.
What are the major differences between integer programming and constraint programming?
- 2,013
17
votes
1
answer
4k
views
What is the "big-M" method? And are there two of them?
I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?
- 13.1k
13
votes
4
answers
2k
views
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...
- 13.2k
13
votes
6
answers
255
views
How to formulate: each pair of elements in $A$ has one common unit in $B$
We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite ...
- 13.1k
12
votes
2
answers
3k
views
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
Suppose we have the constraint
$$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$
where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
- 13.1k
12
votes
3
answers
2k
views
Does it make sense to use strict equality constraints in optimization?
Once I learned from some post that the strict equality constraint in an optimization problem does not make much sense. We should always use $\le$ constraint. How much truth is in this?
If I must have ...
- 2,211
12
votes
2
answers
610
views
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
- 897
12
votes
1
answer
5k
views
If-then constraints in MIP programming
For continuous variables $x$ and $y$, the constraints are:
...
- 221
12
votes
0
answers
165
views
which method has been used to automatically reformulate logical constraints in a standard MIP solver?
There are many of the formulations to linearize logical constraints by introducing new auxiliary binary or any appropriate variables and adding the corresponding constraints to the model. It can be ...
- 8,450
11
votes
1
answer
485
views
Expressing a chain of boolean ORs using ILP involving different variables
How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
- 897
10
votes
1
answer
612
views
MIP: If integer variable $>0$ it should be equal to other integer variables $>0$
I have an MIP problem where $n$ different types of cars are delivering packages. Sometimes multiple types of cars are required to go to a single location. For example if car $1$ makes two deliveries ...
- 205
9
votes
2
answers
766
views
Common structures in Gurobi - Python
I'm new to Gurobi in Python and I was wondering if someone knows how to code some common structures of linear constraints. I'm trying to understand how you'll code something like the following ...
- 103
9
votes
1
answer
200
views
Binary variable to count appearances
Let $x \in \mathbb{R}^n$ be an optimization variable. Now, at a constraint, I would like to count how many times a value, say $2$, appears in $x$ decision.
I think we can have a binary variable $y_i$...
- 3,980
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
7
votes
2
answers
388
views
Difference between Chance constraints and logical constraints
A logical constraint combines linear constraints using
logical operators, such as logical-and, logical-or, negation (that is, not), conditional statements (that is, if ... then ...) to express complex ...
- 8,450
7
votes
4
answers
951
views
is prime? in Operations Research
Is there a way to linearize is prime? in Operations Research?
is prime(n) being true if $n$ is a prime number or false otherwise....
- 583
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
7
votes
1
answer
129
views
Expressing a chain of boolean if-then with logical ANDs using MIP
How to express a chain of boolean If-then as MIP such as:
If $(x_{10} \ge b_1$ and $x_{11} \le b_1)$ AND $(x_{20} \ge b_2$ and $x_{21} \le b_2)$... AND... then $y_1 = 1$ else $y_1 = 0$.
So basically,...
- 71
7
votes
1
answer
339
views
Logical Constraints Modelling using Big-M formulation
I am trying to model some logical constraints in ILOG. Logical constraints could be given such as:
Constraint 1 or Constraint 2,
Constraint 3 or Constraint 4,
Constraint 5 or Constraint 6.
The ...
- 71
6
votes
4
answers
786
views
Can this be formulated as one inequality
I have two binary variables $x_1$ and $x_2$ and a non-negative continuous variable $y$. In addition, I have the following two parameters $u>q>0$. I would like to formulate the following ...
- 1,133
6
votes
2
answers
865
views
How to transform this logical if-then constraint?
Consider the binary variables $x, y, z \in \{0,1\}$.
I'd like to formulate the two if-then constraints:
$$ x + y \geq 2 \implies z = 0, \tag{1} $$
$$ x + y \leq 1 \implies z = 1. \tag{2} $$
Constraint ...
- 385
6
votes
1
answer
8k
views
How to linearize min function as a constraint?
I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
- 77
6
votes
1
answer
536
views
ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied
Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $x_i$'s. Consider an ILP constraint $x_1 + x_2 + x_3 \geq 1$ and another constraint $x_4 + x_5 + x_6 \geq 1$. I would like to ...
- 897
6
votes
1
answer
487
views
Convert summation of min functions into linear constraints for optimization
I have the following optimization problem:
$$
\mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
- 63
5
votes
4
answers
875
views
Rewriting if-then constraints of binary summations
Suppose both $x_{i,j}^{ab}$ and $y_{i,j}^a$ are binaries. Then how can I rewrite the following if-then in linear form?
$\sum_b x_{i,j}^{ab} \ge 1 \implies \sum_{i,j} y_{i,j}^a = 0$
I was thinking of ...
- 177
5
votes
3
answers
253
views
MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$
I want to formulate a MIP constraint such that :
$$\sum_{i=1}^nx_i = 2 \implies \delta = 1$$
$x_i, \delta \in \{0, 1\}$.
My problem is that delta should be one when this sum is exactly 2 and not ...
- 235
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
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, ...
5
votes
2
answers
528
views
How to convert this if-then constraint to MIP constraint?
How to convert this if-then constraint to MIP constraint?
$\text{if } a \geq 0 \text{ then } b=K_1 \text{ else(a <0 ) } \ b =K_2$
- 294
5
votes
2
answers
730
views
How to linearize specific range constraints?
I would like to know about the linearization of the $(If, Then)$ constraints as follows:
$$\begin{array}{l}
\text { If: } \\
15 \leqslant x \leqslant 25 \\
\text { then: } \quad y=\color{blue}{a} x+\...
- 8,450
5
votes
2
answers
926
views
In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?
In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something.
I'm working ...
- 51
5
votes
1
answer
591
views
Model "if and only if" indicator constraints in Linear programming
Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following:
\begin{align}\text{cond} < \dfrac{1}{3} &\iff x =...
- 534
5
votes
1
answer
152
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,980
5
votes
1
answer
319
views
how to apply Big M to model the logic constraint （if-then-else）
I was hoping to get some help in modelling the following logic as an MIP Constraint
c_{m,l}^{RC} is binary decision variable.
Simplify it：
- 51
4
votes
3
answers
434
views
How to transform a logical constraint with integer variables?
Consider the binary variables $x_1, x_2 \in \{0,1\}$ and the integer variable $y \in \mathbb{Z}$ with $0 \leq y \leq 3$.
I'd like to formulate the following logical constraint:
$$
x_1 = 1 \wedge y \...
- 385
4
votes
2
answers
480
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}=...
- 707
4
votes
2
answers
307
views
Model "If, then" constraint
How to model the following "If, then" type constraint?
If $\sum\limits_{i \in I}x_i = 0$ then $\sum\limits_{j \in J}x_{j} = n$
where $x$ are binary variables, $n$ is a known parameter and $...
4
votes
2
answers
280
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 \ \ \...
- 315
4
votes
2
answers
376
views
How to model $C_1=C_2$ implies $b_1 = b_2$
Suppose $C_1 \ge 0$, $C_2 \ge 0$ are continuous variables and $b_1$, $b_2$ are binary variables.
How could I model the following?
$C_1 = C_2 \implies b_1 = b_2$, the opposite does not hold.
- 2,180
4
votes
2
answers
297
views
The linearization of the (Iff-and-only-Iff) expression
I am trying to linearize the following expression without using the Big-M formulation, but I cannot convert it. I am willing to know if there exists an efficient way to do that?
$$ Iff \quad (w=1) \...
- 43
4
votes
3
answers
500
views
How can I formulate this 'if-then' constraint problem?
I have five integer variables, and I need to write some constraints on them:
$x_0$ , $[x_1, x_2, x_3, x_4 ]$. $1 \leq x_i \leq 3$
if $x_0 =1$ then no constraint on $[x_1, x_2, x_3, x_4 ]$
if $x_0 =...
- 1,277
4
votes
2
answers
525
views
Formulating the conditional constraint
I want to develop a model extension of capacitated location problem.
The variables are a binary $x_i$ and a continuous $Q_i$. The following condition must be satisfied:
if $x_i = 0$, $Q_i$ must be ...
4
votes
1
answer
358
views
How can I transform this logical if-then constraint? [duplicate]
I want to know how to transform this logical if-then constraint? If $B=1$,then $A \ge C$, else $A=0$, where $A$ and $B$ are decision variables and $C$ are constants. $B$ is binary variable and $A\ge 0$...
- 43
4
votes
1
answer
187
views
Formulating these logical constraint in an ILP
I have these two constraints :
$z \leq My$
$t \leq M'y $
where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers.
So basically these ...
- 117
4
votes
1
answer
203
views
Constrain Mixed-Integer problem such that a graph is fully connected
I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
- 3,975
4
votes
1
answer
94
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 ...
- 3,980
4
votes
1
answer
158
views
Buying shares in increments
I constructed an optimisation model which objective is to find highest return on available stocks. Now want to add a constraint that allows to buy stocks only in $2000 increments, how can I do it? i.e ...
- 41
4
votes
1
answer
260
views
Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is to be equated to a third ...
- 707
4
votes
1
answer
249
views
Creating constraints dynamically in pyomo abstract model
I have a networkX graph with few nodes and these nodes have attributes such as "demand".
...
- 69