Duality for Mixed-Integer Linear Programs

Menal Guzelsoy (megblehigh.edu)
Ted Ralphs (tkralphslehigh.edu)

Abstract: This paper is a survey of and some minor extensions to the theory of duality for mixed-integer linear programs. The theory of duality for linear programs is well-developed and has been extremely successful in both theory and practice. Much of this broad framework can be extended to MILPs in principle, but this has proven largely impractical because a duality theory well-integrated with current practice has yet to be developed. This paper surveys what is know about duality for integer programs with an eye towards developing a more practical framework.

Keywords: Integer Programming, Duality, Branch and Cut

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

Citation: Technical Report, COR@L Lab, Industrial and Systems Engineering, Lehigh University, January 2007.

Download: [Postscript][PDF]

Entry Submitted: 01/26/2007
Entry Accepted: 01/26/2007
Entry Last Modified: 04/05/2007

Modify/Update this entry