{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_HADDOCK show-extensions #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  ToySolver.Arith.Simplex.Textbook.LPSolver.Simple
-- Copyright   :  (c) Masahiro Sakai 2011
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  non-portable
--
-- High-Level API for LPSolver.hs
--
-----------------------------------------------------------------------------

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 (..))

-- ---------------------------------------------------------------------------

-- | results of optimization
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

-- ---------------------------------------------------------------------------
-- Test cases

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制約の例
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
  ]

-- ---------------------------------------------------------------------------