[Symphony] help with interpreting the output (does symphony continue after finding optimal solution?)

[Ted Ralphs]

Just to follow up, I ran SYMPHONY with more detailed output and
everything looked fine for me---it terminated right after finding the
first feasible solution. Are you still seeing this behavior? If you
want, you can solve the instance with verbosity set to "3" and send me
the output so I can see what's happening. By the way, I also tried
solving this instance with the latest version of Cbc and after a few
days and over 1000 nodes, it still hasn't found  feasible solution.
I'm not sure why it's having so much trouble.

In any case, this seems to be an interesting instance for testing. Are
you willing to say more about the origin of this instance and/or
provide more of the same? I would encourage you to consider submitting
it for inclusion in MIPLIB 2010:

http://miplib.zib.de/miplib2010/

Doing so will ensure that solver developers are aware of the
difficulties of solving this class of instances and may target the
development of solver capabilities for better handling this kind of
structure.

Cheers,

Ted

On Thu, Jun 24, 2010 at 10:54 AM, Ted Ralphs <ted at lehigh.edu> wrote:
> I ran the instance myself on the trunk version of SYMPHONY and it
> solves in only 15 nodes, but it ook almost a day on a reasonably fast
> machine. So the biggest reason why it's taking so long is that the LP
> relaxations appear to be very difficult to solve. You could possibly
> cut down the running time by parallelizing, but given that the tree is
> so small, this might not buy you much. I'm doing another run now with
> more detailed output to see exactly what's going on with the bounds.
>
> Ted
>
> On Thu, Jun 17, 2010 at 6:32 AM, Ted Ralphs <ted at lehigh.edu> wrote:
>> The output is rounded to two digits of precision. My guess is that
>> even though it appears that the bounds are equal, they differ in less
>> significant digits. You could try setting "gap_limit" to something
>> like .01 and see if it finishes more quickly. Can you send me the
>> model off-line?
>>
>> Cheers,
>>
>> Ted
>>
>> On Sun, Jun 13, 2010 at 7:10 PM, Iulian Ober <iulian.ober at irit.fr> wrote:
>>> Hello,
>>>
>>> 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).
>>> For this problem I know that all feasible solutions have value = 81, like the LP optimal solution.
>>> 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:
>>>
>>> =================================================
>>> Starting Preprocessing...
>>> Preprocessing finished...
>>>         coefficients modified: 47022
>>>         constraints removed: 7116
>>>         variables fixed: 1844
>>> Problem has
>>>         33846 constraints
>>>         8560 variables
>>>         403100 nonzero coefficients
>>>
>>> Total Presolve Time: 0.689973...
>>>
>>> Solving...
>>>
>>> solving root lp relaxation
>>> done: 0 left: 1 ub: ?? lb: ?? time: 20
>>> done: 0 left: 1 ub: ?? lb: ?? time: 40
>>> ...
>>> ...
>>> done: 0 left: 1 ub: ?? lb: ?? time: 1524
>>> The LP value is: 81.000 [0,54820]                                       -- found the continuous solution ?
>>> ...
>>> ...
>>> done: 0 left: 1 ub: ?? lb: ?? time: 10979
>>> done: 1 left: 2 ub: ?? lb: 81.00 time: 10999                    -- does this mean it found a feasible integer solution for 81 ?
>>> ...
>>> ...
>>> done: 6 left: 7 ub: ?? lb: 81.00 time: 14783
>>> 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?
>>> ...
>>> ...
>>> done: 28 left: 1 ub: 81.00 lb: 81.00 gap: 0.00 time: 74648
>>>
>>> ****************************************************
>>> * Optimal Solution Found                           *
>>> * Now displaying stats and best solution found...  *
>>> ****************************************************
>>> ...
>>> ...
>>> =======================================================
>>>
>>> Can anybody please help me interpret the output ?
>>> I tried to augment verbosity (verbosity 3), but then I get fewer output (!?) -- no periodic messages every 20 sec anymore...
>>>
>>> I also tried to set :
>>>        find_first_feasible 1
>>> but does not seem to finish quicker, so maybe I'm wrong...
>>>
>>> Thanks for your help,
>>>
>>> Iulian Ober
>>> IRIT, Universite de Toulouse
>>> 118 route de Narbonne
>>> 31062 Toulouse, France
>>> http://www.irit.fr/~Iulian.Ober/
>>>
>>>
>>> _______________________________________________
>>> Symphony mailing list
>>> Symphony at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/symphony
>>>
>>
>>
>>
>> --
>> 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