[Zurück]

M. Leitner, I. Ljubic, M. Sinnl:
"Solving the bi-objective prize-collecting Steiner tree problem with the e-constraint method";
Vortrag: International Network Optimization Conference (INOC), Teneriffa; 20.05.2013 - 22.05.2013; in: "Proceedings of INOC 2013", Electronic Notes in Discrete Mathematics, Volume 41 (2013), S. 181 - 188.

In this paper, we study the bi-objective prize-collecting Steiner tree problem, whose
goal is to find a subtree that minimizes the edge costs for building that tree, and,
at the same time, to maximize the collected node revenues. We propose to solve
the problem using an -constraint algorithm. This is an iterative mixed-integer-
programming framework that identifies one solution for every point on the Pareto
front. In this framework, a branch-and-cut approach for the single-objective variant
of the problem is enhanced with warm-start procedures that are used to (i) generate
feasible solutions, (ii) generate violated cutting planes, and (iii) guide the branching
process. Standard benchmark instances from the literature are used to assess the
efficacy of our method.

http://dx.doi.org/10.1016/j.endm.2013.05.068

http://publik.tuwien.ac.at/files/PubDat_222023.pdf