Arborescenze di costo minimo con vincoli di precedenza

The minimum-cost arborescence problem is a well-studied problem in the area of graph theory, with known polynomial algorithms for solving the problem. Since the problem was introduced, various variations on the problem with different objective function and/or constraints were introduced in the literature. In this work we introduce a new variation of the problem called the Precedence-Constrained Minimum-Cost Arborescence problem, in which precedence constraints are enforced on pairs of vertices in the graph. The purpose of the precedence constraints is to prevent the formation of directed paths in the arborescence that violate a precedence relationship. A precedence relationship enforced on the pair of vertices (s,t) imply that a directed path that leads from t to s could not appear in any feasible solution. We show that the Precedence-Constrained Minimum-Cost Arborescence problem is NP-hard, and propose a set of mixed integer linear programming models for formulating the problem, and a branch-and-bound algorithm that is based on Lagrangian Relaxations. An experimental study is conducted which compares the performance of the models and the branch-and-bound algorithm. An extension to the Precedence-Constrained Minimum-Cost Arborescence problem named the Precedence-Constrained Minimum-Cost Arborescence problem with Waiting Times is also introduced in this work, that is characterized by an additional constraint that can be described as follows. Given a weighted directed graph with arc costs indicating the time required to traverse that arc, and assuming that there is a flow that start at the root and traverses each path of the arborescence. The additional constraint imposes that for any precedence constraint (s,t) the flow must enter s before entering t. The constraint implies that there is a waiting time on vertex t, if vertex t is closer to the root compared to vertex s. The objective of the problem is to find an arborescence that has a minimum total cost, plus total waiting times. We show that the Precedence-Constrained Minimum-Cost Arborescence problem with waiting times is also NP-hard, and propose a set of mixed integer linear programming models for formulating the problem. An experimental study is conducted which compares the performance of the models.

Il problema dell'arborescenza adi costo minimo è un problema ben studiato nell'area della teoria dei grafi, con noti algoritmi polinomiali per risolvere il problema. Da quando il problema è stato introdottopresentato, sono state introdotte in letteratura varie variazioni sul problema con diverse funzioni obiettivo e/o vincoli. In questo lavoro introduciamo proponiamo una nuova variante del problema chiamata problema di arborescenza dia costo minimo vincolato allacon vincoli di precedenza, in cui i vincoli di precedenza sono imposti su coppie di vertici nel grafo. Lo scopo dei vincoli di precedenza è impedire la formazione di percorsi diretti nell'arborescenza che violano un rapporto di precedenzaa sequenza temporale. Una relazione di precedenza imposta sulla coppia di vertici (s,t) implica che un percorso diretto che conduce da t a s non potrebbe può apparire in nessuna soluzione ammissibile. Mostriamo che il problema di arborescenza dia costo minimo vincolato alla precedenzacon vincoli di precedenza è NP-hard difficile e proponiamo un insieme di modelli di programmazione lineare intera mista per formulare il problema e un algoritmo esatto branch-and-bound basato su rilassamenti lagrangiani. Viene condotto uno studio sperimentale che confronta le prestazioni dei modelli e l'algoritmo branch-and-bound. In questo lavoro viene introdotta anche un'estensione del problema di arborescenza dia costo minimo vincolato allacon vincoli di precedenza, denominato problema di arborescenza a costo minimo vincolato alla precedenza con tempi di attesa, caratterizzato da un vincolo aggiuntivo che può essere descritto come segue. Dato un grafo orientato ponderato con costi dell'arco sugli archi, dove ogni costo che indica il tempo necessario per attraversare quell'arco, e supponendo che ci sia un flusso che inizia alla radice e attraversa ogni percorso dell'arborescenza. Il vincolo aggiuntivo impone che per ogni vincolo di precedenza (s,t) il flusso debba entrare in s prima di entrare in t. Il vincolo implica che vi sia un tempo di attesa sul vertice t, se il vertice t è più vicino alla radice rispetto al vertice s. L'obiettivo del problema è trovare un'arborescenza che abbia minimizzi la somma delun costo totale minimo, piùe dei tempi di attesa totali. Mostriamo che il problema dell'arborescenza dia costo minimo vincolato allacon vincoli di precedenza con e tempi di attesa è anch’essoe NP-hard difficile e proponiamo una serie di modelli di programmazione lineare interi misti per formulare il problema. Viene condotto uno studio sperimentale che confronta le prestazioni dei modelli.