Optimization Online


Consistency for 0-1 programming

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

Abstract: Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type of consistency that is particularly suited for 0-1 programming and develop the associated theory. We define a 0-1 constraint set as LP-consistent when any partial assignment that is consistent with its linear programming relaxation is consistent with the original 0-1 constraint set. We prove basic properties of LP-consistency, including its relationship with Chvatal-Gomory cuts and the integer hull. We show that a weak form of LP-consistency can reduce or eliminate backtracking in a way analogous to k-consistency but is easier to achieve. In so doing, we identify a class of valid inequalities that can be more effective than traditional cutting planes at cutting off infeasible 0-1 partial assignments.

Keywords: Consistency; Resolution; Constraint satisfaction; Integer programming; Backtracking; Cutting planes

Category 1: Integer Programming

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 12/01/2018
Entry Accepted: 12/01/2018
Entry Last Modified: 12/01/2018

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