CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe consider the problem of spanning the nodes of a given colored graph G=(N,A) by a set of node-disjoint cycles at minimum reload cost, where a non-negative reload cost is paid whenever passing through a node where the two consecutive arcs have different colors. We call this problem Minimum Reload Cost Cycle Cover (MinRC3 for short). We prove that it is strongly NP-hard and not approximable within 1/ϵ for any ϵ>0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. Some IP models for MinRC3 are then presented, one well suited for a Column Generation approach. The corresponding pricing subproblem is also proved strongly NP-hard. Primal bounds for MinRC3 are obtained via local search based heuristics exploiting 2-opt and 3-opt neighborhoods. Computational results are presented comparing lower and upper bounds obtained by the above mentioned approaches.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | On Minimum Reload Cost Cycle Cover | |
| Autori: | ||
| Data di pubblicazione: | 2014 | |
| Rivista: | ||
| Abstract: | We consider the problem of spanning the nodes of a given colored graph G=(N,A) by a set of node-disjoint cycles at minimum reload cost, where a non-negative reload cost is paid whenever passing through a node where the two consecutive arcs have different colors. We call this problem Minimum Reload Cost Cycle Cover (MinRC3 for short). We prove that it is strongly NP-hard and not approximable within 1/ϵ for any ϵ>0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. Some IP models for MinRC3 are then presented, one well suited for a Column Generation approach. The corresponding pricing subproblem is also proved strongly NP-hard. Primal bounds for MinRC3 are obtained via local search based heuristics exploiting 2-opt and 3-opt neighborhoods. Computational results are presented comparing lower and upper bounds obtained by the above mentioned approaches. | |
| Handle: | http://hdl.handle.net/11571/805638 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
Copyright © 2022