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

• Автор: Орловская, Татьяна Геннадьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 101 с. : ил.

Оглавление
Введение

1 Модели и методы целочисленного программирования

1.1 Постановки задач

1.2 Метод регулярных разбиений

1.3 О применении унимодулярных преобразований

2 Исследование и решение задач о рюкзаке на основе Ь — разбиения

2.1 Унимодулярные преобразования для задач о рюкзаке

2.2 Анализ Ь - структуры и алгоритмов решения задач о рюкзаке

2.3 Экспериментальные исследования

3 Анализ 2 - алгоритма решения задач целочисленного линейного программирования

3.1 Специальный класс задач целочисленного линейного программирования и г - алгоритм
3.2 Исследование г - алгоритма с использованием регулярных разбиений
3.3 Об оценках числа итераций
Заключение
Литература

Введение
Актуальность темы. Для решения многих задач, возникающих в планировании, управлении, проектировании и других областях, применяются модели и методы целочисленного программирования (ЦП), в которых учитываются такие факторы, как неделимость объектов, дискретность процессов, альтернативность выбора. Аппарат ЦП широко используется при исследовании различных классов задач дискретной оптимизации, в частности задач оптимального размещения [3-5,9,24,42,65], о покрытии [18,72], об упаковке [28,53,63], выполнимости логической формулы [1,34,35], задач с логическими и ресурсными ограничениями [43]. Значительный интерес к задачам ЦП обусловлен их MV - трудностью [12].
Проблематика ЦП является достаточно разнообразной и включает исследование структуры и сложности задач, разработку и анализ методов их решения, изучение вопросов устойчивости задач и алгоритмов, многокритериальные постановки и ряд других [1,2,4-8,13,16,17,19-21,31,32,35, 36,39,42,54-57,60,62,66,67,69,70,73-75,77,79-90,92,95,96].
В настоящее время в целочисленном программировании активно развивается предложенный A.A. Колоколовым метод регулярных разбиений [31, 32,52]. Наиболее изученным разбиением является L — разбиение, на основе которого разработаны алгоритмы решения задачи о покрытии, задачи о рюкзаке, задач выполнимости и других [27,31,39]. С помощью этого метода исследована L - структура некоторых задач ЦП [22,31,32,39,64], построены оценки числа итераций для ряда известных алгоритмов [21,27,29], введены новые классы отсечений [23,31,32,75], получены результаты по устойчивости задач и алгоритмов дискретной оптимизации [13,36].

Многие методы решения задач ЦГ1 основаны на использовании релаксационного множества задачи, которое определяется исходной системой ограничений без условия целочислениости переменных. При этом важную роль играют структура задачи и ее дробное накрытие, состоящее из точек, находящихся между лексикографически оптимальными решениями задачи ЦП и соответствующей непрерывной задачи. Регулярные разбиения позволяют оценивать “объем” дробного накрытия, характеризующего сложность решения задачи, и, таким образом, измерять эффективность алгоритмов. Как правило, мощные накрытия затрудняют процесс решения, поэтому перспективными представляются исследования, связанные с поиском и анализом методов улучшения структуры задач в терминах регулярных разбиений.
Одним из таких направлений, показавших свою продуктивность и актуальность, является построение и исследование унимодулярных преобразований [17,30,77], с помощью которых исходная задача сводится к эквивалентной ей задаче ЦП [15,38]. Применение унимодулярных преобразований сохраняет множество допустимых целочисленных точек, но может сделать структуру задачи более приемлемой для решения.
Несмотря на большое число результатов, полученных в области ЦП, с теоретической точки зрения многие вопросы требуют дальнейшего исследования. Среди них следует отметить: выделение полиномиально разрешимых случаев задач; построение семейств задач, трудных для решения некоторыми алгоритмами; получение оценок числа итераций; разработка и анализ новых, в том числе гибридных, алгоритмов.
Цель диссертации — исследование структуры и сложности задач ЦП, построение и анализ алгоритмов их решения с использованием регулярных разбиений и унимодулярных преобразований.
Для достижения поставленной цели решались следующие задачи:
1. Изучить возможности применения в ЦП различных линейных преобразований, в том числе унимодулярных, выделить классы таких пре-

преобразований. Как показывают указанные примеры, такие преобразования могут существенно улучшать структуру задачи и ускорять процесс ее решения с помощью алгоритмов ЦЛП.
Вопросы об использовании унимодулярных преобразований в алгоритмах решения задач целочисленного программирования рассматривались в приведенных ниже и других публикациях.
В статьях Вотякова A.A. [10,11] предложен 2 - алгоритм решения задач ЦЛП, основанный на использовании унимодулярных преобразований. Полученные нами результаты исследования указанного алгоритма приводятся в главе 3 данной диссертации.
В работе Г. Ленстры (см., например, в [77]) унимодулярные преобразования применялись при доказательстве полиномиальной разрешимости задачи целочисленного программирования в случае фиксированного числа переменных. Заблоцкой O.A. (см. [22]) рассматривалась задача о рюкзаке в булевой постановке с одним ограничением на равенство и последовательностью чисел Фибоначчи в качестве коэффициентов, упорядоченных по убыванию. В частности, было доказано, что, при условии существования целочисленного решения, мощность L - накрытия задачи не превосходит п. Как следствие, было установлено, что при решении указанной задачи регулярным процессом отсечения потребуется не более 77,+ 1 итерации. Также показано, что изменение порядка переменных на противоположный (простейшее унимодулярнос преобразование) приводит к тому, что задача может иметь экспоненциальное (от числа переменных задачи) L - накрытие даже при наличии целочисленной точки.
В [1,15] авторами предложены семейства задач ЦЛП, которые обладают L - накрытиями экспоненциальной от длины входа мощности и являются трудными для решения многими алгоритмами, основанными на использовании релаксационных множеств задач, в частности алгоритмов отсечения, ветвей и границ, перебора L - классов. Показано, что применение унимодулярных преобразований специального вида позволяет значительно уменьшать мощность L - накрытий задач и ускорять процесс их решения.