Expresse operações lógicas booleanas na programação linear inteira zero (um)

58

Eu tenho um programa linear inteiro (ILP) com algumas variáveis xEu que se destinam a representar valores booleanos. Os xEu são restritos a serem inteiros e a conter 0 ou 1 ( 0 0xEu1 ).

Eu quero expressar operações booleanas nessas variáveis ​​com valor de 1/1, usando restrições lineares. Como posso fazer isso?

Mais especificamente, eu quero definir y1=x1x2 (booleano AND), y2=x1x2 (booleano OR), e y3=¬x1 (boolean NOT). Estou usando a interpretação óbvia de 0/1 como valores booleanos: 0 = false, 1 = true. Como faço para escrever restrições ILP para garantir que o yEu 's são relacionados à xEu ' s como desejado?

(Isso pode ser visto como uma redução do CircuitSAT para o ILP ou uma maneira de expressar o SAT como um ILP, mas aqui quero ver uma maneira explícita de codificar as operações lógicas mostradas acima.)

DW
fonte

Respostas:

66

AND lógico: use as restrições lineares y1x1+x2-1 , y1x1 , y1x2 , 0 0y11 , em que y1 é restrito como um número inteiro. Isso reforça o relacionamento desejado. (Muito legal que você pode fazê-lo com apenas desigualdades lineares , hein?)

OR lógico: use as restrições lineares y2x1+x2 , y2x1 , y2x2 , 0 0y21 , em que y2 é restrito para ser um número inteiro.

Lógico NÃO: Use y3=1-x1 .

Implicação lógica: Para expressar y4=(x1x2) (ou seja, y4=¬x1x2 ), podemos adaptar a construção para OR lógico. Em particular, use as restrições lineares y41-x1+x2 , y41-x1 , y4x2 , 0 0y41 , ondey4 é constrangida a ser um número inteiro.

Implicação lógica forçada: Para expressar que x1x2 deve se manter, basta usar a restrição linear x1x2 (supondo que x1 e x2 já estejam restritos a valores booleanos).

XOR: Para expressar y5=x1x2 (a exclusiva ou-de x1 e x2 ), utilizar as desigualdades lineares y5x1+x2 , y5x1-x2 , y5x2-x1 , y52-x1-x2 , 0 0y51 , ondey5 é restrito a ser um número inteiro.


E, como bônus, mais uma técnica que geralmente ajuda na formulação de problemas que contêm uma mistura de variáveis ​​zero-um (booleanas) e variáveis ​​inteiras:

Transmitir para booleano (versão 1): suponha que você tenha uma variável inteira x e queira definir y para que y=1 se x0 0 e y=0 0 se x=0 0 . Se você souber adicionalmente que 0 0xvocê , poderá usar as desigualdades lineares 0 0y1 , yx , xvocêy ; no entanto, isso só funciona se você souber um limite superior e inferior nox . Ou, se você sabe disso|x|você (ou seja,-vocêxvocê ) para alguma constantevocê , você pode usar o método descritoaqui. Isso é aplicável apenas se você souber um limite superior em|x|.

Transmitir para booleano (versão 2): Vamos considerar o mesmo objetivo, mas agora não sabemos um limite superior em x . No entanto, suponha que sabemos que x0 0 . Veja como você pode expressar essa restrição em um sistema linear. Primeiro, introduza uma nova variável inteira t . Adicione desigualdades 0 0y1 , yx , t=x-y . Em seguida, escolha a função objetivo para minimizar t . Isso funciona apenas se você ainda não possui uma função objetiva. Se você tem nvariáveis ​​inteiras não negativas x1,...,xn e você deseja converter todas elas em booleanos, para queyEu=1 sexEu1 eyEu=0 0 sexEu=0 0 , você pode introduzirn variáveist1,...,tn com desigualdades0 0yEu1 ,yEuxEu, tEu=xEu-yEu e defina a função objetivo para minimizar t1++tn . Novamente, isso só funciona e nada mais precisa definir uma função objetiva (se, além dos lançamentos para booleano, você planejasse apenas verificar a viabilidade do ILP resultante, não tentar minimizar / maximizar alguma função das variáveis).


Para alguns problemas práticos excelentes e exemplos trabalhados, eu recomendo a Formulação de Programas Lineares Inteiros: A Rogues 'Gallery .

DW
fonte
qual solucionador de programação linear pode resolver isso? porque no formato * .lp ou * .mps, um lado da restrição deve ser um número inteiro fixo e não uma variável.
Box 25/03
4
@ Boxi, não sei nada sobre o formato * .lp ou * .mps, mas todo solucionador de programação linear inteira deve ser capaz de resolver isso. Observe que se você tiver algo como , isso é equivalente a y - x 0 , que pode estar no formato desejado. xyy-x0 0
DW
-i verifiquei novamente. O lp_solve pode resolvê-lo, mas, por exemplo, o qsopt não pode. não sei porque. mas obrigado <3
boxi 25/03
@boxi, acabei de verificar a GUI do applet QSopt on-line e ele pode lidar com esses tipos de restrições depois de alterar para x - y 0 , então não tenho certeza do que está acontecendo. (Usei o formato * .lp.) Eu ficaria surpreso se algum solucionador de ILP não conseguisse lidar com esses sistemas. Se você tiver mais perguntas sobre o QSopt, provavelmente deverá levá-las aos fóruns de suporte do QSopt. xyxy0 0
DW
1
@Pramod, boa captura! Obrigado por detectar esse erro. Você está absolutamente correto. Fiz uma nova pergunta sobre como modelar esse caso e atualizarei essa resposta quando tivermos uma resposta para esse.
DW
19

A relação lógica AND pode ser modelada em uma restrição de intervalo, em vez de três restrições (como na outra solução). Portanto, em vez da três restrições ele pode ser escrito usando a restrição de intervalo único 0 x 1 + x 2 - 2 y 1

y1x1+x2-1,y1x1,y1x2,
Da mesma forma, para OR lógico: 0 2 y 1 - x 1 - x 2
0 0x1+x2-2y11.
0 02y1-x1-x21.

Para NOT, essa melhoria não está disponível.

Em geral, para ( n -WAY E) a restrição será: 0 Σ x i - n y n - 1y=x1x2xnn Da mesma forma para OR: 0 n y - x in - 1

0 0xEu-nyn-1.
0 0ny-xEun-1.
Abdelmonem Mahmoud Amer
fonte
Uma abordagem muito semelhante é neste artigo: ncbi.nlm.nih.gov/pmc/articles/PMC1865583 #
Abdelmonem Mahmoud Amer
3

Encontrei uma solução mais curta para XOR y = x1⊕x2 (xey são binários 0, 1)

apenas uma linha: x1 + x2 - 2 * z = y (z é qualquer número inteiro)

Bysmyyr
fonte
Para expressar a igualdade no ILP, você precisa de duas desigualdades. Além disso, para evitar a solução x1=1,x2=0 0,z=200,y=-1990 0y1
b