mps file :-). run it on cplex just to find out :-)<br>nice to produce new instances that hurt...and well done to symphony (!)<br>Claude ph Medard<br><br><div class="gmail_quote">On Tue, Jun 29, 2010 at 12:20 AM, Ted Ralphs <span dir="ltr"><<a href="mailto:ted@lehigh.edu">ted@lehigh.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Just to follow up, I ran SYMPHONY with more detailed output and<br>
everything looked fine for me---it terminated right after finding the<br>
first feasible solution. Are you still seeing this behavior? If you<br>
want, you can solve the instance with verbosity set to "3" and send me<br>
the output so I can see what's happening. By the way, I also tried<br>
solving this instance with the latest version of Cbc and after a few<br>
days and over 1000 nodes, it still hasn't found feasible solution.<br>
I'm not sure why it's having so much trouble.<br>
<br>
In any case, this seems to be an interesting instance for testing. Are<br>
you willing to say more about the origin of this instance and/or<br>
provide more of the same? I would encourage you to consider submitting<br>
it for inclusion in MIPLIB 2010:<br>
<br>
<a href="http://miplib.zib.de/miplib2010/" target="_blank">http://miplib.zib.de/miplib2010/</a><br>
<br>
Doing so will ensure that solver developers are aware of the<br>
difficulties of solving this class of instances and may target the<br>
development of solver capabilities for better handling this kind of<br>
structure.<br>
<br>
Cheers,<br>
<font color="#888888"><br>
Ted<br>
</font><div><div></div><div class="h5"><br>
On Thu, Jun 24, 2010 at 10:54 AM, Ted Ralphs <<a href="mailto:ted@lehigh.edu">ted@lehigh.edu</a>> wrote:<br>
> I ran the instance myself on the trunk version of SYMPHONY and it<br>
> solves in only 15 nodes, but it ook almost a day on a reasonably fast<br>
> machine. So the biggest reason why it's taking so long is that the LP<br>
> relaxations appear to be very difficult to solve. You could possibly<br>
> cut down the running time by parallelizing, but given that the tree is<br>
> so small, this might not buy you much. I'm doing another run now with<br>
> more detailed output to see exactly what's going on with the bounds.<br>
><br>
> Ted<br>
><br>
> On Thu, Jun 17, 2010 at 6:32 AM, Ted Ralphs <<a href="mailto:ted@lehigh.edu">ted@lehigh.edu</a>> wrote:<br>
>> The output is rounded to two digits of precision. My guess is that<br>
>> even though it appears that the bounds are equal, they differ in less<br>
>> significant digits. You could try setting "gap_limit" to something<br>
>> like .01 and see if it finishes more quickly. Can you send me the<br>
>> model off-line?<br>
>><br>
>> Cheers,<br>
>><br>
>> Ted<br>
>><br>
>> On Sun, Jun 13, 2010 at 7:10 PM, Iulian Ober <<a href="mailto:iulian.ober@irit.fr">iulian.ober@irit.fr</a>> wrote:<br>
>>> Hello,<br>
>>><br>
>>> I'm trying to use Symphony (5.2.4) off-the-shelf (no custom code) to solve a large ILP problem (a 0/1 problem actually).<br>
>>> For this problem I know that all feasible solutions have value = 81, like the LP optimal solution.<br>
>>> The output seems to indicate that the solver continues to search long after finding an optimal solution, but maybe I'm misinterpreting it. Here is a condensed version of what I get:<br>
>>><br>
>>> =================================================<br>
>>> Starting Preprocessing...<br>
>>> Preprocessing finished...<br>
>>> coefficients modified: 47022<br>
>>> constraints removed: 7116<br>
>>> variables fixed: 1844<br>
>>> Problem has<br>
>>> 33846 constraints<br>
>>> 8560 variables<br>
>>> 403100 nonzero coefficients<br>
>>><br>
>>> Total Presolve Time: 0.689973...<br>
>>><br>
>>> Solving...<br>
>>><br>
>>> solving root lp relaxation<br>
>>> done: 0 left: 1 ub: ?? lb: ?? time: 20<br>
>>> done: 0 left: 1 ub: ?? lb: ?? time: 40<br>
>>> ...<br>
>>> ...<br>
>>> done: 0 left: 1 ub: ?? lb: ?? time: 1524<br>
>>> The LP value is: 81.000 [0,54820] -- found the continuous solution ?<br>
>>> ...<br>
>>> ...<br>
>>> done: 0 left: 1 ub: ?? lb: ?? time: 10979<br>
>>> done: 1 left: 2 ub: ?? lb: 81.00 time: 10999 -- does this mean it found a feasible integer solution for 81 ?<br>
>>> ...<br>
>>> ...<br>
>>> done: 6 left: 7 ub: ?? lb: 81.00 time: 14783<br>
>>> done: 17 left: 12 ub: 81.00 lb: 81.00 gap: 0.00 time: 22276 -- is this because no direction for the optimization is specified in the MPS model, so it tries both?<br>
>>> ...<br>
>>> ...<br>
>>> done: 28 left: 1 ub: 81.00 lb: 81.00 gap: 0.00 time: 74648<br>
>>><br>
>>> ****************************************************<br>
>>> * Optimal Solution Found *<br>
>>> * Now displaying stats and best solution found... *<br>
>>> ****************************************************<br>
>>> ...<br>
>>> ...<br>
>>> =======================================================<br>
>>><br>
>>> Can anybody please help me interpret the output ?<br>
>>> I tried to augment verbosity (verbosity 3), but then I get fewer output (!?) -- no periodic messages every 20 sec anymore...<br>
>>><br>
>>> I also tried to set :<br>
>>> find_first_feasible 1<br>
>>> but does not seem to finish quicker, so maybe I'm wrong...<br>
>>><br>
>>> Thanks for your help,<br>
>>><br>
>>> Iulian Ober<br>
>>> IRIT, Universite de Toulouse<br>
>>> 118 route de Narbonne<br>
>>> 31062 Toulouse, France<br>
>>> <a href="http://www.irit.fr/%7EIulian.Ober/" target="_blank">http://www.irit.fr/~Iulian.Ober/</a><br>
>>><br>
>>><br>
>>> _______________________________________________<br>
>>> Symphony mailing list<br>
>>> <a href="mailto:Symphony@list.coin-or.org">Symphony@list.coin-or.org</a><br>
>>> <a href="http://list.coin-or.org/mailman/listinfo/symphony" target="_blank">http://list.coin-or.org/mailman/listinfo/symphony</a><br>
>>><br>
>><br>
>><br>
>><br>
>> --<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/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
>><br>
><br>
><br>
><br>
> --<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/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
><br>
<br>
<br>
<br>
--<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/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>
<br>
_______________________________________________<br>
Symphony mailing list<br>
<a href="mailto:Symphony@list.coin-or.org">Symphony@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/symphony" target="_blank">http://list.coin-or.org/mailman/listinfo/symphony</a><br>
</div></div></blockquote></div><br>