Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data  

作　　者：Eduardo lvarez-Miranda Alfredo Candia-Vjar Xu-jin CHEN Xiao-dong HU Bi LI 

机构地区：[1]Industrial Management Department,Universidad de Talca,Chile [2]DEI,University of Bologna,Italy [3]Academy of Mathematics and Systems Science,CAS

出　　处：《Acta Mathematicae Applicatae Sinica》2014年第1期1-26,共26页应用数学学报（英文版）

基　　金：Supported in part by the National Natural Science Foundation of China under Grant No.11021161 and 10928102;973 Program of China under Grant No.2011CB80800;Chinese Academy of Sciences under Grant No.kjcx-yw-s7,project grant of"Center for Research and Applications in Plasma Physics and Pulsed Power Technology,PBCT-Chile-ACT 26";Direccio'n de Programas de Investigaci'ón,Universidad de Talca,Chile

摘　　要：Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.

关 键 词：uncertainty modeling prize collecting Steiner tree interval data series-parallel graphs polynomial-time solvability 

分 类 号：O157.5[理学—数学] O211.67[理学—基础数学]