Optimization Online


Achieving Consistency with Cutting Planes

Danial Davarnia(davarnia***at***iastate.edu)
Atefeh Rajabalizadeh(Alizade***at***iastate.edu)
John Hooker(jh38***at***andrew.cmu.edu)

Abstract: 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.

Keywords: Consistency; Constraint programming; Integer programming; Cutting planes; Branch-and-bound

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 01/01/2020
Entry Accepted: 01/01/2020
Entry Last Modified: 01/01/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society