Optimization Online


Mixed-Integer Programming Models and Polynomial-time Algorithms for Solving Probabilistic Multicommodity Flow Capacity Expansion Problems

Siqian Shen(siqian***at***umich.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 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.

Download: [PDF]

Entry Submitted: 06/10/2012
Entry Accepted: 06/11/2012
Entry Last Modified: 06/10/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