Scholarlink

<p>A <i>caterpillar</i> is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph <i>G</i>, a <i>caterpillar-packing of G</i> is a set of vertex-disjoint (not necessarily induced) subgraphs of <i>G</i> 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 <i>2-schemes strip cutting problem with a sequencing constraint</i> (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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年5月15日

查看全文
  • Javier Marenco

摘要

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