[Scip] Design choices

Marc Pfetsch pfetsch at mathematik.tu-darmstadt.de
Mon Jul 1 12:08:42 MEST 2013



Hi Stefan!

>  > For example adding 1 to 1e20 will result in 1e20.
>
> Yeah, I do understand floats, but why should you calculate inf + 1
> anyway? That's a rather useless "example". What about real world (SCIP!)
> code where it actually makes a difference between 1e20 or a constant
> closer to (or) DBL_MAX and 1e20 is better.

1e20 is an arbitrary number (CPLEX uses 1e30 I think). The point is that 
you want to truncate very large numbers to a well defined value, i.e., 
you replace a number that has been computed somewhere and is larger than 
1e20 by 1e20. Using DBL_MAX does not allow to do this. Furthermore, it 
will give you an overflow if you do calculations.

> Well, again, let's just try and compare to values. This time for the
> _whole_ SCIP suite.
>
> Time compiling SCIP as C: 3min42s
>
> Time compiling SCIP as C++: 3min43s

This is a misunderstanding: Writing C code instead of complicated C++ 
code with templates will compile faster. Of course, the price you have 
to pay is that you do not have the benefits.


> There are _many_ nodes and just _one_ currently best global solution.

There is only one current node and one current LP solution for it.

> This immediately suggest using the one value NULL as global, and
> specific ones, namely connecting to a node, for the LP.

The point is that no solution might exist. SCIPgetBestSol() allows you 
to test this.

> It might be handy in the SCIP core _now_, but I doubt this will be good
> for the future.

O.k. - if the need arises, we can think about changing it.

> In our area, practically every problem is so difficult
> that sequential algorithms are doomed to fail terribly without hope
> since the next generation of hardware may be vastly improved, but it
> still only suffices for a tiny improvement in terms of practically
> solvable problem instances. The need for parallelization is outrageously
> evident although still this is limited.

Instead of brute force computation, you can also develop better 
mathematical methods to solve the problems.

> But what if we can develop an efficient way of parallelizing
> branch-and-cut? I know that this is extremely difficult, but let's just
> imagine. So you probably solve two cleverly picked nodes at the same
> time. Which solution does the currently working method refer to? Sure,
> NULL as in "the current LP solution". Failure. There are two current LP
> solutions.

You should use a separate function then, since this involves communication.

> NULL is never a good value to refer to a specific construct.

So, NULL should not refer to the best solution?

NULL is just a handy way of coding that you want the LP solutions - 
moreover, it allows a more direct way to access the information (we do 
not have to create a separate data structure for the LP solution).


Best,

Marc


More information about the Scip mailing list