Range Minimization and Fairness over Time

EI-ERIM-OR seminar
Image of campus Woudestein
Bart van Rossum
Friday 8 Dec 2023, 12:00 - 13:00
E Building
Add to calendar
Image of campus Woudestein

There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers.

Joint with Rui Chen and Andrea Lodi (Cornell Tech)

This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy.

A New Branching Rule for Range Minimization Problems

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 a series of fair capacitated vehicle routing instances.

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.

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, such as vehicle routing and crew scheduling.

More information

Lunch will be provided (vegetarian option included).

For more information please contact the Secretariat Econometrics at eb-secr@ese.eur.nl

Compare @count study programme

  • @title

    • Duration: @duration
Compare study programmes