zbMATH — the first resource for mathematics

A geometric view of parametric linear programming. (English) Zbl 0767.90042
The subject of the paper is to study parametric right-hand side linear programming problems in order to introduce a new definition of optimality intervals. It is shown that an optimal interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function of parametric optimal values. The main motivation to look back into this problem is the quick development of interior point methods. Based on these optimality intervals, an algorithm is suggested for solving the parametric problem requiring a linear programming solver as a subroutine. If a polynomial- time linear programming solver is used to implement this subroutine, a substantial improvement on complexity analysis can be achieved in case of degeneracy.

90C05 Linear programming
90C31 Sensitivity, stability, parametric optimization
PDF BibTeX Cite
Full Text: DOI
[1] G. B. Dantzig,Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.
[2] I. I. Dikin, Iterative solution of problems of linear and quadratic programming,Soviet Mathematics Doklady 8 (1967), 674–675. · Zbl 0189.19504
[3] R. M. Freund, R. Roundy, and M. J. Todd, Identifying the set of always active constraints in a system of linear inequalities by a single linear program, Technical Report, Sloan W. P. No. 1674-85, Boston, MA, 1985.
[4] T. Gal,Postoptimal Analysis, Parametric Programming and Related Topics, McGraw-Hill, New York, 1979.
[5] S. I. Gass and T. L. Saaty, The computational algorithm for the parametric objective function,Naval Research Logistics Quarterly,2 (1955), 39–45.
[6] N. Karmarkar, A new polynomial time algorithm for linear programming,Combinatorica 4 (1984), 373–395. · Zbl 0557.90065
[7] L. G. Khachiyan, A polynomial algorithm in linear programming,Soviet Mathematics Doklady 20 (1979), 191–194. · Zbl 0414.90086
[8] K. G. Murty, Computational complexity of parametric linear programming,Mathematical Programming 19 (1980), 213–219. · Zbl 0443.90102
[9] K. G. Murty,Linear Programming, Wiley, 1983. · Zbl 0521.90071
[10] A. Schrijver,Theory of Linear and Integer Programming, Wiley, 1986. · Zbl 0665.90063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.