Sage package for SCIP integer programming solver

[mkoeppe]

Split out from the larger ticket #10879. This ticket just adds an spkg, not the Cython interface.

"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 Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver #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

Upstream discussion: http://listserv.zib.de/pipermail/scip/2016-July/002853.html

Follow-up: #21003: Add SCIP backend using PySCIPOpt

Depends on #21151

CC: @malb @haraldschilly @jasongrout @dimpase @videlec @fchapoton @jdemeyer @slel @tscrim @embray @vbraun

Component: packages: experimental

Author: Martin Albrecht, Matthias Koeppe

Branch: 1c070e4

Reviewer: Travis Scrimshaw, Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/21094

[mkoeppe]

Branch: u/mkoeppe/sage_package_for_scip_integer_programming_solver

[sagetrac-git]

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

e213452

Update build instructions

[sagetrac-git]

Commit: e213452

[sagetrac-git]

Changed commit from e213452 to 0b4219c

[sagetrac-git]

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

55307b3	build soplex with -install_name
0b4219c	Fix library dependencies on Mac OS X

[mkoeppe]

comment:4

It finally builds on Mac OS X.
Needs testing / review.

[mkoeppe]

Author: Martin Albrecht, Matthias Koeppe

[sagetrac-git]

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

0836b16	Unpack soplex and scip where the scipoptsuite Makefile would
29a8853	Use OPT=dbg build to fix segfault on Mac OS X
9b7a26c	spkg-install: check scip starts, spkg-check: run testsuite

[sagetrac-git]

Changed commit from 0b4219c to 9b7a26c

[sagetrac-git]

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

5d900b0

Build scip linking against libscip.

[sagetrac-git]

Changed commit from 9b7a26c to 5d900b0

[tscrim]

comment:8

On 7.3.rc0 with my Ubuntu 14.04 LTS, I could not get this to build:

Found local metadata for scipoptsuite-3.2.1
Using cached file /home/travis/sage-build/upstream/scipoptsuite-3.2.1.tgz
scipoptsuite-3.2.1
====================================================
Setting up build directory for scipoptsuite-3.2.1
Finished extraction
****************************************************
Host system:
Linux apricot 3.13.0-87-generic #133-Ubuntu SMP Tue May 24 18:32:09 UTC 2016 x86_64 x86_6
4 x86_64 GNU/Linux
****************************************************
C compiler: gcc
C compiler version:
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.9/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.9.3-8ubuntu2~14.04' --wi
th-bugurl=file:///usr/share/doc/gcc-4.9/README.Bugs --enable-languages=c,c++,java,go,d,fo
rtran,objc,obj-c++ --prefix=/usr --program-suffix=-4.9 --enable-shared --enable-linker-bu
ild-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx
-include-dir=/usr/include/c++/4.9 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enabl
e-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-ob
ject --disable-vtable-verify --enable-plugin --with-system-zlib --disable-browser-plugin 
--enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.9
-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.9-amd64 -
-with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.9-amd64 --with-arch-directory=amd
64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --d
isable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enab
le-multilib --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host
=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.9.3 (Ubuntu 4.9.3-8ubuntu2~14.04) 
****************************************************
soplex-2.2.1/COPYING
soplex-2.2.1/INSTALL
...
soplex-2.2.1/src/usertimer.cpp
soplex-2.2.1/src/wallclocktimer.cpp
patching file Makefile
Compiling SoPlex
make: Entering an unknown directory
make: *** empty string invalid as file name.  Stop.
make: Leaving an unknown directory
Error building SOPLEX.

The log file doesn't contain anything else of interest, but I can post it if you want. Tell me what you need from me or what I can do to debug.

[mkoeppe]

comment:9

"Entering an unknown directory", very mysterious.
Perhaps you can go to the temporary build directory and do a "bash -x spkg-install" and post the result.
Thanks!

[sagetrac-git]

Changed commit from 5d900b0 to a050604

[sagetrac-git]

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

a050604

Install libscip also as libscipopt

[sagetrac-git]

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

c21e1bb

Redo SCIP patches, install missing headers

[sagetrac-git]

Changed commit from a050604 to c21e1bb

[sagetrac-git]

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

438a190

More fixes for Darwin/non-Darwin

[sagetrac-git]

Changed commit from c21e1bb to 438a190

[mkoeppe]

comment:13

OK, I've solved this particular problem, but it needs more work regarding the shared libraries on Linux.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:14

Sorry for the delay in getting back to this. Yes, this installed for me now. However, the spkg-install is non-trivial, so I would prefer someone with a bit more expertise, such as Jeroen (jdemeyer), Erik (embray) or Volker (vbraun), to look over it before giving this a positive review.

[sagetrac-git]

Changed commit from b372675 to 49659e3

[sagetrac-git]

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

49659e3

Fixup

[mkoeppe]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw + NEEDS MORE REVIEWERS

[mkoeppe]

comment:18

OK, now it works also on Linux. Needs review.

[tscrim]

comment:19

FYI, recent changes also compile on my Ubuntu.

Erik, Volker, or Jeroen, do one of you have time to look over the build setup? Also, a more general question, can we rehost the tarball?

[mkoeppe]

comment:20

Replying to @tscrim:

can we rehost the tarball?

No. Users need to download it themselves from the ZIB server. Details:
http://listserv.zib.de/pipermail/scip/2015-July/002448.html

[mkoeppe]

Dependencies: #21151

[jdemeyer]

comment:22

Given that we cannot host the tarball, I would really want to see this as an "experimental" package, just like the component on this ticket suggests.

Besides this, if the package has successfully been built on Linux and OS X, that is sufficient for me to have positive_review.

[tscrim]

comment:23

Matthias, have you asked SCIP whether or not we could host the tarball on our mirrors and/or have Sage have some kind of automatic download of the tarball (but not hosted on our mirrors)?

[dimpase]

comment:24

We did have a long discussion with ZIB on this, and the answer was no. They want to count their downloads, full stop.

[sagetrac-git]

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

527147e	Merge tag '7.3.rc0' into t/21094/sage_package_for_scip_integer_programming_solver
1c070e4	scipoptsuite: Change package type to experimental

[sagetrac-git]

Changed commit from 49659e3 to 1c070e4

[mkoeppe]

comment:26

Replying to @jdemeyer:

Given that we cannot host the tarball, I would really want to see this as an "experimental" package, just like the component on this ticket suggests.

OK, done.

Besides this, if the package has successfully been built on Linux and OS X, that is sufficient for me to have positive_review.

OK, could you take a look at #21151, which I have marked as a dependency - it's a minor update to TOPCOM so that it still installs when scipoptsuite has been installed.

[tscrim]

comment:27

Replying to @dimpase:

We did have a long discussion with ZIB on this, and the answer was no. They want to count their downloads, full stop.

We can't even set it up so that running sage -i scipoptsuite automatically goes through and does the download?

[jdemeyer]

Changed reviewer from Travis Scrimshaw + NEEDS MORE REVIEWERS to Travis Scrimshaw, Jeroen Demeyer

[jdemeyer]

comment:28

I think this is sufficient for an experimental package.

[mkoeppe]

comment:29

Replying to @tscrim:

Replying to @dimpase:
We can't even set it up so that running sage -i scipoptsuite automatically goes through and does the download?

As per http://listserv.zib.de/pipermail/scip/2015-July/002448.html :
Q: Users could "download and install" this copy by running "sage -i scip"

A: In this case you would have to ensure that people notice and acknowledge that
they use SCIP under the Academic License, which excludes any commercial
usage.

So some kind of license display and acknowledgement prompt could be done. I don't want to work on this, though. If you want to add this, please make a follow-up ticket.

[mkoeppe]

comment:30

Replying to @jdemeyer:

I think this is sufficient for an experimental package.

Thanks!

[mkoeppe]

comment:31

#21151?

[vbraun]

Changed branch from u/mkoeppe/sage_package_for_scip_integer_programming_solver to 1c070e4

[jdemeyer]

comment:33

Replying to @sagetrac-git:

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

c21e1bb

Redo SCIP patches, install missing headers

Why were the patches put inside a scip subdirectory? I see no reason for that (scipoptsuite is the only package doing this)

[jdemeyer]

Changed commit from 1c070e4 to none

[mkoeppe]

comment:34

SCIPoptsuite itself is a "distribution", consisting of SoPlex, SCIP, and other packages, whose tar.gz files are included in the tarball of SCIPoptsuite. (Not all of these packages have a separate upstream download.)

The patches are relative to the scip subdirectory that is created after unpacking the included SCIP tar.gz. They are generated from a git repository of SCIP.