1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_pscostdiving.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief LP diving heuristic that chooses fixings w.r.t. the pseudo cost values
19 * @author Tobias Achterberg
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "scip/heuristics.h"
25 #include "scip/heur_pscostdiving.h"
26 #include "scip/pub_heur.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_misc.h"
29 #include "scip/pub_var.h"
30 #include "scip/scip_heur.h"
31 #include "scip/scip_mem.h"
32 #include "scip/scip_numerics.h"
33 #include "scip/scip_prob.h"
34 #include "scip/scip_sol.h"
35 #include "scip/scip_var.h"
36 #include <string.h>
37
38 #define HEUR_NAME "pscostdiving"
39 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values"
40 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
41 #define HEUR_PRIORITY -1002000
42 #define HEUR_FREQ 10
43 #define HEUR_FREQOFS 2
44 #define HEUR_MAXDEPTH -1
45 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
46 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
47 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
48 #define DIVESET_ISPUBLIC TRUE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
49
50
51 /*
52 * Default parameter settings
53 */
54
55 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
56 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
57 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
58 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
59 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60 * where diving is performed (0.0: no limit) */
61 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
62 * where diving is performed (0.0: no limit) */
63 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
64 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
65 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
66 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
67 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
68 #define DEFAULT_ONLYLPBRANCHCANDS TRUE /**< should only LP branching candidates be considered instead of the slower but
69 * more general constraint handler diving variable selection? */
70 #define DEFAULT_RANDSEED 103 /**< initial random seed */
71
72
73 /* locally defined heuristic data */
74 struct SCIP_HeurData
75 {
76 SCIP_SOL* sol; /**< working solution */
77 };
78
79 /*
80 * local methods
81 */
82
83 /*
84 * Callback methods
85 */
86
87 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
88 static
SCIP_DECL_HEURCOPY(heurCopyPscostdiving)89 SCIP_DECL_HEURCOPY(heurCopyPscostdiving)
90 { /*lint --e{715}*/
91 assert(scip != NULL);
92 assert(heur != NULL);
93 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
94
95 /* call inclusion method of primal heuristic */
96 SCIP_CALL( SCIPincludeHeurPscostdiving(scip) );
97
98 return SCIP_OKAY;
99 }
100
101 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
102 static
SCIP_DECL_HEURFREE(heurFreePscostdiving)103 SCIP_DECL_HEURFREE(heurFreePscostdiving) /*lint --e{715}*/
104 { /*lint --e{715}*/
105 SCIP_HEURDATA* heurdata;
106
107 assert(heur != NULL);
108 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
109 assert(scip != NULL);
110
111 /* free heuristic data */
112 heurdata = SCIPheurGetData(heur);
113 assert(heurdata != NULL);
114 SCIPfreeBlockMemory(scip, &heurdata);
115 SCIPheurSetData(heur, NULL);
116
117 return SCIP_OKAY;
118 }
119
120
121 /** initialization method of primal heuristic (called after problem was transformed) */
122 static
SCIP_DECL_HEURINIT(heurInitPscostdiving)123 SCIP_DECL_HEURINIT(heurInitPscostdiving) /*lint --e{715}*/
124 { /*lint --e{715}*/
125 SCIP_HEURDATA* heurdata;
126
127 assert(heur != NULL);
128 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
129
130 /* get heuristic data */
131 heurdata = SCIPheurGetData(heur);
132 assert(heurdata != NULL);
133
134 /* create working solution */
135 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
136
137 return SCIP_OKAY;
138 }
139
140
141 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
142 static
SCIP_DECL_HEUREXIT(heurExitPscostdiving)143 SCIP_DECL_HEUREXIT(heurExitPscostdiving) /*lint --e{715}*/
144 { /*lint --e{715}*/
145 SCIP_HEURDATA* heurdata;
146
147 assert(heur != NULL);
148 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
149
150 /* get heuristic data */
151 heurdata = SCIPheurGetData(heur);
152 assert(heurdata != NULL);
153
154 /* free working solution */
155 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
156
157 return SCIP_OKAY;
158 }
159
160 /** execution method of primal heuristic */
161 static
SCIP_DECL_HEUREXEC(heurExecPscostdiving)162 SCIP_DECL_HEUREXEC(heurExecPscostdiving) /*lint --e{715}*/
163 { /*lint --e{715}*/
164 SCIP_HEURDATA* heurdata;
165 SCIP_DIVESET* diveset;
166
167 heurdata = SCIPheurGetData(heur);
168 assert(heurdata != NULL);
169 assert(SCIPheurGetNDivesets(heur) > 0);
170 assert(SCIPheurGetDivesets(heur) != NULL);
171 diveset = SCIPheurGetDivesets(heur)[0];
172 assert(diveset != NULL);
173
174 *result = SCIP_DIDNOTRUN;
175
176 /* terminate if there are no integer variables (note that, e.g., SOS1 variables may be present) */
177 if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
178 return SCIP_OKAY;
179
180 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, SCIP_DIVECONTEXT_SINGLE) );
181
182 return SCIP_OKAY;
183 }
184
185
186 /** returns a score for the given candidate -- the best candidate maximizes the diving score */
187 static
SCIP_DECL_DIVESETGETSCORE(divesetGetScorePscostdiving)188 SCIP_DECL_DIVESETGETSCORE(divesetGetScorePscostdiving)
189 {
190 SCIP_Real pscostdown;
191 SCIP_Real pscostup;
192 SCIP_Real pscostquot;
193
194 SCIP_Bool mayrounddown;
195 SCIP_Bool mayroundup;
196
197 mayrounddown = SCIPvarMayRoundDown(cand);
198 mayroundup = SCIPvarMayRoundUp(cand);
199
200 /* bound fractions to not prefer variables that are nearly integral */
201 candsfrac = MAX(candsfrac, 0.1);
202 candsfrac = MIN(candsfrac, 0.9);
203
204 pscostdown = SCIPgetVarPseudocostVal(scip, cand, 0.0 - candsfrac);
205 pscostup = SCIPgetVarPseudocostVal(scip, cand, 1.0 - candsfrac);
206
207 /* determine the candidate direction. if the variable may be trivially rounded in one direction, take the other direction;
208 * otherwise, consider first the direction from the root solution, second the candidate fractionality, and
209 * last the direction of smaller pseudo costs
210 *
211 * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
212 * round down if the values to compare are equal within tolerances.
213 */
214 assert(pscostdown >= 0.0 && pscostup >= 0.0);
215 if( mayrounddown != mayroundup )
216 *roundup = mayrounddown;
217 else if( SCIPisLT(scip, candsol, SCIPvarGetRootSol(cand) - 0.4)
218 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) - 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
219 *roundup = FALSE;
220 else if( SCIPisGT(scip, candsol, SCIPvarGetRootSol(cand) + 0.4)
221 || (SCIPisEQ(scip, candsol, SCIPvarGetRootSol(cand) + 0.4) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
222 *roundup = TRUE;
223 else if( SCIPisLT(scip, candsfrac, 0.3)
224 || (SCIPisEQ(scip, candsfrac, 0.3) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
225 *roundup = FALSE;
226 else if( SCIPisGT(scip, candsfrac, 0.7)
227 || (SCIPisEQ(scip, candsfrac, 0.7) && SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0) )
228 *roundup = TRUE;
229 else if( SCIPisEQ(scip, pscostdown, pscostup) )
230 *roundup = (SCIPrandomGetInt(SCIPdivesetGetRandnumgen(diveset), 0, 1) == 0);
231 else if( pscostdown > pscostup )
232 *roundup = TRUE;
233 else
234 *roundup = FALSE;
235
236 if( *roundup )
237 pscostquot = sqrt(candsfrac) * (1.0 + pscostdown) / (1.0 + pscostup);
238 else
239 pscostquot = sqrt(1.0 - candsfrac) * (1.0 + pscostup) / (1.0 + pscostdown);
240
241 /* prefer decisions on binary variables */
242 if( SCIPvarIsBinary(cand) && !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)))
243 pscostquot *= 1000.0;
244
245 assert(pscostquot >= 0);
246 *score = pscostquot;
247
248 return SCIP_OKAY;
249 }
250
251 #define divesetAvailablePscostdiving NULL
252
253 /*
254 * heuristic specific interface methods
255 */
256
257 /** creates the pscostdiving heuristic and includes it in SCIP */
SCIPincludeHeurPscostdiving(SCIP * scip)258 SCIP_RETCODE SCIPincludeHeurPscostdiving(
259 SCIP* scip /**< SCIP data structure */
260 )
261 {
262 SCIP_HEURDATA* heurdata;
263 SCIP_HEUR* heur;
264
265 /* create Pscostdiving primal heuristic data */
266 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
267
268 /* include primal heuristic */
269 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
270 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
271 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPscostdiving, heurdata) );
272
273 assert(heur != NULL);
274
275 /* set non-NULL pointers to callback methods */
276 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPscostdiving) );
277 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePscostdiving) );
278 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitPscostdiving) );
279 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitPscostdiving) );
280
281 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
282 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT,
283 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT,
284 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS,
285 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScorePscostdiving, divesetAvailablePscostdiving) );
286
287 return SCIP_OKAY;
288 }
289
290