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-2022 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 scipopt.org. */
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 "graph.h"
36 
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 #define DEFAULT_HOPFACTOR 0.33
43 
44 
45 /** TM mode for PC/MW
46  * NOTE: bias_simple is only used for PC/RPC */
49 
50 
51 /** compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics */
52 SCIP_EXPORT
54  GRAPH* graph, /**< graph data structure */
55  int* starts, /**< starting points array */
56  int* runs /**< pointer to number of runs */
57  );
58 
59 /** creates the TM primal heuristic and includes it in SCIP */
60 SCIP_EXPORT
62  SCIP* scip /**< SCIP data structure */
63  );
64 
65 /** execute shortest paths heuristic to obtain a Steiner tree */
66 SCIP_EXPORT
68  SCIP* scip, /**< SCIP data structure */
69  enum PCMW_TmMode pcmw_tmmode, /**< mode for PC/MW */
70  GRAPH* graph, /**< graph data structure */
71  int* starts, /**< array containing start vertices (NULL to not provide any) */
72  const SCIP_Real* prize, /**< prizes (for PCMW) or NULL */
73  int* best_result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
74  int runs, /**< number of runs */
75  int bestincstart, /**< best incumbent start vertex */
76  SCIP_Real* cost, /**< arc costs */
77  SCIP_Real* costrev, /**< reversed arc costs */
78  SCIP_Real* hopfactor, /**< edge cost multiplicator for HC problems */
79  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
80  SCIP_Bool* success /**< pointer to store whether a solution could be found */
81  );
82 
83 /** run shortest path heuristic, but bias edge costs towards best current LP solution */
84 SCIP_EXPORT
86  SCIP* scip, /**< SCIP data structure */
87  GRAPH* graph, /**< graph data structure */
88  SCIP_HEUR* heur, /**< heuristic or NULL */
89  int* result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
90  int runs, /**< number of runs */
91  SCIP_Bool* success /**< pointer to store whether a solution could be found */
92  );
93 
94 /** build (rooted) prize collecting Steiner tree in such a way that all leaves are positive-weight vertices */
95 SCIP_EXPORT
97  SCIP* scip, /**< SCIP data structure */
98  const GRAPH* g, /**< graph structure */
99  SCIP_Bool useRootSym, /**< use? */
100  PATH* mst, /**< path data structure array */
101  const SCIP_Real* cost, /**< edge costs */
102  SCIP_Real* objresult, /**< pointer to store objective value of result */
103  int* connected /**< CONNECT/UNKNOWN */
104  );
105 
106 /** build Steiner tree in such a way that all leaves are terminals */
107 SCIP_EXPORT
109  SCIP* scip, /**< SCIP data structure */
110  GRAPH* g, /**< graph structure */
111  PATH* mst, /**< path data structure array */
112  const SCIP_Real* cost, /**< edge costs */
113  SCIP_Real* objresult, /**< pointer to store objective value of result */
114  int* connected /**< CONNECT/UNKNOWN */
115  );
116 
117 /** prune a degree constrained Steiner tree in such a way that all leaves are terminals */
118 SCIP_EXPORT
120  SCIP* scip, /**< SCIP data structure */
121  const GRAPH* g, /**< graph structure */
122  int* result, /**< ST edges */
123  STP_Bool* connected /**< ST nodes */
124  );
125 
126 #ifdef __cplusplus
127 }
128 #endif
129 
130 #endif
SCIP_RETCODE SCIPStpIncludeHeurTM(SCIP *scip)
Definition: heur_tm.c:3711
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:3226
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Bool *success)
Definition: heur_tm.c:3509
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
PCMW_TmMode
Definition: heur_tm.h:47
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
unsigned char STP_Bool
Definition: portab.h:34
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
#define SCIP_Real
Definition: def.h:177
SCIP callable library.