Numeric.Limp.Solve.Simplex.StandardForm

Standard form for programs: only equalities and all variables >= 0 To convert an arbitrary program to this form, we need to:

Convert unconstrained (-inf <= x <= +inf) variable into two separate parts, x+ and x- wherever x occurs, it will be replaced with "x+" - "x-".

Convert variables with non-zero lower bounds (c <= x) to a new variable x', so that x = x' + c

The opposite of these conversions must be performed when extracting a variable assignment from the solved program.

All constraints are converted into a less-than with a constant on the right, and then these less-than constraints (f <= c) have a slack variable s added such that f + s == c && s >= 0

Documentation

type StandardRow z r c = (StandardLinear z r c, R c)

A single linear function with a constant summand

data Standard z r c

Entire program in standard form, as well as substitutions required to extract an assignment

Constructors

Standard

Fields

_objective :: StandardRow z r c

_constraints :: Map (StandardVar z r) (StandardRow z r c)

_substs :: StandardSubst z r c

Instances

(Show z, Show r, Show (R c)) => Show (Standard z r c)

type StandardSubst z r c = Map (Either z r) (StandardRow z r c)

type StandardLinear z r c = Map (StandardVar z r) (R c)

data StandardVar z r

Constructors

SV (Either z r)

A normal variable

SVS Int

A slack variable, introduced to make less-eq constraints into equalities

SVO

Magic objective, used when hiding an existing objective as a constraint and creating a new objective

SVLower (Either z r)

When a variable has a lower bound other than 0, we replace all occurences with with a new version minus the lower bound. x >= 5 ==> Lx - 5 >= 5 ==> Lx >= 0

SVPos (Either z r)

When unconstrained variables are encountered, they are replaced with x = SVPos x - SVNeg x so both parts can be constrained to >= 0.

SVNeg (Either z r)

Instances

(Eq z, Eq r) => Eq (StandardVar z r)

(Ord z, Ord r) => Ord (StandardVar z r)

(Show z, Show r) => Show (StandardVar z r)

addLinears :: (Ord z, Ord r, Rep c) => [(StandardLinear z r c, R c)] -> (StandardLinear z r c, R c)

Sum a list of linear functions together

substLinear :: (Ord z, Ord r, Rep c) => StandardSubst z r c -> (StandardLinear z r c, R c) -> (StandardLinear z r c, R c)

Perform substitution over a linear function/row

standard :: (Ord z, Ord r, Rep c) => Program z r c -> Standard z r c

Convert canon program into standard form

lookupRow :: (Ord z, Ord r, Rep c) => StandardRow z r c -> StandardVar z r -> R c

Get the coefficient of a variable in given row

objOfRow :: StandardRow z r c -> R c

Get objective or basis value of a row