O gap de integralidade zero implica em um gap de dualidade zero para certos problemas?

Sabemos que, se o intervalo entre os valores de um programa inteiro e seu dual (o "gap de dualidade") é zero, os relaxamentos de programação linear do programa inteiro e o dual do relaxamento admitem soluções integrais (integralidade zero " Gap = Vão"). Quero saber se o inverso vale, pelo menos em alguns casos.

Suponha que eu tenha um programa inteiro 0-1 , em que a matriz é uma matriz . Suponha que o relaxamento de programação linear de tenha uma solução ótima integral. Então, o dual de programação linear de também admite uma solução integral? $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$ $A$ $0-1$ $P'$ $P$ $P'$

Eu apreciaria qualquer contra-exemplo ou ponteiro ..

ds.algorithms optimization linear-programming integrality-gap Ankur
fonte

A @Kaveh não tem certeza de que os algoritmos de aproximação sejam a tag certa aqui. ou mesmo ds.algorithms

Suresh Venkat

No primeiro parágrafo, o que você quer dizer com dual de um programa inteiro? É útil olhar para o livro de Schrijver sobre programação linear e inteira para entender o básico da teoria poliédrica e, em particular, quando os relaxamentos da programação linear têm vértices inteiros. Matrizes TUM e sistemas de desigualdades TDI são relevantes para sua pergunta.

Chandra Chekuri

@Suresh, programação linear e otimização não caem em algoritmos?

Kaveh

@ChandraChekuri Estou falando de programas lineares inteiros; então o dual é o dual padrão de um ILP para o qual a dualidade fraca se mantém. A dificuldade aqui é que condições suficientes para a integralidade das soluções de LP (primordiais) (como TUM / balanceadas, etc.) parecem passar pelo conceito aparentemente mais forte de integralidade de soluções do primal e seu LP duplo. Isso me fez pensar se a integralidade da solução primária implica a integralidade da solução dupla, pelo menos para os coeficientes integrais. PS: Eu poderia ir até o Siebel e conversarmos lá! Eu estava na sua aula há alguns anos!

Ankur

Essa pergunta em particular está mais próxima das tags que ela possui atualmente.

Suresh Venkat

Respostas:

Aqui está um exemplo que pode estar próximo de um contraexemplo da reivindicação.

Considere o LP e seu duplo para a matriz $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq 0\}$ $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y \geq 0, z \geq 0 \}$ $12 \times 6$

$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 \end{bmatrix}\,.$

Uma solução ótima de é dada por (todas as outras variáveis são zero), com o valor da função objetivo de . A solução óptima de é dada pelo vector . Se você resolver como um programa inteiro, o valor ótimo da função objetiva será de apenas e é uma solução ideal. $P'$ $y_1=y_2=y_{12}=1$ $3$ $P$ $x = [0.5~0.5~0~1~0.5~0.5]^T$ $P$ $2$ $x = [1~0~0~1~0~0]$

Em resumo, o LP tem uma solução ótima integral, mas seu duplo não possui uma solução ótima integral. Os papéis primal-duplo são revertidos da configuração que Ankur queria. Mas, dada a natureza da dualidade do LP, esse exemplo ainda poderia ser considerado um contraexemplo da afirmação geral da reivindicação original. $P'$ $P$

kbala
fonte

Obrigado! Isso funciona! Como você criou esse exemplo? Existe uma classe de problemas a partir da qual ela é extraída?

Ankur

A matriz é uma modificação da matriz limite de uma tira Mobius, apresentada em nosso artigo sobre ciclos homólogos ideais. Estive brincando com essas matrizes de fronteira recentemente e, portanto, comecei naturalmente com essa matriz para criar o exemplo que dei.

Kbala # 8/12