DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:13:52Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:16:23Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-06-22T17:16:23Z (GMT). No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) Previous issue date: 2008 / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out. / Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Neste trabalho, estudamos o problema de localizaÃÃo simples (SPLP - Simple Plant Location Problem). Usando a formulaÃÃo matemÃtica clÃssica e uma outra formulaÃÃo proposta recentemente, desenvolvemos vÃrios algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulaÃÃo clÃssica, tais limites sÃo obtidos utilizando o mÃtodo de correÃÃo de dados e critÃrios de dominÃncia entre os custos …xos e de transporte. Propomos uma projeÃÃo dessa formulaÃÃo, que se mostrou computacionalmente atrativa. Usando a nova formulaÃÃo propomos e mostramos a corretude de vÃrios procedimentos iterativos que procuram encontrar uma soluÃÃo para o problema, resolvendo uma seqÃÃncia de subproblemas paramÃtricos obtidos com a remoÃÃo de variÃveis e restriÃÃes da formulaÃÃo original. Em cada iteraÃÃo desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxaÃÃo lagrangeana a essa nova formulaÃÃo para obter outros limites. Analisamos vÃrias possibilidades de relaxaÃÃo das restriÃÃes. Desenvolmento tambÃm algoritmos branch-and-bound baseados em ambas as formulaÃÃes e nos limites obtidos. Avaliamos a e…ciÃncia computacional de todos os algoritmos com instÃncias de teste difÃceis, disponÃveis na literatura. Resultados computacionais e comparaÃÃes com outros algoritmos da literatura sÃo reportados. / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out.

Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.