lrsfourier - Online nel cloud

PROGRAMMA:

NOME

lrslib - Conversione tra rappresentazioni di poliedri convessi.

SINOSSI

LRS input.ine

LRS input.ine | lrsbuffer

lrsfourier file.ine [file fuori]

ridondanza input.ine

DESCRIZIONE

Un poliedro può essere descritto da un elenco di disuguaglianze (rappresentazione H) o come da un elenco
dei suoi vertici e raggi estremi (V-rappresentazione). LRS è un programma C che converte a
Rappresentazione H di un poliedro alla sua rappresentazione V e viceversa. Questi problemi
sono noti rispettivamente al vertice enumerazione ed convesso scafo problemi.

Fukuda's FAQ pagina[1] contiene un'introduzione più dettagliata al problema, insieme a
tanti consigli utili per il nuovo utente.

lrsbuffer può rimuovere alcuni output duplicati. ridondanza trova disuguaglianze ridondanti nel
ingresso.

RISORSE FORMATI

I formati di file sono stati sviluppati in collaborazione con Komei Fukuda e sono compatibili con CDD[2].

L'ingresso per LRS è una rappresentazione H o V di un politopo.

Nome
{linea di rappresentazione}
{opzioni}
{linearità[3]}
iniziare
mn razionale
{matrice di input}
fine
{opzioni}

Nome è un nome fornito dall'utente per il politopo. I commenti possono apparire prima dell'inizio o
dopo la fine, e per evitare l'interpretazione come opzione, dovrebbe iniziare con uno speciale
carattere come "*" o "#".

Nome è un nome fornito dall'utente per il politopo. rappresentazione linea è l'uno o l'altro
"Rappresentazione ad H" o "Rappresentazione a V". Se viene omesso, si assume la rappresentazione H. Il
i coefficienti di input vengono letti in formato libero e non vengono controllati per il tipo. I coefficienti sono
separati da uno spazio bianco. m è il numero di righe e n il numero di colonne dell'input
matrice.

H-rappresentazione
L'intero m è il numero di disuguaglianze e l'intero n è la dimensione di
ingresso +1. Un elenco di disuguaglianze contiene i coefficienti di disequazioni della forma

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

Questa disuguaglianza viene immessa come linea

a0 a1... an-1

I coefficienti possono essere inseriti come interi o razionali nel formato x/y.

V-rappresentazione
L'intero m è il numero di vertici e raggi, e l'intero n è la dimensione di
l'ingresso +1. Ogni vertice è dato nella forma

1 contro 0 contro 1... vn-1

Ogni raggio è dato nella forma

0 r0 r 1... rn-1

dove r0 r 1... rn-1 è un punto sulla semiretta.

Ci deve essere almeno un vertice in ogni file. Per i poliedri limitati non ci sarà
raggi entrati. I coefficienti possono essere inseriti come interi o razionali nel formato x/y.

Note: per CDD utenti: LRS utilizza essenzialmente lo stesso formato di file di CDD. File preparati per
CDD dovrebbe funzionare con poche o nessuna modifica. Nota che la V-rappresentazione
corrisponde all'opzione "scafo" in CDD. Opzioni specifiche per CDD può essere lasciato nell'input
file e verrà ignorato da LRS. Nota i file di input per LRS vengono letti in formato libero,
dopo la linea m n razionale, LRS cercherà esattamente m*n razionali o interi separati
per spazio bianco (vuoto, ritorno a capo, tabulazione ecc.). LRS non "rilascerà" colonne extra di
input se n è minore del numero di colonne fornite.

Standard Opzioni
Quasi tutte le opzioni sono posizionate dopo la dichiarazione finale, mantenendo la compatibilità con CDD.
In caso contrario, sarà menzionato esplicitamente.

tutte le basi Questa opzione indica LRS elencare ogni vertice (o sfaccettatura) per ciascuna delle sue basi.
Uscita Duplicazione,.[5] Questa opzione è spesso combinata con printcobasis.

legato x Utilizzare con rappresentazione H - per lrs o nash Ingrandisci o riduci a icona
l'opzione dovrebbe essere selezionata. x è un intero o razionale. Per la massimizzazione (risp.
minimizzazione) l'albero di ricerca inversa viene troncato ogni volta che il valore obiettivo corrente
è minore (risp. maggiore) di x.

nascondiglio nLRS memorizza gli ultimi n dizionari nell'albero di ricerca inversa. Questo accelera
il passo indietro, ma richiede più memoria.

mettere a punto base di partenza base finaleStampa tracce criptiche ma dettagliate, dizionari ecc.
iniziando da #B=baseiniziale e terminando con #B=basefinale. mettere a punto 0 0 dà un completo
tracciare.

cifre n posto prima , il iniziare dichiarazione n è il numero massimo di cifre decimali da essere
Usato. Se questo viene superato il programma termina con un messaggio (di solito può essere
riavviato). L'impostazione predefinita è di circa 100 cifre. Alla fine di una corsa un messaggio è
dato che informa l'utente della dimensione intera massima incontrata. Questo può essere usato per
ottimizzare l'utilizzo della memoria e la velocità nelle esecuzioni successive (se si esegue una stima, ad esempio).

doppia perturbazione Se lrs viene eseguito con l'opzione di ingrandimento o riduzione a icona, la ricerca inversa
albero è radicato in un vertice ottimale per questa funzione. Se ci sono più ottimi
vertici, l'output spesso non sarà completo. Questa opzione dà una piccola perturbazione a
l'obiettivo di evitarlo. Viene visualizzato un messaggio di avviso se il dizionario iniziale è dual
degenerare.

stime k Stimare la dimensione dell'output. Usato in combinazione con maxdepth - vedi
Stima.,

geometrico // Solo rappresentazione H o opzione voronoi // Con questa opzione, ogni raggio è
stampato insieme al vertice con cui è incidente. Per ulteriori informazioni, vedere
Raggi geometrici in Suggerimenti ed Commenti[5].

incidenzaQuesta opzione si attiva automaticamente printcobase , quindi vedi sotto per a
prima la descrizione di questa opzione. Utilizzabile con printcobasis n. (Ver 4.2b) .PP Per
input H-rappresentazione, indici di tutte le disuguaglianze di input che contengono il vertice/raggio che
sta per essere prodotto. Per una faccia simpliciale, non c'è un nuovo output, poiché questi indici
sono già elencati. Altrimenti, le disuguaglianze strette aggiuntive sono elencate dopo i due punti.
.PP Per la rappresentazione V di input, indici di tutti i vertici/raggi di input che giacciono sulla faccetta
che sta per essere prodotto. Un indice asterisco indica che questo vertice è anche nel
cobasis, ma non è contenuto nella sfaccettatura. Sorge a causa dell'operazione di sollevamento utilizzata
con rappresentazioni V di ingresso.

#incidenzaLo stesso di printcobasis. Incluso per compatibilità con cdd.

linearità k i1i2 i ... ikL'input contiene k linearità in righe i1i2i ... ikdella
file di input sono equazioni. Vedere Linearità.,

profondità massima k La ricerca verrà troncata alla profondità k. Tutte le basi con profondità inferiore a o
uguale a k sarà calcolato. k è un numero intero non negativo e questa opzione è usata per
stime - vedi Stima.,Note:: Per le rappresentazioni H, i raggi alla profondità k non saranno
segnalato. Per le rappresentazioni V, le sfaccettature alla profondità k non verranno riportate.

massimizzare a0 a1... an-1 // Solo rappresentazione H //

ridurre al minimo a0 a1... an-1 // Solo rappresentazione H //

Se usato con lrs il vertice di partenza massimizza (o minimizza) la funzione a0 + a1x1+ ...
+ an-1 xn-1.L'opzione dualperturb potrebbe essere necessaria per evitare la doppia degenerazione.Vedi Nash
Equilibri e Lineare Programmazione,

uscita massima n Limita il numero di linee di output prodotte (vertici + raggi o sfaccettature) a n

minprofondità k Il backtracking terminerà alla profondità k, per ka intero non negativo. Questo
può essere utilizzato per eseguire la ricerca inversa su sottoalberi come processi separati, ad esempio in a
ambiente di calcolo distribuito.

non negativo // Questa opzione deve precedere l'istruzione begin// //Solo rappresentazione H
// Bug: può essere utilizzato solo se l'origine è un vertice del poliedro Per problemi in cui
l'input è una rappresentazione H della forma b+Ax>=0, x>=0 (ovvero tutte le variabili
non negativo, tutti i vincoli disuguaglianze) non è necessario dare il non negativo
vincoli esplicitamente se viene utilizzata l'opzione non negativa. Questa opzione non può essere utilizzata per
Rappresentazioni a V, o con l'opzione di linearità (nel qual caso le linearità saranno
trattate come disuguaglianze). Questa opzione può essere utilizzata con ridondante, ma è implicito
i vincoli di non negatività non vengono testati per la ridondanza. Per testare tutto
è necessario inserire esplicitamente i vincoli di non negatività nel file di input. (In Ver
4.1, l'origine deve essere un vertice).

printcobase k;Modificato in lrs 4.0 Ogni k'th cobasis viene stampato. Se k viene omesso, il
cobasis viene stampato per ogni vertice/raggio/faccetta che viene emesso. Per un lungo periodo è utile
stampare occasionalmente il cobasis in modo che il programma possa essere riavviato se necessario.
H-rappresentazione: Se l'input è una rappresentazione H la cobasis è una lista degli indici di
le disuguaglianze dal file di input che definiscono il vertice o il raggio corrente. Vedi opzione
incidenza sopra per maggiori informazioni. Per i raggi, viene stampata anche una cobasis. In questo caso
la cobasis è la cobasis del vertice da cui emana il raggio. Uno degli indici
è asterisco, questo indica la disuguaglianza da eliminare dalla cobasis per definire il
raggio. In alternativa, se il tutte le basiviene utilizzata l'opzione, verranno stampate tutte le cobase.
V-rappresentazione: Se l'ingresso è una rappresentazione V, il cobasis è un elenco dell'ingresso
vertici/raggi che definiscono la sfaccettatura corrente. Vedi opzione incidenza sopra per di più
informazione. Iniziare LRS da questa sfaccettatura tutti e 4 gli indici devono essere dati in questo ordine
(omettere *).

printlack Novità nella versione 4.2; // Usa con rappresentazione H // lrs stampa un elenco di
indici delle disuguaglianze di input che sono soddisfatte rigorosamente per il vertice corrente, es.
la corrispondente variabile di gioco è positiva. Se è impostato non negativo, anche l'elenco sarà
includi indici n+i per ogni variabile di decisione xi che è positiva. progetto Usato da
lrsfourier[8] solo.

nuovo inizio V# R# B# profondità {sfaccettatura #s or vertice/raggio #s} Modificato in lrs4.0 LRS può essere
riavviato da qualsiasi cobasis noto. Il calcolo procederà alla risoluzione normale. Tutto
dell'informazione è contenuta nell'output di a printcobase opzione. Il minimo of
, il indici is molto importante, inseriscili esattamente come appaiono nell'output del
corsa precedentemente interrotta.

partenza cobase i1i2i ... in 1 Ciò consente all'utente di specificare una cobasi nota per
iniziare la ricerca inversa. i1i2i ... in 1 è un elenco delle disuguaglianze (per
rappresentazione H) o vertici/raggi (per rappresentazione V) che definiscono una cobasi. Se è
non valido, o questa opzione non è specificata, LRS troverà la propria cobase di partenza. Il
l'albero di ricerca inversa viene troncato (eliminato) ogni volta che viene incontrato un nuovo vertice. Nota: questo
nota produce necessariamente l'insieme di tutti i vertici adiacenti al vertice ottimo in
il poliedro, ma solo un sottoinsieme di essi.

verbosoStampa informazioni leggermente più dettagliate sulla corsa.

volume // Solo rappresentazione V // Calcola volume - vedi sezione Volume Calcolo.,

voronoi // Solo rappresentazione V - posizionalo immediatamente dopo l'istruzione end // Calcola
Diagramma di Voronoi - vedere la sezione Voronoi Diagrammi.,

NOTE

1. Pagina delle domande frequenti
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à
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities

4. Duplicazione dell'output
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplicazione

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Suggerimenti%20e%20Commenti

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

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

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

9. Calcolo del volume.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Calcolo

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

Usa lrsfourier online utilizzando i servizi onworks.net