MixedIntegerLinearProgram.add_constraint: Option to return row indices, fix handling of empty constraints

[mkoeppe]

(from #21003 comment:136)

... for use with methods that take row indices as input, such as row, row_bounds, remove_constraint.

If a backend does not map a constraint to a unique new row (or check_redundant=True and the constraint is discarded by the frontend), the method may return None.

We also fix a longstanding bug in how empty constraints are handled in add_constraint.

The changed interface (an optional return value) is backward-compatible with user code.

We also add a Feature CVXOPT so that the backend gets tested again.

CC: @mantepse @dimpase

Component: linear programming

Author: Matthias Koeppe, Martin Rubey

Branch/Commit: 3b929f8

Reviewer: Martin Rubey, Matthias Koeppe

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

[mkoeppe]

Branch: u/mkoeppe/mixedintegerlinearprogram_add_constraint__return_row_index

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

comment:2

Doctests need adjusting because of the extra output

---

New commits:

7ad324f

MixedIntegerLinearProgram.add_constraint: Return row index

[mkoeppe]

Commit: 7ad324f

[sagetrac-git]

Changed commit from 7ad324f to 9daa44c

[sagetrac-git]

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

9daa44c

src/sage/numerical/mip.pyx: Update doctests for .add_constraint returning the row index

[sagetrac-git]

Changed commit from 9daa44c to e154d29

[sagetrac-git]

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

bc01716	MixedIntegerLinearProgram.add_constraint: Do not refuse to add empty constraints; they could be infeasible or we may need their row index for later
e154d29	src/sage/numerical/backends: Update doctests

[sagetrac-git]

Changed commit from e154d29 to 8adca04

[sagetrac-git]

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

166b1d3	src/sage/numerical/backends/cvxopt_backend.pyx: Update doctests
8adca04	src/sage/features/mip_backends.py: Add CVXOPT feature

[mantepse]

comment:8

I'm sorry to comment late. I have two (quite orthogonal) suggestions:

• I think that add_constraint should return a list of constraints added, or None.
  • None should be returned if and only if the backend does not provide a means to remove this constraint again.
  • The empty list should be returned if and only if the constraint was redundant.
  • Otherwise, removing the constraints using remove_constraint yields the original MILP.
• possibly, it would make sense to return this list only on demand, eg., have a flag return_indices. I am guessing that this would be better for interactive use, and it also means that only very few doctests would have to be modified.

[mkoeppe]

comment:9

That would be fine with me. Do you want to push a branch that does this?

[mantepse]

comment:10

Yes, I can do this.

[mantepse]

Changed branch from u/mkoeppe/mixedintegerlinearprogram_add_constraint__return_row_index to u/mantepse/mixedintegerlinearprogram_add_constraint__return_row_index

[sagetrac-git]

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

cfe24fe

add a doctest for adding and removing constraints

[sagetrac-git]

Changed commit from 8adca04 to cfe24fe

[sagetrac-git]

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

6c34bc3

make linter happy

[sagetrac-git]

Changed commit from cfe24fe to 6c34bc3

[sagetrac-git]

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

3b929f8

forgot newline in docstring

[sagetrac-git]

Changed commit from 6c34bc3 to 3b929f8

[mantepse]

comment:15

Please review!

In particular, whether

        The row indices of the constraints added, if
        ``return_indices`` is true and the backend guarantees that
        removing them again yields the original MIP, ``None``
        otherwise.

is correct, i.e., there are currently no backends that do anything bad.

[mantepse]

Reviewer: Martin Rubey, Matthias Koeppe

[mantepse]

Changed author from Matthias Koeppe to Matthias Koeppe, Martin Rubey

[mkoeppe]

comment:17

LGTM, thanks!

[mantepse]

comment:20

Thank you!

Actually, it would be practical if the following too would also work, don't you think (Ideally also with False, or True as argument)?

If you agree, it won't be hard to fix. I don't know whether one can add these as constraints to all backends, but we could simply ignore the first and raise a MIPSolverException for the second.

This would make (my) user code much more readable.

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.add_constraint(p.linear_functions_parent()(0 <= 0))
ValueError                                Traceback (most recent call last)
...
ValueError: at least one of "max" or "min" must be set

sage: p.add_constraint(p.linear_functions_parent()(1 <= 0))
ValueError                                Traceback (most recent call last)
...
ValueError: at least one of "max" or "min" must be set

[mkoeppe]

comment:21

You probably mean linear_constraints_parent here

[mkoeppe]

comment:22

It would be OK with me for

• p.add_constraint(True) to add the trivial constraint "0 <= 0"
• p.add_constraint(False) to add the infeasible constraint "0 <= -1"

[mantepse]

comment:23

Oh, thanks, yes, you are right. Here we currently have

sage: p.add_constraint(p.linear_constraints_parent()(1 <= 0))
sage: p
Mixed Integer Program (no objective, 0 variables, 0 constraints)
sage: p.show()
Maximization:
  

Constraints:
Variables:
sage: p.linear_constraints_parent()(1 <= 0)
trivial constraint starting with 0
sage: p.linear_constraints_parent()(0 <= 0)
trivial constraint starting with 1

[mkoeppe]

comment:24

"trivial constraint starting with" is, of course, ridiculous wording. We should revise this.

[mantepse]

comment:25

I am away for a few hours now :-)

[mkoeppe]

comment:26

I've opened #34882 for this.

[mantepse]

comment:27

Thanks! However, I think the other two are bugs and should be fixed here.

[mkoeppe]

comment:28

Which two?

[mkoeppe]

comment:29

Note that there's the coercion route bool -> int -> ZZ

[mantepse]

comment:30

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.add_constraint(p.linear_constraints_parent()(1 <= 0))
sage: p.solve()
0.0

because it is actually not adding a constraint.

[mkoeppe]

comment:31

that's bool -> int -> ZZ -> linear_function_parent -> linear_constraints_parent, not a bug

[mkoeppe]

comment:32

-> #34882

[mantepse]

comment:33

The problem is that for f = p.linear_constraints_parent()(1 <= 0) we have neither have f.equations() nor f.inequalities().

The following does work (also for GLPK):

sage: p = MixedIntegerLinearProgram(solver='SCIP')
sage: f = p.linear_functions_parent()(1 - 0)
sage: p.add_constraint(f, max=0, return_indices=True)
[0]
sage: p.show()
Maximization:
  

Constraints:
  c1: <= -1.0
Variables:

I am not sure how reliable this is. Also, shouldn't the max be shown?

[mantepse]

comment:34

Ah, sorry, now I see. Sorry.

[mkoeppe]

comment:35

I agree that changing the display of the empty linear form in " <= -1.0" to 0 would be an improvement

[mantepse]

comment:36

So actually we should also try to do something sensible with p.linear_constraints_parent()(False).

[vbraun]

Changed branch from u/mantepse/mixedintegerlinearprogram_add_constraint__return_row_index to 3b929f8