Optimization Online


Sequential pairing of mixed integer inequalities

Yongpei Guan (guanyp***at***isye.gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
George L. Nemhauser (gnemhaus***at***isye.gatech.edu)

Abstract: We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results which show the efficiency of adding the new generated inequalities as cuts.

Keywords: mixed-integer programming, valid inequalities, facets

Category 1: Integer Programming (Cutting Plane Approaches )

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

Citation: Technical report, School of Industrial & Systems Engineering, Georgia Institute of Technology, 2004.

Download: [PDF]

Entry Submitted: 12/22/2004
Entry Accepted: 12/23/2004
Entry Last Modified: 12/22/2004

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