Linear.Simplex.Simplex

Module implementing the two-phase simplex method. findFeasibleSolution performs phase one of the two-phase simplex method. optimizeFeasibleSystem performs phase two of the two-phase simplex method. twoPhaseSimplex performs both phases of the two-phase simplex method.

Documentation

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

Find a feasible solution for the given system of PolyConstraints by performing the first phase of the two-phase simplex method All Integer variables in the PolyConstraint must be positive. If the system is infeasible, return Nothing Otherwise, return the feasible system in DictionaryForm as well as a list of slack variables, a list artificial variables, and the objective variable.

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

Optimize a feasible system by performing the second phase of the two-phase simplex method. We first pass an ObjectiveFunction. Then, the feasible system in DictionaryForm as well as a list of slack variables, a list artificial variables, and the objective variable. Returns a pair with the first item being the Integer variable equal to the ObjectiveFunction and the second item being a map of the values of all Integer variables appearing in the system, including the ObjectiveFunction.

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

Perform the two phase simplex method with a given ObjectiveFunction a system of PolyConstraints. Assumes the ObjectiveFunction and PolyConstraint is not empty. Returns a pair with the first item being the Integer variable equal to the ObjectiveFunction and the second item being a map of the values of all Integer variables appearing in the system, including the ObjectiveFunction.