The value function of a mixed integer program: II |
| |
Authors: | C.E. Blair R.G. Jeroslow |
| |
Affiliation: | Department of Business Administration, University of Illinois, Urbana, IL 61801, USA;College of Industrial Management, Georgia Institute of Technology, Atlanta, GA 30332, USA |
| |
Abstract: | We prove that the gap in optimal value, between a mixed-integer program in rationals and its corresponding linear programming relaxation, is bounded as the right-hand-side is varied. In addition, a variant of value iteration is shown to construct subadditive functions which resolve a pure-integer program when no dual degeneracy occurs. These subadditive functions provide solutions to subadditive dual programs for integer programs which are given here, and for which the values of primal and dual problems are equal. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|