Contents

Introduction 2

Program Overview........................................................................................................................... 2

Primal Problem............................................................................................................................... 2

Dual Problem................................................................................................................................... 2

Overview 2

Program Interface........................................................................................................................... 2

LP Problem Example...................................................................................................................... 2

C Programming Interface............................................................................................................... 2

MPS and QPS File Interface.......................................................................................................... 2

Examples 2

Discussion....................................................................................................................................... 2

Example 1c.c: LP Problem and C Interface (coordinate form).................................................. 2

Example 2c.c: QP Problem and C Interface (coordinate form)................................................. 2

Example 1.c: LP Problem and C Interface (sparse column format)........................................... 2

Example 2.c: QP Problem and C Interface (sparse column format).......................................... 2

Example 1.mps: LP Problem and MPS Interface......................................................................... 2

Example 2.qps: QP Problem and QPS Interface.......................................................................... 2

The LP_QP_Solve C Interface 2

Discussion....................................................................................................................................... 2

LP_QP_Solve.................................................................................................................................. 2

LP_QP_Problem_init..................................................................................................................... 2

LP_QP_Solution_init..................................................................................................................... 2

LP_QP_Options_init...................................................................................................................... 2

LP_QP_Problem_C_init................................................................................................................ 2

put_LP_QP_Problem_C................................................................................................................ 2

LP_QP_Problem_From_C............................................................................................................ 2

Free_LP_QP_Options.................................................................................................................... 2

Free_LP_QP_Solution................................................................................................................... 2

Free_LP_QP_Problem................................................................................................................... 2

Free_LP_QP_Problem_C.............................................................................................................. 2

LP_QP_Problem_Check................................................................................................................ 2

LP_QP_Problem_C_Check........................................................................................................... 2

The PAR File and Algorithmic Parameters 2

Discussion....................................................................................................................................... 2

Input/Output Parameters................................................................................................................. 2

Optimization Parameters................................................................................................................ 2

Parameters for Handling Sparsity................................................................................... 2

Supernode Parameters..................................................................................................... 2

Pivot and Factorization Parameters................................................................................ 2

Stopping Criterion Parameters....................................................................................... 2

Numerical Tolerances...................................................................................................... 2

Iterative Refinement Parameters.................................................................................... 2

Scaling Parameters........................................................................................................... 2

Predictor-Corrector and Barrier Parameters................................................................ 2

Centrality Corrections Parameters................................................................................. 2

Steplength Parameters..................................................................................................... 2

Starting Point Parameters................................................................................................ 2

Presolve Parameters........................................................................................................ 2

Regularization Parameters.............................................................................................. 2

Data Structure Declarations 2

Discussion....................................................................................................................................... 2

LP_QP_Problem_C........................................................................................................................ 2

LP_QP_Problem............................................................................................................................. 2

LP_QP_Solution............................................................................................................................. 2

LP_QP_Options.............................................................................................................................. 2

MATLAB Interface 2

Discussion....................................................................................................................................... 2

Example 1........................................................................................................................................ 2

Example 2........................................................................................................................................ 2

MATLAB functions (m-files)........................................................................................................ 2

References 2

References....................................................................................................................................... 2

Windward Technologies, Inc.......................................................................................................... 2

Restricted Rights Legend............................................................................................................... 2

Credits.............................................................................................................................................. 2

Introduction

Program Overview

LP_QP_Solve is a program that solves sparse linear programs (LPs) and sparse convex quadratic programs (QPs). LP_QP_Solve solves the primal and dual problems described below. The theory relating the primal and dual problems is discussed in many texts (see for example Bazaraa and Shetty).

LP_QP_Solve is a state-of-the-art C implementation of the primal-dual interior point algorithm. The main algorithmic 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 that:

removes empty rows/columns
removes singleton rows
eliminates free (or implied free) singleton columns
removes redundant constraints and fixes variables based on minimum/maximum constraints activity
does the above on the dual problem
substitutes duplicated variables
removes redundant bounds on variables
eliminates free (or implied free) variables
makes the constraint matrix sparser

The linear algebra is especially advanced. It contains sophisticated techniques that:

make decisions between normal equation and augmented system approach
scale the problem for better numerical properties
produce advanced symbolic ordering for normal equations approach
use left-looking supernodal factorization algorithm with loop unrolling
use supernodal backsolve with loop unrolling
increase numerical robustness (Iterative refinement, PCG, QMR)

Significant interface issues addressed by LP_QP_Solve include:

support for an easy to use sparse coordinate input format
support for C structures that package variables in a natural grouping
routines for checking the consistency of these structures
support for the MPS and QPS file formats

Primal Problem

LP_QP_Solve solves the standard LP problem:

Min c^T x

Subject to: a £ A x £ b, d £ x £ e

LP_QP_Solve can also solve the standard QP problem:

Min c^Tx + (x^T 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 Rⁿ, and the vectors a and b are in R^m. The matrices Q and A are n by n and m by n respectively and Q is positive semi-definite. This is the primal form of the LP and QP problem.

Dual 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 d^T w1 - c^T w2 + a^T w3 - b^T w4

Subject to: w1 - w2 + A^t(w3 - w4) = c, 0 £ (w1, w2, w3, w4)

The dual form of the QP problem is:

Max d^T w1 - c^T w2 + a^T w3 - b^T w4 - (y^TQ y) / 2

Subject to: -Q y + w1-w2 + A^T(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

d^T w1 - c^T w2 + a^T w3 - b^T w4 - ( y^TQ y) / 2 £ c^Tx + (x^TQ 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 w1_j - w2_j ³ 0 implies w2_j = 0 and w1_j - w2_j £ 0 implies w1_j =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).

Overview

Program Interface

There are two ways to access the functionality of LP_QP_Solve, C programming and MPS file. To use the C programming interface, you supply the problem data in a data structure called LP_QP_Problem and then you call the C function LP_QP_Solve to solve the problem. All LP_QP_Solve C functions are available through the LP_QP_Solve DLL, LP_QP.dll. To use the MPS or QPS file interface, you provide the problem as an MPS or QPS file, a specifically formatted file containing the data for the LP or QP problem, and execute the LP_QP_Solve program, LP_QP.exe.

LP Problem Example

The LP problem given below is named Example 1 and it is used throughout this manual to describe the C programming interface and the MPS file interface for LP_QP_Solve. A complete C program for Example 1 is provided in file Example_1c.c and Example_1.c. The MPS input for Example 1 is provided in file Example_1.mps. Both of these files are part of the LP_QP_Solve product.

Min     -x1 + 4x2 - 9x3 + x4

Subject to:

              [ 1   0   5   7 ] (x1)

        0 <=  [ 0   3   6   8 ] (x2)  <= 10

              [ 2   4   0   9 ] (x3)

                                (x4)

        0 <= x1, x2, x3, x4

Optimal value   = -50/3

Primal Solution = (5/3, 0, 5/3, 0)

Dual solution   = (0, 6, 0, 40/3, -1, -2/3, 0)

C Programming Interface

The LP_QP_Solve C interface uses four structures, two independent structures for the problem, one for program options, and one for the solution. A C program would declare all three or four structures and initialize them. The program must provide values for the problem structure. The program might provide values for some options or it might just use the default option values. The problem structure and the options structure are passed as arguments to LP_QP_Solve, the C function that computes a solution and returns it to the program in the solution structure. The C program should be linked to the LP_QP_Solve DLL, LP_QP.dll.

The C code segments shown below illustrate how this is done for the sparse column structure LP_QP_Problem.

struct LP_QP_Problem  *prob;

struct LP_QP_Solution *sol;

struct LP_QP_Options  *opt;

/* initialize problem structure

    3 rows

    4 columns

    9 nonzero elements in A

    0 nonzero elements in Q

    0 quadratic variables

*/

prob = LP_QP_Problem_init(3, 4, 9, 0, 0);

/* initialize options structure */

opt  = LP_QP_Options_init();

/* Fill out problem values here */

/* compute a solution and

   return it in the solution structure */

sol = LP_QP_Solve(prob, opt);

The LP_QP_Solve sparse column problem structure (LP_QP_Problem) has following components:

Problem Component	Description	Value for Example 1
prob->m	Number of rows of A (constraints)	3
prob->n	Number of columns of A (variables)	4
prob->num_quad_vars	Number of quadratic variables	0
prob->num_nza	Number of non-zero elements of A	9
prob->num_nzq	Number of non-zero elements of Q	0
prob->a	Non-zeros of A in column order	(1,2,3,4,5,6,7,8,9)
prob->q	Non-zero elements of the lower triangular part of Q in column order	(empty)
prob->a_col_count	Number of non-zeros in each column of A	(2,2,2,3)
prob->a_row_index	The row indices of the entries in prob->a	(1,3,2,3,1,2,1,2,3)
prob->q_col_count	Number of non-zero elements in each column of the lower triangle of Q	(empty)
prob->q_row_index	The row indices of the entries in prob->q	(empty)
prob->obj	The vector c	(-1, 4, -9, 1)
prob->xlb	The lower bounds on x (use -1e30 for negative infinity)	(0,0,0,0)
prob->xub	The upper bounds on x (use 1e30 for infinity)	*(1,1,1,1)1e30**
prob->axlb	The lower bounds on A x (use -1e30 for negative infinity)	(0,0,0,0)
prob->axub	The upper bounds on A x (use 1e30 for infinity)	(10,10,10,10)

The LP_QP_Solve coordinate problem structure (LP_QP_Problem_C) facilitates placing the nonzeros into the sparse column structure by allowing the user to use the coordinate structure (or use the put_LP_QP__Problem_C function) to place the nonzeros of A and Q into this structure. See Example_1c.c and Example_2c.c for usage of this structure. LP_QP_Problem_C has following components:

Problem Component	Description	Value for Example 1
prob->m	Number of rows of A (constraints)	3
prob->n	Number of columns of A (variables)	4
prob->max_num_nza	An upper bound for the number of non-zero elements of A	>= 9
prob->max_num_nzq	An upper bound for the number of non-zero elements of Q	>= 0
prob->num_nza	Number of non-zero elements of A	9
prob->num_nzq	Number of non-zero elements of Q	0
prob->a	Non-zeros of A in any order	(1,2,3,4,5,6,7,8,9)
prob->q	Non-zero elements of the lower triangular part of Q	(empty)
prob->a_row_index	The row indices of the entries in prob->a	(1,3,2,3,1,2,1,2,3)
prob->a_col_index	The column indices of the entries in prob->a	(1,1,2,2,3,3,4,4,4)
prob->q_row_index	The row indices of the entries in prob->q	(empty)
prob->q_col_index	The column indices of the entries in prob->q	(empty)
prob->obj	The vector c	(-1, 4, -9, 1)
prob->xlb	The lower bounds on x (use -1e30 for negative infinity)	(0,0,0,0)
prob->xub	The upper bounds on x (use 1e30 for infinity)	*(1,1,1,1)1e30**
prob->axlb	The lower bounds on A x (use -1e30 for negative infinity)	(0,0,0,0)
prob->axub	The upper bounds on A x (use 1e30 for infinity)	(10,10,10,10)

The LP_QP_Solve coordinate solution structure has following components:

Solution Component	Description	Value for Example 1
sol->primal_len	An integer indicating the length of the primal solution	4
sol->dual_len	An integer indicating the length of the dual solution	4+3
sol->status_len	An integer indicating the length of the status vector	4+3
sol->value	The value of the LP	-50/3
sol->primal	A pointer to the primal solution	(5/3, 0, 5/3, 0)
sol->dual	A pointer to the dual solution	(0, 6, 0, 40/3, -1, -2/3, 0)
sol->status	The status of each of the primal and dual variables (basic or nonbasic)	(1,0,1,0,0,0,1) The 1's correspond to basic primal variables and the 0's to basic dual variables.
sol->error_code	Error code for the problem	0