Смешано-целочисленные алгоритмы линейного программирования

Определение смешано-целочисленного линейного программирования

Смешано-целочисленная линейная программа (MILP) является проблемой

Линейная целевая функция, f^Tx, где f является вектором-столбцом констант, и x является вектором-столбцом неизвестных
Ограничения и линейные ограничения, но без нелинейных ограничений (для определений см. «Ограничения записи»)
Ограничения для некоторых компонентов x иметь целочисленные значения

В математических терминах заданные векторы f, lb и ub, матрицы A и Aeq, соответствующие векторы b и beq и набор индексов intcon, найти вектор x для решения

$\min_{x} f^{T} x при условии , что {\begin{array}{l} x (intcon) являются целыми числами \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

Алгоритм intlinprog

Обзор алгоритма
Предварительная обработка линейной программы
Линейное программирование
Предварительная обработка смешано-целочисленной программы
Генерация резов
Эвристика для нахождения возможных решений
Ветвь и граница

Обзор алгоритма

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

Уменьшите размер задачи с помощью Linear Program Precessing.
Решите начальную расслабленную (нецелое) задачу, используя Linear Programming.
Выполните Mixed-Integer Program Preprocessing, чтобы затянуть релаксацию LP смешано-целочисленной задачи.
Попробуйте Cut Generation, чтобы еще больше ужесточить ослабление LP смешано-целочисленной задачи.
Попытайтесь найти целочисленно-допустимые решения с помощью эвристики.
Используйте алгоритм Branch и Bound для систематического поиска оптимального решения. Этот алгоритм решает релаксации LP с ограниченными областями значений возможных значений целочисленных переменных. Он пытается сгенерировать последовательность обновленных границ оптимального значения целевой функции.

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

Согласно Определению Смешано-Целочисленного Линейного Программирования, существуют матрицы A и Aeq и соответствующие векторы b и beq, которые кодируют набор линейных неравенств и линейных равенств

$\begin{matrix} A \cdot x \leq b \\ A e q \cdot x = b e q . \end{matrix}$

Эти линейные ограничения ограничивают x решения.

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

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

Для получения дополнительной информации смотрите Андерсена и Андерсена [2] и Mészáros и Suhl [8].

Линейное программирование

Начальной relaxed задачей является задача линейного программирования с той же целью и ограничениями, что и Определение Смешано-Целого Линейного Программирования, но без целочисленных ограничений. Вызовите x _НД решение расслабленной задачи и x решение исходной задачи с целочисленными ограничениями. Ясно,

f^Tx ≤ НД f^Tx,

потому что x _LP минимизирует ту же функцию, но с меньшим количеством ограничений.

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

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

Во время смешано-целочисленной предварительной обработки программы, intlinprog анализирует линейное неравенство A*x ≤ b наряду с ограничениями целостности для определения:

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

The IntegerPreprocess опция позволяет вам выбрать, будет ли intlinprog делает несколько шагов, делает все или почти ни один из них. Если вы включаете x0 аргумент, intlinprog использует это значение в предварительной обработке.

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

Для получения дополнительной информации о целочисленной предварительной обработке смотрите Savelsbergh [10].

Генерация резов

Разрезы являются дополнительными линейными ограничениями неравенства, которые intlinprog добавляет к задаче. Эти неравенства пытаются ограничить допустимую область релаксаций LP, чтобы их решения были ближе к целым числам. Вы управляете типом вырезов, которые intlinprog использует с CutGeneration опция.

'basic' вырезы включают:

Смешано-целочисленные округления
Гоморские порезы
Кликовые разрезы
Порезы крышек
Порезы крышки потока

Кроме того, если задача является чисто целым числом (все переменные имеют целочисленное значение), то intlinprog также использует следующие вырезы:

Сильные шватало-гоморские разрезы
Нулевые полуразрезы

'intermediate' вырезы включают все 'basic' вырезы, плюс:

Простые подъемно-проектные сокращения
Простые поворотно-редуцированные вырезы
Сокращение-и-разделение вырезов

'advanced' вырезы включают все 'intermediate' вырезы, за исключением сокращенных и разделенных вырезов, плюс:

Сильные шватало-гоморские разрезы
Нулевые полуразрезы

Для чисто целочисленных задач, 'intermediate' использует большинство типов вырезов, потому что использует сокращения и разделения, в то время как 'advanced' не делает.

Другая опция, CutMaxIterations, задает верхнюю границу от количества раз intlinprog итерация для генерации вырезов.

Для получения дополнительной информации об алгоритмах генерации резов (также называемых методами секущей плоскости), см. Cornuéjols [5] и, для кликовых разрезов, Atamtürk, Nemhauser и Savelsbergh [3].

Эвристика для нахождения возможных решений

Чтобы получить верхнюю границу целевой функции, процедура branch-and-bound должна найти допустимые точки. Решение релаксации LP во время ветви и связи может быть целочисленным допустимым, что может обеспечить улучшенную верхнюю границу исходного MILP. Некоторые методы находят допустимые точки быстрее до или во время ветви и связи. intlinprog использует эти методы в корневом узле и во время некоторых итераций, связанных между собой. Эти методы эвристичны, что означает, что они являются алгоритмами, которые могут быть успешными, но могут также неудачными.

Эвристика может быть start эвристикой, которая помогает решателю найти начальное или новое целочисленно-допустимое решение. Или эвристика может быть improvement эвристикой, которая начинается с целочисленно-допустимой точки и пытается найти лучшую целочисленно-допустимую точку, означающую точку с более низким значением целевой функции. intlinprog улучшением эвристики являются 'rins', 'rss', 1-опт, 2-опт, и направленное погружение.

Установите intlinprog эвристика с использованием 'Heuristics' опция. Опции:

Опция	Описание
`'basic'` (по умолчанию)	Решатель дважды запускает округление эвристики с различными параметрами, дважды запускает дайвинг-эвристику с различными параметрами, затем запускает `'rss'`. Решатель не запускает более позднюю эвристику, когда более ранняя эвристика приводит к достаточно хорошему целочисленно-допустимому решению.
`'intermediate'`	Решатель дважды запускает округление эвристики с различными параметрами, затем дважды запускает дайвинг-эвристику с различными параметрами. Если существует целочисленно-допустимое решение, решатель затем запускает `'rins'` далее следуют `'rss'`. Если `'rss'` находит новое решение, решатель запускается `'rins'` снова. Решатель не запускает более позднюю эвристику, когда более ранняя эвристика приводит к достаточно хорошему целочисленно-допустимому решению.
`'advanced'`	Решатель дважды запускает округление эвристики с различными параметрами, затем дважды запускает дайвинг-эвристику с различными параметрами. Если существует целочисленно-допустимое решение, решатель затем запускает `'rins'` далее следуют `'rss'`. Если `'rss'` находит новое решение, решатель запускается `'rins'` снова. Решатель не запускает более позднюю эвристику, когда более ранняя эвристика приводит к достаточно хорошему целочисленно-допустимому решению.
`'rins'` или эквивалентное `'rins-diving'`	`intlinprog` ищет окрестность текущей, наилучшей целочисленной допустимой точки решения (если она доступна), чтобы найти новое и лучшее решение. Видите Данну, Ротберга и Ле Папе [6]. Когда вы выбираете `'rins'`решатель дважды запускает округление эвристики с различными параметрами, дважды запускает дайвинг-эвристику с различными параметрами, затем запускает `'rins'`.
`'rss'` или эквивалентное `'rss-diving'`	`intlinprog` применяет гибридную процедуру, объединяющую идеи из `'rins'` и локальное ответвление для поиска целочисленно-допустимых решений. Когда вы выбираете `'rss'`решатель дважды запускает округление эвристики с различными параметрами, дважды запускает дайвинг-эвристику с различными параметрами, затем запускает `'rss'`. Решатель не запускает более позднюю эвристику, когда более ранняя эвристика приводит к достаточно хорошему целочисленно-допустимому решению. Эти настройки выполняют ту же эвристику, что и `'basic'`.
`'round'`	`intlinprog` принимает решение LP для расслабленной задачи в узле и округляет целочисленные компоненты таким образом, чтобы попытаться сохранить допустимость. Когда вы выбираете `'round'`решатель в корневом узле дважды запускает округление эвристики с различными параметрами, затем дважды запускает дайвинг-эвристику с различными параметрами. После этого решатель запускает только округление эвристики в некоторых узлах с ветвями и связями.
`'round-diving'`	Решатель работает аналогично `'round'`, но также запускает дайвинг-эвристику (в дополнение к округлению эвристики) в некоторых узлах, связанных ветвями, а не только в корневом узле.
`'diving'`	`intlinprog` использует эвристику, которая подобна шагам ветвей и связей, но следует только за одной ветвью дерева вниз, не создавая других ветвей. Эта единственная ветвь приводит к быстрому «нырянию» вниз по фрагменту дерева, таким образом имя «дайвинг». В настоящее время, `intlinprog` использует шесть дайвинг эвристику в этом порядке: Погружение в длину вектора Погружение коэффициентов Дробное погружение Псевдозатраты на дайвинг Line search diving Управляемое погружение (применяется, когда решатель уже нашел хотя бы одну целочисленно-допустимую точку) Эвристика погружения обычно выбирает одну переменную, которая должна быть целочисленной, для которой текущее решение дробное. Затем эвристика вводит границу, которая заставляет переменную быть целочисленной, и снова решает связанную расслабленную LP. Метод выбора переменной, которая будет связана, является основным различием эвристики погружения. См. Berthold [4], раздел 3.1.
`'none'`	`intlinprog` не выполняет поиск допустимой точки. Решатель просто принимает любую допустимую точку, с которой он сталкивается в своем поиске «ветвь и граница».

Основное различие между 'intermediate' и 'advanced' является ли это 'advanced' более часто запускает эвристику во время итераций ветвей и связей.

В дополнение к предыдущей таблице следующая эвристика выполняется при Heuristics опция 'basic', 'intermediate', или 'advanced'.

ZI round - Эта эвристика запускается всякий раз, когда алгоритм решает расслабленную LP. Эвристика проходит через каждую дробную целую переменную, чтобы попытаться переложить ее на соседнее целое число, не влияя на допустимость относительно других ограничений. Для получения дополнительной информации см. Hendel [7].
1-opt - Эта эвристическая система запускается каждый раз, когда алгоритм находит новое целочисленно-допустимое решение. Эвристика проходит через каждую целочисленную переменную, чтобы попытаться переложить ее на соседнее целое число, не влияя на допустимость относительно других ограничений, при этом понижая значение целевой функции.
2-opt - Эта эвристическая система запускается каждый раз, когда алгоритм находит новое целочисленно-допустимое решение. 2-opt находит все пары целочисленных переменных, которые влияют на одно и то же ограничение, что означает, что они имеют ненулевые значения в одной строке A или Aeq матрица ограничений. Для каждой пары 2-opt принимает целочисленно допустимое решение и перемещает значения пар переменных вверх или вниз, используя все четыре возможных хода (вверх, вверх-вниз, вниз-вниз и вниз), ища допустимое соседнее решение, которое имеет лучшее значение целевой функции. Алгоритм проверяет каждое целое число переменных, вычисляя самый большой размер (ту же величину) сдвигов для каждой переменной в паре, которая удовлетворяет ограничениям, а также улучшает значение целевой функции.

В начале фазы эвристики, intlinprog запускает trivial эвристику, если Heuristics является 'none' или вы обеспечиваете начальную целочисленную допустимую точку в x0 аргумент. Тривиальный эвристический проверяет следующие точки на допустимость:

Все нули
Верхняя граница
Нижняя граница (если ненулевая)
Точка «Блокировка»

Точка «lock» задается только для задач с конечными верхней и нижней границами для всех переменных. Точка «блокировки» для каждой переменной является ее верхней или нижней границей, выбранной следующим образом. Для каждой переменной j, подсчитайте количество соответствующих положительных записей в линейной матрице ограничений A(:,j) и вычесть число, соответствующее отрицательным значениям. Если результат положительный, используйте нижнюю границу для этой переменной, lb(j). В противном случае используйте верхнюю границу для этой переменной, ub(j). Точка «блокировки» пытается удовлетворить наибольшему числу линейных ограничений неравенства для каждой переменной, но не обязательно является допустимой.

После того, как каждый эвристический завершает с возможным решением, intlinprog вызывает выходные функции и функции построения графика. См. «Синтаксис выходной функции intlinprog и функции построения графика».

Если вы включаете x0 аргумент, intlinprog использует это значение в 'rins' и управляемую эвристику погружения, пока она не найдет лучшую целочисленно-допустимую точку. Так что, когда вы предоставляете x0, вы можете получить хорошие результаты путем установки 'Heuristics' опция для 'rins-diving' или другой параметр, который использует 'rins'.

Ветвь и граница

Метод branch-and-bound создает последовательность подпрограмм, которые пытаются сходиться к решению MILP. Подпрограммы дают последовательность верхних и нижних границ решения f^Tx. Первая верхняя граница является любым возможным решением, а первая нижняя граница является решением расслабленной задачи. Для обсуждения верхней границы смотрите Эвристику для нахождения возможных решений.

Как объяснено в Linear Programming, любое решение расслабленной задачи линейного программирования имеет более низкое значение целевой функции, чем решение MILP. Кроме того, любые допустимые ставки x точки удовлетворяют

f^Tx _feas ≥ f^Tx,

потому что f^Tx является минимумом среди всех допустимых точек.

В этом контексте node является LP с той же целевой функцией, границами и линейными ограничениями, что и исходная задача, но без целочисленных ограничений и с конкретными изменениями линейных ограничений или границ. root node является исходной задачей без целочисленных ограничений и без изменений линейных ограничений или границ, что означает, что корневой узел является исходным расслабленным LP.

Из начальных границ метод branch-and-bound создает новые подпроекты путем ветвления от корневого узла. Шаг ветвления делается эвристически, по одному из нескольких правил. Каждое правило основано на идее разделения задачи ограничением одной переменной меньше или равной целому числу J или больше или равны J + 1. Эти две подпрограммы возникают, когда запись в _x LP, соответствующая целому числу, заданному в intcon, не является целым числом. Здесь x LP является решением расслабленной задачи. Примите J как пол переменной (округлый вниз), и J + 1 как потолок (округлый вверх). Получившиеся две задачи имеют решения, которые больше или равны f^Tx _LP, потому что у них больше ограничений. Поэтому эта процедура потенциально увеличивает нижнюю границу.

Эффективность метода branch-and-bound зависит от правила выбора переменной, которую нужно разделить (правило ветвления). Алгоритм использует эти правила, которые можно задать в BranchRule опция:

'maxpscost' - Выберите дробную переменную с максимальными pseudocost.
Псевдостоимость
Псевдокост переменной i основан на эмпирических оценках изменения нижней границы, когда i была выбрана в качестве переменной ветвления, объединенной с дробной частью i компонента текущей точечной x. Дробная часть p состоит из двух частей, нижней части и верхней части:
_пи^– = x (<reservedrangesplaceholder2>) – <reservedrangesplaceholder1> (<reservedrangesplaceholder0>) ⌋
_пи⁺ = 1 - _pi^–.
Пусть _xi^– будьте решением линейной программы, ограниченной, чтобы иметь x (<reservedrangesplaceholder2>) <reservedrangesplaceholder1> (<reservedrangesplaceholder0>) ⌋ и позволить изменению в объективной функции быть обозначенным
_Δi^– = f^T_xi^– – f^Tx.
Точно так же,⁺ изменение в объективной функции, когда проблема ограничена, чтобы иметь x (<reservedrangesplaceholder2>) <reservedrangesplaceholder1> (<reservedrangesplaceholder0>) ⌉.
Целевой коэффициент усиления на модуль изменения переменной _xi
$d_{i}^{-} = \frac{Δ_{i}^{-}}{p_{i}^{-}} или d_{i}^{+} = \frac{Δ_{i}^{+}}{p_{i}^{+}} .$
Позвольте _си^– и _си⁺ быть эмпирическими средними показателями _di^– и _di⁺ во время алгоритма ветви и связи до этой точки. Эмпирические значения инициализируются в абсолютное значение целевого коэффициента f (i) для членов, прежде чем будут какие-либо наблюдения. Затем 'maxpscost' правило состоит в том, чтобы ветвить на узле i, который максимизирует, для некоторых положительных весов w⁺ и w^–, количество
w^– * _pi^– * _si^– + w⁺ * _pi⁺ * _si⁺.
Грубо говоря, это правило выбирает коэффициент, который, вероятно, увеличит нижнюю границу максимально.
'strongpscost' - Подобно 'maxpscost', но вместо псевдокоста, инициализируемого в 1 для каждой переменной решатель пытается ветвиться на переменной только после того, как псевдокост имеет более достоверную оценку. Чтобы получить более достоверную оценку, решатель делает следующее (см. Ахтерберг, Кох и Мартин [1]).
- Упорядочьте все потенциальные переменные ветвления (те, которые в настоящее время дробны, но должны быть целым числом) по их текущим основанным на псевдокосте счетам.
- Запустите две расслабленные линейные программы на основе текущей переменной ветвления, начиная с переменной с самым высоким счетом (если переменная еще не использовалась для вычисления ветвления). Решатель использует эти два решения, чтобы обновить псевдокосты для текущей переменной ветвления. Решатель может остановить этот процесс раньше, чтобы сэкономить время в выборе ветви.
- Продолжите выбор переменных в списке, пока текущая самая высокий счет не изменится для k последовательные переменные, где k является внутренне выбранным значением, обычно от 5 до 10.
- Ветвь на переменной с самым высоким основанным на псевдокосте счетом. Решатель, возможно, уже вычислял расслабленные линейные программы на основе этой переменной во время более ранней процедуры оценки псевдокоста.
Из-за дополнительных линейных программных решений каждая итерация 'strongpscost' ответвление занимает больше времени, чем по умолчанию 'maxpscost'. Однако количество итераций с ветвями и связями обычно уменьшается, поэтому 'strongpscost' метод может сэкономить время в целом.
'reliability' - Подобно 'strongpscost', но вместо запуска расслабленных линейных программ только для неинициализированных псевдокостовых ветвей, 'reliability' запускает программы до k2 время для каждой переменной, где k2 является маленьким целым числом, таким как 4 или 8. Поэтому 'reliability' имеет даже более медленное ответвление, но потенциально меньше итераций, связанных между собой, по сравнению с 'strongpscost'.
'mostfractional' - Выберите переменную с дробной деталью, ближайшей к 1/2.
'maxfun' - Выберите переменную с максимальным соответствующим абсолютным значением в целевом векторе f.

После ветвей алгоритма существует два новых узла, которые нужно исследовать. Алгоритм выбирает, какой узел исследовать среди всех, которые доступны, используя одно из следующих правил:

'minobj' - Выберите узел, который имеет самое низкое значение целевой функции.
'mininfeas' - Выберите узел с минимальной суммой целочисленных infeasibilities. Это означает, что для каждого недопустимого целочисленного компонента x (i) в узле, складывайте меньшее из _pi^– и _pi⁺, где
_пи^– = x (<reservedrangesplaceholder2>) – <reservedrangesplaceholder1> (<reservedrangesplaceholder0>) ⌋
_пи⁺ = 1 - _pi^–.
'simplebestproj' - Выберите узел с best projection.
Лучшая проекция
Позвольте _xB обозначить лучшую целочисленно-допустимую точку, найденную до сих пор, _xR понизить расслабленное решение LP в корневом узле и x обозначить узел, который мы исследуем. Пусть in (x) обозначают сумму целочисленных infeasibilities в узле x (см 'mininfeas'). Лучшим правилом проекции является минимизация
$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{i n (x_{R})} i n (x) .$
Если до сих пор не найдена целочисленно-допустимая точка, установите f^T_xB = 0.

intlinprog пропускает анализ некоторых подпроектов путем рассмотрения информации от исходной задачи, такой как наибольший общий делитель (GCD) целевой функции.

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

Алгоритм превышает MaxTime опция.
Различие между нижней и верхней границами целевой функции меньше, чем AbsoluteGapTolerance или RelativeGapTolerance допуски.
Количество исследованных узлов превышает MaxNodes опция.
Количество целого числа допустимых точек превышает MaxFeasiblePoints опция.

Для получения дополнительной информации о процедуре ветви и связи, см. Nemhauser and Wolsey [9] и Wolsey [11].

Ссылки

[1] Ахтерберг, Т., Т. Кох и А. Мартин. Пересмотрены правила ветвления. Operations Research Letters 33, 2005, pp. 42-54. Доступно в https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf.

[2] Андерсен, Э. Д., и Андерсен, К. Д. Пресольвинг в линейном программировании. Математическое программирование 71, стр. 221-245, 1995.

[3] Атамтюрк, А., Г. Л. Немхаузер, М. В. П. Савельсберг. Конфликтные графики в решении целочисленных задач программирования. Европейский журнал операционных исследований 121, 2000, с. 40-55.

[4] Бертольд, Т. Основная Эвристика для смешанных целочисленных программ. Technischen Universität Berlin, сентябрь 2006. Доступно в https://www.zib.de/groetschel/students/Diplom-Berthold.pdf.

[5] Cornuéjols, G. Валидное неравенство для смешанных целочисленных линейных программ. Математическое программирование B, том 112, стр. 3-44, 2008.

[6] Danna, E., Rothberg, E., Le Pape, C. Исследование релаксации побудило районы улучшить решения MIP. Математическое программирование, том 102, выпуск 1, стр. 71-90, 2005.

[7] Хендель, Г. Новая эвристика округления и распространения для смешанного целочисленного программирования. Бакалавриат в Technische Universität Berlin, 2011. PDF доступен в https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf.

[8] Mészáros C., and Suhl, U. H. Передовые методы предварительной обработки для линейного и квадратичного программирования. ОР Спектр, 25 (4), стр. 575-595, 2003.

[9] Немхаузер, Г. Л. и Вольси, Л. А. Целое число и комбинаторная оптимизация. Wiley-Interscience, Нью-Йорк, 1999.

[10] Savelsbergh, M. W. P. Методы предварительной обработки и зондирования для задач смешанного целочисленного программирования. ORSA J. Computing, том 6, № 4, стр. 445-454, 1994.

[11] Уолси, Л. А. Целочисленное программирование. Wiley-Interscience, Нью-Йорк, 1998.

Документация