-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | representation of Integer Linear Programs -- -- This package provides two representations for linear programs: -- Numeric.Limp.Program, which is what I expect end-users to use, -- and Numeric.Limp.Canon, which is simpler, but would be less -- nice for writing linear programs. You can convert programs from the -- Program representation to the Canon representation using -- Numeric.Limp.Canon.Convert, and then pretty-print the program -- using Numeric.Limp.Canon.Pretty. There is a very simple -- branch-and-bound solver in Numeric.Limp.Solve.Branch.Simple, -- and a simplex solver for relaxed (real only) programs in -- Numeric.Limp.Solve.Simplex.Maps. See the limp-cbc package for a -- simple external solver. @package limp @version 0.3.2.3 -- | Reasons an analysis, simplification or solution could fail module Numeric.Limp.Error -- | Give reason for being infeasible, if possible data Infeasible -- | An integer variable is constrained to be equal to a non-int InfeasibleNotIntegral :: Infeasible -- | The bound on a variable or constraint is empty - lower bound is above -- upper. InfeasibleBoundEmpty :: Infeasible instance GHC.Show.Show Numeric.Limp.Error.Infeasible instance GHC.Classes.Eq Numeric.Limp.Error.Infeasible -- | Representation of integers (Z) and reals (R) of similar precision. -- Programs are abstracted over this, so that ideally in the future we -- could have a solver that produces Integers and Rationals, instead of -- just Ints and Doubles. -- -- We bundle Z and R up into a single representation instead of -- abstracting over both, because we must be able to convert from Z to R -- without loss. module Numeric.Limp.Rep.Rep -- | The Representation class. Requires its members Z c and R -- c to be Num, Ord and Eq. -- -- For some reason, for type inference to work, the members must be -- data instead of type. This gives some minor -- annoyances when unpacking them. See unwrapR below. class (Num (Z c), Ord (Z c), Eq (Z c), Integral (Z c), Num (R c), Ord (R c), Eq (R c), RealFrac (R c)) => Rep c where { -- | Integers data family Z c; -- | Real numbers data family R c; } -- | Convert an integer to a real. This should not lose any precision. -- (whereas fromIntegral 1000 :: Word8 would lose precision) fromZ :: Rep c => Z c -> R c -- | An assignment from variables to values. Maps integer variables to -- integers, and real variables to reals. data Assignment z r c Assignment :: Map z (Z c) -> Map r (R c) -> Assignment z r c -- | Retrieve value of integer variable - or 0, if there is no value. zOf :: (Rep c, Ord z) => Assignment z r c -> z -> Z c -- | Retrieve value of real variable - or 0, if there is no value. rOf :: (Rep c, Ord r) => Assignment z r c -> r -> R c -- | Retrieve value of an integer or real variable, with result cast to a -- real regardless. zrOf :: (Rep c, Ord z, Ord r) => Assignment z r c -> Either z r -> R c assSize :: Assignment z r c -> Int instance (GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c), GHC.Show.Show z, GHC.Show.Show r) => GHC.Show.Show (Numeric.Limp.Rep.Rep.Assignment z r c) instance (GHC.Classes.Ord z, GHC.Classes.Ord r) => GHC.Base.Semigroup (Numeric.Limp.Rep.Rep.Assignment z r c) instance (GHC.Classes.Ord z, GHC.Classes.Ord r) => GHC.Base.Monoid (Numeric.Limp.Rep.Rep.Assignment z r c) -- | Fixed/floating precision number representation module Numeric.Limp.Rep.IntDouble -- | A representation that uses native 64-bit ints and 64-bit doubles. -- Really, this should be 32-bit ints. data IntDouble -- | Convert a wrapped (R IntDouble) to an actual Double. unwrapR :: R IntDouble -> Double instance GHC.Real.RealFrac (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Real.Real (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Real.Fractional (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Enum.Enum (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Num.Num (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Classes.Eq (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Classes.Ord (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Enum.Enum (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Num.Num (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Real.Real (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Real.Integral (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Classes.Eq (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Classes.Ord (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance Numeric.Limp.Rep.Rep.Rep Numeric.Limp.Rep.IntDouble.IntDouble instance GHC.Show.Show (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.IntDouble.IntDouble) instance GHC.Show.Show (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.IntDouble.IntDouble) -- | Arbitrary precision number representation module Numeric.Limp.Rep.Arbitrary -- | A representation that uses arbitrary-sized Integers and Rationals data Arbitrary instance GHC.Real.RealFrac (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Real.Real (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Real.Fractional (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Enum.Enum (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Num.Num (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Classes.Eq (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Classes.Ord (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Enum.Enum (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Num.Num (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Real.Real (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Real.Integral (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Classes.Eq (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Classes.Ord (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance Numeric.Limp.Rep.Rep.Rep Numeric.Limp.Rep.Arbitrary.Arbitrary instance GHC.Show.Show (Numeric.Limp.Rep.Rep.Z Numeric.Limp.Rep.Arbitrary.Arbitrary) instance GHC.Show.Show (Numeric.Limp.Rep.Rep.R Numeric.Limp.Rep.Arbitrary.Arbitrary) -- | Representation of integers (Z) and reals (R) of similar precision. -- Programs are abstracted over this, so that ideally in the future we -- could have a solver that produces Integers and Rationals, instead of -- just Ints and Doubles. -- -- We bundle Z and R up into a single representation instead of -- abstracting over both, because we must be able to convert from Z to R -- without loss. module Numeric.Limp.Rep -- | Type-level functions on result types. -- -- Linear functions are classified as either int-valued or real-valued, -- so we define KZ and KR as data kinds to denote this -- in the type. module Numeric.Limp.Program.ResultKind -- | Classify the result type of a linear function to either integral or -- real: data K -- | Integral Z KZ :: K -- | Real or mixed R KR :: K -- | Representation of either integral of real linear functions: a list of -- variables with coefficients, plus a constant summand. data Linear z r c k [LZ] :: [(z, Z c)] -> Z c -> Linear z r c 'KZ [LR] :: [(Either z r, R c)] -> R c -> Linear z r c 'KR -- | Find the result type of merging, or adding, two linear functions: -- adding two integers produces an integer, while adding a real on either -- side produces a real. type family KMerge (a :: K) (b :: K) :: K -- | Convert a K to its actual representation (Z or -- R). type family KRep (a :: K) :: * -> * instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Program.ResultKind.Linear z r c k) -- | Representation, constructors and limited arithmetic on linear -- functions. -- -- The linear function is indexed by its result type: either purely -- integer (KZ) or mixed/real (KR). This index is used -- to allow strictly-less-than constraints only on integer functions, and -- to allow retrieving integer values from purely integer functions. module Numeric.Limp.Program.Linear -- | Representation of either integral of real linear functions: a list of -- variables with coefficients, plus a constant summand. data Linear z r c k [LZ] :: [(z, Z c)] -> Z c -> Linear z r c 'KZ [LR] :: [(Either z r, R c)] -> R c -> Linear z r c 'KR -- | Any linear function can be converted into a real linear function. toR :: Rep c => Linear z r c k -> Linear z r c 'KR -- | Integral variable z :: Rep c => z -> Z c -> Linear z r c 'KZ -- | Integral variable with coefficient 1 z1 :: Rep c => z -> Linear z r c 'KZ -- | Real variable r :: Rep c => r -> R c -> Linear z r c 'KR -- | Real variable with coefficient 1 r1 :: Rep c => r -> Linear z r c 'KR -- | An integral constant summand con :: Rep c => Z c -> Linear z r c 'KZ -- | An integral constant summand conZ :: Rep c => Z c -> Linear z r c 'KZ -- | A real constant conR :: Rep c => R c -> Linear z r c 'KR -- | Constant 0 c0 :: Rep c => Linear z r c 'KZ -- | Constant 1 c1 :: Rep c => Linear z r c 'KZ -- | Negate a linear function. Negation does not change the kind. neg :: Rep c => Linear z r c k -> Linear z r c k -- | Multiply a linear function by some constant. -- -- Note that you cannot multiply a linear function by another linear -- function, as the result would likely be non-linear! (.*) :: Rep c => Linear z r c k -> KRep k c -> Linear z r c k infix 7 .* -- | Multiply a linear function by some constant. (*.) :: Rep c => KRep k c -> Linear z r c k -> Linear z r c k infix 7 *. -- | Add two linear functions together. They can have different result -- types. (.+.) :: Rep c => Linear z r c k1 -> Linear z r c k2 -> Linear z r c (KMerge k1 k2) infixl 6 .+. -- | Subtract one linear function from another. They can have different -- result types. (.-.) :: Rep c => Linear z r c k1 -> Linear z r c k2 -> Linear z r c (KMerge k1 k2) infixl 6 .-. module Numeric.Limp.Program.Constraint -- | Different kind of constraints. -- -- These are not all necessary, but I have a hunch that keeping some -- structure may be helpful in the future. -- -- Constructors: -- -- data Constraint z r c [:==] :: Linear z r c k1 -> Linear z r c k2 -> Constraint z r c [:<=] :: Linear z r c k1 -> Linear z r c k2 -> Constraint z r c [:<] :: Linear z r c 'KZ -> Linear z r c 'KZ -> Constraint z r c [:>=] :: Linear z r c k1 -> Linear z r c k2 -> Constraint z r c [:>] :: Linear z r c 'KZ -> Linear z r c 'KZ -> Constraint z r c [Between] :: Linear z r c k1 -> Linear z r c k2 -> Linear z r c k3 -> Constraint z r c [:&&] :: Constraint z r c -> Constraint z r c -> Constraint z r c [:!] :: String -> Constraint z r c -> Constraint z r c [CTrue] :: Constraint z r c infix 4 :! infixr 3 :&& infix 5 :>= infix 5 :<= infix 5 :== infix 5 :< infix 5 :> instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Program.Constraint.Constraint z r c) instance GHC.Base.Semigroup (Numeric.Limp.Program.Constraint.Constraint z r c) instance GHC.Base.Monoid (Numeric.Limp.Program.Constraint.Constraint z r c) -- | Define upper and lower bounds of program variables. module Numeric.Limp.Program.Bounds -- | Define upper and lower bounds of program variables. Bounds may be -- specified multiple times: the intersection of all bounds is used. data Bounds z r c BoundZ :: B (Z c) z -> Bounds z r c BoundR :: B (R c) r -> Bounds z r c -- | Maybe a lower bound, the variable's name, and maybe an upper bound. type B rep v = (Maybe rep, v, Maybe rep) -- | Create a lower and upper bound for an integer variable. lowerUpperZ :: Rep c => Z c -> z -> Z c -> Bounds z r c -- | Create only a lower bound for an integer variable. lowerZ :: Rep c => Z c -> z -> Bounds z r c -- | Create only an upper bound for an integer variable. upperZ :: Rep c => z -> Z c -> Bounds z r c -- | A binary integer variable: can only be 0 or 1. binary :: Rep c => z -> Bounds z r c -- | Create a lower and upper bound for a real variable. lowerUpperR :: Rep c => R c -> r -> R c -> Bounds z r c -- | Create only a lower bound for a real variable. lowerR :: Rep c => R c -> r -> Bounds z r c -- | Create only an upper bound for a real variable. upperR :: Rep c => r -> R c -> Bounds z r c instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Program.Bounds.Bounds z r c) -- | Definition of a whole program module Numeric.Limp.Program.Program -- | Direction to optimise program in: minimise or maximise. data Direction Minimise :: Direction Maximise :: Direction -- | Whole program, parameterised by: -- -- data Program z r c Program :: Direction -> Linear z r c 'KR -> Constraint z r c -> [Bounds z r c] -> Program z r c -- | Optimisation direction [_direction] :: Program z r c -> Direction -- | The objective function [_objective] :: Program z r c -> Linear z r c 'KR -- | All constraints bundled up with :&&. [_constraints] :: Program z r c -> Constraint z r c -- | Upper and lower bounds of variables. Not all variables need to be -- mentioned, and if variables are mentioned multiple times, the -- intersection is used. [_bounds] :: Program z r c -> [Bounds z r c] program :: Rep c => Direction -> Linear z r c k -> Constraint z r c -> [Bounds z r c] -> Program z r c minimise :: Rep c => Linear z r c k -> Constraint z r c -> [Bounds z r c] -> Program z r c maximise :: Rep c => Linear z r c k -> Constraint z r c -> [Bounds z r c] -> Program z r c instance GHC.Show.Show Numeric.Limp.Program.Program.Direction instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Program.Program.Program z r c) -- | Functions for evaluating linear functions and checking constraints. module Numeric.Limp.Program.Eval -- | Evaluate a linear function with given assignment. If the linear -- function is purely integral, a Z will be returned; otherwise, -- R. eval :: (Rep c, Ord z, Ord r) => Assignment z r c -> Linear z r c k -> KRep k c -- | Evaluate a linear function with given assignment, returning real -- value. evalR :: (Rep c, Ord z, Ord r) => Assignment z r c -> Linear z r c k -> R c -- | Check whether assignment satisfies constraint. check :: (Rep c, Ord z, Ord r) => Assignment z r c -> Constraint z r c -> Bool -- | Check whether an assignment satisfies the program's constraints and -- bounds checkProgram :: (Rep c, Ord z, Ord r) => Assignment z r c -> Program z r c -> Bool checkBounds :: (Rep c, Ord z, Ord r) => Assignment z r c -> [Bounds z r c] -> Bool -- | Front-end representation of programs. See Program for the -- entire program; Constraint for constraints such as less than or -- equal, greater than, etc; and Linear for linear functions. module Numeric.Limp.Program -- | Representation of subset of linear functions: only variables and -- coefficients, no constant summand module Numeric.Limp.Canon.Linear -- | Linear function is represented as a map from either a integral -- variable or an real variable, to a real coefficient. data Linear z r c Linear :: Map (Either z r) (R c) -> Linear z r c -- | Create linear function from list of variables and coefficients mkLinear :: (Ord z, Ord r, Rep c) => [(Either z r, R c)] -> Linear z r c -- | Evaluate linear function with given assignment evalR :: (Rep c, Ord z, Ord r) => Assignment z r c -> Linear z r c -> R c -- | Find set of all variables mentioned in function varsOfLinear :: (Ord z, Ord r) => Linear z r c -> Set (Either z r) instance (GHC.Classes.Ord z, GHC.Classes.Ord r, Numeric.Limp.Rep.Rep.Rep c) => GHC.Classes.Eq (Numeric.Limp.Canon.Linear.Linear z r c) instance (GHC.Classes.Ord z, GHC.Classes.Ord r, Numeric.Limp.Rep.Rep.Rep c) => GHC.Classes.Ord (Numeric.Limp.Canon.Linear.Linear z r c) -- | Representation of linear constraints module Numeric.Limp.Canon.Constraint -- | Conjunction of simple constraints data Constraint z r c Constraint :: [Constraint1 z r c] -> Constraint z r c -- | A simple constraint data Constraint1 z r c -- | Maybe a lower bound, a linear function, and maybe an upper bound. -- -- In order to be meaningful, at least one of lower or upper bound should -- be Just. C1 :: Maybe (R c) -> Linear z r c -> Maybe (R c) -> Constraint1 z r c -- | Check whether an assignment satisfies the constraint check :: (Rep c, Ord z, Ord r) => Assignment z r c -> Constraint z r c -> Bool -- | Get set of variables in constraint varsOfConstraint :: (Ord z, Ord r) => Constraint z r c -> Set (Either z r) -- | Canon representation of linear program module Numeric.Limp.Canon.Program -- | A program represented by objective, constraints and bounds. There is -- no need for an optimisation direction; the objective is just negated. data Program z r c Program :: Linear z r c -> Constraint z r c -> Map (Either z r) (Maybe (R c), Maybe (R c)) -> Program z r c [_objective] :: Program z r c -> Linear z r c [_constraints] :: Program z r c -> Constraint z r c [_bounds] :: Program z r c -> Map (Either z r) (Maybe (R c), Maybe (R c)) -- | Find set of all variables mentioned in program varsOfProgram :: (Ord z, Ord r) => Program z r c -> Set (Either z r) -- | Merge some lower and upper bounds mergeBounds :: Rep c => (Maybe (R c), Maybe (R c)) -> (Maybe (R c), Maybe (R c)) -> (Maybe (R c), Maybe (R c)) -- | Check whether an assignment satisfies the program's constraints and -- bounds checkProgram :: (Rep c, Ord z, Ord r) => Assignment z r c -> Program z r c -> Bool checkBounds :: (Rep c, Ord z, Ord r) => Assignment z r c -> Map (Either z r) (Maybe (R c), Maybe (R c)) -> Bool -- | Substitute an assignment into functions, constraints and programs module Numeric.Limp.Canon.Simplify.Subst -- | Substitute assignment into linear function. However, Linear -- isn't quite a linear function! That is, it doesn't have a constant -- summand. So we must return the constant summand we lose. -- -- Satisfies: -- -- 
--   forall a b f.
--   let (f', c') = substLinear a f
--   in  eval (a <> b) f == eval b f' + c'
--
-- -- 
--   subst (x := 5) in 2x + y
--   (y, 10)
--
substLinear :: (Ord z, Ord r, Rep c) => Assignment z r c -> Linear z r c -> (Linear z r c, R c) -- | Substitute assignment into a single linear constraint. See -- substConstraint. -- -- 
--   5 <= 2x + y <= 10
--   subst (y := 3)
--   2 <= 2x     <= 7
--
substConstraint1 :: (Ord z, Ord r, Rep c) => Assignment z r c -> Constraint1 z r c -> Constraint1 z r c -- | Substitute assignment into a set of linear constraints. Satisfies: -- -- 
--   forall a b f.
--   let c' = substConstraint a c
--   in  check (a <> b) c == check b c'
--
-- -- 
--   subst (x := 5) in 15 <= 2x + y <= 20
--   5 <= y <= 10
--
substConstraint :: (Ord z, Ord r, Rep c) => Assignment z r c -> Constraint z r c -> Constraint z r c -- | Substitute assignment into a program. What does this satisfy? Hm. substProgram :: (Ord z, Ord r, Rep c) => Assignment z r c -> Program z r c -> Program z r c -- | Crunch together all constraints with same linear function module Numeric.Limp.Canon.Simplify.Crunch -- | Crunch the constraints in some program crunchProgram :: (Ord z, Ord r, Rep c) => Program z r c -> Program z r c -- | Crunch some constraints. Constraints with the same function, for -- example -- -- 
--                2x + y    < 5
--   &&   0 <     2x + y
--   &&           2x + y    < 10
--
-- -- becomes -- -- 
--   0 <     2x + y    < 5
--
-- -- This should satisfy: -- -- 
--   forall a c. check a c == check a (crunchConstraint c)
--   forall a.   length (checkConstraint c) <= length c
--
crunchConstraint :: (Ord z, Ord r, Rep c) => Constraint z r c -> Constraint z r c -- | Convert linear constraints that only mention one variable to bounds module Numeric.Limp.Canon.Simplify.Bounder type Bound z r c = (Either z r, (Maybe (R c), Maybe (R c))) -- | Convert a single constraint into a bound, if possible. -- -- 
--   bounder $ Constraint (5 <= y <= 10)
--   == Bound (Just 5) y (Just 10)
--
-- -- 
--   bounder $ Constraint (5 <= 2y <= 10)
--   == Bound (Just 2.5) y (Just 5)
--
-- -- 
--   bounder $ Constraint (10 <= 2y <= 5)
--   == Left InfeasibleBoundEmpty
--
bounderConstraint1 :: (Ord z, Ord r, Rep c) => Constraint1 z r c -> Either Infeasible (Maybe (Bound z r c)) bounderConstraint :: (Ord z, Ord r, Rep c) => Constraint z r c -> Either Infeasible (Constraint z r c, [Bound z r c]) bounderProgram :: (Ord z, Ord r, Rep c) => Program z r c -> Either Infeasible (Program z r c) module Numeric.Limp.Canon.Pretty ppr :: (Show (Z c), Show (R c), Rep c, Show z, Show r, Ord z, Ord r) => (z -> String) -> (r -> String) -> Program z r c -> String instance (GHC.Show.Show (Numeric.Limp.Rep.Rep.Z c), GHC.Show.Show (Numeric.Limp.Rep.Rep.R c), Numeric.Limp.Rep.Rep.Rep c, GHC.Show.Show z, GHC.Show.Show r, GHC.Classes.Ord z, GHC.Classes.Ord r) => GHC.Show.Show (Numeric.Limp.Canon.Program.Program z r c) -- | Convert from Numeric.Limp.Program representation to simpler, -- so-called canonical representation. module Numeric.Limp.Canon.Convert -- | Convert a Frontend Linear into a Canon Linear. Returns -- the constant summand as well, as Canon Linear do not have these. -- -- Should satisfy that forall a l. P.evalR a l == evalR a (fst $ -- linear l) + (snd $ linear l) linear :: (Rep c, Ord z, Ord r) => Linear z r c k -> (Linear z r c, R c) -- | Convert a Frontend Constraint into a Canon Constraint. -- -- Should satisfy that forall a c. P.check a c == check a (constraint -- c) constraint :: (Rep c, Ord z, Ord r) => Constraint z r c -> Constraint z r c -- | Convert a Frontend Program into a Canon Program. -- -- If we had a solve function that worked on either, it would ideally -- satisfy forall p. P.solve p == solve (program p) -- -- However, due to potential non-determinism in solving functions, it -- could be possible to get a different, but still optimal, solution: -- -- 
--   forall p. let aP = P.solve p
--                  p' = program p
--                  a  =   solve p'
--              in P.eval aP (P._objective p) == eval a (_objective p')
--              &&  check a (P._constraints p) && check ...
--
program :: (Rep c, Ord z, Ord r) => Program z r c -> Program z r c -- | A simpler representation of programs. The frontend representation -- (Numeric.Limp.Program) has many different kinds of constraints -- (<=, <, ==, between), as -- well as constant additions on each linear function (eg. x + 2y + -- 5). The so-called canonical representation removes the constant -- addition from each linear constraint, and converts each constraint -- (Lin Op Lin) to (Num <= Lin <= Num). -- -- The most interesting function here is program for converting -- from Program representation to Canon. module Numeric.Limp.Canon -- | Analyse a program to find all constants module Numeric.Limp.Canon.Analyse.Constants -- | Find the constants in a program, only by looking at the bounds with -- lo==up. (See Numeric.Limp.Canon.Simplify.Stride to convert -- constraints to bounds) constantsProgram :: (Ord z, Ord r, Rep c) => Program z r c -> Either Infeasible (Assignment z r c) -- | Perform some simple optimisations on program module Numeric.Limp.Canon.Simplify simplify :: (Ord z, Ord r, Rep c) => Program z r c -> Either Infeasible (Assignment z r c, Program z r c) simplify' :: (Ord z, Ord r, Rep c) => Assignment z r c -> Program z r c -> Either Infeasible (Assignment z r c, Program z r c) -- | The simplest, stupidest possible branch and bound algorithm. module Numeric.Limp.Solve.Branch.Simple branch :: (Ord z, Ord r, Rep c) => (Program z r c -> Maybe (Assignment () (Either z r) c, R c)) -> Program z r c -> Maybe (Assignment z r c, R c) makeIntegral :: (Ord z, Ord r, Rep c) => Assignment () (Either z r) c -> Either (z, R c) (Assignment z r c) -- | 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 module Numeric.Limp.Solve.Simplex.StandardForm -- | A single linear function with a constant summand type StandardRow z r c = (StandardLinear z r c, R c) -- | Entire program in standard form, as well as substitutions required to -- extract an assignment data Standard z r c Standard :: StandardRow z r c -> Map (StandardVar z r) (StandardRow z r c) -> StandardSubst z r c -> Standard z r c [_objective] :: Standard z r c -> StandardRow z r c [_constraints] :: Standard z r c -> Map (StandardVar z r) (StandardRow z r c) [_substs] :: Standard z r c -> 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 -- | A normal variable SV :: Either z r -> StandardVar z r -- | A slack variable, introduced to make less-eq constraints into -- equalities SVS :: Int -> StandardVar z r -- | Magic objective, used when hiding an existing objective as a -- constraint and creating a new objective SVO :: StandardVar 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 SVLower :: Either z r -> StandardVar z r -- | When unconstrained variables are encountered, they are replaced with x -- = SVPos x - SVNeg x so both parts can be constrained to >= 0. SVPos :: Either z r -> StandardVar z r SVNeg :: Either z r -> StandardVar z r -- | Sum a list of linear functions together addLinears :: (Ord z, Ord r, Rep c) => [(StandardLinear z r c, R c)] -> (StandardLinear z r c, R c) -- | Perform substitution over a linear function/row substLinear :: (Ord z, Ord r, Rep c) => StandardSubst z r c -> (StandardLinear z r c, R c) -> (StandardLinear z r c, R c) -- | Convert canon program into standard form standard :: (Ord z, Ord r, Rep c) => Program z r c -> Standard z r c -- | Get the coefficient of a variable in given row lookupRow :: (Ord z, Ord r, Rep c) => StandardRow z r c -> StandardVar z r -> R c -- | Get objective or basis value of a row objOfRow :: StandardRow z r c -> R c instance (GHC.Show.Show z, GHC.Show.Show r) => GHC.Show.Show (Numeric.Limp.Solve.Simplex.StandardForm.StandardVar z r) instance (GHC.Classes.Ord z, GHC.Classes.Ord r) => GHC.Classes.Ord (Numeric.Limp.Solve.Simplex.StandardForm.StandardVar z r) instance (GHC.Classes.Eq z, GHC.Classes.Eq r) => GHC.Classes.Eq (Numeric.Limp.Solve.Simplex.StandardForm.StandardVar z r) instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Solve.Simplex.StandardForm.Standard z r c) -- | The simplest, stupidest possible simplex algorithm. The idea here is -- to be slow, but "obviously correct" so other algorithms can be -- verified against it. -- -- That's the plan, at least. For now this is just a first cut of trying -- to implement simplex. module Numeric.Limp.Solve.Simplex.Maps -- | Result of a single pivot attempt data IterateResult z r c -- | Maximum reached! Done :: IterateResult z r c -- | Pivot was made Progress :: Standard z r c -> IterateResult z r c -- | No progress can be made: unbounded along the objective Stuck :: IterateResult z r c -- | Try to find a pivot and then perform it. We're assuming, at this -- stage, that the existing solution is feasible. simplex1 :: (Ord z, Ord r, Rep c) => Standard z r c -> IterateResult z r c -- | Find pivot row for given column. We're trying to find a way to -- increase the value of column from zero, and the returned row will be -- decreased to zero. Since all variables are >= 0, we cannot return a -- row that would set the column to negative. pivotRowForCol :: (Ord z, Ord r, Rep c) => Standard z r c -> StandardVar z r -> Maybe (StandardVar z r) -- | Find minimum, or nothing if empty minBy' :: (a -> a -> Ordering) -> [a] -> Maybe a -- | Perform pivot for given row and column. We normalise row so that -- row.column = 1 -- -- 
--   norm = row / row[column]
--
-- -- Then, for all other rows including the objective, we want to make sure -- its column entry is zero: -- -- 
--   row' = row - row[column]*norm
--
-- -- In the end, this means "column" will be an identity column, or a basis -- column. pivot :: (Ord z, Ord r, Rep c) => Standard z r c -> (StandardVar z r, StandardVar z r) -> Standard z r c -- | Single phase of simplex. Keep repeating until no progress can be made. single_simplex :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c) -- | Two phase: first, find a satisfying solution. then, solve simplex as -- normal. simplex :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c) -- | Find a satisfying solution. if there are any rows with negative -- values, this means their basic values are negative (which is not -- satisfying the x >= 0 constraint) these negative-valued rows must -- be pivoted around using modified pivot criteria find_initial_sat :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c) assignmentAll :: Rep c => Standard z r c -> (Map (StandardVar z r) (R c), R c) assignment :: (Ord z, Ord r, Rep c) => Standard z r c -> (Assignment () (Either z r) c, R c) -- | Minimise whatever variables are basic in given standard input -- must not already have an objective row SVO, because the -- existing objective is added as a new row with that name minimise_basics :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c -- | Find the basic variables and "price them out" of the objective -- function, by subtracting multiples of the basic row from objective pricing_out :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c -- | Pull the previously-hidden objective out of constraints, and use it drop_fake_objective :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c instance (GHC.Show.Show z, GHC.Show.Show r, GHC.Show.Show (Numeric.Limp.Rep.Rep.R c)) => GHC.Show.Show (Numeric.Limp.Solve.Simplex.Maps.IterateResult z r c)