DYNAMIC CONSTRAINT OPTIMAL SELECTION TECHNIQUES FOR LINEAR PROGRAMMING
Degree granted by The University of Texas at Arlington
Abstract
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 e?cient 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.