Solving nonlinear bilevel programming models of the equilibrium network design problem: A comparative review

Nonlinear bilevel programming problems, of which the equilibrium network design problem is one, are extremely difficult to solve. Even if an optimum solution is obtained, there is no sure way of knowing whether the solution is the global optimum or not, due to the nonconvexity of the bilevel programming problem. This paper reviews and discusses recent developments in solution methodologies for nonlinear programming models of the equilibrium network design problem. In particular, it provides a primer for descent-type algorithms reported in the technical literature and proposes certain enhancements thereof.