Advanced Methods
The Large-Scale LP/QP Solver uses an advanced implementation of the Primal and Dual Simplex methods. It automatically selects the best Simplex method, pricing method, pivoting strategy and the like, and uses robust methods to automatically handle degenerate models.
An automatic Presolve method can eliminate many unnecessary variables and constraints, and tighten bounds on other variables and constraints.
The new Assume Quadratic Objective option enables the Large-Scale LP/QP Solver to solve quadratic programming (QP) problems without requiring structure analysis by the Premium Solver Platform.
Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity in large LP models, where subsets of the constraints typically depend on only a small subset of the variables. For example, an LP coefficient matrix for a problem with 10,000 variables and 10,000 constraints would take about 800 megabytes for matrix storage using dense storage methods, but if this problem has the sparsity typical of larger models, it would take about 24 megabytes using the sparse storage methods in the Large-Scale LP/QP Solver.
(To learn more, click on Problem Size and Sparsity, covered in our Solver Tutorial.)
Matrix Factorization
Large LP models require hundreds of thousands to millions of floating-point arithmetic calculations to solve. Because of the finite precision inherent in computer arithmetic, small numerical errors occur in these calculations. Using conventional matrix representation and Simplex method iterations, these errors typically have a cumulative effect, leading to a numerically unstable problem and possibly large errors in the "solution."
The Large-Scale LP/QP Solver Engine uses a factorization of the LP matrix, called the LU decomposition, which remains numerically stable. This factorization is updated using advanced numerical methods (various matrix updates and dynamic Markowitz refactorization) that are much faster than a full update on each Simplex iteration. These methods enable the Large-Scale LP/QP Solver to maintain accuracy, find the optimal solution, and do so much faster than conventional methods.
Options for Mixed-Integer Linear Problems
The Large-Scale LP/QP Solver uses its own Branch and Bound method to handle integer variables and "alldifferent" constraints. If your problem includes integer constraints, you can obtain a quick solution of the relaxation (temporarily ignoring the integer constraints) without having to delete these constraints and then re-enter them later. You can control the number of Branch and Bound subproblems and the number of integer feasible solutions found before the Solver stops. And you can speed up the solution of problems with integer constraints by supplying an integer cutoff value -- often known from a previous run.
The Large-Scale LP/QP Solver employs an array of techniques, including powerful Cut Generation methods, for faster solution of mixed-integer linear programming problems -- in an overall Branch and Cut framework.
It uses Strong Branching to guide the choice of the next subproblem to explore, and the next integer variable to branch upon. It automatically generates a wide range of cuts -- new constraints that 'cut off' portions of the feasible region of LP subproblems without eliminating any possible integer solutions. Among others, Lift and Cover Cuts and new Clique Cuts are often highly effective in speeding up the Branch and Bound search, and Probing Cuts determine the values of some binary integer variables based on the settings of others.
It uses a Rounding Heuristic and a Local Search Heuristic to find new integer solutions "close to" existing solutions. These methods can save significant time on LP/MIP problems, depending on the model.