  


MixedInteger Programming Models and Polynomialtime Algorithms for Solving Probabilistic Multicommodity Flow Capacity Expansion Problems
Siqian Shen(siqianumich.edu) Abstract: As one of the classical network flow problems, multicommodity flow problem arises in many transportation applications, including airline scheduling, signal routing, and evacuation planning. This paper analyzes capacityexpansion variants of the multicommodity flow problem under demand uncertainty, and optimizes the overall transportation and capacityexpansion cost while chance constraints to restrict demand losses. The paper studies four model variants as follows. A basic model formulates a joint chance constraint to guarantee the probability of positive demand loss at any node with respect to any commodity being no more than a risk tolerance. Model 1 allows riskcontrol flexibility, and imposes a singlerow chance constraint for a loss of every commodity at every demand node. Such individual risk tolerances permit considerations of heterogeneous risk perceptions. Model 2 and Model 3 transform the joint chance constraint in the basic model into several smallerscale constraints, each of which is a joint chance constraint for bounding demand loss of each commodity (Model 2) or demand loss at each node (Model 3). The paper employs mixedinteger programming techniques for solving each probabilistic model, and derives polynomialtime algorithms for models with singlerow chance constraints. Moreover, we analyze the solution relationship among different models to generate valid objective bounds to each other. The computational efficacy of our approaches are demonstrated on a set of randomly generated graph instances with diverse settings. Keywords: Multicommodity flow, capacity expansion, joint chance constraint, mixedinteger programming Category 1: Stochastic Programming Category 2: Network Optimization Category 3: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Department of Industrial and Operations Engineering, University of Michigan, May 2012. Download: [PDF] Entry Submitted: 06/10/2012 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  