Как минимизировать расстояние между городами в Гуроби?

Question

Я пытаюсь построить модель, используя Gurobi, но у меня проблемы с синтаксисом.

У меня есть список расстояний и городов. dist - расстояние между каждым городом. Например, Chica go до Chica go будет 0, тогда как Chica go до Бостона - 443, Chica go до D C - 223 и так далее. В списке dist есть переменные len (city) * len (city).

dist = [0,443,223,123,124,778,123,0,344,455,412,1235...]
city = ["Chicago","Boston","D.C.","Seattle","Los Angeles","Raleigh"]

Итак, теперь я установил переменную решения на

store = m.addVars(city, city, obj = Distances, name = "store")
print(store)
<Chicago, Chicago> <Chicago, Boston> <Chicago, D.C.> ... 
<Raleigh, Chicago> <Raleigh, Boston>, <Raleigh, D.C.>... <Raleigh, Raleigh> 

Как мне установить свои ограничения и цель, чтобы он искал самые низкие расстояния между каждым городом.

Answer 1

Это похоже на проблему кратчайшего пути для всех пар. Эта проблема может быть решена с помощью специализированных алгоритмов, которые не слишком сложны (см. ссылка ). Я не думаю, что есть такая компактная формулировка, как LP / MIP.