[Scip] Design choices

Stefan Lörwald stefan.loerwald at gmail.com
Fri Jun 28 21:09:45 MEST 2013


Hi Gerald,

thanks for your answer. I don't have an example for such a heuristic.
However I encountered some cases in which the value was very easy to
calculate and the solution needs quite a lot of code. In these cases it is
extremely helpful to explore the potential of a heuristic by just adding
the value as a limit rather than spending lot's of time to implement the
solution generation. Using SCIPsetObjLimit during that phase of development
is helpful, but puzzling if by accident the optimal value is calculated.
I'd have expected SCIPsetObjLimit to act as a "<=" or ">=" (just as
constraints do, so in a way this would be the consistent way!) and perhaps
SCIPsetStrictObjLimit as "<" or ">".

Of course if one is familiar with SCIP, adding some epsilon is easy, but I
found this to be non-intuitive as a beginner.

Yours,
Stefan

2013/6/28 Gerald Gamrath <gamrath at zib.de>

>  Hi Stefan,
>
> in a sense, you want to simulate the behaviour that SCIP would show if it
> already had a solution with that objective value.
>
> Moreover, I did only encounter situations, where you only want to find
> solutions which are better than a certain value. A typical example is
> within sub-MIP heuristics, where you only want to find improving solutions.
> Thus, you set the objective limit to the objective value of the incumbent,
> so that for example nodes with a lower bound of that value can be cut off
> because they cannot contain a better solution. Another example is when
> solving a pricing subproblem as a MIP during column generation, where you
> are only looking for variables with strictly negative reduced costs.
>
> Those are common cases where you want to have it as it is implemented. I
> never encountered a primal heuristic which could determine the optimal
> objective value without being able to construct a solution or parts of a
> solution which can be extended to a complete solution probably much more
> efficiently than just letting a branch-and-bound run with just the
> objective limit added. But I would be interested in an example. Do you have
> one?
>
> If you want to have your intended behaviour, you should set the cutoff
> bound to the optimal value + some epsilon. You can get an epsilon proposed
> by SCIP using the method SCIPcutoffbounddelta().
>
> Best,
> Gerald
>
>
> On 28.06.2013 11:58, Stefan Lörwald wrote:
>
> Hi again,
>
>  just a quick follow up question concerning SCIPsetObjLimit: Why does the
> optimal value has to be strictly better than the provided value? Why not
> allow for equality? A simple scenario would be to have a heuristic which
> finds the optimal value without providing solution data.
>
>  Yours,
> Stefan
>
> 2013/6/28 Benjamin Hiller <hiller at zib.de>
>
>> Hi Michael,
>>
>> On 06/27/2013 10:23 PM, michael.winkler at zib.de wrote:
>> >> Ah, well i should have looked into the documentation for that one.
>> That's
>> >> the reason I dislike boolean values in function calls by the way: The
>> >> purpose is not clear at all, better use enum.
>> >
>> > Imo, in most cases boolean values are better understandable then enums
>> and
>> > also enums seem to make you wonder whether there are more then two
>> > possible values.
>>
>>  I think that Sefan was (indeed) thinking of enums with more than two
>> values, e.g.
>>
>> SCIP_IS_INITIAL = 1
>> SCIP_DO_SEPARATE = 2
>> SCIP_DO_ENFORCE = 4
>> SCIP_CHECK_FEASIBLE = 8
>> ...
>>
>> so one could put
>>
>> SCIP_IS_INITIAL + SCIP_CHECK_FEASIBLE
>>
>> instead of
>>
>> true, false, false, true
>>
>> And I'd prefer this, too, but in a long-running project like SCIP things
>> are as they are and it it is not easy to change them. I'm sure it started
>> out with two or three bools, which wasn't too bad, and grew more ugly over
>> time.
>>
>> Best,
>>
>> Benjamin
>>
>
>
>
> _______________________________________________
> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130628/df53a516/attachment.html


More information about the Scip mailing list