Scippy

SCIP

Solving Constraint Integer Programs

heur_rec.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_rec.h
17  * @brief Primal recombination heuristic for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements a recombination heuristic for Steiner problems, see
21  * "SCIP-Jack - A solver for STP and variants with parallelization extensions" by
22  * Gamrath, Koch, Maher, Rehfeldt and Shinano
23  *
24  */
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #ifndef __SCIP_HEUR_REC_H__
28 #define __SCIP_HEUR_REC_H__
29 
30 #include "scip/scip.h"
31 #include "grph.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /** element of Steiner tree solution pool */
38 typedef struct stp_solution
39 {
41  int* soledges;
42  int index;
43 } STPSOL;
44 
45 /** edge based solution pool for Steiner tree problems (in presolving) */
46 typedef struct stp_solution_pool
47 {
49  int size;
50  int nedges;
51  int maxsize;
52  int maxindex;
53 } STPSOLPOOL;
54 
55 /** run REC heuristic */
56 extern
58  SCIP* scip, /**< SCIP data structure */
59  STPSOLPOOL* pool, /**< solution pool or NULL */
60  SCIP_HEUR* heur, /**< heuristic or NULL */
61  SCIP_HEURDATA* heurdata, /**< heuristic data or NULL */
62  const GRAPH* graph, /**< graph data */
63  SCIP_VAR** vars, /**< variables or NULL */
64  int* newsolindex, /**< index of new solution */
65  int runs, /**< number of runs */
66  int nsols, /**< number of solutions */
67  SCIP_Bool restrictheur, /**< use restricted version of heur? */
68  SCIP_Bool* solfound /**< new solution found? */
69 );
70 
71 
72 /** get solution from index */
73 extern
75  STPSOLPOOL* pool, /**< the pool */
76  const int soindex /**< the index */
77  );
78 
79 /** initializes STPSOL pool */
80 extern
82  SCIP* scip, /**< SCIP data structure */
83  STPSOLPOOL** pool, /**< the pool */
84  const int nedges, /**< number of edges of solutions to be stored in the pool */
85  const int maxsize /**< capacity of pool */
86  );
87 
88 /** tries to add STPSOL to pool */
89 extern
91  SCIP* scip, /**< SCIP data structure */
92  const SCIP_Real obj, /**< objective of solution to be added */
93  const int* soledges, /**< edge array of solution to be added */
94  STPSOLPOOL* pool, /**< the pool */
95  SCIP_Bool* success /**< has solution been added? */
96  );
97 
98 /** frees STPSOL pool */
99 extern
101  SCIP* scip, /**< SCIP data structure */
102  STPSOLPOOL** pool /**< the pool */
103  );
104 
105 /** creates the rec primal heuristic and includes it in SCIP */
106 extern
108  SCIP* scip /**< SCIP data structure */
109  );
110 
111 
112 /** heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective */
113 extern
115  SCIP* scip, /**< SCIP data structure */
116  const GRAPH* graph, /**< graph structure */
117  const int* result, /**< edge solution array (UNKNOWN/CONNECT) */
118  int* newresult, /**< new edge solution array (UNKNOWN/CONNECT) */
119  int* dnodemap, /**< node array for internal use */
120  STP_Bool* stvertex, /**< node array for internally marking solution vertices */
121  SCIP_Bool* success /**< solution improved? */
122  );
123 
124 #ifdef __cplusplus
125 }
126 #endif
127 
128 #endif
void SCIPStpHeurRecFreePool(SCIP *scip, STPSOLPOOL **pool)
Definition: heur_rec.c:925
SCIP_RETCODE SCIPStpIncludeHeurRec(SCIP *scip)
Definition: heur_rec.c:2104
Definition: grph.h:57
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
STPSOL ** sols
Definition: heur_rec.h:48
unsigned char STP_Bool
Definition: grph.h:52
struct stp_solution_pool STPSOLPOOL
SCIP_RETCODE SCIPStpHeurRecInitPool(SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize)
Definition: heur_rec.c:894
SCIP_RETCODE SCIPStpHeurRecExclude(SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success)
Definition: heur_rec.c:1595
#define SCIP_Bool
Definition: def.h:69
struct stp_solution STPSOL
SCIP_Real obj
Definition: heur_rec.h:40
includes various files containing graph methods used for Steiner tree problems
int * soledges
Definition: heur_rec.h:41
SCIP_RETCODE SCIPStpHeurRecRun(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_VAR **vars, int *newsolindex, int runs, int nsols, SCIP_Bool restrictheur, SCIP_Bool *solfound)
Definition: heur_rec.c:1026
#define SCIP_Real
Definition: def.h:157
SCIP_RETCODE SCIPStpHeurRecAddToPool(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: heur_rec.c:953
STPSOL * SCIPStpHeurRecSolfromIdx(STPSOLPOOL *pool, const int soindex)
Definition: heur_rec.c:870
SCIP callable library.