Исследование одного класса задач об упаковке множества

МАТЕМАТИКА

Вестн. Ом. ун-та. 2012. № 4. С. 21-26.

УДК 519.854.3

А.А. Колоколов, М.Ф. Корбут

ИССЛЕДОВАНИЕ ОДНОГО КЛАССА ЗАДАЧ ОБ УПАКОВКЕ МНОЖЕСТВА*

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

Ключевые слова: исследование операций, целочисленное программирование, задача об упаковке множества, задачи блочной структуры, Х-накрытие.

Задача об упаковке множества вызывает большой интерес как с теоретической точки зрения, так и имеет важное прикладное значение в экономике, планировании, теории информации и др. областях. Она широко изучается российскими и зарубежными специалистами [1-6]. Для ее решения разрабатываются и исследуются алгоритмы различного типа. Так, в [2] приводится обзор использования полиэдрального подхода, который заключается в построении правильных неравенств и в применении методов их эффективного получения. Там же рассматривается взаимосвязь задачи об упаковке множества с ее теоретико-графовой постановкой и выделяются классы графов, на основе которых возможно построение неравенств указанного типа.

При моделировании сложных экономических и технических систем часто возникают оптимизационные задачи большой размерности. В силу естественной иерархической структуры связей таких систем в совокупности переменных могут выделяться подмножества (подсистемы), имеющие небольшое число общих переменных и совместных ограничений. Во многих случаях такие модели относятся к задачам целочисленного или частично целочисленного программирования блочного типа [7]. В [7] приводятся такого вида постановки для задачи о рюкзаке, транспортной задачи, задач в области планирования, систем обработки данных и др. Для их решения целесообразным является применение методов, в которых учитывается блочная структура модели. Там же представлен обзор декомпозиционных подходов к решению блочных задач целочисленного программирования.

В работе [8] исследуется эффективность модифицированного локального алгоритма решения задач дискретного программирования со специальной блочной структурой.

Для анализа задач целочисленного программирования (ЦП) и построения алгоритмов их решения А.А. Колоколовым был предложен метод регулярных разбиений (см., например, [9]), получивший применение и развитие во многих исследованиях. В соответствии с этим подходом релаксационное множество задачи ЦП разбивается определенным образом на классы эквивалентности. С помощью регулярных разбиений изучена структура ряда задач ЦП, разработаны алгоритмы их решения, рассмотрены вопросы устойчивости, проведены экспериментальные исследования. Многие результаты получены с помощью Ь-разбиения [9; 10]. В связи с этим представляется целесообразным применение данного подхода к исследованию задачи об упаковке множества.

* Работа выполнена при финансовой поддержке гранта РФФИ (проект 10-01-00598).

© А.А. Колоколов, М.Ф. Корбут, 2012

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

В данной работе продолжается исследование задачи об упаковке множества блочной структуры. Здесь Ь-разбиение используется как инструмент для оценки сложности задачи с точки зрения ее решения алгоритмами, основанными на методе лексикографического перебора Ь-классов, подробное описание которого представлено в [10]. Построены нижние оценки мощности Ь-накрытия для ряда задач об упаковке множества блочной структуры с одним и несколькими связующими столбцами, выделен подкласс ЖР-трудных задач, имеющих Ь-накрытия экспоненциальной мощности. Краткие сообщения об этих результатах содержатся в [4-6].

Задача об упаковке множества формулируется следующим образом. Пусть дано конечное множество I = {1, к, m} и семейство его подмножеств а = {51, к, Sn }. Упаковкой

множества I называется совокупность попарно непересекающихся подмножеств из а. Задача состоит в нахождении упаковки множества I максимальной мощности. Если для каждого подмножества SJ е а задан его

вес Cj > 0 , . = 1,к,п , то задача называется

взвешенной и в ней требуется найти упаковку множества I наибольшего веса.

Для анализа и решения рассматриваемой задачи используется модель целочисленного линейного программирования (ЦЛП). Обозначим через А = (а.) матрицу

инциденций элементов множества I и подмножеств Sj, где а. = 1, если г е Sj, а. = 0 -

иначе, г = 1,к,т , . = 1,к,п . Тогда модель ЦЛП имеет вид:

f (x) = Xcjxj ^ max

j=i

при условиях:

п

Xаух. - ^ г = 1,^,m,

.=1

X. е{0,1}, . = 1,к,п.

Здесь х = 1, если S.j включается в упаковку, х. = 0 в противном случае, у = 1,...,п.

Многогранник задачи (1)-(3) будем обозначать М = {х еЯп: Ах — е, х > 0}, е = (1,...,1).

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

U = {x' е Rn+1 : x0 - (c, x) = 0, x e M},

X' = (^ X1,K, xn ^

т. е. определить

z* = lex max

Заметим, что если z = (x0,...,xn) - решение задачи (4) (оно всегда существует и единственно), то x = (x1,k,xn) , где x1 = xlv..,xn = xn - оптимальное решение задачи (1)-(3), причем f (x) = x0. В дальнейшем z будем называть целочисленным решением, или оптимальным решением, задачи ЦЛП (4).

Задача линейного программирования (ЛП), соответствующая постановке (4), состоит в нахождении x = lex max(U), вектор x = (x„,..., xn ) будем называть непрерывным решением, или оптимальным решением, задачи ЛП. Оно также всегда существует и единственно.

Дробным накрытием задачи (4) называется множество

U0 = {x'eU : x f z, Vz e (UIZn+1)} , здесь f - знак лексикографического сравнения векторов.

Для исследования и решения задачи об упаковке множества используется

L-разбиение, которое определяется следующим образом:

1) каждая целочисленная точка

z е Zn образует отдельный класс разбиения;

2) нецелочисленные точки x, у е Rn

(x f у) принадлежат одному классу, если они не являются отделимыми, т. е.

3z е Zn: x f z f у .

Элементы такого разбиения называются L-классами. Фактор-множество U0/L называется L-накрытием.

Далее, при построении оценок мощности L-накрытий задач об упаковке множества (1)—(3) с матрицами инциденций специального блочного типа мы будем переходить к лексикографической задаче вида (4).

Анализ L-структуры задач блочного типа

Рассмотрим семейство задач (1)-(3) с числом переменных n = 3k , c = (1,...,1) и матрицей Dt, k е N :

(D \

Dk =

D

0

D

D =

( 0 1 1

Для задачи с матрицей Бк непрерывное решение имеет вид:

2111 111

2;2,2,2;"';2,2,2

х =

целочисленное - г =

юности Ь-нак дач в [3] был

|и.( А)/х\ >

Для мощности Ь-накрытия указанного семейства задач в [3] была получена оценка:

3к _ 3

8

В связи с этим возникает интерес и к задачам об упаковке множества О\, матрица которых имеет следующую структуру:

( О

О

0

Т1

где

V

(Т 1 І,1

Т

1І,2

Т

V -,3

О Тк

к У

Т,. є {0,1}, і = 1,2,3 ,

- = 1,к,к . Далее Т, будем называть тройкой, І = 1,к,к , а последний столбец (предполагаем, что он ненулевой) - связующим. Число переменных такой задачи п = 3к +1, где к - количество блоков. Нами доказана следующая теорема.

Теорема 1. Для мощности Ь-накрытия задач об упаковке множества (1)-(3) с матрицами О^, к єN имеет место оценка:

3к_2 - 5 8

Доказательство. Рассуждения будем проводить основываясь на том, что если значение хп в векторе решения определено, то при поиске остальных переменных можно решать к независимых задач, каждая из которых соответствует отдельному блоку. Напомним, что целочисленная линия уровня целевой функции задается уравнением / (х) = Е , где Е еZ .

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

1. Пусть связующий столбец содержит только одну единицу. Не уменьшая общности, можем считать, что единица принадлежит первой тройке 7]. Оптимальное решение задачи ЛП в этом случае будет иметь

_ (3к 1111 111 ^

вид х = 1 — + —; Ь; —,—,—;...;—,—,—;1 I, а за-^ 2 2 2 2 2 2 2 2 )

дачи ЦЛП - г* = (к +1;Ь;1,0,0;...;1,0,0;1) , где

= Т .

Если

Ь - это вектор-строка и

7[ = (1, 0, 0)7 , то г совпадает с лексикографически максимальной целой точкой на линии уровня Е = к +1. Поэтому необходимо найти суммарное количество Ь-классов на всех целочисленных линиях уровня целевой функции от Е = х0 до Е = к + 2 . Заметим, что в случае к = 1 , оптимальные решения задач ЛП и ЦЛП совпадают с вектором (1,0,0,1). Пусть к нечетное, к > 3. Линиям уровня целевой функции со значениями

г = 2,4,6,...,к - 3 ,

р = Зк +1 _ і 2 + 2 2 ’

принадлежат точки

У, =

3к і _ 1

1 1 1

1 1 1

’ ’ 15'"’ ,5^2’^"’2’2’2’

и

3к_2 _ 3

^ =(3к - г-1 Ь Ь 111 111 0

У ^ 2 2 ; 1;к; ‘-1;2,2,2;к;2,2,2;

где Ь. е {(1,0,0), (0,1,0), (0,0,1)} , . = 1,к,г.

Общее число точек на всех таких линиях уровня будет равно

к-3 к-3

X (3' + 3г-1 ) = Х 3г =:

г=2, г-четное г=1 ^

Если к - четное, то точки вида у1 и у2 принадлежат линиям уровня со значениями целевой функции:

Т7 3к г -1 . , 3 , 3

Е = — —— , г =1,3 к - 3 .

Количество допустимых целочисленных точек на всех линиях уровня будет равно

к-3 к-3 3к-2 - 1

х к+3г-1 )=х33г=—-.

г=1, г-нечетное г=0 ^

Таким образом, для любого к > 0 , получаем следующую оценку мощности

3к-^ - 3

Ь-накрытия задачи |^*(>-------------2--.

2. Пусть связующий столбец содержит I > 2 единиц, но в нем нет тройки с двумя единицами.

Оптимальное решение задачи ЛП имеет

_ (3к 111 1 1 1 п

вид х = 1 —;—,—,—;...;—,—,—;0 ^ 2 2 2 2 2 2 2

Это может быть проверено следующим образом. Рассмотрим другое допустимое решение х = (х„,..., хп) , в котором хп = е , где е е (0,1) . Тогда вектор значений переменных в блоках, соответствующих тройкам (1,0,0)7

и (0,1, 0)7 , будет равен [ -2,-1,_1 -е|, а трой-

ке (0,0,1)Т -

1 1 1

—,-----£,—

2 2 2

Значения осталь-

а

ных переменных не изменятся, а для целевой функции будет иметь место убывание: 3„ / 3 ^ 3 , 3

= — (к -ї) +ї1 — є I = — к - їє <—к =

:х„.

2Ч ' ^2 ) 2 2

Следовательно, х Р х . Такой же результат получается и для х = (х0,..., хп ) , хп = 1.

Оптимальное решение задачи ЦЛП имеет вид:

7* = (к +1; 1,0,0; ^; 1,0,0;• ••; Ъ2; ...Ъ, ;1,0,0;1),

,.,ї.

где

Ъ1 = Т , ] = 1,

J J ’ ’

Применяя рассуждения, случаю 1, получаем

аналогичные

И о\)/ 4

3к-2 - 3к-ї - 6 8

3. Отдельного внимания требует ситуация, когда I = 2 , Т = (1,0, 0)Т

и Тг е {(1,0,0)Т, (0,1,0)Т, (0,0,1)Т } .

Здесь непрерывным решением является

_ (3к 1111 1111 ^

х = 1 — ;—,—,—; а;—,...,—; Ь2;—,—,—;1 I, где

^ 2 2 2 2 *2 2 2 2 2 )

Ъх = (1, 0, 0) , Ъ\ = Г2 . Целочисленное решение

в этом случае имеет вид:

г* = (к +1; 1,0,0; 1,0,0;.;Ъ2;1,0,0;1) .

Оценка мощности Ь-накрытия вытекает из (7) с учетом I = 2 и может быть записана следующим образом:

А)/4

3к-2 - 3 4

Заметим, что результаты, полученные для I = 1 и I = 2 , являются частными случаями оценки (7). С увеличением I мощность Ь-накрытий уменьшается и достигает наименьшего значения при I = к , поэтому случаи 1-3 можно объединить, и для них справедлива оценка (6).

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

Оптимальное решение задачи ЛП будет иметь вид:

~=(3к 111 1110

Х = [ 2 ;2,2,2;к;2,2,2;

Покажем, что это так. Рассмотрим допустимое решение х = (х0,...,хп) , хп = б, где бе (0,1]. Тогда вектор значений переменных, соответствующих первому блоку, ра-

1 1 1

2 Є,2,2

1 = (0,1,1)Т ,

111 'ї Т

2, 2 -Є, 2 I , если Т = (1,0,1) и будет сов-

в случае 1 = (1,1,0)Т .

(1 1 1

падать с I — —,-----б

{ 2 2 2

Остальные переменные останутся равными 1, а значение целевой функции не изменится:

х0 = | кк - 0 + (3-б)+б= 3 к = х0.

Но решение х Р х, следовательно, х -непрерывное решение. Отметим, что если к троек содержат не менее двух единиц, к = 2,., к , то в случае хп =б значение целевой функции уменьшится на величину (к - 1)б .

Оптимальное решение задачи ЦЛП имеет следующий вид: г = (к;1,0,0;...; 1,0,0;0) . В

противном случае, если рассмотреть другую допустимую целочисленную точку

г = (г0,...,гп) и положить гп = 1, то для г будет верно г0 = г* и г Р г*. Оценим мощность Ь-накрытия задачи в этом случае. Так как последняя переменная в оптимальных решениях задач ЛП и ЦЛП равна нулю, то ее можно исключить, уменьшив тем самым размерность задачи.

Следовательно, остается справедлива оценка типа (5) для .

Объединяя все рассмотренные случаи, получаем, что для мощности Ь-накрытия задачи (4) с матрицей выполнено неравенство (6).

Далее перейдем к рассмотрению более общего случая. Пусть матрица задачи об упаковке множества Огк состоит из к блоков и г столбцов в связующем блоке, к > г, к, г е N:

(

Б =

Б

Б

'Т’к

Т1

Тк

Т

тк

к+г Л

Б Тк

7-<к

и

где

Тк_____

п-'к

Т,2

п-'к

V1,3 У

Ткі є {0,1}, і = 1,2,3 ,

у = 1,...,к, к = 1,...,г . Далее Тк также будем называть тройкой у = 1,..., к, к = 1,..., г.

Теорема 2. Если в каждом столбце с номерами у = к +1,...,к + г имеется хотя бы одна тройка, в которой не менее двух единиц, то для мощности Ь-накрытий семейст-

вен

ва задач с матрицами Огк справедлива оценка типа (5).

Доказательство. Установим, что оптимальное решение задачи ЛП имеет вид:

~=(3к111 1110 0

х ^ 2 ; 2,2,2;к;2,2,2;

Отметим, что х7 = 0 , ] = 3к +1,.,п . Каждая переменная х7 для указанных у в некотором допустимом решении х независимо от остальных не может принимать значение б > 0 , это следует из рассуждений, приведенных для одного связующего столбца в доказательстве теоремы 1. К этим же рассуждениям сводится случай, когда в первом столбце две единицы стоят в тройке

7]1, во втором - в тройке Т22, в третьем -Т33 и т. д.

Пусть в матрице Огк, в столбцах /, 7 Е{3к +1,., п} содержится не менее двух единиц в тройках Т'?, . Если предполо-

жить, что х1 = 1 и х7 = 1, то вектор х становится недопустимым, две единицы в тройках с номером q обязательно совпадут

хотя бы в одной строке. Если обе переменные х1 и одновременно будут меньше

единицы, то х0 = х0 = к , но по-прежнему

х Р х . Аналогичные рассуждения справедливы для комбинаций переменных по три, четыре и т. д.

Оптимальное решение задачи ЦЛП имеет следующий вид:

г* = (к;1,0,0;...;1,0,0; 0,..,0).

Здесь х7 = 0 , 7 = 3к +1,.,п , так как если хотя бы одна из этих переменных приняла значение 1 , то для такой целочисленной допустимой точки г было бы верно х0 = х*

л *

и г Р г .

Теперь можно применить рассуждения, аналогичные доказательству теоремы 1, и получить оценку вида (5) для Огк .

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

)/Ь\

3к-г - 3 ,

>----------- , к > г .

8

В случае когда к = г , непрерывное и целочисленное решения совпадают и, следовательно, мощность Ь-накрытия равно нулю.

Доказательство. Не уменьшая общности, будем считать, что в первом столбце из связующего блока единица стоит в первой

тройке 1 , во втором столбце - во второй

тройке Т22 и т.д. Так как к > г, то строки, соответствующие тройкам с номерами г +1,...,г + к , заполнены нулями в связующем блоке.

Оптимальное решение задачи ЛП имеет следующий вид:

~ (3к г ,111 111, Л

х = 1-ъ —;Ъ,;Ъ2;...Ъ ;—,—,—;...;—,—,—;1,...,1 I,

V 2 2’ 1 25 г 2’2’2’ ’2’2’2” ’ У

а ЦЛП:

7* =(к + г;Ъ1;Ъ2;.Ъг;1,0,0;...;1,0,0;1,..,1) , где Ъ1 = Ту, у = 1,...,г .

Поскольку значения переменных с номерами у = 1,...,3г и у = 3к +1,...,п совпадают в оптимальных решениях задач ЛП и ЦЛП, то Ь-накрытие состоит в данном случае из всевозможных комбинаций значений переменных с номерами у = 3г + 1,...,3к , образующих допустимые точки. Отсюда вытекает оценка (8).

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

Об одном подклассе ЛР-трудных задач

Дальнейшее исследование семейства задач (1) —(3) с матрицей Бк привело к следующим результатам.

Лемма 1. Пусть имеются две невзвешенные задачи об упаковке множества (1)—(3) с

А 0'

матрицами Ащ, В,

гда справедливо неравенство

\и,(И)/Ц > |и.(А)/Ц + |и.(В)/Ц.

Доказательство. Обозначим оптимальные целочисленные решения задач с матрицами А , В , Н - г*А, г*в , г*н соответственно, а непрерывные решения - хА, хв, хн . Заметим, что хн = (хА, хв ) , гн = (г А, г в ) .

Оценим количество Ь-классов на целочисленных линиях уровня целевой функции от

Е = /(г*н) до Е = |^/(х*н )J . Заметим, что все Ь-классы на линиях уровня от Е = / (гА) до

Е = |_/(хА ^ и от Е = /(гВ) до Е = |_/(хВ)]

содержатся в множестве Ь-классов на лини-

от f _f (zH) до f _|_f (xH) J,

так

ях уровня

как Ь-структура многогранника инвариантна относительно сдвига на константы

п п

X(гВ )к и X(гА)к в пространстве.

к=1 к=1

Рассмотрим линию уровня целевой

функции Е = /(гН +1) =(/(гА)+1)+/(гВ), на

ней лежат точки (хрх2,..,хп1,(гВХ,...,(гВ)Пг), где х = (х1, х2 , к , х ) - это элемент

Ь-накрытия для задачи с матрицей А , такой что /(^,х2,...,х^) = /(гА) +1 ихе(0,1)п,

Ах < е . Аналогично значение целевой функции можно представить в виде

Е = /(гН+1) = /(гА)+(/(гВ)+1) и, соответственно, точки ((гA)1,к,(гA)n1,Xl', х2, • • •, х'п1 ) будут лежать на линии уровня Е = /(гн +1) , здесь х' = (х1,х2,...,х^) - элемент Ь-накрытия для задачи с матрицей В , такой что /(х1, х1,..., х’п2) = /(гВ ) +1 и х Е[0,1]п , Вх < е .

Так как дробное накрытие задачи с матрицей н содержит все Ь-классы из дробных накрытий задач с матрицами А и В и, кроме того, может содержать и другие Ь-классы, лежащие на линиях уровня со значением целевой функции из отрезка

F є

max

[7 ("A >J+f(z: l / (4 )j

L f (xB) J+f (zA) L J

то получаем оценку:

1^.(Н)/Ц > р*(А) /Ц +р.(В)/Ц .

Рассмотрим класс не взвешенных задач об упаковке множества (1)—(3) размерности п1 х ш1 с матрицами:

(А 0 ^

Нк =1 I, к є N

к V 0 Бку

где А = (ау), ау є {0,1}, і = 1,...,ш , у = 1,...,п , п1 = п + 3к , ш1 = ш + п .

Из леммы 1 и оценки (5) следует теорема 4.

Теорема 4. Для мощности Ь-накрытия задач из указанного класса справедлива оценка:

3к - 3

|U.(Hk)/L\ >:

8

Из теоремы 4 следует, что произвольную задачу об упаковке множества (1)-(3) можно

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

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

ЛИТЕРАТУРА

[1] Кристофидес Н. Теория графов. Алгоритмический подход. М. : Мир, 1978. 45 с.

[2] Borndorfer R. Aspects of set packing, partitioning, and covering. Ph.D. Dissertation. Technical University of Berlin, 1998.

[3] Сайко Л. А. Исследование мощности L-накрытий некоторых задач о покрытии // Дискретная оптимизация и анализ сложных систем. Новосибирск : ВЦ СОАН СССР, 1989. C. 76-97.

[4] Колоколов А. А., Рыбалка М. Ф. Исследование и решение задачи об упаковке множества блочной структуры // Динамика систем, механизмов и машин : матер. VII Междунар. науч.-техн. конф. Омск : Изд-во ОмГТУ, 2009. Кн. 3. С. 55-59.

[5] Колоколов А. А., Рыбалка М. Ф. Анализ и решение одного класса задач об упаковке множества // Дискретная оптимизация и исследование операций : матер. Российской конф. Новосибирск: Изд-во Института математики, 2010. С. 95.

[6] Рыбалка М. Ф. Анализ некоторых алгоритмов для задачи об упаковке множества с матрицей блочной структуры // Методы оптимизации и их приложения : труды XV Байкальской междунар. школы-семинара. Иркутск, 2011. Т. 4. С.197-202.

[7] Авербах И. Л., Цурков В. И. Целочисленные оптимизационные модели блочного типа // Математическое моделирование. 1990. T. 2. № 2. С. 39-57.

[8] Щербина О. А. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // ЖВМ и МФ. 1986. Т. 26. № 9. С. 1339-1349.

[9] Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. 1994. Т. 1. № 2. C. 18-39.

[10] Колоколов А.А., Девятерикова М.В., Заозер-ская Л.А. Регулярные разбиения в целочисленном программировании : учебное пособие. Омск : Изд-во Ом. гос. ун-та, 2007. 60 с.