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.