Opened 10 years ago
Closed 10 years ago
#12884 closed defect (fixed)
Fix problems introduced by remove_constraint functionality in MIP
Reported by: | john_perry | Owned by: | ncohen |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.1 |
Component: | linear programming | Keywords: | glpk, mixed integer programming, mip, linear programming, sd40.5 |
Cc: | Merged in: | sage-5.1.beta5 | |
Authors: | John Perry | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12823 | Stopgaps: |
Description (last modified by )
- if the
check_redundant
option in MIP is true, thenremove_constraint()
should remove the constraint fromself._constraints
- apparently, GLPK wants you to re-initialize the basis after removing constraints, by calling
glp_std_basis()
Apply:
Attachments (1)
Change History (16)
comment:1 follow-up: ↓ 2 Changed 10 years ago by
- Dependencies set to #12823
- Status changed from new to needs_review
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 10 years ago by
Hellooooooooo !!!
Okay, a patch is ready. I don't see any way of removing the constraints efficiently, shy of trying to changing the constraints to a list. I'm not sure we lose that much in terms of efficiency in searching for a new constraint, but removing the ith constraint is quick and easy. Maybe you have a better way of removing the constraints?
Well, what about taking the ith constraint, then normalize it (as you do before adding it to the set), then pop the normalized constraint out of the set ? We could have a _normalize_constraint method in the main class, which would be called before adding or removing a constraint, couldn't we ?
And could you please add a doctest ? Otherwise I am pretty sure we could forget again this duplication mechanism next time we work on constraints :-)
Nathann
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 10 years ago by
Well, what about taking the ith constraint, then normalize it (as you do before adding it to the set), then pop the normalized constraint out of the set ? We could have a _normalize_constraint method in the main class, which would be called before adding or removing a constraint, couldn't we ?
I thought about that, but would floating-point comparisons be a problem?
And could you please add a doctest ? Otherwise I am pretty sure we could forget again this duplication mechanism next time we work on constraints
:-)
We already have a doctest for the duplication mechanism. But, sure, I can add a doctest for this.
comment:4 Changed 10 years ago by
BTW, I will either work on this at home (where I have beta13) or wait until 5.0 comes out. I don't want to download & build yet another beta at the office.
comment:5 in reply to: ↑ 3 ; follow-up: ↓ 6 Changed 10 years ago by
Helloooooooo !!!
I thought about that, but would floating-point comparisons be a problem?
Which floating point comparisons do you have in mind ?
I thought that if normalization works to test for duplicate constraints it would also work for removing them :-)
Nathann
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to ncohen:
Which floating point comparisons do you have in mind ? I thought that if normalization works to test for duplicate constraints it would also work for removing them
:-)
Possibly. My caution on this, however, is due to errors that I encountered when testing w*a > w*b (here w, a, and b are tuples of floats) and sometimes getting true when I would have gotten false had I used ints. If an error like this prevented me from removing constraints, that would be catastrophic when later I tried to add it again.
comment:7 follow-up: ↓ 8 Changed 10 years ago by
+1 to experience against hasty thinking. Let them be lists :-)
Nathann
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 10 years ago by
Replying to ncohen:
+1 to experience against hasty thinking. Let them be lists
:-)
Ah, too bad. I had been hoping you had some insight on floating point that would convert me. :-)
But, yes, failing to detect some redundant constraints isn't as catastrophic as failing to remove even one constraint that must be removed. Maybe one day we can figure some way to make the check for redundancy more efficient by sorting the list somehow, but it works pretty well for me right now in practice.
It would be nicer if the backends did that for us, but they don't. :-(
Alright: I'll submit a revision of this patch at some point, with the added doctest. Speaking of which, I noticed that the doctest coverage in sage/numerical isn't quite at 100%, and some people have been talking about that. Shall I try to complete that, and add it to this patch? That shouldn't be an issue, except that I can't quite test all the packages. (Though I can now test Gurobi & Cbc as well as GLPK).
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 10 years ago by
Hello !!!!
but it works pretty well for me right now in practice.
Good to know ! :-)
Speaking of which, I noticed that the doctest coverage in sage/numerical isn't quite at 100%, and some people have been talking about that. Shall I try to complete that, and add it to this patch?
Oh.. Are we missing much there ? I thought I was careful when writing the MILP classes O_o
I can not check right now as sage 5.0-rc0 is being compiled, but I hope there is not much work to do. I would also like to see a proud 100% on these files. If you feel like adding some documentation while working on this patch please do, but leave some of the work, it would not be fair otherwise :-)
Nathann
comment:10 in reply to: ↑ 9 Changed 10 years ago by
Replying to ncohen:
Speaking of which, I noticed that the doctest coverage in sage/numerical isn't quite at 100%, and some people have been talking about that. Shall I try to complete that, and add it to this patch?
Oh.. Are we missing much there ? I thought I was careful when writing the MILP classes
O_o
You were, actually. We're not missing much; here's the result of what I get when I run ../../sage -coverage sage/numerical
(slightly edited for readability)
No functions in sage/numerical//__init__.py No functions in sage/numerical//all.py ---------------------------------------------------------------------- sage/numerical//optimize.py SCORE sage/numerical//optimize.py: 100% (8 of 8) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//mip.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//mip.pyx: 98% (59 of 60) ---------------------------------------------------------------------- No functions in sage/numerical//test.py No functions in sage/numerical//backends/__init__.py ---------------------------------------------------------------------- sage/numerical//backends/gurobi_backend.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//backends/gurobi_backend.pyx: 89% (26 of 29) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//backends/generic_backend.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//backends/generic_backend.pyx: 87% (29 of 33) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//backends/cplex_backend.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//backends/cplex_backend.pyx: 90% (29 of 32) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//backends/coin_backend.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//backends/coin_backend.pyx: 93% (29 of 31) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//backends/glpk_backend.pyx ERROR: Please add a `TestSuite(s).run()` doctest. SCORE sage/numerical//backends/glpk_backend.pyx: 93% (31 of 33) ---------------------------------------------------------------------- ---------------------------------------------------------------------- sage/numerical//knapsack.py SCORE sage/numerical//knapsack.py: 100% (8 of 8) ----------------------------------------------------------------------
I can not check right now as sage 5.0-rc0 is being compiled, but I hope there is not much work to do. I would also like to see a proud 100% on these files. If you feel like adding some documentation while working on this patch please do, but leave some of the work, it would not be fair otherwise
:-)
I'll try to take care of it. It's on my schedule for tomorrow, then. :-)
john
Changed 10 years ago by
comment:11 Changed 10 years ago by
- Description modified (diff)
- Keywords sd40.5 added
I updated the patch, adding a few doctests, including the one Nathann requested. Sage will still complain that doctest coverage isn't complete, but that's due to an old bug that still hasn't been resolve (see #1795).
Please review!
comment:12 Changed 10 years ago by
- Status changed from needs_review to positive_review
sage -t "devel/sage-2/sage/numerical/mip.pyx" [1.6 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 1.6 seconds
Gooooooooooood to go ! :-)
Thank you for this patch !!
Nathann
comment:13 Changed 10 years ago by
Please fill in your real name in the Author / Reviewer fields.
comment:14 Changed 10 years ago by
- Reviewers set to Nathann Cohen
comment:15 Changed 10 years ago by
- Merged in set to sage-5.1.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
Okay, a patch is ready. I don't see any way of removing the constraints efficiently, shy of trying to changing the constraints to a list. I'm not sure we lose that much in terms of efficiency in searching for a new constraint, but removing the ith constraint is quick and easy. Maybe you have a better way of removing the constraints?