A geometric view of parametric linear programming (Q1193520)

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.