A New Branching Rule for Range Minimization Problems

A New Branching Rule for Range Minimization Problems and Linear Programming with Pareto-Efficiency Constraints

Joint with Rui Chen and Andrea Lodi

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 is compatible with any problem-specific branching scheme. We show several desirable properties of range branching and show its effectiveness on the fair capacitated vehicle routing problem and the fair generalized assignment problem. Range branching outperforms 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.

Linear Programming with Pareto-Efficiency Constraints

Joint with Twan Dollevoet

We consider a linear programming problem subject to additional Pareto-efficiency constraints. In particular, we assume that each feasible solution is linearly mapped to a utility vector, and impose that this utility vector is not Pareto-dominated by any other attainable utility vector. We show that this problem is NP-complete and provide some analytical results allowing us to formulate the problem as a bilinear program with exponentially many constraints. We propose a cutting-plane algorithm as well as a tractable reformulation, and compare the performance of both approaches on instances of the generalized assignment problem.

About Bart van Rossum

Bart van Rossum is a PhD Candidate at the Econometric Institute. He works with Dennis Huisman and Twan Dollevoet on algorithms for integer problems.

Coordinator

• Olga Kuryatnikova
• Ece Karakoyun
• Ruben van Beesten