<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<p></p>
<p style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
Hi Tom,</p>
<p style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</p>
<p style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
I really did not read all detail... (sorry) But If you want to try... Usually CBC standalone solver it's very fast (there many questions about how it works to try to get the same performance), so I build the problem and aftewards I write a file in MPS format
and invoque CBC like this:<br>
</p>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
/home/cbc/Cbc-2.8.10/build/bin/cbc mps_filename solve -solution solution_filename > stdout_filename</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
or if you want to get the best solution after some seconds, you can limit the time:</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<span style="font-family: Calibri, Helvetica, sans-serif, EmojiFont, "Apple Color Emoji", "Segoe UI Emoji", NotoColorEmoji, "Segoe UI Symbol", "Android Emoji", EmojiSymbols;">/home/cbc/Cbc-2.8.10/build/bin/cbc mps_filename -sec time_in_seconds solve -solution
solution_filename > stdout_filename</span><br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
<span class="x_Apple-tab-span" style="white-space: pre;"></span></div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
Then you have to build a simple parser to know if the problem is optimal, best integer, infeaseable, ... and also get the solution.</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
It something "quick and dirty" but has been useful for me for real life and near real time problems. Hope it's useful.</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
Kind regards</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif, serif, EmojiFont; font-size: 16px;">
David Ibarra Gómez</div>
<div><br>
</div>
<br>
<p></p>
<br>
<br>
<div style="color: rgb(0, 0, 0);">
<div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>De:</b> Cbc <cbc-bounces@coin-or.org> en nombre de Tom Anderson <twic@urchin.earth.li><br>
<b>Enviado:</b> viernes, 23 de junio de 2017 14:19<br>
<b>Para:</b> cbc@list.coin-or.org<br>
<b>Asunto:</b> [Cbc] Beginner questions on making Cbc go faster</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt;">
<div class="PlainText">Hello!<br>
<br>
I am using Cbc (2.9.9) to attack a blending problem. I am very new to Cbc, <br>
and quite new to linear programming in general, so i have some possibly <br>
silly questions.<br>
<br>
My problem is quite small - the first instance that comes to hand has 996 <br>
variables, all integer, 24 constraints, and 2976 nonzero coefficients <br>
(half positive, half negative). I have ~20 instances, corresponding to <br>
different desired blends; they have the same coefficients and variable <br>
costs and bounds, but different constraint bounds. I've set the instances <br>
up, and am getting lovely solutions.<br>
<br>
Where things get interesting is that the variable costs and bounds change <br>
frequently (~ 1-1000 variables per second, potentially changing both cost <br>
and bound each time). The goal is to present a dashboard to users, updated <br>
in real time, telling them the current cost of each blend (and allowing <br>
them to drill down into the details of the recipe) . Because the users are <br>
human, they won't notice a latency of <100 milliseconds, but they will <br>
notice if it's much more than that.<br>
<br>
My current very naive code takes anything from 10 to 2000 milliseconds. <br>
I'm interested in anything i can do to make it faster, and in particular <br>
more consistent.<br>
<br>
Some random facts about my current code:<br>
<br>
* The application is in Java, and uses (a local fork of) the jCbc wrapper <br>
to call into Cbc. A call from Java into native code costs about a <br>
microsecond, and i'm making a lot of them, but i doubt it's a significant <br>
fraction of the time.<br>
<br>
* I maintain a CoinModel for each instance, created with a bunch of addCol <br>
calls, then addRow calls with the coefficients, then updated with a stream <br>
of setColumnObjective and setColumnBounds calls. I am also using <br>
setRowBounds when i update the amount of the blend that needs to be made, <br>
but i could stop doing that.<br>
<br>
* Every time i want to solve, i create a fresh CbcModel and <br>
OsiClpSolverInterface, and use the CoinModel with addRows to initialise <br>
the CbcModel.<br>
<br>
* I use jCbc's basic solve() method, which internally calls CbcMain with <br>
these arguments:<br>
<br>
driver3 -strong 5 -heuristicsOnOff off -presolve off -cutsOnOff off <br>
-primalS -preprocess off -tune 100000000 -passc 1 -feas off -rins off <br>
-solve -quit<br>
<br>
* I have a couple of other ways of coming up with blends, which i was <br>
using before adopting integer programming. One is to work through a static <br>
set of candidate blends, evaluating their feasibility and cost; i can do <br>
that in a few microseconds. The other is to solve the relaxation of the <br>
blending problem, and then heuristically bash it into integers, by <br>
rounding and then satisfying constraints by adding dashes of certain basic <br>
ingredients which i know are usually cheap and plentiful; i can do that in <br>
~10 milliseconds. These often come up with the genuinely optimal solution, <br>
and when they don't, are usually close in cost (although 'close' is very <br>
subjective).<br>
<br>
* It's possible to use negative amounts of ingredients; this has a <br>
negative unit cost, which is slightly smaller in absolute value than the <br>
unit cost of using a positive amount. I model this by having two variables <br>
for each ingredient, one for using a positive amount, one negative, with <br>
negated cost and coefficients for the negative one. It never makes sense <br>
to have nonzero values in both variables.<br>
<br>
So, what should i try to improve performance?<br>
<br>
I can think of a few things, but i have no idea how feasible, difficult, <br>
or beneficial any of them will be. But how about:<br>
<br>
* Reusing the CbcModel and/or OsiClpSolverInterface instances<br>
<br>
* Doing some kind of warm start to reuse the previous solution<br>
<br>
* Using the heuristic blends as starting points<br>
<br>
* Updating the model data differently, so that the organisation in memory <br>
is more efficient<br>
<br>
* Doing some kind of pre-solve<br>
<br>
* Defining special ordered sets for the positive-negative variable pairs<br>
<br>
* Somehow tuning the cut generation process (using particular cut <br>
generators, specialOptions/moreSpecialOptions/moreSpecialOptions2, or some <br>
of the many other tweakables)<br>
<br>
* Somehow tuning the underlying Clp solver<br>
<br>
* Using multiple threads, although given that i have several instances to <br>
update, i might be better off solving each one with a single thread, but <br>
solving several instances in parallel.<br>
<br>
Any suggestions, or directions to documention i should already have read, <br>
gratefully received!<br>
<br>
Thanks,<br>
tom<br>
<br>
-- <br>
Many CS algorithms become less useful when questions start getting<br>
answered with "maybe". -- Eric Sink<br>
_______________________________________________<br>
Cbc mailing list<br>
Cbc@list.coin-or.org<br>
<a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=vP8NPxGX0sTiuRjMTfR1zHc9c5gNBmQgVChcO-aYUoU&m=741mZ2k6aItlEOXJv4kfXreQ0I2leQfYKkfRSrz3t9o&s=lJKuSljP2rFwRPI1nd2240XxvICrHT3Rvz28W06oTmM&e=" id="LPlnk694329" previewremoved="true">https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=vP8NPxGX0sTiuRjMTfR1zHc9c5gNBmQgVChcO-aYUoU&m=741mZ2k6aItlEOXJv4kfXreQ0I2leQfYKkfRSrz3t9o&s=lJKuSljP2rFwRPI1nd2240XxvICrHT3Rvz28W06oTmM&e=</a>
<br>
</div>
</span></font></div>
</div>
</body>
</html>