public class SparseLP extends Object implements Serializable, Cloneable
Class SparseLP
uses an infeasible primaldual interiorpoint
method to solve linear programming problems, i.e., problems of the form
where c is the objective coefficient vector, A is the coefficient matrix, and the vectors , , , and are the lower and upper bounds on the constraints and the variables, respectively.
Internally, SparseLP
transforms the problem given by the user
into a simpler form that is computationally more tractable. After redefining
the notation, the new form reads
Here, is a partition of the index set into upper bounded and standard variables.
In order to simplify the description it is assumed in the following that the problem above contains only variables with upper bounds, i.e. is of the form
The corresponding dual problem is
The KarushKuhnTucker (KKT) optimality conditions for (P) and (D) are
where are diagonal matrices and is a vector of ones.
Class SparseLP
, like all infeasible interiorpoint methods,
generates a sequence
of iterates that satisfy for all k, but are in general not feasible, i.e. the linear constraints (1.1)(1.3) are only satisfied in the limiting case .
The barrier parameter , defined by
measures how good the complementarity conditions (1.4), (1.5) are satisfied.
Mehrotra's predictorcorrector algorithm is a variant of Newton's method
applied to the KKT conditions (1.1)(1.5). Class SparseLP
uses a
modified version of this algorithm to compute the iterates
. In every step of the algorithm,
the search direction vector
is decomposed into two parts, , where and denote the affinescaling and the weighted centering components, respectively. Here,
where and denote the primal and dual corrector weights, respectively.
The vectors and are determined by solving the linear system
for two different righthand sides.
For , the righthand side is defined as
Here, and are the violations of the primal constraints and defines the violations of the dual constraints.
The resulting direction is the pure Newton step applied to the system (1.1)(1.5).
In order to obtain the corrector direction , the maximum stepsizes in the primal and in the dual space preserving nonnegativity of and respectively, are determined, and the predicted complementarity gap
is computed. It is then used to determine the barrier parameter
where denotes the current complementarity gap.
The direction is then computed by choosing
as the righthand side in the linear system (2).
Class SparseLP
now uses a line search to find the optimal weight
that maximizes the stepsizes
in the primal and dual directions of
, respectively.
A new iterate is then computed using a step reduction factor :
In addition to the weighted Mehrotra predictorcorrector,
SparseLP
also uses multiple centrality correctors to enlarge the
primaldual stepsizes per iteration step and to reduce the overall number of
iterations required to solve an LP problem. The maximum number of centrality
corrections depends on the ratio of the factorization and solve efforts for
system (2) and is therefore problem dependent. For a detailed description of
multiple centrality correctors, refer to Gondzio (1994).
The linear system (2) can be reduced to more compact forms, the augmented system (AS)
or further by elimination of to the normal equations (NE) system
where
The matrix on the lefthand side of (3), which is symmetric indefinite, can be transformed into a symmetric quasidefinite matrix by regularization. Since these types of matrices allow for a Choleskylike factorization, the resulting linear system can be solved easily for by triangular substitutions. For more information on the regularization technique, see Altman and Gondzio (1998). For the NE system, matrix is positive definite, and therefore a sparse Cholesky algorithm can be used to factor and solve the system for by triangular substitutions with the Cholesky factor L.
In class SparseLP
, both approaches are implemented. The AS
approach is chosen if A contains dense columns, if there are a
considerable number of columns in A that are much denser than the
remaining ones, or if there are many more rows than columns in the structural
part of A. Otherwise, the NE approach is selected.
Class SparseLP
stops with optimal termination status if the
current iterate satisfies the following three conditions:
and
where primalTolerance
, dualTolerance
and
optimalityTolerance
are primal infeasibility, dual infeasibility
and optimality tolerances, respectively. The default value is 1.0e10 for
optimalityTolerance
and 1.0e8 for the other two tolerances.
Class SparseLP
is based on the code HOPDM developed by Jacek
Gondzio et al., see the HOPDM User's Guide (1995).
Modifier and Type  Class and Description 

static class 
SparseLP.CholeskyFactorizationAccuracyException
The Cholesky factorization failed because of accuracy problems.

static class 
SparseLP.DiagonalWeightMatrixException
A diagonal element of the diagonal weight matrix is too small.

static class 
SparseLP.DualInfeasibleException
The dual problem is infeasible.

static class 
SparseLP.IllegalBoundsException
The lower bound is greater than the upper bound.

static class 
SparseLP.IncorrectlyActiveException
One or more LP variables are falsely characterized by the internal
presolver.

static class 
SparseLP.IncorrectlyEliminatedException
One or more LP variables are falsely characterized by the internal
presolver.

static class 
SparseLP.InitialSolutionInfeasibleException
The initial solution for the onerow linear program is infeasible.

static class 
SparseLP.PrimalInfeasibleException
The primal problem is infeasible.

static class 
SparseLP.PrimalUnboundedException
The primal problem is unbounded.

static class 
SparseLP.ProblemUnboundedException
The problem is unbounded.

static class 
SparseLP.TooManyIterationsException
The maximum number of iterations has been exceeded.

static class 
SparseLP.ZeroColumnException
A column of the constraint matrix has no entries.

static class 
SparseLP.ZeroRowException
A row of the constraint matrix has no entries.

Constructor and Description 

SparseLP(int[] colPtr,
int[] rowInd,
double[] values,
double[] b,
double[] c)
Constructs a
SparseLP object using Compressed Sparse Column
(CSC), or HarwellBoeing format. 
SparseLP(MPSReader mps)
Constructs a
SparseLP object using an MPSReader object. 
SparseLP(SparseMatrix a,
double[] b,
double[] c)
Constructs a
SparseLP object. 
Modifier and Type  Method and Description 

double 
getConstant()
Returns the value of the constant term in the objective function.

int[] 
getConstraintType()
Returns the types of general constraints in the matrix A.

double 
getDualInfeasibility()
Returns the dual infeasibility of the solution.

double 
getDualInfeasibilityTolerance()
Returns the dual infeasibility tolerance.

double[] 
getDualSolution()
Returns the dual solution.

int 
getIterationCount()
Returns the number of iterations used by the primaldual solver.

double 
getLargestCPRatio()
Returns the ratio of the largest complementarity product to the average.

double[] 
getLowerBound()
Returns the lower bound on the variables.

int 
getMaxIterations()
Returns the maximum number of iterations allowed for the primaldual
solver.

double 
getOptimalValue()
Returns the optimal value of the objective function.

int 
getPreordering()
Returns the variant of the Minimum Degree Ordering (MDO) algorithm used
in the preordering of the normal equations or augmented system matrix.

int 
getPresolve()
Returns the presolve option.

double 
getPrimalInfeasibility()
Returns the primal infeasibility of the solution.

double 
getPrimalInfeasibilityTolerance()
Returns the primal infeasibility tolerance.

int 
getPrintLevel()
Returns the print level.

double 
getRelativeOptimalityTolerance()
Returns the relative optimality tolerance.

double 
getSmallestCPRatio()
Returns the ratio of the smallest complementarity product to the average.

double[] 
getSolution()
Returns the solution x of the linear programming problem.

int 
getTerminationStatus()
Returns the termination status for the problem.

double[] 
getUpperBound()
Returns the upper bound on the variables.

double[] 
getUpperLimit()
Returns the upper limit of the constraints that have both a lower and an
upper bound.

double 
getViolation()
Returns the violation of the variable bounds.

void 
setConstant(double c0)
Sets the value of the constant term in the objective function.

void 
setConstraintType(int[] constraintType)
Sets the types of general constraints in the matrix A.

void 
setDualInfeasibilityTolerance(double dualTolerance)
Sets the dual infeasibility tolerance.

void 
setLowerBound(double[] lowerBound)
Sets the lower bound on the variables.

void 
setMaxIterations(int maxIterations)
Sets the maximum number of iterations allowed for the primaldual solver.

void 
setPreordering(int preorder)
Sets the variant of the Minimum Degree Ordering (MDO) algorithm used in
the preordering of the normal equations or augmented system matrix.

void 
setPresolve(int presolve)
Sets the presolve option.

void 
setPrimalInfeasibilityTolerance(double primalTolerance)
Sets the primal infeasibility tolerance.

void 
setPrintLevel(int printLevel)
Sets the print level.

void 
setRelativeOptimalityTolerance(double optimalityTolerance)
Sets the relative optimality tolerance.

void 
setUpperBound(double[] upperBound)
Sets the upper bound on the variables.

void 
setUpperLimit(double[] bu)
Sets the upper limit of the constraints that have both a lower and an
upper bound.

void 
solve()
Solves the sparse linear programming problem by an infeasible primaldual
interiorpoint method.

public SparseLP(int[] colPtr, int[] rowInd, double[] values, double[] b, double[] c)
SparseLP
object using Compressed Sparse Column
(CSC), or HarwellBoeing format. See Compressed Sparse Column (CSC)
Format, Chapter 1.colPtr
 an int
array containing the location in
values
in which to place the first nonzero value of each
succeeding column of the constraint matrix A. colPtr
,
rowInd
and values
specify the location and
value of each nonzero coefficient in the constraint matrix
A in CSC format.rowInd
 an int
array containing a list of the row
indices of each column of the constraint matrix
A. colPtr
, rowInd
and
values
specify the location and value of each nonzero
coefficient in the constraint matrix A in CSC format.values
 a double
array containing the value of each
nonzero coefficient in the constraint matrix A.
colPtr
, rowInd
and values
specify
the location and value of each nonzero coefficient in the constraint
matrix A in CSC format.b
 a double
array of length m, number of
constraints, containing the righthand side of the constraints; if there
are limits on both sides of the constraints, then b
contains
the lower limit of the constraintsc
 a double
array of length n, the number of
variables, containing the coefficients of the objective functionpublic SparseLP(MPSReader mps)
SparseLP
object using an MPSReader
object.mps
 an MPSReader
object specifying the Linear
Programming problempublic SparseLP(SparseMatrix a, double[] b, double[] c)
SparseLP
object.a
 a SparseMatrix
object containing the location and
value of each nonzero coefficient in the constraint matrix A. If
there is no constraint matrix, set a = null
.b
 a double
array of length m, the number of
constraints, containing the righthand side of the constraints. If there
are limits on both sides of the constraints, then b
contains
the lower limit of the constraints.c
 a double
array of length n, the number of
variables, containing the coefficients of the objective functionpublic double getConstant()
double
scalar containing the value of the constant
term in the objective functionpublic int[] getConstraintType()
setConstraintType
.int
array containing the types of general
constraints in the matrix Apublic double getDualInfeasibility()
double
scalar containing the dual infeasibility of
the solution, public double getDualInfeasibilityTolerance()
double
scalar containing the dual infeasibility
tolerancepublic double[] getDualSolution()
double
array containing the dual solutionpublic int getIterationCount()
int
scalar containing the number of iterations
used by the primaldual solverpublic double getLargestCPRatio()
double
scalar containing the ratio of the largest
complementarity product to the averagepublic double[] getLowerBound()
double
array containing the lower bound on the
variablespublic int getMaxIterations()
int
scalar containing the maximum number of
iterations allowed for the primaldual solverpublic double getOptimalValue()
double
scalar containing the optimal value of the
objective functionpublic int getPreordering()
setPreordering
.int
scalar containing the variant of the Minimum
Degree Ordering (MDO) algorithm used in the preordering of the normal
equations or augmented system matrixpublic int getPresolve()
setPresolve
.int
scalar containing the presolve optionpublic double getPrimalInfeasibility()
double
scalar containing the primal infeasibility
of the solution, public double getPrimalInfeasibilityTolerance()
double
scalar containing the primal infeasibility
tolerancepublic int getPrintLevel()
setPrintLevel
.int
scalar containing the print levelpublic double getRelativeOptimalityTolerance()
double
scalar containing the relative optimality
tolerancepublic double getSmallestCPRatio()
double
scalar containing the ratio of the smallest
complementarity product to the averagepublic double[] getSolution()
double
array containing the solution
x of the linear programming problempublic int getTerminationStatus()
int
scalar containing the termination status for
the problem
status 
Description 
0  Optimal solution found. 
1  The problem is primal infeasible (or dual unbounded). 
2  The problem is primal unbounded (or dual infeasible). 
3  Suboptimal solution found (accuracy problems). 
4  Iterations limit maxIterations exceeded. 
5  An error outside of the solution phase of the algorithm, e.g. a user input or a memory allocation error. 
public double[] getUpperBound()
double
array containing the upper bound on the
variablespublic double[] getUpperLimit()
double
array containing the upper limit of the
constraints that have both a lower and an upper bound. Returns
null
if the upper limit has not been set.public double getViolation()
double
scalar containing the violation of the
variable bounds, public void setConstant(double c0)
c0
 a double
scalar containing the value of the
constant term in the objective function
Default: c0 = 0
public void setConstraintType(int[] constraintType)
constraintType
 an int
array of length m
containing the types of general constraints in the matrix A. Let
. Then, the
value of constraintType[i]
signifies the following:
constraintType 
Constraint 
0  
1  
2  
3  
4  Ignore this constraint 
Note that constraintType[i] = 3
should only be used for constraints
i
with both a finite lower and a finite upper bound. For
onesided constraints, use constraintType[i] = 1
or
constraintType[i] = 2
. For free constraints, use
constraintType[i] = 4
.
Default: constraintType[i] = 0
public void setDualInfeasibilityTolerance(double dualTolerance)
dualTolerance
 a double
scalar containing the dual
infeasibility tolerance
Default: dualTolerance = 1.0e8
public void setLowerBound(double[] lowerBound)
lowerBound
 a double
array of length n
containing the lower bound on the variables. If
there is no lower bound on a variable, then 1.0e30 should be set as the
lower bound.
Default: lowerBound[i] = 0
public void setMaxIterations(int maxIterations)
maxIterations
 an int
scalar containing the maximum
number of iterations allowed for the primaldual solver
Default: maxIterations = 200
public void setPreordering(int preorder)
preorder
 an int
scalar containing the variant of the
Minimum Degree Ordering (MDO) algorithm used in the preordering of the
normal equations or augmented system matrix
preorder  Method 
0  A variant of the MDO algorithm using pivotal cliques. 
1  A variant of George and Liu's Quotient Minimum Degree algorithm. 
Default: preorder = 0
public void setPresolve(int presolve)
presolve
 an int
containing the the presolve option to
resolve the LP problem in order to reduce the problem size or to detect
infeasibility or unboundedness of the problem. Depending on the number of
presolve techniques used, different presolve levels can be chosen:
presolve  Description 
0  No presolving. 
1  Eliminate singleton rows. 
2  In addition to 1, eliminate redundant (and forcing) rows. 
3  In addition to 1 and 2, eliminate dominated variables. 
4  In addition to 1, 2, and 3, eliminate singleton columns. 
5  In addition to 1, 2, 3, and 4, eliminate doubleton rows. 
6  In addition to 1, 2, 3, 4, and 5, eliminate aggregate columns. 
Default: presolve = 0
public void setPrimalInfeasibilityTolerance(double primalTolerance)
primalTolerance
 a double
scalar containing the primal
infeasibility tolerance
Default: primalTolerance = 1.0e8
public void setPrintLevel(int printLevel)
printLevel
 an int
containing the print level
printLevel  Action 
0  No printing. 
1  Prints statistics on the LP problem and the solution process. 
Default: printLevel = 0
public void setRelativeOptimalityTolerance(double optimalityTolerance)
optimalityTolerance
 a double
scalar containing the
relative optimality tolerance
Default: optimalityTolerance = 1.0e10
public void setUpperBound(double[] upperBound)
upperBound
 a double
array of length n
containing the upper bound on the variables. If
there is no upper bound on a variable, then 1.0e30 should be set as the
upper bound.
Default: None of the variables has an upper bound
public void setUpperLimit(double[] bu)
bu
 a double
array of length m containing the
upper limit of the constraints that have both a
lower and an upper bound. If such a constraint exists, then method
setConstraintType
must be used to define the type of the
constraints. If constraintType[i] != 3
, i.e. if constraint
i
is not twosided, then the corresponding entry in
bu
, bu[i]
, is ignored.
Default: None of the constraints has an upper limit
public void solve() throws SparseLP.DiagonalWeightMatrixException, SparseLP.CholeskyFactorizationAccuracyException, SparseLP.PrimalUnboundedException, SparseLP.PrimalInfeasibleException, SparseLP.DualInfeasibleException, SparseLP.InitialSolutionInfeasibleException, SparseLP.TooManyIterationsException, SparseLP.ProblemUnboundedException, SparseLP.ZeroColumnException, SparseLP.ZeroRowException, SparseLP.IncorrectlyEliminatedException, SparseLP.IncorrectlyActiveException, SparseLP.IllegalBoundsException
SparseLP.DiagonalWeightMatrixException
 is thrown if a diagonal element of
the diagonal weight matrix is too smallSparseLP.CholeskyFactorizationAccuracyException
 is thrown if the Cholesky
factorization failed because of accuracy problemsSparseLP.PrimalUnboundedException
 is thrown if the primal problem is
unboundedSparseLP.PrimalInfeasibleException
 is thrown if the primal problem is
infeasibleSparseLP.DualInfeasibleException
 is thrown if the dual problem is
infeasibleSparseLP.InitialSolutionInfeasibleException
 is thrown if the initial
solution for the onerow linear program is infeasibleSparseLP.TooManyIterationsException
 is thrown if the maximum number of
iterations has been exceededSparseLP.ProblemUnboundedException
 is thrown if the problem is unboundedSparseLP.ZeroColumnException
 is thrown if a column of the constraint
matrix has no entriesSparseLP.ZeroRowException
 is thrown if a row of the constraint matrix has
no entriesSparseLP.IncorrectlyEliminatedException
 is thrown if one or more LP
variables are falsely characterized by the internal presolverSparseLP.IncorrectlyActiveException
 is thrown if one or more LP variables
are falsely characterized by the internal presolverSparseLP.IllegalBoundsException
 is thrown if the lower bound is
greater than the upper boundCopyright © 19702015 Rogue Wave Software
Built October 13 2015.