Исследуется вопрос о разрешимости задач дискретной оптимизации алгоритмом покоординатного подъема (жадным алгоритмом). Цели диссертации: нахождение условий точности и оценок погрешности алгоритма, отыскание классов задач, разрешимых им с приемлемой (например, константной) точностью, выявление свойств множества допустимых решений, влияющих на точность алгоритма.
Рассматриваются две основные задачи: задача целочисленного программирования с линейным целевым функционалом и задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Также рассматриваются задача максимизации аддитивного функционала на семействе множеств, задача о длиннейшем пути в специальной постановке, задача коммивояжера и одна обобщенная задача коммивояжера.
Для решения данных задач предлагается использовать алгоритм, действующий по схеме покоординатного подъема с единичным шагом. Алгоритм начинает работу с некоторого начального решения (например, нулевого вектора) и на каждом шаге увеличивает на единицу одну из компонент текущего решения таким образом, чтобы целевой функционал имел максимально возможное приращение.
Идея алгоритма настолько проста и естественна, что невозможно проследить, кто первым ее придумал. Исследования алгоритма проводились еще в 1920;е годы [17]. В последние десятилетия интерес к теме алгоритмов типа покоординатного подъема во многом обусловлен следующими факторами.
Во-первых, анализ подобных быстрых алгоритмов способствует нахождению новых классов задач, эффективно разрешимых с приемлемой точностью. Это представляется: довольно целесообразным, поскольку для большинства задач дискретной оптимизации скорее всего не существует точных эффективных алгоритмов, что связано с фундаментальной проблемой соотношения классов Р и NP [5].
Во-вторых, несмотря на свою простоту, во многих случаях жадные алгоритмы имеют максимальную точность в классе полиномиальных алгоритмов [31] либо являются асимптотически точными алгоритмами [2, 12].
И, наконец, вопрос точности алгоритмов типа покоординатного подъема имеет глубинные связи с бурно развивающимися теориями матро-идов и субмодулярных функций. А именно, очень часто точность жадного алгоритма свидетельствует о наличии некоторых важных с точки зрения комбинаторного анализа свойств множества допустимых решений [14, 24].
В настоящее время имеются три наиболее распространенных подхода к анализу жадных алгоритмов.
Первый из них основан на вычислительном эксперименте, использующем тестовые примеры индивидуальных задач. Во многих случаях это единственный способ проверить качество предложенного алгоритма и провести сравнение с другими алгоритмами.
Второй подход — это анализ алгоритма в худшем случае. Данный подход предусматривает нахождение условий точности и оценок погрешности алгоритма, справедливых для всех индивидуальных задач.
Третий подход — это вероятностный анализ алгоритма: предполагается, что на множестве индивидуальных задач задано некоторое вероятностное распределение, после чего оцениваются математическое ожидание и дисперсия погрешности алгоритма,
В диссертации рассматривается второй подход, т. е. проводится анализ алгоритма покоординатного подъема в худшем случае.
Приведем математические формулировки исследуемых задач и дадим краткий обзор основных известных результатов, связанных с разрешимостью этих задач жадными алгоритмами.
Максимизация аддитивного функционала. Наиболее известные результаты относятся к задаче максимизации аддитивного функционала на семействе множеств. Пусть I — конечное множество, ю — вещественная функция на множестве 1 ж Т — некоторое семейство подмножеств множества I. Требуется максимизировать функционал w (F) =? w (i) ieF при условии F? Т. В другой постановке вместо условия F? Т рассматривается условие F? где В (Т) — семейство максимальных по включению множеств из Т (такие множества называются базами семейства Т).
Алгоритм покоординатного подъема в данном случае имеет следующий вид: алгоритм начинает работу с пустого множества, А и на каждом шаге добавляет к множеству, А элемент г? / — А такой, что A U г? Т и w (г) = max{w (j)| j? I — A, A U j? j27}- если A U j ^ Т при всех j? / — А, то алгоритм заканчивает работу.
Теорема Радо-Эдмондса. Семейство множеств Jназывается системой независимости, если выполнено условие монотонности вниз: из того, что, А С В и В Е Т, следует, А? Т. Система независимости Т называется матроидом, если при любом, А С I базы семейства Та — {F? Т F С Л} имеют одинаковую мощность, Радо [43, 44] установил следующий факт.
Задача максимизации аддитивного функционала на множестве баз матроида разрешима алгоритмом покоординатного подъема.
Эдмондс [24] усилил данный результат до следующего вида.
Задача максимизации аддитивного функционала на множестве баз системы независимости разрешима алгоритмом покоординатного подъема тогда и только тогда, когда данная система является матроидом.
Теорема Радо-Эдмондса является обобщением следующего известного результата об остовном дереве максимального веса [39].
Остовное дерево с максимальным суммарным весом ребер может быть найдено с помощью алгоритма Краскала.
Алгоритм Краскала начинает работу с пустого множества и на каждом шаге к текущему множеству ребер добавляет одно ребро максимального веса, сохраняющее условие отсутствия циклов.
Отметим, что связь между свойством точности алгоритма покоординатного подъема и матроидными свойствами множества допустимых решений впервые была установлена Борувкой [17], но получила широкую известность только после работ Радо и Эдмондса (см. также [26]).
Погрешность алгорима в случае систем независимости.
Относительной точностью алгоритма покоординатного подъема наги* зывается величина inf-, где w0T1T — оптимальное значение целевого о it>onT функционала и w* — значение, полученное с помощью алгоритма покоординатного подъема. Дженкинс, Кортэ и Хаусманн [31, 32, 33, 35] доказали следующее утверждение.
В случае произвольной системы независимости Т относительная точность алгоритма покоординатного подъема равна минимуму отношения функций нижнего и верхнего ранга системы Т, т. е. inf — = min{ М С 7, г (А) > 0}, w>0wonT г (А) ~ где г'(А) и г{А) — минимальная и максимальная мощности баз семейства Та
Данный результат является обобщением теоремы Радо-Эдмондса, поскольку в случае матроидов ранговые функции совпадают. Отметим также, что аналогичная оценка справедлива и в случае двойственного жадного алгоритма в минимизационной задаче [6].
Другим интересным и важным результатом в теории жадных алгоритмов является следующая фундаментальная теорема [31].
Пусть некоторый алгоритм, А имеет, относительную точность, более высокую, чем алгоритм покоординатного подъема (для всех систем независимости, не являющихся матроидами). Тогда трудоемкость алгоритма, А оценивается снизу как 2п~°(п где п = |/|.
Другими словами, в случае систем независимости (и, следовательно, в случае более общих рассматриваемых ниже задач целочисленного программирования) жадный алгоритм имеет максимальную точность в классе полиномиальных алгоритмов.
Гридоиды и системы достижимых множеств. В 80-е годы начали появляться результаты о поведении алгоритмов типа покоординатного подъема в случае семейств множеств, не монотонных вниз. В частности, было проведено очень интенсивное исследование гридоидов [15, 25, 27, 28, 36, 37, 38]. Само их название говорит о том, что данное понятие связано с темой жадных алгоритмов. Семейство множеств Т называется гридоидом, если выполнены следующие условия: если, А? Т и, А не пусто, то, А — i? Т при некотором i? Аесли А, В? Т и |А| + 1 = |В|, то AUi? при некотором i? В — А. Отметим, что матроиды — это в точности монотонные вниз гридои-ды. Кортэ и Ловас [36] установили, что если семейство Т является гридоидом, то алгоритм покоординатного подъема позволяет максимизировать целевые функционалы, в определенном смысле совместимые с гридоидом Т. Гоэтчел [29, 30] показал, что алгоритм покоординатного подъема позволяет максимизировать аддитивный целевой функционал на множестве баз гридоида тогда и только тогда, когда выполнено сильное обменное свойство. Вскоре было доказано [28], что данное свойство является критерием точности алгоритма и в случае произвольных систем достижимых множеств, т. е. семейств множеств Т таких, что если, А? Т и, А не пусто, то, А — г? Т при некотором г? Аесли, А? Т и, А не максимально в то A U г? Т при некотором г? / - А.
Примером не монотонных вниз гридоидов является семейство деревьев в связном неориентированном графе. Как известно [41], задача максимизации аддитивного функционала на множестве баз этого семейства разрешима с помощью алгоритма покоординатного подъема, который в данном случае представляет из себя алгоритм Прима.
Другим интересным примером гридоидов являются гауссовские гри-доиды. Семейство множеств Т называется гауссовским гридоидом, если выполнены следующие условия: если, А? Т и, А не пусто, то A — i при некотором %? Аесли А, В? Т и |А| + 1 = то AUi? Т и В —г? Т при некотором i? В — А.
В [13, 19] был установлен следующий результат.
Произвольная система достижимых множеств Jявляется гаус-совским гридоидом тогда и только тогда, когда при любом аддитивном целевом функционале и при любом к = 1,2,. на к-м шаге работы алгоритма покоординатного подъема получается множество, имеющее максимальный вес среди множеств вида, А? Т, А = к.
Дельта-матроиды. После появления теоремы Радо-Эдмондса было придумано множество обобщений матроидов, так или иначе сохраняющих их оптимизационные свойства. Значительные результаты в этом направлении связаны с дельта-матроидами. Семейство Т подмножеств множества I называется дельта-матроидом, если выполнена следующая симметрическая обменная аксиома: если € ^ и a G, А Д В, то, А Д {a, b} Е Т при некотором b 6 А Д Б, где Л — симметрическая разность множеств.
Отметим, что матроиды — это в точности монотонные вниз дельта-матроиды, базы которых имеют одинаковую мощность. Справедлива следующая теорема [18, 20, 21].
Семейство Т является делъта-матроидом тогда и только тогда, когда задача максимизации аддитивного функционала на семействе Т разрешима симметрическим жадным алгоритмом.
Слабым местом данного алгоритма является то, что он использует довольно громоздкие оракулы, проверяющие условия существования или несуществования множества F Е Т такого, что, А С F С В.
G-матроиды Тардош. Частным случаем дельта-матроидов являются g-матроиды, рассмотренные Тардош [45]. Дадим одно из эквивалентных определений. Непустое семейство множеств Т называется g-матроидом, если выполнены следующие два условия: если А, В? Т т, а? А — В, то, А — а е Т либо A U Ь — а Е Т при некотором Ь? В — Аесли A, BeJFnaeA-B, то В U a G J либо В U, а — Ь? Т при некотором Ь? В — А.
В [45] был предложен жадный алгоритм, позволяющий максимизировать аддитивный функционал на семействе множеств g-матроида. Данный алгоритм использует простой оракул, проверяющий условие принадлежности множества семейству Т.
Максимизация линейного функционала. Задача максимизации аддитивного функционала является частным случаем задачи целочисленного программирования с линейным целевым функционалом. Пусть I — конечное множество, w — вещественная функция на множестве I, N = {0,1,2,.} и ^ — конечное семейство целочисленных неотрицательных векторов С N1). Требуется максимизировать функционал ier при условии I g $ 5. В другой постановке вместо условия IeS рассматривается условие X? где — семейство максимальных векторов из
Результаты Эдмондса о полиматроидах. Рассмотрим еще более общую задачу: максимизировать линейный функционал ги (Х) при условии X е U, где Ы — произвольное подмножество R1. Для решения данной задачи Эдмондс [23] предложил использовать следующий жадный алгоритм: пусть е- — такой вектор, что ег-(г) = 1 и e-(j) = 0 при j? I — г, I = {1,., п} и w (l) >. > w (m) > 0 > w (m + 1) >. > w (n) — при к = 1,., т алгоритм полагает Х (к) = тах{ у X{l)ei +. + Х (к — l) efci + уек? Щ при к = т + 1,., п алгоритм полагает Х (к) = 0.
Семейство векторов U называется расширенным полиматроидом) если оно не пусто и выполнены следующие условия: из того, что X
Семейство целочисленных неотрицательных векторов расширенного полиматроида называется целочисленным полиматроидом.
Справедливы следующие два утверждения [14, 23].
Жадный алгоритм Эдмондса позволяет максимизировать любой линейный функционал на полиэдре U тогда и только тогда, когда U является расширенным полиматроидом.
Задача целочисленного программирования с линейным целевым функционалом на целочисленном полиматроиде разрешима с помощью жадного алгоритма Эдмондса.
Алгоритм Дунстана-Вэлша. Дунстан и Вэлш [22] модифицировали жадный алгоритм Эдмондса, предложив использовать в нем более сложный оракул, связанный с множеством допустимых решений. Данный оракул для произвольного вектора X определяет, существует ли вектор Y £Ы такой, что X < Y (в этом случае пишем X? li). Алгоритм Дунстана-Вэлша работает следующим образом: пусть / = {1,., п} и Щ1)| >. > Щтг)|- при к — 1,., п алгоритм полагает Х (к) = тах{ у |X (l)ei + ••• + Х (к — l) ek- + уек? U}, если w (k) > О, min{ у X (l)ei + ••• + Х (к — 1) ек- + уек? U}, если w{k) < 0.
Справедлива следующая теорема [14, 22].
Жадный алгоритм Дунстана-Вэлша позволяет максимизировать любой неотрицательный линейный функционал на компактном множестве U тогда и только тогда, когда выпуклая оболочка множества {X? R11 X? U} является расширенным полиматроидом.
Другие условия точности алгоритма Дунстана-Вэлша получены в более поздних работах [20, 34, 40, 42]. Данные условия связаны с би-субмодулярными полиэдрами (см. также [14]).
Максимизация сепарабельного функционала. Другой основной задачей, исследуемой в диссертации, является задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Пусть I — конечное множество, N = {0,1,2,.}, /г- — вогнутые вещественные функции на JV (г? I) и ^ — конечное семейство целочисленных неотрицательных векторов (3s С N1). Требуется максимизировать функционал г£/ при условии X? В другой постановке вместо условия I? 3 рассматривается условие X? где B ($s) — семейство максимальных векторов из ^s.
Функционалы вида Y, ieifiX (i) называются сепарабелъными. Примером сепарабельного функционала является линейный функционал. В случае булевых векторов сепарабельный функционал с точностью до аддитивной константы совпадает с линейным функционалом. Алгоритм покоординатного подъема имеет следующий вид: алгоритм начинает работу с нулевого вектора X и на каждом шаге добавляет к вектору X вектор егтакой, что X + ег? Q и f (X + ег) = max{f (X + е,-) X + ej Е Щесли X + e. j (? Q при всех j? /, то алгоритм заканчивает работу.
Справедлива следующая теорема [3, 11].
Пусть S — непустое конечное семейство векторов, монотонное вниз, т. е. из того, что X
Данный результат является обобщением теоремы Радо-Эдмондса. По аналогии со случаем систем независимости может быть доказана и следующая более сильная теорема [8].
В случае произвольной конечной монотонной вниз системы векторов S относительная точность алгоритма покоординатного подъема равна минимуму отношения ранговых функций системы т. е. inf-f- = min{ | X G N q (X) > 0}, f>0 four I q (X) 1 J' где q'(X) и q (X) — минимальная и максимальная суммы компонент максимальных векторов системы не превосходящих X.
Отметим, что аналогичные теоремы справедливы также в случае, когда множество допустимых решений является производным конечным частично-упорядоченным множеством с соответствующими ограничениями типа монотонности вниз [7, 8].
Задача коммивояжера. В качестве приложения полученных результатов в диссертации рассматриваются задача коммивояжера и некоторое ее обобщение. Отметим два результата о разрешимости задачи коммивояжера жадными алгоритмами.
Пусть G = (V, Е) — полный ориентированный граф и каждой дуге графа G приписан неотрицательный вес. Требуется найти гамильто-нов контур максимального или минимального суммарного веса.
Первый результат относится к максимизационной задаче. Для ее решения предлагается использовать следующий жадный алгоритм: алгоритм начинает работу с пустого множества, А и на каждом шаге добавляет к множеству, А одну дугу е? Е — А максимального веса такую, что A U е образует подмножество некоторого гамильтонова контураесли, А = |V|, то алгоритм заканчивает работу.
В работах [9, 32, 35] показано, что относительная точность данного алгоритма имеет достижимую нижнюю оценку 1/3, причем в симметрическом случае справедлива оценка ½.
Другой результат относится к минимизационной задаче коммивояжера. Для ее решения предлагается использовать следующий очень простой жадный алгоритм: алгоритм начинает работу в произвольной вершине г>о? V и на каждом шаге достраивает имеющийся путь по правилу «иди в ближайшую еще не пройденную вершину» — если все вершины пройдены, то путь замыкается в вершине vq.
В работах [2, 12] найдены такие классы вероятностных распределений весов дуг, что при росте числа вершин графа G выполняются следующие условия: математическое ожидание относительной точности жадного алгоритма стремится к единицедисперсия относительной точности стремится к нулювероятность несрабатывания алгоритма стремится к нулю.
Результаты диссертации. В настоящей диссертации рассматриваются две основные задачи: задача целочисленного программирования с линейным целевым функционалом и задача целочисленного программирования с вогнутым сепарабельным целевым функционалом. Для их решения предлагается использовать следующий алгоритм покоординатного подъема: алгоритм начинает работу с нулевого вектора X и на каждом шаге добавляет к вектору X вектор егтакой, что получающийся вектор X + егпринадлежит семейству S и имеет среди всех таких векторов максимальное значение целевого функционалаесли X + еj?s при всех j Е I, то алгоритм заканчивает работу.
Среди известных эвристик данный алгоритм является одним из самых быстрых методов. По сравнению с такими подходами, как генетические алгоритмы или алгоритмы поиска с запретами (tabu search), он лучше поддается строгому теоретическому анализу. С другой стороны, в отличие от аналогичных алгоритмов Эдмондса и Дунстана-Вэлша предлагаемый алгоритм не использует каких-либо сложных оракулов, связанных с множеством допустимых решений. (Напомним, что жадные алгоритмы Эдмондса и Дунстана-Вэлша используют оракулы, вычисляющие величины тах{ у Х + увг 6 5} и тах{ у Х + уегЕ соответственно. К сожалению, не всегда существуют эффективные реализации данных оракулов.)
Изложим кратко результаты настоящей диссертационной работы, состоящей из введения, трех глав, заключения, списка используемой литературы и списка публикаций автора по теме диссертации.
В первой главе определяются условия разрешимости алгоритмом покоординатного подъема задачи целочисленного программирования с линейным целевым функционалом и связанной с ней задачи о длиннейшем пути в специальной постановке. Доказано одно обобщение теоремы Радо-Эдмондса [24, 43] и одно необходимое и достаточное условие точности алгоритма в случае систем достижимых векторов. Расширена область действия известного критерия точности жадного алгоритма в случае гридоидов и систем достижимых множеств [28].
Во второй главе определяются условия разрешимости алгоритмом покоординатного подъема задачи целочисленного программирования с вогнутым сепарабельным целевым функционалом. Получено необходимое и достаточное условие точности алгоритма в случае произвольного множества допустимых решений. В качестве следствия доказано одно простое достаточное условие точности рассматриваемого алгоритма и предложено одно интересное обобщение матроидов и целочисленных полиматроидов, сохраняющее свойство точности алгоритма.
В третьей главе определяются достижимые оценки относительной точности алгоритма покоординатного подъема в случае целевых функционалов обоих рассматриваемых типов. Показано, что относительная точность алгоритма равна минимуму отношения обобщенных ранговых функций. Данные результаты являются обобщениями аналогичных результатов для систем независимости и монотонных вниз систем векторов [8, 33, 35]. Установлена связь между свойством точности алгоритма и свойствами субмодулярности и монотонности обобщенных ранговых функций. В качестве приложения показано, что обобщенная максимизационная задача коммивояжера разрешима жадным алгоритмом с относительной точностью ½.
В заключении приводятся основные результаты диссертации.
Основные результаты диссертации опубликованы и докладывались на следующих научных конференциях:
Международная Конференция «Проблемы оптимизации и экономические приложения», Омск, 1997;
XXXVI, XXXVII и XXXVIII Международная Научная Студенческая Конференция «Студент и научно-технический прогресс», Новосибирский Государственный Университет, 1998;2000;
III Молодежная Школа по Дискретной Математике, Институт Математики СО РАН, Новосибирск, 1999;
Международная Научная Конференция по Дискретному Анализу и Исследованию Операций «DAOR'2000» (два доклада), Институт Математики СО РАН, Новосибирск, 2000;
Международный Симпозиум по Комбинаторной Оптимизации «СО'2000», Университет Гринвича, Лондон, 2000.
Заключение
В настоящей диссертации исследуется вопрос о разрешимости алгоритмом покоординатного подъема задач дискретной оптимизации с линейным и вогнутым сепарабельным целевыми функционалами. Сформулируем основные результаты проведенных исследований.
1. Получены необходимые и достаточные условия разрешимости алгоритмом покоординатного подъема задачи целочисленного программирования на различных множествах допустимых решений.
2. Расширена область действия известного критерия точности алгоритма в случае задачи максимизации аддитивного функционала на гридоидах и системах достижимых множеств.
3. Получено одно обобщение матроидов и целочисленных полима-троидов, сохраняющее свойство точности алгоритма покоординатного подъема.
4. Доказано, что относительная точность алгоритма в случае задачи целочисленного программирования равна минимуму отношения обобщенных ранговых функций.
5. Установлена связь между точностью алгоритма и свойствами субмодулярности и монотонности обобщенных ранговых функций.
6. Получены некоторые примеры задач дискретной оптимизации, разрешимые алгоритмом покоординатного подъема с константной точностью.
