Subadditive approaches in integer programming |
| |
Authors: | Diego Klabjan |
| |
Affiliation: | Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, 1206 West Green Street, Urbana, IL 61801, United States |
| |
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. |
| |
Keywords: | Integer programming Duality Algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|