ToySolver.Arith.Simplex.Textbook.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

Methods

(==) :: OptResult -> OptResult -> Bool

(/=) :: OptResult -> OptResult -> Bool

Ord OptResult

Methods

compare :: OptResult -> OptResult -> Ordering

(<) :: OptResult -> OptResult -> Bool

(<=) :: OptResult -> OptResult -> Bool

(>) :: OptResult -> OptResult -> Bool

(>=) :: OptResult -> OptResult -> Bool

max :: OptResult -> OptResult -> OptResult

min :: OptResult -> OptResult -> OptResult

Show OptResult

Methods

showsPrec :: Int -> OptResult -> ShowS

show :: OptResult -> String

showList :: [OptResult] -> ShowS

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])