[Coin-bcpdiscuss] Re: Coin-bcpdiscuss Digest, Vol 18, Issue 1

[Gleb Belov]

Dear Marc Sol,

>I am doing some experiments with BCP to see what it can do. Looks great
>so far. But getting it to work under Microsoft Visual Studio would
>really be an enormous improvement. If I could just step through the code
>in a debugger this would speed up learning the framework.
>  
>
Yes, but when you get used to gdb, it is almost as effective

>Anyway, I am now experimenting (under cygwin) with a set covering and
>column generation approach to the cutting stock problem (just to learn
>how column geration should work in the BCP framework). App_lp is my
>class derived from BCP_lp_user. I come across the following issues that
>I don't understand.
>
>(1) In App_lp::test_feasibility I must return 0 (false) if I still have
>algorithmic variables that should be added. To me this appears strange
>since the fact that algorithmic variables should be added should only
>impact optimality but not feasibility. In a set covering problem, during
>the column generation phase in the root node one can encouter feasible
>integer solutions even if not all columns have been added. Anyway I now
>have to search for new columns based on the lp solution that I receive
>in test_feasibility. I store these columns in a local column pool. I
>ignore the lp solution that I receive in generate_vars_in_lp and just
>add the columns from my local pool. Is this a correct approach? Are both
>lp solutions identical?
>  
>
You are right, feasible (and even optimal) solution can be found before 
LP optimum. The standard way to handle column generation in a 
single-thread implementation is to generate new cols in 
compute_lower_bound and to add them in generate_vars_in_lp, see examples.

>(2) After I have added a first set of columns, BCP goes into iteration
>2, visible from
>LP: *** Starting iteration 2 ***
>The output shows that my new variables have been added (matrix size
>increased), and the solution value has gone down (good)
>But then again in test_feasibility, the dual solution is still the
>solution from iteration 1. This looks like a bug ... but I am too new to
>BCP to dare claim that it is a bug. :-) More precise, I initialize the
>algorithm with an identity matrix, such that the solution in iteration 1
>has all vars x[.] = 1 and all dual variables pi[.]=1.0  In iteration 2,
>still all pi[.] = 1.0 and sum(pi[.]) <> primal value ... Then of course
>my column generator calculates the same columns as in iteration 1 and
>just adds them to the LP. In iteration 3, I now do get a correct dual
>solution. Am I doing something wrong here?
>  
>
Don't know how you pass the dual values. Check that or try it as above.

Regards
Gleb

>I hope someone can help me with these questions. I really do like this
>BCP framework and the open-source approach to OR software, so I am
>looking forward to any reply.
>
>
>Kind regards,
>Marc Sol
>
>
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: http://list.coin-or.org/pipermail/coin-bcpdiscuss/attachments/20060828/7c68ca3e/attachment-0001.html
>
>------------------------------
>
>_______________________________________________
>Coin-bcpdiscuss mailing list
>Coin-bcpdiscuss at list.coin-or.org
>http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss
>
>
>End of Coin-bcpdiscuss Digest, Vol 18, Issue 1
>**********************************************
>
>
>  
>