For many families of optimization problems there is some sort of classification scheme. I am thinking about the triple notation for machine scheduling introduced in "Optimization and approximation in deterministic sequencing and scheduling: a survey" by Graham, Lawler, Lenstra, and Kan, or "A Compendium on Steiner Tree Problems" by Hauptmann and Karpinski. I wouldn't include something like "Vehicle Routing Problems, Methods, and Applications" by Toth and Vigo, as it focuses on the overview of solution techniques and not so much on a comprehensive list/system to talk about "all" vehicle routing problems.

I was wondering, if there was a survey of surveys with the scope of all operations research/combinatorial optimization problems? If not, are there any publications that try something similar (surveys/books of optimization problems with a much broader scope than the examples given)? Or to ask the same question in different words:

What are the broadest surveys of operations research/combinatorial optimization problems?

  • 5
    $\begingroup$ Related: What are common abbreviations in Operations Research? $\endgroup$ – Kevin Dalmeijer Nov 18 '19 at 14:41
  • 2
    $\begingroup$ @KevinDalmeijer I think, it is tangentially related.Therefore thank you for your helpful comment. I think, my question focuses more on the systemizing aspect of surveys for problems, their complexity and practical solvability status. $\endgroup$ – Luke599999 Nov 18 '19 at 16:08
  • 5
    $\begingroup$ I remember having read that the inventors of the three field notation in scheduling considered their creation as one of the worst things in their scientific careers -- if someone can dig up a reference I would be grateful $\endgroup$ – Marco Lübbecke Nov 19 '19 at 8:28
  • 3
    $\begingroup$ @Luke599999 I can't remember; it may be something like "once you have a schema, everyone obeys the schema, 'eliminates' creativity," ... but this is just guessing, I really don't know $\endgroup$ – Marco Lübbecke Nov 19 '19 at 11:47
  • 3
    $\begingroup$ Not as applied as what you a are asking, but a nice collection of problem classes can be found here: neos-guide.org/content/optimization-taxonomy $\endgroup$ – Nikos Kazazakis Nov 22 '19 at 14:22

I know some related sites which provide what you want.

The first is A compendium of NP optimization problems, the most related to your question. It has formal definitions of the problems and papers containing algorithms for solving them.

The second is mostly related to mathematical programming and constraint programming, Global Constraint Catalog. It has many constraints and their properties. For example, a constraint family to remove symmetries in TSP.

The third site is a well-known GraphClasses. It is only for problems related to graphs, but it is the most comprehensive that I know.


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.