Mixed-Integer Programming

When a Solver model includes integer constraints, it is called an integer programming problem. (When some, but not all of the decision variables are restricted to integers, the problem is called a mixed-integer programming (MIP) problem. Solving such problems may require far more computing time than the same problem without the integer constraints.

The standard spreadsheet Solvers, the Premium and Quadratic Solvers, and the Large-Scale LP Solver all use the Branch and Bound method to find optimal solutions to such problems. However, refinements to this method in the enhanced solvers will often result in considerably faster solutions than those obtained with the standard Solvers.

The Branch and Bound Method

The Branch and Bound method begins by finding the optimal solution in the absence of the integer constraints. If it happens that in this solution, the decision variables whose values are constrained to be integers already have integer values, then no further work is required.

If one or more integer variables have non-integral solutions, the Branch and Bound method chooses one such variable and "branches," creating two new subproblems where the value of that variable is more tightly constrained. For example, if integer variable A1 has the value 3.45 at the solution, then one subproblem will have the additional constraint A1 <= 3 and the other subproblem will add the constraint A1 >= 4. These subproblems are solved and the process is repeated, "branching" as needed on each of the integer decision variables, until a solution is found where all of the integer variables have integer values (to within a small tolerance).

Hence, the Branch and Bound method may solve many subproblems, each one a "regular" Solver problem. The number of subproblems may grow exponentially; the "bounding" part of the Branch and Bound method is designed to eliminate sets of subproblems that do not need to be explored because the resulting solutions cannot be better than the solutions already obtained. Obviously this may take a great deal of computing time.

Integer programming has many important applications. Most of them involve the use of integer decision variables that are further constrained to have values of either 0 or 1; these are called binary or 0-1 integer variables. Binary integer variables can be used to represent yes/no decisions, such as whether a pipeline is open, or whether a facility is built at a certain location. For a discussion of applications of integer programming, please consult any of the textbooks listed in Recommended Books. For a more sophisticated treatment of integer programming methods (requiring some background in linear algebra and discrete mathematics), consult one of the following texts:

Integer and Combinatorial Optimization by Nemhauser and Wolsey, published by John Wiley. ISBN TBD.

Discrete Optimization by Parker and Rardin, published by Academic Press. ISBN TBD.

Copyright © 1996 Frontline Systems Inc.
Last modified: December 01, 1996