Linear programming algorithms using least-squares method

The simplex method is the most widely used algorithm for solving linear programming problems. It works very efficiently in practice and is incorporated in most commercial software. However, degeneracy causes slow convergence in certain classes of problems. The airline crew-scheduling set-partitioning formulation is one the problems where degeneracy causes substantial difficulties.; This thesis is a computational study of recently developed algorithms which aim to overcome the above pitfall in the simplex method. To benchmark solution techniques, we use the airline crew-scheduling set-partitioning formulation for comparing the performance of the algorithms treated here with CPLEX. We study the following algorithms: the nonnegative least squares algorithm, the least-squares primal-dual algorithm, the least-squares network flow algorithm, and the combined-objective least-squares algorithm.; All of the above four algorithms use least-squares measures to solve their subproblems, so they do not exhibit degeneracy. But, their properties are not well established yet in literature. Moreover, they have never been efficiently implemented and thus their performance have also not been proved. In this research we implement these algorithms in an efficient manner and improve their performance compared to on their preliminary results.; The non-negative least-squares algorithm is a least-squares algorithm with additional non-negativity constraints. The algorithm works by solving a series of unconstrained least-squares problems and using convex combination process to maintain non-negativity. We show strict improvement during minor iterations and develop basis update techniques and data structures that fit our purpose. In addition, we also develop a measure to help find a good ordering of columns and rows so that we have a sparse and concise representation of QR-factors.; The least-squares primal-dual algorithm uses the non-negative least-squares problem as its subproblem, which minimizes infeasibility while satisfying dual feasibility and complementary slackness. We develop a special technique of relaxing and restoring complementary slackness to improve the convergence rate.; The least-squares network flow algorithm is the least-squares primal-dual algorithm applied to min-cost network flow instances. This is similar to the application of the simplex algorithm to solve min-cost network flow instances efficiently (Network simplex algorithm). The least-squares network flow algorithm can efficiently solve much bigger instances than the least-squares primal-dual algorithm. We implement an upper bounded version of the algorithm. After preliminary tests, we devise a specialized pricing scheme whose performance is similar to the CPLEX network solver.; The combined-objective least-squares algorithm is the primal version of the least-squares primal-dual algorithm. Each subproblem tries to minimize true objective and infeasibility simultaneously so that optimality and primal feasibility can be obtained together. It uses a big-M to minimize the infeasibility. We use dynamic M values to improve the convergence rate. We test the least-squares subproblem method, which uses the least-squares primaldual algorithm and the combined-objective least-squares algorithm to solve large-scale crew pairing problems.; Our computational results show that the least-squares primal-dual algorithm and the combined-objective least-squares algorithm perform better than the CPLEX Primal solver, but are slower than the CPLEX Dual solver. The least-squares network flow algorithm performs as fast as the CPLEX Network solver.