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

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,3 +4,7 @@
 
 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 (a return value) is backward-compatible with user code, but lots of doctests need to be changed. To make sure that also CVXOPT backend is tested when cvxopt is installed, we add it as a 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