comfort-glpk-0.1: Linear Programming using GLPK and comfort-array

Numeric.GLPK

Description

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).

Synopsis

# Documentation

type Term = Term Double Source #

data Bound #

Constructors

 LessEqual Double GreaterEqual Double Between Double Double Equal Double Free
Instances
 Instance detailsDefined in Numeric.LinearProgramming.Common MethodsshowsPrec :: Int -> Bound -> ShowS #show :: Bound -> String #showList :: [Bound] -> ShowS #

data Inequality x #

Constructors

 Inequality x Bound
Instances
 Instance detailsDefined in Numeric.LinearProgramming.Common Methodsfmap :: (a -> b) -> Inequality a -> Inequality b #(<$) :: a -> Inequality b -> Inequality a # Show x => Show (Inequality x) Instance detailsDefined in Numeric.LinearProgramming.Common MethodsshowsPrec :: 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 # Constructors  Undefined NoFeasible Unbounded Instances  Source # Instance detailsDefined in Numeric.GLPK.Private Methods Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowList :: [FailureType] -> ShowS # Source # Instance detailsDefined in Numeric.GLPK.Private Methodsrnf :: FailureType -> () # Constructors  Feasible Infeasible Optimal Instances  Source # Instance detailsDefined in Numeric.GLPK.Private Methods Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowList :: [SolutionType] -> ShowS # Source # Instance detailsDefined in Numeric.GLPK.Private Methodsrnf :: SolutionType -> () # type Constraints ix = Constraints Double ix Source # data Direction # Constructors  Minimize Maximize Instances  Instance detailsDefined in Numeric.LinearProgramming.Common Methods Instance detailsDefined in Numeric.LinearProgramming.Common MethodsenumFrom :: Direction -> [Direction] # Instance detailsDefined in Numeric.LinearProgramming.Common Methods Instance detailsDefined in Numeric.LinearProgramming.Common MethodsshowList :: [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 Source # >>> 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 Source #

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