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_linesearchdiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that fixes variables with a large difference to their root solution
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/heuristics.h"
34   	#include "scip/heur_linesearchdiving.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_heur.h"
39   	#include "scip/scip_mem.h"
40   	#include "scip/scip_numerics.h"
41   	#include "scip/scip_sol.h"
42   	#include <string.h>
43   	
44   	#define HEUR_NAME             "linesearchdiving"
45   	#define HEUR_DESC             "LP diving heuristic that chooses fixings following the line from root solution to current solution"
46   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
47   	#define HEUR_PRIORITY         -1006000
48   	#define HEUR_FREQ             10
49   	#define HEUR_FREQOFS          6
50   	#define HEUR_MAXDEPTH         -1
51   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
52   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
53   	#define DIVESET_DIVETYPES     SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
54   	#define DIVESET_ISPUBLIC      TRUE   /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
55   	
56   	
57   	/*
58   	 * Default parameter settings
59   	 */
60   	
61   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
62   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
63   	#define DEFAULT_MAXLPITERQUOT      0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
64   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
65   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
66   	                                              *   where diving is performed (0.0: no limit) */
67   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
68   	                                              *   where diving is performed (0.0: no limit) */
69   	#define DEFAULT_MAXDIVEUBQUOTNOSOL  0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
70   	#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
71   	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
72   	#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
73   	#define DEFAULT_LPSOLVEFREQ           0 /**< LP solve frequency for diving heuristics */
74   	#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
75   	                                         *   more general constraint handler diving variable selection? */
76   	#define DEFAULT_RANDSEED            137 /**< default initialization for random seed number generation */
77   	/*
78   	 * Data structures
79   	 */
80   	
81   	/** primal heuristic data */
82   	struct SCIP_HeurData
83   	{
84   	   SCIP_SOL*             sol;                /**< working solution */
85   	};
86   	
87   	
88   	/*
89   	 * Local methods
90   	 */
91   	
92   	
93   	/*
94   	 * Callback methods of primal heuristic
95   	 */
96   	
97   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
98   	static
99   	SCIP_DECL_HEURCOPY(heurCopyLinesearchdiving)
100  	{  /*lint --e{715}*/
101  	   assert(scip != NULL);
102  	   assert(heur != NULL);
103  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
104  	
105  	   /* call inclusion method of primal heuristic */
106  	   SCIP_CALL( SCIPincludeHeurLinesearchdiving(scip) );
107  	
108  	   return SCIP_OKAY;
109  	}
110  	
111  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
112  	static
113  	SCIP_DECL_HEURFREE(heurFreeLinesearchdiving)
114  	{  /*lint --e{715}*/
115  	   SCIP_HEURDATA* heurdata;
116  	
117  	   assert(heur != NULL);
118  	   assert(scip != NULL);
119  	
120  	   /* free heuristic data */
121  	   heurdata = SCIPheurGetData(heur);
122  	   assert(heurdata != NULL);
123  	   SCIPfreeBlockMemory(scip, &heurdata);
124  	   SCIPheurSetData(heur, NULL);
125  	
126  	   return SCIP_OKAY;
127  	}
128  	
129  	
130  	/** initialization method of primal heuristic (called after problem was transformed) */
131  	static
132  	SCIP_DECL_HEURINIT(heurInitLinesearchdiving)
133  	{  /*lint --e{715}*/
134  	   SCIP_HEURDATA* heurdata;
135  	
136  	   assert(heur != NULL);
137  	
138  	   /* get heuristic data */
139  	   heurdata = SCIPheurGetData(heur);
140  	   assert(heurdata != NULL);
141  	
142  	   /* create working solution */
143  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
144  	
145  	   return SCIP_OKAY;
146  	}
147  	
148  	
149  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
150  	static
151  	SCIP_DECL_HEUREXIT(heurExitLinesearchdiving)
152  	{  /*lint --e{715}*/
153  	   SCIP_HEURDATA* heurdata;
154  	
155  	   assert(heur != NULL);
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(heurExecLinesearchdiving)
171  	{  /*lint --e{715}*/
172  	   SCIP_HEURDATA* heurdata;
173  	   SCIP_DIVESET* diveset;
174  	
175  	   heurdata = SCIPheurGetData(heur);
176  	   assert(SCIPheurGetNDivesets(heur) > 0);
177  	   assert(SCIPheurGetDivesets(heur) != NULL);
178  	   diveset = SCIPheurGetDivesets(heur)[0];
179  	   assert(diveset != NULL);
180  	
181  	   *result = SCIP_DIDNOTRUN;
182  	
183  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
184  	
185  	   return SCIP_OKAY;
186  	}
187  	
188  	/* diving setting callbacks */
189  	
190  	/** returns a score for the given candidate -- the best candidate maximizes the diving score */
191  	static
192  	SCIP_DECL_DIVESETGETSCORE(divesetGetScoreLinesearchdiving)
193  	{  /*lint --e{715}*/
194  	   SCIP_Real rootsolval;
195  	   SCIP_Real distquot;
196  	
197  	   rootsolval = SCIPvarGetRootSol(cand);
198  	
199  	   /* preferred branching direction is further away from the root LP solution */
200  	   if( SCIPisLT(scip, candsol, rootsolval) )
201  	   {
202  	      /* round down*/
203  	      *roundup = FALSE;
204  	
205  	      switch( divetype )
206  	      {
207  	         case SCIP_DIVETYPE_INTEGRALITY:
208  	            distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
209  	            break;
210  	         case SCIP_DIVETYPE_SOS1VARIABLE:
211  	            if ( SCIPisFeasPositive(scip, candsol) )
212  	               distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
213  	            else
214  	               distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
215  	            break;
216  	         default:
217  	            SCIPerrorMessage("Error: Unsupported diving type\n");
218  	            SCIPABORT();
219  	            return SCIP_INVALIDDATA; /*lint !e527*/
220  	      } /*lint !e788*/
221  	
222  	      /* avoid roundable candidates */
223  	      if( SCIPvarMayRoundDown(cand) )
224  	         distquot *= 1000.0;
225  	   }
226  	   else if( SCIPisGT(scip, candsol, rootsolval) )
227  	   {
228  	      /* round up */
229  	      switch( divetype )
230  	      {
231  	         case SCIP_DIVETYPE_INTEGRALITY:
232  	            distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
233  	            break;
234  	         case SCIP_DIVETYPE_SOS1VARIABLE:
235  	            if ( SCIPisFeasPositive(scip, candsol) )
236  	               distquot = (1.0 - candsfrac + SCIPsumepsilon(scip)) / (candsol - rootsolval);
237  	            else
238  	               distquot = (candsfrac + SCIPsumepsilon(scip)) / (rootsolval - candsol);
239  	            break;
240  	         default:
241  	            SCIPerrorMessage("Error: Unsupported diving type\n");
242  	            SCIPABORT();
243  	            return SCIP_INVALIDDATA; /*lint !e527*/
244  	      } /*lint !e788*/
245  	
246  	      /* avoid roundable candidates */
247  	      if( SCIPvarMayRoundUp(cand) )
248  	         distquot *= 1000.0;
249  	      *roundup = TRUE;
250  	   }
251  	   else
252  	   {
253  	      /* if the solution values are equal, we arbitrarily select branching downwards;
254  	       * candidates with equal LP solution values are penalized with an infinite score
255  	       */
256  	      *roundup = FALSE;
257  	      distquot = SCIPinfinity(scip);
258  	   }
259  	
260  	   *score = -distquot;
261  	
262  	   return SCIP_OKAY;
263  	}
264  	
265  	#define divesetAvailableLinesearchdiving NULL
266  	
267  	/*
268  	 * primal heuristic specific interface methods
269  	 */
270  	
271  	/** creates the linesearchdiving primal heuristic and includes it in SCIP */
272  	SCIP_RETCODE SCIPincludeHeurLinesearchdiving(
273  	   SCIP*                 scip                /**< SCIP data structure */
274  	   )
275  	{
276  	   SCIP_HEURDATA* heurdata;
277  	   SCIP_HEUR* heur;
278  	
279  	   /* create Linesearchdiving primal heuristic data */
280  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
281  	
282  	   /* include primal heuristic */
283  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
284  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
285  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecLinesearchdiving, heurdata) );
286  	
287  	   assert(heur != NULL);
288  	
289  	   /* set non-NULL pointers to callback methods */
290  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyLinesearchdiving) );
291  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeLinesearchdiving) );
292  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitLinesearchdiving) );
293  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitLinesearchdiving) );
294  	
295  	   /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
296  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
297  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL,
298  	         DEFAULT_LPRESOLVEDOMCHGQUOT, DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED,
299  	         DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
300  	         DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreLinesearchdiving, divesetAvailableLinesearchdiving) );
301  	
302  	   return SCIP_OKAY;
303  	}
304