Самый первый кейс, добавление всех столбцов с отрицательной приведенной стоимостью. Очень быстро росла модель, компрессия доходила всего да 30-50% полной задачи. В этом случае перешли на выбор TopN столбцов с наиболее отрицательной приведенной стоимостью. Итого, 10-20% исходной задачи.
Второй кейс, выбор уникальных столбцов. Вводили метрику похожести. Из группы похожих столбцов брали только часть, около 10-15% столбцов из группы похожих.
В работе с алгоритмом генерации столбцов всегда добавлял группу столбцов. В самом простом случае на каждой итерации алгоритма добавлял все столбцы с отрицательной приведенной стоимостью. В задачах с большим кол-вом "похожих" столбцов приходилось вводить дополнительные эвристики (основанные на доминировании), чтобы прореживать группу столбцов.
В статье отмечал, что при добавлении группы столбцов происходит снижение компрессии задачи. Зачастую, это оправдывает себя по производительности.
В случае рассмотрения трех видов транспорта, матрицу переходов из одного узла в другой можно сформировать на основе минимального значения. Если оптимизирует длительность маршрута, то скорее всего граф будет содержать только авиа перемещения.
Что касается неопределенности в данных. Здесь можно рассматривать ожидаемую длительность или стоимость перемещения по ребру. Т.е. оперировать средними величинами. Если нужно робастное решение, то можно рассмотреть более сложную постановку задачи ЛП в условиях неопределенности: https://habr.com/ru/articles/751226/
Это можно сделать. Вопрос в том, чтобы все поставить на одни весы. Либо деньги перевести во время, либо время в деньги. Последний переход наиболее распространенный.
Интересный материал, спасибо! Это уже не первая ваша статья по TSP и в большинстве случаев недостает сравнения. Когда речь идет об одном алгоритме, кажется, что эта наилучший метод решения и других не существует. Но так ли это? Даже сравнение с алгоритмами из предыдущих ваших статей добавило бы объективности, учитывая громкость названия текущей статьи.
К сожалению, у habra нет хаба для исследования операций/математического моделирования/математической оптимизации/индустриальной математики. Поэтому приходится выбирать смежные области, чтобы собрать свою целевую аудиторию из нескольких смежных хабов.
Если положить w очень большим, то получаемое решение будет удовлетворять всем ограничениям для каждого сценария. Таким образом приходим к наихудшему сценарию. В частности, не важно w=1 или w=1000 в представленной задаче, решение будет одно и тоже.
Что касается смысловой нагрузки, вы пришли к тому, что w может выполнять роль стоимости за нарушение ограничения.
Третья часть, увы. Эксперимент демонстрирует поведение робастности решения и робастности модели. Цель показать влияние w на решение и потенциальные возможности им управлять. График можно перестроить (самое полезное замечание), а лучше оставить как есть.
Реальные задачи гораздо больше и возможность проводить запуски для различных w представляется затруднительной. Поэтому затронул вопрос бюджета на нарушения (ожидаемое нарушение) как один из вариантов выбора w.
Если говорить о нормированных весах, конечно, 1 это предел. В статье про нормировку речи не идет. Кроме того, на всех графиках он меньше либо равен 1. Здесь, вес понимается как weight, надеюсь это вопрос закрывает.
Про статус - согласен, если задача имеет целевую функцию. Здесь же, задача удовлетворения ограничениям без целевой. Поэтому проверка на существование допустимого решения.
Благодарю за мнение и обратную связь
Самый первый кейс, добавление всех столбцов с отрицательной приведенной стоимостью. Очень быстро росла модель, компрессия доходила всего да 30-50% полной задачи. В этом случае перешли на выбор TopN столбцов с наиболее отрицательной приведенной стоимостью. Итого, 10-20% исходной задачи.
Второй кейс, выбор уникальных столбцов. Вводили метрику похожести. Из группы похожих столбцов брали только часть, около 10-15% столбцов из группы похожих.
В работе с алгоритмом генерации столбцов всегда добавлял группу столбцов. В самом простом случае на каждой итерации алгоритма добавлял все столбцы с отрицательной приведенной стоимостью.
В задачах с большим кол-вом "похожих" столбцов приходилось вводить дополнительные эвристики (основанные на доминировании), чтобы прореживать группу столбцов.
В статье отмечал, что при добавлении группы столбцов происходит снижение компрессии задачи. Зачастую, это оправдывает себя по производительности.
В случае рассмотрения трех видов транспорта, матрицу переходов из одного узла в другой можно сформировать на основе минимального значения. Если оптимизирует длительность маршрута, то скорее всего граф будет содержать только авиа перемещения.
Что касается неопределенности в данных. Здесь можно рассматривать ожидаемую длительность или стоимость перемещения по ребру. Т.е. оперировать средними величинами. Если нужно робастное решение, то можно рассмотреть более сложную постановку задачи ЛП в условиях неопределенности: https://habr.com/ru/articles/751226/
Спасибо за материал! Проводили тестирование производительности библиотеки?
Отличный материал по presolve. Только уточню, что в соавторах трое основателей gurobi )
Самым очевидным и прямым методом, вручную
Звучит как стартап - автогенератор туров, спасибо за идею!
К сожалению, концентрированной информации по presolve не нашел. Но есть зацепка по gurobi https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work-
Что касается ortools, у них отрытый исходный код, можно в коде посмотреть https://developers.google.com/optimization/reference/sat/cp_model_presolve/CpModelPresolver и https://developers.google.com/optimization/reference/sat/simplification/SatPresolver
Кроме этого, у gurobi проводятся вебинары, где они рассказывают мат.часть в том числе по presolve.
Это можно сделать. Вопрос в том, чтобы все поставить на одни весы. Либо деньги перевести во время, либо время в деньги. Последний переход наиболее распространенный.
Интересный материал, спасибо! Это уже не первая ваша статья по TSP и в большинстве случаев недостает сравнения. Когда речь идет об одном алгоритме, кажется, что эта наилучший метод решения и других не существует. Но так ли это? Даже сравнение с алгоритмами из предыдущих ваших статей добавило бы объективности, учитывая громкость названия текущей статьи.
По поводу сценария - https://math.uwaterloo.ca/tsp/data/ml/monalisa.html - может будет полезно на будущее. Кроме этого, localsolver делает заявку на лидерство по решению TSP: https://www.localsolver.com/benchmark/localsolver-vs-gurobi-traveling-salesman-problem-tsp Можно также взять данные из их benchmark'a. Конечно, сравнивать эвристический подход с точным это как бои без правил, но конкурентность предлагаемого подхода оценить можно.
У ortools есть собственный решатель задач vrp, в частном случае - это tsp. Можно так же сравнить с этой библиотекой.
К сожалению, у habra нет хаба для исследования операций/математического моделирования/математической оптимизации/индустриальной математики. Поэтому приходится выбирать смежные области, чтобы собрать свою целевую аудиторию из нескольких смежных хабов.
Крымчан, очевидно
Живой человек )
Если положить w очень большим, то получаемое решение будет удовлетворять всем ограничениям для каждого сценария. Таким образом приходим к наихудшему сценарию. В частности, не важно w=1 или w=1000 в представленной задаче, решение будет одно и тоже.
Что касается смысловой нагрузки, вы пришли к тому, что w может выполнять роль стоимости за нарушение ограничения.
Первую часть оставлю без комментариев.
По второй, да, все верно.
Третья часть, увы. Эксперимент демонстрирует поведение робастности решения и робастности модели. Цель показать влияние w на решение и потенциальные возможности им управлять. График можно перестроить (самое полезное замечание), а лучше оставить как есть.
Реальные задачи гораздо больше и возможность проводить запуски для различных w представляется затруднительной. Поэтому затронул вопрос бюджета на нарушения (ожидаемое нарушение) как один из вариантов выбора w.
Если говорить о нормированных весах, конечно, 1 это предел. В статье про нормировку речи не идет. Кроме того, на всех графиках он меньше либо равен 1. Здесь, вес понимается как weight, надеюсь это вопрос закрывает.
Уже поступал схожий запрос ранее, следующий материал будет близким к стохастическому программированию
В чем противоречие? В первой про цикл, во второй про цепь/путь
Благодарю! Признаю упущение
Про статус - согласен, если задача имеет целевую функцию. Здесь же, задача удовлетворения ограничениям без целевой. Поэтому проверка на существование допустимого решения.
Про нейминг, возьму на заметку