On the Complexity of Postoptimality Analysis of 0/1 Programs

Abstract

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. W11e 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 can not be performed by polynomial methods, unless P = NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the trite ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis of E - optimal solutions of NP-hard 0/1 problems. It is shown that for an - optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased sutch that the solution remains - optimal, unless P =,NP. OR/MS subject classification: Analysis of algorithms, computational complexity: postoptimality analysis of 0/1 programs; Analysis of algorithms, suboptimal algorithm: sensitivity analysis of approximate solutions of 0/1 programs.