sysid blog

Linear Programming for Dummies 3

April 13, 2020 ☕️ 5 min read

This is a primer on Mixed Integer Programming. It builds on Part2

It is based on personal learning experience and focuses on application rather than theory. For a rigorous approach please refer to a textbook.

Connect decision variable with boolean variable

From Part2 it is known that the fundamental technique to link continuous decision variables with indicator/boolean variables is via Big-M/Small-m constraints.

They implement the following logical statement:

δ=1x>0(0)\delta = 1 \Leftrightarrow x \gt 0 \tag{0}

To allow for more complex boolean logic in MIP models this fundamental relationship needs to be generalized:

Indicator for inequality

One of the simplest logical question that can be asked in mathematical programming is whether a given choice of the decision variables satisfies a constraint. More precisely, when is the following constraint satisfied?

f(x1,...,xn)bjajxjbf(x_1, ... , x_n) \le b\\ \Leftrightarrow\\ \sum_j a_jx_j \le b

Let M,mM, m be an upper and lower bound:

jajxjbMjajxjbm\sum_j a_jx_j -b \le M\\ \sum_j a_jx_j -b \ge m\\

Indicator for \le

δ=1jajxjb(1)\bold{\delta = 1 \Leftrightarrow \sum_j a_jx_j \le b} \tag{1}
Linearization
: jajxj+MδM+b(1a)\tag{1a} \Rightarrow: \ \sum_j a_jx_j +M\delta \le M + b: jajxj(mϵ)δb+ϵ(1b)\tag{1b} \Leftarrow: \ \sum_j a_jx_j - (m -\epsilon)\delta \ge b + \epsilon

If aj,xjNa_j, x_j \in N we can set ϵ=1\epsilon = 1.

Indicator for \ge

δ=1jajxjb(2)\bold{\delta = 1 \Leftrightarrow \sum_j a_jx_j \ge b} \tag{2}
Linearization
: jajxj+mδm+b(2a)\tag{2a} \Rightarrow: \ \sum_j a_jx_j + m\delta \ge m + b: jajxj(M+ϵ)δbϵ(2b)\tag{2b} \Leftarrow: \ \sum_j a_jx_j - (M + \epsilon)\delta \le b - \epsilon

Indicator for equality

Indicator for ==

δ=1jajxj=b(3a)\bold{\delta = 1 \rightarrow \sum_j a_jx_j = b} \tag{3a}
Resulting constraints

Use δ=1\delta=1 to indicate that the \le and \ge cases hold simultaneously. This is done by stating both the constraints (1a) and (2a) together.

jajxj+MδM+b(1a)\tag{1a} \sum_j a_jx_j + M\delta \le M + bjajxj+mδm+b(2a)\tag{2a} \sum_j a_jx_j + m\delta \ge m + b

Indicator for \ne

δ=0    jajxjb(3b)\bold{\delta = 0 \implies \sum_j a_jx_j \ne b} \tag{3b}

If indicator δ=0\delta=0 we want to force either \le or \ge to be broken. This can be done be introducing δ\delta^{'} and δ\delta^{''} in order to link equation 1b and 2b accordingly.

Resulting constraints
jajxj(mϵ)δb+ϵ(1b)\tag{1b} \sum_j a_jx_j - (m -\epsilon)\delta^{'} \ge b + \epsilonjajxj(M+ϵ)δbϵ(2b)\tag{2b} \sum_j a_jx_j - (M + \epsilon)\delta^{''} \le b - \epsilonδ+δδ1(3c)\delta^{'} + \delta^{''} - \delta \le 1 \tag{3c}

(3c) enforces that one of the inequality constraints will be broken if δ=0\delta=0.

Logic Primer

Boolean operations are the building blocks for modelling logic in MIP models. Here are some important relationships.

A proposition is a statement proposing an idea that can be true or false.

Converse of a logical statement/proposition:

pq¬q¬pp \rightarrow q \equiv \lnot q \rightarrow \lnot p \\

Logical Operators (Connectives)

 inclusive or logical and¬ logical not implies if and only if\lor \ \text{inclusive or}\\ \land \ \text{logical and}\\ \lnot \ \text{logical not}\\ \rightarrow \ \text{implies}\\ \Leftrightarrow \ \text{if and only if}\\

Example

Proposition P: ‘I will miss the bus’ Proposition Q: ‘I will be late’ PQP \rightarrow Q stands for the proposition: If I miss the bus I will be late.

Boolean Logic with LP

The trick is to express boolean expressions with LP inequalities. Let XiX_i stand for the proposition δi=1\delta_i = 1, where δ\delta is an indicator variable.

Mapping propositions to (0,1) constraints

The following propositions and constraints are equivalent:

X1X2δ1+δ21X1X2δ1=1,δ2=1¬X1δ1=0,1δ1=1X1X2δ1δ20X1X2δ1δ2=0X_1 \lor X_2 \Leftrightarrow \delta_1 + \delta_2 \ge 1 \\ X_1 \cdot X_2 \Leftrightarrow \delta_1 = 1, \delta_2 = 1 \\ \lnot X_1 \Leftrightarrow \delta_1 = 0, 1- \delta_1 = 1 \\ X_1 \rightarrow X_2 \Leftrightarrow \delta_1 - \delta_2 \le 0 \\ X_1 \Leftrightarrow X_2 \Leftrightarrow \delta_1 - \delta_2 = 0 \\

Linearize polynomial boolean relationship

A product term such as δ1δ2\delta_1\delta_2 can be linearized:

  1. Replace δ1δ2\delta_1\delta_2 with δ3\delta_3
  2. Impose logical condition: δ3δ1δ2\delta_3 \Leftrightarrow \delta_1 \land \delta_2 with constraints:
δ1+δ30δ2+δ30δ1+δ2δ31-\delta_1 + \delta_3 \le 0\\ -\delta_2 + \delta_3 \le 0\\ \delta_1 + \delta_2 - \delta_3 \le 1

Linearize polynomial mixed relationship

A product such as xδx\delta can be linearized. Here xx is a continuous decision variable and δ0,1\delta \in {0,1}.

  1. Replace xδx\delta with yRy \in \mathbb{R}
  2. Impose δ=1y=x\delta=1 \Leftrightarrow y=x with constraints:
yMδ0x+y0xyM(1δ)y - M\delta \le 0\\ -x+y \le 0\\ x - y \le M(1-\delta)\\

M is an upper bound for x and hence also y.

Disjunctive Constraints

Let’s have a set of constraints Rs,s[0,..,S]R_s, s \in [0,..,S], where every constraint RsR_s has the form:

iaixib  or ,=\sum_i a_ix_i \le b \ \text{ or }\ge, =

Disjunction: Only a subset of all constraints needs to hold.

R1..RNR_1 \lor .. \lor R_N

RsR_s is the proposition: ‘The constraints in subset ss are satisfied’:

Now introduce an indicator variable δi\delta_i to indicate whether RiR_i is satisfied. Equivalent to the proposition is imposing the logical condition:

δi=1Ri\delta_i = 1 \rightarrow R_i\\

This proposition translates into the known set of constraints:

  1. [1] for \le
  2. [2] for \ge
  3. [3] for =

Additionally the disjunction needs to be enforced by the following constraint:

δ0+..+δS1\delta_0 +..+ \delta_S \ge 1

Generalization

At least kk of (R0,..,Rs)(R_0,..,R_s) must be satisfied:

δ0+..+δSk\delta_0 +..+ \delta_S \ge k

At most kk of (R0,..,Rs)(R_0,..,R_s) must be satisfied:

δ0+..+δSk\delta_0 +..+ \delta_S \le k

Summary

Disjunctions of constraints involve \lor and necessitate IP models. \land simply involves constraints holding simultaneously.

In this sense, \land corresponds to LP, whereas \lor to IP.

This was a lot of math. Now the foundations are laid.


always be building, by sysid.

© 2022