Алгоритмические вопросы построения двойственного описания выпуклого полиэдра тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Бастраков Сергей Иванович

• Бастраков Сергей Иванович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Бастраков Сергей Иванович

Введение

Глава 1. Построение двойственного описания полиэдра

1.1. Основные понятия и обозначения

1.2. Постановка задачи

1.3. Методы построения двойственного описания полиэдра

1.4. Оценки трудоемкости

1.5. Некоторые приложения

Глава 2. Новая модификация метода двойного описания

2.1. Задача построения двойственного описания полиэдрального конуса

2.2. Метод двойного описания

2.3. Использование идей алгоритма С^шскЬиП в методе двойного описания

2.4. Описание алгоритма

2.5. Оценки трудоемкости

2.6. Вычислительный эксперимент

Глава 3. Быстрый способ проверки правил Черникова в методе

исключения Фурье^Моцкина

3.1. Задача исключения переменных из системы линейных неравенств

3.2. Метод исключения Фурье Моцкина

3.3. Быстрый способ проверки правил Черникова

3.4. Вычислительный эксперимент

3.5. Возможности использования параллельных вычислений

Глава 4. Удаление неравенств из фасетного описания полиэдра

4.1. Постановка задачи

4.2. Обзор методов решения

4.3. Инкрементный алгоритм

4.4. Новый алгоритм удаления неравенств

4.5. Вычислительный эксперимент

Заключение

Список литературы

Список публикаций автора по теме диссертации

Список условных обозначений

X п

X тхп

[а]

оопу X сопе X

кольцо целых чисел; поле рациональных чисел; поле вещественных чисел;

множество п-мерных векторов с компонентами из X; множество матриц размера т х п с элементами из X; целая часть числа а (наибольшее целое, не превосходящее а); выпуклая оболочка векторов множества X; коническая оболочка векторов множества X.

Если вектор умножается слева на матрицу, он считается столбцом, если справа строкой. Равенства и неравенства между векторами понимаются в координатном смысле.

Введение

Введение диссертации (часть автореферата) на тему «Алгоритмические вопросы построения двойственного описания выпуклого полиэдра»

Актуальность темы исследования

В различных областях дискретной математики и математической кибернетики, а также в других разделах математики и приложениях встречается такой объект, как выпуклый полиэдр (многогранное множество, многогранник). Каждый выпуклый полиэдр (далее называемый просто полиэдром) может быть представлен в одном из двух видов: как множество решений конечной системы линейных неравенств и как сумма выпуклой и конической оболочек конечных систем векторов [6, 20, 50]. Данные способы задания полиэдра называются, соответственно, фасетным и вершинным описанием.

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

Задача построения двойственного описания полиэдра является одной из центральных в теории систем линейных неравенств [18, 22] и имеет важные приложения. В числе приложений можно выделить решение задач оптимизации [9, 51], вычислительную биологию [61], теорию управления [19], анализ программ для ЭВМ [44].

Для практически важных случаев размерности 2 и 3 разработаны эффективные алгоритмы построения двойственного описания [16, 45]. В диссертации рассматривается существенно более сложный случай полиэдров произвольной размерности.

Одной из важных открытых проблем теории выпуклых полиэдров является вопрос о существовании алгоритмов построения двойственного описания, полиномиальных от суммарной длины входа и выхода [33, 54]. Таким образом, задача разработки эффективных алгоритмов построения двойственного описа-

ыия полиэдра представляется актуальной как с теоретической точки зрения, так и с практической.

Известно множество методов построения двойственного описания полиэдров в пространствах произвольной размерности. Они могут быть классифицированы по двум критериям [33].

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

Метод двойного описания [56] является одним из наиболее широко используемых и имеет множество модификаций, например, [10, 23, 47, 61]. Основным преимуществом метода двойного описания является работа с существенно вырожденными задачами. С другой стороны, метод относительно плохо справляется с задачами с избыточными входными данными (большое количество неравенств-следствий для задачи построения вершинного описания, большое количество внутренних точек для задачи построения фасетного описания), а также невырожденными и близкими к ним задачами. Поэтому представляет интерес получение оценок трудоемкости метода и его модификаций на различных классах полиэдров, а также разработка новых модификаций, сохраняющих достоинства оригинального метода и при этом эффективно (как с теоретической, так и с практической точки зрения) работающих на более широком классе задач.

Задача построения двойственного описания полиэдра может быть сведена к задаче исключения переменных из системы линейных неравенств [20]. Од-

ним из основных методов решения данной задачи является метод исключения Фурье Моцкина. При использовании правил С. Н. Черникова [22] этот метод является близким к методу двойного описания, что позволяет использовать идеи некоторых модификаций метода двойного описания для ускорения проверки правил Черникова в методе исключения Фурье Моцкина.

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

Цели и задачи диссертационной работы

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

Для достижения поставленных целей были определены следующие задачи исследования:

1. Разработка новой модификации метода двойного описания, эффективной на более широком классе входных данных по сравнению с оригинальным методом.

2. Ускорение проверки правил Черникова в методе исключения Фурье Моцкина путем сокращения перебора.

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

Научная новизна

Новыми являются следующие результаты работы:

1) предложена новая модификация метода двойного описания с использованием идей алгоритма Quickhull;

2) разработан новый способ проверки правил Черникова в методе исключения Фурье Моцкина, сокращающий количество операций по сравнению с традиционным;

3) предложен новый алгоритм для выделенного класса задач удаления неравенств из фасетного описания полиэдра.

Теоретическая и практическая значимость

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

Результаты диссертации могут найти применение в исследованиях, проводимых в Московском государственном университете им. М.В. Ломоносова, Федеральном исследовательском центре «Информатика и управление» РАН, Институте математики и механики им. H.H. Красовского УрО РАН, Ярославском государственном университете им. П. Г. Демидова, Южно-Уральском государственном университете, Институте проблем управления им. В. А. Трапезникова РАН, Нижегородском государственном университете им. Н.И. Лобачевского.

Положения, выносимые на защиту

• Предложена новая модификация метода двойного описания с использованием идей алгоритма Quickhull, получены оценки трудоемкости.

• Разработан способ ускорения проверки правил Черникова в методе исключения переменных Фурье Моцкина с использованием графов.

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

Степень достоверности и апробация результатов

Результаты диссертации научно обоснованы: приводятся математические доказательства корректности и оценок трудоемкости предлагаемых алгоритмов; результаты вычислительных экспериментов согласуются с теоретическими оценками и подтверждают эффективность разработанных алгоритмов.

Основные результаты диссертации обсуждались на заседаниях нижегородского семинара по дискретной математике, семинара НИИ прикладкой математики и кибернетики и лаборатории алгоритмов и технологий анализа сетевых структур (НИУ ВШЭ) и докладывались на 5 международных и всероссийских

конференциях:

•

приложения» (Екатеринбург, 2011);

щенная 100-летию С. Н. Черникова (Екатеринбург, 2012); операций» (Новосибирск, 2013); приложения» (Екатеринбург, 2015); 2015).

Публикации

Материалы диссертации опубликованы в 9 работах [А1-А9], из них 3 статьи в рецензируемых журналах [А1 АЗ], 1 свидетельство о государственной регистрации программы для ЭВМ [А4] и 5 тезисов докладов.

Личный вклад автора

В совместных публикациях личный вклад С. И. Бастракова является определяющим. Научному руководителю принадлежат некоторые идеи алгоритмов в работах [А1, А2], постановки задач и общее редактирование во всех работах. Проработки деталей алгоритмов, все доказательства, программные реализации и вычислительные эксперименты выполнены С. И. Бастраковым лично.

Структура и объем диссертации

Диссертация состоит из списка условных обозначений, введения, 4 глав, заключения и списка литературы. Общий объем диссертации 100 страниц, включая 7 рисунков. Список литературы включает 63 наименования на 6 страницах, список публикаций автора по теме диссертации включает 9 наименований на 2 страницах.

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

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

Во второй главе предлагается новая модификация метода двойного описания для построения остова полиэдрального конуса с использованием идей алгоритма С^шскЬиП. Приводятся оценки трудоемкости и результаты вычислительного эксперимента, подтверждающие эффективность предлагаемого алгоритма.

В третьей главе предлагается быстрый способ проверки правил Черникова в методе исключения Фурье Моцкина для исключения переменных из систем

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

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

В заключении кратко приводятся основные результаты диссертации.

Финансовая поддержка

Диссертация выполнена при финансовой поддержке РФФИ (гранты № 09-01-00545-а, 15-01-06249, 14-07-31318), а также госзадания № 1.115.2014/К.

Глава 1

Построение двойственного описания полиэдра

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

1.1. Основные понятия и обозначения

Используемые понятия и обозначения в основном заимствованы из монографий [6, 18, 20, 26, 50].

1.1.1. Полиэдры и политопы

Выпуклым, полиэдром (многогранным множеством, многогранником) в пространстве Р^ называется множество решений конечной системы линейных неравенств:

Р = {х ер ^ : Ах > Ь} , А ертха, Ь ерт (1.1)

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

Ах > Ь

зывается его фа,сетным описанием,. Фасетное описание полиэдра называется неприводимым, если система не содержит неравенств-следствий.

Согласно теореме Минковского Вейля, любой полиэдр также может быть представлен в виде суммы по-Минковскому выпуклой оболочки конечного мно-

j u:

жества точек и конической оболочки конечного множества векторов:

( n к

P = conv {vi, V2,..., Vn} + cone {ui, U2,..., Uk} = < ^av* + ^ в

n i=1 j=1 (1.2) a > 0, i = l, 2,... = l, в > 0, j = l, 2,... , & >,

i=1 J

где vi, V2,..., Vn,ui,U2,... ,Uk G Qd.

Совокупность множества точек V = {vi, v2,..., vn} и множества векторов U = {ui5u2,..., Uk}, порождающая полиэдр (1.2), называется его вершинным описанием. Вершинное описание (V, U) полиэдра P называется неприводимым, если никакая совокупность множеств (V', U'), такая, ч то V' С V, U 'С U, (V, U) = (V', U'), не является вершинным описанием P.

Ограниченный полиэдр называется политопом. Полиэдр является политопом тогда и только тогда, когда он может быть представлен в виде выпуклой оболочки конечной системы точек:

P = COnV {Vi,V2, ..., Vn} ,

где vi, V2,..., Vn G Qd.

P

iioro подпространства, содержащего полиэдр. Таким образом, размерность полиэдра совпадает с размерностью его аффинной оболочки. Обозначим dim P

P

1.1.2. Полиэдральные конусы

d

шений конечной однородной системы линейных неравенств:

C = {ж G Qd : Аж > 0} , A G Qmxd. (1.3)

Любой полиэдральный конус является полиэдром. В дальнейшем для краткости под конусом подразумевается полиэдральный конус.

Любой полиэдральный конус может быть представлен в виде конической оболочки конечной системы векторов в Qd:

C = cone {ui,u2,... ,Un} = j ^ аг щ : аг > 0, i = 1, 2,...,nj. (1.4)

Система векторов u1, u2,..., un порождает, конус (1.4). Неприводимая порождающая система векторов конуса называется его остовом, минимальная по числу векторов неприводимая порождающая система минимальным остовом. В дальнейшем изложении под U(C) будем понимать некоторый остов конуса C.

Ненулевой вектор u G C называется лучом конуса C. Два луча u,v G C будем называть равными и записывать u ~ v, если для некоторого a G Q, a > 0 выполнено равенство u = av. Луч u G C называется экстремальным, если из условий u = av + ew, а, в G Q, a, в > 0, v, w G C следует u ~ v ~ w.

Конус называется острым, если он не содержит ненулевых линейных подпространств. Необходимым и достаточным условием остроты конуса (1.3) является выполнение равенства rank A = d. Минимальный остов острого конуса определяется единственным образом с точностью до умножения векторов на положительные константы. Если конус (1.3) не является острым, он содержит ненулевое максимальное линейное подпространство L(C) = {ж G Qd : Ax = 0} и векторы минимального остова определяются единственным образом с точностью до умножения на положительные константы и добавления слагаемых из

L(C).

Каждому полиэдру P вида (1.1) может быть поставлен в соответствие конус

с(р )={(:) (-, a) (:) > «}■ м

Пусть известен некоторый остов конуса C(P). Тогда вершинное описание поли-

P = conv <(—,—,...,—J : и = {u0,ui,... ,ud)T G U{C{P)),u0 ^ 0 > + Vuo Uo Uo)

+ cone j(ubu2,... , ud)T : u = (u0,ui,... , ud)T G U(C(P)),u0 = 0 j .

(i.6)

Таким образом, имеется соответствие между вершинным и фасетным описаниями полиэдра P и конуса C(P).

1.1.3. Грани полиэдра

Пусть P — полиэдр в Qd. Неравенство аж > а0, где а G Qd,a0 G Q называ-

P

P С {ж G Qd : аж > а0} .

P

иое неравенство в равенство:

F(P, а, а0) = P П {ж G Qd : аж = а^} , P С {ж G Qd : аж > а^ . (1.7)

Любая грань полиэдра является полиэдром. Если аж > а0, где а = 0, является правильным неравенством для P и F(P, а, а0) = 0, то гиперплоскость ж G d : аж = а0 P

V(P)

P

жеством его крайних точек точек, не представимых в виде выпуклой комбинации других точек полиэдра:

V(P) = {ж G P : ж G conv (P \ {ж})} .

Рецессивным направлением полиэдра P называется ненулевой вектор u такой, что добавление его с любым положительным коэффициентом к любой

рецессивные направления удовлетворяют системе неравенств Аж > 0. Полиэдр является политопом тогда и только тогда, когда он не содержит рецессивных направлений.

Грани размерности 1 называются ребрами полиэдра, обозначим E(P) мно-

P

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

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

Фасетам,и (гипергранями) полиэдра называется его грани размерности dim P — 1, обозначим H(P) множество фасет полиэдра P. Гребням,и называются грани размерности dim P — 2, обознач им R(P) множество гребней полиэдра P

P

венств фасетного описания, которые обращаются в равенство на всех точках грани. Множество / С {1, 2,..., m} называется базой грани F полиэдра P, если

F = P П {ж GQd : А(/ )ж = b(/)} , V/' с / : F = P П {ж G Qd : А(/')ж = b(/')} ,

где А(/), А(/') являются подматрицами А, составленными из строк с номерами из множеств /, /и b(/), b(/') являются соответствующими иодвекторами b. Грань полиэдра может иметь несколько баз.

1.1.4. Решетка граней полиэдра

стично упорядоченное множество r(P), называемое решеткой граней полиэдра [20, 60]:

r(P) = {F(P, а, а0)} , (1.8)

где F(P, а, а0) определяется в соответствии с (1.7).

Обозначим Г^Р), i = 0, l,..., dimP, множество всех граней полиэдра размерности i и r-i(P) множество, состоящее из пустой грани:

Г (P) = {7 G r(P) : dim 7 = i} , i = 0, l,..., dim P

(1.9)

r-i(P ) = {0}

Для любого полиэдра P справедливо р(P) = {P}. Все грани полиэдра, не равные пустому множеству и всему полиэдру, называются собственными и имеют размерность от 0 до dim P — l включительно. Обозначим количество

iP

fi(P) = |ri(P)|, i = —l, 0,..., dim P. (1.10)

Вектор длины dim P + 2, составленный из эле ментов fi(P), i = — l, 0,..., dim P,

P

f (P) = (f—i(P), f0(P),..., fdimp(P)). (1.11)

f(P)

ни:

dim P

7 (p ) = £ f (p ). (1.12)

¿=0

1.1.5. Двойственность полиэдров

Решетка граней задает комбинаторную структуру полиэдра. Полиэдры называются изоморфны,ми (комбинаторно эквивалентными), если их решетки

граней изоморфны в смысле частично упорядоченных множеств [1, 4]. Полиэдры называются двойственными, если их решетки граней антиизоморфны. В частности, если полиэдры Р и Р* являются двойственными, то вершины Р соответствуют фасетам Р*, ребра Р — гребням Р* и наоборот.

Р*

Р

Р*

полиэдр, а любой полиэдр с решеткой граней, антиизоморфной решетке граней Р

Пусть полиэдр задан в виде

Р = {ж ер ^ : Ах < 1} , А ертх^. (1.13)

К такому виду можно привести любой полиэдр, определяемый системой вида (1.1), внутренность которого содержит начало координат. Полярой для полиэдра (1.13) называется полиэдр

Рд = сопу{ахТ,а2Т, ...,атТ} , (1.14)

где ах, а2,..., ат — строки матрицы А (1.13). Полиэдры (1.13) и (1.14) являются двойственными.

1.1.6. Некоторые классы полиэдров

Выпуклая оболочка ¿+1 аффинно независимой точки называется ¿-мерным симплексом, будем обозначать его Т^. Характеристический вектор симплекса имеет следующий вид:

/№)= (( + 1) , г = -1, 0,

( ( + 1 ( + 1

Полиэдр называется симплициальным,, если все его фасеты являются симплексами соответствующей размерности; в этом случае все собственные грани

простым, если каждая из его вершин имеет единственную базу содержится dim P

простым полиэдром и наоборот. Единственным полиэдром, являющимся сим-плициальным и простым, является симплекс. Обозначим Hd d-мерный гиперкуб:

Hd = {ж GQd : —l < жг < l, i = l, 2,..., d} .

Гиперкуб является простым полиэдром, его характеристический вектор имеет вид:

fi(Hd) = 2d—^d), i = 0, l,..., d.

В частности, Hd имеет 2d вершин и 2d фасет.

Двойственный к Hd симилициальный политоп называется d-крестом:

Hd* = conv {(l, 0,0,..., 0)T, (—l, 0, 0,..., 0)T, (0, l, 0,..., 0)T, (0, —l, 0,..., 0)T,

..., (0,0,..., 0, l)T, (0, 0,..., 0, — l)T}

В частности, Hd* имеет 2d вершин и 2d фасет.

Циклический политоп размерности d с n вершинами, обозначим его Cd(n),

является выпуклой оболочкой n вершин, лежащих на кривой t ^ (t, t2,..., td) d

Cd(n) = conv {ж(^),ж^2),...,ж(У} , ж(t) = (t,t2,...,td)T ,ti <t2 < ••• <tn.

Характеристический вектор циклического политопа определяется следующим утверждением.

Утверждение 1.1 ([50])

*<гч< w n — ¿(n — i — 2) fc^ (n — l — j\( n — i — l \

MCdn =--—i\ d . ,

n — i — l j=0 V i + l — j J \2j — i — l + V

где 5 = d - 2 |_f J

Обозначим ^¿(п) количество фасет (-мерного циклического политопа с п вершинами:

ты = /4-,(с„(п)) = (" ~ + (" ~ •

(

^(п) е 0 (п^) .

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

Теорема 1.1 ([20, 55]) Для любого полиэдра Р С р|У(Р)| = п:

/г(Р) < /г(ОД), г = -1,0,..., (. Следствие 1.1 ([20, 55]) Для любого полиэдра Р С рЛ, |Н(Р)| = т:

/г(Р) < /*(^(т)*), г = -1, 0,...,(.

Таким образом, функция ^¿(п), определенная в (1.15), является максимальным количеством фасет полиэдра в С^ с п вершинами и максимальным количеством векторов вершинного описания полиэдра в С^ с п фасетами.

Определим операцию произведения полиэдров следующим образом [33]. Рассмотрим прямое произведение полиэдров Рх е Р^ и Р2 е

Рх х Р2 = {(рх,Р2) : Рх е Рх, Р2 е Р2} С с^1 х С^2

Можно интерпретировать Рх х Р2 как множество векторов в пространстве (в силу естественной биекции между и С^1 х Р¿2), в этом случае оно

является полиэдром размерности ^ш(Рх х Р2) = dim Рх +dim Р2. В дальнейшем под произведением полиэдров будем понимать такую его интерпретацию.

Рх Р2 Рх х Р2

Если Р! является ¿х-мерпой гранью Рх и Р2 — ¿2-мерной гранью Р2, то Рх х Р2

является (¿1 + ¿2)-мерной гранью Р1 х Р2 и любая грань Р1 х Р2 может быть представлена в таком виде. Справедливы соотношения [33]:

/о(Р х Р2) = /с(Р1)/о(Р2) (1.16)

/кт Р\ Р2 — 1 № х Р2) — /йшР1 — 1(Р1) + /йшР2 —1(Р2) (1.17)

7(р1хр2) = 7(р1)7(р2) (1.18)

С помощью операции произведения определим следующие семейства полиэдров:

• произведение двух ¿-мерных симплексов:

тт2л — ^ х Т^; (1.19)

• произведение двух ¿-мерных циклических политопов с п вершинами:

СС^(п) — Сй(п) х сй(п); (1.20)

СС2(52(п) = С2з(п) х С2,(п) х • • • х С25{п\ (1.21)

4-V-'

5

Пусть V — некоторая вершина полиэдра Р. Обозначим д^,Р) количество фасет полиэдра сопу(Р \ {V}), не являющихся фасетами р. Для семейства полиэдров СС252 (п) справедливо следующее утверждение.

Утверждение 1.2 ([33])

д (V, СС252(п)) е 0 (п(5—1)5) , Vv е V (СС252(п))

1.2. Постановка задачи

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

операций над полиэдрами. В связи с этим возникает задача перехода между вершинным и фасетным описаниями полиэдра. Некоторые приложения данной задачи рассмотрены в параграфе 1.5.

Р

нии вершинного описания (1.2) по заданному фасетному описанию (1.1), то есть нахождении системы векторов г>х,-и2,...,г>п, их,и2,...,е Рл по заданной системе линейных неравенств Аж > Ь. Задача построения фасетного описания полиэдра состоит в нахождении фасетного описания (1.1) по заданному вершинному описанию (1.2).

Вершинное и фасетное описания полиэдра являются двойственными друг

Р

Р*

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

Задача построения двойственного описания полиэдра в С^ может быть сведена к аналогичной задаче для конуса в С^+х следующим способом [20]. Пусть

Р

му описанию вида (1.1). Строится конус С(Р) (1.5) в С^+х, соответствующий полиэдру Р. Находится остов конуса С(Р), вершинное описание Р определяется с помощью соотношения (1.6).

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

фициеытами:

P = {x e Qd : Ax > b} , A e Zmxd, b e Zm (1.22)

Входом являются (m + 1)d коэффициентов системы неравенств (1.22): md коэффициентов матрицы A и m коэффициентов вектора b. Предполагается, что арифметические операции над коэффициентами, возникающими в процессе построения двойственного описания, выполняются за единицу времени. Вопрос о битовой длине входа и росте коэффициентов обсуждается в параграфе 1.4.

1.3. Методы построения двойственного описания полиэдра

В настоящем параграфе описываются основные методы построения двойственного описания полиэдра в пространствах произвольной размерности. Для практически важных и существенно более простых случаев d = 2, 3 известно множество эффективных алгоритмов, их обзор можно найти, например, в [16, 45, 57].

Изложение производится в терминах задачи построения вершинного описания полиэдра, подразумевая указанную в параграфе 1.2 сводимость задач построения вершинного и фасетного описания полиэдра друг к другу, а также сводимость задачи построения двойственного полиэдра в Qd к аналогичной задаче для полиэдрального конуса в Qd+1. Приводимая классификация методов построения двойственного описания полиэдра основана на [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] и другие.

Список литературы диссертационного исследования кандидат наук Бастраков Сергей Иванович, 2016 год

Список литературы

1. Александров П. С. Введение в теорию множеств и общую топологию. М.: Наука, 1977. 368 с.

2. Веселов С. И., Парубочий И. Е., Шевченко В. Н. Программа нахождения остова конуса неотрицательных решений системы линейных неравенств // Системные и прикладные программы. Часть 2. Горький: Издательство Горь-ковского государственного университета. 1984. Т. 24, № 19. С. 83 92.

3. Гергель В. П., Стронгин Р. Г. Основы параллельных вычислений для многопроцессорных вычислительных систем / Учебное пособие. 2 изд. Нижний Новгород: Издательство Нижегородского госуниверситета, 2003. 184 с.

4. Гуров С. 14. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. М.: Либроком, 2013. 352 с.

5. Деза М. М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.

6. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

7. Еремин 14. 14. О некоторых свойствах узлов системы линейных неравенств // Успехи математических наук. 1956. Т. 11, № 2. С. 169 172.

8. Еремин 14. 14. Теория линейной оптимизации. Екатеринбург: Изд-во УрО РАН, 1999. 312 с.

9. Еремин 14. 14., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1970. 191 с.

10. Золотых Н. Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. 2012. Т. 52, № 1. С. 153 163.

11. Золотых Н. К)., Лялин С. С. Параллельный алгоритм нахождения общего решения системы линейных неравенств // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 5. С. 193 199.

12. Лукацкий A. M., Шапот Д. В. Конструктивный алгоритм свертывания систем линейных неравенств высокой размерности // Журнал вычислительной математики и математической физики. 2008. № 7. С. 1167 1180.

13. Максименко А. Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Журнал вычислительной математики и математической физики. 2004. № 9. С. 1693 1696.

14. Максименко А. Н. Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжера // Дискретный анализ и исследование операций. 2011. № 3. С. 76 83.

15. Панюков А. В. Представление суммы Минковского для двух полиэдров системой линейных неравенств // Вестник ЮУрГУ. Серия Математическое моделирование и программирование. 2012. № 14. С. 108 119.

16. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989. 478 с.

17. Стрекаловский А. С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. 356 с.

18. Схрейвер А. Теория линейного и целочисленного программирования. Том 1. М.: Мир, 1991. 360 с.

19. Филимонов Н. В., Деменков M. Н. Дискретное упреждающее управление линейными динамическими объектами с параметрической полиэдральной неопределенностью // Мехатроника, автоматизация, управление. 2008. № 9. С. 2 7.

20. Циглер Г. Теория многогранников. М.: МЦНМО, 2014. 586 с.

21. Черников С. Н. Свертывание систем линейных неравенств // Доклады АН СССР. 1960. Т. 131, № 3. С. 518 521.

22. Черников С. Н. Линейные неравенства. М.: Наука, 1968. 488 с.

23. Черникова Н. В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств // Журнал вычислительной математики и математической физики. 1965. Т. 5, № 2. С. 334 337.

24. Черникова Н. В. Алгоритм для отыскания множества всех решений задачи линейного программирования // Журнал вычислительной математики и математической физики. 1968. Т. 8, № 6. С. 1387 1399.

25. Черных О. Л. Построение выпуклой оболочки конечного множества точек на основе триангуляции // Журнал вычислительной математики и математической физики. 1991. Т. 31, № 8. С. 1231 1242.

26. Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. 160 с.

27. Шевченко В. Н., Груздев Д. В. Модификация алгоритма Фурье-Моцкина для построения триангуляции // Дискретный анализ и исследование операций. 2003. Т. 10, № 1. С. 53 64.

28. Шевченко В. Н., Груздев Д. В. Модификация алгоритма Фурье Моцкина для построения триангуляции и ее звездной развертки // Дискретный анализ и исследование операций. 2006. Т. 13, № 1. С. 77 94.

29. Шевченко В. Н., Чирков А. Ю. О сложности построения остова конуса // X Всероссийская конференция «Математическое программирование и приложения. Екатеринбург: Уральское отделение РАН. 1997. С. 237.

30. An algorithm for integer solutions to linear programs // Ed. by R. L. Graves, P. Wolfe. Recent Advances in Mathematical Programming. New York: McGraw-Hill, 1967. P. 269 302.

31. Amato G., Scozzari F., Zaffanella E. Efficient Constraint/Generator Removal from Double Description of Polyhedra // Electronic Notes in Theoretical Computer Science. 2014. Vol. 307. P. 3 15.

32. Avis D. Irs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm // Polytopes Combinatorics and Computation / Ed. by G. Kalai, G. Ziegler. Birkhauser Verlag, 2000. P. 177 198.

33. Avis D., Bremner D., Seidel R. How Good are Convex Hull Algorithms? // Computational Geometry. 1997. Vol. 2, no. 2. P. 265 301.

34. Avis D., Fukuda K. A Pivoting Algorithm for Convex Hull and Vertex Enumera-

tion of Arrangements and Polyhedra // Discrete and Computational Geometry. 1992. Vol. 8. P. 296 313.

35. Bagnara R., Hill P. M., Zaffanella E. Applications of polyhedral computations to the analysis and verification of hardware and software systems // Theoretical Computer Science. 2009. Vol. 410. P. 4672 4691.

36. Barber C. B., Dobkin D. P., Huhdanpaa H. The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software. 1996. Vol. 22, no. 4. P. 469 483.

37. Bremner D. Incremental Convex Hull Algorithms Are Not Output Sensitive // Discrete and Computational Geometry. 1999. Vol. 21, no. 1. P. 57 68.

38. Bremner D., Fukuda K., Marzetta A. Primal-Dual Methods for Vertex and Facet Enumeration // Discrete and Computational Geometry. 1998. Vol. 20. P. 333 357.

39. Burger E. Uber homogene lineare Ungleichungssysteme // Zeitschrift Angewandte Math. Mechanik. 1956. Vol. 36. P. 135 139.

40. Bykat A. Convex hull of a finite set of points in two dimensions // Information Processing Letters. 1978. Vol. 7, no. 6. P. 296 298.

41. Chand D., Kapur S. An Algorithm for Convex Polytopes // Journal of the ACM. 1970. Vol. 17, no. 1. P. 78 86.

42. Chazelle B. An Optimal Convex Hull Algorithm in Any Fixed Dimension // Discrete and Computational Geom. 1993. Vol. 10. P. 377 409.

43. Clarkson K. L., Shor P. Applications of Random Sampling in Computational Geometry // Discrete and Computational Geometry. 1989. Vol. 4, no. 1. P. 387 421.

44. Cousot P., Halbwachs N. Automatic discovery of linear restraints among variables of a program // Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages. 1978. P. 84 96.

45. de Berg M., Cheong O., van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed. edition. Santa Clara, CA, USA:

46

47

48

49

50

51

52

53

54

55

56

57

58

59

Springer-Verlag TELOS, 2008. 386 p.

Eddy W. A New Convex Hull Algorithm for Planar Sets // ACM Transactions of Mathematical Software. 1977. Vol. 3, no. 4. P. 398 403. Fukuda K., Prodon A. Double Description Method Revisited // Lecture Notes in Computer Science. 1996. Vol. 1120. P. 91 111.

Gagneur J., Klamt S. Computation of elementary modes: a unifying framework and the new binary approach // BMC Bioinformatics. 2004. Vol. 5, no. 175. Green P. J., Silverman B. W. Constructing the Convex Hull of a Set of Points in the Plane // Computer Journal. 1979. P. 262 266. Griinbaum B. Convex polytopes. London: Wiley, 1967. 456 p. Horst R., Pardalos P. M., Thoai N. Introduction to Global Optimization. Non-convex optimization and its applications. Vol. 3e. Kluwer Academic Publishers, 1995. 318 p.

Horst R., Thoai N. DC Programming: Overview // Journal of optimization theory and applications. 1999. Vol. 103, no. 1. P. 1 43.

J. O'Rourke J. E. G. Handbook of Discrete and Computational Geometry. 2nd ed. edition. Chapman and Hall/CRC, 2004. 1560 p.

Khachiyan L., Boros E., Borys K. et al. Generating All Vertices of a Polyhedron Is Hard // Discrete and Computational Geometry. 2008. no. 39. P. 174 190. McMullen P. The maximum numbers of faces of a convex polytope // Mathe-matika. 1971. no. 17. P. 179 184.

Motzkin T. S., Raiffa H., Thompson G. L., Trail R. M. The Double Description Method // Contributions to the Theory of Games. 1953. P. 51 73. O'Rourke J. Computational geometry in C. 2nd ed. edition. Cambridge University Press, 1998. 376 p.

Seidel R. A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions // Technical Report, University of British Columbia, Dept. of Computer Science. 1981.

Seidel R. Output-size sensitive algorithms for constructive problems in compu-

tational geometry // Ph.D. thesis. Dept. Comp. Sci., Cornell Univ. 1986.

60. Stanley R. P. Enumerative Combinatorics: Volume 1, 2nd. ed. Cambridge University Press, 2001. 600 p.

61. Terzer M., Stelling J. Accelerating the Computation of Elementary Modes Using Pattern Trees // Lecture Notes in Computer Science. 2006. Vol. 4175. P. 333 343.

62. Terzer M., Stelling J. Large-scale computation of elementary flux modes with bit pattern trees // Systems biology. 2008. Vol. 24, no. 19. P. 2229 2235.

63. Wagner C. Nullspace approach to determine the elementary modes of chemical reaction systems // Journal of Physical Chemistry B. 2004. Vol. 108. P. 2425 2431.

Список публикаций автора по теме диссертации

Публикации в изданиях, рекомендованных ВАК

А1. Бастраков С. И., Золотых Н. Ю. Использование идей алгоритма С^шскЬиП в методе двойного описания // Вычислительные методы и программирование: новые вычислительные технологии. 2011. Т. 12, № 1. С. 232 237.

А2. Бастраков С. И., Золотых Н.Ю. Быстрый способ проверки правила Черникова в методе исключения Фурье Моцкина // Журнал вычислительной математики и математической физики. 2015. Т. 55, № 1. С. 165 172.

АЗ. Бастраков С. И., Золотых Н.Ю. Удаление неравенств из фасетного описания многогранника // Труды института математики и механики УрО РАН. 2015. Т. 21, № 3. С. 37 45.

Свидетельства о государственной регистрации программы для ЭВМ

А4. Бастраков С. 14., Золотых Н.Ю. Свидетельство о государственной регистрации программы для ЭВМ № 2013611385 «Программная система нахождения двойственного описания полиэдра» от 9 января 2013.

Другие публикации и тезисы докладов

А5. Бастраков С. 14., Золотых Н.Ю. Использование метода двойного описания при решении задач БС оптимизации // Информационный бюллетень № 13 XV Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2 6 марта 2015 (тезисы докладов). Екатеринбург: УрО РАН, 2015. С. 16 17.

А6. Бастраков С. И., Золотых Н. Ю. Использование идей алгоритма Quickhull в методе двойного описания //Информационный бюллетень № 12 XIV Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 28 февраля 4 марта 2011. Екатеринбург: УрО РАН, 2011. С. 23 24.

А7. Бастраков С. И., Золотых Н. Ю. Новые модификации метода двойного описания // Тезисы Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н. Черникова, Екатеринбург, 14 19 мая 2012. Екатеринбург: УМЦ-УПИ, 2012. С. 11 13.

А8. Бастраков С. И., Золотых Н. Ю. Быстрый метод проверки правила Черникова в методе исключения Фурье Моцкина // Труды Международной конференции «Дискретная оптимизация и исследование операций», Новосибирск, 24 28 июня 2013. Новосибирск: Изд-во Института математики, 2013. С. 144.

А9. S. Bastrakov. An Algorithm for Constraint/Generator Removal from Double Description of Polyhedra [Электронный ресурс] // The Fifth International Conference on Network Analysis (NET 2015), Nizhni Novgorod, 18-200 May 2015. P. 23. Режим доступа:

https://www.hse.ru/data/2015/05/09/1098851531/full7o20net7o202015. pdf.