[Coin-bcpdiscuss] BCP and column generation - some questions.

[Marc Sol]

Hi all,

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.

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?

(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?

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/bcp/attachments/20060828/7c68ca3e/attachment.html