Hidden Structures and Conflicting Items in Combinatorial Optimization Problems

Abstract

Combinatorial optimization-based methods are widely used to solve complex real life problems.

In this thesis, we use some of these methods for addressing several emerging combinatorial opti- mization problems on graphs that can be classified in two macro areas: i) graph substructures

identification problems; ii) combinatorial optimization problems with conflict constraints.

In graph theory, graphs are defined as mathematical structures that describe entities of inter- est (as nodes) and their relationships (as edges). Many real-world problems can be described

through the use of a graph. For example, graph theory finds application in: i) the context of social network analysis, where graphs are used to represent the interactions (edges) between users (nodes); and in ii) the study of biological networks, such as protein-protein interaction, where the nodes are proteins, and the edges represent their physical interactions. In graph analysis one common application is the identification of clusters (or communities) of nodes that are tightly connected. In social networks, a community could represent a set of users sharing the same interest, while in the protein-protein interaction networks it could represent a set of very similar proteins forming a protein complex. In this thesis, three problems related to identifying graph substructures have been tackled.

The first problem addresses the 2-Edge-Connected Minimum Branch Vertices, that finds ap- plication in the design of optical networks. A graph is 2-Edge-Connected if by removing one

edge, the graph is still connected. The problem looks for a spanning 2-edge connected subgraph having the minimum number of branch vertices that is vertices with degree strictly greater than two. In these networks, branch vertices are associated with switch devices that split the light signals and send them to the adjacent vertices. For this NP-complete problem we developed a genetic algorithm using ad-hoc designed operators. The second addressed problem arise in the social network analysis and aims to study how users influence the choices of their neighbours. In particular, we addressed the Collapsed k-Core Problem that seeks to identify a subset of critical users in the network whose choices would alter the cohesiveness of a community. To the best of our knowledge, this is the first attempt to formulate this problem using mathematical programming. We implemented multiple solution approaches and compared them on a set of benchmark instances. The last case studied is related to network clustering, where a cluster graph is a disjoint union of cliques. The Cluster Deletion problem is defined as the identification of the minimum number of edges to remove from a network to produce a cluster graph. This is a well-known NP-hard problem and we faced it using integer linear programming formulation and a heuristic approach based on edge contraction operation. Our results show the effectiveness of our methodology both on artificial and real-world biological networks.

4

Currently, the definition of many real-life problems, doesn’t always fully capture their com- plexity. Indeed, classical optimization problems encountered over the years, although extensively

studied, do not always take into account additional limitations, such as incompatibility situa- tions, encountered in real-world problems. In this context, two or more elements of the problem

cannot be chosen together to compose a feasible solution. Such incompatibilities are modelled by introducing conflict constraints in classical combinatorial optimization problems, leading to more realistic but often harder problems. Finally, three different combinatorial optimization problems with conflicts constraints are addressed. The first one is a variant of the set cover problem where pairwise conflicts are added among the subsets. In the formulation of this problem, two sets in conflict can belong to the same

solution, provided that a non-negative penalty is paid. We introduced two mathematical formu- lations for the problem and offered a parallel Greedy Randomised Adaptive Search Procedure

for its solution. The performance of our algorithm was evaluated through an extensive set of experiments. The results shown the effectiveness and efficiency of our methodology compared to the mathematical model solutions. The second problem is related to the Maximum Flow Problem with Conflict constraints on the edges, for which we present a matheuristic method based on the combination of two different approaches: Carousel Greedy and Kernel Search. The results shown that the Carousel Greedy selection substantially improves the effectiveness of the Kernel Search. The last problem is the Minimum Spanning Tree with Conflicts, that we solved by using a Kernel Search method. Also in this case, the results on benchmark instances shown that our methods identifies a better solution compared with existing methods. [edited by Author]