InteractiveLPProblem, dictionaries: add_constraint / add_row methods

[mkoeppe]

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

(Split out from the larger ticket #18805.)

[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

[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

[git]

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

​f9c5448

fixup

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

Rebased on 7.3.beta0

[mkoeppe]

ping?

[novoselt]

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]

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]

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]

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"?

[git]

Branch pushed to git repo; I updated commit sha1. 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

[pjxiao]

I fixed the problems your comments 1, 2, 4, and 5.

Replying to novoselt:

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?..

...

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.

Please take a look at the last three commits listed in comment:15.

Thanks!

[novoselt]

Replying to mkoeppe:

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.)

OK, let's have it, but I still find the name confusing - can it be add_relation? While for the revised dictionaries it will add a row to the only of the two tables that can get an extra row, data there will not be the provided coefficients. Hence I'd like something more conceptual than layout reference.

[novoselt]

Replying to mkoeppe:

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"?

Sorry, I meant "where variables live" - I am not a native speaker ;-)

[novoselt]

I can no longer see cumulative changes, please rebase!

[mkoeppe]

rebased on 7.2.beta3

---

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

[mkoeppe]

Replying to novoselt:

Replying to mkoeppe:

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.)

OK, let's have it, but I still find the name confusing - can it be add_relation? While for the revised dictionaries it will add a row to the only of the two tables that can get an extra row, data there will not be the provided coefficients. Hence I'd like something more conceptual than layout reference.

"add_relation" wouldn't express the operation well; because we're not just adding a relation but also a new basic variable. I've never heard anyone call this operation other than "adding a row" (whether it's a textbook dictionary or a revised dictionary). Also note that "row" matches the method row_coefficients.

[pjxiao]

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

[pjxiao]

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

[novoselt]

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]

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

[novoselt]

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.

[mkoeppe]

Thanks for fixing these.

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

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. ?

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

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.

[pjxiao]

Thank you for your work! They look fine.