[Coin-bcpdiscuss] Branching by cuts

[Lasse Nisted]

Hello Carlos

My understanding is that you would like to branch by adding cuts and
use different cuts for each child.

I would do it in select_branching_candidates.
Create a branching object:
    BCP_lp_branching_object(
                                        2,           // two children
                                        0, &newCuts, // new cuts
                                        0, &boundsPos,// indices of bounds
                                        0, &bounds,// bounds
                                        0,0,0,0); // nothing implied.
newCuts should contain the cuts. boundsPos should contain indices for
cuts for which you make new bounds. For the newCuts negative indices
are used. So for the cut newCuts[0], you would have -1 contained in
boundsPos, for cut newCuts[1] you need -2 in boundsPos.

In bounds you have the bounds that are applied for cuts in each child.
For the cut indexed by boundsPos[0]   bounds[0] is the lower bound in
child one, bounds[1] is the upper bound in child one. bounds[2] is the
lower bound of child two, and bounds[3] is the upper bound of child
two.

So lets say you create two cuts, one for child one and another for
child two. Then add those two cuts to newCuts. Add -1 and -2 to
boundsPos and then insert
[childOneCutLB], [childOneCutUB], [-infty], [infty] and [-infty],
[infty], [childTwoCutLB], [childTwoCutUB] into bounds.
This would make the childOneCut get the bounds
[childOneCutLB,childOneCutUB] in child one, and [-infty,infty] in
child two, practically making it unused in child two. Similarly the
other cuts is only used for child two.


I hope this helped,
- Lasse Nisted

On 7/5/07, Carlos Eduardo de Andrade <ce.andrade at gmail.com> wrote:
> Hello people,
>
> My algorithm branch by cuts, implicitly. It holds the information of
> this branching's in user data, that I use to column generation. So,
> the master problem is treated like a original master and branching
> restrictions are implicitly treated.
>
> I would like to modify this behavior, inserting some branching
> restrictions in master formulation. So, the restrictions should be
> inserted in formulation before we process the
> tree node in the question. But, you note that I like to insert this
> restrictions like cuts and not like BCP branching restrictions. I like
> treat the branching implicitly yet. I would like insert this
> cuts/branching restrictions in one of children, not in both.
>
> But I don't know to do this in BCP. The branching restrictions are
> like cuts, but I have to insert then before column generation. Well,
> where do I put the code to add branching restrictions (cuts)? I think
> that "select_branching_candidates()" is a good place, but how to
> insert the branching restrictions in only one child node? Track who is
> child node is simple, I think, because each child node have a proper
> data and a unique ID. Can somebody help me?
>
> Thank very much. Regards,
>
> Carlos
>
> p.s. Sorry my English.
> --
> Carlos Eduardo de Andrade
> Algorithms and Programming, Operation Systems
> Escola Agrotécnica Federal de Inconfidentes - Brazil
>
> _______________________________________________
> Coin-bcpdiscuss mailing list
> Coin-bcpdiscuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss
>