Как добавить дополнительные ограничения для Concorde TSP solver

Question

Я пытаюсь решить измененную версию проблемы продавцов. Это модификация основного TSP, так что все узлы имеют свойство цвета, а оптимальный путь не может касаться более четырех узлов одного и того же цвета последовательно. Это будет выполняться на связанном графике не более 100 узлов. Я пытаюсь запустить это, используя Concorde.

Кто-нибудь знает, как добавить ограничение цвета на Concorde run?

Благодаря

Answer 1

Я не думаю, что Concorde настроен добавлять произвольные ограничения. Решатель очень настроен для классического TSP и не может вместить новые ограничения, подобные этому. Единственный способ сделать это можно было бы, если бы вы могли найти способ превратить свою проблему в классический TSP, изменив только данные (а не ограничения), т. Е. Придумав какой-то трюк, чтобы установить матрицу затрат, чтобы оптимальная решения всегда удовлетворяют ограничениям цвета, но я не вижу способа сделать это, вне руки.