Optimization Online


A Computational Study of the Cutting Plane Tree Algorithm for General Mixed-Integer Linear Programs

Binyuan Chen (bychen***at***email.arizona.edu)
Simge Kucukyavuz (kucukyavuz.2***at***osu.edu)
Suvrajeet Sen (sen.22***at***osu.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


Entry Submitted: 09/16/2010
Entry Accepted: 09/16/2010
Entry Last Modified: 12/14/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society