A Lagrangian heuristic algorithm for the time-dependent combined network design and routing problem

A Lagrangian heuristic algorithm for the time-dependent combined network design and routing problem

0.00 Avg rating0 Votes
Article ID: iaor20165034
Volume: 69
Issue: 1
Start Page Number: 110
End Page Number: 123
Publication Date: Jan 2017
Journal: Networks
Authors: , ,
Keywords: combinatorial optimization, heuristics, communications, networks: scheduling, design
Abstract:

During the planning of communication networks, the routing decision process (distributed and online) often remains decoupled from the network design process, that is, resource installation and allocation‐planning process (centralized and offline). To reconcile both processes and take into account demand variability, we generalize the capacitated multicommodity fixed charge network design class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances of this problem. Two major difficulties are encountered when using commercial solvers to solve the associated mixed integer programs: (i) problems are large scale and even solving the linear relaxation of the problem can be challenging; and (ii) the solver hardly find good feasible solutions for medium to large scale instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, it always provides a lower bound on the optimal solution. Moreover, based on this relaxation, we propose a Lagrangian heuristic that makes the approach more robust than a black‐box usage of a Mixed Integer Programming (MIP) solver.

Reviews

Required fields are marked *. Your email address will not be published.