A New Branching Rule for Range Minimization Problems & Linear Programming with Pareto-Efficiency Constraints
Abstract
We are thrilled to invite you to the next EI-ERIM-OR seminar by Bart van Rossom on Friday, April 12. The talk will cover two topics, the details of the topics can be found below.
Abstract
A New Branching Rule for Range Minimization Problems
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 is a PhD Candidate at the Econometric Institute. He works with Dennis Huisman and Twan Dollevoet on algorithms for integer problems.
Contact
Please let Olga, Ece or Ruben know if you would like to attend this seminar online or if you would like to have a meeting with the speaker after the seminar.
- Olga Kuryatnikova: kuryatnikova@ese.eur.nl
- Ece Karakoyun: karakoyun@ese.eur.nl
- Ruben van Beesten: vanbeesten@ese.eur.nl
