Scippy

SCIP

Solving Constraint Integer Programs

struct_heur.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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file struct_heur.h
26  * @ingroup INTERNALAPI
27  * @brief datastructures for primal heuristics
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_STRUCT_HEUR_H__
34 #define __SCIP_STRUCT_HEUR_H__
35 
36 
37 #include "scip/def.h"
38 #include "scip/type_clock.h"
39 #include "scip/type_heur.h"
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44 
45 
47 {
48  SCIP_Longint nlpiterations; /**< LP iterations used in this dive set */
49  SCIP_Longint nlps; /**< the number of LPs solved by this dive set */
50  SCIP_Longint totaldepth; /**< the total depth used in this dive set */
51  SCIP_Longint totalsoldepth; /**< the sum of depths at which this dive set found solutions */
52  SCIP_Longint totalnnodes; /**< the total number of probing nodes explored by this dive set */
53  SCIP_Longint totalnbacktracks; /**< the total number of backtracks during the execution of this dive set */
54  SCIP_Longint nsolsfound; /**< the total number of solutions found */
55  SCIP_Longint nbestsolsfound; /**< the total number of best solutions found */
56  SCIP_Longint nconflictsfound; /**< the total number of added conflicts during the execution of this dive set */
57  int mindepth; /**< the minimum depth reached by all executions of the dive set */
58  int maxdepth; /**< the maximum depth reached by an execution of the dive set */
59  int minsoldepth; /**< the minimum depth at which this dive set found a solution */
60  int maxsoldepth; /**< the maximum depth at which this dive set found a solution */
61  int ncalls; /**< the total number of calls of this dive set */
62  int nsolcalls; /**< number of calls with a leaf solution */
63 };
65 
66 /** common settings for diving heuristics */
68 {
69  SCIP_HEUR* heur; /**< the heuristic to which this dive set belongs */
70  char* name; /**< name of dive controller, in case that a heuristic has several */
71  SCIP_SOL* sol; /**< working solution of this dive set */
72  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
73  SCIP_DIVESETSTATS* divesetstats[4]; /**< statistics for individual contexts */
74  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
75  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
76  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
77  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
78  * where diving is performed (0.0: no limit) */
79  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
80  * where diving is performed (0.0: no limit) */
81  SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
82  SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
83  SCIP_Real lpresolvedomchgquot;/**< percentage of immediate domain changes during probing to trigger LP resolve */
84  int lpsolvefreq; /**< LP solve frequency for diving heuristics */
85  int maxlpiterofs; /**< additional number of allowed LP iterations */
86  unsigned int initialseed; /**< initial seed for the random number generator */
87  SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
88  SCIP_Bool onlylpbranchcands; /**< should only LP branching candidates be considered instead of the slower but
89  * more general constraint handler diving variable selection? */
90  SCIP_Bool ispublic; /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
91  SCIP_DIVETYPE divetypemask; /**< bit mask that represents the supported dive types by this dive set */
92  SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)); /**< method for candidate score and rounding direction */
93  SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)); /**< callback to check availability of dive set at the current stage, or NULL if always available */
94 };
95 
96 /** primal heuristics data */
97 struct SCIP_Heur
98 {
99  SCIP_Longint ncalls; /**< number of times, this heuristic was called */
100  SCIP_Longint nsolsfound; /**< number of feasible primal solutions found so far by this heuristic */
101  SCIP_Longint nbestsolsfound; /**< number of new best primal CIP solutions found so far by this heuristic */
102  char* name; /**< name of primal heuristic */
103  char* desc; /**< description of primal heuristic */
104  SCIP_DECL_HEURCOPY ((*heurcopy)); /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
105  SCIP_DECL_HEURFREE ((*heurfree)); /**< destructor of primal heuristic */
106  SCIP_DECL_HEURINIT ((*heurinit)); /**< initialize primal heuristic */
107  SCIP_DECL_HEUREXIT ((*heurexit)); /**< deinitialize primal heuristic */
108  SCIP_DECL_HEURINITSOL ((*heurinitsol)); /**< solving process initialization method of primal heuristic */
109  SCIP_DECL_HEUREXITSOL ((*heurexitsol)); /**< solving process deinitialization method of primal heuristic */
110  SCIP_DECL_HEUREXEC ((*heurexec)); /**< execution method of primal heuristic */
111  SCIP_HEURDATA* heurdata; /**< primal heuristics local data */
112  SCIP_DIVESET** divesets; /**< array of diving controllers of this heuristic */
113  SCIP_CLOCK* setuptime; /**< time spend for setting up this heuristic for the next stages */
114  SCIP_CLOCK* heurclock; /**< heuristic execution time */
115  int priority; /**< priority of the primal heuristic */
116  int freq; /**< frequency for calling primal heuristic */
117  int freqofs; /**< frequency offset for calling primal heuristic */
118  int maxdepth; /**< maximal depth level to call heuristic at (-1: no limit) */
119  int delaypos; /**< position in the delayed heuristics queue, or -1 if not delayed */
120  int ndivesets; /**< number of diving controllers of this heuristic */
121  SCIP_HEURTIMING timingmask; /**< positions in the node solving loop where heuristic should be executed */
122  SCIP_Bool usessubscip; /**< does the heuristic use a secondary SCIP instance? */
123  SCIP_Bool initialized; /**< is primal heuristic initialized? */
124  char dispchar; /**< display character of primal heuristic */
125 };
126 
127 /** variable graph data structure to determine breadth-first distances between variables
128  *
129  * the variable graph internally stores a mapping from the variables to the constraints in which they appear.
130  *
131  * @see PublicVariableGraphMethods for available methods
132  */
134 {
135  SCIP_CONS*** varconss; /**< constraints of each variable */
136  SCIP_HASHTABLE* visitedconss; /**< hash table that keeps a record of visited constraints during breadth-first search */
137  int* nvarconss; /**< number of constraints for each variable */
138  int* varconssize; /**< size array for every varconss entry */
139 };
140 
141 #ifdef __cplusplus
142 }
143 #endif
144 
145 #endif
SCIP_Bool onlylpbranchcands
Definition: struct_heur.h:88
int * nvarconss
Definition: struct_heur.h:137
SCIP_Longint nbestsolsfound
Definition: struct_heur.h:55
#define SCIP_DECL_HEURINITSOL(x)
Definition: type_heur.h:132
SCIP_HEUR * heur
Definition: struct_heur.h:69
SCIP_DIVESET ** divesets
Definition: struct_heur.h:112
int ndivesets
Definition: struct_heur.h:120
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:106
int delaypos
Definition: struct_heur.h:119
SCIP_Real maxreldepth
Definition: struct_heur.h:75
SCIP_Bool backtrack
Definition: struct_heur.h:87
SCIP_Real maxlpiterquot
Definition: struct_heur.h:76
SCIP_Longint nsolsfound
Definition: struct_heur.h:100
SCIP_CLOCK * heurclock
Definition: struct_heur.h:114
int * varconssize
Definition: struct_heur.h:138
char * name
Definition: struct_heur.h:70
#define SCIP_DECL_HEURCOPY(x)
Definition: type_heur.h:97
#define SCIP_DECL_HEUREXEC(x)
Definition: type_heur.h:163
SCIP_CLOCK * setuptime
Definition: struct_heur.h:113
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
char dispchar
Definition: struct_heur.h:124
SCIP_Longint nconflictsfound
Definition: struct_heur.h:56
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:63
SCIP_Bool usessubscip
Definition: struct_heur.h:122
#define SCIP_DECL_DIVESETGETSCORE(x)
Definition: type_heur.h:184
SCIP_Longint totalnnodes
Definition: struct_heur.h:52
SCIP_Real maxdiveavgquotnosol
Definition: struct_heur.h:82
SCIP_HEURTIMING timingmask
Definition: struct_heur.h:121
char * name
Definition: struct_heur.h:102
type definitions for primal heuristics
SCIP_Longint nlpiterations
Definition: struct_heur.h:48
SCIP_SOL * sol
Definition: struct_heur.h:71
SCIP_Real lpresolvedomchgquot
Definition: struct_heur.h:83
SCIP_RANDNUMGEN * randnumgen
Definition: struct_heur.h:72
SCIP_Real maxdiveubquot
Definition: struct_heur.h:77
SCIP_Bool initialized
Definition: struct_heur.h:123
SCIP_Bool ispublic
Definition: struct_heur.h:90
#define SCIP_Bool
Definition: def.h:91
SCIP_Longint nsolsfound
Definition: struct_heur.h:54
char * desc
Definition: struct_heur.h:103
SCIP_Longint totalsoldepth
Definition: struct_heur.h:51
int priority
Definition: struct_heur.h:115
SCIP_DIVETYPE divetypemask
Definition: struct_heur.h:91
SCIP_HEURDATA * heurdata
Definition: struct_heur.h:111
unsigned int initialseed
Definition: struct_heur.h:86
type definitions for clocks and timing issues
#define SCIP_DECL_DIVESETAVAILABLE(x)
Definition: type_heur.h:199
SCIP_CONS *** varconss
Definition: struct_heur.h:135
SCIP_Real maxdiveavgquot
Definition: struct_heur.h:79
SCIP_HASHTABLE * visitedconss
Definition: struct_heur.h:136
SCIP_Longint ncalls
Definition: struct_heur.h:99
#define SCIP_DECL_HEUREXIT(x)
Definition: type_heur.h:121
#define SCIP_DECL_HEURINIT(x)
Definition: type_heur.h:113
SCIP_Longint nbestsolsfound
Definition: struct_heur.h:101
#define SCIP_Real
Definition: def.h:173
SCIP_Longint nlps
Definition: struct_heur.h:49
#define SCIP_DECL_HEURFREE(x)
Definition: type_heur.h:105
SCIP_Longint totaldepth
Definition: struct_heur.h:50
#define SCIP_Longint
Definition: def.h:158
SCIP_Real minreldepth
Definition: struct_heur.h:74
int maxlpiterofs
Definition: struct_heur.h:85
common defines and data types used in all packages of SCIP
#define SCIP_DECL_HEUREXITSOL(x)
Definition: type_heur.h:143
SCIP_Longint totalnbacktracks
Definition: struct_heur.h:53
SCIP_Real maxdiveubquotnosol
Definition: struct_heur.h:81
int maxdepth
Definition: struct_heur.h:118