[Coin-bcpdiscuss] Information on the children of a node

[Laszlo Ladanyi]

On Mon, 29 Jan 2007, Soumitra Pal wrote:

> Thanks Laci & Francois.
> 
> In fact, I have the code of CSP with me. Around six months back, I 
> posted a mail on this discussion group asking for an example CSP code 
> and one of the users, Dr. Rao, forwarded me the code since it was not 
> visible on the CVS that time. However, I did not use it because I got 
> busy with other work. Now I am giving more attention to my Masters 
> thesis and this code/BCP will definitely help me working out the ideas 
> we are having.
> 
> I could successfully build the example with the BCP_1.0.0. However, I am 
> not sure if I have the latest copy of the code since I got it long time 
> back. It will be great if you put it on SVN. From my experience, it 
> should not take much time. Only thing I had to do is to take Makefile.in 
> from other example (BAC) and change it for the CSP source files and use 
> configure to generate the Makefile.

The only work is that the interface has changed slightly since the CSP code
was written and it needs to be brought up-to-date.

> 
> However, I still have one doubt on the branching. From my current 
> understanding, vars[i]->is_non_removable() is true in both the children. 
> Right? Then how can we differentiate between the two children using this 
> information only?

Simply by looking at the bounds of the variable. 

> 
> Another problem which I think may come up some time later is the 
> following. In Vanderbeck 1999, it is proposed that there can be 
> branching on the sum of fractional variables instead of a single 
> fractional variable. However, according to my understanding, currently 
> branching in BCP is limited to single fractional variable. Is this correct?

No, it's not correct. A branching object in BCP is anything that (maybe after
adding cuts -- I mean that adding a cut can be part of how a branching object
functions) changes bounds on cuts and variables arbitrarily. Probably the
easiest way to achive Vanderbeck's rule is that you create a cut type of your
own (deriving from BCP_cut_algo) that you'll use for branching. When you
decide to branch and figured out which vars to include, just create a
branching cut and in the children set the cut's bounds as you like. You'll
probably have to store the indices (vars[i]->bcpind(), which is the index of
the var assigned by BCP to a variable, not its current position in the matrix)
of the affected variables in the cut as the matrix may change. Note that the
index of a var may be negative if it has not yet been sent to the tree
manager. In this case -vars[i]->bcpind() will be its final internal index.

> 
> Thanks
> Soumitra.
> 

I hope this helps,
--Laci