A ROBUSTNESS APPROACH TO UNCAPACITATED NETWORK DESIGN-PROBLEMS

In this paper, we address uncapacitated network design problems charac terised by uncertainty in the input data. Network design choices have a determinant impact on the effectiveness of the system, Design decisi ons are frequently made with a great degree of uncertainty about the c onditions under which the system will be required to operate. Instead of finding optimal designs for a given future scenario, designers ofte n search for network configurations that are ''good'' for a variety of likely future scenarios. This approach is referred to as the ''robust ness'' approach to system design. We present a formal definition of '' robustness'' for the uncapacitated network design problem, and develop algorithms aimed at finding robust network designs. These algorithms are adaptations of the Benders decomposition methodology that are tail ored so they can efficiently identify robust network designs, We teste d the proposed algorithms on a see of randomly generated problems. Our computational experiments showed two important properties. First, rob ust solutions are abundant in uncapacitated network design problems, a nd second, the proposed algorithms performance is satisfactory in term s of cost and number of robust network designs obtained.