Questão 3: Gerando Cortes Lagrangianos
Para cada uma das relaxações propostas na questão 1, derive a forma algébrica do Plano Cortante Lagrangiano que se pode obter a partir da solução do Programa Dual Lagrangeano. Note que se a definição geral da Função Lagrangeana é
L(u)=\min \left\{\left(c^{\top}-u^{\top} A\right) x+b^{\top} u \mid x \in \Gamma\right\} .
Então a expressão do Corte Lagrangeano seria:
c^{\top} x+\bar{u}^{\top}(b-A x) \geq L(\bar{u})
Auf Wiedersehen, Senhores!!!

Passo 1

O que o enunciado pede:
  • Derivar a forma algébrica do Plano Cortante Lagrangiano obtido a partir da solução do Programa Dual Lagrangeano para cada uma das relaxações propostas na questão 1.
Informações fornecidas no enunciado:
  • A definição geral da função Lagrangeana:
L(u)=\min\left\{\left(c^{\top}-u^{\top}A\right)x+b^{\top}u \mid x\in\Gamma\right\}.
  • A expressão genérica do corte Lagrangeano:
c^{\top}x+\bar{u}^{\top}(b-Ax)\ge L(\bar{u}).
Informação que falta (impedimento para responder apenas com as relaxações específicas da “questão 1”):
  • O enunciado refere-se a “cada uma das relaxações propostas na questão 1”, porém essas relaxações específicas não foram enviadas. Sem saber quais restrições foram relaxadas, NÃO é possível escrever os cortes explicitamente para os casos particulares pedidos em Q1.
  • Portanto vou: (i) explicar didaticamente como derivar o corte em forma algébrica para o caso geral de relaxação de um subconjunto de restrições; (ii) dar as fórmulas explícitas em termos dos componentes da matriz e dos vetores (ou seja, um “template” que você aplica a cada relaxação específica de Q1 assim que souber quais linhas de A foram relaxadas). Se você quiser depois eu aplico esse template às relaxações concretas de Q1 — é só mandar elas.

Passo 2

Entendendo a estrutura geral (explicação didática, passo a passo, sem pular etapas).
  • Suponha que o problema original (por exemplo um MILP) seja
\min\{\,c^{\top}x\mid Ax\ge b,\;x\in\Gamma\,\},
onde:
  • x é o vetor de variáveis de decisão;
  • c é o vetor de custos;
  • A e b representam um conjunto de restrições “complicadas”;
  • \Gamma é o conjunto das demais restrições fáceis (por exemplo integridade, capacidade local, bounds, etc.) sobre as quais o subproblema será resolvido.
  • Na Lagrangiana usual partimos de uma partição em que relaxamos as restrições complicadoras Ax\ge b com multiplicadores u. Os multiplicadores \;u\; têm sinal conforme o tipo da restrição:
    • se a restrição for do tipo a_i^\top x\ge b_i então u_i\ge0;
    • se for a_i^\top x\le b_i então u_i\le0;
    • se for igualdade = então u_i é livre (sem sinal imposto).
  • A Lagrangeana associada a um vetor u é obtida movendo u^{\top}(b-Ax) para a função objetivo e minimizando sobre \Gamma. Por isso a fórmula
L(u)=\min_{x\in\Gamma}\left\{(c^{\top}-u^{\top}A)x + b^{\top}u\right\}.
  • O dual Lagrangiano busca \max_{u} L(u) com as restrições de sinal apropriadas em u. Seja \bar{u} uma solução dual (ou um candidato de bons multiplicadores) e seja x^(\bar u) um minimizador do subproblema \min_{x\in\Gamma}(c^{\top}-\bar u^{\top}A)x + b^{\top}\bar u. Então L(\bar u) é o valor obtido avaliando esse mínimo.

Passo 3

Derivação algébrica direta do corte Lagrangeano a partir da fórmula dada.
  • A forma genérica do corte é dada no enunciado:
c^{\top}x+\bar{u}^{\top}(b-Ax)\ge L(\bar{u}).
  • Expandindo o termo \bar{u}^{\top}(b-Ax) obtemos:
c^{\top}x+\bar{u}^{\top}b-\bar{u}^{\top}A x \ge L(\bar{u}).
  • Reagrupando os termos que multiplicam x obtemos uma inequação linear padrão em x:
\bigl(c^{\top}-\bar{u}^{\top}A\bigr)x \ge L(\bar{u})-\bar{u}^{\top}b.
  • Esta é a forma algébrica do plano cortante: um coeficiente linear para cada variável (o vetor de coeficientes é c-\!A^{\top}\bar u) e um lado direito escalar L(\bar u)-\bar u^{\top}b. Em notação mais componente a componente:
\sum_{j}\Bigl(c_{j}-\sum_{i}\bar{u}_{i}a_{ij}\Bigr)x_{j} \;\ge\; L(\bar{u})-\sum_{i}\bar{u}_{i}b_{i}.

Passo 4

Forma alternativa usando o minimizador do subproblema (interpretação útil na prática).
  • Seja x^{*} um minimizador de \min_{x\in\Gamma}(c^{\top}-\bar{u}^{\top}A)x + b^{\top}\bar{u}. Então, por definição,
L(\bar{u})=(c^{\top}-\bar{u}^{\top}A)x^{*}+b^{\top}\bar{u}.
  • Substituindo L(\bar{u}) na desigualdade original:
c^{\top}x+\bar{u}^{\top}b-\bar{u}^{\top}Ax \ge (c^{\top}-\bar{u}^{\top}A)x^{*}+b^{\top}\bar{u}.
  • Cancelando \bar{u}^{\top}b dos dois lados obtém-se a forma muito simples
\bigl(c^{\top}-\bar{u}^{\top}A\bigr)x \ge \bigl(c^{\top}-\bar{u}^{\top}A\bigr)x^{*},
ou, escrevendo como diferença,
\bigl(c^{\top}-\bar{u}^{\top}A\bigr)\bigl(x-x^{*}\bigr)\ge0.
  • Interpretação prática: o corte força que qualquer x viável na master respeite que o valor linear avaliado com o vetor de pesos c-\!A^{\top}\bar u não caia abaixo do valor atingido pelo minimizador x^{*}. Se x^{*} for uma solução relaxada que viola as restrições originais, frequentemente essa desigualdade é violada por x^{*} e então o corte é efetivo para separar x^{*}.

Passo 5

Forma expandida por restrição relaxada (template aplicável quando se conhece a lista de restrições relaxadas).
  • Se o conjunto de restrições relaxadas for R (índices i\in R), com cada restrição escrita como \sum_{j} a_{ij}x_{j}\ge b_{i}, então o corte pode ser escrito explicitamente como
\sum_{j} c_{j}x_{j} \;+\; \sum_{i\in R}\bar{u}_{i}\Bigl(b_{i}-\sum_{j}a_{ij}x_{j}\Bigr) \;\ge\; L(\bar{u}).
  • Reagrupando por x_{j}:
\sum_{j}\Bigl(c_{j}-\sum_{i\in R}\bar{u}_{i}a_{ij}\Bigr)x_{j} \;\ge\; L(\bar{u})-\sum_{i\in R}\bar{u}_{i}b_{i}.
  • Esse é o corte em forma totalmente componente a componente: coeficiente de x_j é c_j-\sum_{i\in R}\bar u_i a_{ij}, e o lado direito é L(\bar u)-\sum_{i\in R}\bar u_i b_i.

Passo 6

Exemplos concretos (aplique o template às relaxações de Q1 quando as tiveres)
  • Exemplo 1 — relaxando apenas uma restrição k: a_{k}^{\top}x\ge b_{k} com \bar u_{k}\ge0. O corte fica
c^{\top}x+\bar{u}_{k}\bigl(b_{k}-a_{k}^{\top}x\bigr)\ge L(\bar{u}),
ou equivalentemente
\bigl(c^{\top}-\bar{u}_{k}a_{k}^{\top}\bigr)x \ge L(\bar{u})-\bar{u}_{k}b_{k}.
  • Exemplo 2 — relaxando várias restrições do tipo capacidade/ligação (índices i\in R): já dado no passo 5 — basta substituir os a_{ij}, b_i e \bar u_i correspondentes.

Passo 7

Notas práticas e observações didáticas rápidas (como usar na prova)
  • Sempre verifique o sinal dos \bar{u}_{i} de acordo com o sentido da restrição relaxada antes de montar o corte.
  • Para calcular L(\bar u) na prática, resolve-se o subproblema \min_{x\in\Gamma}(c^{\top}-\bar u^{\top}A)x + b^{\top}\bar u. O x^{*} obtido nesse subproblema permite simplificar o corte (Passo 4).
  • O corte é válido para o problema original: qualquer x que satisfaça as restrições originais também satisfará o corte; ele serve para cortar soluções do master que violam as restrições relaxadas.
  • Quando receber as relaxações específicas da questão 1 eu aplico o template e escrevo o corte explicitamente para cada caso pedido.

Resposta

Forma algébrica geral do Plano Cortante Lagrangiano:
\bigl(c^{\top}-\bar{u}^{\top}A\bigr)x \;\ge\; L(\bar{u})-\bar{u}^{\top}b.
Forma componente a componente (relaxando o conjunto R de linhas de A):
\sum_{j}\Bigl(c_{j}-\sum_{i\in R}\bar{u}_{i}a_{ij}\Bigr)x_{j} \;\ge\; L(\bar{u})-\sum_{i\in R}\bar{u}_{i}b_{i}.
Forma usando o minimizador x^{*} do subproblema (simplificação prática):
\bigl(c^{\top}-\bar{u}^{\top}A\bigr)\bigl(x-x^{*}\bigr)\ge0,
onde L(\bar{u})=(c^{\top}-\bar{u}^{\top}A)x^{*}+ \bar{u}^{\top}b.

Exercícios relacionados