9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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
    Commented Aug 27, 2017 at 20:44
  • $\begingroup$ That list is nice, but focuses mostly on approximation. I want a list focusing on practical heuristics. $\endgroup$
    – usamec
    Commented Aug 27, 2017 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
    Commented Aug 27, 2017 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
    Commented Aug 28, 2017 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
    Commented Aug 28, 2017 at 0:54

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Do you have some links to actual papers and benchmark datasets? $\endgroup$
    – usamec
    Commented Aug 29, 2017 at 6:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you please cite some benchmarks? $\endgroup$
    – usamec
    Commented Aug 30, 2017 at 14:19
  • $\begingroup$ Can you provide some relevant pointers, perhaps? $\endgroup$
    – Yuval Filmus
    Commented Aug 30, 2017 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
    Commented Aug 30, 2017 at 15:35
  • 1
    $\begingroup$ An example is CARP : logistik.bwl.uni-mainz.de/benchmarks.php $\endgroup$
    – user2307639
    Commented Aug 31, 2017 at 16:04

Your Answer

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

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