# Tag Info

## Hot answers tagged logical-constraints

31 votes
Accepted

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$". To enforce "if $x=0$ then $y=1$": use $$y \ge 1-x.$$ To enforce "if $x=1$ then $y=1$": use $$y \ge x.$$ If you ...
• 12.7k
21 votes
Accepted

### What is the "big-M" method? And are there two of them?

People do use the term "big-$M$ method" to mean two different things. In both cases, the name refers to the use of a large constant, often denoted $M$. The first use of the term refers to a method ...
• 12.7k
17 votes
Accepted

### What is the difference between integer programming and constraint programming?

You have asked a broad question, so I will provide a broad answer. Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions ...
• 1,512
17 votes

### Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

Here is a nice, succinct,and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this ...
• 11.3k
14 votes
Accepted

### Does it make sense to use strict equality constraints in optimization?

I suspect you read that actual floating point optimization solvers treat strict inequalities ($<$ and $>$) as non-strict inequalities ($\le$ and $\ge$). Solvers also give themselves a fudge ...
• 11.3k
13 votes

### In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a ...
• 300
13 votes
Accepted

• 12.7k
10 votes
Accepted

### ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\...
• 10.9k
9 votes

### How to formulate: each pair of elements in $A$ has one common unit in $B$

If you don’t require linear constraints, you can introduce (or reuse) binary variables $y_{a.b}$ and quadratic constraints $$\sum_{b\in B} y_{a_1,b} y_{a_2,b} \ge 1 \qquad \forall a_1,a_2\in A,$$ for ...
• 23.4k
9 votes

### If-then constraints in MIP programming

Let's just consider one constraint, since they all have the same form: if x >= 0 and x < 1 then y <= 10 and First, you really can't test for $x<1$, ...
• 12.7k
9 votes

### Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015?
• 191
9 votes
Accepted

### Expressing an implication as ILP where each implication term comprises a chain of boolean ORs

For boolean formulas, you can use the following systematic approach. First, convert your formula to conjunctive normal form. Wikipedia details how to do this. Applied to this specific case it follows ...
• 5,943
9 votes
Accepted

• 23.4k
8 votes
Accepted

### Can this be formulated as one inequality

It is not possible as a linear inequality in the variables that you provide. Without loss of generality, this linear inequality would be of the form $$y \le \alpha x_1 + \beta x_2 + \gamma.$$ ...
• 5,943
8 votes
Accepted

### If else condition to MILP

Let $L$ be a constant lower bound on $X + \sum_j^N G_j$. You want $$X + \sum_j^N G_j \in [L,T-\delta] \cup [T,T]$$ with $c_i=0$ for the first interval and $c_i=1$ for the second (single-point) ...
• 23.4k
8 votes
Accepted

### Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

How about $$\omega_1 + \cdots + \omega_n \le n-1$$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the ...
• 10.9k
8 votes

• 23.4k
7 votes

### What is the difference between integer programming and constraint programming?

There were times when the IP and CP communities started to learn about the existence of the other, and initially, people tried to build a list of vocabulary to translate one concept into another. You ...
• 5,809

Only top scored, non community-wiki answers of a minimum length are eligible