LPsparse -- Sparse Linear Programming via Primal and Dual Coordinate Descent

Description

LPsparse is a general Linear Program (LP) solver based on Augmented Lagrangian + Coordinate Descent (AL-CD). The solver is especially suitable for Linear Program of huge number of variables (n) and constraints (m) with a sparse constraint matrix (A).

Download and Compile

You can download the code here.

Compile it by "make" in a unix system with g++.

Usage

Usage: ./LPsparse (options) [data_dir]

options:
-d solve_dual: solve dual to obtain solution of primal problem (default: No)
-c use_cg: use projected-conjugate gradient method to obtain faster asymptotic convergence (default: No)
-t tol: tolerance of primal and dual infeasibility for terminiation (default: 1e-3)
-e eta: Augmented Lagragnain parameter (default: 1.0)
-p tol_phase2: tolerance for changing to phase 2 (default: 1e-2)
-s tol_sub: tolerance for solving sub-problem in phase-1 (default: 1e-3)
-m max_iter: maximum number of outer iterations (default 1000)
-n nnz_tol: truncate a value to 0 if less than nnz_tol for the output (default 1e-4)

Data Format (example)

(All indexes begin with 1 instead of 0)

$ ls data/
A  Aeq  b  beq  c  meta

$ cat data/meta
nb      44858
nf      0
mI      3000
mE      0

$ head -3 data/A;   echo '...';   tail -1 data/A
3000    44858   0.0
1       958     -0.516262
1       3714    -0.504788
...
3000    44858   -1

$ head -3 data/b;  echo '...';   tail -1 data/b
-1
-1
-1
...
-1

$ head -3 data/c;  echo '...';   tail -1 data/c
0.1
0.1
0.1
...
1

$ cat Aeq
0       44858   0.0

$ cat beq

Output Format (example)

$ ./LPsparse data/
$ head -3 sol;  echo '...';  tail -1 sol
54      0.112922
61      1.48597
73      0.662738
...
44284   1

$ head -3 dual_sol;  echo '...';  tail -1 dual_sol
1       0.151798
6       0.0730839
38      0.142018
...
2992    0.0630901

Examples

Solve by Primal AL-CD (when number of non-zero variables is small at optimal):
	$ ./LPsparse data/

Solve by Dual AL-CD (when number of binding constrains is small at optimal):
	$ ./LPsparse -d data/

Higher precision by phase-2 Newton-CG:
	(primal) $ ./LPsparse -t 1e-7 -c data/
	(dual)   $ ./LPsparse -d -t 1e-7 -c data/

Citation

You are welcome to use the code. For citation, please use: