Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Maurílio Figueiredo (maurilioafigueiredo@yahoo.com.br) on 2015-01-13T18:37:57Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-01-15T17:28:11Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Made available in DSpace on 2015-01-15T17:28:11Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) Previous issue date: 2014 / Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não- Relacionadas com Tempos de Preparação Dependentes da Sequência (UPMSPST, do inglês Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no método Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solução e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é refinada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search { ALS. A busca _e também intensificada e diversificada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca também passa por uma intensificação ao e diversificação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado a melhor das formulações de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores soluções. __________________________________________________________________________________________________________________________ / ABSTRACT: This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times { UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time { ASPT rule. This solution is then refined by the Iterated Local Search { ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking { PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search { ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these experiments utilized a higher runtime. It was observed, however, that the addition of the mathematical programming module does not improved the performance of the AIRMP algorithm in the tested time and in the used structure of subsets of jobs. These tests also showed that increasing the processing time of the AIRP, the algorithm is able to find better solutions.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2015-05-20T18:18:24Z No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-05-20T19:03:59Z (GMT) No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Made available in DSpace on 2015-05-20T19:03:59Z (GMT). No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) Previous issue date: 2015 / Este trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução. _________________________________________________________________________________ / ABSTRACT: This work explores the structural information of relations between binary variables in Integer Programming problems using conflict graphs. Such structure has a fundamental role in the construction of exact and heuristic solving methods. In this sense, the present work proposes and develops techniques based on the analysis of conflict graphs to obtain feasible solutions and strong dual bounds for Integer Programming problems. Optimizations were developed in the conflict detection techniques that allowed the fast construction of dense graphs through the constraints analysis. The obtaining of strong dual bounds for integer programs is performed by a routine developed for the generation of valid inequalities. This routine is responsible for generating clique and odd hole cuts and insert them into the linear relaxation, strengthening the dual bounds and accelerating the convergence to the optimal solution. To obtain feasible solutions for binary programs it was developed a heuristic solver, which uses the logical relations between variables to build an initial solution and improve it through a local search. Local search performs chains of movements at each iteration, which allows to fix infeasibilities of a solution or even jump from a feasible solution to another. Considering the production of strong dual bounds, the results obtained by the developed routine for generating inequalities showed a faster convergence compared with the cut separation routine of COIN-OR Branch-and-Cut solver. Regarding the production of feasible solutions, the heuristic solver was able to generate solutions to a significant number of Integer Binary Programming problems considering restricted runtimes.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnologico / Made available in DSpace on 2016-01-08T15:22:42Z (GMT). No. of bitstreams: 1 108630.pdf: 2538675 bytes, checksum: cab6d8b3105b4bc04dc8773ff7eccada (MD5) Previous issue date: 1986 / Este trabalho foi elaborado com o objetivo de dar ao Método de Planejamento e Programação Espaço-Tempo um modelo de programação matemática que permita otimizar tempos e custos de obras de construção civil lineares através do uso de computadores. Nele estão formuladas todas as considerações matemáticas que, com o uso de Programação Linear Inteira possibilitam a caracterização da totalidade dos projetos lineares que se apresentam na prática. Com a finalidade de facilitar a implementação computacional do método foi elaborado um programa que gera a partir de dados básicos de projetos as variáveis, restrições e função objetivo no formato compatível com o pacote para solução de programação matemática utilizado. A título de ilustração das técnicas propostas, são resolvidos dois exemplos de obras de porte médio.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2012. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2012-10-18T16:28:45Z No. of bitstreams: 1 2012_JoaoPauloCarvalhoColuQueiroz.pdf: 949010 bytes, checksum: 6c8c52f3b39f58d84a5780716ea83b12 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2012-10-24T11:08:41Z (GMT) No. of bitstreams: 1 2012_JoaoPauloCarvalhoColuQueiroz.pdf: 949010 bytes, checksum: 6c8c52f3b39f58d84a5780716ea83b12 (MD5) / Made available in DSpace on 2012-10-24T11:08:41Z (GMT). No. of bitstreams: 1 2012_JoaoPauloCarvalhoColuQueiroz.pdf: 949010 bytes, checksum: 6c8c52f3b39f58d84a5780716ea83b12 (MD5) / Este trabalho apresenta um estudo de metodologias para veri cação formal de aplicativos desenvolvidos em linguagens imperativas, em especial, na linguagem Java. Os formalismos teóricos mostrados incluem a Lógica de Hoare, usada para representar pro- priedades de aplicações imperativas, e construções da linguagem de especi cação JML (baseada na Lógica de Hoare), usada para especi car o comportamento esperado de apli- cações codi cadas em Java. As ferramentas mostradas são o sistema Krakatoa, usado para converter especi cações JML em obrigações de prova, e o ambiente interativo de provas Coq, usado para veri car obrigações de prova. Finalmente, exibe-se um estudo de caso que utiliza o ferramental teórico e prático proposto. ______________________________________________________________________________ ABSTRACT / This work presents a study of methodologies to formally verify applications developed with imperative languages, specially with the Java language. The theoretical formalisms shown include Hoare Logic, which is used to sketch properties on imperative languages, and JML constructions (based on Hoare Logic), which is a speci cation language used to specify the expected behavior from Java programs. The tools shown are the Krakatoa system, used to convert JML speci cations into proof obligations, and the Coq interactive proof environment, used to verify proof obligations. Finally, this paper presents a case study that employs the theoretical and practical proposed framework.

Este trabalho contribui na busca de soluções para o problema de auxílio à programação paralela, apresentando uma abordagem orientada a objetos, como base para a construção de uma ferramenta que dá apoio ao desenvolvimento de programas paralelos. Diversas ferramentas com propostas análogas sac revisadas e suas características principais são destacadas, visando a busca de um modelo adequado para a ferramenta a ser proposta. A ferramenta desenvolvida, implementada e validada neste trabalho (FAPP - Ferramenta de Auxílio à Programação Paralela) baseia-se na tecnologia de orientação a objetos. A teoria dos grafos, modelada segundo a orientação a objetos, serve de base para a criação de modelos tanto para arquiteturas paralelas (hardware) como para programas paralelos (software). Os modelos criados para o hardware e software, permitem ao programador criar o ambiente para a programação, definindo a sua arquitetura paralela, os processos componentes de seu programa e o mapeamento lógico desses processos nos processadores. A ferramenta FAPP gera automaticamente o esqueleto para a aplicação paralela. Todo o desenvolvimento efetuado e validado através de uma implementação básica da ferramenta e são apresentadas às diretrizes para futuras extensões, visando outros ambientes de hardware e software, bem como melhoramentos objetivando futuros trabalhos / This work contributes to the solution of the parallel programming supporting problem, by proposing an object-oriented approach as the basis for building a tool to help the development of parallel programs. Several tools with similar goals are revised and their main features are highlighted aiming the search of an adequate model for the supporting tool to be developed. The tool developed, implemented and validated in this work (FAPP - Parallel Programming Supporting Tool) is based on the object orientation technology. The graph theory was modeled according to the object-orientation and used as the basis for the creation of models for both parallel architectures (hardware) and parallel programs (software). This allows the programmer to create the programming environment by defining his parallel architecture, the program processes and the logical mapping of the processes on the processors. The FAPP tool automatically generates the skeleton for the parallel application. The work is validated by means of a basic implementation of the tool. The guidelines for future extensions aiming other hardware and software environments as well as for future works are presented

Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-04-17T14:15:28Z No. of bitstreams: 2 TESE Jucimar Maia da Silva Júnior.pdf: 4954306 bytes, checksum: fbddc0017ae748afd4a4afa5751c4a17 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-04-17T14:15:28Z (GMT). No. of bitstreams: 2 TESE Jucimar Maia da Silva Júnior.pdf: 4954306 bytes, checksum: fbddc0017ae748afd4a4afa5751c4a17 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-07-31 / Jogos via Internet, redes sociais e as novas aplicações web demandam acesso simultâneo e interativo de milhares (às vezes milhões) de pessoas. Esses sistemas são quase sempre desenvolvidos usando linguagens de script como PHP ou usando frameworks baseados em linguagens como Java, Ruby ou Pyhton. À proporção que o acesso a esses sistemas cresce, os fornecedores de tais serviços necessitam atender a novas demandas por meio da substituição de hardware por modelos mais potentes, aumentando seus custos operacionais. Quando o nível de acesso cresce drasticamente, o projetista se vê forçado a reprojetar toda a arquitetura do sistema migrando para soluções complexas usando Java Enterprise Edition (JEE) ou Node.js. Essas soluções também demandam mais e mais servidores. O problema possui uma raiz mais profunda: as linguagens de programação usadas para o desenvolvimento de sistemas não foram projetadas para suportar concorrência massiva. Linguagens com suporte a concorrência baseadas no modelo de memória compartilhada não possuem a escalabilidade necessária para atender a demanda. Para resolver os problemas ocasionados pela concorrência massiva, os desenvolvedores estão optando por usar linguagens funcionais como Scala e Erlang na arquitetura do sistema ao contrário de linguagens orientadas a objetos como Java. Mas Erlang não possui uma sintaxe própria para programação orientada a objetos. Este trabalho mostra o desenvolvimento de uma extensão orientada a objetos para a linguagem Erlang, chamada ooErlang, que possui uma melhor expressividade para resolução de problemas “do mundo real” e que não degrade o bom desempenho da linguagem em aplicações que demandam alto tráfego de dados e fina granularidade computacional, tal qual em programas Web 2.0. Assim sendo, o nicho da extensão aqui apresentada é o mesmo de Erlang: desenvolver sistemas backend para grandes aplicações onde a concorrência massiva e tolerância a falhas são requeridas.

Orientadores: Marcos Nereu Arenales, Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T21:02:26Z (GMT). No. of bitstreams: 1 Cavichia_MarioConrado_D.pdf: 5998163 bytes, checksum: f6c1820237d358eb60f8cd3709fe7cc4 (MD5) Previous issue date: 1997 / Resumo: Este trabalho tem como objetivo o desenvolvimento de algoritmos de pontos interiores, visando a resolução de problemas de minimização de funções objetivos lineares por partes, separáveis e convexas, sujeitas ainda a restrições lineares. Os métodos disponíveis na literatura para esta classe de problemas são do tipo simplex, com exceção de casos particulares. Uma prática comum para a resolução de programas lineares por partes consiste em transformá-Io num programa linear e explorar suas propriedades. Mostramos que esta estratégia pode ser adequada para métodos do tipo simplex, porém inadequada para métodos de pontos interiores. Neste trabalho abordamos o programa linear por partes diretamente como um problema de programação não linear. Para tanto apresentamos o que convencionamos chamar algoritmo linear por partes interior, isto é, um algoritmo que gera pontos interiores no problema original, embora a solução transformada esteja na fronteira. Mostramos que não se trata de uma simples extensão de um algoritmo de ponto interior aplicado ao programa linear transformado. Apresentamos também uma breve experiência computacional. O algoritmo proposto é aplicado em alguns problemas, sendo alguns elaborados a partir de exemplos-teste retirados da NetLib. Antes da apresentação do algoritmo linear por partes interior, fazemos uma revisão dos vários métodos de pontos interiores, apresentando-os sob um ponto de vista unificado, dando uma pequena contribuição quando da apresentação do algoritmo primal para problemas canalizados, sob tal ponto de vista. Em seguida, o método simplex linear por partes é apresentado para efeito de complementação de informações. Como proposta de estudo futuro, introduzimos um problema que pode ser visto como de programação linear por partes: o problema conhecido como minmax. No decorrer do trabalho, uma relação de outras aplicações que podem ser tratadas sob a ótica aqui abordada é apresentada / Abstract: The objective of this work is the development of an interior point algorithm for a piecewise linear programming problem (PLP). In contrast to the most papers which prefer to transform a PLP in a linear programming problem (LP) and then take advantage of a specific structure now created or considering the problem as an extension of the linear programming problem, using now a piecewise linear simplex algorithm. The PLP will be considered as a problem of non-linear programming and in this context will be proposed an algorithm of interior point in order to solve it. The proposed algorithm is applied to problems, with some of them constructed using examples from NetLib. Before the main algorithm, a review of several interior point methods is presented, under an unified point of view. A review of this nature gives a small contribution when the primal algorithm for bounded linear problems is presented. The piecewise linear simplex method is then developed. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-29T00:37:16Z (GMT). No. of bitstreams: 1 Saito_JuniorToshiharu_M.pdf: 2131960 bytes, checksum: e2163c47f1b0ce788ed24753b3d88814 (MD5) Previous issue date: 2001 / Resumo: O gerenciamento de rede é uma tarefa muito importante para o funcionamento de uma rede, principalmente as redes de telecomunicações. A causa disto é o aumento do tamanho e da complexidade das redes que dificultam a deteção de fallias e baixo desempenho. Outro fator de importância na gerência é permitir que este seja feito de fonna descentralizada. O grupo OMG, analisando a possibilidade de se utilizar a sua platafonna CORBA para permitir esta forma de gerenciamento, lançou um conjunto de serviços para auxiliar a construção de aplicações para o gerenciamento de redes de telecomunicações. Neste traballio será apresentada uma arquitetura para o gerenciamento de redes de telecomunicações que utiliza objetos distribuídos. Esta arquitetura utiliza-se dos recursos existentes no Serviço de Notificação CORBA, várias ferramentas foram desenvolvidas / Abstract: The network management is a task very important to its operation, mainly in telecommunication networks. This fact is caused by increasing of size and complexity of the networks which raises difficulties to detect faults and low performance. Other important fact in network management is the decentralization of the managers, so in case of faults there will be a manager receiving the events. The CORBA architecture allows the decentralized network management, using the CORBA services. In this dissertation an architecture to the management of telecommunication networks using distributed objects is presented. This architecture uses the existent resources in the CORBA Notification Service, many tools were developed. / Mestrado / Mestre em Ciência da Computação

Orientadores : Cid Carvalho de Souza, Abilio Pereira de Lucena Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-31T15:05:43Z (GMT). No. of bitstreams: 1 Calheiros_FelipeCarneiro_M.pdf: 3990645 bytes, checksum: b967de7c86c5f19eb910cd59cf0cd246 (MD5) Previous issue date: 2001 / Resumo: Seja P um conjunto finito de pontos do plano localizados no interior de um retângulo R. Considere as partições de R em retângulos menores. Se nenhum ponto de P for interior a algum destes retângulos, então a partição é viável e seu custo é a soma do comprimento dos segmentos que a definem. O problema de partição retangular (RG-P) busca uma partição retangular de R de custo mínimo. Experimentos descritos na literatura envolvendo algoritmos exatos para esse problema indicam que instâncias do RG-P com pontos não corretilineares em P, chamado de RG-NLP, são as mais difíceis de serem resolvidas até a otimalidade. Esse trabalho apresenta propriedades geométricas de soluções ótimas do RGNLP, que permitem uma redução substancial do número de variáveis do modelo natural de programação inteira. Adicionalmente, essas propriedades levam a desigualdades satifeitas por todas as soluçoes ótimas. Tais desigualdades são usadas em um algoritmo de Relaxação Lagrangeana com Planos de Corte (Relax and Cut). Enquanto resolvedores de programação linear não conseguem computar o enorme modelo para instâncias do RG-NLP, o algoritmo lagrangeano produziu excelentes limitantes. Além disso, para as instâncias em que este algoritmo não foi capaz de provar otimalidade, o número de variáveis eliminadas durante a sua execução foi suficiente para permitir a execução do resolvedor de programação linear. O algoritmo híbrido combinando a Relaxação Lagrangeana e Programação Linear foi capaz de resolver instâncias mais do que duas vezes maiores que as apresentadas na literatura. Além disso, os grandes modelos de partição gerados e resolvidos neste trabalho figuram entre os maiores já resolvidos até a otimalidade / Abstract: Let P be a finite set of points in the plane lying in the interior of a rectangle R. Consider the partitions of R into smaller rectangles. Ir no point in P is interior to any such rectangle, the partition is feasible and its length is the sum of the lengths of the segments defining it. The Rectangular Partition Problem (RG-P) seeks for a feasible partition of R of minimum length. Experiments reported in the literature with exact algorithms based on Integer Programming (IP) indicate that RG-P instances with non corectilinear points in P, called RG-NLP, are the hardest to solve to optimality. This work presents structural properties of optimal RG-NLP solutions which allow for substantial reductions on the number of variables in the natural IP model of the problem. In addition, these properties led to inequalities that are satisfied by alI optimal solutions. Such inequalities are used in a Lagrangean Relax and Cut algorithm for RG-NLP. While commercial LP solvers cannot compute the huge models for RG-NLP instances in general, the Lagrangean algorithm produces very good bounds. For the few test instances where Lagrangean bounds alone are not enough to prove optimality, they allow enough variables to be fixed that an LP solver can now be applied. The hybrid algorithm combining the Lagrangean and the LP phases solves RG-NLP instances more than twice as large as those in the literature. Additionally, the large set partitioning instances solved with this algorithm figure among the biggest ever solved to prove optimality / Mestrado / Mestre em Ciência da Computação

Orientador : Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T15:30:06Z (GMT). No. of bitstreams: 1 Yunes_TallysHoover_M.pdf: 6565656 bytes, checksum: 4ef3637ed1584172d24419ae96564bcc (MD5) Previous issue date: 2000 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento de mão-de-obra oriundo da operação diária de uma empresa de ônibus urbanos da cidade de Belo Horizonte. Por questões de complexidade, este tipo de problema é normalmente dividido em dois subproblemas, a saber: crew scheduling, que trata a alocação diária de viagens a duplas de funcionários (motorista e cobrador), e crew rostering, que parte da solução do subproblema anterior e constrói uma escala de trabalho de mais longo prazo, e.g. um mês. Cada um desses subproblemas foi abordado utilizando-se técnicas de Programação Matemática e Programação por Restrições. Para o problema de crew scheduling, em particular, desenvolveu-se também um algoritmo híbrido de geração de colunas combinando as duas técnicas mencionadas e cujo desempenho foi significativamente melhor que o dos métodos isolados. Em geral, os modelos matemáticos resultantes de problemas dessa natureza são de grande porte. No caso aqui tratado, a matriz de coeficientes do programa linear associado a algumas instâncias dos problemas chega a conter dezenas de milhões de colunas. Todos os algoritmos propostos para a solução do problema foram implementados e testados sobre dados reais obtidos junto à empresa em questão. A análise dos resultados computacionais mostra que foi possível obter soluções de excelente qualidade em um tempo de computação adequado para as necessidades da empresa. Em particular, para o subproblema de scheduling, foi possível comprovar que as soluções obtidas são ótimas / Abstract: This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the problem is usualIy divided in two distinct subproblems, namely: crew scheduling, that deals with the daily alIocation of trips to crews, and crew rostering, which takes the solution of the first subproblem and extends the scheduling to a longer planning horizon, e.g. a month. We have tackled each one of these subproblems using Mathematical Programming (MP) and Constraint Logic Programming (CLP) approaches. Besides, we also developed a hybrid column generation algorithm for solving the crew scheduling problem, combining MP and CLP, which performed much better than the two previous approaches when taken in isolation. Real world crew management problems typicalIy give rise to large scale mathematical models. In our case, the coefficient matrix of the linear program associated with some instances of the problem contains tens of millions of columns. AlI the proposed algorithms have been implemented and tested over real world instances obtained from the aforementioned company. The analysis of our experiments indicates that it was possible to find high quality solutions within computational times that are suitable for the company's needs. In particular, we were able to find provably optimal solutions for the crew scheduling problem / Mestrado / Mestre em Ciência da Computação