[Clp] Incorrect solutions from Clp

[Ted Ralphs]

Just to follow up, the issues were caused by a combination of SYMPHONY not
properly saving and re-loading the basis during strong branching and some
minor bugs in Clp. John put in fixes for the Clp issue and everything seems
to be good now (with respect to both issues, which seem to have been
related). Here is his description of the issues:

When Clp stops on maximum iterations (not hot start) there were several
problems -
a) OsiClp had "crunched" down the problem - on maximum iterations it
thought there was no point in doing work of restoring solutions etc.  I
have fixes so that it will restore (unless in Cbc).  This was cause of bug
you saw.
b) However there were still problems.  Even if you ask for dual, Clp can
decide it prefers primal (you can override this but it could still happen
that it decided it had to switch).  If you finish then it doesn't matter,
but if you hit maximum iterations in primal then objective could be high.

My current fix is to add a new secondary status which signals this
condition.

The secondary status is set to "10" in the scenario described in b).

Cheers,

Ted








On Mon, Aug 18, 2014 at 2:39 PM, Ted Ralphs <ted at lehigh.edu> wrote:

> To reproduce, check out current SYMPHONY trunk and build:
>
> svn co https://projects.coin-or.org/svn/SYMPHONY/trunk SYMPHONY-trunk
> mkdir build
> cd build
> ../configure --enable-debug --enable-gnu-packages
> make install
>
> Create a parameter file "par" with the following contents:
>
> use_hot_starts 0
> should_use_rel_br 0
> do_primal_heuristic 0
> limit_strong_branching_time 0
>
> Run this command under a debugger:
>
> symphony -F fast0507.mps -f par
>
> Around line 1580 of lp_branch.c is where the solves happen in the strong
> branching loop. If you display "can->objval" on line 1601 each time through
> the loop, you will see the result of the strong branching pre-solves. What
> cannot happen is for both objective values to be above 161, since that
> would imply that the objective value for the MIP is above 161, whereas 161
> is the true optimum (note that there is an objective offset of 13 in this
> example---the optimum including the offset is 174).
>
> If you just keep looping until you see a case where can->objval has two
> values above 161, this is apparently a bug. Something like
>
> (gdb) print can->objval
> can->objval = {161.14556667654873, 161.14556667654873, 0, 0}
>
> For me, it happens with the third candidate. If you then go and debug the
> solve call for one of these buggy LP calls (line 1584) and stop in
> hitMaximumIterations() when hitMax gets value "true", you will be able to
> see what I'm talking about. From within hitMaximumIterations(), the LP
> value seems correct, but as you step out of the solve call, the objective
> value gets changed in computeObjectiveValue() at some point and becomes
> incorrect.
>
> If you change the value of use_hot_starts to 1 in the parameter file,
> everything is fine.
>
> Let me know if you have trouble reproducing.
>
> Cheers,
>
> Ted
>
>
>
>
> On Mon, Aug 18, 2014 at 1:43 PM, Ted Ralphs <ted at lehigh.edu> wrote:
>
>>
>>
>>
>> On Mon, Aug 18, 2014 at 12:58 PM, John Forrest <
>> john.forrest at fastercoin.com> wrote:
>>
>>>  Ted,
>>>
>>> 2. - as described - is not a bug - you have to say solve or dual or
>>> similar before -solution $.  Clp is just giving you the solution before
>>> solving it.
>>>
>>
>> Ah yes, you are right! However, in my stupidity, I might have stumbled
>> onto a clue. The solution that Clp is giving me before solving on the
>> command line is precisely the one I am seeing from within SYMPHONY. Inside
>> SYMPHONY, I am definitely making the solve call first. It doesn't seem like
>> that can be a coincidence. What is this solution it produces before solving?
>>
>>
>>> 1. probably is a bug
>>>
>>> What version of SYMPHONY should I check out to debug this - and how do I
>>> reproduce bugs?
>>>
>>
>> It's SYMPHONY trunk. I'll check in my code and send you the details of
>> how to reproduce in a separate e-mail. Thanks!
>>
>>  Cheers,
>>
>> Ted
>> --
>> Dr. Ted Ralphs
>> Associate Professor, Lehigh University
>> (610) 628-1280
>> ted 'at' lehigh 'dot' edu
>> coral.ie.lehigh.edu/~ted
>>
>
>
>
> --
> Dr. Ted Ralphs
> Associate Professor, Lehigh University
> (610) 628-1280
> ted 'at' lehigh 'dot' edu
> coral.ie.lehigh.edu/~ted
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20140821/3f4a089e/attachment.html>