Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_masterdiving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file heur_masterdiving.c
29  * @brief primal heuristic interface for LP diving heuristics on the master variables
30  * @author Tobias Achterberg
31  * @author Christian Puchert
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "heur_masterdiving.h"
40 #include "pricer_gcg.h"
41 #include "relax_gcg.h"
42 
43 
44 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
45 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
46 
47 
48 /*
49  * Default parameter settings for all diving heuristics
50  */
51 
52 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
53 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
54 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */
55 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
56 #define DEFAULT_MAXPRICEROUNDS 0 /**< maximal number of allowed pricing rounds (-1: no limit) */
57 #define DEFAULT_USEFARKASONLY FALSE /**< perform pricing only if infeasibility is encountered */
58 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
59  * where diving is performed (0.0: no limit) */
60 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
61  * where diving is performed (0.0: no limit) */
62 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
63 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
64 #define DEFAULT_BACKTRACK FALSE /**< single backtracking by choosing another variable in case of infeasibility */
65 #define DEFAULT_MAXDISCREPANCY 2 /**< maximal discrepancy allowed in backtracking and limited discrepancy search */
66 #define DEFAULT_MAXDISCDEPTH 0 /**< maximal depth until which a limited discrepancy search is performed */
67 
68 #define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
69 
70 #ifdef SCIP_STATISTIC
71 #define EVENTHDLR_NAME "masterdiving"
72 #define EVENTHDLR_DESC "event handler for masterdiving solution statistics"
73 #endif
74 
75 
76 /* locally defined heuristic data for all diving heuristics */
77 struct SCIP_HeurData
78 {
79  GCG_DECL_DIVINGFREE ((*divingfree)); /**< destructor of diving heuristic */
80  GCG_DECL_DIVINGINIT ((*divinginit)); /**< initialize diving heuristic */
81  GCG_DECL_DIVINGEXIT ((*divingexit)); /**< deinitialize diving heuristic */
82  GCG_DECL_DIVINGINITSOL ((*divinginitsol)); /**< solving process initialization method of diving heuristic */
83  GCG_DECL_DIVINGEXITSOL ((*divingexitsol)); /**< solving process deinitialization method of diving heuristic */
84  GCG_DECL_DIVINGINITEXEC ((*divinginitexec)); /**< execution initialization method of diving heuristic */
85  GCG_DECL_DIVINGEXITEXEC ((*divingexitexec)); /**< execution deinitialization method of diving heuristic */
86  GCG_DECL_DIVINGSELECTVAR ((*divingselectvar)); /**< variable selection method of diving heuristic */
87  GCG_DIVINGDATA* divingdata; /**< diving rule specific data */
88 
89  SCIP_SOL* sol; /**< working solution */
90  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
91  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
92  SCIP_Real maxlpiterquot; /**< maximal fraction of diving LP iterations compared to node LP iterations */
93  int maxlpiterofs; /**< additional number of allowed LP iterations */
94  int maxpricerounds; /**< maximal number of allowed pricing rounds (-1: no limit) */
95  SCIP_Bool usefarkasonly; /**< perform pricing only if infeasibility is encountered */
96  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
97  * where diving is performed (0.0: no limit) */
98  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
99  * where diving is performed (0.0: no limit) */
100  SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
101  SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
102  SCIP_Bool backtrack; /**< single backtracking by choosing another variable in case of infeasibility */
103  int maxdiscrepancy; /**< maximal discrepancy allowed in backtracking and limited discrepancy search */
104  int maxdiscdepth; /**< maximal depth until which a limited discrepancy search is performed */
105  SCIP_Longint nlpiterations; /**< LP iterations used in this heuristic */
106  SCIP_Longint npricerounds; /**< pricing rounds used in this heuristic */
107  int nsuccess; /**< number of runs that produced at least one feasible solution */
108 
109 #ifdef SCIP_STATISTIC
110  SCIP_Longint ncalls; /**< number of calls */
111  SCIP_Longint nsols; /**< number of solutions */
112  SCIP_Longint nimpsols; /**< number of improving solutions */
113  SCIP_Longint ndivesols; /**< number of integral diving LP solutions */
114  SCIP_Longint nimpdivesols; /**< number of improving integral diving LP solutions */
115  SCIP_Longint nroundsols; /**< number of integral solutions that have been obtained by rounding */
116  SCIP_Longint nimproundsols; /**< number of improving integral solutions obtained by rounding */
117  SCIP_Longint ndivenodes; /**< number of diving nodes */
118  SCIP_Longint nfarkas; /**< number of times an infeasibility was resolved by Farkas pricing */
119  SCIP_Longint notherdirections; /**< number of times a cutoff was resolved by branching in the other direction */
120  SCIP_Longint nbacktracks; /**< number of times a single backtracking at a deeper node was performed */
121  SCIP_Longint ndiscsearches; /**< number of times a limited discrepancy search was performed */
122  SCIP_Real bestprimalbd; /**< objective value of best solution found by this heuristic */
123  SCIP_Bool bestsolrounded; /**< was the best solution obtained by rounding? */
124 #endif
125 };
126 
127 #ifdef SCIP_STATISTIC
128 /** event handler data */
129 struct SCIP_EventhdlrData
130 {
131  SCIP_HEUR** heurs; /**< diving heuristics known to the event handler */
132  int nheurs; /**< number of diving heuristics known to the event handler */
133  SCIP_HEUR* runningheur; /**< the diving heuristic that is currently running, or NULL */
134 };
135 #endif
136 
137 
138 /*
139  * local methods
140  */
141 
142 
143 
144 /*
145  * Callback methods
146  */
147 
148 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
149 static
150 SCIP_DECL_HEURFREE(heurFreeMasterdiving) /*lint --e{715}*/
151 { /*lint --e{715}*/
152  SCIP_HEURDATA* heurdata;
153 
154  assert(heur != NULL);
155  assert(scip != NULL);
156 
157  /* get heuristic data */
158  heurdata = SCIPheurGetData(heur);
159  assert(heurdata != NULL);
160 
161  if( heurdata->divingfree != NULL )
162  {
163  SCIP_CALL( heurdata->divingfree(scip, heur) );
164  }
165 
166  /* free heuristic data */
167  SCIPfreeMemory(scip, &heurdata);
168  SCIPheurSetData(heur, NULL);
169 
170  return SCIP_OKAY;
171 }
172 
173 
174 /** initialization method of primal heuristic (called after problem was transformed) */
175 static
176 SCIP_DECL_HEURINIT(heurInitMasterdiving) /*lint --e{715}*/
177 { /*lint --e{715}*/
178  SCIP_HEURDATA* heurdata;
179 
180  assert(heur != NULL);
181 
182  /* get heuristic data */
183  heurdata = SCIPheurGetData(heur);
184  assert(heurdata != NULL);
185 
186  /* create working solution */
187  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
188 
189  heurdata->nlpiterations = 0;
190  heurdata->npricerounds = 0;
191  heurdata->nsuccess = 0;
192 
193  /* diving rule specific initialization */
194  if( heurdata->divinginit != NULL )
195  {
196  SCIP_CALL( heurdata->divinginit(scip, heur) );
197  }
198 
199  return SCIP_OKAY;
200 }
201 
202 
203 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
204 static
205 SCIP_DECL_HEUREXIT(heurExitMasterdiving) /*lint --e{715}*/
206 { /*lint --e{715}*/
207  SCIP_HEURDATA* heurdata;
208 
209  assert(heur != NULL);
210 
211  /* get heuristic data */
212  heurdata = SCIPheurGetData(heur);
213  assert(heurdata != NULL);
214 
215  /* diving rule specific deinitialization */
216  if( heurdata->divingexit != NULL )
217  {
218  SCIP_CALL( heurdata->divingexit(scip, heur) );
219  }
220 
221  /* free working solution */
222  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
223 
224  return SCIP_OKAY;
225 }
226 
227 
228 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
229 static
230 SCIP_DECL_HEURINITSOL(heurInitsolMasterdiving)
231 { /*lint --e{715}*/
232  SCIP_HEURDATA* heurdata;
233 
234  assert(heur != NULL);
235  assert(scip != NULL);
236 
237  /* get heuristic data */
238  heurdata = SCIPheurGetData(heur);
239  assert(heurdata != NULL);
240 
241 #ifdef SCIP_STATISTIC
242  /* initialize statistics */
243  heurdata->ncalls = 0;
244  heurdata->nsols = 0;
245  heurdata->nimpsols = 0;
246  heurdata->ndivesols = 0;
247  heurdata->nimpdivesols = 0;
248  heurdata->nroundsols = 0;
249  heurdata->nimproundsols = 0;
250  heurdata->ndivenodes = 0;
251  heurdata->nfarkas = 0;
252  heurdata->notherdirections = 0;
253  heurdata->nbacktracks = 0;
254  heurdata->ndiscsearches = 0;
255  heurdata->bestprimalbd = SCIPinfinity(scip);
256  heurdata->bestsolrounded = FALSE;
257 #endif
258 
259  /* diving rule specific initialization */
260  if( heurdata->divinginitsol != NULL )
261  {
262  SCIP_CALL( heurdata->divinginitsol(scip, heur) );
263  }
264 
265  return SCIP_OKAY;
266 }
267 
268 
269 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
270 static
271 SCIP_DECL_HEUREXITSOL(heurExitsolMasterdiving)
272 { /*lint --e{715}*/
273  SCIP_HEURDATA* heurdata;
274 
275  assert(heur != NULL);
276  assert(scip != NULL);
277 
278  /* get heuristic data */
279  heurdata = SCIPheurGetData(heur);
280  assert(heurdata != NULL);
281 
282  /* diving rule specific deinitialization */
283  if( heurdata->divingexitsol != NULL )
284  {
285  SCIP_CALL( heurdata->divingexitsol(scip, heur) );
286  }
287 
288  return SCIP_OKAY;
289 }
290 
291 
292 /** execution method of primal heuristic */
293 static
294 SCIP_DECL_HEUREXEC(heurExecMasterdiving) /*lint --e{715}*/
295 { /*lint --e{715}*/
296  SCIP* origprob;
297 #ifdef SCIP_STATISTIC
298  SCIP_EVENTHDLR* eventhdlr;
299  SCIP_EVENTHDLRDATA* eventhdlrdata;
300 #endif
301  SCIP_HEURDATA* heurdata;
302  SCIP_LPSOLSTAT lpsolstat;
303  SCIP_VAR** selectedvars;
304  SCIP_VAR** tabulist;
305  int* discrepancies;
306  SCIP_Real searchubbound;
307  SCIP_Real searchavgbound;
308  SCIP_Real searchbound;
309  SCIP_Real objval;
310  SCIP_Real oldobjval;
311  SCIP_Bool lperror;
312  SCIP_Bool cutoff;
313  SCIP_Longint ncalls;
314  SCIP_Longint nsolsfound;
315  SCIP_Longint nlpiterations; /* lp iterations performed in one single diving loop */
316  SCIP_Longint maxnlpiterations;
317  int totalpricerounds; /* pricing rounds performed in one call of the heuristic */
318  int nlpcands;
319  int startnlpcands;
320  int depth;
321  int maxdepth;
322  int maxdivedepth;
323  int divedepth;
324  int discrepancy;
325 
326 #ifdef NDEBUG
327  SCIP_RETCODE retstat;
328 #endif
329 
330 #ifdef SCIP_STATISTIC
331  /* variable declarations for additional statistics */
332  int ndivenodes; /* number of diving nodes */
333  int maxreacheddepth; /* maximal diving depth reached in this call */
334  int nfarkas; /* number of times an infeasibility was resolved by Farkas pricing */
335  int nbacktracks; /* number of times a single backtracking at a deeper node was performed */
336  int ndiscsearches; /* number of times a limited discrepancy search was performed */
337  SCIP_Longint totallpiters; /* lp iterations performed in one call of the heuristic */
338  SCIP_CLOCK* lptime; /* time spent for solving diving LPs */
339 #endif
340 
341  int i;
342 
343  assert(heur != NULL);
344  assert(scip != NULL);
345  assert(result != NULL);
346 
347  /* get original problem */
348  origprob = GCGmasterGetOrigprob(scip);
349  assert(origprob != NULL);
350 
351 #ifdef SCIP_STATISTIC
352  /* get the masterdiving event handler and its data */
353  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
354  assert(eventhdlr != NULL);
355  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
356  assert(eventhdlrdata != NULL);
357 #endif
358 
359  *result = SCIP_DELAYED;
360 
361  /* only call heuristic, if an optimal LP solution is at hand */
362  if( !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
363  return SCIP_OKAY;
364 
365  /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
366  if( !SCIPisLPSolBasic(scip) )
367  return SCIP_OKAY;
368 
369  /* don't dive two times at the same node */
370  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
371  return SCIP_OKAY;
372 
373  *result = SCIP_DIDNOTRUN;
374 
375  /* get heuristic data */
376  heurdata = SCIPheurGetData(heur);
377  assert(heurdata != NULL);
378 
379  /* check if fundamental diving callbacks are present */
380  assert(heurdata->divingselectvar != NULL);
381 
382  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
383  depth = SCIPgetDepth(scip);
384  maxdepth = SCIPgetMaxDepth(scip);
385  maxdepth = MAX(maxdepth, 30);
386  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
387  return SCIP_OKAY;
388 
389  /* calculate the maximal number of LP iterations until heuristic is aborted */
390  nlpiterations = SCIPgetNNodeLPIterations(scip);
391  ncalls = SCIPheurGetNCalls(heur);
392  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
393  maxnlpiterations = (SCIP_Longint)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxlpiterquot * nlpiterations);
394  maxnlpiterations += heurdata->maxlpiterofs;
395 
396  /* don't try to dive, if we took too many LP iterations during diving */
397  if( heurdata->nlpiterations >= maxnlpiterations )
398  return SCIP_OKAY;
399 
400  /* allow at least a certain number of LP iterations in this dive */
401  maxnlpiterations = MAX(maxnlpiterations, heurdata->nlpiterations + MINLPITER);
402 
403  /* get number of fractional variables that should be integral */
404  nlpcands = SCIPgetNLPBranchCands(scip);
405 
406  /* don't try to dive, if there are no fractional variables */
407  if( nlpcands == 0 )
408  return SCIP_OKAY;
409 
410  /* calculate the objective search bound */
411  if( SCIPgetNSolsFound(scip) == 0 )
412  {
413  if( heurdata->maxdiveubquotnosol > 0.0 )
414  searchubbound = SCIPgetLowerbound(scip)
415  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
416  else
417  searchubbound = SCIPinfinity(scip);
418  if( heurdata->maxdiveavgquotnosol > 0.0 )
419  searchavgbound = SCIPgetLowerbound(scip)
420  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
421  else
422  searchavgbound = SCIPinfinity(scip);
423  }
424  else
425  {
426  if( heurdata->maxdiveubquot > 0.0 )
427  searchubbound = SCIPgetLowerbound(scip)
428  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
429  else
430  searchubbound = SCIPinfinity(scip);
431  if( heurdata->maxdiveavgquot > 0.0 )
432  searchavgbound = SCIPgetLowerbound(scip)
433  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
434  else
435  searchavgbound = SCIPinfinity(scip);
436  }
437  searchbound = MIN(searchubbound, searchavgbound);
438  if( SCIPisObjIntegral(scip) )
439  searchbound = SCIPceil(scip, searchbound);
440 
441  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
442  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
443  maxdivedepth = MIN(maxdivedepth, maxdepth);
444  maxdivedepth *= 10;
445 
446  /* allocate memory */
447  SCIP_CALL( SCIPallocBufferArray(scip, &discrepancies, heurdata->maxdiscdepth) );
448  SCIP_CALL( SCIPallocBufferArray(scip, &tabulist, heurdata->maxdiscrepancy) );
449  SCIP_CALL( SCIPallocBufferArray(scip, &selectedvars, heurdata->maxdiscdepth) );
450 
451  SCIPstatistic( SCIP_CALL( SCIPcreateClock(scip, &lptime) ) );
452 
453  /* initialize arrays */
454  for( i = 0; i < heurdata->maxdiscdepth; ++i )
455  {
456  discrepancies[i] = 0;
457  selectedvars[i] = NULL;
458  }
459  for( i = 0; i < heurdata->maxdiscrepancy; ++i )
460  tabulist[i] = NULL;
461 
462  /* diving rule specific initialization */
463  if( heurdata->divinginitexec != NULL )
464  {
465  SCIP_CALL( heurdata->divinginitexec(scip, heur) );
466  }
467 
468 
469  *result = SCIP_DIDNOTFIND;
470 
471 #ifdef SCIP_STATISTIC
472  /* notify the event handler of the diving heuristic that is now running */
473  eventhdlrdata->runningheur = heur;
474  ++heurdata->ncalls;
475 #endif
476 
477  /* start diving */
478  SCIP_CALL( SCIPstartProbing(scip) );
479 
480  /* enables collection of variable statistics during probing */
481  SCIPenableVarHistory(scip);
482 
483  /* get LP objective value*/
484  lpsolstat = SCIP_LPSOLSTAT_OPTIMAL;
485  objval = SCIPgetLPObjval(scip);
486 
487  SCIPdebugMessage("(node %"SCIP_LONGINT_FORMAT") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
488  SCIPgetNNodes(scip), SCIPheurGetName(heur), SCIPgetDepth(scip), nlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
489 
490  /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
491  * - if possible, we dive at least with the depth 10
492  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
493  */
494  lperror = FALSE;
495  cutoff = FALSE;
496  divedepth = 0;
497  discrepancy = 0;
498  totalpricerounds = 0;
499  startnlpcands = nlpcands;
500 
501 #ifdef SCIP_STATISTIC
502  ndivenodes = 0;
503  maxreacheddepth = 0;
504  nfarkas = 0;
505  nbacktracks = 0;
506  ndiscsearches = 0;
507  totallpiters = 0;
508 #endif
509 
510  while( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL && nlpcands > 0
511  && (divedepth < 10
512  || nlpcands <= startnlpcands - divedepth/2
513  || (divedepth < maxdivedepth && heurdata->nlpiterations < maxnlpiterations && objval < searchbound))
514  && !SCIPisStopped(scip) )
515  {
516  SCIP_VAR* bestcand;
517  SCIP_Real bestcandsol;
518  SCIP_Real bestfrac;
519  SCIP_Bool bestcandmayround;
520 
521  SCIP_Bool backtracked;
522  SCIP_Bool farkaspricing;
523 
524  SCIP_CALL( SCIPnewProbingNode(scip) );
525  divedepth++;
526 
527 #ifdef SCIP_STATISTIC
528  maxreacheddepth = MAX(maxreacheddepth, divedepth);
529  ++ndivenodes;
530 #endif
531 
532  /* get the current LP solution */
533  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
534 
535  bestcand = NULL;
536  bestcandmayround = TRUE;
537 
538  /* choose a variable to dive on */
539  SCIP_CALL( heurdata->divingselectvar(scip, heur, tabulist, heurdata->maxdiscrepancy, &bestcand, &bestcandmayround) );
540 
541  /* if no variable could be chosen, abort diving */
542  if( bestcand == NULL )
543  {
544  SCIPdebugMessage("No variable for diving could be selected, diving aborted\n");
545  break;
546  }
547  assert(bestcand != NULL);
548 
549  bestcandsol = SCIPgetSolVal(scip, heurdata->sol, bestcand);
550  bestfrac = SCIPfeasFrac(scip, bestcandsol);
551 
552  assert(SCIPisFeasGT(scip, bestcandsol, SCIPvarGetLbLocal(bestcand))
553  && SCIPisFeasLT(scip, bestcandsol, SCIPvarGetUbLocal(bestcand)));
554 
555  /* memorize selected variables up to the maximal depth for discrepancy search */
556  if( divedepth-1 < heurdata->maxdiscdepth )
557  selectedvars[divedepth-1] = bestcand;
558 
559  /* if all candidates are roundable, try to round the solution */
560  if( bestcandmayround )
561  {
562  SCIP_Bool success;
563 
564  /* try to round solution from diving LP */
565  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
566 
567  if( success )
568  {
569  SCIPdebugMessage("%s found roundable primal solution: obj=%g\n", SCIPheurGetName(heur), SCIPgetSolOrigObj(scip, heurdata->sol));
570 
571  /* try to add solution to SCIP */
572  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
573 
574  /* check, if solution was feasible and good enough */
575  if( success )
576  {
577  SCIPdebugMessage(" -> solution was feasible and good enough\n");
578  *result = SCIP_FOUNDSOL;
579  }
580  }
581  }
582 
583  /* If the variable is already fixed, numerical troubles may have occurred => abort diving! */
584  if( SCIPvarGetLbLocal(bestcand) >= SCIPvarGetUbLocal(bestcand) - 0.5 )
585  {
586  SCIPdebugMessage("Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
587  SCIPvarGetName(bestcand), SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), bestcandsol);
588  cutoff = TRUE;
589  break;
590  }
591 
592  /* round variable up */
593  SCIPdebugMessage(" dive %d/%d, LP iter %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT", pricerounds %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
594  divedepth, maxdivedepth, heurdata->nlpiterations, maxnlpiterations, totalpricerounds, heurdata->maxpricerounds,
595  SCIPvarGetName(bestcand), bestcandmayround,
596  bestcandsol, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand),
597  SCIPfeasCeil(scip, bestcandsol), SCIPvarGetUbLocal(bestcand));
598  SCIP_CALL( SCIPchgVarLbProbing(scip, bestcand, SCIPfeasCeil(scip, bestcandsol)) );
599 
600  backtracked = FALSE;
601  farkaspricing = FALSE;
602  do
603  {
604  /* apply domain propagation */
605  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
606 
607  if( !cutoff || backtracked || farkaspricing )
608  {
609  int npricerounds; /* pricing rounds performed in one single diving loop */
610 
611  /* resolve the diving LP */
612  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
613  * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
614  */
615  nlpiterations = SCIPgetNLPIterations(scip);
616  npricerounds = SCIPgetNPriceRounds(scip);
617  SCIPstatistic( SCIP_CALL( SCIPstartClock(scip, lptime) ) );
618 #ifdef NDEBUG
619  if( (!heurdata->usefarkasonly || farkaspricing )
620  && (heurdata->maxpricerounds == -1 || totalpricerounds < heurdata->maxpricerounds) )
621  retstat = SCIPsolveProbingLPWithPricing(scip, FALSE, TRUE, heurdata->maxpricerounds == -1 ? -1 : heurdata->maxpricerounds - totalpricerounds, &lperror, &cutoff);
622 
623  else
624  retstat = SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff);
625  if( retstat != SCIP_OKAY )
626  {
627  SCIPwarningMessage(scip, "Error while solving LP in %s heuristic; LP solve terminated with code <%d>\n", SCIPheurGetName(heur), retstat);
628  }
629 #else
630  if( (!heurdata->usefarkasonly || farkaspricing )
631  && (heurdata->maxpricerounds == -1 || totalpricerounds < heurdata->maxpricerounds) )
632  SCIP_CALL( SCIPsolveProbingLPWithPricing(scip, FALSE, TRUE, heurdata->maxpricerounds == -1 ? -1 : heurdata->maxpricerounds - totalpricerounds, &lperror, &cutoff) );
633  else
634  SCIP_CALL( SCIPsolveProbingLP(scip, MAX((int)(maxnlpiterations - heurdata->nlpiterations), MINLPITER), &lperror, &cutoff) );
635 #endif
636  SCIPstatistic( SCIP_CALL( SCIPstopClock(scip, lptime) ) );
637 
638  if( lperror )
639  break;
640 
641  /* update iteration counts */
642  heurdata->nlpiterations += SCIPgetNLPIterations(scip) - nlpiterations;
643  heurdata->npricerounds += (SCIP_Longint) SCIPgetNPriceRounds(scip) - (SCIP_Longint) npricerounds;
644  totalpricerounds += SCIPgetNPriceRounds(scip) - npricerounds;
645  SCIPstatistic( totallpiters += SCIPgetNLPIterations(scip) - nlpiterations );
646 
647  /* get LP solution status */
648  lpsolstat = SCIPgetLPSolstat(scip);
649  }
650 
651  /* If infeasibility is encountered, perform Farkas pricing in order to reach feasibility again */
652  if( lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE && heurdata->usefarkasonly
653  && !farkaspricing && (heurdata->maxpricerounds == -1 || totalpricerounds < heurdata->maxpricerounds)
654  && !backtracked )
655  {
656  SCIPdebugMessage(" *** infeasibility detected at level %d - perform Farkas pricing\n", SCIPgetProbingDepth(scip));
657 #ifdef SCIP_STATISTIC
658  ++nfarkas;
659 #endif
660  farkaspricing = TRUE;
661  }
662  else
663  farkaspricing = FALSE;
664 
665  /* perform backtracking if a cutoff or an infeasibility was detected and if Farkas pricing did not help */
666  if( (lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE || cutoff) && !backtracked && !farkaspricing )
667  {
668  /* Single backtracking (go back only one node) */
669  if( heurdata->backtrack && divedepth > heurdata->maxdiscdepth && discrepancy < heurdata->maxdiscrepancy )
670  {
671  SCIPdebugMessage(" *** cutoff or infeasibility detected at level %d - backtracking one node\n", SCIPgetProbingDepth(scip));
672 
673  /* go back one depth in the search tree */
674  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
675  --divedepth;
676 
677  tabulist[discrepancy] = bestcand;
678  ++discrepancy;
679 
680 #ifdef SCIP_STATISTIC
681  ++nbacktracks;
682 #endif
683  backtracked = TRUE;
684  }
685  /* Limited discrepancy search: If single backtracking unsuccessful, backtrack further */
686  else if( heurdata->maxdiscdepth > 0 )
687  {
688  SCIPdebugMessage(" *** cutoff or infeasibility detected at level %d - performing discrepancy search\n", SCIPgetProbingDepth(scip));
689 
690  /* go back until the search can differ from the previous search tree */
691  do
692  {
693  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
694  --divedepth;
695  }
696  while( divedepth > 0 &&
697  (divedepth >= heurdata->maxdiscdepth || discrepancies[divedepth] >= heurdata->maxdiscrepancy) );
698 
699  assert(divedepth < heurdata->maxdiscdepth);
700 
701  if( discrepancies[divedepth] < heurdata->maxdiscrepancy )
702  {
703  /* add variable selected previously at this depth to the tabu list */
704  tabulist[discrepancies[divedepth]] = selectedvars[divedepth];
705  ++discrepancies[divedepth];
706  discrepancy = discrepancies[divedepth];
707  for( i = discrepancy; i < heurdata->maxdiscrepancy; ++i )
708  tabulist[i] = NULL;
709  for( i = divedepth + 1; i < heurdata->maxdiscdepth; ++i )
710  discrepancies[i] = discrepancies[divedepth];
711 
712 #ifdef SCIP_STATISTIC
713  ++ndiscsearches;
714 #endif
715  backtracked = TRUE;
716  }
717  else
718  {
719  assert(divedepth == 0);
720  }
721  }
722  }
723  else
724  backtracked = FALSE;
725  }
726  while( backtracked || farkaspricing );
727 
728  if( !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
729  {
730  /* get new objective value */
731  oldobjval = objval;
732  objval = SCIPgetLPObjval(scip);
733 
734  /* update pseudo cost values */
735  if( SCIPisGT(scip, objval, oldobjval) )
736  {
737  SCIP_CALL( SCIPupdateVarPseudocost(scip, bestcand, 0.0-bestfrac,
738  objval - oldobjval, 1.0) );
739  }
740 
741  /* get new number of fractional variables */
742  nlpcands = SCIPgetNLPBranchCands(scip);
743 
744  if( GCGrelaxIsOrigSolFeasible(origprob) )
745  {
746  SCIPdebugMessage(" -> LP solution is feasible in the original problem\n");
747  }
748  }
749  SCIPdebugMessage(" -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", lpsolstat, objval, searchbound, nlpcands);
750  }
751 
752  /* check if a solution has been found */
753  if( nlpcands == 0 && !lperror && !cutoff && lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
754  {
755  SCIP_Bool success;
756 
757  /* create solution from diving LP */
758  SCIP_CALL( SCIPlinkLPSol(scip, heurdata->sol) );
759  SCIPdebugMessage("%s found primal solution: obj=%g\n", SCIPheurGetName(heur), SCIPgetSolOrigObj(scip, heurdata->sol));
760 
761  /* try to add solution to SCIP */
762  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
763 
764  /* check, if solution was feasible and good enough */
765  if( success )
766  {
767  SCIPdebugMessage(" -> solution was feasible and good enough\n");
768  *result = SCIP_FOUNDSOL;
769  }
770  }
771 
772  /* end diving */
773  SCIP_CALL( SCIPendProbing(scip) );
774 
775  if( *result == SCIP_FOUNDSOL )
776  heurdata->nsuccess++;
777 
778 #ifdef SCIP_STATISTIC
779  eventhdlrdata->runningheur = NULL;
780  heurdata->ndivenodes += ndivenodes;
781  heurdata->nfarkas += nfarkas;
782  heurdata->nbacktracks += nbacktracks;
783  heurdata->ndiscsearches += ndiscsearches;
784 
785  if( ndivenodes > 0 )
786  {
787  SCIPstatisticPrintf("Masterdiving statistic: %s at node %"SCIP_LONGINT_FORMAT" , %d dive nodes, max depth = %d, lptime = %6.1f sec, %"SCIP_LONGINT_FORMAT" lp iters, %d pricing rds, %d Farkas repairs, %d single backtracks, %d disc searches\n",
788  SCIPheurGetName(heur), SCIPgetNNodes(scip), ndivenodes, maxreacheddepth, SCIPgetClockTime(scip, lptime), totallpiters, totalpricerounds, nfarkas, nbacktracks, ndiscsearches);
789  }
790 #endif
791 
792  /* free memory */
793  if( heurdata->divingexitexec != NULL )
794  {
795  SCIP_CALL( heurdata->divingexitexec(scip, heur) );
796  }
797  SCIPstatistic( SCIP_CALL( SCIPfreeClock(scip, &lptime) ) );
798  SCIPfreeBufferArray(scip, &selectedvars);
799  SCIPfreeBufferArray(scip, &tabulist);
800  SCIPfreeBufferArray(scip, &discrepancies);
801 
802  SCIPdebugMessage("%s heuristic finished\n", SCIPheurGetName(heur));
803 
804  return SCIP_OKAY;
805 }
806 
807 
808 #ifdef SCIP_STATISTIC
809 /** destructor of event handler to free user data (called when SCIP is exiting) */
810 static
811 SCIP_DECL_EVENTFREE(eventFreeMasterdiving)
812 { /*lint --e{715}*/
813  SCIP_EVENTHDLRDATA* eventhdlrdata;
814 
815  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
816  assert(eventhdlrdata != NULL);
817 
818  assert((eventhdlrdata->heurs == NULL) == (eventhdlrdata->nheurs == 0));
819  SCIPfreeMemoryArrayNull(scip, &eventhdlrdata->heurs);
820 
821  SCIPfreeMemory(scip, &eventhdlrdata);
822 
823  SCIPeventhdlrSetData(eventhdlr, NULL);
824 
825  return SCIP_OKAY;
826 }
827 
828 /** initialization method of event handler (called after problem was transformed) */
829 static
830 SCIP_DECL_EVENTINIT(eventInitMasterdiving)
831 { /*lint --e{715}*/
832  assert(eventhdlr != NULL);
833 
834  /* notify GCG that this event should catch the SOLFOUND event */
835  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, NULL, NULL) );
836 
837  return SCIP_OKAY;
838 }
839 
840 /** deinitialization method of event handler (called before transformed problem is freed) */
841 static
842 SCIP_DECL_EVENTEXIT(eventExitMasterdiving)
843 { /*lint --e{715}*/
844  assert(eventhdlr != NULL);
845 
846  /* notify GCG that this event should drop the SOLFOUND event */
847  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, NULL, -1) );
848 
849  return SCIP_OKAY;
850 }
851 
852 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
853 static
854 SCIP_DECL_EVENTEXITSOL(eventExitsolMasterdiving)
855 { /*lint --e{715}*/
856  SCIP_EVENTHDLRDATA* eventhdlrdata;
857  int i;
858 
859  assert(eventhdlr != NULL);
860 
861  /* get event handler data */
862  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
863  assert(eventhdlrdata != NULL);
864 
865  /* print detailed statistics */
866  SCIPstatisticPrintf("Master Diving Heuristics : Calls Sols Improving DiveSols Improving RoundSols Improving Nodes LP iters Price rds max nFarkas Single bt Discsrch BestPrimal Rounded?\n");
867  for( i = 0; i < eventhdlrdata->nheurs; ++i )
868  {
869  SCIP_HEUR* heur;
870  SCIP_HEURDATA* heurdata;
871 
872  heur = eventhdlrdata->heurs[i];
873 
874  /* get heuristic data */
875  heurdata = SCIPheurGetData(heur);
876  assert(heurdata != NULL);
877 
878  SCIPstatisticPrintf("%-17.17s : %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10d %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT" %10"SCIP_LONGINT_FORMAT,
879  SCIPheurGetName(heur), heurdata->ncalls, heurdata->nsols, heurdata->nimpsols, heurdata->ndivesols, heurdata->nimpdivesols, heurdata->nroundsols, heurdata->nimproundsols, heurdata->ndivenodes, heurdata->nlpiterations, heurdata->npricerounds, heurdata->maxpricerounds, heurdata->nfarkas, heurdata->nbacktracks, heurdata->ndiscsearches);
880  if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
881  SCIPstatisticPrintf(" infinity");
882  else
883  SCIPstatisticPrintf(" %13.6e", heurdata->bestprimalbd);
884  SCIPstatisticPrintf(heurdata->bestsolrounded ? " yes\n" : " no\n");
885  }
886  SCIPstatisticPrintf("END\n");
887  SCIPstatisticPrintf("\n");
888 
889  return SCIP_OKAY;
890 }
891 
892 
893 /** execution method of event handler */
894 static
895 SCIP_DECL_EVENTEXEC(eventExecMasterdiving)
896 { /*lint --e{715}*/
897  SCIP_EVENTHDLRDATA* eventhdlrdata;
898  SCIP_HEUR* heur;
899  SCIP_HEURDATA* heurdata;
900  SCIP_SOL* sol;
901  SCIP_HEUR* solheur;
902  SCIP_Bool rounded;
903  SCIP_Bool improving;
904 
905  assert(eventhdlr != NULL);
906 
907  /* get event handler data */
908  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
909  assert(eventhdlrdata != NULL);
910 
911  /* get the diving heuristic which is currently running;
912  * if no diving heuristic is currently running, abort
913  */
914  heur = eventhdlrdata->runningheur;
915  if( heur == NULL )
916  return SCIP_OKAY;
917  assert(heur != NULL);
918 
919  /* get heuristic data */
920  heurdata = SCIPheurGetData(heur);
921  assert(heurdata != NULL);
922 
923  /* get new primal solution */
924  sol = SCIPeventGetSol(event);
925  assert(sol != NULL);
926 
927  /* get the heuristic that found the solution (might differ from the diving heuristic) */
928  solheur = SCIPgetSolHeur(scip, sol);
929 
930  /* update solution statistics */
931  ++heurdata->nsols;
932 
933  if( SCIPeventGetType(event) == SCIP_EVENTTYPE_BESTSOLFOUND )
934  {
935  ++heurdata->nimpsols;
936  improving = TRUE;
937  }
938  else
939  improving = FALSE;
940 
941  rounded = FALSE;
942  if( solheur != NULL && strcmp(SCIPheurGetName(solheur), "simplerounding") == 0 )
943  {
944  rounded = TRUE;
945  ++heurdata->nroundsols;
946  if( improving )
947  ++heurdata->nimproundsols;
948  }
949  else if( solheur == heur )
950  {
951  ++heurdata->ndivesols;
952  if( improving )
953  ++heurdata->nimpdivesols;
954  }
955 
956  if( SCIPgetSolTransObj(scip, sol) < heurdata->bestprimalbd )
957  {
958  heurdata->bestprimalbd = SCIPgetSolTransObj(scip, sol);
959  heurdata->bestsolrounded = rounded;
960  }
961 
962  SCIPstatisticPrintf("Masterdiving statistic: %s found solution %13.6e , improving = %u , rounded = %u\n",
963  SCIPheurGetName(heur), SCIPgetSolTransObj(scip, sol), improving, rounded);
964 
965  return SCIP_OKAY;
966 }
967 #endif
968 
969 
970 /*
971  * heuristic specific interface methods
972  */
973 
974 /** gets diving rule specific data of a diving heuristic */
976  SCIP_HEUR* heur /**< primal heuristic */
977  )
978 {
979  SCIP_HEURDATA* heurdata;
980 
981  assert(heur != NULL);
982 
983  /* get heuristic data */
984  heurdata = SCIPheurGetData(heur);
985  assert(heurdata != NULL);
986 
987  return heurdata->divingdata;
988 }
989 
990 /** sets diving rule specific data of a diving heuristic */
992  SCIP_HEUR* heur, /**< primal heuristic */
993  GCG_DIVINGDATA* divingdata /**< diving rule specific data */
994  )
995 {
996  SCIP_HEURDATA* heurdata;
997 
998  assert(heur != NULL);
999 
1000  /* get heuristic data */
1001  heurdata = SCIPheurGetData(heur);
1002  assert(heurdata != NULL);
1003 
1004  heurdata->divingdata = divingdata;
1005 }
1006 
1007 /** creates a master diving heuristic and includes it in GCG */
1009  SCIP* scip, /**< SCIP data structure */
1010  SCIP_HEUR** heur, /**< pointer to diving heuristic */
1011  const char* name, /**< name of primal heuristic */
1012  const char* desc, /**< description of primal heuristic */
1013  char dispchar, /**< display character of primal heuristic */
1014  int priority, /**< priority of the primal heuristic */
1015  int freq, /**< frequency for calling primal heuristic */
1016  int freqofs, /**< frequency offset for calling primal heuristic */
1017  int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
1018  GCG_DECL_DIVINGFREE ((*divingfree)), /**< destructor of diving heuristic */
1019  GCG_DECL_DIVINGINIT ((*divinginit)), /**< initialize diving heuristic */
1020  GCG_DECL_DIVINGEXIT ((*divingexit)), /**< deinitialize diving heuristic */
1021  GCG_DECL_DIVINGINITSOL ((*divinginitsol)), /**< solving process initialization method of diving heuristic */
1022  GCG_DECL_DIVINGEXITSOL ((*divingexitsol)), /**< solving process deinitialization method of diving heuristic */
1023  GCG_DECL_DIVINGINITEXEC ((*divinginitexec)), /**< execution initialization method of diving heuristic */
1024  GCG_DECL_DIVINGEXITEXEC ((*divingexitexec)), /**< execution deinitialization method of diving heuristic */
1025  GCG_DECL_DIVINGSELECTVAR ((*divingselectvar)), /**< variable selection method of diving heuristic */
1026  GCG_DIVINGDATA* divingdata /**< diving rule specific data (or NULL) */
1027  )
1028 {
1029 #ifdef SCIP_STATISTIC
1030  SCIP_EVENTHDLRDATA* eventhdlrdata;
1031  SCIP_EVENTHDLR* eventhdlr;
1032 #endif
1033  SCIP_HEURDATA* heurdata;
1034  char paramname[SCIP_MAXSTRLEN];
1035 
1036 #ifdef SCIP_STATISTIC
1037  /* get masterdiving event handler and its data */
1038  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
1039  assert(eventhdlr != NULL);
1040  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1041  assert(eventhdlrdata != NULL);
1042 #endif
1043 
1044  /* create Masterdiving primal heuristic data */
1045  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1046 
1047  /* set diving rule callbacks and data */
1048  heurdata->divingfree = divingfree;
1049  heurdata->divinginit = divinginit;
1050  heurdata->divingexit = divingexit;
1051  heurdata->divinginitsol = divinginitsol;
1052  heurdata->divingexitsol = divingexitsol;
1053  heurdata->divinginitexec = divinginitexec;
1054  heurdata->divingexitexec = divingexitexec;
1055  heurdata->divingselectvar = divingselectvar;
1056  heurdata->divingdata = divingdata;
1057 
1058  /* include primal heuristic */
1059  SCIP_CALL( SCIPincludeHeurBasic(scip, heur,
1060  name, desc, dispchar, priority, freq, freqofs,
1061  maxdepth, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecMasterdiving, heurdata) );
1062 
1063  assert(*heur != NULL);
1064 
1065  /* set non-NULL pointers to callback methods */
1066  SCIP_CALL( SCIPsetHeurFree(scip, *heur, heurFreeMasterdiving) );
1067  SCIP_CALL( SCIPsetHeurInit(scip, *heur, heurInitMasterdiving) );
1068  SCIP_CALL( SCIPsetHeurExit(scip, *heur, heurExitMasterdiving) );
1069  SCIP_CALL( SCIPsetHeurInitsol(scip, *heur, heurInitsolMasterdiving) );
1070  SCIP_CALL( SCIPsetHeurExitsol(scip, *heur, heurExitsolMasterdiving) );
1071 
1072  /* masterdiving heuristic parameters */
1073  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/minreldepth", name);
1074  SCIP_CALL( SCIPaddRealParam(scip,
1075  paramname,
1076  "minimal relative depth to start diving",
1077  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
1078  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxreldepth", name);
1079  SCIP_CALL( SCIPaddRealParam(scip,
1080  paramname,
1081  "maximal relative depth to start diving",
1082  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
1083  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterquot", name);
1084  SCIP_CALL( SCIPaddRealParam(scip,
1085  paramname,
1086  "maximal fraction of diving LP iterations compared to node LP iterations",
1087  &heurdata->maxlpiterquot, FALSE, DEFAULT_MAXLPITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1088  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterofs", name);
1089  SCIP_CALL( SCIPaddIntParam(scip,
1090  paramname,
1091  "additional number of allowed LP iterations",
1092  &heurdata->maxlpiterofs, FALSE, DEFAULT_MAXLPITEROFS, 0, INT_MAX, NULL, NULL) );
1093  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxpricerounds", name);
1094  SCIP_CALL( SCIPaddIntParam(scip,
1095  paramname,
1096  "maximal number of allowed pricing rounds (-1: no limit)",
1097  &heurdata->maxpricerounds, FALSE, DEFAULT_MAXPRICEROUNDS, -1, INT_MAX, NULL, NULL) );
1098  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/usefarkasonly", name);
1099  SCIP_CALL( SCIPaddBoolParam(scip,
1100  paramname,
1101  "perform pricing only if infeasibility is encountered",
1102  &heurdata->usefarkasonly, TRUE, DEFAULT_USEFARKASONLY, NULL, NULL) );
1103  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquot", name);
1104  SCIP_CALL( SCIPaddRealParam(scip,
1105  paramname,
1106  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
1107  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
1108  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquot", name);
1109  SCIP_CALL( SCIPaddRealParam(scip,
1110  paramname,
1111  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
1112  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1113  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquotnosol", name);
1114  SCIP_CALL( SCIPaddRealParam(scip,
1115  paramname,
1116  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
1117  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
1118  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquotnosol", name);
1119  SCIP_CALL( SCIPaddRealParam(scip,
1120  paramname,
1121  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
1122  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1123  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/backtrack", name);
1124  SCIP_CALL( SCIPaddBoolParam(scip,
1125  paramname,
1126  "single backtracking by choosing another variable in case of infeasibility",
1127  &heurdata->backtrack, TRUE, DEFAULT_BACKTRACK, NULL, NULL) );
1128  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiscrepancy", name);
1129  SCIP_CALL( SCIPaddIntParam(scip,
1130  paramname,
1131  "maximal discrepancy allowed in backtracking and limited discrepancy search",
1132  &heurdata->maxdiscrepancy, TRUE, DEFAULT_MAXDISCREPANCY, 0, INT_MAX, NULL, NULL) );
1133  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiscdepth", name);
1134  SCIP_CALL( SCIPaddIntParam(scip,
1135  paramname,
1136  "maximal depth until which a limited discrepancy search is performed",
1137  &heurdata->maxdiscdepth, TRUE, DEFAULT_MAXDISCDEPTH, 0, INT_MAX, NULL, NULL) );
1138 
1139 #ifdef SCIP_STATISTIC
1140  /* register the diving heuristic to the masterdiving event handler */
1141  assert((eventhdlrdata->heurs == NULL) == (eventhdlrdata->nheurs == 0));
1142  if( eventhdlrdata->nheurs == 0 )
1143  {
1144  SCIP_CALL( SCIPallocMemoryArray(scip, &eventhdlrdata->heurs, 1) ); /*lint !e506*/
1145  }
1146  else
1147  {
1148  SCIP_CALL( SCIPreallocMemoryArray(scip, &eventhdlrdata->heurs, eventhdlrdata->nheurs+1) );
1149  }
1150  eventhdlrdata->heurs[eventhdlrdata->nheurs] = *heur;
1151  ++eventhdlrdata->nheurs;
1152 #endif
1153 
1154  return SCIP_OKAY;
1155 }
1156 
1157 /** creates event handler for masterdiving event */
1159  SCIP* scip /**< SCIP data structure */
1160  )
1161 {
1162 #ifdef SCIP_STATISTIC
1163  SCIP_EVENTHDLRDATA* eventhdlrdata;
1164  SCIP_EVENTHDLR* eventhdlr;
1165 
1166  /* create master event handler data */
1167  SCIP_CALL( SCIPallocMemory(scip, &eventhdlrdata) );
1168  assert(eventhdlrdata != NULL);
1169 
1170  eventhdlr = NULL;
1171 
1172  /* include event handler into GCG */
1173  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
1174  eventExecMasterdiving, eventhdlrdata) );
1175  assert(eventhdlr != NULL);
1176 
1177  /* set non fundamental callbacks via setter functions */
1178  SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeMasterdiving) );
1179  SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitMasterdiving) );
1180  SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitMasterdiving) );
1181  SCIP_CALL( SCIPsetEventhdlrExitsol(scip, eventhdlr, eventExitsolMasterdiving) );
1182 
1183  /* initialize masterdiving event handler data */
1184  eventhdlrdata->heurs = NULL;
1185  eventhdlrdata->nheurs = 0;
1186  eventhdlrdata->runningheur = NULL;
1187 #endif
1188 
1189  return SCIP_OKAY;
1190 }
#define DEFAULT_MAXDISCDEPTH
static SCIP_DECL_EVENTEXIT(eventExitMastersol)
SCIP_Real maxdiveubquotnosol
static SCIP_DECL_EVENTFREE(eventFreeMastersol)
#define HEUR_TIMING
#define GCG_DECL_DIVINGSELECTVAR(x)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
SCIP_Real minreldepth
#define GCG_DECL_DIVINGINIT(x)
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MINRELDEPTH
static SCIP_DECL_HEURINITSOL(heurInitsolMasterdiving)
GCG_DECL_DIVINGINITEXEC((*divinginitexec))
#define EVENTHDLR_DESC
GCG_DECL_DIVINGEXITEXEC((*divingexitexec))
#define DEFAULT_MAXLPITERQUOT
SCIP_SOL * sol
static SCIP_DECL_EVENTEXITSOL(eventExitsolGenericbranchvaradd)
static SCIP_DECL_EVENTINIT(eventInitMastersol)
#define DEFAULT_MAXDIVEAVGQUOT
static SCIP_DECL_HEURINIT(heurInitMasterdiving)
GCG_DIVINGDATA * GCGheurGetDivingDataMaster(SCIP_HEUR *heur)
#define DEFAULT_MAXRELDEPTH
SCIP_Real maxdiveavgquot
GCG_DIVINGDATA * divingdata
GCG variable pricer.
SCIP_Real maxreldepth
SCIP_Longint npricerounds
SCIP_Real maxdiveavgquotnosol
static SCIP_DECL_HEUREXIT(heurExitMasterdiving)
#define GCG_DECL_DIVINGEXIT(x)
#define DEFAULT_MAXDISCREPANCY
#define GCG_DECL_DIVINGEXITEXEC(x)
#define GCG_DECL_DIVINGINITEXEC(x)
#define HEUR_USESSUBSCIP
#define MINLPITER
SCIP_RETCODE SCIPincludeEventHdlrMasterdiving(SCIP *scip)
GCG_DECL_DIVINGEXIT((*divingexit))
#define EVENTHDLR_NAME
primal heuristic interface for LP diving heuristics on the master variables
SCIP_Longint nlpiterations
GCG_DECL_DIVINGSELECTVAR((*divingselectvar))
#define DEFAULT_MAXDIVEUBQUOT
SCIP_Real maxdiveubquot
GCG_DECL_DIVINGINIT((*divinginit))
static SCIP_DECL_EVENTEXEC(eventExecGenericbranchvaradd)
GCG_DECL_DIVINGFREE((*divingfree))
SCIP * GCGmasterGetOrigprob(SCIP *scip)
#define GCG_DECL_DIVINGEXITSOL(x)
void GCGheurSetDivingDataMaster(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
GCG relaxator.
#define DEFAULT_BACKTRACK
static SCIP_DECL_HEUREXITSOL(heurExitsolMasterdiving)
SCIP_Real maxlpiterquot
#define DEFAULT_USEFARKASONLY
static SCIP_DECL_HEUREXEC(heurExecMasterdiving)
GCG_DECL_DIVINGEXITSOL((*divingexitsol))
#define GCG_DECL_DIVINGINITSOL(x)
#define DEFAULT_MAXLPITEROFS
#define DEFAULT_MAXPRICEROUNDS
static SCIP_DECL_HEURFREE(heurFreeMasterdiving)
#define GCG_DECL_DIVINGFREE(x)
GCG_DECL_DIVINGINITSOL((*divinginitsol))
SCIP_Bool usefarkasonly
SCIP_RETCODE GCGincludeDivingHeurMaster(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, GCG_DECL_DIVINGFREE((*divingfree)), GCG_DECL_DIVINGINIT((*divinginit)), GCG_DECL_DIVINGEXIT((*divingexit)), GCG_DECL_DIVINGINITSOL((*divinginitsol)), GCG_DECL_DIVINGEXITSOL((*divingexitsol)), GCG_DECL_DIVINGINITEXEC((*divinginitexec)), GCG_DECL_DIVINGEXITEXEC((*divingexitexec)), GCG_DECL_DIVINGSELECTVAR((*divingselectvar)), GCG_DIVINGDATA *divingdata)