An Alternative ILP Model and Algorithmic Ideas for the Maximum Edge-Disjoint Paths Problem

Abstract

This document describes an alternative integer linear programming (ILP) model for the so-called edge-disjoint paths (EDP) problem in undirected graphs. EDP is an NP-hard problem where exact methods are not able to produce high quality solutions. Therefore, we propose two different algorithms for combining exact and heuristic methods. On the one hand, we consider a restricted model that limits the number of paths between two given nodes in the graphs (which reduces the search space exploration). On the other hand, the application of a mat-heuristic algorithm known as Construct, Merge, Solve and Adapt (CMSA) is considered. In this document we show some preliminary results concerning the restricted model. These results indicate the potential usefulness of the presented ideas.

Abraham Duarte

Full Professor

Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.

Jesús Sánchez-Oro

Associate Professor

Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.