Qual é a ideia básica do algoritmo de plano de corte em programação inteira?

Gera desigualdades válidas (cortes) a partir da relaxação linear para eliminar soluções fracionárias sem excluir soluções inteiras, repetindo até obter solução inteira.

O método começa resolvendo a relaxação linear; se a solução for fracionária, constrói‑se um corte — uma desigualdade linear que invalida a solução fracionária atual mas permanece verdadeira para toda solução inteira viável — adiciona‑se ao modelo e resolve‑se novamente até alcançar integralidade.

Exemplo:
Considere o PPI: maximizar \(z=5x_1+4x_2\) sujeito a \(3x_1+2x_2\le 7,\; x_1,x_2\ge0,\; x_1,x_2\in\mathbb{Z}\).
A relaxação LP tem solução ótima em \(x_1=0,\;x_2=3.5\) com \(z=14\) (fracionária).
Um corte óbvio é \(\;x_2\le 3\;\) (válido para todas as soluções inteiras, pois \(2x_2\le7\Rightarrow x_2\le3.5\) e, assim, \(x_2\le3\) para inteiros).
Ao acrescentar esse corte e resolver novamente, obtém‑se solução inteira \(x_1=1,\;x_2=2\) com \(z=13\), que é factível e elimina a solução fracionária anterior.