Mixed-Integer Programming Models and Polynomial-time Algorithms for Solving Probabilistic Multicommodity Flow Capacity Expansion Problems
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 capacity-expansion variants of the multicommodity flow problem under demand uncertainty, and optimizes the overall transportation and capacity-expansion 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 risk-control flexibility, and imposes a single-row 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 smaller-scale 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 mixed-integer programming techniques for solving each probabilistic model, and derives polynomial-time algorithms for models with single-row 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, mixed-integer 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.
Entry Submitted: 06/10/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|