SCIP
Solving Constraint Integer Programs
STP
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)
- shortest path based construction heuristics (heur_tm.c)
- reduction based construction heuristics (heur_prune.c, heur_ascendprune, heur_slackprune)
- improvment heuristics (heur_local.c)
- a recombination heuristic (heur_rec.c)
- basic reduction techniques (reduce_simple.c)
- alternative-based reduction techniques (reduce_alt.c)
- bound-based reduction techniques (reduce_bnd.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.
- Problem description and solving approach
- Main problem data, creating the problem
- Separating violated constraints
- Graph minimum cut routine
- Miscellaneous methods used for Steiner tree problems
Installation
See the Install file