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 scip_heur.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for primal heuristic plugins and divesets 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Leona Gottwald 32 * @author Stefan Heinz 33 * @author Gregor Hendel 34 * @author Thorsten Koch 35 * @author Alexander Martin 36 * @author Marc Pfetsch 37 * @author Michael Winkler 38 * @author Kati Wolter 39 * 40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "scip/debug.h" 46 #include "scip/heur.h" 47 #include "scip/pub_message.h" 48 #include "scip/scip_heur.h" 49 #include "scip/set.h" 50 #include "scip/struct_mem.h" 51 #include "scip/struct_scip.h" 52 #include "scip/struct_set.h" 53 54 /** creates a primal heuristic and includes it in SCIP. 55 * 56 * @note method has all heuristic callbacks as arguments and is thus changed every time a new 57 * callback is added in future releases; consider using SCIPincludeHeurBasic() and setter functions 58 * if you seek for a method which is less likely to change in future releases 59 * 60 * @return \ref SCIP_OKAY is returned if everything worked. otherwise a suitable error code is passed. see \ref 61 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 62 * 63 * @pre This method can be called if @p scip is in one of the following stages: 64 * - \ref SCIP_STAGE_INIT 65 * - \ref SCIP_STAGE_PROBLEM 66 */ 67 SCIP_RETCODE SCIPincludeHeur( 68 SCIP* scip, /**< SCIP data structure */ 69 const char* name, /**< name of primal heuristic */ 70 const char* desc, /**< description of primal heuristic */ 71 char dispchar, /**< display character of primal heuristic */ 72 int priority, /**< priority of the primal heuristic */ 73 int freq, /**< frequency for calling primal heuristic */ 74 int freqofs, /**< frequency offset for calling primal heuristic */ 75 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */ 76 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed; 77 * see definition of SCIP_HEURTIMING for possible values */ 78 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */ 79 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 80 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */ 81 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */ 82 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */ 83 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */ 84 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */ 85 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */ 86 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 87 ) 88 { 89 SCIP_HEUR* heur; 90 91 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeHeur", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 92 93 /* check whether heuristic is already present */ 94 if( SCIPfindHeur(scip, name) != NULL ) 95 { 96 SCIPerrorMessage("heuristic <%s> already included.\n", name); 97 return SCIP_INVALIDDATA; 98 } 99 100 SCIP_CALL( SCIPheurCreate(&heur, scip->set, scip->messagehdlr, scip->mem->setmem, 101 name, desc, dispchar, priority, freq, freqofs, maxdepth, timingmask, usessubscip, 102 heurcopy, heurfree, heurinit, heurexit, heurinitsol, heurexitsol, heurexec, heurdata) ); 103 104 SCIP_CALL( SCIPsetIncludeHeur(scip->set, heur) ); 105 106 return SCIP_OKAY; 107 } 108 109 /** creates a primal heuristic and includes it in SCIP with its most fundamental callbacks. 110 * All non-fundamental (or optional) callbacks 111 * as, e. g., init and exit callbacks, will be set to NULL. 112 * Optional callbacks can be set via specific setter functions, see SCIPsetHeurCopy(), SCIPsetHeurFree(), 113 * SCIPsetHeurInit(), SCIPsetHeurExit(), SCIPsetHeurInitsol(), and SCIPsetHeurExitsol() 114 * 115 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeHeur() instead 116 */ 117 SCIP_RETCODE SCIPincludeHeurBasic( 118 SCIP* scip, /**< SCIP data structure */ 119 SCIP_HEUR** heur, /**< pointer to primal heuristic */ 120 const char* name, /**< name of primal heuristic */ 121 const char* desc, /**< description of primal heuristic */ 122 char dispchar, /**< display character of primal heuristic */ 123 int priority, /**< priority of the primal heuristic */ 124 int freq, /**< frequency for calling primal heuristic */ 125 int freqofs, /**< frequency offset for calling primal heuristic */ 126 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */ 127 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed; 128 * see definition of SCIP_HEURTIMING for possible values */ 129 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */ 130 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */ 131 SCIP_HEURDATA* heurdata /**< primal heuristic data */ 132 ) 133 { 134 SCIP_HEUR* heurptr; 135 136 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeHeurBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 137 138 /* check whether heuristic is already present */ 139 if( SCIPfindHeur(scip, name) != NULL ) 140 { 141 SCIPerrorMessage("heuristic <%s> already included.\n", name); 142 return SCIP_INVALIDDATA; 143 } 144 145 SCIP_CALL( SCIPheurCreate(&heurptr, scip->set, scip->messagehdlr, scip->mem->setmem, 146 name, desc, dispchar, priority, freq, freqofs, maxdepth, timingmask, usessubscip, 147 NULL, NULL, NULL, NULL, NULL, NULL, heurexec, heurdata) ); 148 149 assert(heurptr != NULL); 150 151 SCIP_CALL( SCIPsetIncludeHeur(scip->set, heurptr) ); 152 153 if( heur != NULL ) 154 *heur = heurptr; 155 156 return SCIP_OKAY; 157 } 158 159 /* new callback/method setter methods */ 160 161 /** sets copy method of primal heuristic */ 162 SCIP_RETCODE SCIPsetHeurCopy( 163 SCIP* scip, /**< SCIP data structure */ 164 SCIP_HEUR* heur, /**< primal heuristic */ 165 SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */ 166 ) 167 { 168 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 169 170 assert(heur != NULL); 171 172 SCIPheurSetCopy(heur, heurcopy); 173 174 return SCIP_OKAY; 175 } 176 177 /** sets destructor method of primal heuristic */ 178 SCIP_RETCODE SCIPsetHeurFree( 179 SCIP* scip, /**< SCIP data structure */ 180 SCIP_HEUR* heur, /**< primal heuristic */ 181 SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */ 182 ) 183 { 184 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 185 186 assert(heur != NULL); 187 188 SCIPheurSetFree(heur, heurfree); 189 190 return SCIP_OKAY; 191 } 192 193 /** sets initialization method of primal heuristic */ 194 SCIP_RETCODE SCIPsetHeurInit( 195 SCIP* scip, /**< SCIP data structure */ 196 SCIP_HEUR* heur, /**< primal heuristic */ 197 SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */ 198 ) 199 { 200 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 201 202 assert(heur != NULL); 203 204 SCIPheurSetInit(heur, heurinit); 205 206 return SCIP_OKAY; 207 } 208 209 /** sets deinitialization method of primal heuristic */ 210 SCIP_RETCODE SCIPsetHeurExit( 211 SCIP* scip, /**< SCIP data structure */ 212 SCIP_HEUR* heur, /**< primal heuristic */ 213 SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */ 214 ) 215 { 216 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 217 218 assert(heur != NULL); 219 220 SCIPheurSetExit(heur, heurexit); 221 222 return SCIP_OKAY; 223 } 224 225 /** sets solving process initialization method of primal heuristic */ 226 SCIP_RETCODE SCIPsetHeurInitsol( 227 SCIP* scip, /**< SCIP data structure */ 228 SCIP_HEUR* heur, /**< primal heuristic */ 229 SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization method of primal heuristic */ 230 ) 231 { 232 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 233 234 assert(heur != NULL); 235 236 SCIPheurSetInitsol(heur, heurinitsol); 237 238 return SCIP_OKAY; 239 } 240 241 /** sets solving process deinitialization method of primal heuristic */ 242 SCIP_RETCODE SCIPsetHeurExitsol( 243 SCIP* scip, /**< SCIP data structure */ 244 SCIP_HEUR* heur, /**< primal heuristic */ 245 SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization method of primal heuristic */ 246 ) 247 { 248 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 249 250 assert(heur != NULL); 251 252 SCIPheurSetExitsol(heur, heurexitsol); 253 254 return SCIP_OKAY; 255 } 256 257 /** returns the primal heuristic of the given name, or NULL if not existing */ 258 SCIP_HEUR* SCIPfindHeur( 259 SCIP* scip, /**< SCIP data structure */ 260 const char* name /**< name of primal heuristic */ 261 ) 262 { 263 assert(scip != NULL); 264 assert(scip->set != NULL); 265 assert(name != NULL); 266 267 return SCIPsetFindHeur(scip->set, name); 268 } 269 270 /** returns the array of currently available primal heuristics */ 271 SCIP_HEUR** SCIPgetHeurs( 272 SCIP* scip /**< SCIP data structure */ 273 ) 274 { 275 assert(scip != NULL); 276 assert(scip->set != NULL); 277 278 return scip->set->heurs; 279 } 280 281 /** returns the number of currently available primal heuristics */ 282 int SCIPgetNHeurs( 283 SCIP* scip /**< SCIP data structure */ 284 ) 285 { 286 assert(scip != NULL); 287 assert(scip->set != NULL); 288 289 return scip->set->nheurs; 290 } 291 292 /** sets the priority of a primal heuristic */ 293 SCIP_RETCODE SCIPsetHeurPriority( 294 SCIP* scip, /**< SCIP data structure */ 295 SCIP_HEUR* heur, /**< primal heuristic */ 296 int priority /**< new priority of the primal heuristic */ 297 ) 298 { 299 assert(scip != NULL); 300 assert(scip->set != NULL); 301 302 SCIPheurSetPriority(heur, scip->set, priority); 303 304 return SCIP_OKAY; 305 } 306 307 /** create a diving set associated with a primal heuristic. The primal heuristic needs to be included 308 * before this method can be called. The diveset is installed in the array of divesets of the heuristic 309 * and can be retrieved later by accessing SCIPheurGetDivesets() 310 * 311 * @return \ref SCIP_OKAY is returned if everything worked. otherwise a suitable error code is passed. see \ref 312 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 313 * 314 * @pre This method can be called if @p scip is in one of the following stages: 315 * - \ref SCIP_STAGE_INIT 316 * - \ref SCIP_STAGE_PROBLEM 317 */ 318 SCIP_RETCODE SCIPcreateDiveset( 319 SCIP* scip, /**< SCIP data structure */ 320 SCIP_DIVESET** diveset, /**< pointer to created diving heuristic settings, or NULL if not needed */ 321 SCIP_HEUR* heur, /**< primal heuristic to which the diveset belongs */ 322 const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */ 323 SCIP_Real minreldepth, /**< minimal relative depth to start diving */ 324 SCIP_Real maxreldepth, /**< maximal relative depth to start diving */ 325 SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */ 326 SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 327 * where diving is performed (0.0: no limit) */ 328 SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 329 * where diving is performed (0.0: no limit) */ 330 SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 331 SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 332 SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */ 333 int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/ 334 int maxlpiterofs, /**< additional number of allowed LP iterations */ 335 unsigned int initialseed, /**< initial seed for random number generation */ 336 SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */ 337 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but 338 * more general constraint handler diving variable selection? */ 339 SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 340 SCIP_Bool specificsos1score, /**< should SOS1 variables be scored by the diving heuristics specific score function; 341 * otherwise use the score function of the SOS1 constraint handler */ 342 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */ 343 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */ 344 ) 345 { 346 SCIP_DIVESET* divesetptr = NULL; 347 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateDiveset", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 348 349 /* create the diveset (this will add diving specific parameters for this heuristic) */ 350 SCIP_CALL( SCIPdivesetCreate(&divesetptr, heur, name, scip->set, scip->messagehdlr, scip->mem->setmem, 351 minreldepth, maxreldepth, maxlpiterquot, maxdiveubquot, maxdiveavgquot, maxdiveubquotnosol, 352 maxdiveavgquotnosol, lpresolvedomchgquot, lpsolvefreq, maxlpiterofs, initialseed, backtrack, 353 onlylpbranchcands, ispublic, specificsos1score, divesetgetscore, divesetavailable) ); 354 355 assert(divesetptr != NULL); 356 if( diveset != NULL ) 357 *diveset = divesetptr; 358 359 return SCIP_OKAY; 360 } 361 362 /** check specific preconditions for diving, e.g., if an incumbent solution is available */ 363 SCIP_RETCODE SCIPisDivesetAvailable( 364 SCIP* scip, /**< SCIP data structure */ 365 SCIP_DIVESET* diveset, /**< diving heuristic settings */ 366 SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */ 367 ) 368 { 369 assert(scip != NULL); 370 assert(diveset != NULL); 371 assert(available != NULL); 372 373 SCIP_CALL( SCIPdivesetIsAvailable(diveset, scip->set, available) ); 374 375 return SCIP_OKAY; 376 } 377