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_veclendiving.c
26   	 * @ingroup DEFPLUGINS_HEUR
27   	 * @brief  LP diving heuristic that rounds variables with long column vectors
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_veclendiving.h"
35   	#include "scip/pub_heur.h"
36   	#include "scip/pub_lp.h"
37   	#include "scip/pub_message.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             "veclendiving"
47   	#define HEUR_DESC             "LP diving heuristic that rounds variables with long column vectors"
48   	#define HEUR_DISPCHAR         SCIP_HEURDISPCHAR_DIVING
49   	#define HEUR_PRIORITY         -1003100
50   	#define HEUR_FREQ             10
51   	#define HEUR_FREQOFS          4
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 /**< 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   	#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
75   	#define DEFAULT_LPSOLVEFREQ           0 /**< LP solve frequency for diving heuristics */
76   	#define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
77   	                                         *   more general constraint handler diving variable selection? */
78   	#define DEFAULT_RANDSEED            113 /**< initial seed for random number generation */
79   	
80   	/* locally defined heuristic data */
81   	struct SCIP_HeurData
82   	{
83   	   SCIP_SOL*             sol;                /**< working solution */
84   	};
85   	
86   	
87   	/*
88   	 * local methods
89   	 */
90   	
91   	/*
92   	 * Callback methods
93   	 */
94   	
95   	/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
96   	static
97   	SCIP_DECL_HEURCOPY(heurCopyVeclendiving)
98   	{  /*lint --e{715}*/
99   	   assert(scip != NULL);
100  	   assert(heur != NULL);
101  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
102  	
103  	   /* call inclusion method of primal heuristic */
104  	   SCIP_CALL( SCIPincludeHeurVeclendiving(scip) );
105  	
106  	   return SCIP_OKAY;
107  	}
108  	
109  	/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
110  	static
111  	SCIP_DECL_HEURFREE(heurFreeVeclendiving) /*lint --e{715}*/
112  	{  /*lint --e{715}*/
113  	   SCIP_HEURDATA* heurdata;
114  	
115  	   assert(heur != NULL);
116  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
117  	   assert(scip != NULL);
118  	
119  	   /* free heuristic data */
120  	   heurdata = SCIPheurGetData(heur);
121  	   assert(heurdata != NULL);
122  	
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(heurInitVeclendiving) /*lint --e{715}*/
133  	{  /*lint --e{715}*/
134  	   SCIP_HEURDATA* heurdata;
135  	
136  	   assert(heur != NULL);
137  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
138  	
139  	   /* get heuristic data */
140  	   heurdata = SCIPheurGetData(heur);
141  	   assert(heurdata != NULL);
142  	
143  	   /* create working solution */
144  	   SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
145  	
146  	   return SCIP_OKAY;
147  	}
148  	
149  	
150  	/** deinitialization method of primal heuristic (called before transformed problem is freed) */
151  	static
152  	SCIP_DECL_HEUREXIT(heurExitVeclendiving) /*lint --e{715}*/
153  	{  /*lint --e{715}*/
154  	   SCIP_HEURDATA* heurdata;
155  	
156  	   assert(heur != NULL);
157  	   assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
158  	
159  	   /* get heuristic data */
160  	   heurdata = SCIPheurGetData(heur);
161  	   assert(heurdata != NULL);
162  	
163  	   /* free working solution */
164  	   SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
165  	
166  	   return SCIP_OKAY;
167  	}
168  	
169  	
170  	/** execution method of primal heuristic */
171  	static
172  	SCIP_DECL_HEUREXEC(heurExecVeclendiving) /*lint --e{715}*/
173  	{  /*lint --e{715}*/
174  	   SCIP_HEURDATA* heurdata;
175  	   SCIP_DIVESET* diveset;
176  	
177  	   heurdata = SCIPheurGetData(heur);
178  	   assert(SCIPheurGetNDivesets(heur) > 0);
179  	   assert(SCIPheurGetDivesets(heur) != NULL);
180  	   diveset = SCIPheurGetDivesets(heur)[0];
181  	   assert(diveset != NULL);
182  	
183  	   *result = SCIP_DIDNOTRUN;
184  	
185  	   /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */
186  	   if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
187  	      return SCIP_OKAY;
188  	
189  	   SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) );
190  	
191  	   return SCIP_OKAY;
192  	}
193  	
194  	/** calculate score and preferred rounding direction for the candidate variable */
195  	static
196  	SCIP_DECL_DIVESETGETSCORE(divesetGetScoreVeclendiving)
197  	{
198  	   SCIP_Real obj;
199  	   SCIP_Real objdelta;
200  	   SCIP_Real colveclen;
201  	
202  	   obj = SCIPvarGetObj(cand);
203  	   *roundup = (obj >= 0.0);
204  	   objdelta = ((*roundup) ? (1.0 - candsfrac) * obj : -candsfrac * obj);
205  	   assert(objdelta >= 0.0);
206  	
207  	   colveclen = (SCIPvarGetStatus(cand) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(cand)) : 0.0);
208  	
209  	   /* larger score is better */
210  	   *score = (colveclen + 1.0) / (objdelta + SCIPsumepsilon(scip));
211  	
212  	   /* prefer decisions on binary variables */
213  	   if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY )
214  	      *score *= 0.001;
215  	
216  	   return SCIP_OKAY;
217  	}
218  	
219  	#define divesetAvailableVeclendiving NULL
220  	
221  	/*
222  	 * heuristic specific interface methods
223  	 */
224  	
225  	/** creates the veclendiving heuristic and includes it in SCIP */
226  	SCIP_RETCODE SCIPincludeHeurVeclendiving(
227  	   SCIP*                 scip                /**< SCIP data structure */
228  	   )
229  	{
230  	   SCIP_HEURDATA* heurdata;
231  	   SCIP_HEUR* heur;
232  	
233  	   /* create Veclendiving primal heuristic data */
234  	   SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
235  	
236  	   /* include primal heuristic */
237  	   SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
238  	         HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
239  	         HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecVeclendiving, heurdata) );
240  	
241  	   assert(heur != NULL);
242  	
243  	   /* set non-NULL pointers to callback methods */
244  	   SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyVeclendiving) );
245  	   SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeVeclendiving) );
246  	   SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitVeclendiving) );
247  	   SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitVeclendiving) );
248  	
249  	   /* veclendiving heuristic parameters */
250  	   /* create a diveset (this will automatically install some additional parameters for the heuristic) */
251  	   SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
252  	         DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
253  	         DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
254  	         DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreVeclendiving, divesetAvailableVeclendiving) );
255  	
256  	   return SCIP_OKAY;
257  	}
258  	
259