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-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 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 */
49 SCIP_DECL_SORTPTRCOMP(SCIPheurComp);
50 
51 /** comparison method for sorting heuristics w.r.t. to their name */
53 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName);
54 
55 /** gets user data of primal heuristic */
58  SCIP_HEUR* heur /**< primal heuristic */
59  );
60 
61 /** sets user data of primal heuristic; user has to free old data in advance! */
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 */
70 const char* SCIPheurGetName(
71  SCIP_HEUR* heur /**< primal heuristic */
72  );
73 
74 /** gets description of primal heuristic */
76 const char* SCIPheurGetDesc(
77  SCIP_HEUR* heur /**< primal heuristic */
78  );
79 
80 /** gets display character of primal heuristic */
83  SCIP_HEUR* heur /**< primal heuristic */
84  );
85 
86 /** returns the timing mask of the heuristic */
89  SCIP_HEUR* heur /**< primal heuristic */
90  );
91 
92 /** sets new timing mask for heuristic */
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? */
102  SCIP_HEUR* heur /**< primal heuristic */
103  );
104 
105 /** gets priority of primal heuristic */
108  SCIP_HEUR* heur /**< primal heuristic */
109  );
110 
111 /** gets frequency of primal heuristic */
113 int SCIPheurGetFreq(
114  SCIP_HEUR* heur /**< primal heuristic */
115  );
116 
117 /** sets frequency of primal heuristic */
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 */
127  SCIP_HEUR* heur /**< primal heuristic */
128  );
129 
130 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */
133  SCIP_HEUR* heur /**< primal heuristic */
134  );
135 
136 /** gets the number of times, the heuristic was called and tried to find a solution */
139  SCIP_HEUR* heur /**< primal heuristic */
140  );
141 
142 /** gets the number of primal feasible solutions found by this heuristic */
145  SCIP_HEUR* heur /**< primal heuristic */
146  );
147 
148 /** gets the number of new best primal feasible solutions found by this heuristic */
151  SCIP_HEUR* heur /**< primal heuristic */
152  );
153 
154 /** is primal heuristic initialized? */
157  SCIP_HEUR* heur /**< primal heuristic */
158  );
159 
160 /** gets time in seconds used in this heuristic for setting up for next stages */
163  SCIP_HEUR* heur /**< primal heuristic */
164  );
165 
166 /** gets time in seconds used in this heuristic */
169  SCIP_HEUR* heur /**< primal heuristic */
170  );
171 
172 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */
175  SCIP_HEUR* heur /**< primal heuristic */
176  );
177 
178 /** returns the number of divesets of this primal heuristic */
181  SCIP_HEUR* heur /**< primal heuristic */
182  );
183 
184 /* @} */
185 
186 /** get the heuristic to which this diving setting belongs */
189  SCIP_DIVESET* diveset /**< diving settings */
190  );
191 
192 /** get the working solution of this dive set */
195  SCIP_DIVESET* diveset /**< diving settings */
196  );
197 
198 /** set the working solution for this dive set */
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 */
212 const char* SCIPdivesetGetName(
213  SCIP_DIVESET* diveset /**< diving settings */
214  );
215 
216 /** get the minimum relative depth of the diving settings */
219  SCIP_DIVESET* diveset /**< diving settings */
220  );
221 
222 /** get the maximum relative depth of the diving settings */
225  SCIP_DIVESET* diveset /**< diving settings */
226  );
227 
228 /** get the number of successful runs of the diving settings */
231  SCIP_DIVESET* diveset /**< diving settings */
232  );
233 
234 /** get the number of calls to this dive set */
237  SCIP_DIVESET* diveset /**< diving settings */
238  );
239 
240 /** get the number of calls successfully terminated at a feasible leaf node */
243  SCIP_DIVESET* diveset /**< diving settings */
244  );
245 
246 /** get the minimum depth reached by this dive set */
249  SCIP_DIVESET* diveset /**< diving settings */
250  );
251 
252 /** get the maximum depth reached by this dive set */
255  SCIP_DIVESET* diveset /**< diving settings */
256  );
257 
258 /** get the average depth this dive set reached during execution */
261  SCIP_DIVESET* diveset /**< diving settings */
262  );
263 
264 /** get the minimum depth at which this dive set found a solution */
267  SCIP_DIVESET* diveset /**< diving settings */
268  );
269 
270 /** get the maximum depth at which this dive set found a solution */
273  SCIP_DIVESET* diveset /**< diving settings */
274  );
275 
276 /** get the average depth at which this dive set found a solution */
279  SCIP_DIVESET* diveset /**< diving settings */
280  );
281 
282 /** get the total number of LP iterations used by this dive set */
285  SCIP_DIVESET* diveset /**< diving settings */
286  );
287 
288 /** get the total number of probing nodes used by this dive set */
291  SCIP_DIVESET* diveset /**< diving settings */
292  );
293 
294 /** get the total number of backtracks performed by this dive set */
297  SCIP_DIVESET* diveset /**< diving settings */
298  );
299 
300 /** get the total number of conflicts found by this dive set */
303  SCIP_DIVESET* diveset /**< diving settings */
304  );
305 
306 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */
309  SCIP_DIVESET* diveset /**< diving settings */
310  );
311 
312 /** get the maximum LP iterations quotient of the diving settings */
315  SCIP_DIVESET* diveset /**< diving settings */
316  );
317 
318 /** get the maximum LP iterations offset of the diving settings */
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 */
327  SCIP_DIVESET* diveset /**< diving settings */
328  );
329 
330 /** get the average quotient parameter of the diving settings if no solution is available */
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 */
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 */
345  SCIP_DIVESET* diveset /**< diving settings */
346  );
347 
348 /** should backtracking be applied? */
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) */
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)*/
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  */
371  SCIP_DIVESET* diveset /**< diving settings */
372  );
373 
374 /** returns TRUE if dive set supports diving of the specified type */
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 */
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  */
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 */
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 */
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_EXPORT SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1380
SCIP_EXPORT void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition: heur.c:1349
SCIP_EXPORT int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition: heur.c:527
SCIP_EXPORT SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1390
SCIP_EXPORT const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
SCIP_EXPORT int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1339
type definitions for miscellaneous datastructures
timing definitions for SCIP
SCIP_EXPORT SCIP_Bool SCIPdivesetSupportsType(SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype)
Definition: heur.c:617
SCIP_EXPORT SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_EXPORT SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:595
SCIP_EXPORT SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:364
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:97
SCIP_EXPORT SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:584
SCIP_EXPORT SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset)
Definition: heur.c:468
#define SCIP_EXPORT
Definition: def.h:98
SCIP_EXPORT SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1792
SCIP_EXPORT 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_EXPORT int SCIPdivesetGetMaxSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:448
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_EXPORT SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition: heur.c:566
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_EXPORT SCIP_Longint SCIPdivesetGetSolSuccess(SCIP_DIVESET *diveset)
Definition: heur.c:380
type definitions for return codes for SCIP methods
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:48
SCIP_EXPORT SCIP_HEURTIMING SCIPheurGetTimingmask(SCIP_HEUR *heur)
Definition: heur.c:1284
SCIP_EXPORT SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1400
SCIP_EXPORT SCIP_Real SCIPdivesetGetAvgSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:458
SCIP_EXPORT int SCIPdivesetGetMinSolutionDepth(SCIP_DIVESET *diveset)
Definition: heur.c:438
SCIP_EXPORT SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition: heur.c:519
SCIP_EXPORT int SCIPheurGetPriority(SCIP_HEUR *heur)
Definition: heur.c:1315
SCIP_EXPORT int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1462
type definitions for primal heuristics
SCIP_EXPORT int SCIPdivesetGetNSolutionCalls(SCIP_DIVESET *diveset)
Definition: heur.c:398
SCIP_EXPORT SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:325
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:535
SCIP_EXPORT SCIP_Longint SCIPdivesetGetNProbingNodes(SCIP_DIVESET *diveset)
Definition: heur.c:478
SCIP_EXPORT void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition: heur.c:343
SCIP_EXPORT void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
SCIP_EXPORT const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition: heur.c:354
SCIP_EXPORT SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset)
Definition: heur.c:508
SCIP_EXPORT void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1294
SCIP_EXPORT SCIP_Real SCIPdivesetGetAvgDepth(SCIP_DIVESET *diveset)
Definition: heur.c:428
type definitions for problem variables
SCIP_EXPORT SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition: heur.c:543
SCIP_EXPORT SCIP_Bool SCIPheurIsInitialized(SCIP_HEUR *heur)
Definition: heur.c:1410
SCIP_EXPORT void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:1830
SCIP_EXPORT SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition: heur.c:372
SCIP_EXPORT char SCIPheurGetDispchar(SCIP_HEUR *heur)
Definition: heur.c:1274
SCIP_EXPORT SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1452
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_SOL * SCIPdivesetGetWorkSolution(SCIP_DIVESET *diveset)
Definition: heur.c:333
SCIP_EXPORT int SCIPheurGetMaxdepth(SCIP_HEUR *heur)
Definition: heur.c:1370
SCIP_EXPORT SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition: heur.c:607
SCIP_EXPORT SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition: heur.c:550
type definitions for storing primal CIP solutions
SCIP_EXPORT const char * SCIPheurGetDesc(SCIP_HEUR *heur)
Definition: heur.c:1264
SCIP_EXPORT int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset)
Definition: heur.c:388
SCIP_EXPORT SCIP_Longint SCIPdivesetGetNConflicts(SCIP_DIVESET *diveset)
Definition: heur.c:498
SCIP_EXPORT SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1442
SCIP_EXPORT int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1360
SCIP_EXPORT SCIP_Bool SCIPheurUsesSubscip(SCIP_HEUR *heur)
Definition: heur.c:1305
SCIP_EXPORT int SCIPdivesetGetMinDepth(SCIP_DIVESET *diveset)
Definition: heur.c:408
#define SCIP_Real
Definition: def.h:164
SCIP_EXPORT SCIP_Real SCIPheurGetSetupTime(SCIP_HEUR *heur)
Definition: heur.c:1432
SCIP_EXPORT int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition: heur.c:574
#define SCIP_Longint
Definition: def.h:149
SCIP_EXPORT int SCIPdivesetGetMaxDepth(SCIP_DIVESET *diveset)
Definition: heur.c:418
common defines and data types used in all packages of SCIP
SCIP_EXPORT SCIP_Longint SCIPdivesetGetNBacktracks(SCIP_DIVESET *diveset)
Definition: heur.c:488
SCIP_EXPORT SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
Definition: heur.c:41
SCIP_EXPORT SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition: heur.c:558