[BCP] BCP 1.2.0 question, BCP_vg_user vs. BCP_tm_user::generate_vars_in_lp

[Laszlo Ladanyi]

On Wed, 22 Oct 2008, Laszlo Ladanyi wrote:

> Hi Sebastian,
>>
>>  LinearProgram::generate_vars_in_lp, fathom 0
>>  LP:   Number of vars received from VG: 0
>>  LP:   Total number of vars in local pool: 0
>>  LP:   In iteration 1 BCP generated 0 cuts , 0 vars before calling branch()
>>
>> then Bcp continues, and fails with:
>>  LP: Default select_branching_candidates() executed.
>>  BM: Couldn't branch!
>>
>> Which could be legit but is still strange as the core variables/columns
>> I added ensure feasibility and the root node solution is integral.
>> (Hence without added columns it should be recognized as optimal solution.)
>
> Hmmm..., this is odd. Is there any output beforehand that indicates that a
> feasible solution is found? You should get the "Couldn't branch" message
> only if the current node is not integral feasible, no vars/cuts are added
> and yet every var that's declared integer has an integer value. One
> possibility is that feasibility checking has a different zero tolerance
> than the branching (hence a solution might not be found feasible but then
> later no branching var can be selected), but I think I have rooted out all
> such problems. Can you share the code with me? I could try to look into what's
> going on.
>

I was wrong... You should get the "Couldn't branch" message if BCP thinks that 
it must branch, but couldn't. How can this happen? Why does BCP think that it 
must branch? Well, it must branch if the current upper bound is higher than 
the current lower bound (forget about various gaps for now). In your case the 
upper bound is the feas solution found, but what is the lower bound? The lower 
bound is *NOT* te value of the LP relaxation. That would be the lb if no 
columns were generated, but you have specified that you will generate columns.

So column generation code will work properly only if the compute_lower_bound() 
method is implemented properly which should return a true lower bound (one 
that's correct no matter what cols could still be generated) for the current 
node. By default this routine returns the old lower bound if columns are to be 
generated. The starting lb is -inf, so if you have not implemented this 
method then the lb stays -inf forever, so BCP will want to keep branching.

A related question is how to generate a true lower bound. Well, that's not 
trivial :-). Usually what happens is that the columns that can be generated 
form several cliques so in any solution you can have at most one column from 
any of the cliques. Then if you can estimate the most negative reduced cost 
for every clique then a true lower bound is the current LP relaxation value 
plus the sum of those most negative reduced costs.

I hope this describes the problem clearly and you can get going.

Cheers,
--Laci

>>
>> Thanks a lot,
>> Sebastian
>>
>> PS: The .hpp documentation of Bcp is quite detailed and understandable,
>> I am positively surprised!
>
> Hey! I'm positively surprised that someone finds the docs understandable! :-)
>
>> _______________________________________________
>> BCP mailing list
>> BCP at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/bcp
>>
>
> Thanks,
> --Laci
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>