Optimization Online


Dominance in Pricing Problems with Stochasticity

Natashia Boland(natashia.boland***at***isye.gatech.edu)
Sophie Dickson(sophiedickson***at***gmail.com )
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu)
Karen Smilowitz(ksmilowitz***at***northwestern.edu)

Abstract: Sequencing activities over time is a fundamental optimization problem. The problem can be modeled using a directed network in which activities are represented by nodes and pairs of activities that can be performed consecutively are represented by arcs. A sequence of activities then corresponds to a path in the directed network, and an optimal sequence of activities, assuming appropriately chosen costs on nodes and/or arcs, can then be determined by finding a shortest path in the directed network. In the presence of uncertainty, a stochastic variant of shortest path problem has to be solved, which is far more complex, particularly when the cost of a path depends on a probability distribution function at each node along the path. Calculating a path cost is more time consuming and the dominance between partial paths, which is at the heart of any shortest path algorithm, is no longer clear-cut. In this paper, we identify conditions to establish novel path dominance criteria that can be used to increase the efficiency of label setting algorithms for such problems. We show, using two activity sequencing applications, that these conditions are often satisfied naturally.

Keywords: shortest path, uncertainty, dominance, pricing problem

Category 1: Integer Programming

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 08/03/2015
Entry Accepted: 08/03/2015
Entry Last Modified: 08/03/2015

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