Solved – What exactly is a “solver” in optimization

definitionoptimizationsoftwareterminology

I am really confused by the usage of solver in computational optimization. I have looked around for a month on and off in order to see if I can get a good sense of what this term means yet I still do not have any good understanding of it.

It seems that, if I would like to solve an optimization problem in machine learning or elsewhere, I would refer to the exact computational procedure as an algorithm instead a solver. For example, if I had a quadratic program, I would use MATLAB's Quadprog function to solve the QP.

I would personally not refer to Quadprog function as a QP solver, because it is just a MATLAB function, or a script. I would not refer to the exact algorithm behind Quadprog as a QP solver, I don't care if it is gradient descent, interior point method, Newton Raphson…they are all algorithms to me. Finally, I would not refer to MATLAB as a QP solver because that is not MATLAB's sole purpose. So it seems that the word "solver" is missing from my everyday vocabulary despite having to routinely work with optimization, this confuses me quite a bit, it just feels I am not up to date with the lingo.

So by my reasoning, algorithms and MATLAB are not solvers. But suppose I have downloaded some softwares such as Gurobi or YALMIP to solve optimization problems, are these softwares called solvers? I have often time heard people referencing what "solver" you are using in sort of the same tone as what "software" you are using. What differentiate optimization softwares and solvers?

I know this sounds like a really rudimentary question, but I have only done optimization in MATLAB.

Best Answer

I suggest a solver is:

  • a software package
  • that incorporates one or more algorithms
  • for finding solutions to one or more classes of problem

The classes of problem is part of it. It is a X solver.

So

  • I would call Gurobi "a MIP/LP solver".
  • And I would say "Matlab incorperates a QP solver, that it exposes via the Quadprog function.", In this case the actual "QP solver" may or may not exist as a stand alone product.
  • Concorde is a TSP solver
  • Concorde incorporates QSopt, which is a LP solver

I think this usage is in line with (for example) the JuMP documentation

JuMP is a domain-specific modeling language for mathematical optimization embedded in Julia. It currently supports a number of open-source and commercial solvers (see below) for a variety of problem classes, including linear programming, mixed-integer programming, second-order conic programming, semidefinite programming, and nonlinear programming.

Here is a list of things that JuMP calls solvers. None of them are algorithms, all are specific programs

Related Question