Sequenciamento de lotes em prensas de alta capacidade com tempo de setup dependente da sequência

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Heurística especializada aplicada na alocação ótima de bancos de capacitores em sistemas de distribuição radial

Pós-graduação em Engenharia Elétrica - FEIS

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Mobile Search and Advertising

Mobile advertising is a rapidly growing sector providing brands and marketing agencies the opportunity to connect with consumers beyond traditional and digital media and instead communicate directly on their mobile phones. Mobile advertising will be intrinsically linked with mobile search, which has transported from the internet to the mobile and is identified as an area of potential growth. The result of mobile searching show that as a general rule such search result exceed 160 characters; the dialog is required to deliver the relevant portion of a response to the mobile user. In this paper we focus initially on mobile search and mobile advert creation, and later the mechanism of interaction between the user’s request, the result of searching, advertising and dialog.

Méthode de recherche à grand voisinage pour un problème de tournées de véhicules avec flotte privée et transporteur externe

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden.

Méthode de recherche à grand voisinage pour un problème de tournées de véhicules avec flotte privée et transporteur externe

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden.

Text Classification and Indexing in IP Networks

Internet on elektronisen postin perusrakenne ja ollut tärkeä tiedonlähde akateemisille käyttäjille jo pitkään. Siitä on tullut merkittävä tietolähde kaupallisille yrityksille niiden pyrkiessä pitämään yhteyttä asiakkaisiinsa ja seuraamaan kilpailijoitansa. WWW:n kasvu sekä määrällisesti että sen moninaisuus on luonut kasvavan kysynnän kehittyneille tiedonhallintapalveluille. Tällaisia palveluja ovet ryhmittely ja luokittelu, tiedon löytäminen ja suodattaminen sekä lähteiden käytön personointi ja seuranta. Vaikka WWW:stä saatavan tieteellisen ja kaupallisesti arvokkaan tiedon määrä on huomattavasti kasvanut viime vuosina sen etsiminen ja löytyminen on edelleen tavanomaisen Internet hakukoneen varassa. Tietojen hakuun kohdistuvien kasvavien ja muuttuvien tarpeiden tyydyttämisestä on tullut monimutkainen tehtävä Internet hakukoneille. Luokittelu ja indeksointi ovat merkittävä osa luotettavan ja täsmällisen tiedon etsimisessä ja löytämisessä. Tämä diplomityö esittelee luokittelussa ja indeksoinnissa käytettävät yleisimmät menetelmät ja niitä käyttäviä sovelluksia ja projekteja, joissa tiedon hakuun liittyvät ongelmat on pyritty ratkaisemaan.

Construction d'un Atlas 3D numérique de la cornée humaine par recalage d'images

Nous proposons de construire un atlas numérique 3D contenant les caractéristiques moyennes et les variabilités de la morphologie d’un organe. Nos travaux seront appliqués particulièrement à la construction d'un atlas numérique 3D de la totalité de la cornée humaine incluant la surface antérieure et postérieure à partir des cartes topographiques fournies par le topographe Orbscan II. Nous procédons tout d'abord par normalisation de toute une population de cornées. Dans cette étape, nous nous sommes basés sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanément les surfaces antérieures et postérieures d'une population de cornée vers les surfaces antérieure et postérieure d'une cornée de référence. En effet, nous avons élaboré une variante de l'algorithme ICP adapté aux images (cartes) de cornées qui tient compte de changement d'échelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour établir la correspondance entre les points. Après, nous avons procédé pour la construction de l'atlas cornéen par le calcul des moyennes des élévations de surfaces antérieures et postérieures recalées et leurs écarts-types associés. Une population de 100 cornées saines a été utilisée pour construire l'atlas cornéen normal. Pour visualiser l’atlas, on a eu recours à des cartes topographiques couleurs similairement à ce qu’offrent déjà les systèmes topographiques actuels. Enfin, des observations ont été réalisées sur l'atlas cornéen reflétant sa précision et permettant de développer une meilleure connaissance de l’anatomie cornéenne.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Meshing highly regular structures: The case of super carbon nanotubes of arbitrary order

Mesh generation is an important step inmany numerical methods.We present the “HierarchicalGraphMeshing” (HGM)method as a novel approach to mesh generation, based on algebraic graph theory.The HGM method can be used to systematically construct configurations exhibiting multiple hierarchies and complex symmetry characteristics. The hierarchical description of structures provided by the HGM method can be exploited to increase the efficiency of multiscale and multigrid methods. In this paper, the HGMmethod is employed for the systematic construction of super carbon nanotubes of arbitrary order, which present a pertinent example of structurally and geometrically complex, yet highly regular, structures. The HGMalgorithm is computationally efficient and exhibits good scaling characteristics. In particular, it scales linearly for super carbon nanotube structures and is working much faster than geometry-based methods employing neighborhood search algorithms. Its modular character makes it conducive to automatization. For the generation of a mesh, the information about the geometry of the structure in a given configuration is added in a way that relates geometric symmetries to structural symmetries. The intrinsically hierarchic description of the resulting mesh greatly reduces the effort of determining mesh hierarchies for multigrid and multiscale applications and helps to exploit symmetry-related methods in the mechanical analysis of complex structures.

Lengua materna y rendimiento : desarrollo de las habilidades psicol??ng????sticas en Preescolar y ciclo inicial en el Principado de Asturias

Tratan de precisar la relaci??n de la lengua materna y la clase social de pertenencia con respecto a las caracter??sticas personales aptitudinales y el desarrollo de las habilidades psicoling????sticas. Si los alumnos de lengua materna castellana y los de lengua materna asturiana obtienen, cuando la escuela emplea el castellano como lengua de instrucci??n, un rendimiento escolar similar y un dominio de competencia oral y escrita sin incidencia en el l??xico y en su capacidad de expresi??n. El uso del lenguaje en las diferentes situaciones sociales de la comunidad ling????stica favorece que los alumnos de clase alta obtengan mejor rendimiento y mayor desarrollo de habilidades psicoling????sticas. Dos grupos de sujetos de Preescolar y ciclo inicial, 4-8 a??os, en escolarizaci??n normal en Asturias. Muestreo aleatorio estratificado con afijaci??n proporcional. Variables criterio: calificaci??n escolar, resultados del test Boehm, rendimiento escolar, capacitaci??n intelectual, inteligencia general. Variable dependiente: se operativiza con el test de habilidad psicol??ng????stica de Illinois ITPA. Variables predictoras: lengua materna y clase social. Para medir la capacitaci??n intelectual el test de Raven, CIV de WPPSSI, WISC de inteligencia general, por medio del homeindex de Gough en versi??n espa??ola se mide el ??ndice o nivel de desarrollo socioecon??mico familiar. Cuestionario 'ad hoc' para evaluar el l??xico espont??neo en asturiano, el uso de los rasgos morfosint??cticos m??s caracter??sticos y el conocimiento y uso de locuciones y expresiones propias. Las preguntas del cuestionario son le??das al entrevistado en asturiano. El rendimiento acad??mico, el desarrollo de la inteligencia y las habilidades psicoling????sticas no est??n relacionadas con las condiciones en que difiere la lengua en el ??mbito familiar, con la instrucci??n tanto en Preescolar como en ciclo inicial. En Preescolar no se aprecian diferencias significativas entre clase social y medidas de rendimiento, inteligencia y habilidades psicoling????sticas en las condiciones en que difiere la lengua materna, en ciclo inicial hay una relaci??n altamente significativa entre clase social y aspectos del rendimiento y aptitudinales en cualquiera de las condiciones de la lengua materna. El estatus familiar definido por el ??ndice de clase social es una condici??n poderosa para el establecimiento de relaciones entre lengua, desarrollo intelectual y ejecuci??n ling????stica. Las implicaciones ling????sticas no son un asunto de c??digos sino de conductas solidarias con las pr??cticas sociales, condiciones de vida del ??mbito familiar y en comunidad.

The multiple team formation problem using sociometry

The Team Formation problem (TFP) has become a well-known problem in the OR literature over the last few years. In this problem, the allocation of multiple individuals that match a required set of skills as a group must be chosen to maximise one or several social positive attributes. Speci�cally, the aim of the current research is two-fold. First, two new dimensions of the TFP are added by considering multiple projects and fractions of people's dedication. This new problem is named the Multiple Team Formation Problem (MTFP). Second, an optimization model consisting in a quadratic objective function, linear constraints and integer variables is proposed for the problem. The optimization model is solved by three algorithms: a Constraint Programming approach provided by a commercial solver, a Local Search heuristic and a Variable Neighbourhood Search metaheuristic. These three algorithms constitute the first attempt to solve the MTFP, being a variable neighbourhood local search metaheuristic the most effi�cient in almost all cases. Applications of this problem commonly appear in real-life situations, particularly with the current and ongoing development of social network analysis. Therefore, this work opens multiple paths for future research.

Estudo de propriedades críticas em sistemas complexos: método de procura automática em sistemas tipo Ising e percolação de longo alcance

The new technique for automatic search of the order parameters and critical properties is applied to several well-know physical systems, testing the efficiency of such a procedure, in order to apply it for complex systems in general. The automatic-search method is combined with Monte Carlo simulations, which makes use of a given dynamical rule for the time evolution of the system. In the problems inves¬tigated, the Metropolis and Glauber dynamics produced essentially equivalent results. We present a brief introduction to critical phenomena and phase transitions. We describe the automatic-search method and discuss some previous works, where the method has been applied successfully. We apply the method for the ferromagnetic fsing model, computing the critical fron¬tiers and the magnetization exponent (3 for several geometric lattices. We also apply the method for the site-diluted ferromagnetic Ising model on a square lattice, computing its critical frontier, as well as the magnetization exponent f3 and the susceptibility exponent 7. We verify that the universality class of the system remains unchanged when the site dilution is introduced. We study the problem of long-range bond percolation in a diluted linear chain and discuss the non-extensivity questions inherent to long-range-interaction systems. Finally we present our conclusions and possible extensions of this work

Busca em vizinhança variável aplicado na solução do problema de planejamento da expansão do sistema de transmissão de energia elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Reconfiguração de sistemas de distribuição de energia elétrica utilizando a metaheurística busca em vizinhança variável

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)