[Coin-lpsolver] COIN/Cbc/Samples/qmip.cpp

[John J Forrest]

Yiming,

I agree the partial derivative is -1 but that variable is at its upper 
bound.  I looked at computation of gradient and it seemed to check out.

John



Yiming Yao <yao3 at llnl.gov> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
03/09/2006 07:26 PM

To
John J Forrest/Watson/IBM at IBMUS
cc
coin-lpsolver at list.coin-or.org
Subject
Re: [Coin-lpsolver] COIN/Cbc/Samples/qmip.cpp






John,

Thanks for looking into it and quickly replying to my question.

I've not verified that the objective function (f) is nonconvex. Whether 
it's convex or not, the solution (N0C0=N1C0=N2C0=N3C0=1 and 
N0C1=N1C1=N2C1=N3C1=0) shouldn't be a local minimum because the gradient 
of f is not a 0-vector at this point. (The partial derivative wrt N0C0 = 
1-8+4+2= -1.) 

Is it possible that something in CbcModel has caused the B&B process to 
stop prematurely?

Best regards,

Yiming


At 11:46 AM 3/9/2006, John J Forrest wrote:

Yiming, 

The problem does not seem to be convex and the solution giving 0.0 is a 
local optimum. 

John Forrest 


Yiming Yao <yao3 at llnl.gov> 
Sent by: coin-lpsolver-bounces at list.coin-or.org 

03/08/2006 08:56 PM 
To
<coin-lpsolver at list.coin-or.org>, John J Forrest/Watson/IBM at IBMUS 
cc
Subject
[Coin-lpsolver] COIN/Cbc/Samples/qmip.cpp 




I tried to use qmip.cpp in Cbc/Samples (downloaded March 7) to solve a 
simple quadratic 0-1 integer program (qmip1.mps) and got the following 
solution:

N0C0=N1C0=N2C0=N3C0=1 and min obj = 0

This is not the minimum solution. Either N0C0=N1C0=N2C1=N3C1=1 or 
N0C1=N1C1=N2C0=N3C1=1 will result in obj = -6

Would you take a look at it and see what's gone wrong?

As an experiment, I made the coefficient of the N0C0*N1C0 in the objective 
function very large relative to other terms (see qmip2.mps), preventing 
N0C0 and N1C0 from being 1 at the same time, qmip then produced a correct 
answer: N0C1=N1C1=N2C0=N3C1=1 with obj = -6.

The variables are indexed as below:
0 N0C0
1 N0C1
2 N1C0
3 N1C1
4 N2C0
5 N2C1
6 N3C0
7 N3C1
 
Thanks,

Yiming

----------------------------------------------------------------
Yiming Yao 
Systems & Decision Sciences Section         yao3 at llnl.gov 
Lawrence Livermore National Laboratory      Tel: 925-422-1922 
7000 East Avenue, L-377
Livermore, CA 94550
----------------------------------------------------------------




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



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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20060309/db4ab608/attachment.html>