Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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