summaryrefslogtreecommitdiff
path: root/packages
diff options
context:
space:
mode:
Diffstat (limited to 'packages')
-rw-r--r--packages/glpk/src/Numeric/LinearProgramming.hs41
1 files changed, 24 insertions, 17 deletions
diff --git a/packages/glpk/src/Numeric/LinearProgramming.hs b/packages/glpk/src/Numeric/LinearProgramming.hs
index 25cdab2..5de8577 100644
--- a/packages/glpk/src/Numeric/LinearProgramming.hs
+++ b/packages/glpk/src/Numeric/LinearProgramming.hs
@@ -12,7 +12,8 @@ This module provides an interface to the standard simplex algorithm.
12 12
13For example, the following LP problem 13For example, the following LP problem
14 14
15@maximize 4 x_1 - 3 x_2 + 2 x_3 15
16maximize 4 x_1 - 3 x_2 + 2 x_3
16subject to 17subject to
17 18
182 x_1 + x_2 <= 10 192 x_1 + x_2 <= 10
@@ -20,40 +21,46 @@ subject to
20 21
21and 22and
22 23
23x_i >= 0@ 24x_i >= 0
25
24 26
25can be solved as follows: 27can be solved as follows:
26 28
27@import Numeric.LinearProgramming 29@
30import Numeric.LinearProgramming
28 31
29prob = Maximize [4, -3, 2] 32prob = Maximize [4, -3, 2]
30 33
31constr1 = Sparse [ [2\#1, 1\#2] :<=: 10 34constr1 = Sparse [ [2\#1, 1\#2] :<=: 10
32 , [1\#2, 5\#3] :<=: 20 35 , [1\#2, 5\#3] :<=: 20
33 ] 36 ]
37@
38
39>>> simplex prob constr1 []
40Optimal (28.0,[5.0,0.0,4.0])
34 41
35\> simplex prob constr1 []
36Optimal (28.0,[5.0,0.0,4.0])@
37 42
38The coefficients of the constraint matrix can also be given in dense format: 43The coefficients of the constraint matrix can also be given in dense format:
39 44
40@constr2 = Dense [ [2,1,0] :<=: 10 45@
46constr2 = Dense [ [2,1,0] :<=: 10
41 , [0,1,5] :<=: 20 47 , [0,1,5] :<=: 20
42 ]@ 48 ]
49@
43 50
44By default all variables are bounded as @x_i >= 0@, but this can be 51By default all variables are bounded as @x_i >= 0@, but this can be
45changed: 52changed:
46 53
47@\> simplex prob constr2 [ 2 :=>: 1, 3 :&: (2,7)] 54>>> simplex prob constr2 [ 2 :>=: 1, 3 :&: (2,7)]
48Optimal (22.6,[4.5,1.0,3.8]) 55Optimal (22.6,[4.5,1.0,3.8])
49 56
50\> simplex prob constr2 [Free 2] 57>>> simplex prob constr2 [Free 2]
51Unbounded@ 58Unbounded
52 59
53The given bound for a variable completely replaces the default, 60The given bound for a variable completely replaces the default,
54so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@. 61so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@.
55Multiple bounds for a variable are not allowed, instead of 62Multiple bounds for a variable are not allowed, instead of
56@[i :=>: a, i:<=: b]@ use @i :&: (a,b)@. 63@[i :>=: a, i:<=: b]@ use @i :&: (a,b)@.
57 64
58-} 65-}
59 66
@@ -86,7 +93,7 @@ infixl 5 #
86(#) = (,) 93(#) = (,)
87 94
88data Bound x = x :<=: Double 95data Bound x = x :<=: Double
89 | x :=>: Double 96 | x :>=: Double
90 | x :&: (Double,Double) 97 | x :&: (Double,Double)
91 | x :==: Double 98 | x :==: Double
92 | Free x 99 | Free x
@@ -149,28 +156,28 @@ extract sg sol = r where
149 156
150obj :: Bound t -> t 157obj :: Bound t -> t
151obj (x :<=: _) = x 158obj (x :<=: _) = x
152obj (x :=>: _) = x 159obj (x :>=: _) = x
153obj (x :&: _) = x 160obj (x :&: _) = x
154obj (x :==: _) = x 161obj (x :==: _) = x
155obj (Free x) = x 162obj (Free x) = x
156 163
157tb :: Bound t -> Double 164tb :: Bound t -> Double
158tb (_ :<=: _) = glpUP 165tb (_ :<=: _) = glpUP
159tb (_ :=>: _) = glpLO 166tb (_ :>=: _) = glpLO
160tb (_ :&: _) = glpDB 167tb (_ :&: _) = glpDB
161tb (_ :==: _) = glpFX 168tb (_ :==: _) = glpFX
162tb (Free _) = glpFR 169tb (Free _) = glpFR
163 170
164lb :: Bound t -> Double 171lb :: Bound t -> Double
165lb (_ :<=: _) = 0 172lb (_ :<=: _) = 0
166lb (_ :=>: a) = a 173lb (_ :>=: a) = a
167lb (_ :&: (a,_)) = a 174lb (_ :&: (a,_)) = a
168lb (_ :==: a) = a 175lb (_ :==: a) = a
169lb (Free _) = 0 176lb (Free _) = 0
170 177
171ub :: Bound t -> Double 178ub :: Bound t -> Double
172ub (_ :<=: a) = a 179ub (_ :<=: a) = a
173ub (_ :=>: _) = 0 180ub (_ :>=: _) = 0
174ub (_ :&: (_,a)) = a 181ub (_ :&: (_,a)) = a
175ub (_ :==: a) = a 182ub (_ :==: a) = a
176ub (Free _) = 0 183ub (Free _) = 0
@@ -188,7 +195,7 @@ mkBounds n b1 b2 = fromLists (cb++vb) where
188 | otherwise = error $ "simplex: duplicate bounds for vars " ++ show (gv'\\nub gv') 195 | otherwise = error $ "simplex: duplicate bounds for vars " ++ show (gv'\\nub gv')
189 rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv 196 rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv
190 | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n 197 | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n
191 vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:=>: 0)) rv ++ map mkBound2 b2 198 vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:>=: 0)) rv ++ map mkBound2 b2
192 cb = map mkBound1 b1 199 cb = map mkBound1 b1
193 200
194mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double 201mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double