4
$\begingroup$

Suppose you are writing a paper about a certain new problem class. You have certain problem instances of different size (real-world as well as random) given. You developed different integer programming problem formulations for this problem and want to compare the performance of these models in the paper. (I would also be interested if something changes if we compare different algorithms, i.e. Benders Decomposition vs naive MIP formulation)

Now you want to present statistics to compare the performance of the different models.

An incomplete list of some things come to my mind are:

  • Value of LP Relaxation
  • Gap
  • Time to first solution
  • Gap of first solution to optimal solution
  • when is the optimal solution found
  • Time to solve the model
  • Number of solved models
  • Performance profiles
  • Number of branch and bound nodes
  • Primal/Dual integral
  • ....

and there are many more, but what are the most important statistics which you want to display (and in what form) to give a convincing picture of the performance of the different models without overloading it with too much statistic.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Have a look at: or.stackexchange.com/questions/1329/… $\endgroup$
    – Mostafa
    Apr 22, 2020 at 10:57
  • $\begingroup$ Time to solve the root node/relaxation. LP value after the solver has added its cuts. $\endgroup$
    – Sune
    Apr 22, 2020 at 12:37

2 Answers 2

Reset to default
8
$\begingroup$

After 20 years of practice of ORMS (= serving industrial and business clients), we observe that 99% of users of optimization software are first interested in the best solution found in K seconds, with K being on average 60. This is the must have.

Having good lower bounds (even with longer running times, minutes or hours) is a nice to have, mostly in the development and early production phases, to reassure the stakeholders - in particular the users - about the quality of solutions delivered.

Note that it often appears that solutions mathematically proved to be optimal are not good for the users. This is just because the mathematical optimization model is well not in line with the business needs. This is why in the practice of ORMS "modeling remains the master and computation the servant" as John N. Hooker well said.

But this is just what (we observe and then think that) people want in real life. For research purposes, we let the researchers express themselves.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ What do you mean by having lower bound to reassure the stakeholders? Do you compute a relaxation, decomposition, etc. method to compute a lower bound on every instance provided by the user, or you just show some historical data about those bounds? $\endgroup$
    – Joffrey L.
    May 14, 2020 at 10:42
  • 1
    $\begingroup$ @JoffreyL. Having a bound (and then an optimality gap) to assess the quality of the solution provided for each instance solved, whatever the mathematical way to compute it. By bounding, we mean here something like "we can affirm that no solution with a cost lower than 100 exists" (be careful, such a claim is difficult to check and errors/misreasonnings are frequent in practice). In that case, if you have found a solution with cost 101, then you can be happy as a "mathematical optimizer". Now, the road to make your client happy is much longer in the practice of OR ;-) $\endgroup$
    – LocalSolver
    May 14, 2020 at 12:22
  • 1
    $\begingroup$ @LocalSolver Would you mind elaborating a little bit on this? What are the commonly used ways to compute bounds? What are the common difficulties faced in practice to make the client happy? $\endgroup$
    – Antarctica
    May 14, 2020 at 14:10
  • $\begingroup$ @AmiraZarglayoun About the computation of bounds, there is so much to say. A big part of the research in OR is dedicated to prove, then to compute bounds. For combinatorial problems, the two basic ways to get bounds are: combinatorial relaxations (remove some constraints to make the relaxed problem efficiently solvable, for example using polynomial-time algorithms) and linear relaxations (relax the problem linearly to make it solvable by LP). The last decade, a research trend grows about exploiting nonlinear, convex relaxations (for example, conic or SDP relaxations). $\endgroup$
    – LocalSolver
    May 15, 2020 at 16:36
  • $\begingroup$ @AmiraZarglayoun There is even more to say about how to make business clients happy with OR. Too much to summarize it in a few lines here. Maybe you could have a look to our paper "Lessons learned from 15 years of operations research for French TV channel TF1", Interfaces 42(6), pp. 577-584. The preprint is available here: localsolver.com/fgardi/downloads/… $\endgroup$
    – LocalSolver
    May 15, 2020 at 16:44
1
$\begingroup$

The most powerful metric is to prove the power of a formulation theoretically, e.g., that the relaxation of formulation A will always be at least as tight as the relaxation of formulation B.

Solvers use a lot of black magic, so in order for an empirical comparison to be scientifically valid you want to eliminate any factors that are implementation-sensitive, or dependent on design choices such as primal heuristics, or acceleration heuristics.

It's also not rigorous to use a solver that you didn't write yourself (or is open source) to make such comparisons, unless you can justify with certainty what the solver is doing and why it's producing the behaviour that you are observing. Otherwise, what you are publishing is only really useful for that solver's developers.

Metrics that are less implementation-sensitive

  • Relaxation lower bound at the root node (assuming minimisation problem)
  • Size of the relaxation
  • Size of presolved model

Metrics that are very implementation-sensitive

  • Convergence rate
  • Optimality gap
  • Time/ability to find a feasible point
  • Number of nodes explored
  • Performance profiles
  • Solution time

Most of the latter are dependent on the choice of branching strategy, acceleration heuristics, primal heuristics, scalability of algorithms used in the solver, and whether a certain formulation is triggering a bottleneck inside the solver.

Alternatively, you can run statistical analysis on large problem test sets and test solver behavior on one formulation vs another, and then any metric goes really because you enter number-fudging territory. In this case beware, because all this comparison is telling you is how the change in formulation affected that specific solver in that specific problem set, unless you can credibly justify the solver's behavior. Even if your formulation is on average 100 times faster, you can not attribute that to the formulation unless you know what exactly the solver is (or is not) doing.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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