comfort-glpk-0.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

data Term ix Source #

Constructors

 Term Double ix
Instances
 Show ix => Show (Term ix) Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowsPrec :: Int -> Term ix -> ShowS #show :: Term ix -> String #showList :: [Term ix] -> ShowS #

data Bound Source #

Constructors

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

data Inequality x Source #

Constructors

 Inequality x Bound
Instances
 Source # Instance detailsDefined in Numeric.GLPK.Private Methodsfmap :: (a -> b) -> Inequality a -> Inequality b #(<$) :: a -> Inequality b -> Inequality a # Show x => Show (Inequality x) Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowsPrec :: Int -> Inequality x -> ShowS #show :: Inequality x -> String #showList :: [Inequality x] -> ShowS # (<=.) :: x -> Double -> Inequality x infix 4 Source # (>=.) :: x -> Double -> Inequality x infix 4 Source # (==.) :: x -> Double -> Inequality x infix 4 Source # (>=<.) :: x -> (Double, Double) -> Inequality x infix 4 Source # Constructors  Undefined NoFeasible Unbounded Instances  Source # Instance detailsDefined in Numeric.GLPK.Private Methods Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowList :: [NoSolutionType] -> ShowS # Source # Instance detailsDefined in Numeric.GLPK.Private Methodsrnf :: NoSolutionType -> () # 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 -> () # data Direction Source # Constructors  Minimize Maximize Instances  Source # Instance detailsDefined in Numeric.GLPK.Private Methods Source # Instance detailsDefined in Numeric.GLPK.Private MethodsenumFrom :: Direction -> [Direction] # Source # Instance detailsDefined in Numeric.GLPK.Private Methods Source # Instance detailsDefined in Numeric.GLPK.Private MethodsshowList :: [Direction] -> ShowS # type Bounds ix = [Inequality ix] Source # (.*) :: Double -> ix -> Term ix infix 7 Source # objectiveFromTerms :: (Indexed sh, Index sh ~ ix) => sh -> [Term ix] -> Objective sh Source # simplex :: (Indexed sh, Index sh ~ ix) => Bounds ix -> Constraints ix -> (Direction, Objective sh) -> Solution 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
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 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))) Source #

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 #

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

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

Minimal complete definition

formatIdentifier

Instances
 Source # Instance detailsDefined in Numeric.GLPK Methods Source # Instance detailsDefined in Numeric.GLPK Methods Source # Instance detailsDefined in Numeric.GLPK Methods Source # Instance detailsDefined in Numeric.GLPK MethodsformatIdentifier :: [c] -> String