Mathematical programming approaches for dual multicast routing problem with multilayer risk cost

Liang, Zhe; Lee, Chungmok; Chaovalitwongse, W.
March 2013
Annals of Operations Research;Mar2013, Vol. 203 Issue 1, p101
Academic Journal
This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to find two redundant multicast trees, each from one of the two sources to every destination at a minimum cost. The cost of the problem contains two parts: the multicast routing cost and the shard common risk cost. Such common risk could cause the failures of multiple links simultaneously. Therefore, the DMR-SRLGD ensures the availability and reliability of multicast service. We formulate an edge-based model for the DMR-SRLGD. In addition, we also propose a path-based model that rises from the Dantzig-Wolfe decomposition of the edge-based model, and develop a column-generation framework to solve the linear relaxation of the path-based formulation. We then employ a branch-and-price solution method to find integer solutions to DMR-SRLGD. We also extend both edge-based and path-based models to handle the complex quality of service requirements. The computational results show the edge-based model is superior than the path-based model for the easy and small test instances, whereas the path-based model provides better solutions in a timely fashion for hard or large test instances.


Related Articles

  • Robust delay-constrained routing in telecommunications. Hijazi, Hassan; Bonami, Pierre; Ouorou, Adam // Annals of Operations Research;Jul2013, Vol. 206 Issue 1, p163 

    In telecommunications, operators usually use market surveys and statistical models to estimate traffic evolution in networks or to approximate queuing delay functions in routing strategies. Many research activities concentrated on handling traffic uncertainty in network design. Measurements on...

  • A cross-layer QoS-aware optimization protocol for guaranteed data streaming over wireless body area networks. Ababneh, Nedal; Timmons, Nicholas; Morrison, Jim // Telecommunication Systems;Feb2015, Vol. 58 Issue 2, p179 

    In this paper, we study the problem of routing, bandwidth and flow assignment in wireless body area networks (BANs). We present an adaptive joint routing and bandwidth allocation protocol for traffic streaming in BAN. Our solution considers BAN for real-time data streaming applications, where...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • On reduction of the multistage problem of stochastic programming with quantile criterion to the problem of mixed integer linear programming. Kibzun, A.; Khromova, O. // Automation & Remote Control;Apr2014, Vol. 75 Issue 4, p688 

    Consideration was given to the a priori formulation of the multistage problem of stochastic programming with a quantile criterion which is reducible to the two-stage problem. Equivalence of the two-stage problems with the quantile criterion in the a priori and a posteriori formulations was...

  • A MIP-based framework and its application on a lot sizing problem with setup carryover. Caserta, Marco; Voß, Stefan // Journal of Heuristics;Apr2013, Vol. 19 Issue 2, p295 

    In this paper we present a framework to tackle mixed integer programming problems based upon a 'constrained' black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to...

  • Optimal Cardinality Constrained Portfolio Selection. Jianjun Gao; Duan Li // Operations Research;May/Jun2013, Vol. 61 Issue 3, p745 

    One long-standing challenge in both the optimization and investment communities is to devise an efficient algorithm to select a small number of assets from an asset pool such that a portfolio objective is optimized. This cardinality constrained investment situation naturally arises due to the...

  • Undercover: a primal MINLP heuristic exploring a largest sub-MIP. Berthold, Timo; Gleixner, Ambros // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p315 

    We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each...

  • A scenario-based mixed integer linear programming model for composite power system expansion planning with greenhouse gas emission controls. Chang, Mei-Shiang // Clean Technologies & Environmental Policy;Aug2014, Vol. 16 Issue 6, p1001 

    In this paper, the influence of uncertain factors in the power supply system is considered by applying scenario-based programming techniques. A multi-period network design model for composite power system expansion planning is formulated as a mixed integer programming model. This model aims to...

  • A novel probabilistic formulation for locating and sizing emergency medical service stations. Zhang, Zhi-Hai; Li, Kang // Annals of Operations Research;Jun2015, Vol. 229 Issue 1, p813 

    The paper proposes a novel probabilistic model with chance constraints for locating and sizing emergency medical service stations. In this model, the chance constraints are approximated as second-order cone constraints to overcome computational difficulties for practical applications. The...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics