УДК 519.854.64

ИССЛЕДОВАНИЕ В СРЕДНЕМ ОДНОГО КЛАССА ОБОБЩЕННЫХ ЗАДАЧ 
ОБ УПАКОВКЕ МНОЖЕСТВА

Л.А. Заозерская, 1А.В. Яклюшин
Институт  математики им С.Л. Соболева СО РАН, Омский филиал, г. Омск, Россия
1Омский государственный университет им. Ф.М. Достоевского, г. Омск, Россия

Аннотация – В работе рассматривается класс обобщенных задач об упаковке множества при известном распределении данных. На основе анализа структуры  множества допустимых решений были получены полиномиальные в среднем верхние оценки числа допустимых решений задач из рассматриваемого класса. Исследуется поведение метода ветвей и границ (схема Лэнд и Дойг) при решении задач из данного класса, приводятся результаты вычислительного эксперимента.  

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

Задача об упаковке множества является одной из известных NP-трудных задач дискретной оптимизации. Существуют примеры семейств задач (см. [1]), которые требуют для своего решения экспоненциального числа итераций алгоритма ветвей и границ типа Лэнд и Дойг, алгоритма перебора L – классов и некоторых алгоритмов отсечения (см. [9]). С другой стороны, экспериментальные исследования показывают, что такие задачи со случайными исходными данными успешно решаются для достаточно больших размерностей. Поэтому актуальным является исследование в среднем свойств задачи и поведения алгоритмов при ее решении для различных распределений исходных данных. В [8] для задачи о многомерном рюкзаке был выделен класс задач, который является полиномиально разрешимым в среднем алгоритмом динамического программирования. Этот результат основан на построении верхней полиномиальной оценки для средней мощности множества допустимых решений задач. Там же аналогичный результат получен для задачи об упаковке множества.
 В [4, 6] был предложен подход к построению верхних оценок числа итераций в среднем для ряда известных алгоритмов целочисленного линейного программирования (ЦЛП), основанных на использовании аппарата непрерывной оптимизации. Идея подхода заключается в использовании детерминированных оценок числа итераций алгоритмов, полученных в рамках метода регулярных разбиений предложенного Колоколовым А.А. [7], и верхних оценок средней мощности множества допустимых решений задач. Этот подход был применен к получению полиномиальных оценок числа итераций указанных выше алгоритмов при решении задач об  упаковке множества и покрытия множества и некоторых их обобщений [2, 4], а так же для специальных случаев задачи о многомерном рюкзаке с булевыми переменными [3] .
Рассматривается   обобщенная задача об упаковке множества:

при условиях 

где булева матрица, и все целые, вектор переменных.
Если все  то (1) является классической задачей об упаковке множества [1].
Рассмотрим класс  задач типа (1) в которых,  независимые случайные величины, причем  а    а все  Заметим, что верхние оценки числа допустимых решений для класса  остаются верными для задач, в которых  Для классической задачи об упаковке множества и ее обобщения (все ) были установлены  соотношения для ипри которых имеют место полиномиальные  верхние оценки среднего числа допустимых решений [2, 4].  В данной работе нами исследуется средняя мощность множества допустимых решений задач из класса  при  
Обозначим через  – допустимый вектор задачи, имеющий   ровно единичных компонент, а через  – множество таких векторов. Далее это множество назовем s-ым слоем. Для простоты обозначений, будем считать, что все единичные компоненты вектора  занимают первые мест. Заметим, что вероятность того, что булев вектор   удовлетворяет i-му ограничению задачи, не зависит от выбора. Обозначим эту вероятность через  Очевидно, что
для  s = 0,…,n,
а  – вероятность того, что вектор  является допустимым решением задачи.  Тогда , где  – математическое ожидание случайной величины .
В [10] для класса  доказано, что при  имеют место неравенства
где                                                     
	Отсюда непосредственно следует, что 

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

Лемма.  При и целом m () выполнено 

	Заметим, что при заданных условиях среднее число допустимых решений достигает максимума на слое с номером k и монотонно убывает после. Полученные данные позволяют построить средние верхние полиномиальные оценки мощности множества допустимых решений для задач из рассматриваемого класса. 
Теорема. Для обобщенной задач об упаковке множества при целых и  справедлива следующая оценка:
 
Таким образом, при фиксированном k имеем полиномиальные верхние оценки на мощность множества допустимых решений из предложенного класса. Из теоремы на основе подхода из [7] получены полиномиально разрешимые в среднем подклассы обобщенных задач об упаковке множества такими алгоритмами, как метод ветвей и границ, алгоритмы отсечения (например, первый алгоритм Гомори), алгоритм перебора L-классов. В частности, среднее число итераций метода ветвей и границ (схема Лэнд и Дойг) выражено через математическое ожидание мощности множества допустимых решений задачи [5]:
.
	Полученные оценки позволяют провести вычислительный эксперимент следующим образом. Задачи из рассматриваемого класса можно разбить на группы по значению параметра k, в которых число ограничений m и число переменных n удовлетворяют условиям леммы. Это означает, что слой с номером k имеет наибольшую мощность среди остальных слоев множества допустимых решений задачи, т.е. задачи из одной группы обладают похожими множествами допустимых решений. 
Алгоритмом метода ветвей и границ (схема Лэнд и Дойг) было решено 100 серий из 10 тестовых задач для n = 70, p = {0.02, 0.03, 0.04, 0.05, 0.08}, B = 1 и . За одну итерацию алгоритма было принято вычисление границы. Ниже приведены графики значения среднего числа итераций при указанных значениях p. Для каждой пары p и k под графиком указано число ограничений m для задач из данной серии, например для k = 6 и p = 0.02  число ограничений равно 1014. 

Рис. 1. Среднее число итераций метода ветвей и границ

Максимальное значение среднего числа итераций достигался на k = 6 для  p = 0.02, 0.03, а для больших значений p  при k = 4.  При уменьшении вероятности максимальное значение среднего числа итераций достигается при большем значении k. Как следует из графиков, наиболее сложными для алгоритма являются задачи для . Отметим, что при достаточно малых k (т.е. большом числе ограничений) задачи являются легкими для алгоритма. В среднем они решаются за 200 итераций. Также при росте k (т.е. уменьшении числа ограничений) наблюдается снижение среднего числа итераций и при k > 16 среднее число итераций стремится к единице. Отметим, что при уменьшении вероятности p расширяется интервал для k, соответствующий  "сложным"  задачам. Например, для p = 0.05 – это задачи при 2 < k < 7, а для  p = 0.02 – при 2 < k < 12.  Отметим,  что среднее оптимальное значение целевой функции не превосходило 3k.  При уменьшении значения параметра k возрастает разрыв двойственности.
	В работе был рассмотрен класс обобщенных задач об упаковке множества со случайными исходными данными. Для задач из  этого класса были исследованы свойства множества допустимых решений  и получены верхние оценки на число допустимых решений задачи. Полученные свойства и оценки позволили предложить новый вариант проведения вычислительного эксперимента, в котором задачи группируются по значению параметра k. Полученные результаты обладают похожими свойствами, что вызывает интерес к проведению экспериментов предложенным способом.  В дальнейшем представляет интерес получить аналогичные результаты для  задачи о многомерном рюкзаке.

Библиографический список
1. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М. : Мир, 1982. – 416 c.
2. Заозерская, Л. А. Исследование среднего числа допустимых решений некоторых классов задач булева программирования / Л. А. Заозерская // Проблемы оптимизации и экономические приложения: материалы V Всероссийской конф. –  Омск, 2012. –  С. 127. 
3.  Заозерская, Л. А. Исследование среднего числа допустимых решений многомерной задачи о рюкзаке / Л. А. Заозерская // Дискретная оптимизация и исследование операций: материалы междунар. конференции (Новосибирск, 24 – 28 июня). –  2013. – С. 70.
4. Заозерская, Л. А.  О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества / Л. А. Заозерская,  А. А. Колоколов // Методы оптимизации и их приложения: труды XIV Байкальской междунар. школы-семинара. –  Иркутск: ИСЭМ СО РАН, 2008. –  Т. 1. –  С. 388–395.
5. Заозерская, Л. А.  Оценки среднего числа итераций для ряда алгоритмов решения задач об упаковке и покрытии множества / Л. А. Заозерская, А. А. Колоколов // Интеллектуализация обработки информации: 9-ая междунар. конф. Черногория, г. Будва, 2012 г.: Сборник докладов. – М. : Торус пресс, 2012. – С. 260–262.
6. Заозерская, Л. А.  Построение и анализ оценок числа итераций для алгоритмов целочисленного программирования с использованием метода регулярных разбиений / Л. А. Заозерская, А. А. Колоколов //  Известия вузов. Математика. – 2014. – № 1. – С.41–54.
7. Колоколов, А.А. Регулярные разбиения и отсечения в целочисленном линейном программировании / А. А. Колоколов // Сибирский журнал исследования операций. – 1994. – Т.1, №2. – С. 18–39.
8. Кузюрин, Н. Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании / Н. Н. Кузюрин // Сибирский журнал исследования операций. – 1994. – Т.1, №3. – С. 38–48.
9.  Схрейвер,  А. Теория линейного и целочисленного программирования: монография / А. Схрейвер. – М. : Мир, 1981. – 600 с.
10. Яклюшин, А. В. Анализ в среднем множества допустимых решений одного класса обобщенных задач об упаковке множества/ А. В. Яклюшин //  Сборник статей III региональной конференции магистров, аспирантов и молодых ученых по физике и математике. – Омск, 2015. – С. 29–32.