Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.10.009 Byline: Diego Klabjan Keywords: Integer programming; Duality; Algorithms Abstract: Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable. Author Affiliation: Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, 1206 West Green Street, Urbana, IL 61801, United States Article History: Received 13 February 2006; Accepted 19 October 2006