- A Computational Study of the Cutting Plane Tree Algorithm for General Mixed-Integer Linear Programs Binyuan Chen (bychenemail.arizona.edu) Simge Kucukyavuz (kucukyavuz.2osu.edu) Suvrajeet Sen (sen.22osu.edu) Abstract: 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. Keywords: Pure cutting plane algorithm, disjunctive programming Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Research report, Data Driven Decisions Lab, The Ohio State University Download: Entry Submitted: 09/16/2010Entry Accepted: 09/16/2010Entry Last Modified: 12/14/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.