Linear programs

The following routines attempt to solve linear programs of the form

\[\text{min}\, c^T z \;\;\;\text{such that }Az=b,\; z \ge 0.\]

using the Alternating Direction Method of Multipliers.

The following functions were inspired by a simple ADMM linear program solver due to Boyd et al. Elemental’s implementations make use of parallel (dense) linear algebra, a custom structured factorization, and allows the user to optionally directly invert the (pivoted) Schur complement to accelerate its application. The return value is the number of performed ADMM iterations.

C++ API

Int LinearProgram(const Matrix<Real> &A, const Matrix<Real> &b, const Matrix<Real> &c, Matrix<Real> &z, Real rho = 1., Real alpha = 1.2, Int maxIter = 500, Real absTol = 1e-6, Real relTol = 1e-4, bool inv = false, bool progress = true)
Int LinearProgram(const AbstractDistMatrix<Real> &A, const AbstractDistMatrix<Real> &b, const AbstractDistMatrix<Real> &c, AbstractDistMatrix<Real> &z, Real rho = 1., Real alpha = 1.2, Int maxIter = 500, Real absTol = 1e-6, Real relTol = 1e-4, bool inv = true, bool progress = true)

Implementation

Example driver

Parameters

Input/Output

Explanation

A

Input

part of constraints, \(Ax=b\)

b

Input

part of constraints, \(Ax=b\)

c

Input

part of the objective, \(c^T x\)

z

Output

primal solution (second term)

rho

Input

augmented-Lagrangian parameter

alpha

Input

over-relaxation parameter (usually in \([1,1.8]\))

maxIter

Input

maximum number of ADMM iterations

absTol

Input

absolute convergence tolerance

relTol

Input

relative convergence tolerance

inv

Input

directly compute Schur-complement inverse?

progress

Input

display detailed progress information?

C API

ElError ElLinearProgram_s(ElConstMatrix_s A, ElConstMatrix_s b, ElConstMatrix_s c, ElMatrix_s z, ElInt* numIts)
ElError ElLinearProgram_d(ElConstMatrix_d A, ElConstMatrix_d b, ElConstMatrix_d c, ElMatrix_d z, ElInt* numIts)
ElError ElLinearProgramDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s b, ElConstDistMatrix_s c, ElDistMatrix_s z, ElInt* numIts)
ElError ElLinearProgramDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d b, ElConstDistMatrix_d c, ElDistMatrix_d z, ElInt* numIts)