Opened 11 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: Nathann Cohen
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:

Status badges

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 11 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 11 years ago by John Perry

Dependencies: #12823
Status: newneeds_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 ; Changed 11 years ago by Nathann Cohen

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 ; Changed 11 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 11 years ago by John Perry

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.

Version 0, edited 11 years ago by John Perry (next)

comment:5 in reply to:  3 ; Changed 11 years ago by Nathann Cohen

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 11 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 Changed 11 years ago by Nathann Cohen

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

Nathann

comment:8 in reply to:  7 ; Changed 11 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 ; Changed 11 years ago by Nathann Cohen

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 11 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 11 years ago by John Perry

Attachment: trac_12884.patch added

comment:11 Changed 11 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 11 years ago by Nathann Cohen

Status: needs_reviewpositive_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 Jeroen Demeyer

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

comment:14 Changed 10 years ago by Nathann Cohen

Reviewers: Nathann Cohen

comment:15 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.1.beta5
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.