Fairness in Combinatorial Optimization

Il existe une grande variété au sein des problèmes d'optimisation combinatoire. Dans un contexte réel, les solutions de tels problèmes requièrent souvent une certaine forme d'équilibre. Cependant, la recherche dans le domaine de l'équilibre en optimisation combinatoire est assez limitée. Nous pouvons également observer que lorsqu'un problème comprend une dimension d'équilibre, elle n'est pas toujours intégrée de façon consciencieuse. Dans cette thèse, nous étudions et nous comparons différentes manières d'intégrer la notion d'équilibre en programmation par contraintes et en programmation en nombres entiers. Nous analysons également les caractéristiques et les propriétés associées au différentes formes d'équilibre. Dans un premier temps, nous étudions le problème du sac à dos multiple quadratique avec des conflits et des contraintes d'équilibre. Dans ce problème, nous cherchons à remplir plusieurs sacs à dos avec des objets de différents poids, et dont il existe une valeur ou un conflit entre chaque paire d'objets. Les contraintes d'équilibre s'assurent que les poids des sacs à dos soient équilibrés. Nous présentons des modèles de programmation par contraintes et de programmation en nombres entiers. Nous touchons également à la génération de colonnes, et utilisons un algorithme de « branch and price. » Nous pouvons ainsi comparer la complexité d'implémentation et la performance de ces modèles. Ce problème peut être appliqué à la formation de plans de tables pour des événements, tels des réceptions de mariage. Dans un deuxième temps, nous nous concentrons sur la méthodologie associée à l'équilibre, et étudions les caractéristiques associées aux différentes formes d'équilibres. Nous présentons quatre manières d'équilibrer des solutions et discutons de leur propriétés. Nous présentons aussi trois problèmes existants où la manière d'atteindre des solutions équilibrées pourrait être améliorée. Ceci nous permet d'émettre plusieurs lignes directrices qui permettraient d'aider un modélisateur à choisir une bonne manière d'équilibrer les solutions d'un problème. Dans un troisième temps, nous étudions un problème particulier, où nous ne considérons pas l'équilibre local à une seule solution, mais plutôt l'équilibre global atteint à l'issue d'une séquence de solutions. À l'aide de certaines preuves théoriques, nous pouvons démontrer, par exemple, le nombre de solutions nécessaires à atteindre un équilibre global parfait, dans certains cas spéciaux. Nous introduisons aussi une structure nous permettant de résoudre ce problème pour des cas plus compliqués. Nous utilisons cette structure pour résoudre le problème de répartition d'ambulances. Un ensemble d'ambulances doit être réparti au travers de différentes zones d'une région, de manière à répondre de façon efficace aux besoins de la population. Cette répartition doit aussi être équitable, lorsque considérée sur une certaine période de temps. Pour résoudre ce problème, nous utilisons la génération de colonnes et la programmation par contraintes.

Abstract

Combinatorial optimization problems come in a plethora of flavors. In a realistic setting, solutions to many of these problems require some sort of balance or fairness. Yet, there has been little research specifically on the concept of fairness and balance in the context of combinatorial optimization. Furthermore, it can be observed that when a problem includes a fairness component, that component is generally not constructed very carefully. This thesis studies and compares various ways of achieving balance in constraint programming and in integer programming, and analyzes the characteristics and propertiesof various balancing methods. In the first part of this thesis, we study the quadratic multiknapsack problem with conflicts and balance constraints, that is, packing items of different weights and with pairwise preferences and conflicts into knapsacks, while satisfying constraints on the balance of the loads of those knapsacks. We present and compare constraint programming and integer programming models, including a model based on column generation and branch and price. This allows us to constrast these models by the difficulty of their implementation, and their resulting performance. The problem studied finds an application in event seating. The second part of this thesis focuses on methodology, and is concerned with the characteristics associated with various ways of achieving balance. We present four different methods of finding balanced solutions in problems, and discuss some of their properties. We further present three cases showing that the way balance is achieved in some existing problems can be improved. These experiments allow us to make a list of general modeling guidelines, which should help a modeler decide on how to best integrate fairness into a problem. For the last part of this thesis, we study a special problem where fairness is considered over a period of time. We show some theoretical proofs for special cases of this problem, allowing us, for instance, to know what length of time is needed to ensure a perfectly fair solution. We then introduce a general framework which allows us to tackle more complicated cases of this problem. We use this framework to solve the ambulance allocation problem: A number of ambulances must be allocated to some zones in a region, such that the population of the region is efficiently covered by the ambulance service. This coverage should also be fair, when considered over a given time horizon. To solve this problem, we introduce a model based on column generation and constraint programming.