A note on ‘a dual-ascent approach to the fixed-charge capacitated network design problem’

We show by a counterexample that the dual-ascent procedure proposed by Herrmann, Ioannou, Minis and Proth in a 1996 issue of the European Journal of Operational Research is incorrect in the sense that it does not generate a valid lower bound to the optimal value of fixed-charge capacitated network design problems. We provide a correct dual-ascent procedure based on the same ideas and we give an interpretation of it in terms of a simple Lagrangean relaxation. Although correct, this procedure is not effective, as in general, it provides a less tight bound than the linear programming relaxation.