Подземные формулировки ограничений для TSP и эвристики Christofide - PullRequest
Новая
       32

Подземные формулировки ограничений для TSP и эвристики Christofide

0 голосов
/ 04 апреля 2019

Я работаю над сравнением различных формулировок задачи коммивояжера (TSP). В частности, я сравниваю DFJ против MTZ формулировка ограничения подземного хода. Они реализованы с использованием решателя GLPK (через код Python с пакетом pyomo. Из-за очень большого числа ограничений в первом, TSP решается следующим образом:

  1. Ослабить все ограничения субтурма
  2. решить MIP
  3. если решение допустимо: закончить
  4. else: добавить ограничение подуровня DFJ для каждого подцикла в текущем решении

Это довольно эффективно в тех случаях, когда мне нужно работать. С другой стороны, состав MTZ медленнее (от 10 до 10 тыс. Раз). Поэтому у меня есть следующие вопросы:

  1. Может ли формулировка MTZ эффективно решаться итеративно?
  2. Что является причиной этого 10-10-кратного увеличения во времени?

Что касается 2-го вопроса, то два различия заключаются в том, что формулировка DFJ содержит ограничения на субтур $ O (2 ^ n) $, тогда как MTZ содержит ограничения на субтур $ O (n ^ 2) $ и что DFJ работает с переменными $ n $, тогда как МТЗ работает с $ 2n $. Тем не менее, поскольку DFJ решается итеративно, все ограничения подуровня не нужны (на самом деле для экземпляров, с которыми я работаю, достаточно менее 10 итераций), у нас остается такое же количество ограничений. Следовательно, я предполагаю, что разница - это число переменных, но я не могу понять, почему это приводит к такой большой разнице.

В качестве заключительного замечания я решил, что использование эвристического метода (а именно алгоритм Кристофайда ) может дать верхнюю границу для цели, которую можно использовать в качестве нового ограничения (надеюсь, радикально сократить набор выполнимых). растворы). Однако если я сначала применю эвристический метод Christofide, чтобы установить верхнюю границу для цели, а затем добавлю ее к ограничениям до решения MIP, эффективность в лучшем случае не изменится, а в худшем снизится до 10 раз.

Как получилось? Связано ли это с новой формой множества возможных решений? Мой друг также предположил, что GLPK может не выполнить надлежащую предварительную обработку для устранения доминирующих ограничений, но я не знаю, верно ли это, и я не знаю, где это искать.

У кого-нибудь есть идеи по одному из моих многочисленных вопросов?

1 Ответ

1 голос
/ 12 апреля 2019

Относительно использования эвристики Christofides: я не думаю, что правильный подход состоит в том, чтобы включить его цель в качестве ограничения. Скорее, вы хотите предоставить цель в качестве верхней границы для решателя. Я не уверен, как GLPK справляется с этим, но я предполагаю, что есть способ обеспечить начальную верхнюю границу, которую решатель может сначала использовать для поиска дерева ветвей и границ, прежде чем найдет возможное решение, которое лучше вашей границы.

Кроме того, Christofides обладает хорошими теоретическими свойствами, но в целом это не лучшая эвристика для TSP. Даже некоторые действительно простые, такие как самая дальняя вставка, в среднем работают лучше.

К сожалению, у меня нет никаких предложений относительно ограничений по удалению подземных ходов DFJ и MTZ ...

...