Safe Haskell	None
Language	Haskell2010

Numeric.Limp.Solve.Simplex.StandardForm

Description

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

Synopsis

type StandardRow z r c = (StandardLinear z r c, R c)
data Standard z r c = Standard {
- _objective :: StandardRow z r c
- _constraints :: Map (StandardVar z r) (StandardRow z r c)
- _substs :: StandardSubst 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
- = SV (Either z r)
- | SVS Int
- | SVO
- | SVLower (Either z r)
- | SVPos (Either z r)
- | SVNeg (Either z r)
addLinears :: (Ord z, Ord r, Rep c) => [(StandardLinear z r c, R c)] -> (StandardLinear z r c, R c)
substLinear :: (Ord z, Ord r, Rep c) => StandardSubst z r c -> (StandardLinear z r c, R c) -> (StandardLinear z r c, R c)
standard :: (Ord z, Ord r, Rep c) => Program z r c -> Standard z r c
lookupRow :: (Ord z, Ord r, Rep c) => StandardRow z r c -> StandardVar z r -> R c
objOfRow :: StandardRow z r c -> R c

Documentation

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

A single linear function with a constant summand

data Standard z r c Source #

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) Source #
Instance details Defined in Numeric.Limp.Solve.Simplex.StandardForm Methods showsPrec :: Int -> Standard z r c -> ShowS # show :: Standard z r c -> String # showList :: [Standard z r c] -> ShowS #

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

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

data StandardVar z r Source #

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) Source #
Instance details Defined in Numeric.Limp.Solve.Simplex.StandardForm Methods (==) :: StandardVar z r -> StandardVar z r -> Bool # (/=) :: StandardVar z r -> StandardVar z r -> Bool #
(Ord z, Ord r) => Ord (StandardVar z r) Source #
Instance details Defined in Numeric.Limp.Solve.Simplex.StandardForm Methods compare :: StandardVar z r -> StandardVar z r -> Ordering # (<) :: StandardVar z r -> StandardVar z r -> Bool # (<=) :: StandardVar z r -> StandardVar z r -> Bool # (>) :: StandardVar z r -> StandardVar z r -> Bool # (>=) :: StandardVar z r -> StandardVar z r -> Bool # max :: StandardVar z r -> StandardVar z r -> StandardVar z r # min :: StandardVar z r -> StandardVar z r -> StandardVar z r #
(Show z, Show r) => Show (StandardVar z r) Source #
Instance details Defined in Numeric.Limp.Solve.Simplex.StandardForm Methods showsPrec :: Int -> StandardVar z r -> ShowS # show :: StandardVar z r -> String # showList :: [StandardVar z r] -> ShowS #

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

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) Source #

Perform substitution over a linear function/row

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

Convert canon program into standard form

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

Get the coefficient of a variable in given row

objOfRow :: StandardRow z r c -> R c Source #

Get objective or basis value of a row