Fix problems introduced by remove_constraint functionality in MIP

[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:

• trac_12884.patch​

[john_perry]

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?

[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

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

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

[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

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

[ncohen]

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

Nathann

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

[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

[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

[john_perry]

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!

[ncohen]

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

[jdemeyer]

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