[Cbc] Beginner questions on making Cbc go faster

[David Ibarra Gómez]

Hi Tom,


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:

/home/cbc/Cbc-2.8.10/build/bin/cbc  mps_filename solve -solution solution_filename > stdout_filename

or if you want to get the best solution after some seconds, you can limit the time:

/home/cbc/Cbc-2.8.10/build/bin/cbc  mps_filename -sec time_in_seconds solve -solution solution_filename > stdout_filename

Then you have to build a simple parser to know if the problem is optimal, best integer, infeaseable, ... and also get the solution.

It something "quick and dirty" but has been useful for me for real life and near real time problems. Hope it's useful.

Kind regards

David Ibarra Gómez




________________________________
De: Cbc <cbc-bounces at coin-or.org> en nombre de Tom Anderson <twic at urchin.earth.li>
Enviado: viernes, 23 de junio de 2017 14:19
Para: cbc at list.coin-or.org
Asunto: [Cbc] Beginner questions on making Cbc go faster

Hello!

I am using Cbc (2.9.9) to attack a blending problem. I am very new to Cbc,
and quite new to linear programming in general, so i have some possibly
silly questions.

My problem is quite small - the first instance that comes to hand has 996
variables, all integer, 24 constraints, and 2976 nonzero coefficients
(half positive, half negative). I have ~20 instances, corresponding to
different desired blends; they have the same coefficients and variable
costs and bounds, but different constraint bounds. I've set the instances
up, and am getting lovely solutions.

Where things get interesting is that the variable costs and bounds change
frequently (~ 1-1000 variables per second, potentially changing both cost
and bound each time). The goal is to present a dashboard to users, updated
in real time, telling them the current cost of each blend (and allowing
them to drill down into the details of the recipe) . Because the users are
human, they won't notice a latency of <100 milliseconds, but they will
notice if it's much more than that.

My current very naive code takes anything from 10 to 2000 milliseconds.
I'm interested in anything i can do to make it faster, and in particular
more consistent.

Some random facts about my current code:

* The application is in Java, and uses (a local fork of) the jCbc wrapper
to call into Cbc. A call from Java into native code costs about a
microsecond, and i'm making a lot of them, but i doubt it's a significant
fraction of the time.

* I maintain a CoinModel for each instance, created with a bunch of addCol
calls, then addRow calls with the coefficients, then updated with a stream
of setColumnObjective and setColumnBounds calls. I am also using
setRowBounds when i update the amount of the blend that needs to be made,
but i could stop doing that.

* Every time i want to solve, i create a fresh CbcModel and
OsiClpSolverInterface, and use the CoinModel with addRows to initialise
the CbcModel.

* I use jCbc's basic solve() method, which internally calls CbcMain with
these arguments:

driver3 -strong 5 -heuristicsOnOff off -presolve off -cutsOnOff off
-primalS -preprocess off -tune 100000000 -passc 1 -feas off -rins off
-solve -quit

* I have a couple of other ways of coming up with blends, which i was
using before adopting integer programming. One is to work through a static
set of candidate blends, evaluating their feasibility and cost; i can do
that in a few microseconds. The other is to solve the relaxation of the
blending problem, and then heuristically bash it into integers, by
rounding and then satisfying constraints by adding dashes of certain basic
ingredients which i know are usually cheap and plentiful; i can do that in
~10 milliseconds. These often come up with the genuinely optimal solution,
and when they don't, are usually close in cost (although 'close' is very
subjective).

* It's possible to use negative amounts of ingredients; this has a
negative unit cost, which is slightly smaller in absolute value than the
unit cost of using a positive amount. I model this by having two variables
for each ingredient, one for using a positive amount, one negative, with
negated cost and coefficients for the negative one. It never makes sense
to have nonzero values in both variables.

So, what should i try to improve performance?

I can think of a few things, but i have no idea how feasible, difficult,
or beneficial any of them will be. But how about:

* Reusing the CbcModel and/or OsiClpSolverInterface instances

* Doing some kind of warm start to reuse the previous solution

* Using the heuristic blends as starting points

* Updating the model data differently, so that the organisation in memory
is more efficient

* Doing some kind of pre-solve

* Defining special ordered sets for the positive-negative variable pairs

* Somehow tuning the cut generation process (using particular cut
generators, specialOptions/moreSpecialOptions/moreSpecialOptions2, or some
of the many other tweakables)

* Somehow tuning the underlying Clp solver

* Using multiple threads, although given that i have several instances to
update, i might be better off solving each one with a single thread, but
solving several instances in parallel.

Any suggestions, or directions to documention i should already have read,
gratefully received!

Thanks,
tom

--
Many CS algorithms become less useful when questions start getting
answered with "maybe". -- Eric Sink
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
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=
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20170623/9af3ac30/attachment.html>