Optimization Online


A probabilistic comparison of split and type 1 triangle cuts for two row mixed-integer programs

Qie He(qie.he***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
George Nemhauser(gnemhaus***at***isye.gatech.edu)

Abstract: We provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables. Under a simple probabilistic model of the problem parameters, we show that a simple split cut, i.e. a Gomory cut, is more likely to be better than a type 1 triangle cut in terms of cut coefficients and volume cut off.

Keywords: Mixed integer programming, Split cuts, Triangle cuts, Probabilistic comparison

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Submitted for publication.

Download: [PDF]

Entry Submitted: 06/01/2010
Entry Accepted: 06/01/2010
Entry Last Modified: 06/01/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