On Some Optimization Problems on Dynamic Networks

The basic assumption of re-optimization consists in the need of eiciently managing huge quantities of data in order to reduce the waste of resources, both in terms of space and time. Re-optimization refers to a series of computational strategies through which new problem instances are tackled analyzing similar, previously solved, problems, reusing existing useful information stored in memory from past computations. Its natural collocation is in the context of dynamic problems, with these latter accounting for a large share of the themes of interest in the multifaceted scenario of combinatorial optimization, with notable regard to recent applications. Dynamic frameworks are topic of research in classical and new problems spanning from routing, scheduling, shortest paths, graph drawing and many others. Concerning our speciic theme of investigation, we focused on the dynamical characteristics of two problems deined on networks: re-optimization of shortest paths and incremental graph drawing. For the former, we proposed a novel exact algorithm based on an auction approach, while for the latter, we introduced a new constrained formulation, Constrained Incremental Graph Drawing, and several meta-heuristics based prevalently on Tabu Search and GRASP frameworks. Moreover, a parallel branch of our research focused on the design of new GRASP algorithms as eicient solution strategies to address further optimization problems. Speciically, in this research thread, will be presented several GRASP approaches devised to tackle intractable problems such as: the Maximum-Cut Clique, p-Center, and Minimum Cost Satisiability.