Scippy

SCIP

Solving Constraint Integer Programs

heur_guideddiving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_guideddiving.c
17  * @brief LP diving heuristic that chooses fixings in direction of incumbent solutions
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/heur_guideddiving.h"
27 
28 #define HEUR_NAME "guideddiving"
29 #define HEUR_DESC "LP diving heuristic that chooses fixings in direction of incumbent solutions"
30 #define HEUR_DISPCHAR 'g'
31 #define HEUR_PRIORITY -1007000
32 #define HEUR_FREQ 10
33 #define HEUR_FREQOFS 7
34 #define HEUR_MAXDEPTH -1
35 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
36 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
37 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */
38 
39 
40 /*
41  * Default parameter settings
42  */
43 
44 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
45 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
46 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
47 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
48 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
49  * where diving is performed (0.0: no limit) */
50 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
51  * where diving is performed (0.0: no limit) */
52 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
53 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */
54 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
55 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
56  * more general constraint handler diving variable selection? */
57 #define DEFAULT_RANDSEED 127 /**< initial seed for random number generation */
58 
59 /* locally defined heuristic data */
60 struct SCIP_HeurData
61 {
62  SCIP_SOL* sol; /**< working solution */
63 };
64 
65 /*
66  * local methods
67  */
68 
69 /*
70  * Callback methods
71  */
72 
73 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
74 static
75 SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
76 { /*lint --e{715}*/
77  assert(scip != NULL);
78  assert(heur != NULL);
79  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
80 
81  /* call inclusion method of primal heuristic */
83 
84  return SCIP_OKAY;
85 }
86 
87 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
88 static
89 SCIP_DECL_HEURFREE(heurFreeGuideddiving) /*lint --e{715}*/
90 { /*lint --e{715}*/
91  SCIP_HEURDATA* heurdata;
92 
93  assert(heur != NULL);
94  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
95  assert(scip != NULL);
96 
97  /* free heuristic data */
98  heurdata = SCIPheurGetData(heur);
99  assert(heurdata != NULL);
100 
101  SCIPfreeBlockMemory(scip, &heurdata);
102  SCIPheurSetData(heur, NULL);
103 
104  return SCIP_OKAY;
105 }
106 
107 
108 /** initialization method of primal heuristic (called after problem was transformed) */
109 static
110 SCIP_DECL_HEURINIT(heurInitGuideddiving) /*lint --e{715}*/
111 { /*lint --e{715}*/
112  SCIP_HEURDATA* heurdata;
114  assert(heur != NULL);
115  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
116 
117  /* get heuristic data */
118  heurdata = SCIPheurGetData(heur);
119  assert(heurdata != NULL);
120 
121  /* create working solution */
122  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
123 
124  return SCIP_OKAY;
125 }
126 
127 
128 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
129 static
130 SCIP_DECL_HEUREXIT(heurExitGuideddiving) /*lint --e{715}*/
131 { /*lint --e{715}*/
132  SCIP_HEURDATA* heurdata;
134  assert(heur != NULL);
135  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
136 
137  /* get heuristic data */
138  heurdata = SCIPheurGetData(heur);
139  assert(heurdata != NULL);
140 
141  /* free working solution */
142  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
143 
144  return SCIP_OKAY;
145 }
146 
147 
148 /** execution method of primal heuristic */
149 static
150 SCIP_DECL_HEUREXEC(heurExecGuideddiving) /*lint --e{715}*/
151 { /*lint --e{715}*/
152 
153  SCIP_HEURDATA* heurdata;
154  SCIP_DIVESET* diveset;
155 
156  assert(heur != NULL);
157  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
158  assert(scip != NULL);
159  assert(result != NULL);
160  assert(SCIPhasCurrentNodeLP(scip));
161 
162  *result = SCIP_DIDNOTRUN;
163 
164  /* don't dive, if no feasible solutions exist */
165  if( SCIPgetNSols(scip) == 0 )
166  return SCIP_OKAY;
167 
168  /* get best solution that should guide the search; if this solution lives in the original variable space,
169  * we cannot use it since it might violate the global bounds of the current problem
170  */
172  return SCIP_OKAY;
173 
174  /* get heuristic's data */
175  heurdata = SCIPheurGetData(heur);
176  assert(heurdata != NULL);
177 
178  /* if there are no integer variables (note that, e.g., SOS1 variables may be present) */
179  if ( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0 )
180  return SCIP_OKAY;
181 
182  assert(SCIPheurGetNDivesets(heur) > 0);
183  assert(SCIPheurGetDivesets(heur) != NULL);
184  diveset = SCIPheurGetDivesets(heur)[0];
185  assert(diveset != NULL);
186 
187  /* call generic diving algorithm */
188  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible) );
189 
190  return SCIP_OKAY;
191 }
192 
193 /* callbacks for diving */
194 
195 /** calculate score and preferred rounding direction for the candidate variable; the best candidate maximizes the
196  * score
197  */
198 static
199 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving)
200 {
201  SCIP_SOL* bestsol;
202  SCIP_Real bestsolval;
203  SCIP_Real obj;
204  SCIP_Real objnorm;
205  SCIP_Real objgain;
206 
207  bestsol = SCIPgetBestSol(scip);
208  assert(bestsol != NULL);
209  assert(!SCIPsolIsOriginal(bestsol));
210 
211  bestsolval = SCIPgetSolVal(scip, bestsol, cand);
212 
213  /* variable should be rounded (guided) into the direction of its incumbent solution value */
214  if( candsol < bestsolval )
215  *roundup = TRUE;
216  else
217  *roundup = FALSE;
218 
219  obj = SCIPvarGetObj(cand);
220  objnorm = SCIPgetObjNorm(scip);
221 
222  /* divide by objective norm to normalize obj into [-1,1] */
223  if( SCIPisPositive(scip, objnorm) )
224  obj /= objnorm;
225 
226  /* calculate objective gain and fractionality for the selected rounding direction */
227  if( *roundup )
228  {
229  candsfrac = 1.0 - candsfrac;
230  objgain = obj * candsfrac;
231  }
232  else
233  objgain = -obj * candsfrac;
234 
235  assert(objgain >= -1.0 && objgain <= 1.0);
236 
237  /* penalize too small fractions */
238  if( candsfrac < 0.01 )
239  candsfrac *= 0.1;
240 
241  /* prefer decisions on binary variables */
242  if( !SCIPvarIsBinary(cand) )
243  candsfrac *= 0.1;
244 
245  /* prefer variables which cannot be rounded by scoring their fractionality */
246  if( !(SCIPvarMayRoundDown(cand) || SCIPvarMayRoundUp(cand)) )
247  *score = -candsfrac;
248  else
249  *score = -2.0 - objgain;
250 
251  return SCIP_OKAY;
252 }
253 
254 /*
255  * heuristic specific interface methods
256  */
257 
258 /** creates the guideddiving heuristic and includes it in SCIP */
260  SCIP* scip /**< SCIP data structure */
261  )
262 {
263  SCIP_HEURDATA* heurdata;
264  SCIP_HEUR* heur;
265 
266  /* create Guideddiving primal heuristic data */
267  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
268 
269  /* include primal heuristic */
270  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
272  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGuideddiving, heurdata) );
273 
274  assert(heur != NULL);
275 
276  /* set non-NULL pointers to callback methods */
277  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyGuideddiving) );
278  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGuideddiving) );
279  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGuideddiving) );
280  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitGuideddiving) );
281 
282  /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
286 
287  return SCIP_OKAY;
288 }
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2465
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11902
SCIP_RETCODE SCIPincludeHeurGuideddiving(SCIP *scip)
#define DEFAULT_LPSOLVEFREQ
#define DEFAULT_MINRELDEPTH
#define HEUR_MAXDEPTH
static SCIP_DECL_HEURINIT(heurInitGuideddiving)
#define HEUR_PRIORITY
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8177
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47088
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1396
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreGuideddiving)
#define FALSE
Definition: def.h:64
#define DEFAULT_ONLYLPBRANCHCANDS
#define DEFAULT_LPRESOLVEDOMCHGQUOT
#define DEFAULT_MAXDIVEAVGQUOT
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
LP diving heuristic that chooses fixings in direction of incumbent solutions.
static SCIP_DECL_HEURCOPY(heurCopyGuideddiving)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8084
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1119
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define DEFAULT_MAXLPITERQUOT
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition: scip.c:11465
#define HEUR_TIMING
static SCIP_DECL_HEURFREE(heurFreeGuideddiving)
#define DIVESET_DIVETYPES
#define HEUR_USESSUBSCIP
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1198
#define HEUR_FREQOFS
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8145
#define DEFAULT_MAXRELDEPTH
SCIP_SOL * sol
Definition: struct_heur.h:41
#define SCIP_CALL(x)
Definition: def.h:350
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1406
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29208
#define DEFAULT_MAXLPITEROFS
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)))
Definition: scip.c:8521
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:38535
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
static SCIP_DECL_HEUREXIT(heurExitGuideddiving)
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39783
#define HEUR_DESC
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11857
#define DEFAULT_MAXDIVEUBQUOT
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible)
Definition: heuristics.c:192
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39882
#define DEFAULT_RANDSEED
static SCIP_DECL_HEUREXEC(heurExecGuideddiving)
#define HEUR_FREQ
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8161
#define DEFAULT_BACKTRACK
#define SCIP_Real
Definition: def.h:149
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8129
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1109
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38911
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3280
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3272
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37878
#define HEUR_NAME