lrsfourier - Online en la nube

PROGRAMA:

NOMBRE

lrslib: convierte entre representaciones de poliedros convexos.

SINOPSIS

LRS entrada.ine

LRS entrada.ine | lrsbúfer

lrsfourier archivo.ine [salida de archivo]

redundar entrada.ine

DESCRIPCIÓN

Un poliedro se puede describir mediante una lista de desigualdades (Representación H) o como por una lista
de sus vértices y rayos extremos (Representación en V). LRS es un programa en C que convierte un
Representación H de un poliedro a su representación V, y viceversa. Estos problemas
son conocidos respectivamente en el vértice enumeración y convexo cáscara problemas.

De Fukuda Preguntas Frecuentes página[1] contiene una introducción más detallada al problema, junto con
muchos consejos útiles para el nuevo usuario.

lrsbúfer puede eliminar algunos resultados duplicados. redundar encuentra desigualdades redundantes en el
entrada.

ARCHIVO FORMATOS

Los formatos de archivo se desarrollaron conjuntamente con Komei Fukuda y son compatibles con cdd[2].

La entrada para LRS es una representación H o V de un politopo.

nombre
{línea de representación}
{opciones}
{linealidades[3]}
comenzar
mn racional
{matriz de entrada}
final
{opciones}

nombre es un nombre proporcionado por el usuario para el politopo. Los comentarios pueden aparecer antes del comienzo o
después del final, y para evitar la interpretación como una opción, debe comenzar con un especial
carácter como "*" o "#".

nombre es un nombre proporcionado por el usuario para el politopo. representación línea es cualquiera
"Representación H" o "Representación V". Si se omite, se asume la representación H. los
los coeficientes de entrada se leen en formato libre y no se comprueba el tipo. Los coeficientes son
separados por espacios en blanco. m es el número de filas yn el número de columnas de la entrada
matriz.

Representación H
El entero m es el número de desigualdades y el entero n es la dimensión de la
entrada +1. Una lista de desigualdades contiene los coeficientes de desigualdades de la forma

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

Esta desigualdad se ingresa como la línea

a0 a1 ... an-1

Los coeficientes se pueden ingresar como números enteros o racionales en el formato x / y.

Representación en V
El entero m es el número de vértices y rayos, y el entero n es la dimensión de
la entrada +1. Cada vértice se da en la forma

1 v0 v 1 ... vn-1

Cada rayo se da en la forma

0 r0 r 1 ... rn-1

donde r0 r 1 ... rn-1 es un punto del rayo.

Debe haber al menos un vértice en cada archivo. Para poliedros acotados no habrá
entraron rayos. Los coeficientes se pueden ingresar como números enteros o racionales en el formato x / y.

Note para cdd usuarios: LRS utiliza esencialmente el mismo formato de archivo que cdd. Archivos preparados para
cdd debería funcionar con poca o ninguna modificación. Tenga en cuenta que la representación V
corresponde a la opción "casco" en cdd. Opciones específicas para cdd se puede dejar en la entrada
archivos y será ignorado por LRS. Tenga en cuenta los archivos de entrada para LRS se leen en formato libre,
después de la línea m n racional, LRS buscará exactamente m * n racionales o enteros separados
por espacio en blanco (en blanco, retorno de carro, tabulación, etc.). LRS no "soltará" columnas adicionales de
ingrese si n es menor que el número de columnas suministradas.

Basic Opciones
Casi todas las opciones están colocadas después de la declaración final, manteniendo la compatibilidad con cdd.
Cuando este no sea el caso, se mencionará explícitamente.

todas las bases Esta opción instruye LRS para enumerar cada vértice (o faceta) de cada una de sus bases.
Salida Duplicación[ 4 ].[5] Esta opción se suele combinar con printcobasis.

obligado x Úselo con representación H: para lrs o nash, ya sea para maximizar o minimizar
Se debe seleccionar la opción. x es un número entero o racional. Para maximizar (resp.
minimización) el árbol de búsqueda inversa se trunca siempre que el valor objetivo actual
es menor (resp. más) que x.

cache nLRS almacena los últimos n diccionarios en el árbol de búsqueda inversa. Esto acelera
el paso de retroceso, pero requiere más memoria.

depurar base de partida finalizaciónImprima trazas crípticas pero detalladas, diccionarios, etc.
comenzando en # B = base inicial y terminando en # B = base final. depurar 0 0 da un completo
rastrear.

dígitos n metido antes las comenzar ambiental n es el número máximo de dígitos decimales que se
usó. Si se excede, el programa termina con un mensaje (normalmente puede ser
reiniciado). El valor predeterminado está configurado en aproximadamente 100 dígitos. Al final de una ejecución, se muestra un mensaje
dado que informa al usuario del tamaño de entero máximo encontrado. Esto puede usarse para
optimizar el uso de la memoria y la velocidad en ejecuciones posteriores (si se hace una estimación, por ejemplo).

dualperturbio Si lrs se ejecuta con la opción maximizar o minimizar, la búsqueda inversa
árbol está enraizado en un vértice óptimo para esta función. Si hay múltiples óptimos
vértices, la salida a menudo no estará completa. Esta opción da una pequeña perturbación a
el objetivo de evitar esto. Se da un mensaje de advertencia si el diccionario inicial es dual
degenerar.

estima k Estime el tamaño de salida. Usado junto con maxdepth - ver
Estimacion.[ 6 ]

geométrico // Opción de representación H o voronoi solamente // Con esta opción, cada rayo es
impreso junto con el vértice con el que incide. Para más información, ver
Rayos geométricos en Sugerencias y Comentarios[5].

incidenciaEsta opción se enciende automáticamente imprimircobase , así que vea a continuación una
descripción de esta opción primero. Se puede utilizar con printcobasis n. (Ver 4.2b) .PP Para
representación H de entrada, índices de todas las desigualdades de entrada que contienen el vértice / rayo que
está a punto de salir. Para una cara simple, no hay una nueva salida, ya que estos índices
ya están en la lista. De lo contrario, las desigualdades estrictas adicionales se enumeran después de dos puntos.
.PP Para la representación V de entrada, índices de todos los vértices / rayos de entrada que se encuentran en la faceta
que está a punto de salir. Un índice con asterisco indica que este vértice también está en el
cobasis, pero no está contenido en la faceta. Surge debido a la operación de elevación utilizada.
con representaciones V de entrada.

#incidenciaLo mismo que printcobasis. Incluido para compatibilidad con CDD.

linealidad k i1i2 i ... ikLa entrada contiene k linealidades en filas i1i2i ... ikde las
archivo de entrada son ecuaciones. Ver Linealidades.[ 3 ]

máxima profundidad k La búsqueda se truncará en la profundidad k. Todas las bases con profundidad menor que o
se calculará igual ak. k es un número entero no negativo, y esta opción se usa para
estimaciones - ver Estimacion.[ 6 ]Note: Para representaciones H, los rayos a una profundidad k no serán
informó. Para las representaciones en V, no se informarán las facetas a la profundidad k.

maximizarán a0 a1 ... un-1 // Representación H solamente //

minimizar a0 a1 ... un-1 // Representación H solamente //

Si se usa con lrs, el vértice inicial maximiza (o minimiza) la función a0 + a1x1 + ...
+ an-1 xn-1 La opción de doble perturbación puede ser necesaria para evitar la degeneración dual. Ver Nash
Equilibrios y Lineal Programación[ 7 ]

salida máxima n Limita el número de líneas de salida producidas (vértices + rayos o facetas) an

profundidad mental k El retroceso terminará en la profundidad k, para ka entero no negativo. Esta
se puede utilizar para ejecutar la búsqueda inversa en subárboles como procesos separados, por ejemplo, en un
entorno informático distribuido.

no negativo // Esta opción debe venir antes de la instrucción begin // // Solo representación H
// Error: solo se puede usar si el origen es un vértice del poliedro Para problemas donde
la entrada es una representación H de la forma b + Ax> = 0, x> = 0 (es decir, todas las variables
no negativo, todas las restricciones desigualdades) no es necesario dar el no negativo
restricciones explícitamente si se utiliza la opción no negativa. Esta opción no se puede utilizar para
Representaciones en V, o con la opción de linealidad (en cuyo caso las linealidades serán
tratados como desigualdades). Esta opción se puede utilizar con redund, pero la implícita
las restricciones de no negatividad no se prueban en sí mismas para determinar la redundancia. Para probarlo todo
Es necesario ingresar las restricciones de no negatividad explícitamente en el archivo de entrada. (En Ver
4.1, el origen debe ser un vértice).

imprimircobase k;Modificado en lrs 4.0 Se imprime cada k'th cobasis. Si se omite k, el
cobasis se imprime para cada vértice / rayo / faceta que se genera. A largo plazo es útil
para imprimir el cobasis ocasionalmente para que el programa pueda reiniciarse si es necesario.
Representación H: Si la entrada es una representación H, la cobase es una lista de los índices de
las desigualdades del archivo de entrada que definen el vértice o rayo actual. Ver opción
incidencia arriba para obtener más información. Para los rayos, también se imprime una cobasis. En este caso
la cobasis es la cobasis del vértice del que emana el rayo. Uno de los índices
está estrellado, esto indica la desigualdad que se eliminará de la cobasis para definir la
rayo. Alternativamente, si el todas las basesse utiliza la opción, se imprimirán todas las cobases.
Representación en V: Si la entrada es una representación en V, la cobasis es una lista de la entrada
vértices / rayos que definen la faceta actual. Ver opción incidencia arriba para más
información. Para iniciar LRS de esta faceta, los 4 índices deben darse en este orden
(omita el *).

impresiones negras Nuevo en Ver 4.2; // Usar con representación H // lrs imprime una lista de los
índices de las desigualdades de entrada que se satisfacen estrictamente para el vértice actual, es decir.
la variable de holgura correspondiente es positiva. Si se establece no negativo, la lista también
incluir índices n + i para cada variable de decisión xi que sea positiva. proyecto Usado por
lrsfourier[8] solamente.

reanudar V# R# B# profundidad {faceta #s or vértice / rayo #s} Modificado en lrs4.0 LRS puede ser
reiniciado desde cualquier cobasis conocido. El cálculo procederá a la terminación normal. Todos
de la información está contenida en la salida de un imprimircobase opción. La solicite of
las índices is muy importante, introdúzcalos exactamente como aparecen en la salida del
ejecución previamente abortada.

comenzando i1i2i ... en-1 Esto permite al usuario especificar una cobase conocida para
comenzando la búsqueda inversa. i1i2i ... en-1 es una lista de las desigualdades (para
Representación H) o vértices / rayos (para representación V) que definen una cobasis. Si esto es
inválido, o esta opción no está especificada, LRS encontrará su propia cobasis inicial. los
El árbol de búsqueda inversa se trunca (poda) cada vez que se encuentra un nuevo vértice. Nota: este
nota necesariamente produce el conjunto de todos los vértices adyacentes al vértice óptimo en
el poliedro, pero solo un subconjunto de ellos.

verbosoImprime información un poco más detallada sobre la ejecución.

volumen // Representación V solamente // Calcular volumen - ver sección Volumen Cálculo.[ 9 ]

voronói // Solo representación en V: lugar inmediatamente después de la instrucción final // Calcular
Diagrama de Voronoi - ver sección Voronói Diagramas.[ 10 ]

NOTAS

1. Página de preguntas frecuentes
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. linealidades
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linealidades

4. Duplicación de salida
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Salida% 20Duplicación

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

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

7. Programación lineal
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linear% 20Programming

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

9. Computación de volumen.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Volume% 20Computation

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

Utilice lrsfourier en línea utilizando los servicios de onworks.net