lrsfourier – Online in der Cloud

PROGRAMM:

NAME/FUNKTION

lrslib - Konvertiert zwischen Darstellungen konvexer Polyeder.

ZUSAMMENFASSUNG

lrs input.ine

lrs input.ine | lrspuffer

lrsfourier Datei.ine [Dateiausgabe]

überflüssig input.ine

BESCHREIBUNG

Ein Polyeder kann durch eine Liste von Ungleichungen beschrieben werden (H-Darstellung) oder wie durch eine Liste
seiner Scheitel und extremen Strahlen (V-Darstellung). lrs ist ein C-Programm, das a . umwandelt
H-Darstellung eines Polyeders in seine V-Darstellung und umgekehrt. Diese Probleme
sind jeweils bei der . bekannt Scheitel Aufzählung und konvexen Rumpf Probleme.

Fukudas FAQ Seite[1] enthält eine ausführlichere Einführung in das Problem, zusammen mit
viele nützliche Tipps für den neuen Benutzer.

lrspuffer kann einige doppelte Ausgaben entfernen. überflüssig findet redundante Ungleichungen im
Eingang.

FILE FORMATEN

Dateiformate wurden gemeinsam mit Komei Fukuda entwickelt und sind kompatibel mit CDD[2].

Die Eingabe für lrs ist eine H- oder V-Darstellung eines Polytops.

Name
{Darstellungslinie}
{Optionen}
{Linearitäten[3]}
beginnen
mn rational
{Eingabematrix}
Ende
{Optionen}

Name ist ein vom Benutzer bereitgestellter Name für das Polytop. Kommentare können vor Beginn erscheinen oder
nach dem Ende, und um eine Interpretation als Option zu vermeiden, sollte mit einem Special beginnen
Zeichen wie "*" oder "#".

Name ist ein vom Benutzer bereitgestellter Name für das Polytop. Darstellung Linie entweder
"H-Darstellung" oder "V-Darstellung". Wenn weggelassen wird, wird die H-Darstellung angenommen. Die
Eingabekoeffizienten werden im freien Format gelesen und nicht auf Typ geprüft. Koeffizienten sind
durch Leerzeichen getrennt. m ist die Anzahl der Zeilen und n die Anzahl der Spalten der Eingabe
Matrix.

H-Darstellung
Die ganze Zahl m ist die Anzahl der Ungleichungen und die ganze Zahl n ist die Dimension der
Eingabe +1. Eine Liste von Ungleichungen enthält die Ungleichungskoeffizienten der Form

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

Diese Ungleichung wird als Gerade eingegeben

a0 a1... an-1

Die Koeffizienten können ganzzahlig oder rational im Format x/y eingegeben werden.

V-Darstellung
Die ganze Zahl m ist die Anzahl der Scheitelpunkte und Strahlen, und die ganze Zahl n ist die Dimension von
die Eingabe +1. Jeder Knoten ist in der Form

1 v0 v 1... vn-1

Jeder Strahl ist in der Form

0 r0 r 1... rn-1

wobei r0 r 1... rn-1 ein Punkt auf dem Strahl ist.

In jeder Datei muss mindestens ein Scheitelpunkt vorhanden sein. Für beschränkte Polyeder gibt es kein
Strahlen eingetreten. Die Koeffizienten können ganzzahlig oder rational im Format x/y eingegeben werden.

Note für CDD Nutzer: lrs verwendet im Wesentlichen das gleiche Dateiformat wie CDD. Dateien vorbereitet für
CDD sollte mit wenig oder keiner Änderung funktionieren. Beachten Sie, dass die V-Darstellung
entspricht der Option "Rumpf" in CDD. Spezifische Optionen für CDD kann in der Eingabe belassen werden
Dateien und werden ignoriert von lrs. Beachten Sie die Eingabedateien für lrs im freien Format gelesen werden,
nach der zeile m n rational, lrs sucht nach genau m*n rationalen oder ganzen Zahlen getrennt
durch Leerzeichen (Leerzeichen, Wagenrücklauf, Tabulator usw.). lrs "löscht" keine zusätzlichen Spalten von
Eingabe, wenn n kleiner ist als die Anzahl der angegebenen Spalten.

Basic Optionen
Fast alle Optionen sind platziert nachdem die Endanweisung, die Kompatibilität mit CDD.
Wo dies nicht der Fall ist, wird ausdrücklich darauf hingewiesen.

allebasen Diese Option weist lrs um jeden Scheitelpunkt (oder jede Facette) für jede seiner Basen aufzulisten.
Output Vervielfältigung[4].[5] Diese Option wird oft mit printcobasis kombiniert.

gebunden x Verwendung mit H-Darstellung - für lrs oder nash Entweder maximieren oder minimieren
Option ausgewählt werden sollte. x ist eine ganze Zahl oder rational. Zur Maximierung (bzw.
Minimierung) wird der Rückwärtssuchbaum immer dann abgeschnitten, wenn der aktuelle Zielwert
kleiner (bzw. mehr) als x ist.

Cache-Speicher nlrs speichert die letzten n Wörterbücher im Rückwärtssuchbaum. Das beschleunigt
Backtracking-Schritt, erfordert aber mehr Speicher.

debuggen Ausgangsbasis EndbasisDrucken Sie kryptische, aber detaillierte Traces, Wörterbücher usw.
beginnend bei #B=startbasis und endend bei #B=endbasis. debuggen 0 0 gibt ein komplettes
verfolgen.

Ziffern n platziert Bevor beginnen Aussage n ist die maximal zulässige Anzahl von Dezimalstellen
Gebraucht. Wird dieser überschritten, bricht das Programm mit einer Meldung ab (es kann in der Regel sein
neu gestartet). Der Standardwert ist auf etwa 100 Stellen eingestellt. Am Ende eines Laufs steht eine Nachricht
gegeben, um den Benutzer über die maximale gefundene Ganzzahlgröße zu informieren. Dies kann verwendet werden, um
Optimieren Sie die Speichernutzung und -geschwindigkeit bei nachfolgenden Durchläufen (z. B. bei der Schätzung).

Doppelstörung Wenn lrs mit der Option Maximieren oder Minimieren ausgeführt wird, wird die Rückwärtssuche
Baum an einem optimalen Scheitelpunkt für diese Funktion wurzelt. Wenn mehrere Optimum vorhanden sind
Scheitelpunkte ist die Ausgabe oft nicht vollständig. Diese Option verursacht eine kleine Störung
das Ziel, dies zu vermeiden. Eine Warnmeldung wird ausgegeben, wenn das Startwörterbuch dual ist
degenerieren.

Schätzungen k Schätzen Sie die Ausgabegröße. Wird in Verbindung mit maxdepth verwendet - siehe
Einschätzung.[6]

geometrische // Nur H-Darstellung oder Voronoi-Option // Mit dieser Option ist jeder Strahl
zusammen mit dem Scheitelpunkt gedruckt, mit dem es einfällt. Weitere Informationen finden Sie unter
Geometrische Strahlen in Hinweise und Ihre Nachricht[5].

HäufigkeitDiese Option schaltet sich automatisch ein printcobasis , siehe unten für a
Beschreibung dieser Option zuerst. Kann mit printcobasis n verwendet werden. (Ver 4.2b) .PP For
Eingabe-H-Darstellung, Indizes aller Eingabeungleichungen, die den Scheitelpunkt/Strahl enthalten, der
steht kurz vor der Ausgabe. Für ein vereinfachtes Gesicht gibt es keine neue Ausgabe, da diese Indizes
sind bereits aufgeführt. Andernfalls werden die zusätzlichen engen Ungleichungen nach einem Doppelpunkt aufgelistet.
.PP Für Eingabe-V-Darstellung Indizes aller Eingabescheitelpunkte/-strahlen, die auf der Facette liegen
das wird gleich ausgegeben. Ein mit Sternchen versehener Index zeigt an, dass dieser Scheitelpunkt auch im
cobasis, ist aber nicht in der Facette enthalten. Es entsteht durch den verwendeten Hebevorgang
mit Eingangs-V-Darstellungen.

#VorfallDas gleiche wie printcobasis. Enthalten für Kompatibilität mit CDD.

Linearität k i1i2 i ... ikDie Eingabe enthält k Linearitäten in Zeilen i1i2i ... ikdauert ebenfalls 3 Jahre. Das erste Jahr ist das sog.
Eingabedatei sind Gleichungen. Sehen Linearitäten.[3]

maximale Tiefe k Die Suche wird bei Tiefe k abgeschnitten. Alle Basen mit einer Tiefe von weniger als oder
gleich k berechnet wird. k ist eine nicht negative ganze Zahl, und diese Option wird verwendet für
Schätzungen - siehe Einschätzung.[6]Note: Für H-Darstellungen sind Strahlen in der Tiefe k nicht
berichtet. Bei V-Darstellungen werden Facetten in der Tiefe k nicht gemeldet.

maximieren a0 a1 ... ein-1 // nur H-Darstellung //

minimieren a0 a1 ... ein-1 // nur H-Darstellung //

Bei Verwendung mit lrs maximiert (oder minimiert) der Startknoten die Funktion a0 + a1x1+ ...
+ an-1 xn-1.Die Option dualperturb kann erforderlich sein, um eine doppelte Entartung zu vermeiden.Siehe Nash
Gleichgewichte und Linear Programmierung[7]

max. Ausgang n Begrenzt die Anzahl der erzeugten Ausgabelinien (entweder Scheitelpunkte+Strahlen oder Facetten) auf n

Mindesttiefe k Das Zurückverfolgen wird bei der Tiefe k für ka nicht negative ganze Zahlen beendet. Dies
kann verwendet werden, um die Rückwärtssuche in Teilbäumen als separate Prozesse auszuführen, z. B. in a
verteilte Computerumgebung.

nicht negativ // Diese Option muss vor der begin-Anweisung stehen // // Nur H-Darstellung
// Bug: Kann nur verwendet werden, wenn der Ursprung ein Scheitelpunkt des Polyeders ist Für Probleme, bei denen
die Eingabe ist eine H-Darstellung der Form b+Ax>=0, x>=0 (dh alle Variablen
nicht-negativ, alle Nebenbedingungs-Ungleichungen) ist es nicht notwendig, die nicht-negativen
Einschränkungen explizit, wenn die nichtnegative Option verwendet wird. Diese Option kann nicht verwendet werden für
V-Darstellungen oder mit der Linearitätsoption (in diesem Fall sind die Linearitäten
als Ungleichheit behandelt). Diese Option kann mit redund verwendet werden, aber das implizierte
Nicht-Negativitätsbeschränkungen werden selbst nicht auf Redundanz getestet. Um alles zu testen
ist erforderlich, um die Nicht-Negativitäts-Beschränkungen explizit in die Eingabedatei einzugeben. (In Ver
4.1, der Ursprung muss ein Scheitelpunkt sein).

printcobasis k;Geändert in lrs 4.0 Jede k'te Kobasis wird gedruckt. Wenn k weggelassen wird, ist die
cobasis wird für jeden ausgegebenen Scheitelpunkt/Strahl/Facette gedruckt. Auf lange Sicht ist es nützlich
die Cobasis gelegentlich auszudrucken, damit das Programm bei Bedarf neu gestartet werden kann.
H-Darstellung: Wenn die Eingabe eine H-Darstellung ist, ist die Kobasis eine Liste der Indizes von
die Ungleichungen aus der Eingabedatei, die den aktuellen Scheitelpunkt oder Strahl definieren. Siehe Option
Häufigkeit oben für weitere Informationen. Bei Strahlen wird auch eine Cobasis gedruckt. In diesem Fall
die Kobasis ist die Kobasis des Scheitels, von dem der Strahl ausgeht. Einer der Indizes
markiert ist, zeigt dies die Ungleichung an, die aus der Kobasis entfernt werden muss, um die
Strahl. Alternativ, wenn die allebasenOption verwendet, werden alle Cobases ausgedruckt.
V-Darstellung: Wenn die Eingabe eine V-Darstellung ist, ist die Kobasis eine Liste der Eingaben
Scheitelpunkte/Strahlen, die die aktuelle Facette definieren. Siehe Option Häufigkeit oben für mehr
Information. Etwas initiieren lrs ab dieser Facette müssen alle 4 Indizes in dieser Reihenfolge angegeben werden
(das * weglassen).

drucklos Neu in Version 4.2; // Verwendung mit H-Darstellung // lrs druckt eine Liste der
Indizes der Eingabeungleichungen, die für den aktuellen Knoten strikt erfüllt sind, d.
entsprechende Slack-Variable ist positiv. Wenn nicht negativ eingestellt ist, wird die Liste auch
schließen Indizes n+i für jede positive Entscheidungsvariable xi ein. Projekt Verwendet von
lrsfourier[8] nur.

Wiederaufnahme V# R# B# Tiefe {Facette #s or Scheitelpunkt/Strahl #s} Geändert in lrs4.0 lrs kann sein
von jeder bekannten Cobasis neu gestartet. Die Berechnung wird zur normalen Beendigung fortgesetzt. Alle
der Informationen sind in der Ausgabe von a . enthalten printcobasis Option. Die Auftrag of
Indizes is sehr wichtig, Geben Sie sie genau so ein, wie sie in der Ausgabe des erscheinen
zuvor abgebrochener Lauf.

Startcobasis i1i2i ... in 1 Dadurch kann der Benutzer eine bekannte Kobasis für . angeben
Beginn der Rückwärtssuche. i1i2i ... in 1 ist eine Liste der Ungleichungen (für
H-Darstellung) oder Scheitelpunkte/Strahlen (für V-Darstellung), die eine Kobasis definieren. Wenn es ist
ungültig oder diese Option ist nicht angegeben, lrs findet seine eigene Ausgangsbasis. Die
Der Rückwärtssuchbaum wird abgeschnitten (beschnitten), wenn ein neuer Scheitelpunkt angetroffen wird. Hinweis: Dies
erzeugt nicht notwendigerweise die Menge aller an den optimalen Knoten angrenzenden Knoten in
das Polyeder, aber nur eine Teilmenge davon.

ausführlichDrucken Sie etwas detailliertere Informationen über den Lauf.

Volumen // Nur V-Darstellung // Volumen berechnen - siehe Abschnitt Volume Berechnung.[9]

voronoi // Nur V-Darstellung - direkt nach der Endanweisung platzieren // Compute
Voronoi-Diagramm - siehe Abschnitt Woronoi Diagramme.[10]

ANMERKUNG

1. FAQ-Seite
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. CD
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. Linearitäten
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearitäten

4. Duplizierung der Ausgabe
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplikation

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hinweise%20und%20Kommentare

6. Schätzung.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Schätzung

7. Lineare Programmierung
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programmierung

8. lrsfourier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/BENUTZERHANDBUCH.html#fourier

9. Volumenberechnung.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Berechnung

10. Voronoi-Diagramme.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagramme

Nutzen Sie lrsfourier online über die Dienste von onworks.net