Adjacent Basis Based Algorithm for Multiparametric Linear Programming

Abstract

This thesis focuses on a class of multiparametric linear programming (mpLP) problems which have linear parameters in the cost and the right-hand side of the constraints. Based on the theory about basis partition of the space of linear programs, a novel algorithm, namely adjacent basis based algorithm is proposed. Rather than enumerating all the subregions it only checks the adjacent bases of feasible bases to determine all the critical regions in the parameter space. This method can partition the space completely.

The cutting theorem is given which can make the finding of a feasible point from the parameter space more efficient. The critical region is represented by a set of nonredundant boundaries. The method for generating the adjacent bases of a feasible basis is introduced. The algorithm for determining the critical region for a point and the method to test the validity of the adjacent basis based algorithm are also discussed. Numerical experiments are given to test the feasibility the algorithm. Moreover, further research is done to filter feasible bases from all adjacent bases.