lrsfourier - Интернет в облаке

ПРОГРАММА:

ИМЯ

lrslib - Преобразование между представлениями выпуклых многогранников.

СИНТАКСИС

LRS input.ine

LRS input.ine | lrsbuffer

Ирсфурье файл.ine [из файла]

дублировать input.ine

ОПИСАНИЕ

Многогранник можно описать списком неравенств (H-представление) или как списком
его вершин и крайних лучей (V-образное представление). LRS это программа на C, которая преобразует
От H-представления многогранника к его V-представлению, и наоборот. Эти проблемы
известны соответственно на вершина перечисление и выпуклый корпус проблемам.

Фукуда FAQ страница[1] содержит более подробное введение в проблему, а также
много полезных советов для нового пользователя.

lrsbuffer может удалить дублирующийся вывод. дублировать находит избыточное неравенство в
вход.

ФАЙЛОВ ФОРМАТЫ

Форматы файлов были разработаны совместно с Komei Fukuda и совместимы с CDD[2].

Вход для LRS является H- или V-представлением многогранника.

имя
{линия представления}
{параметры}
{линейности[3]}
начинать
мин рациональный
{матрица ввода}
конец
{параметры}

имя имя многогранника, задаваемое пользователем. Комментарии могут появиться перед началом или
после окончания, и чтобы избежать толкования как варианта, следует начинать со специальной
такой символ, как «*» или «#».

имя имя многогранника, задаваемое пользователем. представление линия либо
«H-представление» или «V-представление». Если не указано, предполагается H-представление. В
входные коэффициенты читаются в свободном формате и не проверяются на тип. Коэффициенты
разделенные пробелом. m - количество строк, а n - количество столбцов входных данных.
матрица.

H-представление
Целое число m - это количество неравенств, а целое число n - это размерность
вход +1. Список неравенств содержит коэффициенты неравенств вида

a0 + a1x1 + ... + an-1 xn-1> = 0.

Это неравенство вводится как строка

а0 а1 ... ан-1

Коэффициенты можно вводить как целые или рациональные числа в формате x / y.

V-образное представление
Целое число m - это количество вершин и лучей, а целое число n - это размерность
вход +1. Каждая вершина задана в виде

1 v0 v 1 ... vn-1

Каждый луч задан в виде

0 r0 r 1 ... rn-1

где r0 r 1 ... rn-1 - точка на луче.

В каждом файле должна быть хотя бы одна вершина. Для ограниченных многогранников не будет
лучи вошли. Коэффициенты можно вводить как целые или рациональные числа в формате x / y.

Внимание для CDD пользователей: LRS использует по существу тот же формат файла, что и CDD. Файлы подготовлены для
CDD должен работать с небольшими изменениями или без них. Обратите внимание, что V-представление
соответствует варианту "корпус" в CDD. Параметры, специфичные для CDD можно оставить на входе
файлы и будут проигнорированы LRS. Обратите внимание на входные файлы для LRS читаются в свободном формате,
после линии m n рациональный, LRS будет искать точно m * n рациональных или целых чисел, разделенных
пробелом (пробел, возврат каретки, табуляция и т. д.). LRS не будет "отбрасывать" лишние столбцы
ввод, если n меньше количества предоставленных столбцов.

Базовый Опции
Практически все варианты размещены после конечный оператор, поддерживающий совместимость с CDD.
Если это не так, об этом будет сказано отдельно.

все базы Эта опция указывает LRS чтобы перечислить каждую вершину (или фасет) для каждой из ее баз.
Результат дупликация[4].[5] Этот вариант часто сочетается с printcobasis.

связанный x Использование с H-представлением - для lrs или nash Либо максимизировать, либо минимизировать
вариант должен быть выбран. x - целое или рациональное число. Для максимизации (соотв.
минимизация) обратное дерево поиска обрезается всякий раз, когда текущее целевое значение
меньше (соответственно больше), чем x.

кэш nLRS сохраняет последние n словарей в обратном дереве поиска. Это ускоряет
шаг возврата, но требует больше памяти.

отлаживать начальная основа окончаниеРаспечатайте загадочный, но подробный след, словари и т. Д.
начиная с # B = начальная основа и заканчивая # B = конечная основа. отлаживать 0 0 дает полный
проследить.

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

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

Оценки k Оцените размер вывода. Используется вместе с maxdepth - см.
Предварительный расчет.[6]

геометрический // H-представление или только опция voronoi // С этой опцией каждый луч
печатается вместе с вершиной, с которой он инцидентен. Для получения дополнительной информации см.
Геометрические лучи в Советы и Комментарии[5].

падениеЭта опция автоматически включается печать , так что см. ниже
описание этого варианта сначала. Может использоваться с printcobasis n. (Версия 4.2b) .PP Для
входное H-представление, индексы всех входных неравенств, содержащих вершину / луч,
вот-вот будет выведен. Для симплициального лица нового выхода нет, так как эти индексы
уже перечислены. В противном случае дополнительные жесткие неравенства указываются после двоеточия.
.PP Для входного V-представления, индексы всех входных вершин / лучей, лежащих на фасете.
который вот-вот будет выведен. Помеченный звездочкой индекс указывает, что эта вершина также находится в
cobasis, но не содержится в фасете. Возникает из-за используемой подъемной операции.
с входными V-представлениями.

# инцидентТо же, что и printcobasis. Включено для совместимости с компакт-диск.

линейность k i1i2 i ... ikВходные данные содержат k линейностей в строках i1i2i ... ik
входным файлом являются уравнения. Видеть Линейности.[3]

Максимальная глубина k Поиск будет обрезан на глубине k. Все базы с глубиной меньше или
равный k, будет вычислен. k - неотрицательное целое число, и этот параметр используется для
оценки - см. Предварительный расчет.[6]Внимание: Для H-представлений лучи на глубине k не будут
сообщил. Для V-представлений фасеты на глубине k не сообщаются.

максимизировать a0 а1 ... ан-1 // Только H-представление //

минимизировать a0 а1 ... ан-1 // Только H-представление //

Если используется с lrs, начальная вершина максимизирует (или минимизирует) функцию a0 + a1x1 + ...
+ an-1 xn-1, чтобы избежать двойного вырождения, может потребоваться опция двойного возмущения.
Равновесия и Линейные приводы Программирование[7]

максимальный вывод n Ограничивает количество выводимых линий (вершин + лучей или граней) до n

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

неотрицательное // Эта опция должна стоять перед оператором begin // // Только H-представление
// Ошибка: может использоваться, только если начало координат является вершиной многогранника. Для задач, где
вход является H-представлением формы b + Ax> = 0, x> = 0 (т.е. все переменные
неотрицательный, все ограничения неравенства) неотрицательный
ограничения явно, если используется неотрицательный параметр. Этот параметр нельзя использовать для
V-представления или с опцией линейности (в этом случае линейности будут
рассматривается как неравенство). Эта опция может использоваться с избыточностью, но подразумевается
Ограничения неотрицательности сами по себе не проверяются на избыточность. Чтобы проверить все это
необходимо явно ввести ограничения неотрицательности во входной файл. (В Ver
4.1 начало координат должно быть вершиной).

печать k;Изменено в lrs 4.0 Каждый k-й кобазис печатается. Если k опущено,
cobasis печатается для каждой выводимой вершины / луча / фасета. На долгое время это полезно
время от времени печатать кобазис, чтобы при необходимости можно было перезапустить программу.
H-представление: Если вход является H-представлением, кобазис - это список индексов
неравенства из входного файла, определяющие текущую вершину или луч. См. Вариант
падение выше для получения дополнительной информации. Для лучей также печатается кобазис. В этом случае
кобазис - это кобазис вершины, из которой исходит луч. Один из показателей
помечен звездочкой, это означает, что неравенство необходимо исключить из кобазиса, чтобы определить
луч. В качестве альтернативы, если все базыиспользуется опция, все кобазы будут распечатаны.
V-образное представление: Если вход является V-представлением, кобазис - это список входных данных.
вершины / лучи, определяющие текущий фасет. См. Вариант падение выше для большего
Информация. Инициировать LRS с этой грани все 4 индекса должны быть указаны в таком порядке
(опустите *).

принты Новое в версии 4.2; // Использование с H-представлением // lrs выводит список
индексы входных неравенств, которые выполняются строго для текущей вершины, т.е.
соответствующая переменная резерва положительна. Если установлено неотрицательное значение, список также будет
включить индексы n + i для каждой положительной переменной решения xi. Проект Использован
ИрсфурьеТолько [8].

перезапуск V# R# B# глубина {грань #s or вершина / луч #s} Изменено в lrs4.0 LRS может быть
перезапускается с любого известного кобазиса. Расчет продолжится до нормального завершения. Все
информации содержится в выходных данных печать вариант. заказ of
домен Индексы is очень важный, введите их в точности так, как они отображаются на выходе из
ранее прерванный запуск.

стартовый i1i2i ... в-1 Это позволяет пользователю указать известную кобазису для
начало обратного поиска. i1i2i ... в-1 список неравенств (при
H-представление) или вершины / лучи (для V-представления), которые определяют кобазис. Если это
недопустимый, или эта опция не указана, LRS найдет свой стартовый кобазис. В
дерево обратного поиска обрезается (сокращается) всякий раз, когда встречается новая вершина. Примечание: это
отмечает, что обязательно производит набор всех вершин, смежных с оптимальной вершиной в
многогранник, но только их подмножество.

подробныйРаспечатайте чуть более подробную информацию о пробеге.

объем // Только V-представление // Вычислить объем - см. Раздел Объём Расчет.[9]

вороной // Только V-представление - помещается сразу после оператора end // Вычислить
Диаграмма Вороного - см. Раздел Вороного Диаграммы.[10]

ПРИМЕЧАНИЯ

1. Страница часто задаваемых вопросов
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. компакт-диск
http://www.cs.mcgill.ca/% 7Efukuda / soft / cdd_home / cdd.html

3. линейности
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linearities

4. Дублирование вывода
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Output% 20Duplication

5.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Hints% 20and% 20Comments

6. Оценка.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Estimation

7. Линейное программирование.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linear% 20Программирование

8. Ирсфурье
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # fourier

9. Расчет объема.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Volume% 20Computation

10. Диаграммы Вороного.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Voronoi% 20Diagrams

Используйте lrsfourier онлайн с помощью сервисов onworks.net