Комментарии 40
Статья супер!
Хабр опять торт!
Особенно впечатляет визуализация решений при разном количестве ограничений.
Сильно жаль, что могу поставить за статью только два плюсика. ?
Очень не хватает формального описания подхода для понимания сути происходящего.
Очень не хватает формального описания подхода для понимания сути происходящего.
Теоретическое обоснование разжевано десятилетия назад. Читать не математику это будет не интересно, а тот к то в теме поймёт опираясь на свой опыт работы с TSP.
Всё что я сделал, это применил новый подход к выбору ограничивающих условий.
Тем более, если теоретически обосновано, почему не дать ссылку на готовое? А то я к TSP небезразличен, но вот реконструировать подход по косвенным признакам уже лень :)
То, что я вижу, никак не говорит о том, что в варианте задачи дискретной оптимизации есть уход от NP-полноты. Главное матрицу расстояний попротивнее подогнать на обсчет.
Понимаете коллега, где вы тут увидели дискретную оптимизацию? В ней я разочаровался еще, когда делал ветви и границы. Как раз линейное целочисленное программирование, основанное на симплекс методе и алгоритме Гомори, как раз и даёт эти чудесные результаты.
У Вас после жирной "Сути метода" пошла формула как раз из раздела "Дискретная оптимизация":
https://ru.wikipedia.org/wiki/Задача_коммивояжёра#Формулировка_в_виде_задачи_дискретной_оптимизации
Поэтому и хотелось увидеть, где случился ранее незамеченный поворот в прорывную методику.
О! Я так рад, что вы заинтересовались и начали копать. Вы абсолютно правы, за основу была выбрана именно эта формулировка. Но если посмотреть работы Данцига, Фалкерсона и Джонсона, а так же Миллера, Такера и Землина (ссылки на эти работы есть там же в википедии), то можно прийти к следующему выводу:
Эти авторы пытались засунуть все ограничения в систему уравнений сразу, а так их получается очень много и решатель захлёбывается. Я же предлагаю добавлять только те ограничения, которые нужны по факту в конкретной задаче.
Надеюсь так яснее. Я думал код приведённый выше сам за себя скажет.
Тут я не совсем корректно выразился. Выше названные исследователи, конечно же, перебирали комбинации. Если выразить эти комбинации в виде линейных неравенств и отдать их целочисленному решателю, то будет слишком много уравнений.
Мне просто все происходящее напомнило одну давнюю дискуссию про "коммивояжера за полином" (https://forum.ixbt.com/topic.cgi?id=40:3025)
Там была и ссылка на наборы "нехороших" данных для задачи, которая, увы, протухла, но, вроде бы, я нашел именное ее файл в своей домашней помойке. Не хотите ли скормить в свой алгоритм?
https://drive.google.com/file/d/11PfpGmwgUCbyg9xeyEeQYpa-niWp53sL
Не хотите ли скормить в свой алгоритм?
Только если вы расскажете, как это прочитать. В архиве что угодно, но только не симметричная матрица смежности.
По поводу дискуссии на форуме, как мне показалось, там речь шла про точность самой вводимой матрицы.
В тексте статьи был обозначен худший случай, требующий (n/2+1) вызовов решателя. В своих изысканиях специально искал примеры, которые являются адом для решателя, но и там он справлялся не плохо. Хоть и нелегко, но вдвое бил динамическое программирование по размеру матрицы. Если у динамического программирования сложность O(n^2*2^n), то тут я предполагаю она упирается в худшем случае в O(n*2^n) но это прикидочная величина.
Простите, но ваш код невозможно читать. Вложенные циклы, переменные с ничего не говорящими названиями. Что происходит, без отладчика совершенно неясно, особенно если человек не понимает вашего хода мысли. Общие моменты текста статьи ещё кое-как маппятся на вашу реализацию, но детали остаются неочевидны.
Признаю код не самый простой, есть грешок. Самые сложные места постарался прокомментировать по ходу. Вложенные циклы можно спокойно развернуть и добавить точки отладчика чтобы посмотреть сложные места. Непонятные переменные только для циклов, для краткости, не люблю, знаете, длинные строки.
Если есть конкретные вопросы спрашивайте отвечу. Так долго варился в этом коде что не могу критически оценить его сложность.
Дискретная оптимизация подразумевает различные методы. В данном случаи используется формулировка, как задачи целочисленного программирования. Прелесть в том, что матрицу подогнать конечно теоретически можно, но на практике это довольно сложно. Уже давал в предыдущей статье автора ссылку на SOTA решатель, основанный на тех же принципах https://en.wikipedia.org/wiki/Concorde_TSP_Solver, он может решать инстансы до десятков тысяч вершин. В то время как другие наивные подходы уже взрываются на паре десятков.
Благодарю вас за наводку на солвер Concorde, он лучший. Однако после ознакомления с их описание задачи у меня сложилось чёткое убеждение, что они не используют именно целочисленное линейное программирование, скорее там обычное линейное программирование. А так же я не увидел именно точного решения. Возможно, вы мне поможете с этим разобраться?
У них там точное решение https://www.reddit.com/r/compsci/comments/8auwm9/how_does_concorde_claim_to_be_a_tsp_solver/ В частности "Concorde is an exact algorithm based on Dantzig's cutting plane method which has obtained an optimal tour for an instance with 85900 cities." Впечатление возможно сложилось потому, что они неявно реализуют решение целочисленной формулировки через https://en.wikipedia.org/wiki/Branch_and_cut используя релаксацию. Весь дьявол в деталях реализации branc-and-cut, но я сильно глубоко не разбирался.
PS: в частности есть книжка от автора Concorde "The Traveling Salesman Problem: A Computational Study" там есть много подробностей, она лежит на libgen
Было бы интересно взглянуть на то как формулируются линейные ограничения для задачи коммивояжера. Просто из статьи это никак не следует, а сам по себе Симплекс - ни разу не магия.
Из открытых библиотек есть еще GLPK, OR-Tools от Google.
GLPK у меня не захотел решать целочисленную задачу, пришлось забраковать.
А какой решатель встроен OR-Tools, по умолчанию?
А какой решатель встроен OR-Tools, по умолчанию?
По умолчанию у них свой решатель. Но можно и другие подключить. Правда другие я не пробовал. На линейних задачах встроенный быстрее чем GLPK. В свое время проводил сравнение SciPy. GLPK, OR-Tools по скорости и максимальной размерности задачи. SciPy отказался решать систему с 5000 переменных. GLPK и OR-Tools с ними справляются, последний несколько быстрее.
КДПВ для статьи сформирована SciPy и для неё потребовалось 280875 переменных, нормально справился. Обратите внимание, что в последних версиях scipy.optimize.linprog завезли классные быстрые решатели. Особенно меня порадовал метод глубинной точки, для нецелочисленных задач.
Отличная статья да и люди тут важные )
Примерно так работает Active Set Solver для QP проблем.
Правда в нем еще есть шаг релаксации ограничений, т.к. можно в процессе построить ограничения которые будут загонять в локальный минимум.
Кстати для AS солвера мне помогло не решать проблему полностью заново, а дорешивать её для новых условий , сложность падает с n^3 до ~n^2
Интересно, что будет если уточняющие ограничения вводить с условием >=1 ?
Нужно строгое доказательство оптимальности решения или пример, показывающий, что метод может выдавать неоптимальное.
Долго думал, как вам ответить. Сам я не на ангстрем не математик, скорее практик. Мне очень сложно играть на чужом научном поле. Попробую в двух словах пояснить почему решение точное.
Представление формулировки задачи коммивояжёра как задачи дискретной оптимизации позволяет всегда получать решение как набор циклов, минимум из трёх вершин, охватывающих все узлы графа. А решение решателем оптимизационной задачи однозначно гарантирует, что суммарная длина всех этих циклов будет минимальна для графа. Минимальное же значение суммы циклов запрещает графу перекручиваться. Такое поведение не означает, что минимальное решение будет единственным, но нас по большому счёту устоит любое из минимальных если их несколько. Создавая дополнительные ограничения, мы запрещаем графу распадаться на уже обнаруженные множества, циклы которых в сумме короче минимального Гамильтонова пути. Повторяя поиск и добавляя дополнительные ограничения мы рано или поздно приходим к оптимальному решению задачи.
Возможно кто-то из молодого поколения возьмёт данную работу как курсовой/дипломный проект и всё хорошо разложит по полочкам.
Спасибо за ответ, я немного неточно выразился -- если вы как-то целесообразно, разумно меняете порядок добавления классических ограничений на мини-циклы в задачу, вместо добавления всех сразу, то проблемы нет: как только вы находите гамильтонов цикл, задача решена. Очевидно, что данный цикл будет удовлетворять и полному набору ограничений на нераспадаемость решения на подциклы (он ведь уже гамильтонов), т.е. этот цикл действительно будет оптимальным решением задачи. И как резонно писали выше -- различные попытки ввести порядок на ограничениях и надеяться, что оптимальное решение удастся перехватить раньше, чем потребуются все ограничения, -- уже были.
Вопрос касается Шага 4, где вводятся иные ограничения. Тут придется доказывать, а зная сколько научного внимания и сил потрачено на эту задачу, -- скорее искать контрпример :) Но статья у вас, конечно, все-равно хорошая :)
Добрый день, есть ли у кого опыт решения задач LP с количеством переменных более млн? Интересен процесс обработки данных для формирования задач и вывода полученного решения.
Вопрос очень актуальный, тоже ищу на него ответ, при миллионе переменных (а там используется переменные типа double), матрица перестаёт влезать в оперативную память. Нужен какой-то солвер который умеет расчёты или по частям, или эффективной подгрузкой с HDD, или эффективно сжимать данные. Разряженный матрицы SciPy проявили себя не очень.
Если не заморачиваться со связностью, то в первой задаче, вроде бы, есть вариант 0->2->0, 1->3>4->1 со значением целевой функции 3+3+2+6+7=21, а не 34.
Я что-то не учел?
Ради интереса посчитал в glpsol тупой лобовой алгоритм запрета распада маршрута на несвязные части (давно порывался глянуть, но как-то все руки не доходили).
Задача 1 Time used: 0.1 secs, задача 2 Time used: 260.0 secs.
Дальше как-то не захотелось смотреть ;)
Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)