A geometric view of parametric linear programming
A geometric view of parametric linear programming
复制标题
参数线性规划的几何视图
DOI：
10.1007/bf01758841
复制
发表时间：
1992
期刊：
影响因子：
1.1
通讯作者：
R. Monteiro
中科院分区：
文献类型：
--
作者：
I. Adler;R. Monteiro
对参数右端线性规划问题<$（λ）= min{ctx <$Ax =B + λ <$B，x ≥ 0}给出了一个新的最优性区间的定义.然后我们证明了最优性区间由连续分段线性凸函数λ的一个断点或两个连续断点之间的开区间组成。因此，最优性区间形成闭区间{λ;<$（λ）<$< ∞}的一个分区。基于这些最优区间，我们还介绍了一种算法，用于解决参数RHS LP问题，需要一个LP求解器作为一个子程序。如果一个多项式时间LP求解器是用来实现这个子程序，我们得到了显着改善的复杂性，这些参数RHS LP实例表现出退化。当λ的断点个数与参数问题的规模成多项式关系时，我们证明了参数问题可以在多项式时间内求解.
We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ϑ(λ) = min{ctx¦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.