[Coin-discuss] ClpModel, optimize for delayed constraint generation

[John J Forrest]

Sebastian,

I keep meaning to get back to making such things more efficient, but ...

It would be much faster to build up all the constraints yourself in
AddViolatedInequalities and then use addRows before you return from that
function.  The fastest addRows is this one

void
OsiClpSolverInterface::addRows(const int numrows,
                         const int * rowStarts, const int * columns, const
double * element,
                         const double* rowlb, const double* rowub)

You could set up reasonable sized arrays and then trigger an addRows
earlier if you are generating too many violated constraints, or if finding
the violated inequalities is fast then just count, reserve, fill and
addRows.

John Forrest

                                                                                                                         
  From:       Sebastian Nowozin <nowozin at gmail.com>                                                                      
                                                                                                                         
  To:         Discussions about open source software for Operations Research <coin-discuss at list.coin-or.org>             
                                                                                                                         
  Date:       10/13/2008 09:28 AM                                                                                        
                                                                                                                         
  Subject:    [Coin-discuss] ClpModel, optimize for delayed constraint generation                                        
                                                                                                                         






Hello everybody,

I am using OsiClpSolverInterface for delayed constraint generation,
using a sequence of resolve()/addRow() calls.  How to best optimize for
this setting?

So far, I do:
    OsiClpSolverInterface* si = new OsiClpSolverInterface;
    ClpSolve lp_options;
    lp_options.setPresolveType(ClpSolve::presolveOff);
    si->setSolveOptions(lp_options);

    // Initial static constraints
    CoinPackedMatrix* matrix = new CoinPackedMatrix(false, 0.5, 0);
    // ... (setup matrix, var*, row*
    si->loadProblem(*matrix, varLB, varUB, objective, rowLB, rowUB);

    int constraints_found = 0;
    do {
        si->resolve();  // Warm-start solving (we only add constraints)

        RemoveInactiveConstraints();  // delete non-binding constraints
        constraints_found = AddViolatedInequalities();    // add cuts
    } while (constraints_found > 0);

Here, RemoveInactiveConstraints uses si->deleteRows, and
AddViolatedInequalities() uses si->addRow() repeatedly.  From profiling,
I see that quite some time is spend in addRow().

I tried using:
    if (si->getModelPtr()->matrix()->isColOrdered()) {
        si->getModelPtr()->matrix()->setExtraGap(0.5);
    } else {
        si->getModelPtr()->matrix()->setExtraMajor(0.5);
    }

with no result.  Strangely, the si->getModelPtr()->matrix() is always
column ordered, even if my initial CoinPackedMatrix using in
si->loadProblem is row-ordered.  Calling reverseOrdering() on the matrix
leads to a crash in the solver, so it does not seem to be working.

How to optimize OsiClpSolverInterface for repeated calls of addRow() and
resolve()?  I do not know the exact number of cuts a-priori (around
5000-10000 cuts per iteration).

Thank you,
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/20081014/9f07ce97/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/20081014/9f07ce97/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/20081014/9f07ce97/attachment-0001.gif>