Search

National audience; This article proposes a new perspective for understanding electoral maps, using computational social science to study the criteria which shape how electoral districts are drawn up in France. Defining the boundaries of legislative constituencies is a complex task, given its technical dimension and the various demographic, geographic, and legal criteria that must be respected. Looking at demographic and geographic territorial data and the whole of the admissible redistrictings, we evaluate the criteria-based constraints on the empirical possibilities of the electoral map and, more broadly, we highlight the value of using computer for the map making of the electoral constituencies redistricting.; Cet article propose une nouvelle perspective d’étude de la carte électorale, fondée sur la computational social science, pour analyser les critères qui encadrent la réalisation du découpage électoral en France. La délimitation des circonscriptions législatives est complexe en raison de sa dimension technique et des critères juridiques, démographiques et géographiques à respecter. À partir des données démographiques et géographiques des territoires et de la mesure de l’ensemble des découpages admissibles, nous évaluons les contraintes formées par les critères sur les potentialités empiriques de la carte électorale et, plus largement, nous montrons l’intérêt d’avoir recours aux découpages assistés par ordinateur.

If the instance of an optimization problem changes, an initial solution may become suboptimal or infeasible. It is then necessary to compute a new solution, but it is also desirable to keep some decisions from the initial solution unchanged. In this thesis we propose the anchoring criterion to favor unchanged decisions between solutions. In a reoptimization setting, the goal is to find a new solution while keeping a maximum number of decisions from the initial solution. In a robust 2-stage optimization setting, we propose the anchor-robust approach to compute in advance a baseline solution, along with a subset of so-called anchored decisions. For any realization in the considered uncertainty set, it is possible to repair the baseline solution into a new solution without changing anchored decisions. The anchor-robust approach allows for a trade-off between the cost of a solution and guaranteed decisions. Anchoring problems are formally defined and studied on two problem classes. The first one is the class of integer programs in binary variables, including classical polynomial problems such as spanning trees. The second one is project scheduling, where jobs must be scheduled under precedence only, or precedence and resource constraints. The complexity of anchoring problems is analyzed. Combinatorial properties of anchored solutions are exhibited, and dedicated algorithmic and polyhedral approaches are devised. Mixed-integer programming techniques are investigated, that highlight the practical implementability of anchoring problems.; Si les données d'un problème d'optimisation combinatoire changent, une solution initiale peut devenir sous-optimale ou infaisable. Il est alors nécessaire de calculer une nouvelle solution, mais aussi souhaitable de maintenir les décisions prises dans la solution initiale. Dans cette thèse nous proposons le critère d'ancrage pour favoriser les décisions inchangées entre solutions. En réoptimisation, il s'agit de trouver une solution conservant un nombre maximal de décisions d'une solution initiale. En optimisation robuste à deux étapes, nous proposons l'approche robuste-ancrée, qui consiste à calculer en avance une solution baseline et un sous-ensemble de décisions dites ancrées. Pour toute réalisation des données dans l'ensemble d'incertitude considéré, on peut réparer la solution baseline en une nouvelle solution sans changer les décisions ancrées. Cette approche permet un compromis entre le coût de la solution et les garanties sur les décisions. Les problèmes d'ancrage sont formalisés et déclinés sur deux classes de problèmes. La première est celle des programmes linéaires en variables binaires, et notamment des problèmes polynomiaux classiques comme l'arbre couvrant. La deuxième est celle des problèmes d'ordonnancement de projet, où des tâches doivent être ordonnancées sous des contraintes de précédences ou de ressources. La complexité algorithmique des problèmes d'ancrage est analysée. Les propriétés combinatoires des solutions ancrées sont étudiées, et permettent la conception d'approches algorithmiques et polyédrales dédiées. Des techniques de programmation linéaire en nombres entiers sont mises en œuvre, démontrant l'implémentabilité des problèmes d'ancrage.

National audience

A project scheduling framework is considered where processing times of jobs lie in some uncertainty set. The decision maker needs to compute a baseline schedule in advance, while guaranteeing that some jobs may not be rescheduled later. A subset of jobs is said to be anchored with respect to a baseline schedule if for any realization of processing times in the uncertainty set, the baseline schedule can be repaired in a second stage without changing the starting times of anchored jobs. Each job has an anchoring weight. The Anchor-Robust Project Scheduling Problem (AnchRobPSP) is to find in a first stage a baseline schedule satisfying a given deadline, and a subset of anchored jobs with maximum total weight. AnchRobPSP is considered for several uncertainty sets, such as box or budgeted uncertainty set, and dedicated graph models are presented. AnchRobPSP is shown to be NP-hard even for budgeted uncertainty. Polynomial or pseudo-polynomial algorithms are devised for box uncertainty and special cases of budgeted uncertainty. Numerical experiments for AnchRobPSP under budgeted uncertainty are presented. AnchRobPSP solutions are compared to those of state-of-the-art robust techniques. Finally it is shown how to achieve a trade-off between the number of anchored jobs and the makespan of the baseline schedule.

National audience

International audience