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-2021 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 "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 */
45  GRAPH* graph, /**< graph data structure */
46  int* starts, /**< starting points array */
47  int* runs /**< pointer to number of runs */
48  );
49 
50 /** creates the TM primal heuristic and includes it in SCIP */
52  SCIP* scip /**< SCIP data structure */
53  );
54 
55 /** execute shortest paths heuristic to obtain a Steiner tree */
57  SCIP* scip, /**< SCIP data structure */
58  SCIP_HEURDATA* heurdata, /**< SCIP data structure */
59  GRAPH* graph, /**< graph data structure */
60  int* starts, /**< array containing start vertices (NULL to not provide any) */
61  int* bestnewstart, /**< pointer to the start vertex resulting in the best soluton */
62  int* best_result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
63  int runs, /**< number of runs */
64  int bestincstart, /**< best incumbent start vertex */
65  SCIP_Real* cost, /**< arc costs */
66  SCIP_Real* costrev, /**< reversed arc costs */
67  SCIP_Real* hopfactor, /**< edge cost multiplicator for HC problems */
68  SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
69  SCIP_Real maxcost, /**< maximal edge cost (only for HC) */
70  SCIP_Bool* success, /**< pointer to store whether a solution could be found */
71  SCIP_Bool pcmwfull /**< use full computation of tree (i.e. connect all terminals and prune), only for prize-collecting variants */
72  );
73 
74 /** run shortest path heuristic, but bias edge costs towards best current LP solution */
76  SCIP* scip, /**< SCIP data structure */
77  GRAPH* graph, /**< graph data structure */
78  SCIP_HEUR* heur, /**< heuristic or NULL */
79  int* result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
80  int runs, /**< number of runs */
81  SCIP_Real* cost, /**< arc costs (uninitialized) */
82  SCIP_Real* costrev, /**< reversed arc costs (uninitialized) */
83  SCIP_Bool* success /**< pointer to store whether a solution could be found */
84  );
85 
86 /** prune a Steiner tree in such a way that all leaves are terminals */
88  SCIP* scip, /**< SCIP data structure */
89  const GRAPH* g, /**< graph structure */
90  const SCIP_Real* cost, /**< edge costs */
91  int layer, /**< layer, @note: should be set to 0 */
92  int* result, /**< ST edges */
93  STP_Bool* connected /**< ST nodes */
94  );
95 
96 /** prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals */
98  SCIP* scip, /**< SCIP data structure */
99  const GRAPH* g, /**< graph structure */
100  const SCIP_Real* cost, /**< edge costs */
101  int* result, /**< ST edges */
102  STP_Bool* connected /**< ST nodes */
103  );
104 
105 /** build (rooted) prize collecting Steiner tree in such a way that all leaves are positive-weight vertices */
107  SCIP* scip, /**< SCIP data structure */
108  const GRAPH* g, /**< graph structure */
109  PATH* mst, /**< path data structure array */
110  const SCIP_Real* cost, /**< edge costs */
111  SCIP_Real* objresult, /**< pointer to store objective value of result */
112  int* connected /**< CONNECT/UNKNOWN */
113  );
114 
115 /** build Steiner tree in such a way that all leaves are terminals */
117  SCIP* scip, /**< SCIP data structure */
118  const GRAPH* g, /**< graph structure */
119  PATH* mst, /**< path data structure array */
120  const SCIP_Real* cost, /**< edge costs */
121  SCIP_Real* objresult, /**< pointer to store objective value of result */
122  int* connected /**< CONNECT/UNKNOWN */
123  );
124 
125 /** prune a degree constrained Steiner tree in such a way that all leaves are terminals */
127  SCIP* scip, /**< SCIP data structure */
128  const GRAPH* g, /**< graph structure */
129  int* result, /**< ST edges */
130  STP_Bool* connected /**< ST nodes */
131  );
132 
133 #ifdef __cplusplus
134 }
135 #endif
136 
137 #endif
SCIP_RETCODE SCIPStpIncludeHeurTM(SCIP *scip)
Definition: heur_tm.c:2832
SCIP_RETCODE SCIPStpHeurTMBuildTree(SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:653
Definition: grph.h:57
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_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
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:732
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
unsigned char STP_Bool
Definition: grph.h:52
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:114
#define SCIP_Bool
Definition: def.h:70
includes various files containing graph methods used for Steiner tree problems
#define SCIP_Real
Definition: def.h:163
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_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:382
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:167
SCIP callable library.