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* \subset E* such that the problem, maximize z(\lambda) = c^T(\lambda)x, subject to Ax = b(\lambda), x \geqq 0, has a finite optimal solution for all \lambda \in 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 \lambda \in 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.