Linear Programming for Dummies 2
This is a primer on Mixed Integer Programming.
It builds on Part1.
It is based on personal learning experience and focuses on application rather than theory. For a rigorous approach please refer to a textbook.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NPhard.
If only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming (MIP) problem. These are generally also NPhard because they are even more general than ILP programs.
General Facts
 More constraints make a MIP problem easier to solve.
 MIP formulation is nonconvex.
Application
Sometimes decision variables have to be integral because the realworld objects which they represent are entities and the number is low. When deciding how many aircraft carriers to have, fractional solutions are meaningless.
However, when dealing with bigger numbers it is often possible to use LP and round the results, e.g. Optimized Car Rental.
Often it makes no sense to consider fractional values because e.g. the problem requires a go–nogo decision. Hence, an important application of integer decision variables is the introduction of boolean logic into LP by providing ‘indicator’ or boolean variables which only take the values 0 (false) or 1 (true).
A third application is to model nonlinearities such as fixed costs for e.g. opening a warehouse.
This allows to frame problems like:
If A or B is in the mix, then at least one of C, D or E must also be in the mix.
One technique is to link the boolean variables to its associated continuous variables via BigM constraints.
BigM
BigM constraints get the name from the fact that either a “big” upper limit (M), or a “small” lower limit (m) are chosen. M must not limit the real solution space of the variables, it is an upper (lower) bound which allows to relate the boolean to the continuous variables.
For numerical stability it is important to choose M/m as small/big as possible.
BigM Constraint, Upper Boundary
It forces the indicator (bool) variable to true if \(x > 0\).
$$ x > 0 \rightarrow \delta = 1 \\ x  M\delta \le 0 \tag{1} \\ $$
Smallm Constraint, Lower Boundary
It forces the indicator variable to false if \(x = 0\).
$$ x = 0 \rightarrow \delta = 0 \\ x  m\delta \ge 0 \tag{2} \\ $$
Result
Both constraints applied in a model implement the logical statement: $$ \delta = 1 \Leftrightarrow x \gt 0 $$
Recipe

Start with a proposition: $$ \delta = 0 \rightarrow \ \text{constraint for x, e.g. } \ x \le 0 \tag{a} $$

Find an inequality which enforces this proposition with the assumed \(\delta\) value. $$ x  M\delta \le 0 \tag{b} $$
Whenever \(\delta = 0\) gives a feasible solution to constraint (b), we know that constraint (a) must also be satisfied. The value of \(\delta\) enforces the proposition (a).
The inverse value of \(\delta\) must not constrain \(x\) because the proposition (a) does not imply anything about \(\delta = 1\).
 Test both alternatives:
 \(\delta = 0\) enforces \(x \le 0\)
 \(\delta = 1\) does not constrain \(x  M\delta \le 0\)
Two constraints are necessary in order to model the proposition ‘if and only if’.
Example
If A is in the mix, B must also be included. $$ x_A, x_B \ge 0 \ \text{(proportion of A, B in the mix)}\\ \delta \in {0, 1} \ \text{(indicator variable)}\\ $$
 Link the indicator variable to the continouus variable A: \(x_A > 0 \rightarrow \delta = 1\) $$ x_A  \delta \le 0, M = 1 $$
 use the indicator variable to connect B: \(\delta = 1 \rightarrow x_b > 0\) $$ x_B  0.01\delta \ge 0, m=0.01 \\ $$
\(M=1\) is upper bound for \(x_A, x_B\) because these variables are proportions. \(m=0.01\) is an arbitrary choice which assumes that below 1% concentration B is not relevant.
Summary
BigM and Smallm constraints are an important building block in order to help modelling conditions and boolean logic in Linear Programming.
The next chapter will deal with how to model more advanced conditions.