Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Dans cette thèse nous considérons une classe de problèmes d’optimisation ayant une particularité : des décisions à la fois discrètes et continues doivent être prises simultanément. Ces problèmes se posent dans de nombreuses applications pratiques, comme par exemple dans les réseaux de télécommunications à large bande passante et dans les problèmes de transport écologique, où les ressources disponibles peuvent être très légèrement consommées ou réparties. Ces problèmes se sont avérés être plus difficiles à résoudre que leurs homologues purement discrets. Des méthodes efficaces pour la résolution de ces problèmes sont proposées dans cette thèse. Notre approche est de prendre en compte des variantes de problèmes classiques d’optimisation combinatoire appartenant à trois domaines : packing, routage et routage/ packing intégré. Les résultats obtenus suggèrent l’existence de méthodes efficaces, réduisant l’effort de calcul nécessaire pour résoudre ce type de problème. La plupart du temps, ces méthodes sont basées sur l’exploitation de la structure des solutions optimales pour réduire l’espace de recherche. / In this thesis we consider a class of optimization problems having adistinctive feature : both discrete and continuous decisions need to betaken simultaneously. These problems arise in many practical applications,for example broadband telecommunications and green transportation problems, where resources are available, that can be fractionally consumed or assigned. These problems are proven of being harder than their purely discrete counterpart. We propose effective methodologies to tackle them. Our approach is to consider variants of classical combinatorial optimization problems belonging to three domains : packing, routing, and integrated routing / packing. Our results suggest that indeed effective approaches exist, reducing the computational effort required for solving the problem. Mostly, they arebased on exploiting the structure of optimal solutions to reduce the search space. / In questa tesi affrontiamo una classe di problemi di ottimizzazione con una caratteristica in comune : sia le decisioni discrete che quelle continue devono essere prese simultaneamente. Questi problemi emergono in molti campi, come ad esempio le nelle telecomunicazioni abanda larga e in problemi di trasporto ecologico, dove le risorse disponibili possono essere consumate o assegnate in modo frazionario.Questi problemi sono generalmente più difficili da risolvere rispetto alla loro controparte puramente combinatoria. Noi proponiamo metodologie efficaci per affrontarli. Con il nostro approccio consideriamo varianti di problemi classici nel campo dell’ottimizzazione combinatoriache appartengono a tre domini : impaccamento, instradamento einstradamento / impaccamento integrati. I nostri risultati suggeriscono l’esistenza di approcci efficienti che riducono lo sforzo computazionale necessario per risolvere questi problemi. Nella maggior parte deicasi, tali approcci sono basati sullo sfruttamento di particolari proprietà della struttura delle soluzioni ottime in modo da ridurre lo spaziodi ricerca.

Este trabalho tem como propósito realizar um estudo sobre a vinculação de receitas públicas, com especial atenção para o ordenamento brasileiro. Considera-se o caráter jurídico das vinculações, bem como os prós e contras de sua utilização, cotejando com uma exposição acerca do caráter econômico e político destes institutos. Diante disto, realiza-se uma análise dos critérios temporais, além de sua tipologia e classificação quanto aos efeitos e funções. No ordenamento brasileiro, existem vinculações na sua modalidade stricto sensu ou então na forma de garantia (vinculações-garantia). Há ainda algumas vinculações que são assim chamadas de forma imprópria, como as vinculações para o federalismo fiscal e as despesas mínimas obrigatórias. Após uma análise das vinculações, passa-se para o estudo do princípio da não afetação e sua inter-relação com os princípios da unidade, universalidade e outros também correlatos. A tendência seguida no trabalho é que, apesar das diferenciações entre estes princípios, a sua análise integrativa pode ser proveitosa com o escopo de se atingir os desideratos desejados. Por derradeiro, faz-se uma abordagem dos mecanismos mitigadores das afetações e do princípio da não vinculação de receitas no ordenamento pátrio, sem prescindir da observância aos modelos estrangeiros. Os fundos específicos são os instrumentos mais utilizados no Brasil para se operacionalizar uma vinculação. Porém, com o inchaço da atividade estatal e o consequente aumento das vinculações, verifica-se a criação de um instrumento peculiar a fim de atenuar esta realidade: a Desvinculação das Receitas da União DRU. / Le but de ce travail est de réaliser une étude sur laffectation des recettes publiques, avec une attention particulière à la réglementation brésilienne. On considère langle juridique des affectations, les avantages et les inconvénients de leur utilisation, ainsi quune comparaison avec ses caractères économique et politique de ces instituts. Pour cela, il analyse les critères temporels et établit leur typologie et une classification des effets et des fonctions poursuivis. Dans le système juridique brésilien, peu daffectations sont stricto sensu ou ont un rôle de garantie (affectation-garantie). Certaines affectations sont ainsi faussement nommées, telles que les affectations au fédéralisme fiscal et les dépenses minimales obligatoires. Après lanalyse des affectations, il est nécessaire deffectuer une étude sur le principe de la non-affectation, sa relation avec les principes d\'unité, d\'universalité, ainsi que sa connexion à dautres principes équivalents. En dépit des différences entre ces principes, lidée poursuivie dans ce travail est que la convergence de ces approches peut être bénéfique aux objectifs escomptés. Enfin, une description du mécanisme qui mitige les affectations et le principe de la non-affectation du système juridique brésilien est élaborée, prenant en compte aussi les modèles étrangers. Les fonds spécifiques sont les instruments utilisés au Brésil pour produire une affectation. Cependant, avec laugmentation des l\'activités du gouvernement et la conséquente surexploitation des affectations, la création d\'un outil particulier pour atténuer cette réalité peut être observée: la Désaffectation des Recettes Fédéral DRU.

La résolution efficace de problèmes d'optimisation à permutation de grande taille nécessite le développement de méthodes hybrides complexes combinant différentes classes d'algorithmes d'optimisation. L'hybridation des métaheuristiques avec les méthodes exactes arborescentes, tel que l'algorithme du branch-and-bound (B&B), engendre une nouvelle classe d'algorithmes plus efficace que ces deux classes de méthodes utilisées séparément. Le défi principal dans le développement de telles méthodes consiste à trouver des liens ou connections entre les stratégies de recherche divergentes utilisés dans les deux classes de méthodes. Les Algorithmes Génétiques (AGs) sont des métaheuristiques, à base de population, très populaires basés sur des opérateurs stochastiques inspirés de la théorie de l'évolution. Contrairement aux AGs et aux métaheuristiques généralement, les algorithmes de B&B sont basés sur l'énumération implicite de l'espace de recherche représenté par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation consiste à définir un codage commun des solutions et de l'espace de recherche ainsi que des opérateurs de recherche adéquats afin de permettre un couplage efficace de bas niveau entre les deux classes de méthodes AGs et B&B. La représentation de l'espace de recherche par le moyen d'arbres est traditionnellement utilisée dans les algorithmes de B&B. Dans cette thèse, cette représentation a été adaptée aux métaheuristiques. L'encodage des permutations au moyen de nombres naturels faisant référence à l'ordre d'énumération lexicographique des permutations dans l'arbre du B&B, est proposé comme une nouvelle manière de représenter l'espace de recherche des problèmes à permutations dans les métaheuristiques. Cette méthode de codage est basée sur les propriétés mathématiques des permutations, à savoir les codes de Lehmer et les tables d'inversions ainsi que les système d'énumération factoriels. Des fonctions de transformation permettant le passage entre les deux représentations (permutations et nombres) ainsi que des opérateurs de recherche adaptés au codage, sont définis pour les problèmes à permutations généralisés. Cette représentation, désormais commune aux métaheuristiques et aux algorithmes de B&B, nous a permis de concevoir des stratégies d'hybridation et de collaboration efficaces entre les AGs et le B&B. En effet, deux approches d'hybridation entre les AGs et les algorithmes de B&B (HGABB et COBBIGA) basés sur cette représentation commune ont été proposées dans cette thèse. Pour validation, une implémentation a été réalisée pour le problème d'affectation quadratique à trois dimension (Q3AP). Afin de résoudre de larges instances de ce problème, nous avons aussi proposé une parallélisation pour les deux algorithmes hybrides, basée sur des techniques de décomposition d'espace (décomposition par intervalle) utilisées auparavant pour la parallélisation des algorithmes de B&B. Du point de vue implémentation, afin de faciliter de futurs conceptions et implémentations de méthodes hybrides combinant métaheuristiques et méthodes exacte arborescentes, nous avons développé une plateforme d'hybridation intégrée au logiciel pour métaheuristiques, ParadisEO. La nouvelle plateforme a été utilisée pour réaliser des expérimentations intensives sur la grille de calcul Grid'5000. / Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization methods. Indeed, it is now acknowledged that such methods perform better than traditional optimization methods when used separately. The key challenge is how to find connections between the divergent search strategies used in each class of methods in order to build efficient hybridization strategies. Genetic algorithms (GAs) are very popular population-based metaheuristics based on stochastic evolutionary operators. The hybridization of GAs with tree-based exact methods such as Branch-and-Bound is a promising research trend. B&B algorithms are based on an implicit enumeration of the solution space represented as a tree. Our hybridization approach consists in providing a common solution and search space coding and associated search operators enabling an efficient cooperation between the two methods. The tree-based representation of the solution space is traditionally used in B&B algorithms to enumerate the solutions of the problem at hand. In this thesis, this special representation is adapted to metaheuristics. The encoding of permutations as natural numbers, which refer to their lexicographic enumeration in the tree, is proposed as a new way to represent the solution space of permutation problems in metaheuristics. This encoding approach is based on the mathematical properties of permutations (Lehmer codes, inversion tables, etc.). Mapping functions between the two representations (permutations and numbers) and special search operators adapted to the encoding are defined for general permutation problems, with respect to the theory of representation. This common representation allows the design of efficient cooperation strategies between GAs and B\&B algorithms. In this thesis, two hybridization schemes combining GAs with B\&B based on this common representation are proposed. The two hybridization approaches HGABB/HAGABB (Hybrid Adaptive GA-B\&B) and COBBIGA (cooperative B&B interval-based GA), have been validated on standard benchmarks of one of the hardest permutation-based problems, the three dimensional quadratic assignment problem (Q3AP). In order to solve large benchmarks of permutation-based problems, a parallelization for computational grids is also proposed for the two hybrid schemes. This parallelization is based on space decomposition techniques (the decomposition by intervals) used in parallel B\&B algorithms. From the implementation point of view, in order to facilitate further design and implementation of hybrid methods combining metaheuristics with tree-based exact methods, a hybridization C++ framework integrated to the framework for metaheuristics ParadisEO is developed. The new framework is used to conduct extensive experiments over the computational grid Grid'5000.

Thèses (LL.M.)--Université de Sherbrooke (Canada), 1997. / Titre de l'écran-titre (visionné le 19 juillet 2006). Publié aussi en version papier.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse étudie l'affectation centralisée des enseignants aux écoles et un nouveau modèle d'appariement inspirée par cette dernière.Dans le premier chapitre, nous développons un modèle théorique de réaffectation afin d'étudier le problème de réaffecter des enseignants titulaires enseignant au sein d'un établissement et demandant une mutation. Le problème est similaire à celui d'affecter des élèves dans des écoles. Dans ce cas, l'algorithme à Acceptation Différée a été identifié comme étant le seul algorithme qui: i) est stable, ii) efficace et qui iii) incite les élèves à soumettre sincèrement leurs préférences. La différence principale avec le problème d'affecter des élèves aux écoles est que les enseignants ont déjà une position initiale au sein d'un établissement. On doit donc prendre en compte une contrainte additionnelle, la Rationalité Individuelle (RI): un enseignant doit être affecté dans un établissement qu'il préfère faiblement à son établissement d'origine. Pour prendre en compte cette contrainte, une modification de l'algorithme à Acceptation Différée a été identifiée dans la littérature académique et utilisé en pratique pour affecter les enseignants aux écoles en France. Nous montrons que cet algorithme modifié souffre d'un important défaut: il n'est pas efficace au sens fort. Il est en effet possible de réaffecter les enseignants aux écoles de telle sorte que: i) les enseignants obtiennent une école qu'ils préfèrent et ii) les écoles obtiennent des enseignants mieux classés. Partant de ce constat, nous identifions la classe de tous les algorithmes, les algorithmes Block-Exchange (BE), qui ne souffrent pas de ce défaut. Parmi eux, nous montrons qu'il en existe un unique qui incite les enseignants à soumettre leurs préférences sincèrement: le Teacher Optimal Block-Exchange algorithm (TO-BE). En utilisant un modèle de marché large, nous montrons théoriquement que ces algorithmes ont de meilleures performances en termes de mouvement et de bien-être des enseignants que l'algorithme actuel. Nous utilisons ensuite une base de données sur l'affectation des enseignants aux écoles du secondaire en France en 2013 pour quantifier les gains possibles que nos algorithmes peuvent apporter. Dans un cadre de réaffectation pur sans enseignant néotitulaire et places vacantes, nous montrons qu'il est possible de plus que double le nombre d'enseignants obtenant une nouvelle affectation.Dans le second chapitre, nous concevons un algorithme pratique, inspiré de nos résultats du chapitre précédent, pour la procédure française d'affectation des enseignants du secondaire. Plus globalement, cette conception a également pour but de fournir un outil face à deux problèmes importants communs aux pays de l'OCDE: i) le manque d'attractivité de la profession enseignants et ii) les importantes inégalités de réussites des élèves issus de milieux sociaux différents. Nous considérons l'ensemble du marché français composé des enseignants titulaires demandant une réaffectation, les enseignants sans affectation initiale et des places vacantes. Améliorer la mobilité des enseignants permet de leur donner de meilleures perspectives de carrière ce qui peut potentiellement attirer plus d'entrants dans la profession. Mais cette mobilité accrue peut entrainer l'affectation de plus d'enseignants peu expérimentés au sein d'académies déjà très défavorisées, affectant in fine la réussite des élèves au sein de celles-ci. Nous proposons un algorithme flexible qui permet de mieux contrôler le mouvement et la distribution des enseignants au sein de régions, notamment celles très désavantagées. En utilisant les données françaises d'affectation de 2013, nous simulons plusieurs scénarios contre factuels et montrons que notre algorithme peut prendre en compte plusieurs objectifs de politique publique. / This thesis studies the centralized assignment of teachers to schools and a new matching framework inspired by it. In the first chapter, we develop a theoretical model of reassignment to study the problem of reassigning tenured teachers who already have a position and are willing to move to another school. The problem is similar to the one of assigning students to schools. In this case, the well known Deferred Acceptance algorithm has been identified as the only algorithm that: i) is stable ii) efficient and iii) gives incentives to students to report their true preferences. The main difference with the problem of assigning students to schools is that teachers have an initial assignment. One has to consider an additional constraint, Individual Rationality (IR): a teacher must receive a school that he weakly prefers to his initial one. To incorporate this constraint, a modification of the Deferred Acceptance algorithm has been identified in the academic literature and used in practice to assign teachers to schools in France. We show that this modified algorithm has a serious drawback: it is not efficient in a strong sense. Indeed, it is possible to reassign teachers to schools such that both: i) teachers obtain a school that they prefer and ii) schools are assigned teachers that they rank higher. Thus, we identify the class of all algorithms, the Block-Exchange (BE) algorithms, that do not suffer from this drawback. Among them, we show that there is a unique one that gives good incentives to teachers to report their true preferences, the Teacher Optimal Block-Exchange algorithm (TO-BE). In using a large market setting, we theoretically show that these algorithms perform better in terms of movement and welfare for teachers than the currently used one. We then use a dataset on the assignment of teachers to schools in France in 2013 to quantify the possible gains that can bring our algorithms. In a reassignment setting with no newly tenured teachers or empty seats, we show that we can more than double the number of teachers obtaining a new assignment. In the second chapter, we aim to design a practical algorithm, inspired by our findings in the previous chapter, for the French assignment system of teachers to schools. More generally, this design also aims to provide a tool about two important issues common to OECD countries: i) the lack of attractiveness of the teaching profession and ii) the high achievement inequality between students from different social backgrounds. We consider the complete French market composed of tenured teachers looking for a reassignment, newly tenured teachers with no initial assignment and empty positions. In improving the mobility of teachers, one can give them better career perspectives and so potentially attract more teachers into the profession. But in doing so, it can also hurt deprived regions in assigning more teachers with low experience to them and ultimately the students from these regions. We propose a flexible algorithm that allows to better control the movement and distribution of teachers across regions, especially deprived ones. Using the data of the French assignment of teachers in 2013, we simulate several counter factuals and show that our algorithm can accommodate a wide range of policy objectives.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Saisir la relation de l’État aux utilités qu’un logement social est à même d’offrir, tel est le fondement de cette étude. La relation entre propriété publique et logement social, aisément perceptible en cas de mobilisation des propriétés publiques en vue de la réalisation d’une opération de logement social ou de propriété publique d’un logement social, exige pour être pleinement appréhendée de reconsidérer l’approche de la propriété en droit public, comme elle l’est au demeurant en droit privé. Retenant une approche dite « structurale », la propriété publique est alors entendue, matériellement, comme une chose publique, en raison de la nature publique de la personne qui exerce une maîtrise sur cette chose, elle-même considérée comme une somme d’utilités, et formellement, comme le droit de propriété public, en raison de la nature publique du titulaire de ce droit, lui-même défini comme le pouvoir de jouir et de disposer, sauf sources d’obligations contraires, de toutes les utilités qu’une chose est à même d’offrir. En matière de logement social, l’État est non seulement titulaire d’un droit personnel sur le bailleur de logement social, mais également d’un droit réel passif sur l’habitation locative affectée au service public. Autrement dit, en encadrant le pouvoir de jouir et de disposer du bailleur, l’État se réserve la valeur de l’habitation locative affectée à due proportion du financement public de l’activité de logement social, et cela sans en être formellement propriétaire. Finalement, à l’instar de la large confusion de l’histoire du logement avec l’évolution de la conception de la propriété, l’histoire du logement social se confond largement avec l’évolution proposée de la conception de la propriété publique. / Understand the relationship of the State to utilities that social housing is able to offer, specifically the distribution of rights and obligations in connection or on a rental housing assigned to the public service of social housing, is the foundation of our study. The relationship between public ownership and social housing, easily perceptible in case of mobilization of public properties for the realization of a housing project or public ownership of social housing, requires to be fully understood to reconsider the approach to ownership in public law, as it is in any private law. Neither the « classic » approach nor the « renovated » one of the property can grip the right owned by the State on social housing, only a « structural » approach allows. Based on this approach, public ownership is then heard, materially, as a public thing, because of the public nature of the person who exercises control over this thing, itself considered as a sum of utilities, and formally, as the right to public property, because of the public nature of the copyright owner, itself defined as the power to enjoy and dispose unless otherwise sources obligations of all the utilities that a thing is even to offer. In social housing, the State is not only holds a personal right on the provider of social housing, as it is traditionally on any manager of a public service, but also a real right on liability rental housing assigned to the public service of social housing. In other words, framing the power to enjoy and dispose of social housing landlord, the State reserves the value of rental housing affected in due proportion of the public funding of social housing activity, and this without being formal owner. Thus, the State controls the use value and exchange value of social housing yet belonging to others. Finally, like the wide confusion in the history of housing with the evolution of the design of the property, the history of social housing is largely coincides with the evolution of the design of public property.