A caterpillar is a 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 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 F. Rinaldi and A. Franz in 2007. We study the polytope associated with a natural integer programming formulation of this problem. We explore basic properties of this polytope, including a lifting lemma and several facet-preserving operations on the graph. These results allow us to introduce several families of facet-inducing inequalities. © 2015 Elsevier B.V.
Documento: | Artículo |
Título: | The caterpillar-packing polytope |
Autor: | Marenco, J. |
Filiación: | Sciences Institute, National University of General Sarmiento, Argentina Computer Science Dept., FCEyN, University of Buenos Aires, Argentina |
Palabras clave: | Caterpillar-packing; Facets |
Año: | 2015 |
Volumen: | 50 |
Página de inicio: | 47 |
Página de fin: | 52 |
DOI: | http://dx.doi.org/10.1016/j.endm.2015.07.009 |
Título revista: | Electronic Notes in Discrete Mathematics |
Título revista abreviado: | Electron. Notes Discrete Math. |
ISSN: | 15710653 |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p47_Marenco |