#mathematical-optimization #heuristics #glpk
#математическая оптимизация #эвристика #glpk
Вопрос:
Я работаю над сравнением различных формулировок задачи коммивояжера (TSP). В частности, я сравниваю формулировку промежуточных ограничений DFJ и MTZ. Они реализованы с использованием решателя GLPK (с помощью кода Python с pyomo пакетом. Из-за очень большого количества ограничений в первом, TSP решается следующим образом:
- Ослабьте все ограничения промежуточного тура
- решите MIP
- если решение допустимо: завершить
- еще: добавьте промежуточное ограничение DFJ для каждого подцикла в текущем решении
Это довольно эффективно в тех случаях, над которыми мне нужно работать. Формулировка MTZ, с другой стороны, намного медленнее (от 10 до 10 тыс. раз). Поэтому у меня есть следующие вопросы:
- Может ли формулировка MTZ быть эффективно решена итеративно?
- В чем причина этого увеличения времени в 10-10 тысяч раз?
Что касается 2-го вопроса, два различия заключаются в том, что формулировка DFJ содержит $ O (2 ^ n) $ ограничения промежуточного тура, тогда как MTZ содержит $ O (n ^ 2) $ ограничения промежуточного тура и что DFJ работает с $ n $ переменными, тогда как MTZ работает с $ 2n $. Однако, поскольку DFJ решается итеративно, все ограничения промежуточного этапа не требуются (на самом деле для экземпляров, с которыми я работаю, достаточно менее 10 итераций), мы остаемся с аналогичным количеством ограничений. Следовательно, я предполагаю, что разница заключается в количестве переменных, но я не могу понять, почему это приводит к такой большой разнице.
В качестве заключительного замечания я решил, что использование эвристического метода (а именно алгоритма Кристофайда) может привести к верхней границе цели, которую можно использовать в качестве нового ограничения (надеюсь, резко сократив набор возможных решений).). Однако, если я сначала применю эвристический метод Кристофайда для определения верхней границы цели, а затем добавлю его к ограничениям перед решением MIP, эффективность в лучшем случае не изменится, а в худшем случае снизится до 10 раз.
Как получилось? Связано ли это с новой формой набора возможных решений? Мой друг также предположил, что GLPK может не выполнять надлежащую предварительную обработку, чтобы удалить доминирующие ограничения, но я не знаю, верно ли это, и я не знаю, где это искать.
У кого-нибудь есть идея по одному из многочисленных вопросов, которые у меня есть.
Ответ №1:
Что касается использования эвристики Кристофайда: я не думаю, что правильный подход заключается в том, чтобы включать его цель в качестве ограничения. Скорее, вы хотите предоставить цель в качестве верхней границы для решателя. Я не уверен, как GLPK справляется с этим, но я бы предположил, что есть способ предоставить начальную верхнюю границу, которую решатель может использовать для понимания дерева ветвей и границ, прежде чем он найдет возможное решение, которое лучше, чем ваша граница.
Кроме того, Christofides обладает хорошими теоретическими свойствами, но, в общем, это не лучшая эвристика для TSP. Даже некоторые действительно простые, такие как самая дальняя вставка, в среднем выполняются лучше.
К сожалению, у меня нет никаких предложений по поводу ограничений устранения промежуточных туров DFJ и MTZ…