O planejamento operacional de redes de média e baixa tensão consiste em determinar as melhores intervenções a serem aplicadas nas redes atuais de forma a otimizar os investimentos e atender aos critérios técnicos de operação. Na Média Tensão (MT) são usuais alterações como alocação de capacitores, alteração de cabos e remanejamento de cargas para obter uma melhoria para o sistema. Normalmente os objetivos são a minimização de perdas, melhora do nível de tensão e redução do custo das intervenções realizadas. Na Baixa Tensão (BT) são aplicadas intervenções relacionadas a substituição de cabos, alteração da posição do transformador e balanceamento de cargas. As alterações propostas visam melhorar os índices de equilíbrio de cargas, carregamento de transformadores e queda de tensão ao longo da rede MT e BT. Neste trabalho considera-se a minimização dos investimentos para a realização de alterações nos alimentadores e circuitos de BT, levando em conta a inserção de Geração Distribuída (GD) como solução alternativa. As dificuldades do problema de otimização resultam do tamanho dos sistemas reais e da possibilidade de alternativas que podem ser aplicadas durante o estudo. Para resolver o problema de explosão combinatória resultante das possíveis combinações de alternativas, os modelos propostos neste trabalho utilizam técnicas de computação evolutiva. Os modelos desenvolvidos respeitam aspectos técnicos e econômicos envolvidos em cada solução. A metodologia é aplicada em uma rede real partindo-se de uma base de dados georrefenciada. / The operational planning of medium and low voltage networks consists in determining the best interventions to be applied to existing networks in order to optimize investments and meet the technical criteria for operation. In the Medium Voltage (MV) capacitor allocation, recabling and relocation of loads are useful to achieve an improvement to the system. Usually the objectives are power losses minimization, voltage level improvement and cost reduction of the interventions carried out. In the Low Voltage (LV) interventions for replacing cables and transformer position and load relocation are commonly considered. The proposed changes are aimed at improving the load balance, transformer loading and voltage drops across LV network circuits. This work considers the investment minimization to intervene inMV and LV networks, considering Distributed Generation (DG) insertion as an alternative solution. The dificulties of optimization problem result from the size of the real systems and the possibility of alternatives that can be applied during the study. In order to solve the combinatorial explosion problem resulting from possible combinations of alternatives, the model proposed in this work uses evolutionary computational techniques. The developed models take into account technical and economical aspects involved in each solution. The methodology is applied in a real network starting from a georeferenced database.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

by Lo Kam Ming. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 107-111). / Chapter 1 --- Introduction --- p.7 / Chapter 1.1 --- The Goal --- p.8 / Chapter 1.2 --- The Work of the Thesis --- p.9 / Chapter 1.3 --- Layout of Thesis --- p.9 / Chapter 2 --- The Unit Commitment Problem --- p.11 / Chapter 2.1 --- What is UCP? --- p.11 / Chapter 2.1.1 --- Why is UCP difficult? --- p.12 / Chapter 2.1.2 --- Costs --- p.12 / Chapter 2.1.3 --- Constraints --- p.13 / Chapter 2.2 --- Mathematical Formulation --- p.15 / Chapter 2.3 --- Literature Review --- p.19 / Chapter 2.3.1 --- Exhaustive Enumeration --- p.19 / Chapter 2.3.2 --- Priority List --- p.20 / Chapter 2.3.3 --- Langragian Relaxation --- p.21 / Chapter 2.3.4 --- Neural Network --- p.21 / Chapter 2.3.5 --- Genetic Algorithms --- p.22 / Chapter 2.3.6 --- Dynamic Programming --- p.22 / Chapter 3 --- Genetic Algorithms --- p.24 / Chapter 3.1 --- Introduction --- p.24 / Chapter 3.1.1 --- Outline of Traditional GA --- p.25 / Chapter 3.2 --- Basic elements --- p.26 / Chapter 3.2.1 --- Coding --- p.26 / Chapter 3.2.2 --- Fitness Function --- p.26 / Chapter 3.2.3 --- Selection and Reproduction --- p.26 / Chapter 3.2.4 --- Mutation --- p.28 / Chapter 3.2.5 --- Replacement --- p.29 / Chapter 3.2.6 --- Epistasis --- p.29 / Chapter 3.2.7 --- A Simple Example --- p.30 / Chapter 3.3 --- Exploration vs Exploitation --- p.33 / Chapter 3.4 --- Constraints Handlings --- p.34 / Chapter 3.4.1 --- Penalty Function --- p.35 / Chapter 3.4.2 --- Proper Encoding --- p.36 / Chapter 3.4.3 --- Repair Algorithms --- p.36 / Chapter 4 --- Dynamic Programming --- p.37 / Chapter 4.1 --- Introduction --- p.37 / Chapter 4.1.1 --- Decomposition --- p.38 / Chapter 4.2 --- Mathematical Formulation --- p.43 / Chapter 4.3 --- A Simple Example --- p.44 / Chapter 5 --- DP Crossover Operator (DPX) --- p.50 / Chapter 5.1 --- Why DP is chosen as the crossover operator --- p.50 / Chapter 5.2 --- What is DPX? --- p.51 / Chapter 5.2.1 --- A Simple Example --- p.51 / Chapter 5.2.2 --- Mechanism of DPX --- p.58 / Chapter 5.3 --- Properties of DPX --- p.63 / Chapter 5.3.1 --- Number of parents --- p.63 / Chapter 5.3.2 --- Crossover Sites --- p.65 / Chapter 5.3.3 --- Perservation of Feasibility --- p.66 / Chapter 6 --- Implementation --- p.69 / Chapter 6.1 --- GA Construction --- p.69 / Chapter 6.1.1 --- Coding --- p.69 / Chapter 6.1.2 --- Fitness Function --- p.70 / Chapter 6.1.3 --- Selection --- p.72 / Chapter 6.1.4 --- Crossover --- p.76 / Chapter 6.1.5 --- Mutation Rate --- p.76 / Chapter 6.1.6 --- Replacement --- p.77 / Chapter 6.2 --- Algorithm --- p.77 / Chapter 6.3 --- Optimal Power Generations for Fuel Costs --- p.80 / Chapter 6.3.1 --- The Simple Scheduling Method --- p.80 / Chapter 7 --- Experimental Results --- p.84 / Chapter 7.1 --- Experiment Details --- p.84 / Chapter 7.2 --- Problem A --- p.86 / Chapter 7.2.1 --- Data Results --- p.86 / Chapter 7.2.2 --- Graphical Results --- p.90 / Chapter 7.2.3 --- Analysis --- p.90 / Chapter 7.3 --- Problem B --- p.92 / Chapter 7.3.1 --- Data Results --- p.92 / Chapter 7.3.2 --- Graphical Results --- p.94 / Chapter 7.3.3 --- Analysis --- p.96 / Chapter 8 --- Conclusion and Future Work --- p.97 / Chapter 8.1 --- Conclusion --- p.97 / Chapter 8.2 --- Future Work --- p.98 / Chapter A --- Problems Parameters --- p.100 / Chapter A.1 --- Problem A --- p.100 / Chapter A.1.1 --- Parameters of Generating Units --- p.101 / Chapter A.2 --- Problem B --- p.103 / Chapter A.2. --- 1 Parameters of Generating Units --- p.104

For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class a class of random structures. Random structures form good models of many real world problems, in particular real networks and disordered media. For many such problems, the systems under consideration can be very large, and we often care about whether a property holds most of the time. In particular, for a given class of random structures, we say that a property holds with high probability if the probability that that property holds tends to one as the size of the structures increase. We examine several classes of random structures with real world applications, and look at some properties of each that hold with high probability. First we look at percolation in 3 dimensional lattices, giving a method for producing rigorous confidence intervals on the percolation threshold. Next we look at random geometric graphs, first examining the connectivity thresholds of nearest neighbour models, giving good bounds on the threshold for a new variation on these models useful for modelling wireless networks, and then look at the cop number of the Gilbert model. Finally we look at the structure of random sum-free sets, in particular examining what the possible densities of such sets are, what substructures they can contain, and what superstructures they belong to.

The central nervous system (CNS) has an astonishing diversity of neurons and glia. The diversity of cell types in the CNS has greatly increased throughout evolution and underlies our unique cognitive abilities. The diverse neurons and glia in the CNS are made from a relatively small pool of neural stem cells and progenitors. Understanding the developmental mechanisms that generate diverse cell types from neural progenitors will provide insight into the complexity of the mammalian CNS and guide stem cell based therapies for brain repair. Temporal patterning, during which individual neural progenitors change over time to make different neurons and a glia, is essential for the generation of neural diversity. However, the regulation of temporal patterning is poorly understood. Human outer subventricular zone (OSVZ) neural stem cells and Drosophila type II neural stem cells (called neuroblasts) both generate transit-amplifying intermediate neural progenitors (INPs). INPs undergo additional rounds of cell division to increase the number of neurons and glia generated in neural stem cell lineages. However, it is unknown whether INPs simply expand the numbers of a particular cell type or make diverse neural progeny. In this dissertation, I show that type II neuroblast lineages give rise to extraordinary neural diversity in the Drosophila adult brain and contribute diverse neurons to a major brain structure, the central complex. I find that INPs undergo temporal patterning to expand neural diversity in type II lineages. I show that INPs sequentially generate distinct neural subtypes; that INPs sequentially express Dichaete, Grainyhead, and Eyeless transcription factors; and that these transcription factors are required for the production of distinct neural subtypes. Moreover, I find that parental type II neuroblasts also sequentially express transcription factors and generate different neuronal/glial progeny over time, providing a second temporal identity axis. I conclude that neuroblast and INP temporal patterning axes act combinatorially to specify diverse neural cell types within adult central complex; OSVZ neural stem cells may use similar mechanisms to increase neural diversity in the human brain. This dissertation includes previously published co-authored material.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Les Problèmes d’Optimisation Combinatoire (COP) sont largement utilisés pour modéliser et résoudre un grand nombre de problèmes industriels. La résolution de ces problèmes pose un véritable défi en raison de leur inhérente difficulté, la plupart étant NP-difficiles. En effet, les COP sont difficiles à résoudre par des méthodes exactes car la taille de l’espace de recherche à explorer croît de manière exponentielle par rapport à la taille du problème. Les méta-heuristiques sont souvent les méthodes les plus efficaces pour résoudre les problèmes les plus difficiles. Malheureusement, bien des problèmes réels restent hors de portée des meilleures méta-heuristiques. Le parallélisme permet d’améliorer les performances des méta-heuristiques. L’idée de base est d’avoir plusieurs instances d’une méta-heuristique explorant de manière simultanée l’espace de recherche pour accélérer la recherche de solution. Les meilleures techniques font communiquer ces instances pour augmenter la probabilité de trouver une solution. Cependant, la conception d’une méthode parallèle coopérative n’est pas une tâche aisée, et beaucoup de choix cruciaux concernant la communication doivent être résolus. Malheureusement, nous savons qu’il n’existe pas d’unique configuration permettant de résoudre efficacement tous les problèmes. Ceci explique que l’on trouve aujourd’hui des systèmes coopératifs efficaces mais conçus pour un problème spécifique ou bien des systèmes plus génériques mais dont les performances sont en général limitées. Dans cette thèse nous proposons un cadre général pour les méta-heuristiques parallèles coopératives (CPMH). Ce cadre prévoit plusieurs paramètres permettant de contrôler la coopération. CPMH organise les instances de méta-heuristiques en équipes ; chaque équipe vise à intensifier la recherche dans une région particulière de l’espace de recherche. Cela se fait grâce à des communications intra-équipes. Des communications inter-équipes permettent quant a` elles d’assurer la diversification de la recherche. CPMH offre à l’utilisateur la possibilité d’ajuster le compromis entre intensification et diversification. De plus, ce cadre supporte différentes méta-heuristiques et permet aussi l’hybridation de méta-heuristiques. Nous proposons également X10CPMH, une implémentation de CPMH, écrite en langage parallèle X10. Pour valider notre approche, nous abordons deux COP du monde industriel : des variantes difficiles du Problème de Stable Matching (SMP) et le Problème d’Affectation Quadratique (QAP). Nous proposons plusieurs méta-heuristiques originales en version séquentielle et parallèle, y compris un nouvelle méthode basée sur l’optimisation extrémale ainsi qu’un nouvel algorithme hybride en parallèle coopératif pour QAP. Ces algorithmes sont implémentés grâce à X10CPMH. L’évaluation expérimentale montre que les versions avec parallélisme coopératif offrent un très bon passage à l’échelle tout en fournissant des solutions de haute qualité. Sur les variantes difficiles de SMP, notre méthode coopérative offre des facteurs d’accélération super-linéaires. En ce qui concerne QAP, notre méthode hybride en parallèle coopératif fonctionne très bien sur les cas les plus difficiles et permet d’améliorer les meilleures solutions connues de plusieurs instances. / Combinatorial Optimization Problems (COP) are widely used to model and solve real-life problems in many different application domains. These problems represent a real challenge for the research community due to their inherent difficulty, as many of them are NP-hard. COPs are difficult to solve with exact methods due to the exponential growth of the problem’s search space with respect to the size of the problem. Metaheuristics are often the most efficient methods to make the hardest problems tractable. However, some hard and large real-life problems are still out of the scope of even the best metaheuristic algorithms. Parallelism is a straightforward way to improve metaheuristics performance. The basic idea is to perform concurrent explorations of the search space in order to speed up the search process. Currently, the most advanced techniques implement some communication mechanism to exchange information between metaheuristic instances in order to try and increase the probability to find a solution. However, designing an efficient cooperative parallel method is a very complex task, and many issues about communication must be solved. Furthermore, it is known that no unique cooperative configuration may efficiently tackle all problems. This is why there are currently efficient cooperative solutions dedicated to some specific problems or more general cooperative methods but with limited performances in practice. In this thesis we propose a general framework for Cooperative Parallel Metaheuristics (CPMH). This framework includes several parameters to control the cooperation. CPMH organizes the explorers into teams; each team aims at intensifying the search in a particular region of the search space and uses intra-team communication. In addition, inter-team communication is used to ensure search diversification. CPMH allows the user to tune the trade-off between intensification and diversification. However, our framework supports different metaheuristics and metaheuristics hybridization. We also provide X10CPMH, an implementation of our CPMH framework developed in the X10 parallel language. To assess the soundness of our approach we tackle two hard real-life COP: hard variants of the Stable Matching Problem (SMP) and the Quadratic Assignment Problem (QAP). For all problems we propose new sequential and parallel metaheuristics, including a new Extremal Optimization-based method and a new hybrid cooperative parallel algorithm for QAP. All algorithms are implemented thanks to X10CPMH. A complete experimental evaluation shows that the cooperative parallel versions of our methods scale very well, providing high-quality solutions within a limited timeout. On hard and large variants of SMP, our cooperative parallel method reaches super-linear speedups. Regarding QAP, the cooperative parallel hybrid algorithm performs very well on the hardest instances, and improves the best known solutions of several instances.

Le développement réactionnel est problème multidimensionnel complexe qui, dans un scénario représentatif, implique l’unique convergence de plusieurs paramètres à une réactivité désirée. Le choix incorrect d’un seul paramètre réactionnel tel que le pré-catalyseur, le ligand mais aussi le solvant ou encore l’acide/base peut complètement supprimer la réactivité du système. De ce fait, ce processus requiert souvent de nombreuses expérimentations pour obtenir un premier résultat probant. Pour éviter de tester toutes les combinaisons en parallèle, des approches créatives de criblage ont été développées ces dernières années mais le nombre important de reactions nécessaires à l’exploration de juste trois ou quatre paramètres est toujours un challenge pour les chimistes qui n’ont pas accès au criblage à haut debit. Afin de répondre à cette problèmatique, une stratégie combinatoire réaction-économique pour l’identification d’un lead hit dans une reaction spécifique est proposée. Des mélanges complexes de pré-catalyseurs et de ligands, choisis au préalable, sont testés avec un ou deux autres paramètres de reaction supplémentaires pour identifier de bonnes conditions de réaction dans un nombre minimum de manipulations. La déconvolution iterative permet ensuite d’identifier le catalyseur, généré in situ, le plus actif dans les conditions réactionnelles. L’application de cette approche est décrite sur une réaction de Friedel-Crafts, une arylation ortho-C–H sélective de composés benzamides, une alkylation C3 d’indole et en catalyse asymétrique sur une réaction d’hétéro Diels-Alder. / Reaction development is a complex multidimensional problem that, in a representative scenario, requires often the unique convergence of multiple parameters for a desired reactivity. The incorrect choice of a single parameter, such as the pre-catalyst, the ligand, the solvent or the acid/base, can completely eliminate the reactivity of the system. Thus, the process often requires extensive manipulations to obtain a lead hit. To avoid this time consuming process, many creative screening approaches have been developed but the large number of reactions necessary to explore the intersection of just three or four parameters is still a challenge for chemists who do not have access to high throughput experimentation. A reaction-economic combinatorial strategy is described for lead hit identification in catalyst discovery directed towards a specific transformation. Complex mixtures of rationally chosen pre-catalysts and ligands are screened against various reaction parameters to identify lead conditions in a small number of reactions. Iterative deconvolution of the resulting hits identifies which components contribute to the lead in situ generated catalyst. The application of this screening approach is described in the dehydrative Friedel-Crafts reaction, in the ortho-C–H arylation of benzamides, in the C3-indole alkylation and in the asymmetric hetero Diels-Alder cycloaddition.

Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. The families of highly regular structures, for example Steiner 2-designs, strongly regular graphs and primitive coherent configurations, have been perceived as difficult cases for graph isomorphism. These highly regular structures arise naturally as obstacles for both the classical group theory and combinatorial approaches for the graph isomorphism problem. In this thesis we investigate the isomorphism problem of highly regular structures. We present new results to understand the combinatorial structure of highly regular structures, and propose some new algorithms to compute the canonical forms (and thus isomorphism testing) of highly regular structures based on the structural theorems. We also give an algorithm solving the isomorphism problem of two unknown graphs in the property testing setting. Our new algorithm has sample complexity matching the information theoretical lower bound up to some multiplicative subpolynomial factor.