Abstract: Benders Decomposition for Network Design Problems with Underlying Tree Structure


We present a class of network design problems with underlying tree structure. The problem is formulated as a mixed nonlinear programming model including investment integer variables associated with the equipments to be installed and continuous variables associated with the use of the network. The generalized Benders decomposition method is used to solve it. In this article, we introduce simple procedures to determine the optimal multipliers used to specify the cuts in the master problem. The procedures do not require to solve any optimization problem as they take advantage of the underlying tree structure of the problem.