summaryrefslogtreecommitdiff
path: root/packages
diff options
context:
space:
mode:
Diffstat (limited to 'packages')
-rw-r--r--packages/glpk/examples/simplex1.hs4
-rw-r--r--packages/glpk/examples/simplex2.hs5
-rw-r--r--packages/glpk/examples/simplex3.hs5
-rw-r--r--packages/glpk/examples/simplex4.hs5
-rw-r--r--packages/glpk/lib/Numeric/LinearProgramming.hs70
5 files changed, 74 insertions, 15 deletions
diff --git a/packages/glpk/examples/simplex1.hs b/packages/glpk/examples/simplex1.hs
index 4609524..9639f37 100644
--- a/packages/glpk/examples/simplex1.hs
+++ b/packages/glpk/examples/simplex1.hs
@@ -5,8 +5,8 @@ import Numeric.LinearProgramming
5objFun = Maximize [10, 6, 4] 5objFun = Maximize [10, 6, 4]
6 6
7constr = Dense [ [1,1,1] :<: 100 7constr = Dense [ [1,1,1] :<: 100
8 , [10,4,5] :<: 600 8 , [10,4,5] :<: 600
9 , [2,2,6] :<: 300 ] 9 , [2,2,6] :<: 300 ]
10 10
11-- default bounds 11-- default bounds
12bnds = [ 1 :>: 0 12bnds = [ 1 :>: 0
diff --git a/packages/glpk/examples/simplex2.hs b/packages/glpk/examples/simplex2.hs
index 76a53df..40e4bbd 100644
--- a/packages/glpk/examples/simplex2.hs
+++ b/packages/glpk/examples/simplex2.hs
@@ -1,6 +1,6 @@
1import Numeric.LinearProgramming 1import Numeric.LinearProgramming
2 2
3prob = Maximize [1,2,3,4] 3prob = Maximize [4, 3, -2, 7]
4 4
5constr1 = Sparse [ [1#1, 1#2] :<: 10 5constr1 = Sparse [ [1#1, 1#2] :<: 10
6 , [1#3, 1#4] :<: 10 6 , [1#3, 1#4] :<: 10
@@ -12,5 +12,6 @@ constr2 = Dense [ [1,1,0,0] :<: 10
12 12
13main = do 13main = do
14 print $ simplex prob constr1 [] 14 print $ simplex prob constr1 []
15 print $ simplex prob constr2 [] 15 print $ simplex prob constr2 [ 2 :>: 1, 4 :&: (2,7)]
16 print $ simplex prob constr2 [ Free 3 ]
16 17
diff --git a/packages/glpk/examples/simplex3.hs b/packages/glpk/examples/simplex3.hs
index 0f787cb..3a7e8e8 100644
--- a/packages/glpk/examples/simplex3.hs
+++ b/packages/glpk/examples/simplex3.hs
@@ -1,7 +1,8 @@
1import Numeric.LinearProgramming 1-- compare with
2
3-- $ glpsol --cpxlp /usr/share/doc/glpk-utils/examples/plan.lp -o result.txt 2-- $ glpsol --cpxlp /usr/share/doc/glpk-utils/examples/plan.lp -o result.txt
4 3
4import Numeric.LinearProgramming
5
5prob = Minimize [0.03, 0.08, 0.17, 0.12, 0.15, 0.21, 0.38] 6prob = Minimize [0.03, 0.08, 0.17, 0.12, 0.15, 0.21, 0.38]
6 7
7constr = Dense 8constr = Dense
diff --git a/packages/glpk/examples/simplex4.hs b/packages/glpk/examples/simplex4.hs
index 3b9c060..8496f6d 100644
--- a/packages/glpk/examples/simplex4.hs
+++ b/packages/glpk/examples/simplex4.hs
@@ -1,7 +1,8 @@
1import Numeric.LinearProgramming 1-- compare with
2
3-- $ glpsol --cpxlp /usr/share/doc/glpk-utils/examples/plan.lp -o result.txt 2-- $ glpsol --cpxlp /usr/share/doc/glpk-utils/examples/plan.lp -o result.txt
4 3
4import Numeric.LinearProgramming
5
5prob = Minimize [0.03, 0.08, 0.17, 0.12, 0.15, 0.21, 0.38] 6prob = Minimize [0.03, 0.08, 0.17, 0.12, 0.15, 0.21, 0.38]
6 7
7constr = Sparse 8constr = Sparse
diff --git a/packages/glpk/lib/Numeric/LinearProgramming.hs b/packages/glpk/lib/Numeric/LinearProgramming.hs
index 1b14080..fff304f 100644
--- a/packages/glpk/lib/Numeric/LinearProgramming.hs
+++ b/packages/glpk/lib/Numeric/LinearProgramming.hs
@@ -1,12 +1,66 @@
1{-# LANGUAGE ForeignFunctionInterface #-} 1{-# LANGUAGE ForeignFunctionInterface #-}
2 2
3{- |
4Module : Numeric.LinearProgramming
5Copyright : (c) Alberto Ruiz 2010
6License : GPL
7
8Maintainer : Alberto Ruiz (aruiz at um dot es)
9Stability : provisional
10
11This module provides an interface to the standard simplex algorithm.
12
13For example, the following linear programming problem
14
15@maximize 4 x_1 + 3 x_2 - 2 x_3 + 7 x_4
16subject to
17
18x_1 + x_2 <= 10
19x_3 + x_4 <= 10
20
21and
22
23x_i >= 0@
24
25can be solved as follows:
26
27@import Numeric.LinearProgramming
28
29prob = Maximize [4, 3, -2, 7]
30
31constr1 = Sparse [ [1\#1, 1\#2] :<: 10
32 , [1\#3, 1\#4] :<: 10
33 ]
34
35
36\> simplex prob constr1 []
37Optimal (110.0,[10.0,0.0,0.0,10.0])@
38
39The coefficients of the constraint matrix can also be given in dense format:
40
41@constr2 = Dense [ [1,1,0,0] :<: 10
42 , [0,0,1,1] :<: 10
43 ]@
44
45By default all variables are bounded as @x_i <= 0@, but this can be
46changed:
47
48@\> simplex prob constr2 [2 :>: 1, 4 :&: (2,7)]
49Optimal (88.0,[9.0,1.0,0.0,7.0])
50
51\> simplex prob constr2 [Free 3]
52Unbounded@
53
54-}
55
3module Numeric.LinearProgramming( 56module Numeric.LinearProgramming(
57 simplex,
4 Optimization(..), 58 Optimization(..),
59 Constraints(..),
60 Bounds,
5 Bound(..), 61 Bound(..),
6 (#), 62 (#),
7 Coeffs(..), 63 Solution(..)
8 Solution(..),
9 simplex,
10) where 64) where
11 65
12import Numeric.LinearAlgebra 66import Numeric.LinearAlgebra
@@ -21,7 +75,7 @@ import Data.Function(on)
21 75
22----------------------------------------------------- 76-----------------------------------------------------
23 77
24-- | Coefficient of a variable 78-- | Coefficient of a variable for a sparse representation of constraints.
25(#) :: Double -> Int -> (Double,Int) 79(#) :: Double -> Int -> (Double,Int)
26infixl 5 # 80infixl 5 #
27(#) = (,) 81(#) = (,)
@@ -41,13 +95,15 @@ data Solution = Undefined
41 | Unbounded 95 | Unbounded
42 deriving Show 96 deriving Show
43 97
44data Coeffs = Dense [ Bound [Double] ] 98data Constraints = Dense [ Bound [Double] ]
45 | Sparse [ Bound [(Double,Int)] ] 99 | Sparse [ Bound [(Double,Int)] ]
46 100
47data Optimization = Maximize [Double] 101data Optimization = Maximize [Double]
48 | Minimize [Double] 102 | Minimize [Double]
49 103
50simplex :: Optimization -> Coeffs -> [Bound Int] -> Solution 104type Bounds = [Bound Int]
105
106simplex :: Optimization -> Constraints -> Bounds -> Solution
51 107
52simplex opt (Dense constr) bnds = extract sg sol where 108simplex opt (Dense constr) bnds = extract sg sol where
53 sol = simplexDense (mkConstrD objfun constr) (mkBoundsD constr bnds) 109 sol = simplexDense (mkConstrD objfun constr) (mkBoundsD constr bnds)