# Programação linear inteira

Variáveis inteiras e binárias, relaxação, branch and bound e cortes válidos.

Página: https://resumos.rgo.pt/cadeiras/da/programacao-inteira/

Comprar máquinas exige quantidades inteiras. Uma solução LP que propõe $4/3$ de cada máquina pode servir de limite otimista, mas não de plano de compra executável. A **programação linear inteira**, ou **ILP**, acrescenta domínios inteiros a um modelo linear.

A relaxação, a ramificação e os cortes exploram essa diferença. A ideia comum é conservar todos os planos inteiros válidos enquanto se excluem soluções fracionárias ou ramos que não podem melhorar o melhor inteiro conhecido.

## Variáveis binárias e modelos

Uma variável $x_i\in\{0,1\}$ representa uma decisão sim/não. A mochila 0-1 fica

$$
\max\sum_i v_ix_i,\qquad \sum_i w_ix_i\le W,\qquad x_i\in\{0,1\}.
$$

Numa atribuição de tarefas, $x_{ij}=1$ significa atribuir a tarefa $j$ à pessoa $i$. Para uma atribuição por tarefa, usa $\sum_i x_{ij}=1$; para no máximo $b_i$ tarefas por pessoa, $\sum_j x_{ij}\le b_i$. Compatibilidades podem excluir variáveis ou impor $x_{ij}=0$. Não dupliques a mesma tarefa na contagem por esquecer uma igualdade.

Um custo fixo de abrir uma instalação precisa de uma variável binária $y_i$. Uma restrição $\sum_j x_{ij}\le M_i y_i$ permite atribuições apenas quando está aberta. $M_i$ deve ser um limite válido e tão apertado quanto o modelo permita. Um valor demasiado pequeno elimina soluções; um valor desnecessariamente grande enfraquece a relaxação e pode criar problemas numéricos.

## Relaxação linear

Retirar a integridade alarga o conjunto de soluções. Para maximização, o ótimo LP é um **limite superior** do ótimo inteiro; para minimização, é um **limite inferior**. Se uma solução ótima da relaxação já for inteira em todas as variáveis exigidas, também é ótima no ILP, porque nenhuma solução inteira pode superá-la.

Considera

$$
\max x+y,\qquad 2x+y\le4,\quad x+2y\le4,\quad x,y\ge0\text{ inteiros}.
$$

A relaxação tem ótimo $(4/3,4/3)$ e valor $8/3$. Os pontos inteiros $(2,0)$, $(1,1)$ e $(0,2)$ têm valor 2; nenhuma solução inteira atinge 3, pois somar as restrições dá $3(x+y)\le8$. Como $x+y$ é inteiro, fica $x+y\le2$.

## Arredondar não resolve o ILP

Arredondar cada coordenada pode violar uma desigualdade, uma igualdade ou uma exigência mínima. No modelo $x+y\ge1$, $x-y=0$, $x,y\ge0$ inteiros, minimizar $x+y$ tem relaxação ótima $(1/2,1/2)$, valor 1. Arredondar ambos para baixo dá $(0,0)$, que viola o mínimo; arredondar um para cima e outro para baixo viola a igualdade. A solução inteira ótima é $(1,1)$, valor 2.

Mesmo um arredondamento admissível não é automaticamente ótimo, porque o valor LP sozinho não identifica o ponto inteiro que atinge o melhor valor possível.

## Branch and bound com relaxações

Assumimos que as variáveis têm limites finitos, para que a árvore seja finita e cada relaxação admissível tenha um ótimo finito. Uma relaxação ilimitada exige análise própria; não é uma solução fracionária em que possamos aplicar diretamente estes passos.

Em cada nó, resolve a relaxação LP com as restrições herdadas. Num problema de maximização:

1.  Se a relaxação é inviável, poda o nó.
2.  Se o seu limite superior não supera o incumbente inteiro, poda o nó quando só precisas de um ótimo.
3.  Se a solução é inteira, atualiza o incumbente e fecha o nó.
4.  Caso contrário, escolhe uma variável inteira $x_j$ com valor fracionário $a$ e cria os ramos $x_j\le\lfloor a\rfloor$ e $x_j\ge\lceil a\rceil$.

Todos os valores inteiros de $x_j$ pertencem a um desses ramos. Não perdemos uma solução inteira e excluímos o ponto fracionário atual. Repetir a divisão em cada ramo mantém a cobertura do espaço de soluções.

### Seguir o exemplo

Na raiz do exemplo, $(x,y)=(4/3,4/3)$ e limite $8/3$. Ramifica em $x\le1$ e $x\ge2$.

No ramo $x\ge2$, a restrição $2x+y\le4$ e $y\ge0$ forçam $x=2,y=0$. É inteiro, valor 2, e passa a incumbente.

No ramo $x\le1$, a relaxação pode chegar a $(1,3/2)$, valor $5/2$. Esse limite ainda é maior que 2, portanto não basta para podar. Ramifica em $y\le1$ e $y\ge2$:

*   Com $y\le1$, o ótimo é $(1,1)$, valor 2.
*   Com $y\ge2$, $x+2y\le4$ força $(0,2)$, valor 2.

A árvore regista a restrição acrescentada em cada ramo. Seguimos primeiro $x\ge2$ para obter um incumbente. Para mostrar os restantes ótimos, conservamos os ramos que empatam com ele.

![Raiz com limite 8/3. Ramo x maior ou igual a 2 dá (2,0), valor 2. Ramo x menor ou igual a 1 tem limite 5/2 e divide em y menor ou igual a 1, dando (1,1), e y maior ou igual a 2, dando (0,2). As três folhas inteiras têm valor 2.](https://resumos.rgo.pt/cadeiras/da/programacao-inteira/figura-1.svg)

Os três ramos inteiros atingem valor 2. Para devolver um único ótimo, bastaria fechar os ramos sem possibilidade de melhorar o incumbente; para devolver todos, precisamos de conservar os empates. Isso é necessário, mas não suficiente: uma relaxação que devolve uma solução inteira pode ter outros ótimos no mesmo nó. Fechá-lo ao encontrar a primeira solução serve para obter um ótimo; a enumeração precisa de continuar a procurar outras soluções de igual valor.

Podemos usar também que o objetivo tem valor inteiro: um limite $8/3$ permite o limite mais apertado $\lfloor8/3\rfloor=2$. Com um incumbente de 2, a raiz já seria podável. Este arredondamento do **limite** é válido porque o objetivo assume valores inteiros em todas as soluções inteiras; não é arredondar uma solução fracionária.

A ordem DFS, BFS ou melhor-limite afeta tempo e memória. DFS segue um ramo; BFS processa primeiro os nós menos profundos; melhor-limite escolhe o nó com melhor limite otimista. Encontrar cedo uma boa solução inteira permite descartar outros nós já gerados, usando os seus limites. Não confundas gerar um filho com resolver a sua relaxação: um enunciado ou uma implementação deve dizer quando esse cálculo acontece. O pior caso continua exponencial. Um bom incumbente e limites apertados reduzem a árvore, mas não transformam o problema geral em LP.

## Cortes válidos

Um corte acrescenta uma desigualdade satisfeita por todos os pontos inteiros admissíveis e violada pela solução fracionária atual. Reduz a relaxação sem retirar nenhuma solução inteira.

No exemplo, somar as restrições e usar a integridade de $x+y$ dá o corte $x+y\le2$. O ponto $(4/3,4/3)$ é eliminado; os três ótimos inteiros permanecem. Este corte prova diretamente o valor ótimo quando combinado com uma solução de valor 2.

![Região LP com vértices (0,0), (2,0), (4/3,4/3) e (0,2). O corte x+y≤2 retira o triângulo hachurado que contém o ótimo fracionário (4/3,4/3). Os seis pontos inteiros admissíveis permanecem, incluindo (2,0), (1,1) e (0,2) sobre a linha do corte.](https://resumos.rgo.pt/cadeiras/da/programacao-inteira/figura-2.svg)

A zona hachurada pertence à relaxação original, mas fica acima de $x+y=2$. Os pontos preenchidos mostram todos os inteiros admissíveis: nenhum fica nessa zona.

Não basta desenhar uma linha que afaste o ponto atual. É necessário provar que a linha conserva **todos** os inteiros admissíveis, incluindo os que ainda não vimos.

### Corte fracionário de Gomory

Numa formulação puramente inteira com variáveis não negativas, uma linha da base pode escrever-se

$$
x_B+\sum_j a_jx_j=b,
$$

com $x_B$ e $x_j$ inteiros. Se $b$ é fracionário, usa a parte fracionária $\{r\}=r-\lfloor r\rfloor$ e acrescenta

$$
\sum_j\{a_j\}x_j\ge\{b\}.
$$

A justificação vem de $x_B+\sum_j\lfloor a_j\rfloor x_j$ ser inteiro. Como $x_j\ge0$ e $\lfloor a_j\rfloor\le a_j$, esse inteiro é no máximo $b$, logo no máximo $\lfloor b\rfloor$. Subtrair da equação dá o corte.

Por exemplo, $x_B+\frac12x_1+\frac13x_2=\frac73$ dá $\frac12x_1+\frac13x_2\ge\frac13$. Na solução básica fracionária atual, as não básicas $x_1=x_2=0$ violam o corte. Qualquer solução inteira da equação respeita-o. A parte fracionária de $-1/3$ é $2/3$, não $-1/3$; usa o chão matemático, não truncar para zero.

Esta fórmula não se aplica sem alterações a uma linha com variáveis contínuas. ILP misto exige cortes adequados à mistura de domínios. Métodos modernos combinam ramificação e cortes, mas cada corte continua a precisar da mesma condição de validade.

## Integridade e fluxo

Alguns modelos LP têm ótimos inteiros sem precisarem de procurar por ramificação. Em redes de fluxo com capacidades inteiras, os aumentos inteiros preservam integridade e atingem um ótimo inteiro. A estrutura dessas restrições permite métodos especializados polinomiais.

Não generalizes: uma matriz com coeficientes inteiros pode ter ótimo fracionário, como o exemplo $2x+y\le4$, $x+2y\le4$. Para usar integridade como propriedade do LP, precisamos de um resultado sobre a estrutura do modelo, não apenas sobre o aspeto dos coeficientes.

## Relação com NP-completude

Podemos representar uma cláusula $\ell_1\lor\ell_2\lor\ell_3$ por $L_1+L_2+L_3\ge1$, usando uma variável binária $x$ para literal positivo e $1-x$ para a sua negação. A atribuição satisfaz a fórmula se e só se cumpre todas essas desigualdades.

Por exemplo, $(x\lor\neg y\lor z)$ dá $x+(1-y)+z\ge1$. A transformação usa tamanho polinomial e mostra que viabilidade inteira já pode representar satisfazibilidade. Isto explica a dificuldade geral do ILP, apesar de as restrições serem lineares.

## Exercícios

Apertar a relaxação por integridade

x e y são inteiros não negativos e cumprem 3x+2y≤11 e 2x+3y≤11. Deriva um corte para x+y e encontra o máximo inteiro dessa soma.

Pista

Soma as duas restrições e usa que x+y é inteiro.

Solução

O corte é x+y≤4, válido para todos os inteiros admissíveis porque x+y é inteiro e não pode ficar entre 4 e 4,4. O ponto (2,2) cumpre as restrições, pois ambas dão 10≤11, e atinge soma 4. Portanto o ótimo inteiro é 4. A relaxação pode ter (2,2;2,2), soma 4,4, que viola o corte e é eliminada.

Erros frequentes

Arredondar os coeficientes de uma restrição sem uma prova pode retirar pontos válidos. Aqui arredondámos o limite de uma quantidade que sabemos inteira.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/programacao-inteira/#cortes-v%C3%A1lidos)

Dividir sem perder inteiros

Num nó de maximização, a relaxação dá x=2,7 e objetivo 18,6. x tem de ser inteiro e o objetivo também tem de ser inteiro. O incumbente é 18. Que ramos corresponderiam a x e é necessário explorá-los para obter um ótimo?

Pista

Os inteiros não pertencem ao intervalo aberto entre 2 e 3.

Mais uma pista

Os ramos são x≤2 e x≥3. O objetivo de qualquer continuação inteira é no máximo floor(18,6).

Solução

A ramificação válida seria x≤2 ou x≥3, conservando todos os valores inteiros. Porém o limite superior inteiro do objetivo é 18. Como já existe uma solução inteira de valor 18, o nó pode ser podado sem explorar esses ramos para devolver um ótimo. Para enumerar todos os ótimos, o empate não permite podar. Se o objetivo não tivesse valores inteiros, não poderíamos apertar 18,6 para 18.

Confere a tua resposta:

*   Dei os ramos x≤2 e x≥3.
*   Usei a integridade do objetivo para limite 18.
*   Expliquei a poda com incumbente 18 e o caso de todos os ótimos.

Erros frequentes

Criar x≤2,7 e x≥2,7 não exclui a solução fracionária na relaxação dos filhos. Arredondar a solução x não substitui a ramificação nem prova viabilidade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/programacao-inteira/#branch-and-bound-com-relaxa%C3%A7%C3%B5es)

Encontrar o incumbente antes de expandir

Numa maximização inteira, o objetivo assume valores inteiros e basta devolver um ótimo. A relaxação da raiz é fracionária, com limite 12, e gera A e B, por esta ordem. A é fracionário com limite 10,5 e gera A1 e A2, ambos inteiros, de valores 8 e 10. B já é inteiro e vale 11. Não há incumbente inicial. Compara DFS, começando por A, com BFS. Um nó só é resolvido quando sai da pilha ou fila; se o seu limite já é conhecido, pode ser descartado sem resolver de novo. Indica a ordem dos nós processados e os que deixam de precisar de exploração.

Solução

DFS processa raiz,A,A1,A2,B. A1 fornece incumbente 8; A2 melhora-o para 10. Depois B melhora-o para 11. As folhas inteiras não geram filhos. O valor final é 11.

BFS processa raiz,A,B. Depois de A, a fila contém B,A1,A2. B fornece incumbente 11 antes de chegar aos filhos de A. Os limites conhecidos de A1 e A2, respetivamente 8 e 10, já não o superam, pelo que ambos são descartados. São nós gerados, mas não precisam de voltar a ser processados. Também o limite 10,5 de A, apertado para 10 pelo objetivo inteiro, certifica que toda a sua subárvore não pode melhorar 11.

A ordem pode alterar o trabalho porque altera quando surge uma boa solução completa. Não altera a validade de um limite nem o ótimo. Em ambos os percursos, a solução B atinge 11 e os restantes ramos não o excedem.

Confere a tua resposta:

*   Rastreei DFS: raiz,A,A1,A2,B.
*   Rastreei BFS: raiz,A,B.
*   Podei A1 e A2 em BFS pelo incumbente 11 e distingui gerar de processar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/programacao-inteira/#branch-and-bound-com-relaxa%C3%A7%C3%B5es)