4
$\begingroup$

What is the appropriate measure to indicate the efficiency of an algorithm\model that solves a MILP through B&B?

Is it

  • the number of nodes examined to reach the optimum?
  • the number of iterations to reach the optimum?
  • the computing time required to reach the optimum?
  • ...

I would favour the computing time but is there anything that speaks against that?

$\endgroup$
6
  • 5
    $\begingroup$ Time. Nodes is a bad measure: more heuristics or strong branching decreases the node count so they would always win. $\endgroup$ – Erwin Kalvelagen Dec 23 '20 at 18:39
  • $\begingroup$ I agree with other answers favoring time. After all, this is what the only measure affecting the final user (+ compute/RAM costs). I'd like to add that number of nodes is not a useless metric either when developing an algorithm or solver. For example, it is exactly reproducible between runs. Similar metrics, such as number of moves or of simplex pivots, can be very useful if you're aware of their caveats. It can give you more insight into what's going on, but is almost never the primary measure $\endgroup$ – Gabriel Gouvine Dec 23 '20 at 19:01
  • $\begingroup$ @ErwinKalvelagen Just to point out, heuristics are typically run per node, so nu_nodes is typically invariant to the heuristics being used $\endgroup$ – Nikos Kazazakis Dec 23 '20 at 19:45
  • $\begingroup$ "number of nodes is typically invariant to the heuristics being used" The idea behind heuristics (and strong branching and cuts) is to spend more time per node. The payoff is: fewer nodes. If there is no reduction in expected node count no one would use heuristics. Also, looking only at node count, you only focus on one side of the trade-off. $\endgroup$ – Erwin Kalvelagen Dec 24 '20 at 13:09
  • $\begingroup$ Ah I thought you were referring to primal heuristics. For cuts and strong branching that's true, however the resulting computing time is very sensitive to implementation. $\endgroup$ – Nikos Kazazakis Dec 24 '20 at 21:01
9
$\begingroup$

I agree with Erwin's comment about heuristics and strong branching. When comparing algorithms or models, I would lean toward compute time, with a few caveats:

  1. they would have to be tested on the same hardware, using the same number of cores/threads;
  2. they would have to be tested on multiple problem instances;
  3. they would have to use the same solver (if comparing models) or be coded equally well (if comparing algorithms);
  4. they should be compared on both time to find the optimal solution (or progress on the primal bound) and time to prove optimality (or progress on the dual bound).

The first two points should be fairly obvious. The third point reflects the fact that a lot of person-hours of professional coders goes into creating CPLEX or Gurobi, while a limited number of person-hours of hack coding goes into anything I create. If testing, say, my cut generation subroutine versus someone else's, I would want to code theirs rather than rely on their published code (which might be better or worse than mine for reasons unrelated to the efficiency of the respective cuts).

As to the fourth point, some people (particularly academics) feel the need to reach proven optimality, and other people just need a good (or really good) solution in a "reasonable" amount of time. For the former, time to proven optimality is the obvious measure, regardless of whether the optimal solution pops up in the first few seconds or the last few seconds. For the latter, a performance profile (comparing solution quality over time) makes more sense, since it is unclear how patient they will be (and how that patience will translate into time, since 30 minutes on their 64 core computing beast is not 30 minutes on my 4 core desktop PC).

$\endgroup$
7
$\begingroup$

Obviously, the only universally valid (but little useful) answer is: it depends. One reason is that, as mentioned in other answers, implementation has a huge impact on practical performance.

That being said:

  • No matter which metric you choose, I would look at each approach's scalability w.r.t problem size.

  • There exist various statistical tests & comparison tools (from geometric mean of computing time to performance profiles) for assessing performance. Each has its pros and cons. You can read more in this lecture at the CO@Work workshop .

  • In addition to @prubin's answer: unless that's the component you're comparing, I would recommend to extract the presolved models (you can do so with Gurobi), and then run each approach on them. Presolve is so important that, otherwise, you may be comparing apples and oranges.

  • If you are deciding "should I use algorithm A or B to solve problem X in real life?", then computing time would likely be the most relevant, BUT bear in mind that:

    • It is not deterministic
    • It is impacted by many things, including: the machine you're using, how many cores you are using, whether other processes are running at the same time, etc. I've seen problems take 3x longer to solve just because I was running other tasks on my machine at the same time, and I typically see at least 20-30% variability (same code, same problem, same machine specs) on a shared computing cluster.
  • Number of nodes/simplex iterations is a "cleaner" metric, but again, it does not necessarily tell the whole story: are you "better" if you're exploring 10x less nodes, but each node is 100x slower? You may look at this paper and this one, which introduce & discuss some performance metrics (e.g. the "fair" number of nodes).

  • Other metrics include primal, dual, primal-dual integral (see e.g. here, particularly useful to assess the ability to find good solutions/ good dual bounds fast.

All in all: you probably want a combination of several metrics :)

$\endgroup$
5
$\begingroup$

For algorithms, hands down number of nodes, assuming you are not solving numerous (MI)LPs/node (e.g. you are not doing strong branching). This is how we evaluate potential when we prototype new algorithms at Octeract.

The reason is that the steps performed per node can be optimised in many ways, while the number of nodes we need to explore is purely a result of the algorithm(s) used.

Computing time is not a very good one, because it's very sensitive to implementation rather than a result of the algorithm itself. I've achieved improvements of 20,000x just by optimising code for existing algorithms. If we were evaluating using time, those algorithms would never have passed the test, but after optimisations they were really good.

Computing time becomes a more relevant metric when tuning a solver with highly optimised code. Even then, a trained eye can identify steps to skip altogether without changing the overarching algorithm.

As people have pointed out there is merit to computing time, but I'll just give an example as to how misleading this can be when developing an algorithm. Say I have two algorithms, A and B. A converges in 100 iterations and 100 seconds, B converges in 10 iterations and 500 seconds. Closer analysis reveals that B is slower because the linear solver solving the relaxation gets stuck on one node and spends 480 seconds on that 1 node. Even though it's slower, algorithm B is clearly superior to algorithm A. B is simply slower because of implementation issues which can be addressed (e.g. by switching to a different LP solver).

This is not an academic example btw, we deal with issues like this every day.

Since you mentioned number of iterations, for a branch-and-bound algorithm that's pretty much interchangeable with the number of nodes, so either goes. Number of iterations is also the equivalent of what I describe for non-BnB algorithms, e.g., interior point. There we would care much less about cost per iteration (when it comes to evaluating the algorithm itself) than we would about the number of iterations.

$\endgroup$
2
  • $\begingroup$ But it is possible to evaluate more nodes in less time? No? $\endgroup$ – Clement Dec 23 '20 at 18:00
  • $\begingroup$ Yes of course, the snag is that it's hard (but doable) to explicitly tie that metric to the algorithm itself. $\endgroup$ – Nikos Kazazakis Dec 23 '20 at 18:46
1
$\begingroup$

To be clear, we should distinguish between the following two comparisons:

  1. measuring the quality of a model solved by a B&B algorithm
  2. measuring the efficiency of a B&B algorithm that solves a given model

The first comparrison has been extensively studied for MILP problems solved by LP-based B&B algorithms. Regarding the second comparison, I add the time per node measure since it indicates how difficult it is to explore a node. This measure is quite useful since it explains why a model may be solved faster by an algorithm that uses a relatively larger number of nodes. The time per iteration can also be used if an LP-based B&B algorithm is used. It indicates how fast the LP-relaxations are solved. This measure proves useful in cases where the quality of the LP-relaxation bounds are good, but each LP is solved relatively slowly which results in a larger overall time. A time-independent measure would be the number of iterations per node which removes the drawbacks of the computational time. This measure somewhat shows how difficult the LP-relaxations of the model are. Note that the solution time of each LP is dependent on the number of variables and constraints as well as the number of non-zero elements in the coefficient matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.