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

This application contains the branch-and-cut based solver SCIP-Jack for Steiner tree and related problems, realized within the framework SCIP. See the doctoral thesis: "Faster algorithms for Steiner tree and related problems: From theory to practice" by Daniel Rehfeldt for more details. See also https://scipjack.zib.de. This application includes (among others):

problem readers, which parse the problem out of .stp or .gr files (reader_stp.c, reader_gr.c)
a (global) problem data structure, containing all necessary information including the graph, which creates the model within SCIP (probdata_stp.c)
various algorithms and data structures for handling Steiner tree graphs (graph_base.c, graph_edge.c, graph_history.c, graph_mcut.c, graph_path.c, graph_save.c, graph_stats.c, graph_tpath.c, graph_util.c graph_delpseudo.c, graph_grid.c, graph_load.c, graph_node.c, graph_pcbase.c, graph_sdpath.c, graph_sub.c, graph_trans.c, graph_vnoi.c)
decomposition methods (bidecomposition.c, cons_stpcomponents.c)
algorithms to solve fixed-parameter tractable (sub-)problems (dpborder_base.c, dpborder_core.c, dpborder_util.c, dpterms_base.c, dpterms_core.c, dpterms_util.c, enumeration.c)
various primal heuristics (heur_tm.c, heur_prune.c, heur_ascendprune.c, heur_slackprune.c, heur_local.c, heur_rec.c)
a dual heuristic (dualascent.c)
various reduction techniques (reduce_alt.c, reduce_bnd.c, reduce_ext.c, reduce_pcsimple.c, reduce_sdcomp.c, reduce_sdutil.c, reduce_simple.c, reduce_termsepa.c,reduce_termsepafull.c, reduce_base.c, reduce_da.c, reduce_path.c, reduce_sd.c, reduce_sdgraph.c, reduce_sepa.c, reduce_sol.c, reduce_termsepada.c, reduce_util.c)
extended reduction techniques (extreduce_base.c, extreduce_contract.c, extreduce_data.c, extreduce_dist.c, extreduce_extmst.c, extreduce_mldists.c, extreduce_util.c, extreduce_bottleneck.c, extreduce_core.c, extreduce_dbg.c, extreduce_extmstbiased.c, extreduce_extspg.c, extreduce_redcosts.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, or detects infeasiblity (prop_stp.c)
relaxation handlers, for example to detect and efficiently solve fixed-parameter tractable instances (relax_stp.c, relax_stpdp.c, relax_stpenum.c)
a branching rule (branch_stp.c)
generic data-structures and algorithms (stpvector.h, stpbitset.h, stpprioqueue.c, misc_stp.c, mst.c)

In the following, the problem is introduced and the solving process is delineated. Next, two main plugins are sketched. Finally, information on reading a problem and on writing a solution found by SCIP-Jack is given.

Installation

See the Install file, application "stp" (for Make) or "scipstp" (for CMake)