Содержание к диссертации
Введение
Глава 1. Построение двойственного описания полиэдра 12
1.1. Основные понятия и обозначения 12
1.2. Постановка задачи 21
1.3. Методы построения двойственного описания полиэдра 23
1.4. Оценки трудоемкости 26
1.5. Некоторые приложения 31
Глава 2. Новая модификация метода двойного описания 34
2.1. Задача построения двойственного описания полиэдрального конуса 34
2.2. Метод двойного описания 35
2.3. Использование идей алгоритма Quickhull в методе двойного описания 45
2.4. Описание алгоритма 46
2.5. Оценки трудоемкости 52
2.6. Вычислительный эксперимент 57
Глава 3. Быстрый способ проверки правил Черникова в методе исключения Фурье—Моцкина 62
3.1. Задача исключения переменных из системы линейных неравенств 62
3.2. Метод исключения Фурье-Моцкина 64
3.3. Быстрый способ проверки правил Черникова 70
3.4. Вычислительный эксперимент 75
3.5. Возможности использования параллельных вычислений 77
Глава 4. Удаление неравенств из фасетного описания полиэдра 79
4.1. Постановка задачи 79
4.2. Обзор методов решения 80
4.3. Инкрементный алгоритм 81
4.4. Новый алгоритм удаления неравенств 83
4.5. Вычислительный эксперимент 88
Заключение 91
Список литературы
- Методы построения двойственного описания полиэдра
- Использование идей алгоритма Quickhull в методе двойного описания
- Быстрый способ проверки правил Черникова
- Новый алгоритм удаления неравенств
Введение к работе
Актуальность темы исследования
В различных областях дискретной математики и математической кибернетики, а также в других разделах математики и приложениях встречается такой объект, как выпуклый полиэдр (многогранное множество, многогранник). Каждый выпуклый полиэдр (далее называемый просто полиэдром) может быть представлен в одном из двух видов: как множество решений конечной системы линейных неравенств и как сумма выпуклой и конической оболочек конечных систем векторов , , ]. Данные способы задания полиэдра называются, соответственно, фасетным и вершинным описанием.
Построение двойственного описания полиэдра заключается в переходе от одного из указанных описаний полиэдра к другому: построение вершинного описания полиэдра по заданному фасетному описанию или построение фасетного описания полиэдра по заданному вершинному описанию. В силу двойственности эти задачи сводятся друг к другу.
Задача построения двойственного описания полиэдра является одной из центральных в теории систем линейных неравенств , ] и имеет важные приложения. В числе приложений можно выделить решение задач оптимизации [, ], вычислительную биологию ], теорию управления ], анализ программ для ЭВМ [].
Для практически важных случаев размерности 2 и 3 разработаны эффективные алгоритмы построения двойственного описания , ]. В диссертации рассматривается существенно более сложный случай полиэдров произвольной размерности.
Одной из важных открытых проблем теории выпуклых полиэдров является вопрос о существовании алгоритмов построения двойственного описания, полиномиальных от суммарной длины входа и выхода [11, ]. Таким образом, задача разработки эффективных алгоритмов построения двойственного описа-
ния полиэдра представляется актуальной как с теоретической точки зрения, так и с практической.
Известно множество методов построения двойственного описания полиэдров в пространствах произвольной размерности. Они могут быть классифицированы по двум критериям [11].
По первому критерию методы делятся на методы обхода графа и инкре-ментные методы. Основная идея алгоритмов первой группы заключается в обходе графа заданного полиэдра. Методы второй группы работают с промежуточными полиэдрами, определенными подсистемами исходной системы неравенств. Другим критерием является способ работы с вырожденными задачами. По данному критерию все методы делятся на три группы: строящие полную решетку граней, триангулирующие, отдельную группу образует метод двойного описания. Для всех классов методов построены семейства входных данных, на которых трудоемкость не ограничена полиномом от суммарной длины входа и выхода [11].
Метод двойного описания ] является одним из наиболее широко используемых и имеет множество модификаций, например, , , , ]. Основным преимуществом метода двойного описания является работа с существенно вырожденными задачами. С другой стороны, метод относительно плохо справляется с задачами с избыточными входными данными (большое количество неравенств-следствий для задачи построения вершинного описания, большое количество внутренних точек для задачи построения фасетного описания), а также невырожденными и близкими к ним задачами. Поэтому представляет интерес получение оценок трудоемкости метода и его модификаций на различных классах полиэдров, а также разработка новых модификаций, сохраняющих достоинства оригинального метода и при этом эффективно (как с теоретической, так и с практической точки зрения) работающих на более широком классе задач.
Задача построения двойственного описания полиэдра может быть сведена к задаче исключения переменных из системы линейных неравенств ]. Одним
из основных методов решения данной задачи является метод исключения Фу-рье-Моцкина. При использовании правил С. Н. Черникова ] этот метод является близким к методу двойного описания, что позволяет использовать идеи некоторых модификаций метода двойного описания для ускорения проверки правил Черникова в методе исключения Фурье-Моцкина.
Помимо анализа и разработки алгоритмов построения двойственного описания полиэдра в общем случае, актуальной является разработка алгоритмов решения задачи в модифицированных постановках. Одной из практически важных постановок является следующая ]: заданы неприводимые фасетное и вершинное описания полиэдра, требуется найти вершинное описание полиэдра, фасетное описание которого является подсистемой системы неравенств, определяющих исходный полиэдр.
Цели и задачи диссертационной работы
Целями работы являются разработка новых и модификация существующих алгоритмов построения двойственного описания выпуклого полиэдра и решения близких задач, а также выделение подклассов задач, для которых существуют эффективные алгоритмы.
Для достижения поставленных целей были определены следующие задачи исследования:
-
Разработка новой модификации метода двойного описания, эффективной на более широком классе входных данных по сравнению с оригинальным методом.
-
Ускорение проверки правил Черникова в методе исключения Фурье-Моцкина путем сокращения перебора.
-
Выделение полиномиально разрешимых случаев задачи удаления неравенств из фасетного описания полиэдра и разработка эффективного алгоритма для таких случаев.
Научная новизна
Новыми являются следующие результаты работы:
-
предложена новая модификация метода двойного описания с использованием идей алгоритма Quickhull;
-
разработан новый способ проверки правил Черникова в методе исключения Фурье-Моцкина, сокращающий количество операций по сравнению с традиционным;
-
предложен новый алгоритм для выделенного класса задач удаления неравенств из фасетного описания полиэдра.
Теоретическая и практическая значимость
Результаты работы могут быть использованы в исследованиях по развитию теории систем линейных неравенств, включая вопросы сложности. Предложенные в работе алгоритмы могут использоваться в областях, в которых возникает задача построения общего решения системы линейных неравенств и близкие задачи: решение задач оптимизации, вычислительная биология, теория управления и др.
Результаты диссертации могут найти применение в исследованиях, проводимых в Московском государственном университете им. М.В. Ломоносова, Федеральном исследовательском центре «Информатика и управление» РАН, Институте математики и механики им. Н. Н. Красовского УрО РАН, Ярославском государственном университете им. П. Г. Демидова, Южно-Уральском государственном университете, Институте проблем управления им. В. А. Трапезникова РАН, Нижегородском государственном университете им. Н. И. Лобачевского.
Методы исследования
В работе используются методы теории систем линейных неравенств, анализа алгоритмов, теории сложности.
Положения, выносимые на защиту
Предложена новая модификация метода двойного описания с использованием идей алгоритма Quickhull, получены оценки трудоемкости.
Разработан способ ускорения проверки правил Черникова в методе исключения переменных Фурье-Моцкина с использованием графов.
Предложен новый алгоритм удаления неравенств из фасетного описания выпуклого полиэдра для выделенного класса задач. Доказано, что алгоритм является полиномиальным от длины входа в случае удаления фиксированного числа неравенств.
Степень достоверности и апробация результатов
Результаты диссертации научно обоснованы: приводятся математические доказательства корректности и оценок трудоемкости предлагаемых алгоритмов; результаты вычислительных экспериментов согласуются с теоретическими оценками и подтверждают эффективность разработанных алгоритмов.
Основные результаты диссертации обсуждались на заседаниях нижегородского семинара по дискретной математике, семинара НИИ прикладной математики и кибернетики (ИНГУ им. И.И. Лобачевского) и лаборатории алгоритмов и технологий анализа сетевых структур (НИУ ВШЭ) и докладывались на 5 международных и всероссийских конференциях:
XIV Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 2011);
Международная конференция «Алгебра и линейная оптимизация», посвященная 100-летию СИ. Черникова (Екатеринбург, 2012);
Международная конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2013);
XV Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 2015);
the 5th International Conference on Network Analysis (Нижний Новгород, 2015).
Публикации
Материалы диссертации опубликованы в 9 работах [А1-А9], из них 3 статьи в рецензируемых журналах [А1-АЗ], 1 свидетельство о государственной регистрации программы для ЭВМ [А4] и 5 тезисов докладов.
Личный вклад автора
В совместных публикациях личный вклад СИ. Бастракова является определяющим. Научному руководителю принадлежат некоторые идеи алгоритмов в работах [Al, А2], постановки задач и общее редактирование во всех работах. Проработка деталей алгоритмов, все доказательства, программные реализации и вычислительные эксперименты выполнены С. И. Бастраковым лично.
Структура и объем диссертации
Методы построения двойственного описания полиэдра
Задача построения вершинного описания полиэдра Р состоит в нахождении вершинного описания (1.2) по заданному фасетному описанию (1.1), то есть нахождении системы векторов по заданной системе линейных неравенств Ах Ь. Задача построения фасетного описания полиэдра состоит в нахождении фасетного описания (1.1) по заданному вершинному описанию (1.2).
Вершинное и фасетное описания полиэдра являются двойственными друг к другу: по вершинному описанию Р легко построить фасетное описание двойственного к нему полиэдра Р и наоборот. Таким образом, задача построения вершинного описания полиэдра может быть сведена к задаче построения фасетного описания для двойственного полиэдра и обратно. Поэтому задачи построения вершинного и фасетного описания полиэдра эквивалентны и называются задачей построения двойственного описания полиэдра.
Задача построения двойственного описания полиэдра в Q может быть сведена к аналогичной задаче для конуса в Q + следующим способом [20]. Пусть необходимо построить вершинное описание полиэдра Р по заданному фасетному описанию вида (1.1). Строится конус С(Р) (1.5) в Q , соответствующий полиэдру Р. Находится остов конуса С(Р), вершинное описание Р определяется с помощью соотношения (1.6).
В дальнейшем изложении рассматривается задача построения вершинного описания полиэдра по заданной системе линейных неравенств вида (1.1). Каждое неравенство системы с рациональными коэффициентами умножим на наименьшее общее кратное модулей знаменателей коэффициентов левой и правой части, таким образом перейдя к эквивалентной системе с целочисленными коэффициентами. В дальнейшем предполагается, что в качестве фасетного описания полиэдра задана система линейных неравенств с целочисленными коэф фициентами: Р = {х є qd : Ах Ъ} , А є Zmxd, b Є Zm (1.22)
Входом являются (m + l)d коэффициентов системы неравенств (1.22): md коэффициентов матрицы А и т коэффициентов вектора Ь. Предполагается. что арифметические операции над коэффициентами, возникающими в процессе построения двойственного описания, выполняются за единицу времени. Вопрос о битовой длине входа и росте коэффициентов обсуждается в параграфе 1.4.
В настоящем параграфе описываются основные методы построения двойственного описания полиэдра в пространствах произвольной размерности. Для практически важных и существенно более простых случаев d = 2,3 известно множество эффективных алгоритмов, их обзор можно найти, например, в [16, 45, 57].
Изложение производится в терминах задачи построения вершинного описания полиэдра, подразумевая указанную в параграфе 1.2 сводимость задач построения вершинного и фасетного описания полиэдра друг к другу, а также сводимость задачи построения двойственного полиэдра в Q к аналогичной задаче для полиэдрального конуса в Q . Приводимая классификация методов построения двойственного описания полиэдра основана на [33].
По способу построения вершин и рецессивных направлений полиэдра все методы могут быть разбиты на два класса: 1. Методы, основанные на обходе графа полиэдра (graph traversal). 2. Инкрементные [incremental) методы, иногда также называемые итеративными. Методы, основанные на обходе графа полиэдра, начинают с одной из вершин либо одного из экстремальных лучей полиэдра и, двигаясь по ребрам определенным образом, постепенно строят весь граф полиэдра. Движение по ребру соответствует изменению базы, подобно итерации симплекс-метода при решении задач линейного программирования [34]. Представителями данного класса методов являются метод «заворачивания подарка» (gift-wrapping algorithm) [41], метод Зейделя [59], метод обратного поиска (reverse search) [34] и его модификация -- метод лексикографического обратного поиска (lexicographic reverse search) [32] и другие.
Инкрементные методы начинают с построения вершинного описания полиэдра, заданного некоторой подсистемой исходной системы неравенств. В качестве начального используется полиэдр, для которого вершинное описание может быть легко выражено через фасетное описание, например, симплекс. полупространство или все пространство. Далее на каждом шаге вычисляется вершинное описание пересечения построенного на текущий момент полиэдра с одним или несколькими полупространствами, соответствующими не обработанным неравенствам системы; построенный таким образом полиэдр становится текущим на следующем шаге. После обработки всех неравенств вершинное описание текущего полиэдра совпадает с вершинным описанием искомого полиэдра. Важной составляющей каждого инкрементного метода является порядок обработки неравенств. Теоретические результаты и данные вычислительных экспериментов [10, 33, 47] показывают, что трудоемкость инкрементного метода может существенно зависеть от порядка обработки неравенств из-за размера промежуточных полиэдров. К данной группе методов относятся метод двойного описания (double description method) [56], метод «под-над» (beneath-beyond) [58], инкрементный рандомизированный алгоритм [43], алгоритм Quickhull [36], оптимальный алгоритм для любой фиксированной размерности [42] и другие.
Использование идей алгоритма Quickhull в методе двойного описания
Алгоритм Quickhull широко применяется для построения построения выпуклой оболочки системы точек. Классическая версия алгоритма была разработана для случая точек на плоскости [40, 46, 49], версия для случая произвольной размерности была предложена в [36]. Заметим, что к нему близок другой алгоритм построения выпуклой оболочки [25]. Настоящий параграф посвящен краткому описанию идей алгоритма Quickhull и возможности их использования в методе двойного описания. Получаемая при этом новая модификация метода двойного описания излагается в следующем параграфе.
Описание ниже приводится в терминах задачи построения выпуклой оболочки множества точек в Q . Как и метод двойного описания, алгоритм Quickhull к классу инкрементных (согласно классификации, приведенной в параграфе 1.3) и осуществляет поочередное добавление точек к выпуклой оболочке ранее обработанных точек. Основной особенностью алгоритма Quickhull является возможность быстрой обработки входных точек, не являющихся вершинами итоговой выпуклой оболочки. Для этого в ходе работы алгоритма с каждой фасетой ассоциируется внешнее множество, состоящее из (некоторых) необработанных на текущий момент точек, которые не удовлетворяют неравенству соответствующему фасете. В таком случае говорят, что фасета видима из точки. В случае, когда из точки видимы несколько фасет, она попадает во внешнее множество одной (любой) из них.
В начале каждой итерации выбирается фасета с непустым внешним множеством и в качестве добавляемой точки выбирается наиболее удаленная из точек внешнего множества данной фасеты. После этого определяется множество видимых и невидимых из добавляемой точки фасет и множество граничных гребней, являющихся пересечением видимой и невидимой фасеты, эта процедура выполняется путем поиска на графе, образованном фасетами текущего политопа (фасеты являются вершинами графа, вершины графа смежны тогда и только тогда, когда смежны соответствующие фасеты). Из каждого граничного гребня создается новая фасета, проходящая через добавляемую точку. Точки из внешних множеств видимых фасет перераспределяются по внешним множествам новых фасет. При этом точки, принадлежащие внешнему множеству одной из видимых фасет, но не попавшие ни в одно из внешних множеств новых фасет, являются внутренними, таким образом, и исключаются из дальнейшей обработки. Видимые фасеты удаляются. Алгоритм завершает работу, когда внешние множества всех фасет пусты.
Алгоритм Quickhull осуществляет работу с вырожденным случаем на основе триангуляции. Как показано в параграфе 1.4, такие алгоритмы неэффективны в сильно вырожденных задачах, в отличие от метода двойного описания.
Предлагаемый в настоящем параграфе алгоритм основан на модификации метода двойного описания, описанной в параграфе 2.2, с использованием следу ющих особенностей алгоритма Quickhull: наличие внешних множеств и порядок обработки неравенств: использование поиска на графе для определения множеств (2.2)-(2.4).
Для каждого вектора остова будем хранить внешнее множество OS (и). состоящее из неравенств, которым он не удовлетворяет: если а Є OS (и), то аи О, где а — строка матрицы системы неравенств. В случае, когда неравенству не удовлетворяют несколько векторов, оно попадает во внешнее множество одного (любого) из них.
Аналогично алгоритму, описанному в параграфе 2.2, новая модификаций метода двойного описания начинает работу с выбора базисной подсистемы неравенств и построения остова определяемого ей конуса. В дополнение к этому строятся внешние множества векторов начального остова. Псевдокод начального шага приведен ниже.
Алгоритм 2.6. Начальный шаг новой модификации метода двойного описа ния. procedure InitialStepNewModification(A, m, d) Выбрать строковую базу IQ матрицы А Построить матрицу A(Io) = det(A(Io))\A(Io) [/(Со) := {а\} а?2}..., a d}} где а\} а?2}..., a d -- столбцы матрицы A(IQ] for each и Є U(Со)
Построение множеств U+ , U- и Uo производится при помощи поиска на графе конуса способом, близким к используемому в Quickhull, U-\- и U- соответствуют невидимым и видимым фасетам в терминологии Quickhull, U+ не строится в явном виде. В процессе поиска также определяются все граничные ребра (u,v): и Є U+1 v Є [/_, {u}v} Є Е(С). Неравенства, не попавшие ни в одно из внешних множеств при перераспределении, являются следствиями и исключаются из дальнейшего рассмотрения. При обновлении информации о смежности основным этапом является определение смежности векторов из Uo U U±. Оно может производиться одним из стандартных для метода двойного описания способов, описанных в параграфе 2.2. Проверка смежности является наиболее трудоемкой операцией алгоритма, при этом используется только данные об инцидентности векторов и неравенств, представленные в виде множеств 1пс{и). При осуществлении тестов на смежность необходимо выполнение большого количества операций пересечения двух множеств, сами же 1пс{и) меняются относительно редко (только в случае и Є Uo).
Быстрый способ проверки правил Черникова
В настоящем параграфе предлагается быстрый способ проверки второго правила Черникова.
Рассмотрим простой граф G, который построим по заданному множеству индексов неравенств следующим образом. Множество вершин графа G есть множество неравенств исходной системы и их комбинаций, удовлетворяющих первому правилу Черникова. Пара вершин {u,v} образует ребро тогда и только тогда, когда \S(u) U S(v)\ s + 1 (для значения s на текущей итерации). Таким образом, вершины, соответствующие неравенствам, являются смежными тогда и только тогда, когда результат их комбинирования удовлетворяет первому правилу Черникова. Множество всех вершин графа G обозначим V{G) . всех ребер -- E(G). Графовый способ проверки правил Черникова основан на следующей теореме.
Теорема 3.1. Пусть {u}v} Є E{G) и соответствующие неравенства обладают разным знаком коэффициента перед исключаемой переменной. Тогда для того, чтобы результат комбинирования неравенств и, v, удовлетворял второму правилу Черникова, необходимо и достаточно, чтобы в V(G) не существовало неравенства w, отличного от и, v, такого, что {u}w} Є E{G), {v,w} Є E{G) и S{w) С S{u) U S{v).
Доказательство. При использовании алгоритма 3.2 проверка второго правила Черникова требует перебора всех комбинаций, удовлетворяющих первому правилу Черникова, и неравенств из IQ. Общее количество таких неравенств составляет 0(/+ /_ + /о)- Проверка включения множеств над универсом размера т может быть выполнена за время 0(т): что дает требуемую оценку. При использовании алгоритма 3.3 количество перебираемых неравенств не превосходит A(G). Таким образом, трудоемкость составляет 0(mA(G)). ш
Рассмотрим класс матриц А таких, что при выполнении исключения переменных из системы неравенств Ах О, А Є А все коэффициенты перед неисключенными переменными ненулевые (на всех шагах IQ = 0). Оценим трудоемкость проверки правил Черникова для матриц из данного класса.
Теорема 3.3. Пусть метод исключения Фуръе-Моцкина применяется для последовательного исключения переменных из системы с матрицей А Є Л с т строками. Трудоемкость проверки второго правила Черникова для комбинации, удовлетворяющей первому правилу, при исключении любой переменной составляет 0{ті).
Доказательство. Для матриц из А на каждой итерации выполняется IQ = 0. Для матриц такого вида по окончании каждой итерации индексы всех неравенств обладают свойством \S(i)\ = s + 1. Это несложно показать по индукции: на начальном шаге все индексы состоят из 1 элемента, на каждом шаге при комбинировании неравенств происходит объединение двух множеств индексов максимального для данного шага размера, так как множества не совпадают, мощность объединения на 1 больше мощности каждого из исходных индексов.
Таким образом, первое правило Черникова выполняется лишь для нера венств с индексами, отличными в 1 элементе. Для заданного индекса количе ство таких неравенств составляет 0(т2). В таком случае A(G) = 0(т2) и в силу утверждения 3.1 максимальная трудоемкость графового способа провер ки правил Черникова для пары неравенств {и, v} составляет 0(т ). ш Результаты экспериментов, приводимые в параграфе 3.4, показывают существенное уменьшение количества проверок включения множеств при использовании графового способа проверки по сравнению с оригинальным. 3.4. Вычислительный эксперимент
Была разработана программная реализация алгоритмов 3.2, 3.3. Для представления индексов неравенств используются характеристические векторы множеств, хранимые в виде битовых полей. В настоящем параграфе представлены результаты сравнения эффективности оригинального и предлагаемого способов проверки правил Черникова. Использовался следующий эвристический способ выбора очередной исключаемой переменной: выбирается переменная, для которой достигается минимальное значение произведения мощности множеств I+ и I- (таким образом, минимизируется количество потенциальных комбинаций неравенств). Вычислительные эксперименты проводились на узле кластера ИНГУ «Лобачевский» с процессорами Intel Xeon Е5-2660 и 64 ГБ ОЗУ, использовался компилятор Intel версии 14.0.1.
В первом эксперименте решалась задача исключения всех переменных из системы из 30 линейных неравенств с 10 переменными, каждый из коэффициентов которой был случайно сгенерирован на отрезке [-1,1] в соответствии с равномерным распределением. При таком выборе коэффициентов все неравенства примерно пополам распределялись между множествами I+ и I- и, поэтому, количество выполняемых проверок близко к максимально возможному при данном размере задачи. На рисунке 3.1 представлено количество выполняемых проверок включения подмножеств на каждой итерации для оригинального и предлагаемого способов проверки правил Черникова. Данный случай является наилучшим для предлагаемого алгоритма с точки зрения сокращения количества проверок включения множеств. Использование модифицированного способа позволяет сократить общее количество проверок примерно в 5700 раз: 1,77 миллиона для предлагаемого способа и около 1 миллиарда для оригинального. Общее время решения задачи составляет 30 и 10 секунд, соответственно. При этом при проверке второго правила Черникова по определению оно занимает больше половины общего времени работы, а при использовании предлагаемого
Новый алгоритм удаления неравенств
Двойственной задачей является удаление элементов вершинного описания - построение фасетного описания полиэдра, порождаемого подмножеством векторов, - - она легко сводится к рассматриваемой задаче для двойственного полиэдра. Требование неприводимости фасетного описания полиэдра Р является существенным, в противном случае результат удаления неравенств может определяться неоднозначно [31]. В качестве мотивации к исследованию данной задачи авторы [31] называют анализ, оптимизацию и верификацию программ [35, 44].
С помощью стандартной процедуры, описанной в параграфе 1.1, задача удаления неравенств из фасетного описания полиэдра в Q может быть сведена к задаче удаления неравенств из фасетного описания полиэдрального конуса в qd+1. Длиной входа является размер полиэдра Р — суммарная длина его неприводимого вершинного и фасетного описаний. Отметим, что в общем случае задача не является полиномиальной от длины входа даже в случае удаления одного неравенства либо вершины. Как следует из утверждения 1.2, при удалении любой вершины из вершинного описания многогранника СС2$2(п) размер выхода не ограничен полиномом от размера входа.
Задачу удаления неравенств из фасетного описания многогранника можно рассматривать как задачу построения вершинного описания многогранника Р(1) по заданному фасетному описанию (4.3) с дополнительной информацией о многограннике Р (4.1), (4.2). Под прямым способом решения задачи будем пони мать построение вершинного описания многогранника Р(І) без использования этой дополнительной информации. Таким образом, прямой способ состоит в решении классической задачи построения двойственного описания многогранника, рассматриваемой в главе 1.
Использование дополнительной информации о многограннике Р может позволить ускорить решение задачи, особенно в случае удаления небольшого количества неравенств. Так, в [31] предложен алгоритм удаления неравенств из фасетного описания многогранника, названный авторами инкрементным, и эмпирически показано его превосходство над прямым построением вершинного описания. При этом основным этапом инкрементного алгоритма также является построение вершинного описания многогранника, определяемого некоторой подсистемой системы неравенств (4.3). Из результатов [33] следует, что при использовании любого из известных методов построения вершинного описания многогранника не удается дать полиномиальную верхнюю оценку трудоемкости прямого и инкрементного алгоритмов даже в случае удаления одного неравенства. В связи с этим возникает вопрос о существовании полиномиального алгоритма решения задачи удаления неравенств из фасетного описания многогранника, хотя бы для частного случая удаления фиксированного числа неравенств.
В настоящем параграфе дадим краткое описание алгоритма удаления неравенств, предложенного в [31] и названного авторами инкрементным. Так как фасетное описание исходного конуса неприводимо, каждое из неравенств соответствует фасете. Обозначим F множество фасет, соответствующих удаляемым неравенствам. В дальнейшем для краткости будем называть их удаляемыми фасетами. Строится множество фасет, смежных хотя бы с одной из удаляемых фасет, обозначим его Fadj. Обозначим через Аа(ц матрицу подсистемы неравенств, определяющих фасеты из Fadj. С помощью одной из модификаций метода двойного описания [56] строится остов конуса, определяемого неравенствами из Aaa\f Cadj = {х Є Qd : AadjX 0} = cone uh u2, ...un. В остове U{Cadj) найдем подмножество векторов Unew: которые не удовлетворяют хотя бы одному из удаляемых неравенств. Тогда для для остова результирующего конуса справедливо включение U(C(I)) С U{C) U Unew. Таким образом, множество векторов U(С) U Unew порождает искомый конус, однако не обязательно является неприводимым. Удаление избыточных элементов порождающего множества является стандартной процедурой, которая может быть выполнена достаточно эффективно [31], в результате получается искомый остов U{C{I)). Таким образом, трудоемкость алгоритма равна трудоемкости построения остова конуса Са(%. Вместо метода двойного описания может использоваться любой другой алгоритм построения двойственного описания многогранника, в ряде случаев это может давать существенное преимущество [33].
В случае удаления нескольких неравенств описанную процедуру можно либо произвести сразу для всех неравенств, либо итеративно для каждого из них. Авторы алгоритма отмечают, что, по-видимому, ни один из этих способов не является предпочтительным для всех случаев.
Так как инкрементный алгоритм явным образом использует метод двойного описания, для него справедливы оценки трудоемкости от размера полиэдра из работы [33]. В частности, если множество Faa\j содержит все фасеты, кроме удаляемых, алгоритм не является полиномиальным от длины входа даже в случае удаления одного неравенства.