[Scip] Branch, price and cut : how to update the farkas pricing?

[nikolaj@crt.umontreal.ca]

On Tue, September 7, 2010 7:14 pm, Gerald Gamrath wrote:
> Hi Nikolaj,

Hello Gerald and everybody else,

> 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.

Yes. For the moment (maybe there is something I don't see?), I do see big
implementation differences between the two.If you add the cuts only at the
root node, there are there once and for all, while if you add them locally
at every node of the search tree, you have to update the dual accordingly
(i.e. locally).


> 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.

Yes, this is what I was talking about.

>> 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.

If the cut is only valid locally, I have to know if this cut is active or
not at the current node.

>>
> 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.

This is understood.

 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.

I have an original formulation but still I don't find this easy (to write
efficient code (or even code that works! ;-) )).

> 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.

Is this really so? If I know for sure that an added cut will not cut off
any feasible solution and I have enough variables to find a feasible
solution, I guess the farkas pricing will never be called at all as the
LPs will remain feasible.

For the reduced cost pricing, there is something I don't understand: if I
don't update the dual model with the corresponding dual variable to the
new added primal cut, I still have the original model. If the reduced cost
pricing doesn't return any new variable, doesn't this mean that the
original model is solved to optimality?

I have implemented that and it looks like it is working (quite well). Is
this pure luck?

> 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.

Yes, I'm a beginner discovering like a newborn baby. Sorry if I say silly
things, I really would like to understand what is happening.

Your answers help me a lot and I thank you very much for your insights.

I'll implement a version where I update the dual in the more classical
(and only?) way.

>
>
> Best regards,
> Gerald
>

Have a nice day/night.

Best regards,

Nikolaj
>