[Scip] [Fwd: Re: [Fwd: Re: solution times]]

[Timo Berthold]

tldr: sub-MIP heuristic stops earlier, leading to worse solution

Hi Todd,

this verifies the hypothesis from the first mail: In both cases,
Undercover stops at (close to) the given time limit.

Undercover is a heuristic that solves (500 nodes of) a sub-MIP. The time
limit of the MIQP gets passed to the sub-MIP. So, the sub-MIP gets stopped
prematurely, with a worse incumbent, leading to a worse solution in the
original problem.

If you wnat to see the output from the sub-MIP, you need to add a #define
SCIP_DEBUG in src/scip/heur_undercover.c This will create a SCIP log
within a SCIP log, which sometimes cna be a bit confusing to read (in
particular for scripts that are used to parse SCIP output). ;-)

If you want Undercover to get faster, what you could try is reducing the
parameter heuristics/undercover/maxnodes (which might not help if the
sub-MIP, e.g. is still in its oot node processing).

Cheers from Maldives
Timo

> Hi Timo,
>
> I've attached the log file containing both runs. In both it is reported
> that the solution is found with the "U" undercover heuristic.
>
> Cheers,
>
> Todd
>
> On 22 February 2013 00:52, Timo Berthold <berthold at zib.de> wrote:
>
>> Hi Todd,
>>
>> I am not very familiar with Ryan's python interface. Can you produce
>> some
>> log files/output that shows us which heuristic found the feasible
>> solution?
>>
>> Best
>> Timo
>>
>>
>> > ------------------------ Ursprüngliche Nachricht
>> -------------------------
>> > Betreff: Re: [Scip] solution times
>> > Von:     "Todd Niven" <toddniven at gmail.com>
>> > Datum:   Di, 19.02.2013, 00:39
>> > An:      "Timo Berthold" <berthold at zib.de>
>> > Cc:      scip at zib.de
>> >
>> --------------------------------------------------------------------------
>> >
>> > Hi Timo,
>> >
>> > I've attached the necessary files to run the model. I am using the
>> > python-zibopt interface with python3.2.
>> > The run.py script will run the model for 10 seconds and then run again
>> in
>> > `first solution' mode.
>> > On my machine, the `first solution' run takes roughly 60 seconds, not
>> 45
>> > as
>> > I originally stated.
>> >
>> > Cheers,
>> >
>> > Todd
>> >
>> > On 18 February 2013 17:50, Timo Berthold <berthold at zib.de> wrote:
>> >
>> >> Hi Todd,
>> >>
>> >> your understanding is correct, but like always, life can be more
>> >> complicated. ;-)
>> >> What might have happened: The solutions are found be a heuristic
>> which
>> >> itself takes a considerable amount of running time.
>> >> Normally it would be finished after 45 seconds total running time and
>> >> present the solution it could construct. If however, it is
>> interrupted
>> >> due
>> >> to your time limit, it will still check whatever it has at this point
>> >> (e.g., a partial solution) for feasibility.
>> >>
>> >> Could you send me the log files and maybe a model file of your
>> problem
>> >> to
>> >> verify this hypothesis?
>> >>
>> >> Best
>> >> Timo
>> >>
>> >> > I am solving a mixed integer problem with a single quadratic
>> >> constraint
>> >> > (this constraint is in fact the objective which is a sum of
>> bilinear
>> >> > terms)
>> >> > using SCIP2.1 and the output for solution times is puzzling me.
>> >> >
>> >> > I have an instance where if I ask SCIP to find me 1 solution it
>> halts
>> >> > after
>> >> > 45 seconds and outputs a feasible solution. However, if I ask SCIP
>> to
>> >> run
>> >> > for 10 seconds, it finishes and outputs a feasible solution. This
>> >> solution
>> >> > is not as good as the one obtained after 45 seconds. I was under
>> the
>> >> > impression that if I asked SCIP to halt after finding 1 solution,
>> it
>> >> would
>> >> > halt after finding the first solution, however this does not seem
>> to
>> >> be
>> >> > the
>> >> > case. This may have already been discussed and if so, I apologize
>> for
>> >> the
>> >> > duplication.
>> >> >
>> >> > Thanks,
>> >> >
>> >> > Todd
>> >> > _______________________________________________
>> >> > Scip mailing list
>> >> > Scip at zib.de
>> >> > http://listserv.zib.de/mailman/listinfo/scip
>> >> >
>> >>
>> >>
>> >
>>
>>
>>
>