- -

Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Corberán;Plana;Sanchís ...
Tamaño: 362.5Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: mathprogzigzag2006.pdf
Tamaño: 245.3Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Corberán, A. es_ES
dc.contributor.author Plana, I. es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-09-24T12:30:43Z
dc.date.available 2020-09-24T12:30:43Z
dc.date.issued 2006-08 es_ES
dc.identifier.issn 0025-5610 es_ES
dc.identifier.uri http://hdl.handle.net/10251/150683
dc.description.abstract [EN] In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed. es_ES
dc.description.sponsorship The authors wish to thank the Ministerio de Ciencia y Tecnología of Spain (project TIC2003-05982-C05-01) and the Generalitat Valenciana (Ref: GRUPOS03/189) their support. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Mathematical Programming es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Polyhedral Combinatorics es_ES
dc.subject Facets es_ES
dc.subject Arc Routing es_ES
dc.subject Windy Rural Postman Problem es_ES
dc.subject Windy General Routing Problem es_ES
dc.subject Mixed Rural Postman Problem es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10107-005-0643-y es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICYT//TIC2003-05982-C05-01/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/GVA//GRUPOS03%2F189/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada es_ES
dc.description.bibliographicCitation Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2006). Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems. Mathematical Programming. 108(1):79-96. https://doi.org/10.1007/s10107-005-0643-y es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10107-005-0643-y es_ES
dc.description.upvformatpinicio 79 es_ES
dc.description.upvformatpfin 96 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 108 es_ES
dc.description.issue 1 es_ES
dc.relation.pasarela S\29885 es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder Ministerio de Ciencia y Tecnología es_ES
dc.description.references Benavent, E., Carrotta, A., Corberán, A., Sanchis, J.M., Vigo, D.: Lower Bounds and Heuristics for the Windy Rural Postman Problem. Technical Report TR03-2003. Department of Statistics and OR, University of Valencia (Spain). Submitted to EJOR 2003 es_ES
dc.description.references Benavent, E., Corberán, A., Piñana, E., Plana, I., Sanchis, J.M.: New Heuristics for the Windy Rural Postman Problem. To appear in Comput. Oper. Res. 2005 es_ES
dc.description.references Chopra, S., Rinaldi, G.: The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities. SIAM J. Discrete Math. 9 (4), 602–624 (1996) es_ES
dc.description.references Christofides, N., Benavent, E., Campos, V., Corberán, A., Mota, E.: An Optimal Method for the Mixed Postman Problem. In: P. Thoft-Christensen (ed.) System Modelling and Optimization. Lecture Notes in Control and Information Sciences, 59. Berlin: Springer-Verlag 1984 es_ES
dc.description.references Christofides, N., Campos, V., Corberán, A., Mota, E.: An Algorithm for the Rural Postman Problem. Report IC.OR. 81.5. Imperial College, London 1981 es_ES
dc.description.references Corberán, A., Mejía, G., Sanchis, J.M.: New Results on the Mixed General Routing Problem. To appear in Oper. Res. 2005 es_ES
dc.description.references Corberán, A., Mota, E., Sanchis, J.M.: A Comparison of Two Different Formulations for Arc Routing Problems on Mixed Graphs. To appear in Comput. Oper. Res. 2005 es_ES
dc.description.references Corberán, A., Plana, I., Sanchis, J.M.: On the Windy General Routing Polyhedron. In preparation 2005 es_ES
dc.description.references Corberán, A., Romero, A., Sanchis, J.M.: The Mixed General Routing Problem Polyhedron. Math. Programming 96, 103–137 (2003) es_ES
dc.description.references Cornuèjols, G., Fonlupt, J., Naddef, D.: The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming 33, 1–27 (1985) es_ES
dc.description.references Eiselt, H.A., Gendreau, M., Laporte, G.: Arc-Routing Problems, Part 2: the Rural Postman Problem. Oper. Res. 43, 399–414 (1995) es_ES
dc.description.references Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton, NJ 1962 es_ES
dc.description.references Grötschel, M., Win, Z.: On the Windy Postman Polyhedron. Report No. 75, Schwerpunktprogram der Deutschen Forschungsgemeinschaft, Universität Augsburg, Germany 1988 es_ES
dc.description.references Grötschel, M., Win, Z.: A Cutting Plane Algorithm for the Windy Postman Problem. Math. Programming 55, 339–358 (1992) es_ES
dc.description.references Guan, M.: On the Windy Postman Problem. Discrete Applied Mathematics 9, 41–46 (1984) es_ES
dc.description.references Letchford, A.: New inequalities for the General Routing Problem. Eur. J. Oper. Res. 96, 317–322 (1997) es_ES
dc.description.references Minieka, E.: The Chinese Postman Problem for Mixed Networks. Management Sci. 25, 643–648 (1979) es_ES
dc.description.references Naddef, D., Rinaldi, G.: The Symmetric Traveling Salesman Polytope and its Graphical Relaxation: Composition of Valid Inequalities. Math. Programming 51, 359–400 (1991) es_ES
dc.description.references Nobert, Y., Picard, J.C.: An Optimal Algorithm for the Mixed Chinese Postman Problem. Networks 27, 95–108 (1996) es_ES
dc.description.references Ralphs, T.K.: On the Mixed Chinese Postman Problem. Oper. Res. Lett. 14, 123–127 (1993) es_ES
dc.description.references Win, Z.: Contributions to Routing Problems. PhD Dissertation, University of Augsburg, Germany 1987 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem