[Clp] Incorrect solutions from Clp

[Ted Ralphs]

Hi all,

I've been puzzling over the fact that Clp sporadically gives incorrect
solutions when used within SYMPHONY to solve LP relaxations of an MILP.
It's difficult to create a minimal example of the issue because it happens
when the problem has already been modified and warm solved a number of
times. There are two different seemingly unrelated scenarios in which
issues arise:

1. When doing strong branching with a dual iteration limit, Clp sometimes
returns an incorrect objective value. I have debugged this issue and I can
see that when the solver first stops in hitMaximumIterations(), the value
seems correct, but it is then later re-calculated before the solver exist
in computeObjectiveValue() and this computed value is incorrect (if I dump
the LP to a file and solve with stand-alone Clp, the corrected value
exceeds the reported optimum by a substantial amount, while the uncorrected
is a correct lower bound) . It seems to compute this value from a primal
solution, though I would think that this would be done from a dual solution
in this case. This problem can be fixed, by the way, by solving from a hot
start rather than a warm start, which perhaps gives a clue as to what the
issue is. I have not been able to create an isolated example yet, though it
happens almost immediately when branching in the root node of fast0507 from
MIPLIB 3 and can be easily reproduced there within SYMPHONY with a short
computational run.

2. The second problem is that Clp sometimes gets a (very) wrong solution
when solving an LP to full optimality. I have managed to isolate one LP
relaxation where this can be replicated on the command line with stable
version 1.15, revision 2046. If you solve the attached MPS file with

clp danoint1.MPS

the result is

Optimal - objective value 63.062691
After Postsolve, objective 63.062691, infeasibilities - dual 0 (0), primal
0 (0)
Optimal objective 63.06269136 - 703 iterations time 0.252, Presolve 0.01

However, solving it with

clp danoint1.MPS -solution $

gives the wrong objective value and the incorrect solution that I am seeing
in SYMPHONY:

Model was imported from ./danoint1.MPS in 0.016001 seconds

status unknown
Objective value               0
     31 C0000031               1                      0
     39 C0000039               1                      0
    505 C0000505              80                      0
    506 C0000506              90                      0
    507 C0000507              68                      0
    508 C0000508              69                      0
    509 C0000509              83                      0
    510 C0000510              75                      0
    511 C0000511              71                      0
    512 C0000512              66                      0
    513 C0000513              74                      0
    514 C0000514              81                      0
    515 C0000515              63                      0
    516 C0000516              63                      0
    517 C0000517              75                      0
    518 C0000518              70                      0
    519 C0000519              65                      0
    520 C0000520              61                      0

Note that Clp says "status unknown" in this case.

John, any idea on either of these two problems?

Cheers,

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/8daa5b14/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: danoint1.MPS
Type: application/octet-stream
Size: 135811 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20140818/8daa5b14/attachment-0001.obj>