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