[Coin-discuss] Small problem with BCP's LP_user::compare_vars

[Laszlo Ladanyi]

Thanks for the post! Comments are always welcome, whether it's a specific
question, a suggestion, a bugfix or voluteering to maintain parts of the code
:-).

On Wed, 1 May 2002, Juan Pablo Vielma wrote:

> Hi everyone
> 
>             I been working (trying at least ;-) ) with BCP for a while and
> inspired by the recent submissions I will start posting some small bugs and
> suggestions.   
> 
>             The first one is regarding the CompareNewVarsToOldOnes LP
> parameter and LP_user::compare_vars function. In combination they are used
> to check if new variables ( form column generation, etc) are different from
> variables already in the formulation.    
> 
>             The "problem" is that this works for variables generated in the
> variable generation module ( BCP_vg_user derived class ), but not for
> variables generated in BCP_lp_user's derived generate_vars_in_lp
> functions. This can only be noticed by reading the source code and there
> doesn't seem to be any reference about this in the documentation.    
> 

The meaning of CompareNewVarsToOldOnes is slightly different than you describe
above.

BCP assumes that every variable generated will have negative reduced cost
(minimization). Since the LP relaxation was solved to optimality, every column
in the current formulation has nonneg reduced cost. Therefore it's not worth
to compare with columns already in the formulation, it's much faster to
compute the reduced costs for the newly generated columns. 

On the other hand there is a local pool in the LP process which keeps those
variables that have been generated in some earlier round, but did not make it
into the formulation (there was a limit on how many vars can be added and
there were more than that many vars w/ negative reduced cost). The parameter
instructs BCP to compare the newly generated columns with those in this local
pool. And you are right, it should probably compare the vars generated in the
LP to the content of the local pool as well. When I have time I'll fix it. Or
if you'd like to contribute a fixed I'd really appreciate it. :-)

>             I am not sure if this really qualifies as a "bug", but at least
> a warning note in the documentation would be nice. 
> 
>             I haven't check, but this probably applies to the cut comparison
> functions. 
> 

Yes it does. 

> 
> 
> Juan Pablo Vielma
> jvielma at dim.uchile.cl
> Departamento de Ingenieria Matematica
> Universidad de Chile
> 

--Laci