Scippy

SCIP

Solving Constraint Integer Programs

heur_nlpdiving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_nlpdiving.c
17  * @brief NLP diving heuristic that chooses fixings w.r.t. the fractionalities
18  * @author Timo Berthold
19  * @author Stefan Vigerske
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/heur_nlpdiving.h"
28 #include "scip/heur_subnlp.h" /* for NLP initialization */
29 #include "scip/heur_undercover.h" /* for cover computation */
30 #include "nlpi/nlpi.h" /* for NLP statistics, currently */
31 
32 
33 #define HEUR_NAME "nlpdiving"
34 #define HEUR_DESC "NLP diving heuristic that chooses fixings w.r.t. the fractionalities"
35 #define HEUR_DISPCHAR 'd'
36 #define HEUR_PRIORITY -1003000
37 #define HEUR_FREQ 10
38 #define HEUR_FREQOFS 3
39 #define HEUR_MAXDEPTH -1
40 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
41 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
42 
43 /* event handler properties */
44 #define EVENTHDLR_NAME "Nlpdiving"
45 #define EVENTHDLR_DESC "bound change event handler for " HEUR_NAME " heuristic"
46 
47 
48 /*
49  * Default parameter settings
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_MAXNLPITERABS 200 /**< minimial absolute number of allowed NLP iterations */
55 #define DEFAULT_MAXNLPITERREL 10 /**< additional allowed number of NLP iterations relative to successfully found solutions */
56 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
57  * where diving is performed (0.0: no limit) */
58 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
59  * where diving is performed (0.0: no limit) */
60 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
61 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
62 #define DEFAULT_MINSUCCQUOT 0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
63 #define DEFAULT_MAXFEASNLPS 10 /**< maximal number of NLPs with feasible solution to solve during one dive */
64 #define DEFAULT_FIXQUOT 0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */
65 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
66 #define DEFAULT_LP FALSE /**< should the LP relaxation be solved before the NLP relaxation? */
67 #define DEFAULT_PREFERLPFRACS FALSE /**< prefer variables that are also fractional in LP solution? */
68 #define DEFAULT_PREFERCOVER TRUE /**< should variables in a minimal cover be preferred? */
69 #define DEFAULT_SOLVESUBMIP FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */
70 #define DEFAULT_NLPSTART 's' /**< which point should be used as starting point for the NLP solver? */
71 #define DEFAULT_VARSELRULE 'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
72  * 'p'seudocost, 'g'uided, 'd'ouble)
73  */
74 #define DEFAULT_NLPFASTFAIL TRUE /**< should the NLP solver stop early if it converges slow? */
75 
76 #define MINNLPITER 10 /**< minimal number of NLP iterations allowed in each NLP solving call */
77 
78 /* locally defined heuristic data */
79 struct SCIP_HeurData
80 {
81  SCIP_SOL* sol; /**< working solution */
82  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
83  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
84  int maxnlpiterabs; /**< minimial absolute number of allowed NLP iterations */
85  int maxnlpiterrel; /**< additional allowed number of NLP iterations relative to successfully found solutions */
86  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
87  * where diving is performed (0.0: no limit) */
88  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
89  * where diving is performed (0.0: no limit) */
90  SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
91  SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
92  int maxfeasnlps; /**< maximal number of NLPs with feasible solution to solve during one dive */
93  SCIP_Real minsuccquot; /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
94  SCIP_Real fixquot; /**< percentage of fractional variables that should be fixed before the next NLP solve */
95  SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
96  SCIP_Bool lp; /**< should the LP relaxation be solved before the NLP relaxation? */
97  SCIP_Bool preferlpfracs; /**< prefer variables that are also fractional in LP solution? */
98  SCIP_Bool prefercover; /**< should variables in a minimal cover be preferred? */
99  SCIP_Bool solvesubmip; /**< should a sub-MIP be solved if all cover variables are fixed? */
100  SCIP_Bool nlpfastfail; /**< should the NLP solver stop early if it converges slow? */
101  char nlpstart; /**< which point should be used as starting point for the NLP solver? */
102  char varselrule; /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
103  * 'p'seudocost, 'g'uided, 'd'ouble)
104  */
105 
106  int nnlpiterations; /**< NLP iterations used in this heuristic */
107  int nsuccess; /**< number of runs that produced at least one feasible solution */
108  int nfixedcovervars; /**< number of variables in the cover that are already fixed */
109 #ifdef SCIP_STATISTIC
110  int nnlpsolves; /**< number of NLP solves */
111  int nfailcutoff; /**< number of fails due to cutoff */
112  int nfaildepth; /**< number of fails due to too deep */
113  int nfailnlperror; /**< number of fails due to NLP error */
114 #endif
115  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
116 };
117 
118 
119 /*
120  * local methods
121  */
122 
123 /** gets fractional variables of last NLP solution along with solution values and fractionalities
124  *
125  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
126  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
127  *
128  * @pre This method can be called if SCIP is in one of the following stages:
129  * - \ref SCIP_STAGE_INITSOLVE
130  * - \ref SCIP_STAGE_SOLVING
131  */
132 static
133 SCIP_RETCODE getNLPFracVars(
134  SCIP* scip, /**< SCIP data structure */
135  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
136  SCIP_VAR*** nlpcands, /**< pointer to store the array of NLP fractional variables, or NULL */
137  SCIP_Real** nlpcandssol, /**< pointer to store the array of NLP fractional variables solution values, or NULL */
138  SCIP_Real** nlpcandsfrac, /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */
139  int* nnlpcands /**< pointer to store the number of NLP fractional variables , or NULL */
140  )
141 {
142  int c;
143 
144  assert(scip != NULL);
145  assert(heurdata != NULL);
146  assert(nlpcands != NULL);
147  assert(nlpcandssol != NULL);
148  assert(nlpcandsfrac != NULL);
149  assert(nnlpcands != NULL);
150 
151  /* get fractional variables that should be integral */
152  SCIP_CALL( SCIPgetNLPFracVars(scip, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, NULL) );
153 
154  /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still
155  * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this
156  * (example: primsol=29.99999853455704, lower bound = 30)
157  */
158  for( c = 0; c < *nnlpcands; ++c )
159  {
160  assert(!SCIPisFeasIntegral(scip, (*nlpcandssol)[c]));
161 
162  if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) )
163  {
164  SCIP_Real newval;
165 
166  newval = ((*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]))
167  ? SCIPvarGetLbLocal((*nlpcands)[c]) - 0.5*SCIPfeastol(scip)
168  : SCIPvarGetUbLocal((*nlpcands)[c]) + 0.5*SCIPfeastol(scip);
169 
170  assert(SCIPisFeasIntegral(scip, newval));
171 
172  SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, (*nlpcands)[c], newval) );
173 
174  (*nnlpcands)--;
175 
176  if( c < *nnlpcands )
177  {
178  (*nlpcands)[c] = (*nlpcands)[*nnlpcands];
179  (*nlpcandssol)[c] = (*nlpcandssol)[*nnlpcands];
180  (*nlpcandsfrac)[c] = (*nlpcandsfrac)[*nnlpcands];
181  }
182  }
183  }
184 
185  /* prefer decisions on variables which are also fractional in LP solution */
186  if( heurdata->preferlpfracs && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
187  {
188  for( c = 0; c < *nnlpcands; ++c )
189  {
190  if( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, (*nlpcands)[c])) )
191  (*nlpcandsfrac)[c] *= 100.0;
192  }
193  }
194 
195  return SCIP_OKAY;
196 }
197 
198 /** finds best candidate variable w.r.t. fractionality:
199  * - prefer variables that may not be rounded without destroying NLP feasibility:
200  * - of these variables, round least fractional variable in corresponding direction
201  * - if all remaining fractional variables may be rounded without destroying NLP feasibility:
202  * - round variable with least increasing objective value
203  * - binary variables are prefered
204  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
205  * also be prefered if a correpsonding parameter is set
206  */
207 static
208 SCIP_RETCODE chooseFracVar(
209  SCIP* scip, /**< original SCIP data structure */
210  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
211  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
212  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
213  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
214  int nnlpcands, /**< number of NLP fractional variables */
215  SCIP_HASHMAP* varincover, /**< hash map for variables */
216  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
217  int* bestcand, /**< pointer to store the index of the best candidate variable */
218  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
219  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
220  )
221 {
222  SCIP_Real bestobjgain;
223  SCIP_Real bestfrac;
224  SCIP_Bool bestcandmayrounddown;
225  SCIP_Bool bestcandmayroundup;
226  int c;
227 
228  /* check preconditions */
229  assert(scip != NULL);
230  assert(heurdata != NULL);
231  assert(nlpcands != NULL);
232  assert(nlpcandssol != NULL);
233  assert(nlpcandsfrac != NULL);
234  assert(covercomputed == (varincover != NULL));
235  assert(bestcand != NULL);
236  assert(bestcandmayround != NULL);
237  assert(bestcandroundup != NULL);
238 
239  bestcandmayrounddown = TRUE;
240  bestcandmayroundup = TRUE;
241  bestobjgain = SCIPinfinity(scip);
242  bestfrac = SCIP_INVALID;
243 
244  for( c = 0; c < nnlpcands; ++c )
245  {
246  SCIP_VAR* var;
247  SCIP_Bool mayrounddown;
248  SCIP_Bool mayroundup;
249  SCIP_Bool roundup;
250  SCIP_Real frac;
251  SCIP_Real obj;
252  SCIP_Real objgain;
253 
254  var = nlpcands[c];
255 
256  mayrounddown = SCIPvarMayRoundDown(var);
257  mayroundup = SCIPvarMayRoundUp(var);
258  frac = nlpcandsfrac[c];
259  obj = SCIPvarGetObj(var);
260 
261  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
262  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
263  continue;
264 
265  if( mayrounddown || mayroundup )
266  {
267  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
268  if( bestcandmayrounddown || bestcandmayroundup )
269  {
270  /* choose rounding direction:
271  * - if variable may be rounded in both directions, round corresponding to the fractionality
272  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
273  * the current fractional solution
274  */
275  if( mayrounddown && mayroundup )
276  roundup = (frac > 0.5);
277  else
278  roundup = mayrounddown;
279 
280  if( roundup )
281  {
282  frac = 1.0 - frac;
283  objgain = frac*obj;
284  }
285  else
286  objgain = -frac*obj;
287 
288  /* penalize too small fractions */
289  if( frac < 0.01 )
290  objgain *= 1000.0;
291 
292  /* prefer decisions on binary variables */
293  if( !SCIPvarIsBinary(var) )
294  objgain *= 1000.0;
295 
296  /* prefer decisions on cover variables */
297  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
298  objgain *= 1000.0;
299 
300  /* check, if candidate is new best candidate */
301  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
302  {
303  *bestcand = c;
304  bestobjgain = objgain;
305  bestfrac = frac;
306  bestcandmayrounddown = mayrounddown;
307  bestcandmayroundup = mayroundup;
308  *bestcandroundup = roundup;
309  }
310  }
311  }
312  else
313  {
314  /* the candidate may not be rounded */
315  if( frac < 0.5 )
316  roundup = FALSE;
317  else
318  {
319  roundup = TRUE;
320  frac = 1.0 - frac;
321  }
322 
323  /* penalize too small fractions */
324  if( frac < 0.01 )
325  frac += 10.0;
326 
327  /* prefer decisions on binary variables */
328  if( !SCIPvarIsBinary(var) )
329  frac *= 1000.0;
330 
331  /* prefer decisions on cover variables */
332  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
333  frac *= 1000.0;
334 
335  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
336  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
337  {
338  *bestcand = c;
339  bestfrac = frac;
340  bestcandmayrounddown = FALSE;
341  bestcandmayroundup = FALSE;
342  *bestcandroundup = roundup;
343  }
344  assert(bestfrac < SCIP_INVALID);
345  }
346  }
347 
348  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
349 
350  return SCIP_OKAY;
351 }
352 
353 /** finds best candidate variable w.r.t. vector length:
354  * - round variable with a small ratio between the increase in the objective and the locking numbers
355  * - binary variables are prefered
356  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
357  * also be prefered if a corresponding parameter is set
358  */
359 static
360 SCIP_RETCODE chooseVeclenVar(
361  SCIP* scip, /**< original SCIP data structure */
362  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
363  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
364  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
365  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
366  int nnlpcands, /**< number of NLP fractional variables */
367  SCIP_HASHMAP* varincover, /**< hash map for variables */
368  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
369  int* bestcand, /**< pointer to store the index of the best candidate variable */
370  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
371  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
372  )
373 {
374  SCIP_Real bestscore;
375  int c;
376 
377  /* check preconditions */
378  assert(scip != NULL);
379  assert(heurdata != NULL);
380  assert(nlpcands != NULL);
381  assert(nlpcandsfrac != NULL);
382  assert(nlpcandssol != NULL);
383  assert(bestcand != NULL);
384  assert(bestcandmayround != NULL);
385  assert(bestcandroundup != NULL);
386 
387  *bestcandmayround = TRUE;
388  bestscore = SCIP_REAL_MAX;
389 
390  /* get best candidate */
391  for( c = 0; c < nnlpcands; ++c )
392  {
393  SCIP_VAR* var;
394 
395  SCIP_Real obj;
396  SCIP_Real objdelta;
397  SCIP_Real frac;
398  SCIP_Real score;
399 
400  int nlocks;
401 
402  SCIP_Bool roundup;
403 
404  var = nlpcands[c];
405 
406  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
407  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
408  continue;
409 
410  frac = nlpcandsfrac[c];
411  obj = SCIPvarGetObj(var);
412  roundup = (obj >= 0.0);
413  objdelta = (roundup ? (1.0-frac)*obj : -frac * obj);
414  assert(objdelta >= 0.0);
415 
416  /* check whether the variable is roundable */
417  *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var));
418  nlocks = SCIPvarGetNLocksDown(var) + SCIPvarGetNLocksUp(var);
419 
420  /* smaller score is better */
421  score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)nlocks+1.0);
422 
423  /* prefer decisions on binary variables */
424  if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
425  score *= 1000.0;
426 
427  /* prefer decisions on cover variables */
428  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
429  score *= 1000;
430 
431  /* check, if candidate is new best candidate */
432  if( score < bestscore )
433  {
434  *bestcand = c;
435  bestscore = score;
436  *bestcandroundup = roundup;
437  }
438  }
439 
440  return SCIP_OKAY;
441 }
442 
443 
444 /** finds best candidate variable w.r.t. locking numbers:
445  * - prefer variables that may not be rounded without destroying LP feasibility:
446  * - of these variables, round variable with least number of locks in corresponding direction
447  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
448  * - round variable with least number of locks in opposite of its feasible rounding direction
449  * - binary variables are prefered
450  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
451  * also be prefered if a correpsonding parameter is set
452  */
453 static
454 SCIP_RETCODE chooseCoefVar(
455  SCIP* scip, /**< original SCIP data structure */
456  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
457  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
458  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
459  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
460  int nnlpcands, /**< number of NLP fractional variables */
461  SCIP_HASHMAP* varincover, /**< hash map for variables */
462  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
463  int* bestcand, /**< pointer to store the index of the best candidate variable */
464  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
465  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
466  )
467 {
468  SCIP_Bool bestcandmayrounddown;
469  SCIP_Bool bestcandmayroundup;
470  int bestnviolrows; /* number of violated rows for best candidate */
471  SCIP_Real bestcandfrac; /* fractionality of best candidate */
472  int c;
473 
474  /* check preconditions */
475  assert(scip != NULL);
476  assert(heurdata != NULL);
477  assert(nlpcands != NULL);
478  assert(nlpcandsfrac != NULL);
479  assert(nlpcandssol != NULL);
480  assert(bestcand != NULL);
481  assert(bestcandmayround != NULL);
482  assert(bestcandroundup != NULL);
483 
484  bestcandmayrounddown = TRUE;
485  bestcandmayroundup = TRUE;
486  bestnviolrows = INT_MAX;
487  bestcandfrac = SCIP_INVALID;
488 
489  /* get best candidate */
490  for( c = 0; c < nnlpcands; ++c )
491  {
492  SCIP_VAR* var;
493 
494  int nlocksdown;
495  int nlocksup;
496  int nviolrows;
497 
498  SCIP_Bool mayrounddown;
499  SCIP_Bool mayroundup;
500  SCIP_Bool roundup;
501  SCIP_Real frac;
502 
503  var = nlpcands[c];
504  mayrounddown = SCIPvarMayRoundDown(var);
505  mayroundup = SCIPvarMayRoundUp(var);
506  frac = nlpcandsfrac[c];
507 
508  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
509  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
510  continue;
511 
512  if( mayrounddown || mayroundup )
513  {
514  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
515  if( bestcandmayrounddown || bestcandmayroundup )
516  {
517  /* choose rounding direction:
518  * - if variable may be rounded in both directions, round corresponding to the fractionality
519  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
520  * the current fractional solution
521  */
522  if( mayrounddown && mayroundup )
523  roundup = (frac > 0.5);
524  else
525  roundup = mayrounddown;
526 
527  if( roundup )
528  {
529  frac = 1.0 - frac;
530  nviolrows = SCIPvarGetNLocksUp(var);
531  }
532  else
533  nviolrows = SCIPvarGetNLocksDown(var);
534 
535  /* penalize too small fractions */
536  if( frac < 0.01 )
537  nviolrows *= 100;
538 
539  /* prefer decisions on binary variables */
540  if( !SCIPvarIsBinary(var) )
541  nviolrows *= 1000;
542 
543  /* prefer decisions on cover variables */
544  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
545  nviolrows *= 1000;
546 
547  /* check, if candidate is new best candidate */
548  assert( (0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var) );
549  if( nviolrows + frac < bestnviolrows + bestcandfrac )
550  {
551  *bestcand = c;
552  bestnviolrows = nviolrows;
553  bestcandfrac = frac;
554  bestcandmayrounddown = mayrounddown;
555  bestcandmayroundup = mayroundup;
556  *bestcandroundup = roundup;
557  }
558  }
559  }
560  else
561  {
562  /* the candidate may not be rounded */
563  nlocksdown = SCIPvarGetNLocksDown(var);
564  nlocksup = SCIPvarGetNLocksUp(var);
565  roundup = (nlocksdown > nlocksup || (nlocksdown == nlocksup && frac > 0.5));
566  if( roundup )
567  {
568  nviolrows = nlocksup;
569  frac = 1.0 - frac;
570  }
571  else
572  nviolrows = nlocksdown;
573 
574  /* penalize too small fractions */
575  if( frac < 0.01 )
576  nviolrows *= 100;
577 
578  /* prefer decisions on binary variables */
579  if( !SCIPvarIsBinary(var) )
580  nviolrows *= 100;
581 
582  /* prefer decisions on cover variables */
583  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
584  nviolrows *= 1000;
585 
586  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
587  assert((0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var));
588  if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
589  {
590  *bestcand = c;
591  bestnviolrows = nviolrows;
592  bestcandfrac = frac;
593  bestcandmayrounddown = FALSE;
594  bestcandmayroundup = FALSE;
595  *bestcandroundup = roundup;
596  }
597  assert(bestcandfrac < SCIP_INVALID);
598  }
599  }
600 
601  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
602 
603  return SCIP_OKAY;
604 }
605 
606 /** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */
607 static
608 void calcPscostQuot(
609  SCIP* scip, /**< SCIP data structure */
610  SCIP_VAR* var, /**< problem variable */
611  SCIP_Real primsol, /**< primal solution of variable */
612  SCIP_Real frac, /**< fractionality of variable */
613  int rounddir, /**< -1: round down, +1: round up, 0: select due to pseudo cost values */
614  SCIP_Real* pscostquot, /**< pointer to store pseudo cost quotient */
615  SCIP_Bool* roundup, /**< pointer to store whether the variable should be rounded up */
616  SCIP_Bool prefvar /**< should this variable be prefered because it is in a minimal cover? */
617  )
618 {
619  SCIP_Real pscostdown;
620  SCIP_Real pscostup;
621 
622  assert(pscostquot != NULL);
623  assert(roundup != NULL);
624  assert(SCIPisEQ(scip, frac, primsol - SCIPfeasFloor(scip, primsol)));
625 
626  /* bound fractions to not prefer variables that are nearly integral */
627  frac = MAX(frac, 0.1);
628  frac = MIN(frac, 0.9);
629 
630  /* get pseudo cost quotient */
631  pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac);
632  pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac);
633  assert(pscostdown >= 0.0 && pscostup >= 0.0);
634 
635  /* choose rounding direction */
636  if( rounddir == -1 )
637  *roundup = FALSE;
638  else if( rounddir == +1 )
639  *roundup = TRUE;
640  else if( primsol < SCIPvarGetRootSol(var) - 0.4 )
641  *roundup = FALSE;
642  else if( primsol > SCIPvarGetRootSol(var) + 0.4 )
643  *roundup = TRUE;
644  else if( frac < 0.3 )
645  *roundup = FALSE;
646  else if( frac > 0.7 )
647  *roundup = TRUE;
648  else if( pscostdown < pscostup )
649  *roundup = FALSE;
650  else
651  *roundup = TRUE;
652 
653  /* calculate pseudo cost quotient */
654  if( *roundup )
655  *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
656  else
657  *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
658 
659  /* prefer decisions on binary variables */
660  if( SCIPvarIsBinary(var) )
661  (*pscostquot) *= 1000.0;
662 
663  /* prefer decisions on cover variables */
664  if( prefvar )
665  (*pscostquot) *= 1000.0;
666 }
667 
668 /** finds best candidate variable w.r.t. pseudo costs:
669  * - prefer variables that may not be rounded without destroying LP feasibility:
670  * - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding
671  * direction
672  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
673  * - round variable in the objective value direction
674  * - binary variables are prefered
675  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
676  * also be prefered if a correpsonding parameter is set
677  */
678 static
679 SCIP_RETCODE choosePscostVar(
680  SCIP* scip, /**< original SCIP data structure */
681  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
682  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
683  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
684  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
685  int nnlpcands, /**< number of NLP fractional variables */
686  SCIP_HASHMAP* varincover, /**< hash map for variables */
687  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
688  int* bestcand, /**< pointer to store the index of the best candidate variable */
689  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
690  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
691  )
692 {
693  SCIP_Bool bestcandmayrounddown;
694  SCIP_Bool bestcandmayroundup;
695  SCIP_Real bestpscostquot;
696  int c;
697 
698  /* check preconditions */
699  assert(scip != NULL);
700  assert(heurdata != NULL);
701  assert(nlpcands != NULL);
702  assert(nlpcandsfrac != NULL);
703  assert(nlpcandssol != NULL);
704  assert(bestcand != NULL);
705  assert(bestcandmayround != NULL);
706  assert(bestcandroundup != NULL);
707 
708  bestcandmayrounddown = TRUE;
709  bestcandmayroundup = TRUE;
710  bestpscostquot = -1.0;
711 
712  for( c = 0; c < nnlpcands; ++c )
713  {
714  SCIP_VAR* var;
715  SCIP_Real primsol;
716 
717  SCIP_Bool mayrounddown;
718  SCIP_Bool mayroundup;
719  SCIP_Bool roundup;
720  SCIP_Bool prefvar;
721  SCIP_Real frac;
722  SCIP_Real pscostquot;
723 
724  var = nlpcands[c];
725  mayrounddown = SCIPvarMayRoundDown(var);
726  mayroundup = SCIPvarMayRoundUp(var);
727  primsol = nlpcandssol[c];
728  frac = nlpcandsfrac[c];
729  prefvar = covercomputed && heurdata->prefercover && SCIPhashmapExists(varincover, var);
730  pscostquot = SCIP_INVALID;
731 
732  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
733  continue;
734 
735  if( mayrounddown || mayroundup )
736  {
737  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
738  if( bestcandmayrounddown || bestcandmayroundup )
739  {
740  /* choose rounding direction:
741  * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
742  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
743  * the current fractional solution
744  */
745  roundup = FALSE;
746  if( mayrounddown && mayroundup )
747  calcPscostQuot(scip, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
748  else if( mayrounddown )
749  calcPscostQuot(scip, var, primsol, frac, +1, &pscostquot, &roundup, prefvar);
750  else
751  calcPscostQuot(scip, var, primsol, frac, -1, &pscostquot, &roundup, prefvar);
752 
753  assert(!SCIPisInfinity(scip,ABS(pscostquot)));
754 
755  /* check, if candidate is new best candidate */
756  if( pscostquot > bestpscostquot )
757  {
758  *bestcand = c;
759  bestpscostquot = pscostquot;
760  bestcandmayrounddown = mayrounddown;
761  bestcandmayroundup = mayroundup;
762  *bestcandroundup = roundup;
763  }
764  }
765  }
766  else
767  {
768  /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
769  calcPscostQuot(scip, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
770  assert(!SCIPisInfinity(scip,ABS(pscostquot)));
771 
772  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
773  if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
774  {
775  *bestcand = c;
776  bestpscostquot = pscostquot;
777  bestcandmayrounddown = FALSE;
778  bestcandmayroundup = FALSE;
779  *bestcandroundup = roundup;
780  }
781  }
782  }
783 
784  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
785 
786  return SCIP_OKAY;
787 }
788 
789 /** finds best candidate variable w.r.t. the incumbent solution:
790  * - prefer variables that may not be rounded without destroying LP feasibility:
791  * - of these variables, round a variable to its value in direction of incumbent solution, and choose the
792  * variable that is closest to its rounded value
793  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
794  * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
795  * - round variable with least increasing objective value
796  * - binary variables are prefered
797  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
798  * also be prefered if a correpsonding parameter is set
799  */
800 static
801 SCIP_RETCODE chooseGuidedVar(
802  SCIP* scip, /**< original SCIP data structure */
803  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
804  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
805  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
806  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
807  int nnlpcands, /**< number of NLP fractional variables */
808  SCIP_SOL* bestsol, /**< incumbent solution */
809  SCIP_HASHMAP* varincover, /**< hash map for variables */
810  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
811  int* bestcand, /**< pointer to store the index of the best candidate variable */
812  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
813  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
814  )
815 {
816  SCIP_Real bestobjgain;
817  SCIP_Real bestfrac;
818  SCIP_Bool bestcandmayrounddown;
819  SCIP_Bool bestcandmayroundup;
820  int c;
821 
822  /* check preconditions */
823  assert(scip != NULL);
824  assert(heurdata != NULL);
825  assert(nlpcands != NULL);
826  assert(nlpcandsfrac != NULL);
827  assert(nlpcandssol != NULL);
828  assert(bestcand != NULL);
829  assert(bestcandmayround != NULL);
830  assert(bestcandroundup != NULL);
831 
832  bestcandmayrounddown = TRUE;
833  bestcandmayroundup = TRUE;
834  bestobjgain = SCIPinfinity(scip);
835  bestfrac = SCIP_INVALID;
836 
837  for( c = 0; c < nnlpcands; ++c )
838  {
839  SCIP_VAR* var;
840  SCIP_Real bestsolval;
841  SCIP_Real solval;
842  SCIP_Real obj;
843  SCIP_Real frac;
844  SCIP_Real objgain;
845 
846  SCIP_Bool mayrounddown;
847  SCIP_Bool mayroundup;
848  SCIP_Bool roundup;
849 
850  var = nlpcands[c];
851  mayrounddown = SCIPvarMayRoundDown(var);
852  mayroundup = SCIPvarMayRoundUp(var);
853  solval = nlpcandssol[c];
854  frac = nlpcandsfrac[c];
855  obj = SCIPvarGetObj(var);
856  bestsolval = SCIPgetSolVal(scip, bestsol, var);
857 
858  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
859  if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) )
860  continue;
861 
862  /* select default rounding direction */
863  roundup = (solval < bestsolval);
864 
865  if( mayrounddown || mayroundup )
866  {
867  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
868  if( bestcandmayrounddown || bestcandmayroundup )
869  {
870  /* choose rounding direction:
871  * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
872  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
873  * the current fractional solution with SCIProundSol()
874  */
875  if( !mayrounddown || !mayroundup )
876  roundup = mayrounddown;
877 
878  if( roundup )
879  {
880  frac = 1.0 - frac;
881  objgain = frac*obj;
882  }
883  else
884  objgain = -frac*obj;
885 
886  /* penalize too small fractions */
887  if( frac < 0.01 )
888  objgain *= 1000.0;
889 
890  /* prefer decisions on binary variables */
891  if( !SCIPvarIsBinary(var) )
892  objgain *= 1000.0;
893 
894  /* prefer decisions on cover variables */
895  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
896  objgain *= 1000.0;
897 
898  /* check, if candidate is new best candidate */
899  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
900  {
901  *bestcand = c;
902  bestobjgain = objgain;
903  bestfrac = frac;
904  bestcandmayrounddown = mayrounddown;
905  bestcandmayroundup = mayroundup;
906  *bestcandroundup = roundup;
907  }
908  }
909  }
910  else
911  {
912  /* the candidate may not be rounded */
913  if( roundup )
914  frac = 1.0 - frac;
915 
916  /* penalize too small fractions */
917  if( frac < 0.01 )
918  frac += 10.0;
919 
920  /* prefer decisions on binary variables */
921  if( !SCIPvarIsBinary(var) )
922  frac *= 1000.0;
923 
924  /* prefer decisions on cover variables */
925  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
926  frac *= 1000.0;
927 
928  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
929  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
930  {
931  *bestcand = c;
932  bestfrac = frac;
933  bestcandmayrounddown = FALSE;
934  bestcandmayroundup = FALSE;
935  *bestcandroundup = roundup;
936  }
937  }
938  }
939 
940  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
941 
942  return SCIP_OKAY;
943 }
944 
945 /** finds best candidate variable w.r.t. both, the LP and the NLP solution:
946  * - choose a variable for which the sum of the distances from the relaxations' solutions to a common
947  * integer value is minimal
948  * - binary variables are prefered
949  * - variables in a minimal cover might be prefered if a corresponding parameter is set
950  */
951 static
952 SCIP_RETCODE chooseDoubleVar(
953  SCIP* scip, /**< original SCIP data structure */
954  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
955  SCIP_VAR** pseudocands, /**< array of non-fixed variables */
956  SCIP_Real* pseudocandsnlpsol, /**< array of NLP solution values */
957  SCIP_Real* pseudocandslpsol, /**< array of LP solution values */
958  int npseudocands, /**< number of NLP fractional variables */
959  SCIP_HASHMAP* varincover, /**< hash map for variables */
960  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
961  int* bestcand, /**< pointer to store the index of the best candidate variable */
962  SCIP_Real* bestboundval, /**< pointer to store the bound, the best candidate should be rounded to */
963  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
964  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
965  )
966 {
967  SCIP_Real bestfrac;
968  int c;
969 
970  /* check preconditions */
971  assert(scip != NULL);
972  assert(heurdata != NULL);
973  assert(pseudocands != NULL);
974  assert(pseudocandsnlpsol != NULL);
975  assert(pseudocandslpsol != NULL);
976  assert(covercomputed == (varincover != NULL));
977  assert(bestcand != NULL);
978  assert(bestcandmayround != NULL);
979  assert(bestcandroundup != NULL);
980 
981  bestfrac = SCIP_INVALID;
982 
983  for( c = 0; c < npseudocands; ++c )
984  {
985  SCIP_VAR* var;
986  SCIP_Bool mayround;
987  SCIP_Bool roundup;
988 
989  SCIP_Real frac;
990  SCIP_Real lpsol;
991  SCIP_Real nlpsol;
992  SCIP_Real lpsolfloor;
993  SCIP_Real nlpsolfloor;
994  SCIP_Real lpsolceil;
995  SCIP_Real nlpsolceil;
996  SCIP_Real boundval;
997  SCIP_Real floorval;
998  SCIP_Real ceilval;
999 
1000  var = pseudocands[c];
1001  lpsol = pseudocandslpsol[c];
1002  nlpsol = pseudocandsnlpsol[c];
1003 
1004  assert(SCIPvarGetUbLocal(var)-SCIPvarGetLbLocal(var) > 0.5);
1005  assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var)));
1006 
1007  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
1008  if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) )
1009  continue;
1010 
1011  mayround = SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var);
1012 
1013  /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */
1014  if( mayround && !(*bestcandmayround) )
1015  continue;
1016 
1017  if( SCIPisFeasEQ(scip, lpsol, nlpsol) && SCIPisFeasIntegral(scip, lpsol))
1018  continue;
1019 
1020  lpsolfloor = SCIPfeasFloor(scip, lpsol);
1021  nlpsolfloor = SCIPfeasFloor(scip, nlpsol);
1022  lpsolceil = SCIPfeasCeil(scip, lpsol);
1023  nlpsolceil = SCIPfeasCeil(scip, nlpsol);
1024  floorval = MIN(lpsolfloor,nlpsolfloor);
1025  ceilval = MAX(lpsolceil,nlpsolceil);
1026  /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the
1027  * new bound. The minima and maxima are necessary since one or both values with be integer
1028  */
1029  if( SCIPvarIsBinary(var) || ceilval-floorval < 1.5 )
1030  {
1031 
1032  frac = 0.33*(lpsol-floorval) + 0.67*(nlpsol-floorval);
1033  if( frac < 0.5 )
1034  {
1035  roundup = FALSE;
1036  boundval = MIN(lpsolfloor,nlpsolfloor);
1037  }
1038  else
1039  {
1040  roundup = TRUE;
1041  frac = 1.0-frac;
1042  boundval = MAX(nlpsolceil,lpsolceil);
1043  }
1044  }
1045  else
1046  {
1047  /* determine new bound in the middle of both relaxations, such that the NLP stays feasible */
1048  SCIP_Real midval;
1049  midval = (nlpsol+lpsol)/2.0;
1050  roundup = nlpsol > lpsol;
1051  frac = ABS(nlpsol-lpsol);
1052 
1053  if( roundup )
1054  boundval = SCIPfeasCeil(scip, midval);
1055  else
1056  boundval = SCIPfeasFloor(scip, midval);
1057 
1058  assert(roundup == SCIPisGT(scip, nlpsol, boundval));
1059  }
1060 
1061  /* penalize too small fractions */
1062  if( frac < 0.01 )
1063  frac += 10.0;
1064 
1065  /* prefer decisions on binary variables */
1066  if( !SCIPvarIsBinary(var) )
1067  frac *= 1000.0;
1068 
1069  /* prefer decisions on cover variables */
1070  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1071  frac *= 1000.0;
1072 
1073  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
1074  if( frac < bestfrac || (*bestcandmayround && !mayround) )
1075  {
1076  *bestcand = c;
1077  bestfrac = frac;
1078  *bestcandmayround = FALSE;
1079  *bestcandroundup = roundup;
1080  *bestboundval = boundval;
1081  }
1082  assert(bestfrac < SCIP_INVALID);
1083  }
1084 
1085  if( *bestcandroundup )
1086  *bestboundval -= 0.5;
1087  else
1088  *bestboundval += 0.5;
1089 
1090  return SCIP_OKAY;
1091 }
1092 
1093 /** creates a new solution for the original problem by copying the solution of the subproblem */
1094 static
1095 SCIP_RETCODE createNewSol(
1096  SCIP* scip, /**< original SCIP data structure */
1097  SCIP* subscip, /**< SCIP structure of the subproblem */
1098  SCIP_HEUR* heur, /**< heuristic structure */
1099  SCIP_HASHMAP* varmap, /**< hash map for variables */
1100  SCIP_SOL* subsol, /**< solution of the subproblem */
1101  SCIP_Bool* success /**< used to store whether new solution was found or not */
1102  )
1103 {
1104  SCIP_VAR** vars; /* the original problem's variables */
1105  SCIP_VAR** subvars;
1106  SCIP_Real* subsolvals; /* solution values of the subproblem */
1107  SCIP_SOL* newsol; /* solution to be created for the original problem */
1108  int nvars; /* the original problem's number of variables */
1109  int i;
1110 
1111  assert(scip != NULL);
1112  assert(subscip != NULL);
1113  assert(subsol != NULL);
1114 
1115  /* get variables' data */
1116  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1117 
1118  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1119  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
1120  */
1121  assert(nvars <= SCIPgetNOrigVars(subscip));
1122 
1123  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1124  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
1125 
1126  for( i = 0; i < nvars; i++ )
1127  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
1128 
1129  /* copy the solution */
1130  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
1131 
1132  /* create new solution for the original problem */
1133  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1134  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1135 
1136  /* try to add new solution to scip and free it immediately */
1137  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, success) );
1138 
1139  SCIPfreeBufferArray(scip, &subvars);
1140  SCIPfreeBufferArray(scip, &subsolvals);
1141 
1142  return SCIP_OKAY;
1143 }
1144 
1145 
1146 /** solves subproblem and passes best feasible solution to original SCIP instance */
1147 static
1148 SCIP_RETCODE solveSubMIP(
1149  SCIP* scip, /**< SCIP data structure of the original problem */
1150  SCIP_HEUR* heur, /**< heuristic data structure */
1151  SCIP_VAR** covervars, /**< variables in the cover, should be fixed locally */
1152  int ncovervars, /**< number of variables in the cover */
1153  SCIP_Bool* success /**< pointer to store whether a solution was found */
1154  )
1155 {
1156  SCIP* subscip;
1157  SCIP_HASHMAP* varmap;
1158  SCIP_SOL** subsols;
1159  SCIP_Real timelimit;
1160  SCIP_Real memorylimit;
1161  SCIP_RETCODE retcode;
1162  int c;
1163  int nsubsols;
1164  SCIP_Bool valid;
1165 
1166  /* create subproblem */
1167  SCIP_CALL( SCIPcreate(&subscip) );
1168 
1169  /* create the variable mapping hash map */
1170  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), SCIPcalcHashtableSize(5 * SCIPgetNVars(scip))) );
1171 
1172  *success = FALSE;
1173 
1174  /* copy original problem to subproblem; do not copy pricers */
1175  SCIP_CALL( SCIPcopy(scip, subscip, varmap, NULL, "undercoversub", FALSE, FALSE, TRUE, &valid) );
1176 
1177  /* assert that cover variables are fixed in source and target SCIP */
1178  for( c = 0; c < ncovervars; c++)
1179  {
1180  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1181  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])),
1182  SCIPvarGetUbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c]))));
1183  }
1184 
1185  /* set parameters for sub-SCIP */
1186 
1187  /* do not abort subproblem on CTRL-C */
1188  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1189 
1190  /* disable output to console */
1191  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1192 
1193  /* check whether there is enough time and memory left */
1194  timelimit = 0.0;
1195  memorylimit = 0.0;
1196  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1197  if( !SCIPisInfinity(scip, timelimit))
1198  timelimit -= SCIPgetSolvingTime(scip);
1199  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1200 
1201  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1202  if( !SCIPisInfinity(scip, memorylimit) )
1203  {
1204  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1205  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1206  }
1207 
1208  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
1209  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1210  goto TERMINATE;
1211 
1212  /* disable statistic timing inside sub SCIP */
1213  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1214 
1215  /* set limits for the subproblem */
1216  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", (SCIP_Longint)100) );
1217  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", (SCIP_Longint)500) );
1218  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1219  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1220 
1221  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
1222  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1223 
1224  /* disable cutting plane separation */
1225  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
1226 
1227  /* disable expensive presolving */
1228  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
1229 
1230  /* use best estimate node selection */
1231  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1232  {
1233  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
1234  }
1235 
1236  /* use inference branching */
1237  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1238  {
1239  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
1240  }
1241 
1242  /* disable conflict analysis */
1243  if( !SCIPisParamFixed(subscip, "conflict/useprop") )
1244  {
1245  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) );
1246  }
1247  if( !SCIPisParamFixed(subscip, "conflict/useinflp") )
1248  {
1249  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useinflp", FALSE) );
1250  }
1251  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
1252  {
1253  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useboundlp", FALSE) );
1254  }
1255  if( !SCIPisParamFixed(subscip, "conflict/usesb") )
1256  {
1257  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) );
1258  }
1259  if( !SCIPisParamFixed(subscip, "conflict/usepseudo") )
1260  {
1261  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) );
1262  }
1263 
1264  if( SCIPgetNSols(scip) > 0 )
1265  {
1266  SCIP_Real upperbound;
1267  SCIP_Real cutoffbound;
1268  SCIP_Real minimprove;
1269 
1270  cutoffbound = SCIPinfinity(scip);
1271  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
1272 
1273  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1274  minimprove = 0.01;
1275 
1276  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
1277  {
1278  cutoffbound = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
1279  }
1280  else
1281  {
1282  if( SCIPgetUpperbound(scip) >= 0 )
1283  cutoffbound = (1 - minimprove)*SCIPgetUpperbound(scip);
1284  else
1285  cutoffbound = (1 + minimprove)*SCIPgetUpperbound(scip);
1286  }
1287  cutoffbound = MIN(upperbound, cutoffbound);
1288  SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
1289  }
1290 
1291 #ifdef SCIP_DEBUG
1292  /* for debugging, enable sub-SCIP output */
1293  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1294  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
1295 #endif
1296 
1297  retcode = SCIPsolve(subscip);
1298 
1299  /* Errors in solving the subproblem should not kill the overall solving process
1300  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1301  */
1302  if( retcode != SCIP_OKAY )
1303  {
1304 #ifndef NDEBUG
1305  SCIP_CALL( retcode );
1306 #endif
1307  SCIPwarningMessage(scip, "Error while solving subproblem in " HEUR_NAME " heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1308  }
1309 
1310  /* check, whether a solution was found;
1311  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1312  */
1313  nsubsols = SCIPgetNSols(subscip);
1314  subsols = SCIPgetSols(subscip);
1315  for( c = 0; c < nsubsols && !(*success); ++c )
1316  {
1317  SCIP_CALL( createNewSol(scip, subscip, heur, varmap, subsols[c], success) );
1318  }
1319 
1320  TERMINATE:
1321  /* free sub-SCIP and hash map */
1322  SCIP_CALL( SCIPfree(&subscip) );
1323  SCIPhashmapFree(&varmap);
1324 
1325  return SCIP_OKAY;
1326 }
1327 
1328 /* ---------------- Callback methods of event handler ---------------- */
1329 
1330 /* exec the event handler
1331  *
1332  * We update the number of variables fixed in the cover
1333  */
1334 static
1335 SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
1336 {
1337  SCIP_EVENTTYPE eventtype;
1338  SCIP_HEURDATA* heurdata;
1339  SCIP_VAR* var;
1340 
1341  SCIP_Real oldbound;
1342  SCIP_Real newbound;
1343  SCIP_Real otherbound;
1344 
1345  assert(eventhdlr != NULL);
1346  assert(eventdata != NULL);
1347  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1348  assert(event != NULL);
1349 
1350  heurdata = (SCIP_HEURDATA*)eventdata;
1351  assert(heurdata != NULL);
1352  assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1353 
1354  oldbound = SCIPeventGetOldbound(event);
1355  newbound = SCIPeventGetNewbound(event);
1356  var = SCIPeventGetVar(event);
1357 
1358  eventtype = SCIPeventGetType(event);
1359  otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var);
1360 
1361  switch( eventtype )
1362  {
1363  case SCIP_EVENTTYPE_LBTIGHTENED:
1364  case SCIP_EVENTTYPE_UBTIGHTENED:
1365  /* if cover variable is now fixed */
1366  if( SCIPisFeasEQ(scip, newbound, otherbound) && !SCIPisFeasEQ(scip, oldbound, otherbound) )
1367  {
1368  assert(!SCIPisEQ(scip, oldbound, otherbound));
1369  ++(heurdata->nfixedcovervars);
1370  }
1371  break;
1372  case SCIP_EVENTTYPE_LBRELAXED:
1373  case SCIP_EVENTTYPE_UBRELAXED:
1374  /* if cover variable is now unfixed */
1375  if( SCIPisFeasEQ(scip, oldbound, otherbound) && !SCIPisFeasEQ(scip, newbound, otherbound) )
1376  {
1377  assert(!SCIPisEQ(scip, newbound, otherbound));
1378  --(heurdata->nfixedcovervars);
1379  }
1380  break;
1381  default:
1382  SCIPerrorMessage("invalid event type.\n");
1383  return SCIP_INVALIDDATA;
1384  }
1385  assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1386 
1387  /* SCIPdebugMessage("changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var),
1388  oldbound, newbound, heurdata->nfixedcovervars); */
1389 
1390  return SCIP_OKAY;
1391 }
1392 
1393 
1394 /*
1395  * Callback methods
1396  */
1397 
1398 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1399 static
1400 SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
1401 { /*lint --e{715}*/
1402  assert(scip != NULL);
1403  assert(heur != NULL);
1404  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1405 
1406  /* call inclusion method of primal heuristic */
1407  SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
1408 
1409  return SCIP_OKAY;
1410 }
1411 
1412 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1413 static
1414 SCIP_DECL_HEURFREE(heurFreeNlpdiving) /*lint --e{715}*/
1415 { /*lint --e{715}*/
1416  SCIP_HEURDATA* heurdata;
1417 
1418  assert(heur != NULL);
1419  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1420  assert(scip != NULL);
1421 
1422  /* free heuristic data */
1423  heurdata = SCIPheurGetData(heur);
1424  assert(heurdata != NULL);
1425  SCIPfreeMemory(scip, &heurdata);
1426  SCIPheurSetData(heur, NULL);
1427 
1428  return SCIP_OKAY;
1429 }
1430 
1431 
1432 /** initialization method of primal heuristic (called after problem was transformed) */
1433 static
1434 SCIP_DECL_HEURINIT(heurInitNlpdiving) /*lint --e{715}*/
1435 { /*lint --e{715}*/
1436  SCIP_HEURDATA* heurdata;
1437 
1438  assert(heur != NULL);
1439  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1440 
1441  /* get heuristic data */
1442  heurdata = SCIPheurGetData(heur);
1443  assert(heurdata != NULL);
1444 
1445  /* create working solution */
1446  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
1447 
1448  /* initialize data */
1449  heurdata->nnlpiterations = 0;
1450  heurdata->nsuccess = 0;
1451  heurdata->nfixedcovervars = 0;
1452  SCIPstatistic(
1453  heurdata->nnlpsolves = 0;
1454  heurdata->nfailcutoff = 0;
1455  heurdata->nfaildepth = 0;
1456  heurdata->nfailnlperror = 0;
1457  );
1458 
1459  return SCIP_OKAY;
1460 }
1461 
1462 
1463 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1464 static
1465 SCIP_DECL_HEUREXIT(heurExitNlpdiving) /*lint --e{715}*/
1466 { /*lint --e{715}*/
1467  SCIP_HEURDATA* heurdata;
1468 
1469  assert(heur != NULL);
1470  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1471 
1472  /* get heuristic data */
1473  heurdata = SCIPheurGetData(heur);
1474  assert(heurdata != NULL);
1475 
1476  /* free working solution */
1477  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
1478 
1479  SCIPstatistic(
1480  if( strstr(SCIPgetProbName(scip), "_covering") == NULL && SCIPheurGetNCalls(heur) > 0 )
1481  {
1482  SCIPstatisticMessage("%-30s %5" SCIP_LONGINT_FORMAT " sols in %5" SCIP_LONGINT_FORMAT " runs, %6.1fs, %7d NLP iters in %5d NLP solves, %5.1f avg., %3d%% success %3d%% cutoff %3d%% depth %3d%% nlperror\n",
1483  SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
1484  heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves),
1485  (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur)
1486  );
1487  }
1488  );
1489 
1490  return SCIP_OKAY;
1491 }
1492 
1493 
1494 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1495 static
1496 SCIP_DECL_HEURINITSOL(heurInitsolNlpdiving)
1497 { /*lint --e{715}*/
1498  SCIP_HEUR* nlpheur;
1499 
1500  if( !SCIPisNLPConstructed(scip) )
1501  return SCIP_OKAY;
1502 
1503  /* find NLP local search heuristic */
1504  nlpheur = SCIPfindHeur(scip, "subnlp");
1505 
1506  /* add global linear constraints to NLP relaxation */
1507  if( nlpheur != NULL )
1508  {
1509  SCIP_CALL( SCIPaddLinearConsToNlpHeurSubNlp(scip, nlpheur, TRUE, TRUE) );
1510  }
1511 
1512  return SCIP_OKAY;
1513 }
1514 
1515 
1516 /** execution method of primal heuristic */
1517 static
1518 SCIP_DECL_HEUREXEC(heurExecNlpdiving)
1519 { /*lint --e{715}*/
1520  SCIP_HEURDATA* heurdata;
1521  SCIP_NLPSOLSTAT nlpsolstat;
1522  SCIP_LPSOLSTAT lpsolstat;
1523  SCIP_SOL* nlpstartsol;
1524  SCIP_SOL* bestsol;
1525  SCIP_VAR** nlpcands;
1526  SCIP_VAR** covervars;
1527  SCIP_Real* nlpcandssol;
1528  SCIP_Real* nlpcandsfrac;
1529  SCIP_Real* pseudocandslpsol;
1530  SCIP_Real* pseudocandsnlpsol;
1531  SCIP_HASHMAP* varincover;
1532  SCIP_Real searchubbound;
1533  SCIP_Real searchavgbound;
1534  SCIP_Real searchbound;
1535  SCIP_Real objval;
1536  SCIP_Real oldobjval;
1537  SCIP_Real fixquot;
1538  SCIP_Real bestboundval;
1539  SCIP_Bool bestcandmayround;
1540  SCIP_Bool bestcandroundup;
1541  SCIP_Bool nlperror;
1542  SCIP_Bool lperror;
1543  SCIP_Bool cutoff;
1544  SCIP_Bool backtracked;
1545  SCIP_Bool solvenlp;
1546  SCIP_Bool covercomputed;
1547  SCIP_Bool solvesubmip;
1548  SCIP_Longint ncalls;
1549  SCIP_Longint nsolsfound;
1550  int avgnnlpiterations;
1551  int maxnnlpiterations;
1552  int npseudocands;
1553  int nlpbranchcands;
1554  int ncovervars;
1555  int nnlpcands;
1556  int startnnlpcands;
1557  int depth;
1558  int maxdepth;
1559  int maxdivedepth;
1560  int divedepth;
1561  int lastnlpsolvedepth;
1562  int nfeasnlps;
1563  int bestcand;
1564  int origiterlim;
1565  int origfastfail;
1566  int c;
1567  int backtrackdepth; /* depth where to go when backtracking */
1568  SCIP_VAR* backtrackvar; /* (first) variable to fix differently in backtracking */
1569  SCIP_Real backtrackvarval; /* (fractional) value of backtrack variable */
1570  SCIP_Bool backtrackroundup; /* whether variable should be rounded up in backtracking */
1571 
1572  backtrackdepth = -1;
1573  backtrackvar = NULL;
1574  backtrackvarval = 0.0;
1575  backtrackroundup = FALSE;
1576  bestsol = NULL;
1577  pseudocandsnlpsol = NULL;
1578  pseudocandslpsol = NULL;
1579  covervars = NULL;
1580 
1581  assert(heur != NULL);
1582  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1583  assert(scip != NULL);
1584  assert(result != NULL);
1585  /* assert(SCIPhasCurrentNodeLP(scip)); */
1586 
1587  *result = SCIP_DIDNOTRUN;
1588 
1589  /* do not call heuristic of node was already detected to be infeasible */
1590  if( nodeinfeasible )
1591  return SCIP_OKAY;
1592 
1593  /* only call heuristic, if an NLP relaxation has been constructed */
1594  if( !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0 )
1595  return SCIP_OKAY;
1596 
1597  /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */
1598  if( SCIPisFeasGE(scip, SCIPgetLocalLowerbound(scip), SCIPgetUpperbound(scip)) )
1599  return SCIP_OKAY;
1600 
1601  /* get heuristic's data */
1602  heurdata = SCIPheurGetData(heur);
1603  assert(heurdata != NULL);
1604 
1605  /* do not call heuristic, if it barely succeded */
1606  if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot )
1607  return SCIP_OKAY;
1608 
1609  *result = SCIP_DELAYED;
1610 
1611  /* don't dive two times at the same node */
1612  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
1613  return SCIP_OKAY;
1614 
1615  *result = SCIP_DIDNOTRUN;
1616 
1617  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
1618  depth = SCIPgetDepth(scip);
1619  maxdepth = SCIPgetMaxDepth(scip);
1620  maxdepth = MAX(maxdepth, 30);
1621  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
1622  return SCIP_OKAY;
1623 
1624  /* calculate the maximal number of NLP iterations until heuristic is aborted
1625  * maximal number is maxnlpiterabs plus a success-depending multiplier of maxnlpiterrel
1626  */
1627  ncalls = SCIPheurGetNCalls(heur);
1628  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
1629  maxnnlpiterations = heurdata->maxnlpiterabs;
1630  maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel);
1631 
1632  /* don't try to dive, if we took too many NLP iterations during diving */
1633  if( heurdata->nnlpiterations >= maxnnlpiterations )
1634  return SCIP_OKAY;
1635 
1636  /* allow at least a bit more than the so far average number of NLP iterations per dive */
1637  avgnnlpiterations = (int)(heurdata->nnlpiterations / MAX(ncalls, 1.0));
1638  maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations);
1639 
1640  /* don't try to dive, if there are no unfixed discrete variables */
1641  SCIP_CALL( SCIPgetPseudoBranchCands(scip, NULL, &npseudocands, NULL) );
1642  if( npseudocands == 0 )
1643  return SCIP_OKAY;
1644 
1645  *result = SCIP_DIDNOTFIND;
1646 
1647 #ifdef SCIP_DEBUG
1648  /* SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_VERBLEVEL, 1) ); */
1649 #endif
1650 
1651  /* set iteration limit */
1652  SCIP_CALL( SCIPgetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, &origiterlim) );
1653  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, maxnnlpiterations - heurdata->nnlpiterations) );
1654 
1655  /* set whether NLP solver should fail fast */
1656  SCIP_CALL( SCIPgetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, &origfastfail) );
1657  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, (int)heurdata->nlpfastfail) );
1658 
1659  /* set starting point to lp solution */
1660  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1661 
1662  /* solve NLP relaxation, if not solved already */
1663  nlpsolstat = SCIPgetNLPSolstat(scip);
1664  if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE )
1665  {
1666  SCIP_NLPSTATISTICS* nlpstatistics;
1667 
1668  SCIP_CALL( SCIPsolveNLP(scip) );
1669  SCIPstatistic( ++heurdata->nnlpsolves );
1670 
1671  /* update iteration count */
1672  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERR )
1673  {
1674  SCIP_CALL( SCIPnlpStatisticsCreate(&nlpstatistics) );
1675  SCIP_CALL( SCIPgetNLPStatistics(scip, nlpstatistics) );
1676  heurdata->nnlpiterations += SCIPnlpStatisticsGetNIterations(nlpstatistics);
1677  SCIPnlpStatisticsFree(&nlpstatistics);
1678  }
1679 
1680  nlpsolstat = SCIPgetNLPSolstat(scip);
1681 
1682  /* give up, if no feasible solution found */
1683  if( nlpsolstat >= SCIP_NLPSOLSTAT_LOCINFEASIBLE )
1684  {
1685  SCIPdebugMessage("initial NLP infeasible or not solvable --> stop\n");
1686 
1687  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERR )
1688  {
1689  SCIPstatistic( heurdata->nfailcutoff++ );
1690  }
1691  else
1692  {
1693  SCIPstatistic( heurdata->nfailnlperror++ );
1694  }
1695 
1696  /* reset changed NLP parameters */
1697  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
1698  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
1699 
1700  return SCIP_OKAY;
1701  }
1702  }
1703 
1704  /* get NLP solution */
1705  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
1706 
1707  /* get fractional variables that should be integral */
1708  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1709  assert(nnlpcands <= npseudocands);
1710 
1711  /* get LP candidates if LP solution is optimal */
1712  lpsolstat = SCIPgetLPSolstat(scip);
1713  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1714  nlpbranchcands = SCIPgetNLPBranchCands(scip);
1715  else
1716  nlpbranchcands = 0;
1717 
1718  /* don't try to dive, if there are no fractional variables */
1719  if( nnlpcands == 0 )
1720  {
1721  SCIP_Bool success;
1722 
1723  /* check, if solution was feasible and good enough */
1724 #ifdef SCIP_DEBUG
1725  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, FALSE, FALSE, TRUE, &success) );
1726 #else
1727  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, &success) );
1728 #endif
1729  if( success )
1730  {
1731  SCIPdebugMessage(" -> solution of first NLP was integral, feasible, and good enough\n");
1732  *result = SCIP_FOUNDSOL;
1733  }
1734 
1735  /* reset changed NLP parameters */
1736  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
1737  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
1738 
1739  return SCIP_OKAY;
1740  }
1741 
1742  nlpstartsol = NULL;
1743  assert(nlpcandsfrac != NULL);
1744  assert(nlpcands != NULL);
1745  assert(nlpcandssol != NULL);
1746 
1747  /* save solution of first NLP, if we may use it later */
1748  if( heurdata->nlpstart != 'n' )
1749  {
1750  SCIP_CALL( SCIPcreateNLPSol(scip, &nlpstartsol, heur) );
1751  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
1752  }
1753 
1754  /* calculate the objective search bound */
1755  if( SCIPgetNSolsFound(scip) == 0 )
1756  {
1757  if( heurdata->maxdiveubquotnosol > 0.0 )
1758  searchubbound = SCIPgetLowerbound(scip)
1759  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1760  else
1761  searchubbound = SCIPinfinity(scip);
1762  if( heurdata->maxdiveavgquotnosol > 0.0 )
1763  searchavgbound = SCIPgetLowerbound(scip)
1764  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1765  else
1766  searchavgbound = SCIPinfinity(scip);
1767  }
1768  else
1769  {
1770  if( heurdata->maxdiveubquot > 0.0 )
1771  searchubbound = SCIPgetLowerbound(scip)
1772  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1773  else
1774  searchubbound = SCIPinfinity(scip);
1775  if( heurdata->maxdiveavgquot > 0.0 )
1776  searchavgbound = SCIPgetLowerbound(scip)
1777  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1778  else
1779  searchavgbound = SCIPinfinity(scip);
1780  }
1781  searchbound = MIN(searchubbound, searchavgbound);
1782  if( SCIPisObjIntegral(scip) )
1783  searchbound = SCIPceil(scip, searchbound);
1784 
1785  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
1786  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1787  maxdivedepth = MIN(maxdivedepth, maxdepth);
1788  maxdivedepth *= 10;
1789 
1790  covercomputed = FALSE;
1791  varincover = NULL;
1792 
1793  /* compute cover, if required */
1794  if( heurdata->prefercover || heurdata->solvesubmip )
1795  {
1796  SCIP_Real timelimit;
1797  SCIP_Real memorylimit;
1798 
1799  /* get limits */
1800  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1801  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1802  if( !SCIPisInfinity(scip, timelimit) )
1803  timelimit -= SCIPgetSolvingTime(scip);
1804 
1805  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1806  if( !SCIPisInfinity(scip, memorylimit) )
1807  {
1808  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1809  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1810  }
1811 
1812  /* compute cover */
1813  ncovervars = -1;
1814  SCIP_CALL( SCIPallocBufferArray(scip, &covervars, SCIPgetNVars(scip)) );
1815  if( memorylimit > 2.0*SCIPgetMemExternEstim(scip)/1048576.0 && timelimit > 0.0 )
1816  {
1817  SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), FALSE, FALSE, FALSE, 'u', &covercomputed) );
1818  }
1819 
1820  if( covercomputed )
1821  {
1822  /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1823  assert(ncovervars >= 0);
1824 
1825  /* create hash map */
1826  SCIP_CALL( SCIPhashmapCreate(&varincover, SCIPblkmem(scip), SCIPcalcHashtableSize(2 * ncovervars)) );
1827 
1828  /* process variables in the cover */
1829  for( c = 0; c < ncovervars; c++ )
1830  {
1831  /* insert variable into hash map */
1832  if( SCIPvarGetType(covervars[c]) < SCIP_VARTYPE_IMPLINT )
1833  {
1834  assert(!SCIPhashmapExists(varincover, covervars[c]));
1835  SCIP_CALL( SCIPhashmapInsert(varincover, covervars[c], (void*) (size_t) (c+1)) );
1836  }
1837 
1838  /* catch bound change events of cover variables */
1839  assert(heurdata->eventhdlr != NULL);
1840  SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1841  (SCIP_EVENTDATA*) heurdata, NULL) );
1842  assert(!SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1843  }
1844  }
1845  }
1846  else
1847  {
1848  covervars = NULL;
1849  ncovervars = 0;
1850  }
1851 
1852  /* start diving */
1853  SCIP_CALL( SCIPstartProbing(scip) );
1854 
1855  /* enables collection of variable statistics during probing */
1856  SCIPenableVarHistory(scip);
1857 
1858  /* get NLP objective value*/
1859  objval = SCIPgetNLPObjval(scip);
1860 
1861  SCIPdebugMessage("(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1862  SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
1863 
1864  /* store a copy of the best solution, if guided diving should be used */
1865  if( heurdata->varselrule == 'g' )
1866  {
1867  /* don't dive, if no feasible solutions exist */
1868  if( SCIPgetNSols(scip) == 0 )
1869  return SCIP_OKAY;
1870 
1871  /* get best solution that should guide the search; if this solution lives in the original variable space,
1872  * we cannot use it since it might violate the global bounds of the current problem
1873  */
1874  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1875  return SCIP_OKAY;
1876 
1877  SCIP_CALL( SCIPcreateSolCopy(scip, &bestsol, SCIPgetBestSol(scip)) );
1878  }
1879 
1880  /* if double diving should be used, create arrays to hold to entire LP and NLP solution */
1881  if( heurdata->varselrule == 'd' )
1882  {
1883  SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandslpsol, npseudocands) );
1884  SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandsnlpsol, npseudocands) );
1885  }
1886 
1887  /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
1888  * - if possible, we dive at least with the depth 10
1889  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
1890  */
1891  nlperror = FALSE;
1892  lperror = FALSE;
1893  cutoff = FALSE;
1894  divedepth = 0;
1895  lastnlpsolvedepth = 0;
1896  backtracked = FALSE; /* whether we are in backtracking */
1897  fixquot = heurdata->fixquot;
1898  nfeasnlps = 1;
1899  startnnlpcands = nnlpcands;
1900  solvesubmip = heurdata->solvesubmip;
1901 
1902  while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0
1903  && (nfeasnlps < heurdata->maxfeasnlps
1904  || nnlpcands <= startnnlpcands - divedepth/2
1905  || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound))
1906  && !SCIPisStopped(scip) )
1907  {
1908  SCIP_VAR* var;
1909  SCIP_Bool updatepscost;
1910 
1911  /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
1912  if( SCIPgetDepth(scip) < SCIPgetDepthLimit(scip) )
1913  {
1914  SCIP_CALL( SCIPnewProbingNode(scip) );
1915  divedepth++;
1916  }
1917  else
1918  break;
1919 
1920  bestcand = -1;
1921  bestcandmayround = TRUE;
1922  bestcandroundup = FALSE;
1923  bestboundval = SCIP_INVALID;
1924  updatepscost = TRUE;
1925  var = NULL;
1926 
1927  /* find best candidate variable */
1928  switch( heurdata->varselrule )
1929  {
1930  case 'c':
1931  SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
1932  &bestcand, &bestcandmayround, &bestcandroundup) );
1933  if( bestcand >= 0 )
1934  {
1935  var = nlpcands[bestcand];
1936  bestboundval = nlpcandssol[bestcand];
1937  }
1938  break;
1939  case 'v':
1940  SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
1941  &bestcand, &bestcandmayround, &bestcandroundup) );
1942  if( bestcand >= 0 )
1943  {
1944  var = nlpcands[bestcand];
1945  bestboundval = nlpcandssol[bestcand];
1946  }
1947  break;
1948  case 'p':
1949  SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
1950  &bestcand, &bestcandmayround, &bestcandroundup) );
1951  if( bestcand >= 0 )
1952  {
1953  var = nlpcands[bestcand];
1954  bestboundval = nlpcandssol[bestcand];
1955  }
1956  break;
1957  case 'g':
1958  SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed,
1959  &bestcand, &bestcandmayround, &bestcandroundup) );
1960  if( bestcand >= 0 )
1961  {
1962  var = nlpcands[bestcand];
1963  bestboundval = nlpcandssol[bestcand];
1964  }
1965  break;
1966  case 'd':
1967  /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */
1968  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1969  {
1970  SCIP_VAR** pseudocands;
1971 
1972  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, NULL) );
1973  assert(backtrackdepth > 0 || nnlpcands <= npseudocands);
1974  assert(SCIPgetNLPBranchCands(scip) <= npseudocands);
1975  SCIP_CALL( SCIPgetSolVals(scip, NULL, npseudocands, pseudocands, pseudocandslpsol) );
1976  SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) );
1977  SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands,
1978  varincover, covercomputed, &bestcand, &bestboundval, &bestcandmayround, &bestcandroundup) );
1979  if( bestcand >= 0 )
1980  var = pseudocands[bestcand];
1981  break;
1982  }
1983  else
1984  updatepscost = FALSE;
1985  /*lint -fallthrough*/
1986  case 'f':
1987  SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
1988  &bestcand, &bestcandmayround, &bestcandroundup) );
1989  if( bestcand >= 0 )
1990  {
1991  var = nlpcands[bestcand];
1992  bestboundval = nlpcandssol[bestcand];
1993  }
1994  break;
1995  default:
1996  SCIPerrorMessage("invalid variable selection rule\n");
1997  return SCIP_INVALIDDATA;
1998  }
1999 
2000  /* if all candidates are roundable, try to round the solution
2001  * if var == NULL (i.e., bestcand == -1), then all solution candidates are outside bounds
2002  * this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance),
2003  * but far enough out to be considered as fractional (within feastol, but using absolute tolerance)
2004  * in this case, we also try our luck with rounding
2005  */
2006  if( (var == NULL || bestcandmayround) && backtrackdepth == -1 )
2007  {
2008  SCIP_Bool success;
2009 
2010  /* create solution from diving NLP and try to round it */
2011  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
2012 
2013  if( success )
2014  {
2015  SCIPdebugMessage("nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2016 
2017  /* try to add solution to SCIP */
2018 #ifdef SCIP_DEBUG
2019  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, FALSE, FALSE, TRUE, &success) );
2020 #else
2021  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, &success) );
2022 #endif
2023 
2024  /* check, if solution was feasible and good enough */
2025  if( success )
2026  {
2027  SCIPdebugMessage(" -> solution was feasible and good enough\n");
2028  *result = SCIP_FOUNDSOL;
2029  }
2030  }
2031  }
2032 
2033  /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */
2034  if( var == NULL )
2035  break;
2036 
2037  do
2038  {
2039  SCIP_Real frac;
2040  frac = SCIP_INVALID;
2041 
2042  if( backtracked && backtrackdepth > 0 )
2043  {
2044  assert(backtrackvar != NULL);
2045 
2046  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2047  * occured or variable was fixed by propagation while backtracking => Abort diving!
2048  */
2049  if( SCIPvarGetLbLocal(backtrackvar) >= SCIPvarGetUbLocal(backtrackvar) - 0.5 )
2050  {
2051  SCIPdebugMessage("Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2052  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2053  cutoff = TRUE;
2054  break;
2055  }
2056  if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) )
2057  {
2058  SCIPdebugMessage("selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2059  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2060  assert(backtracked);
2061  break;
2062  }
2063 
2064  /* round backtrack variable up or down */
2065  if( backtrackroundup )
2066  {
2067  SCIPdebugMessage(" dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2068  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2069  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2070  SCIPfeasCeil(scip, backtrackvarval), SCIPvarGetUbLocal(backtrackvar));
2071  SCIP_CALL( SCIPchgVarLbProbing(scip, backtrackvar, SCIPfeasCeil(scip, backtrackvarval)) );
2072  }
2073  else
2074  {
2075  SCIPdebugMessage(" dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2076  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2077  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2078  SCIPvarGetLbLocal(backtrackvar), SCIPfeasFloor(scip, backtrackvarval));
2079  SCIP_CALL( SCIPchgVarUbProbing(scip, backtrackvar, SCIPfeasFloor(scip, backtrackvarval)) );
2080  }
2081 
2082  /* forget about backtrack variable */
2083  backtrackdepth = -1;
2084 
2085  /* for pseudo cost computation */
2086  bestcandroundup = backtrackroundup;
2087  frac = SCIPfrac(scip, backtrackvarval);
2088  var = backtrackvar;
2089  }
2090  else
2091  {
2092  assert(var != NULL);
2093 
2094  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2095  * occured or variable was fixed by propagation while backtracking => Abort diving!
2096  */
2097  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
2098  {
2099  SCIPdebugMessage("Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2100  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2101  cutoff = TRUE;
2102  break;
2103  }
2104  if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) )
2105  {
2106  SCIPdebugMessage("selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2107  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2108  assert(backtracked);
2109  break;
2110  }
2111 
2112  /* apply rounding of best candidate */
2113  if( bestcandroundup == !backtracked )
2114  {
2115  /* round variable up */
2116  SCIPdebugMessage(" dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2117  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2118  SCIPvarGetName(var), bestcandmayround,
2119  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2120  SCIPfeasCeil(scip, bestboundval), SCIPvarGetUbLocal(var));
2121  SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, bestboundval)) );
2122 
2123  /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2124  if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2125  {
2126  backtrackdepth = divedepth;
2127  backtrackvar = var;
2128  backtrackvarval = bestboundval;
2129  backtrackroundup = FALSE;
2130  }
2131  }
2132  else
2133  {
2134  /* round variable down */
2135  SCIPdebugMessage(" dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2136  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2137  SCIPvarGetName(var), bestcandmayround,
2138  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2139  SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, bestboundval));
2140  SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, bestboundval)) );
2141 
2142  /* remember variable for backtracking, if we have none yet (e.g., we are just after NLP solve) or we are half way to the next NLP solve */
2143  if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2144  {
2145  backtrackdepth = divedepth;
2146  backtrackvar = var;
2147  backtrackvarval = bestboundval;
2148  backtrackroundup = TRUE;
2149  }
2150  }
2151 
2152  /* for pseudo-cost computation */
2153  if( updatepscost && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2154  {
2155  if( heurdata->varselrule == 'd' )
2156  {
2157  assert(pseudocandsnlpsol != NULL);
2158  assert(0 <= bestcand && bestcand < npseudocands);
2159  frac = SCIPfrac(scip, pseudocandsnlpsol[bestcand]);
2160  }
2161  else
2162  frac = nlpcandsfrac[bestcand];
2163  }
2164  }
2165 
2166  /* apply domain propagation */
2167  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2168  if( cutoff )
2169  {
2170  SCIPdebugMessage(" *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip));
2171  }
2172 
2173  /* if all variables in the cover are fixed or there is no fractional variable in the cover,
2174  * then solve a sub-MIP
2175  */
2176  if( !cutoff && solvesubmip && covercomputed &&
2177  (heurdata->nfixedcovervars == ncovervars ||
2178  (heurdata->nfixedcovervars >= (ncovervars+1)/2 && !SCIPhashmapExists(varincover, var))) )
2179  {
2180  int probingdepth;
2181 
2182  solvesubmip = FALSE;
2183  probingdepth = SCIPgetProbingDepth(scip);
2184  assert(probingdepth >= 1);
2185  assert(covervars != NULL);
2186 
2187  if( heurdata->nfixedcovervars != ncovervars )
2188  {
2189  /* fix all remaining cover variables */
2190  for( c = 0; c < ncovervars && !cutoff ; c++ )
2191  {
2192  SCIP_Real lb;
2193  SCIP_Real ub;
2194  lb = SCIPvarGetLbLocal(covervars[c]);
2195  ub = SCIPvarGetUbLocal(covervars[c]);
2196  if( !SCIPisFeasEQ(scip, lb, ub) )
2197  {
2198  SCIP_Real nlpsolval;
2199 
2200  /* adopt lpsolval w.r.t. intermediate bound changes by propagation */
2201  nlpsolval = SCIPvarGetNLPSol(covervars[c]);
2202  nlpsolval = MIN(nlpsolval,ub);
2203  nlpsolval = MAX(nlpsolval,lb);
2204  assert(SCIPvarGetType(covervars[c]) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, nlpsolval));
2205 
2206  /* open a new probing node if this will not exceed the maximal tree depth,
2207  * otherwise fix all the remaining variables at the same probing node
2208  * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff
2209  * we backtrack to the last probing node before we started to fix the covervars (and we do
2210  * not solve the probing LP). thus, it would be less work load in SCIPendProbing
2211  * and SCIPbacktrackProbing.
2212  */
2213  if( SCIPgetDepthLimit(scip) > SCIPgetDepth(scip) )
2214  {
2215  SCIP_CALL( SCIPnewProbingNode(scip) );
2216  }
2217 
2218  /* fix and propagate */
2219  assert(SCIPisLbBetter(scip, nlpsolval, lb, ub) || SCIPisUbBetter(scip, nlpsolval, lb, ub));
2220 
2221  if( SCIPisLbBetter(scip, nlpsolval, lb, ub) )
2222  {
2223  SCIP_CALL( SCIPchgVarLbProbing(scip, covervars[c], nlpsolval) );
2224  }
2225  if( SCIPisUbBetter(scip, nlpsolval, lb, ub) )
2226  {
2227  SCIP_CALL( SCIPchgVarUbProbing(scip, covervars[c], nlpsolval) );
2228  }
2229 
2230  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2231  }
2232  }
2233  }
2234 
2235  /* solve sub-MIP or return to standard diving */
2236  if( cutoff )
2237  {
2238  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2239  }
2240  else
2241  {
2242  SCIP_Bool success;
2243  success = FALSE;
2244 
2245  SCIP_CALL( solveSubMIP(scip, heur, covervars, ncovervars, &success));
2246  if( success )
2247  *result = SCIP_FOUNDSOL;
2248  backtracked = TRUE; /* to avoid backtracking */
2249  nnlpcands = 0; /* to force termination */
2250  cutoff = TRUE;
2251  }
2252  }
2253 
2254  /* resolve the diving LP */
2255  if( !cutoff && !lperror && (heurdata->lp || heurdata->varselrule == 'd')
2256  && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && SCIPisLPSolBasic(scip) )
2257  {
2258  SCIP_CALL( SCIPsolveProbingLP(scip, 100, &lperror, &cutoff) );
2259 
2260  /* get LP solution status, objective value, and fractional variables, that should be integral */
2261  lpsolstat = SCIPgetLPSolstat(scip);
2262  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2263  (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2264 
2265  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2266  {
2267  nlpbranchcands = SCIPgetNLPBranchCands(scip);
2268 
2269  /* get new objective value */
2270  oldobjval = objval;
2271  objval = SCIPgetLPObjval(scip);
2272 
2273  /* update pseudo cost values */
2274  if( updatepscost && SCIPisGT(scip, objval, oldobjval) )
2275  {
2276  assert(frac != SCIP_INVALID); /*lint !e777*/
2277  if( bestcandroundup )
2278  {
2279  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 1.0-frac, objval - oldobjval, 1.0) );
2280  }
2281  else
2282  {
2283  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 0.0-frac, objval - oldobjval, 1.0) );
2284  }
2285  }
2286  }
2287  else
2288  {
2289  nlpbranchcands = 0;
2290  }
2291 
2292  if( cutoff )
2293  {
2294  SCIPdebugMessage(" *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2295  }
2296  }
2297  else
2298  lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2299 
2300  /* check whether we want to solve the NLP, which is the case if
2301  * - we are in backtracking, or
2302  * - we have (actively) fixed/rounded fixquot*nnlpcands variables
2303  * - all fractional variables were rounded/fixed (due to fixing and domain propagation)
2304  */
2305  solvenlp = backtracked;
2306  if( !solvenlp && !cutoff )
2307  {
2308  solvenlp = (lastnlpsolvedepth < divedepth - fixquot * nnlpcands);
2309  if( !solvenlp )
2310  {
2311  /* check if fractional NLP variables are left (some may have been fixed by propagation) */
2312  for( c = 0; c < nnlpcands; ++c )
2313  {
2314  var = nlpcands[c];
2315  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2316  continue;
2317  else
2318  break;
2319  }
2320  if( c == nnlpcands )
2321  solvenlp = TRUE;
2322  }
2323  }
2324 
2325  nlpsolstat = SCIP_NLPSOLSTAT_UNKNOWN;
2326 
2327  /* resolve the diving NLP */
2328  if( !cutoff && solvenlp )
2329  {
2330  SCIP_NLPTERMSTAT termstat;
2331  SCIP_NLPSTATISTICS* nlpstatistics;
2332 
2333  /* set iteration limit, allow at least MINNLPITER many iterations */
2334  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) );
2335 
2336  /* set start solution, if we are in backtracking (previous NLP solve was infeasible) */
2337  if( heurdata->nlpstart != 'n' && backtracked )
2338  {
2339  assert(nlpstartsol != NULL);
2340 
2341  SCIPdebugMessage("setting NLP initial guess\n");
2342 
2343  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, nlpstartsol) );
2344  }
2345 
2346  SCIP_CALL( SCIPsolveNLP(scip) );
2347  SCIPstatistic( ++heurdata->nnlpsolves );
2348 
2349  termstat = SCIPgetNLPTermstat(scip);
2350  if( termstat >= SCIP_NLPTERMSTAT_NUMERR )
2351  {
2352  if( termstat >= SCIP_NLPTERMSTAT_LICERR )
2353  {
2354  SCIPwarningMessage(scip, "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2355  }
2356  nlperror = TRUE;
2357  break;
2358  }
2359 
2360  /* update iteration count */
2361  SCIP_CALL( SCIPnlpStatisticsCreate(&nlpstatistics) );
2362  SCIP_CALL( SCIPgetNLPStatistics(scip, nlpstatistics) );
2363  heurdata->nnlpiterations += SCIPnlpStatisticsGetNIterations(nlpstatistics);
2364  SCIPnlpStatisticsFree(&nlpstatistics);
2365 
2366  /* get NLP solution status, objective value, and fractional variables, that should be integral */
2367  nlpsolstat = SCIPgetNLPSolstat(scip);
2368  cutoff = (nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE);
2369 
2370  if( cutoff )
2371  {
2372  SCIPdebugMessage(" *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2373  }
2374  else
2375  {
2376  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
2377 
2378  /* remember that we have solve NLP on this depth successfully */
2379  lastnlpsolvedepth = divedepth;
2380  /* forget previous backtrack variable, we will never go back to a depth before the current one */
2381  backtrackdepth = -1;
2382  /* store NLP solution for warmstarting, if nlpstart is 'f' */
2383  if( heurdata->nlpstart == 'f' )
2384  {
2385  assert(nlpstartsol != NULL);
2386 
2387  /* copy NLP solution values into nlpstartsol, is there a better way to do this???? */
2388  SCIP_CALL( SCIPlinkNLPSol(scip, nlpstartsol) );
2389  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
2390  }
2391  /* increase counter on number of NLP solves with feasible solution */
2392  ++nfeasnlps;
2393  }
2394  }
2395 
2396  /* perform backtracking if a cutoff was detected */
2397  if( cutoff && !backtracked && heurdata->backtrack )
2398  {
2399  if( backtrackdepth == -1 )
2400  {
2401  /* backtrack one step */
2402  SCIPdebugMessage(" *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2403  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
2404 
2405  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2406  assert(SCIPgetDepthLimit(scip) > SCIPgetDepth(scip));
2407 
2408  SCIP_CALL( SCIPnewProbingNode(scip) );
2409  }
2410  else
2411  {
2412  /* if we have a stored a depth for backtracking, go there */
2413  SCIPdebugMessage(" *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2414  SCIP_CALL( SCIPbacktrackProbing(scip, backtrackdepth-1) );
2415 
2416  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2417  assert(SCIPgetDepthLimit(scip) > SCIPgetDepth(scip));
2418 
2419  SCIP_CALL( SCIPnewProbingNode(scip) );
2420  divedepth = backtrackdepth;
2421 
2422  /* do not update pseudocosts if backtracking by more than one level */
2423  updatepscost = FALSE;
2424 
2425  /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2426  * @todo should we remember the fixquot in heurdata for the next run?
2427  */
2428  fixquot *= 0.5;
2429  }
2430  /* remember that we are backtracking now */
2431  backtracked = TRUE;
2432  }
2433  else
2434  backtracked = FALSE;
2435  }
2436  while( backtracked );
2437 
2438  if( !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2439  {
2440  /* get new fractional variables */
2441  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2442  }
2443  SCIPdebugMessage(" -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2444  }
2445 
2446  /*lint --e{774}*/
2447  SCIPdebugMessage("NLP nlpdiving ABORT due to ");
2448  if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2449  {
2450  SCIPdebugPrintf("NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2451  SCIPstatistic( heurdata->nfailnlperror++ );
2452  }
2453  else if( SCIPisStopped(scip) || cutoff )
2454  {
2455  SCIPdebugPrintf("LIMIT hit - stop: %ud cutoff: %ud \n", SCIPisStopped(scip), cutoff);
2456  SCIPstatistic( heurdata->nfailcutoff++ );
2457  }
2458  else if(! (divedepth < 10
2459  || nnlpcands <= startnnlpcands - divedepth/2
2460  || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2461  {
2462  SCIPdebugPrintf("TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2463  (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2464  (objval >= searchbound));
2465  SCIPstatistic( heurdata->nfaildepth++ );
2466  }
2467  else if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2468  {
2469  SCIPdebugPrintf("SUCCESS\n");
2470  }
2471  else
2472  {
2473  SCIPdebugPrintf("UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2474  }
2475 
2476  /* check if a solution has been found */
2477  if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2478  {
2479  SCIP_Bool success;
2480 
2481  /* create solution from diving NLP */
2482  SCIPdebugMessage("nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2483 
2484  /* try to add solution to SCIP */
2485 #ifdef SCIP_DEBUG
2486  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, FALSE, FALSE, TRUE, &success) );
2487 #else
2488  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, &success) );
2489 #endif
2490 
2491  /* check, if solution was feasible and good enough */
2492  if( success )
2493  {
2494  SCIPdebugMessage(" -> solution was feasible and good enough\n");
2495  *result = SCIP_FOUNDSOL;
2496  }
2497  else
2498  {
2499  SCIPdebugMessage(" -> solution was not accepted\n");
2500  }
2501  }
2502 
2503  /* end diving */
2504  SCIP_CALL( SCIPendProbing(scip) );
2505 
2506  /* free hash map and drop variable bound change events */
2507  if( covercomputed )
2508  {
2509  assert(heurdata->eventhdlr != NULL);
2510  assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2511  assert(varincover != NULL);
2512  assert(covervars != NULL);
2513 
2514  SCIPhashmapFree(&varincover);
2515 
2516  /* drop bound change events of cover variables */
2517  for( c = 0; c < ncovervars; c++ )
2518  {
2519  SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2520  }
2521  }
2522  else
2523  assert(varincover == NULL);
2524 
2525  /* free array of cover variables */
2526  if( heurdata->prefercover || heurdata->solvesubmip )
2527  {
2528  assert(covervars != NULL || !covercomputed);
2529  if( covervars != NULL )
2530  SCIPfreeBufferArray(scip, &covervars);
2531  }
2532  else
2533  assert(covervars == NULL);
2534 
2535  /* free NLP start solution */
2536  if( nlpstartsol != NULL )
2537  {
2538  SCIP_CALL( SCIPfreeSol(scip, &nlpstartsol) );
2539  }
2540 
2541  /* reset changed NLP parameters */
2542  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
2543  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
2544 
2545  /* free copied best solution */
2546  if( heurdata->varselrule == 'g' )
2547  {
2548  assert(bestsol != NULL);
2549  SCIP_CALL( SCIPfreeSol(scip, &bestsol) );
2550  }
2551  else
2552  assert(bestsol == NULL);
2553 
2554  /* free arrays of LP and NLP solution */
2555  if( heurdata->varselrule == 'd' )
2556  {
2557  assert(pseudocandsnlpsol != NULL);
2558  assert(pseudocandsnlpsol != NULL);
2559  SCIPfreeBufferArray(scip, &pseudocandslpsol);
2560  SCIPfreeBufferArray(scip, &pseudocandsnlpsol);
2561  }
2562  else
2563  {
2564  assert(pseudocandsnlpsol == NULL);
2565  assert(pseudocandsnlpsol == NULL);
2566  }
2567 
2568  if( *result == SCIP_FOUNDSOL )
2569  heurdata->nsuccess++;
2570 
2571  SCIPdebugMessage("nlpdiving heuristic finished\n");
2572 
2573  return SCIP_OKAY;
2574 }
2575 
2576 
2577 /*
2578  * heuristic specific interface methods
2579  */
2580 
2581 /** creates the nlpdiving heuristic and includes it in SCIP */
2582 SCIP_RETCODE SCIPincludeHeurNlpdiving(
2583  SCIP* scip /**< SCIP data structure */
2584  )
2585 {
2586  SCIP_HEURDATA* heurdata;
2587  SCIP_HEUR* heur;
2588 
2589  /* create heuristic data */
2590  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
2591 
2592  heur = NULL;
2593  /* include heuristic */
2594  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2595  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecNlpdiving, heurdata) );
2596 
2597  assert(heur != NULL);
2598  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyNlpdiving) );
2599  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeNlpdiving) );
2600  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitNlpdiving) );
2601  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitNlpdiving) );
2602  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolNlpdiving) );
2603 
2604  /* get event handler for bound change events */
2605  heurdata->eventhdlr = NULL;
2606  /* create event handler for bound change events */
2607  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2608  eventExecNlpdiving, NULL) );
2609  if ( heurdata->eventhdlr == NULL )
2610  {
2611  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
2612  return SCIP_PLUGINNOTFOUND;
2613  }
2614 
2615  /* nlpdiving heuristic parameters */
2616  SCIP_CALL( SCIPaddRealParam(scip,
2617  "heuristics/" HEUR_NAME "/minreldepth",
2618  "minimal relative depth to start diving",
2619  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
2620  SCIP_CALL( SCIPaddRealParam(scip,
2621  "heuristics/" HEUR_NAME "/maxreldepth",
2622  "maximal relative depth to start diving",
2623  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
2624  SCIP_CALL( SCIPaddIntParam(scip,
2625  "heuristics/" HEUR_NAME "/maxnlpiterabs",
2626  "minimial absolute number of allowed NLP iterations",
2627  &heurdata->maxnlpiterabs, FALSE, DEFAULT_MAXNLPITERABS, 0, INT_MAX, NULL, NULL) );
2628  SCIP_CALL( SCIPaddIntParam(scip,
2629  "heuristics/" HEUR_NAME "/maxnlpiterrel",
2630  "additional allowed number of NLP iterations relative to successfully found solutions",
2631  &heurdata->maxnlpiterrel, FALSE, DEFAULT_MAXNLPITERREL, 0, INT_MAX, NULL, NULL) );
2632  SCIP_CALL( SCIPaddRealParam(scip,
2633  "heuristics/" HEUR_NAME "/maxdiveubquot",
2634  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2635  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
2636  SCIP_CALL( SCIPaddRealParam(scip,
2637  "heuristics/" HEUR_NAME "/maxdiveavgquot",
2638  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2639  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2640  SCIP_CALL( SCIPaddRealParam(scip,
2641  "heuristics/" HEUR_NAME "/maxdiveubquotnosol",
2642  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
2643  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
2644  SCIP_CALL( SCIPaddRealParam(scip,
2645  "heuristics/" HEUR_NAME "/maxdiveavgquotnosol",
2646  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
2647  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2648  SCIP_CALL( SCIPaddIntParam(scip,
2649  "heuristics/" HEUR_NAME "/maxfeasnlps",
2650  "maximal number of NLPs with feasible solution to solve during one dive",
2651  &heurdata->maxfeasnlps, FALSE, DEFAULT_MAXFEASNLPS, 1, INT_MAX, NULL, NULL) );
2652  SCIP_CALL( SCIPaddBoolParam(scip,
2653  "heuristics/" HEUR_NAME "/backtrack",
2654  "use one level of backtracking if infeasibility is encountered?",
2655  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
2656  SCIP_CALL( SCIPaddBoolParam(scip,
2657  "heuristics/" HEUR_NAME "/lp",
2658  "should the LP relaxation be solved before the NLP relaxation?",
2659  &heurdata->lp, TRUE, DEFAULT_LP, NULL, NULL) );
2660  SCIP_CALL( SCIPaddBoolParam(scip,
2661  "heuristics/" HEUR_NAME "/preferlpfracs",
2662  "prefer variables that are also fractional in LP solution?",
2663  &heurdata->preferlpfracs, TRUE, DEFAULT_PREFERLPFRACS, NULL, NULL) );
2664  SCIP_CALL( SCIPaddRealParam(scip,
2665  "heuristics/" HEUR_NAME "/minsuccquot",
2666  "heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)",
2667  &heurdata->minsuccquot, FALSE, DEFAULT_MINSUCCQUOT, 0.0, 1.0, NULL, NULL) );
2668  SCIP_CALL( SCIPaddRealParam(scip,
2669  "heuristics/" HEUR_NAME "/fixquot",
2670  "percentage of fractional variables that should be fixed before the next NLP solve",
2671  &heurdata->fixquot, FALSE, DEFAULT_FIXQUOT, 0.0, 1.0, NULL, NULL) );
2672  SCIP_CALL( SCIPaddBoolParam(scip,
2673  "heuristics/" HEUR_NAME "/prefercover",
2674  "should variables in a minimal cover be preferred?",
2675  &heurdata->prefercover, FALSE, DEFAULT_PREFERCOVER, NULL, NULL) );
2676  SCIP_CALL( SCIPaddBoolParam(scip,
2677  "heuristics/" HEUR_NAME "/solvesubmip",
2678  "should a sub-MIP be solved if all cover variables are fixed?",
2679  &heurdata->solvesubmip, FALSE, DEFAULT_SOLVESUBMIP, NULL, NULL) );
2680  SCIP_CALL( SCIPaddBoolParam(scip,
2681  "heuristics/" HEUR_NAME "/nlpfastfail",
2682  "should the NLP solver stop early if it converges slow?",
2683  &heurdata->nlpfastfail, FALSE, DEFAULT_NLPFASTFAIL, NULL, NULL) );
2684  SCIP_CALL( SCIPaddCharParam(scip,
2685  "heuristics/" HEUR_NAME "/nlpstart",
2686  "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2687  &heurdata->nlpstart, TRUE, DEFAULT_NLPSTART, "fns", NULL, NULL) );
2688  SCIP_CALL( SCIPaddCharParam(scip,
2689  "heuristics/" HEUR_NAME "/varselrule",
2690  "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
2691  &heurdata->varselrule, FALSE, DEFAULT_VARSELRULE, "fcpgdv", NULL, NULL) );
2692 
2693  return SCIP_OKAY;
2694 }
SCIPsetHeurInitsol
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:7361
HEUR_FREQOFS
#define HEUR_FREQOFS
Definition: heur_nlpdiving.c:38
SCIPunlinkSol
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:34812
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:33158
SCIP_DECL_HEUREXIT
static SCIP_DECL_HEUREXIT(heurExitNlpdiving)
Definition: heur_nlpdiving.c:1469
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41572
SCIPsolveProbingLP
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:32788
SCIPsetNLPIntPar
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip.c:28969
SCIPgetAvgLowerbound
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip.c:38350
createNewSol
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HASHMAP *varmap, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1099
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:10698
HEUR_NAME
#define HEUR_NAME
Definition: heur_nlpdiving.c:33
SCIP_FOUNDSOL
Definition: type_result.h:47
SCIPallocMemory
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
SCIP_NLPTERMSTAT
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:85
heur_nlpdiving.h
NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
DEFAULT_BACKTRACK
#define DEFAULT_BACKTRACK
Definition: heur_nlpdiving.c:67
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
SCIP_DELAYED
Definition: type_result.h:34
SCIP_NLPSOLSTAT_LOCINFEASIBLE
Definition: type_nlpi.h:64
SCIP_NLPPAR_ITLIM
Definition: type_nlpi.h:51
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
DEFAULT_MAXFEASNLPS
#define DEFAULT_MAXFEASNLPS
Definition: heur_nlpdiving.c:65
SCIPheurGetName
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1147
SCIPheurGetNCalls
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1273
SCIPsetHeurCopy
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:7297
SCIPcreateNLPSol
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:34072
SCIPbacktrackProbing
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:32250
SCIPheurGetNSolsFound
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1283
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16623
SCIPvarMayRoundDown
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3259
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1248
HEUR_TIMING
#define HEUR_TIMING
Definition: heur_nlpdiving.c:40
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41920
DEFAULT_NLPSTART
#define DEFAULT_NLPSTART
Definition: heur_nlpdiving.c:72
SCIPenableVarHistory
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:23145
chooseVeclenVar
static SCIP_RETCODE chooseVeclenVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:364
NULL
#define NULL
Definition: lpi_spx.cpp:130
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1125
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:42032
SCIPeventGetVar
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:940
nlpi.h
internal methods for NLPI solver interfaces
DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_MAXDIVEAVGQUOT
Definition: heur_nlpdiving.c:59
DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
Definition: heur_nlpdiving.c:63
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17067
SCIP_Var
Definition: struct_var.h:196
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:34843
chooseFracVar
static SCIP_RETCODE chooseFracVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:212
SCIPincludeHeurBasic
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, unsigned int timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7252
chooseGuidedVar
static SCIP_RETCODE chooseGuidedVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_SOL *bestsol, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:805
heur_undercover.h
Undercover primal heuristic for MINLPs.
SCIPpropagateProbing
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:32552
SCIPfindHeur
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:7393
FALSE
#define FALSE
Definition: def.h:56
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:41009
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2057
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4046
DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_MAXDIVEUBQUOT
Definition: heur_nlpdiving.c:56
SCIPgetNLPTermstat
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition: scip.c:28812
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:10743
SCIPincludeEventhdlrBasic
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:7778
TRUE
#define TRUE
Definition: def.h:55
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPupdateVarPseudocost
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:23184
SCIPstatisticMessage
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIPsolveNLP
SCIP_RETCODE SCIPsolveNLP(SCIP *scip)
Definition: scip.c:28767
SCIPgetNLPSolstat
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip.c:28790
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:266
SCIPtrySolFree
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:36299
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4109
SCIPgetVarPseudocostVal
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip.c:23218
SCIPgetNLPObjval
SCIP_Real SCIPgetNLPObjval(SCIP *scip)
Definition: scip.c:28861
SCIP_HEURDATA
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:42008
DEFAULT_MINRELDEPTH
#define DEFAULT_MINRELDEPTH
Definition: heur_nlpdiving.c:52
SCIPgetCutoffbound
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:38561
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:26439
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:34983
SCIPcomputeCoverUndercover
SCIP_RETCODE SCIPcomputeCoverUndercover(SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
Definition: heur_undercover.c:3486
DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXRELDEPTH
Definition: heur_nlpdiving.c:53
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:16905
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2116
SCIP_LPSOLSTAT
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIP_NLPTERMSTAT_LICERR
Definition: type_nlpi.h:82
DEFAULT_VARSELRULE
#define DEFAULT_VARSELRULE
Definition: heur_nlpdiving.c:73
DEFAULT_SOLVESUBMIP
#define DEFAULT_SOLVESUBMIP
Definition: heur_nlpdiving.c:71
SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:37
SCIP_EVENTTYPE_BOUNDCHANGED
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:99
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:26482
SCIP_NLPTERMSTAT_NUMERR
Definition: type_nlpi.h:79
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:42044
MINNLPITER
#define MINNLPITER
Definition: heur_nlpdiving.c:80
SCIPgetNLPFracVars
SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars)
Definition: scip.c:28910
SCIPisLbBetter
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:42255
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:38393
SCIP_NLPSOLSTAT_UNKNOWN
Definition: type_nlpi.h:67
chooseDoubleVar
static SCIP_RETCODE chooseDoubleVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **pseudocands, SCIP_Real *pseudocandsnlpsol, SCIP_Real *pseudocandslpsol, int npseudocands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Real *bestboundval, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:956
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:35066
SCIP_EVENTTYPE_LBCHANGED
#define SCIP_EVENTTYPE_LBCHANGED
Definition: type_event.h:95
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:35668
SCIP_Sol
Definition: struct_sol.h:50
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3547
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2159
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3573
SCIP_EVENTTYPE_LBRELAXED
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:56
SCIPvarGetRootSol
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12607
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:11138
SCIPcatchVarEvent
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:36622
SCIPeventGetOldbound
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1096
SCIP_HashMap
Definition: struct_misc.h:101
SCIPfreeMemory
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
getNLPFracVars
static SCIP_RETCODE getNLPFracVars(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR ***nlpcands, SCIP_Real **nlpcandssol, SCIP_Real **nlpcandsfrac, int *nnlpcands)
Definition: heur_nlpdiving.c:137
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:38372
SCIPcopy
SCIP_RETCODE SCIPcopy(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip.c:3254
SCIP_NLPSOLSTAT_FEASIBLE
Definition: type_nlpi.h:63
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_NlpStatistics
Definition: struct_nlpi.h:78
SCIPdebugPrintf
#define SCIPdebugPrintf
Definition: pub_message.h:80
SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:54
SCIPgetNLPStatistics
SCIP_RETCODE SCIPgetNLPStatistics(SCIP *scip, SCIP_NLPSTATISTICS *statistics)
Definition: scip.c:28837
SCIPisObjIntegral
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:10310
SCIP_NLPSOLSTAT
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
SCIPcalcHashtableSize
int SCIPcalcHashtableSize(int minsize)
Definition: misc.c:1157
SCIPgetProbingDepth
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:32223
sqrt
SCIPInterval sqrt(const SCIPInterval &x)
Definition: intervalarithext.h:355
SCIPgetMaxDepth
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:38214
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:28407
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41598
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:34002
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:41353
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41907
SCIP_EVENTDATA
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:146
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2075
SCIPgetPseudoBranchCands
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:33464
SCIPsetSeparating
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:4457
choosePscostVar
static SCIP_RETCODE choosePscostVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:683
SCIP_EVENTTYPE_UBRELAXED
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:58
SCIP_OKAY
Definition: type_retcode.h:33
SCIPvarGetNLocksUp
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3204
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:35020
HEUR_PRIORITY
#define HEUR_PRIORITY
Definition: heur_nlpdiving.c:36
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:41637
SCIP_EVENTTYPE_LBTIGHTENED
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:55
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:766
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:35717
DEFAULT_MAXNLPITERREL
#define DEFAULT_MAXNLPITERREL
Definition: heur_nlpdiving.c:55
SCIPaddLinearConsToNlpHeurSubNlp
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2330
EVENTHDLR_NAME
#define EVENTHDLR_NAME
Definition: heur_nlpdiving.c:44
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41946
SCIPgetLastDivenode
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:32067
SCIPgetDepthLimit
int SCIPgetDepthLimit(SCIP *scip)
Definition: scip.c:38190
SCIP_Heur
Definition: struct_heur.h:75
SCIPheurSetData
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1068
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
solveSubMIP
static SCIP_RETCODE solveSubMIP(SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1152
SCIP_DECL_HEUREXEC
static SCIP_DECL_HEUREXEC(heurExecNlpdiving)
Definition: heur_nlpdiving.c:1522
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:38534
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
SCIP_NLPPAR_FASTFAIL
Definition: type_nlpi.h:54
SCIP_EVENTTYPE
unsigned int SCIP_EVENTTYPE
Definition: type_event.h:125
SCIPvarGetNLPSol
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:17444
SCIP_Bool
#define SCIP_Bool
Definition: def.h:53
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
HEUR_MAXDEPTH
#define HEUR_MAXDEPTH
Definition: heur_nlpdiving.c:39
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4001
SCIPretransformObj
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:35198
SCIPisParamFixed
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:3709
SCIPsetSubscipsOff
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:4382
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIPgetLocalLowerbound
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
Definition: scip.c:12191
SCIP_DECL_HEURFREE
static SCIP_DECL_HEURFREE(heurFreeNlpdiving)
Definition: heur_nlpdiving.c:1418
SCIPcreateSolCopy
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip.c:34271
DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXDIVEUBQUOTNOSOL
Definition: heur_nlpdiving.c:62
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:41396
SCIP_DECL_EVENTEXEC
static SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
Definition: heur_nlpdiving.c:1339
SCIPlinkNLPSol
SCIP_RETCODE SCIPlinkNLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:34674
SCIPstartProbing
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:32153
SCIPendProbing
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:32285
SCIPnlpStatisticsFree
void SCIPnlpStatisticsFree(SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:798
SCIP_EVENTTYPE_UBTIGHTENED
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:57
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:4431
SCIPstatistic
#define SCIPstatistic(x)
Definition: pub_message.h:101
SCIPfrac
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:41794
HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP
Definition: heur_nlpdiving.c:41
SCIP_DECL_HEURINIT
static SCIP_DECL_HEURINIT(heurInitNlpdiving)
Definition: heur_nlpdiving.c:1438
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:38140
SCIPsolIsOriginal
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2179
SCIPsetHeurExit
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:7345
SCIPsetHeurInit
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:7329
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:128
SCIPdropVarEvent
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:36668
DEFAULT_PREFERLPFRACS
#define DEFAULT_PREFERLPFRACS
Definition: heur_nlpdiving.c:69
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:14503
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16608
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:41770
SCIPheurGetNBestSolsFound
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1293
SCIPincludeHeurNlpdiving
SCIP_RETCODE SCIPincludeHeurNlpdiving(SCIP *scip)
Definition: heur_nlpdiving.c:2586
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20585
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17057
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:692
chooseCoefVar
static SCIP_RETCODE chooseCoefVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:458
HEUR_DESC
#define HEUR_DESC
Definition: heur_nlpdiving.c:34
SCIPgetNSolsFound
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:38746
DEFAULT_FIXQUOT
#define DEFAULT_FIXQUOT
Definition: heur_nlpdiving.c:66
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:10788
calcPscostQuot
static void calcPscostQuot(SCIP *scip, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup, SCIP_Bool prefvar)
Definition: heur_nlpdiving.c:612
SCIPnlpStatisticsGetNIterations
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:810
SCIPeventhdlrGetName
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIPchgVarUbProbing
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:32352
heur_subnlp.h
NLP local search primal heuristic using sub-SCIPs.
SCIPsetHeurFree
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:7313
SCIPfindBranchrule
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:8436
SCIP_Real
#define SCIP_Real
Definition: def.h:127
SCIPnewProbingNode
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:32190
SCIPnlpStatisticsCreate
SCIP_RETCODE SCIPnlpStatisticsCreate(SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:781
SCIPaddCharParam
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3657
SCIPheurGetTime
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1335
SCIPchgVarLbProbing
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:32318
DEFAULT_PREFERCOVER
#define DEFAULT_PREFERCOVER
Definition: heur_nlpdiving.c:70
MIN
#define MIN(x, y)
Definition: memory.c:67
EVENTHDLR_DESC
#define EVENTHDLR_DESC
Definition: heur_nlpdiving.c:45
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41959
SCIPvarMayRoundUp
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3267
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:147
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:41146
SCIPsetObjlimit
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:10194
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:9941
SCIPsetNLPInitialGuessSol
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:28735
SCIP_Longint
#define SCIP_Longint
Definition: def.h:112
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
SCIPgetNNlpis
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:8685
SCIPeventGetType
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:917
SCIPsetSolVals
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:34885
SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:35
HEUR_FREQ
#define HEUR_FREQ
Definition: heur_nlpdiving.c:37
DEFAULT_MAXNLPITERABS
#define DEFAULT_MAXNLPITERABS
Definition: heur_nlpdiving.c:54
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:3938
SCIPheurGetData
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1058
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:10572
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20597
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:3797
SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:33
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:26847
SCIPhashmapInsert
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2094
SCIPfindNodesel
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8124
SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:53
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPeventGetNewbound
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1120
SCIPgetNLPIntPar
SCIP_RETCODE SCIPgetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int *ival)
Definition: scip.c:28941
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:35767
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:3629
SCIP_DECL_HEURCOPY
static SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
Definition: heur_nlpdiving.c:1404
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:41132
HEUR_DISPCHAR
#define HEUR_DISPCHAR
Definition: heur_nlpdiving.c:35
SCIPvarGetNLocksDown
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3149
SCIPtrySol
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:36217
SCIP_DECL_HEURINITSOL
static SCIP_DECL_HEURINITSOL(heurInitsolNlpdiving)
Definition: heur_nlpdiving.c:1500
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:37372
SCIP_Eventhdlr
Definition: struct_event.h:185
SCIPisUbBetter
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:42270
DEFAULT_MINSUCCQUOT
#define DEFAULT_MINSUCCQUOT
Definition: heur_nlpdiving.c:64
DEFAULT_LP
#define DEFAULT_LP
Definition: heur_nlpdiving.c:68
SCIPfreeSol
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:34607
DEFAULT_NLPFASTFAIL
#define DEFAULT_NLPFASTFAIL
Definition: heur_nlpdiving.c:78
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:41409
SCIProundSol
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:35909
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:56