Abstract: 

The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, we will present a general-purpose solver that can be used to compute optimal solutions to both the classical Steiner tree problem and many of its variants without modification.

Speaker

Prof. Thorsten Koch

Research Area
Affiliation

Technische Universitaet (TU) and Zuse Institute Berlin (ZIB)

Date

Tue, 31/10/2017 - 3:30pm

Venue

RC-1043, The Red Centre, UNSW

In particular, the following problem classes can be solved:

  • Steiner Tree in Graphs (STP),
  • Steiner Arborescence (SAP),
  • Rectilinear Steiner Minimum Tree (RSMTP),
  • Node-weighted Steiner Tree (NWSTP),
  • Prize-collecting Steiner Tree (PCSTP),
  • Rooted Prize-collecting Steiner Tree (RPCSTP),
  • Maximum-weight Connected Subgraph (MWCSP),
  • Degree-constrained Steiner Tree (DCSTP),
  • Group Steiner Tree (GSTP), and
  • Hop-constrained Directed Steiner Tree (HCDSTP).

This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.

 

SCIP-Jack has participated in the 11th DIMACS Implementation Challenge and been demonstrated to be the fastest solver in two categories. Since the Challenge tremendous progress regarding new solving routines such as transformation, preprocessing and heuristics was made, resulting in a reduction of the runtime of more than two orders of magnitude for many instances. The talk will report on the latest developments.