Linear Programming

Linear programming problems are intrinsically easier to solve than nonlinear problems. In an NLP there may be more than one feasible region and the optimal solution might be found at any point within any such region. In contrast, an LP has at most one feasible region with "flat faces" (i.e. no curves) on its outer surface, and the optimal solution will always be found at a "corner point" on the surface where the constraints intersect. (In some problems there may be multiple optimal solutions, all of them lying along a line between corner points, with the same objective function value.) This means that an LP Solver needs to consider many fewer points than an NLP Solver, and it is always possible to determine (subject to the limitations of finite precision computer arithmetic) that an LP problem (i) has no feasible solution, (ii) has an unbounded objective, or (iii) has an optimal solution (either a single point or multiple equivalent points along a line).

Problem Size and Numerical Stability

Because of their structural simplicity, the main limitations on the size of LP problems which can be solved are time, memory, and the possibility of numerical "instabilities" which are the cumulative result of the small errors intrinsic to finite precision computer arithmetic. The larger the model, the more likely it is that numerical instabilities will be encountered in solving it.

Most large LP models are sparse in nature: While they may include thousands of decision variables and constraints, the typical constraint will depend upon only a few of the variables. This sparsity can be exploited to save memory and gain speed in solving the problem.

The Simplex Method

LP problems are generally solved via the Simplex method. The standard spreadsheet Solvers and the Premium Solver use a straightforward implementation of the Simplex method to solve LP problems, when the Assume Linear Model box is checked in the Solver Options dialog. The memory required by this Simplex code increases with the number of variables times the number of constraints, regardless of the model's sparsity.

The Large-Scale LP Solver uses a far more sophisticated implementation of the Simplex method, which fully exploits sparsity in the LP model to save time and memory. To cope with potential numerical instabilities, the Large-Scale LP Solver uses techniques such as automatic scaling, matrix factorization using the LU decomposition with the Bartels-Golub update, steepest-edge pivoting strategies, and dynamic Markowitz refactorization. These same techniques often result in much faster solution times -- making it practical to solve LP problems with thousands of variables and constraints.

The basic Simplex method is explained in many textbooks, such as Shogan's Management Science, listed in Recommended Books. For a more sophisticated treatment of the Simplex algorithm and extensions, consult one of the following:

Linear Programming and Network Flows, 2nd Edition by Bazaraa, Jarvis & Sherali, published by John Wiley. ISBN 0-471-63681-9.

Computer Solution of Linear Programs by J.L. Nazareth, published by Oxford University Press. ISBN 0-19-504278-6.

Quadratic Programming

Quadratic programming problems are more complex than LP problems, but simpler than general NLP problems. Such problems have only one feasible region with "flat faces" on its surface, but the optimal solution may be found anywhere within the region or on its surface. Frontline's Quadratic Solver uses the Simplex method to determine the feasible region, then uses special methods based on the properties of quadratics to find the optimal solution.

Large QP problems are subject to many of the same considerations as large LP problems: When using a straightforward or "dense" representation as in Frontline's current Quadratic Solver, the amount of memory required increases with the number of variables times the number of constraints, regardless of the model's sparsity. Numerical instabilities can arise in QP problems and may cause more difficulty than in similar-size LP problems. To deal with these issues, Frontline hopes to offer a large-scale sparse quadratic solver in the future.

Copyright © 1996 Frontline Systems Inc.
Last modified: December 01, 1996