<p>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.</p>

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

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

CC BY-SA 3.0
2017-08-29T06:25:42.240Z
Thanks. Do you have some links to actual papers and benchmark datasets?
usamec
CC BY-SA 3.0
2017-08-28T22:40:44.033Z
2017-08-28T22:40:44.033Z
Joshua Grochow
<p>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.</p>

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

CC BY-SA 3.0
2017-08-30T14:19:42.860Z
Can you please cite some benchmarks?
usamec
CC BY-SA 3.0
2017-08-30T14:20:35.837Z
Can you provide some relevant pointers, perhaps?
Yuval Filmus
CC BY-SA 3.0
2017-08-30T15:35:25.660Z
You can look at journals such as Mathematical Programming, Operations Research, Networks, Management Science etc for many papers on heuristics for combinatorial optimization problems.
Chandra Chekuri
CC BY-SA 3.0
2017-08-31T16:04:09.527Z
An example is CARP : logistik.bwl.uni-mainz.de/benchmarks.php
user2307639
CC BY-SA 3.0
2017-08-30T14:13:56.673Z
2017-08-30T14:13:56.673Z
user2307639
<p>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.</p>

<p>Examples include:
Phylogenetic tree reconstruction (heuristic for example <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4271533/" rel="noreferrer">here</a>)
Travelling salesman (not so active, but <a href="http://www.akira.ruc.dk/~keld/research/LKH/" rel="noreferrer">LKH</a> is quite well known)</p>

<p>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.</p>

CC BY-SA 3.0
2017-08-27T20:44:58.403Z
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: https://www.nada.kth.se/~viggo/problemlist/compendium.html
Kaveh
CC BY-SA 3.0
2017-08-27T20:56:19.913Z
That list is nice, but focuses mostly on approximation. I want a list focusing on practical heuristics.
usamec
CC BY-SA 3.0
2017-08-27T21:00:40.507Z
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/on-topic].) 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.
Kaveh
CC BY-SA 3.0
2017-08-28T00:52:44.130Z
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?
Chandra Chekuri
CC BY-SA 3.0
2017-08-28T00:54:16.530Z
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.
Chandra Chekuri
CC BY-SA 3.0
2017-08-29T22:36:44.023Z
Heuristic algorithms for the Shortest Vector Problem on lattices are being actively studied. They're used both for their direct applications and for setting cryptographic parameters.
Noah Stephens-Davidowitz
<heuristics>
List of NP-hard problems, where there is active research in practical heuristics
usamec
# List of NP-hard problems, where there is active research in practical heuristics

(Asked by: username_0 on 2017-08-27)

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](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4271533/))
Travelling salesman (not so active, but [LKH](http://www.akira.ruc.dk/~keld/research/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.

**Tags:** heuristics
> **Comments:**
> **username_1**: 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: https://www.nada.kth.se/~viggo/problemlist/compendium.html  
> **username_0**: That list is nice, but focuses mostly on approximation. I want a list focusing on practical heuristics.  
> **username_1**: 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/on-topic].) 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.  
> **username_2**: 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?  
> **username_2**: 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.  
> **username_3**: Heuristic algorithms for the Shortest Vector Problem on lattices are being actively studied. They're used both for their direct applications and for setting cryptographic parameters.  

---

## 2 answers

### Answer by username_4 on 2017-08-28. Score: 5

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.

> **Comments:**
> **username_0**: Thanks. Do you have some links to actual papers and benchmark datasets?  

---

### Answer by username_5 on 2017-08-30. Score: 1

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.

> **Comments:**
> **username_0**: Can you please cite some benchmarks?  
> **username_6**: Can you provide some relevant pointers, perhaps?  
> **username_2**: You can look at journals such as Mathematical Programming, Operations Research, Networks, Management Science etc for many papers on heuristics for combinatorial optimization problems.  
> **username_5**: An example is CARP : logistik.bwl.uni-mainz.de/benchmarks.php  

---

