lrsfourier - クラウドでオンライン

プログラム：

NAME

lrslib-凸多面体の再プリセット間で変換します。

SYNOPSIS

LRS 入力.ine

LRS 入力.ine | lrsバッファ

ルズフーリエ ファイル.ine [ファイルアウト]

冗長化 入力.ine

DESCRIPTION

多面体は、不等式のリストで表すことができます（H表現） またはリストによる
その頂点と極端な光線の（V表現）. LRS を変換するCプログラムです
多面体のH表現からV表現へ、またはその逆。 これらの問題
それぞれで知られています 頂点 列挙 & 船体 問題.

福田さん よくある質問 ページ[1]には、問題のより詳細な紹介と、
新規ユーザーのための多くの役立つヒント。

lrsバッファ 重複する出力を削除できます。 冗長化 で冗長な不等式を見つけます
入力。

FILE 書式

ファイル形式は福田光明と共同開発されたもので、 CDD[2]。

の入力 LRS ポリトープのHまたはV表現です。

名
{代表線}
{オプション}
{直線性[3]}
始まる
mn有理
{入力行列}
end
{オプション}

名 ポリトープのユーザー指定の名前です。 コメントは、開始前または開始前に表示される場合があります
終了後、オプションとしての解釈を避けるために、特別なものから始める必要があります
「*」や「＃」などの文字。

名 ポリトープのユーザー指定の名前です。 表現 ライン どちらかです
「H表現」または「V表現」。 省略した場合、H表現が想定されます。 NS
入力係数は自由形式で読み取られ、タイプはチェックされません。 係数は
空白で区切られます。 mは行数、nは入力の列数です。
マトリックス。

H表現
整数mは不等式の数であり、整数nは不等式の次元です。
入力+1。 不等式のリストには、形式の不等式の係数が含まれています

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

この不等式は線として入力されます

a0 a1 ... an-1

係数は、x / yの形式で整数または有理数として入力できます。

V表現
整数mは頂点と光線の数であり、整数nは次の次元です。
入力+1。 各頂点は次の形式で与えられます

1 v0 v 1 ... vn-1

各光線は次の形式で与えられます

0 r0 r 1 ... rn-1

ここで、r0 r 1 ... rn-1は光線上の点です。

各ファイルには少なくともXNUMXつの頂点が必要です。 有界多面体の場合、
光線が入った。 係数は、x / yの形式で整数または有理数として入力できます。

Note for CDD users: LRS 本質的に同じファイル形式を使用します CDD。 のために準備されたファイル
CDD ほとんどまたはまったく変更せずに動作するはずです。 V表現に注意してください
の「船体」オプションに対応します CDD。 に固有のオプション CDD 入力に残すことができます
ファイルとによって無視されます LRS。 の入力ファイルに注意してください LRS 自由形式で読まれます、
行の後 m n 合理的な, LRS 正確にm * n個の有理数または分離された整数を検索します
空白（空白、キャリッジリターン、タブなど）。 LRS の余分な列を「ドロップ」しません
nが指定された列数より少ない場合に入力します。

Basic オプション
ほとんどすべてのオプションが配置されます After との互換性を維持しながら、endステートメント CDD.
そうでない場合は、明示的に言及されます。

すべての拠点 このオプションは指示します LRS 各ベースの各頂点（またはファセット）を一覧表示します。
出力 複製【4].[5]このオプションは、多くの場合、printcobasisと組み合わされます。

結合した x H表現で使用-lrsまたはnashの場合最大化または最小化のいずれか
オプションを選択する必要があります。 xは整数または有理数です。 最大化のために（または。
最小化）逆検索ツリーは、現在の目的値が常に切り捨てられます
xよりも小さい（または多い）。

キャッシュ nLRS 最新のn個の辞書を逆検索ツリーに格納します。 これはスピードアップします
バックトラッキングステップですが、より多くのメモリが必要です。

debug 開始基準 エンディングベース不可解だが詳細なトレース、辞書などを印刷します。
＃B = startingbasisで始まり、＃B = endingbasisで終わります。 debug 0 0 完全な
トレース。

数字 n 配置 　 始まる ステートメント nは、小数点以下の桁数の最大数です。
中古。 これを超えると、プログラムはメッセージで終了します（通常は
再起動）。 デフォルトは約100桁に設定されています。 実行の最後に、メッセージは次のようになります。
検出された最大整数サイズをユーザーに通知します。 これはに使用される可能性があります
後続の実行でメモリ使用量と速度を最適化します（たとえば、見積もりを行う場合）。

デュアルパーバーブ 最大化または最小化オプションを指定してlrsを実行すると、逆検索が実行されます
ツリーは、この関数の最適な頂点に根ざしています。複数の最適なものがある場合
頂点の場合、出力は完全ではないことがよくあります。 このオプションは、に小さな摂動を与えます
これを回避する目的。 開始辞書がデュアルの場合、警告メッセージが表示されます
退化。

見積もり k 出力サイズを見積もります。 maxdepthと組み合わせて使用​​-を参照してください
推定。【6]

幾何学的な // H表現またはボロノイオプションのみ//このオプションを使用すると、各光線は
入射する頂点と一緒に印刷されます。 詳細については、を参照してください。
の幾何学的光線 ヒント & コメント[5]。

発生率このオプションは自動的にオンになります プリントコベース 、以下を参照してください
最初にこのオプションの説明。 printcobasisnで使用できます。 （Ver 4.2b）.PP For
入力H表現、頂点/光線を含むすべての入力不等式のインデックス
出力されようとしています。 単純な顔の場合、これらのインデックスは新しい出力がないためです。
すでにリストされています。 それ以外の場合、追加のタイトな不等式はコロンの後にリストされます。
.PP入力V表現の場合、ファセット上にあるすべての入力頂点/光線のインデックス
それが出力されようとしています。 スター付きのインデックスは、この頂点が
cobasisですが、ファセットには含まれていません。 使用した持ち上げ操作が原因で発生します
入力V表現を使用します。

＃入射printcobasisと同じです。 との互換性のために含まれています cdd。

直線性 k i1i2 i ... ik入力には、行にk個の線形性が含まれています i1i2i ... ik
入力ファイルは方程式です。 見る 直線性。【3]

最大深度 k 検索は深さkで切り捨てられます。 または以下の深さのすべてのベース
kに等しいものが計算されます。 kは非負の整数であり、このオプションは次の場合に使用されます。
見積もり-を参照してください 推定。【6]Note：H表現の場合、深さkの光線は
報告。 V表現の場合、深さkのファセットは報告されません。

最大化します a0 a1..。 an-1 // H表現のみ//

最小限に抑えます a0 a1..。 an-1 // H表現のみ//

lrsとともに使用する場合、開始頂点は関数a0 + a1x1 + ..を最大化（または最小化）します。
+ an-1 xn-1。二重縮退を回避するために、dualperturbオプションが必要になる場合があります。Nashを参照してください。
平衡と 線形 プログラミング【7]

最大出力 n 生成される出力ラインの数（頂点+光線またはファセットのいずれか）をnに制限します

最小深度 k kaが負でない整数の場合、バックトラッキングは深さkで終了します。 この
サブツリーで逆検索を個別のプロセスとして実行するために使用できます。
分散コンピューティング環境。

非負 //このオプションはbeginステートメントの前に置く必要があります//// H-表現のみ
//バグ：原点が多面体の頂点である場合にのみ使用できます
入力は、b + Ax> = 0、x> = 0（つまり、すべての変数）の形式のH表現です。
非負、すべての制約の不等式）非負を与える必要はありません
非負のオプションが使用されている場合は、明示的に制約します。 このオプションは、
V表現、または線形性オプションを使用（この場合、線形性は次のようになります）
不等式として扱われます）。 このオプションは冗長で使用できますが、暗黙的に使用されます
非負性制約は、冗長性についてそれ自体はテストされません。 すべてをテストするには
非負性制約を入力ファイルに明示的に入力する必要があります。 （Ver。
4.1、原点は頂点でなければなりません）。

プリントコベース k;lrs4.0で変更されました。k番目ごとのコベーシスが印刷されます。 kを省略した場合、
cobasisは、出力される頂点/光線/ファセットごとに出力されます。 長期的には便利です
必要に応じてプログラムを再起動できるように、コベーシスをときどき印刷します。
H表現： 入力がH表現である場合、コベーシスはのインデックスのリストです。
現在の頂点または光線を定義する入力ファイルからの不等式。 オプションを参照してください
発生率 詳細については、上記をご覧ください。 光線の場合、コベーシスも印刷されます。 この場合
コベーシスは、光線が放射される頂点のコベーシスです。 インデックスのXNUMXつ
スターが付いている場合、これは、定義するためにコベーシスから削除される不等式を示します
レイ。 または、 すべての拠点オプションを使用すると、すべてのコベースが印刷されます。
V表現：入力がV表現の場合、コベーシスは入力のリストです
現在のファセットを定義する頂点/光線。 オプションを参照してください 発生率 詳細については上記
情報。 開始するには LRS このファセットから、4つのインデックスすべてをこの順序で指定する必要があります
（*を省略します）。

印刷不足 Ver4.2の新機能; // H表現で使用// lrsはのリストを出力します
現在の頂点に対して厳密に満たされる入力不等式のインデックス。
対応するスラック変数は正です。 非負が設定されている場合、リストも
正である各決定変数xiのインデックスn + iを含めます。 プロジェクト によって使われた
ルズフーリエ[8]のみ。

再起動 V# R# B# 深さ {ファセット #s or 頂点/光線 #s} lrs4.0で変更 LRS することができます
既知のコベーシスから再起動しました。 計算は通常の終了に進みます。 全て
情報の一部は、からの出力に含まれています プリントコベース オプション。 ザ· 注文 of
　 索引 is 非常に 重要、 からの出力に表示されるとおりに正確に入力してください
以前に実行を中止しました。

開始コベーシス i1i2i ... 1で これにより、ユーザーは既知のコベーシスを指定できます。
逆検索を開始します。 i1i2i ... 1で 不等式のリストです（
H-表現）またはコベーシスを定義する頂点/光線（V-表現の場合）。 もしそれが
無効、またはこのオプションが指定されていない場合 LRS 独自の開始コベーシスを見つけます。 NS
逆検索ツリーは、新しい頂点が検出されるたびに切り捨てられます（削除されます）。 注：これ
の最適な頂点に隣接するすべての頂点のセットを必ず生成することに注意してください。
多面体ですが、それらのサブセットにすぎません。

詳細実行に関するもう少し詳細な情報を印刷します。

ボリューム // V表現のみ//ボリュームの計算-セクションを参照 音量 計算。【9]

ボロノイ // V表現のみ-endステートメントの直後に配置//計算
ボロノイ図-セクションを参照 ボロノイ ダイアグラム。【10]

注意事項

1.FAQページ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2.CDD
http://www.cs.mcgill.ca/％7Efukuda / soft / cdd_home / cdd.html

3.直線性
http://cgm.cs.mcgill.ca/％7Eavis / C / lrslib / USERGUIDE.html＃線形性

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％20Programming

8.lrsfourier
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

onworks.net サービスを使用してオンラインで lrsfourier を使用する