Add SCIP backend using PySCIPOpt

[mkoeppe]

This ticket adds a package pyscipopt and adds a new MIP backend based on it.

​https://github.com/SCIP-Interfaces/PySCIPOpt

Branch is on top of #31329.

Steps to get it to work:

• pull from this branch
• put ​http://scip.zib.de/download.php?fname=scipoptsuite-7.0.2.tgz in ./upstream
• put PySCIPOpt-3.1.0.tar.gz in ./upstream
• sage -f pyscipopt

[git]

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

​7075b83	Pacth SCIP Makefile more to get library dependencies right
​b372675	Fixup
​49659e3	Fixup
​db1b1d9	Merge branch 't/21094/sage_package_for_scip_integer_programming_solver' into t/21003/pyscipopt

[git]

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

​805a034

Merge tag '7.4.beta0' into t/21003/pyscipopt

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a3bf199	Add SCIP backend (stubs only)
​d3271c0	New pip package pyscipopt

[git]

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

​41b70bb

PySCIPOpt: Install from git

[git]

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

​6cc2bd7	Update patches and script for 4.0.0
​31f7397	Merge branch 't/22557/upgrade_scipopt_to_4_0' into t/21003/pyscipopt
​92b7420	pyscipopt: Use real upstream git
​d973980	SCIPBackend: First step

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​ccf5e37	Update patches and script for 4.0.0
​75fb34c	Use OPT=opt on Linux. Check results of test suite
​74f1d79	scip: Working configuration for clang on Mac
​0f37658	scipoptsuite: Use clang on Mac OS
​607a51c	Add SCIP backend (stubs only)
​05a723f	New pip package pyscipopt
​74a2875	PySCIPOpt: Install from git
​b433c65	pyscipopt: Use real upstream git
​9794b3a	SCIPBackend: First step

[moritz]

This (hopefully) works now, after putting PySCIPOpt-1.4.0.tar.gz into upstream, which can be found here:

​https://pypi.python.org/packages/59/73/087bcb1d4e284681346a8847b83c5a86568dd19034ead0884450fa6bda50/PySCIPOpt-1.4.0.tar.gz#md5=6d40750e286348247e31e568bf16ee2d

*UPDATE* (from a later edit): now you need to put PySCIPOpt-1.4.2.tar.gz ​https://pypi.python.org/packages/c0/b6/b619a33cd90dbf5579de341c873f85f0388030c47ee5da71a9113ee308d4/PySCIPOpt-1.4.2.tar.gz#md5=4f175316bc3ba4ce97c284434a4b62f0

*UPDATE* (from yet a later edit): Check the description of the ticket for the latest version!

---

Last 10 new commits:

​966aeb9	compiling with cmake
​057a2c7	add dependency info
​f4a061e	use cmake sage package; make output verbose
​b86cf01	scipoptsuite: Add patch for using libhistory (needed for Mac OS X)
​e94b94e	improving the check
​6cce2c7	Add SCIP backend (stubs only)
​4eb6e95	New pip package pyscipopt
​fbe8e62	PySCIPOpt: Install from git
​9c8d7c6	pyscipopt: Use real upstream git
​f260221	SCIPBackend: First step

[git]

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

​8fdae7c

new version 1.4.0

[git]

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

​1958470

added SPKG.txt

[git]

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

​b0462bd	starting with the backend
​6ebdc93	most functions of the backend

[git]

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

​1eb3412

almost all doctests working, some pyscipopt patches

[git]

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

​84e6b11	getParam and setParam working
​67542be	all methods implemented in backend; all doctests working
​a586569	one more patch

[moritz]

In this version, there are a number of patches in the patches directory. All of them will be merged upstream in a version of pyscipopt with version number >=1.4.3, which should be available on Pypi not too long from now. I will update the pyscipopt package then.

[mkoeppe]

I merged latest #24662.

All doctests need to be marked # optional - pyscipopt

---

New commits:

​f4ad108	put readline as depency
​8b20290	scipoptsuite: Update patch to remove cmake warning
​f25f900	scipoptsuite: Set GMP_DIR so that we do not catch /usr/local/include
​d49ff94	scipoptsuite: Add patch: ZIMPL cmake scripts: Put ZIMPL includes first to avoid clash of idxset.h with install soplex idxset.h
​d7e29d5	scipoptsuite: Fix install name for libscip on Mac
​737e606	Make bliss and MP_LIBRARY dependencies, cmake order-only dependency
​080bc90	Merge branch 't/24662/public/scipoptsuite' into t/21003/pyscipopt

[mkoeppe]

Also 1.4.3 is out.

[moritz]

in the meantime its version 1.4.4: I am on it...

[moritz]

I marked all doctest optional and updated.

Suddenly, one doctest doesn't work anymore:

sage: g = graphs.CubeGraph(9)
sage: p = MixedIntegerLinearProgram(solver = "SCIP")                # optional - pyscipopt

sage: b = p.new_variable(binary=True)                               # optional - pyscipopt
sage: p.set_objective(p.sum(b[v] for v in g))                       # optional - pyscipopt
sage: for v in g:                                                   # optional - pyscipopt
....:     p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1) # optional - pyscipopt
sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution    # optional - pyscipopt
sage: p.solver_parameter("limits/absgap", 100)                      # optional - pyscipopt
sage: p.solve() # rel tol 100                                       # optional - pyscipopt

and totaly chrashes sage with an error message free(): invalid pointer. I don't quite know what is going on.

What is really weird is that it works if I don't run the last line, but instead:

sage: q = copy(p)
sage: q.solver_parameter("limits/absgap", 100)
sage: q.solve()
0

(I temperarily change 9 to 4 in the doctest above, in order to be able to run the rest of the doctest. The current branch works without failures for me.)

---

Last 10 new commits:

​0544b25	almost all doctests working, some pyscipopt patches
​c774d7e	getParam and setParam working
​41f641b	all methods implemented in backend; all doctests working
​c10594c	one more patch
​c7eee88	pyscipopt: update to v1.4.3
​a054b24	pyscipopt: update to v1.4.4
​3e5621a	scip-backend: added '# optional - pyscipopt'
​52b98d0	Make bliss and MP_LIBRARY dependencies, cmake order-only dependency
​f217970	quicksum and modify doctests
​82fd6d6	remove all patches

[moritz]

... the nice thing: all my patches have been merged by a very responsive upstream!

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​07a8254	almost all doctests working, some pyscipopt patches
​9206579	getParam and setParam working
​60b470f	all methods implemented in backend; all doctests working
​ccaae73	one more patch
​c0bc9d2	pyscipopt: update to v1.4.3
​04f33d1	pyscipopt: update to v1.4.4
​3816595	scip-backend: added '# optional - pyscipopt'
​563e0aa	quicksum and modify doctests
​59d8529	remove all patches
​8af6e7f	change 4 back to 9

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​670146b	almost all doctests working, some pyscipopt patches
​cfbbdb1	getParam and setParam working
​9d66f70	all methods implemented in backend; all doctests working
​2b6efc9	one more patch
​d246de5	pyscipopt: update to v1.4.3
​b431129	pyscipopt: update to v1.4.4
​1f9050d	scip-backend: added '# optional - pyscipopt'
​95890af	quicksum and modify doctests
​6c7d9c9	remove all patches
​c82646a	change 4 back to 9

[moritz]

now everything seems to work! I reviewed the stubs and everything written by Matthias on this ticket.

[vdelecroix]

In the spkg-install script you should not be using the make command but rather sdh_make from the "Sage-distribution helper" tools (see src/bin/sage-dist-helpers).

[vdelecroix]

Also avoid $MAKE test | tee testsuite.log (in spkg-check). It is not the role of the script to perform redirections.

[moritz]

Thanks for the comments, Vincent! I assume, they are meant for the scipoptsuite package, not the pyscipopt one, I will change that on #24662..

[vdelecroix]

Please use multiple lines for

cmake .. -DCMAKE_INSTALL_PREFIX="${SAGE_LOCAL}"/ -DCMAKE_VERBOSE_MAKEFILE=ON -DGMP_DIR="${SAGE_LOCAL}" -DZLIB_ROOT="${SAGE_LOCAL}" -DReadline_ROOT_DIR="${SAGE_LOCAL}" -DBLISS_DIR="${SAGE_LOCAL}" -DIPOPT=FALSE

[vdelecroix]

Replying to moritz:

Thanks for the comments, Vincent! I assume, they are meant for the scipoptsuite package, not the pyscipopt one, I will change that on #24662..

You should not, this ticket is in positive review!

[moritz]

Replying to vdelecroix:

Replying to moritz:

Thanks for the comments, Vincent! I assume, they are meant for the scipoptsuite package, not the pyscipopt one, I will change that on #24662..

You should not, this ticket is in positive review!

ok

[vdelecroix]

Why this change in numerical/mip.pyx

-        self._p._backend.set_variable_type(j, self._vtype)
+        #self._p._backend.set_variable_type(j, self._vtype)

If this line is not needed anymore just remove it.

[vdelecroix]

You could also simplify the SPKG.txt file:

• the section SPKG Maintainers of SPKG.txt is not needed anymore (the information is likely to be not up to date in few time)
• if Special Update/Build Instructions is empty, just avoid it.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​c3bc320	getParam and setParam working
​c4c3680	all methods implemented in backend; all doctests working
​d3aa9d0	one more patch
​e9f531e	pyscipopt: update to v1.4.3
​0a07d61	pyscipopt: update to v1.4.4
​de6b1bf	scip-backend: added '# optional - pyscipopt'
​fba294a	quicksum and modify doctests
​4aadef8	remove all patches
​94fac2d	change 4 back to 9
​31e0d1f	rebased and Vincent's suggestions

[git]

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

​c0b432c

correct linebreaks

[moritz]

I addressed all suggestions by Vincent and tested the install of scipoptsuite as well as pyscipopt.

[vdelecroix]

merge conflicts

[vdelecroix]

And this will not work

cmake .. -DCMAKE_INSTALL_PREFIX="${SAGE_LOCAL}"/
         -DCMAKE_VERBOSE_MAKEFILE=ON
         -DGMP_DIR="${SAGE_LOCAL}"
         -DZLIB_ROOT="${SAGE_LOCAL}"
         -DReadline_ROOT_DIR="${SAGE_LOCAL}"
         -DBLISS_DIR="${SAGE_LOCAL}"
         -DIPOPT=FALSE

You need to add backslashes for line continuation

cmake .. -DCMAKE_INSTALL_PREFIX="${SAGE_LOCAL}" \
         -DCMAKE_VERBOSE_MAKEFILE=ON            \
         -DGMP_DIR="${SAGE_LOCAL}"              \
         -DZLIB_ROOT="${SAGE_LOCAL}"            \
         -DReadline_ROOT_DIR="${SAGE_LOCAL}"    \
         -DBLISS_DIR="${SAGE_LOCAL}"            \
         -DIPOPT=FALSE

[moritz]

I will get to work. I think the line break issue was fixed here: ​https://git.sagemath.org/sage.git/commit/?id=c0b432c427236c07f76f930a156a15d3f33eb1f1

But I can make the slashes align, of course.

[vdelecroix]

Alignment does not matter. But there should be backslashes.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​3c7d354	all methods implemented in backend; all doctests working
​e9095b7	one more patch
​f33a55e	pyscipopt: update to v1.4.3
​99c5010	pyscipopt: update to v1.4.4
​78ef11d	scip-backend: added '# optional - pyscipopt'
​e59e041	quicksum and modify doctests
​24ca41d	remove all patches
​d627bcd	change 4 back to 9
​10913f8	rebased and Vincent's suggestions
​c07eb7e	correct linebreaks

[moritz]

Replying to vdelecroix:

merge conflicts

I did a rebase, and it was done automatically. I ran all the tests, and (at least on my machine) everything works..

I am a bit confused, because I expected to see merge conflicts..

[vdelecroix]

Replying to moritz:

Replying to vdelecroix:

merge conflicts

I did a rebase, and it was done automatically. I ran all the tests, and (at least on my machine) everything works..

I am a bit confused, because I expected to see merge conflicts..

Applying patches is not commutative!

[vdelecroix]

What is the point of using Cython here? Because you use pyscipopt everywhere there is no C at all in the file scip_backend.pyx. I would keep it simple and use pure python here.

[moritz]

Replying to vdelecroix:

What is the point of using Cython here? Because you use pyscipopt everywhere there is no C at all in the file scip_backend.pyx. I would keep it simple and use pure python here.

I think Matthias made the backend Cython, because the generic_backend.pyx is also written this way and all the other files are written in this way. However other backends might actually need this.

I agree that there we don't really need Cython for the pyscipopt backend. But it doesn't do any harm, does it? I am indifferent; we can change it or leave it, both is fine with me.

[vdelecroix]

Replying to moritz:

Replying to vdelecroix:

What is the point of using Cython here? Because you use pyscipopt everywhere there is no C at all in the file scip_backend.pyx. I would keep it simple and use pure python here.

I think Matthias made the backend Cython, because the generic_backend.pyx is also written this way and all the other files are written in this way. However other backends might actually need this.

I agree that there we don't really need Cython for the pyscipopt backend. But it doesn't do any harm, does it? I am indifferent; we can change it or leave it, both is fine with me.

On the plus side

• do like the other backends

On the minus side

• two files (pxd/pyx) instead of one
• longer compilation time
• more delicate to debug

The reason why all other backends are written in Cython is because they do call C functions.

[mkoeppe]

Replying to moritz:

I think Matthias made the backend Cython, because the generic_backend.pyx is also written this way and all the other files are written in this way.

That's correct, I did this just for copypastability and no technical reason otherwise.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​0e30cca	pyscipopt: update to v1.4.3
​7e112c8	pyscipopt: update to v1.4.4
​d1519b9	scip-backend: added '# optional - pyscipopt'
​901f8cf	quicksum and modify doctests
​8fc35cf	remove all patches
​32884a0	change 4 back to 9
​0ef22c6	rebased and Vincent's suggestions
​d23ed3e	correct linebreaks
​1cefe04	towards uncythening the scip backend
​ae0bab0	decythonizing finished

[mkoeppe]

Another update to SCIPoptsuite 6.0 is due

[vdelecroix]

milestone update 8.3 -> 8.4

[mkoeppe]

Squashed/rebased onto #31329 (Update scipoptsuite to 7.0.2)

[git]

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

​cd0b761

build/pkgs/pyscipopt: Update to 3.1.0, update metadata format

[mkoeppe]

sage: from pyscipopt import Model                                                                                                                                                                                        
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-fcc6f2f967b1> in <module>
----> 1 from pyscipopt import Model

~/s/sage/sage-rebasing/worktree-algebraic-2018-spring/local/lib/python3.9/site-packages/pyscipopt/__init__.py in <module>
      9 # export user-relevant objects:
     10 from pyscipopt.Multidict import multidict
---> 11 from pyscipopt.scip      import Model
     12 from pyscipopt.scip      import Benders
     13 from pyscipopt.scip      import Benderscut

ImportError: dlopen(/Users/mkoeppe/s/sage/sage-rebasing/worktree-algebraic-2018-spring/local/lib/python3.9/site-packages/pyscipopt/scip.cpython-39-darwin.so, 2): Library not loaded: libscip.7.0.dylib
  Referenced from: /Users/mkoeppe/s/sage/sage-rebasing/worktree-algebraic-2018-spring/local/lib/python3.9/site-packages/pyscipopt/scip.cpython-39-darwin.so
  Reason: image not found

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

Setting a new milestone for this ticket based on a cursory review.