|
Registro Completo |
|
Biblioteca(s): |
Embrapa Agricultura Digital. |
|
Data corrente: |
28/10/2003 |
|
Data da última atualização: |
17/01/2020 |
|
Autoria: |
LORENA, L. A. N.; NARCISO, M. G. |
|
Afiliação: |
LUIZ ANTONIO N. LORENA, Inpe; MARCELO GONCALVES NARCISO, CNPTIA. |
|
Título: |
Using logical surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. |
|
Ano de publicação: |
2002 |
|
Fonte/Imprenta: |
European Journal of Operational Research, v. 138, p. 473-483, 2002. |
|
DOI: |
10.1016/S0377-2217(01)00159-X |
|
Idioma: |
Inglês |
|
Conteúdo: |
The traveling salesman problem (TSP) is a classical combinatorial optimization problem, which has been intensively studied. The Lagrangean relaxation was firts applied to the TSP in 1970. The Lagrangean relaxation limit approximates what is known today as Held and Karp (HK) bound, a very good bound (less than 1% from optimal) for a large class of symmetric instances. It became a reference bound for new heuristics, mainly for the very large scale instances, where the use of exact methods is prohibitive. A known problem for the Lagrangean relaxation application is the definition of a convenient step size control in subgradient like methods. Even preserving theoretical convergence properties, a wrong defined control can affect the performance and increase computational times. We show in this work how to accelerate a classical subgradient method while conserving good approximations to the HK bounds. The surrogate and Lagrangean relaxations are combined using the local information of the relaxed constraints. It results in a one-dimensional search that corrects the possibly wrong step size and independent of the used step size control. Comparing with the ordinary subgradient method, and beginning with the same initial multiplier, the computational times are almost twice as fast for medium instances and greatly improved for some large scale TSPLIB instances. |
|
Palavras-Chave: |
Lagrangean relaxation; Problema do caixeiro viajante; Relaxação lagrangeana; Subgradient method; Surrogate relaxation. |
|
Categoria do assunto: |
X Pesquisa, Tecnologia e Engenharia |
|
Marc: |
LEADER 02086naa a2200205 a 4500
001 1008506
005 2020-01-17
008 2002 bl uuuu u00u1 u #d
024 7 $a10.1016/S0377-2217(01)00159-X$2DOI
100 1 $aLORENA, L. A. N.
245 $aUsing logical surrogate information in Lagrangean relaxation$ban application to symmetric traveling salesman problems.$h[electronic resource]
260 $c2002
520 $aThe traveling salesman problem (TSP) is a classical combinatorial optimization problem, which has been intensively studied. The Lagrangean relaxation was firts applied to the TSP in 1970. The Lagrangean relaxation limit approximates what is known today as Held and Karp (HK) bound, a very good bound (less than 1% from optimal) for a large class of symmetric instances. It became a reference bound for new heuristics, mainly for the very large scale instances, where the use of exact methods is prohibitive. A known problem for the Lagrangean relaxation application is the definition of a convenient step size control in subgradient like methods. Even preserving theoretical convergence properties, a wrong defined control can affect the performance and increase computational times. We show in this work how to accelerate a classical subgradient method while conserving good approximations to the HK bounds. The surrogate and Lagrangean relaxations are combined using the local information of the relaxed constraints. It results in a one-dimensional search that corrects the possibly wrong step size and independent of the used step size control. Comparing with the ordinary subgradient method, and beginning with the same initial multiplier, the computational times are almost twice as fast for medium instances and greatly improved for some large scale TSPLIB instances.
653 $aLagrangean relaxation
653 $aProblema do caixeiro viajante
653 $aRelaxação lagrangeana
653 $aSubgradient method
653 $aSurrogate relaxation
700 1 $aNARCISO, M. G.
773 $tEuropean Journal of Operational Research$gv. 138, p. 473-483, 2002.
Download
Esconder MarcMostrar Marc Completo |
|
Registro original: |
Embrapa Agricultura Digital (CNPTIA) |
|
