Opened 12 years ago

Last modified 4 years ago

#10879 needs_work enhancement

add optional SCIP integer constraint solver — at Version 10

Reported by: Martin Albrecht Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: packages: optional Keywords: lp, mip, mixed integer programming
Cc: Harald Schilly, Jason Grout, Dima Pasechnik, Vincent Delecroix, Frédéric Chapoton, Jeroen Demeyer, Samuel Lelièvre Merged in:
Authors: Martin Albrecht Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Martin Albrecht)

"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

However, we don't have the right to redistribute the SCIP source code. Thus, the attached SPKG is empty except for the spkg-install script etc.

To build a SCIP for Sage do:

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.

Change History (10)

comment:1 Changed 12 years ago by Martin Albrecht

Cc: Nathann Cohen added
Description: modified (diff)

comment:2 Changed 12 years ago by Martin Albrecht

Cc: ncohenm Harald Schilly added; Nathann Cohen removed
Description: modified (diff)

comment:3 Changed 12 years ago by Martin Albrecht

Status: newneeds_work

comment:4 Changed 12 years ago by Martin Albrecht

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'
**********************************************************************

comment:5 Changed 12 years ago by Martin Albrecht

Description: modified (diff)

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)
**********************************************************************

comment:6 Changed 12 years ago by Martin Albrecht

Cc: Nathann Cohen added; ncohenm removed

comment:7 Changed 12 years ago by Martin Albrecht

Forgot to update the patch, done that now.

comment:8 Changed 11 years ago by Jason Grout

Cc: Jason Grout added

comment:9 Changed 11 years ago by Martin Albrecht

Revised patch to match 4.7.1.

comment:10 Changed 10 years ago by Martin Albrecht

Description: modified (diff)
Note: See TracTickets for help on using tickets.