Opened 4 years ago

Closed 3 years ago

#20559 closed enhancement (fixed)

InteractiveLPProblem, dictionaries: add_constraint / add_row methods

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: linear programming Keywords:
Cc: novoselt, pjxiao Merged in:
Authors: Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: c8559f3 (Commits) Commit: c8559f3cb19ded99c11ff5eda108be8ab211a3eb
Dependencies: #20500 Stopgaps:

Description

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

Change History (38)

comment:1 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:2 Changed 4 years ago by mkoeppe

  • Cc novoselt pjxiao added
  • Commit set to 58499805624d848b2c7852bb59931b82b35e9c8d
  • Dependencies set to #20500
  • Status changed from new to needs_review

New commits:

d6ee048Refactor leaving_coefficients in terms of new method row_coefficients
3cbdeefFixup
db52d0eAdd @abstract_method methods to LPAbstractDictionary
4e9955eRefactor entering_coefficients in terms of new method column_coefficients
a382ec1Fix documentation
b292e63Merge 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
5849980InteractiveLPProblem, dictionaries: add_constraint / add_row methods

comment:3 Changed 4 years ago by git

  • Commit changed from 58499805624d848b2c7852bb59931b82b35e9c8d to f5b39004786d11dc7ce772849ff5972e8ca4c9f2

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

639865cMerge tag '7.2.rc1' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
f5b3900add_row: Use @abstract_method

comment:4 Changed 4 years ago by git

  • Commit changed from f5b39004786d11dc7ce772849ff5972e8ca4c9f2 to f9c54486e8351c71320d7a1df662090f05d2096c

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

f9c5448fixup

comment:5 Changed 3 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to needs_work
  • Work issues set to rebasing

comment:6 Changed 3 years ago by git

  • Commit changed from f9c54486e8351c71320d7a1df662090f05d2096c to 2d444bc2f4c5ebca4003ce6b0e20a762e41f49b2

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

d9a6356InteractiveLPProblem, dictionaries: add_constraint / add_row methods
77e0a00add_row: Use @abstract_method
2d444bcfixup

comment:7 Changed 3 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:8 Changed 3 years ago by mkoeppe

Rebased on 7.3.beta0

comment:9 Changed 3 years ago by mkoeppe

ping?

comment:10 follow-ups: Changed 3 years ago by novoselt

  • Status changed from needs_review to needs_work
  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.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 3 years ago by mkoeppe

Just a quick reply to point 7:

Replying to novoselt:

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

comment:12 in reply to: ↑ 10 Changed 3 years ago by mkoeppe

Replying to novoselt:

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

comment:13 in reply to: ↑ 10 ; follow-up: Changed 3 years ago by mkoeppe

Replying to novoselt:

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

comment:14 Changed 3 years ago by pjxiao

  • Branch changed from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods
  • Commit 2d444bc2f4c5ebca4003ce6b0e20a762e41f49b2 deleted

comment:15 Changed 3 years ago by git

  • Commit set to f73fc57d12596752224ad3b5ff456574efab178d

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

b292e63Merge 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
5849980InteractiveLPProblem, dictionaries: add_constraint / add_row methods
639865cMerge tag '7.2.rc1' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
f5b3900add_row: Use @abstract_method
f9c5448fixup
119c8c6Rewording
d7d809bThe argument for new slack variable is optional
f73fc57Preserve information when construct a new problem

comment:16 in reply to: ↑ 10 Changed 3 years ago by 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?..

...

  1. 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!!!
  2. 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!

comment:17 in reply to: ↑ 11 ; follow-up: Changed 3 years ago by 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.

comment:18 in reply to: ↑ 13 Changed 3 years ago by novoselt

Replying to mkoeppe:

Replying to novoselt:

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

comment:19 Changed 3 years ago by novoselt

I can no longer see cumulative changes, please rebase!

comment:20 Changed 3 years ago by mkoeppe

  • Branch changed from u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:21 Changed 3 years ago by mkoeppe

  • Commit changed from f73fc57d12596752224ad3b5ff456574efab178d to 206d5ca51bb4a2cfe121caf21db7f1afb76e9037

rebased on 7.2.beta3


New commits:

b7d61fcInteractiveLPProblem, dictionaries: add_constraint / add_row methods
34f22abadd_row: Use @abstract_method
1d73925fixup
56d4a14Rewording
206d5caPreserve information when construct a new problem

comment:22 in reply to: ↑ 17 Changed 3 years ago by 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.

comment:23 Changed 3 years ago by pjxiao

  • Branch changed from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods
  • Commit changed from 206d5ca51bb4a2cfe121caf21db7f1afb76e9037 to f73fc57d12596752224ad3b5ff456574efab178d

New commits:

b292e63Merge 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
5849980InteractiveLPProblem, dictionaries: add_constraint / add_row methods
639865cMerge tag '7.2.rc1' into t/20559/interactivelpproblem__dictionaries__add_constraint___add_row_methods
f5b3900add_row: Use @abstract_method
f9c5448fixup
119c8c6Rewording
d7d809bThe argument for new slack variable is optional
f73fc57Preserve information when construct a new problem

comment:24 Changed 3 years ago by mkoeppe

  • Branch changed from u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:25 Changed 3 years ago by pjxiao

  • Branch changed from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:26 Changed 3 years ago by pjxiao

  • Commit changed from f73fc57d12596752224ad3b5ff456574efab178d to e3d934bde9cb612c76afacddd2d44611d24f175f
  • Status changed from needs_work to needs_review

New commits:

b7d61fcInteractiveLPProblem, dictionaries: add_constraint / add_row methods
34f22abadd_row: Use @abstract_method
1d73925fixup
56d4a14Rewording
206d5caPreserve information when construct a new problem
e3d934bThe argument for new slack variable is optional

comment:27 Changed 3 years ago by 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...

comment:28 Changed 3 years ago by mkoeppe

  • Branch changed from u/pjxiao/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:29 Changed 3 years ago by mkoeppe

  • Authors changed from Peijun Xiao to Peijun Xiao, Matthias Koeppe
  • Commit changed from e3d934bde9cb612c76afacddd2d44611d24f175f to 7c93d94e81987b9eed1432cbbe04064444c86048
  • Work issues rebasing deleted

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


New commits:

1a931ddInteractiveLPProblem, dictionaries: add_constraint / add_row methods
f525960add_row: Use @abstract_method
e5925a7fixup
6f41037Rewording
e6404abPreserve information when construct a new problem
6cb5622The argument for new slack variable is optional
a8af968Simplify code, don't create unnecessary rings
6d5f861add_row methods: Rename slack_variable to basic_variable, new_b to constant
7c93d94add_constraint: Delegate error checking to constructor

comment:30 Changed 3 years ago by novoselt

  • Branch changed from u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods to u/novoselt/interactivelpproblem__dictionaries__add_constraint___add_row_methods

comment:31 Changed 3 years ago by novoselt

  • Commit changed from 7c93d94e81987b9eed1432cbbe04064444c86048 to 92f48681fb17e29065b4ca2f2fbad3992d5d4c58

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:

92f4868Reviewer tweaks, part 1.

comment:32 Changed 3 years ago by mkoeppe

Thanks for fixing these.

comment:33 Changed 3 years ago by git

  • Commit changed from 92f48681fb17e29065b4ca2f2fbad3992d5d4c58 to a931471a742ea7c6350b833b67341c9052bf1d9b

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

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

comment:34 Changed 3 years ago by novoselt

  • Authors changed from Peijun Xiao, Matthias Koeppe to Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev

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

comment:35 Changed 3 years ago by git

  • Commit changed from a931471a742ea7c6350b833b67341c9052bf1d9b to c8559f3cb19ded99c11ff5eda108be8ab211a3eb

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

6a5998fAdd consistency check for adding a row to the auxiliary problem
c8559f3Clarify the sign of row coefficients.

comment:36 Changed 3 years ago by 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.

comment:37 Changed 3 years ago by pjxiao

  • Status changed from needs_review to positive_review

Thank you for your work! They look fine.

comment:38 Changed 3 years ago by vbraun

  • Branch changed from u/novoselt/interactivelpproblem__dictionaries__add_constraint___add_row_methods to c8559f3cb19ded99c11ff5eda108be8ab211a3eb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.