A general cut-generating strategy for the caterpillar-packing polytope

  • A caterpillar is a connected graph such that the removal of all its vertices with degree 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:1371–1384, 2007) We show new facet-preserving procedures for this polytope, and we present a general cut-generating strategy based on these procedures. Computational experiments show that this approach is effective in practice.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Javier Marenco
DOI:https://doi.org/10.1007/s12532-025-00283-1
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2025
Volume:17
Issue:4
Page Number:32
First Page:699
Last Page:730
Mathematical Programming Computation :MPC 2025 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.