A DUAL ASCENT APPROACH TO THE FIXED-CHARGE CAPACITATED NETWORK DESIGNPROBLEM

In this layer we consider the problem of constructing a network over w hich a number of commodities are to be transported. Fixed costs are as sociated to the construction of network arcs and variable costs are as sociated to routing of commodities. In addition, one capacity constrai nt is related to each arc. The problem is to determine a network desig n that minimizes the total cost; i.e., it balances the construction an d operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated net work design problem is proposed. The method is shown to generate tight er lower bounds than the linear programming relaxation of the problem.