limp-0.3.2.3: representation of Integer Linear Programs

Safe HaskellNone
LanguageHaskell2010

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

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

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