InteractiveLPProblem, dictionaries: add_constraint / add_row methods

[mkoeppe]

This ticket adds add_constraint and add_row methods.
Following the suggestion at
#18805 comment:27
these methods create new problems / dictionaries, leaving the original ones unmodified.

(Split out from the larger ticket #18805.)

Depends on #20500

CC: @novoselt @pgxiao

Component: linear programming

Author: Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev

Branch/Commit: c8559f3

Reviewer: Andrey Novoseltsev

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

[mkoeppe]

Branch: u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[mkoeppe]

Commit: 5849980

[mkoeppe]

New commits:

d6ee048	Refactor leaving_coefficients in terms of new method row_coefficients
3cbdeef	Fixup
db52d0e	Add @abstract_method methods to LPAbstractDictionary
4e9955e	Refactor entering_coefficients in terms of new method column_coefficients
a382ec1	Fix documentation
b292e63	Merge branch 't/20500/lpabstractdictionary__refactor_leaving_coefficients__entering_coefficients_using_new_methods_row_coefficients__column_coefficients' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
5849980	InteractiveLPProblem, dictionaries: add_constraint / add_row methods

[mkoeppe]

Dependencies: #20500

[sagetrac-git]

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

639865c	Merge tag '7.2.rc1' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
f5b3900	add_row: Use @abstract_method

[sagetrac-git]

Changed commit from 5849980 to f5b3900

[sagetrac-git]

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

f9c5448

fixup

[sagetrac-git]

Changed commit from f5b3900 to f9c5448

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

Work Issues: rebasing

[sagetrac-git]

Changed commit from f9c5448 to 2d444bc

[sagetrac-git]

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

d9a6356	InteractiveLPProblem, dictionaries: add_constraint / add_row methods
77e0a00	add_row: Use @abstract_method
2d444bc	fixup

[mkoeppe]

comment:8

Rebased on 7.3.beta0

[mkoeppe]

comment:9

ping?

[novoselt]

comment:10

1. "a 1 by n matrix of the new constraint coefficients" is a bit weird, especially since examples show using a list rather than a matrix. I'd write just "coefficients of the new constraint"
2. new_row does not reflect very well the meaning, how about coefficients?..
3. I think the method for adding constraints should not do input check that can be done by the problem constructor - it will reduce code duplication and lead to more uniform error messages.
4. When constructing a new problem, as much of the old one as possible should be preserved. The current version does not keep even the type of the problem!!!
5. It should not be necessary to explicitly name a new slack variable.
6. It would be better not to construct polynomial rings where variables leave directly - leave it to the constructor of the problem in case we want to do something else later.
7. I don't think that add_row should be supported by abstract dictionaries - for the current revised dictionaries I'd say it is confusing what does it even mean. And the convoluted code to achieve it agrees with me ;-) Rather I'd suggest having it for regular dictionaries (perhaps add_relation would be a better name). For the revised ones add_constraint, the same as for the problem with more or less the same parameters, would make more sense - since revised dictionaries are linked to the problem, they can construct the new one and then based on it construct a new suitable dictionary.

[mkoeppe]

comment:11

Just a quick reply to point 7:

Replying to @novoselt:

7. I don't think that add_row should be supported by abstract dictionaries - for the current revised dictionaries I'd say it is confusing what does it even mean. And the convoluted code to achieve it agrees with me ;-) Rather I'd suggest having it for regular dictionaries (perhaps add_relation would be a better name). For the revised ones add_constraint, the same as for the problem with more or less the same parameters, would make more sense - since revised dictionaries are linked to the problem, they can construct the new one and then based on it construct a new suitable dictionary.

No, no, it's crucial that add_row is supported by abstract dictionaries.
The whole point is to have a method that adds a row to the dictionary, no matter how the dictionary is internally represented. This is the operation needed by tableau cutting plane procedures.
In the revised dictionary, one needs to do this kind of transformation to compute the new row of the problem, which gives the desired tableau row. (This is how tableau cutting planes are actually implemented in numerical solvers.)

[mkoeppe]

comment:12

Replying to @novoselt:

5. It should not be necessary to explicitly name a new slack variable.

Agreed, this argument should be optional; and a name should be generated if it is not provided.

[mkoeppe]

comment:13

Replying to @novoselt:

6. It would be better not to construct polynomial rings where variables leave directly - leave it to the constructor of the problem in case we want to do something else later.

What do you mean by "where variables leave"?

[pgxiao]

Changed branch from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[pgxiao]

New commits:

b292e63	Merge branch 't/20500/lpabstractdictionary__refactor_leaving_coefficients__entering_coefficients_using_new_methods_row_coefficients__column_coefficients' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
5849980	InteractiveLPProblem, dictionaries: add_constraint / add_row methods
639865c	Merge tag '7.2.rc1' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
f5b3900	add_row: Use @abstract_method
f9c5448	fixup
119c8c6	Rewording
d7d809b	The argument for new slack variable is optional
f73fc57	Preserve information when construct a new problem

[mkoeppe]

Changed branch from u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[pgxiao]

Changed branch from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[pgxiao]

New commits:

b7d61fc	InteractiveLPProblem, dictionaries: add_constraint / add_row methods
34f22ab	add_row: Use @abstract_method
1d73925	fixup
56d4a14	Rewording
206d5ca	Preserve information when construct a new problem
e3d934b	The argument for new slack variable is optional

[pgxiao]

Changed commit from f73fc57 to e3d934b

[novoselt]

comment:27

7 is retracted, 3 and 6 still stand. And I wanted to look closer and do some changes but was not able to checkout due to trac problems...

[mkoeppe]

Changed branch from u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[mkoeppe]

Changed author from Peijun Xiao to Peijun Xiao, Matthias Koeppe

[mkoeppe]

Changed work issues from rebasing to none

[mkoeppe]

comment:29

I've made some changes that address points 3 and 6.
Also rebased on latest beta.
Ready for review.

---

New commits:

1a931dd	InteractiveLPProblem, dictionaries: add_constraint / add_row methods
f525960	add_row: Use @abstract_method
e5925a7	fixup
6f41037	Rewording
e6404ab	Preserve information when construct a new problem
6cb5622	The argument for new slack variable is optional
a8af968	Simplify code, don't create unnecessary rings
6d5f861	add_row methods: Rename slack_variable to basic_variable, new_b to constant
7c93d94	add_constraint: Delegate error checking to constructor

[mkoeppe]

Changed commit from e3d934b to 7c93d94

[novoselt]

Changed branch from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/novoselt/interactivelpproblem__dictionaries__add_constraint___add_row_methods

[novoselt]

comment:31

Going carefully doing some tweaks, not done yet, but have to stop for the moment.

• I thought it is clear that if new_ prefix is not great for one argument, it is not great for another ;-)
• There were still some data of problems not preserved, I think everything that can be preserved should be.
• a number of the constant term for the new row?..
• Explicit hard-coded ring LPDictionary(matrix(QQ, A)?!?!?!

---

New commits:

92f4868

Reviewer tweaks, part 1.

[novoselt]

Changed commit from 7c93d94 to 92f4868

[mkoeppe]

comment:32

Thanks for fixing these.

[sagetrac-git]

Changed commit from 92f4868 to a931471

[sagetrac-git]

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

9847157	Merge branch 'develop' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
a931471	Reviewer's rewrite of add_row methods for dictionaries

[novoselt]

comment:34

With all due respect the old code for add_row for revised dictionaries was incomprehensible and extremely unnecessary complicated.

The current code will probably break on a dictionary for an auxiliary problem - is there any point in properly supporting these or there is never a need to add rows there and we can just throw an exception?

Documentation of add_row and row_coefficients needs some clarification with respect to signs (since I got confused and presumably some poor students may get as well). How about something like These are the coefficients with which nonbasic variables are subtracted in the relation of this basic variable. ?

[novoselt]

Changed author from Peijun Xiao, Matthias Koeppe to Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev

[sagetrac-git]

Changed commit from a931471 to c8559f3

[sagetrac-git]

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

6a5998f	Add consistency check for adding a row to the auxiliary problem
c8559f3	Clarify the sign of row coefficients.

[novoselt]

comment:36

After some more thinking, it is perfectly fine to add rows to auxiliary problems with this code, but there is a constraint on input.

If you are OK with my changes, set to positive review.

[pgxiao]

comment:37

Thank you for your work! They look fine.

[vbraun]

Changed branch from u/novoselt/interactivelpproblem__dictionaries__add_constraint___add_row_methods to c8559f3