Achieving Consistency with Cutting Planes

Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when it cannot be extended to a full feasible assignment. The constraint programming community has studied consistency extensively and used it as an effective tool for the reduction of backtracking. We extend this approach to integer programming (IP) by defining concepts of consistency that are useful in a branch-and-bound context. We present a theoretical framework for studying these concepts, their connection with the convex hull and cutting planes, and their power to exclude infeasible partial assignments. We propose an algorithm for achieving partial consistency that is based on a variant of the reformulation-linearization technique and that efficiently excludes infeasible partial assignments by solving cut-generating LPs. Computational experiments show that such an algorithm can substantially reduce the search tree. More broadly, we suggest that consistency concepts offer a new perspective on IP that can lead to a better understanding of what makes branching methods work.

Article

Download

View Achieving Consistency with Cutting Planes