lrsfourier - Online na nuvem

PROGRAMA:

NOME

lrslib - Converter entre representações de poliedros convexos.

SINOPSE

lrs entrada.ine

lrs entrada.ine | lrsbuffer

lrsfourier arquivo.ine [saída de arquivo]

redundante entrada.ine

DESCRIÇÃO

Um poliedro pode ser descrito por uma lista de desigualdades (Representação H) ou como por uma lista
de seus vértices e raios extremos (Representação V). lrs é um programa C que converte um
Representação H de um poliedro para sua representação V e vice-versa. Estes problemas
são conhecidos respectivamente no vértice enumeração e convexo casco problemas.

Fukuda's Perguntas frequentes página[1] contém uma introdução mais detalhada do problema, junto com
muitas dicas úteis para o novo usuário.

lrsbuffer pode remover alguma saída duplicada. redundante encontra desigualdades redundantes no
entrada.

ARQUIVO FORMATOS

Os formatos de arquivo foram desenvolvidos em conjunto com Komei Fukuda e são compatíveis com cdd[2].

A entrada para lrs é uma representação H- ou V- de um politopo.

nome
{linha de representação}
{opções}
{linearidades[3]}
começar
mn racional
{matriz de entrada}
final
{opções}

nome é um nome fornecido pelo usuário para o politopo. Os comentários podem aparecer antes do início ou
após o final, e para evitar a interpretação como uma opção, deve começar com um especial
caractere como "*" ou "#".

nome é um nome fornecido pelo usuário para o politopo. representação linha é também
"Representação H" ou "representação V". Se for omitido, a representação H é assumida. o
os coeficientes de entrada são lidos em formato livre e não são verificados quanto ao tipo. Coeficientes são
separados por espaço em branco. m é o número de linhas eno número de colunas da entrada
matriz.

Representação H
O inteiro m é o número de desigualdades, e o inteiro n é a dimensão do
entrada +1. Uma lista de desigualdades contém os coeficientes de desigualdades do formulário

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

Esta desigualdade é inserida como a linha

a0 a1 ... an-1

Os coeficientes podem ser inseridos como inteiros ou racionais no formato x / y.

Representação em V
O inteiro m é o número de vértices e raios, e o inteiro n é a dimensão de
a entrada +1. Cada vértice é dado na forma

1 v0 v 1 ... vn-1

Cada raio é dado na forma

0 r0 r 1 ... rn-1

onde r0 r 1 ... rn-1 é um ponto no raio.

Deve haver pelo menos um vértice em cada arquivo. Para poliedros delimitados, não haverá
raios entraram. Os coeficientes podem ser inseridos como inteiros ou racionais no formato x / y.

Note para cdd usuários: lrs usa essencialmente o mesmo formato de arquivo que cdd. Arquivos preparados para
cdd deve funcionar com pouca ou nenhuma modificação. Observe que a representação em V
corresponde à opção "casco" em cdd. Opções específicas para cdd pode ser deixado na entrada
arquivos e serão ignorados por lrs. Observe os arquivos de entrada para lrs são lidos em formato livre,
depois da linha m n racional, lrs iráprocurar exatamente m * n racionais ou inteiros separados
por espaço em branco (em branco, retorno de carro, guia etc.). lrs não vai "descartar" colunas extras de
entrada se n for menor que o número de colunas fornecidas.

Basico Opções
Quase todas as opções são colocadas depois de a declaração final, mantendo a compatibilidade com cdd.
Quando este não for o caso, será mencionado explicitamente.

todas as bases Esta opção instrui lrs para listar cada vértice (ou faceta) para cada uma de suas bases.
saída Duplicação[4].[5] Esta opção é freqüentemente combinada com printcobasis.

obrigado x Use com representação H - para lrs ou nash Maximize ou minimize
opção deve ser selecionada. x é um número inteiro ou racional. Para maximização (resp.
minimização) a árvore de pesquisa reversa é truncada sempre que o valor do objetivo atual
é menos (resp. mais) do que x.

esconderijo nlrs armazena os últimos n dicionários na árvore de pesquisa reversa. Isso acelera
a etapa de retrocesso, mas requer mais memória.

depurar base de partida terminando a baseImprima rastreamento enigmático, mas detalhado, dicionários etc.
começando em # B = base inicial e terminando em # B = base final. depurar 0 0 dá um completo
vestígio.

dígitos n colocado antes que o começar afirmação n é o número máximo de dígitos decimais a serem
usado. Se for excedido, o programa termina com uma mensagem (geralmente pode ser
reiniciado). O padrão é definido para cerca de 100 dígitos. No final de uma corrida, uma mensagem é
fornecido informando ao usuário o tamanho inteiro máximo encontrado. Isso pode ser usado para
otimizar o uso de memória e velocidade em execuções subsequentes (se estiver fazendo estimativas, por exemplo).

perturbação dupla Se lrs for executado com a opção de maximizar ou minimizar, a pesquisa reversa
árvore está enraizada em um vértice ótimo para esta função.
vértices, a saída geralmente não será concluída. Esta opção dá uma pequena perturbação para
o objetivo de evitar isso. Uma mensagem de aviso é dada se o dicionário inicial for dual
degenerar.

estimativas k Estime o tamanho da saída. Usado em conjunto com maxdepth - consulte
Estimativa.[6]

geométrico // Representação H ou opção voronoi apenas // Com esta opção, cada raio é
impresso junto com o vértice com o qual é incidente. Para mais informações, veja
Raios geométricos em Dicas e Comentários[5].

incidênciaEsta opção liga automaticamente printcobase , então veja abaixo um
descrição desta opção primeiro. Pode ser usado com printcobasis n. (Ver 4.2b) .PP para
entrada representação H, índices de todas as desigualdades de entrada que contêm o vértice / raio que
está prestes a ser produzido. Para simplificar, não há saída nova, uma vez que esses índices
já estão listados. Caso contrário, as desigualdades restritas adicionais são listadas após dois pontos.
.PP Para a representação V de entrada, índices de todos os vértices / raios de entrada que se encontram na faceta
que está prestes a ser produzido. Um índice com estrela indica que este vértice também está no
cobasis, mas não está contido na faceta. Surge devido à operação de elevação utilizada
com representações V de entrada.

#incidênciaO mesmo que printcobasis. Incluído para compatibilidade com cd.

linearidade k i1i2 i ... ikA entrada contém k linearidades em linhas i1i2i ... ikda
arquivo de entrada são equações. Ver Linearidades.[3]

profundidade máxima k A pesquisa será truncada na profundidade k. Todas as bases com profundidade menor que ou
igual a k será calculado. k é um número inteiro não negativo, e esta opção é usada para
estimativas - veja Estimativa.[6]Note: Para representações H, os raios na profundidade k não serão
relatado. Para representações em V, as facetas na profundidade k não serão relatadas.

maximizar a0 a1 ... um-1 // apenas representação H //

minimizar a0 a1 ... um-1 // apenas representação H //

Se usado com lrs, o vértice inicial maximiza (ou minimiza) a função a0 + a1x1 + ...
+ an-1 xn-1. A opção dualperturb pode ser necessária para evitar degenerescência dupla. Ver Nash
Equilíbrio e Linear Programação[7]

saída máxima n Limita o número de linhas de saída produzidas (vértices + raios ou facetas) para n

profundidade mínima k O retrocesso será encerrado na profundidade k, para ka inteiro não negativo. Esse
pode ser usado para executar a pesquisa reversa em subárvores como processos separados, por exemplo, em um
ambiente de computação distribuída.

não negativo // Esta opção deve vir antes da instrução begin // // apenas representação H
// Bug: Só pode ser usado se a origem for um vértice do poliedro Para problemas onde
a entrada é uma representação H da forma b + Ax> = 0, x> = 0 (ou seja, todas as variáveis
não negativo, todas as restrições de desigualdades), não é necessário dar o não negativo
restrições explicitamente se a opção não negativa for usada. Esta opção não pode ser usada para
V-representações, ou com a opção de linearidade (neste caso as linearidades serão
tratados como desigualdades). Esta opção pode ser usada com redundância, mas o implícito
as restrições de não-negatividade não são testadas para redundância. Para testar tudo isso
é necessário inserir as restrições de não-negatividade explicitamente no arquivo de entrada. (Em Ver
4.1, a origem deve ser um vértice).

printcobase k;Modificado em lrs 4.0. Cada k'th cobasis é impressa. Se k for omitido, o
cobasis é impresso para cada vértice / raio / faceta que é produzido. Para um longo prazo, é útil
para imprimir o cobasis ocasionalmente para que o programa possa ser reiniciado se necessário.
Representação H: Se a entrada for uma representação H, a cobase é uma lista dos índices de
as desigualdades do arquivo de entrada que definem o vértice ou raio atual. Veja a opção
incidência acima para obter mais informações. Para os raios, uma cobase também é impressa. Nesse caso
a cobase é a cobase do vértice de onde o raio emana. Um dos índices
está marcado com estrela, isso indica a desigualdade a ser eliminada da cobase para definir o
raio. Alternativamente, se o todas as basesopção for usada, todos os cobases serão impressos.
Representação em V: Se a entrada for uma representação em V, o cobasis é uma lista da entrada
vértices / raios que definem a faceta atual. Veja a opção incidência acima para mais
em formação. Iniciar lrs desta faceta, todos os 4 índices devem ser dados nesta ordem
(omita o *).

falta de impressão Novo na versão 4.2; // Use com representação H // lrs imprime uma lista dos
índices das desigualdades de entrada que são satisfeitas estritamente para o vértice atual, ou seja,
a variável de folga correspondente é positiva. Se não negativo for definido, a lista também
incluem índices n + i para cada variável de decisão xi que é positiva. projeto Usado por
lrsfourier[8] apenas.

restart V# R# B# profundidade {faceta #s or vértice / raio #s} Modificado em lrs4.0 lrs pode ser
reiniciado a partir de qualquer cobase conhecida. O cálculo prosseguirá para o encerramento normal. Tudo
das informações estão contidas na saída de um printcobase opção. O ordem of
que o índices is muito importante, insira-os exatamente como aparecem na saída do
execução abortada anteriormente.

começando a cobase i1i2i ... em-1 Isso permite que o usuário especifique uma cobase conhecida para
começando a busca reversa. i1i2i ... em-1 é uma lista das desigualdades (para
Representação H) ou vértices / raios (para representação em V) que definem uma cobase. Se for
inválido ou esta opção não foi especificada, lrs encontrará seu próprio cobasis inicial. o
a árvore de pesquisa reversa é truncada (podada) sempre que um novo vértice é encontrado. Nota: este
nota necessariamente produz o conjunto de todos os vértices adjacentes ao vértice ideal em
o poliedro, mas apenas um subconjunto deles.

detalhadoImprima informações um pouco mais detalhadas sobre a execução.

volume // Apenas representação em V // Computa o volume - consulte a seção Volume Computação.[9]

Voronoi // Apenas representação V - coloque imediatamente após a instrução final // Compute
Diagrama de Voronoi - consulte a seção Voronoi Diagramas.[10]

NOTAS

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

4. Duplicação de saída
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. Estimativa.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Estimation

7. Programação Linear
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linear% 20Programming

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

9. Computação de volume.
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

Use lrsfourier online usando serviços onworks.net