Problema do tipo LP - LP-type problem

No estudo de algoritmos , um problema do tipo LP (também chamado de programa linear generalizado ) é um problema de otimização que compartilha certas propriedades com programas lineares de baixa dimensão e que pode ser resolvido por algoritmos semelhantes. Os problemas do tipo LP incluem muitos problemas de otimização importantes que não são programas lineares, como o problema de encontrar o menor círculo contendo um determinado conjunto de pontos planares. Eles podem ser resolvidos por uma combinação de algoritmos aleatórios em um período de tempo que é linear no número de elementos que definem o problema e subexponencial na dimensão do problema.

Definição

Problemas do tipo LP foram definidos por Sharir & Welzl (1992) como problemas nos quais é dado como entrada um conjunto finito S de elementos e uma função f que mapeia subconjuntos de S para valores de um conjunto totalmente ordenado. A função é necessária para satisfazer duas propriedades principais:

  • Monotonicidade: para cada dois conjuntos A ⊆ B ⊆ S , f ( A ) ≤ f ( B ) ≤ f ( S ).
  • Localidade: para cada dois conjuntos A ⊆ B ⊆ S e cada elemento x em S , se f ( A ) = f ( B ) = f ( A ∪ { x }) , então f ( A ) = f ( B ∪ { x }) .

A base de um problema do tipo LP é um conjunto B ⊆ S com a propriedade de que cada subconjunto próprio de B tem um valor menor de f do que o próprio B , e a dimensão (ou dimensão combinatória ) de um problema do tipo LP é definida para ser a cardinalidade máxima de uma base.

Supõe-se que um algoritmo de otimização pode avaliar a função f apenas em conjuntos que são bases ou que são formados pela adição de um único elemento a uma base. Alternativamente, o algoritmo pode ser restrito a duas operações primitivas: um teste de violação que determina, para uma base B e um elemento x se f ( B ) = f ( B ∪ { x }) , e um cálculo de base que (com o mesmo entradas) encontra uma base de B ∪ { x }. A tarefa a ser executada pelo algoritmo é avaliar f ( S ) usando apenas essas avaliações restritas ou primitivas.

Exemplos e aplicações

Lp Balls

Um programa linear pode ser definido por um sistema de d variáveis ​​reais não negativas , sujeitas a n restrições de desigualdade linear, juntamente com uma função objetivo linear não negativa a ser minimizada. Isso pode ser colocado na estrutura de problemas do tipo LP, deixando S ser o conjunto de restrições e definindo f ( A ) (para um subconjunto A das restrições) como o valor mínimo da função objetivo do programa linear menor definido por Um . Com suposições de posição geral adequadas (a fim de evitar que vários pontos de solução tenham o mesmo valor de função objetivo ideal), isso satisfaz os requisitos de monotonicidade e localidade de um problema do tipo LP e tem dimensão combinatória igual ao número d de variáveis. Da mesma forma, um programa inteiro (consistindo em uma coleção de restrições lineares e uma função objetivo linear, como em um programa linear, mas com a restrição adicional de que as variáveis ​​devem assumir apenas valores inteiros) satisfaz as propriedades de monotonicidade e localidade de um LP -tipo problema, com as mesmas suposições de posição geral que para programas lineares. Teoremas de Bell (1977) e Scarf (1977) mostram que, para um programa inteiro com d variáveis, a dimensão combinatória é no máximo  2 d .

Muitos problemas de otimização natural em geometria computacional são do tipo LP:

Image
Problema do menor círculo
  • O problema do menor círculo é encontrar o raio mínimo de um círculo contendo um determinado conjunto de n pontos no plano. Ele satisfaz a monotonicidade (adicionar mais pontos só pode tornar o círculo maior) e localidade (se o menor círculo do conjunto A contém B e x , então o mesmo círculo também contém B ∪ { x }). Como o menor círculo é sempre determinado por alguns três pontos, o menor problema do círculo tem dimensão combinatória três, embora seja definido usando a geometria euclidiana bidimensional. Mais geralmente, a menor bola de pontos envolventes em d dimensões forma um problema do tipo LP de dimensão combinatória d + 1 . O menor problema do círculo pode ser generalizado para a menor bola envolvendo um conjunto de bolas, para a menor bola que toca ou circunda cada um de um conjunto de bolas, para o problema de 1 centro ponderado , ou para problemas semelhantes menores de bola envolvente em não Espaços euclidianos, como o espaço com distâncias definidas pela divergência de Bregman . O problema relacionado de encontrar o menor elipsóide envolvente também é um problema do tipo LP, mas com uma dimensão combinatória maior, d ( d + 3) / 2 .
  • Seja K 0 , K 1 , ... uma seqüência de n conjuntos convexos no espaço euclidiano d- dimensional, e suponha que desejamos encontrar o prefixo mais longo dessa seqüência que tem um ponto de interseção comum. Isso pode ser expresso como um problema do tipo LP em que f ( A ) = - i onde K i é o primeiro membro de A que não pertence a um prefixo de interseção de A , e onde f ( A ) = - n se houver esse membro não existe. A dimensão combinatória deste sistema é d + 1 .
  • Suponha que recebamos uma coleção de caixas retangulares alinhadas ao eixo no espaço tridimensional e desejamos encontrar uma linha direcionada para o octante positivo do espaço que corta todas as caixas. Isso pode ser expresso como um problema do tipo LP com dimensão combinatória 4.
  • O problema de encontrar a distância mais próxima entre dois politopos convexos , especificados por seus conjuntos de vértices, pode ser representado como um problema do tipo LP. Nesta formulação, o conjunto S é o conjunto de todos os vértices em ambos os politopos, e o valor da função f ( A ) é a negação da menor distância entre os cascos convexos dos dois subconjuntos A de vértices nos dois politopos. A dimensão combinatória do problema é d + 1 se os dois politopos forem disjuntos, ou d + 2 se tiverem uma intersecção não vazia.
  • Seja S = { f 0 , f 1 , ... } um conjunto de funções quase-convexas . Então, o máximo pontual max i f i é ele mesmo quase convexo, e o problema de encontrar o valor mínimo de max i f i é um problema do tipo LP. Possui dimensão combinatória no máximo 2 d + 1 , onde d é a dimensão do domínio das funções, mas para funções suficientemente suaves a dimensão combinatória é menor, no máximo d + 1 . Muitos outros problemas do tipo LP também podem ser expressos usando funções quase-convexas dessa maneira; por exemplo, o menor problema do círculo fechado é o problema de minimizar max i f i, onde cada uma das funções f i mede a distância euclidiana de um dos pontos dados.

Problemas do tipo LP também foram usados ​​para determinar os resultados ideais de certos jogos na teoria dos jogos algorítmicos , melhorar a colocação de vértices em malhas de métodos de elementos finitos , resolver problemas de localização de instalações , analisar a complexidade de tempo de certos algoritmos de busca em tempo exponencial e reconstruir o posições tridimensionais de objetos a partir de suas imagens bidimensionais.

Algoritmos

Seidel

Seidel (1991) forneceu um algoritmo para programação linear de baixa dimensão que pode ser adaptado para a estrutura de problemas do tipo LP. O algoritmo de Seidel toma como entrada o conjunto S e um conjunto separado X (inicialmente vazio) de elementos conhecidos por pertencerem à base ótima. Em seguida, considera os elementos restantes um a um em ordem aleatória, realizando testes de violação para cada um e, dependendo do resultado, realizando uma chamada recursiva para o mesmo algoritmo com um conjunto maior de elementos de base conhecidos. Pode ser expresso com o seguinte pseudocódigo: 

function seidel(S, f, X) is
    R := empty set
    B := X
    for x in a random permutation of S:
        if f(B) ≠ f(B ∪ {x}):
            B := seidel(R, f, basis(X ∪ {x}))
        R := R ∪ {x}
    return B

Em um problema com dimensão combinatória d , o teste de violação na i- ésima iteração do algoritmo falha apenas quando x é um de d - | X | restantes elementos de base, o que acontece com probabilidade no máximo ( d - | X |) / i . Com base nesse cálculo, pode-se mostrar que, de maneira geral, o número esperado de testes de violação realizados pelo algoritmo é O ( d ! N) , linear em n, mas pior do que exponencial em d .

Clarkson

Clarkson (1995) define dois algoritmos, um algoritmo recursivo e um algoritmo iterativo, para programação linear baseada em técnicas de amostragem aleatória, e sugere uma combinação dos dois que chama o algoritmo iterativo do algoritmo recursivo. O algoritmo recursivo escolhe repetidamente amostras aleatórias cujo tamanho é aproximadamente a raiz quadrada do tamanho de entrada, resolve o problema amostrado recursivamente e, em seguida, usa testes de violação para encontrar um subconjunto dos elementos restantes que devem incluir pelo menos um elemento de base: 

function recursive(S, f) is
    X := empty set
    repeat
        R := a random subset of S with size d√n
        B := basis for R ∪ X, computed recursively
        V := {x | f(B) ≠ f(B ∪ {x})}
        X := X ∪ V
    until V is empty
    return B

Em cada iteração, o tamanho esperado de V é O ( √ n ) , e sempre que V é não vazio que inclui, pelo menos, um novo elemento da eventual base de S . Portanto, o algoritmo realiza no máximo d iterações, cada uma das quais realiza n testes de violação e faz uma única chamada recursiva para um subproblema de tamanho O ( d √ n ) .

O algoritmo iterativo de Clarkson atribui pesos a cada elemento de S , inicialmente todos iguais. Ele então escolhe um conjunto R de 9 d 2 elementos de S aleatoriamente e calcula os conjuntos B e V como no algoritmo anterior. Se o peso total de V for no máximo 2 / (9 d - 1) vezes o peso total de S (como acontece com probabilidade constante), o algoritmo dobra os pesos de cada elemento de V e, como antes, repete este processo até V fica vazio. Em cada iteração, o peso da base ótima pode ser mostrado para aumentar a uma taxa maior do que o peso total de S , a partir do qual se segue que o algoritmo deve terminar dentro de O (log n ) iterações.

Usando o algoritmo recursivo para resolver um determinado problema, alternando para o algoritmo iterativo para suas chamadas recursivas e, em seguida, alternando novamente para o algoritmo de Seidel para as chamadas feitas pelo algoritmo iterativo, é possível resolver um determinado problema do tipo LP usando O ( dn + d ! d O (1) log n ) testes de violação.

Quando aplicado a um programa linear, esse algoritmo pode ser interpretado como um método dual simplex . Com certas primitivas computacionais adicionais além do teste de violação e primitivas de cálculo de base, este método pode se tornar determinístico.

Matoušek, Sharir e Welzl

Matoušek, Sharir & Welzl (1996) descrevem um algoritmo que usa uma propriedade adicional de programas lineares que nem sempre é mantida por outros problemas do tipo LP, que todas as bases têm a mesma cardinalidade umas das outras. Se um problema do tipo LP não tiver essa propriedade, ele pode ser feito adicionando d novos elementos fictícios e modificando a função f para retornar o par ordenado de seu antigo valor f ( A ) e do número min ( d , | A |) , ordenado lexicograficamente .

Em vez de adicionar elementos de S um de cada vez, ou encontrar amostras dos elementos, Matoušek, Sharir & Welzl (1996) descrevem um algoritmo que remove os elementos um de cada vez. Em cada etapa, ele mantém uma base C que pode ser inicialmente o conjunto de elementos fictícios. Ele pode ser descrito com o seguinte pseudocódigo: 

function msw(S, f, C) is
    if S = C then
        return C
    choose a random element x of S \ C
    B = msw(S \ x, f, C)
    if f(B) ≠ f(B ∪ {x}) then
        B := basis(B ∪ {x})
        B := msw(S, f, B)
    return B

Na maioria das chamadas recursivas do algoritmo, o teste de violação é bem-sucedido e a instrução if é ignorada. No entanto, com uma pequena probabilidade, o teste de violação falha e o algoritmo faz um cálculo de base adicional e, em seguida, uma chamada recursiva adicional. Como os autores mostram, o tempo esperado para o algoritmo é linear em ne exponencial na raiz quadrada de d log n . Ao combinar este método com os procedimentos recursivos e iterativos de Clarkson, essas duas formas de dependência do tempo podem ser separadas uma da outra, resultando em um algoritmo que realiza testes de violação O ( dn ) no algoritmo recursivo externo e um número que é exponencial no raiz quadrada de d log d nos níveis inferiores do algoritmo.

Variações

Otimização com outliers

Matoušek (1995) considera uma variação dos problemas de otimização do tipo LP em que um é dado, junto com o conjunto S e a função objetivo f , um número k ; a tarefa é remover k elementos de S para tornar a função objetivo no conjunto restante a menor possível. Por exemplo, quando aplicado ao problema do menor círculo, isso daria o menor círculo que contém todos, exceto k de um determinado conjunto de pontos planos. Ele mostra que, para todos os problemas do tipo LP não degenerados (ou seja, problemas em que todas as bases têm valores distintos), esse problema pode ser resolvido no tempo O ( nk d ) , resolvendo um conjunto de O ( k d ) LP -tipo problemas definidos por subconjuntos de S .

Problemas implícitos

Alguns problemas de otimização geométrica podem ser expressos como problemas do tipo LP em que o número de elementos na formulação do tipo LP é significativamente maior do que o número de valores de dados de entrada para o problema de otimização. Como exemplo, considere uma coleção de n pontos no plano, cada um se movendo com velocidade constante. Em qualquer momento, o diâmetro deste sistema é a distância máxima entre dois de seus pontos. O problema de encontrar um tempo no qual o diâmetro é minimizado pode ser formulado como minimizar o máximo pontual de O ( n 2 ) funções quasiconvexas, uma para cada par de pontos, medindo a distância euclidiana entre o par em função do tempo. Assim, pode ser resolvido como um problema do tipo LP de dimensão combinatória dois em um conjunto de elementos O ( n 2 ) , mas esse conjunto é significativamente maior do que o número de pontos de entrada.

Chan (2004) descreve um algoritmo para resolver problemas do tipo LP implicitamente definidos, como este em que cada elemento do tipo LP é determinado por um k -tuplo de valores de entrada, para alguma constante k . A fim de aplicar a sua abordagem, deve existir um algoritmo de decisão que pode determinar, para um dado tipo de LP base B e conjunto S de n valores de entrada, se B é uma base para o problema de tipo LP determinada por S .

O algoritmo de Chan executa as seguintes etapas:

  • Se o número de valores de entrada estiver abaixo de algum valor limite, encontre o conjunto de elementos do tipo LP que ele determina e resolva o problema explícito do tipo LP resultante.
  • Caso contrário, particione os valores de entrada em um número adequado maior que k de subconjuntos de tamanhos iguais S i .
  • Se f é a função objetivo para o problema do tipo LP implicitamente definido a ser resolvido, então defina uma função g que mapeia coleções de subconjuntos S i ao valor de f na união da coleção. Então, a coleção de subconjuntos S i e a própria função objetivo g definem um problema do tipo LP, da mesma dimensão que o problema implícito a ser resolvido.
  • Resolva o problema do tipo LP (explícito) definido por g usando o algoritmo de Clarkson, que realiza um número linear de testes de violação e um número polilogarítmico de avaliações de base. As avaliações básicas para g podem ser realizadas por chamadas recursivas ao algoritmo de Chan, e os testes de violação podem ser realizados por chamadas ao algoritmo de decisão.

Com a suposição de que o algoritmo de decisão leva uma quantidade de tempo O ( T ( n )) que cresce pelo menos polinomialmente em função do tamanho de entrada n , Chan mostra que o limite para mudar para uma formulação LP explícita e o número de subconjuntos na partição pode ser escolhido de tal forma que o algoritmo de otimização do tipo LP implícito também execute no tempo O ( T ( n )) .

Por exemplo, para o diâmetro mínimo de pontos móveis, o algoritmo de decisão precisa apenas calcular o diâmetro de um conjunto de pontos em um tempo fixo, um problema que pode ser resolvido em tempo O ( n log n ) usando a técnica de calibradores rotativos . Portanto, o algoritmo de Chan para encontrar o tempo em que o diâmetro é minimizado também leva tempo O ( n log n ) . Chan usa este método para encontrar um ponto de profundidade máxima de Tukey entre uma dada coleção de n pontos no espaço euclidiano d- dimensional, no tempo O ( n d - 1 + n log n ) . Uma técnica semelhante foi usada por Braß, Heinrich-Litan & Morin (2003) para encontrar um ponto de profundidade máxima de Tukey para a distribuição uniforme em um polígono convexo.

História e problemas relacionados

A descoberta de algoritmos de tempo linear para programação linear e a observação de que os mesmos algoritmos poderiam em muitos casos ser usados ​​para resolver problemas de otimização geométrica que não eram programas lineares remonta pelo menos a Megiddo ( 1983 , 1984 ), que deu um tempo linear esperado algoritmo para programas lineares de três variáveis ​​e o problema do menor círculo. No entanto, Megiddo formulou a generalização da programação linear geometricamente ao invés de combinatorialmente, como um problema de otimização convexa ao invés de um problema abstrato em sistemas de conjuntos. Da mesma forma, Dyer (1986) e Clarkson (na versão da conferência de 1988 de Clarkson 1995 ) observaram que seus métodos podiam ser aplicados tanto a programas convexos quanto a programas lineares. Dyer (1992) mostrou que o problema do elipsóide de fechamento mínimo também poderia ser formulado como um problema de otimização convexa, adicionando um pequeno número de restrições não lineares. O uso de randomização para melhorar os limites de tempo para programação linear de baixa dimensão e problemas relacionados foi iniciado por Clarkson e por Dyer & Frieze (1989) .

A definição de problemas do tipo LP em termos de funções que satisfaçam os axiomas de localidade e monotonicidade é de Sharir & Welzl (1992) , mas outros autores no mesmo período formularam generalizações combinatórias alternativas de programas lineares. Por exemplo, em um modelo desenvolvido por Gaertner (1995) , a função F é substituído por uma ordem total sobre os subconjuntos de S . É possível quebrar os laços em um problema do tipo LP para criar uma ordem total, mas apenas às custas de um aumento na dimensão combinatória. Além disso, como em problemas do tipo LP, Gärtner define certas primitivas para realizar cálculos em subconjuntos de elementos; entretanto, sua formalização não tem um análogo da dimensão combinatória.

Outra generalização abstrata tanto de programas lineares quanto de problemas de complementaridade linear , formulada por Stickney & Watson (1978) e posteriormente estudada por vários outros autores, diz respeito às orientações das bordas de um hipercubo com a propriedade de que todas as faces do hipercubo (incluindo todo o hipercubo como uma face) tem um coletor único , um vértice sem arestas de saída. Uma orientação deste tipo pode ser formada a partir de um problema do tipo LP, correspondendo os subconjuntos de S com os vértices de um hipercubo de tal forma que dois subconjuntos diferem por um único elemento se e somente se os vértices correspondentes forem adjacentes, e por orientar a aresta entre os conjuntos vizinhos A ⊆ B em direção a B se f ( A ) ≠ f ( B ) e em direção a A caso contrário. A orientação resultante tem a propriedade adicional de formar um gráfico acíclico direcionado , a partir do qual pode ser mostrado que um algoritmo aleatório pode encontrar o sumidouro único de todo o hipercubo (a base ótima do problema do tipo LP) em uma série de etapas exponencial na raiz quadrada de  n .

A estrutura de espaços violadores desenvolvida mais recentemente generaliza problemas do tipo LP, no sentido de que todo problema do tipo LP pode ser modelado por um espaço violador, mas não necessariamente vice-versa. Espaços violadores são definidos de forma semelhante aos problemas do tipo LP, por uma função f que mapeia conjuntos para valores de função objetivo, mas os valores de f não são ordenados. Apesar da falta de ordenação, cada conjunto S tem um conjunto de bases bem definido (os conjuntos mínimos com o mesmo valor de todo o conjunto) que podem ser encontrados por variações dos algoritmos de Clarkson para problemas do tipo LP. Na verdade, foi demonstrado que os espaços de violação caracterizam exatamente os sistemas que podem ser resolvidos pelos algoritmos de Clarkson.

Notas

Referências