Resolução de problemas de programação
linear combinando o algoritmo
volumétrico e uma função de penalidade
exponencial
Ana Maria A. C. Rocha, Universidade do Minho
[email protected]
Edite M. G. P. Fernandes, Universidade do Minho
[email protected]
João Luís C. Soares, Universidade de Coimbra
[email protected]
Guimarães, 24-27 Março 2002
Conteúdo
 Introdução
 O Algoritmo Volumétrico
 Combinação com uma Função de
Penalidade Exponencial
 Experiências Computacionais
 Trabalho Futuro
2
Introdução
Consideremos um problema de fractional set partitioning
onde A é uma matriz 0-1 e é um vector de uns.
 O problema (1) resulta da relaxação linear de problemas de set partitioning
(political districting, airline crew scheduling, protection of microdata,
information retrieval, ...).
 Os métodos tradicionais podem demorar mais de 10 horas, mesmo em máquinas
rápidas (dimensão típica é n = 50000, m = 2500 e superior).
 Os algoritmos de ponto interior têm funcionado melhor que o simplex, mas
requerem mais memória.
 O algoritmo volumétrico, considerado como uma extensão do método do
subgradiente, para além de produzir soluções duais produz também boas
aproximações à solução primal.
3
Algoritmo do subgradiente
Para um dado vector de multiplicadores
(também designado por solução
dual), uma natural relaxação Lagrangeana do problema linear (1) é:

é uma função linear por partes, côncava e não diferenciável
se e só se
.
Desde os anos setenta que o algoritmo do subgradiente tem sido usado para
produzir limites inferiores em programas lineares de grande dimensão ([3]).
4
Aspecto genérico de um algoritmo do subgradiente
Passo 1: Dado
,resolver (2) com
, para obter a sua solução .
Calcular
, que é um subgradiente da função em
Passo 2: Determinar
, onde
.
é o comprimento do passo.
Passo 3: Se o critério de paragem se verificar então terminar;
senão fazer
e ir para Passo 1.
5
Inconvenientes





A verificação do critério de paragem
problema de optimização
resolução.
obriga à resolução do seguinte
, que não aparenta ser de fácil
A escolha adequada do tamanho do passo
não deve basear-se apenas na
análise teórica da convergência, senão torna-o muito pequeno.
A direcção dual pode não ser uma direcção de subida para
em . Para
isso, seria necessário calcular a derivada direccional que requer algum esforço
adicional. Além disso, os procedimentos da pesquisa unidimensional obrigam a
sucessivas avaliações da função
, o que é normalmente custoso.
O algoritmo do subgradiente tem convergência linear (provavelmente porque a
direcção calculada apenas depende do último ponto encontrado e toda a
informação dada pelas iterações anteriores é ignorada).
O algoritmo do subgradiente não garante variáveis primais admissíveis.
6
O algoritmo Volumétrico
O algoritmo volumétrico é uma extensão do algoritmo do subgradiente que, com o
mesmo esforço computacional, produz não só as variáveis duais como também
aproximações às variáveis primais.
Este algoritmo foi desenvolvido por F. Barahona (ver [1] e [2]) e mostrou que era
funcional nas seguintes classes de problemas:
 Problemas Lineares Combinatórios;
 quando a matriz A tem coeficientes 0, 1, -1;
 quando as variáveis são limitadas entre 0 e 1.
7
Passos do algoritmo volumétrico
Passo 0: Dado
,resolver (2) com
. Definir
.
Passo 1: Calcular
e
passo
.
Resolver (2) com
Actualizar
com
onde
Passo 2: Se
, para obter a sua solução
e
para um comprimento de
, para obter a sua solução
e
.
é um comprimento de passo entre 0 e 1.
então actualizar
Passo 3: Testar o critério de paragem.
Se falhar então definir
e
com
.
e ir para Passo 1.
8
Critério de paragem
1.
2.
limite máximo do número de iterações
ou

máxima violação das restrições
e

diferença relativa entre solução dual
solução primal
e o valor da aproximação à
9
Experiência computacional com o algoritmo volumétrico
10
O algoritmo volumétrico com uma
função de penalidade exponencial
Consideremos um problema de fractional set partitioning da seguinte forma
onde
,
e
.
podem ser:
 restrições adicionais relacionadas com planos de corte quando se resolve o
problema original de set partitioning
ou
o conjunto das restrições de A consideradas mais difíceis, após aplicação do
algoritmo volumétrico original.
11
Aplicando uma função de penalidade exponencial ao 1º conjunto de restrições, (3)
transforma-se numa sucessão de subproblemas parametrizados por m
onde m > 0 é o parâmetro de penalidade.
 Para esta técnica de penalidade quando
então
.
12
Para um vector de multiplicadores
, a relaxação Lagrangeana do problema é:
Para aplicar o algoritmo volumétrico a este problema, podemos
 Linearizar o termo de penalidade de
 Resolver problemas não lineares para obter
e resolver problemas lineares.
.
13
Experiências com o caso linear
A matriz A, do problema (1), é decomposta em duas matrizes A1 e A2.
Após uma aplicação do algoritmo volumétrico ao problema original de fractional
set partitioning,
 A1 contém o conjunto das restrições m1 com maior violação (mais difíceis) e
 A2 contém todas as outras restrições (mais fáceis).
As restrições mais difíceis são penalizadas e o problema original transforma-se na
sucessão de subproblemas
onde
é o parâmetro de penalidade.
14
Após a linearização do termo de penalidade, a relaxação Lagrangeana do problema
é
para qualquer
.
15
O algoritmo volumétrico aplicado ao caso linear
Passo 0: Dado
, um vector
e um vector
para obter a sua solução
e
Passo 1: Calcular
Resolver (7) com
Actualizar
com
onde
Passo 2: Se
e
, resolver (7) com
. Definir
.
para um comprimento de passo
, para obter a sua solução e
.
.
é um comprimento de passo entre 0 e 1.
então actualizar
e
com
Passo 3: Actualizar , se necessário.
Testar critério de paragem. Se falhar então definir
.
e ir para Passo 1.
16
Escolha do parâmetro de penalidade m
1. Dado um valor inicial
2. Actualizar com
, cada k iterações.
Critério de paragem
1.
2.
máximo número de iterações
ou
 máxima violação das restrições
e
 diferença relativa entre solução dual
e o valor da aproximação à solução
primal
17
Experiências computacionais com a estrutura de
penalidade exponencial
18
Experiências preliminares com o caso não linear
Relembremos o problema original
Aplicando uma função de penalidade exponencial, ao conjunto das m
restrições de igualdade
é o parâmetro de penalidade.
19
Resolução de (9) através do algoritmo L-BFGS-B (ver [4]) desenvolvido
por Nocedal, para a resolução de problemas não lineares, de grandes
dimensões e com limites nas restrições.
 método Quasi-Newton;
 usa uma matriz BFGS de memória reduzida para aproximar a Hessiana da
função objectivo;
 a direcção de procura é determinada pelo método dos gradientes
projectados.
20
Algoritmo
Passo 0: Dado
e um vector
. Definir
.
Passo 1: Resolver (9) usando L-BFGS-B (processo iterativo interno), para obter a
solução
.
Passo 2: Actualizar
.
Passo 3: Testar o critério de paragem.
Se falhar então definir
e ir para Passo 1.
21
Critério de paragen
1.
(a)
ou
(b)
ou
2.
22
Experiências computacionais com o L-BFGS-B
23
Trabalho Futuro



Integrar o package L-BFGS-B no algoritmo volumétrico (penalizando apenas as
restrições mais difíceis).
Testar outros packages para a resolução de problemas não lineares de grandes
dimensões, com limites nas restrições. Por fim, integrá-los no algoritmo
volumétrico.
Estender a estrutura de penalidade exponencial a planos de corte (para resolver
problemas originais de set partitioning).
Referências
[1] F. Barahona e R. Anbil. On some difficult Linear Programs coming from set partitioning.
IBM T.J. Watson Research Center, NY.
[2] F. Barahona e R. Anbil. The Volume Algorithm: producing primal solutions with a
subgradient method. Mathematical Programming, 87:385-399, 2000.
[3] M. Held, P. Wolfe e H.P. Crowder. Validation os subgradient optimization. Mathematical
Programming, 6:62-68, 1974.
[4] C. Zhu, R. Byrd, P. Lu e J. Nocedal. L-BFGS-B – fortran routines for large-scale bound
constrained optimization. Northwestern Univ. EECS Technical Report, 1996.
24