  


Dominance in Pricing Problems with Stochasticity
Natashia Boland(natashia.bolandisye.gatech.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 clearcut. 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 Citation: Download: [PDF] Entry Submitted: 08/03/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  