Структурные и алгоритмические свойства мультипотоков и расширений конечных метрик

I Задача, о допустимом мультипотоке (ЗДМ).

1 Задача для общей сети.19.

2 Задача для плоских сетей .25.

3 Задача о двух путях .28.

II Задача о максимальном мультипотоке (ЗММ) и смежные задачи.

1 ЗММ с разрезно-обусловленньши схемами.30.

2 Задача о запирании разрезов, метрическая мультипотоковая задача и бисуб-модулярные многогранники.34.

3 Результаты о дробности ЗММ и ЗММ*.39.

Ш Задача о максимальном мультипотоке минимальной стоимости (ЗМС) и ее целочисленная версия.

1 Полуцелочисленные оптимальные решения ЗМС с полной многодольной схемой 42.

2 Случаи неограниченной дробности ЗМС и труднорешаемости ЦЗМС.46.

3 Эффективная разрешимость ЦЗМС с полной многодольной схемой.47.

4 (Т,(1)-соедииения минимального веса.50.

IV Задачи об упаковках полуметрик.

1 Реализация расстояний путем упаковки разрезных полуметрик .53.

2 Упаковки разрезных и (2,3)-полуметрик, реализующие расстояния.58.

3 Максимальные упаковки разрезов и MFMC-свойства.60.

V Задача о минимальном О-расширении метрики. Примитивные расширения конечных метрик.

1 Описание класса минимизируемых метрик в ЗМНР.64.

2 Труднорешаемые случаи ЗМНР.71.

3 Орбитно-аддитивные модулярные метрики и метод распараллеливания для ЗМНР .72.

4 Примитивно-конечные метрики и связь с мультипотоками.76.

VI Приложение. Сепарабельная выпуклая минимизация над унимодулярным линейным пространством и ее приложения.

1 Постановка задачи, частные случаи и источники методов.80.

2 Общий метод минимального среднего цикла (ММСЦ).82.

3 Метод агрегированных сокращений (MAC).85.

4 Обзор результатов.85.

Список работ по теме диссертации.88.

Цитированная литература.91.

О.

Введение

.

Основный результаты диссертации излагаются в разделах I-V. Ниже мы вводим или напоминаем базовые понятия, формулируем основные рассматриваемые задачи, уточняем про,-блематику, касаемся источниковых аспектов и даем краткий очерк содержания.

Мультипотоки и задачи о них. Разделы I-III посвящены изложению результатов о мультипотоках в неориентированных сетях, или неориентированных мультипотоках. Далее эпитет «неориентированный» мы будем опускать.

Исходными объектами являются потоковая сеть (G, с), состоящая из конечного графа G = (V, Е) и неотрицательной целочисленной функции с: Е —> Z+ пропускных способао-стсй ребер, и подмножество U неупорядоченных пар вершин в G, которые предполагается соединить потоками. Граф Н = (Т, U), порожденный этими парами, называют (потоковой) схемой, или графом продуктов, а его вершины — полюсами сети. Для краткости неупорядоченная пара {ж, у} вершин обозначается ху. В комбинаторной оптимизации обычно придерживаются определения мультипотока в форме (взвешенной) упаковки путей. [Для рассматриваемых задач это эквивалентно используемому в теории сетей определению мультипотока как совокупности двухполюсных потоков, заданных в виде функций на направленных ребрах, см. [FF]. ] Более точно, обозначим V3t (G) множество простых путей в G, соединяющих вершины s я 1, ii Н) — объединение этих множеств по всем парам st € U. Мультипоток в сети (С, с) со схемой Н — это неотрицательная вещественная функция /: P (G, Н) —" R+, удовлетворяющая ограничениям, но пропускным способностям.

0.1) С7(е) := ХХЯР) е Р 6 < Ф) Для всех ребер с е Е.

Ограничение / на подмножество Tst (G) (siе U) понимается как поток fst мощности va. l (/.,() := ^(/(Р): Р? Tst{G)) между полюсами s и I. Сумма мощностей потоков считается общей мощностью мультипотока / и обозначается val (/). Наиболее распространены три тина мультипотоковых задач.

ЗДМ) Задача о допустимом, мультипотокс. Для заданной функции d: U —" Z+ (требований на мощности потоков) найти мультипоток удовлетворяющий val (/,() = d (st) для всех st g U (или выяснить, что такого / не существует).

ЗММ) Задача о максимальном мультипотокс. Найти мультипоток максимальной общей мощности, или максимальный мультипоток.

ЗМС) Задача о максимальном мультинотоке минимальной стоимости: Для заданной функции а: Е Z+ (уделышх. стоимостей ребер) найти максимальный мультипоток /, имеющий минимальную общую стоимость 53(я (е)С^(е) :е? Е).

Эти задачи вместе с их целочисленными усилениями (задачами о целочисленных упаковках путей) обобщают классические задачи о допустимом потоке, о максимальном потоке и о максимальном потоке минимальной стоимости для неориентированных сетей. [Теория, методы решения и приложения однопродуктовых потоковых задач, включая варианты транспортной задачи [Кап], представлены в [FF, ADK, EKK, GTT, AMO] и многих других монографиях и обзорах. В литературе рассматриваются и более общие многопродуктовые транспортные модели, чем указанные вышесм., например, [GY, Ro2]. ].

Эквивалентное представление потоков как функций на направленных ребрах позволяет записать ЗДМ, ЗММ и ЗМС в виде задач линейного программирования с «компактной» матрицей ограничений размера 0(|V||C/| + |Е|) хО (|С/||?|) с коэффициентами 0, 1, -1. Поэтому задачи решаются в сильнополиномиальное время с помощью усиленной версии [Та] метода эллипсоидов [Kh], К ним также применимы достаточно эффективные практически сетевые модификации симплекс-методов (см., например, [АМО]).

Нас, однако, интересует возможность создания более эффективных «комбинаторных» методов при фиксированных потоковых схемах Н и получение точных решений с малыми знаменателями в тех случаях, когда их существование гарантировано теорией (аппарат линейного программирования для этого недостаточен). Обозначим ЗДМ (Я) множество (класс) частных задач о допустимом мультипотоке при фиксированной схеме Я и произвольных G, с, d, и аналогично для ЗММ и ЗМС. Основные направления наших исследований мультипотоковых и других задач сфокусированы на четырех проблемах. Мы формулируем их в общем виде.

Основная проблематика. Пусть 1С — некоторый класс задач («массовая задача») о допустимости: найти элемент в заданном (быть может, неявно) множестве 5 С R", или оптимизации: максимизировать или минимизировать заданную функцию </:?—> R. Для рационального вектора х 6 Q" обозначим <�р (х) наименьшее общее кратное знаменателей его компонент. Для частной задачи Р € К обозначим у (Р) минимум чисел f (x) среди всех допустимых (соответственно, оптимальных) рациональных решений х, полагая <�р{Р) := О, если таких решений не существует. Наконец, обозначим <�р (1С) максимум чисел ip (P) по всем задачам Р 6 1С, полагая <�р (К) := оо, если эти числа не ограничены сверху. Величина ifi называется дробностью (вектора, задачи или класса задач). Первая из изучаемых проблем — проблема дробности — заключается в определении или, по крайней мере, нетривиальном оценивании сверху значения tp (K).

В этих терминах класс абсолютно целочисленных задач линейного программирования имеет дробность 1. Поскольку этот класс включает стандартные потоковые задачи, поставленные мультипотоковые задачи имеют дробность 1 при |?/| = 1 (или Я ~ Кг), а ЗММ и ЗМС — даже при Н ~ А", 1 Г (ввиду сведения к многополюсным однопродуктовым задачам). Уже в случае U = 2 целочисленные решения не гарантированы, однако Ху [Ни] показал существование полуцелочисленных решений для неориентированных двухпродуктовых задач о допустимости и максимальности, из чего следует у (ЗДМ (Я)) = <�р (ЗММ (Я)) = 2 для Я ~ Ki 4- К2- Здесь и далее Г + Г' обозначает объединение непересекающихся графов Г и Г', КТ — полный граф с г вершинами, Кяг — полный двудольный граф с долями из q и г вершин, и ~ обозначает изоморфные графы. [В комбинаторной оптимизации существование целочисленных и полуцелочисленных решений было установлено для целого ряда содержательных задачнапример, ip = 1 для задачи об упаковке корневых ветвлений в орграфе [Ed2], и <р = 2 для линейных релаксаций задач о максимальном паросочетании и о максимальной клике. В то же время для многих известных задач проблема дробности остается открытой. Такими, например, являются релаксации задач о точном покрытии ребер графа простыми циклами и о точном покрытии регулярного графа совершенными паросо-четаниями, для которых гипотезы Фалкерсона-Сеймура и Вержа предполагают дробность 2 (см. [Se2,Se3]).].

Вторая проблема касается возможности эффективного построения допустимых и оптимальных решений, дробность которых отвечает дробности класса. Общие методы такого рода не известны даже в области задач линейного программирования, и известные эффективные алгоритмы для содержательных классов задач, как правило, весьма нетривиальны и используют средства комбинаторного характера.

Третья проблема (усиливающая предыдущую при <�р (1С) > 1) связана с возможностью эффективного нахождения оптимального целочисленного решения. В комбинаторной оптимизации целочисленные задачи являются наиболее распространеными, и вопрос об их слож-ностном статусе (в смысле полиномиальной разрешимости или NP-трудности) занимает центральное место.

Для рассматриваемых мультипотоковых задач нам удается определить значения дробности и построить эффективные комбинаторные алгоритмы для широких классов потоковых схем, а в случае ЗМС — решить проблему дробности и определить сложностной статус целочисленной стоимостной задачи для всех потоковых схем. [Отметим, что аналогичные ориентированные многопродуктовые потоковые задачи имеют существенно более бедные свойства с точки зрения указанных проблем. Например, для общих орсетей задача о допустимом мультипотоке имеет дробность оо, а соответствующая целочисленная задача — NP-трудная, если потоковая схема не является односторонне ориентированной звездой (в противном случае задача эквивалентна однопродуктовой и имеет дробность 1). Для некоторых частных случаев орсетей все же получены нетривиальные комбинаторные результатыодин из них будет указан в разделе П.].

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

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

Метрики, метрические расширения и задачи о них. Напомним, что полуметрика на множестве V — это функция т: V х V —> R+, устанавливающая расстояния на парах элементов (точек) в V, удовлетворяющие: (i) т (х, х) = 0, (ii) т (х, у) = т (у,-х) (симметрия), и (iii) т (х, у) m (y, z) > т (х, z) (неравенство треугольника), для всех x, y, z 6 V. Учитывая (i) и (ii), расстояние между точками г и у может обозначаться т (ху), и т определяется своими значениями на множестве неупорядоченных нар различных элементов в.

V. Поэтому m отождествляют с соответствующим вектором эвклидова пространства RW (координаты которого индексируются элементами в (j)). Множество Mv полуметрик на V образует выпуклый замкнутый многогранный конус в К.(=), называемый полуметрическим конусом. Если т (ху) > 0 при х ф у, то т называется метрикой. Мы не делаем различий между (полу)метрикой т на V и (полу)метрическим пространством (V, т), и называем т конечной, если множество V конечное.

Связный граф G = (V, Е) с функцией I: Е —" R+ длин ребер порождает полуметрику distG'' на V, в которой расстояние между вершинами х, у равно длине кратчайшего пути, соединяющего эти вершины. При (.= I получаем метрику графа G, обозначаемую distG. Разрезная полуметрика ру определяется собственным подмножеством X С V (или разбиением {X, V — X}) и устанавливает расстояние 0 на парах в X и на парах в V — X, и расстояние 1 — на остальных парах в V.

Говорят, что т е Mv — расширение р? Мт, если существует инъективное отображение сг: Ту V, при котором n (st) = tn (<7(s).

Всякая полуметрика m? Mv является О-расширением некоторой метрики х. А именно: максимальные подмножества X С V с нулевыми расстояниями для всех х, у? X (называемые 0-множествами) образуют разбиение V, и fi есть полуметрика на подмножестве Т С V, содержащем ровно один элемент из каждого О-множества. Разрезная полуметрика имеет два О-множества и является О-расширением метрики простейшего графа Ki.

Мы будем рассматривать ряд задач о конечных метриках и их расширениях. Часть из них представляет специальные случаи общей задачи минимизации неотрицательной линейной функции над полуметриками заданного вида:

0.2) Для конечного множества V, функции с: -«¦ Z+ и (неявно заданного) конечного семейства П полуметрик на V, найти m? Q с минимальной величиной с ¦ т.

Здесь и далее a ¦ Ь обозначает скалярное произведение a (e)b (e) числовых функций a, b на общей части S их областей определений. В частности, задача (0.2) для определенных семейств П возникает по линейной двойственности в связи с задачами о допустимых и максимальных мультипотоках. В разделе V исследуется (0.2) следующего типа:

ЗМНР) Задача о минимальном О-расишрении: Для конечного метрического пространства (Т, р.), конечного множества V Э Г и функции с: (?) —> R+ найти 0-расширение m? Ext°(/x, V) с минимальным с — т.

Эта задача эквивалентна известной версии задачи о размещении оборудования, см. [TFL]. В последней Т— это множество пунктов, предназначенных для размещения заводов (или единиц оборудования) Qi,. ., Qjvв одном пункте может размещаться несколько заводов. Для каждой пары Qj) задано число dj > 0, выражающее предполагаемый объем обмена продукцией (или степень взаимодействия). Заводы Qi, ¦ ¦ ¦, Qk уже размещены в пункта! х 7(1),., 7(fc) 6 Т, и надо разместить оставшиеся, минимизируя ожидаемые «транспортные издержки». Формально: продлить у до отображения у: {l,., iV} —> Т с минимальной величиной Y2(cijlli7(>)т0)): 1 < ' < j < №)• Можно привести и другие содержательные интерпретации ЗМНР (например, задача минимизации общей длины проводов при размещении электрической схемы на плате).

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

ЗМР) Задача о минимальном расширении: Для V, c как выше минимизировать с — m среди всех расширений m 6 Ext (/<, V).

В разделе IV исследуются задачи об упаковках разрезных и иных полуметрик. Начало рассмотрению задач такого рода (в терминах упаковок разрезов) было положено работами Эдмондса, Джонсона и Сеймура [EJ, Sel, Se7]. В этих задачах основными объектами являются связный граф G = (V, Е) с длинами (¦(е) 6 Z+ ребер е 6 Е и некоторое конечное множество О С A4v. Обычно Q задается неявно указадием вида полуметрикнапример, Г2 — множество разрезных полуметрик на V. (Взвешенная) упаковка Q в (G, t) — это функция Л: Q —> R+, удовлетворяющая.

0.3) Лп, Л© < f.(e) для всех eG Е, где ЛП, А обозначает полуметрику ?](A (ni)m: гп 6 fi). Из (0.3) следует Ла, х (<�су) < distG, f (3-ji/) для всех я',-/ 6 V. Одна из рассматриваемых задач, имеющая полярно-двойственную связь с задачей о допустимом мультипотоке, формулируется так.

ЗРР) Задача о реализации расстоят-й: Для G, I, SI и подмножества U С [) найти упаковку А, реализующую расстояния дл я всех пар si. € V, т. е. удовлетворяющую.

0.4) Лп’Л (я") = <Шй°''(«4) для всех st е f/, или выяснить, что такого Л не существует).

Если U = (j), то ЗРР превращается в задачу разложения полу метрики dist13^ в неотрицательную линейную комбинацию (н.л.к.) полуметрик из S2. При изучении ЗРР и других задач об упаковках полуметрик центральными вопросами будут по-прежнему вопросы, дробности, эффективной алгоритмической разрешимости и специальной двойственности.

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

Для целого ряда подклассов задач с доказываемой дробностью 2 будет установлена усиленная полуцелочисленность — существование целочисленных решений в случае, когда числовые функции (пропускных способностей, требований, длин) обладают свойством т.н. парности, означающим четность весов определенных коциклов (в матроидном смысле). Феномен усиленной полуцелочисленности для задач на допустимость связывается с тем обстоятельством, что некоторая ассоциированная система векторов образует Гильбертов базис. [В теории векторных решеток конечное множество X С Q™ рациональных векторов называют Гильбертовым базисом, если их неотрицательная целочисленная оболочка совпадает с пересечением конической и целочисленной оболочек: Z+(X) = R+(Jf) П Z (X) — см., например, [Schl, DL]. ] В случае стоимостной мультипотоковой задачи природа полуцелочисленности будет иной.

Краткий обзор содержания по разделам. Раздел I посвящен задаче о допустимом мультипотоке. Известно, что множество разрешимых задач при фиксированном V представляется в виде конуса, полярного полуметрическому конусу MvПоэтому критерий разрешимости ЗДМ для общих сетей и схем состоит в выполнении линейных неравенств относительно полуметрик HaV, а именно, с-тп> d-m.fi ля всехпг6>1л. При фиксированной схеме Я разрешимость задачи гарантируется выполнением неравенств для полуметрик, лежащих на крайних лучах определенного надконуса Mv', они называются Н-экстремальными полуметриками, или препятствиями для ЗДМ (Н). Хорошо известным случаем препятствий являются разрезные полуметрикидля них неравенство эквивалентно разрезному условию: общая пропускная способность ребер между X С V и V — X должна быть не менее суммы требований на потоки между этими множествами. На актуальный в 70-е годы вопрос, для каких схем // препятствиями служат только разрезные полуметрики, полный ответ был дан Паперновым: ими являются К" 4, С5 (цикл на 5 вершинах) и объединение двух звезд. Позднее было установлено, что в этих случаях для эйлеровых (с, d) разрешимая задача имеет целочисленное решение (эйлеровость соответствует условию парности для ЗДМ). С другой стороны Ломоносов показал, что ^(ЗДМ (Н')) = оо, если Н имеет три попарно несмежных ребра.

Мы рассматриваем все оставшиеся случаи схем Н. Это: (a) ft'5, (б) объединение Л'3 и звезды, © Л'з 4- Л’д. Для этих Н мы описываем множества препятствий и устанавливаем специальные критерии разрешимости ЗДМ (//). В случаях (а) и (б) неразрезными препятствиями оказываются (2,3)-полуметрики (О-расширения метрики графа Кг, з)> дробность ЗДМ (Я) равна 2, и имеется сильнополиномиальный комбинаторный алгоритм нахождения полуцелочисленного решения. В случае © имеются и более сложные препятствия.

Далее в разделе рассматривается популярный случай плоской сети (G, c) и схемы Л, ребра которой (пары «источник-сток») лежат в к гранях G. Окамура [Ok] показала раз-рганость всех препятствий и полуцелочисленность при к < 2. Мы описываем множества препятствий и решаем проблему дробности для случаев к = 3 и к = 4, а также выясняем, что уже при к = 5 множество препятствий становится «плохо структурированным». Так при к = 3 неразрезными препятствиями оказываются (2,3)-полуметрики, и дробность равна 2, а при к = 4 появляется дополнительная серия препятствий, и дробность становится равной 4. В заключительном параграфе решается целочисленная двухпродуктовая задача с единичными требованиями.

Результаты о дробности 2 показываются в форме усиленной полуцелочисленности: для эйлеровых (с, с () разрешимая ЗДМ имеет целочисленное решение, а для случая плоского G и к = 4 доказывается усиленная четвертьцелочисленность. В основе доказательств и алгоритмов лежит идея т.н. вилочной декомпозиции — последовательности определенных эквивалентных преобразований, упрощающих сеть.

Раздел // посвящен задаче о максимальном мультипотоке. Здесь по сравнению с ЗДМ классы потоковых схем, обеспечивающих хорошие структурные свойства задачи, оказы^ вается значительно шире. Наш подход к ЗММ базируются на углубленном исследовании двойственной задачи ЗММ* (являющейся специальным случаем (0.2)).

Мы обобщаем на произвольную дробность базовый результат Эдмондса и Джайлса. [EG] о тотально двойственно-целочисленных системах. Из обобщения следует, что дробность ЗММ не меньше дробности двойственной задачи. Это дает неравенство 9?(ЗММ (Я)) > (,?(ЗММ*(Я)) для каждой схемы Я. В частности, неограниченная дробность ЗММ*(Я) влечет неограниченную дробность ЗММ (Я). Мы устанавливаем точные значения у (ЗММ*(Я)) для всех схем Явозможными значениями служат 1, 2, 4, оо. Классы схем Я, обеспечивающих двойственную дробность 1,2,4 оказываются весьма широкими, и для них мы описываем структуру специальных оптимальных двойственных решений. Это дает комбинаторные теоремы двойственности для ЗММ (Я).

Важным типом специального двойственного решения является неотрицательная линейная комбинация разрезных полуметрик. Схемы Я, для которых каждая частная задача в ЗММ (Я) имеет оптимальное двойственное решение такого вида, называются разрезно-обусловлснпыми, или РО-схемами. Нам удается полностью описать этот класс схем: Я является РО-схемой т. и т. т., когда каждая вершина Я принадлежит не более двум апти-кликам. Показывается, что <�р (ЗММ (Я)) для РО-схемы Я равно 1, 2 или 4 (с уточнением, какие именно схемы дают эти значения дробности), и предлагается с. ильнополиномиаль-ный комбинаторный алгоритм нахождения оптимальных полуи четвертьцелочислепных решений. .Алгоритм основан на технике вилочной декомпозиции, и для эффективных проверок корректности при декомпозиции используется сведении двойственной задачи к задаче о минимальном разрезе в расширенной сети. Другой предлагаемый эффективный метод решения использует выявленную связь с задачей на обобщениях полиматроидов.

Завершая исследование прямых задач с полуцелочисленными оптимальными решениями, мы показываем, что за пределами класса РО-схем имеется всего одна схема Я, для которой уз (ЗММ (Я)) = 2, а именно, Н ~ К2 4- /1″ з, и предлагаем эффективный комбинаторный алгоритм для эч’ого случая.

Аналогично ЗДМ, в случаях дробности 2 в действительности доказывается свойство усиленной полуцелочисленности.