Achieving Consistency with Cutting Planes

Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linearprogramming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes canalso 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 feasibleassignment. The constraint programming community has studied consistency extensively and used it as aneffective tool for the reduction of backtracking. We extend this approach to integer programming (IP) bydefining concepts of consistency that are useful in a branch-and-bound context. We present a theoreticalframework for studying these concepts, their connection with the convex hull and cutting planes, and theirpower to exclude infeasible partial assignments. We propose an algorithm for achieving partial consistencythat is based on a variant of the reformulation-linearization technique and that efficiently excludes infeasiblepartial assignments by solving cut-generating LPs. Computational experiments show that such an algorithmcan substantially reduce the search tree. More broadly, we suggest that consistency concepts offer a newperspective on IP that can lead to a better understanding of what makes branching methods work