{"action":"closed","issue":{"url":"https://api.github.com/repos/amosr/limp-cbc/issues/5","repository_url":"https://api.github.com/repos/amosr/limp-cbc","labels_url":"https://api.github.com/repos/amosr/limp-cbc/issues/5/labels{/name}","comments_url":"https://api.github.com/repos/amosr/limp-cbc/issues/5/comments","events_url":"https://api.github.com/repos/amosr/limp-cbc/issues/5/events","html_url":"https://github.com/amosr/limp-cbc/issues/5","id":294801006,"number":5,"title":"'solve' occasionally and non-deterministically gives wrong solution","user":{"login":"feuerbach","id":24844,"avatar_url":"https://avatars3.githubusercontent.com/u/24844?v=4","gravatar_id":"","url":"https://api.github.com/users/feuerbach","html_url":"https://github.com/feuerbach","followers_url":"https://api.github.com/users/feuerbach/followers","following_url":"https://api.github.com/users/feuerbach/following{/other_user}","gists_url":"https://api.github.com/users/feuerbach/gists{/gist_id}","starred_url":"https://api.github.com/users/feuerbach/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/feuerbach/subscriptions","organizations_url":"https://api.github.com/users/feuerbach/orgs","repos_url":"https://api.github.com/users/feuerbach/repos","events_url":"https://api.github.com/users/feuerbach/events{/privacy}","received_events_url":"https://api.github.com/users/feuerbach/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2018-02-06T15:28:46Z","updated_at":"2018-02-09T00:02:01Z","closed_at":"2018-02-09T00:02:01Z","author_association":"NONE","body":"I wrote a QuickCheck test to demonstrate this:\r\n\r\n\r\n``` haskell\r\n{-# LANGUAGE FlexibleInstances, ScopedTypeVariables, TupleSections #-}\r\n{-# OPTIONS_GHC -fno-warn-orphans #-}\r\nimport Test.Tasty\r\nimport Test.Tasty.QuickCheck\r\nimport Test.QuickCheck.Property\r\nimport Data.IORef\r\nimport Data.Void\r\nimport Data.Either\r\nimport Numeric.Limp.Solvers.Cbc (solve, Error(..))\r\nimport Numeric.Limp.Program\r\nimport Numeric.Limp.Rep.IntDouble\r\n\r\nmain :: IO ()\r\nmain = defaultMain limpTest\r\n\r\ninstance Arbitrary (Program Int Void IntDouble) where\r\n  arbitrary = do\r\n    let\r\n      vars :: [Int]\r\n      vars = [1 .. 10]\r\n      bounds = map binary vars\r\n      obj = LZ ((,1) <$> vars) 0\r\n    constraints <- fmap mconcat . vectorOf 5 $ do\r\n      vars1 <- sublistOf vars\r\n      return $ LZ ((,1) <$> vars1) 0 :== c1\r\n    return $ minimise obj constraints bounds\r\n  \r\ninstance Eq Error where\r\n  Infeasible == Infeasible = True\r\n\r\nlimpTest :: TestTree\r\nlimpTest = testProperty \"limp\" $ \\(prog1 :: Program Int Void IntDouble) ->\r\n  ioProperty $ do\r\n    -- prevent CSE\r\n    v <- newIORef prog1\r\n    prog2 <- readIORef v\r\n    let sol1 = solve prog1\r\n        sol2 = solve prog2\r\n        score1 = eval <$> sol1 <*> pure (_objective prog1)\r\n        score2 = eval <$> sol2 <*> pure (_objective prog2)\r\n    return $\r\n      classify (isRight sol1) \"feasible\" $\r\n      if score1 == score2\r\n        then property True\r\n        else property $\r\n          MkResult (Just False) True\r\n            (\"\\n\" ++ show (score1,sol1) ++\r\n             \"\\n\" ++ show (score2,sol2))\r\n            Nothing False Nothing mempty mempty mempty [show prog1]\r\n```\r\n\r\nThe above program tests that `solve` gives the same value of the objective function for the same problem when evaluated two times in a row.\r\n\r\nIf you run this with, say, `./test --quickcheck-tests 20000`, you will sooner or later run into a counterexample, such as\r\n\r\n```\r\nlimp: FAIL (3.50s)\r\n  *** Failed! (after 4262 tests): \r\n  \r\n  (Right 1.0,Right (Assignment (fromList [(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,1),(10,0)]) (fromList [])))\r\n  (Right 2.0,Right (Assignment (fromList [(1,1),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,1),(10,0)]) (fromList [])))\r\n  Program {_direction = Minimise, _objective = LR [(Left 1,1.0),(Left 2,1.0),(Left 3,1.0),(Left 4,1.0),(Left 5,1.0),(Left 6,1.0),(Left 7,1.0),(Left 8,1.0),(Left 9,1.0),(Left 10,1.0)] 0.0, _constraints = LZ [(1,1),(10,1)] 0 :== LZ [] 1 :&& (LZ [(4,1),(6,1),(7,1),(9,1),(10,1)] 0 :== LZ [] 1 :&& (LZ [(1,1),(3,1),(4,1),(6,1),(7,1)] 0 :== LZ [] 1 :&& (LZ [(4,1),(5,1),(6,1),(7,1),(9,1),(10,1)] 0 :== LZ [] 1 :&& (LZ [(3,1),(5,1),(9,1),(10,1)] 0 :== LZ [] 1 :&& CTrue)))), _bounds = [BoundZ (Just 0,1,Just 1),BoundZ (Just 0,2,Just 1),BoundZ (Just 0,3,Just 1),BoundZ (Just 0,4,Just 1),BoundZ (Just 0,5,Just 1),BoundZ (Just 0,6,Just 1),BoundZ (Just 0,7,Just 1),BoundZ (Just 0,8,Just 1),BoundZ (Just 0,9,Just 1),BoundZ (Just 0,10,Just 1)]}\r\n  Use --quickcheck-replay=553233 to reproduce.\r\n\r\n1 out of 1 tests failed (3.50s)\r\n```\r\n\r\n(Don't pay attention to `--quickcheck-replay`; this is non-deterministic.)\r\n\r\nI doubt this is a problem in the Haskell package itself, but I thought I'd let you know.\r\n\r\nIf this is a bug in cbc, it might have been solved already ­— worth testing when #4 is fixed."}}
{"actor":{"display_login":"amosr"}}