# Linear Programming for Dummies 4

This is a collection of logic recipies for Mixed Integer Programming. It builds on Part3.

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

## Logic Recipies

All variables here can only take boolean values: $$x_i, y \in{0, 1}$$
Let $$X_i$$ stand for the proposition $$x_i=1$$, anaolog for $$Y$$.

### if X then Y

$$x \rightarrow y$$

Set of constraints: $$y \ge x \\$$

#### Example

You can launch satellite X only if you have chosen a compatible booster Y.

### Y then X1 AND X2 (and vice versa)

$$y \leftrightarrow x_1 \land x_2$$ Set of constraints: $$y \ge x_1 + x_2 -1\\ y \le x_1\\ y \le x_2\\ 0 \le y \le 1 \\$$

Generalized with range constraint:
$$y = x_1 \land … \land x_n\\ 0 \le \sum_i x_i -ny \le n-1\\$$

#### Example

Y can be produced if and only if a machine X1 and worker X2 are available.”

### Y then X1 OR X2 (and vice versa)

$$y \leftrightarrow x_1 \lor x_2$$ y if and only if x1 or x2 or both.

$$y \le x_1 + x_2 \\ y \ge x_1\\ y \ge x_2\\ 0 \le y \le 1 \\$$

generalized with range constraint:
$$y = x_1 \lor … \lor x_n\\ 0 \le ny - \sum_i x_i \le n-1\\$$

#### Example

Project Y can be funded if and only if project X1 or project X2, or both projects are funded.

### XOR

$$y \leftrightarrow x_1 \oplus x_2$$ y if x1 or x2, but not both.

$$y \le x_1 + x_2\\ y \ge x_1 - x_2\\ y \ge x_2 - x_1\\ y \le 2 - x_1 - x_2\\ 0 \le y \le 1\\$$

#### Example

Packaging line Y can receive product from either processing line X1 or processing line X2.

### Cheat Sheet

I helpful collection of recipies can be found here:

## Summary

This collection is a living document. If you have a recipe to be included, please let me know. I am more than happy to extend the collection and cite the originator.