Optimization Online


New Inequalities for Finite and Infinite Group Problems from Approximate Lifting

Lisa A. Miller (lmiller***at***me.umn.edu)
Yanjun Li (li14***at***mgmt.purdue.edu)
Jean-Philippe P. Richard (jprichar***at***purdue.edu)

Abstract: In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new valid inequalities for the infinite group problem are families of two- and three-slope extreme inequalities, including nontrivial inequalities that are not continuous. These new inequalities not only illustrate the diversity of strong inequalities for the finite and infinite group problems, but also provide a large variety of new cutting planes for solving integer and mixed-integer programming problems.

Keywords: integer programming, approximate lifting, group problem, facet-defining inequality, extreme inequality, polyhedral theory

Category 1: Integer Programming (Cutting Plane Approaches )

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


Download: [PDF]

Entry Submitted: 05/17/2006
Entry Accepted: 05/17/2006
Entry Last Modified: 05/17/2006

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