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

data Term ix

Constructors

Term Double ix

Instances

Show ix => Show (Term ix)

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> Term ix -> ShowS

show :: Term ix -> String

showList :: [Term ix] -> ShowS

data Bound

Constructors

LessEqual Double

GreaterEqual Double

Between Double Double

Equal Double

Free

Instances

Show Bound

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> Bound -> ShowS

show :: Bound -> String

showList :: [Bound] -> ShowS

data Inequality x

Constructors

Inequality x Bound

Instances

Functor Inequality

Defined in Numeric.GLPK.Private

Methods

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

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

Show x => Show (Inequality x)

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> Inequality x -> ShowS

show :: Inequality x -> String

showList :: [Inequality x] -> ShowS

free :: x -> Inequality x

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

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

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

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

data NoSolutionType

Constructors

Undefined

NoFeasible

Unbounded

Instances

Eq NoSolutionType

Defined in Numeric.GLPK.Private

Methods

(==) :: NoSolutionType -> NoSolutionType -> Bool

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

Show NoSolutionType

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> NoSolutionType -> ShowS

show :: NoSolutionType -> String

showList :: [NoSolutionType] -> ShowS

NFData NoSolutionType

Defined in Numeric.GLPK.Private

Methods

rnf :: NoSolutionType -> ()

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 Solution sh = Either NoSolutionType (SolutionType, (Double, Array sh Double))

type Constraints ix = [Inequality [Term ix]]

data Direction

Constructors

Minimize

Maximize

Instances

Bounded Direction

Defined in Numeric.GLPK.Private

Methods

minBound :: Direction

maxBound :: Direction

Enum Direction

Defined in Numeric.GLPK.Private

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.GLPK.Private

Methods

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

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

Show Direction

Defined in Numeric.GLPK.Private

Methods

showsPrec :: Int -> Direction -> ShowS

show :: Direction -> String

showList :: [Direction] -> ShowS

type Objective sh = Array sh Double

type Bounds ix = [Inequality ix]

(.*) :: Double -> ix -> Term ix infix 7

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

simplex :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution 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

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

simplexMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)

Deprecated: use GLPK.Monad instead

Optimize for one objective after another. That is, if the first optimization succeeds then the optimum is fixed as constraint and the optimization is continued with respect to the second objective and so on. The iteration fails if one optimization fails. The obtained objective values are returned as well. Their number equals the number of attempted optimizations.

The last objective value is included in the Solution value. This is a bit inconsistent, but this way you have a warranty that there is an objective value if the optimization is successful.

The objectives are expected as Terms because after successful optimization step they are used as (sparse) constraints. It's also easy to assert that the same array shape is used for all objectives.

The function does not work reliably, because an added objective can make the system infeasible due to rounding errors. E.g. a non-negative objective can become very small but negative.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case LP.simplexMulti bounds constrs (Array.shape origin) objs of (_, Right (LP.Optimal, _)) -> QC.property True; result -> QC.counterexample (show result) False

The same property fails for exactMulti and interiorMulti. I guess, due to rounding errors.

simplexSuccessive :: (Traversable f, Eq sh, Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> f ((SolutionType, (Double, Array sh Double)) -> Constraints ix, (Direction, Objective sh)) -> Either NoSolutionType (T f (SolutionType, (Double, Array sh Double)))

Deprecated: use GLPK.Monad instead

Like the Multi functions, but allows not only to fix the previously found optimal solution as constraint, but allows constraints with a tolerance. This is necessary in the presence of rounding errors.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.simplexSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.exactSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

exact :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution 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)))

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAll (TestLP.genProblem 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

exactMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)

Deprecated: use GLPK.Monad instead

Optimize for one objective after another. That is, if the first optimization succeeds then the optimum is fixed as constraint and the optimization is continued with respect to the second objective and so on. The iteration fails if one optimization fails. The obtained objective values are returned as well. Their number equals the number of attempted optimizations.

The last objective value is included in the Solution value. This is a bit inconsistent, but this way you have a warranty that there is an objective value if the optimization is successful.

The objectives are expected as Terms because after successful optimization step they are used as (sparse) constraints. It's also easy to assert that the same array shape is used for all objectives.

The function does not work reliably, because an added objective can make the system infeasible due to rounding errors. E.g. a non-negative objective can become very small but negative.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case LP.simplexMulti bounds constrs (Array.shape origin) objs of (_, Right (LP.Optimal, _)) -> QC.property True; result -> QC.counterexample (show result) False

The same property fails for exactMulti and interiorMulti. I guess, due to rounding errors.

exactSuccessive :: (Traversable f, Eq sh, Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> f ((SolutionType, (Double, Array sh Double)) -> Constraints ix, (Direction, Objective sh)) -> Either NoSolutionType (T f (SolutionType, (Double, Array sh Double)))

Deprecated: use GLPK.Monad instead

Like the Multi functions, but allows not only to fix the previously found optimal solution as constraint, but allows constraints with a tolerance. This is necessary in the presence of rounding errors.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.simplexSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.exactSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

interior :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution 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)))

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAll (TestLP.genProblem 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

interiorMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)

Deprecated: run interior in Either monad instead

Optimize for one objective after another. That is, if the first optimization succeeds then the optimum is fixed as constraint and the optimization is continued with respect to the second objective and so on. The iteration fails if one optimization fails. The obtained objective values are returned as well. Their number equals the number of attempted optimizations.

The last objective value is included in the Solution value. This is a bit inconsistent, but this way you have a warranty that there is an objective value if the optimization is successful.

The objectives are expected as Terms because after successful optimization step they are used as (sparse) constraints. It's also easy to assert that the same array shape is used for all objectives.

The function does not work reliably, because an added objective can make the system infeasible due to rounding errors. E.g. a non-negative objective can become very small but negative.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case LP.simplexMulti bounds constrs (Array.shape origin) objs of (_, Right (LP.Optimal, _)) -> QC.property True; result -> QC.counterexample (show result) False

The same property fails for exactMulti and interiorMulti. I guess, due to rounding errors.

interiorSuccessive :: (Traversable f, Eq sh, Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> f ((SolutionType, (Double, Array sh Double)) -> Constraints ix, (Direction, Objective sh)) -> Either NoSolutionType (T f (SolutionType, (Double, Array sh Double)))

Deprecated: run interior in Either monad instead

Like the Multi functions, but allows not only to fix the previously found optimal solution as constraint, but allows constraints with a tolerance. This is necessary in the presence of rounding errors.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.simplexSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAllShrink (TestLP.genProblem origin) TestLP.shrinkProblem $ \(bounds, constrs) -> QC.forAllShrink (TestLP.genObjectives origin) TestLP.shrinkObjectives $ \objs -> case uncurry (LP.exactSuccessive bounds constrs) $ TestLP.successiveObjectives origin 0.01 objs of result -> QC.counterexample (show result) $ case result of Right results -> all (\r -> case r of (LP.Optimal, _) -> True; _ -> False) results; _ -> False

solveSuccessive :: (Traversable f, Eq sh, Indexed sh, Index sh ~ ix) => (Constraints ix -> (Direction, Objective sh) -> Solution sh) -> Constraints ix -> (Direction, Objective sh) -> f ((SolutionType, (Double, Array sh Double)) -> Constraints ix, (Direction, Objective sh)) -> Either NoSolutionType (T f (SolutionType, (Double, Array sh Double)))

Deprecated: run simple solvers in GLPK.Monad or Either monad instead

Allows for generic implementation of simplexSuccessive et.al. without reuse of interim results.

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAll (TestLP.genProblem origin) $ \(bounds, constrs) -> QC.forAll (TestLP.genObjectives origin) $ (. TestLP.successiveObjectives origin 0.01) $ \(obj,objs) -> case (LP.simplexSuccessive bounds constrs obj objs, LP.solveSuccessive (LP.simplex bounds) constrs obj objs) of (resultA,resultB) -> TestLP.approxSuccession 0.01 resultA resultB

QC.forAllShrink TestLP.genOrigin TestLP.shrinkOrigin $ \origin -> QC.forAll (TestLP.genProblem origin) $ \(bounds, constrs) -> QC.forAll (TestLP.genObjectives origin) $ (. TestLP.successiveObjectives origin 0.01) $ \(obj,objs) -> case (LP.exactSuccessive bounds constrs obj objs, LP.solveSuccessive (LP.exact bounds) constrs obj objs) of (resultA,resultB) -> TestLP.approxSuccession 0.01 resultA resultB

class FormatIdentifier ix

Minimal complete definition

formatIdentifier

Instances

FormatIdentifier Char

Defined in Numeric.GLPK

Methods

formatIdentifier :: Char -> String

FormatIdentifier Int

Defined in Numeric.GLPK

Methods

formatIdentifier :: Int -> String

FormatIdentifier Integer

Defined in Numeric.GLPK

Methods

formatIdentifier :: Integer -> String

FormatIdentifier c => FormatIdentifier [c]

Defined in Numeric.GLPK

Methods

formatIdentifier :: [c] -> String

formatMathProg :: (Indexed sh, Index sh ~ ix, FormatIdentifier ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> [String]