Numeric.GLPK

The following LP problem

maximize 4 x_1 - 3 x_2 + 2 x_3 subject to

2 x_1 + x_2 <= 10

x_2 + 5 x_3 <= 20

and

x_i >= 0

is used as an example in the doctest comments.

By default all indeterminates are non-negative. A given bound for a variable completely replaces the default, so 0 <= x_i <= b must be explicitly given as i >=<. (0,b). Multiple bounds for a variable are not allowed, instead of [i >=. a, i <=. b] use i >=<. (a,b).

Documentation

type Term = Term Double

data Bound

Constructors

LessEqual Double

GreaterEqual Double

Between Double Double

Equal Double

Free

Instances

Show Bound

Defined in Numeric.LinearProgramming.Common

Methods

showsPrec :: Int -> Bound -> ShowS

show :: Bound -> String

showList :: [Bound] -> ShowS

data Inequality x

Constructors

Inequality x Bound

Instances

Functor Inequality

Defined in Numeric.LinearProgramming.Common

Methods

fmap :: (a -> b) -> Inequality a -> Inequality b

(<$) :: a -> Inequality b -> Inequality a

Show x => Show (Inequality x)

Defined in Numeric.LinearProgramming.Common

Methods

showsPrec :: Int -> Inequality x -> ShowS

show :: Inequality x -> String

showList :: [Inequality x] -> ShowS

free :: x -> Inequality x

(<=.) :: x -> Double -> Inequality x

(>=.) :: x -> Double -> Inequality x

(==.) :: x -> Double -> Inequality x

(>=<.) :: x -> (Double, Double) -> Inequality x

data FailureType

Constructors

Undefined

NoFeasible

Unbounded

Instances

Eq FailureType

Defined in Numeric.GLPK.Private

Methods

(==) :: FailureType -> FailureType -> Bool

(/=) :: FailureType -> FailureType -> Bool

Show FailureType

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> FailureType -> ShowS

show :: FailureType -> String

showList :: [FailureType] -> ShowS

NFData FailureType

Defined in Numeric.GLPK.Private

Methods

rnf :: FailureType -> ()

data SolutionType

Constructors

Feasible

Infeasible

Optimal

Instances

Eq SolutionType

Defined in Numeric.GLPK.Private

Methods

(==) :: SolutionType -> SolutionType -> Bool

(/=) :: SolutionType -> SolutionType -> Bool

Show SolutionType

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> SolutionType -> ShowS

show :: SolutionType -> String

showList :: [SolutionType] -> ShowS

NFData SolutionType

Defined in Numeric.GLPK.Private

Methods

rnf :: SolutionType -> ()

type Result sh = Either FailureType (SolutionType, (Double, Array sh Double))

type Constraints ix = Constraints Double ix

data Direction

Constructors

Minimize

Maximize

Instances

Bounded Direction

Defined in Numeric.LinearProgramming.Common

Methods

minBound :: Direction

maxBound :: Direction

Enum Direction

Defined in Numeric.LinearProgramming.Common

Methods

succ :: Direction -> Direction

pred :: Direction -> Direction

toEnum :: Int -> Direction

fromEnum :: Direction -> Int

enumFrom :: Direction -> [Direction]

enumFromThen :: Direction -> Direction -> [Direction]

enumFromTo :: Direction -> Direction -> [Direction]

enumFromThenTo :: Direction -> Direction -> Direction -> [Direction]

Eq Direction

Defined in Numeric.LinearProgramming.Common

Methods

(==) :: Direction -> Direction -> Bool

(/=) :: Direction -> Direction -> Bool

Show Direction

Defined in Numeric.LinearProgramming.Common

Methods

showsPrec :: Int -> Direction -> ShowS

show :: Direction -> String

showList :: [Direction] -> ShowS

type Objective sh = Array sh Double

type Bounds ix = [Inequality ix]

(.*) :: a -> ix -> Term a ix

objectiveFromTerms :: (Indexed sh, Index sh ~ ix) => sh -> [Term Double ix] -> Objective sh

simplex :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Result sh

>>> case Shape.indexTupleFromShape tripletShape of (x1,x2,x3) -> mapSnd (mapSnd Array.toTuple) <$> LP.simplex [] [[2.*x1, 1.*x2] <=. 10, [1.*x2, 5.*x3] <=. 20] (LP.Maximize, Array.fromTuple (4,-3,2) :: Array.Array TripletShape Double)
Right (Optimal,(28.0,(5.0,0.0,4.0)))

\target -> case Shape.indexTupleFromShape pairShape of (pos,neg) -> case mapSnd (mapSnd Array.toTuple) <$> LP.simplex [] [[1.*pos, (-1).*neg] ==. target] (LP.Minimize, Array.fromTuple (1,1) :: Array.Array PairShape Double) of (Right (LP.Optimal,(absol,(posResult,negResult)))) -> QC.property (TestLP.approxReal 0.001 absol (abs target)) .&&. (posResult === 0 .||. negResult === 0); _ -> QC.property False

\(QC.Positive posWeight) (QC.Positive negWeight) target -> case Shape.indexTupleFromShape pairShape of (pos,neg) -> case mapSnd (mapSnd Array.toTuple) <$> LP.simplex [] [[1.*pos, (-1).*neg] ==. target] (LP.Minimize, Array.fromTuple (posWeight,negWeight) :: Array.Array PairShape Double) of (Right (LP.Optimal,(absol,(posResult,negResult)))) -> QC.property (absol>=0) .&&. (posResult === 0 .||. negResult === 0); _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.simplex bounds constrs (dir,obj) of Right (LP.Optimal, _) -> True; _ -> False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.simplex bounds constrs (dir,obj) of Right (LP.Optimal, (_,sol)) -> TestLP.checkFeasibility 0.1 bounds constrs sol; _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.simplex bounds constrs (dir,obj) of Right (LP.Optimal, (_,sol)) -> QC.forAll (QC.choose (0,1)) $ \lambda -> TestLP.checkFeasibility 0.1 bounds constrs $ TestLP.affineCombination lambda sol (Array.map fromIntegral origin); _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.simplex bounds constrs (dir,obj) of Right (LP.Optimal, (opt,sol)) -> QC.forAll (QC.choose (0,1)) $ \lambda -> let val = TestLP.scalarProduct obj $ TestLP.affineCombination lambda sol (Array.map fromIntegral origin) in (case dir of LP.Minimize -> opt-0.01 <= val; LP.Maximize -> opt+0.01 >= val); _ -> QC.property False

exact :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Result sh

>>> case Shape.indexTupleFromShape tripletShape of (x1,x2,x3) -> mapSnd (mapSnd Array.toTuple) <$> LP.exact [] [[2.*x1, 1.*x2] <=. 10, [1.*x2, 5.*x3] <=. 20] (LP.Maximize, Array.fromTuple (4,-3,2) :: Array.Array TripletShape Double)
Right (Optimal,(28.0,(5.0,0.0,4.0)))

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case (LP.simplex bounds constrs (dir,obj), LP.exact bounds constrs (dir,obj)) of (Right (LP.Optimal, (optSimplex,_)), Right (LP.Optimal, (optExact,_))) -> TestLP.approx "optimum" 0.001 optSimplex optExact; _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.exact bounds constrs (dir,obj) of Right (LP.Optimal, (_,sol)) -> TestLP.checkFeasibility 0.1 bounds constrs sol; _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.exact bounds constrs (dir,obj) of Right (LP.Optimal, (_,sol)) -> QC.forAll (QC.choose (0,1)) $ \lambda -> TestLP.checkFeasibility 0.01 bounds constrs $ TestLP.affineCombination lambda sol (Array.map fromIntegral origin); _ -> QC.property False

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case LP.exact bounds constrs (dir,obj) of Right (LP.Optimal, (opt,sol)) -> QC.forAll (QC.choose (0,1)) $ \lambda -> let val = TestLP.scalarProduct obj $ TestLP.affineCombination lambda sol (Array.map fromIntegral origin) in (case dir of LP.Minimize -> opt-0.01 <= val; LP.Maximize -> opt+0.01 >= val); _ -> QC.property False

interior :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Result sh

>>> case Shape.indexTupleFromShape tripletShape of (x1,x2,x3) -> mapSnd (mapPair (round3, Array.toTuple . Array.map round3)) <$> LP.interior [] [[2.*x1, 1.*x2] <=. 10, [1.*x2, 5.*x3] <=. 20] (LP.Maximize, Array.fromTuple (4,-3,2) :: Array.Array TripletShape Double)
Right (Optimal,(28.0,(5.0,0.0,4.0)))

TestLP.forAllOrigin $ \origin -> TestLP.forAllProblem origin $ \bounds constrs -> QC.forAll (TestLP.genObjective origin) $ \(dir,obj) -> case (LP.simplex bounds constrs (dir,obj), LP.interior bounds constrs (dir,obj)) of (Right (LP.Optimal, (optSimplex,_)), Right (LP.Optimal, (optExact,_))) -> TestLP.approx "optimum" 0.001 optSimplex optExact; _ -> QC.property False