Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/18835
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
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/18835
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

OPEN

NoneView/Download

Page view(s)

242
checked on Dec 11, 2017

Download(s)

263
checked on Dec 11, 2017

Google ScholarTM

Check


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