Campus Units

Industrial and Manufacturing Systems Engineering

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2020

Abstract

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.

Comments

This is a manuscript of the article Davarnia, Danial, Atefeh Rajabalizadeh, and John Hooker. "Achieving Consistency with Cutting Planes." (2020).

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS