Groupe d’études et de recherche en analyse des décisions

G-83-23

Network Design Problem with Congestion Effects: A Case of Bilevel Programming

Recently much attention has been focused on multilevel programming, a branch of mathematical programming that can be viewed either as a generalization of min-max problems or as a particular class of Stackelberg games with continuous variables. The network design problem with continuous decision variables (link capacities) can be cast into such a framework. We first give a formal description of the problem and then develop various heuristic procedures to solve it. Worst-case behaviour results concerning the heuristics, as well as numerical results on a small network, are presented.

, 38 pages