A smoothing heuristic for a bilevel pricing problem

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 tech...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2006-11, Vol.174 (3), p.1396-1413
Main Authors: Dussault, Jean-Pierre, Marcotte, Patrice, Roch, Sébastien, Savard, Gilles
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Bilevel programming
Complementarity
Exact sciences and technology
Flows in networks. Combinatorial problems
Global optimization
Heuristic
Implicit programming
Interior point methods
Mathematical programming
MPEC
Network pricing
Operational research and scientific management
Operational research. Management science
Parameter optimization
Pricing policies
Smoothing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2004.07.076