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

# Documentation

data Inequality x Source #

## Instances

Functor Inequality Source # | |

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

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

Defined in Numeric.GLPK 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 (==) :: NoSolutionType -> NoSolutionType -> Bool # (/=) :: NoSolutionType -> NoSolutionType -> Bool # | |

Show NoSolutionType Source # | |

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

NFData NoSolutionType Source # | |

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

data SolutionType Source #

## Instances

Eq SolutionType Source # | |

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

Show SolutionType Source # | |

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

NFData SolutionType Source # | |

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

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

type Constraints ix = [Inequality [Term ix]] 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)`

\(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

simplexMulti :: (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 `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.

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

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

interiorMulti :: (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 `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.