Component Bound Branching in a Branch-and-Price Framework

Til Mohr ()
Additional contact information
Til Mohr: RWTH Aachen University

A chapter in Operations Research Proceedings 2024, 2025, pp 428-433 from Springer

Abstract: Abstract This paper integrates the component bound branching rule, originally proposed by Vanderbeck et al. [6, 7] and later reformulated by Desrosiers et al. [1], into the branch-price-and-cut solver GCG [2]. This rule, like Vanderbeck’s generic branching scheme [5], operates solely within the Dantzig-Wolfe reformulated problem, where branching decisions often lack corresponding actions in the original formulation. The current GCG framework requires modifications to accommodate such branching rules, particularly within the pricing loop. This paper’s significant contribution is enhancing the GCG architecture to seamlessly integrate new branching rules that operate exclusively on the reformulated problem. This enhancement allows these rules to benefit from current and future improvements in the branch-price-and-cut framework, including dual value stabilization, without necessitating changes to the branching rule itself. We propose an interface to manage such constraints in the master problem that lack counterparts in the original formulation. The generic mastercut interface, integrated into the GCG solver, spans the pricing loop, column generation, and dual value stabilization. The paper concludes with an evaluation, comparing the performance of the component bound branching rule to Vanderbeck’s generic branching scheme, as well as the impact of dual value stabilization on the component bound branching rule’s performance.

Keywords: Column Generation; Branch-and-price; Dantzig-Wolfe reformulation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-92575-7_61

Ordering information: This item can be ordered from
http://www.springer.com/9783031925757

DOI: 10.1007/978-3-031-92575-7_61

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().