The most widely-used and effective algorithm for solving integer programming problems is 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 n 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 n 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 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. |

LP Training > 5. Integer Programming >