A Bounding Technique for Integer Linear Programming with Binary Variables

摘要

We present a bounding technique for use in implicit enumeration algorithms for solving the integer linear programming problem with binary variables. The main assumptions used by this technique are the associated linear program, obtained by dropping the integrality constraints on the variables, possesses a unique optimal solution, this optimal solution is not binary, and a good feasible solution to the original problem is available. An alternative to the last assumption which is weaker is also presented. We show that joint bounds can be obtained on the values of a subset of the variables. In addition we given an efficient method to implement this bounding technique. Finally, a class of problems particularly well-suited to this bounding procedure is specified. (Author)