Um novo algoritmo para soluções ótimas locais do problema linear de dois níveis

Leonardo Delarmelina Secchin

Abstract


Neste artigo, apresentamos um algoritmo para encontrar soluções ótimas locais dos problemas lineares de dois níveis. A cada ponto viável corrente, o método busca por melhores soluções no conjunto dos pontos que se encontram em suas faces adjacentes. Em cada passo tenta-se encontrar as faces adjacentes de maior dimensão, na esperança de acelerar o processo. Uma prova de corretude do método é fornecida, e testes computacionais foram realizados.

References


J.F. Bard, "Practical Bilevel Optimization: Algorithms and Applications", Nonconvex Optimization and Its Applications, Vol. 30, Kluwer Academic Publishers, 1998.

H.I. Calvete, C. Galé, P.M. Mateo. A new approach for solving linear bilevel problems using genetic algorithms, European Journal of Operational Research, 188, No. 1 (2008), 14-28.

M.B.C. Campêlo, "Programação Linear em Dois Níveis: Uma Abordagem Teórica e Computacional", Tese de Doutorado, COPPE, UFRJ, Rio de Janeiro, 1999.

B. Colson, P. Marcotte, G. Savard, An overview of bilevel optimization, Annals of Operations Research, 153, No. 1 (2007), 235-256.

C.H.M. de Sabóia, M.B.C. Campêlo, S. Scheimberg, A computational study of global algorithms for bilevel linear programming, Numerical Algorithms, 35, No. 2-4 (2004), 155-173.

S. Dempe, "Foundations of Bilevel Programming", Nonconvex Optimization and Its Applications, Vol. 61, Kluwer Academic Publishers, 2002.

X. Deng, Complexity issues in bilevel linear programming, em "Multilevel Optimization: Algorithms and Applications" (A. Migdalas, P.M. Pardalos, P. Värbrand, eds.), Nonconvex Optimization and Its Applications, pp. 149-164, Kluwer Academic Publishers, 1998.

C.A. Floudas, C.E. Gounaris, A review of recent advances in global optimization. Journal of Global Optimization, 45, No. 1 (2009), 3-38.

J. Glackin, J.G. Ecker, M. Kupferschmid, Solving bilevel linear programs using multiple objective linear programming, Journal of Optimization Theory And Application, 140, No. 2 (2009), 197-212.

R.J. Kuoa, C.C. Huang, Application of particle swarm optimization algorithm for solving bi-level linear programming problem, Computers and Mathematics with Applications, 58, No. 4 (2009), 678-685.

K.H. Sabin, A.R. Ciric, A dual temperature simulated annealing approach for solving bilevel programming problems, Computers and Chemical Engineering, 23, No. 1 (1998), 11-25.

G. Still. Linear bilevel problems: genericity results and an efficient method for computing local minima, Mathematical Methods of Operations Research, 55, No. 3 (2002), 383-400.

U.P. Wen, A.D. Huang, A simple tabu search method to solve the mixed-integer linear bilevel programming problem, European Journal of Operational Research, 88, No. 3 (1996), 563-571.




DOI: https://doi.org/10.5540/tema.2012.013.01.0051

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia