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-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_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 */
57  SCIP* scip, /**< SCIP data structure */
58  STPSOLPOOL* pool, /**< solution pool or NULL */
59  SCIP_HEUR* heur, /**< heuristic or NULL */
60  SCIP_HEURDATA* heurdata, /**< heuristic data or NULL */
61  const GRAPH* graph, /**< graph data */
62  SCIP_VAR** vars, /**< variables or NULL */
63  int* newsolindex, /**< index of new solution */
64  int runs, /**< number of runs */
65  int nsols, /**< number of solutions */
66  SCIP_Bool restrictheur, /**< use restricted version of heur? */
67  SCIP_Bool* solfound /**< new solution found? */
68 );
69 
70 
71 /** get solution from index */
73  STPSOLPOOL* pool, /**< the pool */
74  const int soindex /**< the index */
75  );
76 
77 /** initializes STPSOL pool */
79  SCIP* scip, /**< SCIP data structure */
80  STPSOLPOOL** pool, /**< the pool */
81  const int nedges, /**< number of edges of solutions to be stored in the pool */
82  const int maxsize /**< capacity of pool */
83  );
84 
85 /** tries to add STPSOL to pool */
87  SCIP* scip, /**< SCIP data structure */
88  const SCIP_Real obj, /**< objective of solution to be added */
89  const int* soledges, /**< edge array of solution to be added */
90  STPSOLPOOL* pool, /**< the pool */
91  SCIP_Bool* success /**< has solution been added? */
92  );
93 
94 /** frees STPSOL pool */
96  SCIP* scip, /**< SCIP data structure */
97  STPSOLPOOL** pool /**< the pool */
98  );
99 
100 /** creates the rec primal heuristic and includes it in SCIP */
102  SCIP* scip /**< SCIP data structure */
103  );
104 
105 
106 /** heuristic to exclude vertices or edges from a given solution (and inserting other edges) to improve objective */
108  SCIP* scip, /**< SCIP data structure */
109  const GRAPH* graph, /**< graph structure */
110  const int* result, /**< edge solution array (UNKNOWN/CONNECT) */
111  int* newresult, /**< new edge solution array (UNKNOWN/CONNECT) */
112  int* dnodemap, /**< node array for internal use */
113  STP_Bool* stvertex, /**< node array for internally marking solution vertices */
114  SCIP_Bool* success /**< solution improved? */
115  );
116 
117 #ifdef __cplusplus
118 }
119 #endif
120 
121 #endif
void SCIPStpHeurRecFreePool(SCIP *scip, STPSOLPOOL **pool)
Definition: heur_rec.c:924
SCIP_RETCODE SCIPStpIncludeHeurRec(SCIP *scip)
Definition: heur_rec.c:2103
Definition: grph.h:57
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
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:893
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:1594
#define SCIP_Bool
Definition: def.h:70
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:1025
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPStpHeurRecAddToPool(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: heur_rec.c:952
STPSOL * SCIPStpHeurRecSolfromIdx(STPSOLPOOL *pool, const int soindex)
Definition: heur_rec.c:869
SCIP callable library.