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

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

целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности .

Простейший метод решения задачи целочисленного программирования — сведение ее к задаче линейного программирования с проверкой результата на целочисленность.

Булевское программирование
К частному случаю задачи целочисленного линейного программирования относятся задачи, где переменные X могут принимать всего лишь два значения — 0 и 1. Соответствующие задачи часто называют задачами булевского программирования. Наиболее известные из этих задач — задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т. д. Целочисленное программирование применяется при решении задачи оптимизации развития компании, в которой 0 или 1 означают покупку какого-либо оборудования.

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

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

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

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

Целочисленные линейные программы могут быть выражены либо в канонической , либо в стандартной форме (обе формы определены ниже), которые отличаются друг от друга. Целочисленная линейная программа в канонической форме выражается следующим образом (обратите внимание, что этох вектор, который необходимо определить): [ 5 ]

максимизировать

а целочисленное линейное программирование в стандартной форме выражается следующим образом:

максимизировать

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

IP-политоп с LP-релаксацией

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

максимизировать

Допустимые целочисленные точки показаны красным цветом, а красные пунктирные линии обозначают их выпуклую оболочку , которая представляет собой наименьший выпуклый многогранник, содержащий все эти точки. Синие линии вместе с координатными осями определяют многогранник LP-релаксации, который задается неравенствами без ограничения целочисленности. Цель оптимизации — переместить черную пунктирную линию как можно выше, не касаясь многогранника. Оптимальными решениями целочисленной задачи являются точки(1,2) и(2,2) что оба параметра имеют объективное значение, равное 2. Единственный оптимум релаксации — это(1.8,2.8) с целевым значением 2,8. Если решение релаксации округляется до ближайших целых чисел, оно не является допустимым для целочисленного линейного программирования. См. проекцию на симплекс.

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

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

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

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

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

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

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

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

Программирование со смешанными целочисленными переменными находит широкое применение в промышленном производстве, включая моделирование мелкосерийного производства. Об этом говорит сайт https://intellect.icu . Важный пример — планирование сельскохозяйственного производства , где необходимо определить урожайность нескольких культур, для которых доступны общие ресурсы (например, земля, рабочая сила, капитал, семена, удобрения и т. д.). Возможная цель — максимизировать общий объем производства, не превышая имеющихся ресурсов. В некоторых случаях это можно выразить в виде линейной программы, но переменные должны быть целочисленными.

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

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

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

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

• Сопоставление денежных потоков
• Оптимизация энергетической системы [ 10 ] [ 11 ]
• Наведение БПЛА [ 12 ] [ 13 ]
• Схема расположения транспортных маршрутов [ 14 ]

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

В общем случае решение задачи релаксации линейного программирования не гарантирует целочисленности, если целочисленное линейное программирование имеет следующий вид:макссТхтаким образом, чтоАх=бгдеАибиметь все целочисленные элементы иАЕсли функция является полностью унимодулярной , то каждое базисное допустимое решение является целочисленным. Следовательно, решение, возвращаемое симплекс -алгоритмом, гарантированно является целочисленным. Чтобы показать, что каждое базисное допустимое решение является целочисленным, пустьхПусть будет произвольное базисное допустимое решение. Посколькухэто осуществимо, мы это знаем.Ах=б. Позволятьх0=[хн1,хн2,⋯,хндж]пусть элементы будут соответствовать базисным столбцам для базисного решения.хПо определению базиса, существует некоторая квадратная подматрица.Биз Ас линейно независимыми столбцами такими, чтоБх0=б.

Поскольку колонныБявляются линейно независимыми иБквадратный,Бявляется несингулярным, и, следовательно, по предположению,Бявляется одномодульным , и поэтомудет(Б)=±1Кроме того, посколькуБявляется невырожденной, она обратима и, следовательно По определению, . ЗдесьБадджобозначает сопряженное​Би является неотъемлемой частью, потому чтоБявляется целочисленным. Следовательно,⇒Б−1=±Баддж является неотъемлемой частью.⇒х0=Б−1б является неотъемлемой частью.⇒Каждое базовое возможное решение является неотъемлемой частью процесса.Таким образом, если матрицаАЕсли задача целочисленного линейного программирования (ЦЛП) является полностью унимодулярной, то вместо использования алгоритма ЦЛП для решения релаксации ЦЛП можно использовать симплекс-метод, и решение будет целочисленным.

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

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

ПредполагатьАявляется целочисленной матрицей размером m × n иб— это целочисленный вектор размером m × 1. Мы сосредоточимся на проблеме выполнимости, которая заключается в определении того, существует ли вектор размером n × 1.худовлетворительныйАх≤б.

Пусть V — максимальное абсолютное значение коэффициентов вА ибЕсли n (число переменных) является фиксированной константой, то задача осуществимости может быть решена за время, полиномиальное от m и log V. Это тривиально для случая n = 1. Случай n = 2 был решен в 1981 году Гербертом Скарфом . [ 15 ] Общий случай был решен в 1983 году Хендриком Ленстрой , объединившим идеи Ласло Ловаша и Питера ван Эмде Боаса . [ 16 ] Теорема Дуаньона утверждает, что целочисленная программа осуществима, если каждое подмножество2нОграничения являются осуществимыми; метод, сочетающий этот результат с алгоритмами для задач типа линейного программирования, может быть использован для решения задач целочисленного программирования за время, линейно зависящее от времени.ми поддающийся обработке с фиксированными параметрами (FPT) внно, возможно, с двойной экспоненциальной зависимостью.н, без зависимости отВ. [ 17 ]

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

• Оригинальный алгоритм Ленстры [ 16 ] имел время выполнения .
• Каннан [ 18 ] представил улучшенный алгоритм с временем выполнения. . [ 19 ]
• Франк и Тардос [ 20 ] представили улучшенный алгоритм с временем выполнения. . [ 21 ] [ 22 ] : Предложение 8 
• Дадуш [ 23 ] представил улучшенный алгоритм с временем выполнения. .
• Рейс и Ротвосс [ 24 ] представили улучшенный алгоритм с временем выполнения. .

Эти алгоритмы также могут использоваться для смешанных целочисленных линейных программ (MILP) — программ, в которых некоторые переменные являются целыми, а некоторые — действительными. [ 25 ] Оригинальный алгоритм Ленстры [ 16 ] : Раздел 5  имеет время выполнения , где n — количество целочисленных переменных, d — количество непрерывных переменных, а L — размер двоичного кодирования задачи. Используя методы из более поздних алгоритмов, фактор можно улучшить до или кнн. [ 25 ]

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

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

• Восхождение на холм
• Имитация отжига
• Реактивная оптимизация поиска
• Оптимизация муравьиной колонии
• Нейронные сети Хопфилда

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

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

• Метод наименьших квадратов с ограничениями
• Диофантово уравнение — полиномиальное уравнение, для которого ищутся целочисленные решения.

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