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

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

Смешано-целочисленная линейная программа (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) и сократить количество линейных ограничений. В то время как выполнение этих сокращений может занять время для решателя, они обычно понижают полное время к решению и могут сделать большие проблемы разрешимыми. Алгоритмы могут сделать решение более численно устойчивым. Кроме того, эти алгоритмы могут иногда обнаруживать неосуществимую проблему.

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

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

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

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

f ^TxLP ≤ f ^Tx,

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

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

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

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

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

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

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

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

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

Сокращения являются дополнительными линейными ограничениями неравенства что 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 использование эти методы в корневом узле и во время некоторых итераций метода ветвей и границ. Эти методы являются эвристикой, означая, что они - алгоритмы, которые могут успешно выполниться, но могут также перестать работать.

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

Установите 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' эвристика запусков более часто во время итераций метода ветвей и границ.

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

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

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

Все нули
Верхняя граница
Нижняя граница (если ненулевой)
"Заблокируйте" точку

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

После того, как каждая эвристика завершается с возможным решением, 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 опция.
Различие между нижними и верхними границами на целевой функции меньше AbsoluteGapTolerance или RelativeGapTolerance допуски.
Количество исследуемых узлов превышает MaxNodes опция.
Количество целочисленных допустимых точек превышает MaxFeasiblePoints опция.

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

Ссылки

[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] Hendel, G. Новая Эвристика Округления и Распространения для Частично-целочисленного программирования. Тезис степени бакалавра в Берлинском техническом университете, 2011. PDF, доступный по https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf.

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

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

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

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

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