Article ID: | iaor20001648 |
Country: | Netherlands |
Volume: | 91 |
Issue: | 1/3 |
Start Page Number: | 251 |
End Page Number: | 263 |
Publication Date: | Jan 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Wagelmans Albert, Hoesel Stan Van |
Keywords: | programming: integer |
In this paper we address the complexity of postoptimality analysis of 0/1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0/1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems cannot be performed by polynomial methods, unless