lrsfourier - Online în cloud

PROGRAM:

NUME

lrslib - Convertiți între reprezentări ale poliedrelor convexe.

REZUMAT

LRS intrare.ine

LRS intrare.ine | lrsbuffer

lrsfourier fişier.ine [fileout]

redundată intrare.ine

DESCRIERE

Un poliedru poate fi descris printr-o listă de inegalități (reprezentare H) sau ca printr-o listă
a vârfurilor și razelor sale extreme (reprezentare V). LRS este un program C care convertește a
Reprezentarea H a unui poliedru față de reprezentarea lui V și invers. Aceste probleme
sunt cunoscute respectiv la zenit enumerare și convex carenă probleme.

a lui Fukuda FAQ pagină[1] conține o introducere mai detaliată a problemei, împreună cu
multe sfaturi utile pentru noul utilizator.

lrsbuffer poate elimina unele rezultate duplicat. redundată găsește inegalități redundante în
intrare.

FILE FORMATE

Formatele de fișiere au fost dezvoltate împreună cu Komei Fukuda și sunt compatibile cu CDD[2].

Intrarea pentru LRS este o reprezentare H sau V a unui politop.

nume
{linia de reprezentare}
{Opțiuni}
{liniarități[3]}
începe
mn raţional
{matrice de intrare}
capăt
{Opțiuni}

nume este un nume furnizat de utilizator pentru politop. Comentariile pot apărea înainte de început sau
după sfârșit, și pentru a evita interpretarea ca opțiune, ar trebui să înceapă cu o specială
caracter precum „*” sau „#”.

nume este un nume furnizat de utilizator pentru politop. reprezentare linie este fie
„Reprezentare H” sau „reprezentare V”. Dacă este omis, se presupune reprezentarea H. The
coeficienții de intrare sunt citiți în format liber și nu sunt verificați pentru tip. Coeficienții sunt
separate prin spații albe. m este numărul de rânduri și n numărul de coloane ale intrării
matrice.

H-reprezentare
Întregul m este numărul de inegalități, iar întregul n este dimensiunea lui
introduceți +1. O listă de inegalități conține coeficienții de inegalități ai formei

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

Această inegalitate este introdusă ca linie

a0 a1... an-1

Coeficienții pot fi introduși ca numere întregi sau raționale în format x/y.

V-reprezentare
Întregul m este numărul de vârfuri și raze, iar întregul n este dimensiunea lui
intrarea +1. Fiecare vârf este dat sub forma

1 v0 v 1... vn-1

Fiecare rază este dată sub formă

0 r0 r 1... rn-1

unde r0 r 1... rn-1 este un punct pe rază.

Trebuie să existe cel puțin un vârf în fiecare fișier. Pentru poliedre mărginite nu va exista
razele au intrat. Coeficienții pot fi introduși ca numere întregi sau raționale în format x/y.

notițe pentru CDD utilizatorii: LRS folosește în esență același format de fișier ca CDD. Fișiere pregătite pentru
CDD ar trebui să funcționeze cu modificări mici sau deloc. Rețineți că reprezentarea V
corespunde opțiunii „cocă” din CDD. Opțiuni specifice CDD poate fi lăsat în intrare
fișiere și vor fi ignorate de LRS. Notați fișierele de intrare pentru LRS sunt citite în format liber,
după linie m n rațional, LRS va căuta exact m*n raționali sau numere întregi separate
prin spații albe (blank, retur car, tab etc.). LRS nu va „scăpa” coloane suplimentare de
introduceți dacă n este mai mic decât numărul de coloane furnizat.

pachet de bază Opţiuni
Aproape toate opțiunile sunt plasate după declarația finală, menținând compatibilitatea cu CDD.
Acolo unde nu este cazul, acesta va fi menționat în mod explicit.

toate bazele Această opțiune instruiește LRS pentru a enumera fiecare vârf (sau fațetă) pentru fiecare dintre bazele sale.
producție dublare[4].[5] Această opțiune este adesea combinată cu printcobasis.

legat x Utilizați cu reprezentarea H - pentru lrs sau nash Fie pentru maximizare, fie pentru minimizare
ar trebui selectată opțiunea. x este un număr întreg sau rațional. Pentru maximizare (resp.
minimizarea) arborele de căutare inversă este trunchiat ori de câte ori valoarea obiectivă curentă
este mai mic (resp. mai mult) decât x.

cache nLRS stochează cele mai recente n dicționare în arborele de căutare inversă. Acest lucru se accelerează
pasul de întoarcere, dar necesită mai multă memorie.

depana baza de pornire baza finalăImprimați urme criptice, dar detaliate, dicționare etc.
începând cu #B=startingbasis și se termină la #B=endingbasis. depana 0 0 oferă un complet
urme.

cifre n plasat înainte il începe declaraţie n este numărul maxim de cifre zecimale care trebuie să fie
folosit. Dacă acest lucru este depășit, programul se încheie cu un mesaj (de obicei poate fi
repornit). Valoarea implicită este setată la aproximativ 100 de cifre. La sfârșitul unei rulări este un mesaj
dat informând utilizatorul asupra mărimii întregi maxime întâlnite. Acest lucru poate fi folosit pentru
optimizați utilizarea memoriei și viteza la rulările ulterioare (dacă faceți estimare, de exemplu).

dualperturb Dacă lrs este executat cu opțiunea de maximizare sau de minimizare, căutarea inversă
arborele este înrădăcinat la un vârf optim pentru această funcție. Dacă există optimi multipli
vârfuri, rezultatul nu va fi adesea complet. Această opțiune dă o mică perturbare
obiectivul de a evita acest lucru. Este dat un mesaj de avertizare dacă dicționarul de pornire este dual
degenerat.

estimări k Estimați dimensiunea ieșirii. Folosit împreună cu maxdepth - vezi
Estimare.[6]

geometric // Numai opțiunea H-reprezentare sau voronoi // Cu această opțiune, fiecare rază este
imprimat împreună cu vârful cu care este incident. Pentru mai multe informații vezi
Raze geometrice în sugestii și Comentarii[5].

incidențăAceastă opțiune se activează automat printcobasis , deci vezi mai jos pentru a
mai întâi descrierea acestei opțiuni. Poate fi folosit cu printcobasis n. (Ver 4.2b) .PP Pentru
intrare H-reprezentare, indici ai tuturor inegalităților de intrare care conțin vârful/raza care
este pe cale să fie scos. Pentru o față simplă, nu există o ieșire nouă, deoarece acești indici
sunt deja listate. În caz contrar, inegalitățile strânse suplimentare sunt enumerate după două puncte.
.PP Pentru reprezentarea V de intrare, indici ai tuturor vârfurilor/razelor de intrare care se află pe fațetă
care urmează să fie scos. Un index marcat cu stea indică faptul că acest vârf se află și în
cobasis, dar nu este cuprins în fațetă. Apare din cauza operațiunii de ridicare folosită
cu reprezentări V de intrare.

#incidenţăLa fel ca printcobasis. Inclus pentru compatibilitate cu cdd.

liniaritatea k i1i2 i ... ikIntrarea conține k liniarități în rânduri i1i2i ... ika
fișierul de intrare sunt ecuații. Vedea Linearități.[3]

adancime maxima k Căutarea va fi trunchiată la adâncimea k. Toate bazele cu adâncime mai mică de sau
egal cu k va fi calculat. k este un întreg nenegativ și această opțiune este folosită pentru
estimări – vezi Estimare.[6]notițe: Pentru reprezentările H, razele la adâncimea k nu vor fi
raportat. Pentru reprezentările V, fațetele la adâncimea k nu vor fi raportate.

maximaliza a0 a1... an-1 // Numai reprezentarea H //

minimaliza a0 a1... an-1 // Numai reprezentarea H //

Dacă este utilizat cu lrs, vârful de pornire maximizează (sau minimizează) funcția a0 + a1x1+ ...
+ an-1 xn-1. Opțiunea dualperturb poate fi necesară pentru a evita degenerarea dublă. Vezi Nash
Echilibre și Liniar Programare[7]

ieșire maximă n Limitează numărul de linii de ieșire produse (fie vârfuri+raze, fie fațete) la n

mintea k Backtracking va fi terminat la adâncimea k, pentru ka întreg nenegativ. Acest
poate fi folosit pentru rularea căutării inverse pe subarbori ca procese separate, de exemplu în a
mediu de calcul distribuit.

nenegativ // Această opțiune trebuie să apară înainte de instrucțiunea begin// //Numai reprezentarea H
// Bug: Poate fi folosit numai dacă originea este un vârf al poliedrului Pentru probleme în care
intrarea este o reprezentare H de forma b+Ax>=0, x>=0 (adică toate variabilele
nenegativ, toate constrângerile inegalități) nu este necesar să se dea nenegativul
constrângeri în mod explicit dacă este utilizată opțiunea nenegativă. Această opțiune nu poate fi folosită pentru
Reprezentări V sau cu opțiunea de liniaritate (caz în care liniaritățile vor fi
tratate ca inegalități). Această opțiune poate fi utilizată cu redund , dar implicit
constrângerile de nonnegativitate nu sunt testate ele însele pentru redundanță. Pentru a testa totul
este necesar să introduceți explicit constrângerile de nonnegativitate în fișierul de intrare. (În Ver
4.1, originea trebuie să fie un vârf).

printcobasis k;Modificat în lrs 4.0 Fiecare k'-a cobază este tipărită. Dacă k este omis,
cobasis este tipărit pentru fiecare vârf/rază/fațetă care este scos. Pe termen lung este util
pentru a imprima cobasis ocazional pentru ca programul să poată fi repornit dacă este necesar.
H-reprezentare: Dacă intrarea este o reprezentare H, cobaza este o listă a indicilor
inegalitățile din fișierul de intrare care definesc vârful sau raza curentă. Vezi opțiunea
incidență mai sus pentru mai multe informații. Pentru raze se imprimă și o cobază. În acest caz
cobaza este cobaza vârfului din care emană raza. Unul dintre indici
este marcat cu stea, aceasta indică inegalitatea care trebuie eliminată din cobază pentru a defini
raza. Alternativ, dacă toate bazeleeste utilizată opțiunea, toate cobazele vor fi tipărite.
V-reprezentare: Dacă intrarea este o reprezentare V, cobaza este o listă a intrării
vârfuri/raze care definesc fațeta curentă. Vezi opțiunea incidență mai sus pentru mai mult
informație. A initia LRS din această fațetă trebuie dați toți cei 4 indici în această ordine
(omiteți *).

printslack Nou în Versiunea 4.2; // Folosește cu reprezentarea H // lrs tipărește o listă a
indici ai inegalităților de intrare care sunt satisfăcute strict pentru vârful curent, adică.
variabila slack corespunzătoare este pozitivă. Dacă este setat nenegativ, lista va fi de asemenea
includeți indicii n+i pentru fiecare variabilă de decizie xi care este pozitivă. proiect Folosit de
lrsfourier[8] numai.

reîncepe V# R# B# adâncime {faţetă #s or vârf/rază #s} Modificat în lrs4.0 LRS poate fi
repornit de la orice cobază cunoscută. Calculul va trece la terminarea normală. Toate
a informațiilor este conținută în rezultatul de la a printcobasis opțiune. comandă of
il Indicii is foarte important, introduceți-le exact așa cum apar în rezultatul din
rulare anulată anterior.

startingcobazis i1i2i ... în-1 Acest lucru permite utilizatorului să specifice o cobază cunoscută pentru
începe căutarea inversă. i1i2i ... în-1 este o listă a inegalităților (pentru
H-reprezentare) sau vârfuri/raze (pentru reprezentarea V) care definesc o cobază. Dacă este
invalid sau această opțiune nu este specificată, LRS își va găsi propria cobază de pornire. The
Arborele de căutare inversă este trunchiat (tuns) ori de câte ori este întâlnit un nou vârf. Notă: Aceasta
observă că produce în mod necesar mulțimea tuturor vârfurilor adiacente vârfului optim în
poliedrul, ci doar un subset al acestora.

prolixImprimați informații puțin mai detaliate despre alergare.

volum // Numai reprezentarea V // Calculați volumul - vezi secțiunea Volum Calcul.[9]

voronoi // Numai reprezentare în V - plasați imediat după instrucțiunea de final // Calculați
Diagrama Voronoi - vezi sectiunea Voronoi Diagrame.[10]

NOTE

1. Pagina de întrebări frecvente
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. liniarități
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities

4. Dublarea ieșirii
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. Estimare.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. Programare liniară
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programare

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

9. Calcularea volumului.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

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

Utilizați lrsfourier online folosind serviciile onworks.net