Введение

Проблема математической оптимизации, ограниченная целыми числами. Проблема целочисленного программирования — это задача математической оптимизации или задача на допустимость, в которой некоторые или все переменные должны принимать целочисленные значения. Во многих контекстах под этим термином подразумевают целочисленное линейное программирование (ILP), в котором целевая функция и ограничения (за исключением целочисленных ограничений) являются линейными. Целочисленное программирование является NP-полной задачей. В частности, частный случай 0–1 целочисленного линейного программирования, в котором неизвестные принимают только бинарные значения, и требуется лишь выполнение ограничений, входит в список из 21 NP-полной задачи Карпа. Если некоторые переменные решения не являются дискретными, то задача называется задачей смешанного целочисленного программирования.

Пример

График справа иллюстрирует следующую задачу. Допустимые целочисленные точки показаны красным цветом, а красные пунктирные линии обозначают их выпуклую оболочку – наименьший выпуклый многогранник, содержащий все эти точки. Синие линии вместе с координатными осями определяют многогранник LP-релаксации, заданный неравенствами без требования целочисленности. Цель оптимизации состоит в том, чтобы переместить чёрную пунктирную линию максимально вверх, сохраняя при этом касание с многогранником. Оптимальными решениями целочисленной задачи являются точки и , обе имеющие значение целевой функции равное 2. Единственный оптимум релаксации – с значением целевой функции 2.8. Если решение релаксации округлить до ближайших целых чисел, оно не будет допустимым для ILP.

Доказательство NP-жесткости

Ниже приведено сведение задачи о минимальном вершинном покрытии к задаче целочисленного программирования, которое послужит доказательством NP-трудности. Пусть G – неориентированный граф. Определим линейную программу следующим образом:

Учитывая, что ограничения ограничивают значения переменных xᵢ либо 0, либо 1, любое допустимое решение задачи целочисленного программирования является подмножеством вершин. Первое ограничение гарантирует, что в это подмножество включена хотя бы одна конечная точка каждого ребра. Следовательно, решение описывает вершинное покрытие. Кроме того, для любого вершинного покрытия C, можно присвоить xᵢ = 1 для всех вершин i ∈ C и xᵢ = 0 для всех вершин i ∉ C, тем самым получив допустимое решение задачи целочисленного программирования. Таким образом, мы можем заключить, что минимизируя сумму xᵢ, мы также находим минимальное вершинное покрытие.

Варианты

Смешанное целочисленное линейное программирование (MILP) включает задачи, в которых лишь некоторые переменные, , должны быть целыми, а остальные переменные могут быть нецелыми. Линейное программирование 0–1 (или бинарное целочисленное программирование) включает задачи, в которых переменные могут принимать только значения 0 или 1. Любую ограниченную целочисленную переменную можно представить в виде комбинации бинарных переменных. Например, для заданной целочисленной переменной , эту переменную можно выразить, используя бинарных переменных:

Планирование производства

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

Расписание

Эти проблемы связаны с планированием работы транспорта и составлением расписаний в транспортных сетях. Например, задача может заключаться в назначении автобусов или поездов метро на отдельные маршруты для соблюдения расписания, а также в обеспечении их водителями. В данном случае бинарные переменные решения указывают, назначен ли автобус или поезд метро на маршрут, и назначен ли водитель на конкретный поезд или состав метро. Метод целочисленного программирования с ограничениями 0-1 успешно применяется для решения задачи выбора проектов, которые являются взаимоисключающими и/или технологически зависимыми. Он используется в особом случае целочисленного программирования, где все переменные решения являются целыми числами. Переменная может принимать только значения ноль или один.

Территориальное разделение

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

Сети телекоммуникаций

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

Сотовые сети

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

Алгоритмы

Наивный способ решения задачи целочисленного линейного программирования (ILP) — просто отменить требование, что x должно быть целым числом, решить соответствующую задачу линейного программирования (LP), называемую LP-релаксацией ILP, а затем округлить значения в полученном решении. Однако это решение может быть не только неоптимальным, но и даже недопустимым, то есть оно может нарушать некоторые ограничения.

Точные алгоритмы

Когда матрица не является полностью унимодулярной, существует множество алгоритмов, которые могут быть использованы для точного решения задач целочисленного линейного программирования. Один из классов алгоритмов – методы разделяющих плоскостей, которые работают путем решения LP-релаксации и последующего добавления линейных ограничений, направляющих решение к целочисленности, не исключая при этом ни одной допустимой целочисленной точки. Другой класс алгоритмов – варианты метода ветвей и границ. Например, метод ветвей и отсечений, который объединяет метод ветвей и границ и методы разделяющих плоскостей. Алгоритмы ветвей и границ имеют ряд преимуществ перед алгоритмами, использующими только разделяющие плоскости. Одно из преимуществ заключается в том, что алгоритмы могут быть остановлены преждевременно, и, если найдено хотя бы одно целочисленное решение, может быть возвращено допустимое, хотя и не обязательно оптимальное, решение. Кроме того, решения LP-релаксаций могут быть использованы для получения пессимистичной оценки расстояния до оптимальности возвращаемого решения. Наконец, методы ветвей и границ могут быть использованы для возврата нескольких оптимальных решений.

Точные алгоритмы для небольшого количества переменных

Предположим, что – это целочисленная матрица размера m на n, а – целочисленный вектор размера m на 1. Мы сосредоточимся на задаче осуществимости, которая заключается в определении того, существует ли вектор размера n на 1, удовлетворяющий условию. Пусть V – максимальное абсолютное значение коэффициентов в матрице . Если n (количество переменных) является фиксированной константой, то задача осуществимости может быть решена за время, полиномиальное относительно m и log V. Это тривиально для случая n=1. Случай n=2 был решен в 1981 году Гербертом Шарфом. Общий случай был решен в 1983 году Хендриком Ленстрой, объединив идеи Ласло Ловаса и Питера ван Эмде Боаса. Теорема Дойона утверждает, что целочисленная программа осуществима, если осуществимо каждое подмножество ограничений; метод, объединяющий этот результат с алгоритмами для задач линейного программирования, может быть использован для решения целочисленных программ за время, линейное относительно и фиксированных параметров, обрабатываемое (но, возможно, двойственно экспоненциальное) относительно , без зависимости от .

В специальном случае 0-1 ILP алгоритм Ленстры эквивалентен полному перечислению: число всех возможных решений фиксировано (2n), и проверка осуществимости каждого решения может быть выполнена за время poly(m, log V). В общем случае, когда каждая переменная может быть произвольным целым числом, полное перечисление невозможно. Здесь алгоритм Ленстры использует идеи из геометрии чисел. Он преобразует исходную задачу в эквивалентную, обладающую следующим свойством: либо существование решения очевидно, либо значение (n-й переменной) принадлежит интервалу, длина которого ограничена функцией от n. В последнем случае задача сводится к конечному числу задач меньшей размерности. Временная сложность алгоритма была улучшена в несколько этапов:

Оригинальный алгоритм Ленстры представил улучшенный алгоритм с временем выполнения . Франк и Тардос представили улучшенный алгоритм с временем выполнения . Дадуш представил улучшенный алгоритм с временем выполнения . Рейс и Ротвосс представили улучшенный алгоритм с временем выполнения .

Программа с рассеянными целыми числами

Часто бывает, что матрица, определяющая задачу целочисленного программирования, является разреженной. В частности, это происходит, когда матрица имеет блочную структуру, что часто встречается в различных приложениях. Разреженность матрицы можно измерить следующим образом. Граф имеет вершины, соответствующие столбцам матрицы , и две колонки соединены ребром, если существует строка, в которой обе колонки имеют ненулевые элементы. Эквивалентно, вершины соответствуют переменным, и две переменные соединены ребром, если они участвуют в одном и том же неравенстве. Мера разреженности матрицы обозначается как минимум глубины дерева графа и глубины дерева графа транспонированной матрицы . Пусть – числовая мера матрицы , определяемая как максимальное по модулю значение любого её элемента. Пусть – количество переменных в задаче целочисленного программирования. Тогда в 2018 году было показано, что задача целочисленного программирования может быть решена за сильно полиномиальное время и является параметрически разрешимой относительно параметров и . То есть, существуют вычислимая функция и константа , такие что задача целочисленного программирования может быть решена за время . В частности, это время не зависит от правой части и целевой функции. Кроме того, в отличие от классического результата Ленстры, где количество переменных является параметром, здесь количество переменных является переменной частью входных данных.