Rim Multiparametric Linear Programming

Abstract

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.