{-# 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
[OptResult r] -> ShowS
OptResult r -> String
(Int -> OptResult r -> ShowS)
-> (OptResult r -> String)
-> ([OptResult r] -> ShowS)
-> Show (OptResult r)
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
$cshowsPrec :: forall r. Show r => Int -> OptResult r -> ShowS
showsPrec :: Int -> OptResult r -> ShowS
$cshow :: forall r. Show r => OptResult r -> String
show :: OptResult r -> String
$cshowList :: forall r. Show r => [OptResult r] -> ShowS
showList :: [OptResult r] -> ShowS
Show, OptResult r -> OptResult r -> Bool
(OptResult r -> OptResult r -> Bool)
-> (OptResult r -> OptResult r -> Bool) -> Eq (OptResult r)
forall r. Eq r => OptResult r -> OptResult r -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$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
/= :: OptResult r -> OptResult r -> Bool
Eq, Eq (OptResult r)
Eq (OptResult r) =>
(OptResult r -> OptResult r -> Ordering)
-> (OptResult r -> OptResult r -> Bool)
-> (OptResult r -> OptResult r -> Bool)
-> (OptResult r -> OptResult r -> Bool)
-> (OptResult r -> OptResult r -> Bool)
-> (OptResult r -> OptResult r -> OptResult r)
-> (OptResult r -> OptResult r -> OptResult r)
-> Ord (OptResult r)
OptResult r -> OptResult r -> Bool
OptResult r -> OptResult r -> Ordering
OptResult r -> OptResult r -> OptResult r
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
$ccompare :: forall r. Ord r => OptResult r -> OptResult r -> Ordering
compare :: OptResult r -> OptResult r -> Ordering
$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
>= :: OptResult r -> OptResult r -> Bool
$cmax :: forall r. Ord r => OptResult r -> OptResult r -> OptResult r
max :: OptResult r -> OptResult r -> OptResult r
$cmin :: forall r. Ord r => OptResult r -> OptResult r -> OptResult r
min :: OptResult r -> OptResult r -> OptResult r
Ord)

maximize :: (RealFrac r) => LA.Expr r -> [LA.Atom r] -> OptResult r
maximize :: forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize = OptDir -> Expr r -> [Atom r] -> OptResult r
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 = OptDir -> Expr r -> [Atom r] -> OptResult r
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 =
  (State (Solver r) (Maybe (Model r)) -> Solver r -> Maybe (Model r))
-> Solver r
-> State (Solver r) (Maybe (Model r))
-> Maybe (Model r)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State (Solver r) (Maybe (Model r)) -> Solver r -> Maybe (Model r)
forall s a. State s a -> s -> a
evalState (VarSet -> Solver r
forall r. VarSet -> Solver r
emptySolver VarSet
vs) (State (Solver r) (Maybe (Model r)) -> Maybe (Model r))
-> State (Solver r) (Maybe (Model r)) -> Maybe (Model r)
forall a b. (a -> b) -> a -> b
$ do
    [Atom r] -> LP r ()
forall r. RealFrac r => [Atom r] -> LP r ()
tableau [Atom r]
cs
    Bool
ret <- LP r Bool
forall r. (Fractional r, Real r) => LP r Bool
phaseI
    if Bool -> Bool
not Bool
ret
      then Maybe (Model r) -> State (Solver r) (Maybe (Model r))
forall a. a -> StateT (Solver r) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (Model r)
forall a. Maybe a
Nothing
      else do
        Model r
m <- VarSet -> LP r (Model r)
forall r. Fractional r => VarSet -> LP r (Model r)
getModel VarSet
vs
        Maybe (Model r) -> State (Solver r) (Maybe (Model r))
forall a. a -> StateT (Solver r) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (Model r -> Maybe (Model r)
forall a. a -> Maybe a
Just Model r
m)
  where
    vs :: VarSet
vs = [Atom r] -> VarSet
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 =
  (State (Solver r) (OptResult r) -> Solver r -> OptResult r)
-> Solver r -> State (Solver r) (OptResult r) -> OptResult r
forall a b c. (a -> b -> c) -> b -> a -> c
flip State (Solver r) (OptResult r) -> Solver r -> OptResult r
forall s a. State s a -> s -> a
evalState (VarSet -> Solver r
forall r. VarSet -> Solver r
emptySolver VarSet
vs) (State (Solver r) (OptResult r) -> OptResult r)
-> State (Solver r) (OptResult r) -> OptResult r
forall a b. (a -> b) -> a -> b
$ do
    [Atom r] -> LP r ()
forall r. RealFrac r => [Atom r] -> LP r ()
tableau [Atom r]
cs
    OptResult
ret <- OptDir -> Expr r -> LP r OptResult
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 -> OptResult r -> State (Solver r) (OptResult r)
forall a. a -> StateT (Solver r) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return OptResult r
forall r. OptResult r
OptUnsat
      OptResult
LPSolver.Unbounded -> OptResult r -> State (Solver r) (OptResult r)
forall a. a -> StateT (Solver r) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return OptResult r
forall r. OptResult r
Unbounded
      OptResult
LPSolver.Optimum -> do
        Model r
m <- VarSet -> LP r (Model r)
forall r. Fractional r => VarSet -> LP r (Model r)
getModel VarSet
vs
        Tableau r
tbl <- LP r (Tableau r)
forall r. LP r (Tableau r)
getTableau
        OptResult r -> State (Solver r) (OptResult r)
forall a. a -> StateT (Solver r) Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (OptResult r -> State (Solver r) (OptResult r))
-> OptResult r -> State (Solver r) (OptResult r)
forall a b. (a -> b) -> a -> b
$ r -> Model r -> OptResult r
forall r. r -> Model r -> OptResult r
Optimum (Tableau r -> r
forall r. Tableau r -> r
Simplex.currentObjValue Tableau r
tbl) Model r
m
  where
    vs :: VarSet
vs = [Atom r] -> VarSet
forall a. Variables a => a -> VarSet
vars [Atom r]
cs VarSet -> VarSet -> VarSet
`IS.union` Expr r -> VarSet
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    x3 :: Expr Rational
x3 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
3
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3
    cond :: [Atom Rational]
cond = [ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
           ,    Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
5
           , Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_3_2 :: Bool
test_3_2 :: Bool
test_3_2 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_3_2 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum (Rational
27Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
5) ([(Int, Rational)] -> Model Rational
forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
5),(Int
2,Rational
0),(Int
3,Rational
8Rational -> Rational -> Rational
forall 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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    x3 :: Expr Rational
x3 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
3
    x4 :: Expr Rational
x4 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
4
    x5 :: Expr Rational
x5 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
5
    obj :: Expr Rational
obj = (-Rational
2)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
7Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
5Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5
    cond :: [Atom Rational]
cond = [ (-Rational
1)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
7
           , (-Rational
1)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x5 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
           , (-Rational
1)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x5 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x5 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_3_5 :: Bool
test_3_5 :: Bool
test_3_5 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
minimize (Expr Rational, [Atom Rational])
example_3_5 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum Rational
19 ([(Int, Rational)] -> Model Rational
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
    cond :: [Atom Rational]
cond = [ (-Rational
1)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
           ,       Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
1
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_1 :: Bool
test_4_1 :: Bool
test_4_1 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_1 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  OptResult Rational
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
    cond :: [Atom Rational]
cond = [ (-Rational
1)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
10
           ,    Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
40
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_2 :: Bool
test_4_2 :: Bool
test_4_2 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_2 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  OptResult Rational
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
6Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2
    cond :: [Atom Rational]
cond = [ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_3 :: Bool
test_4_3 :: Bool
test_4_3 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_3 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum Rational
12 ([(Int, Rational)] -> Model Rational
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x2
    cond :: [Atom Rational]
cond = [ Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
12
           , Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
8
           , Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^    Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
8
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_5 :: Bool
test_4_5 :: Bool
test_4_5 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_5 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum Rational
5 ([(Int, Rational)] -> Model Rational
forall a. [(Int, a)] -> IntMap a
IM.fromList [(Int
1,Rational
3Rational -> Rational -> Rational
forall 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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    x3 :: Expr Rational
x3 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
3
    x4 :: Expr Rational
x4 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
4
    obj :: Expr Rational
obj = Rational
Scalar (Expr Rational)
20Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
2)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
Scalar (Expr Rational)
6Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
3Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
4)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4
    cond :: [Atom Rational]
cond = [     Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
           ,  Rational
Scalar (Expr Rational)
8Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^        Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
9Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
4)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
16
           , Rational
Scalar (Expr Rational)
12Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
2)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
2)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
24
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
1
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_6 :: Bool
test_4_6 :: Bool
test_4_6 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_6 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum (Rational
165Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
4) ([(Int, Rational)] -> Model Rational
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 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
1
    x2 :: Expr Rational
x2 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
2
    x3 :: Expr Rational
x3 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
3
    x4 :: Expr Rational
x4 = Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var Int
4
    obj :: Expr Rational
obj = Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
1.5Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
5Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4
    cond :: [Atom Rational]
cond = [ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
6
           , Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
5Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.<=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
4
           , Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
6Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
8Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ,    Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
4Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           ]

test_4_7 :: Bool
test_4_7 :: Bool
test_4_7 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
maximize (Expr Rational, [Atom Rational])
example_4_7 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum (Rational
48Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
11) ([(Int, Rational)] -> Model Rational
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] = (Int -> Expr Rational) -> [Int] -> [Expr Rational]
forall a b. (a -> b) -> [a] -> [b]
map Int -> Expr Rational
forall r. Num r => Int -> Expr r
LA.var [Int
1..Int
7]
    obj :: Expr Rational
obj = (-Rational
2)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (-Rational
3)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Expr Rational
x6 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
12Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7
    cond :: [Atom Rational]
cond = [ Expr Rational
x1 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^     Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ Rational
Scalar (Expr Rational)
9Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^        Expr Rational
x6 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^   Rational
Scalar (Expr Rational)
9Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
3)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^    Expr Rational
x5 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^ (Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
3)Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x6 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^   Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^     Rational
Scalar (Expr Rational)
2Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x4 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^+^ Rational
Scalar (Expr Rational)
3Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x5 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^        Expr Rational
x6 Expr Rational -> Expr Rational -> Expr Rational
forall v. AdditiveGroup v => v -> v -> v
^-^  Rational
Scalar (Expr Rational)
12Scalar (Expr Rational) -> Expr Rational -> Expr Rational
forall v. VectorSpace v => Scalar v -> v -> v
*^Expr Rational
x7 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsEqRel e r => e -> e -> r
.==. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
2
           , Expr Rational
x1 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x2 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x3 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x4 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x5 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x6 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
forall r. (Num r, Eq r) => r -> Expr r
LA.constant Rational
0
           , Expr Rational
x7 Expr Rational -> Expr Rational -> Atom Rational
forall e r. IsOrdRel e r => e -> e -> r
.>=. Rational -> Expr Rational
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 =
  (Expr Rational -> [Atom Rational] -> OptResult Rational)
-> (Expr Rational, [Atom Rational]) -> OptResult Rational
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Expr Rational -> [Atom Rational] -> OptResult Rational
forall r. RealFrac r => Expr r -> [Atom r] -> OptResult r
minimize (Expr Rational, [Atom Rational])
kuhn_7_3 OptResult Rational -> OptResult Rational -> Bool
forall a. Eq a => a -> a -> Bool
==
  Rational -> Model Rational -> OptResult Rational
forall r. r -> Model r -> OptResult r
Optimum (-Rational
2) ([(Int, Rational)] -> Model Rational
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 = [Bool] -> Bool
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
  ]

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