Add package pyscipopt, add MIP backend

[mkoeppe]

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

https://github.com/scipopt/PySCIPOpt

Branch is on top of #31329.

Steps to get it to work:

• pull from this branch
• sage -f pyscipopt

Depends on #31329

CC: @mo271 @yuan-zhou @malb @dcoudert @dimpase

Component: linear programming

Keywords: days84, IMA-PolyGeom

Author: Matthias Koeppe, Moritz Firsching, Martin Rubey

Branch/Commit: 099c15b

Reviewer: Moritz Firsching, Vincent Delecroix, David Coudert, Matthias Koeppe

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

[mkoeppe]

Changed dependencies from #10879 to #21094

[mkoeppe]

Branch: u/mkoeppe/pyscipopt

[sagetrac-git]

Commit: db1b1d9

[sagetrac-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

[sagetrac-git]

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

805a034

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

[sagetrac-git]

Changed commit from db1b1d9 to 805a034

[sagetrac-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

[sagetrac-git]

Changed commit from 805a034 to d3271c0

[sagetrac-git]

Changed commit from d3271c0 to 41b70bb

[sagetrac-git]

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

41b70bb

PySCIPOpt: Install from git

[videlec]

Changed keywords from none to days84

[mkoeppe]

Author: Matthias Koeppe, needs more authors

[sagetrac-git]

Changed commit from 41b70bb to d973980

[sagetrac-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

[mkoeppe]

Changed dependencies from #21094 to #22557

[sagetrac-git]

Changed commit from d973980 to 9794b3a

[sagetrac-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

[mo271]

Changed dependencies from #22557 to #22557, #24662

[mo271]

Changed branch from u/mkoeppe/pyscipopt to u/moritz/pyscipopt

[mo271]

Changed commit from 9794b3a to f260221

[mantepse]

comment:132

I hope that this is not too off topic here - please let me provide background on why I am copying MILPS:

In #33238, I need to solve a program with temporarily added constraints. In principle, I see two options for doing this:

1. copy the MILP, add the new constraints to the copy, solve, throw away the copy

2. add the constraints, solve, remove the constraints

Currently, I am doing 1., because I am afraid that I cannot control what happens when adding a constraint. In particular, a clever solver might detect that it is redundant, or an even more intelligent solver might rewrite the whole list of constraints. Possibly I could check whether my new constraint wasn't added at all, but could a complete rewrite of a program happen in theory?

[mkoeppe]

comment:133

Replying to Martin Rubey:

In #33238, I need to solve a program with temporarily added constraints. In principle, I see two options for doing this:

1. copy the MILP, add the new constraints to the copy, solve, throw away the copy

2. add the constraints, solve, remove the constraints

Currently, I am doing 1., because I am afraid that I cannot control what happens when adding a constraint.

Removing constraints is supported by our frontend and backend interfaces and by the SCIP API.

In particular, a clever solver might detect that it is redundant, or an even more intelligent solver might rewrite the whole list of constraints.

There's no need to worry about this. Working with dynamically modified models is a very typical operation in IP solvers, that includes delete constraints. See SCIPdelCons https://github.com/scipopt/PySCIPOpt/blob/master/src/pyscipopt/scip.pyx#L3104

[mantepse]

comment:134

Are you saying that it is very hard to imagine a solver that rewrites the constraints upon solving?

I would prefer that my code works generically, and not just specifically for SCIP.

Also, I don't really have any means to identify a constraint, except by index. I admit it may be silly, but in principle I do not even know whether my solver adds a constraint at the beginning or at the end.

[mkoeppe]

comment:135

Solvers do this kind of rewriting internally but do not expose it to the user. The API functions are there to be actually used.

[mkoeppe]

comment:136

Replying to Martin Rubey:

Also, I don't really have any means to identify a constraint, except by index. I admit it may be silly, but in principle I do not even know whether my solver adds a constraint at the beginning or at the end.

Yes, that's a valid concern. Our MIP frontend and backend interfaces are unfortunately underdeveloped and underdocumented. While the backend method add_variable returns a backend variable index, the method add_linear_constraint does not return anything, which leaves the user to make assumptions about constraint indices in methods that take row indices as input, such as row, row_bounds, remove_constraint.

[mkoeppe]

comment:137

That said, it's OK to assume that the constraint is added at the end.

[dimpase]

comment:138

different solvers do it differently. Some are doing some kind of postprocessing, and so the problem as held by the backend might be different (but equivalent)

[mantepse]

comment:139

Here is a patch. With this patch SCIP does the problem in roughly 2/3 of the time, which is quite OK. I don't have gurobi installed right now.

Could you please check and commit it - provided it is OK - on my behalf?

diff --git a/src/sage/numerical/backends/scip_backend.pxd b/src/sage/numerical/backends/scip_backend.pxd
index b919fe4c223..dc4981a89c3 100644
--- a/src/sage/numerical/backends/scip_backend.pxd
+++ b/src/sage/numerical/backends/scip_backend.pxd
@@ -14,6 +14,7 @@ cdef class SCIPBackend(GenericBackend):
 
     cdef model
     cdef object variables
+    cdef object constraints
 
     cpdef _get_model(self)
     cpdef get_row_prim(self, int i)
diff --git a/src/sage/numerical/backends/scip_backend.pyx b/src/sage/numerical/backends/scip_backend.pyx
index d063d012b98..b2ecf0f923b 100644
--- a/src/sage/numerical/backends/scip_backend.pyx
+++ b/src/sage/numerical/backends/scip_backend.pyx
@@ -60,6 +60,16 @@ cdef class SCIPBackend(GenericBackend):
         self.obj_constant_term = 0.0
         self.variables = []
         self.model.hideOutput()
+        # always set this to None if the list of constraints may change
+        self.constraints = None
+
+    def get_constraints(self):
+        """
+        Get all constraints of the problem.
+        """
+        if self.constraints is None:
+            self.constraints = self.model.getConss()
+        return self.constraints
 
     cpdef _get_model(self):
         """
@@ -360,7 +370,9 @@ cdef class SCIPBackend(GenericBackend):
             raise ValueError("The constraint's index i must satisfy 0 <= i < number_of_constraints")
         if self.model.getStatus() != 'unknown':
             self.model.freeTransform()
-        self.model.delCons(self.model.getConss()[i])
+            self.constraints = None
+        self.model.delCons(self.get_constraints()[i])
+        self.constraints = None
 
     cpdef add_linear_constraint(self, coefficients, lower_bound, upper_bound, name=None):
         """
@@ -408,6 +420,7 @@ cdef class SCIPBackend(GenericBackend):
 
         cons = lower_bound <= (linfun <= upper_bound)
         self.model.addCons(cons, name=name)
+        self.constraints = None
 
     cpdef row(self, int index):
         r"""
@@ -438,7 +451,7 @@ cdef class SCIPBackend(GenericBackend):
             (2.0, 2.0)
         """
         namedvars = [var.name for var in self.variables]
-        valslinear = self.model.getValsLinear(self.model.getConss()[index])
+        valslinear = self.model.getValsLinear(self.get_constraints()[index])
         cdef list indices = []
         cdef list values = []
         for var, coeff in valslinear.iteritems():
@@ -470,7 +483,7 @@ cdef class SCIPBackend(GenericBackend):
             sage: p.row_bounds(0)
             (2.0, 2.0)
         """
-        cons = self.model.getConss()[index]
+        cons = self.get_constraints()[index]
         lhs = self.model.getLhs(cons)
         rhs = self.model.getRhs(cons)
         if lhs == -self.model.infinity():
@@ -548,7 +561,8 @@ cdef class SCIPBackend(GenericBackend):
             sage: p.nrows()
             5
         """
-        mcons = self.model.getConss()
+        mcons = self.get_constraints()
+        self.constraints = None  # is this necessary?
         # after update of
         index = self.add_variable(lower_bound=-self.model.infinity())
         var = self.variables[index]
@@ -770,7 +784,7 @@ cdef class SCIPBackend(GenericBackend):
             sage: lp.get_row_prim(2)
             8.0
         """
-        return self.model.getActivity(self.model.getConss()[i])
+        return self.model.getActivity(self.get_constraints()[i])
 
     cpdef int ncols(self):
         """
@@ -803,7 +817,7 @@ cdef class SCIPBackend(GenericBackend):
             sage: p.nrows()
             2
         """
-        return len(self.model.getConss())
+        return len(self.get_constraints())
 
     cpdef col_name(self, int index):
         """
@@ -840,7 +854,7 @@ cdef class SCIPBackend(GenericBackend):
             sage: p.row_name(0)
             'Empty constraint 1'
         """
-        return self.model.getConss()[index].name
+        return self.get_constraints()[index].name
 
     cpdef bint is_variable_binary(self, int index):
         """
@@ -1148,7 +1162,7 @@ cdef class SCIPBackend(GenericBackend):
         cdef SCIPBackend cp = type(self)(maximization=self.is_maximization())
         cp.problem_name(self.problem_name())
         for i, v in enumerate(self.variables):
-            vtype = v.vtype
+            vtype = v.vtype()
             cp.add_variable(self.variable_lower_bound(i),
                             self.variable_upper_bound(i),
                             binary=vtype == 'BINARY',
@@ -1159,10 +1173,13 @@ cdef class SCIPBackend(GenericBackend):
         assert self.ncols() == cp.ncols()
 
         for i in range(self.nrows()):
-            cp.add_linear_constraint(zip(*self.row(i)),
-                                     self.row_bounds(i)[0],
-                                     self.row_bounds(i)[1],
-                                     name=self.row_name(i))
+            coefficients = zip(*self.row(i))
+            lower_bound, upper_bound = self.row_bounds(i)
+            name = self.row_name(i)
+            cp.add_linear_constraint(coefficients,
+                                     lower_bound,
+                                     upper_bound,
+                                     name=name)
         assert self.nrows() == cp.nrows()
         return cp

[mantepse]

comment:140

It might indeed be faster to add and remove constraints, because I am doing a lot of this. However, comment:138 seems to contradict comment:137 and comment:135.

So maybe we could have some kind of flag telling us whether a solver does rewrite constraints or not?

[mkoeppe]

comment:141

I recommend that in your code you wrap your use of add_constraint with a check that exactly one constraint is added - just to document this assumption (which you are allowed to make).

[mkoeppe]

comment:142

Also, __copy__ can likely be improved by using Model(sourceModel=...) instead of manually transferring variables and constraints - see https://github.com/scipopt/PySCIPOpt/blob/master/src/pyscipopt/scip.pyx#L939

[mantepse]

comment:143

Well, there is another thing with adding and removing: removing will - with the patch above - unnecessarily recompute the list of constraints again. If I additionally check that adding the constraint also increases the number of constraints by one, then I have this overhead twice.

It's a bit strange that the backend needs the constraint to remove it, whereas in sage we need the index.

That said, replacing copy with adding/removing constraints makes a HUGE difference for this problem, roughly a factor of 8!

I won't be able to improve __copy__ right now, but I'd appreciate improvements.

[mkoeppe]

comment:144

Replying to Matthias Köppe:

Replying to Martin Rubey:

Also, I don't really have any means to identify a constraint, except by index. I admit it may be silly, but in principle I do not even know whether my solver adds a constraint at the beginning or at the end.

Yes, that's a valid concern. Our MIP frontend and backend interfaces are unfortunately underdeveloped and underdocumented. While the backend method add_variable returns a backend variable index, the method add_linear_constraint does not return anything, which leaves the user to make assumptions about constraint indices in methods that take row indices as input, such as row, row_bounds, remove_constraint.

I've opened #34878 for an API improvement

[mantepse]

comment:145

I tried to understand why .show() has different variable names. Here is what I currently have:

sage: p = MixedIntegerLinearProgram(solver="GLPK")
sage: p.new_variable()[0]
x_0
sage: b = p.get_backend()
sage: b.col_name(0)
''
sage: p = MixedIntegerLinearProgram(solver="SCIP")
sage: p.new_variable()[0]
x_0
sage: b = p.get_backend()
sage: b.col_name(0)
'x1'

is there a good reason for that?

[mkoeppe]

comment:146

Either SCIP itself or PySCIPOpt is inventing these variable names, I think

[mantepse]

comment:147

Indeed local/lib/python3.10/site-packages/pyscipopt/scip.pyx, line 1413-:

    def addVar(self, name='', vtype='C', lb=0.0, ub=None, obj=0.0, pricedVar = False):
        ...
        # replace empty name with generic one
        if name == '':
            name = 'x'+str(SCIPgetNVars(self._scip)+1)

[sagetrac-git]

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

099c15b

src/sage/numerical/backends/scip_backend.pyx: Cache constraints to avoid expensive calls to getConss

[sagetrac-git]

Changed commit from 2040546 to 099c15b

[mkoeppe]

Changed author from Matthias Koeppe, Moritz Firsching to Matthias Koeppe, Moritz Firsching, Martin Rubey

[mkoeppe]

Changed reviewer from Moritz Firsching, Vincent Delecroix, David Coudert to Moritz Firsching, Vincent Delecroix, David Coudert, Matthias Koeppe

[mkoeppe]

comment:151

Replying to Matthias Köppe:

__copy__ can likely be improved by using Model(sourceModel=...) instead of manually transferring variables and constraints - see https://github.com/scipopt/PySCIPOpt/blob/master/src/pyscipopt/scip.pyx#L939

That's now #34890

[vbraun]

Changed branch from u/mkoeppe/pyscipopt to 099c15b