Целочисленное программирование - Integer programming

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

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

Если некоторые переменные решения не являются дискретными, проблема известна как задача смешанного целочисленного программирования .

Каноническая и стандартная форма для ILP

В целочисленном линейном программировании каноническая форма отличается от стандартной формы . Целочисленная линейная программа в канонической форме выражается таким образом (обратите внимание, что это вектор, который должен быть определен):

а ПДОДИ в стандартной форме выражается как

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

Пример

Многогранник IP с LP релаксацией

На графике справа показана следующая проблема.

Допустимые целые точки показаны красным цветом, а красные пунктирные линии обозначают их выпуклую оболочку, которая является наименьшим выпуклым многогранником, содержащим все эти точки. Синие линии вместе с осями координат определяют многогранник релаксации ЛП, который задается неравенствами без ограничения целочисленности. Цель оптимизации - переместить черную пунктирную линию как можно дальше вверх, все еще касаясь многогранника. Оптимальные решения целочисленной задачи являются точками и которые оба имеют объективное значение 2. Уникальный оптимум релаксации с объективным значением 2,8. Если решение ослабления округляется до ближайших целых чисел, это невозможно для ILP.

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

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

Позвольте быть неориентированным графом. Определите линейную программу следующим образом:

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

Варианты

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

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

Приложения

Есть две основные причины использования целочисленных переменных при моделировании задач в виде линейной программы:

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

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

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

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

Планирование

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

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

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

Телекоммуникационные сети

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

Сотовые сети

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

Другие приложения

Алгоритмы

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

Использование полной унимодулярности

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

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

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

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

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

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

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

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

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

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

Алгоритм Ленстры подразумевает, что ILP полиномиально разрешима также в двойственном случае, когда n меняется, но m (количество ограничений) постоянно.

Впоследствии алгоритм Ленстры был улучшен Каннаном, Фрэнком и Тардосом. Улучшенная среда выполнения:, где - количество входных битов, в .

Эвристические методы

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

К другим эвристическим методам, которые можно применить к ПДОДИ, относятся:

Существует также множество других эвристических методов для конкретных задач, таких как эвристика k-opt для задачи коммивояжера. Недостатком эвристических методов является то, что, если они не могут найти решение, невозможно определить, является ли это причиной отсутствия допустимого решения или алгоритм просто не смог его найти. Кроме того, обычно невозможно количественно оценить, насколько близко к оптимальному решение, возвращаемое этими методами.

Разреженное целочисленное программирование

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

Смотрите также

Рекомендации

дальнейшее чтение

  • Джордж Л. Немхаузер ; Лоуренс А. Вулси (1988). Целочисленная и комбинаторная оптимизация . Вайли. ISBN 978-0-471-82819-8.
  • Александр Шрайвер (1998). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. ISBN 978-0-471-98232-6.
  • Лоуренс А. Вулси (1998). Целочисленное программирование . Вайли. ISBN 978-0-471-28366-9.
  • Димитрис Берцимас; Роберт Вайсмантель (2005). Оптимизация по целым числам . Динамические идеи. ISBN 978-0-9759146-2-5.
  • Джон К. Карлоф (2006). Целочисленное программирование: теория и практика . CRC Press. ISBN 978-0-8493-1914-3.
  • Х. Пол Уильямс (2009). Логическое и целочисленное программирование . Springer. ISBN 978-0-387-92279-9.
  • Михаэль Юнгер; Томас М. Либлинг; Денис Наддеф; Джордж Немхаузер ; Уильям Р. Пуллибланк ; Герхард Райнельт; Джованни Ринальди; Лоуренс А. Вулси, ред. (2009). 50 лет целочисленного программирования 1958-2008: от первых лет до современного состояния . Springer. ISBN 978-3-540-68274-5.
  • Дер-Сан Чен; Роберт Дж. Батсон; Ю Данг (2010). Прикладное целочисленное программирование: моделирование и решение . Джон Уайли и сыновья. ISBN 978-0-470-37306-4.
  • Жерар Сирксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . CRC Press. ISBN 978-1-498-71016-9.

Внешние ссылки