[Cbc] Tie-breaking in the face of numerical instability

[rhavar at protonmail.com]

I'm more of a code-monkey than someone who understands how all this stuff works -- so if someone could sanity-check my idea and give feedback it would be greatly appreciated.

I'm running cbc against problems that have realllly big constants, and it tends to lead to a bunch of numerical instability problems (e.g. missing solutions and the like ). And one thing that I would like to do is start adding "tie-breaking"  but the naive way just causes the instability issues to blow up.

By "tie-breaking" I mean telling cbc that "Optimizing against obj1, but if multiple solutions have the same value ... then optimize against obj2".  The naive way to do this is compute the max-possible value that  obj2 can be, and then tell cbc to optimize for:

obj1 * (MAX_POSSIBLE_OBJ2+1) + obj2

Which of course would work if it wasn't for the numeric instability issues.  However, I have a "smarter" idea, which is to run cbc twice.   The first time I optimize for obj1  and figure out what the value is. (Let's say = 1099511627768 ), then this time run cbc a second time but this time with an additional constraint:

obj1 = 1099511627768

And now optimize for obj2 instead of obj1

--

So my question for the list is, "is this a good idea"? And secondly, could something like this be supported natively by cbc, which would save me a lottt of plumbing work.

-Ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20180603/3cffedab/attachment.html>