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.