Please use this identifier to cite or link to this item:
Title: Adjacent Basis Based Algorithm for Multiparametric Linear Programming
Authors: CHEN FEI
Keywords: Multiparametric Linear Programming, Basis Partition, Boundary, Adjacent Basis, Critical Region, Cutting Hyperplane.
Issue Date: 6-Aug-2009
Citation: CHEN FEI (2009-08-06). Adjacent Basis Based Algorithm for Multiparametric Linear Programming. ScholarBank@NUS Repository.
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.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Chen Fei.pdf322.3 kBAdobe PDF



Page view(s)

checked on Apr 19, 2019


checked on Apr 19, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.