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.
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 |
|---|