<html><body>
<p>Sebastian,<br>
<br>
I know Clp QP is a mess - and I don't have the time to fix it.<br>
<br>
SLP is a fairly rugged trust region approach. If I have to solve a large QP I do something like -<br>
<br>
switch off presolve as there may be bugs<br>
nonlinearSLP(20,1.0e8) i.e. just a few iterations - although that can vary<br>
primal() which works a lot lot better given a near optimal solution<br>
<br>
John<br>
<img width="16" height="16" src="cid:1__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt="Inactive hide details for Sebastian Nowozin ---09/16/2008 08:51:31 AM---Dear all,"><font color="#424282">Sebastian Nowozin ---09/16/2008 08:51:31 AM---Dear all,</font><br>
<br>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">From:</font></td><td width="100%"><img width="1" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">Sebastian Nowozin <nowozin@gmail.com></font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">To:</font></td><td width="100%"><img width="1" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">Discussions about open source software for Operations Research <coin-discuss@list.coin-or.org></font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">Date:</font></td><td width="100%"><img width="1" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">09/16/2008 08:51 AM</font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">Subject:</font></td><td width="100%"><img width="1" height="1" src="cid:2__=0ABBFE54DFA2EDE38f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">[Coin-discuss] Another Clp QP question</font></td></tr>
</table>
<hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br>
<br>
<br>
<tt><br>
Dear all,<br>
<br>
sorry, I have some more Clp QP questions. I need to solve a QP problem <br>
of the form:<br>
<br>
min 0.5 x'Ix + f'y<br>
x,y<br>
sb.t. y >= 0,<br>
Ax + By >= c. (1)<br>
<br>
with delayed constraint generation for the set (1) where a few hundred <br>
rows are added per iteration. The problem has < 50k variables, and < 5k <br>
constraints, with a block-sparsity such that a total of ~10% of the <br>
elements in A are set, B has only one non-zero per row. The QP solution <br>
time is not very important, though it would be nice to warmstart from a <br>
previous solution. The number of rows should be kept small by pruning <br>
inactive constraints (either by duals of these constraints or by <br>
identifying non-binding rows manually). For constraint generation I do <br>
not need the dual multipliers, only the primal restricted solution x of <br>
that iteration.<br>
<br>
Using COIN-OR Clp, I have identified the following options I can use:<br>
<br>
1. ClpSimplex::nonlinearSLP(5000, 1e-8);<br>
works reasonably well, but gives poor dual variables, making it <br>
difficult to prune the constraint set. Also, I am not sure I understand <br>
its workings well enough to trust it.<br>
<br>
2. ClpSimplex::primal();<br>
does not work well, cycles forever.<br>
<br>
3. ClpSimplex::initialBarrierSolve();<br>
surprisingly (this is ClpSimplex after all), seems to work <br>
nicely, although slow and using a lot of memory once the problem grows.<br>
<br>
4. Instantiating ClpInterior and using:<br>
ClpInterior model;<br>
model.borrowModel(simplex);<br>
ClpCholeskyBase * cholesky = new ClpCholeskyBase();<br>
cholesky->setKKT(true);<br>
model.setCholesky(cholesky);<br>
model.primalDual();<br>
model.returnModel(simplex);<br>
is not stable, mostly crashing with "dual goes to infinity" message.<br>
<br>
Are there any general recommendations on how to use Clp for the above <br>
problem? The QP functionality is almost not documented at all and I <br>
would be grateful for any advice.<br>
<br>
Thanks,<br>
Sebastian<br>
_______________________________________________<br>
Coin-discuss mailing list<br>
Coin-discuss@list.coin-or.org<br>
</tt><tt><a href="http://list.coin-or.org/mailman/listinfo/coin-discuss">http://list.coin-or.org/mailman/listinfo/coin-discuss</a></tt><tt><br>
</tt><br>
<br>
</body></html>