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

作者：Leitner Markus^*; Ljubic Ivana; Sinnl Markus

来源：INFORMS Journal on Computing, 2015, 27(1): 118-134.

DOI：10.1287/ijoc.2014.0614

• bicriteria
• optimization
• mixed-integer programming
• is an element of-constraint method
• two-phase method
• Chebyshev norm method

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 is an element of-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 (i) additional strengthening valid inequalities, (ii) procedures for initializing feasible solutions (using a solution pool), (iii) procedures for recycling violated cuts (using a cut pool), and (iv) 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.

• 出版日期2015