Opened 3 years ago

Last modified 7 months ago

#21003 needs_info enhancement

Add SCIP backend using PySCIPOpt

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-8.4
Component: linear programming Keywords: lp, days84, IMA-PolyGeom
Cc: moritz, yzh, malb Merged in:
Authors: Matthias Koeppe, Moritz Firsching Reviewers: Moritz Firsching, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: u/moritz/pyscipopt (Commits) Commit: ae0bab040a3b6d0cb77c5593bf486242365621f6
Dependencies: #22557, #24662 Stopgaps:

Description (last modified by moritz)

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 #24662.

Steps to get it to work:

Change History (66)

comment:1 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:2 Changed 3 years ago by mkoeppe

  • Dependencies changed from #10879 to #21094

comment:3 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/pyscipopt

comment:4 Changed 3 years ago by git

  • Commit set to db1b1d9c9de824cb25e614b9b39ee838f7f510ad

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

7075b83Pacth SCIP Makefile more to get library dependencies right
b372675Fixup
49659e3Fixup
db1b1d9Merge branch 't/21094/sage_package_for_scip_integer_programming_solver' into t/21003/pyscipopt

comment:5 Changed 3 years ago by git

  • Commit changed from db1b1d9c9de824cb25e614b9b39ee838f7f510ad to 805a0349170376f392c0b1aff410b554d894a4c1

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

805a034Merge tag '7.4.beta0' into t/21003/pyscipopt

comment:6 Changed 2 years ago by git

  • Commit changed from 805a0349170376f392c0b1aff410b554d894a4c1 to d3271c0e047c6ead45eb7330101db1e2b1c0843f

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

a3bf199Add SCIP backend (stubs only)
d3271c0New pip package pyscipopt

comment:7 Changed 2 years ago by moritz

  • Cc moritz added

comment:8 Changed 2 years ago by git

  • Commit changed from d3271c0e047c6ead45eb7330101db1e2b1c0843f to 41b70bb400d4a0142f5bbf6ff64756868f4383a5

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

41b70bbPySCIPOpt: Install from git

comment:9 Changed 2 years ago by mkoeppe

  • Description modified (diff)
  • Milestone changed from sage-7.3 to sage-7.6

comment:10 Changed 2 years ago by vdelecroix

  • Keywords days84 added

comment:11 Changed 2 years ago by mkoeppe

  • Authors set to Matthias Koeppe, needs more authors

comment:12 Changed 2 years ago by git

  • Commit changed from 41b70bb400d4a0142f5bbf6ff64756868f4383a5 to d973980c8bea05015dbcc4e28121f77de30eb6a2

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

6cc2bd7Update patches and script for 4.0.0
31f7397Merge branch 't/22557/upgrade_scipopt_to_4_0' into t/21003/pyscipopt
92b7420pyscipopt: Use real upstream git
d973980SCIPBackend: First step

comment:13 Changed 2 years ago by mkoeppe

  • Dependencies changed from #21094 to #22557
  • Description modified (diff)

comment:14 Changed 2 years ago by git

  • Commit changed from d973980c8bea05015dbcc4e28121f77de30eb6a2 to 9794b3ae7c7b836ddff0e419aaf8a369d0ec76dc

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

ccf5e37Update patches and script for 4.0.0
75fb34cUse OPT=opt on Linux. Check results of test suite
74f1d79scip: Working configuration for clang on Mac
0f37658scipoptsuite: Use clang on Mac OS
607a51cAdd SCIP backend (stubs only)
05a723fNew pip package pyscipopt
74a2875PySCIPOpt: Install from git
b433c65pyscipopt: Use real upstream git
9794b3aSCIPBackend: First step

comment:15 Changed 2 years ago by mkoeppe

  • Cc yzh added

comment:16 Changed 13 months ago by moritz

  • Dependencies changed from #22557 to #22557, #24662

comment:17 Changed 11 months ago by moritz

  • Branch changed from u/mkoeppe/pyscipopt to u/moritz/pyscipopt

comment:18 Changed 11 months ago by moritz

  • Commit changed from 9794b3ae7c7b836ddff0e419aaf8a369d0ec76dc to f260221f94bcfeada17fa4836303e8dd57fbd4f7

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:

966aeb9compiling with cmake
057a2c7add dependency info
f4a061euse cmake sage package; make output verbose
b86cf01scipoptsuite: Add patch for using libhistory (needed for Mac OS X)
e94b94eimproving the check
6cce2c7Add SCIP backend (stubs only)
4eb6e95New pip package pyscipopt
fbe8e62PySCIPOpt: Install from git
9c8d7c6pyscipopt: Use real upstream git
f260221SCIPBackend: First step
Last edited 10 months ago by moritz (previous) (diff)

comment:19 Changed 11 months ago by git

  • Commit changed from f260221f94bcfeada17fa4836303e8dd57fbd4f7 to 8fdae7c429e4814f15fa13bf9ff9b7699586c9a9

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

8fdae7cnew version 1.4.0

comment:20 Changed 11 months ago by git

  • Commit changed from 8fdae7c429e4814f15fa13bf9ff9b7699586c9a9 to 1958470beb6fecca8d71ebd7fbf1dfcf452f7cb9

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

1958470added SPKG.txt

comment:21 Changed 11 months ago by git

  • Commit changed from 1958470beb6fecca8d71ebd7fbf1dfcf452f7cb9 to 6ebdc937ef5033d45dc7a6107d02c0be56b8970e

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

b0462bdstarting with the backend
6ebdc93most functions of the backend

comment:22 Changed 11 months ago by moritz

  • Authors changed from Matthias Koeppe, needs more authors to Matthias Koeppe, Moritz Firsching, needs more authors

comment:23 Changed 11 months ago by mkoeppe

  • Keywords IMA-PolyGeom added
  • Milestone changed from sage-7.6 to sage-8.2

comment:24 Changed 11 months ago by git

  • Commit changed from 6ebdc937ef5033d45dc7a6107d02c0be56b8970e to 1eb34120be1864103d24c7a057e8e30101f6d822

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

1eb3412almost all doctests working, some pyscipopt patches

comment:25 Changed 11 months ago by moritz

  • Description modified (diff)

comment:26 Changed 11 months ago by git

  • Commit changed from 1eb34120be1864103d24c7a057e8e30101f6d822 to a586569de8a5b864cdd5dc431eb61b05825d6dd4

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

84e6b11getParam and setParam working
67542beall methods implemented in backend; all doctests working
a586569one more patch

comment:27 Changed 11 months ago by moritz

  • Authors changed from Matthias Koeppe, Moritz Firsching, needs more authors to Matthias Koeppe, Moritz Firsching
  • Status changed from new to needs_review

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.

comment:28 Changed 11 months ago by moritz

  • Cc malb added

comment:29 Changed 10 months ago by mkoeppe

  • Branch changed from u/moritz/pyscipopt to u/mkoeppe/pyscipopt

comment:30 Changed 10 months ago by mkoeppe

  • Commit changed from a586569de8a5b864cdd5dc431eb61b05825d6dd4 to 080bc9037c475123d4ed1428150d740d64480001

I merged latest #24662.

All doctests need to be marked # optional - pyscipopt


New commits:

f4ad108put readline as depency
8b20290scipoptsuite: Update patch to remove cmake warning
f25f900scipoptsuite: Set GMP_DIR so that we do not catch /usr/local/include
d49ff94scipoptsuite: Add patch: ZIMPL cmake scripts: Put ZIMPL includes first to avoid clash of idxset.h with install soplex idxset.h
d7e29d5scipoptsuite: Fix install name for libscip on Mac
737e606Make bliss and MP_LIBRARY dependencies, cmake order-only dependency
080bc90Merge branch 't/24662/public/scipoptsuite' into t/21003/pyscipopt

comment:31 Changed 10 months ago by mkoeppe

  • Status changed from needs_review to needs_work

Also 1.4.3 is out.

comment:32 Changed 10 months ago by moritz

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

comment:33 Changed 10 months ago by moritz

  • Branch changed from u/mkoeppe/pyscipopt to u/moritz/pyscipopt

comment:34 Changed 10 months ago by moritz

  • Commit changed from 080bc9037c475123d4ed1428150d740d64480001 to 82fd6d6f0ef30160e00a794cb339b78170ef9bf7

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:

0544b25almost all doctests working, some pyscipopt patches
c774d7egetParam and setParam working
41f641ball methods implemented in backend; all doctests working
c10594cone more patch
c7eee88pyscipopt: update to v1.4.3
a054b24pyscipopt: update to v1.4.4
3e5621ascip-backend: added '# optional - pyscipopt'
52b98d0Make bliss and MP_LIBRARY dependencies, cmake order-only dependency
f217970quicksum and modify doctests
82fd6d6remove all patches

comment:35 Changed 10 months ago by moritz

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

comment:36 Changed 10 months ago by moritz

  • Description modified (diff)

comment:37 Changed 10 months ago by moritz

  • Description modified (diff)

comment:38 Changed 10 months ago by git

  • Commit changed from 82fd6d6f0ef30160e00a794cb339b78170ef9bf7 to 8af6e7f53004ab54d17305f2c23ba25425089487

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

07a8254almost all doctests working, some pyscipopt patches
9206579getParam and setParam working
60b470fall methods implemented in backend; all doctests working
ccaae73one more patch
c0bc9d2pyscipopt: update to v1.4.3
04f33d1pyscipopt: update to v1.4.4
3816595scip-backend: added '# optional - pyscipopt'
563e0aaquicksum and modify doctests
59d8529remove all patches
8af6e7fchange 4 back to 9

comment:39 Changed 10 months ago by git

  • Commit changed from 8af6e7f53004ab54d17305f2c23ba25425089487 to c82646a9948757fd4ae193cd4379565e4c275d52

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

670146balmost all doctests working, some pyscipopt patches
cfbbdb1getParam and setParam working
9d66f70all methods implemented in backend; all doctests working
2b6efc9one more patch
d246de5pyscipopt: update to v1.4.3
b431129pyscipopt: update to v1.4.4
1f9050dscip-backend: added '# optional - pyscipopt'
95890afquicksum and modify doctests
6c7d9c9remove all patches
c82646achange 4 back to 9

comment:40 Changed 10 months ago by moritz

  • Reviewers set to Moritz Firsching
  • Status changed from needs_work to needs_review

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

comment:41 Changed 10 months ago by vdelecroix

  • Status changed from needs_review to needs_work

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).

comment:42 Changed 10 months ago by vdelecroix

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

comment:43 follow-up: Changed 10 months ago by 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..

comment:44 Changed 10 months ago by 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
Last edited 10 months ago by vdelecroix (previous) (diff)

comment:45 in reply to: ↑ 43 ; follow-up: Changed 10 months ago by 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!

comment:46 in reply to: ↑ 45 Changed 10 months ago by 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

comment:47 Changed 10 months ago by 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.

comment:48 Changed 10 months ago by 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.

comment:49 Changed 10 months ago by git

  • Commit changed from c82646a9948757fd4ae193cd4379565e4c275d52 to 31e0d1fec4e8547f0d2c08e4932b39c21d788508

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

c3bc320getParam and setParam working
c4c3680all methods implemented in backend; all doctests working
d3aa9d0one more patch
e9f531epyscipopt: update to v1.4.3
0a07d61pyscipopt: update to v1.4.4
de6b1bfscip-backend: added '# optional - pyscipopt'
fba294aquicksum and modify doctests
4aadef8remove all patches
94fac2dchange 4 back to 9
31e0d1frebased and Vincent's suggestions

comment:50 Changed 10 months ago by git

  • Commit changed from 31e0d1fec4e8547f0d2c08e4932b39c21d788508 to c0b432c427236c07f76f930a156a15d3f33eb1f1

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

c0b432ccorrect linebreaks

comment:51 Changed 10 months ago by moritz

  • Status changed from needs_work to needs_review

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

comment:52 follow-up: Changed 9 months ago by vdelecroix

  • Milestone changed from sage-8.2 to sage-8.3
  • Reviewers changed from Moritz Firsching to Moritz Firsching, Vincent Delecroix
  • Status changed from needs_review to needs_work

merge conflicts

comment:53 Changed 9 months ago by 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

comment:54 Changed 9 months ago by 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.

comment:55 Changed 9 months ago by vdelecroix

Alignment does not matter. But there should be backslashes.

comment:56 Changed 9 months ago by git

  • Commit changed from c0b432c427236c07f76f930a156a15d3f33eb1f1 to c07eb7ed461c58b1c353c7518566a1c7e7ec7e35

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

3c7d354all methods implemented in backend; all doctests working
e9095b7one more patch
f33a55epyscipopt: update to v1.4.3
99c5010pyscipopt: update to v1.4.4
78ef11dscip-backend: added '# optional - pyscipopt'
e59e041quicksum and modify doctests
24ca41dremove all patches
d627bcdchange 4 back to 9
10913f8rebased and Vincent's suggestions
c07eb7ecorrect linebreaks

comment:57 in reply to: ↑ 52 ; follow-up: Changed 9 months ago by moritz

  • Status changed from needs_work to needs_review

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..

comment:58 in reply to: ↑ 57 Changed 9 months ago by 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!

comment:59 follow-up: Changed 9 months ago by 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.

comment:60 Changed 9 months ago by vdelecroix

  • Status changed from needs_review to needs_info

comment:61 in reply to: ↑ 59 ; follow-ups: Changed 9 months ago by 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.

comment:62 in reply to: ↑ 61 Changed 9 months ago by 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.

comment:63 in reply to: ↑ 61 Changed 9 months ago by 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.

comment:64 Changed 9 months ago by git

  • Commit changed from c07eb7ed461c58b1c353c7518566a1c7e7ec7e35 to ae0bab040a3b6d0cb77c5593bf486242365621f6

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

0e30ccapyscipopt: update to v1.4.3
7e112c8pyscipopt: update to v1.4.4
d1519b9scip-backend: added '# optional - pyscipopt'
901f8cfquicksum and modify doctests
8fc35cfremove all patches
32884a0change 4 back to 9
0ef22c6rebased and Vincent's suggestions
d23ed3ecorrect linebreaks
1cefe04towards uncythening the scip backend
ae0bab0decythonizing finished

comment:65 Changed 7 months ago by mkoeppe

Another update to SCIPoptsuite 6.0 is due

comment:66 Changed 7 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

milestone update 8.3 -> 8.4

Note: See TracTickets for help on using tickets.