Ковалев М.М. Матроиды в дискретной оптимизации Изд. стереотип.

Оглавление

Введение

Задачи дискретной оптимизации (ДО) есть модели практических ситуаций выбора наилучших вариантов из конечного их множества. Математические модели не тождественны самой ситуации, а являются ее приближенным описанием, поэтому и решать задачи ДО разумно с той же степенью приближения к оптимуму. Тем более, что принципиальная трудность задач ДО делает, по-видимому, невозможным построение эффективных точных алгоритмов для нетривиальных классов задач. Следовательно, вопросы систематизации эвристических процедур, создания математических средств оценки их качества, синтеза высокоэффективных семейств "конкурирующих" алгоритмов представляются актуальными. Их актуальность возрастает с расширением приложений ДО в таких новых областях, как проектирование сетей ЭВМ, параллельные вычисления, создание интегрированных производственных систем из гибких модулей, автоматизация проектирования всевозможных схем и в первую очередь сверхбольших интегральных схем (СБИС).

Проблематика регуляризации задач ДО и их приближенного решения находится в стадии становления. Намечаются подходы к регуляризации пространств "исходных данных", например, путем покрытия их epsilon-сетью (epsilon-приближенные алгоритмы) или создания архивов решенных задач (подход Ю.И.Журавлева, В.К.Леонтьева). Апробируются разные меры эффективности приближений, основанные на различных метризациях либо области значений минимизируемой функции (приближения по функционалу), либо области задания аргументов (приближения по решению). Отличительная особенность большинства исследований в области теории приближенных решений задач ДО состоит в том, что значительная часть их базируется на использовании широко известных и хорошо зарекомендовавших себя при решении реальных задач алгоритмических схем, связанных с именами В.С.Михалевича, Н.Н.Моисеева, Ю.И.Журавлева, Д.А.Супруненко, И.В.Сергиенко, В.А.Емеличева, В.С.Танаева, В.П.Черенина, В.Р.Хачатурова и др.

Для приближенных алгоритмов главная проблема – получение оценок эффективности [3, 6, 49, 71, 76, 78, 86, 93, 99, 100]. За последние 15 лет были найдены или привлекли внимание теоретические разработки зачастую из областей, далеких от ДО, оказавшиеся способными служить инструментом исследования эффективности алгоритмов (см., например, [112, 158, 180]). Одним из таких инструментов явилась теория матроидов.

Теория матроидов широко применяется в таких областях математики, как теория представлений, теория трансверсалей, комбинаторная геометрия, теория решеток. Применению матроидов в ДО посвящена обширная журнальная литература (библиографию см. в [78, 152]), отдельные вопросы освещались в монографиях [4, 90, 97, 152, 158, 178, 189, 200, 209].

Книга посвящена описанию одного из направлений применений теории матроидов в ДО, матроидному подходу анализа эффективности алгоритмов. Основу матроидного подхода составляют: метод частичных порядков; концепция выпуклости в частично упорядоченных множествах; схемы построения серий градиентных алгоритмов.

Матроидные структуры (суперматроиды, полиматроиды, матроиды) и введенные их обобщения используются для систематизации классов задач ДО, изучения на этой основе локальных свойств допустимых областей и анализа алгоритмов, простейшие из которых – алгоритмы координатного и бикоординатного подъема. Установленные связи между выпуклыми и матроидными структурами в частично упорядоченных множествах служат фундаментом для решения поставленных проблем оценки эффективности приближенных алгоритмов. Связующим звеном между выпуклостью и матроидами служит метод частичных порядков [41, 44].

Отношения частичного порядка в оптимизации используются широко. Так, в [28, 29] изложен общий подход к исследованию локальных экстремумов на основе отношения мажоризации. В [106] построена единая концепция необходимых условий оптимальности в экстремальных задачах на подстановках; разнообразны применения частичных порядков в теории расписаний [107] и теории оптимальных алгоритмов обработки информации [6]. Следует сказать, что частичные порядки и решетки становятся важным инструментом в ДО. Этому в немалой степени способствуют недавние важные результаты в теории решеток [180, 181, 199]. Среди них следует упомянуть дискретный решеточный аналог неравенства Чебышева о среднем – неравенство FKG [142, 154]; теорему Ловаса о возможности построения базиса целочисленной решетки, заданной оракулом "отделимость" в полиномиальное время [185, 186]; теорию субмодулярных функций и гридоидов [23–25, 111, ИЗ, 134, 156, 157, 173, 183, 193, 207]; оценку для числа порядковых идеалов, содержащих данный элемент [143, 182].

Метод частичных порядков заключается в следующем. Допустимое множество задачи ДО погружается в такое частично упорядоченное множество, что не только целевая функция, но и ее градиенты ("дискретные производные") монотонны вдоль цепей, индуцированных частичным порядком. Функции с таким свойством названы порядково-выпуклыми. Монотонность градиентов порядково-выпуклых функций, аналогичная монотонности производных выпуклых функций в Rⁿ, позволяет вывести ряд неравенств, дающих инструмент формулировки условий экстремума и получения оценок отклонений от оптимума. Порядково-выпуклые функции составляют подкласс хорошо известных в дискретной математике субмодулярных функций.

Следует отметить, что в 80-е гг. наметились пути к формированию дискретного выпуклого анализа, необходимого, в первую очередь, в теории ДО. Появились плодотворные аналоги выпуклости: d – выпуклость в дискретных метрических пространствах [11, 99, 104]; r – выпуклость [99, 100], порядковая выпуклость [66, 103, 147], дискретная квазивыпуклость [99, 100], субмодулярность [39, 113, 183], полиномиальная выпуклость [8, 108].

Алгоритм градиентного типа (метод скорейшего спуска) применен в дискретной математике, по-видимому, впервые в работах школы С.В.Яблонского для минимизации д.н. ф. [116, 117] и связанных с ними задач о покрытиях. Идея градиентных алгоритмов была высказана еще Монжем [190] при построении алгоритма решения специальной транспортной задачи. Градиентные алгоритмы являются представителями класса локальных алгоритмов оптимизации. Для задач ДО широкий класс локальных алгоритмов, построенных по схеме метода вектора спада, предложен в работах киевской школы математиков под руководством И.В.Сергиенко [99, 100]. К настоящему времени градиентные методы нашли широкое практическое применение. Простейший из градиентных алгоритмов – алгоритм координатного подъема.

В работе [198] доказано, что данный алгоритм максимизирует линейную функцию на независимой системе матроида. Эдмондс [135] дал критерий оптимальности решений, полученных с помощью алгоритма координатного подъема при решении задач линейного программирования (ЛП) на допустимых областях со свойством монотонности: если х принадлежит D и у <= х, то у принадлежит D. Независимо от Эдмондса в [16] получен более общий критерий сходимости алгоритма координатного подъема к оптимальному решению в задаче выпуклого целочисленного программирования (см. также [89]). Работы [44, 60, 68, 87, 92, 94, 101, 161, 172, 174, 191, 192] являются исходными для систематических анализов точности алгоритма координатного подъема, называемого в англоязычной литературе greedy алгоритмом. Согласно теоретическим результатам алгоритм координатного подъема имеет неплохую точность даже в наихудшем случае, а согласно числовым экспериментам в среднем он дает решения, близкие к оптимальным [22, 204]. Таким образом, алгоритм координатного подъема – важный инструмент решения реальных практических задач. Кроме того, он имеет невысокую трудоемкость и эффективно реализуется на ЭВМ. Следующим по простоте после алгоритма координатного подъема является алгоритм бикоординатного подъема, на каждом шаге которого изменяются только две координаты текущей точки. На графах такой алгоритм превращается в простой метод замен: на каждой итерации из строящейся "конструкции" так удаляется ребро (вершина) и добавляется новое, чтобы максимально увеличилась целевая функция. В книге описаны задачи ДО, решаемые бикоординатным алгоритмом точно, и приведены оценки его погрешности.

В теории схем и распознаваний образов, в некоторых других разделах дискретной математики идея синтеза алгоритмов с требуемой точностью из "ненадежных алгоритмов " получила широкое распространение [36, 113, 116]. Пути использования этой идеи в ДО указали Ю.И.Журавлев и В.К.Леонтьев. В книге предлагаются три новые схемы синтеза серий градиентных алгоритмов и приводятся оценки погрешности для лучшего из построенных решений на примере модельных задач ДО – задач о ранце и коммивояжере. Данные оценки оказываются лучше, чем оценки лучшего из алгоритмов, входящих в серию. Это объясняется тем, что не одни и те же задачи являются "плохими" для разных алгоритмов серии. Весьма заманчивой представляется идея строить методы точного решения задач ДО с помощью серий конкурирующих эвристик.

Приложения градиентных алгоритмов иллюстрируются при решении сложных сетевых задач потоковыми алгоритмами.

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

При написании книги использован ряд ценных советов академика АН БССР Д.А.Супруненко, профессоров В.А.Емеличева, В.С.Танаева и В.К.Леонтьева.

Значительная часть результатов, отраженных в книге, была получена в процессе совместной работы автора с его учениками Е.Димовым, П.Милановым, В.М.Котовым, Н.Н.Писаруком. Автор особенно признателен Н.Н.Писаруку, который оказал значительную помощь при отработке текста рукописи.

Автор выражает глубокую благодарность Э.Н.Гордееву и Я.М.Шафранскому за полезные обсуждения и критические замечания.

Об авторе

Ковалев Михаил Михайлович

Доктор физико-математических наук (1993), профессор (1994). В 1969 г. окончил Белорусский государственный университет (БГУ), в 1973 г. — аспирантуру этого вуза и уже 50 лет работает в БГУ, из них 20 лет — деканом экономического факультета. Заслуженный деятель науки Республики Беларусь (2001).

Автор более 600 научных работ в области математической экономики, дискретной оптимизации, системного анализа, среди которых 25 монографий, в том числе изданных в Кембридже, Берлине и Москве. С 1993 по 1994 гг. — советник Председателя Верховного Совета.