Range Minimization and Fairness over Time

Bart van Rossum will present two of his recent research topics, both of which are joint with Rui Chen and Andrea Lodi of Cornell Tech. The details of the topics can be found below. Please contact Olga Kuryatnikova, the coordinator of this seminar, to schedule a meeting with the speaker after the seminar. 

Optimizing Fairness over Time with Homogeneous Workers

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. 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.