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_coefdiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that chooses fixings w.r.t. the matrix coefficients
28   	 * @author Tobias Achterberg
29   	 * @author Marc Pfetsch
30   	 *
31   	 * Indicator constraints are taken into account if present.
32   	 */
33   	
34   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35   	
36   	#include "scip/heur_coefdiving.h"
37   	#include "scip/heuristics.h"
38   	#include "scip/pub_heur.h"
39   	#include "scip/pub_message.h"
40   	#include "scip/pub_misc.h"
41   	#include "scip/pub_var.h"
42   	#include "scip/scip_heur.h"
43   	#include "scip/scip_lp.h"
44   	#include "scip/scip_mem.h"
45   	#include "scip/scip_numerics.h"
46   	#include "scip/scip_sol.h"
47   	#include <string.h>
48   	
49   	#define HEUR_NAME             "coefdiving"
50   	#define HEUR_DESC             "LP diving heuristic that chooses fixings w.r.t. the matrix coefficients"
51   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
52   	#define HEUR_PRIORITY         -1001000
53   	#define HEUR_FREQ             -1
54   	#define HEUR_FREQOFS          1
55   	#define HEUR_MAXDEPTH         -1
56   	#define HEUR_TIMING           SCIP_HEURTIMING_AFTERLPPLUNGE
57   	#define HEUR_USESSUBSCIP      FALSE  /**< does the heuristic use a secondary SCIP instance? */
58   	#define DIVESET_DIVETYPES     SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
59   	#define DIVESET_ISPUBLIC      TRUE  /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
60   	
61   	
62   	/*
63   	 * Default parameter settings
64   	 */
65   	
66   	#define DEFAULT_MINRELDEPTH         0.0 /**< minimal relative depth to start diving */
67   	#define DEFAULT_MAXRELDEPTH         1.0 /**< maximal relative depth to start diving */
68   	#define DEFAULT_MAXLPITERQUOT      0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
69   	#define DEFAULT_MAXLPITEROFS       1000 /**< additional number of allowed LP iterations */
70   	#define DEFAULT_MAXDIVEUBQUOT       0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
71   	                                         *   where diving is performed (0.0: no limit) */
72   	#define DEFAULT_MAXDIVEAVGQUOT      0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
73   	                                         *   where diving is performed (0.0: no limit) */
74   	#define DEFAULT_MAXDIVEUBQUOTNOSOL  0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
75   	#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
76   	#define DEFAULT_BACKTRACK          TRUE /**< use one level of backtracking if infeasibility is encountered? */
77   	#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
78   	#define DEFAULT_LPSOLVEFREQ           0 /**< LP solve frequency for diving heuristics */
79   	#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
80   	                                         *   more general constraint handler diving variable selection? */
81   	#define DEFAULT_RANDSEED             83 /**< default random seed */
82   	
83   	/* locally defined heuristic data */
84   	struct SCIP_HeurData
85   	{
86   	   SCIP_SOL*             sol;                /**< working solution */
87   	};
88   	
89   	/*
90   	 * local methods
91   	 */
92   	
93   	/*
94   	 * Callback methods
95   	 */
96   	
97   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
98   	static
99   	SCIP_DECL_HEURCOPY(heurCopyCoefdiving)
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 constraint handler */
106  	   SCIP_CALL( SCIPincludeHeurCoefdiving(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(heurFreeCoefdiving) /*lint --e{715}*/
114  	{  /*lint --e{715}*/
115  	   SCIP_HEURDATA* heurdata;
116  	
117  	   assert(heur != NULL);
118  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
119  	   assert(scip != NULL);
120  	
121  	   /* free heuristic data */
122  	   heurdata = SCIPheurGetData(heur);
123  	   assert(heurdata != NULL);
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(heurInitCoefdiving) /*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(heurExitCoefdiving) /*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(heurExecCoefdiving) /*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  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
187  	
188  	   return SCIP_OKAY;
189  	}
190  	
191  	/** returns a score for the given candidate -- the best candidate maximizes the diving score */
192  	static
193  	SCIP_DECL_DIVESETGETSCORE(divesetGetScoreCoefdiving)
194  	{
195  	   SCIP_Bool mayrounddown = SCIPvarMayRoundDown(cand);
196  	   SCIP_Bool mayroundup = SCIPvarMayRoundUp(cand);
197  	
198  	   if( mayrounddown || mayroundup )
199  	   {
200  	      /* choose rounding direction:
201  	       * - if variable may be rounded in both directions, round corresponding to the fractionality
202  	       * - otherwise, round in the infeasible direction
203  	       */
204  	      if( mayrounddown && mayroundup )
205  	      {
206  	         assert( divetype != SCIP_DIVETYPE_SOS1VARIABLE );
207  	
208  	         /* try to avoid variability; decide randomly if the LP solution can contain some noise */
209  	         if( SCIPisEQ(scip, candsfrac, 0.5) )
210  	            *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0);
211  	         else
212  	            *roundup = (candsfrac > 0.5);
213  	      }
214  	      else
215  	         *roundup = mayrounddown;
216  	   }
217  	   else
218  	   {
219  	      /* the candidate may not be rounded */
220  	      int nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
221  	      int nlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL);
222  	      *roundup = (nlocksdown > nlocksup || (nlocksdown == nlocksup && candsfrac > 0.5));
223  	   }
224  	
225  	   if( *roundup )
226  	   {
227  	      switch( divetype )
228  	      {
229  	         case SCIP_DIVETYPE_INTEGRALITY:
230  	            candsfrac = 1.0 - candsfrac;
231  	            break;
232  	         case SCIP_DIVETYPE_SOS1VARIABLE:
233  	            if ( SCIPisFeasPositive(scip, candsol) )
234  	               candsfrac = 1.0 - candsfrac;
235  	            break;
236  	         default:
237  	            SCIPerrorMessage("Error: Unsupported diving type\n");
238  	            SCIPABORT();
239  	            return SCIP_INVALIDDATA; /*lint !e527*/
240  	      } /*lint !e788*/
241  	      *score = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_MODEL);
242  	   }
243  	   else
244  	   {
245  	      if ( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
246  	         candsfrac = 1.0 - candsfrac;
247  	      *score = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
248  	   }
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 scaling the score
255  	       */
256  	      if( SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
257  	         (*score) *= 0.01;
258  	   }
259  	   else if( candsfrac < 0.01 )
260  	      (*score) *= 0.01;
261  	
262  	   /* prefer decisions on binary variables */
263  	   if( !SCIPvarIsBinary(cand) )
264  	      (*score) *= 0.1;
265  	
266  	   /* penalize the variable if it may be rounded. */
267  	   if( mayrounddown || mayroundup )
268  	      (*score) -= SCIPgetNLPRows(scip);
269  	
270  	   /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
271  	   assert( (0.0 < candsfrac && candsfrac < 1.0) || SCIPvarIsBinary(cand) || divetype == SCIP_DIVETYPE_SOS1VARIABLE );
272  	
273  	   return SCIP_OKAY;
274  	}
275  	
276  	/*
277  	 * heuristic specific interface methods
278  	 */
279  	
280  	#define divesetAvailableCoefdiving NULL
281  	
282  	/** creates the coefdiving heuristic and includes it in SCIP */
283  	SCIP_RETCODE SCIPincludeHeurCoefdiving(
284  	   SCIP*                 scip                /**< SCIP data structure */
285  	   )
286  	{
287  	   SCIP_HEURDATA* heurdata;
288  	   SCIP_HEUR* heur;
289  	
290  	   /* create coefdiving primal heuristic data */
291  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
292  	
293  	   /* include primal heuristic */
294  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
295  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
296  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCoefdiving, heurdata) );
297  	
298  	   assert(heur != NULL);
299  	
300  	   /* set non-NULL pointers to callback methods */
301  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCoefdiving) );
302  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCoefdiving) );
303  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCoefdiving) );
304  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitCoefdiving) );
305  	
306  	   /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
307  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
308  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
309  	         DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
310  	         DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreCoefdiving, divesetAvailableCoefdiving) );
311  	
312  	   return SCIP_OKAY;
313  	}
314  	
315