Programação Inteira Mista

Visão geral

Programação Inteira Mista (Mixed-Integer Programming, MIP) é uma estrutura de otimização matemática para problemas que envolvem tanto:

  • Variáveis de decisão contínuas (continuous decision variables) (por exemplo, quantidades de produção, fluxos, tempos)
  • Variáveis de decisão inteiras (integer decision variables) (por exemplo, número de máquinas a usar) e, especialmente, variáveis binárias (binary variables) (por exemplo, decisões sim/não como “abrir esta instalação”)

Um MIP genérico tem a forma:

[ \min_{x, y}; f(x, y) \quad \text{s.t.}\quad g(x, y)\le 0,; x\in\mathbb{R}^n,; y\in\mathbb{Z}^m ]

onde (x) são variáveis contínuas e (y) são variáveis inteiras.

MIPs são um pilar da pesquisa operacional (operations research) e são amplamente usados para programação (scheduling), roteirização (routing) e alocação de recursos (resource allocation), especialmente em manufatura e cadeia de suprimentos (supply chain). Eles também são cada vez mais relevantes em IA (AI), onde decisões discretas (seleção, lógica, combinatória) surgem junto de quantidades contínuas.

Este artigo se baseia em ideias de Programação Linear, Otimização com Restrições e Otimização Convexa.

Subclasses comuns de MIP (MILP e MIQP)

Na prática, duas famílias cobrem uma grande fração dos casos de uso do mundo real:

Programação Linear Inteira Mista (Mixed-Integer Linear Programming, MILP)

Um MILP tem uma função objetivo linear e restrições lineares:

[ \min; c^\top x \quad \text{s.t.}\quad Ax \le b,; x_i\in \mathbb{R},; x_j\in\mathbb{Z} ]

MILPs modelam muitas decisões do tipo “se fizermos isto, então aquilo” por meio de variáveis binárias.

Programação Quadrática Inteira Mista (Mixed-Integer Quadratic Programming, MIQP)

Um MIQP inclui uma função objetivo e/ou restrições quadráticas, frequentemente convexas:

[ \min; \tfrac{1}{2}x^\top Qx + c^\top x \quad \text{s.t.}\quad Ax \le b,; x_j\in\mathbb{Z} ]

MIQP é comum em otimização de portfólio, ajuste por mínimos quadrados com escolhas discretas e alguns problemas de controle. Se a parte quadrática for convexa ((Q\succeq 0)), as relaxações são mais fortes e os solucionadores (solvers) tendem a ser mais confiáveis do que em casos não convexos.

Você também pode ver MINLP (Programação Não Linear Inteira Mista, Mixed-Integer Nonlinear Programming), que permite não linearidades gerais, mas costuma ser mais difícil e menos robusta do que MILP/MIQP. Muitos profissionais preferem reformular não linearidades em MILP/MIQP quando possível (por exemplo, via aproximações lineares por partes).

Por que variáveis inteiras importam

Muitas decisões são inerentemente discretas:

  • Atribuir cada tarefa a exatamente uma máquina
  • Escolher se deve abrir um depósito
  • Selecionar k atributos de um conjunto (seleção de atributos)
  • Roteirizar um veículo por cidades sem sub-rotas
  • Impor condições lógicas (“se construirmos a planta A, devemos construir a planta B”)

A otimização contínua, sozinha, não consegue expressar diretamente essas restrições “combinatórias”. Adicionar variáveis inteiras torna o modelo muito mais expressivo — mas tipicamente também NP-difícil (NP-hard) no pior caso.

MIP vs. LP: relaxação e integralidade

Um conceito central em MIP é a relaxação de PL (LP relaxation):

  • Pegue um MILP
  • Substitua restrições inteiras como (y \in {0,1}) por (y \in [0,1])
  • Resolva o problema resultante de Programação Linear

A relaxação fornece:

  • Um limitante inferior para minimização (ou superior para maximização)
  • Intuição sobre a qualidade da formulação por meio da lacuna de integralidade (integrality gap) (o quão distante o ótimo relaxado está da melhor solução inteira)

Uma boa modelagem de MIP frequentemente significa projetar uma formulação cuja relaxação seja apertada (lacuna pequena), porque isso, em geral, torna o problema dramaticamente mais fácil de resolver.

Padrões centrais de modelagem

A maioria dos MIPs práticos é construída a partir de um pequeno conjunto de padrões reutilizáveis.

Decisões binárias “liga/desliga” (Big‑M e restrições indicadoras)

Suponha que uma linha de produção possa estar ativa ou inativa:

  • (y \in {0,1}): linha ligada/desligada
  • (x \ge 0): quantidade produzida

Uma restrição linear comum de ligação é:

[ 0 \le x \le M y ]

Se (y=0), então (x=0). Se (y=1), então (x\le M).

Armadilhas do Big‑M (Big‑M):

  • Se (M) for grande demais, a relaxação de PL fica fraca e numericamente instável.
  • Escolha o menor (M) válido usando limites conhecidos.

Restrições indicadoras (indicator constraints) (suportadas por solucionadores modernos) evitam o Big‑M manual em muitos casos:

  • “Se (y=0) então (x=0)”
  • “Se (y=1) então (Ax \le b)”

Os solucionadores frequentemente traduzem isso automaticamente para formas internas apertadas.

Restrições de atribuição

Padrão clássico de “escolher exatamente uma opção”:

  • (y_{ij} \in {0,1}): atribuir a tarefa (i) à máquina (j)

[ \sum_{j} y_{ij} = 1 \quad \forall i ]

Adicionar capacidades:

[ \sum_{i} p_i y_{ij} \le \text{cap}_j \quad \forall j ]

Esse padrão aparece em programação, alocação no estilo de clusterização e emparelhamento bipartido.

Relações lógicas (implicações, AND/OR)

Com variáveis binárias, é possível codificar lógica de forma linear.

Implicação: “Se (a=1) então (b=1)” [ a \le b ]

AND: (c = a \land b) pode ser codificado com: [ c \le a,; c \le b,; c \ge a + b - 1 ]

Esses padrões permitem que MILPs representem restrições do tipo regras, comuns em planejamento e operações.

Cardinalidade (“escolher no máximo k”)

Selecionar até (k) itens:

[ \sum_i y_i \le k,\quad y_i\in{0,1} ]

Isso é amplamente usado em alocação de recursos e seleção de atributos em ML.

Aproximações lineares por partes

Para modelar custos não lineares (por exemplo, custos convexos de produção) usando MILP, aproxime com segmentos lineares por partes (piecewise-linear).

Abordagens comuns:

  • Método de combinação convexa (lambda) (convex combination (lambda) method)
  • Variáveis SOS2 (SOS2 variables) (conjuntos ordenados especiais, tipo 2), suportadas por muitos solucionadores

Isso é uma ponte prática entre a realidade não linear e a solucionabilidade de MILP.

Como funcionam os solucionadores de MIP (visão de alto nível)

Como as restrições de integralidade criam complexidade combinatória, MIPs tipicamente são resolvidos por ramificação e delimitação (branch-and-bound) com aprimoramentos.

Intuição de ramificação e delimitação

  1. Resolva a relaxação (PL ou PQ convexa).
  2. Se a solução for inteira, terminou.
  3. Caso contrário, escolha uma variável inteira fracionária e ramifique:
    • Adicione a restrição (y \le 0) em um ramo e (y \ge 1) no outro (para (y) binária).
  4. Use valores da relaxação como limitantes para podar ramos que não podem superar a melhor solução viável conhecida (a incumbente (incumbent)).

Pseudo-estrutura:

incumbent = +infinity
queue = {root problem}

while queue not empty:
    P = pop(queue)
    solve relaxation of P -> (bound, x*)
    if bound >= incumbent: continue  # prune
    if x* integral:
        incumbent = min(incumbent, objective(x*))
        continue
    choose fractional var y_k in x*
    queue.add(P with y_k = 0)
    queue.add(P with y_k = 1)

return incumbent

Planos de corte e ramificação e corte

Solucionadores modernos adicionam planos de corte (cutting planes): restrições válidas extras que eliminam soluções fracionárias da relaxação mantendo todas as soluções inteiras viáveis.

O paradigma dominante é ramificação e corte (branch-and-cut):

  • Busca por ramificação e delimitação
  • Intercalada com geração de cortes (cortes de Gomory, cover cuts, clique cuts, cortes MIR, cortes específicos do problema etc.)

Resultados práticos: lacunas de otimalidade e limites de tempo

Solucionadores de MIP geralmente reportam:

  • Melhor objetivo viável (z_\text{inc})
  • Melhor limitante (z_\text{bound})
  • Lacuna de otimalidade (optimality gap) (\frac{|z_\text{inc}-z_\text{bound}|}{|z_\text{inc}|})

Em operações reais, é comum aceitar soluções com lacunas pequenas (por exemplo, 0,1%–1%) sob limites de tempo.

Exemplo prático 1: Localização de instalações capacitada (cadeia de suprimentos)

Um problema canônico de cadeia de suprimentos: decidir quais depósitos abrir e como enviar para clientes.

Conjuntos

  • Instalações (i \in I)
  • Clientes (j \in J)

Parâmetros

  • Custo fixo de abertura (f_i)
  • Capacidade (u_i)
  • Demanda (d_j)
  • Custo de transporte (c_{ij})

Variáveis

  • (y_i \in {0,1}): abrir a instalação (i)
  • (x_{ij} \ge 0): quantidade enviada de (i) para (j)

Formulação MILP [ \min \sum_i f_i y_i + \sum_{i,j} c_{ij} x_{ij} ] s.t. [ \sum_i x_{ij} = d_j \quad \forall j \quad \text{(atender à demanda)} ] [ \sum_j x_{ij} \le u_i y_i \quad \forall i \quad \text{(capacidade apenas se estiver aberta)} ] [ x_{ij}\ge 0,; y_i\in{0,1} ]

Isso mostra a essência de MIP em cadeias de suprimentos: fluxos contínuos (x) + decisões discretas de projeto (y).

Exemplo prático 2: Escala de turnos (planejamento da força de trabalho)

Escalonar trabalhadores para cobrir níveis de pessoal requeridos.

Parâmetros

  • Pessoal requerido (r_t) para cada período de tempo (t)
  • Custo (c_s) de alocar um trabalhador ao padrão de turno (s)
  • Matriz de cobertura (a_{st}\in{0,1}): o turno (s) cobre o tempo (t)

Variáveis

  • (x_s \in \mathbb{Z}_{\ge 0}): número de trabalhadores atribuídos ao turno (s)

MILP [ \min \sum_s c_s x_s ] s.t. [ \sum_s a_{st} x_s \ge r_t \quad \forall t ] [ x_s \in \mathbb{Z}_{\ge 0} ]

Embora isso pareça simples, escala para escalas de pessoal grandes e realistas em hospitais, centrais de atendimento e armazéns. Restrições adicionais (máximo de dias consecutivos, equidade, preferências) acrescentam mais estrutura — muitas vezes ainda compatível com MILP.

Exemplo prático 3: Roteirização (estilo TSP/VRP)

Roteirização é um domínio clássico de MIP. Para um Problema do Caixeiro Viajante (Traveling Salesperson Problem, TSP) simplificado:

  • (y_{ij}\in{0,1}): viajar diretamente da cidade (i) para a cidade (j)

Restrições de grau garantem uma entrada/saída por cidade: [ \sum_{j\ne i} y_{ij} = 1,\quad \sum_{j\ne i} y_{ji}=1 \quad \forall i ]

Mas isso permite sub-rotas (subtours) (múltiplos ciclos desconectados). Um MILP comum adiciona restrições de eliminação de sub-rotas (uma variante são as restrições MTZ (MTZ constraints) com variáveis de ordenação). Problemas industriais de roteamento de veículos usam cortes e formulações mais fortes, mas a ideia-chave permanece: escolhas binárias de rotas + restrições lineares.

MIPs de roteirização são amplamente usados em:

  • Entrega de última milha
  • Rotas de separação (picking) em armazéns
  • Planejamento de frota sob janelas de tempo e capacidades

Por que MIPs são tão amplamente usados em manufatura e cadeia de suprimentos

MIPs atingem um “ponto ideal” entre expressividade e solucionabilidade:

  • Expressividade: variáveis binárias/inteiras modelam naturalmente setups, escolhas, regras lógicas, tamanhos mínimos de lote e atribuições.
  • Maturidade dos solucionadores: solucionadores comerciais e de código aberto têm décadas de engenharia algorítmica (pré-processamento (presolve), cortes, heurísticas, paralelismo).
  • Auditabilidade: restrições e decisões são explícitas, tornando resultados mais fáceis de explicar do que muitos modelos de caixa-preta.
  • Análise de cenários: altere custos, capacidades ou demandas e reotimize.

Casos de uso industriais comuns de MIP:

  • Planejamento de produção / dimensionamento de lotes (lot sizing): decisões de setup (binárias) + quantidades (contínuas)
  • Programação job-shop / flow-shop: restrições de atribuição + sequenciamento
  • Projeto de rede: quais rotas, depósitos ou fornecedores ativar
  • Otimização de estoques: pontos de reposição com custos fixos de pedido (frequentemente MIP ou variantes estocásticas)
  • Alocação de recursos: orçamentos, planejamento de headcount, seleção de projetos (tipo mochila)

MIP em IA e ML (onde aparece)

Embora o treinamento em ML frequentemente dependa de otimização contínua (ver Descida do Gradiente e Otimização Estocástica), MIP é útil quando o aprendizado ou a inferência envolve estrutura discreta ou restrições rígidas.

Exemplos:

  • Árvores de decisão ótimas (optimal decision trees): algumas formulações treinam pequenas árvores de decisão via MILP para otimizar erro de classificação com restrições de interpretabilidade (profundidade, esparsidade).
  • Seleção de atributos (feature selection): selecionar (k) atributos com uma restrição de cardinalidade enquanto ajusta um modelo linear (MILP/MIQP).
  • Verificação de redes neurais (neural network verification): ativações lineares por partes (por exemplo, ReLU) podem ser codificadas com restrições MILP para provar propriedades de segurança para redes pequenas/médias.
  • Predição estruturada e inferência com restrições (structured prediction and constrained inference): impor regras globais (por exemplo, restrições de rotulagem) durante a predição.

Nesses cenários, MIP complementa ML: ML pode prever custos/demandas; MIP toma a decisão final sob restrições.

Dicas práticas para construir MIPs solucionáveis

1) Limites apertados e Big‑M cuidadoso

  • Sempre forneça limites realistas para as variáveis.
  • Derive o menor (M) válido a partir dos limites do domínio.

2) Prefira formulações mais fortes

Formulações diferentes para a mesma lógica podem variar enormemente em dificuldade. Formulações mais fortes tipicamente:

  • Reduzem lacunas de integralidade
  • Melhoram a poda do solucionador

3) Reduza simetria

Simetria (máquinas intercambiáveis, instalações idênticas) pode causar uma busca massiva. Adicione restrições de quebra de simetria quando possível.

4) Escalone dados para estabilidade numérica

Mantenha coeficientes em uma faixa razoável (evite misturar (10^{-6}) e (10^{9}) no mesmo modelo).

5) Use recursos do solucionador

Solucionadores modernos oferecem:

  • Restrições indicadoras
  • SOS1/SOS2
  • Inicializações quentes (warm starts) (fornecer uma solução viável)
  • Parâmetros de ajuste (cortes, heurísticas, ramificação)

6) Saiba quando decompor

Problemas grandes podem se beneficiar de técnicas de decomposição:

  • Decomposição de Benders (Benders decomposition) (separar decisões de projeto de fluxos operacionais)
  • Geração de colunas (column generation) (conjuntos enormes de atribuição, por exemplo, escala de tripulações)

Isso pode ser essencial em escala industrial.

Código ilustrativo mínimo (estilo MILP em Python)

Abaixo está um pequeno esboço no estilo de localização de instalações usando um padrão típico de API de modelagem (a sintaxe exata varia: Pyomo, PuLP, OR-Tools, JuMP em Julia etc.):

# Sketch only (not tied to a specific library)

I = ["A", "B", "C"]      # facilities
J = ["u1", "u2"]         # customers

f = {"A": 50, "B": 60, "C": 55}                 # fixed costs
u = {"A": 100, "B": 80, "C": 90}                # capacities
d = {"u1": 70, "u2": 60}                        # demands
c = {("A","u1"): 1, ("A","u2"): 3,
     ("B","u1"): 2, ("B","u2"): 1,
     ("C","u1"): 2, ("C","u2"): 2}

# Variables:
# y[i] in {0,1} open facility
# x[i,j] >= 0 shipped units
# Objective: min sum_i f[i]*y[i] + sum_{i,j} c[i,j]*x[i,j]
# Constraints:
# 1) demand: sum_i x[i,j] == d[j]
# 2) capacity: sum_j x[i,j] <= u[i]*y[i]

O ponto importante não é a sintaxe, e sim a estrutura de modelagem: decisões binárias de abrir/fechar acopladas a fluxos contínuos.

Quando MIP é (e não é) uma boa escolha

MIP é uma escolha forte quando:

  • As decisões são discretas e devem respeitar restrições rígidas
  • Você precisa de um plano auditável, ótimo (ou quase ótimo)
  • A estrutura do problema é linear ou pode ser bem linearizada

MIP pode ser uma escolha ruim quando:

  • O modelo é altamente não linear/não convexo e difícil de aproximar
  • Você precisa de decisões extremamente rápidas em escala massiva sem pré-processamento
  • Heurísticas aproximadas são aceitáveis e a exatidão não compensa o custo computacional

Na prática, muitas organizações usam um fluxo de trabalho híbrido:

  • ML prevê entradas (demanda, tempo de viagem, risco)
  • MIP otimiza decisões dadas essas previsões e restrições

Resumo

A Programação Inteira Mista estende a otimização linear e convexa ao permitir variáveis inteiras e binárias, tornando-se uma estrutura poderosa para modelar sistemas reais de tomada de decisão. Com formulações padrão como MILP e MIQP, MIPs podem codificar atribuições, lógica, custos lineares por partes e restrições liga/desliga — exatamente os tipos de estruturas encontrados em programação, roteirização e alocação de recursos em manufatura e cadeia de suprimentos.

Apesar da complexidade NP-difícil no pior caso, solucionadores modernos de ramificação e corte e boas formulações tornam muitas instâncias grandes do mundo real solucionáveis com otimalidade comprovável (ou lacunas de otimalidade pequenas), motivo pelo qual MIP continua sendo uma ferramenta central em otimização aplicada e um complemento cada vez mais importante para sistemas de aprendizado de máquina.