General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
- PDF / 103,895 Bytes
- 6 Pages / 595.276 x 793.701 pts Page_size
- 51 Downloads / 155 Views
GENERAL APPROACH TO ESTIMATING THE COMPLEXITY OF POSTOPTIMALITY ANALYSIS FOR DISCRETE OPTIMIZATION PROBLEMS UDC 519.854
V. A. Mikhailyuk
It is shown that there does not exist a polynomial algorithm to derive the optimal solution of a set cover problem that differs from the original problem in one position of the constraint matrix if the optimal solution of the original problem is known and P ¹ NP. A similar result holds for the knapsack problem. Keywords: postoptimality analysis, polynomial algorithm, polynomially solvable problem.
Solving a specific optimization problem with a fixed set of input data yields a plenty of information, which is used only partially to solve the problem. The other portion of the information is lost. Therefore, it is expedient to use the redundant information to solve other optimization problems “close” to the original one. For the postoptimality analysis of discrete optimization problems [1–4], the following questions should be answered: — how the optimal solution of a specific problem will change if values of its coefficients are modified in a certain way; — how the information obtained in solving some problem by a specific method can be used to solve the modified problem; — what minimum additional information should be accumulated in solving the original problem for the efficient solution of the modified problem. The application domain of the postoptimality analysis is the analysis of a real process described by a discrete optimization model and underlying various kinds of innovations. Moreover, with minor changes of the initial data, discrete programming models are usually unstable and unpredictable. The postoptimality analysis of a discrete programming problem is performed based on a certain approach (method) used to solve precisely this problem. Procedures available for the postoptimality analysis of integer programming problems are based on Gomory’s cutting-plane method and branch and bound algorithm [4]. Approximate methods such as local search can be used in postoptimality analysis. Postoptimality analysis is closely related to parametric analysis and stability of discrete optimization problems. Parametric analysis employs a family of equitype problems distinguished by some parameter (either in the objective function or in the constraints); this concerns optimal solutions of the whole family, based on optimal solutions of problems of some subfamily. The stability analysis studies the modifications of the initial data that do not influence the optimal solutions. The stability of parametric and postoptimality analyses was considered in [3], then in [5]. Theoretical stability analysis [2] is intended to establish conditions whereby the set of efficient solutions of a problem is associated with some property that characterizes the stability of problems against “minor” variations in data. Such studies are usually based on the properties of point-set maps, and the stability of a problem is associated with the Hausdorff or Berge continuity (semicontinuity) of these maps. An approach
Data Loading...
