summaryrefslogtreecommitdiff
path: root/packages/glpk/lib/Numeric/LinearProgramming.hs
diff options
context:
space:
mode:
Diffstat (limited to 'packages/glpk/lib/Numeric/LinearProgramming.hs')
-rw-r--r--packages/glpk/lib/Numeric/LinearProgramming.hs55
1 files changed, 21 insertions, 34 deletions
diff --git a/packages/glpk/lib/Numeric/LinearProgramming.hs b/packages/glpk/lib/Numeric/LinearProgramming.hs
index a888214..78f55a2 100644
--- a/packages/glpk/lib/Numeric/LinearProgramming.hs
+++ b/packages/glpk/lib/Numeric/LinearProgramming.hs
@@ -28,8 +28,8 @@ can be solved as follows:
28 28
29prob = Maximize [4, -3, 2] 29prob = Maximize [4, -3, 2]
30 30
31constr1 = Sparse [ [2#1, 1#2] :<: 10 31constr1 = Sparse [ [2\#1, 1\#2] :<: 10
32 , [1#2, 5#3] :<: 20 32 , [1\#2, 5\#3] :<: 20
33 ] 33 ]
34 34
35\> simplex prob constr1 [] 35\> simplex prob constr1 []
@@ -52,6 +52,8 @@ Unbounded@
52 52
53The given bound for a variable completely replaces the default, 53The given bound for a variable completely replaces the default,
54so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@. 54so @0 <= x_i <= b@ must be explicitly given as @i :&: (0,b)@.
55Multiple bounds for a variable are not allowed, instead of
56@[i :>: a, i:<: b]@ use @i :&: (a,b)@.
55 57
56-} 58-}
57 59
@@ -65,11 +67,11 @@ module Numeric.LinearProgramming(
65 Solution(..) 67 Solution(..)
66) where 68) where
67 69
68import Numeric.LinearAlgebra 70import Numeric.LinearAlgebra hiding (i)
69import Data.Packed.Development 71import Data.Packed.Development
70import Foreign(Ptr,unsafePerformIO) 72import Foreign(Ptr,unsafePerformIO)
71import Foreign.C.Types(CInt) 73import Foreign.C.Types(CInt)
72import Data.List((\\),sortBy) 74import Data.List((\\),sortBy,nub)
73import Data.Function(on) 75import Data.Function(on)
74 76
75--import Debug.Trace 77--import Debug.Trace
@@ -82,7 +84,7 @@ import Data.Function(on)
82infixl 5 # 84infixl 5 #
83(#) = (,) 85(#) = (,)
84 86
85data Bound x = x :<: Double 87data Bound x = x :<: Double
86 | x :>: Double 88 | x :>: Double
87 | x :&: (Double,Double) 89 | x :&: (Double,Double)
88 | x :==: Double 90 | x :==: Double
@@ -107,11 +109,13 @@ type Bounds = [Bound Int]
107 109
108simplex :: Optimization -> Constraints -> Bounds -> Solution 110simplex :: Optimization -> Constraints -> Bounds -> Solution
109 111
110simplex opt (Dense []) bnds = simplex opt (Sparse [Free [0#1]]) bnds 112simplex opt (Dense []) bnds = simplex opt (Sparse []) bnds
111simplex opt (Sparse []) bnds = simplex opt (Sparse [Free [0#1]]) bnds 113simplex opt (Sparse []) bnds = simplex opt (Sparse [Free [0#1]]) bnds
112 114
113simplex opt (Dense constr) bnds = extract sg sol where 115simplex opt (Dense constr) bnds = extract sg sol where
114 sol = simplexDense (mkConstrD sz objfun constr) (mkBounds sz constr bnds) 116 sol = simplexSparse m n (mkConstrD sz objfun constr) (mkBounds sz constr bnds)
117 n = length objfun
118 m = length constr
115 (sz, sg, objfun) = adapt opt 119 (sz, sg, objfun) = adapt opt
116 120
117simplex opt (Sparse constr) bnds = extract sg sol where 121simplex opt (Sparse constr) bnds = extract sg sol where
@@ -178,46 +182,37 @@ mkBound2 b = (obj b, mkBound1 b)
178 182
179mkBounds :: Int -> [Bound [a]] -> [Bound Int] -> Matrix Double 183mkBounds :: Int -> [Bound [a]] -> [Bound Int] -> Matrix Double
180mkBounds n b1 b2 = fromLists (cb++vb) where 184mkBounds n b1 b2 = fromLists (cb++vb) where
181 gv = map obj b2 185 gv' = map obj b2
186 gv | nub gv' == gv' = gv'
187 | otherwise = error $ "simplex: duplicate bounds for vars " ++ show (gv'\\nub gv')
182 rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv 188 rv | null gv || minimum gv >= 0 && maximum gv <= n = [1..n] \\ gv
183 | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n 189 | otherwise = error $ "simplex: bounds: variables "++show gv++" not in 1.."++show n
184 vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:>: 0)) rv ++ map mkBound2 b2 190 vb = map snd $ sortBy (compare `on` fst) $ map (mkBound2 . (:>: 0)) rv ++ map mkBound2 b2
185 cb = map mkBound1 b1 191 cb = map mkBound1 b1
186 192
187mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double 193mkConstrD :: Int -> [Double] -> [Bound [Double]] -> Matrix Double
188mkConstrD n f b1 | ok = fromLists (f : cs) 194mkConstrD n f b1 | ok = fromLists (ob ++ co)
189 | otherwise = error $ "simplex: dense constraints require "++show n 195 | otherwise = error $ "simplex: dense constraints require "++show n
190 ++" variables, given " ++ show ls 196 ++" variables, given " ++ show ls
191 where 197 where
192 cs | null b1 = error $ "simplex: dense: empty constraints" 198 cs = map obj b1
193 | otherwise = map obj b1
194 ls = map length cs 199 ls = map length cs
195 ok = all (==n) ls 200 ok = all (==n) ls
201 den = fromLists cs
202 ob = map (([0,0]++).return) f
203 co = [[fromIntegral i, fromIntegral j,den@@>(i-1,j-1)]| i<-[1 ..rows den], j<-[1 .. cols den]]
196 204
197mkConstrS :: Int -> [Double] -> [Bound [(Double, Int)]] -> Matrix Double 205mkConstrS :: Int -> [Double] -> [Bound [(Double, Int)]] -> Matrix Double
198mkConstrS n objfun b1 = fromLists (ob ++ co) where 206mkConstrS n objfun b1 = fromLists (ob ++ co) where
199 ob = map (([0,0]++).return) objfun 207 ob = map (([0,0]++).return) objfun
200 co = concat $ zipWith f [1::Int ..] cs 208 co = concat $ zipWith f [1::Int ..] cs
201 cs | null b1 = error $ "simplex: sparse: empty constraints" 209 cs = map obj b1
202 | otherwise = map obj b1
203 f k = map (g k) 210 f k = map (g k)
204 g k (c,v) | v >=1 && v<= n = [fromIntegral k, fromIntegral v,c] 211 g k (c,v) | v >=1 && v<= n = [fromIntegral k, fromIntegral v,c]
205 | otherwise = error $ "simplex: sparse constraints: variable "++show v++" not in 1.."++show n 212 | otherwise = error $ "simplex: sparse constraints: variable "++show v++" not in 1.."++show n
206 213
207----------------------------------------------------- 214-----------------------------------------------------
208 215
209foreign import ccall "c_simplex_dense" c_simplex_dense
210 :: CInt -> CInt -> Ptr Double -- coeffs
211 -> CInt -> CInt -> Ptr Double -- bounds
212 -> CInt -> Ptr Double -- result
213 -> IO CInt -- exit code
214
215simplexDense :: Matrix Double -> Matrix Double -> Vector Double
216simplexDense c b = unsafePerformIO $ do
217 s <- createVector (2+cols c)
218 app3 c_simplex_dense mat (cmat c) mat (cmat b) vec s "c_simplex_dense"
219 return s
220
221foreign import ccall "c_simplex_sparse" c_simplex_sparse 216foreign import ccall "c_simplex_sparse" c_simplex_sparse
222 :: CInt -> CInt -- rows and cols 217 :: CInt -> CInt -- rows and cols
223 -> CInt -> CInt -> Ptr Double -- coeffs 218 -> CInt -> CInt -> Ptr Double -- coeffs
@@ -241,14 +236,6 @@ glpFX = 4
241 236
242{- Raw format of coeffs 237{- Raw format of coeffs
243 238
244simplexDense
245
246((3+1) >< 3)
247 [ 10, 6, 4
248 , 1, 1, 1
249 , 10, 4, 5
250 , 2, 2, 6 :: Double]
251
252simplexSparse 239simplexSparse
253 240
254(12><3) 241(12><3)
@@ -264,7 +251,7 @@ simplexSparse
264 , 3.0, 1.0, 2.0 251 , 3.0, 1.0, 2.0
265 , 3.0, 2.0, 2.0 252 , 3.0, 2.0, 2.0
266 , 3.0, 3.0, 6.0 ] 253 , 3.0, 3.0, 6.0 ]
267 254
268bounds = (6><3) 255bounds = (6><3)
269 [ glpUP,0,100 256 [ glpUP,0,100
270 , glpUP,0,600 257 , glpUP,0,600