{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_HADDOCK show-extensions #-}
module ToySolver.Arith.Simplex.Textbook.LPSolver.Simple
( OptResult (..)
, minimize
, maximize
, optimize
, solve
) where
import Control.Monad.State
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS
import Data.OptDir
import Data.VectorSpace
import ToySolver.Data.OrdRel
import qualified ToySolver.Data.LA as LA
import ToySolver.Data.IntVar
import qualified ToySolver.Arith.Simplex.Textbook as Simplex
import qualified ToySolver.Arith.Simplex.Textbook.LPSolver as LPSolver
import ToySolver.Arith.Simplex.Textbook.LPSolver hiding (OptResult (..))
data OptResult r = OptUnsat | Unbounded | Optimum r (Model r)
deriving (Int -> OptResult r -> ShowS
forall r. Show r => Int -> OptResult r -> ShowS
forall r. Show r => [OptResult r] -> ShowS
forall r. Show r => OptResult r -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [OptResult r] -> ShowS
$cshowList :: forall r. Show r => [OptResult r] -> ShowS
show :: OptResult r -> String
$cshow :: forall r. Show r => OptResult r -> String
showsPrec :: Int -> OptResult r -> ShowS
$cshowsPrec :: forall r. Show r => Int -> OptResult r -> ShowS
Show, OptResult r -> OptResult r -> Bool
forall r. Eq r => OptResult r -> OptResult r -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: OptResult r -> OptResult r -> Bool
$c/= :: forall r. Eq r => OptResult r -> OptResult r -> Bool
== :: OptResult r -> OptResult r -> Bool
$c== :: forall r. Eq r => OptResult r -> OptResult r -> Bool
Eq, OptResult r -> OptResult r -> Bool
OptResult r -> OptResult r -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {r}. Ord r => Eq (OptResult r)
forall r. Ord r => OptResult r -> OptResult r -> Bool
forall r. Ord r => OptResult r -> OptResult r -> Ordering
forall r. Ord r => OptResult r -> OptResult r -> OptResult r
min :: OptResult r -> OptResult r -> OptResult r
$cmin :: forall r. Ord r => OptResult r -> OptResult r -> OptResult r
max :: OptResult r -> OptResult r -> OptResult r
$cmax :: forall r. Ord r => OptResult r -> OptResult r -> OptResult r
>= :: OptResult r -> OptResult r -> Bool
$c>= :: forall r. Ord r => OptResult r -> OptResult r -> Bool
> :: OptResult r -> OptResult r -> Bool
$c> :: forall r. Ord r => OptResult r -> OptResult r -> Bool
<= :: OptResult r -> OptResult r -> Bool
$c<= :: forall r. Ord r => OptResult r -> OptResult r -> Bool
< :: OptResult r -> OptResult r -> Bool
$c< :: forall r. Ord r => OptResult r -> OptResult r -> Bool
compare :: OptResult r -> OptResult r -> Ordering
$ccompare :: forall r. Ord r => OptResult r -> OptResult r -> Ordering
Ord)
maximize :: (RealFrac r) => LA.Expr r -> [LA.Atom r] -> OptResult r
maximize :: forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize = forall r. RealFrac r => OptDir -> Expr r -> [Atom r] -> OptResult r
optimize OptDir
OptMax
minimize :: (RealFrac r) => LA.Expr r -> [LA.Atom r] -> OptResult r
minimize :: forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
minimize = forall r. RealFrac r => OptDir -> Expr r -> [Atom r] -> OptResult r
optimize OptDir
OptMin
solve :: (RealFrac r) => [LA.Atom r] -> Maybe (Model r)
solve :: forall r. RealFrac r => [Atom r] -> Maybe (Model r)
solve [Atom r]
cs =
forall a b c. (a -> b -> c) -> b -> a -> c
flip forall s a. State s a -> s -> a
evalState (forall r. VarSet -> Solver r
emptySolver VarSet
vs) forall a b. (a -> b) -> a -> b
$ do
forall r. RealFrac r => [Atom r] -> LP r ()
tableau [Atom r]
cs
Bool
ret <- forall r. (Fractional r, Real r) => LP r Bool
phaseI
if Bool -> Bool
not Bool
ret
then forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
else do
Model r
m <- forall r. Fractional r => VarSet -> LP r (Model r)
getModel VarSet
vs
forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just Model r
m)
where
vs :: VarSet
vs = forall a. Variables a => a -> VarSet
vars [Atom r]
cs
optimize :: (RealFrac r) => OptDir -> LA.Expr r -> [LA.Atom r] -> OptResult r
optimize :: forall r. RealFrac r => OptDir -> Expr r -> [Atom r] -> OptResult r
optimize OptDir
optdir Expr r
obj [Atom r]
cs =
forall a b c. (a -> b -> c) -> b -> a -> c
flip forall s a. State s a -> s -> a
evalState (forall r. VarSet -> Solver r
emptySolver VarSet
vs) forall a b. (a -> b) -> a -> b
$ do
forall r. RealFrac r => [Atom r] -> LP r ()
tableau [Atom r]
cs
OptResult
ret <- forall r.
(Fractional r, Real r) =>
OptDir -> Expr r -> LP r OptResult
LPSolver.twoPhaseSimplex OptDir
optdir Expr r
obj
case OptResult
ret of
OptResult
LPSolver.Unsat -> forall (m :: * -> *) a. Monad m => a -> m a
return forall r. OptResult r
OptUnsat
OptResult
LPSolver.Unbounded -> forall (m :: * -> *) a. Monad m => a -> m a
return forall r. OptResult r
Unbounded
OptResult
LPSolver.Optimum -> do
Model r
m <- forall r. Fractional r => VarSet -> LP r (Model r)
getModel VarSet
vs
Tableau r
tbl <- forall r. LP r (Tableau r)
getTableau
forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall r. r -> Model r -> OptResult r
Optimum (forall r. Tableau r -> r
Simplex.currentObjValue Tableau r
tbl) Model r
m
where
vs :: VarSet
vs = forall a. Variables a => a -> VarSet
vars [Atom r]
cs VarSet -> VarSet -> VarSet
`IS.union` forall a. Variables a => a -> VarSet
vars Expr r
obj
example_3_2 :: (LA.Expr Rational, [LA.Atom Rational])
example_3_2 :: (Expr Rational, [Atom Rational])
example_3_2 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
x3 :: Expr Rational
x3 = forall r. Num r => Int -> Expr r
LA.var Int
3
obj :: Expr Rational
obj = Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3
cond :: [Atom Rational]
cond = [ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
, Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
5
, Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_3_2 :: Bool
test_3_2 :: Bool
test_3_2 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_3_2 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum (Rational
27forall a. Fractional a => a -> a -> a
/Rational
5) (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
1forall a. Fractional a => a -> a -> a
/Rational
5),(Int
2,Rational
0),(Int
3,Rational
8forall a. Fractional a => a -> a -> a
/Rational
5)])
example_3_5 :: (LA.Expr Rational, [LA.Atom Rational])
example_3_5 :: (Expr Rational, [Atom Rational])
example_3_5 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
x3 :: Expr Rational
x3 = forall r. Num r => Int -> Expr r
LA.var Int
3
x4 :: Expr Rational
x4 = forall r. Num r => Int -> Expr r
LA.var Int
4
x5 :: Expr Rational
x5 = forall r. Num r => Int -> Expr r
LA.var Int
5
obj :: Expr Rational
obj = (-Rational
2)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
7forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
5forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5
cond :: [Atom Rational]
cond = [ (-Rational
1)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
7
, (-Rational
1)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x5 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
, (-Rational
1)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x5 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x5 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_3_5 :: Bool
test_3_5 :: Bool
test_3_5 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
minimize (Expr Rational, [Atom Rational])
example_3_5 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum Rational
19 (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,-Rational
1),(Int
2,Rational
0),(Int
3,Rational
1),(Int
4,Rational
0),(Int
5,Rational
2)])
example_4_1 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_1 :: (Expr Rational, [Atom Rational])
example_4_1 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
obj :: Expr Rational
obj = Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
cond :: [Atom Rational]
cond = [ (-Rational
1)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
, Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
1
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_1 :: Bool
test_4_1 :: Bool
test_4_1 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_1 forall a. Eq a => a -> a -> Bool
==
forall r. OptResult r
OptUnsat
example_4_2 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_2 :: (Expr Rational, [Atom Rational])
example_4_2 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
obj :: Expr Rational
obj = Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
cond :: [Atom Rational]
cond = [ (-Rational
1)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
10
, Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
40
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_2 :: Bool
test_4_2 :: Bool
test_4_2 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_2 forall a. Eq a => a -> a -> Bool
==
forall r. OptResult r
Unbounded
example_4_3 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_3 :: (Expr Rational, [Atom Rational])
example_4_3 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
obj :: Expr Rational
obj = Rational
6forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2
cond :: [Atom Rational]
cond = [ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_3 :: Bool
test_4_3 :: Bool
test_4_3 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_3 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum Rational
12 (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
4),(Int
2,Rational
6)])
example_4_5 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_5 :: (Expr Rational, [Atom Rational])
example_4_5 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
obj :: Expr Rational
obj = Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
cond :: [Atom Rational]
cond = [ Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
12
, Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
8
, Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
8
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_5 :: Bool
test_4_5 :: Bool
test_4_5 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_5 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum Rational
5 (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
3forall a. Fractional a => a -> a -> a
/Rational
2),(Int
2,Rational
2)])
example_4_6 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_6 :: (Expr Rational, [Atom Rational])
example_4_6 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
x3 :: Expr Rational
x3 = forall r. Num r => Int -> Expr r
LA.var Int
3
x4 :: Expr Rational
x4 = forall r. Num r => Int -> Expr r
LA.var Int
4
obj :: Expr Rational
obj = Rational
20forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
2)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
6forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
3forall a. Fractional a => a -> a -> a
/Rational
4)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4
cond :: [Atom Rational]
cond = [ Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
, Rational
8forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
9forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
4)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
16
, Rational
12forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
2)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
2)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
24
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
1
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_6 :: Bool
test_4_6 :: Bool
test_4_6 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_6 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum (Rational
165forall a. Fractional a => a -> a -> a
/Rational
4) (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
2),(Int
2,Rational
1),(Int
3,Rational
0),(Int
4,Rational
1)])
example_4_7 :: (LA.Expr Rational, [LA.Atom Rational])
example_4_7 :: (Expr Rational, [Atom Rational])
example_4_7 = (Expr Rational
obj, [Atom Rational]
cond)
where
x1 :: Expr Rational
x1 = forall r. Num r => Int -> Expr r
LA.var Int
1
x2 :: Expr Rational
x2 = forall r. Num r => Int -> Expr r
LA.var Int
2
x3 :: Expr Rational
x3 = forall r. Num r => Int -> Expr r
LA.var Int
3
x4 :: Expr Rational
x4 = forall r. Num r => Int -> Expr r
LA.var Int
4
obj :: Expr Rational
obj = Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
1.5forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
5forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4
cond :: [Atom Rational]
cond = [ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
, Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
5forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.<=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
, Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
6forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
8forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
4forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_4_7 :: Bool
test_4_7 :: Bool
test_4_7 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_7 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum (Rational
48forall a. Fractional a => a -> a -> a
/Rational
11) (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
0),(Int
2,Rational
0),(Int
3,Rational
81),(Int
4,Rational
41)])
kuhn_7_3 :: (LA.Expr Rational, [LA.Atom Rational])
kuhn_7_3 :: (Expr Rational, [Atom Rational])
kuhn_7_3 = (Expr Rational
obj, [Atom Rational]
cond)
where
[Expr Rational
x1,Expr Rational
x2,Expr Rational
x3,Expr Rational
x4,Expr Rational
x5,Expr Rational
x6,Expr Rational
x7] = forall a b. (a -> b) -> [a] -> [b]
map forall r. Num r => Int -> Expr r
LA.var [Int
1..Int
7]
obj :: Expr Rational
obj = (-Rational
2)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ (-Rational
3)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x6 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
12forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7
cond :: [Atom Rational]
cond = [ Expr Rational
x1 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
9forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x6 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
9forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
3)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x5 forall v. AdditiveGroup v => v -> v -> v
^-^ (Rational
1forall a. Fractional a => a -> a -> a
/Rational
3)forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x6 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
2forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
3forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x6 forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
12forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 forall e r. IsEqRel e r => e -> e -> r
.==. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
, Expr Rational
x1 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x2 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x3 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x4 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x5 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x6 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
, Expr Rational
x7 forall e r. IsOrdRel e r => e -> e -> r
.>=. forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
]
test_kuhn_7_3 :: Bool
test_kuhn_7_3 :: Bool
test_kuhn_7_3 =
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
minimize (Expr Rational, [Atom Rational])
kuhn_7_3 forall a. Eq a => a -> a -> Bool
==
forall r. r -> Model r -> OptResult r
Optimum (-Rational
2) (forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
2),(Int
2,Rational
0),(Int
3,Rational
0),(Int
4,Rational
2),(Int
5,Rational
0),(Int
6,Rational
2),(Int
7,Rational
0)])
_testAll :: Bool
_testAll :: Bool
_testAll = forall (t :: * -> *). Foldable t => t Bool -> Bool
and
[ Bool
test_3_2
, Bool
test_3_5
, Bool
test_4_1
, Bool
test_4_2
, Bool
test_4_3
, Bool
test_4_5
, Bool
test_4_6
, Bool
test_4_7
, Bool
test_kuhn_7_3
]