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
135 SCIP_RETCODE getNLPFracVars(
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
210 SCIP_RETCODE chooseFracVar(
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
386 SCIP_RETCODE chooseVeclenVar(
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
480 SCIP_RETCODE chooseCoefVar(
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
745 SCIP_RETCODE choosePscostVar(
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
867 SCIP_RETCODE chooseGuidedVar(
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
1039 SCIP_RETCODE chooseDoubleVar(
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
1190 SCIP_RETCODE createNewSol(
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
1243 SCIP_RETCODE solveSubMIP(
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 */
1307  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
1308 
1309  /* disable expensive presolving */
1310  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
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  {
1425  case SCIP_EVENTTYPE_LBTIGHTENED:
1426  case SCIP_EVENTTYPE_UBTIGHTENED:
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;
1434  case SCIP_EVENTTYPE_LBRELAXED:
1435  case SCIP_EVENTTYPE_UBRELAXED:
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 */
1469  SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
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",
1551  SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
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 
1568  if( !SCIPisNLPConstructed(scip) )
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  {
1577  SCIP_CALL( SCIPaddLinearConsToNlpHeurSubNlp(scip, nlpheur, TRUE, TRUE) );
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 */
1728  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
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 */
1740  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERR )
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 
1755  SCIPstatistic(
1756  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERR )
1757  heurdata->nfailcutoff++;
1758  else
1759  heurdata->nfailnlperror++;
1760  )
1761 
1762  /* reset changed NLP parameters */
1763  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
1764  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
1765 
1766  return SCIP_OKAY;
1767  }
1768  }
1769 
1770  /* get NLP solution */
1771  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
1772 
1773  /* get fractional variables that should be integral */
1774  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1775  assert(nnlpcands <= npseudocands);
1776 
1777  /* get LP candidates if LP solution is optimal */
1778  lpsolstat = SCIPgetLPSolstat(scip);
1779  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1780  nlpbranchcands = SCIPgetNLPBranchCands(scip);
1781  else
1782  nlpbranchcands = 0;
1783 
1784  /* don't try to dive, if there are no fractional variables */
1785  if( nnlpcands == 0 )
1786  {
1787  SCIP_Bool success;
1788 
1789  /* check, if solution was feasible and good enough
1790  *
1791  * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
1792  * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
1793  * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
1794  */
1795 #ifdef SCIP_DEBUG
1796  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
1797 #else
1798  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
1799 #endif
1800  if( success )
1801  {
1802  SCIPdebugMsg(scip, " -> solution of first NLP was integral, feasible, and good enough\n");
1803  *result = SCIP_FOUNDSOL;
1804  }
1805 
1806  /* reset changed NLP parameters */
1807  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
1808  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
1809 
1810  return SCIP_OKAY;
1811  }
1812 
1813  nlpstartsol = NULL;
1814  assert(nlpcandsfrac != NULL);
1815  assert(nlpcands != NULL);
1816  assert(nlpcandssol != NULL);
1817 
1818  /* save solution of first NLP, if we may use it later */
1819  if( heurdata->nlpstart != 'n' )
1820  {
1821  SCIP_CALL( SCIPcreateNLPSol(scip, &nlpstartsol, heur) );
1822  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
1823  }
1824 
1825  /* calculate the objective search bound */
1826  if( SCIPgetNSolsFound(scip) == 0 )
1827  {
1828  if( heurdata->maxdiveubquotnosol > 0.0 )
1829  searchubbound = SCIPgetLowerbound(scip)
1830  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1831  else
1832  searchubbound = SCIPinfinity(scip);
1833  if( heurdata->maxdiveavgquotnosol > 0.0 )
1834  searchavgbound = SCIPgetLowerbound(scip)
1835  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1836  else
1837  searchavgbound = SCIPinfinity(scip);
1838  }
1839  else
1840  {
1841  if( heurdata->maxdiveubquot > 0.0 )
1842  searchubbound = SCIPgetLowerbound(scip)
1843  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1844  else
1845  searchubbound = SCIPinfinity(scip);
1846  if( heurdata->maxdiveavgquot > 0.0 )
1847  searchavgbound = SCIPgetLowerbound(scip)
1848  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1849  else
1850  searchavgbound = SCIPinfinity(scip);
1851  }
1852  searchbound = MIN(searchubbound, searchavgbound);
1853  if( SCIPisObjIntegral(scip) )
1854  searchbound = SCIPceil(scip, searchbound);
1855 
1856  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
1857  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1858  maxdivedepth = MIN(maxdivedepth, maxdepth);
1859  maxdivedepth *= 10;
1860 
1861  covercomputed = FALSE;
1862  varincover = NULL;
1863 
1864  /* compute cover, if required */
1865  if( heurdata->prefercover || heurdata->solvesubmip )
1866  {
1867  SCIP_Real timelimit;
1868  SCIP_Real memorylimit;
1869 
1870  /* get limits */
1871  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1872  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1873  if( !SCIPisInfinity(scip, timelimit) )
1874  timelimit -= SCIPgetSolvingTime(scip);
1875 
1876  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1877  if( !SCIPisInfinity(scip, memorylimit) )
1878  {
1879  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1880  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1881  }
1882 
1883  /* compute cover */
1884  ncovervars = -1;
1885  SCIP_CALL( SCIPallocBufferArray(scip, &covervars, SCIPgetNVars(scip)) );
1886  if( memorylimit > 2.0*SCIPgetMemExternEstim(scip)/1048576.0 && timelimit > 0.0 )
1887  {
1888  SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), FALSE, FALSE, FALSE, 'u', &covercomputed) );
1889  }
1890 
1891  if( covercomputed )
1892  {
1893  /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1894  assert(ncovervars >= 0);
1895 
1896  /* create hash map */
1897  SCIP_CALL( SCIPhashmapCreate(&varincover, SCIPblkmem(scip), ncovervars) );
1898 
1899  /* process variables in the cover */
1900  for( c = 0; c < ncovervars; c++ )
1901  {
1902  /* insert variable into hash map */
1903  if( SCIPvarGetType(covervars[c]) < SCIP_VARTYPE_IMPLINT )
1904  {
1905  assert(!SCIPhashmapExists(varincover, covervars[c]));
1906  SCIP_CALL( SCIPhashmapInsert(varincover, covervars[c], (void*) (size_t) (c+1)) );
1907  }
1908 
1909  /* catch bound change events of cover variables */
1910  assert(heurdata->eventhdlr != NULL);
1911  SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1912  (SCIP_EVENTDATA*) heurdata, NULL) );
1913  assert(!SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1914  }
1915  }
1916  }
1917  else
1918  {
1919  covervars = NULL;
1920  ncovervars = 0;
1921  }
1922 
1923  /* start diving */
1924  SCIP_CALL( SCIPstartProbing(scip) );
1925 
1926  /* enables collection of variable statistics during probing */
1927  SCIPenableVarHistory(scip);
1928 
1929  /* get NLP objective value*/
1930  objval = SCIPgetNLPObjval(scip);
1931 
1932  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1933  SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
1934 
1935  /* store a copy of the best solution, if guided diving should be used */
1936  if( heurdata->varselrule == 'g' )
1937  {
1938  /* don't dive, if no feasible solutions exist */
1939  if( SCIPgetNSols(scip) == 0 )
1940  return SCIP_OKAY;
1941 
1942  /* get best solution that should guide the search; if this solution lives in the original variable space,
1943  * we cannot use it since it might violate the global bounds of the current problem
1944  */
1945  if( SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1946  return SCIP_OKAY;
1947 
1948  SCIP_CALL( SCIPcreateSolCopy(scip, &bestsol, SCIPgetBestSol(scip)) );
1949  }
1950 
1951  /* if double diving should be used, create arrays to hold to entire LP and NLP solution */
1952  if( heurdata->varselrule == 'd' )
1953  {
1954  SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandslpsol, npseudocands) );
1955  SCIP_CALL( SCIPallocBufferArray(scip, &pseudocandsnlpsol, npseudocands) );
1956  }
1957 
1958  /* dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
1959  * - if possible, we dive at least with the depth 10
1960  * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
1961  */
1962  nlperror = FALSE;
1963  lperror = FALSE;
1964  cutoff = FALSE;
1965  divedepth = 0;
1966  lastnlpsolvedepth = 0;
1967  backtracked = FALSE; /* whether we are in backtracking */
1968  fixquot = heurdata->fixquot;
1969  nfeasnlps = 1;
1970  startnnlpcands = nnlpcands;
1971  solvesubmip = heurdata->solvesubmip;
1972 
1973  while( !nlperror && !cutoff && (nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_UNKNOWN) && nnlpcands > 0
1974  && (nfeasnlps < heurdata->maxfeasnlps
1975  || nnlpcands <= startnnlpcands - divedepth/2
1976  || (nfeasnlps < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound))
1977  && !SCIPisStopped(scip) )
1978  {
1979  SCIP_VAR* var;
1980  SCIP_Bool updatepscost;
1981 
1982  /* open a new probing node if this will not exceed the maximal tree depth, otherwise stop here */
1983  if( SCIPgetDepth(scip) < SCIP_MAXTREEDEPTH )
1984  {
1985  SCIP_CALL( SCIPnewProbingNode(scip) );
1986  divedepth++;
1987  }
1988  else
1989  break;
1990 
1991  bestcand = -1;
1992  bestcandmayround = TRUE;
1993  bestcandroundup = FALSE;
1994  bestboundval = SCIP_INVALID;
1995  updatepscost = TRUE;
1996  var = NULL;
1997 
1998  /* find best candidate variable */
1999  switch( heurdata->varselrule )
2000  {
2001  case 'c':
2002  SCIP_CALL( chooseCoefVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2003  &bestcand, &bestcandmayround, &bestcandroundup) );
2004  if( bestcand >= 0 )
2005  {
2006  var = nlpcands[bestcand];
2007  bestboundval = nlpcandssol[bestcand];
2008  }
2009  break;
2010  case 'v':
2011  SCIP_CALL( chooseVeclenVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2012  &bestcand, &bestcandmayround, &bestcandroundup) );
2013  if( bestcand >= 0 )
2014  {
2015  var = nlpcands[bestcand];
2016  bestboundval = nlpcandssol[bestcand];
2017  }
2018  break;
2019  case 'p':
2020  SCIP_CALL( choosePscostVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2021  &bestcand, &bestcandmayround, &bestcandroundup) );
2022  if( bestcand >= 0 )
2023  {
2024  var = nlpcands[bestcand];
2025  bestboundval = nlpcandssol[bestcand];
2026  }
2027  break;
2028  case 'g':
2029  SCIP_CALL( chooseGuidedVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, bestsol, varincover, covercomputed,
2030  &bestcand, &bestcandmayround, &bestcandroundup) );
2031  if( bestcand >= 0 )
2032  {
2033  var = nlpcands[bestcand];
2034  bestboundval = nlpcandssol[bestcand];
2035  }
2036  break;
2037  case 'd':
2038  /* double diving only works if we have both relaxations at hand, otherwise we fall back to fractional diving */
2039  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2040  {
2041  SCIP_VAR** pseudocands;
2042 
2043  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, NULL) );
2044  assert(backtrackdepth > 0 || nnlpcands <= npseudocands);
2045  assert(SCIPgetNLPBranchCands(scip) <= npseudocands);
2046  SCIP_CALL( SCIPgetSolVals(scip, NULL, npseudocands, pseudocands, pseudocandslpsol) );
2047  SCIP_CALL( SCIPgetSolVals(scip, heurdata->sol, npseudocands, pseudocands, pseudocandsnlpsol) );
2048  SCIP_CALL( chooseDoubleVar(scip, heurdata, pseudocands, pseudocandsnlpsol, pseudocandslpsol, npseudocands,
2049  varincover, covercomputed, &bestcand, &bestboundval, &bestcandmayround, &bestcandroundup) );
2050  if( bestcand >= 0 )
2051  var = pseudocands[bestcand];
2052  break;
2053  }
2054  else
2055  updatepscost = FALSE;
2056  /*lint -fallthrough*/
2057  case 'f':
2058  SCIP_CALL( chooseFracVar(scip, heurdata, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, varincover, covercomputed,
2059  &bestcand, &bestcandmayround, &bestcandroundup) );
2060  if( bestcand >= 0 )
2061  {
2062  var = nlpcands[bestcand];
2063  bestboundval = nlpcandssol[bestcand];
2064  }
2065  break;
2066  default:
2067  SCIPerrorMessage("invalid variable selection rule\n");
2068  return SCIP_INVALIDDATA;
2069  }
2070 
2071  /* if all candidates are roundable, try to round the solution
2072  * if var == NULL (i.e., bestcand == -1), then all solution candidates are outside bounds
2073  * this should only happen if they are slightly outside bounds (i.e., still within feastol, relative tolerance),
2074  * but far enough out to be considered as fractional (within feastol, but using absolute tolerance)
2075  * in this case, we also try our luck with rounding
2076  */
2077  if( (var == NULL || bestcandmayround) && backtrackdepth == -1 )
2078  {
2079  SCIP_Bool success;
2080 
2081  /* create solution from diving NLP and try to round it */
2082  SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
2083 
2084  if( success )
2085  {
2086  SCIPdebugMsg(scip, "nlpdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2087 
2088  /* try to add solution to SCIP */
2089 #ifdef SCIP_DEBUG
2090  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, FALSE, TRUE, &success) );
2091 #else
2092  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
2093 #endif
2094 
2095  /* check, if solution was feasible and good enough */
2096  if( success )
2097  {
2098  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
2099  *result = SCIP_FOUNDSOL;
2100  }
2101  }
2102  }
2103 
2104  /* if all variables have been found to be essentially integral (even though there is some numerical doubt, see comment above), then stop */
2105  if( var == NULL )
2106  break;
2107 
2108  do
2109  {
2110  SCIP_Real frac;
2111  frac = SCIP_INVALID;
2112 
2113  if( backtracked && backtrackdepth > 0 )
2114  {
2115  assert(backtrackvar != NULL);
2116 
2117  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2118  * occured or variable was fixed by propagation while backtracking => Abort diving!
2119  */
2120  if( SCIPvarGetLbLocal(backtrackvar) >= SCIPvarGetUbLocal(backtrackvar) - 0.5 )
2121  {
2122  SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2123  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2124  cutoff = TRUE;
2125  break;
2126  }
2127  if( SCIPisFeasLT(scip, backtrackvarval, SCIPvarGetLbLocal(backtrackvar)) || SCIPisFeasGT(scip, backtrackvarval, SCIPvarGetUbLocal(backtrackvar)) )
2128  {
2129  SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2130  SCIPvarGetName(backtrackvar), SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar), backtrackvarval);
2131  assert(backtracked);
2132  break;
2133  }
2134 
2135  /* round backtrack variable up or down */
2136  if( backtrackroundup )
2137  {
2138  SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2139  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2140  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2141  SCIPfeasCeil(scip, backtrackvarval), SCIPvarGetUbLocal(backtrackvar));
2142  SCIP_CALL( SCIPchgVarLbProbing(scip, backtrackvar, SCIPfeasCeil(scip, backtrackvarval)) );
2143  }
2144  else
2145  {
2146  SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2147  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2148  SCIPvarGetName(backtrackvar), backtrackvarval, SCIPvarGetLbLocal(backtrackvar), SCIPvarGetUbLocal(backtrackvar),
2149  SCIPvarGetLbLocal(backtrackvar), SCIPfeasFloor(scip, backtrackvarval));
2150  SCIP_CALL( SCIPchgVarUbProbing(scip, backtrackvar, SCIPfeasFloor(scip, backtrackvarval)) );
2151  }
2152 
2153  /* forget about backtrack variable */
2154  backtrackdepth = -1;
2155 
2156  /* for pseudo cost computation */
2157  bestcandroundup = backtrackroundup;
2158  frac = SCIPfrac(scip, backtrackvarval);
2159  var = backtrackvar;
2160  }
2161  else
2162  {
2163  assert(var != NULL);
2164 
2165  /* if the variable is already fixed or if the solution value is outside the domain, numerical troubles may have
2166  * occured or variable was fixed by propagation while backtracking => Abort diving!
2167  */
2168  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
2169  {
2170  SCIPdebugMsg(scip, "Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
2171  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2172  cutoff = TRUE;
2173  break;
2174  }
2175  if( SCIPisFeasLT(scip, bestboundval, SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, bestboundval, SCIPvarGetUbLocal(var)) )
2176  {
2177  SCIPdebugMsg(scip, "selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
2178  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bestboundval);
2179  assert(backtracked);
2180  break;
2181  }
2182 
2183  /* apply rounding of best candidate */
2184  if( bestcandroundup == !backtracked )
2185  {
2186  /* round variable up */
2187  SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2188  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2189  SCIPvarGetName(var), bestcandmayround,
2190  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2191  SCIPfeasCeil(scip, bestboundval), SCIPvarGetUbLocal(var));
2192  SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, bestboundval)) );
2193 
2194  /* 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 */
2195  if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2196  {
2197  backtrackdepth = divedepth;
2198  backtrackvar = var;
2199  backtrackvarval = bestboundval;
2200  backtrackroundup = FALSE;
2201  }
2202  }
2203  else
2204  {
2205  /* round variable down */
2206  SCIPdebugMsg(scip, " dive %d/%d, NLP iter %d/%d: var <%s>, round=%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
2207  divedepth, maxdivedepth, heurdata->nnlpiterations, maxnnlpiterations,
2208  SCIPvarGetName(var), bestcandmayround,
2209  bestboundval, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
2210  SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, bestboundval));
2211  SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, bestboundval)) );
2212 
2213  /* 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 */
2214  if( backtrackdepth == -1 || (divedepth - lastnlpsolvedepth == (int)(MIN(fixquot * nnlpcands, nlpbranchcands)/2.0)) )
2215  {
2216  backtrackdepth = divedepth;
2217  backtrackvar = var;
2218  backtrackvarval = bestboundval;
2219  backtrackroundup = TRUE;
2220  }
2221  }
2222 
2223  /* for pseudo-cost computation */
2224  if( updatepscost && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2225  {
2226  if( heurdata->varselrule == 'd' )
2227  {
2228  assert(pseudocandsnlpsol != NULL);
2229  assert(0 <= bestcand && bestcand < npseudocands);
2230  frac = SCIPfrac(scip, pseudocandsnlpsol[bestcand]);
2231  }
2232  else
2233  frac = nlpcandsfrac[bestcand];
2234  }
2235  }
2236 
2237  /* apply domain propagation */
2238  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2239  if( cutoff )
2240  {
2241  SCIPdebugMsg(scip, " *** cutoff detected in propagation at level %d\n", SCIPgetProbingDepth(scip));
2242  }
2243 
2244  /* if all variables in the cover are fixed or there is no fractional variable in the cover,
2245  * then solve a sub-MIP
2246  */
2247  if( !cutoff && solvesubmip && covercomputed &&
2248  (heurdata->nfixedcovervars == ncovervars ||
2249  (heurdata->nfixedcovervars >= (ncovervars+1)/2 && !SCIPhashmapExists(varincover, var))) )
2250  {
2251  int probingdepth;
2252 
2253  solvesubmip = FALSE;
2254  probingdepth = SCIPgetProbingDepth(scip);
2255  assert(probingdepth >= 1);
2256  assert(covervars != NULL);
2257 
2258  if( heurdata->nfixedcovervars != ncovervars )
2259  {
2260  /* fix all remaining cover variables */
2261  for( c = 0; c < ncovervars && !cutoff ; c++ )
2262  {
2263  SCIP_Real lb;
2264  SCIP_Real ub;
2265  lb = SCIPvarGetLbLocal(covervars[c]);
2266  ub = SCIPvarGetUbLocal(covervars[c]);
2267  if( !SCIPisFeasEQ(scip, lb, ub) )
2268  {
2269  SCIP_Real nlpsolval;
2270 
2271  /* adopt lpsolval w.r.t. intermediate bound changes by propagation */
2272  nlpsolval = SCIPvarGetNLPSol(covervars[c]);
2273  nlpsolval = MIN(nlpsolval,ub);
2274  nlpsolval = MAX(nlpsolval,lb);
2275  assert(SCIPvarGetType(covervars[c]) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, nlpsolval));
2276 
2277  /* open a new probing node if this will not exceed the maximal tree depth,
2278  * otherwise fix all the remaining variables at the same probing node
2279  * @todo do we need a new probing node for each fixing? if one of these fixings leads to a cutoff
2280  * we backtrack to the last probing node before we started to fix the covervars (and we do
2281  * not solve the probing LP). thus, it would be less work load in SCIPendProbing
2282  * and SCIPbacktrackProbing.
2283  */
2284  if( SCIP_MAXTREEDEPTH > SCIPgetDepth(scip) )
2285  {
2286  SCIP_CALL( SCIPnewProbingNode(scip) );
2287  }
2288 
2289  /* fix and propagate */
2290  assert(SCIPisLbBetter(scip, nlpsolval, lb, ub) || SCIPisUbBetter(scip, nlpsolval, lb, ub));
2291 
2292  if( SCIPisLbBetter(scip, nlpsolval, lb, ub) )
2293  {
2294  SCIP_CALL( SCIPchgVarLbProbing(scip, covervars[c], nlpsolval) );
2295  }
2296  if( SCIPisUbBetter(scip, nlpsolval, lb, ub) )
2297  {
2298  SCIP_CALL( SCIPchgVarUbProbing(scip, covervars[c], nlpsolval) );
2299  }
2300 
2301  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2302  }
2303  }
2304  }
2305 
2306  /* solve sub-MIP or return to standard diving */
2307  if( cutoff )
2308  {
2309  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2310  }
2311  else
2312  {
2313  SCIP_Bool success;
2314  success = FALSE;
2315 
2316  SCIP_CALL( solveSubMIP(scip, heur, covervars, ncovervars, &success));
2317  if( success )
2318  *result = SCIP_FOUNDSOL;
2319  backtracked = TRUE; /* to avoid backtracking */
2320  nnlpcands = 0; /* to force termination */
2321  cutoff = TRUE;
2322  }
2323  }
2324 
2325  /* resolve the diving LP */
2326  if( !cutoff && !lperror && (heurdata->lp || heurdata->varselrule == 'd')
2327  && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && SCIPisLPSolBasic(scip) )
2328  {
2329  SCIP_CALL( SCIPsolveProbingLP(scip, 100, &lperror, &cutoff) );
2330 
2331  /* get LP solution status, objective value, and fractional variables, that should be integral */
2332  lpsolstat = SCIPgetLPSolstat(scip);
2333  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2334  (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2335 
2336  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2337  {
2338  nlpbranchcands = SCIPgetNLPBranchCands(scip);
2339 
2340  /* get new objective value */
2341  oldobjval = objval;
2342  objval = SCIPgetLPObjval(scip);
2343 
2344  /* update pseudo cost values */
2345  if( updatepscost && SCIPisGT(scip, objval, oldobjval) )
2346  {
2347  assert(frac != SCIP_INVALID); /*lint !e777*/
2348  if( bestcandroundup )
2349  {
2350  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 1.0-frac, objval - oldobjval, 1.0) );
2351  }
2352  else
2353  {
2354  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 0.0-frac, objval - oldobjval, 1.0) );
2355  }
2356  }
2357  }
2358  else
2359  {
2360  nlpbranchcands = 0;
2361  }
2362 
2363  if( cutoff )
2364  {
2365  SCIPdebugMsg(scip, " *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2366  }
2367  }
2368  else
2369  lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2370 
2371  /* check whether we want to solve the NLP, which is the case if
2372  * - we are in backtracking, or
2373  * - we have (actively) fixed/rounded fixquot*nnlpcands variables
2374  * - all fractional variables were rounded/fixed (due to fixing and domain propagation)
2375  */
2376  solvenlp = backtracked;
2377  if( !solvenlp && !cutoff )
2378  {
2379  solvenlp = (lastnlpsolvedepth < divedepth - fixquot * nnlpcands);
2380  if( !solvenlp )
2381  {
2382  /* check if fractional NLP variables are left (some may have been fixed by propagation) */
2383  for( c = 0; c < nnlpcands; ++c )
2384  {
2385  var = nlpcands[c];
2386  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2387  continue;
2388  else
2389  break;
2390  }
2391  if( c == nnlpcands )
2392  solvenlp = TRUE;
2393  }
2394  }
2395 
2396  nlpsolstat = SCIP_NLPSOLSTAT_UNKNOWN;
2397 
2398  /* resolve the diving NLP */
2399  if( !cutoff && solvenlp )
2400  {
2401  SCIP_NLPTERMSTAT termstat;
2402  SCIP_NLPSTATISTICS* nlpstatistics;
2403 
2404  /* set iteration limit, allow at least MINNLPITER many iterations */
2405  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) );
2406 
2407  /* set start solution, if we are in backtracking (previous NLP solve was infeasible) */
2408  if( heurdata->nlpstart != 'n' && backtracked )
2409  {
2410  assert(nlpstartsol != NULL);
2411 
2412  SCIPdebugMsg(scip, "setting NLP initial guess\n");
2413 
2414  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, nlpstartsol) );
2415  }
2416 
2417  SCIP_CALL( SCIPsolveNLP(scip) );
2418  SCIPstatistic( ++heurdata->nnlpsolves );
2419 
2420  termstat = SCIPgetNLPTermstat(scip);
2421  if( termstat >= SCIP_NLPTERMSTAT_NUMERR )
2422  {
2423  if( termstat >= SCIP_NLPTERMSTAT_LICERR )
2424  {
2425  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL,
2426  "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2427  }
2428  nlperror = TRUE;
2429  break;
2430  }
2431 
2432  /* update iteration count */
2433  SCIP_CALL( SCIPnlpStatisticsCreate(&nlpstatistics) );
2434  SCIP_CALL( SCIPgetNLPStatistics(scip, nlpstatistics) );
2435  heurdata->nnlpiterations += SCIPnlpStatisticsGetNIterations(nlpstatistics);
2436  SCIPnlpStatisticsFree(&nlpstatistics);
2437 
2438  /* get NLP solution status, objective value, and fractional variables, that should be integral */
2439  nlpsolstat = SCIPgetNLPSolstat(scip);
2440  cutoff = (nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE);
2441 
2442  if( cutoff )
2443  {
2444  SCIPdebugMsg(scip, " *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2445  }
2446  else
2447  {
2448  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
2449 
2450  /* remember that we have solve NLP on this depth successfully */
2451  lastnlpsolvedepth = divedepth;
2452  /* forget previous backtrack variable, we will never go back to a depth before the current one */
2453  backtrackdepth = -1;
2454  /* store NLP solution for warmstarting, if nlpstart is 'f' */
2455  if( heurdata->nlpstart == 'f' )
2456  {
2457  assert(nlpstartsol != NULL);
2458 
2459  /* copy NLP solution values into nlpstartsol, is there a better way to do this???? */
2460  SCIP_CALL( SCIPlinkNLPSol(scip, nlpstartsol) );
2461  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
2462  }
2463  /* increase counter on number of NLP solves with feasible solution */
2464  ++nfeasnlps;
2465  }
2466  }
2467 
2468  /* perform backtracking if a cutoff was detected */
2469  if( cutoff && !backtracked && heurdata->backtrack )
2470  {
2471  if( backtrackdepth == -1 )
2472  {
2473  /* backtrack one step */
2474  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2475  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
2476 
2477  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2478  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2479 
2480  SCIP_CALL( SCIPnewProbingNode(scip) );
2481  }
2482  else
2483  {
2484  /* if we have a stored a depth for backtracking, go there */
2485  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2486  SCIP_CALL( SCIPbacktrackProbing(scip, backtrackdepth-1) );
2487 
2488  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2489  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2490 
2491  SCIP_CALL( SCIPnewProbingNode(scip) );
2492  divedepth = backtrackdepth;
2493 
2494  /* do not update pseudocosts if backtracking by more than one level */
2495  updatepscost = FALSE;
2496 
2497  /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2498  * @todo should we remember the fixquot in heurdata for the next run?
2499  */
2500  fixquot *= 0.5;
2501  }
2502  /* remember that we are backtracking now */
2503  backtracked = TRUE;
2504  }
2505  else
2506  backtracked = FALSE;
2507  }
2508  while( backtracked );
2509 
2510  if( !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2511  {
2512  /* get new fractional variables */
2513  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2514  }
2515  SCIPdebugMsg(scip, " -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2516  }
2517 
2518  /*lint --e{774}*/
2519  SCIPdebugMsg(scip, "NLP nlpdiving ABORT due to ");
2520  if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2521  {
2522  SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2523  SCIPstatistic( heurdata->nfailnlperror++ );
2524  }
2525  else if( SCIPisStopped(scip) || cutoff )
2526  {
2527  SCIPdebugMsgPrint(scip, "LIMIT hit - stop: %ud cutoff: %ud \n", SCIPisStopped(scip), cutoff);
2528  SCIPstatistic( heurdata->nfailcutoff++ );
2529  }
2530  else if(! (divedepth < 10
2531  || nnlpcands <= startnnlpcands - divedepth/2
2532  || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2533  {
2534  SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2535  (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2536  (objval >= searchbound));
2537  SCIPstatistic( heurdata->nfaildepth++ );
2538  }
2539  else if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2540  {
2541  SCIPdebugMsgPrint(scip, "SUCCESS\n");
2542  }
2543  else
2544  {
2545  SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2546  }
2547 
2548  /* check if a solution has been found */
2549  if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2550  {
2551  SCIP_Bool success;
2552 
2553  /* create solution from diving NLP */
2554  SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2555 
2556  /* try to add solution to SCIP
2557  *
2558  * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
2559  * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
2560  * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
2561  */
2562 #ifdef SCIP_DEBUG
2563  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
2564 #else
2565  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
2566 #endif
2567 
2568  /* check, if solution was feasible and good enough */
2569  if( success )
2570  {
2571  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
2572  *result = SCIP_FOUNDSOL;
2573  }
2574  else
2575  {
2576  SCIPdebugMsg(scip, " -> solution was not accepted\n");
2577  }
2578  }
2579 
2580  /* end diving */
2581  SCIP_CALL( SCIPendProbing(scip) );
2582 
2583  /* free hash map and drop variable bound change events */
2584  if( covercomputed )
2585  {
2586  assert(heurdata->eventhdlr != NULL);
2587  assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2588  assert(varincover != NULL);
2589  assert(covervars != NULL);
2590 
2591  SCIPhashmapFree(&varincover);
2592 
2593  /* drop bound change events of cover variables */
2594  for( c = 0; c < ncovervars; c++ )
2595  {
2596  SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2597  }
2598  }
2599  else
2600  assert(varincover == NULL);
2601 
2602  /* free array of cover variables */
2603  if( heurdata->prefercover || heurdata->solvesubmip )
2604  {
2605  assert(covervars != NULL || !covercomputed);
2606  if( covervars != NULL )
2607  SCIPfreeBufferArray(scip, &covervars);
2608  }
2609  else
2610  assert(covervars == NULL);
2611 
2612  /* free NLP start solution */
2613  if( nlpstartsol != NULL )
2614  {
2615  SCIP_CALL( SCIPfreeSol(scip, &nlpstartsol) );
2616  }
2617 
2618  /* reset changed NLP parameters */
2619  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_ITLIM, origiterlim) );
2620  SCIP_CALL( SCIPsetNLPIntPar(scip, SCIP_NLPPAR_FASTFAIL, origfastfail) );
2621 
2622  /* free copied best solution */
2623  if( heurdata->varselrule == 'g' )
2624  {
2625  assert(bestsol != NULL);
2626  SCIP_CALL( SCIPfreeSol(scip, &bestsol) );
2627  }
2628  else
2629  assert(bestsol == NULL);
2630 
2631  /* free arrays of LP and NLP solution */
2632  if( heurdata->varselrule == 'd' )
2633  {
2634  assert(pseudocandsnlpsol != NULL);
2635  assert(pseudocandsnlpsol != NULL);
2636  SCIPfreeBufferArray(scip, &pseudocandslpsol);
2637  SCIPfreeBufferArray(scip, &pseudocandsnlpsol);
2638  }
2639  else
2640  {
2641  assert(pseudocandsnlpsol == NULL);
2642  assert(pseudocandsnlpsol == NULL);
2643  }
2644 
2645  if( *result == SCIP_FOUNDSOL )
2646  heurdata->nsuccess++;
2647 
2648  SCIPdebugMsg(scip, "nlpdiving heuristic finished\n");
2649 
2650  return SCIP_OKAY;
2651 }
2652 
2653 
2654 /*
2655  * heuristic specific interface methods
2656  */
2657 
2658 /** creates the nlpdiving heuristic and includes it in SCIP */
2659 SCIP_RETCODE SCIPincludeHeurNlpdiving(
2660  SCIP* scip /**< SCIP data structure */
2661  )
2662 {
2663  SCIP_HEURDATA* heurdata;
2664  SCIP_HEUR* heur = NULL;
2665 
2666  /* create heuristic data */
2667  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2668 
2669  /* include heuristic */
2670  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2671  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecNlpdiving, heurdata) );
2672 
2673  assert(heur != NULL);
2674  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyNlpdiving) );
2675  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeNlpdiving) );
2676  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitNlpdiving) );
2677  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitNlpdiving) );
2678  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolNlpdiving) );
2679 
2680  /* get event handler for bound change events */
2681  heurdata->eventhdlr = NULL;
2682  /* create event handler for bound change events */
2683  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2684  eventExecNlpdiving, NULL) );
2685  if ( heurdata->eventhdlr == NULL )
2686  {
2687  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
2688  return SCIP_PLUGINNOTFOUND;
2689  }
2690 
2691  /* nlpdiving heuristic parameters */
2692  SCIP_CALL( SCIPaddRealParam(scip,
2693  "heuristics/" HEUR_NAME "/minreldepth",
2694  "minimal relative depth to start diving",
2695  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
2696  SCIP_CALL( SCIPaddRealParam(scip,
2697  "heuristics/" HEUR_NAME "/maxreldepth",
2698  "maximal relative depth to start diving",
2699  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
2700  SCIP_CALL( SCIPaddIntParam(scip,
2701  "heuristics/" HEUR_NAME "/maxnlpiterabs",
2702  "minimial absolute number of allowed NLP iterations",
2703  &heurdata->maxnlpiterabs, FALSE, DEFAULT_MAXNLPITERABS, 0, INT_MAX, NULL, NULL) );
2704  SCIP_CALL( SCIPaddIntParam(scip,
2705  "heuristics/" HEUR_NAME "/maxnlpiterrel",
2706  "additional allowed number of NLP iterations relative to successfully found solutions",
2707  &heurdata->maxnlpiterrel, FALSE, DEFAULT_MAXNLPITERREL, 0, INT_MAX, NULL, NULL) );
2708  SCIP_CALL( SCIPaddRealParam(scip,
2709  "heuristics/" HEUR_NAME "/maxdiveubquot",
2710  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2711  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
2712  SCIP_CALL( SCIPaddRealParam(scip,
2713  "heuristics/" HEUR_NAME "/maxdiveavgquot",
2714  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2715  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2716  SCIP_CALL( SCIPaddRealParam(scip,
2717  "heuristics/" HEUR_NAME "/maxdiveubquotnosol",
2718  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
2719  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
2720  SCIP_CALL( SCIPaddRealParam(scip,
2721  "heuristics/" HEUR_NAME "/maxdiveavgquotnosol",
2722  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
2723  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2724  SCIP_CALL( SCIPaddIntParam(scip,
2725  "heuristics/" HEUR_NAME "/maxfeasnlps",
2726  "maximal number of NLPs with feasible solution to solve during one dive",
2727  &heurdata->maxfeasnlps, FALSE, DEFAULT_MAXFEASNLPS, 1, INT_MAX, NULL, NULL) );
2728  SCIP_CALL( SCIPaddBoolParam(scip,
2729  "heuristics/" HEUR_NAME "/backtrack",
2730  "use one level of backtracking if infeasibility is encountered?",
2731  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
2732  SCIP_CALL( SCIPaddBoolParam(scip,
2733  "heuristics/" HEUR_NAME "/lp",
2734  "should the LP relaxation be solved before the NLP relaxation?",
2735  &heurdata->lp, TRUE, DEFAULT_LP, NULL, NULL) );
2736  SCIP_CALL( SCIPaddBoolParam(scip,
2737  "heuristics/" HEUR_NAME "/preferlpfracs",
2738  "prefer variables that are also fractional in LP solution?",
2739  &heurdata->preferlpfracs, TRUE, DEFAULT_PREFERLPFRACS, NULL, NULL) );
2740  SCIP_CALL( SCIPaddRealParam(scip,
2741  "heuristics/" HEUR_NAME "/minsuccquot",
2742  "heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)",
2743  &heurdata->minsuccquot, FALSE, DEFAULT_MINSUCCQUOT, 0.0, 1.0, NULL, NULL) );
2744  SCIP_CALL( SCIPaddRealParam(scip,
2745  "heuristics/" HEUR_NAME "/fixquot",
2746  "percentage of fractional variables that should be fixed before the next NLP solve",
2747  &heurdata->fixquot, FALSE, DEFAULT_FIXQUOT, 0.0, 1.0, NULL, NULL) );
2748  SCIP_CALL( SCIPaddBoolParam(scip,
2749  "heuristics/" HEUR_NAME "/prefercover",
2750  "should variables in a minimal cover be preferred?",
2751  &heurdata->prefercover, FALSE, DEFAULT_PREFERCOVER, NULL, NULL) );
2752  SCIP_CALL( SCIPaddBoolParam(scip,
2753  "heuristics/" HEUR_NAME "/solvesubmip",
2754  "should a sub-MIP be solved if all cover variables are fixed?",
2755  &heurdata->solvesubmip, FALSE, DEFAULT_SOLVESUBMIP, NULL, NULL) );
2756  SCIP_CALL( SCIPaddBoolParam(scip,
2757  "heuristics/" HEUR_NAME "/nlpfastfail",
2758  "should the NLP solver stop early if it converges slow?",
2759  &heurdata->nlpfastfail, FALSE, DEFAULT_NLPFASTFAIL, NULL, NULL) );
2760  SCIP_CALL( SCIPaddCharParam(scip,
2761  "heuristics/" HEUR_NAME "/nlpstart",
2762  "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2763  &heurdata->nlpstart, TRUE, DEFAULT_NLPSTART, "fns", NULL, NULL) );
2764  SCIP_CALL( SCIPaddCharParam(scip,
2765  "heuristics/" HEUR_NAME "/varselrule",
2766  "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
2767  &heurdata->varselrule, FALSE, DEFAULT_VARSELRULE, "fcpgdv", NULL, NULL) );
2768 
2769  return SCIP_OKAY;
2770 }
HEUR_FREQOFS
#define HEUR_FREQOFS
Definition: heur_nlpdiving.c:38
SCIPsolIsOriginal
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2299
SCIP_DECL_HEUREXIT
static SCIP_DECL_HEUREXIT(heurExitNlpdiving)
Definition: heur_nlpdiving.c:1534
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11770
createNewSol
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HASHMAP *varmap, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1194
SCIPrandomCreate
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_DIDNOTRUN
Definition: type_result.h:33
HEUR_NAME
#define HEUR_NAME
Definition: heur_nlpdiving.c:33
SCIP_FOUNDSOL
Definition: type_result.h:47
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45371
SCIPsetSeparating
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5130
SCIP_NLPTERMSTAT
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:85
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45508
heur_nlpdiving.h
NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
DEFAULT_BACKTRACK
#define DEFAULT_BACKTRACK
Definition: heur_nlpdiving.c:67
SCIP_DELAYED
Definition: type_result.h:34
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30965
SCIPnlpStatisticsCreate
SCIP_RETCODE SCIPnlpStatisticsCreate(SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:781
SCIP_NLPSOLSTAT_LOCINFEASIBLE
Definition: type_nlpi.h:64
DEFAULT_RANDSEED
#define DEFAULT_RANDSEED
Definition: heur_nlpdiving.c:79
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
SCIPgetNLPIntPar
SCIP_RETCODE SCIPgetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int *ival)
Definition: scip.c:31499
SCIP_NLPPAR_ITLIM
Definition: type_nlpi.h:51
SCIPbacktrackProbing
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35291
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46333
DEFAULT_MAXFEASNLPS
#define DEFAULT_MAXFEASNLPS
Definition: heur_nlpdiving.c:65
SCIPcatchVarEvent
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40502
SCIPgetProbingDepth
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35264
SCIPgetCutoffbound
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
SCIPisUbBetter
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46683
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
HEUR_TIMING
#define HEUR_TIMING
Definition: heur_nlpdiving.c:40
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4461
SCIPgetVarPseudocostVal
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip.c:25687
DEFAULT_NLPSTART
#define DEFAULT_NLPSTART
Definition: heur_nlpdiving.c:72
SCIPheurGetNBestSolsFound
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIPgetNSolsFound
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42891
chooseVeclenVar
static SCIP_RETCODE chooseVeclenVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:390
SCIPsetHeurExit
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
SCIPgetNOrigVars
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12120
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
nlpi.h
internal methods for NLPI solver interfaces
DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_MAXDIVEAVGQUOT
Definition: heur_nlpdiving.c:59
DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
Definition: heur_nlpdiving.c:63
SCIPincludeEventhdlrBasic
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8561
SCIPgetNLPSolstat
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip.c:31348
SCIP_Var
Definition: struct_var.h:197
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16735
chooseFracVar
static SCIP_RETCODE chooseFracVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:214
SCIPvarGetRootSol
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12654
SCIPgetMaxDepth
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42371
chooseGuidedVar
static SCIP_RETCODE chooseGuidedVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_SOL *bestsol, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:871
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46372
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
heur_undercover.h
Undercover primal heuristic for MINLPs.
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:39108
FALSE
#define FALSE
Definition: def.h:64
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_MAXDIVEUBQUOT
Definition: heur_nlpdiving.c:56
SCIPeventhdlrGetName
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
SCIPcopyLimits
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4164
SCIPcopyConsCompression
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:3856
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
TRUE
#define TRUE
Definition: def.h:63
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPgetLocalLowerbound
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
Definition: scip.c:13271
SCIPstatisticMessage
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIPsolveNLP
SCIP_RETCODE SCIPsolveNLP(SCIP *scip)
Definition: scip.c:31325
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5104
SCIP_RandNumGen
Definition: struct_misc.h:239
SCIPfindBranchrule
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9219
SCIPgetAvgLowerbound
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip.c:42507
SCIP_HEURDATA
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
DEFAULT_MINRELDEPTH
#define DEFAULT_MINRELDEPTH
Definition: heur_nlpdiving.c:52
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIPincludeHeurBasic
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:8034
SCIPrandomGetInt
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:8723
SCIPchgVarLbProbing
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35367
DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXRELDEPTH
Definition: heur_nlpdiving.c:53
SCIPsetNLPIntPar
SCIP_RETCODE SCIPsetNLPIntPar(SCIP *scip, SCIP_NLPPARAM type, int ival)
Definition: scip.c:31527
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_LPSOLSTAT
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
SCIPheurSetData
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
SCIP_NLPTERMSTAT_LICERR
Definition: type_nlpi.h:82
DEFAULT_VARSELRULE
#define DEFAULT_VARSELRULE
Definition: heur_nlpdiving.c:73
DEFAULT_SOLVESUBMIP
#define DEFAULT_SOLVESUBMIP
Definition: heur_nlpdiving.c:71
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36334
SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:37
SCIP_EVENTTYPE_BOUNDCHANGED
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:108
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip.h:452
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:451
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
SCIP_NLPTERMSTAT_NUMERR
Definition: type_nlpi.h:79
SCIPnlpStatisticsFree
void SCIPnlpStatisticsFree(SCIP_NLPSTATISTICS **statistics)
Definition: nlpi.c:798
MINNLPITER
#define MINNLPITER
Definition: heur_nlpdiving.c:81
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46457
SCIP_NLPSOLSTAT_UNKNOWN
Definition: type_nlpi.h:67
chooseDoubleVar
static SCIP_RETCODE chooseDoubleVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **pseudocands, SCIP_Real *pseudocandsnlpsol, SCIP_Real *pseudocandslpsol, int npseudocands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Real *bestboundval, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:1043
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
SCIP_EVENTTYPE_LBCHANGED
#define SCIP_EVENTTYPE_LBCHANGED
Definition: type_event.h:104
SCIP_Sol
Definition: struct_sol.h:51
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10759
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2996
SCIP_EVENTTYPE_LBRELAXED
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
SCIPupdateVarPseudocost
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25653
SCIPlinkNLPSol
SCIP_RETCODE SCIPlinkNLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37873
SCIPisLbBetter
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46668
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29392
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
SCIP_HashMap
Definition: struct_misc.h:121
SCIPrandomFree
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIPeventGetNewbound
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1162
SCIPcreateSolCopy
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip.c:37468
SCIPgetNLPTermstat
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition: scip.c:31370
getNLPFracVars
static SCIP_RETCODE getNLPFracVars(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR ***nlpcands, SCIP_Real **nlpcandssol, SCIP_Real **nlpcandsfrac, int *nnlpcands)
Definition: heur_nlpdiving.c:139
SCIPsetHeurInitsol
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8143
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15846
SCIPaddLinearConsToNlpHeurSubNlp
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2389
SCIP_NLPSOLSTAT_FEASIBLE
Definition: type_nlpi.h:63
SCIPheurGetName
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIPfindHeur
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip.c:8175
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_NlpStatistics
Definition: struct_nlpi.h:78
SCIPisParamFixed
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4373
SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:54
SCIPsetHeurFree
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8095
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
SCIPpropagateProbing
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35650
SCIP_NLPSOLSTAT
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38219
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip.c:42529
sqrt
SCIPInterval sqrt(const SCIPInterval &x)
Definition: intervalarithext.h:357
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4602
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
SCIPendProbing
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35326
SCIP_EVENTDATA
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
NULL
#define NULL
Definition: lpi_spx1.cpp:137
SCIPgetNNlpis
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9479
SCIPsetNLPInitialGuessSol
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:31293
choosePscostVar
static SCIP_RETCODE choosePscostVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:749
SCIP_EVENTTYPE_UBRELAXED
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:66
SCIP_OKAY
Definition: type_retcode.h:33
HEUR_PRIORITY
#define HEUR_PRIORITY
Definition: heur_nlpdiving.c:36
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:316
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
SCIP_EVENTTYPE_LBTIGHTENED
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46359
SCIPsolveProbingLP
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35886
SCIPcomputeCoverUndercover
SCIP_RETCODE SCIPcomputeCoverUndercover(SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
Definition: heur_undercover.c:3544
DEFAULT_MAXNLPITERREL
#define DEFAULT_MAXNLPITERREL
Definition: heur_nlpdiving.c:55
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
EVENTHDLR_NAME
#define EVENTHDLR_NAME
Definition: heur_nlpdiving.c:44
SCIPheurGetNCalls
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_PROBINGSCORE_PENALTYRATIO
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition: def.h:258
SCIPgetPseudoBranchCands
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:36640
SCIP_Heur
Definition: struct_heur.h:79
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
SCIPgetLastDivenode
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip.c:35099
solveSubMIP
static SCIP_RETCODE solveSubMIP(SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1247
SCIP_DECL_HEUREXEC
static SCIP_DECL_HEUREXEC(heurExecNlpdiving)
Definition: heur_nlpdiving.c:1590
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38042
SCIP_NLPPAR_FASTFAIL
Definition: type_nlpi.h:54
SCIPeventGetVar
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:982
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIPgetNLPStatistics
SCIP_RETCODE SCIPgetNLPStatistics(SCIP *scip, SCIP_NLPSTATISTICS *statistics)
Definition: scip.c:31395
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
HEUR_MAXDEPTH
#define HEUR_MAXDEPTH
Definition: heur_nlpdiving.c:39
SCIPeventGetType
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
SCIProundSol
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39300
SCIPsetObjlimit
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip.c:11114
SCIPvarGetNLPSol
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:17556
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
SCIP_VERBLEVEL_MINIMAL
Definition: type_message.h:43
SCIPvarGetNLocksUp
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_DECL_HEURFREE
static SCIP_DECL_HEURFREE(heurFreeNlpdiving)
Definition: heur_nlpdiving.c:1480
SCIPtrySolFree
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:40070
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4660
DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXDIVEUBQUOTNOSOL
Definition: heur_nlpdiving.c:62
SCIPinitializeRandomSeed
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
SCIPfreeSol
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37806
SCIPenableVarHistory
void SCIPenableVarHistory(SCIP *scip)
Definition: scip.c:25614
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
SCIPdropVarEvent
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40548
SCIP_DECL_EVENTEXEC
static SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
Definition: heur_nlpdiving.c:1401
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:39059
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38268
SCIP_EVENTTYPE_UBTIGHTENED
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP
Definition: heur_nlpdiving.c:41
SCIP_DECL_HEURINIT
static SCIP_DECL_HEURINIT(heurInitNlpdiving)
Definition: heur_nlpdiving.c:1500
SCIPtrySol
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:39976
SCIP_MAXTREEDEPTH
#define SCIP_MAXTREEDEPTH
Definition: def.h:252
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11725
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:146
DEFAULT_PREFERLPFRACS
#define DEFAULT_PREFERLPFRACS
Definition: heur_nlpdiving.c:69
SCIPincludeHeurNlpdiving
SCIP_RETCODE SCIPincludeHeurNlpdiving(SCIP *scip)
Definition: heur_nlpdiving.c:2663
SCIPisObjIntegral
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip.c:11254
SCIPcreateNLPSol
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37248
SCIPvarGetNLocksDown
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39158
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
chooseCoefVar
static SCIP_RETCODE chooseCoefVar(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **nlpcands, SCIP_Real *nlpcandssol, SCIP_Real *nlpcandsfrac, int nnlpcands, SCIP_HASHMAP *varincover, SCIP_Bool covercomputed, int *bestcand, SCIP_Bool *bestcandmayround, SCIP_Bool *bestcandroundup)
Definition: heur_nlpdiving.c:484
SCIPaddCharParam
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
HEUR_DESC
#define HEUR_DESC
Definition: heur_nlpdiving.c:34
calcPscostQuot
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)
Definition: heur_nlpdiving.c:669
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:45796
DEFAULT_FIXQUOT
#define DEFAULT_FIXQUOT
Definition: heur_nlpdiving.c:66
heur_subnlp.h
NLP local search primal heuristic using sub-SCIPs.
SCIPsetHeurInit
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
SCIPretransformObj
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:38402
SCIPeventGetOldbound
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1138
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip.c:45822
SCIPfindNodesel
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8907
SCIPgetNLPFracVars
SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars)
Definition: scip.c:31468
SCIPstatistic
#define SCIPstatistic(x)
Definition: pub_message.h:101
SCIP_Real
#define SCIP_Real
Definition: def.h:145
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
DEFAULT_PREFERCOVER
#define DEFAULT_PREFERCOVER
Definition: heur_nlpdiving.c:70
MIN
#define MIN(x, y)
Definition: memory.c:75
EVENTHDLR_DESC
#define EVENTHDLR_DESC
Definition: heur_nlpdiving.c:45
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:165
SCIPnlpStatisticsGetNIterations
int SCIPnlpStatisticsGetNIterations(SCIP_NLPSTATISTICS *statistics)
Definition: nlpi.c:810
SCIP_Longint
#define SCIP_Longint
Definition: def.h:130
SCIPheurGetNSolsFound
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1317
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
SCIPunlinkSol
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38011
SCIPfrac
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:46207
SCIPcheckCopyLimits
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4128
SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:35
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
HEUR_FREQ
#define HEUR_FREQ
Definition: heur_nlpdiving.c:37
DEFAULT_MAXNLPITERABS
#define DEFAULT_MAXNLPITERABS
Definition: heur_nlpdiving.c:54
SCIPsetSolVals
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:38084
SCIPgetNLPObjval
SCIP_Real SCIPgetNLPObjval(SCIP *scip)
Definition: scip.c:31419
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
SCIPsetHeurCopy
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:33
SCIPnewProbingNode
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:35231
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46421
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45494
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42699
SCIPstartProbing
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35185
SCIPhashmapInsert
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2845
SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:53
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46183
SCIPheurGetData
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_DECL_HEURCOPY
static SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
Definition: heur_nlpdiving.c:1466
SCIPheurGetTime
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1369
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIPchgVarUbProbing
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35411
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
HEUR_DISPCHAR
#define HEUR_DISPCHAR
Definition: heur_nlpdiving.c:35
SCIPaddRealParam
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIPsetSubscipsOff
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5055
SCIPvarMayRoundUp
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3280
SCIP_DECL_HEURINITSOL
static SCIP_DECL_HEURINITSOL(heurInitsolNlpdiving)
Definition: heur_nlpdiving.c:1568
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4718
SCIP_Eventhdlr
Definition: struct_event.h:186
SCIPvarMayRoundDown
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3272
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
DEFAULT_MINSUCCQUOT
#define DEFAULT_MINSUCCQUOT
Definition: heur_nlpdiving.c:64
DEFAULT_LP
#define DEFAULT_LP
Definition: heur_nlpdiving.c:68
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178
DEFAULT_NLPFASTFAIL
#define DEFAULT_NLPFASTFAIL
Definition: heur_nlpdiving.c:78
SCIP_EVENTTYPE
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58