NDLI: Exact solutions for the robust prize-collecting steiner tree problem

Content Provider	IEEE Xplore Digital Library
Author	Alvarez-Miranda, E. Ljubic, I. Toth, P.
Copyright Year	2011
Description	Author affiliation: DEIS, Università di Bologna, Italy (Toth, P.) \|\| DEIS Università di Bologna, Italy (Alvarez-Miranda, E.) \|\| Department of Statistics and Operations Research, University of Vienna, Austria (Ljubic, I.)
Abstract	We consider a combinatorial optimization problem that models an expansion of fiber optic telecommunication networks. Thereby, we are given a set of customers with potential gains of revenue and the set of edges with fixed installation costs. The goal is to decide which customers to connect to a given root node so that the sum of edge costs plus the node revenues for the nodes that are left out from the solution is minimized. The problem is known in the literature as the Prize-Collecting Steiner Tree Problem (PCStT). In many applications it is unrealistic to assume that the gains of revenue or installation costs are known in advance. In this paper, we extend this well-studied deterministic problem by considering the robust optimization approach in which the input parameters are subject to interval uncertainty. To control the level of conservatism of the solution, we consider Bertsimas & Sim robust optimization approach. We propose a branch-and-cut approach to solve this problem to optimality and provide an extensive computational study on a set of benchmark instances that are adapted from those previously used to solve the deterministic version of the problem. We show how the price of robustness influences the costs of the solutions and the algorithm performance.
Starting Page	1
Ending Page	7
File Size	755249
Page Count	7
File Format	PDF
ISBN	9781457706820
ISSN	2157023X
e-ISBN	9789638111777
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-10-05
Publisher Place	Hungary
Access Restriction	Subscribed
Rights Holder	HTE
Subject Keyword	Algorithm design and analysis Steiner trees Uncertainty Biological system modeling Robustness Data models Optimization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exact Solutions for the Robust Prize-Collecting Steiner Tree Problem

A matheuristic algorithm for the Prize-collecting Steiner Tree Problem

Finding Provably Optimal Solutions for the (Prize Collecting) Steiner Tree Problem (2005)

The Fractional Prize-Collecting Steiner Tree Problem on Trees (Extended Abstract) (2003)

A Note on Johnson, Minkoff and Phillips’ Algorithm for the Prize-Collecting Steiner Tree Problem

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree

Exact Approaches for Solving Robust Prize-Collecting Steiner Tree Problems (2012)

Solving the Prize-Collecting Steiner Tree Problem to Optimality (2004)

Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks

Exact solutions for the robust prize-collecting steiner tree problem

Similar Documents

Exact Solutions for the Robust Prize-Collecting Steiner Tree Problem

A matheuristic algorithm for the Prize-collecting Steiner Tree Problem

Finding Provably Optimal Solutions for the (Prize Collecting) Steiner Tree Problem (2005)

The Fractional Prize-Collecting Steiner Tree Problem on Trees (Extended Abstract) (2003)

A Note on Johnson, Minkoff and Phillips’ Algorithm for the Prize-Collecting Steiner Tree Problem

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree

Exact Approaches for Solving Robust Prize-Collecting Steiner Tree Problems (2012)

Solving the Prize-Collecting Steiner Tree Problem to Optimality (2004)

Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks

Exact solutions for the robust prize-collecting steiner tree problem