Steiner Problem Application (Branch-and-cut): Overview

Author: Daniel Rehfeldt; Gerald Gamrath; Thorsten Koch; Stephen Maher; Yuji Shinano; Michael Winkler

This application contains the branch-and-cut based solver SCIP-Jack for Steiner tree problems, realized within the framework SCIP, see: "A generic approach to solving the Steiner tree problem and variants" by D. Rehfeldt. The following plugins are implemented:

a problem reader, which parses the problem out of a .stp file (reader_stp.c)
a (global) problem data structure, containing all necessary information including the graph, which creates the model within SCIP (probdata_stp.c)
a construction heuristic (heur_tm.c)
an improvment heuristic (heur_local.c)
a recombination heuristic (heur_rec.c)
a, by default deactivated, pricer, which generates new variables/columns during the search (pricer_stp.c)
a constraint handler, which checks solutions for feasibility and separates any violated model constraints (cons_stp.c)
a propagator, which attempts to fix (edge) variables to zero utilizing their reduced costs (prop_stp.c)
an event handler, which simply writes each incumbent solution to a file – if activated (event_bestsol.c)

In the following the problem is introduced and the solving process is delineated. Furthermore, the two main plugins are sketched.