MIR cuts bug

[lvenerosy]

From what has been reported on issue https://github.com/JWally/jsLPSolver/issues/63 :

• broken part of the MIR cuts removed (as I don't have the time to get on it right now, I will make an actual fix later hopefully)
• new test from the instance that broke the MIR cuts
• solver's export updated in order to fix the call to grunt test

@JWally since the MIR cut bug is breaking the solver, could you update the npm version please ?

[bchevalier]

This means that the solving might be slightly less efficient? Any insight about the bug?

[lvenerosy]

Some are faster, some are slower. But I didn't do profiling so I don't know whether the differences in time are because of the logic of the algorithm or because there still is code (data structures, pivot...) to optimize.

And I don't have much insight on the bug. Just by playing around I can sort of get it to work but it is just poking in the dark. I will need to check the papers where the algorithm appears.

[JWally]

Question, do y'all still want to merge this into master?

[lvenerosy]

I will try to free up some time this week and look a bit into it if that's ok with you.

[JWally]

No rush, I just wanted to make sure I'm not holding anything up.

THANKS!

On Mon, Aug 28, 2017 at 3:36 AM lvenerosy notifications@github.com wrote:

I will try to free up some time this week and look a bit into it if that's ok with you.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/JWally/jsLPSolver/pull/64#issuecomment-325294717, or mute the thread https://github.com/notifications/unsubscribe-auth/ACXi9ybsKccAvmU1dvjWNdp2iFMNnW-Yks5scnv1gaJpZM4OER4X .

[lvenerosy]

Just by looking at it for a bit I can't find a solution (and prove that it's the right one) so I will need to read some more papers to make sure. The thing is, I don't know when I will have this kind of time so no ETA for the moment.

[lvenerosy]

Finally got around to rechecking the paper, AGGREGATION and MIXED INTEGER ROUNDING to SOLVE MIPs Hugues Marchand and Laurence A.Wolsey June 1998, where the upper mir cut is from.

This PR can go in because, I quote,

Finally we show that the MIR inequality (2) is essentially just a more direct version of the Gomory mixed integer cut.

where (2) is (what I call) the lower mir cut. Then the part right after this quote proceeds to prove the equivalence by using (what I call) the upper mir cut. Thus that upper mir cut is only a reformulation used for a proof and as such is redundant.

Since it is equivalent there is an error in the way I used the upper mir cut but the right course of action is to remove it anyway.