A Constraint-Activating Outer Polar Method for Solving Pure or Mixed Integer 0-1 Programs

摘要

The paper discusses a procedure for solving pure and mixed integer 0-1 programs, based on the properties of outer polar sets introduced in another paper. Rather than generating cutting planes from outer polars, here the author uses the latter in a different way. Starting with a subset of the problem constraints, the author activates as many of the remaining constraints as are needed to produce a convex polytope that is contained in the outer polar of the convex hull of feasible integer points. When this is achieved, the algorithm terminates and the best solution found in the process is optimal. (Author)