Consistency in integer programming

dc.contributor.advisor Davarnia, Danial D
dc.contributor.advisor De Brabanter, Kris K
dc.contributor.advisor Olafsson, Sigurdur S
dc.contributor.advisor Ryan, Sarah S
dc.contributor.advisor Turhan, Bertan B Rajabalizadeh, Atefeh
dc.contributor.department Industrial and Manufacturing Systems Engineering en_US 2022-11-09T05:45:42Z 2022-11-09T05:45:42Z 2023-09-07T00:00:00Z 2022-08 2022-11-09T05:45:42Z
dc.description.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
dc.format.mimetype PDF
dc.language.iso en
dc.language.rfc3066 en
dc.subject.disciplines Industrial engineering en_US
dc.subject.keywords Branch and bound en_US
dc.subject.keywords Cutting planes en_US
dc.subject.keywords Integer programming en_US
dc.subject.keywords Machine learning en_US
dc.title Consistency in integer programming
dc.type article en_US
dc.type.genre dissertation en_US
dspace.entity.type Publication Industrial engineering en_US Iowa State University en_US dissertation $ Doctor of Philosophy en_US
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
2.7 MB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
0 B
Item-specific license agreed upon to submission