[Scip] Design choices

Sat Jun 29 01:05:05 MEST 2013

Dear Stefan,

but in the case that you want to test the potential of a heuristic 
before implementing a lot of code needed to actually generate the 
solution (I hope I got you right that this was your application of the 
objective limit), the behaviour of SCIP is exactly what you want.
If you would invest some more time to write the code which generates the 
solution itself instead of just its objective value (which you would 
probably do after the objective limit experiments show that a heuristic 
is promising), you would get the same behavior: The objective value of 
this solution is set as the objective cutoff, resulting in only 
searching for solutions with a strictly smaller objective. In 
particular, all nodes with a lower bound >= the solution's objective 
value are cut off.

If the objective limit would work in the way that you suggest, the 
positive effect of the heuristic might be underestimated, because nodes 
with a lower bounds equal to the objective limit would still need to be 
processed. This has nothing to do with being consistent with how 
constraint work, it is just the way an objective limit works within SCIP 
and probably works within every MIP solver, unless you want to do 
additional work and deteriorate your performance.

Best,
Gerald

Am 28.06.2013 21:09, schrieb Stefan Lörwald:
> 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 <mailto: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 <mailto:hiller at zib.de>>
>>
>>         Hi Michael,
>>
>>         On 06/27/2013 10:23 PM, michael.winkler at zib.de
>>         <mailto: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 list
>>     Scip at zib.de  <mailto:Scip at zib.de>
>>     http://listserv.zib.de/mailman/listinfo/scip
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130629/1f60a9f6/attachment.html