SCIP-Jack: A Solver for Steiner Tree Problems in Graphs and their Relatives

Speaker: 

Prof. Thorsten Koch

Affiliation: 

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

Date: 

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

Venue: 

RC-1043, The Red Centre, UNSW

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.

 

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.

School Seminar Series: