Embedding a Bundle Method in a Branch and Bound Framework: an Application-Oriented Development

An effective Branch and Bound algorithm based on Lagrangean heuristic is presented, which aims at reducing the gap between the lower and upper bounds. The Branch and Bound method proposed exploits the information gathered while going down in the enumeration tree in order to solve efficiently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangean dual. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is used as a benchmark to validate the efficiency of the method proposed. Such model simultaneously locates obnoxious facilities and routes obnoxious materials between a set of built-up areas and the facilities. Obnoxious facilities are those facilities which cause nuisance to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. OFLR is a particular case of the Obnoxious Network Design problem which occurs when also an obnoxious network has to be designed such as the case of electric power supplier networks. These are meaningful problems given the industrial development and the increasing importance of environmental issues in our society. The use of the B&B to solve this latter problem is under development.