Fast Algorithms for Linear Programs with a Large Number of Constraints
Dr. Andre Tits, Professor
 |
| Dr. Andre Tits |
For over half a century, linear programming (LP) has been a key paradigm for modeling a large class of problems in areas such as planning, routing, scheduling, assignment, blending, portfolio selection, etc. Industries that make use of LP and its extensions include transportation, energy, telecommunications, and manufacturing of many kinds (e.g., http://www.faqs.org/faqs/linear-programming-faq/). Accordingly, any significant advance in algorithms for the solution of LPs has the potential of having a notable economic impact.
Linear programming consists in the minimization of a linear objective (cost) function, subject to linear constraints. Starting with the ground-breaking 1984 work of Narendra Karmarkar, the methods of choice for solving LPs have been of the "interior point" variety: by-and-large they have superseded the simplex method, introduced in the 1940s by the late George Dantzig, the father of linear programming.
Interior-point methods solve LPs by constructing a sequence of "iterates" that converge to the solution. While the number of iterations needed to reach the solution is typically much smaller than when a simplex method is used, the computational cost of one iteration may be large, as it involves the solution of a linear system of equations whose size is the sum of the number of decision variables and the number of constraints, while in the case of the simplex method, linear systems to be solved have size merely equal to the number of variables. This difference in system sizes is particular acute when the number of constraints is much larger than the number of variables. This situation is the focus of the present project.
Supported by funding from the National Science Foundation and the US Department of Energy, Prof. Tits and his fellow researchers have developed a scheme (rather, a class of schemes), which can be grafted upon many current interior-point methods, by which the set of constraints taken into account at any given iteration is but a (carefully, and adaptively selected) small subset of the total set of constraints. The computational cost per iteration is significantly reduced: it can be shown to be is roughly proportional to the size of that subset. Strikingly, extensive testing has shown that the number of iterations needed to reach the solution remains essentially constant, as the size of that subset is decreased, down to a small multiple of the number of decision variables.
Paper and Matlab code can be downloaded from http://www.csit.fsu.edu/~absil/Publi/reducedLP.htm
Work is underway toward (i) further investigating, refining, and extending, the proposed class of schemes, to obtain even larger savings, perhaps on specific subclasses of problems, and (ii) extending the ideas to quadratic programming and to more general nonlinear programming.
Faculty Researchers:
University of Maryland:
Andre Tits (ECE and ISR)
Dianne O'Leary (CS)
Remote collaborator:
Pierre-Antoine Absil (Univ. of Cambridge)
 return to spotlight on research
|
