DenseLP (JMSL Numerical Library (jmsl) 2021.0.0 API)

java.lang.Object
- com.imsl.math.DenseLP

All Implemented Interfaces:

Serializable, Cloneable
```
public class DenseLP
extends Object
implements Serializable, Cloneable
```
Solves a linear programming problem using an active set strategy.
Class DenseLP uses an active set strategy to solve linear programming problems, i.e., problems of the form

$$\mathop {\min }\limits_{x\; \in \;R^n } c^T x$$

subject to

$$b_l \le Ax \le b_u$$

$$\,\,x_l \le x \le x_u$$

where c is the objective coefficient vector, A is the coefficient matrix, and the vectors $b_l$, $b_u$, $x_l$, and $x_u$ are the lower and upper bounds on the constraints and the variables, respectively.

If the linear constraints are infeasible an $L_1$ solution to the constraints are used as a replacement for the stated constraints. An exception is thrown but a generalized solution is computed and available using methods getPrimalSolution or getDualSolution. Similar comments hold for any of the three additional conditions: (1) There are multiple solutions; (2) some constraints are discarded, or (3) cycling in the algorithm is identified.

Refer to the following paper for further information:

Krogh, Fred, T. (2005), see An Algorithm for Linear Programming http://mathalacarte.com/fkrogh/pub/lp.pdf

See Also:

Example1, Example2, Example3, Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static class`	`DenseLP.AllConstraintsNotSatisfiedException` All constraints are not satisfied.
`static class`	`DenseLP.BoundsInconsistentException` The bounds given are inconsistent.
`static class`	`DenseLP.CyclingOccurringException` The algorithm appears to be cycling.
`static class`	`DenseLP.MultipleSolutionsException` The problem has multiple solutions giving essentially the same minimum.
`static class`	`DenseLP.NoAcceptablePivotException` No acceptable pivot could be found.
`static class`	`DenseLP.NoConstraintsAvailableException` The LP problem has no constraints.
`static class`	`DenseLP.ProblemUnboundedException` The problem is unbounded.
`static class`	`DenseLP.ProblemVacuousException` The problem is vacuous.
`static class`	`DenseLP.SomeConstraintsDiscardedException` Some constraints were discarded because they were too linearly dependent on other active constraints.
`static class`	`DenseLP.WrongConstraintTypeException` Deprecated. No longer used, replaced with an `IllegalArgumentException`.

Constructor Summary

Constructors
Constructor and Description
`DenseLP(double[][] a, double[] b, double[] c)` Constructor variables of type `double`.
`DenseLP(MPSReader mps)` Constructor using an MPSReader object.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`Object`	`clone()` Creates and returns a copy of this object.
`double[]`	`getDualSolution()` Returns the dual solution.
`int`	`getIterationCount()` Returns the iteration count.
`double`	`getOptimalValue()` Returns the optimal value of the objective function.
`double[]`	`getPrimalSolution()` Returns the solution x of the linear programming problem.
`void`	`setConstraintType(int[] constraintType)` Sets the types of general constraints in the matrix `a`.
`void`	`setLowerBound(double[] lowerBound)` Sets the lower bound, $x_l$, on the variables.
`void`	`setRefinementType(int iRefinement)` Set the type of refinement used.
`void`	`setUpperBound(double[] upperBound)` Sets the upper bound, $x_u$, on the variables.
`void`	`setUpperLimit(double[] upperLimit)` Sets the upper limit of the constraints.
`void`	`solve()` Solves the problem using an active set method.

Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail
- DenseLP
```
public DenseLP(MPSReader mps)
```
  Constructor using an MPSReader object.
  
  Parameters:
  
  mps - An MPSReader object specifying the Linear Programming problem.
  
  Throws:
  
  IllegalArgumentException - is thrown if the problem dimensions are not consistent.
- DenseLP
```
public DenseLP(double[][] a,
               double[] b,
               double[] c)
```
  Constructor variables of type double.
  
  Parameters:
  
  a - A double matrix with coefficients of the constraints.
  
  b - A double array containing the right-hand side of the constraints.
  
  c - A double array containing the coefficients of the objective function.
  
  Throws:
  
  IllegalArgumentException - is thrown if the dimensions of a, b.length, and c.length are not consistent.

Method Detail

clone
```
public Object clone()
```
Creates and returns a copy of this object.

Overrides:

clone in class Object

solve
```
public final void solve()
                 throws DenseLP.BoundsInconsistentException,
                        DenseLP.NoAcceptablePivotException,
                        DenseLP.ProblemUnboundedException,
                        DenseLP.ProblemVacuousException,
                        DenseLP.AllConstraintsNotSatisfiedException,
                        DenseLP.MultipleSolutionsException,
                        DenseLP.SomeConstraintsDiscardedException,
                        DenseLP.CyclingOccurringException,
                        DenseLP.NoConstraintsAvailableException
```
Solves the problem using an active set method. solve must be invoked prior to calling any of the "get" methods.

Throws:

DenseLP.BoundsInconsistentException - is thrown if the bounds are inconsistent.

DenseLP.NoAcceptablePivotException - is thrown if an acceptable pivot could not be found.

DenseLP.ProblemUnboundedException - is thrown if there is no finite solution to the problem.

DenseLP.ProblemVacuousException - is thrown if the problem is vacuous.

DenseLP.AllConstraintsNotSatisfiedException - is thrown if all constraints are not satisfied.

DenseLP.MultipleSolutionsException - is thrown if the problem has multiple solutions.

DenseLP.SomeConstraintsDiscardedException - is thrown if some constraints were discarded because they were too linearly dependent on other active constraints.

DenseLP.CyclingOccurringException - is thrown if the algorithm appears to be cycling.

DenseLP.NoConstraintsAvailableException - is thrown if all constraints are of constraint type 4.

setRefinementType

public void setRefinementType(int iRefinement)

Set the type of refinement used.

Parameters:

iRefinement - An int scalar value which defines the type of refinement to be used. The possible settings are:

iRefinement	Action
0	No refinement. Always compute dual. Default.
1	Iterative refinement.
2	Use extended refinement. Iterate until no more progress.

If refinement is used, the coefficient matrices and other data are saved at the beginning of the computation. When finished this data together with the solution obtained is checked for consistency. If the discrepancy is too large, the solution process is restarted using the problem data just after processing the equalities, but with the final x values and final active set.

setUpperLimit
```
public void setUpperLimit(double[] upperLimit)
```
Sets the upper limit of the constraints.

Parameters:

upperLimit - a double array containing the upper limit, $b_u$, of the constraints.

setLowerBound
```
public void setLowerBound(double[] lowerBound)
```
Sets the lower bound, $x_l$, on the variables. If there is no lower bound on a variable, then 1.0e30 should be set as the lower bound.

Parameters:

lowerBound - a double array containing the lower bound on the variables. Default = 0.

setUpperBound
```
public void setUpperBound(double[] upperBound)
```
Sets the upper bound, $x_u$, on the variables. If there is no upper bound on a variable, then -1.0e30 should be set as the upper bound.

Parameters:

upperBound - a double array containing the upper bound on the variables. The default is no upper bound.

setConstraintType

public void setConstraintType(int[] constraintType)

Sets the types of general constraints in the matrix a.

Parameters:

constraintType - an int array containing the types of general constraints. Let $ r_i=a_{i1}x_1+...+a_{in}x_n$. Then the value of constraintType[i] signifies the following:

constraintType	Constraint
0	${\rm {r}}_i = {\rm {b}}_i$
1	${\rm {r}}_i \le {\rm {b}}_i \,\,\, or \,\,\, {\rm {r}}_i \le {\rm {b}}_{{\rm {u}}_i} \,\,\, if \,\,supplied$
2	${\rm {r}}_i \ge {\rm {b}}_i$
3	${\rm {b}}_i \le {\rm {r}}_i \le {\rm {b}}_{{\rm {u}}_i}$
4	Ignore this constraint

Default=0.

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

Returns:

a double scalar containing the optimal value of the objective function. If a solution has not been computed, Double.NaN is returned.

getIterationCount
```
public int getIterationCount()
```
Returns the iteration count.

Returns:

an int scalar containing the iteration count.

getPrimalSolution
```
public double[] getPrimalSolution()
```
Returns the solution x of the linear programming problem.

Returns:

a double array containing the solution x of the linear programming problem.

getDualSolution
```
public double[] getDualSolution()
```
Returns the dual solution.

Returns:

a double array containing the dual solution of the linear programming problem.

constraintType	Constraint
0	\({\rm {r}}_i = {\rm {b}}_i\)
1	\({\rm {r}}_i \le {\rm {b}}_i \,\,\, or \,\,\, {\rm {r}}_i \le {\rm {b}}_{{\rm {u}}_i} \,\,\, if \,\,supplied\)
2	\({\rm {r}}_i \ge {\rm {b}}_i\)
3	\({\rm {b}}_i \le {\rm {r}}_i \le {\rm {b}}_{{\rm {u}}_i}\)
4	Ignore this constraint

Class DenseLP

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

DenseLP

DenseLP

Method Detail

clone

solve

setRefinementType

setUpperLimit

setLowerBound

setUpperBound

setConstraintType

getOptimalValue

getIterationCount

getPrimalSolution

getDualSolution