[Cbc] Beginner questions on making Cbc go faster

[Tom Anderson]

On Fri, 23 Jun 2017, David Ibarra Gómez wrote:

> 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:

Thanks for the suggestion. I've translated my problem into an LP file, and 
that has proved to be a useful way to experiment with different settings. 
Many instances are still very slow, but at least now i have a simple way 
of doing experiments.

Something that has turned out to be particularly useful is the -cpp flag 
to the command-line tool, which writes out C++ code to reproduce the 
settings given on the command line. This gives me a really easy and 
reliable way to set up a solve in code!

If anyone has any more suggestions for how to improve performance, i'm all 
ears.

Regards,
tom

> /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=
>

-- 
Tristan Tzara offered to create a poem on the spot by pulling words at
random from a hat. A riot ensued and Andre Breton expelled Tzara from
the movement.