Mixed Integer Programming (MIP)
Integer variables and Linear Programming equals Mixed Integer Programming
Linear Programming has long been an important optimization tool, especially in the business arena. Decisions regarding optimum inventory quantities, shipping and transportation choices, manufacturing scheduling, and numerous other processes can often benefit from the application of Linear Programming (LP).
In its simplest form, linear programming is a technique for solving a set of mathematical inequalities subject to a particular optimization goal. Consider the following optimization problem: a company sells two products, A and B, and wants to make as much profit each week as possible. The company is just getting started and has space constraints for inventory, and budget constraints for both inventory purchase and labor.
If a and b represent the quantity of products A and B they can produce each week, the following constraints must be met:
inventory space: 2a + b <= 2000 since units of A take twice as much room as those of B,
inventory cost: a + b <= 1400 since the unit materials cost the same amount,
labor cost: b <= 1000 since units of A require no labor,
and the profit is given by P = 3a + 2b, that is, units of A are more profitable.
This problem is directly solvable by standard ’simplex’ LP solvers. The solution to this problem is a = 600, b = 800, P = 3400, and the labor is idle 20% of the time, so a 4 day work week might be appropriate. Although a and b worked out to be integers in this problem, that is not always the case. But the answers, if decimal numbers, would still be close enough to be useful.
But now suppose that the inventory of A can only be purchased in lots of 250. What is the best solution?
The new constraint is a = 250c, where c must be an integer (the number of lots).
The LP solver does not allow integer constraints. Running it with this constraint would produce the same solution, with c = 2.4 (so that a = 250c = 600 as before.
This problem can still be solved, but it now requires use of a Mixed Integer Programming (MIP) solver. A MIP solver allows us to constrain the variable c to be an integer.
The new solution will be a = 500, b = 900, c = 2, P = 3300, with the labor idle only 10% of the time. These differences in the solution could be very important to the business.
In practice, these types of problems typically have many more variables and many more constraints, perhaps numbering in the hundreds or thousands.
As a final note, MIP solvers often take much longer to solve a problem than an LP solver, since the MIP solver runs iteratively, and each iteration calculates an LP solution. The art of MIP usage is knowing how to reduce the number of required iterations.
A good advanced text on MIP solver theory is “Production Planning by Mixed Integer Programming” by Pochet and Wolsey, published by Springer. Many high school algebra texts cover introductory graphical methods for the solution of simple LP problems.
