[Scip] B&BC Vs B&PC

[Gerald Gamrath]

Hi Vivek,

I'm not sure that I got your questions, but let me try to answer it.

First: I guess B&BC should be branch-and-cut and B&PC should be
branch-price-and-cut?

If you start with a restricted problem, with just some of the
(exponentially many) variables added, your question is what is faster:
solving this restricted problem by branch-and-cut or (producing a
potentially suboptimal solution) or solving it by branch-cut-and-price?
Then just doing branch-and-cut should normally be faster, much more
reductions can be found, e.g., in presolving, and you don't have the
pricing effort (but you won't reach global optimality). On the other
hand, if you start your branch-and-price approach with a smaller number
of variables, say 200 and only price those which are really needed, the
situation might change, because you will probably have less variables in
total at the end. But I would still guess that due to the pricing
effort, a pure branch-and-cut approach would be much faster, as long as
the restricted problem you solve has a reasonable size (which 20k x 22k
normally is).

If you can send me your restricted problem with the 20000 variables (as
.lp or .mps file), I could have a look at it and perhaps tell you some
parameter changes which improve the performance on that specific (type
of) instance.

Best,
Gerald

On 09.04.2013 16:46, Vivek Periaraj wrote:
> Hi Scip,
>
> Was wondering about it.
>
> Suppose I generate a set of columns of a MIP and then use B&BC on that generated columns, instead of B&PC, would my complexity with respect to performance remain the same?
>
> I am currently not interested in optimal solutions but only near optimal solutions.
>
> I have about 20000 columns and 22676 rows, and B&BC takes a long time. Wondering if doing pure B&PC, would improve my performance. Is there a benchmarking between B&BC on reduced MIP versus B&PC?
>
> I hope my question is valid.
>
> Regards,
> Vivek.
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip