Por que a negligência complementar é importante?

10

Folga complementar (CS) é comumente ensinada quando se fala de dualidade. Estabelece uma boa relação entre as restrições / variáveis ​​primárias e as duplas do ponto de vista matemático.

Os dois principais motivos para a aplicação do CS (conforme ensinado em cursos de graduação e livros didáticos):

  1. Para verificar a otimização do LP
  2. Para ajudar a resolver o duplo

Dado o poder computacional de hoje e os algoritmos polinomiais para resolver LPs, o CS ainda é relevante do ponto de vista pragmático? Sempre poderíamos resolver os duais e abordar os dois pontos acima. Concordo que é "mais eficiente" resolver o dual com a ajuda do CS, mas é isso? Ou há mais no CS do que aparenta? Onde exatamente o CS é útil além dos dois pontos acima ? Eu geralmente vi textos aludindo ao conceito de CS quando falamos sobre algoritmos de aproximação, mas não entendo seu papel lá.

Doutorado
fonte
2
Não é minha área de especialização, mas parece que você está perguntando por que ensinamos propriedades de X, mesmo que decidir X seja computacionalmente fácil. Por exemplo, por que ensinamos a caracterização da bipartidade "sem ciclos ímpares = bipartidos", apesar de termos algoritmos de tempo polinomial para verificar a bipartidade. É isso que você está perguntando, em algum sentido?
22614 Robin Ontário
Não exatamente. Eu entendo "por que" você ensina. Desejo saber de um ponto de vista prático como ele é usado na resolução de LPs e / ou no design de algoritmos de aproximação. Qual é o insight que obtemos além das relações matemáticas entre as variáveis ​​e as restrições.
PhD
Bem, acho que pode ajudar a obter soluções "analíticas" ... que podem ser mais difíceis de obter com um computador.
usul
11
Eu não entendi a pergunta. Só porque usamos calculadoras e computadores para adicionar e multiplicar números, ainda precisamos conhecer as propriedades dos números?
Chandra Chekuri
@ChandraChekuri - não quero dizer isso. Estou apenas tentando descobrir o que há de tão bom nesse teorema e o que o torna importante. Eu não quero aceitá-lo como um "que é como ele é", mas gostaria de ter uma compreensão mais profunda de sua importância wrt LP dualidade
PhD

Respostas:

14

A negligência complementar é essencial para o design de algoritmos primal-duplo. A ideia básica é:

  1. Comece com uma solução dupla viável .y
  2. Tente encontrar primário viável, de modo que satisfaçam folga complementar.x(x,y)
  3. Se o passo 2. for bem-sucedido, estamos concluídos. Caso contrário, uma obstrução para encontrar permite modificar modo que o valor da função objetiva dupla aumente. Repetir.xy

Um exemplo clássico é o algoritmo húngaro. O algoritmo Ford-Fulkerson pode ser visto como outro exemplo. Observe que a etapa 2. é um problema de viabilidade que geralmente é mais fácil do que o problema de otimização original e também pode ser resolvido combinatoriamente. Esse é o poder da negligência complementar. Por exemplo, no caso de correspondência bipartida de custo mínimo, a etapa 2 equivale a verificar se existe uma correspondência perfeita usando apenas arestas apertadas. No caso de vazão máxima - , a etapa 2 equivale a verificar se as arestas saturadas separam e .stst

Os algoritmos primal-duplos são bons por vários motivos. Filosoficamente, eles fornecem mais informações do que um algoritmo genérico. Eles geralmente fornecem algoritmos de tempo fortemente polinomiais, enquanto ainda não temos solucionadores de LP fortemente polinomiais. Eles geralmente são mais práticos do que algoritmos genéricos. Isso é especialmente verdadeiro se não podemos escrever o LP explicitamente e nossa única outra opção é o algoritmo elipsóide, que é o caso da correspondência não bipartida e do algoritmo primal-dual de Edmonds.

Primal-dual também é uma estrutura muito útil para algoritmos de aproximação, usando versões descontraídas de folga complementar. Isso tem sido útil no projeto de algoritmos de aproximação para problemas difíceis de NP (veja, por exemplo, o Capítulo 7 do livro Williamson-Shmoys ) e no design de algoritmos on-line com boa relação competitiva (veja o livro de Buchbinder e Naor ). O ponto aqui é que o algoritmo mantém uma solução ao duplo do relaxamento de LP de um problema difícil e, a cada passo, encontra um viável primal integral modo que a folga complementar aproximada é satisfeita ou melhora a solução duplayxy. A preguiça complementar aproximada é uma condição da seguinte forma: se , a restrição dupla correspondente é estanque e, se , a restrição primal correspondente seria estanque se for escalonado por . Isso fornece um fator de aproximação . Está tudo muito bem explicado nas duas fontes acima.xEu>0 0yj>0 0xαα

Sasho Nikolov
fonte