com.imsl.math

Class Transport

java.lang.Object

com.imsl.math.Transport

All Implemented Interfaces:

Serializable

public class Transport
extends Object
implements Serializable

Solves a Transportation problem.

Class Transport solves the transportation problem which can be described as follows: Let \(nw\) sources (or warehouses) be given that store \(w_i\) (\(i=1,..,nw\)) units of a commodity. The sources are connected with \(ns\) destinations (or sinks) that demand \(s_j\) (\(j = 1,...,ns\)) units of the commodity. The transportation costs per unit from source i to destination j are \(c_{ij}\). The goal is to transport the commodity from the sources to the destinations in such a way that all demands are met and the total transportation costs are minimized. If \(x_{ij}\) denotes the desired quantity of the commodity transported from source i to destination j, then the mathematical formulation of the transportation problem is $$ \min \sum_{i=1}^{nw}\sum_{j=1}^{ns}c_{ij}x_{ij}$$ subject to the constraints $$\sum_{j=1}^{ns}x_{ij} \le w_i, i = 1,\ldots,nw \\ \sum_{i=1}^{nw}x_{ij} = s_j, j = 1,\ldots,ns \\ x_{ij} \ge 0, i=1,\ldots,nw, j=1,\ldots,ns. $$
The revised simplex method is used to solve a very sparse linear programming problem with nw + ns constraints and nw * ns variables. If nw = ns = k, the work per iteration is \(O(k^2)\), compared with \(O(k^3)\) when a dense simplex algorithm is used. For more details, see Sewell (2014), Section 4.6.
Alternatively, the interior point method implemented in class SparseLP can be used to solve the transportation problem.
Denoting the dual solution of the transportation problem as dual, dual[i] gives the decrease in total cost per unit increase in sources[i], for small increases, and dual[nw + j] gives the increase in total cost per unit increase in destinations[j].

References
Sewell, Granville (2014), Computational Methods of Linear Algebra, third edition, World Scientific Publishing, Singapore.

See Also:

Example 1, Example 2, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Transport.SolutionMethod Indicates which algorithm is used to solve the transportation problem.
static class	Transport.TooManyIterationsException Maximum number of iterations exceeded.
static class	Transport.UnexpectedErrorException An unexpected error occurred.

Constructor Summary

Constructors

Constructor and Description
Transport(double[] sources, double[] destinations, double[][] costs) Construct the transportation problem from given sources, destinations and costs.
Transport(Transport transportProblem) Copy constructor for the transportation problem.

Method Summary

Modifier and Type	Method and Description
double[]	getDualSolution() Returns the dual solution of the transportation problem.
int	getMaxIterations() Returns the maximum iteration number allowed in the solution of the transportation problem.
int	getNumberOfThreads() Returns the number of java.lang.Thread instances used for parallel processing.
double[][]	getOptimalRouting() Returns the optimal routing.
Transport.SolutionMethod	getSolutionMethod() Returns the algorithm used to solve the transportation problem.
double	getTotalCost() Returns the total cost of the optimal routing.
void	setMaxIterations(int maxIterations) Sets the maximum number of iterations in the solver for the transportation problem.
void	setNumberOfThreads(int numberOfThreads) Sets the number of java.lang.Thread instances to be used for parallel processing.
void	setSolutionMethod(Transport.SolutionMethod method) Sets the algorithm used to solve the transportation problem.
void	solve() Solves a transportation problem using the revised simplex method or an interior-point method.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Transport

public Transport(double[] sources,
                 double[] destinations,
                 double[][] costs)

Construct the transportation problem from given sources, destinations and costs.

Parameters:

sources - a double array containing the source capacities. Since no internal copy of the array is made, the user should not change its content during the existence of the related Transport object.

destinations - a double array containing the destination requirements. Since no internal copy of the array is made, the user should not change its content during the existence of the related Transport object.

costs - a double matrix containing the cost matrix. If nw is the length of sources and ns the length of destinations, then costs is of size nw by ns, and costs[i][j] is the per unit cost to ship from source i to destination j. Since no internal copy of the matrix is made, the user should not change its content during the existence of the related Transport object.

Transport

public Transport(Transport transportProblem)

Copy constructor for the transportation problem.

Parameters:

transportProblem - the Transport object to be copied

Method Detail

solve

public final void solve()
                 throws Transport.TooManyIterationsException,
                        Transport.UnexpectedErrorException,
                        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

Solves a transportation problem using the revised simplex method or an interior-point method.

Throws:

Transport.TooManyIterationsException - is thrown by the simplex method if the maximum number of simplex steps is exceeded

Transport.UnexpectedErrorException - is thrown by the simplex method if an unexpected error occurred

SparseLP.DiagonalWeightMatrixException - is thrown by the interior point method if a diagonal element of the diagonal weight matrix is too small

SparseLP.CholeskyFactorizationAccuracyException - is thrown by the interior point method if the Cholesky factorization failed because of accuracy problems

SparseLP.PrimalUnboundedException - is thrown by the interior point method if the primal problem is unbounded

SparseLP.PrimalInfeasibleException - is thrown by the interior point method if the primal problem is infeasible

SparseLP.DualInfeasibleException - is thrown by the interior point method if the dual problem is infeasible

SparseLP.InitialSolutionInfeasibleException - is thrown by the interior point method if the initial solution for the one-row linear program is infeasible

SparseLP.TooManyIterationsException - is thrown by the interior point method if the maximum number of iterations has been exceeded

SparseLP.ProblemUnboundedException - is thrown by the interior point method if the problem is unbounded

SparseLP.ZeroColumnException - is thrown by the interior point method if a column of the constraint matrix has no entries

SparseLP.ZeroRowException - is thrown by the interior point method if a row of the constraint matrix has no entries

SparseLP.IncorrectlyEliminatedException - is thrown by the interior point method if one or more LP variables are falsely characterized by the internal presolver

SparseLP.IncorrectlyActiveException - is thrown by the interior point method if one or more LP variables are falsely characterized by the internal presolver

SparseLP.IllegalBoundsException - is thrown by the interior point method if the lower bound is greater than the upper bound

setMaxIterations

public void setMaxIterations(int maxIterations)

Sets the maximum number of iterations in the solver for the transportation problem.

Parameters:

maxIterations - an int scalar containing the maximum number of iterations allowed in the algorithm for the solution of the transportation problem.
If SolutionMethod == RevisedSimplexMethod, then an upper bound for the simplex steps is set. For maxIterations = 0, the number of simplex steps is unbounded.
If SolutionMethod == InteriorPointMethod, then the maximum number of iterations in the interior-point method is set.

By default, maxIterations = 0 for the revised simplex method and maxIterations = 200 for the interior-point method.

getMaxIterations

public int getMaxIterations()

Returns the maximum iteration number allowed in the solution of the transportation problem.

Returns:

an int scalar containing the maximum number of iterations allowed for the revised simplex method or the primal-dual solver, depending on the SolutionMethod chosen

getDualSolution

public double[] getDualSolution()

Returns the dual solution of the transportation problem.

Returns:

a double array containing the dual solution. The size of the solution is nw + ns, where nw is the number of sources and ns is the number of destinations.

getTotalCost

public double getTotalCost()

Returns the total cost of the optimal routing.

Returns:

a double containing the total cost of the optimal solution

getOptimalRouting

public double[][] getOptimalRouting()

Returns the optimal routing.

Returns:

a double array, size the same as input array costs, containing the optimal solution of the transportation problem

setSolutionMethod

public void setSolutionMethod(Transport.SolutionMethod method)

Sets the algorithm used to solve the transportation problem.

Parameters:

method - a SolutionMethod constant indicating if the revised simplex method or the interior-point method is used to solve the transportation problem.

Default: method = SolutionMethod.RevisedSimplexMethod.

getSolutionMethod

public Transport.SolutionMethod getSolutionMethod()

Returns the algorithm used to solve the transportation problem.

Returns:

a SolutionMethod constant indicating if the revised simplex method or the interior-point method is used to solve the transportation problem.

setNumberOfThreads

public void setNumberOfThreads(int numberOfThreads)

Sets the number of java.lang.Thread instances to be used for parallel processing.

Parameters:

numberOfThreads - an int specifying the number of java.lang.Thread instances to be used for parallel processing

Default: numberOfThreads = 1.

getNumberOfThreads

public int getNumberOfThreads()

Returns the number of java.lang.Thread instances used for parallel processing.

Returns:

an int containing the number of java.lang.Thread instances used for parallel processing