An exact algorithm for the network pricing problem

Brotcorne, Luce; Cirinei, Fabien; Marcotte, Patrice; Savard, Gilles

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.disopt.2010.09.003

Titre :

An exact algorithm for the network pricing problem

Auteur(s) :

Brotcorne, Luce [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Cirinei, Fabien [Auteur]
ExPretio
Marcotte, Patrice [Auteur]
Département d'Informatique et de Recherche Opérationnelle [Montreal] [DIRO]
Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT]
Savard, Gilles [Auteur]
Département de Mathématiques et de Génie Industriel [MAGI]
Groupe d’études et de recherche en analyse des décisions [GERAD]

Titre de la revue :

Discrete Optimization

Pagination :

246-258

Éditeur :

Elsevier

Date de publication :

2011-05

ISSN :

1572-5286

Mot(s)-clé(s) en anglais :

Pricing
Bilevel programming
Networks
Column generation
Combinatorial optimization

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [en]

This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved ...
Lire la suite >This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :