[Coin-lpsolver] CLP: Question about current state of QP solving capabilities.

[John J Forrest]

Christian,

Not much work has been done on either algorithm recently, but some bugs 
have been fixed and performance seems reasonable with some caveats.

1.  With the default Cholesky ordering and factorization I would guess 
that a problem of the size you describe would be fairly slow.  You would 
need to download an alternative open source ordering and factorization 
e.g. from University of Florida.  With the new build procedures it should 
be possible to make this easy, but I am not an expert in automake etc. See 
ClpCholeskyUfl.?pp for where to get code and what defines are needed.  If 
your quadratic objective is dense then it may still be fairly slow.

2.  The Simplex algorithm is just primal.  There is also a robust SLP 
(Sequential Linear Program) method to obtain an approximate answer to any 
nonlinear objective function.  Often the best way to solve a problem is to 
run this first and then the Quadratic Simplex which often takes zero 
iterations.

3.  Presolve with QP is not too reliable.

Having said all that I have just run qgrow22 from maros test set - 440 
rows and 946 columns using standalone solver

clp qgrow22.sif -presolve off -primals   => QP simplex 7.8 seconds
clp qgrow22.sif -presolve off -slp 20 -primals => QP simplex after SLP 
(does 2 QP iterations) 0.53 seconds
clp qgrow22.sif -presolve off -barrier => QP barrier WITH bad ordering 
0.26 seconds

So see if you need to download a better ordering.

John Forrest



Christian Kirches <christian.kirches at gmail.com> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
09/16/2007 01:16 PM

To
coin-lpsolver at list.coin-or.org
cc

Subject
[Coin-lpsolver] CLP: Question about current state of QP solving 
capabilities.






Dear COIN-OR developers,

I have browsed through CLP's documentation, FAQ, and example programs, 
and was left in doubt a bit about CLP's QP solving capabilities. On the 
one hand, the FAQ entry clearly states that QP solving using the 
interior-point code is in an early state of development only, but 
nonetheless usually more efficient that the quadratic simplex code. On 
the other hand, that FAQ entry dates back to 2004 and seemingly refers 
to a 0.9x version wheres I find 1.5.0 being the most recent revision.

I would be extremely grateful if you could elaborate on the current 
state of the two algorithms regarding the solution of convex / 
semidefinite QPs with a size of ~500 variables and ~1000 linear 
constraints ?

Best regards,
Christian Kirches

-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             Dipl.-Math. Christian Kirches

           Simulation and Optimization Group
Interdisciplinary Center for Scientific Computing (IWR)
        Ruprecht-Karls-University of Heidelberg

address: Im Neuenheimer Feld 368, D-69120 Heidelberg
e-mail:  christian.kirches at iwr.uni-heidelberg.de
phone:   +49 6221 54 8895 
room:    414
                         Private

address: Stahlbuehlring 143, D-68526 Ladenburg
e-mail:  christian.kirches at gmail.com
phone:   +49 6203 922 681
mobile:  +49 176 21 72 37 22
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

_______________________________________________
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/20070917/0db6a201/attachment.html>