Поиск оптимальных решений с помощью метода ветвей и границ

Поиск оптимальных решений методом ветвей и границ

Робокот и кошка играют вместе. Изображение создано автором с помощью Dall·E.

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

«Разделяй и властвуй» (англ. «Branch and bound») – это основной алгоритм, стоящий за многими решателями задач смешанного целочисленного программирования (MIP). Он является отличным дополнением к вашему математическому инструментарию оптимизации, особенно полезным для меньших задач или когда у проблемы множество ограничений. Более того, его простота позволяет легко понять и использовать без необходимости в тяжелых математических формулах.

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

Постановка задачи

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

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

Давайте рассмотрим пример. Представьте, что 3 кошки запросили размещение в вашем приюте. Их зовут Лили, Чарли и Мяустер. Как мы можем разделить этих трех кошек на разные комнаты? Нам понадобится не более трех комнат, и вот все возможные варианты разделения кошек:

Группировки кошек. Изображение создано автором.

Группировки и числа Белла

Как видите, существует 5 возможных способов группировки 3 кошек. В математике термином, обозначающим один из способов группировки элементов множества, является партития. Число Белла соответствует общему количеству…