nÃo hà / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Bendersâs Decomposition. We propose a new general heuristic that combines ingredients from the Bendersâs decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Ãrvore Geradora MÃnima com RestriÃÃo de Grau MÃnimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma Ãrvore geradora mÃnima de um grafo onde cada vÃrtice ou à folha da Ãrvore ou satisfaz uma restriÃÃo de grau mÃnimo. Os vÃrtices folhas sÃo chamados terminais e os demais sÃo os centrais. Definimos e estudamos uma variaÃÃo desse problema, que denotamos MDF-MST, onde os terminais e centrais sÃo definidos a priori. Mostramos que o problema à NP-DifÃcil e està na Classe FPT, parametrizado pelo nÃmero de centrais. Identificamos tambÃm casos onde o problema torna-se polinomial. Propomos vÃrias formulaÃÃes de programaÃÃo inteira para o problema e comparamos teÃrica e computacionalmente a qualidade do limite inferior gerado por suas relaxaÃÃes lineares. Propomos e testamos uma relaxaÃÃo lagrangeana para o problema, que usamos tambÃm para definir heurÃsticas lagrangenas. Definimos heurÃsticas gulosas, uma busca VND e uma heurÃstica VNS. Apresentamos uma decomposiÃÃo de Benders. Propomos uma nova heurÃstica geral que combina ingredientes da decomposiÃÃo de Benders com mÃtodo de subgradientes, a qual denominamos HeurÃstica de Subgradientes. Aplicamos tal heurÃstica ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiÃncia computacional dos algoritmos propostos, especialmente a relaxaÃÃo lagrangeana, à competitiva com a do CPLEX, e superior em vÃrios casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este Ãltimo onde a restriÃÃo sobre os centrais à de grau mÃximo). Quando comparamos os resultados computacionais com a literatura

O problema de programaÃÃo de caminhÃes à um tema de grande relevÃncia na gestÃo de frota das empresas. Estas enfrentam dificuldades em gerenciar seus veÃculos devido Ãs diversas variÃveis inerentes ao processo, tais como o tamanho ideal da frota, os diversos tipos de caminhÃes disponÃveis, a capacidade de carga do caminhÃo, as informaÃÃes tÃcnicas do cliente e o agendamento das viagens. No que se refere ao transporte de derivados de petrÃleo, existem diversas caracterÃsticas operacionais que dificultam a programaÃÃo de caminhÃes. Embora a literatura sobre a programaÃÃo de veÃculos seja vasta, as abordagens para a programaÃÃo de caminhÃes para este tipo de transporte ainda à limitada. O presente trabalho tem como objetivo desenvolver um modelo de programaÃÃo inteira para a otimizaÃÃo da programaÃÃo de veÃculos de mÃltiplos tipos para o transporte de derivados de petrÃleo para obras de construÃÃo de rodovias. Dados reais sobre uma empresa de transporte desse setor foram coletados. Foi desenvolvido um modelo que buscasse a minimizaÃÃo da frota de caminhÃes disponÃveis. Como conclusÃes, pode-se ressaltar que a metodologia empregada serviu para minimizar a frota necessÃria no perÃodo analisado. O desenvolvimento de indicadores de desempenho permitiu avaliar a qualidade das soluÃÃes geradas. / The truck scheduling problem is an important topic in the companiesâ fleet management. Many companies face difficulties to manage their vehicles due to several variables inherent to the management process, such as the optimal fleet size, multiple types of trucks available, trucks capacity, the technical information from the clientâs construction site and trips scheduling. In terms of the transportation of oil products, there are many operational characteristics that make the truck scheduling difficult. Despite the extensive literature about vehicle scheduling, truck scheduling for this type of transport is limited. The purpose of this research study was to develop an Integer Programming model to optimize the multi-type truck scheduling for the transportation of oil products for road construction sites. Data from a real company were gathered. A model that aimed to minimize the truck fleet available was developed. The method used has minimized the available fleet in the period under review. The development of key performance indicators allows to evaluate the quality of the solutions created.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero cromÃtico tambÃm à NP - DifÃcil. A importÃncia do problema de coloraÃÃo tem incentivado a investigar mÃtodos para encontrar limitantes inferiores prÃximos do nÃmero cromÃtico. Historicamente, os primeiros limitantes inferiores utilizados para resolvÃ-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilizaÃÃo de relaxaÃÃes lineares de formulaÃÃes de programaÃÃo inteira. Uma formulaÃÃo que mostrou bons limitantes inferiores foi a formulaÃÃo por conjuntos independentes, cujo valor de relaxaÃÃo equivale ao nÃmero cromÃtico fracionÃrio. No presente trabalho, fazemos uma comparaÃÃo entre as formulaÃÃes de programaÃÃo inteira conhecidas para indicar a escolha pela formulaÃÃo dos representantes. Revisamos a formulaÃÃo para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluÃÃes inteiras. Discutimos como à possÃvel utilizar a formulaÃÃo dos representantes para gerar limites inferiores para o nÃmero cromÃtico fracionÃrio. Realizamos a implementaÃÃo de um mÃtodo de planos de corte para aproximar o nÃmero cromÃtico fracionÃrio e mostramos que podemos gerar limitantes inferiores que normalmente nÃo diferem em mais de uma unidade. / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value.

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.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Introduzimos o problema de Ãrvore Geradora com DependÃncias MÃnima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vÃrtices sÃo as arestas de G e cujos arcos definem dependÃncias entre tais arestas. O problema consiste em encontrar, dentre as Ãrvores geradoras do grafo G(V,E) que satisfaÃam as restriÃÃes de dependÃncia impostas pelo digrafo de entrada D(E,A), uma que tenha custo mÃnimo, segundo a ponderaÃÃo w das arestas de G. As restriÃÃes de dependÃncia exigem que uma aresta e de G sà pode fazer parte de uma soluÃÃo se for uma fonte em D ou se fizer parte da soluÃÃo alguma outra aresta à tal que o arco (e′, e) esteja em D. Provamos que decidir se hà soluÃÃo viÃvel para AGDM(G,D,w) à um problema NP-completo, mesmo quando G à um cacto cordal e D à a uniÃo de arborescÃncias de altura no mÃximo 2. Sua NP-completude tambÃm à mostrada ainda que G seja bipartido, as restriÃÃes de dependÃncia ocorram apenas entre arestas adjacentes de G e formem arborescÃncias de altura no mÃximo 2. Resultados idÃnticos sÃo obtidos para as variantes do problema onde, nas restriÃÃes de dependÃncia, substitui-se o requisito âalgumaâ por âexatamente umaâ ou âtodaâ. Para resolver o problema, apresentamos algumas formulaÃÃes de programaÃÃo inteira e desigualdades vÃlidas. Propomos uma estratÃgia para reduzir a dimensÃo do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instÃncias geradas aleatoriamente. Resultados computacionais sÃo reportados. / We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of âsomeâ, âexactly oneâor âallâdependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported.