Theory and computation of sparse cutting planes

Integer programming;Cutting plane;Sparse;Algorithm;Theory

Wang, Qianyi ; Dey, Santanu Industrial and Systems Engineering Molinaro, Marco Nemhauser, George Ahmed, Shabbir Sun, Andy ; Dey, Santanu

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Integer programming;    Cutting plane;    Sparse;    Algorithm;    Theory;   

Others  :  https://smartech.gatech.edu/bitstream/1853/56307/1/WANG-DISSERTATION-2016.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Cutting plane plays an important role in the theory and computation of integer programming. Nowadays, most state-of-the-art integer programming solvers tend to bias their cutting plane selection towards sparse ones, which emphasizes the significance of sparse cutting planes. In this thesis, we conduct a comprehensive study of sparse cutting planes and prove several theoretical results. We also develop a new approximation algorithm for sparse packing integer programs.