• Целочисленная оптимизация

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

Эти переменные могут возникать несколькими способами:

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

  • Логические переменные , которые представляют решения со значениями 0–1.
    В качестве примера рассмотрим проблему, связанную с назначением работников на задачи (см. «Назначение »). Чтобы создать задачу такого типа, вы можете определить логические переменные x i,j , которые равны 1, если работник i назначен на задачу j , и 0 в противном случае.

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

Инструменты

Google предлагает несколько способов решения проблем MIP :

  • MPsolver : оболочка для нескольких сторонних решателей MIP, которые используют стандартные методы ветвей и границ.
  • Решатель CP-SAT : решатель программирования ограничений , использующий методы SAT (выполнимости).
  • Оригинальный решатель CP : решатель программирования в ограничениях .

Какой решатель мне следует использовать?

Не существует жесткого правила для принятия решения о том, использовать ли решатель MIP или решатель CP-SAT. В качестве приблизительного руководства:

  • Решатели MIP лучше подходят для задач, которые можно настроить как стандартный LP, но с произвольными целочисленными переменными, как в первом примере выше.
  • Решатель CP-SAT лучше подходит для задач, в которых большинство переменных являются логическими, как во втором примере выше.

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

Примеры, в которых используются решатели MIP и CP-SAT, см. в разделе «Решение задачи о назначениях» и других разделах о заданиях.

Другой способ решения задач целочисленного программирования — использование решателя сетевых потоков .
Пример см. в разделе «Назначение как задача минимального потока затрат ».
Для задачи, которая может быть настроена как сетевой поток, решатель потока минимальной стоимости может работать быстрее, чем решатели MIP или CP-SAT. Однако не все MIP можно настроить таким образом.