Scippy

SCIP

Solving Constraint Integer Programs

STP
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)
  • 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.

  1. Problem description and solving approach
  2. Main problem data, creating the problem
  3. Separating violated constraints
  4. Graph minimum cut routine
  5. Miscellaneous methods used for Steiner tree problems

Installation

See the Install file