<html><body>
<p>Sebastian,<br>
<br>
I keep meaning to get back to making such things more efficient, but ...<br>
<br>
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<br>
<br>
void <br>
OsiClpSolverInterface::addRows(const int numrows,<br>
const int * rowStarts, const int * columns, const double * element,<br>
const double* rowlb, const double* rowub)<br>
<br>
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.<br>
<br>
John Forrest<br>
<img width="16" height="16" src="cid:1__=0ABBFE71DFC3B1048f9e8a93df938@us.ibm.com" border="0" alt="Inactive hide details for Sebastian Nowozin ---10/13/2008 09:28:49 AM---Hello everybody,"><font color="#424282">Sebastian Nowozin ---10/13/2008 09:28:49 AM---Hello everybody,</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__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">10/13/2008 09:28 AM</font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:2__=0ABBFE71DFC3B1048f9e8a93df938@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__=0ABBFE71DFC3B1048f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">[Coin-discuss] ClpModel, optimize for delayed constraint generation</font></td></tr>
</table>
<hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br>
<br>
<br>
<tt><br>
Hello everybody,<br>
<br>
I am using OsiClpSolverInterface for delayed constraint generation,<br>
using a sequence of resolve()/addRow() calls. How to best optimize for<br>
this setting?<br>
<br>
So far, I do:<br>
OsiClpSolverInterface* si = new OsiClpSolverInterface;<br>
ClpSolve lp_options;<br>
lp_options.setPresolveType(ClpSolve::presolveOff);<br>
si->setSolveOptions(lp_options);<br>
<br>
// Initial static constraints<br>
CoinPackedMatrix* matrix = new CoinPackedMatrix(false, 0.5, 0);<br>
// ... (setup matrix, var*, row*<br>
si->loadProblem(*matrix, varLB, varUB, objective, rowLB, rowUB);<br>
<br>
int constraints_found = 0;<br>
do {<br>
si->resolve(); // Warm-start solving (we only add constraints)<br>
<br>
RemoveInactiveConstraints(); // delete non-binding constraints<br>
constraints_found = AddViolatedInequalities(); // add cuts<br>
} while (constraints_found > 0);<br>
<br>
Here, RemoveInactiveConstraints uses si->deleteRows, and<br>
AddViolatedInequalities() uses si->addRow() repeatedly. From profiling,<br>
I see that quite some time is spend in addRow().<br>
<br>
I tried using:<br>
if (si->getModelPtr()->matrix()->isColOrdered()) {<br>
si->getModelPtr()->matrix()->setExtraGap(0.5);<br>
} else {<br>
si->getModelPtr()->matrix()->setExtraMajor(0.5);<br>
}<br>
<br>
with no result. Strangely, the si->getModelPtr()->matrix() is always<br>
column ordered, even if my initial CoinPackedMatrix using in<br>
si->loadProblem is row-ordered. Calling reverseOrdering() on the matrix<br>
leads to a crash in the solver, so it does not seem to be working.<br>
<br>
How to optimize OsiClpSolverInterface for repeated calls of addRow() and<br>
resolve()? I do not know the exact number of cuts a-priori (around<br>
5000-10000 cuts per iteration).<br>
<br>
Thank you,<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>