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

[Yiming Yao]

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

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