Context Navigation

← Previous Ticket
Next Ticket →

#10879 needs_work enhancement

add optional SCIP integer constraint solver

Reported by:	malb	Owned by:	tbd
Priority:	major	Milestone:	sage-duplicate/invalid/wontfix
Component:	packages: optional	Keywords:	lp, mip, mixed integer programming
Cc:	schilly, jason, dimpase, vdelecroix, chapoton, jdemeyer, slelievre	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 slelievre)

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

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

Change History (45)

comment:1 Changed 10 years ago by malb

Cc ncohen added
Description modified (diff)

comment:2 Changed 10 years ago by malb

Cc ncohenm schilly added; ncohen removed
Description modified (diff)

comment:3 Changed 10 years ago by malb

Status changed from new to needs_work

comment:4 Changed 10 years ago by malb

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 10 years ago by malb

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 10 years ago by malb

Cc ncohen added; ncohenm removed

comment:7 Changed 10 years ago by malb

Forgot to update the patch, done that now.

comment:8 Changed 10 years ago by jason

Cc jason added

comment:9 Changed 10 years ago by malb

Revised patch to match 4.7.1.

comment:10 Changed 8 years ago by malb

Description modified (diff)

comment:11 Changed 8 years ago by tmonteil

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 8 years ago by malb

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

comment:13 Changed 8 years ago by jdemeyer

Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 7 years ago by vbraun_spam

Milestone changed from sage-6.1 to sage-6.2

comment:15 Changed 7 years ago by malb

Branch set to u/malb/scipoptsuite
Commit set to 7772e92ddbc9531371e3bb53c57b1d6ae51417b1
Description modified (diff)

comment:16 Changed 7 years ago by malb

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 7 years ago by git

Commit changed from 7772e92ddbc9531371e3bb53c57b1d6ae51417b1 to f51861d6f83e3915eb28980f2995d5a38bf1dbc3

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`

comment:18 Changed 7 years ago by vbraun_spam

Milestone changed from sage-6.2 to sage-6.3

comment:19 Changed 7 years ago by vbraun_spam

Milestone changed from sage-6.3 to sage-6.4

comment:20 Changed 6 years ago by jdemeyer

Component changed from packages: standard to packages: optional

comment:21 Changed 6 years ago by mkoeppe

Branch changed from u/malb/scipoptsuite to u/mkoeppe/ticket/10879

comment:22 Changed 6 years ago by mkoeppe

Commit changed from f51861d6f83e3915eb28980f2995d5a38bf1dbc3 to 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:

aba96b4	`Merge tag '6.8.beta5' into t/10879/scipoptsuite`
983d9ea	`Attempt to update scip spkg`

comment:23 Changed 6 years ago by malb

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 6 years ago by ncohen

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 6 years ago by ncohen

Cc dimpase 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 6 years ago by ncohen (previous) (diff)

comment:26 Changed 6 years ago by ncohen

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 follow-up: ↓ 28 Changed 6 years ago by mkoeppe

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 6 years ago by ncohen

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 6 years ago by ncohen (previous) (diff)

comment:29 Changed 6 years ago by mkoeppe

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 6 years ago by dimpase

Description modified (diff)

I updated the ticket description to refer to the newest versions

comment:31 Changed 5 years ago by mkoeppe

Description modified (diff)

comment:32 Changed 5 years ago by mkoeppe

Description modified (diff)

comment:33 Changed 5 years ago by git

Commit changed from 983d9ea066437c92f50efd72b6076e9cff719118 to ac9bbc3ba4d10ad054bab4c07608765d8dd36a78

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

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

comment:34 Changed 5 years ago by git

Commit changed from ac9bbc3ba4d10ad054bab4c07608765d8dd36a78 to a88cb9d7ce0ad3d1dd77d8807bb453a30551f0f8

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

a88cb9d Upgrade to version 3.2.1

comment:35 Changed 5 years ago by git

Commit changed from a88cb9d7ce0ad3d1dd77d8807bb453a30551f0f8 to ee9fcd4c42cd83f9e71b6f7dadc677f5de7bd5c8

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

ee9fcd4 Comment out PY_TYPE_CHECK

comment:36 Changed 5 years ago by mkoeppe

Cc vdelecroix chapoton jdemeyer added; ncohen removed
Description modified (diff)
Keywords lp added
Milestone changed from sage-6.4 to 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 5 years ago by mkoeppe

Description modified (diff)

comment:38 Changed 5 years ago by jdemeyer

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.

comment:39 Changed 5 years ago by git

Commit changed from ee9fcd4c42cd83f9e71b6f7dadc677f5de7bd5c8 to 0a5331572b59156ecbcb859dc802bbbc2a88f9f1

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

0a53315 Attempt to remove extra scip/ in include paths

comment:40 Changed 5 years ago by mkoeppe

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 5 years ago by slelievre

Cc slelievre added
Description modified (diff)

Add link to SCIP license in ticket description.

comment:42 Changed 5 years ago by git

Commit changed from 0a5331572b59156ecbcb859dc802bbbc2a88f9f1 to 1f514de739769916b46be81858628bed446872a2

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`

comment:43 Changed 5 years ago by mkoeppe

Description modified (diff)
Milestone changed from sage-7.3 to 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 3 years ago by moritz

Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix

comment:45 Changed 3 years ago by slelievre

Description modified (diff)

Note: See TracTickets for help on using tickets.

Download in other formats: