Consistency in integer programming

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