| 1. Identificação | |
| Tipo de Referência | Artigo em Revista Científica (Journal Article) |
| Site | marte3.sid.inpe.br |
| Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identificador | 6qtX3pFwXQZ3r59YCT/H3KQg |
| Repositório | sid.inpe.br/iris@1905/2005/08.04.02.50 (acesso restrito) |
| Última Atualização | 2013:04.12.12.27.01 (UTC) jefferson |
| Repositório de Metadados | sid.inpe.br/iris@1905/2005/08.04.02.50.31 |
| Última Atualização dos Metadados | 2018:06.06.03.55.42 (UTC) administrator |
| Chave Secundária | INPE-9832-PRE/5416 |
| ISSN | 0377-2217 |
| Rótulo | 10510 |
| Chave de Citação | LorenaNarc:2002:ApSyTr |
| Título | Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems  |
| Projeto | CNPq (proc. 300837/89-5); FAPESP (proc. 99/06954- 7). |
| Ano | 2002 |
| Data Secundária | 2002609 |
| Mês | May. |
| Data de Acesso | 02 maio 2024 |
| Tipo Secundário | PRE PI |
| Número de Arquivos | 1 |
| Tamanho | 266 KiB |
| 2. Contextualização | |
| Autor | 1 Lorena, Luiz Antonio Nogueira 2 Narciso, Marcelo Gonç |
| Grupo | 1 LAC-INPE-MCT-BR |
| Afiliação | 1 Instituto Nacional de Pesquisas Espaciais (INPE) 2 CNPTIA/EMBRAPA, Campinas, SP, Brazil |
| Endereço de e-Mail do Autor | 1 lorena@lac.inpe.br |
| Revista | European Journal of Operational Research |
| Volume | 138 |
| Número | 312 |
| Páginas | 473-483 |
| Histórico (UTC) | 2013-04-12 12:12:13 :: administrator -> jefferson :: 2002 2013-04-12 14:05:53 :: jefferson -> administrator :: 2002 2018-06-06 03:55:42 :: administrator -> marciana :: 2002 |
| 3. Conteúdo e estrutura | |
| É a matriz ou uma cópia? | é a matriz |
| Estágio do Conteúdo | concluido |
| Transferível | 1 |
| Tipo do Conteúdo | External Contribution |
| Tipo de Versão | publisher |
| Palavras-Chave | Lagrangean/surrogate relaxation traveling salesman problem subgradient method subgradient optimization convergence algorithms constraints duality step |
| Resumo | The traveling salesman problem (TSP) is a classical combinatorial optimization problem, which has been intensively studied. The Lagrangean relaxation was first 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 percent 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 is 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. |
| Área | COMP |
| Arranjo | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > Using logical surrogate... |
| Conteúdo da Pasta doc | acessar |
| Conteúdo da Pasta source | não têm arquivos |
| Conteúdo da Pasta agreement | não têm arquivos |
| 4. Condições de acesso e uso | |
| Arquivo Alvo | 1-s2.0-S037722170100159X-main.pdf |
| Grupo de Usuários | administrator jefferson |
| Visibilidade | shown |
| Política de Arquivamento | denypublisher denyfinaldraft36 |
| Permissão de Leitura | deny from all and allow from 150.163 |
| Permissão de Atualização | não transferida |
| 5. Fontes relacionadas | |
| Unidades Imediatamente Superiores | 8JMKD3MGPCW/3ESGTTP |
| Divulgação | WEBSCI; PORTALCAPES. |
| Acervo Hospedeiro | sid.inpe.br/banon/2001/04.03.15.36 |
| 6. Notas | |
| Campos Vazios | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel doi e-mailaddress format isbn language lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid rightsholder schedulinginformation secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url |
| 7. Controle da descrição | |
| e-Mail (login) | marciana |
| atualizar | |