Programação inteira

A programação inteira (PI) otimiza um objetivo linear sobre variáveis restritas a assumir valores inteiros ou binários. A exigência de integralidade quebra a convexidade que torna a PL tratável: o conjunto viável é uma coleção discreta de pontos, e o método Simplex de PL não se aplica mais diretamente. A maioria dos problemas combinatórios práticos, incluindo escalonamento, roteamento, alocação de recursos, são programas inteiros.

Formulação

Um Programa Linear Inteiro Misto (MILP) tem a forma:

em que \(x\) são variáveis contínuas e \(y\) são variáveis inteiras. Quando todas as variáveis são inteiras: Programa Linear Inteiro (ILP). Quando todas são binárias (\(y \in \{0,1\}^p\)): Programa Inteiro Binário (BIP).

Variáveis binárias são particularmente expressivas: elas modelam decisões sim/não, condições lógicas, e estruturas combinatórias. Praticamente qualquer problema de otimização combinatória pode ser formulado como um BIP.

Formulações clássicas

Mochila: \(n\) itens com valores \(v_i\) e pesos \(w_i\). Maximizar o valor total sujeito à capacidade de peso \(W\):

\[\max \sum_i v_i x_i \quad \text{s.a.} \quad \sum_i w_i x_i \leq W, \quad x_i \in \{0,1\}\]

Atribuição: atribuir \(n\) trabalhadores a \(n\) empregos (um a um). Minimizar o custo total \(c_{ij}\):

\[\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.a.} \quad \sum_j x_{ij} = 1 \;\forall i, \quad \sum_i x_{ij} = 1 \;\forall j, \quad x_{ij} \in \{0,1\}\]

Localização de instalações com custo fixo: decidir quais instalações abrir (\(y_j \in \{0,1\}\)) e quanto transportar de cada uma (\(x_{ij} \geq 0\)):

\[\min \sum_j f_j y_j + \sum_{i,j} c_{ij} x_{ij} \quad \text{s.a.} \quad \sum_j x_{ij} \geq d_i \;\forall i, \quad x_{ij} \leq M y_j \;\forall i,j\]

Por que a integralidade torna a otimização difícil

Adicionar restrições de integralidade a uma PL muda o problema fundamentalmente. A região viável da PL é um politopo convexo; a região viável da PI é o conjunto discreto de pontos inteiros dentro desse politopo. Duas consequências-chave:

Sem gradiente para seguir: o objetivo é linear e o conjunto viável é discreto. Métodos baseados em gradiente não se aplicam. Arredondar a solução da PL para o ponto inteiro mais próximo frequentemente dá uma solução inviável ou altamente subótima.

NP-dificuldade: a programação inteira é NP-difícil em geral. O problema da mochila, o caixeiro-viajante, o empacotamento (bin packing), e o escalonamento são todos problemas de PI NP-difíceis. Nenhum algoritmo de tempo polinomial é conhecido (e nenhum é esperado sob \(P \neq NP\)).

O ótimo da relaxação LP (losango laranja) é não inteiro em \((2,33, 2,33)\) com \(z=11,67\). O verdadeiro ótimo da PI (ponto vermelho) está em \((3,1)\) com \(z=11\). O ótimo LP fornece um limite superior para o objetivo da PI (para maximização).

A relaxação LP e os limites

A relaxação LP remove as restrições de integralidade e resolve a PL resultante. Para um problema de maximização:

\[z_\text{LP} \geq z_\text{PI}\]

A relaxação LP dá um limite superior para o objetivo da PI (limite inferior para minimização). O gap \(z_\text{LP} - z_\text{PI}\) mede o quanto as restrições de integralidade custam.

Se a solução da relaxação LP por acaso tiver valores inteiros, ela também é o ótimo da PI. Para estruturas especiais de problema (matrizes de restrição totalmente unimodulares, por exemplo, problemas de fluxo em rede, problemas de atribuição), a relaxação LP sempre dá uma solução inteira: nenhum branch and bound é necessário.

Branch and bound

Branch and bound é o algoritmo fundamental para resolver programas inteiros. Ele enumera implicitamente todas as soluções inteiras viáveis particionando o problema em subproblemas e usando relaxações LP para podar subproblemas que não podem conter a solução ótima.

Algoritmo:

1. Inicializar: resolva a relaxação LP. Se a solução é inteira, terminado. Caso contrário, o valor ótimo da LP é um limite superior \(\bar{z}\) (para maximização). Defina a melhor solução inteira encontrada até agora \(\underline{z} = -\infty\).

2. Ramificar: selecione uma variável fracionária \(x_j = \bar{x}_j\) (não inteira). Crie dois subproblemas filhos adicionando:

   • Ramo inferior: \(x_j \leq \lfloor \bar{x}_j \rfloor\)
   • Ramo superior: \(x_j \geq \lceil \bar{x}_j \rceil\)

3. Delimitar: resolva a relaxação LP de cada filho. Se o ótimo LP for:

   • Inviável: pode (nenhuma solução inteira viável neste ramo).
   • Pior do que \(\underline{z}\): pode (não pode melhorar a melhor solução conhecida).
   • Inteiro: atualize \(\underline{z}\) se for melhor do que o atual.
   • Fracionário e melhor do que \(\underline{z}\): adicione à lista de nós abertos.

4. Repita até que não restem nós abertos. A melhor solução inteira encontrada é ótima.

O algoritmo encontra a solução ótima \((x=2, y=3, z=12)\) resolvendo apenas 3 relaxações LP em vez de enumerar todos os pontos inteiros.

Planos de corte

Planos de corte são desigualdades lineares adicionais acrescentadas à relaxação LP para cortar soluções fracionárias sem remover nenhum ponto inteiro viável. Eles reforçam a relaxação LP, trazendo seu ótimo para mais perto do ótimo da PI.

Os planos de corte mais importantes:

Cortes de Gomory: derivados algebricamente do tableau da LP. Para uma variável básica fracionária \(x_j = \bar{x}_j\) com \(\bar{x}_j \notin \mathbb{Z}\), o corte de Gomory remove a solução LP fracionária mantendo viáveis todas as soluções inteiras.

Desigualdades de cobertura (para a mochila): se um subconjunto \(S\) de itens não cabe inteiramente na mochila (\(\sum_{i \in S} w_i > W\)), então no máximo \(|S|-1\) deles podem ser selecionados: \(\sum_{i \in S} x_i \leq |S|-1\).

Solvers de PI modernos (Gurobi, CPLEX) combinam branch and bound com planos de corte (branch and cut): cortes são gerados em cada nó da árvore de branch and bound para reforçar a relaxação LP local.

Aplicações

A programação inteira modela uma enorme variedade de problemas reais:

• Escalonamento de companhias aéreas: atribuição de aeronaves e tripulações a voos, respeitando requisitos de descanso e conexões de hub.
• Cadeia de suprimentos: localização de armazéns, roteamento de estoque, escalonamento de veículos.
• Telecomunicações: design de redes, atribuição de frequências.
• Finanças: seleção de carteira com custos de transação, restrições de cardinalidade.
• Saúde: escalonamento de enfermagem, planejamento de salas de cirurgia, distribuição de vacinas.

library(lpSolve)

# Knapsack: 5 items, values and weights
values  <- c(10, 6, 3, 7, 8)
weights <- c(5,  3, 2, 4, 5)
capacity <- 10

obj <- values
mat <- matrix(weights, nrow=1)
rhs <- capacity
dir <- "<="

# Binary IP (all.bin=TRUE)
sol <- lp("max", obj, mat, dir, rhs, all.bin=TRUE)
sol$solution  # which items to take
sol$objval    # optimal value

# Mixed integer with lpSolve
# int.vec specifies which variables must be integer
sol <- lp("max", obj, mat, dir, rhs, int.vec=1:5)

# For serious MIP solving: use highs package (faster)
library(highs)
highs_solve(L=obj, lower=rep(0,5), upper=rep(1,5),
            A=matrix(weights,1), lhs=-Inf, rhs=capacity,
            types=rep("I",5), maximum=TRUE)