Dissertation Defense :: Measuring Facets of Polyhedra to Predict Usefulness in Branch-and-cut Algorithms
Integer programming (IP) can be used to model a variety of industrial problems. One of the most successful ways of solving IPs has been the use of branch-and-cut algorithms, which combine a branch-and-bound framework with the use of cutting planes. This dissertation considers measures of cutting planes with the aim of predicting and understanding their usefulness in branch-and-cut. Measures considered include the volume of the facet, the shooting experiment size of the facet, the best-case improvement that the facet provides, and the Chv'atal-Gomory rank of the facet.