public class DantzigLCPSolver
extends java.lang.Object
w = M z + q
and solving it entails finding w and z subject to the constraints
T
w >= 0, z >= 0, w z = 0
Dantig's method does this by a series of pivoting operations. Each
pivot corresponds to one solver iteration and entails the exchange of a
single variable w_i with its complementary counterpart z_i. A sequence of
pivots results in the pivoted system
w' = M' z' + q'
where w' and z' contain complementary combinations of the w and z variables.
Any variable (w or z) contained in w' is called a basic variable.
When a pivoted system is found for which q' >=
0, this provides a
solution to the LCP in which the z and w variables comprising z' are 0 and
the z and w variables comprising w' are equal to the corresponding entries
in q'. As mentioned above, Dantzig's method only works when M is SPSD.
Full details on the solution of LCPs can be found in The Linear Complementarity Problem, by Cottle, Pang, and Stone.
Modifier and Type | Class and Description |
---|---|
static class |
DantzigLCPSolver.Status
Described whether or not a solution was found.
|
Modifier and Type | Field and Description |
---|---|
static int |
SHOW_ALL |
static int |
SHOW_MIN_RATIO |
static int |
SHOW_NONE |
static int |
SHOW_PIVOTS |
static int |
SHOW_QM |
static int |
SHOW_RETURNS |
static int |
SHOW_VARIABLES |
static int |
W_VAR_LOWER |
static int |
W_VAR_UPPER |
static int |
Z_VAR |
Constructor and Description |
---|
DantzigLCPSolver()
Creates a new Dantzig solver.
|
Modifier and Type | Method and Description |
---|---|
boolean |
getComputeResidual() |
int |
getDebug() |
int |
getIterationCount()
Returns the number of iterations, or pivots, that were used in the most
recent solution operation.
|
int |
getIterationLimit()
Gets the iteration limit for this solver.
|
double |
getResidual() |
boolean |
getSilent() |
double |
getTolerance()
Returns the numeric tolerence for this solver.
|
void |
resolve(VectorNd z,
VectorNd q,
boolean[] zBasic)
Solves the system
|
void |
setComputeResidual(boolean enable) |
void |
setDebug(int code) |
void |
setIterationLimit(int limit)
Sets the iteration limit for this solver.
|
void |
setSilent(boolean code) |
void |
setTolerance(double tol)
Sets the numeric tolerance for this solver.
|
DantzigLCPSolver.Status |
solve(VectorNd z,
MatrixNd M,
VectorNd q,
boolean[] zBasic)
Solves the LCP
|
DantzigLCPSolver.Status |
solve(VectorNd z,
VectorNd w,
MatrixNd M,
VectorNd q,
VectorNd lo,
VectorNd hi,
int nub,
int[] state) |
public static final int SHOW_NONE
public static final int SHOW_PIVOTS
public static final int SHOW_MIN_RATIO
public static final int SHOW_QM
public static final int SHOW_VARIABLES
public static final int SHOW_RETURNS
public static final int SHOW_ALL
public static int Z_VAR
public static int W_VAR_LOWER
public static int W_VAR_UPPER
public int getDebug()
public void setDebug(int code)
public boolean getSilent()
public void setSilent(boolean code)
public boolean getComputeResidual()
public void setComputeResidual(boolean enable)
public double getResidual()
public double getTolerance()
setTolerance(double)
public void setTolerance(double tol)
>=
0, as described in the class documentation. In particular, a
solution will be considered found whenever q' >=
-tol.tol
- new numeric tolerance. Negative numbers will be truncated to 0.getTolerance()
public int getIterationLimit()
public void setIterationLimit(int limit)
limit
- new iteration limitpublic int getIterationCount()
public DantzigLCPSolver.Status solve(VectorNd z, MatrixNd M, VectorNd q, boolean[] zBasic)
w = M z + qwhere M is SPSD. It is possible to use this routine to solve a mixed LCP, by pre-pivoting M and q to make the relevant non-LCP z variables basic and presetting the corresponding entries for these variables in zBasic to true.
z
- returns the solution for zM
- system matrixq
- system vectorzBasic
- On output, identifies which z variables are basic in the solution. On
input, identifies z variables which have been made basic as part of
solving a mixed LCP. If the LCP is not mixed, then all entries in this
array should be set to false.public void resolve(VectorNd z, VectorNd q, boolean[] zBasic)
w = M z + qusing the same matrix M and active set that was determined in the previous call to solve. Non-active z variables are set to 0.
z
- returns the solution for zq
- system vectorzBasic
- (optional) if specified, returns which z variables are basic in the
solution.