[Coin-discuss] Another Clp QP question

[John J Forrest]

Sebastian,

I know Clp QP is a mess - and I don't have the time to fix it.

SLP is a fairly rugged trust region approach.  If I have to solve a large
QP I do something like -

switch off presolve as there may be bugs
nonlinearSLP(20,1.0e8) i.e. just a few iterations - although that can vary
primal() which works a lot lot better given a near optimal solution

John

                                                                                                                
  From:       Sebastian Nowozin <nowozin at gmail.com>                                                             
                                                                                                                
  To:         Discussions about open source software for Operations Research <coin-discuss at list.coin-or.org>    
                                                                                                                
  Date:       09/16/2008 08:51 AM                                                                               
                                                                                                                
  Subject:    [Coin-discuss] Another Clp QP question                                                            
                                                                                                                






Dear all,

sorry, I have some more Clp QP questions.  I need to solve a QP problem
of the form:

    min   0.5 x'Ix + f'y
     x,y
    sb.t. y >= 0,
          Ax + By >= c.   (1)

with delayed constraint generation for the set (1) where a few hundred
rows are added per iteration.  The problem has < 50k variables, and < 5k
constraints, with a block-sparsity such that a total of ~10% of the
elements in A are set, B has only one non-zero per row.  The QP solution
time is not very important, though it would be nice to warmstart from a
previous solution.  The number of rows should be kept small by pruning
inactive constraints (either by duals of these constraints or by
identifying non-binding rows manually).  For constraint generation I do
not need the dual multipliers, only the primal restricted solution x of
that iteration.

Using COIN-OR Clp, I have identified the following options I can use:

    1. ClpSimplex::nonlinearSLP(5000, 1e-8);
       works reasonably well, but gives poor dual variables, making it
difficult to prune the constraint set.  Also, I am not sure I understand
its workings well enough to trust it.

    2. ClpSimplex::primal();
       does not work well, cycles forever.

    3. ClpSimplex::initialBarrierSolve();
       surprisingly (this is ClpSimplex after all), seems to work
nicely, although slow and using a lot of memory once the problem grows.

    4. Instantiating ClpInterior and using:
         ClpInterior model;
         model.borrowModel(simplex);
         ClpCholeskyBase * cholesky = new ClpCholeskyBase();
         cholesky->setKKT(true);
         model.setCholesky(cholesky);
         model.primalDual();
         model.returnModel(simplex);
       is not stable, mostly crashing with "dual goes to infinity" message.

Are there any general recommendations on how to use Clp for the above
problem?  The QP functionality is almost not documented at all and I
would be grateful for any advice.

Thanks,
Sebastian
_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20080917/ef6e5b9c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20080917/ef6e5b9c/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ecblank.gif
Type: image/gif
Size: 45 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20080917/ef6e5b9c/attachment-0001.gif>