Estoy buscando una lista de problemas de optimización NP-hard, donde hay una investigación activa en heurística práctica para resolverlos y hay puntos de referencia comunes, que las personas intentan superar.
Los ejemplos incluyen: Reconstrucción de árboles filogenéticos (heurística, por ejemplo, aquí ) Vendedor ambulante (no tan activo, pero LKH es bastante conocido)
Más específicamente, estoy buscando áreas de investigación, donde las personas realmente se preocupan por el costo resultante (como TSP o filogenia mencionado anteriormente). Por ejemplo, buscar el árbol de decisión no es algo que estoy buscando, ya que a muy pocas personas les importa la altura del árbol resultante.
heuristics
usamec
fuente
fuente
Respuestas:
MaxSAT: la gente realmente se preocupa por esto porque los solucionadores SAT están tan bien desarrollados que a menudo la mejor ruta para su problema favorito de optimización de NP en la práctica es reducirlo a MaxSAT y luego aplicar uno de los solucionadores conocidos. Echa un vistazo a la competencia SAT para puntos de referencia, etc.
Los buscadores de camarillas se utilizan en biología computacional y combinatoria, y los algoritmos heurísticos son sorprendentemente buenos, según recuerdo.
Grandes porciones de la Investigación de operaciones se dedican a algoritmos, incluidos los heurísticos, para resolver casos de programación lineal de enteros o enteros mixtos.
fuente
La investigación de operaciones tiene muchos problemas de optimización combinatoria donde el desarrollo de heurísticas para la minimización (o maximización) de los costos resultantes es un área muy activa.
Por ejemplo, problema de enrutamiento de vehículos, problema de enrutamiento de arco capacitado, problemas de árbol de expansión mínima y variaciones de estos problemas.
fuente