Optimization Online


Efficient Heuristic Algorithms for Maximum Utility Product Pricing Problems

T. G. J. Myklebust(tmyklebu***at***csclub.uwaterloo.ca)
M. A. Sharpe(masharpe***at***math.uwaterloo.ca)
Levent Tuncel(ltuncel***at***math.uwaterloo.ca)

Abstract: We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980's and in the early 1990's. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more recent ideas, some from the theoretical computer science literature, for closely related problems. We provide very efficient implementations of the algorithms of Dobson and Kalish as well as our new algorithms. We show that our improvements lead to algorithms which generate solutions with better objective values and that are more robust in overall performance. Our computational experiments indicate that our implementation of Dobson-Kalish heuristics and our new algorithms can provide good solutions for the underlying MIP problems where the typical LP relaxations would have more than a trillion variables and more than three trillion constraints.

Keywords: mixed integer programming, network flow problems, total unimodularity, optimal product pricing

Category 1: Applications -- OR and Management Sciences

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

Category 3: Combinatorial Optimization

Citation: Research Report, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1, November 2012.

Download: [PDF]

Entry Submitted: 11/19/2012
Entry Accepted: 11/19/2012
Entry Last Modified: 11/19/2012

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