Opened 7 years ago

Closed 7 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 john_perry)

  • if the check_redundant option in MIP is true, then remove_constraint() should remove the constraint from self._constraints
  • apparently, GLPK wants you to re-initialize the basis after removing constraints, by calling glp_std_basis()

Apply:

Attachments (1)

trac_12884.patch (6.6 KB) - added by john_perry 7 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 follow-up: Changed 7 years ago by john_perry

  • Dependencies set to #12823
  • Status changed from new to needs_review

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?

comment:2 in reply to: ↑ 1 ; follow-up: Changed 7 years ago by ncohen

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: Changed 7 years ago by john_perry

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 7 years ago by john_perry

BTW, I will either work on this at home (where I have beta13 on two different machines!) or wait until 5.0 comes out. I don't want to download & build yet another beta at the office.

Last edited 7 years ago by john_perry (previous) (diff)

comment:5 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by ncohen

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 7 years ago by john_perry

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: Changed 7 years ago by ncohen

+1 to experience against hasty thinking. Let them be lists :-)

Nathann

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by john_perry

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: Changed 7 years ago by ncohen

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 7 years ago by john_perry

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 7 years ago by john_perry

comment:11 Changed 7 years ago by john_perry

  • 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 7 years ago by ncohen

  • 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 7 years ago by jdemeyer

Please fill in your real name in the Author / Reviewer fields.

comment:14 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen

comment:15 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.