sysid blog

Linear Programming for Dummies 2

April 12, 2020 ☕️ 4 min read

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.

Wikipedia:

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) NP-hard.

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 NP-hard because they are even more general than ILP programs.

General Facts

  • More constraints make a MIP problem easier to solve.
  • MIP formulation is non-convex.

Application

Sometimes decision variables have to be integral because the real-world 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–no-go 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 non-linearities 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 Big-M constraints.

Big-M

Big-M 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.

Big-M Constraint, Upper Boundary

It forces the indicator (bool) variable to true if x>0x > 0.

x>0δ=1xMδ0(1)x > 0 \rightarrow \delta = 1 \\ x - M\delta \le 0 \tag{1} \\

Small-m Constraint, Lower Boundary

It forces the indicator variable to false if x=0x = 0.

x=0δ=0xmδ0(2)x = 0 \rightarrow \delta = 0 \\ x - m\delta \ge 0 \tag{2} \\

Result

Both constraints applied in a model implement the logical statement:

δ=1x>0\delta = 1 \Leftrightarrow x \gt 0

Recipe

  1. Start with a proposition:
δ=0 constraint for x, e.g.  x0(a)\delta = 0 \rightarrow \ \text{constraint for x, e.g. } \ x \le 0 \tag{a}
  1. Find an inequality which enforces this proposition with the assumed δ\delta value.
xMδ0(b)x - M\delta \le 0 \tag{b}

Whenever δ=0\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 xx because the proposition (a) does not imply anything about δ=1\delta = 1.

  1. Test both alternatives:
    1. δ=0\delta = 0 enforces x0x \le 0
    2. δ=1\delta = 1 does not constrain xMδ0x - 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.

xA,xB0 (proportion of A, B in the mix)δ0,1 (indicator variable)x_A, x_B \ge 0 \ \text{(proportion of A, B in the mix)}\\ \delta \in {0, 1} \ \text{(indicator variable)}\\
  1. Link the indicator variable to the continouus variable A: xA>0δ=1x_A > 0 \rightarrow \delta = 1
xAδ0,M=1x_A - \delta \le 0, M = 1
  1. use the indicator variable to connect B: δ=1xb>0\delta = 1 \rightarrow x_b > 0
xB0.01δ0,m=0.01x_B - 0.01\delta \ge 0, m=0.01 \\

M=1M=1 is upper bound for xA,xBx_A, x_B because these variables are proportions. m=0.01m=0.01 is an arbitrary choice which assumes that below 1% concentration B is not relevant.

Summary

Big-M and Small-m 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.


always be building, by sysid.

© 2022