Rim Multiparametric Linear Programming

The rim multiparametric linear programming problem (RMPLP) is a parametric problem with a vector-parameter in both the right-hand side and objective function (i.e., in the “rim”). The RMPLP determines the region K* ⊂ E* such that the problem, maximize z(λ) = c T (λ)x, subject to Ax = b(λ), x ≧ 0, has a finite optimal solution for all λ ∈ K*. Let B i be an optimal basis to the given problem, and let R i *, be a region assigned to B i such that for all λ ∈ R i * the basis B i is optimal. The goal of the RMPLP problem is to cover K* by the R i * such that the various R i * do not overlap. The purpose of this paper is to present a solution method for finding all regions R i * that cover K* and do not overlap. This method is based upon an algorithm for a multiparametric problem described in an earlier paper by Gal and Nedoma.

• 저널Management Science · 21(5) · 567–575
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.21.5.567
• 저자Tomáš Gál