Quadratic Programming and Linear Programming Solver

Frontline Systems' optimizers solve linear programming (LP) and quadratic programming (QP) problems using these methods:

For an explanation of these types of problems, please see Optimization Problem Types: Linear Programming and Quadratic Programming.

Primal and Dual Simplex Method

The standard Microsoft Excel Solver uses a basic implementation of the primal Simplex method to solve LP problems.  It is limited to 200 decision variables.The Premium Solver uses an improved primal Simplex method with two-sided bounds on the variables.  It handles up to 1,000 decision variables.  The Premium Solver Platform uses an extended LP/Quadratic version of this Simplex Solver to handle problems of up to 2,000 decision variables.  It optionally uses a dual Simplex method to solve LP subproblems in a mixed-integer (MIP) problem.  However, this Simplex algorithm does not exploit sparsity in the model.

The Large-Scale LP Solver for the Premium Solver Platform uses a state-of-the-art implementation of the primal and dual Simplex method, which fully exploits sparsity in the LP model to save time and memory. It uses advanced strategies for matrix updating and refactorization, multiple and partial pricing and pivoting, and overcoming degeneracy. This Solver engine is available in three versions, handling up to 8,000, 32,000, or an unlimited number of variables and constraints, subject to available time and memory.

The MOSEK Solver includes a state-of-the-art primal and dual Simplex method that also exploits sparsity and uses advanced strategies for matrix updating and refactorization.  It handles problems of unlimited size, and has been tested on linear programming problems of over a million decision variables.

The XPRESS Solver Engine and Gurobi Solver Engine both use a highly tuned, state-of-the-art implementation of the primal and dual Simplex method, with advanced strategies for matrix updating and refactorization, multiple and partial pricing and pivoting, and overcoming degeneracy.  Both of these Solver engines can handle an unlimited number of variables and constraints, subject to available time and memory.

Active Set Method

The Large-Scale SQP Solver for the Premium Solver Platform uses a state-of-the-art implementation of an active set method for solving linear (and quadratic) programming problems, which fully exploits sparsity in the model to save time and memory, and uses modern matrix factorization methods for numerical stability.  It can handle problems of unlimited size, subject to available time and memory.

The KNITRO Solver includes an advanced active set method for solving linear and quadratic programming problems, that also exploits sparsity and uses modern matrix factorization methods.  It can handle problems of unlimited size, subject to available time and memory.

Interior Point or Newton-Barrier Method

The Premium Solver Platform includes an SOCP Barrier Solver that uses an Interior Point method to solve LP, QP, QCP, and SOCP problems up to 2,000 decision variables with excellent performance.  See the discussion of Optimization Problem Types - Quadratic Constraints and Conic Optimization for more information.

The XPRESS Solver Engine uses a state-of-the-art implementation of the primal-dual path-following Interior Point or Newton-Barrier method, based on Mehrotra's predictor-corrector algorithm.  It includes high performance linear algebra methods for the normal equations matrix and advanced ordering algorithms for factorizing this matrix. The XPRESS Solver engine is capable of "crossing over" from the Newton-Barrier method to the Simplex method near the optimal solution, in order to generate sensitivity analysis information.

The MOSEK Solver uses a state-of-the-art implementation of an Interior Point or Newton-Barrier method, called the Homogeneous Self-Dual method, to solve LP, QP, QCP, and SOCP problems of unlimited size, subject to available time and memory.

Quadratic Programming

As noted above, the Premium Solver Platform uses an extended LP/Quadratic version of the Simplex method with bounds on the variables to handle LP and QP problems of up to 2,000 decision variables.  This solver is capable of finding optimal solutions for positive definite or semi-definite quadratic objectives (when minimizing; negative definite or semi-definite when maximizing).

Also as noted above, the Large-Scale SQP Solver uses a state-of-the-art implementation of a sparsity-exploiting active set method for solving quadratic programming (QP) problems.  It is especially effective on tightly constrained QP problems.The XPRESS Solver engine uses the natural extension of the Interior Point or Newton-Barrier method to solve QP problems.  It is able to solve extremely large quadratic programming problems, if sufficient memory is available.  However, it is appropriate only for positive definite quadratic objectives (when minimizing; negative definite when maximizing).

The MOSEK Solver uses a state-of-the-art Interior Point method, the Homogeneous Self-Dual method, to solve large-scale LP and QP problems.  It is especially effective on loosely constrained QP problems.  It can also solve large-scale quadratically constrained (QCP) and second order cone programming (SOCP) problems. 

See the discussion of Optimization Problem Types - Quadratic Constraints and Conic Optimization for more information.