Branch and Bound – Введение перед написанием алгоритма с нуля

Branch and Bound - Введение к написанию алгоритма

Введение в целочисленные задачи и один из способов их решения

Введение

Фото от Possessed Photography на Unsplash

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

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

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

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

Я буду использовать примеры из книги “Методы оптимизации в финансах” Корнуэйолса и Тютюнджулу, но дополню их собственными интуитивными объяснениями и, конечно же, реализацией таких алгоритмов на языке Python.

Алгоритм ветвей и границ

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

Это много информации, но будет проще с примером.

Задача 0: Исходная целочисленная задача

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

Шаг 1 – Релаксация линейного программирования