[Clp] Incorrect solutions from Clp

[Ted Ralphs]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20140818/9f9f4c9e/attachment.html>