| Linear programming has evolved over the years, due to sustained research and testing, as an excellent mathematical tool for solving many theoretical and practical problems. Yet, escalating problem sizes in practical problems pose serious challenges for the very best linear programming codes, running on the fastest computing hardware. New linear programming solution techniques have to be developed to meet these challenges. The research performed in this thesis intends to address this issue through a comprehensive study of least-squares methods for solving linear programming problems.; We have developed two new linear programming algorithms based on least-squares theory. A Combined Objectives Least-Squares (COLS) algorithm uses a Non-Negative Least-Squares (NNLS) algorithm framework for solving both the Phase I and Phase II linear programming problems. A Least-Squares Primal-Dual (LSPD) algorithm uses NNLS solutions by solving small NNLS problems to solve relatively larger linear programming problems. These algorithms are impervious to degeneracy. Computational results for the algorithms shows a superior performance over the simplex algorithm on a wide range of linear programming problems.; A Least-Squares Network Flow (LSNF) algorithm, which is an adaptation of the LSPD algorithm for solving minimum cost network flow problems, solves minimum cost network flow problems very efficiently by exploiting special least-squares properties of node-arc incidence matrices. A polynomial bound on the run time of the LSNF algorithm is presented.; Large-scale linear programs can be solved efficiently using a Least-Squares Subproblem (LSS) approach. It solves the whole problem by solving a sequence of subproblems consisting of a small subset of the columns. Computational results for solving the LP relaxation of crew-pairing optimization problems, which are known to be highly degenerate, are presented. Aircrew fatigue issues have been studied and a rule for mitigating crew fatigue at the crew pairing optimization level is proposed. |
