Title:
Combined objective least squares and long step primal dual subproblem simplex methods
Combined objective least squares and long step primal dual subproblem simplex methods
Author(s)
Xu, Sheng
Advisor(s)
Johnson, Ellis L.
Editor(s)
Collections
Supplementary to
Permanent Link
Abstract
The first part of this research work is based on Combined Objective Least Squares (COLS). We took a deeper look at matrix decomposition algorithms that are the dominating components in COLS algorithms, in terms of computational performance and numerical stability. In addition to the traditional QR decomposition approaches, this work studied other possible approaches, such as augmented system matrix and normal equations. This research work proposed a normal equations approach for COLS, which solves linear programming problems efficiently. Even though this approach is only stable under certain conditions according to numerical analysis, we found it stable in practice and provided some possible explanations for such a phenomenon. We also proposed a hybrid approach that could take advantage of the numerical stability of QR decomposition and the efficiency of Cholesky factorization updates so that linear programming problems could be solved reliably and efficiently. The resulting problem becomes a system of semi-normal equations, which may be further improved to achieve higher quality solutions through iterative refinement. The second part of this research work is an improvement to the primal dual subproblem simplex method for set partitioning/packing/covering problems with convexity constraints. Primal dual subproblem simplex methods are very successful in solving large-scale set partitioning problems. In each step of the primal dual subproblem simplex method, dual feasibility is maintained and subsets of columns are selected based on a threshold value to form the restricted master problem. The optimal dual solution from the restricted master problem is used to update the current dual feasible solution, and the step size used to update the dual feasible solution is calculated. For set partitioning/packing/covering problems with convexity constraints, we discovered that the longer step size could be selected because dual values corresponding to convexity constraints could be adjusted to maintain dual feasibility. Additionally, we found that the dual objective is a piecewise linear concave function of the step size and subsequently worked out an algorithm to find the optimal step size to maximize dual objective, so that the convergence rate could be improved. We used the long step primal dual subproblem simplex method (LPD) to solve large-scale multicommodity flow problems(MCF), and with this work, we achieved better performance than primal dual subproblem simplex methods (PD) and Dantzig-Wolfe (DW) decomposition approaches.
Sponsor
Date Issued
2016-04-27
Extent
Resource Type
Text
Resource Subtype
Dissertation