×

Facets of the \(p\)-cycle polytope. (English) Zbl 1009.52025

This paper studies the convex hull of all incidence vectors of simple directed cycles consisting of \(p\) arcs in the complete directed graph \(K_n\). After determining the dimension as a function of \(n\) and \(p\), various other polyhedral results are given. They include a description of the bases of the equality set, two lifting results, and various aspects of valid inequalities and facets. Finally, the relationship to the \(p\)-circuit polytope is investigated, which is the corresponding structure on undirected graphs.

MSC:

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms and Applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Balas, E., The prize collecting traveling salesman problem, Networks, 19, 621-636 (1989) · Zbl 0676.90089
[3] E. Balas, On the cycle polytope of a directed graph, Management Science Research Report #MSSR-593, GSIA, Carnegie Mellon University, 1993.; E. Balas, On the cycle polytope of a directed graph, Management Science Research Report #MSSR-593, GSIA, Carnegie Mellon University, 1993.
[4] Balas, E.; Fischetti, M., A lifting procedure for the asymmetric traveling salesman problem polytope and a large new class of facets, Math. Programming, 58, 325-352 (1993) · Zbl 0780.90100
[5] E. Balas, M. Oosten, On the cycle polytope of a directed graph, preprint, 1996.; E. Balas, M. Oosten, On the cycle polytope of a directed graph, preprint, 1996. · Zbl 0969.90071
[6] Bauer, P., The circuit polytope: facets, Math. Oper. Res., 22, 1, 110-145 (1997) · Zbl 0871.90099
[7] P. Bauer, J.T. Linderoth, M.W.P. Savelsbergh, A branch and cut approach to the cardinality constrained circuit problem, Technical Report LEC-98-04, School of Industrial and Systems Engineering, Georgia Institute of Technology, 1998.; P. Bauer, J.T. Linderoth, M.W.P. Savelsbergh, A branch and cut approach to the cardinality constrained circuit problem, Technical Report LEC-98-04, School of Industrial and Systems Engineering, Georgia Institute of Technology, 1998. · Zbl 1049.90135
[8] Boros, E.; Hammer, P. L.; Hartmann, M. E.; Shamir, R., Balancing problems in acyclic networks, Discrete Appl. Math., 49, 77-93 (1994) · Zbl 0811.90108
[9] T. Christof, Ein Verfahren zur Transformation zwischen Polyederdarstellungen, Diplomarbeit, Universität Augsburg, 1991.; T. Christof, Ein Verfahren zur Transformation zwischen Polyederdarstellungen, Diplomarbeit, Universität Augsburg, 1991.
[10] Coullard, C.; Pulleyblank, W. R., On cycle cones and polyhedra, Linear Algebra Appl., 114/115, 613-640 (1989) · Zbl 0714.90071
[11] Current, J. R.; Schilling, D. A., The median tour and maximal covering tour problems: formulations and heuristics, European J. Oper. Res., 73, 114-126 (1994) · Zbl 0806.90036
[12] G.B. Dantzig, W.O. Blattner, M.R. Rao, Finding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem, in: Theory of Graphs (International Symposium, ed. P. Rosenstiel, Rome, 1966), Gordon and Breach, New York, 1967, pp. 77-83.; G.B. Dantzig, W.O. Blattner, M.R. Rao, Finding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem, in: Theory of Graphs (International Symposium, ed. P. Rosenstiel, Rome, 1966), Gordon and Breach, New York, 1967, pp. 77-83. · Zbl 0189.24102
[13] Fischetti, M., Clique tree inequalities define facets of the asymmetric traveling salesman polytope, Discrete Appl. Math., 56, 9-18 (1995) · Zbl 0819.90121
[14] Fischetti, M.; Gonzalez, J. J.S.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper. Res., 45, 3, 378-394 (1997) · Zbl 0893.90164
[15] Grötschel, M.; Padberg, M. W., Polyhedral theory, (Lawler, E. L.; Lenstra, J. K.; Rinooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley New York), 251-305 · Zbl 0587.90073
[16] M. Hartmann, Ö. Özlük, Solving the traveling circus problem by branch and cut, extended abstract, in: H.J. Broersma, U. Faigle, C. Hoede, J.L. Hurink (Eds.), Sixth Twente Workshop on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Mathematics, Vol. 3, Elsevier, Amsterdam, 1999.; M. Hartmann, Ö. Özlük, Solving the traveling circus problem by branch and cut, extended abstract, in: H.J. Broersma, U. Faigle, C. Hoede, J.L. Hurink (Eds.), Sixth Twente Workshop on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Mathematics, Vol. 3, Elsevier, Amsterdam, 1999. · Zbl 1038.90547
[17] Karp, R. M.; Orlin, J. B., Parametric shortest path algorithms with an application to cyclic staffing, Discrete Appl. Math., 3, 37-45 (1981) · Zbl 0453.68032
[18] M. Kovalev, J.F. Maurras, Y. Vaxes, On the convex hull of the 3-cycles of the complete graph, Technical Report 251, Laboratoire d’Informatique de Marseille, Faculté des Sciences de Luminy, 1997.; M. Kovalev, J.F. Maurras, Y. Vaxes, On the convex hull of the 3-cycles of the complete graph, Technical Report 251, Laboratoire d’Informatique de Marseille, Faculté des Sciences de Luminy, 1997.
[19] J. Maurras, V.H. Nguyen, On the linear description of the 3-cycle polytope, preprint, 1998.; J. Maurras, V.H. Nguyen, On the linear description of the 3-cycle polytope, preprint, 1998.
[20] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052
[21] V.H. Nguyen, J. Maurras, On the linear description of the \(k\)-cycle polytope, \( PC_n^{k\) · Zbl 1009.90100
[22] Ö. Özlük, The \(p\)-cycle polytope, Ph.D. Thesis, Department of Operations Research, UNC Chapel Hill, June 1999.; Ö. Özlük, The \(p\)-cycle polytope, Ph.D. Thesis, Department of Operations Research, UNC Chapel Hill, June 1999. · Zbl 1009.52025
[23] Revelle, C. S.; Laporte, G., The plant location problem: new models and research prospects, Oper. Res., 44, 6, 864-874 (1996) · Zbl 0879.90130
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.