#complexity-theory
#сложность-теория
Вопрос:
Я пробую разные эвристики оптимизации. Знаете ли вы какое-либо место, где я могу получить доступ к экземплярам и решениям NP-сложных задач, кроме TSPLIB?
Комментарии:
1. SAT (соревнование Sat), CP (minizinc, xcsp, …) и сообщества математической оптимизации ( Mittelmann , MIPLIB ) имеют множество примеров. Но, как и в случае с TSPLIB, вы будете конкурировать с десятилетними исследованиями (и коммерческим программным обеспечением, особенно в отношении math-opt). Кроме того, каждая хорошая исследовательская работа, учитывая некоторые проблемы, такие как упаковка контейнеров, маршрутизация транспортных средств и т. Д., Будет оценивать открытые экземпляры (например, Taillard @ Job-Shop-Scheduling; где некоторые экземпляры могут оставаться нерешенными в течение десятилетий).
2. Это не для исследований. Это для небольшой демонстрации, и я не хотел использовать проблемы TSP или рюкзака, поскольку они являются наиболее частыми. Спасибо за ваши предложения.