Extending the stochastic programming framework for the modeling of several decision makers: pricing and competition in the telecommunication sector

In a previous paper, Gouveia and Magnanti (2003) found diameter-constrained minimal spanning and Steiner tree problems to be more difficult to solve when the tree diameter D is odd. In this paper, we provide an alternate modeling approach that views problems with odd diameters as the superposition of two problems with even diameters. We show how to tighten the resulting formulation to develop a model with a stronger linear programming relaxation. The linear programming gaps for the tightened model are very small, typically less than 0.5–, and are usually one third to one tenth of the gaps of the best previous model described in Gouveia and Magnanti (2003). Moreover, the new model permits us to solve large Euclidean problem instances that are not solvable by prior approaches. Research funded in part by the Research Projects POCTI-ISFL-1-152,POSI/CPS/41459/2001 and POCTI/MAT/139/94 Research funded in part by the Singapore-MITAlliance(SMA)