Consistency in integer programming

Thumbnail Image
Date
2022-08
Authors
Rajabalizadeh, Atefeh
Major Professor
Advisor
Davarnia, Danial D
De Brabanter, Kris K
Olafsson, Sigurdur S
Ryan, Sarah S
Turhan, Bertan B
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Industrial and Manufacturing Systems Engineering
Abstract
In this thesis, we study the role of cutting planes in reducing the size of the branch-and-bound tree for integer programs. Cutting planes are traditionally used to tighten relaxations of the problem by excluding fractional solutions, which leads to improving the dual bounds. In this research, we study a fundamentally different role of cutting planes that target excluding integer infeasible partial solutions, which leads to improving consistency of the set. Consistency helps to reduce backtracking, thereby reducing the size of the search tree. We investigate the connections between consistency and convex hull, and design a cutting plane framework to achieve consistency. One of the practical challenges in incorporating cutting planes inside of branch-and-bound is the running time required to solve a cut-generating problem. To address this difficulty, we design a function approximation framework to find an estimate for the cut-generating functions. We use machine learning methods that provide a classifier for the binary outcome of the indicator function representing the cut-generating oracle. Computational experiments conducted show significant time improvement as well as size reduction of B&B tree for the proposed approach compared to traditional techniques
Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright