ToySolver.Arith.Simplex.Textbook

Naïve implementation of Simplex method

Reference:

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

The Tableau type

type Tableau r = VarMap (Row r)

type RowIndex = Int

Basic variables

type ColIndex = Int

Non-basic variables

type Row r = (VarMap r, r)

emptyTableau :: Tableau r

objRowIndex :: RowIndex

pivot :: (Fractional r, Eq r) => RowIndex -> ColIndex -> Tableau r -> Tableau r

lookupRow :: RowIndex -> Tableau r -> Row r

Lookup a row by basic variable

addRow :: (Num r, Eq r) => Tableau r -> RowIndex -> Row r -> Tableau r

setObjFun :: (Num r, Eq r) => Tableau r -> Expr r -> Tableau r

Optimization direction

module Data.OptDir

Reading status

currentValue :: Num r => Tableau r -> Var -> r

currentObjValue :: Tableau r -> r

isFeasible :: Real r => Tableau r -> Bool

isOptimal :: Real r => OptDir -> Tableau r -> Bool

High-level solving functions

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

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

phaseI :: (Real r, Fractional r) => Tableau r -> VarSet -> (Bool, Tableau r)

primalDualSimplex :: (Real r, Fractional r) => OptDir -> Tableau r -> (Bool, Tableau r)

For debugging

isValidTableau :: Tableau r -> Bool

toCSV :: Num r => (r -> String) -> Tableau r -> String