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

Диссертация посвящена исследованию задач целочисленного программирования (ЦП) и разработке алгоритмов их решения. К моделям ЦП сводятся многие прикладные задачи, возникающие в экономике, управлении, проектировании и других областях. Условие целочисленности позволяет учесть такие факторы, как неделимость продукции, дискретность процессов, наличие альтернатив, фиксированные доплаты и т. п.

В настоящее время целочисленное программирование представляет собой одно из активно развивающихся направлений дискретной оптимизации. Современная проблематика ЦП охватывает такие вопросы как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы, программное обеспечение, экспериментальные исследования и др. [1,5,7,9,12,17,32,3947,53−55,57,58,60,62,63,68,69,77,78,80,84,92].

Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности более «легких» задач непрерывной оптимизации. К таким методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг [40,46]), декомпозиции (с отсечениями Бендерса [35,75,86]), алгоритмы перебора Ь-классов [32] и некоторые другие. Характерными особенностями этих методов являются использование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.

Метод отсечения, один из общих подходов к решению задач как непрерывной, так и дискретной оптимизации, получил свое развитие в работах многих авторов, в том числе в [2,21,40,59,60,66,77,80−82,85, 94]. Отличительной чертой метода является генерация и использование в процессе решения дополнительных линейных ограничений (отсечений). При этом допустимая область исходной задачи погружается в некоторое выпуклое многогранное множество, которое затем последовательно «обрезается» с помощью отсечений до получения нужного результата. Исследования по методу отсечения включают вопросы построения и анализа отсечений, разработку алгоритмов, изучение проблемы их конечности, получение оценок числа итераций, сравнение эффективности алгоритмов и ряд других.

Для исследования задач ЦП, построения и анализа алгоритмов их решения, основанных на использовании релаксационных множеств, А. А. Колоколовым был предложен метод регулярных разбиений [27,33], получивший дальнейшее развитие, в частности, в работах [6,1014,18,19,21,24,25,28−32,34,35,38,56,86−88].

В соответствии с этим подходом исходное евклидово пространство, а, следовательно, и допустимая область непрерывной задачи, связанной с задачей ЦП, разбивается определенным образом на классы эквивалентности. С помощью регулярных разбиений введены и исследованы новые классы отсечений, построены оценки числа итераций (отсечений) для ряда рассматриваемых алгоритмов (в том числе для первого алгоритма Гомори), изучена структура некоторых задач ЦП, разработаны алгоритмы решения задач ЦП, проведены экспериментальные исследования. Многие из указанных результатов получены с помощью ¿—разбиения, которое в определенном отношении согласовано с лексикографическим порядком. В частности, на основе этого разбиения предложены алгоритмы решения задач ЦП (алгоритмы перебора ¿—классов).

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

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

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

Диссертация состоит из трех глав. В первой главе изучается ¿—структура задач о покрытии и упаковке множества. Задачи о покрытии имеют широкое практическое применение. Например, они возникают при составлении расписаний экипажей на авиалиниях, в задачах информационного поиска, политического районирования, упрощении булевых выражений [41,74]. Кроме того, другие известные задачи оптимизации могут быть сведены к задаче о покрытии [41].

Э.Балашем предложено и исследовано семейство задач о покрытии [65], которое характеризуется значительной разностью оптимальных значений целевых функций целочисленной задачи и ее линейной релаксации. В этом семействе нами выделены задачи, для которых мощность ¿—накрытий растет экспоненциально с увеличением числа переменных. Число ограничений в них также экспоненциально зависит от числа переменных. Из проведенного нами вычислительного эксперимента следует, что эти задачи являются трудными для 1-го алгоритма Гомори, так как глубина его отсечений при их решении близка к 1. Получено точное выражение мощности ¿—накрытия произвольной задачи из рассматриваемого семейства.

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

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

Вторая глава посвящена построению алгоритмов решения задачи о покрытии и исследованию прямых алгоритмов отсечения в целочисленном линейном программировании (ЦЛП). В литературе описаны точные алгоритмы решения задачи о покрытии, основанные на методе ветвей и границ, отсечениях, субградиентной технике и других подходах [41,67,70,74,79,90], а также различные приближенные алгоритмы и эвристики [8,71,73,76,78,84].

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

Далее в этой главе исследуются вопросы конечности и построения оценок числа итераций для прямых алгоритмов отсечения. Анализу указанных алгоритмов посвящены работы [21,60,64,81,83,89,94,95]. Известно, что простые реализации прямых алгоритмов отсечения (например, рудиментарный алгоритм — РИА) не являются конечными. Первые контпримеры для РПА были опубликованы в [91]. Эти задачи, построенные в Я3, не решаются за конечное число шагов при некоторых «плохих» стратегиях решения. А. А. Колоколовым [23] построены одно-параметрическое и двухпараметрическое семейства задач ЦЛП (также в трехмерном случае), при решении которых получается бесконечный процесс для любого из вариантов РПА и других более сложных прямых алгоритмов отсечения с управляющими ограничениями. Отметим, что на плоскости для РПА получена верхняя оценка числа итераций [20] и нижняя экспоненциальная оценка для общего случая [22].

Во второй главе на основе результатов из [23] получены новые более широкие семейства задач ЦЛП, также дающие бесконечный процесс для любого из вариантов РПА и более сложных алгоритмов. С использованием указанных семейств строятся задачи ЦЛП в Л3, которые как угодно долго решаются конечным прямым алгоритмом (КПА). Это также обобщает результаты из [23]. На основе изучения ¿—структуры дробных накрытий строится верхняя оценка числа регулярных отсечений, появляющихся при решении двойственными алгоритмами части задач из построенных семейств. Исследуется структура дробных накрытий этих же задач для кубических разбиений.

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

Третья глава посвящена кубическим разбиениям, которые порождаются различными округлениями векторов. В ней исследуется связь этих разбиений с ¿—разбиением и существование регулярных систем неравенств относительно кубических разбиений. Регулярные системы неравенств являются обобщением регулярных отсечений. Они вводятся как системы правильных неравенств, исключающие элемент ¿-" -накрытия множества, содержащий точку непрерывного оптимума. Ставится вопрос о минимальной размерности регулярной системы для разбиения называемой индексом этого разбиения, относительно фиксированного класса множеств.

Данный вопрос изучается для кубических разбиений и класса ограниченных сверху множеств [21]. В этом случае получено значение индекса, зависящее от структуры булева вектора, порождающего кубическое разбиение.

Рассматривается регулярность известных классов отсечений (отсечений Гомори [21,40,60,82], вполне регулярных отсечений булева программирования [11] и некоторых других) относительно кубических разбиений. Показана регулярность ¿—алгоритма, предложенного А. А. Вотяковым [3], для специального класса множеств.

Основные результаты диссертации опубликованы в работах [15,16, 34,36,37,48−52] и докладывались на III Всесоюзной школе «Дискретная оптимизация и компьютеры» (Таштагол, 1987), Омской областной математической конференции (1987), 10 Всесоюзном симпозиуме «Системы программного обеспечения решения задач оптимального планирования» (Усть-Нарва, 1988), 6 Всесоюзной конференции «Методы математического программирования и программное обеспечение» (Свердловск, 1989), IV Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (Новосибирск, 1989),.

III Всесоюзном семинаре «Дискретная математика и ее приложения» (Москва, 1990), 7 Всесоюзной конференции «Математическое программирование и приложения» (Свердловск, 1991), XI международной Байкальской школе-семинаре «Методы оптимизации и их приложения» (Иркутск, 1998), а также на семинарах в Институте математики им. С. Л. Соболева СО РАН, в Омском комплексном отделе ВЦ СО АН СССР, в Институте информационных технологий и прикладной математики СО РАН.

Основные результаты диссертации заключаются в следующем:

1. Проведен анализ задач о покрытии и упаковке множества:

— получены нижние оценки и точное значение мощности Ь-накрытий для семейства задач о покрытии, предложенных Э. Балашем;

— построены и исследованы задачи о покрытии и упаковке блочно-диагональной структуры с Ь-накрытиями, экспоненциально зависящими от числа переменных задачи;

— получены оценки числа итераций при решении этих задач некоторыми алгоритмами отсечения и методом Лэнд и Дойг.

2. Разработаны и исследованы алгоритмы перебора Ь-классов для точного и приближенного решения задач о покрытии множества. Создано программное обеспечение для алгоритмов перебора Ь-классов, проведены экспериментальные исследования.

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

4. Исследованы вопросы использования систем правильных линейных неравенств для исключения элементов кубических разбиений релаксационных множеств задач ЦП. Дана классификация кубических разбиений на основе индекса разбиения, изучена регулярность ряда известных отсечений (1-го алгоритма Гомори, вполне регулярных, алгоритма и др.) относительно кубических разбиений.

Заключение

.

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