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

[Marc Sol]

Thanks Gleb,

I moved the call to my column generation algorithm to
compute_lower_bound. This function now returns 0.0 if I found new
columns (since we don't now a true lower bound yet). Otherwise it
returns the rounded-up LP value. BCP now nicely discovers the integer
solutions during column generation. So that is solved. Thanks.

My other problem is still there. I retrieve the dual vector as follows:
In compute_lower_bound, I receive the current LP solution in the
argument lpres (of type const BCP_lp_result&). I retrieve the dual
vector through:
	const double* pi = lpres.pi();
In this way, in the second iteration, I get the same dual vector
(pi[.]=1.0 for all cuts) as in iteration 1, although the LP primal
solution (Z_LP) has a lower value. And I believe that for a set covering
problem with all column costs = 1, we should have
	sum(pi[.]) = Z_LP = sum(x[.])
But in my case, in iteration 2, I have  
	sum(pi[.]) <> Z_LP = sum(x[.])
Any thoughts on this one?

Kind regards,
Marc Sol


-----Original Message-----
From: coin-bcpdiscuss-bounces at list.coin-or.org
[mailto:coin-bcpdiscuss-bounces at list.coin-or.org] On Behalf Of Gleb
Belov
Sent: Tuesday, August 29, 2006 9:45
To: coin-bcpdiscuss at list.coin-or.org
Subject: [Coin-bcpdiscuss] Re: Coin-bcpdiscuss Digest, Vol 18, Issue 1

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
>**********************************************
>
>
>  
>

_______________________________________________
Coin-bcpdiscuss mailing list
Coin-bcpdiscuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss