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

[Soumitra Pal]

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.

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?

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?

Thanks
Soumitra.

Laszlo Ladanyi wrote:
> Francois' suggestion is one way to do it, and another way is to use info
> directly from the branching variables. In initialize_new_search_tree_node()
> vars[i]->is_non_removable() is true iff the variable is has been branched on.
> This gives you which pattern to exclude. 
>
> In fact, we have a paper about how BCP can be used for rapid prototyping of
> algorithms (http://www.springerlink.com/content/w6645815gp163275/), and the
> example we used was the cutting stock problem with branch and price :-).  
> It's not a terribly fast code; there's no good preprocessing specific to the
> cutting stock problem, no good heuristic, but it does show how bcp can be
> used.  
>
> The code was on cvs, but I haven't ported it to the svn repository yet. If
> you'd like, sometime next week I can move the code to svn and make sure that
> it compiles and runs. Then you can extend it any way you like. And if yo ufeel
> like you can contribute the changes back to make it a better code :-).
>
> --Laci
>
> On Sun, 28 Jan 2007 fmargot at andrew.cmu.edu wrote:
>
>   
>> Sumitra:
>>
>> One way to do this is to use BCP_user_data. When the sons are created,
>> put a flag in a BCP_user_data object to identify which is which. This
>> is described in bac.pdf (although not for column generation) 
>> that you can find in the subdirectory Bcp/examples/BAC of your
>> installation directory.
>>
>> Francois
>>
>>
>> On Sun, 28 Jan 2007, Soumitra Pal wrote:
>>
>>     
>>> Hi,
>>>
>>> I am trying to implement the branching strategy used by "P.H. Vance. 
>>> Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem, 
>>> Computational Optimization and Applications, 9(3):211?228, 1998." for solving 
>>> the cutting stock problem. The problem is solved using column generation.
>>>
>>> According to the strategy, on one branch the solver to the subproblem should 
>>> not generate one particular pattern (or column). So, I need to identify the 
>>> node in the BCP_user_lp::initialize_new_search_tree_node() function. This 
>>> should be easy if I could store the indices of the two children created in 
>>> the BCP_user_lp::set_actions_for_children() function and check the index in 
>>> the initialize_new_search_tree_node() function. However, I cant see how to do 
>>> this. It will be great if somebody explains this.
>>>
>>> Also, I will be thankful if you explain me the term "phase" as returned by 
>>> the function current_phase() in the BCP parlance.
>>>
>>> Thanks in advance,
>>> Soumitra.
>>>
>>>
>>>
>>>       
>> _______________________________________________
>> Coin-bcpdiscuss mailing list
>> Coin-bcpdiscuss at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss
>>
>>     
>
>