[Scip] Branch, price and cut : how to update the farkas pricing?
Gerald Gamrath
gamrath at zib.de
Wed Sep 8 01:14:43 MEST 2010
Hi Nikolaj,
> I did some research about actual code with SCIP but I didn't find any. Are
> there some examples of a Branch, price and cut (and not Branch, cut and
> price)?
>
how do you define branch, price and cut and banch, cut and price? Does
the former mean that you create cuts at each node of the
branch-and-bound tree while cuts are only created at the root node for
the latter approach? I don't know of a branch-and-price code with SCIP
that generates cuts not only at the root node, but I don't think that it
should be a big difference to creating cuts only at the root node.
> I have some ideas on how to update the farkas pricing but I find them too
> complicated. Probably, there is a common way of doing so. What is it?
>
> Here comes a more detailed explanation of what I'm trying to do.
>
> I have a core LP (the model) that I've implemented as in the example
> "SamplePricer". This works well with a fixed dual model. Now, if I want to
> add a primal constraint (a cut or a branching constraint) to the original
> model, I wonder how can I easily update the dual model? I have to add the
> dual variable corresponding to this constraint. If the constraint is local
> (as a branching constraint), this has to be done for the node and all its
> successor. If it is a global constraint, I would like to update it for the
> whole tree.
What do you mean with updating the dual model? If you add a primal
constraints, this corresponds to adding a dual variable and SCIP can
then give you the dual solution value of this variable after the LP was
solved to optimality.
> I guess that for the local constraint, I have to use the
> callbacks CONSACTIVE and CONSDEACTIVE of a constraint handler.
This is a common way to handle branching decisions in SCIP for a
branch-and-price approach (see the Coloring example). In this way, you
can for example update the data that is used for the pricing. However, I
don't exactly understand why you want to do this for cuts? In my
understanding, a cut is just a row in the LP. So this row gives rise to
a dual variable and you should probably just check for cuts in the
current LP, get the dual solution values and update the pricing problem
accordingly.
> But how do
> I test if a primal variable could be added to make the LP feasible again
> in the farkas pricing? I guess I have to update the dual constraint
> associated to that variable by adding the dual variable associated to the
> primal constraint I've just added. How can I do this easily?
>
Well, Farkas pricing is actually the same as reduced cost pricing, you
just use the Farkas multipliers instead of the dual solution values and
use a zero objective function. So you can do this similarly to the
reduced cost pricing.
But, as I mentioned in a mail before, respecting the dual variables
corresponding to cuts in the pricing problem is the hard part of
branch-cut-and-price. This is relatively easy if you have an original
formulation, as Marco suggested, but if you don't have one, then there
is no general way to do this.
> Another related question. I generate new primal variables by inspecting
> the corresponding dual constraint. If this dual constraint is violated, I
> add the variable (well, I find the "best" violated constraints and only
> add some of them). If I add a primal constraint that could make a LP
> infeasible I guess I have to update the dual by adding the corresponding
> dual variable. But if I add a primal constraint that I'm certain can not
> make any LP infeasible I guess I don't have to update the dual. But if I
> do update the dual, will this improve the search for primal variables (in
> the reduced cost pricing or/and farkas pricing)?
>
You always have to take the dual solution values of cuts into account in
your pricing problem - for Farkas pricing as well as for reduced cost
pricing. Otherwise, the cut won't help, since the pricing process can
just generate the same variables again without entry in the cut and
restore the former solution.
> I hope I'm clear enough otherwise tell me and I'll rephrase my two
> questions. Pricing is new to me and I'm discovering this fascinating
> world.
> So maybe my questions don't make too much sens. I don't know.
>
Yes, some of your questions show that you are just beginning to do
branch-cut-and-price. But they also remember me of the questions I had
when I started with this topic. :-) So I hope, I was able to help you a bit.
Best regards,
Gerald
More information about the Scip
mailing list