Extreme inequalities for infinite group problems

Santanu S. Dey (sdeypurdue.edu)
Jean-Philippe P. Richard (jpricharecn.purdue.edu)
Lisa A. Miller (lmillerme.umn.edu)
Yanjun Li (li14purdue.edu)

Abstract: In this paper we derive new properties of extreme inequalities for infinite group problems. We develop tools to prove that given valid inequalities for the infinite group problem are extreme. These results show that integer infinite group problems have discontinuous extreme inequalities. These inequalities are strong when compared to related classes of continuous extreme inequalities. This gives further insight that these cuts are be computationally important. Furthermore, the methods we develop also yield the first tools to generate extreme inequalities for the infinite group problem from extreme inequalities of finite group problems. Finally, we study the generalization of these results to the mixed integer infinite group problem and prove that extreme inequalities for mixed integer programs are always continuous.

Keywords: Mixed integer programming, Infinite group problem, Extreme inequalities, Cutting planes.

Category 1: Integer Programming (Cutting Plane Approaches )

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

Citation:

Download: [PDF]

Entry Submitted: 04/01/2006
Entry Accepted: 04/02/2006
Entry Last Modified: 04/03/2006

Modify/Update this entry