Opened 9 years ago
Last modified 20 months 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) | 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 9 years ago by
- Cc ncohen added
- Description modified (diff)
comment:2 Changed 9 years ago by
- Cc ncohenm schilly added; ncohen removed
- Description modified (diff)
comment:3 Changed 9 years ago by
- Status changed from new to needs_work
comment:4 Changed 9 years ago by
comment:5 Changed 9 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 9 years ago by
- Cc ncohen added; ncohenm removed
comment:7 Changed 9 years ago by
Forgot to update the patch, done that now.
comment:8 Changed 9 years ago by
- Cc jason added
comment:9 Changed 8 years ago by
Revised patch to match 4.7.1.
comment:10 Changed 7 years ago by
- Description modified (diff)
comment:11 Changed 7 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 7 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 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:14 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:15 Changed 6 years ago by
- Branch set to u/malb/scipoptsuite
- Commit set to 7772e92ddbc9531371e3bb53c57b1d6ae51417b1
- Description modified (diff)
comment:16 Changed 6 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 6 years ago by
- Commit changed from 7772e92ddbc9531371e3bb53c57b1d6ae51417b1 to f51861d6f83e3915eb28980f2995d5a38bf1dbc3
comment:18 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:19 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:20 Changed 5 years ago by
- Component changed from packages: standard to packages: optional
comment:21 Changed 4 years ago by
- Branch changed from u/malb/scipoptsuite to u/mkoeppe/ticket/10879
comment:22 Changed 4 years ago by
- Commit changed from f51861d6f83e3915eb28980f2995d5a38bf1dbc3 to 983d9ea066437c92f50efd72b6076e9cff719118
comment:23 Changed 4 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 4 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 4 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
. Are you almost done with it? Dima and I could have some time to work on the review this week.
THaaaaanks,
Nathann
comment:26 Changed 4 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 4 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 4 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 4 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 4 years ago by
- Description modified (diff)
I updated the ticket description to refer to the newest versions
comment:31 Changed 4 years ago by
- Description modified (diff)
comment:32 Changed 3 years ago by
- Description modified (diff)
comment:33 Changed 3 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 3 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 3 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 3 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 3 years ago by
- Description modified (diff)
comment:38 Changed 3 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 3 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 3 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 3 years ago by
- Cc slelievre added
- Description modified (diff)
Add link to SCIP license in ticket description.
comment:42 Changed 3 years ago by
- Commit changed from 0a5331572b59156ecbcb859dc802bbbc2a88f9f1 to 1f514de739769916b46be81858628bed446872a2
comment:43 Changed 3 years ago by
- Description modified (diff)
- Milestone changed from sage-7.3 to sage-wishlist
comment:44 Changed 20 months ago by
- Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
comment:45 Changed 20 months 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