# simplex-method
`simplex-method` is a Haskell library that implements the two-phase [simplex method](https://en.wikipedia.org/wiki/Simplex_algorithm) 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`:
```haskell
findFeasibleSolution :: (MonadIO m, MonadLogger m) => [PolyConstraint] -> m (Maybe FeasibleSystem)
```
`findFeasibleSolution` takes a list of `PolyConstraint`s.
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:
```haskell
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:
```haskell
data FeasibleSystem = FeasibleSystem
{ dict :: Dict
, slackVars :: [Var]
, artificialVars :: [Var]
, objectiveVar :: Var
}
deriving (Show, Read, Eq, Generic)
```
```haskell
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:
```haskell
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:
```haskell
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.
```haskell
dictionaryFormToTableau :: Dict -> Tableau
```
There are similar functions for `DictionaryForm` as well as other custom types in the module `Linear.Simplex.Util`.
## Example
```haskell
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:
```haskell
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](https://github.com/rasheedja/simplex-haskell/issues).