knapsack

Рюкзак

Задача о рюкзаке — хорошо известная оптимизационная задача. Встречается, например, при упаковке морских контейнеров. Транспортный контейнер имеет грузоподъемность, которую он может выдержать. Учитывая набор предметов, подлежащих отправке, где каждый предмет имеет стоимость и вес, проблема состоит в том, чтобы выбрать оптимальные предметы для упаковки в транспортный контейнер. Эту задачу оптимизации можно определить как цель с ограничением:

• Цель: максимизировать стоимость фрахта (сумму стоимостей выбранных товаров).
• Ограничение: общий вес груза (сумма весов выбранных предметов) должен быть меньше или равен вместимости контейнера.

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

Использование

Чтобы запустить демо-версию по умолчанию, введите команду:

python knapsack.py

Чтобы просмотреть доступные параметры, введите команду:

python knapsack.py --help

Аргументы командной строки позволяют выбрать один из нескольких наборов данных (в папке /data ) и установить грузоподъемность. Файлы данных представляют собой строки элементов, каждый из которых определяется как пара веса и стоимости.

Обзор кода

Код в knapsack.py включает три основные функции:

• build_knapsack_cqm() создает CQM, устанавливая цель и ограничение следующим образом:

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

• parse_inputs() — это служебная функция, которая считывает данные из файлов примеров.

• parse_solution() анализирует и отображает результаты, полученные решателем.

Лицензия

Выпущено по лицензии Apache 2.0. См. файл ЛИЦЕНЗИИ.