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   heur_guideddiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that chooses fixings in direction of incumbent solutions
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heur_guideddiving.h"
34   	#include "scip/heuristics.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_sol.h"
38   	#include "scip/pub_var.h"
39   	#include "scip/scip_heur.h"
40   	#include "scip/scip_lp.h"
41   	#include "scip/scip_mem.h"
42   	#include "scip/scip_numerics.h"
43   	#include "scip/scip_prob.h"
44   	#include "scip/scip_sol.h"
45   	#include <string.h>
46   	
47   	#define HEUR_NAME             "guideddiving"
48   	#define HEUR_DESC             "LP diving heuristic that chooses fixings in direction of incumbent solutions"
49   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
50   	#define HEUR_PRIORITY         -1007000
51   	#define HEUR_FREQ             10
52   	#define HEUR_FREQOFS          7
53   	#define HEUR_MAXDEPTH         -1
54   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
55   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
56   	#define DIVESET_DIVETYPES     SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
57   	#define DIVESET_ISPUBLIC      TRUE   /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
58   	
59   	
60   	/*
61   	 * Default parameter settings
62   	 */
63   	
64   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
65   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
66   	#define DEFAULT_MAXLPITERQUOT      0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
67   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
68   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
69   	                                         *   where diving is performed (0.0: no limit) */
70   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
71   	                                         *   where diving is performed (0.0: no limit) */
72   	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
73   	#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
74   	#define DEFAULT_LPSOLVEFREQ           0 /**< LP solve frequency for diving heuristics */
75   	#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
76   	                                         *   more general constraint handler diving variable selection? */
77   	#define DEFAULT_RANDSEED            127 /**< initial seed for random number generation */
78   	
79   	/* locally defined heuristic data */
80   	struct SCIP_HeurData
81   	{
82   	   SCIP_SOL*             sol;                /**< working solution */
83   	};
84   	
85   	/*
86   	 * local methods
87   	 */
88   	
89   	/*
90   	 * Callback methods
91   	 */
92   	
93   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
94   	static
95   	SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
96   	{  /*lint --e{715}*/
97   	   assert(scip != NULL);
98   	   assert(heur != NULL);
99   	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
100  	
101  	   /* call inclusion method of primal heuristic */
102  	   SCIP_CALL( SCIPincludeHeurGuideddiving(scip) );
103  	
104  	   return SCIP_OKAY;
105  	}
106  	
107  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
108  	static
109  	SCIP_DECL_HEURFREE(heurFreeGuideddiving) /*lint --e{715}*/
110  	{  /*lint --e{715}*/
111  	   SCIP_HEURDATA* heurdata;
112  	
113  	   assert(heur != NULL);
114  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
115  	   assert(scip != NULL);
116  	
117  	   /* free heuristic data */
118  	   heurdata = SCIPheurGetData(heur);
119  	   assert(heurdata != NULL);
120  	
121  	   SCIPfreeBlockMemory(scip, &heurdata);
122  	   SCIPheurSetData(heur, NULL);
123  	
124  	   return SCIP_OKAY;
125  	}
126  	
127  	
128  	/** initialization method of primal heuristic (called after problem was transformed) */
129  	static
130  	SCIP_DECL_HEURINIT(heurInitGuideddiving) /*lint --e{715}*/
131  	{  /*lint --e{715}*/
132  	   SCIP_HEURDATA* heurdata;
133  	
134  	   assert(heur != NULL);
135  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
136  	
137  	   /* get heuristic data */
138  	   heurdata = SCIPheurGetData(heur);
139  	   assert(heurdata != NULL);
140  	
141  	   /* create working solution */
142  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
143  	
144  	   return SCIP_OKAY;
145  	}
146  	
147  	
148  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
149  	static
150  	SCIP_DECL_HEUREXIT(heurExitGuideddiving) /*lint --e{715}*/
151  	{  /*lint --e{715}*/
152  	   SCIP_HEURDATA* heurdata;
153  	
154  	   assert(heur != NULL);
155  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
156  	
157  	   /* get heuristic data */
158  	   heurdata = SCIPheurGetData(heur);
159  	   assert(heurdata != NULL);
160  	
161  	   /* free working solution */
162  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
163  	
164  	   return SCIP_OKAY;
165  	}
166  	
167  	
168  	/** execution method of primal heuristic */
169  	static
170  	SCIP_DECL_HEUREXEC(heurExecGuideddiving) /*lint --e{715}*/
171  	{  /*lint --e{715}*/
172  	   SCIP_HEURDATA* heurdata;
173  	   SCIP_DIVESET* diveset;
174  	
175  	   assert(heur != NULL);
176  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
177  	   assert(scip != NULL);
178  	   assert(result != NULL);
179  	   assert(SCIPhasCurrentNodeLP(scip));
180  	
181  	   *result = SCIP_DIDNOTRUN;
182  	
183  	  /* don't dive, if no feasible solutions exist */
184  	   if( SCIPgetNSols(scip) == 0 )
185  	      return SCIP_OKAY;
186  	
187  	   /* get best solution that should guide the search; if this solution lives in the original variable space,
188  	    * we cannot use it since it might violate the global bounds of the current problem
189  	    */
190  	   if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
191  	      return SCIP_OKAY;
192  	
193  	   /* get heuristic's data */
194  	   heurdata = SCIPheurGetData(heur);
195  	   assert(heurdata != NULL);
196  	
197  	   /* if there are no integer variables (note that, e.g., SOS1 variables may be present) */
198  	   if ( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
199  	      return SCIP_OKAY;
200  	
201  	   assert(SCIPheurGetNDivesets(heur) > 0);
202  	   assert(SCIPheurGetDivesets(heur) != NULL);
203  	   diveset = SCIPheurGetDivesets(heur)[0];
204  	   assert(diveset != NULL);
205  	
206  	   /* call generic diving algorithm */
207  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
208  	
209  	   return SCIP_OKAY;
210  	}
211  	
212  	/* callbacks for diving */
213  	
214  	/** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
215  	 *  score
216  	 */
217  	static
218  	SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving)
219  	{
220  	   SCIP_SOL* bestsol;
221  	   SCIP_Real bestsolval;
222  	   SCIP_Real obj;
223  	   SCIP_Real objnorm;
224  	   SCIP_Real objgain;
225  	
226  	   bestsol = SCIPgetBestSol(scip);
227  	   assert(bestsol != NULL);
228  	   assert(!SCIPsolIsOriginal(bestsol));
229  	
230  	   bestsolval = SCIPgetSolVal(scip, bestsol, cand);
231  	
232  	   /* variable should be rounded (guided) into the direction of its incumbent solution value */
233  	   if( candsol < bestsolval )
234  	      *roundup = TRUE;
235  	   else
236  	      *roundup = FALSE;
237  	
238  	   obj = SCIPvarGetObj(cand);
239  	   objnorm = SCIPgetObjNorm(scip);
240  	
241  	   /* divide by objective norm to normalize obj into [-1,1] */
242  	   if( SCIPisPositive(scip, objnorm) )
243  	      obj /= objnorm;
244  	
245  	   /* calculate objective gain and fractionality for the selected rounding direction */
246  	   if( *roundup )
247  	   {
248  	      candsfrac = 1.0 - candsfrac;
249  	      objgain = obj * candsfrac;
250  	   }
251  	   else
252  	      objgain = -obj * candsfrac;
253  	
254  	   assert(objgain >= -1.0 && objgain <= 1.0);
255  	
256  	   /* penalize too small fractions */
257  	   if( candsfrac < 0.01 )
258  	      candsfrac *= 0.1;
259  	
260  	   /* prefer decisions on binary variables */
261  	   if( !SCIPvarIsBinary(cand) )
262  	      candsfrac *= 0.1;
263  	
264  	   /* prefer variables which cannot be rounded by scoring their fractionality */
265  	   if( !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)) )
266  	      *score = -candsfrac;
267  	   else
268  	      *score = -2.0 - objgain;
269  	
270  	   return SCIP_OKAY;
271  	}
272  	
273  	/** callback to check preconditions for diving, e.g., if an incumbent solution is available */
274  	static
275  	SCIP_DECL_DIVESETAVAILABLE(divesetAvailableGuideddiving)
276  	{
277  	   /* don't dive with guided diving if no feasible solutions exists or
278  	    * if this solution lives in the original variable space,
279  	    * because it might violate the global bounds of the current problem
280  	    */
281  	   if( SCIPgetNSols(scip) == 0 || SCIPsolIsOriginal(SCIPgetBestSol(scip)))
282  	      *available = FALSE;
283  	   else
284  	      *available = TRUE;
285  	
286  	   return SCIP_OKAY;
287  	}
288  	
289  	/*
290  	 * heuristic specific interface methods
291  	 */
292  	
293  	/** creates the guideddiving heuristic and includes it in SCIP */
294  	SCIP_RETCODE SCIPincludeHeurGuideddiving(
295  	   SCIP*                 scip                /**< SCIP data structure */
296  	   )
297  	{
298  	   SCIP_HEURDATA* heurdata;
299  	   SCIP_HEUR* heur;
300  	
301  	   /* create Guideddiving primal heuristic data */
302  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
303  	
304  	   /* include primal heuristic */
305  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
306  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
307  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGuideddiving, heurdata) );
308  	
309  	   assert(heur != NULL);
310  	
311  	   /* set non-NULL pointers to callback methods */
312  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGuideddiving) );
313  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGuideddiving) );
314  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGuideddiving) );
315  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGuideddiving) );
316  	
317  	   /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
318  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
319  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, 1.0, 1.0, DEFAULT_LPRESOLVEDOMCHGQUOT, DEFAULT_LPSOLVEFREQ,
320  	         DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, DIVESET_ISPUBLIC, DIVESET_DIVETYPES,
321  	         divesetGetScoreGuideddiving, divesetAvailableGuideddiving) );
322  	
323  	   return SCIP_OKAY;
324  	}
325