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.
Citation
Technical Report, COR@L Lab, Industrial and Systems Engineering, Lehigh University, January 2007.