A geometric view of parametric linear programming |
| |
Authors: | Ilan Adler and Renato D C Monteiro |
| |
Affiliation: | (1) Department of Industrial Engineering and Operations Research, University of California, 94720 Berkeley, CA, USA;(2) Systems and Industrial Engineering Department, University of Arizona, 85721 Tucson, AZ, USA |
| |
Abstract: | We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ( ) = min{c
t
x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function ( ). As a consequence, the optimality intervals form a partition of the closed interval { ; ¦ ( )¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of ( ) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged. |
| |
Keywords: | Parametric linear programming Sensitivity analysis Postoptimality analysis Linear programming |
本文献已被 SpringerLink 等数据库收录! |
|