Scholarlink

<p>We present an exact and generic method for solving the pricing problem in column generation, termed the <i>tree search pricing algorithm (TSPA)</i>. TSPA explores the space of feasible columns via a search tree and identifies all columns with a reduced-cost value below an adaptive threshold. Inspired by an approach from Krumke et al. (in: European symposium on algorithms, Springer, pp 637–648, 2002) for vehicle routing problems, we formalize and generalize this dynamic programming-based method to make it applicable across a wide range of problem classes. To improve efficiency, we derive strong completion bounds that effectively prune the search tree, significantly accelerating the generation of columns and reducing overall solution time. Additionally, we demonstrate that TSPA can be seamlessly combined with lexicographic optimization, to address problems with multiple objectives efficiently. We validate the theoretical results through an extensive computational study on two applications: the sequence-dependent cutting stock problem and the assignment of transport orders to hospital employees. Using real-world data, we demonstrate that TSPA outperforms other pricing approaches for column generation within the <i>restricted master heuristic</i>. For the second application, the column generation approach with TSPA surpasses both an industry-standard heuristic and a standard solver for a polynomial-size MIP formulation in a real-world setting.</p>

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

Lexicographic column generation with a tree search pricing algorithm

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月1日

查看全文
  • Andreas Bärmann,
  • Alexander Müller,
  • Dieter Weninger

摘要

We present an exact and generic method for solving the pricing problem in column generation, termed the tree search pricing algorithm (TSPA). TSPA explores the space of feasible columns via a search tree and identifies all columns with a reduced-cost value below an adaptive threshold. Inspired by an approach from Krumke et al. (in: European symposium on algorithms, Springer, pp 637–648, 2002) for vehicle routing problems, we formalize and generalize this dynamic programming-based method to make it applicable across a wide range of problem classes. To improve efficiency, we derive strong completion bounds that effectively prune the search tree, significantly accelerating the generation of columns and reducing overall solution time. Additionally, we demonstrate that TSPA can be seamlessly combined with lexicographic optimization, to address problems with multiple objectives efficiently. We validate the theoretical results through an extensive computational study on two applications: the sequence-dependent cutting stock problem and the assignment of transport orders to hospital employees. Using real-world data, we demonstrate that TSPA outperforms other pricing approaches for column generation within the restricted master heuristic. For the second application, the column generation approach with TSPA surpasses both an industry-standard heuristic and a standard solver for a polynomial-size MIP formulation in a real-world setting.