Estou procurando uma lista de problemas de otimização NP-hard, onde há pesquisas ativas em heurística prática para resolvê-los e há benchmarks comuns que as pessoas tentam superar.
Os exemplos incluem: Reconstrução de árvores filogenéticas (heurística, por exemplo, aqui ) Vendedor ambulante (não tão ativo, mas o LKH é bem conhecido)
Mais especificamente, estou procurando áreas de pesquisa, nas quais as pessoas realmente se preocupam com os custos resultantes (como TSP ou filogenia mencionados acima). Por exemplo, encontrar uma árvore de decisão não é algo que estou procurando, pois poucas pessoas se importam com a altura resultante da árvore.
heuristics
usamec
fonte
fonte
Respostas:
MaxSAT - as pessoas realmente se importam com isso porque os solucionadores SAT são tão bem desenvolvidos que, na prática, a melhor rota para o seu problema de otimização de NP favorito na prática é reduzi-lo ao MaxSAT e, em seguida, aplicar um dos solucionadores conhecidos. Confira a competição SAT para benchmarks etc.
Os buscadores de clique são usados em biologia computacional e combinatória, e os algoritmos heurísticos são surpreendentemente bons, pelo que me lembro.
Vastas partes da Pesquisa Operacional são dedicadas a algoritmos, inclusive heurísticos, para resolver casos de programação linear inteira ou inteira mista.
fonte
A pesquisa operacional apresenta muitos problemas de otimização combinatória, nos quais o desenvolvimento de heurísticas para minimização (ou maximização) dos custos resultantes é uma área muito ativa.
Por exemplo, problema de roteamento de veículo, problema de roteamento de arco capacitado, problemas mínimos de extensão de árvore e variações desses problemas.
fonte