Efficient branching rules for optimizing range and order-based objective functions

• 成果类型: Article
• 署名作者: van Rossum, Bart; Chen, Rui; Lodi, Andrea
• 署名单位: Eindhoven University of Technology; The Chinese University of Hong Kong, Shenzhen
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02306-0
• 发表日期: 2026-03
• 页码: 539-572
• 关键词: Range minimization; branch and price; Vehicle Routing; generalized assignment; fairness; WORKLOAD EQUITY; algorithm; price

摘要

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problem-specific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.