To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.07.076 Byline: Jean-Pierre Dussault (a), Patrice Marcotte (b), Sebastien Roch (c), Gilles Savard (d) Keywords: Global optimization; Bilevel programming; Interior point methods; Smoothing; Implicit programming; MPEC; Complementarity; Network pricing Abstract: In this paper, we provide a heuristic procedure, that performs well from a global optimality point of view, for an important and difficult class of bilevel programs. The algorithm relies on an interior point approach that can be interpreted as a combination of smoothing and implicit programming techniques. Although the algorithm cannot guarantee global optimality, very good solutions can be obtained through the use of a suitable set of parameters. The algorithm has been tested on large-scale instances of a network pricing problem, an application that fits our modeling framework. Preliminary results show that on hard instances, our approach constitutes an alternative to solvers based on mixed 0-1 programming formulations. Author Affiliation: (a) Departement de Mathematiques et d'Informatique, Universite de Sherbrooke, Sherbrooke, Que., Canada (b) Departement d'Informatique et de Recherche Operationnelle, Universite de Montreal, Montreal, Que., Canada (c) Department of Statistics, University of California, Berkeley, CA, USA (d) Departement de Mathematiques et de Genie Industriel, Ecole Polytechnique de Montreal, C.P. 6079, Succ. Centre-ville, Montreal, Que., Canada Article History: Received 5 January 2004; Accepted 1 July 2004