DYNAMIC CONSTRAINT OPTIMAL SELECTION TECHNIQUES FOR LINEAR PROGRAMMING

Publication Year:
2016
Usage 47
Abstract Views 25
Downloads 22
Repository URL:
http://hdl.handle.net/10106/26921
Author(s):
Noroziroshan, Alireza
Tags:
large-scale linear programming, Constraint optimal selection technique
thesis / dissertation description
Linear programming has been studied for over 60 years. It has been considered as one of the most valuable optimization tool for many industrial problems. The simplex algorithm remains the predominant approach to solving linear programming problems. Here we use the simplex method in an active-set frame work to improve it substantially. In general an active-set method obtains solutions by adding one or more problem constraints at a time to solve smaller problems iteratively. In particular, some of these methods have proven to perform significantly faster than the simplex method. In this dissertation we proposed an efficient constraint selection metric for NNLPs called NVRAD to add constraints recursively in two ways; using posterior method and dynamic active-set approach for both nonnegative linear programming and general linear programming. In general linear programming we improve on past prior active-set methods by using dynamic constraint selection technique. These innovations improved the solver’s performance and reduced the computation time needed to solve large-scale linear programming problems.