Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1267-1277.

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G, a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by Rinaldi and Franz (Eur. J. Oper. Res. 183 (2007) 1371–1384). Facet-preserving procedures have been shown to be quite effective at explaining the facet-inducing inequalities of the associated polytope, so in this work we continue this issue by exploring such procedures for valid inequalities with acyclic supports. In particular, the obtained results are applicable when the underlying graph is a tree.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018085
Classification : 90C10, 90C27
Mots-clés : Caterpillar-packing, facets, trees
Marenco, Javier 1

1 
@article{RO_2019__53_4_1267_0,
     author = {Marenco, Javier},
     title = {Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1267--1277},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {4},
     year = {2019},
     doi = {10.1051/ro/2018085},
     mrnumber = {3989210},
     zbl = {1432.90086},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2018085/}
}
TY  - JOUR
AU  - Marenco, Javier
TI  - Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1267
EP  - 1277
VL  - 53
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2018085/
DO  - 10.1051/ro/2018085
LA  - en
ID  - RO_2019__53_4_1267_0
ER  - 
%0 Journal Article
%A Marenco, Javier
%T Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1267-1277
%V 53
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2018085/
%R 10.1051/ro/2018085
%G en
%F RO_2019__53_4_1267_0
Marenco, Javier. Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1267-1277. doi : 10.1051/ro/2018085. http://archive.numdam.org/articles/10.1051/ro/2018085/

R. Baldacci, M. Dell’Amico and J. Salazar González, The capacitated m-ring-star problem. Oper. Res. 55 (2007) 1147–1162. | DOI | MR | Zbl

H. Calvete, C. Galé and J. Iranzo, An efficient evolutionary algorithm for the ring star problem. Eur. J. Oper. Res. 231 (2013) 22–33. | DOI | MR | Zbl

T. Dias, G. De Sousa, E. Macambira, L. Cabral and M. Fampa, An efficient heuristic for the ring star problem. In: Proceedings of the 5th International Workshop on Experimental Algorithms WEA 2006, Menorca, Spain. In Vol. 4007 of Lect. Note Comput. Sci. (2006) 24–35. | Zbl

M. Dinneen and M. Khosravani, A linear time algorithm for the minimum spanning caterpillar problem for bounded treewidth graphs. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, Sirince. In Vol. 6058 of Lect. Notes Comput. Sci. 237–246 (2010). | DOI | MR | Zbl

M. Dinneen and M. Khosravani, Hardness of approximation and integer programming frameworks for searching for caterpillar trees. In: Proceedings of the Seventeenth Computing on The Australasian Theory Symposium, Perth, Australia (2011) 145–150.

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1993). | DOI | MR | Zbl

S. Kedad-Sidhoum and V. Nguyen, An exact algorithm for solving the ring star problem. Optimization 59 (2010) 125–140. | DOI | MR | Zbl

M. Labbé, G. Laporte, I. Martín and J. González, The ring star problem: polyhedral analysis and exact algorithm. Networks 43 (2004) 177–189. | DOI | MR | Zbl

C. Lekkerkerker and J. Boland, Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51 (1962) 45–64. | DOI | MR | Zbl

S. Lucero, J. Marenco and F. Martínez, An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint. Optim. Eng. 16 (2015) 605–632. | DOI | MR | Zbl

J. Marenco, The caterpillar-packing polytope. Discrete Appl. Math. 245 (2018) 4–15. | DOI | MR | Zbl

Z. Naji-Azimi, M. Salari and P. Toth, A heuristic procedure for the capacitated m-ring-star problem. Eur. J. Oper. Res. 207 (2010) 1227–1234. | DOI | MR | Zbl

F. Rinaldi and A. Franz, A two-dimensional strip cutting problem with sequencing constraint. Eur. J. Oper. Res. 183 (2007) 1371–1384. | DOI | MR | Zbl

L. Simonetti, Y. Frota and C.C. De Souza, An exact method for the minimum caterpillar spanning problem. In: Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Optimization, Paris, France (2009) 48–51.

L. Simonetti, Y. Frota and C.C. De Souza, Upper and lower bounding procedures for the minimum caterpillar spanning problem, Eletron. Notes Discrete Math. 35 (2009) 83–88. | DOI | MR | Zbl

K. Sundar and S. Rathinam, Multiple depot ring star problem: a polyhedral study and exact algorithm. J. Global Optim. 67 (2017) 527–551. | DOI | MR | Zbl

Z. Zhang, H. Qin and A. Lim, A memetic algorithm for the capacitated m-ring-star problem. Appl. Intell. 40 (2014) 305–321. | DOI

Cité par Sources :