SOARES, Joel Cruz. O problema da atribuição conexa. 2016. 96 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-11T20:06:15Z No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-12T12:52:08Z (GMT) No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) / Made available in DSpace on 2017-01-12T12:52:08Z (GMT). No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) Previous issue date: 2016 / We present a problem with application in resource allocation in mobile networks, that we name Connected Assignment in Arrays (CAA). This problem has as input a set of symbols $I=\{1,2,\dots,M\}$, an array $v$ indexed by $J=\{1,2,\dots,N\}$, and a gain value $\rho_{ij}$ of allocating $i \in I$ to position $j$ of $v$. We want to find an assignment of symbols to positions so as to maximize the gain, under the constraint that repeated symbols are adjacent in the array. We demonstrate that CAA is an NP-Hard problem by a reduction from the Convex Path Recoloring Problem (CPR). We present an approximate algorithm for a particular case of this problem ($k$-CAA). We propose three ILP formulations and theoretically compare their linear relaxation. We study the polyhedron $\mathcal{P}$ associated with the tightest formulation. We determine all facet-defining inequalities with right-hand side equal to 1 and show that they suffice, together with the non-negativeness constraints, to describe $\mathcal{P}$ when $M=2$ or $N=2$. We generalize this class of valid inequalities while keeping the property of being facet inducing. Finally, we propose 5 heuristics for the problem and compare them by results of computational experiments. / Apresentamos um problema com aplicação em alocação de recursos em redes de comunicações móveis, que denominamos de Problema da Atribuição Conexa em Vetores (ACV). Este problema tem como entrada um conjunto de símbolos $I=\{1,2,\dots,M\}$, um vetor $v$ indexado por $J=\{1,2,\dots,N\}$, e um valor de ganho $\rho_{ij}$ ao alocar $i \in I$ à posição $j$ de $v$. Desejamos encontrar uma atribuição dos símbolos ao vetor que tenha o maior ganho possível, sob a restrição de que símbolos repetidos sejam adjacentes no vetor. Demonstramos que ACV é um problema NP-Difícil a partir de uma redução do Problema de Recoloração Convexa de Caminhos (RCC). Apresentamos um algoritmo aproximativo para um caso particular deste problema ($k$-ACV). Propomos três formulações de Programação Inteira e comparamos teoricamente suas relaxações lineares. Estudamos o poliedro $\mathcal{P}$ associado à formulação mais forte. Determinamos todas as desigualdades indutoras de facetas com lado direito igual a 1 e mostramos que elas, junto com as restrições de não-negatividade, descrevem $\mathcal{P}$ quando $M=2$ ou $N=2$. Generalizamos essa classe de desigualdades válidas, mantendo a propriedade de que induzem facetas. Ao final, propomos 5 heurísticas para o problema e as comparamos através de resultados de experimentos computacionais.

FIGUEIREDO, Tatiane Fernandes. Problema de Formação de Equipes Sociotécnicas: Complexidade, Formulações Matemáticas e Resultados Computacionais. 2016. 86 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:14:08Z No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-04-25T12:32:53Z (GMT) No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Made available in DSpace on 2016-04-25T12:32:53Z (GMT). No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) Previous issue date: 2016 / Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments. / Utilizando conceitos da Teoria dos Sistemas Sociotécnicos, este trabalho define matematicamente os problemas de formação de equipes cooperativas considerando separadamente restrições sociais e técnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, é definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e técnicos para criação de equipes de trabalho cooperativo, denominado FEST (Problema de Formação de Equipes Sociotécnicas). Duas formulações matemáticas e uma meta-heurística para o FEST são propostas. Uma formulação utiliza um número cúbico de variáveis e restrições, enquanto a segunda formulação possui um número quadrático de variáveis, mas um número exponencial de restrições. A meta-heurística proposta é baseada no Simulated Annealing Não-Monotônico com busca local que usa operadores tipo swap. A corretude de ambas as formulações é provada. Um algoritmo polinomial para separar as restrições da segunda formulação é apresentado. Mostra-se que as duas formulações fornecem o mesmo limite de programação linear, e desigualdades válidas para fortalecê-lo são propostas. Para a formulação compacta, algumas classes de desigualdades válidas são demonstradas indutoras de facetas sob hipóteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulações e da meta-heurística apresentadas. Instâncias reais e geradas aleatoriamente são usadas nos experimentos computacionais.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

XAVIER, Alinson Santos. Geração de Facetas para Politopos de Conjuntos Independentes. 2011. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:04:42Z No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:10:07Z (GMT) No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Made available in DSpace on 2016-05-23T19:10:07Z (GMT). No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) Previous issue date: 2011 / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables. / Um conjunto independente de um grafo é um subconjunto de vértices que não contém nenhum par de vértices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade máxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja união tenha cardinalidade máxima. Além de possuírem aplicação em diversas áreas, como visão computacional, biologia molecular e projeto de circuitos integrados, estes problemas também modelam outros problemas de otimização combinatória, como empacotamento de conjuntos e coloração de vértices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geração de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. Além de gerar várias classes de desigualdades indutoras de facetas já conhecidas, este procedimento também gera novas desigualdades que ainda não foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulação por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertação, fazemos um estudo da relação de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversão de faces em facetas que generaliza as diversas versões do procedimento de levantamento de variáveis.

O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema._________________________________________________________________________________________ ABSTRACT: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T07:24:38Z (GMT). No. of bitstreams: 1 Piva_Breno_M.pdf: 1251793 bytes, checksum: bf559620a7bdefeec032b5c87d196b5b (MD5) Previous issue date: 2009 / Resumo: O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema / Abstract: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.