Achieving Consistency with Cutting Planes
Date
2022-02-21
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Davarnia, Danial
Assistant Professor
Research Projects
Organizational Units
Organizational Unit
Industrial and Manufacturing Systems Engineering
The Department of Industrial and Manufacturing Systems Engineering teaches the design, analysis, and improvement of the systems and processes in manufacturing, consulting, and service industries by application of the principles of engineering. The Department of General Engineering was formed in 1929. In 1956 its name changed to Department of Industrial Engineering. In 1989 its name changed to the Department of Industrial and Manufacturing Systems Engineering.
Journal Issue
Is Version Of
Versions
Series
Department
Industrial and Manufacturing Systems Engineering
Abstract
The primary role of cutting planes is to separate fractional solutions of the linear programming relaxation, which results in tighter bounds for pruning the search tree and reducing its size. Bounding, however, has an indirect impact on the size of the search tree. Cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching, which directly reduces the tree size. 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 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 their power to exclude infeasible partial assignments. We introduce a new class of cutting planes that target achieving consistency rather than improving dual bounds. Computational experiments on both synthetic and benchmark instances show that the new class of cutting planes can significantly outperform classical cutting planes, such as disjunctive cuts, by reducing the size of the search tree and the solution time. More broadly, we suggest that consistency concepts offer a new perspective on integer programming that can lead to a better understanding of what makes cutting planes work when used in branch-and-bound search.
Comments
This is a manuscript of the article Davarnia, Danial, Atefeh Rajabalizadeh, and John Hooker. "Achieving Consistency with Cutting Planes." Mathematical Programming (2022).
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Wed Jan 01 00:00:00 UTC 2020