Linear Programming for Dummies 3

$$ \boldsymbol{\delta = 1 \Leftrightarrow \sum_j a_jx_j \le b} \tag{1} $$

Linearization

$$ \tag{1a} \Rightarrow: \ \sum_j a_jx_j +M\delta \le M + b $$

$$ \tag{1b} \Leftarrow: \ \sum_j a_jx_j - (m -\epsilon)\delta \ge b + \epsilon $$

If \(a_j, x_j \in N\) we can set \(\epsilon = 1\).

$$ \boldsymbol{\delta = 1 \Leftrightarrow \sum_j a_jx_j \ge b} \tag{2} $$

Linearization

$$ \tag{2a} \Rightarrow: \ \sum_j a_jx_j + m\delta \ge m + b $$ $$ \tag{2b} \Leftarrow: \ \sum_j a_jx_j - (M + \epsilon)\delta \le b - \epsilon $$

Indicator for \(=\)

$$ \boldsymbol{\delta = 1 \rightarrow \sum_j a_jx_j = b} \tag{3a} $$

Resulting constraints

Use \(\delta=1\) to indicate that the \(\le\) and \(\ge\) cases hold simultaneously. This is done by stating both the constraints (1a) and (2a) together. $$ \tag{1a} \sum_j a_jx_j + M\delta \le M + b $$ $$ \tag{2a} \sum_j a_jx_j + m\delta \ge m + b $$

Indicator for \(\ne\)

$$ \boldsymbol{\delta = 0 \implies \sum_j a_jx_j \ne b} \tag{3b} $$

If indicator \(\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

$$ \tag{1b} \sum_j a_jx_j - (m -\epsilon)\delta^{’} \ge b + \epsilon $$ $$ \tag{2b} \sum_j a_jx_j - (M + \epsilon)\delta^{’’} \le b - \epsilon $$

$$ \delta^{’} + \delta^{’’} - \delta \le 1 \tag{3c} $$

(3c) enforces that one of the inequality constraints will be broken if \(\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: $$ p \rightarrow q \equiv \lnot q \rightarrow \lnot p \\ $$

Logical Operators (Connectives)

$$ \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’ \(P \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 \(X_i\) stand for the proposition \(\delta_i = 1\), where \(\delta\) is an indicator variable.

Mapping propositions to (0,1) constraints

The following propositions and constraints are equivalent:

$$ X_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 \(\delta_1\delta_2\) can be linearized:

1. Replace \(\delta_1\delta_2\) with \(\delta_3\)
2. Impose logical condition: $$\delta_3 \Leftrightarrow \delta_1 \land \delta_2$$ with constraints: $$ -\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\delta\) can be linearized. Here \(x\) is a continuous decision variable and \(\delta \in {0,1}\).

1. Replace \(x\delta\) with \(y \in \mathbb{R}\)
2. Impose \(\delta=1 \Leftrightarrow y=x\) with constraints: $$ 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 \(R_s, s \in [0,..,S]\), where every constraint \(R_s\) has the form: $$ \sum_i a_ix_i \le b \ \text{ or }\ge, = $$

Disjunction: Only a subset of all constraints needs to hold. $$ R_1 \lor .. \lor R_N $$

\(R_s\) is the proposition: ‘The constraints in subset \(s\) are satisfied’:

Now introduce an indicator variable \(\delta_i\) to indicate whether \(R_i\) is satisfied. Equivalent to the proposition is imposing the logical condition: $$ \delta_i = 1 \rightarrow R_i\\ $$

This proposition translates into the known set of constraints: