<div dir="ltr"><div><div>Hi all,<br><br></div>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:<br>
<br></div>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.<br clear="all">
<div><div><div><div><br></div><div>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<br>
<br></div><div>clp danoint1.MPS<br></div><div><br>the result is<br><br>Optimal - objective value 63.062691<br>After Postsolve, objective 63.062691, infeasibilities - dual 0 (0), primal 0 (0)<br>Optimal objective 63.06269136 - 703 iterations time 0.252, Presolve 0.01<br>
<br></div><div>However, solving it with<br><br></div><div>clp danoint1.MPS -solution $<br> <br></div><div>gives the wrong objective value and the incorrect solution that I am seeing in SYMPHONY:<br><br>Model was imported from ./danoint1.MPS in 0.016001 seconds<br>
<br>status unknown<br>Objective value 0<br> 31 C0000031 1 0<br> 39 C0000039 1 0<br> 505 C0000505 80 0<br>
506 C0000506 90 0<br> 507 C0000507 68 0<br> 508 C0000508 69 0<br> 509 C0000509 83 0<br>
510 C0000510 75 0<br> 511 C0000511 71 0<br> 512 C0000512 66 0<br> 513 C0000513 74 0<br>
514 C0000514 81 0<br> 515 C0000515 63 0<br> 516 C0000516 63 0<br> 517 C0000517 75 0<br>
518 C0000518 70 0<br> 519 C0000519 65 0<br> 520 C0000520 61 0<br><br></div><div>Note that Clp says "status unknown" in this case.<br>
<br></div><div>John, any idea on either of these two problems?<br><br></div><div>Cheers,<br><br>Ted<br></div><div>-- <br>Dr. Ted Ralphs<br>Associate Professor, Lehigh University<br>(610) 628-1280<br>ted 'at' lehigh 'dot' edu<br>
<a href="http://coral.ie.lehigh.edu/~ted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
</div></div></div></div></div>