Safe Haskell | None |
---|---|

Language | Haskell98 |

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

- data Term ix = Term Double ix
- data Bound
- data Inequality x = Inequality x Bound
- free :: x -> Inequality x
- (<=.) :: x -> Double -> Inequality x
- (>=.) :: x -> Double -> Inequality x
- (==.) :: x -> Double -> Inequality x
- (>=<.) :: x -> (Double, Double) -> Inequality x
- data NoSolutionType
- data SolutionType
- type Solution sh = Either NoSolutionType (SolutionType, (Double, Array sh Double))
- type Constraints ix = [Inequality [Term ix]]
- data Direction
- type Objective sh = Array sh Double
- type Bounds ix = [Inequality ix]
- (.*) :: Double -> ix -> Term ix
- 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
- simplexMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)
- 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)))
- exact :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution sh
- exactMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)
- 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)))
- interior :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution sh
- interiorMulti :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> sh -> T [] (Direction, [Term ix]) -> ([Double], Solution sh)
- 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)))
- 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)))
- class FormatIdentifier ix
- formatMathProg :: (Indexed sh, Index sh ~ ix, FormatIdentifier ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> [String]

# Documentation

data Inequality x Source #

## Instances

Functor Inequality Source # | |

Defined in Numeric.GLPK.Private fmap :: (a -> b) -> Inequality a -> Inequality b # (<$) :: a -> Inequality b -> Inequality a # | |

Show x => Show (Inequality x) Source # | |

Defined in Numeric.GLPK.Private showsPrec :: Int -> Inequality x -> ShowS # show :: Inequality x -> String # showList :: [Inequality x] -> ShowS # |

free :: x -> Inequality x Source #

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

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

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

data NoSolutionType Source #

## Instances

Eq NoSolutionType Source # | |

Defined in Numeric.GLPK.Private (==) :: NoSolutionType -> NoSolutionType -> Bool # (/=) :: NoSolutionType -> NoSolutionType -> Bool # | |

Show NoSolutionType Source # | |

Defined in Numeric.GLPK.Private showsPrec :: Int -> NoSolutionType -> ShowS # show :: NoSolutionType -> String # showList :: [NoSolutionType] -> ShowS # | |

NFData NoSolutionType Source # | |

Defined in Numeric.GLPK.Private rnf :: NoSolutionType -> () # |

data SolutionType Source #

## Instances

Eq SolutionType Source # | |

Defined in Numeric.GLPK.Private (==) :: SolutionType -> SolutionType -> Bool # (/=) :: SolutionType -> SolutionType -> Bool # | |

Show SolutionType Source # | |

Defined in Numeric.GLPK.Private showsPrec :: Int -> SolutionType -> ShowS # show :: SolutionType -> String # showList :: [SolutionType] -> ShowS # | |

NFData SolutionType Source # | |

Defined in Numeric.GLPK.Private rnf :: SolutionType -> () # |

type Solution sh = Either NoSolutionType (SolutionType, (Double, Array sh Double)) Source #

type Constraints ix = [Inequality [Term ix]] Source #

## Instances

Bounded Direction Source # | |

Enum Direction Source # | |

Defined in Numeric.GLPK.Private succ :: Direction -> Direction # pred :: Direction -> Direction # fromEnum :: Direction -> Int # enumFrom :: Direction -> [Direction] # enumFromThen :: Direction -> Direction -> [Direction] # enumFromTo :: Direction -> Direction -> [Direction] # enumFromThenTo :: Direction -> Direction -> Direction -> [Direction] # | |

Eq Direction Source # | |

Show Direction Source # | |

type Bounds ix = [Inequality ix] Source #

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

`>>>`

Right (Optimal,(28.0,(5.0,0.0,4.0)))`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)`

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

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 `Term`

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

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

`>>>`

Right (Optimal,(28.0,(5.0,0.0,4.0)))`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)`

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

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 `Term`

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

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

`>>>`

Right (Optimal,(28.0,(5.0,0.0,4.0)))`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)`

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

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 `Term`

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

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

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

formatIdentifier

## Instances

FormatIdentifier Char Source # | |

Defined in Numeric.GLPK formatIdentifier :: Char -> String | |

FormatIdentifier Int Source # | |

Defined in Numeric.GLPK formatIdentifier :: Int -> String | |

FormatIdentifier Integer Source # | |

Defined in Numeric.GLPK formatIdentifier :: Integer -> String | |

FormatIdentifier c => FormatIdentifier [c] Source # | |

Defined in Numeric.GLPK formatIdentifier :: [c] -> String |

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