Class LPSolver

java.lang.Object

dk.alexandra.fresco.lib.lp.LPSolver

All Implemented Interfaces:

Computation<LPSolver.LPOutput,ProtocolBuilderNumeric>

public class LPSolver
extends Object
implements Computation<LPSolver.LPOutput,ProtocolBuilderNumeric>

A protocol for solving LP problems using the Simplex method.

We basically use the method of Toft 2009.

We optimize this protocol by using the so called Revised Simplex method. I.e., instead of updating the tableau it self, we keep track of much smaller update matrix representing changes to the initial tableau. Do this only requires multiplication with a small sparse matrix, which can be done more efficiently than general matrix multiplication.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LPSolver.LPOutput
protected static class	LPSolver.LpState
static enum	LPSolver.PivotRule

Constructor Summary

Constructors

Constructor	Description
LPSolver(LPSolver.PivotRule pivotRule, LPTableau tableau, Matrix<DRes<SInt>> updateMatrix, DRes<SInt> pivot, List<DRes<SInt>> initialBasis, int maxNumberOfIterations)	Creates a new LPSolver.

Method Summary

Modifier and Type	Method	Description
DRes<LPSolver.LPOutput>	buildComputation(ProtocolBuilderNumeric builder)
protected boolean	isDebug()	Indicates if debug information should be opened and written.

Methods inherited from class java.lang.Object

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

Constructor Details

LPSolver

public LPSolver(LPSolver.PivotRule pivotRule,
 LPTableau tableau,
 Matrix<DRes<SInt>> updateMatrix,
 DRes<SInt> pivot,
 List<DRes<SInt>> initialBasis,
 int maxNumberOfIterations)

Creates a new LPSolver. Note, we do not do full two-phase Simplex, so the initial state is assumed to be good.

Parameters:

pivotRule - the pivot rule to apply

tableau - the initial tableau, this will not be modified

updateMatrix - the initial update matrix, will be modified to the current state

pivot - the initial pivot, will be modified to reflect the state

initialBasis - the initial basis, will be modified to reflect the state

maxNumberOfIterations - we might not terminate, the solver stops after this iteration

Method Details

buildComputation

public DRes<LPSolver.LPOutput> buildComputation(ProtocolBuilderNumeric builder)

Specified by:

buildComputation in interface Computation<LPSolver.LPOutput,ProtocolBuilderNumeric>

isDebug

protected boolean isDebug()

Indicates if debug information should be opened and written.

This is meant to be possible to override in debugging classes, but should always return false in non-debugging versions of this class.

Returns:

true if this is a debugging class, false otherwise