# Tag Info

26

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 want to require that $y=1$ if and only if the condition holds, then replace the $\ge$s above with $=$s. If $x$ is continuous: In this case, numerical inaccuracy ...

21

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 for finding an initial feasible solution for the simplex method. (Another common method for doing this is the two-phase method.) Sometimes people also use the ...

16

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 are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a ...

16

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 document and then addressing any particular difficulties or concerns the questioner may have. FICO MIP formulations and linearizations Quick reference at https://www....

12

Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints. My colleague works with these a lot and he’s finding the indicator constraints in Gurobi perform worse than big-M. He’s in contact with the Gurobi developers so I might be able to get more info if there’s ...

12

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 note characterizing this formulation. There's also a generalization for convex nonlinear "on/off" constraints here and recent extensions here.

12

Let $M$ be a new parameter (constant) that equals a large number. Greater-than-or-equal-to constraints: The constraint is $a_1x_1 + \cdots + a_nx_n \ge b$. Rewrite it as $$a_1x_1 + \cdots + a_nx_n \ge b - M(1-y).$$ Then, if $y = 1$, the constraint is active, and if $y=0$, it has no effect since the right-hand side is very negative. (If all of the $a_i$ ...

12

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 factor, called feasibility tolerance, equal to the amount by which they may be violated in reality but treated as satisfying the constraint by the solver. If you ...

11

Let $P$ be the set of $(i,j)$ pairs. Here’s a derivation via conjunctive normal form: $$\bigvee_{(i,j)\in P} \left(x_i \implies x_j\right) \\ \bigvee_{(i,j)\in P} \left(\neg x_i \vee x_j\right) \\ \sum_{(i,j)\in P} \left(1-x_i + x_j\right) \ge 1 \\ \sum_{(i,j)\in P} (x_i - x_j) \le |P| - 1$$ For your example, this yields 2x_1+... 11 I recommend Formulating Integer Linear Programs: A Rogues' Gallery: The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full citation below. [1] Gerald G. Brown, Robert F. Dell, (2007) Formulating Integer Linear Programs: A Rogues' Gallery. INFORMS Transactions on Education. 7(2):... 11 Let b_n be a binary indicator variable, and let integer variable y be the common value of the positive x_n. Then you want to enforce x_n=b_n y, which you can linearize using the formulation given here. 10 I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint (1) enforces z=0 \implies x + 1 \le y. Constraint (2) enforces z=1 \implies y + 1 \le x. This idea goes back at least to Manne, On the Job-Shop Scheduling Problem (1960). In some ... 9 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 which your triply-indexed formulation is a linearization. If you do need linear and are worried about the problem size, you can generate the violated ... 9 What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015? 9 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 that$$(a_1 \vee a_2 \vee a_3) \Longrightarrow (b_1 \vee b_2 \vee b_3)$$is equivalent to$$(\bar{a}_1 \vee b_1 \vee b_2 \vee b_3) \wedge (\bar{a}_2 \vee b_1 \...

9

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\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$1 \le x_1+x_2+x_3 \le 3$$ And ...

8

If I understand your question correctly then you want to model that if $$a_1+a_2+a_3\geq 1$$ then it follows that $$b_1+b_2+b_3\geq 1.$$ Since $A \implies B$ is equivalent to $\neg A \lor B$ we want to model $$\sum_{i=1}^3 a_i < 1 \quad\bigvee\quad \sum_{i=1}^3 b_i \geq 1.$$ We can replace $\sum_{i=1}^3 a_i < 1$ with $\sum\limits_{i=1}^3 a_i =0$ ...

8

Here is an answer that uses the same approach as in this answer, but converted from $\max\{\cdot,\cdot\}$ to $\min\{\cdot,\cdot\}$. I'll write the constraint in a more general form: $$X = \min\{x_1,x_2\}$$ This method works if $x_1$ and $x_2$ are constants or decision variables (or one of each). (In your question, $X = q_1$, $x_1 = b$ and $x_2 = ap_1$.) ...

8

These two types of constraint are totally different in terms of their applications in modeling. In fact, the way of using these constraint types (based on your modeling approach) end up in two totally distinct problems each of which can be solved different solution approaches. In the following, I will try to explain where we need to implement each of the ...

8

Logical constraints do not involve probability, except perhaps for the implicit probability of one or zero. Chance constraints specify conditions (constraints) which must hold with a(t least) specified probability, which generally would not be one or zero. Chance constraints could include logical conditions, and potentially even be specified in terms of ...

8

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$, with a strict inequality. The best you can do is something like $x \le 1-\delta$, for small $\delta$. So I'll assume you're taking that approach. Introduce a new binary variable $z$ that equals 1 ...

8

As LarrySnyder610 said, you cannot do exactly what you want when $x_i$ is continuous. (You can if it is an integer variable.) I discussed how to model this particular issue here: Flagging a Specific Variable Value.

8

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.$$ Condition 1 says that for $x_1=0$, the right-hand side must be zero for both $x_2=0$, which implies $\gamma=0$, and for $x_2=1$, which then implies $\beta = 0$ as well. ...

8

Indeed, for the first constraint you can use: $$x+y+z \le 2$$ For the second one, it might be easier to model the contraposition: $$z=0 \quad \Rightarrow \quad x+y \ge 2 \quad \Rightarrow \quad x=y=1$$ This yields: $$1-z \le x \\ 1-z \le y$$

8

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 selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.

8

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$\lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\$$

7

Can you consider an extended formulation? In this case you could consider variables $x_{A',b} \in \{0,1\}$ with value 1 iff \begin{align} \{a,b\} \in E & \quad & \forall a \in A' \\ \{a,b\} \not\in E & \quad & \forall a \not\in A' \end{align} (where $E$ is the edge set of the bipartite graph). In other words it determines which ...

7

Because you are maximizing the sum of $y$, as long as each $y$ appears in no other constraints, you can get by with enforcing only one direction of the implication, namely $$y_1=1\implies (x_{10}\ge b_1 \land x_{11}\le b_1 \land \dots).$$ You can do this with one big-M constraint for each inequality, where $\ell$ and $u$ are (constant) lower and upper bounds ...

7

You want to enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies \sum_{j \in J} x_j = n.$$ Introduce a new binary variable $y$ and enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies y$$ and $$y \implies \sum_{j \in J} x_j = n.$$ For the first implication, conjunctive normal form yields \begin{align} \left(\bigwedge_{i \in I} \lnot x_i\...

7

Let $\epsilon > 0$ be a tolerance for what you consider positive. Now impose linear constraints $z \ge \epsilon y$ and $t \ge \epsilon y$. Because $z$ and $t$ are integer variables, you can take $\epsilon=1$.

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