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

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

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

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

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


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=(H1H2)(H2H1)   и  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SH2 aeu
= eSH1 aeu, где H1,H2H - из определения cH-множества.

Доказательство.
Пусть aTx=u - соответствующее уравнение из системы, определяющей
аффинную оболочку многогранника P(H). Ясно, что оно справедливо и для векторов
xH1 и xH2. Заметим также, что SH2 = H1H2 и SH1=H2H1. Теперь 0 = aTxH1-aTxH2
= aT(xH1-xH2) = aT(xH1H2 - xH2H1) = aTxSH2 - aTxSH1 =eSH2 aeu
= eSH1 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(xSH2 - xSH1) = cTxSH2 - cTxSH1 =eSH2
be - eSH1 be





(3)






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




eSH2 be - eSH1 be= 0





(4)






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




eSH2 (e) - eSH1 (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.

Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/