Opened 3 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:  sage7.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 3 years ago by
 Branch set to u/mkoeppe/interactivelpproblem__dictionaries__add_constraint___add_row_methods
comment:2 Changed 3 years ago by
 Cc novoselt pjxiao added
 Commit set to 58499805624d848b2c7852bb59931b82b35e9c8d
 Dependencies set to #20500
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Commit changed from 58499805624d848b2c7852bb59931b82b35e9c8d to f5b39004786d11dc7ce772849ff5972e8ca4c9f2
comment:4 Changed 3 years ago by
 Commit changed from f5b39004786d11dc7ce772849ff5972e8ca4c9f2 to f9c54486e8351c71320d7a1df662090f05d2096c
Branch pushed to git repo; I updated commit sha1. New commits:
f9c5448  fixup

comment:5 Changed 3 years ago by
 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
 Commit changed from f9c54486e8351c71320d7a1df662090f05d2096c to 2d444bc2f4c5ebca4003ce6b0e20a762e41f49b2
comment:7 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:8 Changed 3 years ago by
Rebased on 7.3.beta0
comment:9 Changed 3 years ago by
ping?
comment:10 followups: ↓ 11 ↓ 12 ↓ 13 ↓ 16 Changed 3 years ago by
 Status changed from needs_review to needs_work
 "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"
new_row
does not reflect very well the meaning, how aboutcoefficients
?.. 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.
 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!!!
 It should not be necessary to explicitly name a new slack variable.
 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.
 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 (perhapsadd_relation
would be a better name). For the revised onesadd_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 ; followup: ↓ 17 Changed 3 years ago by
Just a quick reply to point 7:
Replying to novoselt:
 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 (perhapsadd_relation
would be a better name). For the revised onesadd_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
Replying to novoselt:
 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 ; followup: ↓ 18 Changed 3 years ago by
Replying to novoselt:
 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
 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
 Commit set to f73fc57d12596752224ad3b5ff456574efab178d
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

comment:16 in reply to: ↑ 10 Changed 3 years ago by
I fixed the problems your comments 1, 2, 4, and 5.
Replying to novoselt:
 "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"
new_row
does not reflect very well the meaning, how aboutcoefficients
?.....
 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!!!
 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 ; followup: ↓ 22 Changed 3 years ago by
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
Replying to mkoeppe:
Replying to novoselt:
 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
I can no longer see cumulative changes, please rebase!
comment:20 Changed 3 years ago by
 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
 Commit changed from f73fc57d12596752224ad3b5ff456574efab178d to 206d5ca51bb4a2cfe121caf21db7f1afb76e9037
comment:22 in reply to: ↑ 17 Changed 3 years ago by
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
 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:
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

comment:24 Changed 3 years ago by
 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
 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
 Commit changed from f73fc57d12596752224ad3b5ff456574efab178d to e3d934bde9cb612c76afacddd2d44611d24f175f
 Status changed from needs_work to needs_review
comment:27 Changed 3 years ago by
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
 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
 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:
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

comment:30 Changed 3 years ago by
 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
 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 hardcoded ring
LPDictionary(matrix(QQ, A)
?!?!?!
New commits:
92f4868  Reviewer tweaks, part 1.

comment:32 Changed 3 years ago by
Thanks for fixing these.
comment:33 Changed 3 years ago by
 Commit changed from 92f48681fb17e29065b4ca2f2fbad3992d5d4c58 to a931471a742ea7c6350b833b67341c9052bf1d9b
comment:34 Changed 3 years ago by
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
 Commit changed from a931471a742ea7c6350b833b67341c9052bf1d9b to c8559f3cb19ded99c11ff5eda108be8ab211a3eb
comment:36 Changed 3 years ago by
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
 Status changed from needs_review to positive_review
Thank you for your work! They look fine.
comment:38 Changed 3 years ago by
 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
New commits:
Refactor leaving_coefficients in terms of new method row_coefficients
Fixup
Add @abstract_method methods to LPAbstractDictionary
Refactor entering_coefficients in terms of new method column_coefficients
Fix documentation
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
InteractiveLPProblem, dictionaries: add_constraint / add_row methods