A Fully Distributed Lagrangean Metaheuristic for the Capacitated Network Design Problem: preliminary results

The capacitated network design problem (CNDP) considered in this paper consists in structuring a graph (or network) over which some commodities must be sent, minimizing the total cost. The problem requires to specify for each commodity the quantity and the origin-destination vertices (or nodes), and, for each arc (or connection) of the graph, the capacity, the xed cost for using it and the cost for sending a unit of commodity through it. The commodities can be bifurcated and can share arcs used by other commodities. The main contributions of this paper consist of a fully distributed Lagrangean approach that can be applied to other combinatorial optimization problems and a fully distributed Lagrangean metaheuristic for the CNDP that can be useful in real-world distributed applications, which can take direct advantage of modern multi-core CPU or GPGPU environments. Some preliminary computational results are reported, which show the eectiveness of the subgradient algorithm and of the Lagrangean heuristic in achieving quickly good quality lower and upper bounds, respectively. However, our new algorithm requires further developments and our computational results have to consider a larger set of test instances available in the literature.