Scippy

SCIP

Solving Constraint Integer Programs

heur_tm.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_tm.h
17  * @brief shortest paths based primal heuristics for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Daniel Rehfeldt
21  * @author Michael Winkler
22  *
23  * This file implements several shortest paths based primal heuristics for Steiner problems, see
24  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" by
25  * Gamrath, Koch, Maher, Rehfeldt and Shinano
26  *
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #ifndef __SCIP_HEUR_TM_H__
32 #define __SCIP_HEUR_TM_H__
33 
34 #include "scip/scip.h"
35 #include "grph.h"
36 
37 #define DEFAULT_HOPFACTOR 0.33
38 
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42 
43 /** compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics */
46  GRAPH* graph, /**< graph data structure */
47  int* starts, /**< starting points array */
48  int* runs /**< pointer to number of runs */
49  );
50 
51 /** creates the TM primal heuristic and includes it in SCIP */
54  SCIP* scip /**< SCIP data structure */
55  );
56 
57 /** execute shortest paths heuristic to obtain a Steiner tree */
60  SCIP* scip, /**< SCIP data structure */
61  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
62  GRAPH* graph, /**< graph data structure */
63  int* starts, /**< array containing start vertices (NULL to not provide any) */
64  int* bestnewstart, /**< pointer to the start vertex resulting in the best soluton */
65  int* best_result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
66  int runs, /**< number of runs */
67  int bestincstart, /**< best incumbent start vertex */
68  SCIP_Real* cost, /**< arc costs */
69  SCIP_Real* costrev, /**< reversed arc costs */
70  SCIP_Real* hopfactor, /**< edge cost multiplicator for HC problems */
71  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
72  SCIP_Real maxcost, /**< maximal edge cost (only for HC) */
73  SCIP_Bool* success, /**< pointer to store whether a solution could be found */
74  SCIP_Bool pcmwfull /**< use full computation of tree (i.e. connect all terminals and prune), only for prize-collecting variants */
75  );
76 
77 /** run shortest path heuristic, but bias edge costs towards best current LP solution */
80  SCIP* scip, /**< SCIP data structure */
81  GRAPH* graph, /**< graph data structure */
82  SCIP_HEUR* heur, /**< heuristic or NULL */
83  int* result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
84  int runs, /**< number of runs */
85  SCIP_Real* cost, /**< arc costs (uninitialized) */
86  SCIP_Real* costrev, /**< reversed arc costs (uninitialized) */
87  SCIP_Bool* success /**< pointer to store whether a solution could be found */
88  );
89 
90 /** prune a Steiner tree in such a way that all leaves are terminals */
93  SCIP* scip, /**< SCIP data structure */
94  const GRAPH* g, /**< graph structure */
95  const SCIP_Real* cost, /**< edge costs */
96  int layer, /**< layer, @note: should be set to 0 */
97  int* result, /**< ST edges */
98  STP_Bool* connected /**< ST nodes */
99  );
100 
101 /** prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals */
104  SCIP* scip, /**< SCIP data structure */
105  const GRAPH* g, /**< graph structure */
106  const SCIP_Real* cost, /**< edge costs */
107  int* result, /**< ST edges */
108  STP_Bool* connected /**< ST nodes */
109  );
110 
111 /** build (rooted) prize collecting Steiner tree in such a way that all leaves are positive-weight vertices */
114  SCIP* scip, /**< SCIP data structure */
115  const GRAPH* g, /**< graph structure */
116  PATH* mst, /**< path data structure array */
117  const SCIP_Real* cost, /**< edge costs */
118  SCIP_Real* objresult, /**< pointer to store objective value of result */
119  int* connected /**< CONNECT/UNKNOWN */
120  );
121 
122 /** build Steiner tree in such a way that all leaves are terminals */
125  SCIP* scip, /**< SCIP data structure */
126  const GRAPH* g, /**< graph structure */
127  PATH* mst, /**< path data structure array */
128  const SCIP_Real* cost, /**< edge costs */
129  SCIP_Real* objresult, /**< pointer to store objective value of result */
130  int* connected /**< CONNECT/UNKNOWN */
131  );
132 
133 /** prune a degree constrained Steiner tree in such a way that all leaves are terminals */
136  SCIP* scip, /**< SCIP data structure */
137  const GRAPH* g, /**< graph structure */
138  int* result, /**< ST edges */
139  STP_Bool* connected /**< ST nodes */
140  );
141 
142 #ifdef __cplusplus
143 }
144 #endif
145 
146 #endif
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:167
Definition: grph.h:57
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:732
#define SCIP_EXPORT
Definition: def.h:98
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_EXPORT SCIP_RETCODE SCIPStpIncludeHeurTM(SCIP *scip)
Definition: heur_tm.c:2832
unsigned char STP_Bool
Definition: grph.h:52
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, SCIP_HEURDATA *heurdata, GRAPH *graph, int *starts, int *bestnewstart, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Real maxcost, SCIP_Bool *success, SCIP_Bool pcmwfull)
Definition: heur_tm.c:1649
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMBuildTree(SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:653
includes various files containing graph methods used for Steiner tree problems
SCIP_EXPORT void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:114
#define SCIP_Real
Definition: def.h:164
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Bool *success)
Definition: heur_tm.c:2352
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMPrune(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
Definition: heur_tm.c:555
SCIP_EXPORT SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:382
SCIP callable library.