Programação linear inteira

Relaxação e ramificação

A relaxação LP alarga o conjunto admissível, por isso dá um teto em maximização e um piso em minimização. Arredondar a solução fracionária pode sair do poliedro ou piorar o objetivo; o recurso de 2026 mostra (0,0) como arredondamento natural mas inviável.

Ramifica a variável fracionária de valor $a$ em $x\le\lfloor a\rfloor$ e $x\ge\lceil a\rceil$. Poda o ramo cujo melhor possível não supera o incumbente. Para listar todos os ótimos, conserva os empates.

Cortes

Cada corte conserva todos os pontos inteiros e exclui a solução fracionária atual. Gomory aplica-se a uma linha do tableau cuja variável básica é inteira, quando todas as variáveis dessa linha são inteiras e não negativas:

$$x_B+\sum a_jx_j=b\;\Rightarrow\;\sum\{a_j\}x_j\ge\{b\}.$$

Com $\{r\}=r-\lfloor r\rfloor$. Aplica em tableau ótimo fracionário e repete.

Relaxação e cortes.