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.