[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