SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
|
xternal.c
Go to the documentation of this file.
26 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 36 * This application contains the branch-and-cut based solver SCIP-Jack for Steiner tree problems, realized within the framework 37 * \SCIP, see: "A generic approach to solving the Steiner tree problem and variants" by D. Rehfeldt. The following plugins are implemented: 41 * - a (global) problem data structure, containing all necessary information including the graph, which creates the model within \SCIP (probdata_stp.c) 45 * - a, by default deactivated, pricer, which generates new variables/columns during the search (pricer_stp.c) 46 * - a constraint handler, which checks solutions for feasibility and separates any violated model constraints (cons_stp.c) 47 * - a propagator, which attempts to fix (edge) variables to zero utilizing their reduced costs (prop_stp.c) 48 * - an event handler, which simply writes each incumbent solution to a file -- if activated (event_bestsol.c) 50 * In the following the problem is introduced and the solving process is delineated. Furthermore, the two main plugins are 62 * The Steiner tree problem in graphs (SPG) can be described as follows: Given an undirected connected graph 63 * \f$ G=(V,E)\f$, costs \f[ c: E \rightarrow \mathcal{Q}^+ \f] and a set \f$ T \subset V \f$ of terminals, 64 * the problem is to find a minimum-weight tree \f$ S\subseteq G \f$ that spans \f$ T \f$. Each tree \f$ S \f$ that spans \f$ T \f$, called Steiner tree, is 75 * First, problem specific preprocessing is extremely important. Apart from some pathological instances 76 * specifically constructed to defy presolving techniques, preprocessing is often able to significantly 79 * Second, heuristics are needed, especially for hard instances, to find good or even optimal solutions. 81 * Finally, the core of our approach is constituted by a branch-and-cut procedure used to compute lower bounds and prove optimality. 83 * The problem can be formulated using the directed equivalent of the SPG, the Steiner arborescence problem (SAP): 84 * Given a directed graph \f$ D=(V,A) \f$, a root \f$ r \in V \f$, costs \f$ c: A \rightarrow \mathcal{Q}^+ \f$ 86 * for all \f$ t \in T \f$, \f$ S \f$ contains exactly one directed path from \f$ r \f$ to \f$ t \f$ is called Steiner arborescence. 87 * Thereupon, a Steiner arborescence \f$ S = (V_S, A_S) \f$ is required that minimizes \f$ \sum_{a \in A_S} c_a \f$. An SPG can be 88 * transformed to an SAP by replacing each edge with two anti-parallel arcs of the same cost and distinguishing an arbitrary 89 * terminal as the root. This transformation results in a one-to-one correspondence between the respective solution sets. 90 * Introducing variables \f$y_a\f$ for \f$a\in A\f$ with the interpretation that \f$y_a:=1\f$ if and only if \f$a\f$ is in the 115 * where \f$N=V\setminus T\f$, \f$\delta^+(X):=\{(u,v)\in A| u\in X, v\in V\setminus X\}\f$, \f$\delta^-(X):= \delta^+(V \setminus X)\f$ for 116 * \f$X\subset V\f$ i.e., \f$\delta^+(X)\f$ is the set of all arcs going out of and \f$\delta^-(X)\f$ the set of all arcs going into \f$X\f$. 118 * Since the model potentially contains an exponential number of constraints, a separation approach is employed. 121 * In addition to Steiner problems in graphs there exist several variations. The following Steiner problem variants can be solved by SCIP-JACK, 122 * by transforming them to a Steiner arborescence problem, and in some cases introducing additional constraints: 150 * The Makefile is based on the main \SCIP Makefile. This means that all compiling options which are |