add optional SCIP integer constraint solver #10879

malb · 2011-03-05T18:09:34Z

"SCIP is currently one of the fastest non-commercial mixed integer programming (MIP) solvers. It is also a framework for Constraint Integer Programming and branch-cut-and-price. It allows total control of the solution process and the access of detailed information down to the guts of the solver." -- http://scip.zib.de/

Features interesting to Sage:

SCIP is pretty fast for Mixed Integer Programming
SCIP is a Constraint Integer Programming solver and allows non-linear constraints
SCIP's source code is available
SoPlex (the LP solver which is part of scipoptsuite) has an exact mode which is said to be working well
A beta version of SCIP can do exact MIP: http://scip.zib.de/#exact using qsopt_ex (see also Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver #18766)

However, the SCIP license prevents us from redistributing the SCIP source code:
http://scip.zib.de/#license

To build a SCIP for Sage do:

pull from this ticket
download the SCIP Optimisation Suite from http://scip.zib.de/download.php?fname=scipoptsuite-3.2.1.tgz
put tarfile scipoptsuite-3.2.1.tgz in $SAGE_ROOT/upstream/
sage -f scipoptsuite

KNOWN ISSUES

Sage crashes when SCIP variables are printed with SIGSEGV on OSX. It works fine under Linux.
printing of quadratic constraints does not work yet.

Split out ticket with just the spkg: #21094.

Follow-up: #21003: Add SCIP backend using PySCIPOpt

CC: @haraldschilly @jasongrout @dimpase @videlec @fchapoton @jdemeyer @slel

Component: packages: optional

Author: Martin Albrecht

Branch/Commit: u/mkoeppe/ticket/10879 @ 1f514de

Issue created by migration from https://trac.sagemath.org/ticket/10879

The text was updated successfully, but these errors were encountered:

malb · 2011-03-05T18:22:51Z

comment:4

Doctest failures in detail

doc/en/thematic_tutorials/linear_programming.rst

**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 278:
    sage: p.solve()
Expected:
    3.1502766806530307
Got:
    13.334952068716467
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 288:
    sage: sum(weight[o] * taken[o] for o in L)
Expected:
    0.69649597966191712
Got:
    0.98283592969131794
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 297:
    sage: taken["flashlight"]
Expected:
    1.0
Got:
    17.0
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 366:
    sage: [e for e,b in matching.iteritems() if b == 1]
Expected:
    [(0, 1), (6, 9), (2, 7), (3, 4), (5, 8)]
Got:
    [(1, 6), (0, 4), (2, 3), (5, 8), (7, 9)]
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 436:
    sage: p.set_objective(sum(f[(s,u)] for u in g.neighbors_out(s)))
Exception raised:
    Traceback (most recent call last):
    ...
    AttributeError: 'int' object has no attribute 'dict'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 442:
    sage: p.solve()
Expected:
    2.0
Got:
    -0.0

sage/graphs/digraph.py

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/digraph.py", line 1539:
    sage: x == y
Expected:
    True
Got:
    False

sage/graphs/graph_coloring.py

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/graph_coloring.py", line 534:
    sage: grundy_coloring(g, 4)
Expected:
    3
Got:
    4
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/graph_coloring.py", line 540:
    sage: grundy_coloring(g, 5)
Expected:
    4
Got:
    10
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/graph_coloring.py", line 695:
    sage: b_coloring(g, 5)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_8[4]>", line 1, in <module>
        b_coloring(g, Integer(5))###line 695:
    sage: b_coloring(g, 5)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/graph_coloring.py", line 803, in b_coloring
        obj = Integer(obj)
      File "integer.pyx", line 606, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:6669)
    TypeError: Cannot convert non-integral float to integer

sage/graphs/graph_generators.py

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/graph_generators.py", line 2743:
    sage: G.is_hamiltonian()
Expected:
    True
Got:
    False
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/graph_generators.py", line 3276:
    sage: G.is_hamiltonian()
Expected:
    True
Got:
    False

sage/numerical/knapsack.py

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/knapsack.py", line 53:
    sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2)
Expected:
    [5.0, [(1, 2), (0.500000000000000, 3)]]
Got:
    [14.0, [(1, 2), (0.500000000000000, 3), (0.500000000000000, 3), (0.500000000000000, 3), (0.500000000000000, 3)]]
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/knapsack.py", line 596:
    sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2)
Expected:
    [5.0, [(1, 2), (0.500000000000000, 3)]]
Got:
    [14.0, [(1, 2), (0.500000000000000, 3), (0.500000000000000, 3), (0.500000000000000, 3), (0.500000000000000, 3)]]
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/knapsack.py", line 599:
    sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2, value_only=True)
Expected:
    5.0
Got:
    14.0
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/knapsack.py", line 608:
    sage: knapsack([1,1.5,0.5], max=2, value_only=True)
Expected:
    2.0
Got:
    5.0
**********************************************************************

sage/numerical/mip.pyx

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 64:
    sage: p.show()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[11]>", line 1, in <module>
        p.show()###line 64:
    sage: p.show()
      File "mip.pyx", line 404, in sage.numerical.mip.MixedIntegerLinearProgram.show (sage/numerical/mip.c:2201)
      File "generic_backend.pyx", line 720, in sage.numerical.backends.generic_backend.GenericBackend.col_name (sage/numerical/backends/generic_backend.c:4239)
    NotImplementedError
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 648:
    sage: p.solve()
Expected:
    0.0
Got:
    6.6666666666666767
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 751:
    sage: p.show()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_12[21]>", line 1, in <module>
        p.show()###line 751:
    sage: p.show()
      File "mip.pyx", line 404, in sage.numerical.mip.MixedIntegerLinearProgram.show (sage/numerical/mip.c:2201)
      File "generic_backend.pyx", line 720, in sage.numerical.backends.generic_backend.GenericBackend.col_name (sage/numerical/backends/generic_backend.c:4239)
    NotImplementedError
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 1216:
    sage: p.get_backend()
Expected:
    <sage.numerical.backends.glpk_backend.GLPKBackend object ...>
Got:
    SCIP Constraint Integer Program "scip" ( maximization, 0 variables, 0 constraints )
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 227:
    sage: print p
Expected:
    Mixed Integer Program ( maximization, 2 variables, 1 constraints )
Got:
    Mixed Integer Program "scip" ( maximization, 2 variables, 1 constraints )
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 365:
    sage: p.show()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_7[6]>", line 1, in <module>
        p.show()###line 365:
    sage: p.show()
      File "mip.pyx", line 404, in sage.numerical.mip.MixedIntegerLinearProgram.show (sage/numerical/mip.c:2201)
      File "generic_backend.pyx", line 720, in sage.numerical.backends.generic_backend.GenericBackend.col_name (sage/numerical/backends/generic_backend.c:4239)
    NotImplementedError
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 380:
    sage: p.show()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_7[11]>", line 1, in <module>
        p.show()###line 380:
    sage: p.show()
      File "mip.pyx", line 404, in sage.numerical.mip.MixedIntegerLinearProgram.show (sage/numerical/mip.c:2201)
      File "generic_backend.pyx", line 720, in sage.numerical.backends.generic_backend.GenericBackend.col_name (sage/numerical/backends/generic_backend.c:4239)
    NotImplementedError
**********************************************************************

sage/graphs/generic_graph.py

**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 2364:
    sage: max(o.out_degree()) == ceil((4*3)/(3+4))
Expected:
    True
Got:
    False
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 3938:
    sage: g.edge_cut(0,1, method="FF") == g.edge_cut(0,1,method="LP")
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_66[20]>", line 1, in <module>
        g.edge_cut(Integer(0),Integer(1), method="FF") == g.edge_cut(Integer(0),Integer(1),method="LP")###line 3938:
    sage: g.edge_cut(0,1, method="FF") == g.edge_cut(0,1,method="LP")
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4009, in edge_cut
        return p.solve(objective_only=True, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 622, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4813)
    MIPSolverException: 'Error -9 solving SCIP instance.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4073:
    sage: g.vertex_cut(1, 16, value_only=True)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_67[3]>", line 1, in <module>
        g.vertex_cut(Integer(1), Integer(16), value_only=True)###line 4073:
    sage: g.vertex_cut(1, 16, value_only=True)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4134, in vertex_cut
        return p.solve(objective_only=True, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 622, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4813)
    MIPSolverException: 'Error -9 solving SCIP instance.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4369:
    sage: vc1 = g.vertex_cover(algorithm="MILP")
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_69[5]>", line 1, in <module>
        vc1 = g.vertex_cover(algorithm="MILP")###line 4369:
    sage: vc1 = g.vertex_cover(algorithm="MILP")
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4400, in vertex_cover
        p.solve(log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 622, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4813)
    MIPSolverException: 'Error -9 solving SCIP instance.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4371:
    sage: len(vc1) == len(vc2)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_69[7]>", line 1, in <module>
        len(vc1) == len(vc2)###line 4371:
    sage: len(vc1) == len(vc2)
    NameError: name 'vc1' is not defined
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4616:
    sage: lp = g.longest_path()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[3]>", line 1, in <module>
        lp = g.longest_path()###line 4616:
    sage: lp = g.longest_path()
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4617:
    sage: lp.order() >= g.order() - 2
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[4]>", line 1, in <module>
        lp.order() >= g.order() - Integer(2)###line 4617:
    sage: lp.order() >= g.order() - 2
    NameError: name 'lp' is not defined
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4629:
    sage: for i in range(20):
          g = graphs.RandomGNP(Integer(15), RealNumber('0.3'))
          for u, v in g.edges(labels=False):
              g.set_edge_label(u, v, random())
          lp = g.longest_path()
          if (not lp.is_forest() or
              not max(lp.degree()) <= Integer(2) or
              not lp.is_connected()):
              print("Error!")
              break
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[7]>", line 5, in <module>
        lp = g.longest_path()
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4654:
    sage: lp1 = g1.longest_path()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[11]>", line 1, in <module>
        lp1 = g1.longest_path()###line 4654:
    sage: lp1 = g1.longest_path()
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4655:
    sage: lp2 = g2.longest_path()
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[12]>", line 1, in <module>
        lp2 = g2.longest_path()###line 4655:
    sage: lp2 = g2.longest_path()
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4725, in longest_path
        key=lambda x: x.order())
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4724, in <genexpr>
        for g in self.connected_components_subgraphs()),
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4656:
    sage: len(lp1) == len(lp2)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[13]>", line 1, in <module>
        len(lp1) == len(lp2)###line 4656:
    sage: len(lp1) == len(lp2)
    NameError: name 'lp1' is not defined
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4665:
    sage: lp1 = g1.longest_path(weighted=True)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[17]>", line 1, in <module>
        lp1 = g1.longest_path(weighted=True)###line 4665:
    sage: lp1 = g1.longest_path(weighted=True)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4666:
    sage: lp2 = g2.longest_path(weighted=True)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[18]>", line 1, in <module>
        lp2 = g2.longest_path(weighted=True)###line 4666:
    sage: lp2 = g2.longest_path(weighted=True)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4719, in longest_path
        for g in self.connected_components_subgraphs())
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4719, in <genexpr>
        for g in self.connected_components_subgraphs())
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4891, in longest_path
        p.solve(solver=solver, log=verbose)
      File "mip.pyx", line 1099, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:5792)
      File "scip.pyx", line 627, in sage.libs.scip.scip.SCIP.solve (sage/libs/scip/scip.c:4857)
    MIPSolverException: 'SCIP: No solution was found.'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 4667:
    sage: lp1[0] == lp2[0]
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[19]>", line 1, in <module>
        lp1[Integer(0)] == lp2[Integer(0)]###line 4667:
    sage: lp1[0] == lp2[0]
    NameError: name 'lp1' is not defined
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 5013:
    sage: tsp = g.traveling_salesman_problem(weighted = True)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_72[13]>", line 1, in <module>
        tsp = g.traveling_salesman_problem(weighted = True)###line 5013:
    sage: tsp = g.traveling_salesman_problem(weighted = True)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 5144, in traveling_salesman_problem
        raise ValueError("The given graph is not Hamiltonian")
    ValueError: The given graph is not Hamiltonian
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 5014:
    sage: sum( tsp.edge_labels() ) < 2*10
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_72[14]>", line 1, in <module>
        sum( tsp.edge_labels() ) < Integer(2)*Integer(10)###line 5014:
    sage: sum( tsp.edge_labels() ) < 2*10
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/misc/functional.py", line 661, in symbolic_sum
        return sum(expression, *args)
    TypeError: unsupported operand type(s) for +: 'int' and 'dict'
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 5023:
    sage: tsp = g.traveling_salesman_problem(weighted = True)
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_72[16]>", line 1, in <module>
        tsp = g.traveling_salesman_problem(weighted = True)###line 5023:
    sage: tsp = g.traveling_salesman_problem(weighted = True)
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 5144, in traveling_salesman_problem
        raise ValueError("The given graph is not Hamiltonian")
    ValueError: The given graph is not Hamiltonian
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/generic_graph.py", line 5024:
    sage: sum( tsp.edge_labels() ) == (1/2)*10
Exception raised:
    Traceback (most recent call last):
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/malb/Sage/current/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_72[17]>", line 1, in <module>
        sum( tsp.edge_labels() ) == (Integer(1)/Integer(2))*Integer(10)###line 5024:
    sage: sum( tsp.edge_labels() ) == (1/2)*10
      File "/home/malb/Sage/current/local/lib/python/site-packages/sage/misc/functional.py", line 661, in symbolic_sum
        return sum(expression, *args)
    TypeError: unsupported operand type(s) for +: 'int' and 'dict'
**********************************************************************

malb · 2011-03-06T16:34:54Z

comment:5

Thanks to the input of Nathann the number of failed doctests was greatly reduced.

linear_programming.rst

This seems to be just another just-as-good solution. Probably, the doctest should be changed to allow alternative solutions?

sage -t -long -force_lib "devel/sage/doc/en/thematic_tutorials/linear_programming.rst"
**********************************************************************
File "/home/malb/Sage/current/devel/sage/doc/en/thematic_tutorials/linear_programming.rst", line 366:
    sage: [e for e,b in matching.iteritems() if b == 1]
Expected:
    [(0, 1), (6, 9), (2, 7), (3, 4), (5, 8)]
Got:
    [(1, 6), (0, 4), (2, 3), (5, 8), (7, 9)]
**********************************************************************

digraph.py

Is this worrisome?

sage -t -long -force_lib "devel/sage/sage/graphs/digraph.py"
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/graphs/digraph.py", line 1539:
    sage: x == y
Expected:
    True
Got:
    False
**********************************************************************

mip.pyx

These are purely cosmetic.

sage -t -long -force_lib "devel/sage/sage/numerical/mip.pyx"
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 648:
    sage: p.solve()
Expected:
    0.0
Got:
    -0.0
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 1216:
    sage: p.get_backend()
Expected:
    <sage.numerical.backends.glpk_backend.GLPKBackend object ...>
Got:
    SCIP Constraint Integer Program "" ( maximization, 0 variables, 0 constraints )
**********************************************************************
File "/home/malb/Sage/current/devel/sage/sage/numerical/mip.pyx", line 365:
    sage: p.show()
Expected:
    Maximization:
      Hey[1] +Hey[2]
    Constraints:
      Constraint_1: -3.0 Hey[1] +2.0 Hey[2] <= 2.0
    Variables:
      Hey[1] is a continuous variable (min=0.0, max=+oo)
      Hey[2] is a continuous variable (min=0.0, max=+oo)
Got:
    Maximization:
      x_0 +x_1
    Constraints:
      Constraint_1: -3.0 x_0 +2.0 x_1 <= 2.0
    Variables:
      x_0 is a continuous variable (min=0.0, max=+oo)
      x_1 is a continuous variable (min=0.0, max=+oo)
**********************************************************************

malb · 2011-03-10T14:21:41Z

comment:7

Forgot to update the patch, done that now.

malb · 2011-07-26T14:01:34Z

comment:9

Revised patch to match 4.7.1.

sagetrac-tmonteil · 2013-04-27T20:00:48Z

comment:11

Hi,

why not including http://numberjack.ucc.ie/ in Sage, which already has an interface to SCIP (among others), and allows more expressive constraints (CSP) than MIP only. Also, https://code.google.com/p/python-zibopt/ is another Python interface to SCIP.

malb · 2013-04-28T11:45:37Z

comment:12

Last I checked the latter didn't offer the level of detail I wanted. I didn't know about the former.

malb · 2014-02-06T15:21:59Z

Commit: 7772e92

malb · 2014-02-06T15:21:59Z

Branch: u/malb/scipoptsuite

malb · 2014-02-06T16:01:46Z

comment:16

Doctest failures

$ ./sage -tp 4 --optional sage,scip src/sage
...
sage -t src/sage/libs/scip/scip.pyx  # 2 doctests failed
sage -t src/sage/libs/scip/constraint.pyx  # 2 doctests failed

sagetrac-git · 2014-02-06T17:44:34Z

Branch pushed to git repo; I updated commit sha1. New commits:

`aa23303`	`clean build dir before unpacking tarballs building`
`f51861d`	`quadratic constraint printing and full doctest coverage`

sagetrac-git · 2014-02-06T17:44:34Z

Changed commit from 7772e92 to f51861d

sagetrac-git · 2016-07-12T20:44:06Z

Changed commit from 983d9ea to ac9bbc3

sagetrac-git · 2016-07-12T20:44:06Z

Branch pushed to git repo; I updated commit sha1. New commits:

`ac9bbc3`	`Merge tag '7.3.beta7' into t/10879/ticket/10879`

sagetrac-git · 2016-07-12T21:42:16Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a88cb9d`	`Upgrade to version 3.2.1`

sagetrac-git · 2016-07-12T21:42:16Z

Changed commit from ac9bbc3 to a88cb9d

sagetrac-git · 2016-07-12T22:31:36Z

Changed commit from a88cb9d to ee9fcd4

sagetrac-git · 2016-07-12T22:31:36Z

Branch pushed to git repo; I updated commit sha1. New commits:

`ee9fcd4`	`Comment out PY_TYPE_CHECK`

mkoeppe · 2016-07-12T22:36:27Z

comment:36

Beginning of an attempt to revive this ticket: Updated the SCIP version, merged some stuff, commented out outdated Cython.
Needs more work. "sage -f" does not go through on Mac OS X.

jdemeyer · 2016-07-15T11:48:12Z

comment:38

Several comments about src/module_list.py:

Don't use both condition and package: that is redundant.
Try to avoid include_dirs, it is annoying for portability. Either change the way that SCIP is installed or change the include filenames in the Cython files.
Wildcards are supported: you can use ['sage/libs/scip/*.pyx'] for the sources.

sagetrac-git · 2016-07-15T14:27:44Z

Changed commit from ee9fcd4 to 0a53315

sagetrac-git · 2016-07-15T14:27:44Z

Branch pushed to git repo; I updated commit sha1. New commits:

`0a53315`	`Attempt to remove extra scip/ in include paths`

mkoeppe · 2016-07-17T23:02:13Z

comment:40

Instead of struggling with the hand-written build system of SCIP (http://listserv.zib.de/pipermail/scip/2016-July/002853.html),
we could as well try to leverage the autotoolized build system that COIN-OR uses for SoPlex and SCIP.

See:

slel · 2016-07-18T08:38:43Z

comment:41

Add link to SCIP license in ticket description.

sagetrac-git · 2016-07-20T14:48:24Z

Branch pushed to git repo; I updated commit sha1. New commits:

`322ecb4`	`Merge tag '7.3.beta8' into t/10879/ticket/10879`
`1f514de`	`Fixes for shared library build on Mac`

sagetrac-git · 2016-07-20T14:48:24Z

Changed commit from 0a53315 to 1f514de

mkoeppe · 2016-07-25T19:11:22Z

comment:43

Work will continue on #21094. I'm keeping the branch on this ticket (#10879) as is to preserve the work on the Cython interface to SCIP.
New work on a SCIP backend will probably use #21003 (PySCIPOpt).

mkoeppe · 2023-02-25T07:45:59Z

Completed in #21003

malb added this to the sage-5.11 milestone Mar 5, 2011

malb added c: packages: standard labels Mar 5, 2011

This comment has been minimized.

Sign in to view

malb added the s: needs work label Mar 5, 2011

This comment has been minimized.

Sign in to view

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

This comment has been minimized.

Sign in to view

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

sagetrac-vbraun-spam mannequin removed this from the sage-6.3 milestone Aug 10, 2014

add optional SCIP integer constraint solver #10879

add optional SCIP integer constraint solver #10879

Comments

malb commented Mar 5, 2011

This comment has been minimized.

This comment has been minimized.

malb commented Mar 5, 2011

malb commented Mar 6, 2011

This comment has been minimized.

malb commented Mar 10, 2011

malb commented Jul 26, 2011

This comment has been minimized.

sagetrac-tmonteil mannequin commented Apr 27, 2013

malb commented Apr 28, 2013

malb commented Feb 6, 2014

malb commented Feb 6, 2014

This comment has been minimized.

malb commented Feb 6, 2014

sagetrac-git mannequin commented Feb 6, 2014

sagetrac-git mannequin commented Feb 6, 2014

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

sagetrac-git mannequin commented Jul 12, 2016

sagetrac-git mannequin commented Jul 12, 2016

sagetrac-git mannequin commented Jul 12, 2016

sagetrac-git mannequin commented Jul 12, 2016

sagetrac-git mannequin commented Jul 12, 2016

sagetrac-git mannequin commented Jul 12, 2016

This comment has been minimized.

mkoeppe commented Jul 12, 2016

This comment has been minimized.

jdemeyer commented Jul 15, 2016

sagetrac-git mannequin commented Jul 15, 2016

sagetrac-git mannequin commented Jul 15, 2016

mkoeppe commented Jul 17, 2016

This comment has been minimized.

slel commented Jul 18, 2016

sagetrac-git mannequin commented Jul 20, 2016

sagetrac-git mannequin commented Jul 20, 2016

This comment has been minimized.

mkoeppe commented Jul 25, 2016

This comment has been minimized.

mkoeppe commented Feb 25, 2023