LP_QP_Solve solves sparse linear programs (LPs) and sparse convex quadratic programs (QPs). The program is a state-of-the-art C implementation of the primal-dual interior point algorithm. The main features of the package are the highly flexible sparsity handling, including minimum local fill-in ordering and augmented system formulation, fast and robust linear algebra based on supernodal elimination and advanced presolve techniques. LP_QP_Solve can be used as a callable library, and also accepts problems in standard MPS format. It is designed to solve large problems with thousands of variables and thousands of constraints.
LP_QP_Solve solves the standard LP problem:
Min cT x
Subject to: a £ A x £ b, d £ x £ e
and it also solves the standard QP problem:
Min cT x + (xT Q x) / 2
Subject to: a £ A x £ b, d £ x £ e
In both the LP and QP problems, c, x, d, and e are all vectors in Rn, and the vectors a and b are in Rm. The matrices Q and A are n by n and m by n respectively and Q is positive semi-definite. This is primal form of the LP and QP problem.
LP and QP problems also have a dual form. The dual problems yield additional information concerning the sensitivity of the solution of the primal problem. The dual form of the LP problem is:
Max dT w1 - cT w2 + aT w3 - bT w4
Subject to: w1 - w2 + At(w3 - w4) = c, 0 £ (w1, w2, w3, w4)
The dual form of the QP problem is:
Max dT w1 - cT w2 + aT w3 - bT w4 - (yT Q y) / 2
Subject to: -Q y + w1-w2 + AT (w3 - w4) = c, 0 £ (w1, w2, w3, w4)
Notice that if Q is zero then the primal QP problem reduces to the primal LP problem and the dual QP problem reduces to the dual LP problem.
The theory of the dual problem tells us that if we have a feasible point x for the primal problem and a feasible point (w1, w2, w3, w4, y) for the dual problem then
dT w1 - cT w2 + aT w3 - bT w4 - ( yT Q y) / 2 £ cTx + (xT Q x) / 2
Furthermore, when both the primal and dual problems have optimal solutions then the optimal values of these two programs are equal (and indeed y = x). LP_QP_Solve returns the dual solution in the form
(
(w1 - w2)T, (w3 - w4)T)where if w1j - w2j ³ 0 implies w2j = 0 and w1j - w2j £ 0 implies w1j =0. Similar relationships hold for w3 and w4. This is why it suffices to report only the m+n numbers ((w1 - w2)T, (w3 - w4)T) as opposed to the 2m+2n numbers (w1, w2, w3, w4).
LP_QP_Solve is available as a DLL and in C source code formats. The DLL version is specially designed for the Windows 95 operating system. The LP_QP_Solve User's Guide describes the C interface and gives examples using C and MATLAB. LP_QP_Solve also has an interface to handle MPS and QPS files. Contact The MathWorks, Inc. for more information about MATLAB.
The Windows 95 DLL version of LP_QP_Solve is available for $1995.
A single user development C source code license for LP_QP_Solve is priced at $5995. The C source code can be compiled and run on Windows and Unix systems.
Our Premier Partners program provides licensing terms and service specially designed to meet the needs of commercial software development organizations.
We offer discounts to universities.
Contact Windward Technologies for information about LP_QP_Solve and other WTI products.
View the LP_QP_Solve User's Guide
Back to the MAXTHIS home page.