Dans cette thèse nous considérons deux problèmes d'optimisation combinatoire.Le premier s'appelle problème du double voyageur de commerce avec contraintes de piles. Dans ce problème, un véhicule doit ramasser un certain nombre d'objets dans une région pour les livrer à des clients situés dans une autre région. Lors du ramassage, les objets sont stockés dans les différentes piles du véhicule et la livraison des objets se fait selon une politique de type last-in-first-out. Le ramassage et la livraison consistent chacune en une tournée Hamiltonienne effectuée par le véhicule dans la région correspondante.Nous donnons une formulation linéaire en nombres entiers pour ce problème. Elle est basée sur des variables de précédence et sur des contraintes de chemins infaisables. Nous donnons par la suite des résultats polyédraux sur l'enveloppe convexe des solutions de notre formulation. En particulier, nous montrons des liens forts avec un polytope associé au problème du voyageur de commerce et des liens avec un polytope de type set covering. Cette étude polyédrale nous permet de renforcer la formulation initiale et de développer un algorithme de coupes et branchements efficace. Le deuxième problème que nous considérons consiste à trouver la description des polytopes lexicographiques. Ces derniers sont les enveloppes convexes des points entiers lexicographiquement compris entre deux points entiers fixés. Nous donnons une description complète de ces polytopes en termes d'inégalités linéaires. Nous démontrons que la famille des polytopes lexicographiques est fermée par intersection. / In this thesis we consider two problems arising in combinatorial optimization.The first one is the double traveling salesman problem with multiple stacks. In this problem a vehicle picks up a given set of items in a region and subsequently delivers them to demanding customers in another region. When an item is picked up, it is put in a stack of the vehicle. The items are delivered observing a last-in-first-out policy. The pickup phase and the delivery phase consist in two Hamiltonian circuits, each performed by the vehicle in the corresponding region. We give a new integer linear programming formulation for this problem. Its main features are the presence of precedence variables and new infeasible path constraints. We provide polyhedral results on the convex hull of the solutions to our formulation. In particular, we show strong links with a specific TSPpolytope and a specific set covering polytope. We deduce strengthening inequalities for the initial formulation, subsequently embedded in an efficient branch-and-cut algorithm. The second problem we consider consists in finding the description of the lexicographical polytopes. These are convex hulls of the integer points lexicographically between two given integer points. We give a complete description of these polytopes by means of linear inequalities. We show that the lexicographical polytope family is closed under intersection.

The present thesis shows the manner of distributing workers on shifts with regular work load but uneven work schedules. It is generally known as the covering or set-covering problem. The present paper describes a way to solve it with mathematical modelling and programs for possible planning of workers on shifts. The issue is documented on a case of an existing company.

[pt] As técnicas de agrupamentos aplicadas a um grande número de cenários de incerteza permitem a escolha de um conjunto reduzido, porém, representativo da população de cenários completa. Em outras palavras, selecionar uma amostra que contenha uma quantidade menor de elementos a ponto de reduzir suficientemente o volume total de dados e obter ganhos significativos de eficiência no processamento dos dados. Esta amostra deve, sobretudo, conseguir preservar as características do processo estocástico que o originou. Com este intuito, o presente trabalho propõe uma metodologia de seleção de cenários estocásticos utilizando o modelo clássico de Cobertura de Conjuntos, inspirada no método forward selection proposto por Heitsch e Romisch (2003). Aplicada na etapa de cálculo de demanda estocástica de ferramentas e serviços para construção de poços marítimos de exploração de petróleo, esta abordagem apresenta uma concepção de cenário diferente da usada pelos autores. O conjunto de cenários consiste em cronogramas de atividades gerados a partir da introdução de incertezas no planejamento de cada atividade, sendo eles estáticos, independentes e com múltiplos atributos. Uma análise de sensibilidade compara os resultados das demandas calculadas com os cenários selecionados pelo Problema de Cobertura de Conjuntos (PCC) e a demanda calculada com o conjunto universo de cenários. O PCC foi solucionado, nesta aplicação, em sua versão clássica da literatura a partir de um algoritmo exato e um heurístico. Os resultados apontam diferenças pouco representativas no resultado final das demandas calculadas com cenários reduzidos e com o total de cenários. A heurística, ainda que seja first solution, apresentou um resultado satisfatório em relação ao ganho de desempenho versus confiabilidade, e indica o potencial do método se aplicado em conjunto com algoritmos de metaheurística e busca local. / [en] Clustering techniques applied to a large number of scenarios under uncertainty allows the selection of a reduced, however, representative set of the complete set of scenarios. In other words, it allows to select a sample that contains a smaller amount of elements to the point of sufficiently reducing the total data volume and obtaining efficiency gains in data processing. The challenge is that the sample must, above all, be able to preserve the characteristics of the stochastic process that originated it. To this end, this study proposes a methodology for selecting stochastic scenarios using the classic Set Covering model, inspired by the forward selection method proposed by Heitsch and Romisch (2003). Applied in the calculating of stochastic demand for tools and services for the construction of offshore oil exploration wells, this approach presents a different scenario conception from the one used by the authors. The set of scenarios consists of activity schedules generated from the introduction of uncertainties in the planning of each activity, which are static, independent and with multiple attributes. A sensitivity analysis compares the results of the demands calculated with the scenarios selected by the Set Covering Problem (SCP) and the demand calculated with all the universe of scenarios. The SCP was solved, in this application, in its classic version using an exact algorithm and a heuristic algorithm. The results appoint na unexpressive loss in the final result of the demand calculated with reduced scenarios and with the complete set of scenarios. The simple first solution heuristic presented a satisfactory result in relation to the performance gain versus reliability, and indicates the potential of the method if solved with metaheuristic and local search algorithms.

This thesis applies classical optimization problems such as assignment or set-covering problem on logical puzzles or brainteasers. Listed in the first part are mathematical model, description and typical example of each optimization problem used in this thesis. The second part contains these models applied to the particular brainteasers for example Sudoku or Einstein's Puzzle. Exercises are divided into simpler and more complex ones. There is specification, source and a described method of solution stated for each of them. The calculation examples use Lingo or MS Excel or both. The aim is to show the possibility to address logical puzzles and brainteasers with the use of optimization problems, and thus confirm the wide possibilities of using these models. These examples can clarify and diversify the curriculum.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-04-12T13:49:50Z No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) / Made available in DSpace on 2018-04-12T13:49:50Z (GMT). No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) Previous issue date: 2017-05-17 / Nenhuma / Com a crescente demanda de serviços de voz e, principalmente, dados móveis se fez necessário o desenvolvimento das tecnologias de quarta geração (4G). O padrão Long Term Evolution (LTE), desenvolvido pela Third Generation Partnership Project (3GPP), foi escolhido pela International Telecommunications Union (ITU) como tecnologia para atender os requisitos da quarta geração de serviços móveis. Para as operadoras inserirem esta nova tecnologia em suas redes existentes, se faz necessário um estudo meticuloso de planejamento, muito embora, na prática, este planejamento seja desenvolvido de forma empírica. O problema de planejamento de redes é conhecido e bem estudado no ramo da computação, conhecido como problema de recobrimento de conjuntos e classificado, pela sua complexidade, como NP-difícil. Dadas as características diferenciadas da arquitetura da rede do LTE, este trabalho busca resolver o problema de planejamento de redes de quarta geração (4G), utilizando uma modelagem matemática aplicada a uma metaheurística híbrida, composta de Algoritmo Genético e Busca Tabu. Almejase resolver o problema de cobertura de uma determinada região, cobrindo a maior área possível com o menor número possível de Base Stations (BS), visando ao planejamento com maior assertividade e redução do custo de implantação da rede 4G. / With the constantly demand of voice services and mostly in mobile data, there was the need the development of the mobile services of fourth generation (4G). The pattern Long Term Evolution, developed by the Third Generation Partnership Project (3GPP) was chosen by the International Telecommunications Union (ITU) as technology to attend the requirements of the fourth generation of mobile services. For the mobile operators introduce and apply this new generation in their own existing networks, they need to do an extensive research and planning, even if, in practical means, it is applied using the empirical way. The network planning problem is widely known and studied in computing area as set-covering problem ans classified as NPhard. Due the unique characteristics of network architecture of LTE, this work aims to solve the mobile’s fourth generation planning problem using a mathematics modelling apply to a hybrid metaheuristics, composed with Genetic Algorithm and Tabu Search. It aims solve the coverage problem of a specific region, covering the largest area possible with the fewest number of Base Sations (BS) possible, seeking the best compliance and cost reduction of the LTE network deployment.

Στην παρούσα μεταπτυχιακή εργασία περιγράφεται η διαδικασία συνδυασμού προβλημάτων Επιχειρησιακής Έρευνας με την μεθοδολογία εύρεσης συγκριτικής αποδοτικότητας (DEA). Αρχικά, παρουσιάζεται μια γενική περιγραφή της μεθόδου DEA και μια συνοπτική επισκόπηση της σχετικής βιβλιογραφίας. Παρουσιάζεται ο τρόπος συνδυασμού της μεθόδου DEA και δύο κλασσικών μοντέλων χωροθέτησης εγκαταστάσεων, του μοντέλου με περιορισμό και του αντίστοιχου μοντέλου χωρίς περιορισμό στην χωρητικότητα. Για την επίτευξη αυτού του στόχου γίνονται οι απαραίτητοι χειρισμοί στην μέθοδο DEA ούτως ώστε να μπορεί να υπολογίζεται η αποδοτικότητα για όλες τις μονάδες λήψης απόφασης ταυτόχρονα – μέθοδος ταυτόχρονης DEA (Simultaneous DEA), εφόσον το κλασσικό μοντέλο βρίσκει την αποδοτικότητα μιας μονάδας λύνοντας μια φορά το γραμμικό πρόβλημα με τους συντελεστές βαρύτητας αυτής της μονάδας. Η λύση του πολυκριτήριου προβλήματος αναδεικνύει την αλληλεπίδραση μεταξύ κόστους και αποδοτικότητας, για τη λήψη απόφασης ανάλογα με τις ανάγκες που μπορεί ενυπάρχουν σε ένα αντίστοιχο πραγματικό πρόβλημα. Στην συνέχεια αναπτύσσεται για πρώτη φορά στη διεθνή βιβλιογραφία μια μεθοδολογία για το συνδυασμό δύο άλλων βασικών προβλημάτων, της κάλυψης και της σύμπτυξης συνόλου, αντίστοιχα, με την μεθοδολογία DEA. Στόχος είναι να μορφοποιηθεί ένα μοντέλο γραμμικού προγραμματισμού έτσι ώστε εκτός από το μέτρο απόφασης του κόστους για την κάλυψη ή σύμπτυξη ενός συνόλου-στόχου, από διαθέσιμα υποσύνολα να ληφθεί υπόψη και η αποδοτικότητα του εκάστοτε υποσυνόλου, η οποία εν τέλει θα επηρεάσει και την συνολική αποδοτικότητα του συνόλου-στόχου. Γίνεται ο συνδυασμός των μεθοδολογιών και αναπτύσσονται μεθοδολογίες πολυκριτήριας ανάλυσης που μπορούν να χρησιμοποιηθούν για την λήψη αποφάσεων που αφορούν την αποδοτική και οικονομική κάλυψη ή σύμπτυξη ενός συνόλου. Για την πιστοποίηση και τη διαπίστωση της λειτουργικότητας των προτεινόμενων μεθοδολογιών αναπτύσσονται παραδείγματα προβλημάτων, τα οποία και επιλύονται επιτυχώς. / In the present thesis, the combination of Operation Research Problems with the Data Envelopment Analysis (DEA) is performed in order to make optimal and efficient decisions. Firstly, a general description of DEA and a breath literature review is presented. Then, we show and test location modeling formulations that utilize data envelopment analysis (DEA) efficiency measures to find optimal and efficient facility location/allocation patterns. In addition, to the authors’ best knowledge, the combinations of DEA with the Set Covering Problem as well as Set Packing Problem are formulated as multiobjective problems, for first time in the literature. The main aim of the proposed models is to make cost-effective and efficient decisions regarding the Set Covering and Packing Problem, respectively. Numerical examples are developed in order to validate and test the novel models. The numerical results of multiobjective analysis demonstrate that the proposed methods are able to successfully find optimal and efficient solutions for real set covering, packing and partitioning problems.

We meet with solving of optimization problems every day, when we try to do our tasks in the best way. An Ant Colony Optimization is an algorithm inspired by behavior of ants seeking a source of food. The Ant Colony Optimization is successfuly using on optimization tasks, on which is not possible to use a classical optimization methods. A Genetic Algorithm is inspired by transmision of a genetic information during crossover. The Genetic Algorithm is used for solving optimization tasks like the ACO algorithm. The result of my master's thesis is created simulator for solving choosen optimization tasks by the ACO algorithm and the Genetic Algorithm and a comparison of gained results on implemented tasks.