<br><font size=2 face="sans-serif">Yiming,</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">John</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>Yiming Yao <yao3@llnl.gov></b>
</font>
<br><font size=1 face="sans-serif">Sent by: coin-lpsolver-bounces@list.coin-or.org</font>
<p><font size=1 face="sans-serif">03/09/2006 07:26 PM</font>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif">John J Forrest/Watson/IBM@IBMUS</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td><font size=1 face="sans-serif">coin-lpsolver@list.coin-or.org</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">Re: [Coin-lpsolver] COIN/Cbc/Samples/qmip.cpp</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=3>John,<br>
<br>
Thanks for looking into it and quickly replying to my question.<br>
<br>
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.) <br>
<br>
Is it possible that something in CbcModel has caused the B&B process
to stop prematurely?<br>
<br>
Best regards,<br>
<br>
Yiming<br>
<br>
<br>
At 11:46 AM 3/9/2006, John J Forrest wrote:<br>
</font>
<br><font size=2>Yiming,</font><font size=3> <br>
</font><font size=2><br>
The problem does not seem to be convex and the solution giving 0.0 is a
local optimum.</font><font size=3> <br>
</font><font size=2><br>
John Forrest</font><font size=3> <br>
<br>
</font><font size=1><b><br>
Yiming Yao <yao3@llnl.gov></b> <br>
Sent by: coin-lpsolver-bounces@list.coin-or.org</font><font size=3> <br>
</font><font size=1><br>
03/08/2006 08:56 PM</font><font size=3> </font>
<div align=right>
<br><font size=1>To</font></div>
<br><font size=1><coin-lpsolver@list.coin-or.org>, John J Forrest/Watson/IBM@IBMUS</font><font size=3>
</font>
<div align=right>
<br><font size=1>cc<br>
Subject</font></div>
<br><font size=1>[Coin-lpsolver] COIN/Cbc/Samples/qmip.cpp</font><font size=3>
<br>
<br>
<br>
<br>
<br>
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:<br>
<br>
N0C0=N1C0=N2C0=N3C0=1 and min obj = 0<br>
<br>
This is not the minimum solution. Either N0C0=N1C0=N2C1=N3C1=1 or N0C1=N1C1=N2C0=N3C1=1
will result in obj = -6<br>
<br>
Would you take a look at it and see what's gone wrong?<br>
<br>
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.</font><font size=3 face="Courier New"><br>
<br>
The variables are indexed as below:<br>
0 N0C0<br>
1 N0C1<br>
2 N1C0<br>
3 N1C1<br>
4 N2C0<br>
5 N2C1<br>
6 N3C0<br>
7 N3C1<br>
</font><font size=3><br>
Thanks,<br>
<br>
Yiming<br>
<br>
----------------------------------------------------------------<br>
Yiming Yao
<br>
Systems & Decision Sciences Section yao3@llnl.gov
<br>
Lawrence Livermore National Laboratory Tel: 925-422-1922
<br>
7000 East Avenue, L-377<br>
Livermore, CA 94550<br>
----------------------------------------------------------------<br>
<br>
<br>
<br>
</font><font size=2 face="Courier New"><br>
_______________________________________________<br>
Coin-lpsolver mailing list<br>
Coin-lpsolver@list.coin-or.org</font><font size=2 color=blue face="Courier New"><u><br>
</u></font><a href="http://list.coin-or.org/mailman/listinfo/coin-lpsolver"><font size=2 color=blue face="Courier New"><u>http://list.coin-or.org/mailman/listinfo/coin-lpsolver</u></font></a><font size=3><br>
<br>
<br>
<br>
_______________________________________________<br>
Coin-lpsolver mailing list<br>
Coin-lpsolver@list.coin-or.org</font><font size=3 color=blue><u><br>
</u></font><a href="http://list.coin-or.org/mailman/listinfo/coin-lpsolver"><font size=3 color=blue><u>http://list.coin-or.org/mailman/listinfo/coin-lpsolver</u></font></a>
<br><tt><font size=2>_______________________________________________<br>
Coin-lpsolver mailing list<br>
Coin-lpsolver@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/coin-lpsolver<br>
</font></tt>
<br>