Optimization Online


Optimization Models for Differentiating Quality of Service Levels in Probabilistic Network Capacity Design Problems

Siqian Shen(siqian***at***umich.edu)
Zhihao Chen(czhihao***at***umich.edu)

Abstract: This paper develops various chance-constrained models for optimizing the probabilistic network design problem (PNDP), where we differentiate the quality of service (QoS) and measure the related network performance under uncertain demand. The upper level problem of PNDP designs continuous/discrete link capacities shared by multi-commodity flows, and the lower level problem differentiates the corresponding QoS for demand satisfaction, to prioritize customers and/or commodities. We consider PNDP variants that have either fixed flows (formulated at the upper level) or recourse flows (at the lower level) according to different applications. We transform each probabilistic model into a mixed-integer program, and derive polynomial-time algorithms for special cases with single-row chance constraints. The paper formulates benchmark stochastic programming models by either enforcing to meet all demand or penalizing unmet demand via a linear penalty function. We compare different models and approaches by testing randomly generated network instances and an instance built on the Sioux-Falls network. Numerical results demonstrate the computational efficacy of the solution approaches and derive managerial insights.

Keywords: Network design problem; Quality of Service (QoS); Chance-constrained programming; Stochastic programming; Mixed-integer linear programming; Multi-commodity network flows

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 09/29/2013
Entry Accepted: 10/01/2013
Entry Last Modified: 09/29/2013

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