Branching strategies for the integer Multi-Commodity Flow Problem

The Multi-Commodity Flow Problem (MCFP) represents a fundamental challenge in combinatorial optimization, with critical applications in transportation, logistics, and telecommunications. While modern Mixed-Integer Linear Programming (MILP) solvers exhibit high efficiency, they typically employ general-purpose branching rules that do not explicitly exploit the topological structure of the underlying network. This thesis investigates a novel approach to accelerate the solution process by integrating structural branching strategies into the Branch-and-Bound algorithm. The proposed methodology shifts the branching focus from individual variables to sets of arcs, utilizing structural insights derived from s-t cuts and path-based partitions. Several strategies for selecting commodities and partitioning edges are explored. These methods were implemented using a Python-based framework and evaluated on several instances, encompassing both real-world networks and synthetic graphs. The experimental analysis reveals that structural branching is highly effective in transportation-inspired topologies, where the presence of physical bottlenecks can be modeled with an objective function that allows for significant search tree reductions. While the computational overhead of the implementation environment remains a factor, the results confirm that incorporating domain-specific structural information can lead to superior pruning power. This study underscores the potential of topology-aware branching as a specialized tool for solving complex multi-commodity flow problems more efficiently.

Il Problema del Flusso Multi-Commodity (MCFP) rappresenta una sfida nell'ottimizzazione combinatoria, con applicazioni nei settori dei trasporti, della logistica e delle telecomunicazioni. Nonostante i solutori moderni di Programmazione Lineare Intera Mista (MILP) mostrino un'elevata efficienza, essi impiegano tipicamente regole di branching di tipo general-purpose che non sfruttano la struttura topologica della rete sottostante. Questa tesi analizza un approccio innovativo per accelerare il processo risolutivo integrando strategie di branching strutturale nell'algoritmo di Branch-and-Bound. La metodologia proposta sposta il focus del branching dalle singole variabili a insiemi di archi, utilizzando caratteristiche strutturali derivate da tagli s-t e partizioni basate sui cammini. Sono state esplorate diverse strategie per la selezione delle commodity e per la partizione degli archi. Questi metodi sono stati implementati utilizzando un framework basato su Python e valutati su diverse istanze, comprendenti sia reti reali che grafi sintetici. L'analisi sperimentale rivela che il branching strutturale è altamente efficace nelle topologie ispirate ai trasporti, dove la presenza di colli di bottiglia fisici può essere modellata con una funzione obiettivo che consente una significativa riduzione dell'albero di ricerca. Nonostante l'overhead computazionale dell'ambiente di implementazione rimanga un fattore rilevante, i risultati confermano che l'integrazione di informazioni strutturali specifiche può portare a un potere di pruning superiore. Questo studio sottolinea il potenziale del branching consapevole della topologia come strumento specializzato per risolvere problemi di flusso multi-commodity complessi in modo più efficiente.