[pt] O problema do fluxo máximo multiterminal é uma extensão do conhecido problema de fluxo máximo entre um nó origem e um nó destino de uma rede. Este problema surge no contexto de fluxos em redes, tema que possui diversas aplicações, especialmente nos campos de transporte, telecomunicações e energia. No caso multiterminal, o fluxo máximo é calculado entre todos os pares de nós da rede. No referente a uma rede simétrica, este problema pode ser resolvido, obviamente, pela execução do algoritmo de fluxo máximo n(n − 1) 2 vezes, onde n é o número de nós da rede. Os tradicionais métodos encontrados na literatura o conseguem com apenas n − 1. O presente trabalho busca elaborar um algoritmo capaz de resolver o problema multiterminal com uma complexidade menor do que os métodos da literatura. A recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de uma aresta nos fluxos máximos multiterminais, é utilizada para a construção do algoritmo. Técnicas dos tradicionais métodos, como a de contração de nós, também compõem o método. Ao final, o algoritmo é testado computacionalmente com todas as suas variações e heurísticas adicionadas. Para um determinado caso, o algoritmo se mostrou com eficiência semelhante a dos métodos tradicionais. Novas variações e heurísticas são listadas para futuras pesquisas. / [en] The multi-terminal maximum flow problem is an extension of the well known single source-single terminal maximum flow problem. These problems arise in the context of network flows, theme which has various applications, especially in the fields of transport, telecommunications and energy. In the multiterminal case, the maximum flow is calculated between all pairs of nodes. Clearly, this problem can be solved, in a symmetric network, by computing the maximum flow algorithm n(n − 1) 2 times, where n is the number of nodes of the network, but the traditional methods found in the literature can do it with only n − 1 computations. This paper seeks to elaborate an algorithm able to solve the multiterminal problem with a complexity lower than the methods of the literature. The recent theory of sensitivity analysis, which studies the influence of an edge capacity variation on multi-terminals maximum flows, is employed on the construction of the algorithm. Techniques of the traditional methods, such as the contraction of nodes, are also part of the method. Finally, the algorithm is computationally tested with all its variations and added heuristics. For a given case, the algorithm showed an efficiency very close to the ones of traditional methods. New variations and heuristics are listed for future research.

[pt] Esta dissertação de mestrado apresenta a utilização do novo paradigma de desenvolvimento de software, a programação orientada a objetos (OOP), na modelagem em redes de transportes. A utilização da OOP visa, através de suas características: herança, polimorfismo e encapsulamento, aumentar a flexibilidade, produtividade e eficiência dos softwares desenvolvidos segundo seus princípios. O programa desenvolvido, visa servir como uma ferramenta de auxílio a tomada de decisão, a nível estratégico, no planejamento de redes de transportes urbanos. O software faz a alocação de fluxos em redes buscando minimizar o custo do usuário, ou seja, segundo o primeiro princípio de Wardrop. Este estudo foi baseado no método Fusion, que propõe uma abordagem sistemática para o desenvolvimento de software orientado a objetos. O método também está voltado para requisitos de desenvolvimento para e com reutilização. Será feita uma abordagem a nível de análise, projeto e implementação. / [en] This Master thesis presents the utilization in transport modeling the new paradigm in software development, the Object Oriented Program (OOP). The using of OOP seeks improve the flexibility, productivity and efficiency in software developed under such principles. This will be done thought its characteristics: inheritance, polymorphism and encapsulation. The application of the OOP principles has been done adjusting the software TRAFFIC, developed in the University of Montreal. The model will be used like a decision making tool for the urban network transportation planning, ai a strategic level. The software assigns vehicle flows on road networks in order to minimize the user cost, following the first Wardrop`s principle. This research has been based on the Fusion method, that presents a systematic approach for development of object oriented software. The method also is directed toward the requirements of development with and for reutilization. The study will be developed at the level of analysis, project and implementation. / [es] Esta disertación de mestrado presenta la utilización del nuevo paradigma de desarrollo de software, la programación orientada a objetos (OOP), en la modelaje de redes de transportes. La utilización de la OOP tiene como objetivo, a través de sus características (herencia, polimorfismo y encapsulamiento) aumentar la flexibilidad, productividad y eficiencia de los softwares desarrollados según sus principios. El programa desarrollado sirve como herramienta de auxilio a la toma de decisión, a nivel estratégico, en la planificación de redes de transportes urbanos. El software configura los flujos en redes buscando minimizar el costo del usuario, o sea, según el primer princípio de Wardrop. Este estudio está basado en el método Fusión, que propone una abordaje sistemática para el desarrollo de software orientado a objetos. El método también considera requisitos de desarrollo para y con reutilización. Se realiza una abordaje a nível de análise, proyecto e implementación.

[pt] Problemas de multifluxos surgem como modelos básicos no contexto de várias aplicações de fluxos em redes, tais como redes de telecomunicações, redes de transporte e logística. Em tais aplicações, os fluxos que atravessam a rede compartilham simultaneamente os mesmos recursos disponíveis e são definidos por suas próprias restrições. A cada uma das arestas ligando os pontos da rede está associado um custo, fixo ou proporcional à sua utilização. Este trabalho trata problemas de projeto de redes multifluxos, em que os custos estão associados às capacidades instaladas nas arestas. Particularmente, será estudado o caso em que a função de custo nas arestas possui o comportamento de uma função escada crescente e descontínua, para o qual métodos exatos de resolução são ineficientes. Métodos heurísticos são propostos para a resolução aproximada do problema e sintetizados em um algoritmo de multi-partida com memória adaptativa. Um mecanismo de intensificação, conhecido na literatura como construção de vocabulário, é também explorado e aplicado. Finalmente, experimentos computacionais são realizados e o método de resolução proposto é analisado quanto aos seus resultados e os resultados obtidos pelo método de resolução proposto são analisados. O método obtém as melhores soluções conhecidas para algumas instâncias da literatura. / [en] Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.

A popularização dos contêineres no transporte de cargas gerais por volta dos anos 60 provocou significativa mudança no tráfego de mercadorias ao redor do mundo. A utilização deste equipamento simplifica e agiliza o processo de transporte e manuseio de cargas, uma vez que permite a movimentação entre diferentes modais com rapidez e segurança nas operações de carga e descarga. Neste contexto, esta pesquisa trata do problema que integra decisões de escolha de cargas a serem transportadas pelo modal marítimo com decisões de reposicionamento de contêineres vazios de modo a maximizar a receita total. O modelo baseia-se em um problema de fluxo em rede multiproduto, a partir da qual é proposta uma modelagem matemática inédita, que permite levar em consideração as principais restrições encontradas na prática tais como: horizonte de planejamento de longo prazo; diferentes tipos e tamanhos de contêineres; múltiplos navios, rotas e suas respectivas programações; rotas que permitem que um porto seja visitado mais de uma vez; capacidades dos navios em termos de número máximo de contêineres cheios e vazios por tipo e peso máximo total; para cada rota e trecho entre dois portos consecutivos; etc. O modelo proposto foi implementado em C++ e utiliza o software de otimização GUROBI, lançado recentemente, assim como uma planilha eletrônica para os dados de entrada. O mesmo foi comparado a um modelo da literatura que utiliza método heurístico para resolução de problema semelhante. O modelo também foi aplicado a problemas de diversos portes evidenciando que é capaz de resolver problemas até à otimização de maneira eficiente e em tempos de processamento reduzidos. / The popularization of containers in transporting general cargo caused a significant change in freight traffic around the world. The use of this mechanism simplifies and streamlines the process of shipping and handling charges, allowing you to move it between different transport modes, with speed and safety in loading and unloading process. In this context, this research deals the problem that incorporates decisions of cargo selection to be transported by sea with decisions involving reposition empty containers in order to maximize total revenue. The problem is modeled as a multi-product network flow problem and is proposed a novel mathematical model, which takes into account the main constraints encountered in practice, such as planning horizon of long-term; different types and sizes of containers, multiple ships and routes and their schedules, routes that allow a port to be visited more than once, and capacity of vessels in terms of maximum number of full and empty containers by type, and maximum weight for each route and the segment between two consecutive ports, etc. The proposed model was implemented in C++ and uses for its solution, the optimization software recently launched, GUROBI, as well as a spreadsheet for data entry. The same was applied to a problem of literature that uses a heuristic method to solve it. The model also was applied to several size of problems showing the model able to solve problem to optimality of efficient way and in processing time reduced.

Este trabalho trata do problema de configuração de redes logísticas, em que são consideradas como principais decisões a quantidade e a localização de instalações logísticas e a definição da alocação de clientes às instalações. Mais especificamente, o trabalho considera um processo típico de configuração de redes logísticas que se vale de modelos discretos de otimização e a tomada de decisão com base nos resultados. O objetivo da tese é propor modelos e métodos capazes de dar suporte às etapas fundamentais deste tipo de estudo. Inicialmente são propostos métodos para a seleção de locais candidatos considerados nos modelos de localização. Os métodos se valem de informações sobre a distribuição dos pontos de demanda ao longo da rede para a obtenção dos candidatos a instalação e são avaliados por meio de sua aplicação a dois conjuntos de instâncias da literatura científica e comparação de tempos de resolução e de valores da função objetivo. Os resultados mostram que o tempo de resolução foi reduzido, na média, em 57% e os gaps das funções objetivo resultantes vale menos que 0,16% em comparação com os modelos que consideram todos os pontos de demanda como candidatos. Adicionalmente, também foram propostos métodos capazes de obter soluções alternativas de qualidade para problemas de localização que podem ser comparadas a fim de fornecer mais subsídio para a tomada de decisão. Os métodos são capazes de obter as K melhores soluções de problemas de localização e são avaliados por meio de sua aplicação a 215 instâncias da literatura científica. Além disso, a abordagem proposta permitiu a análise de resultados nunca antes obtidos para um problema muito estudado: as K melhores soluções do problema de localização de instalações capacitadas com custo fixo. Duas características principais foram identificadas: a quantidade de instalações é estável - em 99% das instâncias testadas o desvio padrão da quantidade de instalações nas 20 melhores soluções de cada instância é menor que um - e grande parte das instalações que fazem parte da solução ótima de cada instância também faz parte da maior parte das 20 melhores soluções. A partir de tais conclusões, o trabalho investiga algumas propriedades gerais de problemas de localização e apresenta uma análise topológica das 215 instâncias utilizadas, com base em indicadores propostos. Por fim, três tipos de modelos de redes neurais capazes de identificar relações entre os valores dos indicadores das instâncias e os valores das variáveis resposta associadas às melhores soluções são aplicados e avaliados. A abordagem consiste em comparar o tempo de resolução e o valor da função objetivo de modelos cujos espaços de soluções viáveis são reduzidos com base nos resultados obtidos pelas redes neurais. Os resultados mostram que é possível utilizar tal abordagem para melhorar o processo de configuração de redes logísticas, seja na etapa de construção dos modelos seja proporcionando mais subsídios para a tomada de decisão. / This thesis deals with the supply chain network design problem (SCND) that aims to find the optimal location of facilities and the allocation of customers to each facility. The work considers a typical process of SCND in which discrete optimization models are run and its results are used in the decision making. The goal of the thesis is to propose models and methods to support the stages of this type of planning process. Initially, methods for the selection of candidates considered in the localization models are proposed. The methods consider the distribution of the demand points throughout the network to obtain the candidates and are evaluated by their application to two sets of scientific literature instances and comparison of computational times and objective function values. The results show that the average computational time has been reduced by 57% and the resulting objective function gaps are less than 0,16% compared to the solutions obtained by the models that consider all the demand points as candidates. In addition, the thesis present methods capable of obtaining high-quality alternative solutions to location problems that can be compared in order to provide better support for decision making. The methods obtain the K-best solutions of location problems and are evaluated by their application to 215 instances of the scientific literature. In addition, the proposed approach allowed the analysis of results never before obtained for a well-studied problem: the best solutions of the capacitated fixed cost facility location problem. Two main insights were identified: the number of facilities is stable - in 99% of the tested instances the standard deviation of the number of facilities in the 20 best solutions of each instance is less than one - and most of the selected facilities in the optimal solution of each instance is selected in most of the 20 best solutions as well. Based on these conclusions, the work investigates some general properties of localization problems and presents a topological analysis of the 215 instances, based on proposed indicators. Finally, three types of neural network models capable of identifying relations between the instances indicators and the values of the variables of the best solutions are applied and evaluated. The approach consists in comparing the computational time and the objective function value of models whose feasible solution spaces are reduced based on the results obtained by the neural networks. The results show that it is possible to use such approach to improve the SCND process, either at the construction stage of the models or by providing more information for the decision making.

[pt] Os sistemas rodoviários são grandes candidatos à aplicação de técnicas de otimização para a redução dos custos operacionais. Neste trabalho são apresentados dois modelos de programação inteira para problemas nesta área, o Problema de Transferência de Cargas (PTC) e o Problema de Alocação de Cargas (PAC). Ambos foram resolvidos de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados os problemas, as formulações dos modelos, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] Road systems are major candidates for the use of optimization techniques to obtain operational reduction costs. In this research we present two integer programming models for road problems, the Load Transference Problem and the Load Scheduling Problem. Both problems were solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present the descriptions of the problems, the mathematical formulations, the preprocessing techniques used, as well as computational results for real instances.

A feature of minimizing images of a class of binary Markov random field energies is introduced and proved. Using this, the collection of minimizing images of levels of higher order, levelable MRF energies is shown to be a monotone collection. This implies that these images can be combined to give minimizing images of the MRF energy itself. Due to the recent developments, second and third order binary MRF energies of the mentioned class are known to be exactly minimized by maximum flow/minimum cut computations on appropriately constructed graphs. With the aid of these developments an exact and efficient algorithm to minimize levelable second and third order MRF energies, which is composed of a series of maximum flow/minimum cut computations, is proposed and applications of the proposed algorithm to image restoration are given.

Este trabalho trata do problema de configuração de redes logísticas, em que são consideradas como principais decisões a quantidade e a localização de instalações logísticas e a definição da alocação de clientes às instalações. Mais especificamente, o trabalho considera um processo típico de configuração de redes logísticas que se vale de modelos discretos de otimização e a tomada de decisão com base nos resultados. O objetivo da tese é propor modelos e métodos capazes de dar suporte às etapas fundamentais deste tipo de estudo. Inicialmente são propostos métodos para a seleção de locais candidatos considerados nos modelos de localização. Os métodos se valem de informações sobre a distribuição dos pontos de demanda ao longo da rede para a obtenção dos candidatos a instalação e são avaliados por meio de sua aplicação a dois conjuntos de instâncias da literatura científica e comparação de tempos de resolução e de valores da função objetivo. Os resultados mostram que o tempo de resolução foi reduzido, na média, em 57% e os gaps das funções objetivo resultantes vale menos que 0,16% em comparação com os modelos que consideram todos os pontos de demanda como candidatos. Adicionalmente, também foram propostos métodos capazes de obter soluções alternativas de qualidade para problemas de localização que podem ser comparadas a fim de fornecer mais subsídio para a tomada de decisão. Os métodos são capazes de obter as K melhores soluções de problemas de localização e são avaliados por meio de sua aplicação a 215 instâncias da literatura científica. Além disso, a abordagem proposta permitiu a análise de resultados nunca antes obtidos para um problema muito estudado: as K melhores soluções do problema de localização de instalações capacitadas com custo fixo. Duas características principais foram identificadas: a quantidade de instalações é estável - em 99% das instâncias testadas o desvio padrão da quantidade de instalações nas 20 melhores soluções de cada instância é menor que um - e grande parte das instalações que fazem parte da solução ótima de cada instância também faz parte da maior parte das 20 melhores soluções. A partir de tais conclusões, o trabalho investiga algumas propriedades gerais de problemas de localização e apresenta uma análise topológica das 215 instâncias utilizadas, com base em indicadores propostos. Por fim, três tipos de modelos de redes neurais capazes de identificar relações entre os valores dos indicadores das instâncias e os valores das variáveis resposta associadas às melhores soluções são aplicados e avaliados. A abordagem consiste em comparar o tempo de resolução e o valor da função objetivo de modelos cujos espaços de soluções viáveis são reduzidos com base nos resultados obtidos pelas redes neurais. Os resultados mostram que é possível utilizar tal abordagem para melhorar o processo de configuração de redes logísticas, seja na etapa de construção dos modelos seja proporcionando mais subsídios para a tomada de decisão. / This thesis deals with the supply chain network design problem (SCND) that aims to find the optimal location of facilities and the allocation of customers to each facility. The work considers a typical process of SCND in which discrete optimization models are run and its results are used in the decision making. The goal of the thesis is to propose models and methods to support the stages of this type of planning process. Initially, methods for the selection of candidates considered in the localization models are proposed. The methods consider the distribution of the demand points throughout the network to obtain the candidates and are evaluated by their application to two sets of scientific literature instances and comparison of computational times and objective function values. The results show that the average computational time has been reduced by 57% and the resulting objective function gaps are less than 0,16% compared to the solutions obtained by the models that consider all the demand points as candidates. In addition, the thesis present methods capable of obtaining high-quality alternative solutions to location problems that can be compared in order to provide better support for decision making. The methods obtain the K-best solutions of location problems and are evaluated by their application to 215 instances of the scientific literature. In addition, the proposed approach allowed the analysis of results never before obtained for a well-studied problem: the best solutions of the capacitated fixed cost facility location problem. Two main insights were identified: the number of facilities is stable - in 99% of the tested instances the standard deviation of the number of facilities in the 20 best solutions of each instance is less than one - and most of the selected facilities in the optimal solution of each instance is selected in most of the 20 best solutions as well. Based on these conclusions, the work investigates some general properties of localization problems and presents a topological analysis of the 215 instances, based on proposed indicators. Finally, three types of neural network models capable of identifying relations between the instances indicators and the values of the variables of the best solutions are applied and evaluated. The approach consists in comparing the computational time and the objective function value of models whose feasible solution spaces are reduced based on the results obtained by the neural networks. The results show that it is possible to use such approach to improve the SCND process, either at the construction stage of the models or by providing more information for the decision making.

Notre thèse s'inscrit dans un contexte français marqué par l'augmentation des réseaux d'entrepreneurs, dont on connaît encore peu le fonctionnement et les bénéfices, la recherche en entrepreneuriat s'intéressant davantage au réseau personnel de l'entrepreneur au détriment de l'analyse des réseaux fermés d'entrepreneurs. Pourtant, leur importance pour la construction et la consolidation du capital social des membres a été soulignée ces dernières années. L'objectif de notre thèse est de proposer un cadre théorique et méthodologique permettant d'évaluer les apports des réseaux formels d'entrepreneurs dans une perspective de capital social. A partir des contributions récentes relatives au réseau de l'entrepreneur, au capital social généré par l'activité de réseautage et à la communauté de pratique, nous présentons un cadre théorique permettant d'étudier les flux de conseils, d'opportunités d'affaires et de ressources tangibles circulant dans les réseaux formels d'entrepreneurs, ainsi que la création de valeur perçue pour les membres. Une méthodologie de recherche mixte (questionnaire sociométrique et entretiens semi-directifs) est mobilisée pour étudier cette problématique dans le cadre du Centre des Jeunes Dirigeants La Defense. Sur l'ensemble des neuf propositions formulées à partir de notre modèle de recherche, quatre sont entièrement validées, deux confirmées partiellement et trois infirmées. Nos résultats indiquent que la position structurale dans le réseau, le contenu et les bénéfices perçus de l'activité de réseautage varient selon le profil des membres (le profil d'entrepreneur, défini sur la base de l'expérience entrepreneuriale et le profil de réseauteur, défini sur la base de l'expérience de réseautage). Nous présentons les implications théoriques, méthodologiques et pratiques de notre recherche pour l'étude des réseaux formels d'entrepreneurs et leur utilisation par les membres. / In France, an incresing number of entrepreneurial networks have been launched during the last years. However, we know little about their functioning and benefits, as research in entrepreneurship is traditionnally more interested in stidying the entrepreneur's personal network rather that networks of entrepreneurs. Yet their importance to the construction and the consolidation of their members' social capital has been highlighted in recent years. The objective of our thesis is to propose a theoretical and methodological framework for assessing the benefits of formal entrepreneurial networks in a social capital perspective. We articulate three main streams of research relative to the entrepreneur's personal network, to social capital and communities of practice, in ordre to elaborate a theoretical framework for studying the flows of advice, business opportunities and tangible resources circulating within formal entrepreneurial networks as well as the outcomes of these networks in terms of perceived value creation. A mixed research methodology (sociometric questionnaire and semi-structured interviews) is used to study the Centre des Jeunes Dirigeants La Defense. Out of the nine propositions we formulate on the basis of our research model, four are fully validated, two are partially confirmed, and three are rejected. Our results indicate that the structural position in the network, the content and the perceived benefits of networking activities vary according to the members' profile (the entrepreneurial profile, defined on the basis of entrepreneurial experience and the networking profile, defined on the basis of networking experience). We present the theoretical, methodological and practical implications of our research for the study of formal entrepreneurial networks.

[pt] Calcular o valor do fluxo máximo entre um nó origem e um nó destino em uma rede é um problema clássico no contexto de Fluxos em Redes. Sua extensão, chamada de problema do fluxo máximo multiterminal, consiste em achar os valores dos fluxos máximos entre todos os pares de nós de uma rede não direcionada. Estes problemas possuem diversas aplicações, especialmente nos campos de transporte, logística, telecomunicações e energia. Neste trabalho, apreciamos a recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de arestas nos fluxos máximos multiterminais, e estendemos a computação dinâmica dos fluxos multiterminais para o caso de mais de uma aresta com capacidade variável. Através dessa teoria, relacionamos também nós de corte e fluxos multiterminais, o que permitiu desenvolver um método competitivo para solucionar o problema do fluxo máximo multiterminal, quando a rede possui nós de corte. Os resultados dos experimentos computacionais conduzidos com o método proposto são apresentados e comparados com os de um algoritmo clássico, fazendo uso de instâncias geradas e outras conhecidas da literatura. Por último, aplicamos a teoria apresentada em um problema de identificação de complexos de proteínas em redes de interação proteína-proteína. Através da generalização de um algoritmo e de um resultado teórico sobre exclusão de cortes mínimos, foi possível reduzir o número de cálculos de fluxo máximo necessários para identificar tais complexos. / [en] Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.