Scippy

SCIP

Solving Constraint Integer Programs

type_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-2020 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 type_heur.h
17  * @ingroup TYPEDEFINITIONS
18  * @brief type definitions for primal heuristics
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  *
22  * This file defines the interface for primal heuristics implemented in C.
23  *
24  * - \ref HEUR "Instructions for implementing a primal heuristic"
25  * - \ref PRIMALHEURISTICS "List of available primal heuristics"
26  * - \ref scip::ObjHeur "C++ wrapper class"
27  */
28 
29 /** @defgroup DEFPLUGINS_HEUR Default Primal Heuristics
30  * @ingroup DEFPLUGINS
31  * @brief implementation files (.c files) of the default primal heuristics of SCIP
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef __SCIP_TYPE_HEUR_H__
37 #define __SCIP_TYPE_HEUR_H__
38 
39 #include "scip/def.h"
40 #include "scip/type_scip.h"
41 #include "scip/type_result.h"
42 #include "scip/type_timing.h"
43 #include "scip/type_var.h"
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 /** represents different methods for a dive set to explore the next children */
50 #define SCIP_DIVETYPE_NONE 0x000u /**< no method specified */
51 #define SCIP_DIVETYPE_INTEGRALITY 0x001u /**< use branching on a variable by shrinking the domain in the child nodes */
52 #define SCIP_DIVETYPE_SOS1VARIABLE 0x002u /**< branch on a variable solution value by exploiting special-ordered set conflict structure */
53 
54 typedef unsigned int SCIP_DIVETYPE;
55 
56 /** context for diving statistics */
58 {
59  SCIP_DIVECONTEXT_TOTAL = 0, /**< all contexts combined */
60  SCIP_DIVECONTEXT_SINGLE = 1, /**< single heuristic context */
61  SCIP_DIVECONTEXT_ADAPTIVE = 2 /**< within adaptive diving */
62 };
64 
65 
66 typedef struct SCIP_Heur SCIP_HEUR; /**< primal heuristic */
67 typedef struct SCIP_HeurData SCIP_HEURDATA; /**< locally defined primal heuristic data */
68 typedef struct SCIP_Diveset SCIP_DIVESET; /**< common parameters for all diving heuristics */
69 typedef struct SCIP_VGraph SCIP_VGRAPH; /**< variable graph data structure to determine breadth-first
70  * distances between variables */
71 
72 /** commonly used display characters indicating special classes of primal heuristics */
73 #define SCIP_HEURDISPCHAR_LNS 'L' /**< a 'L'arge Neighborhood or other local search heuristic */
74 #define SCIP_HEURDISPCHAR_DIVING 'd' /**< a 'd'iving heuristic that dives down an auxiliary branch-and-bound path */
75 #define SCIP_HEURDISPCHAR_ITERATIVE 'i' /**< an iterative improvement heuristic such as 1-opt or 2-opt */
76 #define SCIP_HEURDISPCHAR_OBJDIVING 'o' /**< an 'o'bjective diving or feasibility pump heuristic */
77 #define SCIP_HEURDISPCHAR_PROP 'p' /**< a 'p'ropagation heuristic, often applied before branch-and-bound starts */
78 #define SCIP_HEURDISPCHAR_ROUNDING 'r' /**< a 'r'ounding heuristic that iteratively tries to round an LP or relaxation solution */
79 #define SCIP_HEURDISPCHAR_TRIVIAL 't' /**< a 't'rivial or helper heuristic, usually applied before branch-and-bound starts */
80 
81 /** copy method for heuristic plugins (called when SCIP copies plugins)
82  *
83  * input:
84  * - scip : SCIP main data structure
85  * - heur : the primal heuristic itself
86  */
87 #define SCIP_DECL_HEURCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
88 
89 /** destructor of primal heuristic to free user data (called when SCIP is exiting)
90  *
91  * input:
92  * - scip : SCIP main data structure
93  * - heur : the primal heuristic itself
94  */
95 #define SCIP_DECL_HEURFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
96 
97 /** initialization method of primal heuristic (called after problem was transformed)
98  *
99  * input:
100  * - scip : SCIP main data structure
101  * - heur : the primal heuristic itself
102  */
103 #define SCIP_DECL_HEURINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
104 
105 /** deinitialization method of primal heuristic (called before transformed problem is freed)
106  *
107  * input:
108  * - scip : SCIP main data structure
109  * - heur : the primal heuristic itself
110  */
111 #define SCIP_DECL_HEUREXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
112 
113 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
114  *
115  * This method is called when the presolving was finished and the branch and bound process is about to begin.
116  * The primal heuristic may use this call to initialize its branch and bound specific data.
117  *
118  * input:
119  * - scip : SCIP main data structure
120  * - heur : the primal heuristic itself
121  */
122 #define SCIP_DECL_HEURINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
123 
124 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
125  *
126  * This method is called before the branch and bound process is freed.
127  * The primal heuristic should use this call to clean up its branch and bound data.
128  *
129  * input:
130  * - scip : SCIP main data structure
131  * - heur : the primal heuristic itself
132  */
133 #define SCIP_DECL_HEUREXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur)
134 
135 /** execution method of primal heuristic
136  *
137  * Searches for feasible primal solutions. The method is called in the node processing loop.
138  *
139  * input:
140  * - scip : SCIP main data structure
141  * - heur : the primal heuristic itself
142  * - heurtiming : current point in the node solving loop
143  * - nodeinfeasible : was the current node already detected to be infeasible?
144  * - result : pointer to store the result of the heuristic call
145  *
146  * possible return values for *result:
147  * - SCIP_FOUNDSOL : at least one feasible primal solution was found
148  * - SCIP_DIDNOTFIND : the heuristic searched, but did not find a feasible solution
149  * - SCIP_DIDNOTRUN : the heuristic was skipped
150  * - SCIP_DELAYED : the heuristic was skipped, but should be called again as soon as possible, disregarding
151  * its frequency
152  */
153 #define SCIP_DECL_HEUREXEC(x) SCIP_RETCODE x (SCIP* scip, SCIP_HEUR* heur, SCIP_HEURTIMING heurtiming, \
154  SCIP_Bool nodeinfeasible, SCIP_RESULT* result)
155 
156 
157 /* callbacks for diving heuristic specific settings */
158 
159 /** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
160  * score
161  *
162  * input:
163  * - scip : SCIP main data structure
164  * - diveset : diving settings for scoring
165  * - divetype : represents different methods for a dive set to explore the next children
166  * - cand : candidate variable for which the score should be determined
167  * - candsol : solution value of variable in LP relaxation solution
168  * - candsfrac : fractional part of solution value of variable
169  * - score : pointer for diving score value - the best candidate maximizes this score
170  * - roundup : pointer to store whether the preferred rounding direction is upwards
171  *
172  * returns SCIP_OKAY if everything worked, otherwise, a suitable error code
173  */
174 #define SCIP_DECL_DIVESETGETSCORE(x) SCIP_RETCODE x (SCIP* scip, SCIP_DIVESET* diveset, \
175  SCIP_DIVETYPE divetype, SCIP_VAR* cand, SCIP_Real candsol, SCIP_Real candsfrac, SCIP_Real* score, SCIP_Bool* roundup)
176 
177 /**
178  * optional callback to check preconditions for diving, e.g., if an incumbent solution is available
179  *
180  * input:
181  * - scip : SCIP main data structure
182  * - diveset : diving settings for scoring
183  *
184  * output:
185  * - available : TRUE if diveset can run, otherwise FALSE
186  *
187  * returns SCIP_OKAY if everything worked, otherwise, a suitable error code
188  */
189 #define SCIP_DECL_DIVESETAVAILABLE(x) SCIP_RETCODE x (SCIP* scip, SCIP_DIVESET* diveset, SCIP_Bool* available)
190 
191 #ifdef __cplusplus
192 }
193 #endif
194 
195 #endif
timing definitions for SCIP
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:54
type definitions for SCIP&#39;s main datastructure
SCIP_DiveContext
Definition: type_heur.h:57
type definitions for problem variables
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:63
result codes for SCIP callback methods
common defines and data types used in all packages of SCIP