SCIPBackend: Faster copy, remove_constraint methods

[mkoeppe]

(from #21003 comment:142)

Depends on #21003

CC: @mantepse @dimpase

Component: linear programming

Author: Matthias Koeppe

Reviewer: Martin Rubey, ...

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

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

Branch: u/mkoeppe/scipbackend__faster_copy_method

[mkoeppe]

Last 10 new commits:

b33be26	src/sage/graphs/graph_decompositions/vertex_separation.pyx: Factor out _vertex_separation_MILP_formulation
4104322	src/sage/numerical/backends/scip_backend.pyx: Store pyscipopt variables by index
fe72aa5	src/sage/graphs/graph_decompositions/vertex_separation.pyx: Add pyscipopt test
b6242d2	src/sage/numerical/backends/scip_backend.pyx: Mark sage.doctest: optional - pyscipopt
7b19413	src/sage/numerical/backends/scip_backend.pyx: Fix docstring blocks, break some long lines
01d4cdc	Merge tag '9.8.beta6' into t/21003/pyscipopt
2040546	src/sage/numerical/backends/scip_backend.pyx: Fix copying variable types
099c15b	src/sage/numerical/backends/scip_backend.pyx: Cache constraints to avoid expensive calls to getConss
48cf104	Merge #21003
953198e	SCIPBackend.__copy__: Use Model(sourceModel=...) for copying

[mkoeppe]

Commit: 953198e

[mkoeppe]

comment:5

Just 1 commit on top of #21003

[sagetrac-git]

Changed commit from 953198e to 81ea51c

[sagetrac-git]

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

89e5778	GenericBackend.remove_constraints: Fix handling of int
38a33e0	SCIPBackend.nrows: Use model.getNConss if constraints are not cached
81ea51c	SCIPBackend.remove_constraints: New, override generic implementation

[mantepse]

comment:9

When creating a constraint, then copying the MILP, and then adding the constraint to the copied MILP, I sometimes get errors as follows:

      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 1956, in _find_counter_example
        solution = next(bmilp.solutions_iterator(on_blocks, tmp_constraints))
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 2676, in solutions_iterator
        bmilp.add_constraint(constraint, return_indices=True)
      File "sage/numerical/mip.pyx", line 2199, in sage.numerical.mip.MixedIntegerLinearProgram.add_constraint
        new_indices = self.add_constraint(lhs-rhs, max=0,
      File "sage/numerical/mip.pyx", line 2175, in sage.numerical.mip.MixedIntegerLinearProgram.add_constraint
        self._backend.add_linear_constraint(constraint.items(), min, max, name)
      File "sage/numerical/backends/scip_backend.pyx", line 410, in sage.numerical.backends.scip_backend.SCIPBackend.add_linear_constraint
        linfun = quicksum([v * mvars[c] for c, v in coefficients])
    IndexError: list index out of range

Maybe something like copy_for_mip is needed also for constraints?

[mkoeppe]

comment:10

are you passing tmp_constraints coming from one MIP to another?

[mantepse]

comment:11

yes, as I wrote.

[sagetrac-git]

Changed commit from 81ea51c to 5e6ad56

[sagetrac-git]

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

5e6ad56

SCIPBackend.__copy__: Use origcopy=True

[mkoeppe]

comment:13

Please check if this fixes it

[mantepse]

comment:14

Yes, this makes it look good.

[mkoeppe]

comment:15

Thanks for testing!

[mantepse]

Reviewer: Martin Rubey, ...

[mantepse]

comment:17

I think I should mention that copying is still a bit slower than adding and removing constraints, apparently, no matter whether I use SCIP or GLPK.

However, it seems that this is only relevant for extremely small problems, usually almost all time is spent in the solver itself.

Running all tests with SCIP without copying takes about 4.2 seconds, with copying it is about 4.9 seconds. Including the long tests, I get about 56 seconds either way.

(GLPK: with and without copying 2.4 seconds, including long tests 73 seconds)

Besides, it might make sense to have a method add_constraints, analogous to remove_constraints, this would save another 2 lines of code :-)

[mkoeppe]

comment:18

Thanks for these benchmarks with #33238. These timings suggest that we have been successful in removing the artificial slowdowns in remove_constraints.

Not sure about add_constraints. As add_constraint already accepts vector-valued constraints (via LinearTensor, LinearTensorConstraint), perhaps it could just be generalized to also accept lists in such places.

[mantepse]

comment:19

Is there any real difference between vector valued constraints and lists of constraints?

[mkoeppe]

comment:20

No. In the end, everything is a matrix

[mantepse]

comment:21

OK. In any case, it is confusing that we have two methods for removing constraints but only one to add constraints.

[mkoeppe]

comment:22

We could introduce add_constraints as an alias of add_constraint after extending the accepted inputs as per comment:18

[mantepse]

comment:23

I guess, for remove_constraints you have done this already?

[mkoeppe]

comment:24

No, here on the ticket this is a fix for the backend method remove_constraints.

[mkoeppe]

comment:25

I've opened #34896 for these changes to the frontend

[mkoeppe]

Removed branch from issue description; replaced by PR #35103