Opened 11 years ago
Last modified 4 years ago
#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: |
Description (last modified by )
"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 11 years ago by
- Cc ncohen added
- Description modified (diff)
comment:2 Changed 11 years ago by
- Cc ncohenm schilly added; ncohen removed
- Description modified (diff)
comment:3 Changed 11 years ago by
- Status changed from new to needs_work
comment:4 Changed 11 years ago by
comment:5 Changed 11 years ago by
- 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 11 years ago by
- Cc ncohen added; ncohenm removed
comment:7 Changed 11 years ago by
Forgot to update the patch, done that now.
comment:8 Changed 11 years ago by
- Cc jason added
comment:9 Changed 11 years ago by
Revised patch to match 4.7.1.
comment:10 Changed 9 years ago by
- Description modified (diff)
comment:11 Changed 9 years ago by
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 9 years ago by
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
- Milestone changed from sage-5.11 to sage-5.12
comment:14 Changed 9 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:15 Changed 9 years ago by
- Branch set to u/malb/scipoptsuite
- Commit set to 7772e92ddbc9531371e3bb53c57b1d6ae51417b1
- Description modified (diff)
comment:16 Changed 9 years ago by
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
- Commit changed from 7772e92ddbc9531371e3bb53c57b1d6ae51417b1 to f51861d6f83e3915eb28980f2995d5a38bf1dbc3
comment:18 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:19 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:20 Changed 8 years ago by
- Component changed from packages: standard to packages: optional
comment:21 Changed 7 years ago by
- Branch changed from u/malb/scipoptsuite to u/mkoeppe/ticket/10879
comment:22 Changed 7 years ago by
- Commit changed from f51861d6f83e3915eb28980f2995d5a38bf1dbc3 to 983d9ea066437c92f50efd72b6076e9cff719118
comment:23 Changed 7 years ago by
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
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
- 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
. Two questions:
1) Are you almost done with it? Dima and I could have some time to work on the review this week 2) Can you share the archive's url? Even if we follow the same steps, it is unlikely that we would end up with the very same archive (with the same hash) because of different tar versions.
THaaaaanks,
Nathann
comment:26 Changed 7 years ago by
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 7 years ago by
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, 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
comment:29 Changed 7 years ago by
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
- Description modified (diff)
I updated the ticket description to refer to the newest versions
comment:31 Changed 6 years ago by
- Description modified (diff)
comment:32 Changed 6 years ago by
- Description modified (diff)
comment:33 Changed 6 years ago by
- 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 6 years ago by
- 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 6 years ago by
- 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 6 years ago by
- 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 6 years ago by
- Description modified (diff)
comment:38 Changed 6 years ago by
Several comments about src/module_list.py
:
- Don't use both
condition
andpackage
: 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 6 years ago by
- 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 6 years ago by
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
- Cc slelievre added
- Description modified (diff)
Add link to SCIP license in ticket description.
comment:42 Changed 6 years ago by
- Commit changed from 0a5331572b59156ecbcb859dc802bbbc2a88f9f1 to 1f514de739769916b46be81858628bed446872a2
comment:43 Changed 6 years ago by
- Description modified (diff)
- Milestone changed from sage-7.3 to sage-wishlist
comment:44 Changed 4 years ago by
- Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
comment:45 Changed 4 years ago by
- Description modified (diff)
Doctest failures in detail
doc/en/thematic_tutorials/linear_programming.rst
sage/graphs/digraph.py
sage/graphs/graph_coloring.py
sage/graphs/graph_generators.py
sage/numerical/knapsack.py
sage/numerical/mip.pyx
sage/graphs/generic_graph.py