Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-14T11:00:06Z No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) / Made available in DSpace on 2017-02-14T11:00:06Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) Previous issue date: 2016-06-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Transporte reativo a demanda, na língua inglesa Demand Responsive Transport (DRT) é uma forma de prover transporte, seja para passageiros ou mercadorias, na qual o serviço é ativado sob demanda. Ao contrário dos serviços tradicionais de transporte público, os quais operam por meio de rotas, horários e pontos de atendimento fixos, os serviços DRT operam de formas flexíveis ou semi-flexíveis. Para utilização do serviço, passageiros devem enviar requisições, nas quais informam locais e horários desejados de embarque e desembarque. A partir das requisições, ocorre o processo de roteamento dos veículos e agendamento dos atendimentos. Usuários provenientes de requisições diferentes, mas com características em comum, seja área e/ou momento de atuação do serviço podem ser atendidos simultaneamente pelo mesmo veículo. Devido a esta forma de prover transporte, para alguns pesquisadores do tema, serviços DRT são conside- rados uma forma intermediária de transporte, situada entre os serviços de transporte público (caráter geral e compartilhado) e os táxis (personalizado e individual) e con- tribuem direta e indiretamente na redução de alguns dos principais problemas comuns em centros urbanos, tais como: excesso de veículos nas vias trafegando com baixa ocu- pação, poluição, congestionamentos, exclusão social relacionada ao acesso a meios de transporte público e etc. Neste trabalho, foram propostos modelos de programação linear mista, abordagens multiobjetivo e abordagens heurísticas para otimização de um serviço DRT introduzido na literatura, o qual foi explorado para os casos estático e dinâmico. As abordagens apresentadas foram avaliadas por meio de experimentos computacionais e testes estatísticos sobre conjuntos de instâncias com diferentes carac- terísticas, que indicaram as melhores abordagens para cada situação. / Heuristic approaches to optimizing a demand responsive transport. Ad- viser: André Gustavo dos Santos. Demand responsive transport is a way to provide transportation for passengers or go- ods, in which the service is activated on demand. Unlike traditional public transport services, which operate through fixed routes, schedules and service points, DRT ser- vices operate in flexible or semi-flexible way. In order to use the service, passengers must submit requests, in which they inform the desired local and times of departure and arrival. The routing of vehicles and the scheduling of calls are performed based on those requests. Users from different requests, but with common features like area and/or moment of the service can be served simultaneously by the same vehicle. Due to this way of providing transport, some researchers consider the DRT services an inter- mediate form of transport, situated between public transport services (general purpose and shared) and taxis (custom and individual) and contribute directly and indirectly in reducing some of the major common problems in urban centers, such as: too many vehicles traveling on the roads with low occupancy, pollution, congestion, social exclu- sion related to access to public transportation, etc. In this work, we proposed mixed linear programming models, multi-objective approaches and heuristics approaches for optimization of a DRT service from the literature, which was exploited for the static and dynamic case. The approaches presented were evaluated through computational experiments and statistical tests using sets of instances with different characteristics, showing the best approaches for each situation.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-05-08T11:53:07Z No. of bitstreams: 1 texto completo.pdf: 1108981 bytes, checksum: 49f191f3dbc734cbe88ca54d7a84d39a (MD5) / Made available in DSpace on 2017-05-08T11:53:07Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1108981 bytes, checksum: 49f191f3dbc734cbe88ca54d7a84d39a (MD5) Previous issue date: 1997-12-08 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Nove genótipos de trigo (Anahuac, BH 1146, Trigo BR 10 - Formosa, Trigo BR 26 - São Gotardo, CEP 24 - industrial, EMBRAPA 15, EMBRAPA 16, EMBRAPA 21 e EMBRAPA 22), seus F 1 e recíprocos, constituindo um dialelo completo, foram plantados, em maio de 1995, no campo Experimental do Setor de Agronomia da UFV. A parcela constituiu de duas linhas de 1,0 m, espaçadas por 0,30 m entre linhas e 0,10 m entre plantas. As características avaliadas foram: ciclo (do plantio ao espigamento); altura da planta; número de espigas por planta; número de espiguetas estéreis por planta e por espiga; número de espiguetas férteis por planta e por espiga; número de grãos por planta, por espiga e por espigueta; peso de grãos por planta e de mil grãos; e produtividade por parcela e por hectare. A diversidade genética dos genótipos foi avaliada pela distância generalizada de Mahalanobis, com os genótipos Anahuac e Trigo BR 26 - São Gotardo apresentando a menor distância e os genótipos BH 1146 e Trigo BR 26 - São Gotardo, a maior distância. Pelos agrupamentos, segundo os métodos do vizinho mais próximo e de Tocher, foi possível formar quatro grupos. Os genótipos de trigo irrigado (Anahuac, Trigo BR 10 - Formosa e Trigo BR 26 - São Gotardo) formaram um grupo, enquanto o outro genótipo de trigo irrigado (EMBRAPA 22) formou um grupo isoladamente. Os genótipos mais altos (BH 1146 e CEP 24 - Industrial) formaram um outro grupo, enquanto os genótipos de trigo de estatura intermediária (EMBRAPA 15, EMBRAPA 16 e EMBRAPA 21) formaram o quarto grupo. A dispersão gráfica dos genótipos, assim como suas distâncias, foram apresentadas pela metodologia de Singh (1981). A altura da planta explicou mais de 92% da variabilidade genética existente entre os genitores. Para a análise dialélica, utilizaram-se as metodologias de Hayman (1954) e Griffing (1956). Os efeitos da capacidade geral de combinação foram maiores que os da capacidade específica e os recíprocos, para os caracteres estudados. Os genótipos BH 1146, Trigo BR 26 - São Gotardo e EMBRAPA 22 apresentaram os maiores efeitos positivos da capacidade geral de combinação. Para a maioria dos caracteres estudados, o efeito genético aditivo não foi o mais importante, segundo a metodologia de Hayman (1954). A herança dos caracteres estudados mostrou ser oligogênica. / Nine genotypes of wheat (Anahuac, BH 1146, BR 10 – Formosa, Trigo BR 26 – São Gotardo, CEP 24 – Industrial, EMBRAPA 15, EMBRAPA 16, EMBRAPA 21 e EMBRAPA 22) their F 1 and reciprocals, constituting a complete diallel, were planted on May 1992, on the experimental field of the Agronomic Section of the UFV, Minas Gerais State, Brazil. The plots in the blocks were of 2 lines with 1.0 m, spaced at 0.30 m among lines and 0.10 m among plants. The characters evaluated were: cycle (from planting to hearing), plant height, and number of spikes by plant, number of sterile spikelets by spike and by plant, number of fertile spikelets by spike and by plant, number of grains by plant, by spike; and by spikelet, weight of grains by plant, and of a thousond grains, and productivity by hectere. The genetic diversity of the genotypes were evaluated by the Generalized Distance of Mahalanobis, and the genotypes Anahuac and Trigo BR 26 – São Gotardo presented the shortest distance and the genotypes BH 1146 and Trigo BR 26 – São Gotardo presented the greatest distance. According to the grouping analysis using the closest neighbor method and the Tocher method, it was possible to form four groups. The irrigated wheat genotypes (Anahuac, Trigo BR 10 – Formosa and BR 26 – São Gotardo) formed a group, while the irrigated wheat genotype (EMBRAPA 22) formed a single group. The genotypes with the higher plants (BH 1146 and CEP 24 – Industrial) formed another group and the genotypes of wheat of intermediary height (EMBRAPA 15, EMBRAPA 16 and EMBRAPA 21) formed the fourth and bot group. The graphic dispersion of the genotypes, as well as their distances, were presented according to Singh (1981) methodology. The plant hight explained more than 92% of the genetic variability of the parent plants. For the diallelic analyhsis, the methodologies of Griffing (1956) and Hayman (1954) were used. The general capacity effects of combination were greater than those of the specific capacity, and of the reciprocal, for the studied characters. The genotypes BH 1146, Trigo BR 26 – São Gotardo and EMBRAPA 22 presented the greatest positive effects of the general capacity of combination. For almost all of the studied characters, tha additive genetic effect was not the most important one, according to the methodology of Hayman (1954). The heritage of the studied characters showed to be oligogenic. / Tese importada do Alexandria

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-06-01T16:54:22Z No. of bitstreams: 1 texto completo.pdf: 271961 bytes, checksum: ba428af8c95af1d4ed47c3dd808e42db (MD5) / Made available in DSpace on 2017-06-01T16:54:22Z (GMT). No. of bitstreams: 1 texto completo.pdf: 271961 bytes, checksum: ba428af8c95af1d4ed47c3dd808e42db (MD5) Previous issue date: 2003-02-27 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Geralmente, o número de progenitores incluídos num dialelo completo é elevado, acarretando em muitas polinizações manuais, o que aliado às dificuldades das operações de campo, disponibilidade de recursos financeiros, mão-de-obra e período para a execução dos cruzamentos, pode tornar limitante a execução do mesmo. Os dialelos circulantes surgem como uma das alternativas para a solução deste problema. No presente trabalho se verificou as estimativas da capacidade geral de combinação (CGC) e da capacidade específica de combinação (CEC) obtidas nos dialelos circulantes comparadas as estimativas obtidas no dialelo completo. Num primeiro estudo foram simulados dados para um dialelo completo, a fim de se estudar as ações genéticas em consonância ao efeito do dialelo circulante. Num segundo estudo foram utilizados dados de um dialelo completo avaliado por PACHECO (1997). Nos dois estudos o dialelo completo foi composto por 28 progenitores e seus 378 híbridos F 1 ’s, Os dialelos circulantes foram obtidos por reamostragem do dialelo completo, sendo cada um deles representados por s cruzamentos iguais a 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5 e 3. Foram gerados 1000 dialelos circulantes para cada valor de s. No primeiro estudo foram simuladas cinco variáveis hipotéticas de diferentes relações d/a (0, 0,5, 1,0, 1,5 e 2,0) governadas por um gene com dois alelos. Para os dois estudos foram definidos alguns parâmetros genéticos que possibilitaram avaliar as estimativas de CGC e CEC. Foi obtida a distribuição amostral dos parâmetros genéticos estudados e considerou-se os valores obtidos no dialelo completo (s = 27) como valores de referência (valores paramétricos). Concluiu-se que o uso de simulação mostrou-se adequado para a comparação dos dialelos circulantes com o dialelo completo. As estimativas de CGC e CEC obtidas nos dialelos circulantes foram semelhantes às obtidas no dialelo completo, exceto para alguns progenitores, quando o valor de s utilizado foi pequeno. Foi verificado para a variável produção de espigas (t/ha), que com s =19, o que equivale a uma redução de aproximadamente 30% dos cruzamentos, o dialelo circulante permitiu selecionar os melhores progenitores e as melhores combinações híbridas. Portanto, a viabilidade do uso de dialelos circulantes é baseada nas populações estudadas, nas características avaliadas e no objetivo do melhorista. / In maize breeding programs there is almost always a huge number of progenitors to be included in a complete diallel, thus many manual pollinations need to be conducted. In addition, there are the usual difficulties of field operations, availability of financial resources, workmanship and the restricted period available to execute the crossings. Hence, the execution of a complete diallel may become unrealistic and incomplete diallels such as the circulant diallel seem to be a good alternative to the problems mentioned. In the present work we study estimation of the general combining ability (GCA) and specific combining ability (SCA) (GRIFFING, 1956) obtained from circulant diallels as compared to the analogous estimates obtained from the complete diallel. In a first study we simulated data for a complete diallel in order to study gene action in conection with circulant diallel effect. In a second study we used data from a complete diallel conducted by Pacheco (1997). In both studies the complete diallel involved 28 progenitors (p = 28) and their respective 378 F 1 hybrids (p(p- 1)/2). The circulant diallels were obtained from resampling of the complete diallel and each one of the 28 progenitors was represented by s crossings. The s values were set equal to 25, 23, 21, 19, 15, 13, 11, 9, 7, 5 and 3 and we generated 1000 circulant diallels for each one of these 12 alternative values of s. In the first study we simulated different degree of dominance to additive relations (d/a) of gene action using the values of d/a equal to 0, 0,5, 1,0, 1,5 and 2,0. In both studies we defined genetic parameters in order to evaluate the sample distribution of GCA e SCA estimated from the 12000 circulant diallels. We estimated Bootstrap expected values and sample standard deviations for all of the genetic parameters and considered the estimates obtained by using the complete diallel data (s = 27) as reference values (or parametric values). Simulation of circulant diallel data from resampling of the complete diallel data showed to be a very good alternative for comparing these schemes. Estimated values of GCA e SCA obtained from circulant diallels were similar to those obtained from the complete diallel except for a few progenitors in cases where a small s value was used. It was verified for the variable ear weight (t/ha), that with s = 19, equivalent to 30% reduction in the number of crosses, the circulant diallel allowed selection of the best progenitors and hybrid crosses in accordance with the complete diallel. As an overall conclusion we state that circulant diallel can be a good alternative to a complete diallel depending of the characteristics under evaluation, type of populations to be used and also on the goals of the breeding program. / Dissertação importada do Alexandria

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-31T12:45:53Z No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) / Made available in DSpace on 2017-08-31T12:45:53Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) Previous issue date: 2017-03-07 / Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas. / In this work we address two vehicle routing problems with pickup and delivery and loading constraints. Firstly, this work addresses the Double Vehicle Routing Pro- blem with Multiple Stacks (DVRPMS). Posteriorly we formulate and propose the Double Routing Vehicle Problem with Multiple Stacks and Heterogeneous Demand (DVRPMSHD), referring to a more realistic case of the DVRPMS in which custo- mers have multiple and heterogeneous demands and all demand of a same client must be transported by a single vehicle. In both problems, the objective is to de- termine routes for a fleet of vehicles to meet the demand of a set of customers so that the distance travelled by the vehicles is the minimum possible, respecting some loading constraints imposed by the vehicles’ storage stacks. All products located in a pickup region must be collected and then delivered to a delivery region by vehicles. The pickup and delivery regions are largely separated so that all products must be loaded before any unloading. The DVRPMS was approached mainly by four heuristic methods, which were tested in several instances and compared to the exact and heuristic methods already present in literature. The computational experiments showed the efficiency of the proposed algorithms, obtaining solutions of better quality than those presented in the literature for most of the instances and with low computational time. The DVRPMSHD was approached by an exact method and a heuristic method. Initially, the implemented branch-and-price exact method presented higher efficiency compared to the proposed mathematical formu- lation for the problem. The heuristic method overcame the results achieved by the branch-and-price for most of the created instances.

DANTAS, Allberson Bruno de Oliveira. Uma interface de programação distribuída para aplicações em otimização combinatória. 2011. 86 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:57:51Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:23:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-07-13T12:23:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.

ARARUMA Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:26:26Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:35:18Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-07-13T13:35:18Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.

DIAS, Fábio Carlos Sousa. Problema de Árvore Geradora Mínima com Restrição de Grau Mínima e Centrais e Terminais Fixos. 2014. 132 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:49:19Z No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa (jairo@ufc.br) on 2016-07-14T23:17:13Z (GMT) No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Made available in DSpace on 2016-07-14T23:17:13Z (GMT). No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) Previous issue date: 2014 / 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.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-05-20T08:41:16Z No. of bitstreams: 1 texto completo.pdf: 1841361 bytes, checksum: 460f1d8d605da4af4e1d8d606edfaa05 (MD5) / Made available in DSpace on 2016-05-20T08:41:16Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1841361 bytes, checksum: 460f1d8d605da4af4e1d8d606edfaa05 (MD5) Previous issue date: 2007-10-26 / O pivô central é um sistema de irrigação de grande porte, que utiliza grandes quantidades de água durante seu funcionamento. A criação de uma escala de funcio- namento para os pivôs centrais que atuam compartilhando um mesmo recurso hídrico é uma solução para reduzir custos com energia elétrica e controlar o consumo de água visando evitar possíveis danos ambientais sem comprometer a eficácia na irrigação. Para encontrar tal solução, um modelo matemático que representa o problema foi criado e validado. Este modelo serviu de base para a construção de algoritmos que geram a escala de funcionamento dos pivôs centrais. Devido ao grau de complexidade do problema, o uso das metaheurísticas Simulated Annealing e GRASP foi adotado na busca de boas soluções em curto espaço de tempo. A aplicação das metaheurís- ticas foi feita de maneira simples, oferecendo a opção de modificar os parâmetros do problema, de acordo com as necessidades encontradas, sendo possível adaptar a forma de execução dos algoritmos à diferentes realidades. Uma interface que utiliza os al- goritmos desenvolvidos foi construída com o objetivo de facilitar a manipulação das informações de entrada e saída do sistema. Os resultados dos testes obtidos com o sistema utilizando ambos os algoritmos geraram soluções que atenderam plenamente a expectativa inicial sendo, inclusive, avaliados por profissionais da área. Além disto, um estudo de caso, utilizando os algoritmos desenvolvidos, foi realizado com base em informações reais do Projeto Colonização Paracatu Entre-Ribeiros, localizado na Bacia do Rio São Francisco, um dos maiores perímetros de irrigação com pivô central da América Latina. / The central pivot is an system of great importance, which uses much water resource during its working. The development of a working scale to the central pivots that act using one same water resource is a solution to reduce costs with electric energy and to control the water consumption being aimed at to avoid possible nature damages, without compromising its eficiency. To find such solution, a mathematical model that represents the problem was created and validated. This model was the base for the construction of algorithms which solving the scale of the central pivots. Due to the complexity of the problem, the use of metaheuristic Simulated Annealing and GRASP was adopted in the searches of good solutions in very small period of time. The application of the metaheuristics made very simply, offering the options to modify the parameters of the execution, in accordance with the found necessities, being possible to adapt the form of execution of the algorithms to the different realities. An interface that uses the algorithms was constructed with the objective to facilitate to the manipulation of the input and output of the system. The obtained results of tests with the system using both the algorithms had generated solutions that had taken care of the initial expectation fully being, also, evaluated for professionals of the area. Moreover, a case study, using the developed algorithms, were carried through with basis of information of the Project Colonização Paracatu Entre-Ribeiros, located in the Basin of the Rio São Francisco, one of the biggest perimeters of irrigation with central pivot of Latin America. / Dissertação antiga

Neste trabalho estudamos o espectro de grafos, que é o conjunto de autovalores da sua matriz de adjacência. Apresentamos uma teoria baseada na função geradora do número de passeios de um grafo para obter o polinômio característico de algumas classes de grafos. Também desenvolvemos um novo método para o cálculo do polinômio característico de árvores que utiliza um algoritmo geométrico -- também por nós apresentado-- para o determinante de matrizes da forma A+a.I, onde A é a matriz de adjacências e a. é um número real arbitrário. O custo computacional desse algoritmo é O(n2 ), que é menor do que os algoritmos previamente conhecidos. Finalmente apresentamos alguns resultados que visam determinar a estrutura de um grafo a partir de suas propriedades espectrais. / In this dissertation, we study the spectra of graphs, which is the set o f the eigenvalues ofits adjacency matrix. We present a theory, based on the generating function o f the number o f walks, in order to obtain the characteristic polynomial o f certa in classes of graphs. We also develop a new method to compute the characteristic polynomial of a tree's adjacency matrix that hinges on a geometric algorithm --- also introduced in this work ---to obtain the determinant of matrices A+a l, where Ais the adjacency matrix and a an arbitrary real number. The computational cost of this algorithm is O(n2 ) , which is lower than any previously known algorithm. Finally, we present results that try to determine the structure o f a graph from its spectral properties.

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.