The cutting plane tree (CPT) algorithm provides a finite disjunctive programming procedure to obtain the solution of general mixed-integer linear programs (MILP) with bounded integer variables. In this paper, we present our computational experience with variants of the CPT algorithm. Because the CPT algorithm is based on discovering multi-term disjunctions, this paper is the first to present computational results with multi-term disjunctions. We implement two variants for cut generation using alternative normalization schemes. Our results demonstrate that even a preliminary implementation of the CPT algorithm (with either normalization) is able to close a significant portion of the integrality gap without resorting to branch-and-cut. As a by-product of our experiments, we also conclude that one of the cut generation schemes (namely minimizing the $\ell_1$ norm of cut coefficients) appears to have an edge over the other.
Citation
Research report, Data Driven Decisions Lab, The Ohio State University