A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem

摘要

We introduce the bi-objective prize-collecting Steiner tree problem, whose goal is to find a subtree considering the conflicting objectives of minimizing the edge costs for building that tree, and maximizing the collected node revenues. We consider five iterative mixed-integer programming (MIP) frameworks that identify the complete Pareto front, i.e., one efficient solution for every point on the Pareto front. More precisely, the following methods are studied: an e-constraint method, a two-phase method, a binary search in the objective space, a weighted Chebyshev norm method, and a method of Sylva and Crema. We also investigate how to exploit and recycle information gained during these iterative MIP procedures to accelerate the solution process. We consider (ⅰ) additional strengthening valid inequalities, (ⅱ) procedures for initializing feasible solutions (using a solution pool), (ⅲ) procedures for recycling violated cuts (using a cut pool), and (ⅳ) guiding the branching process by previously detected Pareto optimal solutions. This work is a first study on exact approaches for solving the bi-objective prize-collecting Steiner tree problem. Standard benchmark instances from the literature are used to assess the efficacy of the proposed methods.