Range Minimization and Fairness over Time

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.

Speaker

Bart van Rossum

Erasmus University Rotterdam

Date

Friday 8 Dec 2023, 12:00 - 13:00

Type

Seminar

Room

ET-14

Building

E Building

Add to calendar

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.