lrsfourier - En ligne dans le Cloud

PROGRAMME:

Nom

lrslib - Convertit entre les représentations de polyèdres convexes.

SYNOPSIS

lrs entrée.ine

lrs entrée.ine | tampon lrs

lrsfourier fichier.ine [fichier]

redonner entrée.ine

DESCRIPTION

Un polyèdre peut être décrit par une liste d'inéquations (représentation H) ou comme par une liste
de ses sommets et rayons extrêmes (représentation en V). lrs est un programme C qui convertit un
Représentation H d'un polyèdre à sa représentation V, et vice versa. Ces problèmes
sont connus respectivement au sommet énumération ainsi que convexe coque d'ouvrabilité.

de Fukuda QFP page[1] contient une introduction plus détaillée au problème, ainsi que
de nombreux conseils utiles pour le nouvel utilisateur.

tampon lrs peut supprimer certaines sorties en double. redonner trouve des inégalités redondantes dans le
contribution.

DOSSIER FORMATS

Les formats de fichiers ont été développés conjointement avec Komei Fukuda et sont compatibles avec cdd[2].

L'entrée pour lrs est une représentation H ou V d'un polytope.

prénom
{ligne de représentation}
{options}
{linéarités[3]}
commencer
mn rationnel
{matrice d'entrée}
fin
{options}

prénom est un nom fourni par l'utilisateur pour le polytope. Les commentaires peuvent apparaître avant le début ou
après la fin, et pour éviter l'interprétation comme option, devrait commencer par un
caractère tel que "*" ou "#".

prénom est un nom fourni par l'utilisateur pour le polytope. représentation en ligne est soit
« représentation H » ou « représentation V ». Si est omis, la représentation H est supposée. Les
les coefficients d'entrée sont lus au format libre et leur type n'est pas vérifié. Les coefficients sont
séparés par un espace blanc. m est le nombre de lignes et n le nombre de colonnes de l'entrée
matrice.

H-représentation
L'entier m est le nombre d'inégalités, et l'entier n est la dimension du
entrée +1. Une liste d'inégalités contient les coefficients d'inéquations de la forme

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

Cette inégalité est entrée comme la ligne

a0 a1... an-1

Les coefficients peuvent être saisis sous forme d'entiers ou de rationnels au format x/y.

V-représentation
L'entier m est le nombre de sommets et de rayons, et l'entier n est la dimension de
l'entrée +1. Chaque sommet est donné sous la forme

1 v0 contre 1... vn-1

Chaque rayon est donné sous la forme

0 r0 r 1... rn-1

où r0 r 1... rn-1 est un point du rayon.

Il doit y avoir au moins un sommet dans chaque fichier. Pour les polyèdres bornés, il n'y aura pas
les rayons sont entrés. Les coefficients peuvent être saisis sous forme d'entiers ou de rationnels au format x/y.

Notes en cdd utilisateurs: lrs utilise essentiellement le même format de fichier que cdd. Fichiers préparés pour
cdd devrait fonctionner avec peu ou pas de modification. Notez que la représentation en V
correspond à l'option "coque" dans cdd. Options spécifiques à cdd peut être laissé dans l'entrée
fichiers et sera ignoré par lrs. Notez les fichiers d'entrée pour lrs sont lus en format libre,
après la ligne m n rationnel, lrs cherchera exactement m*n rationnels ou entiers séparés
par un espace (blanc, retour chariot, tabulation etc.). lrs ne "supprimera" pas les colonnes supplémentaires de
entrée si n est inférieur au nombre de colonnes fournies.

Basic Options
Presque toutes les options sont placées après l'instruction de fin, en maintenant la compatibilité avec cdd.
Lorsque ce n'est pas le cas, cela sera mentionné explicitement.

toutes les bases Cette option indique lrs pour lister chaque sommet (ou facette) pour chacune de ses bases.
Sortie Duplication .[5] Cette option est souvent associée à printcobasis.

lié x Utiliser avec la représentation H - pour lrs ou nash Maximiser ou minimiser
l'option doit être sélectionnée. x est un nombre entier ou rationnel. Pour une maximisation (resp.
minimisation) l'arbre de recherche inverse est tronqué chaque fois que la valeur de l'objectif courant
est inférieur (resp. supérieur) à x.

cachette nlrs stocke les n derniers dictionnaires dans l'arborescence de recherche inversée. Cela accélère
l'étape de retour en arrière, mais nécessite plus de mémoire.

déboguer base de départ base de terminaisonImprimez une trace cryptique mais détaillée, des dictionnaires, etc.
commençant à #B=startingbasis et se terminant à #B=endingbasis. déboguer 0 0 donne une complète
trace.

chiffres n mis before le commencer déclaration n est le nombre maximum de chiffres décimaux à
utilisé. S'il est dépassé, le programme se termine par un message (il peut généralement être
redémarré). La valeur par défaut est d'environ 100 chiffres. A la fin d'une course, un message est
donnée informant l'utilisateur de la taille d'entier maximale rencontrée. Cela peut être utilisé pour
optimiser l'utilisation de la mémoire et la vitesse lors des exécutions suivantes (si vous effectuez une estimation par exemple).

double perturber Si lrs est exécuté avec l'option maximiser ou minimiser, la recherche inverse
l'arbre est enraciné à un sommet optimal pour cette fonction. S'il y a plusieurs optimaux
sommets, la sortie ne sera souvent pas complète. Cette option donne une petite perturbation à
l'objectif d'éviter cela. Un message d'avertissement est donné si le dictionnaire de départ est double
dégénérer.

estimations k Estimez la taille de sortie. Utilisé en conjonction avec maxdepth - voir
Estimation.

géométrique // Représentation H ou option voronoi uniquement // Avec cette option, chaque rayon est
imprimé avec le sommet avec lequel il est incident. Pour plus d'informations voir
Rayons géométriques dans Allusions ainsi que Commentaires[5].

incidenceCette option s'active automatiquement base d'impression , alors voyez ci-dessous pour un
description de cette option en premier. Peut être utilisé avec printcobasis n. (Ver 4.2b) .PP pour
représentation H en entrée, indices de toutes les inégalités en entrée qui contiennent le sommet/rayon qui
est sur le point d'être produit. Pour un visage simplicial, il n'y a pas de nouvelle sortie, puisque ces indices
sont déjà répertoriés. Sinon, les inégalités serrées supplémentaires sont répertoriées après deux points.
.PP Pour la représentation en V d'entrée, les indices de tous les sommets/rayons d'entrée qui se trouvent sur la facette
qui est sur le point d'être sorti. Un index étoilé indique que ce sommet est également dans le
cobasis, mais n'est pas contenu dans la facette. Il survient en raison de l'opération de levage utilisée
avec des représentations en V d'entrée.

#incidenceIdentique à printcobasis. Inclus pour la compatibilité avec CDD.

linéarité k i1i2 i ikL'entrée contient k linéarités dans les lignes i1i2i ikdes
fichier d'entrée sont des équations. Voir Linéarités.

profondeur max k La recherche sera tronquée à la profondeur k. Toutes les bases avec une profondeur inférieure ou
égal à k sera calculé. k est un entier non négatif, et cette option est utilisée pour
estimations - voir Estimation. Notes: Pour les représentations H, les rayons à la profondeur k ne seront pas
signalé. Pour les représentations en V, les facettes à la profondeur k ne seront pas signalées.

maximisent a0 a1 ... an-1 // Représentation H uniquement //

minimiser a0 a1 ... an-1 // Représentation H uniquement //

S'il est utilisé avec lrs, le sommet de départ maximise (ou minimise) la fonction a0 + a1x1+ ...
+ an-1 xn-1.L'option dualperturb peut être nécessaire pour éviter la double dégénérescence.Voir Nash
équilibres et luminaires Néon Del Programmation

production maximale n Limite le nombre de lignes de sortie produites (sommets + rayons ou facettes) à n

minprofondeur k Le backtracking sera terminé à la profondeur k, pour ka entier non négatif. Cette
peut être utilisé pour exécuter une recherche inversée sur des sous-arbres en tant que processus séparés, par exemple dans un
environnement informatique distribué.

non négatif // Cette option doit être placée avant l'instruction begin // // Représentation H uniquement
// Bug : Ne peut être utilisé que si l'origine est un sommet du polyèdre Pour les problèmes où
l'entrée est une représentation H de la forme b+Ax>=0, x>=0 (c'est-à-dire toutes les variables
non-négatif, toutes contraintes inéquations) il n'est pas nécessaire de donner le non-négatif
contraintes explicitement si l'option non négative est utilisée. Cette option ne peut pas être utilisée pour
représentations en V, ou avec l'option linéarité (auquel cas les linéarités seront
traités comme des inégalités). Cette option peut être utilisée avec redund , mais l'implicite
les contraintes de non-négativité ne sont pas testées elles-mêmes pour la redondance. Pour tout tester
est nécessaire de saisir explicitement les contraintes de non-négativité dans le fichier d'entrée. (En Ver
4.1, l'origine doit être un sommet).

base d'impression k;Modifié dans lrs 4.0 Chaque kième cobase est imprimée. Si k est omis, le
cobasis est imprimé pour chaque sommet/rayon/facette qui est sorti. A long terme c'est utile
d'imprimer occasionnellement le cobasis afin que le programme puisse être relancé si nécessaire.
Représentation H : Si l'entrée est une représentation H, la cobase est une liste des indices de
les inégalités du fichier d'entrée qui définissent le sommet ou le rayon courant. Voir l'option
incidence ci-dessus pour plus d'informations. Pour les raies, une cobase est également imprimée. Dans ce cas
la cobase est la cobase du sommet d'où émane le rayon. L'un des indices
est étoilé, cela indique l'inégalité à supprimer de la cobase pour définir le
rayon. Alternativement, si le toutes les basesest utilisée, toutes les cobases seront imprimées.
V-représentation: Si l'entrée est une représentation en V, la cobase est une liste de l'entrée
sommets/rayons qui définissent la facette courante. Voir l'option incidence ci-dessus pour plus
informations. Initier lrs à partir de cette facette, les 4 indices doivent être donnés dans cet ordre
(omettre le *).

impriméslaque Nouveau dans la version 4.2 ; // Utiliser avec la représentation H // lrs imprime une liste des
indices des inégalités d'entrée qui sont satisfaites strictement pour le sommet courant, c'est-à-dire.
la variable d'écart correspondante est positive. Si non négatif est défini, la liste sera également
inclure des indices n+i pour chaque variable de décision xi qui est positive. Projet Utilisé par
lrsfourier[8] seulement.

recommencer V# R# B# profondeur {facette #s or sommet/rayon #s} Modifié dans lrs4.0 lrs peuvent être
redémarré à partir de toute cobase connue. Le calcul se poursuivra jusqu'à la terminaison normale. Tous
de l'information est contenue dans la sortie d'un base d'impression option. La de commander of
le indices is très important, saisissez-les exactement tels qu'ils apparaissent dans la sortie du
exécution précédemment interrompue.

départcobase i1i2i en-1 Cela permet à l'utilisateur de spécifier une cobase connue pour
commencer la recherche inversée. i1i2i en-1 est une liste des inégalités (pour
représentation H) ou des sommets/rayons (pour la représentation V) qui définissent une cobase. Si c'est
invalide, ou cette option n'est pas spécifiée, lrs trouvera sa propre cobase de départ. Les
l'arbre de recherche inversée est tronqué (élagué) chaque fois qu'un nouveau sommet est rencontré. Remarque : ceci
ne produit pas nécessairement l'ensemble de tous les sommets adjacents au sommet optimal dans
le polyèdre, mais juste un sous-ensemble d'entre eux.

verbeuxImprimez des informations légèrement plus détaillées sur l'exécution.

le volume // Représentation en V uniquement // Calculer le volume - voir la section Volume Calcul.

voronoï // Représentation en V uniquement - placer immédiatement après l'instruction de fin // Calculer
Diagramme de Voronoï - voir section Voronoï Diagrammes.

NOTES

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. linéarités
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linéarités

4. Duplication de sortie
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%20Commentaires

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

7. Programmation linéaire
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programmation

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

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

10. Diagrammes de Voronoï.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoï%20Diagrammes

Utilisez lrsfourier en ligne en utilisant les services onworks.net