Самый первый кейс, добавление всех столбцов с отрицательной приведенной стоимостью. Очень быстро росла модель, компрессия доходила всего да 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, надеюсь это вопрос закрывает.
Про статус - согласен, если задача имеет целевую функцию. Здесь же, задача удовлетворения ограничениям без целевой. Поэтому проверка на существование допустимого решения.
Выбор метода оптимизации - согласен, не добавил вводной части по этому пункту. Попробую исправиться.
По поводу математической оптимизации. Сейчас существует множество различных пакетов с реализацией различных методов оптимизации (линейное/нелинейное программирование, мета-эвристические методы, различные градиентные методы, методы поиска кратчайшего пути и др.). Эти сборники алгоритмов реализованы на хорошем уровне и позволяют проводить проверку гипотез, решать задачи быстрее и экономнее по ресурсам. Яркий пример из другой области - нейросети. Мало кто готов и может натренировать свой GPT4, даже если структура сети будет в общем доступе.
В статье демонстрируется "что" необходимо подать на вход и "как" применять готовые наборы оптимизационных алгоритмов для решения прикладных задач. Аналогично тому, как разметка и подготовка данных используется для finetuning нейросетей под локальные нужды. Мало кто вдается в детали структуры и организации нейросети при их обучении - черный ящик.
И математическая оптимизация — это вполне себе раздел прикладной математики.
Согласен. Добавлю, что стоит предоставить этот инструмент более широкому кругу лиц, чтобы все могли подумать над его применением.
Самый первый кейс, добавление всех столбцов с отрицательной приведенной стоимостью. Очень быстро росла модель, компрессия доходила всего да 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, надеюсь это вопрос закрывает.
Уже поступал схожий запрос ранее, следующий материал будет близким к стохастическому программированию
В чем противоречие? В первой про цикл, во второй про цепь/путь
Благодарю! Признаю упущение
Про статус - согласен, если задача имеет целевую функцию. Здесь же, задача удовлетворения ограничениям без целевой. Поэтому проверка на существование допустимого решения.
Про нейминг, возьму на заметку
Выбор метода оптимизации - согласен, не добавил вводной части по этому пункту. Попробую исправиться.
По поводу математической оптимизации. Сейчас существует множество различных пакетов с реализацией различных методов оптимизации (линейное/нелинейное программирование, мета-эвристические методы, различные градиентные методы, методы поиска кратчайшего пути и др.). Эти сборники алгоритмов реализованы на хорошем уровне и позволяют проводить проверку гипотез, решать задачи быстрее и экономнее по ресурсам. Яркий пример из другой области - нейросети. Мало кто готов и может натренировать свой GPT4, даже если структура сети будет в общем доступе.
В статье демонстрируется "что" необходимо подать на вход и "как" применять готовые наборы оптимизационных алгоритмов для решения прикладных задач. Аналогично тому, как разметка и подготовка данных используется для finetuning нейросетей под локальные нужды. Мало кто вдается в детали структуры и организации нейросети при их обучении - черный ящик.
Согласен. Добавлю, что стоит предоставить этот инструмент более широкому кругу лиц, чтобы все могли подумать над его применением.