<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Le 12/02/2013 18:46, Changhyeok Lee a
écrit :<br>
</div>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">Hello,</pre>
</blockquote>
<br>
Hi,<br>
<br>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">I'm also using Coin-BCP to implement a branch-and-price algorithm. As far as I know, one should override "generate_vars_in_lp" and "vars_to_cols" functions (and "compute_lower_bound") to implement the branch-and-price.</pre>
</blockquote>
Sure.<br>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">In "generate_vars_in_lp", the user is supposed to return newly added variables to Bcp and in "vars_to_cols", the user is supposed to return the column information of the newly added variable to Bcp. This is achieved by receiving the address of BCP_vec< …. > as a parameter and add relevant objects to the vector.</pre>
</blockquote>
Yes.<br>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">Then, the internal functions in the Bcp package will do the rest - adding generated variables to the restricted master problem ( i.e. whatever OsiSolverInterface instance the user is using) and re-optimze. So, basically you don't need to worry about them. If there are new variables, the LP iteration will continue, otherwise, it will proceed to, say, branching decision.</pre>
</blockquote>
Yes.<br>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">One caveat is that in the original implementation of "compute_lower_bound", if the column generation option is turned on (btw, you have to turn this option on by specifying "colgen = BCP_GenerateColumns" in "init_new_phase" function in tree manager class), it simply does not update the lower bound. However, if there's no column to be generated, we should update the lower bound to the new LP objective value.</pre>
</blockquote>
This is the problem. When BCP prune nodes, it uses the lower bound
given by the LP relaxation,<br>
even if <i>colgen </i>is set to <i>BCP_GenerateColumns</i> in <i>init_new_phase
function</i>.<br>
<blockquote
cite="mid:49AF9D07B4FC4E6B9163456206A754A4@u.northwestern.edu"
type="cite">
<pre wrap="">In order to fix this, we have to do the following: Implement the code that is supposed to be in "generate_vars_in_lp" in the "compute_lower_bound" function. and tell "compute_lower_bound" function to update the lower bound, if there's no column to be added, otherwise do not update. Save the generated variable information (e.g. as a member variable of "…_lp" class). In "generate_vars_in_lp", simply return the saved information to Bcp. </pre>
</blockquote>
Yes, I think this is a way to do it.<br>
<br>
What I did is different. I finally managed to have it working.<br>
<br>
In the <i>compute_lower_bound</i> method, I modify the <i>true_lower_bound</i>
value of the node object,<br>
and I return a value such as BCP never prune the node.<br>
Then, in the branching phase, I'm sure that all variables to be
generated have been generated,<br>
and that the LP value is a true lower bound.<br>
So, in the function where a branching object is created (<i>select_branching_object</i>
as far as I can remember),<br>
<i>BCP_DoNotBranch_Fathomed</i> may be returned according to the LP
bound.<br>
Everything is working now but it looks like a hack ...<br>
<br>
Thanks for you response.<br>
<br>
Xavier Schepler<br>
PhD student, Université du Havre, France<br>
<br>
</body>
</html>