Scippy

SCIP

Solving Constraint Integer Programs

pub_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-2018 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 pub_heur.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for primal heuristics
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PUB_HEUR_H__
25 #define __SCIP_PUB_HEUR_H__
26 
27 #include "scip/def.h"
28 #include "scip/type_heur.h"
29 #include "scip/type_misc.h"
30 #include "scip/type_retcode.h"
31 #include "scip/type_scip.h"
32 #include "scip/type_sol.h"
33 #include "scip/type_timing.h"
34 #include "scip/type_var.h"
35 
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39 
40 /**@addtogroup PublicHeuristicMethods
41  *
42  * @{
43  */
44 
45 
46 
47 /** compares two heuristics w. r. to their priority */
48 extern
49 SCIP_DECL_SORTPTRCOMP(SCIPheurComp);
50 
51 /** comparison method for sorting heuristics w.r.t. to their name */
52 extern
53 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName);
54 
55 /** gets user data of primal heuristic */
56 extern
58  SCIP_HEUR* heur /**< primal heuristic */
59  );
60 
61 /** sets user data of primal heuristic; user has to free old data in advance! */
62 extern
63 void SCIPheurSetData(
64  SCIP_HEUR* heur, /**< primal heuristic */
65  SCIP_HEURDATA* heurdata /**< new primal heuristic user data */
66  );
67 
68 /** gets name of primal heuristic */
69 extern
70 const char* SCIPheurGetName(
71  SCIP_HEUR* heur /**< primal heuristic */
72  );
73 
74 /** gets description of primal heuristic */
75 extern
76 const char* SCIPheurGetDesc(
77  SCIP_HEUR* heur /**< primal heuristic */
78  );
79 
80 /** gets display character of primal heuristic */
81 extern
83  SCIP_HEUR* heur /**< primal heuristic */
84  );
85 
86 /** returns the timing mask of the heuristic */
87 extern
89  SCIP_HEUR* heur /**< primal heuristic */
90  );
91 
92 /** sets new timing mask for heuristic */
93 extern
95  SCIP_HEUR* heur, /**< primal heuristic */
96  SCIP_HEURTIMING timingmask /**< new timing mask of heuristic */
97  );
98 
99 /** does the heuristic use a secondary SCIP instance? */
100 extern
102  SCIP_HEUR* heur /**< primal heuristic */
103  );
104 
105 /** gets priority of primal heuristic */
106 extern
108  SCIP_HEUR* heur /**< primal heuristic */
109  );
110 
111 /** gets frequency of primal heuristic */
112 extern
113 int SCIPheurGetFreq(
114  SCIP_HEUR* heur /**< primal heuristic */
115  );
116 
117 /** sets frequency of primal heuristic */
118 extern
119 void SCIPheurSetFreq(
120  SCIP_HEUR* heur, /**< primal heuristic */
121  int freq /**< new frequency of heuristic */
122  );
123 
124 /** gets frequency offset of primal heuristic */
125 extern
127  SCIP_HEUR* heur /**< primal heuristic */
128  );
129 
130 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */
131 extern
133  SCIP_HEUR* heur /**< primal heuristic */
134  );
135 
136 /** gets the number of times, the heuristic was called and tried to find a solution */
137 extern
139  SCIP_HEUR* heur /**< primal heuristic */
140  );
141 
142 /** gets the number of primal feasible solutions found by this heuristic */
143 extern
145  SCIP_HEUR* heur /**< primal heuristic */
146  );
147 
148 /** gets the number of new best primal feasible solutions found by this heuristic */
149 extern
151  SCIP_HEUR* heur /**< primal heuristic */
152  );
153 
154 /** is primal heuristic initialized? */
155 extern
157  SCIP_HEUR* heur /**< primal heuristic */
158  );
159 
160 /** gets time in seconds used in this heuristic for setting up for next stages */
161 extern
163  SCIP_HEUR* heur /**< primal heuristic */
164  );
165 
166 /** gets time in seconds used in this heuristic */
167 extern
169  SCIP_HEUR* heur /**< primal heuristic */
170  );
171 
172 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */
173 extern
175  SCIP_HEUR* heur /**< primal heuristic */
176  );
177 
178 /** returns the number of divesets of this primal heuristic */
179 extern
181  SCIP_HEUR* heur /**< primal heuristic */
182  );
183 
184 /* @} */
185 
186 /** get the heuristic to which this diving setting belongs */
187 extern
189  SCIP_DIVESET* diveset /**< diving settings */
190  );
191 
192 /** get the working solution of this dive set */
193 extern
195  SCIP_DIVESET* diveset /**< diving settings */
196  );
197 
198 /** set the working solution for this dive set */
199 extern
201  SCIP_DIVESET* diveset, /**< diving settings */
202  SCIP_SOL* sol /**< new working solution for this dive set, or NULL */
203  );
204 
205 /**@addtogroup PublicDivesetMethods
206  *
207  * @{
208  */
209 
210 /** get the name of the dive set */
211 extern
212 const char* SCIPdivesetGetName(
213  SCIP_DIVESET* diveset /**< diving settings */
214  );
215 
216 /** get the minimum relative depth of the diving settings */
217 extern
219  SCIP_DIVESET* diveset /**< diving settings */
220  );
221 
222 /** get the maximum relative depth of the diving settings */
223 extern
225  SCIP_DIVESET* diveset /**< diving settings */
226  );
227 
228 /** get the number of successful runs of the diving settings */
229 extern
231  SCIP_DIVESET* diveset /**< diving settings */
232  );
233 
234 /** get the number of calls to this dive set */
235 extern
237  SCIP_DIVESET* diveset /**< diving settings */
238  );
239 
240 /** get the number of calls successfully terminated at a feasible leaf node */
241 extern
243  SCIP_DIVESET* diveset /**< diving settings */
244  );
245 
246 /** get the minimum depth reached by this dive set */
247 extern
249  SCIP_DIVESET* diveset /**< diving settings */
250  );
251 
252 /** get the maximum depth reached by this dive set */
253 extern
255  SCIP_DIVESET* diveset /**< diving settings */
256  );
257 
258 /** get the average depth this dive set reached during execution */
259 extern
261  SCIP_DIVESET* diveset /**< diving settings */
262  );
263 
264 /** get the minimum depth at which this dive set found a solution */
265 extern
267  SCIP_DIVESET* diveset /**< diving settings */
268  );
269 
270 /** get the maximum depth at which this dive set found a solution */
271 extern
273  SCIP_DIVESET* diveset /**< diving settings */
274  );
275 
276 /** get the average depth at which this dive set found a solution */
277 extern
279  SCIP_DIVESET* diveset /**< diving settings */
280  );
281 
282 /** get the total number of LP iterations used by this dive set */
283 extern
285  SCIP_DIVESET* diveset /**< diving settings */
286  );
287 
288 /** get the total number of probing nodes used by this dive set */
289 extern
291  SCIP_DIVESET* diveset /**< diving settings */
292  );
293 
294 /** get the total number of backtracks performed by this dive set */
295 extern
297  SCIP_DIVESET* diveset /**< diving settings */
298  );
299 
300 /** get the total number of conflicts found by this dive set */
301 extern
303  SCIP_DIVESET* diveset /**< diving settings */
304  );
305 
306 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */
307 extern
309  SCIP_DIVESET* diveset /**< diving settings */
310  );
311 
312 /** get the maximum LP iterations quotient of the diving settings */
313 extern
315  SCIP_DIVESET* diveset /**< diving settings */
316  );
317 
318 /** get the maximum LP iterations offset of the diving settings */
319 extern
321  SCIP_DIVESET* diveset /**< diving settings */
322  );
323 
324 /** get the maximum upper bound quotient parameter of the diving settings if no solution is available */
325 extern
327  SCIP_DIVESET* diveset /**< diving settings */
328  );
329 
330 /** get the average quotient parameter of the diving settings if no solution is available */
331 extern
333  SCIP_DIVESET* diveset /**< diving settings */
334  );
335 
336 /** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */
337 extern
339  SCIP_DIVESET* diveset /**< diving settings */
340  );
341 
342 /** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */
343 extern
345  SCIP_DIVESET* diveset /**< diving settings */
346  );
347 
348 /** should backtracking be applied? */
349 extern
351  SCIP_DIVESET* diveset /**< diving settings */
352  );
353 
354 /** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */
355 extern
357  SCIP_DIVESET* diveset /**< diving settings */
358  );
359 
360 /** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/
361 extern
363  SCIP_DIVESET* diveset /**< diving settings */
364  );
365 
366 /** should only LP branching candidates be considered instead of the slower but
367  * more general constraint handler diving variable selection?
368  */
369 extern
371  SCIP_DIVESET* diveset /**< diving settings */
372  );
373 
374 /** returns TRUE if dive set supports diving of the specified type */
375 extern
377  SCIP_DIVESET* diveset, /**< diving settings */
378  SCIP_DIVETYPE divetype /**< bit mask that represents the supported dive types by this dive set */
379  );
380 
381 /** returns the random number generator of this \p diveset for tie-breaking */
382 extern
384  SCIP_DIVESET* diveset /**< diving settings */
385  );
386 
387 /* @} */
388 
389 /**@defgroup PublicVariableGraphMethods Public Variable Graph Methods
390  * @ingroup MiscellaneousMethods
391  *
392  * @brief methods to create a variable graph and perform breadth-first search
393  *
394  * @{
395  */
396 
397 /** Perform breadth-first (BFS) search on the variable constraint graph.
398  *
399  * The result of the algorithm is that the \p distances array contains the correct distances for
400  * every variable from the start variables. The distance of a variable can then be accessed through its
401  * problem index (calling SCIPvarGetProbindex()).
402  * Hence, The method assumes that the length of \p distances is at least
403  * SCIPgetNVars().
404  * Variables that are not connected through constraints to the start variables have a distance of -1.
405  *
406  * Limits can be provided to further restrict the breadth-first search. If a distance limit is given,
407  * the search will be performed until the first variable at this distance is popped from the queue, i.e.,
408  * all variables with a distance < maxdistance have been labeled by the search.
409  * If a variable limit is given, the search stops after it completes the distance level at which
410  * the limit was reached. Hence, more variables may be actually labeled.
411  * The start variables are accounted for those variable limits.
412  *
413  * If no variable variable constraint graph is provided, the method will create one and free it at the end
414  * This is useful for a single use of the variable constraint graph. For several consecutive uses,
415  * it is advised to create a variable constraint graph via SCIPvariableGraphCreate().
416  */
417 extern
419  SCIP* scip, /**< SCIP data structure */
420  SCIP_VGRAPH* vargraph, /**< pointer to the variable graph, or NULL to let the function create a local graph */
421  SCIP_VAR** startvars, /**< array of start variables to calculate distance from */
422  int nstartvars, /**< number of starting variables, at least 1 */
423  int* distances, /**< array to keep distance in vargraph from start variables for every variable */
424  int maxdistance, /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */
425  int maxvars, /**< maximum number of variables to compute distance for */
426  int maxbinintvars /**< maximum number of binary or integer variables to compute distance for */
427  );
428 
429 /** initialization method of variable graph data structure */
430 extern
432  SCIP* scip, /**< SCIP data structure */
433  SCIP_VGRAPH** vargraph, /**< pointer to the variable graph */
434  SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be
435  * ignored by connectivity graph? */
436  SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */
437  int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
438  );
439 
440 /** deinitialization method of variable graph data structure */
441 extern
443  SCIP* scip, /**< SCIP data structure */
444  SCIP_VGRAPH** vargraph /**< pointer to the variable graph */
445  );
446 
447 /* @} */
448 
449 
450 #ifdef __cplusplus
451 }
452 #endif
453 
454 #endif
SCIP_HEURTIMING SCIPheurGetTimingmask(SCIP_HEUR *heur)
Definition: heur.c:1284
int SCIPdivesetGetMinSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:438
int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition: heur.c:1315
SCIP_Real SCIPheurGetSetupTime(SCIP_HEUR *heur)
Definition: heur.c:1432
type definitions for miscellaneous datastructures
timing definitions for SCIP
SCIP_SOL * SCIPdivesetGetWorkSolution(SCIP_DIVESET *diveset)
Definition: heur.c:333
SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset)
Definition: heur.c:488
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:566
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:1830
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:97
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:550
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:527
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1452
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:543
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:372
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1360
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset)
Definition: heur.c:508
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset)
Definition: heur.c:468
SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset)
Definition: heur.c:498
SCIP_Bool SCIPheurUsesSubscip(SCIP_HEUR *heur)
Definition: heur.c:1305
type definitions for return codes for SCIP methods
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:48
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:364
int SCIPdivesetGetNSolutionCalls(SCIP_DIVESET *diveset)
Definition: heur.c:398
SCIP_Real SCIPdivesetGetAvgSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:458
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition: heur.c:1349
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:607
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:519
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1792
int SCIPdivesetGetMaxSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:448
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
int SCIPheurGetMaxdepth(SCIP_HEUR *heur)
Definition: heur.c:1370
type definitions for primal heuristics
type definitions for SCIP&#39;s main datastructure
int SCIPdivesetGetMaxDepth(SCIP_DIVESET *diveset)
Definition: heur.c:418
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:558
SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset)
Definition: heur.c:428
const char * SCIPheurGetDesc(SCIP_HEUR *heur)
Definition: heur.c:1264
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1339
type definitions for problem variables
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:595
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1462
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:325
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype)
Definition: heur.c:617
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition: heur.c:1491
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:535
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:584
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:343
type definitions for storing primal CIP solutions
SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
Definition: heur.c:41
#define SCIP_Real
Definition: def.h:150
char SCIPheurGetDispchar(SCIP_HEUR *heur)
Definition: heur.c:1274
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1294
#define SCIP_Longint
Definition: def.h:135
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1390
SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset)
Definition: heur.c:380
SCIP_Bool SCIPheurIsInitialized(SCIP_HEUR *heur)
Definition: heur.c:1410
common defines and data types used in all packages of SCIP
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1442
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset)
Definition: heur.c:388
SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset)
Definition: heur.c:478
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:574
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:354
int SCIPdivesetGetMinDepth(SCIP_DIVESET *diveset)
Definition: heur.c:408