# 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 `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:

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

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.