Opened 12 years ago

Last modified 5 years ago

#10879 needs_work enhancement

add optional SCIP integer constraint solver

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: u/mkoeppe/ticket/10879 (Commits, GitHub, GitLab) Commit: 1f514de739769916b46be81858628bed446872a2
Dependencies: Stopgaps:

Status badges

Description (last modified by Samuel Lelièvre)

"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 #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:

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

Change History (45)

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: new → needs_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 12 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)

comment:11 Changed 10 years ago by Thierry Monteil

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.

comment:12 Changed 10 years ago by Martin Albrecht

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

comment:13 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

comment:14 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

comment:15 Changed 9 years ago by Martin Albrecht

Branch: → u/malb/scipoptsuite
Commit: → 7772e92ddbc9531371e3bb53c57b1d6ae51417b1
Description: modified (diff)

comment:16 Changed 9 years ago by Martin Albrecht

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

comment:17 Changed 9 years ago by git

Commit: 7772e92ddbc9531371e3bb53c57b1d6ae51417b1 → f51861d6f83e3915eb28980f2995d5a38bf1dbc3

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

​aa23303clean build dir before unpacking tarballs building
​f51861dquadratic constraint printing and full doctest coverage

comment:18 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

comment:19 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

comment:20 Changed 8 years ago by Jeroen Demeyer

Component: packages: standard → packages: optional

comment:21 Changed 7 years ago by Matthias Köppe

Branch: u/malb/scipoptsuite → u/mkoeppe/ticket/10879

comment:22 Changed 7 years ago by Matthias Köppe

Commit: f51861d6f83e3915eb28980f2995d5a38bf1dbc3 → 983d9ea066437c92f50efd72b6076e9cff719118

I've merged latest develop (6.8.beta5), upgraded to scipoptsuite 3.1.1, and updated to the latest spkg conventions.

Needs more work. Compilation errors with SoPlex related to GMP libraries.

New commits:

​aba96b4Merge tag '6.8.beta5' into t/10879/scipoptsuite
​983d9eaAttempt to update scip spkg

comment:23 Changed 7 years ago by Martin Albrecht

Last time I tested SCIP in Sage under OSX it would always crash, if that's still true then maybe we should set type = experimental?

comment:24 Changed 7 years ago by Nathann Cohen

Wow. And to say that I wanted to work on that next week. Well, I will be working on the review then! Thanks for doing that ;-)

Nathann

comment:25 Changed 7 years ago by Nathann Cohen

Cc: Dima Pasechnik added

Hello,

I am available to review it (it's so biiiiiig... :-/) and I only noticed that it was not in needs_review but in needs_work. Are you almost done with it? Dima and I could have some time to work on the review this week.

THaaaaanks,

Nathann

Last edited 7 years ago by Nathann Cohen (previous) (diff)

comment:26 Changed 7 years ago by Nathann Cohen

A related post there: ​https://groups.google.com/d/topic/sage-devel/r0F6WLu8AiU/discussion

Note for later: In order to compile this package I had to install: libgmp-dev, flex, bison

Nathann

comment:27 Changed 7 years ago by Matthias Köppe

Nathann, I won't have time to work on it at the moment. Everything I did is on the ticket already. So if you and Dima want to work on it, go ahead.

I didn't read the license as to whether we are allowed to redistribute the unmodified upstream tarball. Needs checking.

comment:28 in reply to:  27 Changed 7 years ago by Nathann Cohen

Nathann, I won't have time to work on it at the moment. Everything I did is on the ticket already. So if you and Dima want to work on it, go ahead.

I would like to see if I can "cheaply" (i.e. by writing to a .lp file and calling scip as an external binary) count the number of integer points in a polyhedron (to compare results with #18812). Would you allow me to split the 'new-style package' code off this ticket and into another one?

I can rebase this branch atop of it afterwards.

I didn't read the license as to whether we are allowed to redistribute the unmodified upstream tarball. Needs checking.

​http://listserv.zib.de/pipermail/scip/2015-June/002446.html

Nathann

Last edited 7 years ago by Nathann Cohen (previous) (diff)

comment:29 Changed 7 years ago by Matthias Köppe

Nathann, go for it; I don't claim any ownership on this ticket.

I wasn't aware that SCIP had lattice point counting code.

comment:30 Changed 7 years ago by Dima Pasechnik

Description: modified (diff)

I updated the ticket description to refer to the newest versions

comment:31 Changed 7 years ago by Matthias Köppe

Description: modified (diff)

comment:32 Changed 6 years ago by Matthias Köppe

Description: modified (diff)

comment:33 Changed 6 years ago by git

Commit: 983d9ea066437c92f50efd72b6076e9cff719118 → ac9bbc3ba4d10ad054bab4c07608765d8dd36a78

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

​ac9bbc3Merge tag '7.3.beta7' into t/10879/ticket/10879

comment:34 Changed 6 years ago by git

Commit: ac9bbc3ba4d10ad054bab4c07608765d8dd36a78 → a88cb9d7ce0ad3d1dd77d8807bb453a30551f0f8

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

​a88cb9dUpgrade to version 3.2.1

comment:35 Changed 6 years ago by git

Commit: a88cb9d7ce0ad3d1dd77d8807bb453a30551f0f8 → ee9fcd4c42cd83f9e71b6f7dadc677f5de7bd5c8

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

​ee9fcd4Comment out PY_TYPE_CHECK

comment:36 Changed 6 years ago by Matthias Köppe

Cc: Vincent Delecroix Frédéric Chapoton Jeroen Demeyer added; Nathann Cohen removed
Description: modified (diff)
Keywords: lp added
Milestone: sage-6.4 → sage-7.3

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.

comment:37 Changed 6 years ago by Matthias Köppe

Description: modified (diff)

comment:38 Changed 6 years ago by Jeroen Demeyer

Several comments about src/module_list.py:

  1. Don't use both condition and package: that is redundant.
  1. 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.
  1. Wildcards are supported: you can use ['sage/libs/scip/*.pyx'] for the sources.

comment:39 Changed 6 years ago by git

Commit: ee9fcd4c42cd83f9e71b6f7dadc677f5de7bd5c8 → 0a5331572b59156ecbcb859dc802bbbc2a88f9f1

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

​0a53315Attempt to remove extra scip/ in include paths

comment:40 Changed 6 years ago by Matthias Köppe

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:

comment:41 Changed 6 years ago by Samuel Lelièvre

Cc: Samuel Lelièvre added
Description: modified (diff)

Add link to SCIP license in ticket description.

comment:42 Changed 6 years ago by git

Commit: 0a5331572b59156ecbcb859dc802bbbc2a88f9f1 → 1f514de739769916b46be81858628bed446872a2

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

​322ecb4Merge tag '7.3.beta8' into t/10879/ticket/10879
​1f514deFixes for shared library build on Mac

comment:43 Changed 6 years ago by Matthias Köppe

Description: modified (diff)
Milestone: sage-7.3 → sage-wishlist

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

comment:44 Changed 5 years ago by Moritz Firsching

Milestone: sage-wishlist → sage-duplicate/invalid/wontfix

comment:45 Changed 5 years ago by Samuel Lelièvre

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