ToySolver.Arith.LPSolver

Naïve implementation of Simplex method

Reference:

• http://www.math.cuhk.edu.hk/~wei/lpch3.pdf

Solver type

type Solver r = (Var, Tableau r, VarSet, VarMap (Expr r))

emptySolver :: VarSet -> Solver r

LP monad

type LP r = State (Solver r)

getTableau :: LP r (Tableau r)

putTableau :: Tableau r -> LP r ()

Problem specification

newVar :: LP r Var

Allocate a new non-negative variable.

addConstraint :: Real r => Atom r -> LP r ()

Add a contraint, without maintaining feasibilty condition of tableaus.

• Disequality is not supported.
• Unlike addConstraintWithArtificialVariable, an equality constraint becomes two rows.

addConstraintWithArtificialVariable :: Real r => Atom r -> LP r ()

Add a contraint and maintain feasibility condition by introducing artificial variable (if necessary).

• Disequality is not supported.
• Unlike addConstraint, an equality contstraint becomes one row with an artificial variable.

tableau :: RealFrac r => [Atom r] -> LP r ()

define :: Var -> Expr r -> LP r ()

Solving

phaseI :: (Fractional r, Real r) => LP r Bool

simplex :: (Fractional r, Real r) => OptDir -> Expr r -> LP r Bool

dualSimplex :: (Fractional r, Real r) => OptDir -> Expr r -> LP r Bool

data OptResult

results of optimization

Constructors

Optimum

Unsat

Unbounded

Instances

Eq OptResult

Ord OptResult

Show OptResult

twoPhaseSimplex :: (Fractional r, Real r) => OptDir -> Expr r -> LP r OptResult

primalDualSimplex :: (Fractional r, Real r) => OptDir -> Expr r -> LP r OptResult

Extract results

getModel :: Fractional r => VarSet -> LP r (Model r)

Utilities

collectNonnegVars :: forall r. RealFrac r => [Atom r] -> VarSet -> (VarSet, [Atom r])