Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T05:36:32Z (GMT). No. of bitstreams: 1 Cavalcante_VictorFernandes_D.pdf: 1501954 bytes, checksum: afd9c038eef0eb384065875b1df282ca (MD5) Previous issue date: 2008 / Resumo: Uma das principais motivações para o estudo de Otimização Discreta reside no elevado número de problemas do nosso cotidiano representáveis através de modelos de Otimização Inteira e Combinatória. Em particular, muitos destes problemas podem ser formulados com Programação Inteira 0-1, o que desperta especial interesse em técnicas capazes de resolver tais modelos. Dentre as inúmeras formas de solução atualmente disponíveis para problemas desta natureza, os algoritmos baseados na técnica de relaxação Lagrangiana surgem como uma alternativa que tem tido grande sucesso na prática. Além disso, avanços consideráveis ocorreram na área de Programação Inteira com o advento da Combinatória Poliédrica, intensificando o interesse pelos algoritmos de planos de corte. Neste contexto, esta tese tem como principal objetivo verificar as potencialidades do uso combinado de Combinatória Poliédrica e relaxação Lagrangiana na resolução de dois problemas de otimização combinatória. Mais especificamente, o presente trabalho esta focado no desenvolvimento dos chamados algoritmos relax-and-cut para o problema de particionamento de conjuntos e ao problema do separador de vértices de um grafo. Sendo assim, são propostos algoritmos que combinam relaxação Lagrangiana e planos de cortes faciais para os dois problemas sob consideração. Em ambos os casos, os resultados obtidos com os testes computacionais realizados são comparados com os melhores resultados disponíveis na literatura. Os principais resultados alcançados na tese mostram que: (a) o uso combinado de relaxação Lagrangiana e planos de corte constitui uma alternativa bastante competitiva para solucionar o problema de particionamento de conjuntos, freqüentemente superando o desempenho dos melhores algoritmos disponíveis na literatura para o problema e, (b) no caso do problema do separador de vértices, além da combinação de técnicas Lagrangianas com o uso de planos de corte, a hibridização dos algoritmos relax-and-cut e branch-andcut leva á resolução de instâncias da literatura mais rapidamente que o melhor algoritmo exato conhecido para o problema até então. / Abstract: One of the main motivations for the study of Discrete Optimization resides in the huge number of problems from our daily life that can be represented through Integer and Combinatorial Optimization models. In particular, many of these problems can be cast as 0-1 Integer Programs, which gives rise to special interest on how to solve such models. Among the several ways currently available to solve problems of this nature, the algorithms based on Lagrangian relaxation techniques appears as an alternative that has had great success in practice. Besides, noticeable achievements occurred with the advent of Polyhedral Combinatorics, intensifying the interest on cutting plane algorithms. In this context, this thesis has as its main goal to verify the potentialities of the combined usage of Polyhedral Combinatorics and Lagrangian relaxation in the resolution of two combinatorial optimization problems. More specifically, the present work is focused on the development of the so-called relax-and-cut algorithms for the set partition problem and for the vertex separator problem on graphs. Therefore, algorithms combining Lagrangian relaxation and cutting planes are proposed for the two problems under consideration. In both cases, the results obtained in the computational tests carried out are compared with the best ones available in the literature. The main results achieved in the thesis show that: (a) the combined usage of Lagrangian relaxation and cutting planes constitutes a competitive alternative to solve the set partition problem, often outperforming the best algorithms available in the literature for the problem and, (b) in the case of the vertex separator problem, besides the combination of Lagrangian techniques and cutting planes, a hybridization of the relax-and-cut and branch-and-cut algorithms lead to the resolution of instances from the literature more rapidly than the best exact algorithm known for the problem so far. / Doutorado / Doutor em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T14:30:07Z (GMT). No. of bitstreams: 1 Mortati_CamilaFrederico_M.pdf: 341927 bytes, checksum: 5b1a9d9a8e6c0852c0e86425852e2584 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui proposto / Abstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work / Mestrado / Automação / Mestre em Engenharia Elétrica

Submitted by Pedro Henrique Rodrigues (pedro.henriquer@ufpe.br) on 2015-03-04T17:17:29Z No. of bitstreams: 2 dissert-avap.pdf: 401311 bytes, checksum: 5bd3f82323bd612e8265a6ab8a55eda0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-04T17:17:29Z (GMT). No. of bitstreams: 2 dissert-avap.pdf: 401311 bytes, checksum: 5bd3f82323bd612e8265a6ab8a55eda0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-03-08 / Cloud reliance is critical to its success. Although fault-tolerance mechanisms are employed by cloud providers, there is always the possibility of failure of infrastructure components. We consequently need to think proactively of how to deal with the occurrence of failures, in an attempt to minimize their effects. In this work, we draw the risk concept from probabilistic risk analysis in order to achieve this. In probabilistic risk analysis, consequence costs are associated to failure events of the target system, and failure probabilities are associated to infrastructural components. The risk is the expected consequence of the whole system. We use the risk concept in order to present representative mathematical models for which computational optimization problems are formulated and solved, in a Cloud Computing environment. In these problems, consequence costs are associated to incoming applications that must be allocated in the Cloud and the risk is either seen as an objective function that must be minimized or as a constraint that should be limited. The proposed problems are solved either by optimal algorithm reductions or by approximation algorithms with provably performance guarantees. Finally, the models and problems are discussed from a more practical point of view, with examples of how to assess risk using these solutions. Also, the solutions are evaluated and results on their performance are established, showing that they can be used in the effective planning of the Cloud.

We study combinatorial optimization problems on graphs in the mean-field model, which assigns independent and identically distributed random weights to the edges of the graph. Specifically, we focus on two generalizations of minimum weight matching on graphs. The first problem of minimum cost edge cover finds application in a computational linguistics problem of semantic projection. The second problem of minimum cost many-to-one matching appears as an intermediate optimization step in the restriction scaffold problem applied to shotgun sequencing of DNA. For the minimum cost edge cover on a complete graph on n vertices, where the edge weights are independent exponentially distributed random variables, we show that the expectation of the minimum cost converges to a constant as n →∞ For the minimum cost many-to-one matching on an n x m complete bipartite graph, scaling m as [ n/α ] for some fixed α > 1, we find the limit of the expected minimum cost as a function of α. For both problems, we show that a belief propagation algorithm converges asymptotically to the optimal solution. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings. Our proofs use the machinery of the objective method and local weak convergence, which are ideas developed by Aldous for proving the ζ(2) limit for the minimum cost bipartite matching. We use belief propagation as a constructive proof technique to supplement the objective method. Recursive distributional equations(RDEs) arise naturally in the objective method approach. In a class of RDEs that arise as extensions of the minimum weight matching and travelling salesman problems, we prove existence and uniqueness of a fixed point distribution, and characterize its domain of attraction.

Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

No description available.

Dans cette thèse, nous nous concentrons sur l’étude des algèbres de Hopf de type I, à savoir de type sélection/quotient. Nous présentons une structure d’algèbre de Hopf sur l’espace vectoriel engendré par les mots tassés avec du coproduit sélection/quotient. C’est un algèbre libre sur ses mots irreductible. Nous montrons que la série de Hilbert de cette algèbre de Hopf. Nous donnons une nouvelle preuve de l’universalité du polynôme de Tutte pour les matroïdes.Cette preuve utilise des caractères appropriés de l’algèbre de Hopf des matroïdes introduite par Schmitt (1994). Nous montrons que ces caractères sont des solutions des équations différentielles du même type que les équations différentielles utilisées pour décrire le flux du groupe de renormalisation en théorie quantique de champs. Cette approche nous permet aussi de démontrer,d’une manière différente, une formule de convolution du polynôme de Tutte des matroïdes,formule publiée par Kook, Reiner et Stanton (1999) et par Etienne et Las Vergnas (1998). Dans la dernière partie, nous définissons une algèbre de Hopf non-commutative de graphes. Lanon-commutativité du produit est obtenue grâce à des étiquettes entières distinctes associées aux arrêtes du graphe. Cette idée est inspirée de certaines techniques analytiques utilisées en renormalisation en théories quantiques des champs. Nous définissons ensuite une structure d’algèbre de Hopf, avec un coproduit basé sur une règle de type sélection/quotient, et nous démontrons la coassociativité de ce coproduit. Nous analysons finalement la structure de quadri-cogèbre et les structures codendriformes associées. / In this thesis, we focus on the study of Hopf algebras of type I, namely the selection/quotient.We study the new Hopf algebra structure on the vector space spanned by packed words. Weshow that this algebra is free on its irreducible packed words. We also compute the Hilbertseries of this Hopf algebra.We provide a new way to obtain the universality of the Tutte polynomial for matroids. Thisproof uses appropriate characters of Hopf algebra of matroids, algebra introduced by Schmitt(1994). We show that these Hopf algebra characters are solutions of some differential equationswhich are of the same type as the differential equations used to describe the renormalizationgroup flow in quantum field theory. This approach allows us to also prove, in a different way, amatroid Tutte polynomial convolution formula published by Kook, Reiner and Stanton (1999)and by Etienne and Las Vergnas (1998).We define a non-commutative Hopf algebra of graphs. The non-commutativity of the productis obtained thanks to some discrete labels associated to the graph edges. This idea is inspiredfrom certain analytic techniques used in quantum field theory renormalization. We then definea Hopf algebra structure, with a coproduct based on a selection/quotient rule, and prove thecoassociativity of this coproduct. We analyze the associated quadri-coalgebra and codendrifromstructures.

Cette thèse se situe au carrefour de la combinatoire et de l'algèbre. Elle se consacre d'une part à traduire des problèmes algébriques en des problèmes combinatoires, et inversement, utilise le formalisme algébrique pour traiter des questions combinatoires. Après un rappel des notions classiques de combinatoire et d'algèbres de Hopfavec quelques applications, nous abordons l'étude de certaines statistiques définies sur les permutations : les pics, les vallées, les doubles montées et les doubles descentes, qui sont à la base de la bijection de Françon-Viennot, elle-même débouchant sur une étude combinatoire des polynômes orthogonaux. Nous montrons qu'à partir de ces statistiques, il est possible de construire diverses sous-algèbres ou algèbres quotients de FQSym, une algèbre dont une base est indexée par les permutations. Puis, nous étudions deux suites classiques de combinatoire par une démarche non commutative : les polynômes de Gandhi, un raffinement polynomial des nombres de Genocchi, et les nombres d'Euler, une suite recelant de nombreuses propriétés combinatoires. Nous nous attachons à montrer que l'approche non commutative permet, dans la majeure partie des cas, d'obtenir de manière directe des interprétations d'identités combinatoires. Enfin, inversement, certaines questions de nature algébrique peuvent être abordées d'un point de vue combinatoire. Ainsi, à travers l'étude des algèbres dendriformes, des algèbres tridendriformes, et des quadrialgèbres, nous prouvons des questions de liberté à propos de ces algèbres grâce à la combinatoire des arbres étiquetés / This thesis is at the crossroads between combinatorics and algebra. It studies some algebraic problems from a combinatorial point of view, and conversely, some combinatorial problems have an algebraic approach which enables us tosolve them. In the first part, some classical statistics on permutations are studied: the peaks, the valleys, the double rises, and the double descents. We show that we can build sub algebras and quotients of FQSym, an algebra which basis is indexed by permutations. Then, we study classical combinatorial sequences such as Gandhi polynomials, refinements of Genocchi numbers, and Euler numbers in a non commutative way. In particular, we see that combinatorial interpretations arise naturally from the non commutative approach. Finally, we solve some freeness problems about dendriform algebras, tridendriform algebras and quadrialgebras thanks to combinatorics of some labelled trees

In this thesis, we will study a class of divisor functions: the prime symmetric functions. These are polynomials over Q in the so-called elementary prime symmetric functions, whose values lie in Z. The latter are defined on the nonnegative integers and take the values of the elementary symmetric functions applied to the multi-set of prime factors (with repetition) of an integer n. Initially we look at basic properties of prime symmetric functions, and consider analogues of questions posed for the usual sum of proper divisors function, such as those concerning perfect numbers or Aliquot sequences. We consider the inverse question of when, and in how many ways a number $n$ can be expressed as f(m) for certain prime symmetric functions f. Then we look at asymptotic formulae for the average orders of certain fundamental prime symmetric functions, such as the arithmetic function whose value at n is the sum of k-th powers of the prime divisors (with repetition) of n. For these last functions in particular, we also look at statistical results by comparing their distribution of values with the distribution of the largest prime factor dividing n. In addition to average orders, we look at the modular distribution of prime symmetric functions, and show that for a fundamental class, they are uniformly distributed over any fixed modulus. Then our focus shifts to the related area of partitions into prime powers. We compute the appropriate asymptotic formulae, and demonstrate important monotonicity properties. We conclude by looking at iteration problems for some of the simpler prime symmetric functions. In doing so, we consider the empirical basis for certain conjectures, and are left with many open problems. / Science, Faculty of / Mathematics, Department of / Graduate