I am looking for list of NP-hard optimization problems, where there is active research in practical heuristic for solving them and there are common benchmarks, which people try to beat.

Examples include: Phylogenetic tree reconstruction (heuristic for example here) Travelling salesman (not so active, but LKH is quite well known)

More specifically, I am looking for areas of research, where people really care about resulting cost (like TSP or phylogeny mentioned above). E.g. finding decision tree is not a thing I am looking for, since very few people care about resulting tree height.

  • 1
    $\begingroup$ The list is too long I think which makes this question to broad. If you want a list that broad I would suggest checking out the compendium of NP-complete problems: nada.kth.se/~viggo/problemlist/compendium.html $\endgroup$ – Kaveh Aug 27 '17 at 20:44
  • $\begingroup$ That list is nice, but focuses mostly on approximation. I want a list focusing on practical heuristics. $\endgroup$ – usamec Aug 27 '17 at 20:56
  • $\begingroup$ Have you checked that it does have heuristic algorithms that you are interested in? I think they are rather open to various algorithms. (I am guessing that you know what heuristic means in the context of theoretical computer science and not just referring to things that just seem to work, if not please see help center.) Anyway, unfocused questions don't tend to be good in general, if you are not happy with that list you should be more explicit about why you are interested and narrow down the scope of the question. $\endgroup$ – Kaveh Aug 27 '17 at 21:00
  • 5
    $\begingroup$ This is reasonable question. Perhaps the OP can clarify further. Is it about problems for which heuristics are used in practice or is it about problems for which academic research in heuristics is actively being done? $\endgroup$ – Chandra Chekuri Aug 28 '17 at 0:52
  • 6
    $\begingroup$ One broad class of problems is clustering. Heuristics for k-means, k-median and related problems are a fairly active area of research. Also, metric labeling and related problems for graphical inference. $\endgroup$ – Chandra Chekuri Aug 28 '17 at 0:54

MaxSAT - people actually care about this because SAT solvers are so well-developed that often the best route for your favorite NP optimization problem in practice is to reduce it to MaxSAT and then apply one of the well-known solvers. Check out the SAT competition for benchmarks etc.

Clique-finders get used in computational biology and combinatorics, and the heuristic algorithms are shockingly good, as I recall.

Vast portions of Operations Research is devoted to algorithms, including heuristic ones, for solving cases of integer or mixed-integer linear programming.

  • $\begingroup$ Thanks. Do you have some links to actual papers and benchmark datasets? $\endgroup$ – usamec Aug 29 '17 at 6:25

Operations research have a plenty of combinatorial optimization problems where the development of heuristics for minimization (or maximization) of resulting costs are an very active area.

For example, vehicle routing problem, capacitated arc routing problem, minimum spanning tree problems and variations of these problems.

  • $\begingroup$ Can you please cite some benchmarks? $\endgroup$ – usamec Aug 30 '17 at 14:19
  • $\begingroup$ Can you provide some relevant pointers, perhaps? $\endgroup$ – Yuval Filmus Aug 30 '17 at 14:20
  • 1
    $\begingroup$ You can look at journals such as Mathematical Programming, Operations Research, Networks, Management Science etc for many papers on heuristics for combinatorial optimization problems. $\endgroup$ – Chandra Chekuri Aug 30 '17 at 15:35
  • 1
    $\begingroup$ An example is CARP : logistik.bwl.uni-mainz.de/benchmarks.php $\endgroup$ – user2307639 Aug 31 '17 at 16:04

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.