Path Extraction via Column Generation: an Empirical Study

The objective of this thesis is to carry out an empirical study on the extraction of paths and units crossing those paths for given time units in a directed acyclic graph from counts on nodes and arcs. The methodologies addressed involve formulating the problem and defining the function to be minimized, using the OSQP solver, post-processing and regularization operations, and using approaches such as pricing and column generation in order to scale easily on large graphs. The cases studied were produced from synthetic data and also involved the injection of noise into them, resulting in a robust strategy to improve the obtained solutions. Plots were shown on the results regarding the reconstruction errors and the execution time taken by the algorithm, going by changing 3 factors on which the observations were made: the number of nodes, the amount of units on the single path, and the length of the paths in time units.