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