JMSLTM Numerical Library 4.0

com.imsl.math
Class DenseLP

java.lang.Object
  extended bycom.imsl.math.DenseLP
All Implemented Interfaces:
Cloneable, Serializable

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 A_x  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. 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, Serialized Form

Nested Class Summary
static class DenseLP.BoundsInconsistentException
          The bounds given are inconsistent.
static class DenseLP.NoAcceptablePivotException
          No acceptable pivot could be found.
static class DenseLP.ProblemUnboundedException
          The problem is unbounded.
 
Constructor Summary
DenseLP(double[][] a, double[] b, double[] c)
          Constructor variables of type double.
DenseLP(MPSReader mps)
          Constructor using an MPSReader object.
 
Method Summary
 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(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.

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.
Method Detail

clone

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


getDualSolution

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

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

getIterationCount

public int getIterationCount()
Returns the iteration count.

Returns:
an int scalar containing the iteration count.

getOptimalValue

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

Returns:
a double scalar containing the optimal value of the objective function.

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.

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}}_{{rm {u}}_i}
2 {rm {r}}_i ge {rm {b}}_i
3 {rm {b}}_i le {rm {r}}_i le {rm {b}}_{{rm {u}}_i}

Default=0.


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.

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:
iRefinementAction
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.


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.

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 that have both the lower and the upper bounds.

solve

public final void solve()
                 throws DenseLP.BoundsInconsistentException,
                        DenseLP.NoAcceptablePivotException,
                        DenseLP.ProblemUnboundedException
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.

JMSLTM Numerical Library 4.0

Copyright 1970-2006 Visual Numerics, Inc.
Built June 1 2006.