Scippy

SCIP

Solving Constraint Integer Programs

heur_local.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-2020 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_local.h
17  * @brief Improvement heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements three local search heuristics, namely vertex insertion, key-path exchange and key-vertex elimination,
21  * see "Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck. Furthermore, it includes several non-published local
22  * search heuristics for prize-collecting Steiner problem tree variants.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #ifndef __SCIP_HEUR_LOCAL_H__
29 #define __SCIP_HEUR_LOCAL_H__
30 
31 
32 #include "scip/scip.h"
33 #include "grph.h"
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 /** creates the local primal heuristic and includes it in SCIP */
40  SCIP* scip /**< SCIP data structure */
41  );
42 
43 /** perform local heuristics on a given Steiner tree */
45  SCIP* scip, /**< SCIP data structure */
46  GRAPH* graph, /**< graph data structure */
47  const SCIP_Real* cost, /**< arc cost array */
48  int* best_result /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
49  );
50 
51 
52 
53 /** greedy extension local heuristic for (R)PC and MW */
55  SCIP* scip, /**< SCIP data structure */
56  GRAPH* graph, /**< graph data structure */
57  const SCIP_Real* cost, /**< edge cost array*/
58  PATH* path, /**< shortest data structure array */
59  int* stedge, /**< initialized array to indicate whether an edge is part of the Steiner tree */
60  STP_Bool* stvertex, /**< uninitialized array to indicate whether a vertex is part of the Steiner tree */
61  SCIP_Bool* extensions /**< pointer to store whether extensions have been made */
62 );
63 
64 #ifdef __cplusplus
65 }
66 #endif
67 
68 #endif
Definition: grph.h:57
SCIP_RETCODE SCIPStpIncludeHeurLocal(SCIP *scip)
Definition: heur_local.c:2272
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPStpHeurLocalExtendPcMw(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, PATH *path, int *stedge, STP_Bool *stvertex, SCIP_Bool *extensions)
Definition: heur_local.c:1692
unsigned char STP_Bool
Definition: grph.h:52
#define SCIP_Bool
Definition: def.h:70
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *best_result)
Definition: heur_local.c:208
#define SCIP_Real
Definition: def.h:163
SCIP callable library.