0-1 Programação linear: computando a formulação ideal

Considere o espaço dimensional e deixe ser uma restrição linear no formato , em que , e . $n$ $\{0,1\}^n$ $c$ $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$ $a_i \in \mathbb{R}$ $x_i \in \{0,1\}$ $k \in \mathbb{R}$

Claramente, tem o efeito de dividir em dois subconjuntos e . contém todos e apenas os pontos que satisfazem , enquanto contém todos e apenas os pontos que falsificam . $c$ $\{0,1\}^n$ $S_c$ $S_{\lnot c}$ $S_c$ $c$ $S_{\lnot c}$ $c$

Suponha que $|S_c| \geq n$ . Agora, seja $O$ um subconjunto de $S_c$ modo que todas as três instruções a seguir sejam :

$O$ contém exatamente $n$ pontos.
Tais $n$ pontos são linearmente independentes.
Tais $n$ pontos são aqueles à distância mínima do hiperplano representado por $c$ . Mais precisamente, seja $d( x, c )$ a distância de um ponto $x \in \{0,1\}^n$ do hiperplano $c$ . Então, $\forall B \subseteq S_c$ modo que $B$ satisfaça 1 e 2, é o caso $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$ . Em outras palavras, $O$ é, dentre todos os subconjuntos de $S_c$ atendem às condições 1 e 2, aquele que minimiza a soma das distâncias de seus pontos do hiperplano $c$ .

Questões

Dado $c$ , é possível calcular $O$ eficiência?

Qual é o algoritmo mais conhecido para computá-lo?

$\$

Exemplo com $n = 3$

Exemplo com n = 3

$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$ , $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$ .

$\$

Atualização 05/12/2012

Motivação

A motivação é que o uso de $O$ deverá ser possível para determinar o óptimo de restrição $c^*$ , como deve ser o hiperplana definido pelos $n$ pontos em $O$ .

A restrição ideal $c^*$ é aquela que leva ao polítopo ótimo $P^*$ .

O polítopo ideal é aquele cujos vértices são todos e apenas os vértices inteiros do polítopo inicial (um vértice inteiro é um vértice cujas coordenadas são todas inteiras). $P^*$ $P$

Formulação ideal

O processo pode ser iterado para cada restrição de uma instância 0-1 , substituindo sempre com sua restrição ideal correspondente . No final, isto levará à óptima poliepítopo de . Então, como os vértices de são todos e somente os vértices inteiros do polítopo inicial de , qualquer algoritmo para pode ser usado para calcular a solução inteira ideal. Eu sei que ser capaz de calcular eficiência implicaria , no entanto, a seguinte pergunta adicional ainda permanece: $c$ $LP$ $I$ $c$ $c^*$ $P^*$ $I$ $P^*$ $P$ $I$ $LP$ $P^*$ $P = NP$

Pergunta adicional

Existe algum trabalho anterior nesse sentido? Alguém já investigou a tarefa da computação, dado um polítopo , seu correspondente polítopo ótimo ? Qual é o algoritmo mais conhecido para fazer isso? $P$ $P^*$

reference-request co.combinatorics optimization linear-programming convex-optimization Giorgio Camerani
fonte

Isso parece ser NP-difícil de fazer exatamente, pela redução da soma do subconjunto. Dados inteiros binários , para testar se existe um subconjunto somando , podemos testar se há um ponto no hiperplano . Você está interessado em aproximações?

v_{1}, \dots, v_{n}

$v_1,\dots,v_n$

s

$s$

v_{1} x_{1} + \dots + v_{1} x_{n} = s

$v_1x_1+\dots+v_1x_n= s$

Colin McQuillan

@ColinMcQuillan: A pergunta foi feita para uma solução exata, no entanto, certamente estou interessado também em aproximações. Por que você não transforma seu comentário em resposta?

Giorgio Camerani 04/12/12

@ColinMcQuillan: Além disso, seu hiperplano é definido usando uma igualdade, enquanto o meu é definido usando uma desigualdade. Tem certeza de que isso não faz diferença em termos de dureza? Ainda não chequei, então só estou perguntando.

Giorgio Camerani

Estou um pouco confuso sobre todas as restrições . Se você está procurando informações sobre o casco convexo de , há muitos resultados na literatura de pesquisa de operações sobre o polítopo da mochila 0-1. Em termos de formulações aproximadas, veja isso .

O

$O$

S_{c}

$S_c$

Austin Buchanan

Respostas:

Parece ser NP-difícil de fazer exatamente, pela redução da soma do subconjunto. Suponhamos que temos um procedimento eficiente para computação . Dados inteiros positivos codificados em binário, desejamos testar se existe um subconjunto somando . Pré-processe jogando fora números inteiros maiores que . $O$ $v_1,\dots,v_n$ $s$ $s$

Chame o procedimento para obter um pequeno conjunto de pontos que satisfaçam , satisfazendo suas condições de minimalidade (o pré-processamento garante ). Esse conjunto certamente conterá um ponto no hiperplano se houver um. $O$ $v_1x_1+\dots+v_1x_n\leq s$ $|S_c|\geq n$ $v_1x_1+\dots+v_1x_n= s$

Colin McQuillan
fonte

Talvez eu esteja ignorando algo macroscópico aqui, mas tenho 2 perguntas: 1) Quando você diz "Dados inteiros binários ", o que você quer dizer com binário ? pertence a . Talvez você queira dizer codificado em binário? Ou talvez você quisesse dizer positivo? 2) Por que jogar fora todos os números inteiros maiores que ? Eles podem contribuir para a solução. Por exemplo: se você jogar fora

perderá a única solução

v_{1}, . . ., v_{n}

$v_1, ..., v_n$

R

$\mathbb{R}$

s

$s$

v_{1} = - 3, v_{2} = 7, v_{3} = - 5, s = 2

$v_1 = -3, v_2 = 7, v_3 = -5, s = 2$

v_{2}

$v_2$

{v_{2}, v_{3}}

$\{v_2, v_3\}$

Giorgio Camerani

Penso que o que Colin quer dizer é que, se os coeficientes de restrição são números racionais, em sua representação binária usual, então seu problema parece difícil para o NP. (Misturar números reais e NP-difícil é sempre complicado.)

a_{i}

$a_i$

Jeffε

@GiorgioCamerani: Eu precisava dizer positivo - atualizei minha resposta.

Colin McQuillan

Parece-me que você está tentando chegar ao casco convexo do IP - em essência, é isso que os algoritmos de corte tentam alcançar. Embora existam apelações apelativas, esses métodos se dão mal na prática.

Existe toda a teoria sobre a geração de desigualdades válidas. Um bom ponto de partida seria a teoria dos livros de shrijver da programação inteira.

AJ Student
fonte