SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
55extern "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
63typedef 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
75typedef struct SCIP_Heur SCIP_HEUR; /**< primal heuristic */
76typedef struct SCIP_HeurData SCIP_HEURDATA; /**< locally defined primal heuristic data */
77typedef struct SCIP_Diveset SCIP_DIVESET; /**< common parameters for all diving heuristics */
78typedef 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
common defines and data types used in all packages of SCIP
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition type_heur.h:72
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
unsigned int SCIP_DIVETYPE
Definition type_heur.h:63
SCIP_DiveContext
Definition type_heur.h:67
@ SCIP_DIVECONTEXT_SINGLE
Definition type_heur.h:69
@ SCIP_DIVECONTEXT_TOTAL
Definition type_heur.h:68
@ SCIP_DIVECONTEXT_ADAPTIVE
Definition type_heur.h:70
result codes for SCIP callback methods
type definitions for SCIP's main datastructure
timing definitions for SCIP
type definitions for problem variables