Открытые статьи для разбора

Материал из DISCOPAL
Перейти к: навигация, поиск


Всего страниц найдено: 74.

----

«

Реальные проблемы часто характеризуются противоречивой оптимизацией. цели. Следовательно, растет интерес не только к многоцелевые модели, но также и в специализированных многоцелевых метаэвристиках для решения этих моделей. Широкий спектр методов, например NSGA-II, SPEA, IBEA, Таким образом, были предложены рассеянный поиск, локальный поиск по Парето и многие другие. с годами.

Тем не менее, в принципе, многоцелевые задачи могут быть эффективно решены. решается с помощью существующих специализированных одноцелевых решателей — это центральный идея, лежащая в основе хорошо известного метода эпсилон-ограничений (ECM). Несмотря на теоретические свойства и концептуальная простота, метод эпсилон-ограничений в основном игнорируется в области эвристики и остается ассоциированным в основном с точными алгоритмами. В этой статье мы развенчаем эти предубеждения и продемонстрировать, что структура эпсилон-ограничений может быть очень эффективной способ напрямую использовать существующие исследования по одноцелевой оптимизации для решения многоцелевых задач.

Предлагаем улучшенную версию классического ECM, адаптированную к задачам и требованиям, специфичные для эвристического поиска. В результате фреймворк реализовано с помощью существующего современного одноцелевого решателя для Capacitated Vehicle Routing Problem (CVRP) и протестировано на VRP с Route Балансировка (ВРПРБ). На основе обширного вычислительного исследования мы показываем добавленные ценность наших приспособлений по сравнению с классическим ECM, и демонстрируют, что наш простой алгоритм эпсилон-ограничения значительно превосходит текущий современная многоцелевая метаэвристика в отношении множественных показатели качества. В заключение мы обсудим соответствующие факторы успеха и перспективные направления дальнейших исследований.

…»



«

Мы исследуем структурную декомпозицию для маршрутизации транспортных средств с ограниченными возможностями. проблема (CVRP), основанная на «назначении» транспортного средства клиенту и посещениях «упорядочивание» переменных решения. Мы показываем, что эвристический поиск сфокусирован на решения о назначении с систематическим оптимальным выбором последовательностей (с использованием Concorde TSP solver) во время оценки каждого хода многообещающе, но требует непомерно высокие вычислительные затраты.

Поэтому мы вводим промежуточный поиск пространство, основанное на процедуре динамического программирования Баласа и Симонетти, которая находит хороший компромисс между интенсификацией и вычислительной эффективностью.

Предлагаются различные приемы ускорения для быстрого исследования: сокращение соседства, фильтры динамического перемещения, структуры памяти и методы конкатенации. Наконец, стратегия туннелирования призвана изменить форму пространство поиска по мере выполнения алгоритма.

Сочетание этих методов в рамках классического локального поиска, а также как в едином гибридном генетическом поиске (UHGS) приводит к значительным повышение точности решения. Находятся новые лучшие решения для на удивление небольшие экземпляры всего с 256 клиентами. Эти решения имели не были достигнуты до сих пор с классическими кварталами. В целом это исследование позволяет лучше оценить соответствующее влияние последовательности и назначения оптимизации, предлагает новые способы сочетания оптимизации этих двух решений и открывает многообещающие перспективы исследований для CVRP и ее варианты.

…»



«

Представлен углубленный вычислительный анализ четырех хорошо известных Формулировки задачи о маршрутизации емкостного транспортного средства (CVRP) с полиномиальным числом ограничений исключения субтуров: формулировка на основе узлов и три составы на основе дуги (одно-, двух- и многопродуктовые потоки).

Для каждого формулировки, несколько допустимых неравенств (VI) добавлены с целью ужесточение состава. Более того, простая грануляция на основе топологии — предлагается схема для уменьшения количества ВП определенного типа.

Нижняя и верхняя граница производительности и эффективность решения формулировок и соответствующие конфигурации VI проверены на современных коммерческих программное обеспечение для оптимизации.

Обширный вычислительный анализ охватывает 121 экземпляры с количеством клиентских узлов до 100. Мы считаем, что наши выводы могут быть полезно для практиков, а также исследователей, разрабатывающих алгоритмы для CVRP.

…»



«

Изучение того, как автоматически решать задачи оптимизации, имеет потенциал чтобы обеспечить следующий большой скачок в технологии оптимизации. Производительность автоматически изученная эвристика для проблем маршрутизации постоянно улучшается в последние годы, но подходы, основанные исключительно на машинном обучении, по-прежнему уступает самым современным методам оптимизации.

Чтобы закрыть это разрыв в производительности, мы предлагаем новую структуру поиска больших окрестностей (LNS) для маршрутизации транспортных средств, которая объединяет изученную эвристику для создания новых решения. Механизм обучения основан на глубокой нейронной сети с механизм внимания и был специально разработан для интеграции в Настройка поиска LNS. Мы оцениваем наш подход к прокладке маршрута для транспортных средств с ограниченными возможностями — проблема (CVRP) и проблема маршрутизации раздельного транспорта (SDVRP).

На CVRP экземпляров с количеством клиентов до 297, наш подход значительно превосходит LNS, использующий только эвристику, созданную вручную, и хорошо известную эвристику из литература. Кроме того, мы показываем для CVRP и SDVRP, что наш подход превосходит по производительности существующие подходы к машинному обучению и обеспечивает близок к эффективности современных подходов к оптимизации.

…»



«

Недавние исследования использования глубокого обучения для решения проблем маршрутизации сосредоточены на строительная эвристика, решения которой еще далеки от оптимальности. Эвристика улучшения имеет большой потенциал для сокращения этого пробела путем итеративного уточнение решения.

Однако все классические эвристики улучшения основываются на созданные вручную правила, которые могут ограничивать их эффективность. В этой статье мы предлагаем фреймворк глубокого обучения с подкреплением для изучения эвристики улучшения проблемы с маршрутизацией. Мы проектируем глубокую архитектуру, основанную на самовнимании, как сеть политик для руководства выбором следующего решения. Мы применяем наш метод к две важные проблемы маршрутизации, то есть проблема коммивояжера (TSP) и проблема маршрутизации емкостного транспортного средства (CVRP).

Эксперименты показывают, что наш метод превосходит современные подходы, основанные на глубоком обучении. Ученый политики более эффективны, чем традиционные, созданные вручную, и могут быть дальнейшее усиление за счет простых стратегий диверсификации. Более того, политика хорошо обобщать для разных размеров проблем, начальных решений и даже набор данных из реального мира.

…»



«

Возникающая исследовательская парадигма, названная оптимизацией многозадачности, направлена ​​на решать несколько задач оптимизации одновременно с помощью единого поиска процесс.

С этой целью использование взаимодополняемости среди решаемые задачи имеют решающее значение, что часто достигается за счет передачи генетический материал, тем самым создавая поле оптимизации передачи. В этом контекст, эволюционная многозадачность обращается к этой парадигме, прибегая к концепции из эволюционных вычислений.

В рамках этой конкретной ветви подходы такие как многофакторный эволюционный алгоритм (MFEA) в последнее время получил широкое распространение. заметный импульс при решении нескольких задач оптимизации. Эта работа способствует этой тенденции, предлагая первую адаптацию недавно представил Многофакторный эволюционный алгоритм II (MFEA-II) в среды дискретной оптимизации на основе перестановок. Для моделирования этого адаптация, некоторые концепции нельзя напрямую применять к дискретным поисковым пространствам, например, взаимодействие, ориентированное на родителей.

В этой статье мы полностью переформулируем такие концепции, что делает их подходящими для работы с пространствами поиска на основе перестановок без потери неотъемлемых преимуществ MFEA-II.

Производительность предложенный решатель был оценен в 5 различных конфигурациях многозадачности, состоит из 8 наборов данных известного коммивояжера (TSP) и Проблемы маршрутизации емкостных транспортных средств (CVRP). Полученные результаты и их сравнение с дискретной версией MFEA подтверждает хорошее производительности разработанного dMFEA-II и согласуются с выводами, сделанными в предыдущие исследования для непрерывной оптимизации.

…»



«

Оптимизация многозадачности — это недавно представленная парадигма, ориентированная на одновременное решение нескольких экземпляров оптимизационных задач (задач).

Цель многозадачных сред — динамическое использование существующих взаимодополняемость и синергия между задачами, помогая друг другу через передача генетического материала.

Точнее, эволюционная многозадачность (ЭМ) что касается разрешения сценариев многозадачности с использованием унаследованных концепций из эволюционных вычислений. EM-подходы, такие как хорошо известные Многофакторный эволюционный алгоритм (MFEA) в последнее время набирает обороты. импульс исследований при столкновении с множеством проблем оптимизации. Эта работа сосредоточился на применении недавно предложенной многофакторной сотовой генетическом алгоритме (MFCGA) известной проблемы маршрутизации с емкостным транспортным средством (CVRP).

Всего было создано 11 различных настроек многозадачности с использованием 12 наборы данных.

Вклад этого исследования двоякий. С одной стороны, это первое приложение MFCGA к семейству задач маршрутизации транспортных средств проблемы. С другой стороны, не менее интересен второй вклад, который ориентирован на количественный анализ положительных генетических переносимость между проблемными экземплярами. Для этого мы предоставляем эмпирическая демонстрация синергии, возникающей между различными задачи оптимизации.

…»



«

В этой короткой статье мы изучаем маршрутизацию транспортных средств с ограниченной пропускной способностью. задача (CVRP) и ее решение рандомизированными методами Монте-Карло. Для решения CVRP мы используем некоторые генераторы псевдослучайных чисел, которые обычно используются на практике.

Мы использовать линейный, многорекурсивный, инверсивный и явный обратный конгруэнтный генераторы и получить случайные числа от каждого, чтобы обеспечить маршрут для CVRP.

Затем мы сравниваем производительность генераторов псевдослучайных чисел относительно к общему времени, которое занимает случайный маршрут. Мы также создали проект с открытым исходным кодом для решения CVRP методом Монте-Карло на основе эвристические методы.

…»



«

Ключевой проблемой при решении задачи комбинаторной оптимизации является то, как направлять агента (то есть решателя), чтобы эффективно исследовать огромный поиск пространства.

Традиционные подходы часто основаны на перечислении (например, исчерпывающий, случайный или запретный поиск) или должны ограничить исследование довольно ограниченным области (например, единственный путь, как в итерационных алгоритмах). В этой статье мы показать, что можно использовать машинное обучение для ускорения исследования.

В частности, сеть ценностей обучена оценивать варианты решений, которые обеспечивает полезную структуру (т. е. приблизительную поверхность значений) над пространство поиска; затем эта сеть ценностей используется для проверки решений, чтобы помочь агент оптимизации черного ящика для инициализации или перезапуска для навигации по пространство поиска желаемых решений.

Эксперименты показывают, что предложенный алгоритм «Learn to Restart» дает многообещающие результаты в решении «Проблемы маршрутизации емкостных транспортных средств (CVRP)».

…»



«

Сложные задачи маршрутизации из реальной жизни можно смоделировать как вариации известные комбинаторные задачи оптимизации.

Эти проблемы с маршрутизацией давно изучаются и их сложно решить в масштабе. Конкретная установка может также затруднить точную формулировку. Глубокое обучение предлагает все больше привлекательная альтернатива традиционным решениям, которые в основном вращаются вокруг использование различных эвристик. Глубокое обучение может предоставить решения, которые менее затратный по времени и более качественный в больших масштабах, как это обычно бывает нет необходимости генерировать решения итеративно, а модели глубокого обучения проявили удивительную способность решать сложные задачи в последние годы.

Здесь мы рассматриваем конкретный вариант маршрутизации емкостных транспортных средств (CVRP) и исследовать использование моделей глубокого обучения с явным компоненты памяти. Такие компоненты памяти могут помочь в понимании решения модели, так как память и операции с ней могут быть непосредственно проверены в любое время и может помочь в масштабировании метода до такого размера, чтобы он становится жизнеспособным в отраслевых условиях.

…»



«

Методы, основанные на функциях ценности, уже давно играют важную роль в обучение с подкреплением. Однако поиск лучшего следующего действия с учетом ценности функция произвольной сложности нетривиальна, когда пространство действия слишком большой для перечисления. Мы разрабатываем основу для глубокого обучение с подкреплением с комбинаторным пространством действий, в котором действие задача выбора явно формулируется как смешанно-целочисленная оптимизация проблема.

В качестве мотивирующего примера мы представляем применение этого фреймворка. к проблеме выбора маршрута транспортного средства (CVRP), комбинаторной оптимизации проблема, при которой набор местоположений должен быть покрыт одним транспортным средством с ограниченная вместимость.

В каждом случае мы моделируем действие как построение единственный маршрут, и рассмотрите детерминированную политику, которая улучшается за счет простой алгоритм итерации политики. Наш подход конкурентоспособен с другими методы обучения с подкреплением и достигает среднего разрыва 1,7% с современные методы ИЛИ для стандартных библиотек среднего размера.

…»



«

В нейро-комбинаторной оптимизации (CO) обучение с подкреплением (RL) может превратить глубокую нейронную сеть в быстрый и мощный эвристический решатель NP-трудных проблемы. Этот подход имеет большой потенциал в практических приложениях, поскольку он позволяет находить почти оптимальные решения без помощи экспертов, вооруженных существенное знание предметной области.

Мы представляем оптимизацию политик с несколькими Optima (POMO), комплексный подход к созданию такого эвристического решателя. ПОМО применимо к широкому кругу проблем с CO. Он предназначен для использования симметрии в представлении решения CO. ПОМО использует модифицированный Алгоритм REINFORCE, который заставляет разнообразные развертывания для всех оптимальных решений.

Эмпирически базовый уровень POMO с низкой дисперсией делает обучение RL быстрым и стабильный, и он более устойчив к локальным минимумам по сравнению с предыдущими подходы. Мы также представляем новый метод вывода, основанный на расширении, который хорошо сопровождает ПОМО. Мы демонстрируем эффективность ПОМО, решая три популярных NP-сложных задачи, а именно: коммивояжер (коммивояжер), емкостной маршрутизация транспортных средств (CVRP) и рюкзак 0-1 (KP).

Для всех трех наш решатель на основе на POMO показывает значительное улучшение производительности по сравнению со всеми недавно изученными эвристика. В частности, мы достигаем разрыва оптимальности 0,14% с TSP100. при этом время вывода сокращается более чем на порядок.

…»



«

Метаэвристика широко используется для решения сложных задач оптимизации, таких как задачи маршрутизации транспортных средств (VRP), для которых есть точные методы решения непрактично.

В частности, была изучена метаэвристика, основанная на локальном поиске. успешно применен к емкостному VRP (CVRP). CVRP направлен на определение маршруты доставки с минимальной стоимостью для данного набора идентичных транспортных средств, поскольку каждое транспортное средство движется только по одному маршруту, и имеется единственное (центральное) депо.

В лучшая метаэвристика для CVRP, чтобы избежать застревания в локальных оптимумах внедрение определенных механизмов восхождения на холмы, таких как стратегии диверсификации в методы решения. Эта статья представляет гибридизацию романа адаптивная версия итерированного локального поиска с перенаправлением пути (AILS-PR) к CVRP.

Основным вкладом данной статьи является автоматический механизм управления шаг разнообразия метаэвристики, чтобы позволить ей уйти от локальных optima. Результаты экспериментов со 100 тестовыми экземплярами CVPR показывают, что AILS-PR превзошел самые современные метаэвристики CVRP.

…»



«

Глубокое обучение с подкреплением (DRL) использовалось для изучения эффективных эвристик. для решения сложной комбинаторной задачи оптимизации через сети политик и показали многообещающие характеристики. Существующие работы сосредоточены на решении (транспортное средство) проблемы с маршрутизацией, поскольку в них есть хороший баланс между нетривиальностью и трудности.

Современные подходы изучают политику с помощью подкрепления обучения, а изученная политика действует как псевдо-решатель. Эти подходы имеют продемонстрировал хорошую производительность в некоторых случаях, но с учетом большого пространства поиска типичная комбинаторная проблема / проблема маршрутизации, они могут слишком быстро сходиться к плохим политика. Чтобы предотвратить это, в данной статье мы предлагаем подход под названием энтропия регуляризованное обучение с подкреплением (ERRL), которое поддерживает исследование предоставление большего количества стохастических политик, что улучшает оптимизацию.

Опытным путем, ERRL с низкой дисперсией обеспечивает быстрое и стабильное обучение RL. Мы тоже ввести комбинацию локальных поисковых операторов во время тестирования, что значительно улучшает решение и дополняет ERRL. Мы качественно продемонстрировать, что для проблем с маршрутизацией транспортных средств политика с более высокой энтропией может сделать оптимизационный ландшафт плавным, что упростит оптимизацию. В количественная оценка показывает, что характеристики модели сопоставимы с самыми современными вариантами.

В нашей оценке мы экспериментально иллюстрируют, что модель обеспечивает современную производительность на вариантах Проблемы с маршрутизацией транспортных средств, такие как проблема маршрутизации емкостных транспортных средств (CVRP), Множественная маршрутизация с фиксированными проблемами парка (MRPFF) и коммивояжером проблема.

…»



«

Проблема выбора маршрута транспортного средства (CVRP) является одной из наиболее распространенных. проблемы оптимизации в наши дни, учитывая широкое использование маршрутизации алгоритмы в различных областях, таких как транспортная сфера, доставка еды, маршрутизация сети, ...

Проблема маршрутизации емкостных транспортных средств классифицируется как Проблема NP-Hard, следовательно, нормальный алгоритм оптимизации не может ее решить.

Мы обсуждаем новый способ решения упомянутой проблемы с использованием рекурсивного подход наиболее известного алгоритма кластеризации «k-средних», один из известных алгоритм кратчайшего пути «Дейкстра» и некоторые математические операции.

Мы покажем, как реализовать эти методы вместе, чтобы получить ближайшее решение оптимального маршрута, так как исследования и разработки все еще в дальнейшем эта исследовательская работа может быть дополнена другой, которая будет включать результаты реализации этой торической стороны.

…»



«

Разрабатывается параллельный, быстрый и приближенный основанное на обучении решение для универсального класса Capacitated Vehicle Routing Проблемы с Time Windows и динамической маршрутизацией (CVRP-TWDR).

Учитывая транспортных средств в парке в качестве децентрализованных агентов, мы постулируем, что использование «Адаптация на основе обучения с подкреплением (RL)» является ключевым фактором для формирование маршрута в динамичной среде.

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

Результаты с единственная обученная модель на больших тестовых данных вне распределения демонстрирует масштабируемость и гибкость предлагаемого подхода.

…»



«

В этой статье мы представляем новый подход к решению сложных проблем маршрутизации. с улучшенным представлением состояния, которое лучше использует сложность модели чем предыдущие методы.

Мы делаем это возможным благодаря тренировкам с учетом временных различий. В частности, используется Q-Learning. Мы показываем, что наш подход позволяет ультрасовременная производительность для политики авторегрессии, которая последовательно вставьте узлы для построения решений на CVRP.

Кроме того, мы первые решить MDVRP с помощью методов машинного обучения и продемонстрировать, что это тип задачи значительно выигрывает от нашего подхода по сравнению с другими методами машинного обучения.

…»



«

Для NP-сложных задач комбинаторной оптимизации обычно сложно находить качественные решения за полиномиальное время. Дизайн либо точный алгоритм или приближенный алгоритм для этих задач часто требует существенно специализированные знания. В последнее время методы глубокого обучения позволяют новые направления решения подобных проблем. В этой статье предлагается структура сквозное глубокое обучения с подкреплением для решения комбинаторных задач оптимизации этого типа.

Этот фреймворк можно применять к разным проблемы только с небольшими изменениями ввода (например, для путешествий задача продавца (TSP), на входе - двумерные координаты узлов; в то время как для задачи маршрутизации с ограниченной пропускной способностью (CVRP) входом является просто заменены на трехмерные векторы, включая двумерные координаты и требования клиентов узлов), маски и контекст декодера векторов. Предлагаемая структура направлена ​​на улучшение моделей грамотности в термины модели нейронной сети и алгоритма обучения. Решение качество TSP и CVRP до 100 узлов значительно улучшено благодаря нашему рамки.

В частности, средний разрыв оптимальности сокращен с 4,53% до 6,68% для CVRP со 100 узлами при использовании жадная стратегия декодирования.

Кроме того, наш фреймворк использует около 1/3 ∼ 3/4 обучающие образцы по сравнению с другими существующими методами обучения при достижении лучшие результаты. Результаты, полученные на случайно сгенерированных экземплярах, и экземпляры тестов из TSPLIB и CVRPLIB подтверждают, что наша структура имеет линейное время работы от размера задачи (количества узлов) в процессе тестирования фаза, и имеет хорошую производительность обобщения от обучения случайным экземплярам к тестированию реальных экземпляров.

…»



«В этой статье мы представляем схемы аппроксимации для емкостного транспортного средства. Задача маршрутизации (CVRP) на нескольких классах графов. В CVRP, представленный Данциг и Рамзер (1959), нам дан график G=(V,E) с метрическими краями затраты, депо r∈V, и автомобиль ограниченной вместимости Q.

Цель состоит в том, чтобы найти минимальную стоимость туров для автомобиля, который возвращается в депо, каждое посещение не более Q узлы, так что они покрывают все узлы. Это обобщает классический TSP и был тщательно изучен. В более общие настройки, каждый узел v имеет спрос d v и общий спрос каждого тур должен быть не более Q.

Либо спрос каждого узла должен обслуживаться один тур (неразделимый) или может обслуживаться несколькими турами (разделенный). В самый известный алгоритм аппроксимации общих графиков имеет соотношение α + 2 (1-ϵ) (для нерасщепляемого) и α + 1 - ϵ (для splittable) для некоторых фиксированных ϵ > 1/3000, где а это наилучшее приближение для TSP.

Даже для деревьев наилучшее приближение соотношение 4 / 3 Беккера (2018), и вопрос о существовании схема аппроксимации для этого простого класса графов.

Дас и Матье (2015) представили схему аппроксимации со временем п журнал O\log^{(1/ϵ)п} за Евклидова плоскость R^2. Никакой другой схемы аппроксимации не известно ни для одного другой класс метрик (без дополнительных ограничений на Q).

В этой статье мы добиться значительного прогресса в решении этой классической проблемы, представив Квазиполиномиальные схемы аппроксимации времени (QPTAS) для графов ограниченного Treewidth, графики ограниченных размеров автомагистралей и графики ограниченного удвоения габаритные размеры.

Для сравнения наш результат представляет собой схему аппроксимации для Евклидов самолет со временем выполнения n O(\log^{10}{n/ϵ^9}).…»



«

Мы исследуем проблему маршрутизации емкостных транспортных средств (CVRP) под в контексте робототехники, где должна быть завершена доставка автомобиля с ограниченной полезной нагрузкой (или самовывоз) задач для обслуживания группы географически распределенных клиентов с различные требования.

В классической CVRP местоположение клиента моделируется как точка. Однако во многих приложениях робототехники более целесообразно моделировать такие «местоположения клиентов» как 2D-регионы.

Например, при воздушной доставке дрон может уронить посылку в любом месте на стоянке клиента. Это приводит к проблеме CVRG (Маршрутизация емкостного транспортного средства с целевыми геометрическими ограничениями). С вычислительной точки зрения CVRP уже сильно NP-труден; CVRG поэтому больше испытывающий. Тем не менее, мы разрабатываем быстрые алгоритмы для CVRG, способные Вычислительные решения высокого качества для сотен регионов.

Наши алгоритмические решение гарантированно будет оптимальным, когда клиентские регионы выпуклые. Численные оценки показывают, что предложенные нами методы значительно превосходят по эффективности. жадные подходы по принципу «лучший первым». Всесторонние исследования моделирования подтверждают эффективность наших методов.

…»



«

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

Более того, на самом деле существует множество неявных предпочтения укоренились в умах планировщиков маршрутов и водителей. Водители, например, знакомы с определенными районами и знание состояния дорог, и часто считаю лучшие места для отдыха и обеденные перерывы. Это знание сложно сформулировать и сбалансировать, когда необходимо принять оперативные решения по маршрутизации. Это мотивирует нас изучать неявные предпочтения из прошлых решений и включение этих усвоенных предпочтения в процессе оптимизации. Эти предпочтения представлены в виде вероятности дуги, т. е. чем предпочтительнее маршрут, тем выше стык вероятность.

Новизна данной работы заключается в использовании модели нейронной сети для оценить вероятности дуги, что позволяет использовать дополнительные функции и автоматическая оценка параметров. Для этого сначала необходимо определить подходящие особенности, нейронные архитектуры и функции потерь, учитывая, что обычно имеется мало данных. Исследуем разницу с подход к взвешенному марковскому счету и изучение применимости нейронных сети в этой настройке.

…»



«

Подходы глубокого обучения показали многообещающие результаты в решении проблем маршрутизации. проблемы. Однако по-прежнему существует значительный разрыв в качестве решений между алгоритмы машинного обучения и исследования операций. Недавно появилась еще одна линия было проведено исследование, объединяющее сильные стороны машинного обучения и алгоритмы оперативного исследования. В частности, поисковые операторы возмущения были использованы для улучшения решения. Тем не менее, используя возмущение не может гарантировать качественное решение.

Этот документ представляет собой «Обучение руководству Локальный поиск» (L2GLS), основанный на обучении подход к решению проблем маршрутизации, который использует штрафной термин и обучение с подкреплением для адаптивной корректировки поисковых усилий. L2GLS сочетает в себе сильные стороны операторов локального поиска (LS) с условиями штрафов, чтобы избежать локальных оптимальных значений. Проблемы маршрутизации имеют множество практических приложений, часто предварительная настройка более крупных экземпляров, что по-прежнему является сложной задачей для многих существующих алгоритмы, представленные в обучении для оптимизации поля.

Покажем, что L2GLS достигает новых современных результатов на больших TSP и CVRP по сравнению с другими методы машинного обучения.

…»



«

В последнее время Transformer стал преобладающей глубокой архитектурой для решения проблемы с маршрутизацией транспортных средств (VRP). Однако он менее эффективен в обучении модели улучшения VRP, потому что его метод позиционного кодирования (PE) не подходит для представления решений VRP. В этой статье представлен новый Dual-Aspect Collaborative Transformer (DACT) для изучения вложений для узла и позиционные элементы по отдельности, вместо того, чтобы объединять их вместе, как это сделано в существующие, чтобы избежать потенциальных шумов и несовместимых корреляций.

Кроме того, позиционные особенности встроены в новую циклическую метод позиционного кодирования (CPE), позволяющий Transformer эффективно захватывать округлость и симметрия решений VRP (т. е. циклических последовательностей). Мы обучить DACT с помощью Proximal Policy Optimization и разработать учебную программу стратегия для повышения эффективности выборки.

Мы применяем DACT для решения путешествий проблема продавца (TSP) и проблема выбора маршрута транспортного средства (CVRP). Результаты показать, что наш DACT превосходит существующие модели улучшения на основе трансформаторов, и демонстрирует гораздо лучшую производительность обобщения по разным задачам размеры на синтетических и тестовых экземплярах соответственно.

…»



«

Существующие методы на основе глубокого обучения с подкреплением (DRL) для решения емкостная задача маршрутизации транспортных средств (CVRP) по своей сути справляется с однородными автопарк, в котором предполагается, что автопарк повторяет один транспортное средство. Следовательно, их ключ к построению решения заключается исключительно в выборе следующего узла (заказчика) для посещения без учета выбора автомобиля. Однако транспортные средства в реальных сценариях, вероятно, будут неоднородными с различные характеристики, влияющие на их вместимость (или скорость движения), делая существующие методы DRL менее эффективными.

В этой статье мы рассмотрим гетерогенный CVRP (HCVRP), где транспортные средства в основном характеризуются разные емкости. Мы рассматриваем как минимальные, так и максимальные значения для минимальной суммы. HCVRP, которые направлены на минимизацию самого длительного или общего времени в пути транспортного средства (транспортных средств) во флоте. Для решения этих проблем мы предлагаем метод DRL, основанный на механизм внимания с декодером выбора автомобиля, учитывающий гетерогенное ограничение парка и декодер выбора узла, учитывающий построение маршрута, который учится строить решение автоматически выбор транспортного средства и узла для этого транспортного средства на каждом шаге.

Экспериментальный результаты, основанные на случайно сгенерированных экземплярах, показывают, что при желательном обобщения для различных размеров задач, наш метод превосходит современный метод DRL и большинство обычных эвристик, а также обеспечивает конкурентоспособную производительность по сравнению с современным эвристическим методом, то есть SISR. Кроме того, результаты расширенных экспериментов демонстрируют, что наш метод также может решать экземпляры CVRPLib с удовлетворительным представление.

…»



«Мы изучаем распространенную проблему доставки, с которой сегодня сталкиваются в Интернете. платформы заказа еды: клиенты заказывают блюда онлайн, а в ресторане доставляет еду после получения заказа.

Конкретно изучаем проблему где k автомобили вместимостью c обслуживаем набор запросов на заказ еды из одного ресторана. После поступления заявки его может обслужить автомобиль. переезд из ресторана в место доставки. Мы заинтересованы в обслуживание всех запросов с минимизацией максимального времени потока, то есть максимального время, в течение которого покупатель ждет своей еды после подачи приказ.

Мы показываем, что проблема сложна как в офлайн, так и в онлайн-настройках: Там это жесткость приближения Ω(п) для автономной проблемы и нижняя граница Ω(п) о конкурентоспособности любого онлайн-алгоритма, где п количество точек в метрике.

Наш главный результат — это О(1) — конкурентный онлайн-алгоритм для некомпетентных (то есть c=∞) проблема доставки еды на древовидных метриках. Затем мы рассматриваем увеличение скорости модель.

Мы развиваем экспоненциальное время (1+ϵ) — скорость О(1/ϵ) — конкурентный алгоритм для любых ϵ>0.

Полиномиальное время алгоритм может быть получен с коэффициентом скорости α_{TSP}+ϵ или

α_{CVRP}+ϵ, в зависимости от того, исправна ли проблема. Здесь α_{TSP}, а также α_{CVRP} являются коэффициентами наилучшего приближения для коммивояжер (TSP) и проблемы с маршрутизацией транспортного средства (CVRP) соответственно.

Дополняем результаты некоторыми отрицательными.…»



«

Представлена ​​задача планирования многопериодного инспектора (MPISP), что представляет собой новый вариант задачи о маршрутизации многопутевого транспорта со временем. окна (VRPTW). В MPISP каждый инспектор должен выполнить маршрут в заданном многопериодном горизонте планирования. В конце каждого периода каждый инспектор не обязан возвращаться в депо, но должен оставаться в одном из вершины для восстановления сил. Если оставшееся время текущего периода равно недостаточно для того, чтобы инспектор покинул свою текущую вершину А к определенная вершина B, он/она может выбрать либо ожидание в вершине A до начала следующего периода или переход в вершину C, которая ближе к вершине B. Следовательно, на кратчайшее время прохождения между любой парой вершин влияет продолжительность периода и время отправления.

Сначала мы опишем подход вычисление кратчайшего времени прохождения между любой парой вершин с произвольное время отправления. Для решения MPISP мы предлагаем несколько локальных операторы поиска адаптированы из классических операторов для VRPTW и интегрированы их в систему запрета поиска. Кроме того, мы представляем ограниченный модель ранца, которая может дать оценку сверху для задачи. Ну наконец то, мы оцениваем эффективность нашего алгоритма с помощью обширных экспериментов на основе на множестве тестовых экземпляров.

Результаты наших расчетов показывают, что наши подход порождает качественные решения.

…»



«

В данной статье рассматривается нечеткий VRPTW с неопределенным временем пробега. Теория достоверности используется для моделирования проблемы и определяет предпочтения. индекс, при котором желательно, чтобы время в пути до клиентов уменьшалось в свои временные окна.

Предлагаем интеграцию нечеткой и муравьиной колонии. системный эволюционный алгоритм для решения проблемы с сохранением ограничения. Результаты расчетов для некоторых задач тестов, имеющих короткое замыкание и долгосрочные горизонты представлены, чтобы показать эффективность алгоритм.

Проведено сравнение различных индексов предпочтений. чтобы помочь пользователю в принятии подходящего решения.

…»



«

Мы рассматриваем динамическую задачу маршрутизации транспортных средств с временными окнами и стохастические клиенты (DS-VRPTW), такие, что клиенты могут запрашивать услуги поскольку автомобили уже выехали в путь. Чтобы решить эту проблему, цель заключается в предоставлении правила принятия решения для выбора на каждом временном шаге следующего действия выполнять в свете известных запросов и вероятностных знаний о запросах вероятность.

Мы вводим новое правило принятия решений, которое называется Global Stochastic. Правило оценки (GSA) для DS-VRPTW, и мы сравниваем его с существующими правила принятия решений, такие как MSA. В частности, мы показываем, что GSA полностью интегрирует ограничения непредвиденности, так что это приводит к лучшим решениям в нашем стохастический контекст. Мы описываем новый эвристический подход для эффективного приближается к нашему правилу GSA. Мы представляем новую стратегию ожидания.

Эксперименты по динамические и стохастические тесты, включающие экземпляры разной степени динамизма, показывают, что не только наш подход конкурентоспособен с современные методы, но также позволяет вычислять значимые в автономном режиме решения полностью динамических задач, в которых нет априорного клиента запрос предоставляется.

…»



«

Основная цель этой статьи — эффективно прокладывать маршрут и планировать автопарк. электромобилей (EV) на дорожной сети, чтобы обслуживать набор клиенты. В частности, мы стремимся предложить оптимальное планирование маршрута за счет используя преимущества этих транспортных средств. В наши дни электромобили, по сути, играет ключевую роль в сокращении вредных выбросов за счет использования традиционные автомобили. Отправной точкой этого исследования является тот факт, что новейшие передовые технологии для электромобилей позволяют также частично заряжая свои батареи.

В этой работе проблема маршрутизации электромобиля. с Time Windows (E-VRPTW) рассматривается с точки зрения эффективного времени при условии, что частичная подзарядка также разрешена. Для этого E-VRPTW математически сформулирована как смешанная целочисленная линейная программа в которые как общее количество используемых электромобилей, так и общее время, проведенное ими вне депо сведены к минимуму. Из-за NP-сложности проблемы Математический алгоритм Variable Neighborhood Search Branch (VNSB) также предназначен для определение качественных решений за разумное время вычислений.

Числовой результаты, полученные на некоторых тестовых примерах, взятых из литературы предоставить полезную информацию о качестве решения предлагаемых формулировка, по сравнению с предыдущей, и характеристики VNSB.

…»



«

Проблема маршрутизации транспортных средств с временными окнами (VRPTW) — важная проблема. в распределении ресурсов в сетях во времени и пространстве. Мы представляем в этой статье основанный на детерминированном отжиге (DA) подход к решению VRPTW с его аспекты маршрутизации и планирования, а также для моделирования дополнительных ограничений разнородных транспортных средств и грузов. Это впервые, чтобы наши знание того, что подход DA был использован для задач в классе VRPTW.

Мы описываем, как можно адаптировать подход DA для создания эффективных эвристический подход к VRPTW. Наш подход DA также предназначен для того, чтобы попадает в локальные минимумы и демонстрирует меньшую чувствительность к начальному решения. Алгоритм торгует маршрутизацией и планированием в n-мерном пространстве. пространство с помощью настраиваемого параметра, что позволяет нам генерировать качественно хорошие решения.

Эти решения различаются степенью пересечения маршрутов, обоснование пунктов передачи, в которых можно обмениваться грузами. Результаты моделирования на случайно сгенерированных экземплярах показывают, что ограничения уважаемы и демонстрируют близкие к оптимальным результаты (если их можно проверить) с точки зрения расписаний и продолжительности индивидуальных туров в каждом решении.

…»



«

Статические стохастические VRP предназначены для моделирования реальных VRP с учетом неопределенность данных. В частности, SS-VRPTW-CR рассматривает стохастические клиентов с временными окнами и не делает никаких предположений об их раскрытии времена, которые также являются стохастическими. На основе вероятностей запросов клиентов, мы ищем априорное решение, составленное превентивными маршрутами движения транспортных средств, минимизируя ожидаемое количество неудовлетворенных запросов клиентов в конце дня.

Маршрут описывает последовательность переброски стратегических транспортных средств, от которых поблизости запросы могут быть быстро достигнуты. Вместо повторной оптимизации в Интернете, так называемая стратегия обращения определяет способ обработки запросов, когда они появляться. В этой статье мы описываем новую стратегию обращения за SS-VRPTW-CR, улучшение маршрута транспорта за счет пропуска бесполезных деталей.

Мы покажем, как вычислить ожидаемая стоимость априорных решений в псевдополиномиальное время для этого стратегия обращения. Мы представляем новую метаэвристику под названием Progressive Focus Поиск (PFS), который можно комбинировать с любым алгоритмом на основе локального поиска для решение задач статической стохастической оптимизации. PFS ускоряет поиск за счет с использованием коэффициентов аппроксимации: из исходной грубой упрощенной задачи поиск постепенно фокусируется на актуальном описании проблемы. Мы оцениваем наши вклады в новый общедоступный эталонный тест, основанный на реальных условиях.

…»



«

В реальной жизни обеспечение безопасности набора больших площадей за счет покрытия область с беспилотными летательными аппаратами (БПЛА) представляет собой сложную проблему, состоящую из нескольких целей. Эти трудности еще больше, если площадь покрытие должно продолжаться в течение определенного временного окна. Мы решаем эту проблему рассмотрение проблемы маршрутизации транспортных средств с изменением временного окна (VRPTW) в какова емкость агентов — один и каждый клиент (целевая область) должен быть поставлено более чем одним транспортным средством одновременно без нарушения сроков окна.

В этой проблеме наша цель — найти способ покрыть все области необходимое количество БПЛА во временных окнах, минимизировать общее расстояние путешествовал, и предоставить быстрое решение, удовлетворив дополнительное ограничение что у каждого агента есть ограниченное количество топлива. Мы представляем новый алгоритм, основанный на кластеризация целевых областей в соответствии с их временными окнами, а затем постепенное создание транспортных проблем с каждым кластером и готовые БПЛА.

Затем решаем транспортные задачи с помощью симплексного алгоритма на сгенерируйте решение. Производительность предложенного алгоритма и др. реализованные алгоритмы сравнения качества решения оцениваются на примере сценарии с практическими размерами задач.

…»



«

Изучается новый вариант хорошо изученной задачи о маршрутизации транспортных средств во времени. Windows (VRPTW), называемая VRPTW с ограниченной хрупкостью, которая предполагает, что

  • 1) вместимость транспортного средства организована в несколько одинаковых штабелей;
  • 2) all (все) товары, взятые у покупателя, либо «хрупкие», либо нет;
  • 3) не хрупкий предметы можно класть поверх хрупких предметов (ограничение хрупкости); и
  • 4) перестановка груза в пути следования невозможна.

Сначала охарактеризуем выполнимость маршрута с учетом этого ограничения хрупкости. Затем, чтобы мы разрабатываем точную отраслевую систему «цена-скидка» (BPC) алгоритм, который включает алгоритм маркировки, использующий эту возможность определение характеристик для эффективного создания возможных маршрутов.

Этот алгоритм сравнивался с другим алгоритмом BPC, который имеет дело с хрупкостью ограничение в задаче генерации столбца по недопустимому пути порезы. Наши результаты расчетов показывают, что прежний алгоритм BPC явно превосходит последний с точки зрения вычислительного времени и хрупкости ограничение оказывает большее влияние на оптимальную стоимость решения (по сравнению с VRPTW) при уменьшении вместимости транспортного средства высота штабеля увеличивается, а для более сбалансированное сочетание покупателей с хрупкими и не хрупкими предметами.

…»



«

Фиксированные сроки получения и доставки могут сильно ограничить производительность грузовых перевозок. На этом фоне операторы автопарка могут использовать механизмы компенсации, такие как денежные стимулы, чтобы выкупить время задержки у своих клиентов, чтобы повысить эффективность автопарка и, в конечном итоге, минимизировать эксплуатационные расходы. Чтобы максимально использовать такую ​​операционную модель, необходимо совместно оптимизировать деятельность автопарка и стимулы с учетом реакции клиентов. На этом фоне в данной статье представлена ​​схема маршрутизации электромобилей с учетом стимулов, в которой оператор автопарка активно предоставляет клиентам стимулы в обмен на гибкость получения или доставки.

В частности, мы сначала разрабатываем двухуровневую модель, в соответствии с которой оператор автопарка оптимизирует маршруты и графики начисления платы вместе со льготной ставкой, чтобы возместить задержки доставки, с которыми столкнулись клиенты. В то же время клиенты выбирают допустимые задержки, минимизируя денежно-взвешенную комбинацию задержек за вычетом возмещения, предлагаемого оператором. Во-вторых, мы решаем сложность, возникающую из-за двухуровневой и нелинейной структуры задачи, с помощью эквивалентного метода преобразования, переформулируя задачу как одноуровневую задачу оптимизации, которая может быть решена с помощью стандартных алгоритмов смешанно-целочисленного линейного программирования.

Мы демонстрируем эффективность нашей структуры с помощью обширных численных экспериментов с использованием данных VRP-REP из Бельгии. Наши результаты показывают, что за счет совместной оптимизации маршрутов и стимулов в зависимости от предпочтений клиентов операционные расходы могут быть снижены до 5%, в то время как клиенты могут сэкономить более 30% на общих расходах на доставку.

…»



«

Мы представляем NeuroLKH, новый алгоритм, сочетающий глубокое обучение с сильной традиционной эвристикой Лин-Керниган-Хельсгаун (LKH) для решения задачи коммивояжера. В частности, мы обучаем сеть с разреженным графом (SGN) с контролируемым обучением для оценки ребер и неконтролируемым обучением для штрафов за узлы, оба из которых имеют решающее значение для повышения производительности LKH.

На основе выходных данных SGN NeuroLKH создает набор кандидатов на кромки и преобразует расстояния до кромок, чтобы направлять процесс поиска LKH. Обширные эксперименты убедительно демонстрируют, что, обучая одну модель на широком диапазоне размеров задач, NeuroLKH значительно превосходит LKH и хорошо обобщается на гораздо более крупные размеры. Кроме того, мы показываем, что NeuroLKH может быть применен к другим проблемам маршрутизации, таким как проблема маршрутизации емкостного транспортного средства (CVRP), проблема получения и доставки (PDP) и CVRP с временными окнами (CVRPTW).

…»



«

В последнее время фреймворки глубокого обучения с подкреплением (DRL) продемонстрировали потенциал для решения NP-сложных проблем маршрутизации, таких как задача коммивояжера (TSP), без специальных экспертных знаний. Хотя DRL можно использовать для решения сложных проблем, структурам DRL все еще трудно конкурировать с современными эвристиками, показывающими существенный разрыв в производительности. В этой статье предлагается новая иерархическая стратегия решения проблем, называемая политиками сотрудничества при обучении (LCP), которая может эффективно находить почти оптимальное решение с использованием двух итеративных политик DRL: сеялки и ревизора.

Сеялка генерирует как можно более разнообразные решения-кандидаты (семена), будучи посвященной исследованию всего комбинаторного пространства действий (т. Е. Последовательности действий присваивания). С этой целью мы обучаем политику сеялки, используя простое, но эффективное вознаграждение за регуляризацию энтропии, чтобы побудить сеялку находить разнообразные решения.

С другой стороны, ревизор изменяет каждое решение-кандидат, созданное сеялкой; он разделяет полную траекторию на субтуры и одновременно пересматривает каждый субтур, чтобы минимизировать расстояние прохождения. Таким образом, ревизор обучается повышать качество решения-кандидата, уделяя особое внимание уменьшенному пространству решений (что полезно для эксплуатации). Обширные эксперименты показывают, что предложенная схема сотрудничества с двумя политиками лучше, чем структура DRL с одной политикой, в решении различных NP-трудных проблем маршрутизации, включая TSP, TSP с получением призов (PCTSP) и проблему маршрутизации с ограниченными возможностями (CVRP).

…»



«

Мы разработали схему аппроксимации (PTAS) полиномиального времени для задачи маршрутизации транспортных средств с единичным спросом (CVRP) на деревьях для всего диапазона вместимости тура. Результат распространяется на расщепляемую CVRP.

…»



«В этой статье мы представляем улучшенные алгоритмы аппроксимации для (неразделимой) задачи о маршрутизации емкостных транспортных средств (CVRP) в общих показателях.

В CVRP, введенном Данцигом и Рамзером (1959), нам дается набор точек (клиентов) V вместе с депо r в метрическом пространстве, причем каждый v∈V имеет спрос dv>0, и транспортное средство ограниченного вместимость Q.

Цель состоит в том, чтобы найти минимальную стоимость туров для транспортного средства, каждая из которых начинается и заканчивается в депо, чтобы каждый клиент посещался хотя бы один раз, а общие потребности клиентов в каждом туре не превышали Q. В изучаемом нами неразделимом варианте потребность узла должна полностью удовлетворяться одним туром.

Мы представляем два алгоритма аппроксимации для нерасщепляемого CVRP: комбинаторное (α + 1,75) -приближение, где α — коэффициент аппроксимации для задачи коммивояжера, и алгоритм аппроксимации, основанный на округлении LP с гарантией приближения α + ln (2) + δ ≈3.194 + δ за время nO (1 / δ). Оба приближения могут быть дополнительно улучшены на небольшую величину в сочетании с недавней работой Blauth, Traub и Vygen (2021), которые получили (α + 2⋅ (1 − ϵ)) — приближение для нерасщепляемого CVRP для некоторой константы ϵ в зависимости от на α (ϵ> 1/3000 при α = 1,5).…»



«

Оптимизация мобильности транспортных средств в городских районах — давняя проблема интеллектуального города и анализа пространственных данных. Учитывая сложный городской сценарий и непредсказуемые социальные события, наша работа сосредоточена на разработке мобильной системы последовательных рекомендаций, чтобы максимизировать прибыльность поставщиков транспортных услуг (например, водителей такси).

В частности, мы рассматриваем задачу динамической оптимизации маршрута как долгосрочную последовательную задачу принятия решений. Для решения этой проблемы предлагается структура обучения с подкреплением путем интеграции механизма самопроверки и глубокой нейронной сети для мониторинга точек получения клиентов. Чтобы учесть непредвиденные ситуации (например, вспышку COVID-19), наш метод предназначен для обработки связанных изменений окружающей среды с помощью механизма самоадаптивного определения параметров.

Основываясь на данных о желтых такси в Нью-Йорке и его окрестностях до и после вспышки COVID-19, мы провели комплексные эксперименты, чтобы оценить эффективность нашего метода. Результаты показывают неизменно отличную производительность, от ежечасных до еженедельных измерений, что подтверждает превосходство нашего метода над современными методами.

…»



«

Сбои в работе университетских городков, вызванные COVID-19, стимулировали стратегии по предотвращению распространения инфекционных заболеваний при сохранении определенного уровня личного обучения. В ответ предлагаемый подход рекурсивно применял алгоритм квантового отжига для оптимизации Max-Cut в системах D-Wave, который сгруппировал студентов в когорты таким образом, чтобы количество возможных событий заражения через общие классы было минимальным.

Чтобы проверить этот подход, были использованы доступные данные курсовых работ для создания высококластеризованных сетей приема на курсы, представляющих студентов и классы, которые они разделяют. Затем алгоритм рекурсивно вызывался в этих сетях для группирования студентов, а для прогнозирования распространения болезни применялась модель заболевания. Результаты моделирования показали, что при некоторых предположениях о статистике болезней и методах распространения метод квантовой группировки снизил как общий, так и пиковый процент инфицированных студентов по сравнению со случайными группировками студентов.

При масштабировании до более крупных сетей этот подход группирования с помощью квантового отжига может обеспечить практическое преимущество перед классическими подходами. Эта статья, однако, представляет собой строго доказательную демонстрацию подхода и не предназначена для аргументов в пользу квантового ускорения.

…»



«

Мы разрабатываем новые алгоритмы аппроксимации для классического задач на графах и ставим задачи в модели RAM при ограниченном пространстве.

В качестве одного из наших основных результатов мы разработали алгоритм для набора «d-ударов», который выполняется за время n^{O(d^2 + d/\epsilon})}, использует O((d^2 + d / \epsilon) log n) бит пространства и достигает отношения приближения O ((d / {\epsilon}) n^{\epsilon}) для любого положительного \epsilon \leq 1 и любого натурального числа d.

В частности, это дает алгоритм аппроксимации с коэффициентом O(\log n), который выполняется за время n^{O (\log n)} и использует O(\log^2n) бит пространства (для константы d).

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

Для примеров проблем с ограниченной кратностью можно добиться большего. Мы разрабатываем алгоритм аппроксимации фактор-2 для вершинного покрытия на графах с максимальной степенью \Delta и алгоритм для вычисления максимальных независимых множеств, которые выполняются за время n^ {O (\ Delta)} и используют O(\Delta \log n) биты пространства.

Для более общей задачи d-Hitting Set мы разрабатываем алгоритм аппроксимации фактора d, который работает за время n^{O (d {\delta}^2)} и использует O(d {\delta}^2 \log n) биты пространства в наборах семейств, где каждый элемент встречается не более чем в \delta наборах.

Для независимого набора, ограниченного графами со средней степенью d, мы даем алгоритм аппроксимации с коэффициентом (2d), который работает за полиномиальное время и использует O (log n) бит пространства.

Мы также разработали алгоритм аппроксимации фактор — O(d^2) для доминирующего множества на d-вырожденных графах, который работает во времени n^{O(\log n)} и использует O(\log^2n) бит пространства.

Для d-регулярных графов мы покажем, как известный алгоритм приближения с рандомизированным коэффициентом O(\log d) может быть дерандомизирован для работы во времени n^{O(1)} и использования O(\log n) бит пространства.

Наши результаты используют комбинацию идей теории ядра, распределенных алгоритмов и рандомизированных алгоритмов.

…»



«
   The Heterogeneous Fleet Vehicle Routing Problem (HFVRP) is an important variant of the classical Capacitated Vehicle Routing Problem (CVRP) that aims to find routes that minimize the total traveling cost of a heterogeneous fleet of vehicles. 

This problem is of great interest given its importance in many industrial and commercial applications.

In this paper, we present an Adaptive Iterated Local Search (AILS) heuristic for the HFVRP. AILS is a local search-based meta-heuristic that achieved good results for the CVRP.

The main characteristic of AILS is its adaptive behavior that allows the adjustment of the diversity control of the solutions explored during the search process.

The proposed AILS for the HFVRP was tested on benchmark instances containing up to 360 customers. The results of computational experiments indicate that AILS outperformed state-of-the-art metaheuristics on 87\% of the instances.

…»



«

Совместная доставка посылок грузовиками и дронами в течение некоторого времени привлекала большое внимание, поскольку преимущества одного метода доставки компенсировали недостатки другого. В этом документе основное внимание уделяется проблеме маршрутизации транспортных средств с помощью дронов и выбора скорости дронов (VRPD-DSS), в которой подробно рассматриваются зависящее от скорости потребление энергии и зарядка дронов.

С этой целью мы формулируем комплексную целочисленную задачу, которая направлена ​​на минимизацию эксплуатационных затрат, состоящих из затрат на потребление топлива грузовиками, затрат на рабочую силу водителей и затрат на электроэнергию дронов.

Скорость полета дрона должна выбираться из дискретного набора.

Мы вводим этапы предварительной обработки для устранения доминирующих скоростей полета, чтобы уменьшить размер проблемы, и используем допустимые неравенства для ускорения процесса решения.

Учет потребления энергии в зависимости от скорости приводит к тому, что желательно выполнять разные полеты с разной скоростью, а не постоянно управлять дроном на максимальной скорости.

Вместо этого следует выбирать скорость дрона, чтобы сбалансировать дальность полета дрона и скорость доставки.

Наше обширное вычислительное исследование реальной сельской местности показывает, что при реалистичном моделировании энергопотребления экономия эксплуатационных расходов по сравнению с доставкой только на грузовиках значительна, но меньше, чем в ранее опубликованных работах.

Наш анализ также показывает, что наибольшая экономия связана с тем, что общее время доставки сокращается по сравнению с доставкой только грузовиком, что позволяет сократить дорогостоящее время водителя грузовика.

Однако дополнительные затраты на энергию дрона в значительной степени незначительны.

…»



«

Персонализированное федеративное обучение (PFL) недавно добилось огромного прогресса, что позволяет разрабатывать новые приложения машинного обучения для сохранения конфиденциальности данных обучения.

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

В этой работе мы рассматриваем недавно предложенную настройку PFL с целевой функцией смешивания, подход, сочетающий изучение глобальной модели вместе с локально распределенными учащимися.

В отличие от большинства предыдущих работ, которые рассматривали только централизованную настройку, мы работаем в более общей и децентрализованной настройке, которая позволяет нам разрабатывать и анализировать более практичные и объединенные способы подключения устройств к сети.

Мы предложили новые алгоритмы для решения этой проблемы и предоставили теоретический анализ гладких (сильно) выпуклых (сильно) вогнутых задач перевала в стохастическом и детерминированном случаях. Численные эксперименты над билинейными задачами и нейронными сетями с противоборствующим шумом демонстрируют эффективность предложенных методов.


…»

Video: https://drive.google.com/file/d/1LDN3VujlMBVJa6uuhyaAS-Xur5Q1V6N5/view?usp=sharing



«

Мы изучаем методы решения (сильно) выпуклых- (сильно) вогнутых задач перевала (SPP) в сетях двух типов - с основной / рабочей (централизованной) архитектурой и ячеистой (таким образом децентрализованной) сетями.

Предполагается, что локальные функции в каждом узле аналогичны из-за схожести статистических данных или по иным причинам. Мы устанавливаем нижние оценки сложности для довольно общего класса алгоритмов, решающих SPP. Мы показываем, что заданная субоптимальность ϵ> 0 достигается по сетям главный / рабочий в Ω (Δ⋅δ / μ⋅log (1 / ε)) раундах связи, где δ> 0 измеряет степень подобия локальных функций, μ — их константа сильной выпуклости, а Δ - диаметр сети.

Нижняя граница сложности связи для ячеистых сетей составляет Ω (1 / ρ −− √⋅δ / μ⋅log (1 / ε)), где ρ - (нормализованная) собственная щель матрицы сплетен, используемой для связи между соседними узлами. Затем мы предлагаем алгоритмы сопоставления нижних границ для любого типа сетей (с точностью до лог-факторов).

Мы оцениваем эффективность предложенных алгоритмов на проблеме робастной логистической регрессии.

…»



«

Мы представляем новый алгоритм адаптивной оптимизации для крупномасштабных задач машинного обучения.

Благодаря недорогой оценке локальной кривизны и липшицевости, наш метод динамически адаптирует направление поиска и размер шага. Направление поиска содержит информацию о градиенте, предварительно обусловленную хорошо масштабированной диагональной матрицей предварительного кондиционирования, которая фиксирует информацию о локальной кривизне.

Наша методика не требует утомительной настройки скорости обучения, так как скорость обучения обновляется автоматически без добавления дополнительных гиперпараметров. Мы предоставляем гарантии сходимости для исчерпывающего набора задач оптимизации, включая выпуклые, сильно выпуклые и невыпуклые задачи, как в детерминированном, так и в стохастическом режимах. Мы также проводим обширную эмпирическую оценку стандартных задач машинного обучения, обосновывая универсальность нашего алгоритма и демонстрируя его высокую производительность по сравнению с другими современными методами первого и второго порядка.

…»











«

We give a general method for constructing a deterministic strategy of Reality from a randomized strategy in game-theoretic probability.

The construction can be seen as derandomization in game-theoretic probability.

…»



«

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

Недавно была исследована возможность автоматической настройки структуры MOACO, что привело к появлению новых современных алгоритмов MOACO для задач «двухцелевой задачи о путешествующем коммивояжере».

В данной работе мы применяем этот подход к двухцелевой двумерной задаче о ранце (bBKP), чтобы доказать его общность и мощность.

В качестве первого шага мы настраиваем и улучшаем производительность четырех алгоритмов MOACO, которые были предложены ранее для bBKP. На втором этапе мы настраиваем полную структуру MOACO и показываем, что автоматически настроенная структура MOACO превосходит все предыдущие алгоритмы MOACO для bBKP, а также их улучшенные варианты. …»



«

Рассматриваем проблему разделения максимально нарушенных неравенств для задачи ранца с ограничениями предшествования.

Хотя мы рассматриваем максимально нарушенные ограничения в общем случае, особое внимание уделяется индуцированным накрытиям и индуцированным кликовым неравенствам.

Наш вклад включает новую частичную характеристику максимально нарушенных неравенств, новую технику безопасного сокращения, а также новые идеи по усилению и подъему.

…»



«

В этой статье мы представляем новый класс криптографии с открытым ключем ранцевого типа, называемый «K(II)ΣΠPKC».

В K(II)ΣΠPKC Боб случайным образом конструирует очень маленькое подмножество набора открытых ключей Алисы, порядок которых очень велик, при условии, что скорость кодирования ρ удовлетворяет условию «0,01<ρ<0,5».

В K(II)ΣΠPKC не существует секретной последовательности, такой как супер-увеличивающаяся последовательность или сдвинуто-удвоенная последовательность, но последовательность, компонент которой построен произведением одного и того же числа множества простых чисел одинакового размера.

Мы показываем, что K(II)ΣΠPKC безопасен против таких атак, как алгоритм LLL, атака Шамира и т.д. поскольку подмножество открытых ключей Алисы выбирается полностью вероятностно на стороне отправителя.

Мы также показываем, что K(II)ΣΠPKC может быть использован в качестве члена класса криптосистем с общим ключом, поскольку список открытых ключей Алисы выбирается полностью вероятностным образом, потому что список подмножества, случайно выбранного Бобом, может быть использован в качестве общего ключа между Бобом и Алисой, при условии строгого соблюдения условий, приведенных в данной работе, без уведомления Алисы о своем секретный ключом по определенному секретному каналу.

…»



«

Представлена новая реализация генетического алгоритма с использованием кластера с несколькими графическими процессорами. Предложенная реализация использует островной генетический алгоритм, в котором каждый GPU развивает один остров.

Особи обрабатываются с помощью CUDA варпов, что позволяет решать большие ранцы и устраняет нежелательную дивергенцию потоков.

MPI интерфейс MPI используется для обмена генетическим материалом между изолированными островами и сбора статистических данных. Характеристики предложенных ГА исследуются на двухузловом кластере, состоящем из 14 графических процессоров Fermi и 4 шестиядерных процессоров Intel Xeon. Общая общая производительность GPU предложенного ГА достигает 5,67 TFLOPS.

…»



«

В многомерной задаче о ранце задан набор предметов, каждый из которых имеет стоимость и многомерный размер, и мы хотим выбрать подмножество из них таким образом, чтобы общая стоимость выбранных предметов была максимальной, а общий размер удовлетворял некоторому ограничению емкости для каждого измерения.

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

На ограничения емкости накладывается совместное вероятностное ограничение, а целевая функция такая же, как и в основной детерминированной задаче.

Мы показали, что задача является выпуклой, при некотором условии на параметры, для специальных непрерывных и дискретных распределений: гамма, нормального, Пуассона и биномиального, где две последние функции дискретного распределения аппроксимируются логново-вогнутыми функциями непрерывного распределения.

…»
StasFomin 09:42, 23 ноября 2021 (UTC):своего алгоритма у них нет, много зубодробительного анализа в среднем, и потом они гоняют промышленные солверы... все равно можно попробовать.



«

Задачи с «многоруким бандитом» являются доминирующей теоретической моделью компромиссов между разведкой и эксплуатацией в обучении, и они имеют бесчисленное множество применений, начиная от медицинских испытаний, коммуникационных сетей и заканчивая веб-поиском и рекламой.

Во многих из этих прикладных областей обучающийся может быть ограничен одним или несколькими ограничениями на предложение (или бюджет), в дополнение к обычному ограничению на временной горизонт. В литературе отсутствует общая модель, охватывающая такого рода проблемы.

Мы представляем такую модель, называемую «бандиты с ранцами», которая сочетает в себе аспекты стохастического целочисленного программирования и онлайн-обучения. Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку». Следовательно, достижение «сублинейного сожаления» в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.

Мы представляем два алгоритма, чье вознаграждение близко к информационно-теоретическому оптимуму: один основан на новой парадигме «сбалансированной разведки», а другой — это первично-дуальный алгоритм, использующий мультипликативные обновления. Далее мы доказываем, что «сожаление», достигаемое обоими алгоритмами, оптимально до полилогарифмических коэффициентов.

Мы иллюстрируем общность проблемы, представляя приложения в ряде различных областей, включая электронную торговлю, маршрутизацию и составление расписаний. В качестве примера конкретного приложения мы рассматриваем проблему динамического ценообразования на размещение с ограниченным предложением и получаем первый алгоритм, чье сожаление по отношению к оптимальной динамической политике является сублинейным по отношению к предложению. …»

Расширенная версия Citeseer/Bandits_with_Knapsacks_—_Dynamic_procurement_for_crowdsourcing_10.1.1.365.1661



«

В базовой версии динамической «задачи закупок» алгоритм имеет бюджет B, который он должен потратить, и сталкивается с n агентами (потенциальными продавцами), которые прибывают последовательно.

Алгоритм предлагает каждому прибывшему продавцу цену «бери или вали»; стоимость продавца для товара является независимой выборкой из

некоторого фиксированного (но неизвестного) распределения.

Цель — максимизировать количество купленных товаров.

Эта проблема особенно актуальна для развивающейся области краудсорсинга, где агенты соответствуют (относительно недорогим) работникам на краудсорсинговой платформе, такой как Amazon Mechanical Turk, а покупаемые/продаваемые «предметы» соответствуют простым заданиям («микрозадачам»), которые могут быть выполнены этими работниками.

Алгоритм соответствует «клиенту»: субъекту, который подает задания и получает выгоду от их выполнения.

Базовая формулировка допускает различные обобщения, например, на несколько типов заданий.

Мы также

  • рассматриваем альтернативную модель, в которой заказчик публикует предложения для всей толпы.
  • Моделируем динамические проблемы закупок как проблемы многорукого бандита с бюджетным ограничением.
  • определяем «бандиты с ранцами»: широкий класс задач многорукого бандита с ограничениями на использование ресурсов в стиле ранца, который включает в себя динамические закупки и множество других приложений.

Отличительной особенностью нашей задачи, по сравнению с существующей литературой по минимизации сожалений, является то, что оптимальная политика для данного латентного распределения может значительно превосходить политику, которая играет «оптимальную фиксированную руку».

Следовательно, достижение сублинейного сожаления в задаче «бандит с рюкзаками» значительно сложнее, чем в обычных задачах с бандитами.

Наш основной результат — алгоритм для версии бандита с рюкзаками с конечным числом возможных действий.

Это первично-дуальный алгоритм с мультипликативными обновлениями; сожаление этого алгоритма близко к информационно-теоретическому оптимуму.

Мы выводим следствия для динамических закупок, использующих равномерную дискретизацию цен.

…»



«

Предлагается инновационная модель, основанная на эффективности динамических ожиданий и новый алгоритм оптимизации задачи о 0-1 рюкзаке, включая анализ и исследования.

Проанализировав изучение 30 групп задач о 0-1 рюкзаке по дискретному коэффициенту данных, мы нашли пару групп задач, которых можно решить

методом динамического ожидания.

По сравнению с «искусственным свечением плавания червя», скорость сходимости этого алгоритма в десять раз быстрее, чем у «искусственного светлячка»

алгоритм, и объем памяти этого алгоритма составляет одну четверть от объема памяти алгоритма «искусственного плавания светлячков».
…»



«

Точная 0-1 задача квадратичного рюкзака из k элементов («E—kQKP») состоит из максимизации квадратичной функции при двух линейных ограничениях: первое — классическое линейное ограничение вместимости; второе — ограничение равенства кардинальности на количество предметов в ранце.

Большинство случаев этой NP-трудной задачи с более чем сорока переменными не могут быть решены в течение одного часа с помощью коммерческого программного обеспечения, такого как CPLEX 12.1.

Поэтому мы предлагаем быстрый и эффективный эвристический метод, который позволяет получить как хорошие нижние, так и верхние границы стоимости задачи за разумное время. В частности, он включает объединяет первичную эвристику и фазу редукции полудефинитного программирования в рамках суррогатной двойной эвристики.

Большие вычислительные эксперименты над случайно сгенерированными экземплярами, содержащими до 200 переменных, подтверждают актуальность границ, полученных нашей гибридной двойственной эвристикой, которая дает известные оптимумы (и доказывает оптимальность) в 90% (или 76%) в среднем за 100 секунд. …»



«

Мы исследуем две новые задачи оптимизации — минимизацию подмодульной функции при условии ограничения на подмодульную нижнюю границу («подмодульное покрытие») и максимизация субмодулярной функции с учетом субмодулярного верхнего ограничения («субмодулярный ранец»).

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

Эти задачи часто ставятся как минимизация разности между субмодулярными функциями, что в худшем случае не поддается аппроксимации.

Однако мы показываем, что, формулируя эти задачи как оптимизацию с ограничениями, что более естественно для многих приложений, мы получаем ряд ограниченных гарантий аппроксимации.

Мы также показываем, что обе эти проблемы тесно связаны, и алгоритм аппроксимации, решающий одну из них, может быть использован для получения гарантии аппроксимации для другой.

Мы приводим результаты твердости для обеих задач, показывая, что наши коэффициенты аппроксимации тесны вплоть до лог-факторов.

Наконец, мы эмпирически демонстрируем производительность и хорошие свойства масштабируемости наших алгоритмов.

…»



«

В классической задаче о k-центрах нам дается метрический граф, и задача состоит в том, чтобы выбрать k—вершин в качестве центров таким образом, чтобы максимальное расстояние от любой вершины до ближайшего центра было минимизировано.

В данной работе мы рассматриваем два важных обобщения k-центра — проблему матроидного центра и проблему центра ранца.

Обе проблемы мотивированы недавними приложениями сетей распространения контента. Наш вклад можно суммировать следующим образом:

  • Рассматриваем проблему центра матроида, в которой центры должны образовывать независимое множество заданного матроида, показываем, что эта проблема NP-трудна даже на прямой.
  • Представляем алгоритм 3-аппроксимации для этой задачи на общих метриках. Рассматриваем версию проблемы, в которой заданное число вершин может быть исключено как из решения.
    • Представляем 7-аппроксимацию для версии с выбросами.
  • Рассматриваем проблему (мульти)ранцевого центра, в которой центры должны удовлетворять одному (или нескольким) ограничению (ограничениям) ранца. Известно, что проблема центра ранца с одним ранцевым ограничением допускает 3-аппроксимацию. Однако, когда существует мы показываем, что эта задача вообще не аппроксимируема.
  • Чтобы дополнить результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены не более чем в 1 + ǫ раз.
    • Получаем 3-аппроксимацию для версии с выбросом которая может нарушить ограничение ранца на 1 + ǫ.
…»



«

«Алгоритмы развертывания» (Rollout algorithms) продемонстрировали отличную производительность при решении различных задач динамической и дискретной оптимизации.

Хотя во многих случаях гарантируется, что ролл-аут алгоритмы работают так же хорошо, как и их базовые политики, теоретических результатов, показывающих дополнительное улучшение производительности, было немного.

В данной работе мы проводим вероятностный анализ проблемы суммы подмножеств и проблемы ранца, приводя теоретические доказательства того, что алгоритмы выкатывания работают строго лучше, чем их базовые политики.

Используя стохастическую модель из существующей литературы, мы анализируем два метода свертывания, которые мы называем последовательным свертыванием и исчерпывающим свертыванием, оба из которых используют простую жадную базовую политику.

Для задачи о сумме подмножеств мы доказываем, что после всего одной итерации алгоритма выкатывания оба метода дают по крайней мере 30%-ное сокращение ожидаемого разрыва между значением решения и мощностью по сравнению с базовой политикой.

Аналогичные результаты показаны для задачи о ранце. …»

тут немного круто, но можно наверно опустить все доказательства, но хотя бы постановки-сами алгоритмы, …



«

Методы локального поиска все чаще используются в многоцелевой комбинаторной оптимизации из-за их способности улучшать выполнение метаэвристик.

Эффективность многоцелевых методов локального поиска сильно зависит от таких факторов, как (i) операторы соседства, (ii) правила поворота и (iii) склонность к хорошим областям объективного пространства.

В этой работе мы провели обширную экспериментальную кампанию по анализу таких факторов в алгоритме локального поиска Парето (PLS) для двумерной двумерной задачи о рюкзаке (bBKP).

В первой серии экспериментов мы исследуем PLS как автономный алгоритм, начиная со случайных и жадных решений.

Во втором наборе мы анализируем PLS как постоптимизирующую процедуру. …»



«

Мы изучаем выпуклую оболочку непрерывного ранцевого множества, состоящего из одного ограничения неравенства с n неотрицательными целыми и m неотрицательными ограниченными непрерывными переменными.

При n=1 это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993).

Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено 2^n-n. Наш следующий результат - показать, что при n=2 эта верхняя граница на самом деле равна 1.

Из этого следует, что при n=2 коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с m=1.

Затем показано, что выпуклый корпус множеств с n=2 и m=1 задается гранями либо двухпеременных чисто целочисленных ранцевых множеств, либо непрерывных ранцевых множеств с n=2 и m=1, в которых непрерывная переменная не ограничена.

Мы покажем на примере, что при n=3 ненулевые коэффициенты непрерывных переменных могут принимать различные значения.

…»



«

Проблема многорукого бандита (MAB) представляет собой классический компромисс между разведкой и эксплуатацией.

Входные данные определяют несколько стохастических плеч, которые развиваются с каждым рывком, и цель состоит в том, чтобы максимизировать ожидаемое вознаграждение после фиксированного бюджета тяги. Знаменитая работа [GGW89] предполагает «условие на руки», называемое допущением мартингейла.

Недавно Gupta получил основанную на линейном программировании 1/484-приближение для MAB-задачи без допущения мартингейла.

Мы улучшили этот алгоритм до 4/27-приближения, с более простым анализом.

Наш алгоритм также обобщается на случай суперпроцессов МАБ с (стохастические) многопериодные действия.

Также мы получили (1/2−ε)-приближение для варианта МАБ, в котором упреждение не допускается. … …»



«

Смешанное (линейное и целочисленное) подмножество ограничений с множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением.

Недавно Luedtke и Kucukyavuz изучили допустимые неравенства для таких множеств.

Однако большинство их результатов было сосредоточено на случае равных вероятностей (эквивалентно, когда ранец сводится к ограничению кардинальности), и лишь незначительные результаты были получены в общем случае.

В данной работе мы рассматриваем общий случай вероятностей (ограничение общего ранца).

Мы характеризуем допустимые неравенства, не вытекающие из ранцевого политопа, и используем эту характеристику для обобщения неравенств, полученных ранее для случая равных вероятностей.

Мы также показываем, что можно разделить большой класс неравенств за полиномиальное время.

…»



«

«Иерархия Лассерре/Сумма квадратов» — это систематическая процедура усиления релаксаций ЛП путем построения последовательности все более жестких формулировок. Для широкого круга оптимизационных задач этот подход позволяет получить выпуклые релаксации, используемые в лучших доступных алгоритмах аппроксимации.

ЦЛП емкостного покрытия — это целочисленная программа вида «min{cx : U x ≥ d, 0 ≤ x ≤ b, x ∈ Z+}», где все записи c, U и d неотрицательны.

Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать ||d||_{∞}, даже если U состоит из одной строки (то есть задача «Min Knapsack»).

В настоящее время самое сильное ослабление линейной программы получается путем добавления (экспоненциально большого числа) допустимых неравенств, введенных Вулси (Wolsey), что дает очень мощный способ решения этих проблем.

Для задачи «Min Knapsack» мы доказываем, что даже после непостоянного числа уровней «иерархия Лассерра/Сумма квадратов» не улучшает разрыв интегральности 2, подразумеваемый начальными (KC) неравенствами.

Более того, мы показываем, что разрыв интегральности релаксации остается M для особого случая ∑i xi ≥ 1/M при старте со стандартного

политопа Min Knapsack.

Мы отмечаем, что Min Knapsack допускает FPTAS, и наши результаты количественно определяют фундаментальную слабость иерархии Лассерра/суммы квадратов для этой базовой задачи.

…»



«

Предложен эффективный гибридный алгоритм «поиска кукушки» (CS) с улучшенным алгоритмом «перетасованного лягушачьего прыжка» (ISFLA) для решения 0-1 ранцевой задачи. Прежде всего, в рамках SFLA разработан улучшенный оператор «прыжка лягушки» с эффектом глобальной оптимальной информации о прыжке лягушки и обмена информацией между особями лягушки в сочетании с генетической мутацией с небольшой вероятностью.

Чтобы улучшить скорость сходимости и повысить эксплуатационную способность, предлагается новая модель CS с учетом специфических преимуществ «полетов Levy» и оператора прыжка лягушки.

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

Наконец, численное моделирование проведено на шести различных типах экземпляров ранца 0-1, и сравнительные результаты показали эффективность предложенного алгоритма и его способность оптимизировать выполнимое решение, что превосходит бинарный поиск с кукушкой, бинарную дифференциальную эволюцию и генетический алгоритм. …»



«

Мы представляем два новых метода стабилизации алгоритмов генерации столбцов для временной задачи о ранце (Temporal Knapsack Problem, TKP). Впервые мы предложили использовать алгоритмы ветвления и цены для переформулировок Данцига-Вольфа для TKP.

В данном случае соответствующие задачи ценообразования представляют собой TKP меньшего размера, которые могут быть решены с помощью ЦЛП/MIP-решателя общего назначения или динамического программирования.

Наши методы стабилизации адаптированы к ТКП, поскольку они используют (глубокие) двойственные оптимальные неравенства, то есть неравенства, которые, как известно, выполняются всеми (по крайней мере, некоторыми) оптимальными двойственными решениями линейной релаксации.

…»



«

Мы изучаем проблему упаковки ранца, не зная его вместимости.

Всякий раз, когда мы пытаемся упаковать предмет, который не помещается, этот предмет отбрасывается; если предмет помещается, мы должны

включить его в упаковку.

Мы показываем, что всегда существует политика, которая упаковывает ценность в пределах коэффициента 2 от оптимальной упаковки, независимо от фактической вместимости.

Если все предметы имеют единичную плотность, мы достигаем коэффициента, равного золотому сечению φ≈1,618.

Показано, что оба коэффициента являются оптимальными.

Фактически, мы получаем вышеуказанные коэффициенты с помощью упаковочных политик, которые являются универсальными в том смысле, что они фиксируют определенный порядок предметов и пытаются упаковать предметы в этом порядке, независимо от наблюдений, сделанных во время упаковки.

Мы приводим эффективные алгоритмы, вычисляющие эти политики.

С другой стороны, мы показываем, что для любого α > 1 проблема решения вопроса о том, достигает ли данная универсальная политика коэффициента α, является coNP-полной. Если α является частью входных данных, то та же проблема, как показано, является coNP-полной для элементов с единичной плотностью.

Наконец, мы показываем, что для заданного α решить, допускает ли набор предметов универсальную политику с коэффициентом α, даже если все предметы имеют единичную плотность, является coNP-трудной задачей, даже если все элементы имеют единичные плотности.

…»



«

Многие проблемы могут быть сформулированы в виде вариантов проблем ранца. Однако такие модели являются детерминированными, в то время как многие реальные проблемы включают в себя некоторую неопределенность. Поэтому стоит разработать и протестировать модели ранцев, которые могут иметь дело с возмущениями.

В данной работе мы рассматриваем устойчивую по размеру проблему множественного ранца — задачу с несколькими ранцами и набором возможных возмущений.

  • Для каждого возмущения, или сценария, мы знаем вероятность его возникновения и результирующее уменьшение размеров рюкзаков.
  • Для борьбы с этими возмущениями мы используем восстанавливаемую устойчивость.

Восстанавливаемая устойчивость требует, чтобы мы нашли решение, которое выполнимо для случая без нарушений, в то время как в случае с нарушениями, мы можем скорректировать решение с помощью простого алгоритма восстановления, который в нашем случае заключается в удалении элементов из соответствующего ранца.

Наша цель — найти решение, при котором ожидаемый доход будет максимальным. Для решения этой задачи мы используем метод ветвей и цен.

Мы представляем и сравниваем два подхода к решению:

  • раздельное разложение восстановления (SRD)
  • и комбинированное разложение восстановления (CRD).

Мы доказываем, что LP-релаксация модели CRD сильнее, чем LP-релаксация модели SRD.

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

проблемы.

…»



«

Квадратичная задача о множественном рюкзаке (QMKP) — сложная задача комбинаторной оптимизации с многочисленными приложениями.

В этой статье мы предлагаем первый эволюционный подход к повторному связыванию путей (EPR) для приближенного решения QMKP.

Этот подход сочетает в себе расширенные функции как из пути метод повторного связывания (PR) и алгоритм поиска чувствительного порога.

Благодаря свойству туннелирования, которое позволяет контролируемое исследование недопустимых областей, предложенный алгоритм EPR может идентифицировать очень качественные решения.

Экспериментальные исследования набора из 60 хорошо известных тестов и нового набора из 30 экземпляров большого размера показывают, что EPR превосходит несколько современных алгоритмов.

В частности, он обнаруживает 10 улучшенных результатов (новые нижние границы) и соответствует наиболее известному результату для оставшихся 50 случаев.

Что еще более важно, EPR демонстрирует замечательную эффективность на 30 новых более крупных инстансах, легко опережая текущие наиболее эффективные алгоритмы во всем мире.

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

…»



«

Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях.

Сначала пытаемся выбрать среди определенных доступных узлов в сети, а затем, адаптивно, среди соседей этих узлов, когда они становятся доступными, чтобы максимизировать влияние на всю сеть.

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

Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию

вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы.

В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют узлы с разнородной стоимостью активации.

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

Затем мы дополняем это примерно применимость с приближением постоянного множителя для общих субмодулярных функций, показывающая, что трудности, вызванные стохастической природой проблемы, могут быть преодолены.

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

…»


[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.