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