Constraint Optimal Selection Techniques (COSTs) For Linear Programming

Abstract

Simplex pivoting algorithms remain the dominant approach to solve linear programming (LP) because they have advantages over interior-point methods. However, current simplex algorithms are often inadequate for solving a large-scale LPs because of their insufficient computational speeds. This dissertation develops the significantly faster simplex-based, active-set approaches called Constraint Optimal Selection Techniques (COSTs). COSTs specify a constraint-ordering rule based on constraints' likelihood of being binding at optimality, as well as a rule for adding constraints. In particular, new techniques for adding multiple constraints in an active-set framework, and an efficient constraint-ordering rule for LP are proposed. These innovations greatly reduce computation time to solve LP problems.