Optimization Online


Valid inequalities and Branch-and-Cut for the Clique Pricing Problem

Géraldine Heilporn (Geraldine.Heilporn***at***hec.ca)
Martine Labbé (mlabbe***at***ulb.ac.be)
Patrice Marcotte (marcotte***at***iro.umontreal.ca)
Gilles Savard (gilles.savard***at***polymtl.ca)

Abstract: Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. Following a proof that clique pricing is NP-hard, we propose strong valid inequalities, some of which define facets of the 2-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework.

Keywords: Network pricing, mixed-integer programming, combinatorial optimization / Tarification de réseaux, optimisation combinatoire, programmation mixte entière

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )



Entry Submitted: 06/02/2009
Entry Accepted: 06/02/2009
Entry Last Modified: 05/03/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society