lrsfourier - Online in de cloud

PROGRAMMA:

NAAM

lrslib - Converteren tussen herhalingen van convexe veelvlakken.

KORTE INHOUD

LRS input.ine

LRS input.ine | lrsbuffer

lrsfourier bestand.ine [bestand uit]

overbodig input.ine

PRODUCTBESCHRIJVING

Een veelvlak kan worden beschreven door een lijst van ongelijkheden (H-representatie) of als door een lijst
van zijn hoekpunten en extreme stralen (V-weergave). LRS is een C-programma dat a . converteert
H-representatie van een veelvlak naar zijn V-representatie en vice versa. Deze problemen
zijn respectievelijk bekend bij de toppunt opsomming en convex romp problemen.

Fukuda's FAQ pagina[1] bevat een meer gedetailleerde inleiding tot het probleem, samen met:
veel handige tips voor de nieuwe gebruiker.

lrsbuffer kan enkele dubbele uitvoer verwijderen. overbodig vindt overbodige ongelijkheden in de
invoer.

FILE FORMATS

Bestandsindelingen zijn samen met Komei Fukuda ontwikkeld en zijn compatibel met: cdd[2].

De input voor LRS is een H- of V- representatie van een polytoop.

naam
{representatielijn}
{opties}
{lineariteiten[3]}
beginnen
mn rationeel
{invoermatrix}
einde
{opties}

naam is een door de gebruiker opgegeven naam voor de polytoop. Opmerkingen kunnen voor het begin verschijnen of
na het einde, en om interpretatie als een optie te vermijden, moet beginnen met een speciale
teken zoals "*" of "#".

naam is een door de gebruiker opgegeven naam voor de polytoop. vertegenwoordiging lijn is een van beide
"H-representatie" of "V-representatie". Indien wordt weggelaten, wordt H-representatie aangenomen. De
invoercoëfficiënten worden in vrij formaat gelezen en worden niet gecontroleerd op type. Coëfficiënten zijn
gescheiden door witruimte. m is het aantal rijen en n het aantal kolommen van de invoer
Matrix.

H-representatie
Het gehele getal m is het aantal ongelijkheden, en het gehele getal n is de dimensie van de
invoer +1. Een lijst van ongelijkheden bevat de coëfficiënten van ongelijkheden van de vorm

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

Deze ongelijkheid wordt ingevoerd als de lijn

a0 a1... een-1

De coëfficiënten kunnen worden ingevoerd als gehele getallen of rationale getallen in het formaat x/y.

V-representatie
Het gehele getal m is het aantal hoekpunten en stralen, en het gehele getal n is de afmeting van
de invoer +1. Elk hoekpunt wordt gegeven in de vorm

1 v0 v 1... vn-1

Elke straal wordt gegeven in de vorm

0 r0 r 1... rn-1

waarbij r0 r 1... rn-1 een punt op de straal is.

Er moet minimaal één hoekpunt in elk bestand zijn. Voor begrensde veelvlakken is er geen
stralen kwamen binnen. De coëfficiënten kunnen worden ingevoerd als gehele getallen of rationale getallen in het formaat x/y.

Note For cdd gebruikers: LRS gebruikt in wezen hetzelfde bestandsformaat als cdd. Bestanden voorbereid voor
cdd zou moeten werken met weinig of geen wijziging. Merk op dat de V-representatie
komt overeen met de optie "romp" in cdd. Specifieke opties voor cdd kan worden achtergelaten in de invoer
bestanden en worden genegeerd door LRS. Let op de invoerbestanden voor LRS worden in vrij formaat gelezen,
na de regel m n rationeel, LRS zoekt naar exact m*n rationale getallen of gehele getallen gescheiden
door witruimte (spatie, regelterugloop, tab enz.). LRS zal geen extra kolommen "laten vallen" van
invoer als n kleiner is dan het aantal geleverde kolommen.

Basic Opties
Bijna alle opties zijn geplaatst na de eindverklaring, met behoud van compatibiliteit met cdd.
Waar dit niet het geval is, wordt dit expliciet vermeld.

alle basissen Deze optie geeft instructies: LRS om elk hoekpunt (of facet) voor elk van zijn bases op te sommen.
uitgang Verdubbeling[4].[5] Deze optie wordt vaak gecombineerd met printcobasis.

gebonden x Gebruik met H-representatie - voor lrs of nash Ofwel het maximaliseren of minimaliseren
optie moet worden gekozen. x is een geheel getal of rationaal. Voor maximalisatie (resp.
minimalisatie) de omgekeerde zoekboom wordt afgekapt wanneer de huidige objectieve waarde
is kleiner (resp. meer) dan x.

cache nLRS slaat de laatste n woordenboeken op in de omgekeerde zoekboom. Dit versnelt
de backtracking-stap, maar vereist meer geheugen.

debug startbasis eindbasisPrint cryptische maar gedetailleerde sporen, woordenboeken enz.
beginnend bij #B=beginbasis en eindigend bij #B=eindbasis. debug 0 0 geeft een compleet
spoor.

cijfers n geplaatst vaardigheden de beginnen verklaring n is het maximale aantal decimale cijfers dat mag worden
gebruikt. Als dit wordt overschreden, wordt het programma beëindigd met een bericht (dit kan meestal
opnieuw opgestart). De standaard is ingesteld op ongeveer 100 cijfers. Aan het einde van een run is een bericht
gegeven om de gebruiker te informeren over de maximale grootte van het gehele getal. Dit kan worden gebruikt om
optimaliseer het geheugengebruik en de snelheid bij volgende runs (als u bijvoorbeeld een schatting maakt).

dubbele storing Als lrs wordt uitgevoerd met de optie maximaliseren of minimaliseren, wordt omgekeerd zoeken
boom is geworteld in een optimaal hoekpunt voor deze functie.Als er meerdere optimale zijn:
hoekpunten, zal de uitvoer vaak niet volledig zijn. Deze optie geeft een kleine verstoring aan
het doel om dit te voorkomen. Er wordt een waarschuwingsbericht gegeven als het startwoordenboek dubbel is
ontaarden.

schattingen k Schat de uitvoergrootte. Gebruikt in combinatie met maxdepth - zie
Schatting.[6]

meetkundig // Alleen H-representatie of voronoi-optie // Met deze optie is elke straal
afgedrukt samen met het hoekpunt waarmee het invalt. Voor meer informatie zie
Geometrische stralen in Hints en Heb je vragen? Stel ze hier.[5].

invalDeze optie wordt automatisch ingeschakeld printcobasis , dus zie hieronder voor een
beschrijving van deze optie eerst. Kan gebruikt worden met printcobasis n. (Ver 4.2b) .PP Voor
input H-representatie, indices van alle inputongelijkheden die het hoekpunt/de straal bevatten die
staat op het punt uit te komen. Voor een eenvoudig gezicht is er geen nieuwe output, aangezien deze indices
staan ​​al vermeld. Anders worden de extra nauwe ongelijkheden vermeld na een dubbele punt.
.PP Voor invoer V-representatie, indices van alle invoerhoekpunten/stralen die op het facet liggen
dat staat op het punt om uit te komen. Een index met ster geeft aan dat dit hoekpunt zich ook in de bevindt
cobasis, maar zit niet in het facet. Het ontstaat door de gebruikte hefoperatie
met ingang V-representaties.

#incidentieHetzelfde als printcobasis. Inbegrepen voor compatibiliteit met: cdd.

lineariteit k i1i2 i ... ikDe invoer bevat k lineariteiten in rijen i1i2i ... ikvan de
invoerbestand zijn vergelijkingen. Zien Lineariteiten.[3]

maximale diepte k De zoekopdracht wordt afgebroken op diepte k. Alle bases met een diepte kleiner dan of
gelijk aan k wordt berekend. k is een niet-negatief geheel getal, en deze optie wordt gebruikt voor
schattingen - zie Schatting.[6]Note: Voor H-representaties zijn stralen op diepte k niet
gemeld. Voor V-representaties worden facetten op diepte k niet gerapporteerd.

maximaliseren a0 een1... een-1 // Alleen H-representatie //

verkleinen a0 een1... een-1 // Alleen H-representatie //

Indien gebruikt met lrs, maximaliseert (of minimaliseert) het startpunt de functie a0 + a1x1+ ...
+ an-1 xn-1.De dualperturb-optie kan nodig zijn om dubbele degeneratie te voorkomen.Zie Nash
evenwichten en Lineair Programming[7]

maximale output n Beperkt het aantal geproduceerde uitvoerlijnen (ofwel hoekpunten + stralen of facetten) tot n

mindiepte k Backtracking wordt beëindigd op diepte k, voor ka niet-negatief geheel getal. Dit
kan worden gebruikt voor het uitvoeren van omgekeerd zoeken op subbomen als afzonderlijke processen, bijv. in a
gedistribueerde computeromgeving.

niet negatief // Deze optie moet vóór het begin-statement komen// // Alleen H-representatie
// Bug: kan alleen worden gebruikt als de oorsprong een hoekpunt van het veelvlak is Voor problemen waarbij
de invoer is een H-representatie van de vorm b+Ax>=0, x>=0 (dus alle variabelen
niet-negatief, alle beperkingen ongelijkheden) is het niet nodig om de niet-negatieve
beperkingen expliciet als de niet-negatieve optie wordt gebruikt. Deze optie kan niet worden gebruikt voor:
V-representaties, of met de lineariteitsoptie (in dat geval zullen de lineariteiten zijn
behandeld als ongelijkheden). Deze optie kan worden gebruikt met redund , maar de impliciete
niet-negativiteitsbeperkingen worden zelf niet getest op redundantie. Om alles te testen
is nodig om de niet-negativiteitsbeperkingen expliciet in het invoerbestand in te voeren. (In Ver
4.1, de oorsprong moet een hoekpunt zijn).

printcobasis k;Gewijzigd in lrs 4.0 Elke k'th cobasis wordt gedrukt. Als k wordt weggelaten, de
cobasis wordt afgedrukt voor elk hoekpunt/straal/facet dat wordt uitgevoerd. Voor een lange termijn is het handig
om af en toe de cobasis af te drukken zodat het programma eventueel opnieuw kan worden opgestart.
H-representatie: Als de invoer een H-representatie is, is de cobasis een lijst met de indices van
de ongelijkheden uit het invoerbestand die het huidige hoekpunt of de huidige straal definiëren. Zie optie
inval hierboven voor meer informatie. Voor roggen wordt ook een cobasis gedrukt. In dit geval
de cobasis is de cobasis van het hoekpunt waaruit de straal voortkomt. Een van de indices
een ster heeft, geeft dit de ongelijkheid aan die uit de cobasis moet worden geschrapt om de . te definiëren
straal. Als alternatief, als de alle basissenoptie wordt gebruikt, worden alle cobases afgedrukt.
V-representatie: Als de invoer een V-representatie is, is de cobasis een lijst van de invoer
hoekpunten / stralen die het huidige facet definiëren. Zie optie inval hierboven voor meer
informatie. Inwijden LRS van dit facet moeten alle 4 indices in deze volgorde worden gegeven
(laat de * weg).

prentengebrek Nieuw in versie 4.2; // Gebruik met H-representatie // lrs drukt een lijst af van de
indices van de invoerongelijkheden waaraan strikt wordt voldaan voor het huidige hoekpunt, dwz.
overeenkomstige slappe variabele is positief. Als niet-negatief is ingesteld, wordt de lijst ook
omvatten indices n+i voor elke beslissingsvariabele xi die positief is. project Gebruikt door
lrsfourier[8] alleen.

restart V# R# B# diepte {facet #s or hoekpunt/straal #s} Gewijzigd in lrs4.0 LRS kan zijn
herstart vanaf elke bekende cobasis. De berekening gaat verder met de normale beëindiging. Alle
van de informatie is opgenomen in de uitvoer van a printcobasis optie. De bestellen of
de index is zeer belangrijk, voer ze precies zo in als ze verschijnen in de uitvoer van de
eerder afgebroken run.

startcobasis i1i2i ... in 1 Hiermee kan de gebruiker een bekende cobasis opgeven voor:
het omgekeerd zoeken beginnen. i1i2i ... in 1 is een lijst van de ongelijkheden (voor
H-representatie) of hoekpunten/stralen (voor V-representatie) die een cobasis definiëren. Als het is
ongeldig, of deze optie is niet gespecificeerd, LRS vindt zijn eigen startbasis. De
omgekeerde zoekboom wordt afgekapt (gesnoeid) wanneer een nieuw hoekpunt wordt aangetroffen. Opmerking: dit
levert nota noodzakelijkerwijs de verzameling van alle hoekpunten naast het optimale hoekpunt in
het veelvlak, maar slechts een subset ervan.

breedsprakigDruk iets meer gedetailleerde informatie over de run af.

volume // Alleen V-representatie // Bereken volume - zie sectie Volume Berekening.[9]

voronoi // Alleen V-representatie - plaats direct na eindstatement // Compute
Voronoi-diagram - zie sectie Voronoï diagrammen.[10]

OPMERKINGEN

1. FAQ-pagina
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. lineariteiten
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Lineariteiten

4. Uitvoerduplicatie
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplicatie

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

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

7. Lineaire programmering
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Lineaire%20programmering

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

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

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

Gebruik lrsfourier online met behulp van onworks.net-services