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