Implementation of the two-phase simplex method in exact rational arithmetic.

Please see the README on GitHub at https://github.com/rasheedja/simplex-method#readme

simplex-method

simplex-method is a Haskell library that implements the two-phase simplex method in exact rational arithmetic.

Quick Overview

The Linear.Simplex.Solver.TwoPhase module contain both phases of the two-phase simplex method.

Phase One

Phase one is implemented by findFeasibleSolution:

findFeasibleSolution :: (MonadIO m, MonadLogger m) => [PolyConstraint] -> m (Maybe FeasibleSystem)

findFeasibleSolution takes a list of PolyConstraints. The PolyConstraint type, as well as other custom types required by this library, are defined in the Linear.Simplex.Types module. PolyConstraint is defined as:

data PolyConstraint
  = LEQ {lhs :: VarLitMapSum, rhs :: SimplexNum}
  | GEQ {lhs :: VarLitMapSum, rhs :: SimplexNum}
  | EQ {lhs :: VarLitMapSum, rhs :: SimplexNum}
  deriving (Show, Read, Eq, Generic)

SimplexNum is an alias for Rational, and VarLitMapSum is an alias for VarLitMap, which is an alias for Map Var SimplexNum. Var is an alias of Int.

A VarLitMapSum is read as Integer variables mapped to their Rational coefficients, with an implicit + between each entry. For example: Map.fromList [(1, 2), (2, (-3)), (1, 3)] is equivalent to (2x1 + (-3x2) + 3x1).

And a PolyConstraint is an inequality/equality where the LHS is a VarLitMapSum and the RHS is a Rational. For example: LEQ (Map.fromList [(1, 2), (2, (-3)), (1, 3)] 60) is equivalent to (2x1 + (-3x2) + 3x1) <= 60.

Passing a [PolyConstraint] to findFeasibleSolution will return a FeasibleSystem if a feasible solution exists:

data FeasibleSystem = FeasibleSystem
  { dict :: Dict
  , slackVars :: [Var]
  , artificialVars :: [Var]
  , objectiveVar :: Var
  }
  deriving (Show, Read, Eq, Generic)

type Dict = M.Map Var DictValue

data DictValue = DictValue
  { varMapSum :: VarLitMapSum
  , constant :: SimplexNum
  }
  deriving (Show, Read, Eq, Generic)

Dict can be thought of as a set of equations, where the key represents a basic variable on the LHS of the equation that is equal to the RHS represented as a DictValue value.

Phase Two

optimizeFeasibleSystem performs phase two of the simplex method, and has the type:

optimizeFeasibleSystem :: (MonadIO m, MonadLogger m) => ObjectiveFunction -> FeasibleSystem -> m (Maybe Result)

data ObjectiveFunction = Max {objective :: VarLitMapSum} | Min {objective :: VarLitMapSum}

data Result = Result
  { objectiveVar :: Var
  , varValMap :: VarLitMap
  }
  deriving (Show, Read, Eq, Generic)

We give optimizeFeasibleSystem an ObjectiveFunction along with a FeasibleSystem.

Two-Phase Simplex

twoPhaseSimplex performs both phases of the simplex method. It has the type:

twoPhaseSimplex :: (MonadIO m, MonadLogger m) => ObjectiveFunction -> [PolyConstraint] -> m (Maybe Result)

Extracting Results

The result of the objective function is present in the returned Result type of both twoPhaseSimplex and optimizeFeasibleSystem, but this can be difficult to grok in systems with many variables, so the following function will extract the value of the objective function for you.

dictionaryFormToTableau :: Dict -> Tableau

There are similar functions for DictionaryForm as well as other custom types in the module Linear.Simplex.Util.

Example

exampleFunction :: (ObjectiveFunction, [PolyConstraint])
exampleFunction =
  (
    Max {objective = Map.fromList [(1, 3), (2, 5)]},      -- 3x1 + 5x2
    [
      LEQ {lhs = Map.fromList [(1, 3), (2, 1)], rhs = 15}, -- 3x1 + x2 <= 15 
      LEQ {lhs = Map.fromList [(1, 1), (2, 1)], rhs = 7},  -- x1 + x2 <= 7
      LEQ {lhs = Map.fromList [(2, 1)], rhs = 4},          -- x2 <= 4
      LEQ {lhs = Map.fromList [(1, -1), (2, 2)], rhs = 6}  -- -x1 + 2x2 <= 6
    ]
  )

twoPhaseSimplex (fst exampleFunction) (snd exampleFunction)

The result of the call above is:

Just 
  (Result
    { objectiveVar = 7 -- Integer representing objective function
    , varValMap = Map.fromList  
      [ (7, 29) -- Value for variable 7, so max(3x1 + 5x2) = 29.
      , (1, 3) -- Value for variable 1, so x1 = 3 
      , (2, 4) -- Value for variable 2, so x2 = 4
      ]
    }
  )

There are many more examples in test/TestFunctions.hs. You may use prettyShowVarConstMap, prettyShowPolyConstraint, and prettyShowObjectiveFunction to convert these tests into a more human-readable format.

Issues

Please share any bugs you find here.