13
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Related: What are common abbreviations in Operations Research? $\endgroup$
    – Kevin Dalmeijer
    Nov 18, 2019 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$
    – PSLP
    Nov 18, 2019 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, 2019 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, 2019 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, 2019 at 14:22

1 Answer 1

Reset to default
5
$\begingroup$

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.

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.