[Scip] Design choices

[Timo Berthold]

Hi Stefan,

It is a correct observation that no function in SCIP returns "unsigned
int"s.
I know that originally (around version 0.7), "unsigned int"s were only
used inside bit fields and for SCIP_Bool's. I do not know whether there
is a further rationale behind, probably Tobias would be the only one to
answer this.

I do strongly disagree though on the claim that inferinfo is useless.
The idea here is to have sizeof(int) many bits in which the constraint
handler/propagator can encode whatever information it needs to
reconstruct what it did on the corresponding propagation step. This can
be an int, but does not need to, it can of course be casted back and
forth. The reason to not wrap this is in any bigger object is memory
efficiency: There can be dozens or hundreds of bound changes at each
node, and hundreds of thousands of nodes in the whole B&B tree. You
literally want so save every byte that you can.

I did not double-check yet what happens in the LOP example, I just want
to point out that it is an example, thought for readability and not a
productive code.
All constraint handlers and propagators inside the main SCIP
distribution can handle problems with millions of variables and the 32
bits always provided enough space to pass propagation information -- in
many cases you simply need to store which propagation rule has been applied.

Finally, some general remarks:
There are several design choices that we would make differently if we
restarted such a project from scratch. And if we were restarting it over
again in another ten years, the same would hold. John Forrest loves to
tell the story how many LP solvers he wrote in his lifetime (some
double-digit number (base ten ;) ) if I remember correctly) and how much
he learnt from one to the other. i would say he has come pretty close to
perfection concerning the efficiency of the code, but not for
understandibility. This is another important point: At many places, you
have to weigh different objectives against each other when writing code.
There is no "the correct way". What is elegant in the one situation
becomes annoying at another point. You brought up a good example with
the behavior for the objective limit. Very generally speaking one
variant is great if you want to answer the question "is there a better
solution than *" the other when you want to answer "is there a solution
at least as good as *". As long as you handle pure IPs with integer
coefficients (which is a very typical case), it is a piece of cake to
transfer the one to the other, btw.

And a very final remark:
The great thing about having a software in source code is not only that
you are able to raise theses questions, but can even implement the
answers, if you really feel like you need to change something to make it
running for you!

Have a wonderful week everyone,
Timo




Am 01.07.2013 10:57, schrieb Stefan Lörwald:
> Hi again,
>
> one more thing that I forgot to ask in the first mail:
>
> Why do some functions return an int, where there can't ever be a
> negative result?
>
> Take e.g. int SCIPgetNConshdlrs(SCIP*). It is obvious that the number
> of Conshdlrs (or any other SCIPgetN...) can only return a natural
> number, because there can't be any negative numbers of conshdlrs.
>
> Why not return an unsigned int? Is some special value like -1 needed
> for passing an error status? If so, shouldn't this be caught by
> SCIP_RETCODE / SCIP_CALL?
>
> Personally I thought that the oddest place to use an int is in
> SCIPinferVarUbCons and related methods. Why pass the inferinfo as int?
> In your LOP example, this get's used to pass some information about
> indices. However as indices are again inherently unsigned, int is not
> a good match. Furthermore, since the encoding of this information
> needs to do something like i * n * n * n + j * n * n + k * n + l, this
> will fail for instances with n >= 256 This worsens if (as in the LOP
> example) more than one constraint has to be encoded (e.g. with n^8 +
> n^4 + i * n * n * n + ...). So inferinfo remains unusable for most
> applications.
>
> The most useful way to pass information is with a custom struct
> InferInfo containing fields for the indices (staying with this
> example, there are certainly other ways to use this).
> But this can't be done safely (i.e. platform independent) because we'd
> have to use a pointer to the struct which doesn't necessarily have the
> same number of bytes as the int (e.g. with int usually having 4 bytes
> and pointers using 8bytes on 64bit platforms).
>
> So what's the rationale behind integers returning for functions
> returning sizes and what's the reason for using an integer to encode
> information about constraints rather than a struct pointer?
>
> Yours,
> Stefan
>
>
>
> _______________________________________________
> Scip mailing list
> 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/20130701/1677f80a/attachment.html