[Cbc] Beginner questions on making Cbc go faster

[Tom Anderson]

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