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

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

Смешано-целочисленная линейная программа (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 не выполняет более поздние этапы.

Уменьшайте проблемный размер с помощью Линейной Предварительной обработки Программы.
Решите начальную букву, ослабленную (нецелое число) проблема с помощью Линейного Программирования.
Выполните Смешано-целочисленную Предварительную обработку Программы, чтобы усилить релаксацию LP смешано-целочисленной проблемы.
Попробуйте Генерацию Сокращения, чтобы далее усилить релаксацию LP смешано-целочисленной проблемы.
Попытайтесь найти целочисленно-выполнимые решения с помощью эвристики.
Используйте Ответвление и Связанный алгоритм, чтобы систематически искать оптимальное решение. Этот алгоритм решает релаксации LP с ограниченными областями значений возможных значений целочисленных переменных. Это пытается сгенерировать последовательность обновленных границ на оптимальном значении целевой функции.

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

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

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

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

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

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

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

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

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

f ^TxLP ≤ f ^Tx,

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

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

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

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

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

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

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

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

Сократите генерацию

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

Сокращения 'basic' включают:

Сокращения округления смешанного целого числа
Сокращения Gomory
Сокращения клики
Покройте сокращения
Сокращения покрытия потока

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

Сильные сокращения Chvatal-Gomory
Нулевая половина сокращений

Сокращения 'intermediate' включают все сокращения 'basic', плюс:

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

Сокращения 'advanced' включают все сокращения 'intermediate' кроме сокращений уменьшать-и-разделять, плюс:

Сильные сокращения Chvatal-Gomory
Нулевая половина сокращений

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

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

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

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

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

Установите эвристику intlinprog с помощью опции 'Heuristics'. Опции:

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

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

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

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

Перейдите и связанный

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

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

f ^Txfeas ≥ f ^Tx,

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

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

От стартовых границ метод ветвей и границ создает новые подпроблемы путем ветвления от корневого узла. Переходящий шаг сделан эвристическим образом, согласно одному из нескольких правил. Каждое правило основано на идее разделить проблему путем ограничения одной переменной, чтобы быть меньше чем или равным целому числу J, или больше, чем или равным J+1. Эти две подпроблемы возникают, когда запись в _LP x, соответствуя целому числу, заданному в intcon, не является целым числом. Здесь, _LP x является решением расслабленной проблемы. Возьмите J в качестве этажа переменной (округленной в меньшую сторону), и J+1 как (окруженный) потолок. Получившиеся две проблемы имеют решения, которые больше, чем или равны f ^TxLP, потому что у них есть больше ограничений. Поэтому эта процедура потенциально повышает нижнюю границу.

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

'maxpscost' — Выберите дробную переменную с максимальным pseudocost.
Псевдостоимость
Псевдостоимость переменной i основана на эмпирических оценках изменения в нижней границе, когда i был выбран в качестве переходящей переменной, объединенной с дробной частью компонента i текущей точки x. Дробная часть p находится в двух частях, более низкой части и верхней части:
_pi– = x (i) – ⌊x (i) ⌋
_pi+ = 1 – _pi–.
Позвольте _xi– быть решением линейной программы, ограниченной, чтобы иметь x (i) ≤ ⌊x (i) ⌋ и позволить изменению в целевой функции обозначаться
Δ_i– = f ^T_xi– – f ^Tx.
Точно так же Δ_i+ является изменением в целевой функции, когда проблема ограничивается, чтобы иметь x (i) ≥ ⌈x (i) ⌉.
Объективное усиление на модульное изменение в переменной _xi
$d_{i}^{-} = \frac{Δ_{i}^{-}}{p_{i}^{-}} или d_{i}^{+} = \frac{Δ_{i}^{+}}{p_{i}^{+}} .$
Позвольте _si– и _si+ быть эмпирическими средними значениями _di– и _di+ во время алгоритма метода ветвей и границ до этой точки. Эмпирические значения инициализируются к абсолютному значению объективного коэффициента f (i) для условий, прежде чем будут любые наблюдения. Затем правило 'maxpscost' состоит в том, чтобы перейти на узле i, который максимизирует, для некоторых положительных весов ^w+ и ^w–, количество
^w– * _pi– * _si– + ^w+ * _pi+ * _si+.
Примерно говоря, это правило выбирает коэффициент, который, вероятно, увеличит нижнюю границу максимально.
'strongpscost' — Подобно 'maxpscost', но вместо псевдостоимости, инициализируемой к 1 для каждой переменной, решатель пытается перейти на переменной только после того, как псевдостоимость будет иметь более надежную оценку. Чтобы получить более надежную оценку, решатель делает следующее (см. Achterberg, Коха и Мартина [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+, где
_pi– = x (i) – ⌊x (i) ⌋
_pi+ = 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) .$
Если нет никакой целочисленной допустимой точки, найденной до сих пор, установите ^fTxB = 0.

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

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

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

Для получения дополнительной информации о методе ветвей и границ, смотрите Nemhauser и Wolsey [8] и Wolsey [10].

Ссылки

[1] Achterberg, T., Т. Кох и А. Мартин. Пересмотрены переходящие правила. Буквы 33, 2005 Исследования операций, стр 42–54. Доступный в https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf.

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

[3] Atamtürk, A., Г. Л. Немхаузер, М. В. П. Сэвелсберг. Графики конфликта в решении проблем целочисленного программирования. Европейский Журнал Исследования операций 121, 2000, стр 40–55.

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

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

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

[7] Месзарос К., и Зуль, У. Х. Адвэнсед, предварительно обрабатывающий методы для линейного и квадратичного программирования. Спектр OR, 25 (4), стр 575–595, 2003.

[8] Nemhauser, G. L. и Wolsey, L. A. Целочисленная и комбинаторная оптимизация. Wiley-межнаука, Нью-Йорк, 1999.

[9] Savelsbergh, М. В. П. Препросессинг и Методы Зондирования для проблем Частично-целочисленного программирования. ORSA J. Вычисление, Издание 6, № 4, стр 445–454, 1994.

[10] Wolsey, L. A. Целочисленное программирование. Wiley-межнаука, Нью-Йорк, 1998.

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