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

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

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

Пример

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

Переменные

Один из способов решить эту задачу — использовать 9 переменных, по одной для каждой комбинации работника и задания. Переменная x_ad получит значение 1, если Энн должна Даст в оптимальном решении, и 0 в противном случае; x_bp получит значение 1, если Билл должен упаковать оптимальное решение, и 0 в противном случае; и так далее.

Целевая функция

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

Ограничения

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

Чтобы убедиться, что Анна выполняет ровно 1 задание, мы можем добавить ограничение x_ad + x_at + x_ap = 1. Аналогичные ограничения можно добавить для Билла и Карла.

Чтобы удостовериться, что только 1 человек пылит, мы можем добавить ограничение, что x_ad + x_bd + x_cd = 1. Аналогичные ограничения можно добавить для типизации и упаковки.

Всего 6 ограничений. Теперь вы можете передать эту задачу с 9 переменными и 6 ограничениями решателю ILP, и он выдаст значения переменных в одном из оптимальных решений — ровно 3 из них будут равны 1, а остальные — 0. 3, равные 1, говорят вам, какие люди должны выполнять какую работу!

ILP является общим

Как оказалось, эта конкретная проблема имеет особую структуру, которая позволяет решать ее более эффективно с помощью другой алгоритм. Преимущество использования ILP заключается в том, что можно легко включить различные варианты задачи: например, если бы на самом деле было 4 человека и только 3 работы, нам нужно было бы ослабить ограничения, чтобы каждый человек делал максимум 1 задание, а не ровно 1 задание. Это можно выразить, просто изменив знак равенства в каждом из первых трех ограничений на знак «меньше или равно».

Во-первых, прочитайте пример линейного программирования из Википедии

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

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

Пользователь SO flolo говорит: Случаи использования, в которых я часто встречался: в проектировании цифровых схем у вас есть объекты, которые нужно разместить / отобразить на определенные части микросхемы (размещение FPGA) - это можно сделать с помощью ILP. Также в кодировке HW-SW часто возникает проблема разделения: какая часть программы должна по-прежнему работать на процессоре, а какая часть должна быть ускорена на аппаратном уровне. Это также может быть решено с помощью ILP.

Пример проблемы ILP будет выглядеть примерно так:

• развернуть 37∙x1 + 45∙x2

куда

• x1,x2,... должны быть целыми положительными числами

...но есть набор ограничений в форме

• a1∙x1+b1∙x2 < k1
• a2∙x1+b2∙x2 < k2
• a3∙x1+b3∙x2 < k3
• ...

Теперь более простая формулировка примера из Википедии:

• У фермера есть L м² земли, которую можно засеять пшеницей, ячменем или их комбинацией.
• У фермера есть F граммов удобрений и P граммов инсектицидов.
• На каждый м² пшеницы требуется F1 грамм удобрений и P1 грамм инсектицидов.
• На каждый м² ячменя требуется F2 грамма удобрения и P2 грамма инсектицида.

В настоящее время,

• Пусть a1 обозначает продажную цену пшеницы за 1 м².
• Пусть a2 обозначает продажную цену ячменя за 1 м².
• Пусть x1 обозначает площадь земли, которая будет засеяна пшеницей.
• Пусть x2 обозначает площадь земли, которую нужно засеять ячменем.
• x1,x2 — положительные целые числа (предположим, что мы можем посадить растения с разрешением 1 м²).

So,

• прибыль составляет a1∙x1 + a2∙x2 — мы хотим ее максимизировать
• Поскольку у фермера ограниченный участок земли: x1+x2‹=L
• Поскольку у фермера ограниченное количество удобрений: F1∙x1+F2∙x2 ‹ F
• Поскольку у фермера ограниченное количество инсектицида: P1∙x1+P2∙x2 ‹ P

a1,a2,L,F1,F2,F,P1,P2,P — константы (в нашем примере: положительные).

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

Надеюсь понятно...

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

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

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

Однако действительно интересно то, что на самом деле большое количество комбинаторных задач сводится к LP. Одна из моих любимых задач — задача о назначениях.

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

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

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

Вы можете легко применять линейную программу везде, где хотите оптимизировать, и целевая функция является линейной. Вы можете составлять расписания (я имею в виду большие, например, железнодорожные компании, которым нужно оптимизировать использование транспортных средств и путей), производство (оптимизировать выигрыш), почти все. Иногда бывает сложно сформулировать вашу проблему как ИС, и/или иногда вы сталкиваетесь с проблемой, которая заключается в вашем решении, которое вы должны создать, например. 0,345 машины для оптимальной победы. Это, конечно, невозможно, и поэтому вы ограничиваете себя еще больше: ваша переменная для количества автомобилей должна быть целочисленной. Даже если сейчас это звучит проще (потому что у вас бесконечно меньше вариантов для вашей переменной), на самом деле это сложнее. В этот момент он становится NP-сложным. Что на самом деле означает, что вы можете решить ЛЮБУЮ проблему с вашего компьютера с помощью ILP, вам просто нужно преобразовать его.

Для вас я бы порекомендовал введение в чтение некоторых основных материалов (I)LP. На мой взгляд, я не знаю ни одного хорошего онлайн-сайта (но если вы погуглите, вы найдете его), в качестве книги я могу порекомендовать Linear Programming от Chvatal. В нем есть очень хорошие примеры, а также описаны реальные варианты использования.

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

1. журнал Interfaces, издаваемый INFORMS (Институт исследования операций и управленческих наук)
2. лауреаты премии Франца Эдельмана за достижения в области исследования операций и управленческих наук

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