5.7 How Integer Programming Codes Work

The most widely-used and effective algorithm for solving integer programming problems is Branch-and-Bound (see Figure 5). First the problem is solved as an LP, i.e. ignoring the requirement that the integer decision variables must take integer values. The solution is examined. If all the integer decision variables happen to have taken integer values, we are finished.

Figure 5: Branch-and-Bound Tree

If some of the integer decision variables are at non-integer values, we select one of these variables. Suppose n3 = 4.63. We define two sub-problems. In the first sub-problem we add the constraint n3 5.0. In the other we add the constraint n3 4.0. As the variable n3 must take an integer value, these two sub-problems between them contain all possible integer feasible solutions which the original problem contained.

We select one of the sub-problems to solve as an LP. As we have already solved the parent problem, we can solve the sub-problem very efficiently by starting from the solution to the parent problem and using the dual simplex algorithm. There are two possible outcomes. Either the sub-problem has a feasible solution, in which case the variable n3 will be at its bound (which is integer); or the sub-problem will be infeasible. In the former case, we have made some progress towards our aim of finding an integer feasible solution; in the latter, we can exclude the sub-problem from further consideration.

We then examine the solutions to the sub-problems for integer decision variables which are at non-integer values and repeat our procedure, developing a tree of sub-problems.

The trouble with this approach is that at each stage there is an increase in the number of sub-problems which we have to consider. Further, integer decision variables which happen to be at integer values in one sub-problem may move away from those values as we add further constraints, or the sub-problem may become infeasible.

Even if we find a solution in which all the integer decision variables take integer values we are not finished. All that we know is that the problem has an integer feasible solution. As we added constraints to the sub-problems in developing our tree, so the objective function worsened. We know the objective value of the original LP solution and the objective value of the integer feasible solution which we have found. But we do not know whether there are other integer feasible solutions which are better than the one we have found. We must explore the rest of the tree to find out.

This is where we use the "and-Bound" part of the algorithm. Once we have an integer feasible solution we know a worst-case value for the objective of integer feasible solutions. This becomes the cut-off. When we solve sub-problems we can discard them if their objective becomes worse than the cut-off. We thus have two weapons for pruning the proliferation of branches of the tree: infeasibility and the cut-off. If we find a better integer feasible solution, its objective value becomes the new cut-off. The Branch-and-Bound algorithm continues until either the entire tree has been traversed or we run out of time.

There are several problems with the Branch-and-Bound algorithm:

  • there is an exponential proliferation of branches in the tree;
  • there is no good way to estimate what will happen to the objective function as one forces variables to integer values, or indeed, whether the problem will remain feasible.

It is because of these problems that Integer Programming is not straightforward. You can help the IP code by giving it extra information about your problem, such as using the high-level integer structures of Special Ordered Sets, and by guiding the search.

previous contents next

Comments