simplex-method

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

Quick Overview

The Linear.Simplex.Simplex module contain both phases of the simplex method.

Phase One

Phase one is implemented by findFeasibleSolution:

findFeasibleSolution :: [PolyConstraint] -> Maybe (DictionaryForm, [Integer], [Integer], Integer)

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 VarConstMap Rational      | 
  GEQ VarConstMap Rational      | 
  EQ  VarConstMap Rational       deriving (Show, Eq);

And VarConstMap is defined as:

type VarConstMap = [(Integer, Rational)]

A VarConstMap is treated as a list of Integer variables mapped to their Rational coefficients, with an implicit + between each element in the list. For example: [(1, 2), (2, (-3)), (1, 3)] is equivalent to (2x1 + (-3x2) + 3x1).

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

Passing a [PolyConstraint] to findFeasibleSolution will return a feasible solution if it exists as well as a list of slack variables, artificial variables, and a variable that can be safely used to represent the objective for phase two. Nothing is returned if the given [PolyConstraint] is infeasible. The feasible system is returned as the type DictionaryForm:

type DictionaryForm = [(Integer, VarConstMap)]

DictionaryForm can be thought of as a list of equations, where the Integer represents a basic variable on the LHS that is equal to the RHS represented as a VarConstMap. In this VarConstMap, the Integer -1 is used internally to represent a Rational number.

Phase Two

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

data ObjectiveFunction = Max VarConstMap | Min VarConstMap deriving (Show, Eq)

optimizeFeasibleSystem :: ObjectiveFunction -> DictionaryForm -> [Integer] -> [Integer] -> Integer -> Maybe (Integer, [(Integer, Rational)])

We first pass an ObjectiveFunction. Then we give a feasible system in DictionaryForm, a list of slack variables, a list of artificial variables, and a variable to represent the objective. optimizeFeasibleSystem Maximizes/Minimizes the linear equation represented as a VarConstMap in the given ObjectiveFunction. The first item of the returned pair is the Integer variable representing the objective. The second item is a list of Integer variables mapped to their optimized values. If a variable is not in this list, the variable is equal to 0.

Two-Phase Simplex

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

twoPhaseSimplex :: ObjectiveFunction -> [PolyConstraint] -> Maybe (Integer, [(Integer, Rational)])

The return type is the same as that of optimizeFeasibleSystem

Extracting Results

The result of the objective function is present in the return 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.

extractObjectiveValue :: Maybe (Integer, [(Integer, Rational)]) -> Maybe Rational

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

Usage notes

You must only use positive Integer variables in a VarConstMap. This implementation assumes that the user only provides positive Integer variables; the Integer -1, for example, is sometimes used to represent a Rational number.

Example

exampleFunction :: (ObjectiveFunction, [PolyConstraint])
exampleFunction =
  (
    Max [(1, 3), (2, 5)],      -- 3x1 + 5x2
    [
      LEQ [(1, 3), (2, 1)] 15, -- 3x1 + x2 <= 15 
      LEQ [(1, 1), (2, 1)] 7,  -- x1 + x2 <= 7
      LEQ [(2, 1)] 4,          -- x2 <= 4
      LEQ [(1, -1), (2, 2)] 6  -- -x1 + 2x2 <= 6
    ]
  )

twoPhaseSimplex (fst exampleFunction) (snd exampleFunction)

The result of the call above is:

Just
  (7, -- Integer representing objective function
  [
    (7,29 % 1), -- Value for variable 7, so max(3x1 + 5x2) = 29.
    (1,3 % 1),  -- Value for variable 1, so x1 = 3 
    (2,4 % 1)   -- 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.