Algoritmo de Branch and Cut

Esse é o primeiro post de uma série sobre combinatória poliédrica. Ela consiste no estudo da estrutura de problemas combinatórios e representa uma ferramenta importante na construção de modelos eficientes de progração linear inteira. Aqui vou falar sobre o algoritmo de Branch and Cut. Estou assumindo conhecimento prévio sobre Branch and Bound.

Abordagem Geométrica

Podemos pensar em programas lineares de forma geométrica. Para exemplificar, considere um programa linear de minimização (daqui pra frente, estarei sempre me referindo a esse tipo de PL), com duas variáveis (). Uma desigualdade da forma

representa um semi-plano. Em um programa linear, temos um conjunto de desigualdades que devem ser satisfeitas ao mesmo tempo. Geometricamente, isso equivale à interseção dos semi-planos. Um semi-plano é um polígono convexo (ilimitado) e a interseção de polígonos convexos é sempre um polígono convexo. Assim, o espaço de soluções é representado por um polígono convexo, ou para dimensões maiores, poliedros convexos.

Além disso, a função objetivo é da forma

Variando o valor de z, vemos que essa equação representa uma família de retas paralelas, e nosso objetivo é encontrar a reta para a qual z que seja mínimo (seja z* o z mínimo). Para dimensões maiores, a função objetivo é um hiperplano. A solução ótima (seja ela ) é um ponto do poliedro que satisfaz . É possível mostrar que a solução ótima de um programa linear está em um vértice do poliedro.


Poliedro representando a formulação de um problema com duas variáveis. As retas paralelas representam a função objetivo.

Para um programa linear inteiro, temos a restrição de que as variáveis são inteiras. Considere o conjunto P de pontos de coordenadas inteiras que são viáveis para nosso problema. Definimos a envoltória convexa como o menor polígono que contém P.

Na figura abaixo, os pontos inteiros que representam soluções viáveis para nosso problema, estão marcados em vermelho. A envoltória convexa é o polígono de borda preta. Já os polígonos em verde e vermelho são formulações válidas para nosso problema. Uma formulação é válida se não deixa nenhum ponto viável de fora e não inclui nenhum ponto inteiro que não seja viável. De fato, as duas formulações abaixo são válidas, uma vez que não deixam nenhum ponto vermelho de fora e não incluem nenhum ponto branco. Observe que existem infinitas possíveis formulações válidas para um problema.

A envoltória convexa e formulações válidas.

Para problemas NP-difíceis, não podemos encontrar todas as desigualdades que definem a envoltória convexa em tempo polinomial a menos que P=NP, já que do contrário poderíamos resolver o modelo como um programa linear (sem as restrições de integralidade) em tempo polinomial.

Entretanto, só o fato de aproximar a formulação da envoltória convexa já é interessante para o algoritmo de Branch and Bound. Lembrando que em cada nó é resolvida a relaxação linear do modelo, ou seja, remover suas restrições de integralidade. O valor obtido, chamado limitante dual, é usado para realizar podas por limitantes na árvore. A poda por limitantes funciona assim: se a relaxação for maior ou igual à melhor solução conhecida até agora, então não precisamos explorar sua subárvore, uma vez que o limitante dual é sempre menor ou igual ao valor de qualquer solução obtida nessa subárvore.

Aproximar a formulação da envoltória, tende a aumentar o valor da relaxação linear nos nós, que por sua vez tende a aumentar o número de podas por limitantes, melhorando o desempenho do algoritmo. Para isso precisamos encontrar desigualdades válidas e que aproximem o modelo da envoltória convexa. Porém, o número  de dessas desigualdades pode ser muito grande, tornando a resolução da relaxação linear muito lenta, sem contar que algumas das desigualdades podem ser irrelevantes para diminuir o valor do limitante dual. A ideia então é adicionar tais desigualdades apenas por demanda, através de algoritmos de plano de corte.

Algoritmo de Planos de Corte

Como pode ser visto na figura abaixo, o ponto ótimo da relaxação linear (azul) do polígono verde, não possui coordenadas inteiras. Assim, não é uma solução válida para o problema. A ideia é utilizar retas que “cortem” o ponto fora. Essa reta (ou hiperplano em dimensões maiores), chamada de plano de corte, nada mais é do que uma desigualdade que é satisfeita por todos os pontos viáveis (vermelhos) e não é satisfeita pelo ponto que queremos remover (azul). Às vezes, decidir se uma desigualdade representa um plano de corte é NP-difícil! Na prática, usam-se heurísticas.

Plano de corte remove a solução ótima

O que se faz em geral é encontrar famílias de desigualdades válidas a priori e, ao resolver a relaxação linear em cada nó do Branch and Bound, verificamos se a solução ótima encontrada viola alguma dessas desigualdades. Em caso positivo, inserimos a nova restrição no modelo e resolvemos a relaxação linear novamente, repetindo o processo enquanto conseguirmos melhor o limitante dual. Ao mudar de nó no algoritmo, descartamos os planos de corte adicionados.

Um corte pode não ser muito eficaz, porém. Se a desigualdade remover apenas a solução ótima, não ajudou muito a aproximar a formulação da envoltória convexa. Dado um plano de corte, ele pode ser classificado de acordo com a dimensão da sua interseção com a envoltória convexa. Na figura abaixo, vemos os três tipos de desigualdades para duas dimensões: a interseção de l1 com a envoltória é nula e tem dimensão -1; l2 com a envoltória é um ponto e tem dimensão 0; e l3 com a envoltória forma uma reta, com dimensão 1.

Possíveis planos de corte

É intuitivo pensar que os cortes mais eficazes são aqueles de dimensão maior (no exemplo, a reta l3). A prática também mostra que tais cortes são melhores. Assim, sendo n a dimensão da envoltória convexa, estamos interessados em encontrar desigualdades cuja interseção com a envoltória tenham dimensão n-1, que são justamente aquelas desigualdades que definem facetas dessa envoltória.

O Branch and Bound onde aplicamos algoritmos de plano de corte é chamado de Branch and Cut. No próximo post da série falarei sobre como determinar se uma desigualdade representa uma faceta da envoltória convexa.

Leituras adicionais e referências

[1] Disciplina de Programação linear inteira com o prof. Cid.
[2] Wolsey, L. – Integer Programming [link]

Uma resposta a Algoritmo de Branch and Cut

  1. João Fernando Sartorelli diz:

    Muito legal este Blog. Tenho algumas teorias que gostaria de compartilhar: Na área de combinatória tenho, por exemplo, 10 elementos: A,B,C,D,E,F,G,H,I,J, se combiná-los sem repeticão temos C10/2= 45 grupos de dois a dois se os distribuirmos em três posições teriamos que ter 45/3= 15 espaços, por exemplo
    A A A A
    B D F H
    C E G I e assim sucessivamente mas pela minha teoria é impossível distribuir 10 elementos combinados dois a dois em três espaços dimensionais
    Existe uma e somente uma sequência que se distribui e é esta:
    S= ( 3,7,9,11,………………………..) portanto 10 não está na sequência

%d bloggers like this: