Code Monkey home page Code Monkey logo

limp-cbc's People

Contributors

amosr avatar bens avatar jacobstanley avatar langston-barrett avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar avatar avatar

Forkers

jacobstanley rednum bens

limp-cbc's Issues

Executable fails to build with --enable-executable-dynamic

Building a simple executable against limp-cbc with cabal v2-build --enable-executable-dynamic fails.

{-# LANGUAGE DataKinds #-}
module Main where

import qualified Numeric.Limp.Program as I
import qualified Numeric.Limp.Solvers.Cbc as I (solve)
import qualified Numeric.Limp.Rep as I

simpleTest :: IO ()
simpleTest = do
  let obj :: I.Linear String String I.IntDouble 'I.KR
      obj = I.r "y" (I.R 4.5)
  let constraints = I.r1 "y" I.:<= I.conZ (I.Z 10)
  let bounds = [ I.lowerUpperR (I.R 0) "y" (I.R 5) ]
  let prog = I.maximise obj constraints bounds
  case I.solve prog of
    Left err -> error $ show err
    Right ass -> putStrLn $ show ass

main :: IO ()
main = simpleTest
executable exetest
  main-is: Main.hs
  build-depends: base, limp, limp-cbc
cabal v2-build --enable-executable-dynamic exe:exetest
Build profile: -w ghc-8.6.5 -O1
In order, the following will be built (use -v for more details):
 - limp-cbc-0.3.2.2 (exe:exetest) (first run)
Preprocessing executable 'exetest' for limp-cbc-0.3.2.2..
Building executable 'exetest' for limp-cbc-0.3.2.2..
[1 of 1] Compiling Main             ( Main.hs, /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/x/exetest/build/exetest/exetest-tmp/Main.dyn_o )
Linking /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/x/exetest/build/exetest/exetest ...
/nix/store/q354712mnkw3ky8b5crj7ir7dyv29ylj-binutils-2.31.1/bin/ld: /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/build/libHSlimp-cbc-0.3.2.2-inplace-ghc8.6.5.so: undefined reference to `CbcClpUnitTest(CbcModel const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, int, double const*)'
/nix/store/q354712mnkw3ky8b5crj7ir7dyv29ylj-binutils-2.31.1/bin/ld: /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/build/libHSlimp-cbc-0.3.2.2-inplace-ghc8.6.5.so: undefined reference to `CbcOrClpParam::setDoubleParameterWithMessage(CbcModel&, double, int&)'
/nix/store/q354712mnkw3ky8b5crj7ir7dyv29ylj-binutils-2.31.1/bin/ld: /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/build/libHSlimp-cbc-0.3.2.2-inplace-ghc8.6.5.so: undefined reference to `ClpSimplex::loadNonLinear(void*, int&, ClpConstraint**&)'
/nix/store/q354712mnkw3ky8b5crj7ir7dyv29ylj-binutils-2.31.1/bin/ld: /home/siddharthist/code/limp-cbc/dist-newstyle/build/x86_64-linux/ghc-8.6.5/limp-cbc-0.3.2.2/build/libHSlimp-cbc-0.3.2.2-inplace-ghc8.6.5.so: undefined reference to `CbcOrClpParam::setIntParameterWithMessage(CbcModel&, int, int&)'
collect2: error: ld returned 1 exit status
`cc' failed in phase `Linker'. (Exit code: 1)

CBC calling code is slower than command line

The command line version of CBC performs all sorts of cuts and simplifications, but we just call branchAndBound which performs naive solving. Combined with #7, we're probably better off writing the program to disk and shelling out to the external cbc program.

Variables with no specified bounds have different semantics to different solvers

If you have a linear variable and do not explicitly specify bounds, the semantics in this package is a range from (-coinDoubleMax, +coinDoubleMax). If you pretty-print the same program and pass it to CBC on the command line, it is interpreted as the range (0, +coinDoubleMax). I'm tempted to require explicit bounds in all cases.

'solve' occasionally and non-deterministically gives wrong solution

I wrote a QuickCheck test to demonstrate this:

{-# LANGUAGE FlexibleInstances, ScopedTypeVariables, TupleSections #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}
import Test.Tasty
import Test.Tasty.QuickCheck
import Test.QuickCheck.Property
import Data.IORef
import Data.Void
import Data.Either
import Numeric.Limp.Solvers.Cbc (solve, Error(..))
import Numeric.Limp.Program
import Numeric.Limp.Rep.IntDouble

main :: IO ()
main = defaultMain limpTest

instance Arbitrary (Program Int Void IntDouble) where
  arbitrary = do
    let
      vars :: [Int]
      vars = [1 .. 10]
      bounds = map binary vars
      obj = LZ ((,1) <$> vars) 0
    constraints <- fmap mconcat . vectorOf 5 $ do
      vars1 <- sublistOf vars
      return $ LZ ((,1) <$> vars1) 0 :== c1
    return $ minimise obj constraints bounds
  
instance Eq Error where
  Infeasible == Infeasible = True

limpTest :: TestTree
limpTest = testProperty "limp" $ \(prog1 :: Program Int Void IntDouble) ->
  ioProperty $ do
    -- prevent CSE
    v <- newIORef prog1
    prog2 <- readIORef v
    let sol1 = solve prog1
        sol2 = solve prog2
        score1 = eval <$> sol1 <*> pure (_objective prog1)
        score2 = eval <$> sol2 <*> pure (_objective prog2)
    return $
      classify (isRight sol1) "feasible" $
      if score1 == score2
        then property True
        else property $
          MkResult (Just False) True
            ("\n" ++ show (score1,sol1) ++
             "\n" ++ show (score2,sol2))
            Nothing False Nothing mempty mempty mempty [show prog1]

The above program tests that solve gives the same value of the objective function for the same problem when evaluated two times in a row.

If you run this with, say, ./test --quickcheck-tests 20000, you will sooner or later run into a counterexample, such as

limp: FAIL (3.50s)
  *** Failed! (after 4262 tests): 
  
  (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 [])))
  (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 [])))
  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)]}
  Use --quickcheck-replay=553233 to reproduce.

1 out of 1 tests failed (3.50s)

(Don't pay attention to --quickcheck-replay; this is non-deterministic.)

I doubt this is a problem in the Haskell package itself, but I thought I'd let you know.

If this is a bug in cbc, it might have been solved already ­— worth testing when #4 is fixed.

Crashes with the system cbc

Hi, great project, I've found it very useful!

I was wondering if I could get some performance improvements and multithreading support by using cbc shipped with Fedora 27, but it crashes with

malloc.c:2399: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.

(Whereas it seems to work fine using the embedded version.)

Valgrind prints several errors such as

==19084== Invalid write of size 8
==19084==    at 0x5A6CEA4: CbcModel::CbcModel(OsiSolverInterface const&) (in /usr/lib64/libCbc.so.3.9.8)
==19084==    by 0x5B6811: ??? (in ...)
==19084==    by 0x5B43CC: ??? (in ...)
==19084==  Address 0x882e054 is 1,236 bytes inside a block of size 1,240 alloc'd
==19084==    at 0x4C301CA: operator new(unsigned long) (vg_replace_malloc.c:334)
==19084==    by 0x5B67FF: ??? (in ...)
==19084==    by 0x5B43CC: ??? (in ...)

and then

valgrind: m_mallocfree.c:307 (get_bszB_as_is): Assertion 'bszB_lo == bszB_hi' failed.          
valgrind: Heap block lo/hi size mismatch: lo = 1312, hi = 0.                                   
This is probably caused by your program erroneously writing past the                           
end of a heap block and corrupting heap metadata.  If you fix any                              
invalid writes reported by Memcheck, this assertion failure will                               
probably go away.  Please try that before reporting this as a bug.

My library versions are

coin-or-Osi-devel-0.107.8-5.fc27.x86_64
coin-or-Osi-0.107.8-5.fc27.x86_64
coin-or-Clp-devel-1.16.10-5.fc27.x86_64
coin-or-Clp-1.16.10-5.fc27.x86_64
coin-or-Cbc-2.9.8-6.fc27.x86_64
coin-or-CoinMP-1.8.3-4.fc27.x86_64
coin-or-Sample-1.2.10-7.fc27.noarch
coin-or-CoinMP-devel-1.8.3-4.fc27.x86_64
coin-or-CoinUtils-devel-2.10.13-5.fc27.x86_64
coin-or-CoinUtils-2.10.13-5.fc27.x86_64
coin-or-Cgl-devel-0.59.9-5.fc27.x86_64
coin-or-Cgl-0.59.9-5.fc27.x86_64
coin-or-Cbc-devel-2.9.8-6.fc27.x86_64

and limp-cbc-0.3.2.0.

I don't know whether it's cbc itself or the haskell bindings to blame, but it's very easily reproducible on every single run, and I doubt Fedora would ship such a broken package.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.