Смешанно-целочисленная линейная программа (MILP) является проблемой
Линейная целевая функция, fTx, где f - вектор-столбец констант, а x - вектор-столбец неизвестных
Ограничения и линейные ограничения, но без нелинейных ограничений (определения см. в разделе Ограничения записи)
Ограничения для некоторых компонентов x иметь целочисленные значения
В математических терминах, заданных векторами f, lb и ub, матрицы A и Aeq, соответствующие векторы b и beq и набор индексов intcon, найти вектор x для решения
.
intlinprog использует эту базовую стратегию для решения смешанных целочисленных линейных программ. intlinprog может решить проблему на любом из этапов. Если задача решается на этапе, intlinprog не выполняет более поздние этапы.
Уменьшите размер проблемы с помощью предварительной обработки линейной программы.
С помощью линейного программирования решите начальную проблему с ослабленной (неинтегрированной) функцией.
Выполните предварительную обработку смешанной целочисленной программы, чтобы усилить релаксацию LP проблемы смешанной целочисленной программы.
Попробуйте Cut Generation для дальнейшего ужесточения релаксации LP смешанной целочисленной проблемы.
Попробуйте найти целочисленные решения с помощью эвристики.
Используйте алгоритм ветвления и привязки для систематического поиска оптимального решения. Этот алгоритм решает релаксации ЛП с ограниченными диапазонами возможных значений целочисленных переменных. Он пытается создать последовательность обновленных границ для оптимального значения целевой функции.
Согласно определению смешанного целочисленного линейного программирования, существуют матрицы A и Aeq и соответствующие векторы b и beq, которые кодируют набор линейных неравенств и линейных уравнений.
Эти линейные ограничения ограничивают решение x.
Обычно можно уменьшить количество переменных в задаче (число компонентов x), и уменьшить число линейных ограничений. Хотя выполнение этих сокращений может потребовать времени для решателя, они обычно сокращают общее время решения и могут сделать более крупные проблемы разрешимыми. Алгоритмы могут сделать решение более стабильным в числовом отношении. Кроме того, эти алгоритмы могут иногда обнаруживать неосуществимую проблему.
Шаги предварительной обработки направлены на устранение избыточных переменных и ограничений, улучшение масштабирования модели и разреженности матрицы ограничений, усиление границ переменных и обнаружение основной и двойной несходимости модели.
Подробнее см. Андерсен и Андерсен [2] и Месзарос и Суль [8].
Начальная ослабленная задача - это задача линейного программирования с той же целью и ограничениями, что и Определение линейного программирования со смешанным целым числом, но без целочисленных ограничений. Вызовите xLP для решения проблемы и x для решения исходной задачи с целочисленными ограничениями. Ясно,
fTxLP ≤ fTx,
поскольку xLP минимизирует ту же функцию, но с меньшим количеством ограничений.
Этот начальный релаксированный ЛП (корневой узел ЛП) и все сгенерированные релаксации ЛП во время алгоритма перехода и ограничения решаются с использованием методов решения линейного программирования.
Во время предварительной обработки смешанной целочисленной программы, intlinprog анализирует линейные неравенства A*x ≤ b вместе с ограничениями интегральности для определения того,
Проблема неосуществима.
Некоторые границы могут быть ужесточены.
Некоторые неравенства избыточны, поэтому их можно игнорировать или устранять.
Некоторые проявления неравенства могут быть усилены.
Некоторые целочисленные переменные могут быть фиксированными.
IntegerPreprocess позволяет выбрать, intlinprog делает несколько шагов, делает все из них, или почти не делает ни одного из них. Если включить x0 аргумент, intlinprog использует это значение в предварительной обработке.
Основная цель предварительной обработки смешанно-целочисленной программы заключается в упрощении последующих вычислений ветвлений и границ. Предварительная обработка включает в себя быстрое предварительное изучение и устранение некоторых бесполезных кандидатов на подпроблемы, которые в противном случае анализировались бы как ветвь.
Для получения подробной информации о предварительной обработке целых чисел см. Savelsbergh [10].
Вырезы - это дополнительные линейные ограничения неравенства, которые intlinprog добавляет к проблеме. Эти неравенства пытаются ограничить осуществимую область релаксаций ЛП, чтобы их решения были ближе к целым числам. Вы контролируете тип вырезов, которые intlinprog использует с CutGeneration вариант.
'basic' вырезы включают в себя:
Сокращения округления со смешанным целым числом
Гоморские отрубы
Кликовые вырезы
Кройки покрытия
Порезы покрытия потока
Кроме того, если задача является чисто целочисленной (все переменные являются целочисленными), то intlinprog также использует следующие вырезы:
Сильные чватально-гоморские порезы
Отсечки ноль-половина
'intermediate' вырезы включают все 'basic' вырезы, плюс:
Простые подъемно-проектные разрезы
Простые пультовые и уменьшающие разрезы
Сокращение и разделение погонов
'advanced' вырезы включают все 'intermediate' разрезы, кроме разрезов и разрезов, плюс:
Сильные чватально-гоморские порезы
Отсечки ноль-половина
Для чисто целочисленных задач, 'intermediate' использует большинство типов разрезов, поскольку использует разрезы с сокращением и разделением, в то время как 'advanced' не делает.
Другой вариант, CutMaxIterations, указывает верхнюю границу в количестве раз intlinprog выполняет итерации для создания вырезов.
Подробнее о алгоритмах формирования разрезов (также называемых методами секущей плоскости) см. Cornuéjols [5] и, для кликовых разрезов, Atamtürk, Nemhauser и Savelsbergh [3].
Чтобы получить верхнюю границу целевой функции, процедура перехода и привязки должна найти возможные точки. Решение релаксации ЛП во время перехода и связи может быть целочисленным, что может обеспечить улучшенную верхнюю границу исходного MILP. Некоторые методы находят возможные точки быстрее до или во время перехода и привязки. intlinprog использует эти методы в корневом узле и во время некоторых итераций ветвей и границ. Эти методы эвристичны, что означает, что они являются алгоритмами, которые могут преуспеть, но также могут потерпеть неудачу.
Эвристика может быть начальной эвристикой, которая помогает решателю найти начальное или новое целочисленное решение. Или эвристика может быть эвристикой улучшения, которая начинается с целочисленной точки и пытается найти лучшую целочисленную точку, то есть точку с более низким значением целевой функции. intlinprog эвристика улучшения 'rins', 'rss', 1-opt, 2-opt и управляемое погружение.
Установите intlinprog эвристику с использованием 'Heuristics' вариант. Возможны следующие варианты:
| Выбор | Описание |
|---|---|
'basic' (по умолчанию) | Решатель выполняет эвристику округления дважды с различными параметрами, выполняет эвристику погружения дважды с различными параметрами, затем выполняет |
'intermediate' | Решатель дважды выполняет эвристику округления с различными параметрами, затем дважды выполняет эвристику погружения с различными параметрами. Если существует целочисленное решение, решатель запускается |
'advanced' | Решатель дважды выполняет эвристику округления с различными параметрами, затем дважды выполняет эвристику погружения с различными параметрами. Если существует целочисленное решение, решатель запускается |
'rins' или эквивалент 'rins-diving' |
|
'rss' или эквивалент 'rss-diving' |
|
'round' |
|
'round-diving' | Решатель работает аналогично |
'diving' |
Эвристика погружения обычно выбирает одну переменную, которая должна быть целочисленной, для которой текущее решение является дробным. Затем эвристика вводит ограничение, которое вынуждает переменную быть целочисленной, и снова решает связанную ослабленную ЛП. Метод выбора переменной для привязки является основным отличием эвристики погружения. См. Berthold [4], раздел 3.1. |
'none' |
|
Основное различие между 'intermediate' и 'advanced' является ли это 'advanced' чаще выполняет эвристику во время итераций ветвлений и границ.
В дополнение к предыдущей таблице, следующая эвристика выполняется при Heuristics опция - 'basic', 'intermediate', или 'advanced'.
ZI round - эта эвристика выполняется всякий раз, когда алгоритм решает расслабленную ЛП. Эвристика проходит через каждую дробную целочисленную переменную, чтобы попытаться переместить ее в соседнее целое число, не влияя на осуществимость по отношению к другим ограничениям. Для получения более подробной информации см. Hendel [7].
1-opt - эта эвристика выполняется всякий раз, когда алгоритм находит новое целочисленное решение. Эвристика проходит через каждую целочисленную переменную, чтобы попытаться переместить её в соседнее целое число, не влияя на осуществимость по отношению к другим ограничениям, при этом понижая значение целевой функции.
2-opt - эта эвристика выполняется всякий раз, когда алгоритм находит новое целочисленное решение. 2-opt находит все пары целых переменных, которые влияют на одно и то же ограничение, что означает, что они имеют ненулевые записи в одной и той же строке A или Aeq матрица ограничений. Для каждой пары 2-opt принимает целочисленное выполнимое решение и перемещает значения пар переменных вверх или вниз, используя все четыре возможных перемещения (вверх-вверх, вверх-вниз, вниз-вверх и вниз), ища осуществимое соседнее решение, которое имеет лучшее значение целевой функции. Алгоритм проверяет каждую целочисленную пару переменных путем вычисления наибольшего размера (той же величины) сдвигов для каждой переменной в паре, которая удовлетворяет ограничениям, а также улучшает значение целевой функции.
В начале фазы эвристики, intlinprog выполняет тривиальную эвристику, если Heuristics является 'none' или вы предоставляете начальную целочисленную возможную точку в x0 аргумент. Тривиальная эвристика проверяет выполнимость следующих моментов:
Все нули
Верхняя граница
Нижняя граница (если ненулевая)
Точка «Блокировка»
Точка «lock» определяется только для задач с конечными верхними и нижними границами для всех переменных. Точкой «lock» для каждой переменной является ее верхняя или нижняя граница, выбранная следующим образом. Для каждой переменной j, подсчитать количество соответствующих положительных записей в матрице линейных ограничений A(:,j) и вычитают число соответствующих отрицательных записей. Если результат положительный, используйте нижнюю границу для этой переменной, lb(j). В противном случае используйте верхнюю границу для этой переменной, ub(j). Точка «блокировки» пытается удовлетворить наибольшее число линейных ограничений неравенства для каждой переменной, но не обязательно выполнима.
После завершения каждой эвристики с возможным решением, intlinprog вызывает функции вывода и функции печати. См. разделы «Функция вывода intlinprog» и «Синтаксис функции печати».
Если включить x0 аргумент, intlinprog использует это значение в 'rins' и управляемую эвристику погружения до тех пор, пока она не найдет лучшую целочисленную осуществимую точку. Таким образом, когда вы предоставляете x0, вы можете получить хорошие результаты, установив 'Heuristics' опция для 'rins-diving' или другой параметр, использующий 'rins'.
Метод ветвления и связывания конструирует последовательность подпроблем, которые пытаются сойтись к решению MILP. Подпроблемы дают последовательность верхних и нижних границ решения fTx. Первая верхняя граница является любым возможным решением, а первая нижняя граница является решением ослабленной проблемы. Обсуждение верхней границы см. в разделе Эвристика поиска возможных решений.
Как поясняется в разделе «Линейное программирование», любое решение задачи ослабления линейного программирования имеет более низкое значение целевой функции, чем решение MILP. Кроме того, любая возможная точка xfeas удовлетворяет
fTxfeas ≥ fTx,
потому что fTx - это минимум среди всех возможных точек.
В этом контексте узел представляет собой ЛП с той же целевой функцией, границами и линейными ограничениями, что и исходная задача, но без целочисленных ограничений и с конкретными изменениями линейных ограничений или границ. Корневой узел является исходной проблемой без целочисленных ограничений и без изменений линейных ограничений или границ, что означает, что корневой узел является начальным ослабленным LP.
Начиная с начальных границ, метод ветвления и связывания создает новые подпроблемы путем ветвления от корневого узла. Стадия ветвления осуществляется эвристически, согласно одному из нескольких правил. Каждое правило основано на идее разделения задачи, ограничивая одну переменную числом, меньшим или равным целому J, или большим или равным J + 1. Эти две подпроблемы возникают, когда запись в xLP, соответствующая целому числу, указанному в intcon, не является целым числом. В данном случае xLP является решением расслабленной проблемы. Возьмите J в качестве пола переменной (скругленный вниз), а J + 1 в качестве потолка (скругленный вверх). В результате две проблемы имеют решения, которые больше или равны fTxLP, потому что они имеют больше ограничений. Поэтому эта процедура потенциально поднимает нижнюю границу.
Производительность метода ветвления и привязки зависит от правила выбора переменной для разделения (правила ветвления). Алгоритм использует эти правила, которые можно задать в BranchRule вариант:
'maxpscost' - Выберите дробную переменную с максимальной псевдокостью.
'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' - Выберите узел с минимальной суммой целочисленных несходимостей. Это означает, что для каждого несбыточного целого компонента x (i) в узле сложите меньшее из pi- и pi +, где
p- = x (i) - ⌊ x (i) ⌋
pi + = 1 - pi-.
'simplebestproj' - Выберите узел с наилучшей проекцией.
intlinprog пропускает анализ некоторых подпроблем, рассматривая информацию из исходной задачи, такую как наибольший общий делитель целевой функции (GCD).
Процедура перехода и привязки продолжается, систематически генерируя подпроблемы для анализа и отбрасывания тех, которые не улучшат верхнюю или нижнюю границу цели, пока не будет выполнен один из следующих критериев остановки:
Алгоритм превышает MaxTime вариант.
Разница между нижней и верхней границами целевой функции меньше, чем AbsoluteGapTolerance или RelativeGapTolerance допуски.
Количество исследуемых узлов превышает MaxNodes вариант.
Число целых возможных точек превышает MaxFeasiblePoints вариант.
Для получения подробной информации о процедуре перехода и привязки см. Nemhauser и 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] Бертольд, Т. Первичная эвристика для смешанных целочисленных программ. Технишенский университет Берлина, сентябрь 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] Хендел, Г. Новая эвристика округления и распространения для смешанного целочисленного программирования. Степень бакалавра в Техническом университете Берлина, 2011 год. PDF доступен по адресу https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf.
[8] Mészáros C., и Suhl, U.H. Усовершенствованные методы предварительной обработки для линейного и квадратичного программирования. OR Spectrum, 25 (4), стр. 575-595, 2003.
[9] Немхаузер, Г. Л. и Вулси, Л. А. Целочисленная и комбинаторная оптимизация. Wiley-Interscience, Нью-Йорк, 1999.
[10] Савельсберг, М. В. П. Методы предварительной обработки и зондирования для проблем смешанного целочисленного программирования. ORSA J. Computing, том 6, № 4, стр. 445-454, 1994.
[11] Вулси, Л.А. Целочисленное программирование. Wiley-Interscience, Нью-Йорк, 1998.
