Finding dissimilar paths: formulations and variants

Abstract

In the present work, the problem of determining sets of K dissimilar paths between a pair of nodes in a given graph is studied. The concept of path dissimilarity, not being uniform, aims to translate some diversity in the solution sought, which generally relates what the paths of this solution have in common and how they differ. The characteristics of the dissimilarity functions make it difficult to use them as objective functions for combinatorial optimization problems, which was the motivation for looking for alternative ways of representing this concept. In the first part of the thesis, integer linear optimization formulations are introduced that model the dissimilarity of a set of paths based on three assumptions: the minimization of the number of overlapping arcs between the pairs of paths in the set; the minimization of the number of overlapping arcs, and the minimization of the number of repetitions of the overlapping arcs. Additionally, the last two types of formulations are combined with capacity constraints, dependent on an upper-bound obtained by means of an auxiliary problem, which have the double role of limiting the number of uses of the solution arcs and promoting diversification in the event of ties. The suitability of each formulation for solving the original problem, as well as its limitations, is assessed.

In the second part of the thesis, it is assumed that each arc is associated with a given real value and that it is intended to simultaneously minimize two conflicting objective functions: the dissimilarity of K paths and a linear function of its arc values. The extension of some of the previous formulations to the mono-objective case is investigated and an ϵ-constraint type method for the calculation of the Pareto frontier of the bi-objective problem is presented, following two strategies: one in which the ϵ parameter is updated in a decreasing way and another in which the same parameter increases, and which allows to explore the relationship between the sequence of sub-problems that has to be solved.

RESUMO: No presente trabalho estuda-se o problema da determinação de conjuntos de K caminhos dissimilares entre um par de nós de um grafo dado. O conceito de dissimilaridade de caminhos, não sendo uniforme, pretende traduzir alguma diversidade na solução procurada, que geralmente relaciona o que os caminhos dessa solução têm de comum e de diferente. As características de funções de dissimilaridade dificultam a sua utilização como funções objetivo de problemas de otimização combinatória, o que serviu de motivação para a procura de formas alternativas de representar este conceito. Na primeira parte da tese introduzem-se formulações de otimização linear inteira que modelam a dissimilaridade de um conjunto de caminhos com base em três pressupostos: a minimização da sobreposição de arcos entre os pares de caminhos do conjunto; a minimização do número de arcos que se sobrepõem e a minimização do número de repetições dos arcos sobrepostos. Os dois últimos tipos de formulações são combinados com restrições de capacidade, dependentes de um majorante obtido através de um problema auxiliar, que têm a dupla função de limitar o número de utilizações dos arcos da solução e promover a diversificação em caso de empates. Para cada formulação é estudada a adequação à resolução do problema original, assim como as suas limitações. Na segunda parte da tese supõe-se que cada arco está associado a um valor real dado e que se pretende minimizar simultaneamente duas funções objetivo conflituosas: a dissimilaridade de K caminhos e uma função linear dos valores dos seus arcos. Investiga-se a extensão de algumas das formulações anteriores para o caso mono-objetivo e apresenta-se um método do tipo ϵ-restrito para o cálculo da fronteira de Pareto do problema bi-objetivo em causa, seguindo duas estratégias: uma em que o parâmetro ϵ é atualizado de forma decrescente e outra em que o mesmo parâmetro aumenta, e que permite explorar a relação entre a sequência de sub-problemas que tem de ser resolvida.