Комбинаторные условия фасетности опорных неравенств

Р.Ю. Симанчев, Омский государственный университет, кафедра математического моделирования

Пусть E- конечное множество, H- некоторое семейство его подмножеств. Мы будем рассматривать комбинаторно полные семейства, то есть семейства H, удовлетворяющие следующим аксиомам:

1) для любого eE найдутся такие H1H и H2H, что eH1\H2;

2) для любых e1, e2E найдется такой HH, что e1H и e2H.

Сопоставим множеству E E-мерное евклидово пространство RE посредством взаимнооднозначного соответствия между E и множеством координатных осей пространства RE. Иными словами, RE можно мыслить как пространство вектор-столбцов, координаты которых индексированы элементами множества E. Для каждого R E определим его вектор инциденций xRRE как вектор с компонентами xeR = 1 при eR, xeR=0 при eR. Таким образом, множеству всех подмножеств множества E ставится во взаимнооднозначное соответствие множество всех вершин единичного куба в RE. На основании этого соответствия в дальнейшем там, где это не вызовет недоразумений, (0,1)-вектор xRE будем одновременно понимать как подмножество множества E.

Нас будет интересовать следующий многогранник, ассоциированный с семейством H,

PH = conv{ xH RE | H H }.

Перечислим некоторые очевидные свойства многогранника PH.

1) Каждая вершина многогранника PH является (0,1)-вектором. 2) Вершины и только они соответствуют множествам семейства H. 3) Многогранник PH не имеет целочисленных точек, отличных от вершин.

Пусть aRE, a0R. Линейное неравенство aTxa0 называется опорным к многограннику P(H), если aTxa0 для любого xP(H). Всякое опорное неравенство порождает грань многогранника (возможно несобственную). Максимальные по включению грани называются фасетами, а порождающие их опорные неравенства, соответственно, - фасетными. Принципиальная роль фасетных неравенств обуславливается, во-первых, тем, что они присутствуют в любой линейной системе, описывающей многогранник, во-вторых, эффективность их использования в качестве отсечений при решении соответствующих экстремальных комбинаторных задач (см., например, [3]).

В настоящей работе получены достаточные условия фасетности опорного неравенства, имеющие комбинаторную природу.

Через aff P(H) обозначим аффинную оболочку многогранника P(H). Как известно, существуют такие матрица A и вектор-столбец , что

aff P(H)={xRE | ATx =  }.

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

Каждая строка матрицы A соответствует ровно одному элементу eE и наоборот. Поэтому множество строк матрицы A будем обозначать через E. Множество столбцов обозначим буквой V. Ясно, что rankA=VE. Положим V=n. Согласно введенным обозначениям, для коэффициента матрицы A, находящегося в строке eE и столбце uV, будем использовать запись aeu. Обозначим через Ve множество столбцов матрицы A, имеющих в строке e ненулевой элемент. Для S E положим VS =eSVe. Если cRE, то через (cA) (соответственно, (Ac)) обозначим матрицу, полученную приписыванием к матрице A слева (соответственно, справа) столбца c, а через D(c,E) подматрицу матрицы (cA), образованную строками E~E.

Пусть cTx  c0 - опорное к P(H) неравенство. Нам понадобятся следующие определения.

Непустое множество SE будем называть cH-множеством, если существуют такие H1,H2H, что 1) S=(H1\H2)(H2\H1) и 2) cTxH1 = cTxH2 = c0;

Будем говорить, что элемент e0E является cH-следствием некоторого множества E~E, если существует такое упорядоченное множество e1, e2, ... ,et = e0, что для любого i{1,2,,t} элемент ei принадлежит некоторому cH-множеству, лежащему в E~{e1,e2,,ei} .

Лемма. Пусть affP(H)={xRE|ATx=}RE и SE - cH-множество. Тогда для каждого uVS имеет место соотношение eS\H2 aeu = eS\H1 aeu, где H1,H2H - из определения cH-множества.

Доказательство. Пусть aTx=u - соответствующее уравнение из системы, определяющей аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов xH1 и xH2. Заметим также, что S\H2 = H1\H2 и S\H1=H2\H1. Теперь 0 = aTxH1-aTxH2 = aT(xH1-xH2) = aT(xH1\H2 - xH2\H1) = aTxS\H2 - aTxS\H1 =eS\H2 aeu = eS\H1 aeu. Теорема. Пусть cTx c0 - опорное к P(H) неравенство, F={xP(H) | cTx = c0}. Для того, чтобы грань F являлась фасетой многогранника P(H), достаточно существования такого E~E, что 1) E~=n+1; 2) всякое eE \ E~ является cH-следствием множества E~; 3) матрица D(c,E~) имеет полный ранг.

Доказательство. Пусть bTx b0 - опорное к P(H) неравенство, удовлетворяющее условию

{xP(H) | cTx = c0}  {xP(H) | bTx = b0} .

(1)

Покажем, что тогда система линейных уравнений

c + A = b

(2)

относительно неизвестных mR и lRn совместна, причем   0. Очевидно, что в этом случае будет также иметь место равенство b0 = c0 +T. Как известно, из совместности системы (2) следует, что грань F, индуцированная неравенством cTx c0, является фасетой многогранника P(H) (см. [1])

Всякое уравнение системы (2) соответствует единственному eE. Обозначим ее уравнения через (e), eE, имея ввиду и правые, и левые их части, то есть (e): ce+uV aeuu = be.

Пусть SE - cH-множество и H1,H2H - множества, указанные в соответствующем определении. По определению cTxH1 = cTxH2 = c0. Следовательно,

0 = cTxH1 - cTxH2 = cT(xH1 - xH2) = cT(xS\H2 - xS\H1) = cTxS\H2 - cTxS\H1 =eS\H2 be - eS\H1 be

(3)

Так как, в силу (1), bTxH1 = bTxH2 = b0, то из аналогичных выкладок получаем

eS\H2 be - eS\H1 be= 0

(4)

Заметим, что в предыдущей лемме фигурирует такая же, как в (3) и (4), комбинация элементов в остальных столбцах системы (2). Таким образом, сумма строк S\H2 минус сумма строк S\H1 в матрице (cAb) дает нулевую строку. Значит, уравнения (e), eS связаны следующим линейным соотношением:

eS\H2 (e) - eS\H1 (e) = 0

(5)

что означает их линейную зависимость. Поэтому, если SE является cH-множеством, то любое одно уравнение из семейства {(e), eS} может быть отброшено из системы (2) без ущерба для ее совместности.

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

D(c,E~)-=b~

(6)

где b~ = (be : eE~), - = (,T)TRn+1, эквивалентна системе (2). Иными словами, покажем, что всякое уравнение (e) при eE \ E~ может быть отброшено из системы (2). Индукцию проведем по числу элементов в упорядоченном множестве {e1, e2, ,et} , необходимом для того, чтобы элемент etE \ E~ являлся cH-следствием множества E~, то есть по числу t. Если t=1, то, как показано, из (5) следует, что (e) может быть отброшено из системы (2). Пусть EE \ E~ - множество таких cH-следствий множества E~, для которых существует упорядоченное множество длины не более чем t, и пусть уравнения (e) при eE могут быть отброшены из системы (2). Возьмем e*E \ (E~E), для которого длина соответствующего упорядоченного множества равна t+1. По условию теоремы, существует такое cH-множество S, содержащее e*, что S \{e*}  E~E. Тогда, в силу (5), (e*) является линейной комбинацией уравнений (e), eS \ {e} , каждое из которых, по индукционному предположению, является линейной комбинацией уравнений (e), eE~.

Таким образом, действительно, системы (6) и (2) эквивалентны.

По условию теоремы, rank D(c,E~) = E~ = n+1. Следовательно, ранг расширенной матрицы системы (6) равен рангу основной. Значит, система (6), а вместе с ней и система (2), совместны. При этом решение системы (2) нетривиально, ибо в противном случае b = o.

Остается показать, что   0. Так как cTx  c0 опорно к P(H), то существуют такие x1,x2H, что cTx1 = c0 и cTx2c0. Тогда, в силу (1), bTx1 = b0 и bTx2  b0. Отсюда

0  bT(x1-x2) = (cT +TAT)(x1-x2) = (cTx1-cTx2) + T - T

Так как cTx1cTx2, то   0. Отметим, что в общем случае приводимая здесь техника является достаточно громоздкой. Однако конкретизация семейства H, аффинной оболочки соответствующего многогранника и самого опорного неравенства позволяет получать конструктивные результаты. Так, например, в [2] посредством данной техники описаны три класса ранговых неравенств, индуцирующих фасеты многогранника связных k-факторов полного графа.

Список литературы

Схрейвер А. Теория линейного и целочисленного программирования: В 2 т. М.: Мир, 1991.

Симанчев Р.Ю. О ранговых неравенствах, порождающих фасеты многогранника связных k-факторов // Дискретный анализ и исследование операций. 1996. Т.3. N 3. С.84-110.

Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Mathematical Programming. 1991. N 51. P. 141-202.