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-2022 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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_nlpdiving.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief NLP diving heuristic that chooses fixings w.r.t. the fractionalities
19  * @author Timo Berthold
20  * @author Stefan Vigerske
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "blockmemshell/memory.h"
26 #include "scip/heur_nlpdiving.h"
27 #include "scip/heur_subnlp.h"
28 #include "scip/heur_undercover.h"
29 #include "scip/pub_event.h"
30 #include "scip/pub_heur.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc.h"
33 #include "scip/pub_sol.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip_branch.h"
36 #include "scip/scip_copy.h"
37 #include "scip/scip_event.h"
38 #include "scip/scip_general.h"
39 #include "scip/scip_heur.h"
40 #include "scip/scip_lp.h"
41 #include "scip/scip_mem.h"
42 #include "scip/scip_message.h"
43 #include "scip/scip_nlp.h"
44 #include "scip/scip_nlpi.h"
45 #include "scip/scip_nodesel.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_prob.h"
49 #include "scip/scip_probing.h"
50 #include "scip/scip_randnumgen.h"
51 #include "scip/scip_sol.h"
52 #include "scip/scip_solve.h"
53 #include "scip/scip_solvingstats.h"
54 #include "scip/scip_timing.h"
55 #include "scip/scip_tree.h"
56 #include "scip/scip_var.h"
57 #include <string.h>
58 
59 #define HEUR_NAME "nlpdiving"
60 #define HEUR_DESC "NLP diving heuristic that chooses fixings w.r.t. the fractionalities"
61 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
62 #define HEUR_PRIORITY -1003010
63 #define HEUR_FREQ 10
64 #define HEUR_FREQOFS 3
65 #define HEUR_MAXDEPTH -1
66 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
67 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
68 
69 /* event handler properties */
70 #define EVENTHDLR_NAME "Nlpdiving"
71 #define EVENTHDLR_DESC "bound change event handler for " HEUR_NAME " heuristic"
72 
73 
74 /*
75  * Default parameter settings
76  */
77 
78 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
79 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
80 #define DEFAULT_MAXNLPITERABS 200 /**< minimial absolute number of allowed NLP iterations */
81 #define DEFAULT_MAXNLPITERREL 10 /**< additional allowed number of NLP iterations relative to successfully found solutions */
82 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
83  * where diving is performed (0.0: no limit) */
84 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
85  * where diving is performed (0.0: no limit) */
86 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
87 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
88 #define DEFAULT_MINSUCCQUOT 0.1 /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
89 #define DEFAULT_MAXFEASNLPS 10 /**< maximal number of NLPs with feasible solution to solve during one dive */
90 #define DEFAULT_FIXQUOT 0.2 /**< percentage of fractional variables that should be fixed before the next NLP solve */
91 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
92 #define DEFAULT_LP FALSE /**< should the LP relaxation be solved before the NLP relaxation? */
93 #define DEFAULT_PREFERLPFRACS FALSE /**< prefer variables that are also fractional in LP solution? */
94 #define DEFAULT_PREFERCOVER TRUE /**< should variables in a minimal cover be preferred? */
95 #define DEFAULT_SOLVESUBMIP FALSE /**< should a sub-MIP be solved if all cover variables are fixed? */
96 #define DEFAULT_NLPSTART 's' /**< which point should be used as starting point for the NLP solver? */
97 #define DEFAULT_VARSELRULE 'd' /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
98  * 'p'seudocost, 'g'uided, 'd'ouble)
99  */
100 #define DEFAULT_NLPFASTFAIL TRUE /**< should the NLP solver stop early if it converges slow? */
101 #define DEFAULT_RANDSEED 97 /**< initial random seed */
102 
103 #define MINNLPITER 10 /**< minimal number of NLP iterations allowed in each NLP solving call */
104 
105 /* locally defined heuristic data */
106 struct SCIP_HeurData
107 {
108  SCIP_SOL* sol; /**< working solution */
109  SCIP_Real minreldepth; /**< minimal relative depth to start diving */
110  SCIP_Real maxreldepth; /**< maximal relative depth to start diving */
111  int maxnlpiterabs; /**< minimial absolute number of allowed NLP iterations */
112  int maxnlpiterrel; /**< additional allowed number of NLP iterations relative to successfully found solutions */
113  SCIP_Real maxdiveubquot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
114  * where diving is performed (0.0: no limit) */
115  SCIP_Real maxdiveavgquot; /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
116  * where diving is performed (0.0: no limit) */
117  SCIP_Real maxdiveubquotnosol; /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
118  SCIP_Real maxdiveavgquotnosol;/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
119  int maxfeasnlps; /**< maximal number of NLPs with feasible solution to solve during one dive */
120  SCIP_Real minsuccquot; /**< heuristic will not run if less then this percentage of calls succeeded (0.0: no limit) */
121  SCIP_Real fixquot; /**< percentage of fractional variables that should be fixed before the next NLP solve */
122  SCIP_Bool backtrack; /**< use one level of backtracking if infeasibility is encountered? */
123  SCIP_Bool lp; /**< should the LP relaxation be solved before the NLP relaxation? */
124  SCIP_Bool preferlpfracs; /**< prefer variables that are also fractional in LP solution? */
125  SCIP_Bool prefercover; /**< should variables in a minimal cover be preferred? */
126  SCIP_Bool solvesubmip; /**< should a sub-MIP be solved if all cover variables are fixed? */
127  SCIP_Bool nlpfastfail; /**< should the NLP solver stop early if it converges slow? */
128  char nlpstart; /**< which point should be used as starting point for the NLP solver? */
129  char varselrule; /**< which variable selection should be used? ('f'ractionality, 'c'oefficient,
130  * 'p'seudocost, 'g'uided, 'd'ouble)
131  */
132 
133  int nnlpiterations; /**< NLP iterations used in this heuristic */
134  int nsuccess; /**< number of runs that produced at least one feasible solution */
135  int nfixedcovervars; /**< number of variables in the cover that are already fixed */
136 #ifdef SCIP_STATISTIC
137  int nnlpsolves; /**< number of NLP solves */
138  int nfailcutoff; /**< number of fails due to cutoff */
139  int nfaildepth; /**< number of fails due to too deep */
140  int nfailnlperror; /**< number of fails due to NLP error */
141 #endif
142  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
143  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
144 };
145 
146 
147 /*
148  * local methods
149  */
150 
151 /** gets fractional variables of last NLP solution along with solution values and fractionalities
152  *
153  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
154  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
155  *
156  * @pre This method can be called if SCIP is in one of the following stages:
157  * - \ref SCIP_STAGE_INITSOLVE
158  * - \ref SCIP_STAGE_SOLVING
159  */
160 static
161 SCIP_RETCODE getNLPFracVars(
162  SCIP* scip, /**< SCIP data structure */
163  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
164  SCIP_VAR*** nlpcands, /**< pointer to store the array of NLP fractional variables, or NULL */
165  SCIP_Real** nlpcandssol, /**< pointer to store the array of NLP fractional variables solution values, or NULL */
166  SCIP_Real** nlpcandsfrac, /**< pointer to store the array of NLP fractional variables fractionalities, or NULL */
167  int* nnlpcands /**< pointer to store the number of NLP fractional variables , or NULL */
168  )
169 {
170  int c;
171 
172  assert(scip != NULL);
173  assert(heurdata != NULL);
174  assert(nlpcands != NULL);
175  assert(nlpcandssol != NULL);
176  assert(nlpcandsfrac != NULL);
177  assert(nnlpcands != NULL);
178 
179  /* get fractional variables that should be integral */
180  SCIP_CALL( SCIPgetNLPFracVars(scip, nlpcands, nlpcandssol, nlpcandsfrac, nnlpcands, NULL) );
181 
182  /* values may be outside the domain in exact arithmetic, but inside the domain within relative tolerance, and still
183  * slightly fractional, because SCIPisFeasIntegral() uses absolute tolerance; project value onto domain to avoid this
184  * (example: primsol=29.99999853455704, lower bound = 30)
185  */
186  for( c = 0; c < *nnlpcands; ++c )
187  {
188  assert(!SCIPisFeasIntegral(scip, (*nlpcandssol)[c]));
189 
190  if( (*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]) || (*nlpcandssol)[c] > SCIPvarGetUbLocal((*nlpcands)[c]) )
191  {
192  SCIP_Real newval;
193 
194  newval = ((*nlpcandssol)[c] < SCIPvarGetLbLocal((*nlpcands)[c]))
195  ? SCIPvarGetLbLocal((*nlpcands)[c]) - 0.5*SCIPfeastol(scip)
196  : SCIPvarGetUbLocal((*nlpcands)[c]) + 0.5*SCIPfeastol(scip);
197 
198  assert(SCIPisFeasIntegral(scip, newval));
199 
200  SCIP_CALL( SCIPsetSolVal(scip, heurdata->sol, (*nlpcands)[c], newval) );
201 
202  (*nnlpcands)--;
203 
204  if( c < *nnlpcands )
205  {
206  (*nlpcands)[c] = (*nlpcands)[*nnlpcands];
207  (*nlpcandssol)[c] = (*nlpcandssol)[*nnlpcands];
208  (*nlpcandsfrac)[c] = (*nlpcandsfrac)[*nnlpcands];
209  }
210  }
211  }
212 
213  /* prefer decisions on variables which are also fractional in LP solution */
214  if( heurdata->preferlpfracs && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
215  {
216  for( c = 0; c < *nnlpcands; ++c )
217  {
218  if( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, (*nlpcands)[c])) )
219  (*nlpcandsfrac)[c] *= 100.0;
220  }
221  }
222 
223  return SCIP_OKAY;
224 }
225 
226 /** finds best candidate variable w.r.t. fractionality:
227  * - prefer variables that may not be rounded without destroying NLP feasibility:
228  * - of these variables, round least fractional variable in corresponding direction
229  * - if all remaining fractional variables may be rounded without destroying NLP feasibility:
230  * - round variable with least increasing objective value
231  * - binary variables are prefered
232  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
233  * also be prefered if a correpsonding parameter is set
234  */
235 static
236 SCIP_RETCODE chooseFracVar(
237  SCIP* scip, /**< original SCIP data structure */
238  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
239  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
240  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
241  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
242  int nnlpcands, /**< number of NLP fractional variables */
243  SCIP_HASHMAP* varincover, /**< hash map for variables */
244  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
245  int* bestcand, /**< pointer to store the index of the best candidate variable */
246  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
247  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
248  )
249 {
250  SCIP_Real bestobjgain;
251  SCIP_Real bestfrac;
252  SCIP_Bool bestcandmayrounddown;
253  SCIP_Bool bestcandmayroundup;
254  int c;
255 
256  /* check preconditions */
257  assert(scip != NULL);
258  assert(heurdata != NULL);
259  assert(nlpcands != NULL);
260  assert(nlpcandssol != NULL);
261  assert(nlpcandsfrac != NULL);
262  assert(covercomputed == (varincover != NULL));
263  assert(bestcand != NULL);
264  assert(bestcandmayround != NULL);
265  assert(bestcandroundup != NULL);
266 
267  bestcandmayrounddown = TRUE;
268  bestcandmayroundup = TRUE;
269  bestobjgain = SCIPinfinity(scip);
270  bestfrac = SCIP_INVALID;
271 
272  for( c = 0; c < nnlpcands; ++c )
273  {
274  SCIP_VAR* var;
275  SCIP_Bool mayrounddown;
276  SCIP_Bool mayroundup;
277  SCIP_Bool roundup;
278  SCIP_Real frac;
279  SCIP_Real obj;
280  SCIP_Real objgain;
281 
282  var = nlpcands[c];
283 
284  mayrounddown = SCIPvarMayRoundDown(var);
285  mayroundup = SCIPvarMayRoundUp(var);
286  frac = nlpcandsfrac[c];
287  obj = SCIPvarGetObj(var);
288 
289  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
290  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
291  continue;
292 
293  if( mayrounddown || mayroundup )
294  {
295  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
296  if( bestcandmayrounddown || bestcandmayroundup )
297  {
298  /* choose rounding direction:
299  * - if variable may be rounded in both directions, round corresponding to the fractionality
300  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
301  * the current fractional solution
302  */
303  if( mayrounddown && mayroundup )
304  {
305  if( SCIPisEQ(scip, frac, 0.5) )
306  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
307  else
308  roundup = (frac > 0.5);
309  }
310  else
311  roundup = mayrounddown;
312 
313  if( roundup )
314  {
315  frac = 1.0 - frac;
316  objgain = frac*obj;
317  }
318  else
319  objgain = -frac*obj;
320 
321  /* penalize too small fractions */
322  if( SCIPisEQ(scip, frac, 0.01) )
323  {
324  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
325  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
326  */
327  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
328  objgain *= 1000.0;
329  }
330  else if( frac < 0.01 )
331  objgain *= 1000.0;
332 
333  /* prefer decisions on binary variables */
334  if( !SCIPvarIsBinary(var) )
335  objgain *= 1000.0;
336 
337  /* prefer decisions on cover variables */
338  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
339  objgain *= 1000.0;
340 
341  /* check, if candidate is new best candidate */
342  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
343  {
344  *bestcand = c;
345  bestobjgain = objgain;
346  bestfrac = frac;
347  bestcandmayrounddown = mayrounddown;
348  bestcandmayroundup = mayroundup;
349  *bestcandroundup = roundup;
350  }
351  }
352  }
353  else
354  {
355  /* the candidate may not be rounded */
356  if( SCIPisEQ(scip, frac, 0.5) )
357  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
358  else if( frac < 0.5 )
359  roundup = FALSE;
360  else
361  roundup = TRUE;
362 
363  /* adjust fractional part */
364  if( roundup )
365  frac = 1.0 - frac;
366 
367  /* penalize too small fractions */
368  if( SCIPisEQ(scip, frac, 0.01) )
369  {
370  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
371  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
372  */
373  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
374  frac += 10.0;
375  }
376  else if( frac < 0.01 )
377  frac += 10.0;
378 
379  /* prefer decisions on binary variables */
380  if( !SCIPvarIsBinary(var) )
381  frac *= 1000.0;
382 
383  /* prefer decisions on cover variables */
384  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
385  frac *= 1000.0;
386 
387  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
388  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
389  {
390  *bestcand = c;
391  bestfrac = frac;
392  bestcandmayrounddown = FALSE;
393  bestcandmayroundup = FALSE;
394  *bestcandroundup = roundup;
395  }
396  assert(bestfrac < SCIP_INVALID);
397  }
398  }
399 
400  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
401 
402  return SCIP_OKAY;
403 }
404 
405 /** finds best candidate variable w.r.t. vector length:
406  * - round variable with a small ratio between the increase in the objective and the locking numbers
407  * - binary variables are prefered
408  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
409  * also be prefered if a corresponding parameter is set
410  */
411 static
412 SCIP_RETCODE chooseVeclenVar(
413  SCIP* scip, /**< original SCIP data structure */
414  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
415  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
416  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
417  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
418  int nnlpcands, /**< number of NLP fractional variables */
419  SCIP_HASHMAP* varincover, /**< hash map for variables */
420  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
421  int* bestcand, /**< pointer to store the index of the best candidate variable */
422  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
423  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
424  )
425 {
426  SCIP_Real bestscore;
427  int c;
428 
429  /* check preconditions */
430  assert(scip != NULL);
431  assert(heurdata != NULL);
432  assert(nlpcands != NULL);
433  assert(nlpcandsfrac != NULL);
434  assert(nlpcandssol != NULL);
435  assert(bestcand != NULL);
436  assert(bestcandmayround != NULL);
437  assert(bestcandroundup != NULL);
438 
439  *bestcandmayround = TRUE;
440  bestscore = SCIP_REAL_MAX;
441 
442  /* get best candidate */
443  for( c = 0; c < nnlpcands; ++c )
444  {
445  SCIP_VAR* var;
446 
447  SCIP_Real obj;
448  SCIP_Real objdelta;
449  SCIP_Real frac;
450  SCIP_Real score;
451 
452  int nlocks;
453 
454  SCIP_Bool roundup;
455 
456  var = nlpcands[c];
457 
458  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
459  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
460  continue;
461 
462  frac = nlpcandsfrac[c];
463  obj = SCIPvarGetObj(var);
464  roundup = (obj >= 0.0);
465  objdelta = (roundup ? (1.0-frac)*obj : -frac * obj);
466  assert(objdelta >= 0.0);
467 
468  /* check whether the variable is roundable */
469  *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var));
470  nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
471 
472  /* smaller score is better */
473  score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)nlocks+1.0);
474 
475  /* prefer decisions on binary variables */
476  if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
477  score *= 1000.0;
478 
479  /* prefer decisions on cover variables */
480  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
481  score *= 1000;
482 
483  /* check, if candidate is new best candidate */
484  if( score < bestscore )
485  {
486  *bestcand = c;
487  bestscore = score;
488  *bestcandroundup = roundup;
489  }
490  }
491 
492  return SCIP_OKAY;
493 }
494 
495 
496 /** finds best candidate variable w.r.t. locking numbers:
497  * - prefer variables that may not be rounded without destroying LP feasibility:
498  * - of these variables, round variable with least number of locks in corresponding direction
499  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
500  * - round variable with least number of locks in opposite of its feasible rounding direction
501  * - binary variables are prefered
502  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
503  * also be prefered if a correpsonding parameter is set
504  */
505 static
506 SCIP_RETCODE chooseCoefVar(
507  SCIP* scip, /**< original SCIP data structure */
508  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
509  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
510  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
511  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
512  int nnlpcands, /**< number of NLP fractional variables */
513  SCIP_HASHMAP* varincover, /**< hash map for variables */
514  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
515  int* bestcand, /**< pointer to store the index of the best candidate variable */
516  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
517  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
518  )
519 {
520  SCIP_Bool bestcandmayrounddown;
521  SCIP_Bool bestcandmayroundup;
522  int bestnviolrows; /* number of violated rows for best candidate */
523  SCIP_Real bestcandfrac; /* fractionality of best candidate */
524  int c;
525 
526  /* check preconditions */
527  assert(scip != NULL);
528  assert(heurdata != NULL);
529  assert(nlpcands != NULL);
530  assert(nlpcandsfrac != NULL);
531  assert(nlpcandssol != NULL);
532  assert(bestcand != NULL);
533  assert(bestcandmayround != NULL);
534  assert(bestcandroundup != NULL);
535 
536  bestcandmayrounddown = TRUE;
537  bestcandmayroundup = TRUE;
538  bestnviolrows = INT_MAX;
539  bestcandfrac = SCIP_INVALID;
540 
541  /* get best candidate */
542  for( c = 0; c < nnlpcands; ++c )
543  {
544  SCIP_VAR* var;
545 
546  int nlocksdown;
547  int nlocksup;
548  int nviolrows;
549 
550  SCIP_Bool mayrounddown;
551  SCIP_Bool mayroundup;
552  SCIP_Bool roundup;
553  SCIP_Real frac;
554 
555  var = nlpcands[c];
556  mayrounddown = SCIPvarMayRoundDown(var);
557  mayroundup = SCIPvarMayRoundUp(var);
558  frac = nlpcandsfrac[c];
559 
560  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
561  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
562  continue;
563 
564  if( mayrounddown || mayroundup )
565  {
566  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
567  if( bestcandmayrounddown || bestcandmayroundup )
568  {
569  /* choose rounding direction:
570  * - if variable may be rounded in both directions, round corresponding to the fractionality
571  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
572  * the current fractional solution
573  */
574  if( mayrounddown && mayroundup )
575  {
576  if( SCIPisEQ(scip, frac, 0.5) )
577  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
578  else
579  roundup = (frac > 0.5);
580  }
581  else
582  roundup = mayrounddown;
583 
584  if( roundup )
585  {
586  frac = 1.0 - frac;
587  nviolrows = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
588  }
589  else
590  nviolrows = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
591 
592  /* penalize too small fractions */
593  if( SCIPisEQ(scip, frac, 0.01) )
594  {
595  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
596  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
597  */
598  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
599  nviolrows *= 100;
600  }
601  else if( frac < 0.01 )
602  nviolrows *= 100;
603 
604  /* prefer decisions on binary variables */
605  if( !SCIPvarIsBinary(var) )
606  nviolrows *= 1000;
607 
608  /* prefer decisions on cover variables */
609  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
610  nviolrows *= 1000;
611 
612  /* check, if candidate is new best candidate */
613  assert( (0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var) );
614  if( nviolrows + frac < bestnviolrows + bestcandfrac )
615  {
616  *bestcand = c;
617  bestnviolrows = nviolrows;
618  bestcandfrac = frac;
619  bestcandmayrounddown = mayrounddown;
620  bestcandmayroundup = mayroundup;
621  *bestcandroundup = roundup;
622  }
623  }
624  }
625  else
626  {
627  /* the candidate may not be rounded */
628  nlocksdown = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL);
629  nlocksup = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL);
630 
631  roundup = (nlocksdown > nlocksup);
632  if( !roundup )
633  {
634  roundup = (nlocksdown == nlocksup);
635  if( SCIPisEQ(scip, frac, 0.5) )
636  roundup = (roundup && (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0));
637  else
638  roundup = (roundup && frac > 0.5);
639  }
640 
641  if( roundup )
642  {
643  nviolrows = nlocksup;
644  frac = 1.0 - frac;
645  }
646  else
647  nviolrows = nlocksdown;
648 
649  /* penalize too small fractions */
650  if( SCIPisEQ(scip, frac, 0.01) )
651  {
652  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
653  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
654  */
655  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
656  nviolrows *= 100;
657  }
658  else if( frac < 0.01 )
659  nviolrows *= 100;
660 
661  /* prefer decisions on binary variables */
662  if( !SCIPvarIsBinary(var) )
663  nviolrows *= 100;
664 
665  /* prefer decisions on cover variables */
666  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
667  nviolrows *= 1000;
668 
669  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
670  assert((0.0 < frac && frac < 1.0) || SCIPvarIsBinary(var));
671  if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
672  {
673  *bestcand = c;
674  bestnviolrows = nviolrows;
675  bestcandfrac = frac;
676  bestcandmayrounddown = FALSE;
677  bestcandmayroundup = FALSE;
678  *bestcandroundup = roundup;
679  }
680  assert(bestcandfrac < SCIP_INVALID);
681  }
682  }
683 
684  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
685 
686  return SCIP_OKAY;
687 }
688 
689 /** calculates the pseudocost score for a given variable w.r.t. a given solution value and a given rounding direction */
690 static
691 void calcPscostQuot(
692  SCIP* scip, /**< SCIP data structure */
693  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
694  SCIP_VAR* var, /**< problem variable */
695  SCIP_Real primsol, /**< primal solution of variable */
696  SCIP_Real frac, /**< fractionality of variable */
697  int rounddir, /**< -1: round down, +1: round up, 0: select due to pseudo cost values */
698  SCIP_Real* pscostquot, /**< pointer to store pseudo cost quotient */
699  SCIP_Bool* roundup, /**< pointer to store whether the variable should be rounded up */
700  SCIP_Bool prefvar /**< should this variable be preferred because it is in a minimal cover? */
701  )
702 {
703  SCIP_Real pscostdown;
704  SCIP_Real pscostup;
705 
706  assert(heurdata != NULL);
707  assert(pscostquot != NULL);
708  assert(roundup != NULL);
709  assert(SCIPisEQ(scip, frac, primsol - SCIPfeasFloor(scip, primsol)));
710 
711  /* bound fractions to not prefer variables that are nearly integral */
712  frac = MAX(frac, 0.1);
713  frac = MIN(frac, 0.9);
714 
715  /* get pseudo cost quotient */
716  pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac);
717  pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac);
718  assert(pscostdown >= 0.0 && pscostup >= 0.0);
719 
720  /* choose rounding direction
721  *
722  * to avoid performance variability caused by numerics we use random numbers to decide whether we want to roundup or
723  * round down if the values to compare are equal within tolerances.
724  */
725  if( rounddir == -1 )
726  *roundup = FALSE;
727  else if( rounddir == +1 )
728  *roundup = TRUE;
729  else if( SCIPisLT(scip, primsol, SCIPvarGetRootSol(var) - 0.4)
730  || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) - 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
731  *roundup = FALSE;
732  else if( SCIPisGT(scip, primsol, SCIPvarGetRootSol(var) + 0.4)
733  || (SCIPisEQ(scip, primsol, SCIPvarGetRootSol(var) + 0.4) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
734  *roundup = TRUE;
735  else if( SCIPisLT(scip, frac, 0.3) || (SCIPisEQ(scip, frac, 0.3) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
736  *roundup = FALSE;
737  else if( SCIPisGT(scip, frac, 0.7) || (SCIPisEQ(scip, frac, 0.7) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0) )
738  *roundup = TRUE;
739  else if( SCIPisLT(scip, pscostdown, pscostup)
740  || (SCIPisEQ(scip, pscostdown, pscostup) && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0))
741  *roundup = FALSE;
742  else
743  *roundup = TRUE;
744 
745  /* calculate pseudo cost quotient */
746  if( *roundup )
747  *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
748  else
749  *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
750 
751  /* prefer decisions on binary variables */
752  if( SCIPvarIsBinary(var) )
753  (*pscostquot) *= 1000.0;
754 
755  /* prefer decisions on cover variables */
756  if( prefvar )
757  (*pscostquot) *= 1000.0;
758 }
759 
760 /** finds best candidate variable w.r.t. pseudo costs:
761  * - prefer variables that may not be rounded without destroying LP feasibility:
762  * - of these variables, round variable with largest rel. difference of pseudo cost values in corresponding
763  * direction
764  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
765  * - round variable in the objective value direction
766  * - binary variables are prefered
767  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
768  * also be prefered if a correpsonding parameter is set
769  */
770 static
771 SCIP_RETCODE choosePscostVar(
772  SCIP* scip, /**< original SCIP data structure */
773  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
774  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
775  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
776  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
777  int nnlpcands, /**< number of NLP fractional variables */
778  SCIP_HASHMAP* varincover, /**< hash map for variables */
779  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
780  int* bestcand, /**< pointer to store the index of the best candidate variable */
781  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
782  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
783  )
784 {
785  SCIP_Bool bestcandmayrounddown;
786  SCIP_Bool bestcandmayroundup;
787  SCIP_Real bestpscostquot;
788  int c;
789 
790  /* check preconditions */
791  assert(scip != NULL);
792  assert(heurdata != NULL);
793  assert(nlpcands != NULL);
794  assert(nlpcandsfrac != NULL);
795  assert(nlpcandssol != NULL);
796  assert(bestcand != NULL);
797  assert(bestcandmayround != NULL);
798  assert(bestcandroundup != NULL);
799 
800  bestcandmayrounddown = TRUE;
801  bestcandmayroundup = TRUE;
802  bestpscostquot = -1.0;
803 
804  for( c = 0; c < nnlpcands; ++c )
805  {
806  SCIP_VAR* var;
807  SCIP_Real primsol;
808 
809  SCIP_Bool mayrounddown;
810  SCIP_Bool mayroundup;
811  SCIP_Bool roundup;
812  SCIP_Bool prefvar;
813  SCIP_Real frac;
814  SCIP_Real pscostquot;
815 
816  var = nlpcands[c];
817  mayrounddown = SCIPvarMayRoundDown(var);
818  mayroundup = SCIPvarMayRoundUp(var);
819  primsol = nlpcandssol[c];
820  frac = nlpcandsfrac[c];
821  prefvar = covercomputed && heurdata->prefercover && SCIPhashmapExists(varincover, var);
822  pscostquot = SCIP_INVALID;
823 
824  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
825  continue;
826 
827  if( mayrounddown || mayroundup )
828  {
829  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
830  if( bestcandmayrounddown || bestcandmayroundup )
831  {
832  /* choose rounding direction:
833  * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
834  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
835  * the current fractional solution
836  */
837  roundup = FALSE;
838  if( mayrounddown && mayroundup )
839  calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
840  else if( mayrounddown )
841  calcPscostQuot(scip, heurdata, var, primsol, frac, +1, &pscostquot, &roundup, prefvar);
842  else
843  calcPscostQuot(scip, heurdata, var, primsol, frac, -1, &pscostquot, &roundup, prefvar);
844 
845  assert(!SCIPisInfinity(scip,ABS(pscostquot)));
846 
847  /* check, if candidate is new best candidate */
848  if( pscostquot > bestpscostquot )
849  {
850  *bestcand = c;
851  bestpscostquot = pscostquot;
852  bestcandmayrounddown = mayrounddown;
853  bestcandmayroundup = mayroundup;
854  *bestcandroundup = roundup;
855  }
856  }
857  }
858  else
859  {
860  /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
861  calcPscostQuot(scip, heurdata, var, primsol, frac, 0, &pscostquot, &roundup, prefvar);
862  assert(!SCIPisInfinity(scip,ABS(pscostquot)));
863 
864  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
865  if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
866  {
867  *bestcand = c;
868  bestpscostquot = pscostquot;
869  bestcandmayrounddown = FALSE;
870  bestcandmayroundup = FALSE;
871  *bestcandroundup = roundup;
872  }
873  }
874  }
875 
876  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
877 
878  return SCIP_OKAY;
879 }
880 
881 /** finds best candidate variable w.r.t. the incumbent solution:
882  * - prefer variables that may not be rounded without destroying LP feasibility:
883  * - of these variables, round a variable to its value in direction of incumbent solution, and choose the
884  * variable that is closest to its rounded value
885  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
886  * - round variable in direction that destroys LP feasibility (other direction is checked by SCIProundSol())
887  * - round variable with least increasing objective value
888  * - binary variables are prefered
889  * - variables in a minimal cover or variables that are also fractional in an optimal LP solution might
890  * also be prefered if a correpsonding parameter is set
891  */
892 static
893 SCIP_RETCODE chooseGuidedVar(
894  SCIP* scip, /**< original SCIP data structure */
895  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
896  SCIP_VAR** nlpcands, /**< array of NLP fractional variables */
897  SCIP_Real* nlpcandssol, /**< array of NLP fractional variables solution values */
898  SCIP_Real* nlpcandsfrac, /**< array of NLP fractional variables fractionalities */
899  int nnlpcands, /**< number of NLP fractional variables */
900  SCIP_SOL* bestsol, /**< incumbent solution */
901  SCIP_HASHMAP* varincover, /**< hash map for variables */
902  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
903  int* bestcand, /**< pointer to store the index of the best candidate variable */
904  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
905  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
906  )
907 {
908  SCIP_Real bestobjgain;
909  SCIP_Real bestfrac;
910  SCIP_Bool bestcandmayrounddown;
911  SCIP_Bool bestcandmayroundup;
912  int c;
913 
914  /* check preconditions */
915  assert(scip != NULL);
916  assert(heurdata != NULL);
917  assert(nlpcands != NULL);
918  assert(nlpcandsfrac != NULL);
919  assert(nlpcandssol != NULL);
920  assert(bestcand != NULL);
921  assert(bestcandmayround != NULL);
922  assert(bestcandroundup != NULL);
923 
924  bestcandmayrounddown = TRUE;
925  bestcandmayroundup = TRUE;
926  bestobjgain = SCIPinfinity(scip);
927  bestfrac = SCIP_INVALID;
928 
929  for( c = 0; c < nnlpcands; ++c )
930  {
931  SCIP_VAR* var;
932  SCIP_Real bestsolval;
933  SCIP_Real solval;
934  SCIP_Real obj;
935  SCIP_Real frac;
936  SCIP_Real objgain;
937 
938  SCIP_Bool mayrounddown;
939  SCIP_Bool mayroundup;
940  SCIP_Bool roundup;
941 
942  var = nlpcands[c];
943  mayrounddown = SCIPvarMayRoundDown(var);
944  mayroundup = SCIPvarMayRoundUp(var);
945  solval = nlpcandssol[c];
946  frac = nlpcandsfrac[c];
947  obj = SCIPvarGetObj(var);
948  bestsolval = SCIPgetSolVal(scip, bestsol, var);
949 
950  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
951  if( SCIPisLT(scip, solval, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, solval, SCIPvarGetUbLocal(var)) )
952  continue;
953 
954  /* select default rounding direction
955  * try to avoid variability; decide randomly if the LP solution can contain some noise
956  */
957  if( SCIPisEQ(scip, solval, bestsolval) )
958  roundup = (SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 0);
959  else
960  roundup = (solval < bestsolval);
961 
962  if( mayrounddown || mayroundup )
963  {
964  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
965  if( bestcandmayrounddown || bestcandmayroundup )
966  {
967  /* choose rounding direction:
968  * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
969  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
970  * the current fractional solution with SCIProundSol()
971  */
972  if( !mayrounddown || !mayroundup )
973  roundup = mayrounddown;
974 
975  if( roundup )
976  {
977  frac = 1.0 - frac;
978  objgain = frac*obj;
979  }
980  else
981  objgain = -frac*obj;
982 
983  /* penalize too small fractions */
984  if( SCIPisEQ(scip, frac, 0.01) )
985  {
986  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
987  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
988  */
989  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
990  objgain *= 1000.0;
991  }
992  else if( frac < 0.01 )
993  objgain *= 1000.0;
994 
995  /* prefer decisions on binary variables */
996  if( !SCIPvarIsBinary(var) )
997  objgain *= 1000.0;
998 
999  /* prefer decisions on cover variables */
1000  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1001  objgain *= 1000.0;
1002 
1003  /* check, if candidate is new best candidate */
1004  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
1005  {
1006  *bestcand = c;
1007  bestobjgain = objgain;
1008  bestfrac = frac;
1009  bestcandmayrounddown = mayrounddown;
1010  bestcandmayroundup = mayroundup;
1011  *bestcandroundup = roundup;
1012  }
1013  }
1014  }
1015  else
1016  {
1017  /* the candidate may not be rounded */
1018  if( roundup )
1019  frac = 1.0 - frac;
1020 
1021  /* penalize too small fractions */
1022  if( SCIPisEQ(scip, frac, 0.01) )
1023  {
1024  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
1025  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1026  */
1027  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
1028  frac += 10.0;
1029  }
1030  else if( frac < 0.01 )
1031  frac += 10.0;
1032 
1033  /* prefer decisions on binary variables */
1034  if( !SCIPvarIsBinary(var) )
1035  frac *= 1000.0;
1036 
1037  /* prefer decisions on cover variables */
1038  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1039  frac *= 1000.0;
1040 
1041  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
1042  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
1043  {
1044  *bestcand = c;
1045  bestfrac = frac;
1046  bestcandmayrounddown = FALSE;
1047  bestcandmayroundup = FALSE;
1048  *bestcandroundup = roundup;
1049  }
1050  }
1051  }
1052 
1053  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
1054 
1055  return SCIP_OKAY;
1056 }
1057 
1058 /** finds best candidate variable w.r.t. both, the LP and the NLP solution:
1059  * - choose a variable for which the sum of the distances from the relaxations' solutions to a common
1060  * integer value is minimal
1061  * - binary variables are prefered
1062  * - variables in a minimal cover might be prefered if a corresponding parameter is set
1063  */
1064 static
1065 SCIP_RETCODE chooseDoubleVar(
1066  SCIP* scip, /**< original SCIP data structure */
1067  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1068  SCIP_VAR** pseudocands, /**< array of non-fixed variables */
1069  SCIP_Real* pseudocandsnlpsol, /**< array of NLP solution values */
1070  SCIP_Real* pseudocandslpsol, /**< array of LP solution values */
1071  int npseudocands, /**< number of NLP fractional variables */
1072  SCIP_HASHMAP* varincover, /**< hash map for variables */
1073  SCIP_Bool covercomputed, /**< has a minimal cover been computed? */
1074  int* bestcand, /**< pointer to store the index of the best candidate variable */
1075  SCIP_Real* bestboundval, /**< pointer to store the bound, the best candidate should be rounded to */
1076  SCIP_Bool* bestcandmayround, /**< pointer to store whether best candidate is trivially roundable */
1077  SCIP_Bool* bestcandroundup /**< pointer to store whether best candidate should be rounded up */
1078  )
1079 {
1080  SCIP_Real bestfrac;
1081  int c;
1082 
1083  /* check preconditions */
1084  assert(scip != NULL);
1085  assert(heurdata != NULL);
1086  assert(pseudocands != NULL);
1087  assert(pseudocandsnlpsol != NULL);
1088  assert(pseudocandslpsol != NULL);
1089  assert(covercomputed == (varincover != NULL));
1090  assert(bestcand != NULL);
1091  assert(bestcandmayround != NULL);
1092  assert(bestcandroundup != NULL);
1093 
1094  bestfrac = SCIP_INVALID;
1095 
1096  for( c = 0; c < npseudocands; ++c )
1097  {
1098  SCIP_VAR* var;
1099  SCIP_Bool mayround;
1100  SCIP_Bool roundup;
1101 
1102  SCIP_Real frac;
1103  SCIP_Real lpsol;
1104  SCIP_Real nlpsol;
1105  SCIP_Real lpsolfloor;
1106  SCIP_Real nlpsolfloor;
1107  SCIP_Real lpsolceil;
1108  SCIP_Real nlpsolceil;
1109  SCIP_Real boundval;
1110  SCIP_Real floorval;
1111  SCIP_Real ceilval;
1112 
1113  var = pseudocands[c];
1114  lpsol = pseudocandslpsol[c];
1115  nlpsol = pseudocandsnlpsol[c];
1116 
1117  assert(SCIPvarGetUbLocal(var)-SCIPvarGetLbLocal(var) > 0.5);
1118  assert(SCIPisLE(scip, SCIPvarGetLbLocal(var), lpsol) && SCIPisLE(scip, lpsol, SCIPvarGetUbLocal(var)));
1119 
1120  /* since we are not solving the NLP after each fixing, the old NLP solution might be outside the propagated bounds */
1121  if( SCIPisLT(scip, nlpsol, SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpsol, SCIPvarGetUbLocal(var)) )
1122  continue;
1123 
1124  mayround = SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var);
1125 
1126  /* if this candidate is trivially roundable, and we already know a candidate that is not, continue */
1127  if( mayround && !(*bestcandmayround) )
1128  continue;
1129 
1130  if( SCIPisFeasEQ(scip, lpsol, nlpsol) && SCIPisFeasIntegral(scip, lpsol))
1131  continue;
1132 
1133  lpsolfloor = SCIPfeasFloor(scip, lpsol);
1134  nlpsolfloor = SCIPfeasFloor(scip, nlpsol);
1135  lpsolceil = SCIPfeasCeil(scip, lpsol);
1136  nlpsolceil = SCIPfeasCeil(scip, nlpsol);
1137  floorval = MIN(lpsolfloor,nlpsolfloor);
1138  ceilval = MAX(lpsolceil,nlpsolceil);
1139 
1140  /* if both values are in the same interval, find out which integer is (in sum) the closer one, this will be the
1141  * new bound. The minima and maxima are necessary since one or both values with be integer
1142  */
1143  if( SCIPvarIsBinary(var) || ceilval-floorval < 1.5 )
1144  {
1145  frac = 0.33*(lpsol-floorval) + 0.67*(nlpsol-floorval);
1146  if( frac < 0.5 )
1147  {
1148  roundup = FALSE;
1149  boundval = MIN(lpsolfloor,nlpsolfloor);
1150  }
1151  else
1152  {
1153  roundup = TRUE;
1154  frac = 1.0-frac;
1155  boundval = MAX(nlpsolceil,lpsolceil);
1156  }
1157  }
1158  else
1159  {
1160  /* determine new bound in the middle of both relaxations, such that the NLP stays feasible */
1161  SCIP_Real midval;
1162  midval = (nlpsol+lpsol)/2.0;
1163  roundup = nlpsol > lpsol;
1164  frac = ABS(nlpsol-lpsol);
1165 
1166  if( roundup )
1167  boundval = SCIPfeasCeil(scip, midval);
1168  else
1169  boundval = SCIPfeasFloor(scip, midval);
1170 
1171  assert(roundup == SCIPisGT(scip, nlpsol, boundval));
1172  }
1173 
1174  /* penalize too small fractions */
1175  if( SCIPisEQ(scip, frac, 0.01) )
1176  {
1177  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
1178  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for increasing the fractionality, i.e., the score.
1179  */
1180  if( SCIPrandomGetInt(heurdata->randnumgen, 0, SCIP_PROBINGSCORE_PENALTYRATIO) == 0 )
1181  frac += 10.0;
1182  }
1183  else if( frac < 0.01 )
1184  frac += 10.0;
1185 
1186  /* prefer decisions on binary variables */
1187  if( !SCIPvarIsBinary(var) )
1188  frac *= 1000.0;
1189 
1190  /* prefer decisions on cover variables */
1191  if( covercomputed && heurdata->prefercover && !SCIPhashmapExists(varincover, var) )
1192  frac *= 1000.0;
1193 
1194  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
1195  if( frac < bestfrac || (*bestcandmayround && !mayround) )
1196  {
1197  *bestcand = c;
1198  bestfrac = frac;
1199  *bestcandmayround = FALSE;
1200  *bestcandroundup = roundup;
1201  *bestboundval = boundval;
1202  }
1203  assert(bestfrac < SCIP_INVALID);
1204  }
1205 
1206  if( *bestcandroundup )
1207  *bestboundval -= 0.5;
1208  else
1209  *bestboundval += 0.5;
1210 
1211  return SCIP_OKAY;
1212 }
1213 
1214 /** creates a new solution for the original problem by copying the solution of the subproblem */
1215 static
1216 SCIP_RETCODE createNewSol(
1217  SCIP* scip, /**< original SCIP data structure */
1218  SCIP* subscip, /**< SCIP structure of the subproblem */
1219  SCIP_HEUR* heur, /**< heuristic structure */
1220  SCIP_HASHMAP* varmap, /**< hash map for variables */
1221  SCIP_SOL* subsol, /**< solution of the subproblem */
1222  SCIP_Bool* success /**< used to store whether new solution was found or not */
1223  )
1224 {
1225  SCIP_VAR** vars; /* the original problem's variables */
1226  SCIP_Real* subsolvals; /* solution values of the subproblem */
1227  SCIP_SOL* newsol; /* solution to be created for the original problem */
1228  int nvars; /* the original problem's number of variables */
1229  SCIP_VAR* subvar;
1230  int i;
1231 
1232  assert(scip != NULL);
1233  assert(subscip != NULL);
1234  assert(subsol != NULL);
1235 
1236  /* get variables' data */
1237  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1238 
1239  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1240 
1241  /* copy the solution */
1242  for( i = 0; i < nvars; ++i )
1243  {
1244  subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
1245  if( subvar == NULL )
1246  subsolvals[i] = MIN(MAX(0.0, SCIPvarGetLbLocal(vars[i])), SCIPvarGetUbLocal(vars[i])); /*lint !e666*/
1247  else
1248  subsolvals[i] = SCIPgetSolVal(subscip, subsol, subvar);
1249  }
1250 
1251  /* create new solution for the original problem */
1252  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1253  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1254 
1255  /* try to add new solution to scip and free it immediately */
1256  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
1257 
1258  SCIPfreeBufferArray(scip, &subsolvals);
1259 
1260  return SCIP_OKAY;
1261 }
1262 
1263 /** todo setup and solve the subMIP */
1264 static
1265 SCIP_RETCODE doSolveSubMIP(
1266  SCIP* scip, /**< SCIP data structure */
1267  SCIP* subscip, /**< NLP diving subscip */
1268  SCIP_HEUR* heur, /**< heuristic data structure */
1269  SCIP_VAR** covervars, /**< variables in the cover, should be fixed locally */
1270  int ncovervars, /**< number of variables in the cover */
1271  SCIP_Bool* success /**< pointer to store whether a solution was found */
1272  )
1273 {
1274  SCIP_HASHMAP* varmap;
1275  SCIP_SOL** subsols;
1276  int c;
1277  int nsubsols;
1278 
1279  assert(subscip != NULL);
1280  assert(scip != NULL);
1281  assert(heur != NULL);
1282 
1283  /* create the variable mapping hash map */
1284  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), SCIPgetNVars(scip)) );
1285 
1286  *success = FALSE;
1287 
1288  /* copy original problem to subproblem; do not copy pricers */
1289  SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", NULL, NULL, 0, FALSE, FALSE, FALSE,
1290  TRUE, NULL) );
1291 
1292  /* assert that cover variables are fixed in source and target SCIP */
1293  for( c = 0; c < ncovervars; c++)
1294  {
1295  assert(SCIPhashmapGetImage(varmap, covervars[c]) != NULL); /* cover variable cannot be relaxation-only, thus must have been copied */
1296  assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1297  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c])),
1298  SCIPvarGetUbGlobal((SCIP_VAR*) SCIPhashmapGetImage(varmap, covervars[c]))));
1299  }
1300 
1301  /* set parameters for sub-SCIP */
1302 
1303  /* do not abort subproblem on CTRL-C */
1304  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1305 
1306 #ifdef SCIP_DEBUG
1307  /* for debugging, enable full output */
1308  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1309  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
1310 #else
1311  /* disable statistic timing inside sub SCIP and output to console */
1312  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1313  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1314 #endif
1315 
1316  /* set limits for the subproblem */
1317  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
1318  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", (SCIP_Longint)100) );
1319  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", (SCIP_Longint)500) );
1320 
1321  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
1322  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1323 
1324  /* disable cutting plane separation */
1325  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
1326 
1327  /* disable expensive presolving */
1328  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
1329 
1330  /* use best estimate node selection */
1331  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
1332  {
1333  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
1334  }
1335 
1336  /* use inference branching */
1337  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
1338  {
1339  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
1340  }
1341 
1342  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
1343  if( !SCIPisParamFixed(subscip, "conflict/enable") )
1344  {
1345  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
1346  }
1347  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
1348  {
1349  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
1350  }
1351  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
1352  {
1353  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
1354  }
1355 
1356  if( SCIPgetNSols(scip) > 0 )
1357  {
1358  SCIP_Real upperbound;
1359  SCIP_Real cutoffbound;
1360  SCIP_Real minimprove;
1361 
1362  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
1363 
1364  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
1365  minimprove = 0.01;
1366 
1367  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
1368  {
1369  cutoffbound = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
1370  }
1371  else
1372  {
1373  if( SCIPgetUpperbound(scip) >= 0 )
1374  cutoffbound = (1 - minimprove)*SCIPgetUpperbound(scip);
1375  else
1376  cutoffbound = (1 + minimprove)*SCIPgetUpperbound(scip);
1377  }
1378  cutoffbound = MIN(upperbound, cutoffbound);
1379  SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) );
1380  }
1381 
1382  SCIP_CALL_ABORT( SCIPsolve(subscip) );
1383 
1384  /* check, whether a solution was found;
1385  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1386  */
1387  nsubsols = SCIPgetNSols(subscip);
1388  subsols = SCIPgetSols(subscip);
1389  for( c = 0; c < nsubsols && !(*success); ++c )
1390  {
1391  SCIP_CALL( createNewSol(scip, subscip, heur, varmap, subsols[c], success) );
1392  }
1393 
1394  SCIPhashmapFree(&varmap);
1395 
1396  return SCIP_OKAY;
1397 }
1398 
1399 
1400 /** solves subproblem and passes best feasible solution to original SCIP instance */
1401 static
1402 SCIP_RETCODE solveSubMIP(
1403  SCIP* scip, /**< SCIP data structure of the original problem */
1404  SCIP_HEUR* heur, /**< heuristic data structure */
1405  SCIP_VAR** covervars, /**< variables in the cover, should be fixed locally */
1406  int ncovervars, /**< number of variables in the cover */
1407  SCIP_Bool* success /**< pointer to store whether a solution was found */
1408  )
1409 {
1410  SCIP* subscip;
1411  SCIP_RETCODE retcode;
1412 
1413  /* check whether there is enough time and memory left */
1414  SCIP_CALL( SCIPcheckCopyLimits(scip, success) );
1415 
1416  if( !(*success) )
1417  return SCIP_OKAY;
1418 
1419  /* create subproblem */
1420  SCIP_CALL( SCIPcreate(&subscip) );
1421 
1422  retcode = doSolveSubMIP(scip, subscip, heur, covervars, ncovervars, success);
1423 
1424  /* free sub-SCIP even if an error occurred during the subscip solve */
1425  SCIP_CALL( SCIPfree(&subscip) );
1426 
1427  SCIP_CALL( retcode );
1428 
1429  return SCIP_OKAY;
1430 }
1431 
1432 /* ---------------- Callback methods of event handler ---------------- */
1433 
1434 /* exec the event handler
1435  *
1436  * We update the number of variables fixed in the cover
1437  */
1438 static
1439 SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
1440 {
1441  SCIP_EVENTTYPE eventtype;
1442  SCIP_HEURDATA* heurdata;
1443  SCIP_VAR* var;
1444 
1445  SCIP_Real oldbound;
1446  SCIP_Real newbound;
1447  SCIP_Real otherbound;
1448 
1449  assert(eventhdlr != NULL);
1450  assert(eventdata != NULL);
1451  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1452  assert(event != NULL);
1453 
1454  heurdata = (SCIP_HEURDATA*)eventdata;
1455  assert(heurdata != NULL);
1456  assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1457 
1458  oldbound = SCIPeventGetOldbound(event);
1459  newbound = SCIPeventGetNewbound(event);
1460  var = SCIPeventGetVar(event);
1461 
1462  eventtype = SCIPeventGetType(event);
1463  otherbound = (eventtype & SCIP_EVENTTYPE_LBCHANGED) ? SCIPvarGetUbLocal(var) : SCIPvarGetLbLocal(var);
1464 
1465  switch( eventtype )
1466  {
1467  case SCIP_EVENTTYPE_LBTIGHTENED:
1468  case SCIP_EVENTTYPE_UBTIGHTENED:
1469  /* if cover variable is now fixed */
1470  if( SCIPisFeasEQ(scip, newbound, otherbound) && !SCIPisFeasEQ(scip, oldbound, otherbound) )
1471  {
1472  assert(!SCIPisEQ(scip, oldbound, otherbound));
1473  ++(heurdata->nfixedcovervars);
1474  }
1475  break;
1476  case SCIP_EVENTTYPE_LBRELAXED:
1477  case SCIP_EVENTTYPE_UBRELAXED:
1478  /* if cover variable is now unfixed */
1479  if( SCIPisFeasEQ(scip, oldbound, otherbound) && !SCIPisFeasEQ(scip, newbound, otherbound) )
1480  {
1481  assert(!SCIPisEQ(scip, newbound, otherbound));
1482  --(heurdata->nfixedcovervars);
1483  }
1484  break;
1485  default:
1486  SCIPerrorMessage("invalid event type.\n");
1487  return SCIP_INVALIDDATA;
1488  }
1489  assert(0 <= heurdata->nfixedcovervars && heurdata->nfixedcovervars <= SCIPgetNVars(scip));
1490 
1491  /* SCIPdebugMsg(scip, "changed bound of cover variable <%s> from %f to %f (nfixedcovervars: %d).\n", SCIPvarGetName(var),
1492  oldbound, newbound, heurdata->nfixedcovervars); */
1493 
1494  return SCIP_OKAY;
1495 }
1496 
1497 
1498 /*
1499  * Callback methods
1500  */
1501 
1502 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1503 static
1504 SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
1505 { /*lint --e{715}*/
1506  assert(scip != NULL);
1507  assert(heur != NULL);
1508  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1509 
1510  /* call inclusion method of primal heuristic */
1511  SCIP_CALL( SCIPincludeHeurNlpdiving(scip) );
1512 
1513  return SCIP_OKAY;
1514 }
1515 
1516 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1517 static
1518 SCIP_DECL_HEURFREE(heurFreeNlpdiving) /*lint --e{715}*/
1519 { /*lint --e{715}*/
1520  SCIP_HEURDATA* heurdata;
1521 
1522  assert(heur != NULL);
1523  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1524  assert(scip != NULL);
1525 
1526  /* free heuristic data */
1527  heurdata = SCIPheurGetData(heur);
1528  assert(heurdata != NULL);
1529  SCIPfreeBlockMemory(scip, &heurdata);
1530  SCIPheurSetData(heur, NULL);
1531 
1532  return SCIP_OKAY;
1533 }
1534 
1535 
1536 /** initialization method of primal heuristic (called after problem was transformed) */
1537 static
1538 SCIP_DECL_HEURINIT(heurInitNlpdiving) /*lint --e{715}*/
1539 { /*lint --e{715}*/
1540  SCIP_HEURDATA* heurdata;
1541 
1542  assert(heur != NULL);
1543  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1544 
1545  /* get heuristic data */
1546  heurdata = SCIPheurGetData(heur);
1547  assert(heurdata != NULL);
1548 
1549  /* create working solution */
1550  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
1551 
1552  /* create random number generator */
1553  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
1554 
1555  /* initialize data */
1556  heurdata->nnlpiterations = 0;
1557  heurdata->nsuccess = 0;
1558  heurdata->nfixedcovervars = 0;
1559  SCIPstatistic(
1560  heurdata->nnlpsolves = 0;
1561  heurdata->nfailcutoff = 0;
1562  heurdata->nfaildepth = 0;
1563  heurdata->nfailnlperror = 0;
1564  );
1565 
1566  return SCIP_OKAY;
1567 }
1568 
1569 
1570 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1571 static
1572 SCIP_DECL_HEUREXIT(heurExitNlpdiving) /*lint --e{715}*/
1573 { /*lint --e{715}*/
1574  SCIP_HEURDATA* heurdata;
1575 
1576  assert(heur != NULL);
1577  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1578 
1579  /* get heuristic data */
1580  heurdata = SCIPheurGetData(heur);
1581  assert(heurdata != NULL);
1582 
1583  /* free random number generator */
1584  SCIPfreeRandom(scip, &heurdata->randnumgen);
1585 
1586  /* free working solution */
1587  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
1588 
1589  SCIPstatistic(
1590  if( strstr(SCIPgetProbName(scip), "_covering") == NULL && SCIPheurGetNCalls(heur) > 0 )
1591  {
1592  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",
1593  SCIPgetProbName(scip), SCIPheurGetNSolsFound(heur), SCIPheurGetNCalls(heur), SCIPheurGetTime(heur),
1594  heurdata->nnlpiterations, heurdata->nnlpsolves, heurdata->nnlpiterations/MAX(1.0,(SCIP_Real)heurdata->nnlpsolves),
1595  (100*heurdata->nsuccess) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailcutoff) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfaildepth) / (int)SCIPheurGetNCalls(heur), (100*heurdata->nfailnlperror) / (int)SCIPheurGetNCalls(heur)
1596  );
1597  }
1598  );
1599 
1600  return SCIP_OKAY;
1601 }
1602 
1603 /** execution method of primal heuristic */
1604 static
1605 SCIP_DECL_HEUREXEC(heurExecNlpdiving)
1606 { /*lint --e{715}*/
1607  SCIP_HEURDATA* heurdata;
1608  SCIP_NLPSOLSTAT nlpsolstat;
1609  SCIP_LPSOLSTAT lpsolstat;
1610  SCIP_SOL* nlpstartsol;
1611  SCIP_SOL* bestsol;
1612  SCIP_VAR** nlpcands;
1613  SCIP_VAR** covervars;
1614  SCIP_Real* nlpcandssol;
1615  SCIP_Real* nlpcandsfrac;
1616  SCIP_Real* pseudocandslpsol;
1617  SCIP_Real* pseudocandsnlpsol;
1618  SCIP_HASHMAP* varincover;
1619  SCIP_Real searchubbound;
1620  SCIP_Real searchavgbound;
1621  SCIP_Real searchbound;
1622  SCIP_Real objval;
1623  SCIP_Real oldobjval;
1624  SCIP_Real fixquot;
1625  SCIP_Real bestboundval;
1626  SCIP_Bool bestcandmayround;
1627  SCIP_Bool bestcandroundup;
1628  SCIP_Bool nlperror;
1629  SCIP_Bool lperror;
1630  SCIP_Bool cutoff;
1631  SCIP_Bool backtracked;
1632  SCIP_Bool solvenlp;
1633  SCIP_Bool covercomputed;
1634  SCIP_Bool solvesubmip;
1635  SCIP_Longint ncalls;
1636  SCIP_Longint nsolsfound;
1637  int avgnnlpiterations;
1638  int maxnnlpiterations;
1639  int npseudocands;
1640  int nlpbranchcands;
1641  int ncovervars;
1642  int nnlpcands;
1643  int startnnlpcands;
1644  int depth;
1645  int maxdepth;
1646  int maxdivedepth;
1647  int divedepth;
1648  int lastnlpsolvedepth;
1649  int nfeasnlps;
1650  int bestcand;
1651  int c;
1652  int backtrackdepth; /* depth where to go when backtracking */
1653  SCIP_VAR* backtrackvar; /* (first) variable to fix differently in backtracking */
1654  SCIP_Real backtrackvarval; /* (fractional) value of backtrack variable */
1655  SCIP_Bool backtrackroundup; /* whether variable should be rounded up in backtracking */
1656 
1657  backtrackdepth = -1;
1658  backtrackvar = NULL;
1659  backtrackvarval = 0.0;
1660  backtrackroundup = FALSE;
1661  bestsol = NULL;
1662  pseudocandsnlpsol = NULL;
1663  pseudocandslpsol = NULL;
1664  covervars = NULL;
1665 
1666  assert(heur != NULL);
1667  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1668  assert(scip != NULL);
1669  assert(result != NULL);
1670  /* assert(SCIPhasCurrentNodeLP(scip)); */
1671 
1672  *result = SCIP_DIDNOTRUN;
1673 
1674  /* do not call heuristic of node was already detected to be infeasible */
1675  if( nodeinfeasible )
1676  return SCIP_OKAY;
1677 
1678  /* only call heuristic, if an NLP relaxation has been constructed */
1679  if( !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0 )
1680  return SCIP_OKAY;
1681 
1682  /* only call heuristic, if the current node will not be cutoff, e.g., due to a (integer and NLP-)feasible LP solution */
1683  if( SCIPisFeasGE(scip, SCIPgetLocalLowerbound(scip), SCIPgetUpperbound(scip)) )
1684  return SCIP_OKAY;
1685 
1686  /* get heuristic's data */
1687  heurdata = SCIPheurGetData(heur);
1688  assert(heurdata != NULL);
1689 
1690  /* do not call heuristic, if it barely succeded */
1691  if( (SCIPheurGetNSolsFound(heur) + 1.0) / (SCIP_Real)(SCIPheurGetNCalls(heur) + 1.0) < heurdata->minsuccquot )
1692  return SCIP_OKAY;
1693 
1694  *result = SCIP_DELAYED;
1695 
1696  /* don't dive two times at the same node */
1697  if( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
1698  return SCIP_OKAY;
1699 
1700  *result = SCIP_DIDNOTRUN;
1701 
1702  /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
1703  depth = SCIPgetDepth(scip);
1704  maxdepth = SCIPgetMaxDepth(scip);
1705  maxdepth = MAX(maxdepth, 30);
1706  if( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
1707  return SCIP_OKAY;
1708 
1709  /* calculate the maximal number of NLP iterations until heuristic is aborted
1710  * maximal number is maxnlpiterabs plus a success-depending multiplier of maxnlpiterrel
1711  */
1712  ncalls = SCIPheurGetNCalls(heur);
1713  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + heurdata->nsuccess;
1714  maxnnlpiterations = heurdata->maxnlpiterabs;
1715  maxnnlpiterations += (int)((1.0 + 10.0*(nsolsfound+1.0)/(ncalls+1.0)) * heurdata->maxnlpiterrel);
1716 
1717  /* don't try to dive, if we took too many NLP iterations during diving */
1718  if( heurdata->nnlpiterations >= maxnnlpiterations )
1719  return SCIP_OKAY;
1720 
1721  /* allow at least a bit more than the so far average number of NLP iterations per dive */
1722  avgnnlpiterations = (int)(heurdata->nnlpiterations / MAX(ncalls, 1.0));
1723  maxnnlpiterations = (int)MAX((SCIP_Real) maxnnlpiterations, (SCIP_Real) heurdata->nnlpiterations + 1.2*avgnnlpiterations);
1724 
1725  /* don't try to dive, if there are no unfixed discrete variables */
1726  SCIP_CALL( SCIPgetPseudoBranchCands(scip, NULL, &npseudocands, NULL) );
1727  if( npseudocands == 0 )
1728  return SCIP_OKAY;
1729 
1730  *result = SCIP_DIDNOTFIND;
1731 
1732  /* set starting point to lp solution */
1733  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, NULL) );
1734 
1735  /* solve NLP relaxation, if not solved already */
1736  nlpsolstat = SCIPgetNLPSolstat(scip);
1737  if( nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE )
1738  {
1739  SCIP_NLPSTATISTICS nlpstatistics;
1740 
1741  SCIP_CALL( SCIPsolveNLP(scip,
1742  .iterlimit = maxnnlpiterations - heurdata->nnlpiterations,
1743  .fastfail = heurdata->nlpfastfail ? SCIP_NLPPARAM_FASTFAIL_AGGRESSIVE : SCIP_NLPPARAM_FASTFAIL_CONSERVATIVE) ); /*lint !e666*/
1744  SCIPstatistic( ++heurdata->nnlpsolves );
1745 
1746  /* update iteration count */
1747  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR )
1748  {
1749  SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) );
1750  heurdata->nnlpiterations += nlpstatistics.niterations;
1751  }
1752 
1753  nlpsolstat = SCIPgetNLPSolstat(scip);
1754 
1755  /* give up, if no feasible solution found */
1756  if( nlpsolstat >= SCIP_NLPSOLSTAT_LOCINFEASIBLE )
1757  {
1758  SCIPdebugMsg(scip, "initial NLP infeasible or not solvable --> stop\n");
1759 
1760  SCIPstatistic(
1761  if( SCIPgetNLPTermstat(scip) < SCIP_NLPTERMSTAT_NUMERICERROR )
1762  heurdata->nfailcutoff++;
1763  else
1764  heurdata->nfailnlperror++;
1765  )
1766 
1767  return SCIP_OKAY;
1768  }
1769  }
1770 
1771  /* get NLP solution */
1772  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
1773 
1774  /* get fractional variables that should be integral */
1775  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
1776  assert(nnlpcands <= npseudocands);
1777 
1778  /* get LP candidates if LP solution is optimal */
1779  lpsolstat = SCIPgetLPSolstat(scip);
1780  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
1781  nlpbranchcands = SCIPgetNLPBranchCands(scip);
1782  else
1783  nlpbranchcands = 0;
1784 
1785  /* don't try to dive, if there are no fractional variables */
1786  if( nnlpcands == 0 )
1787  {
1788  SCIP_Bool success;
1789 
1790  /* check, if solution was feasible and good enough
1791  *
1792  * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
1793  * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
1794  * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
1795  */
1796 #ifdef SCIP_DEBUG
1797  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
1798 #else
1799  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
1800 #endif
1801  if( success )
1802  {
1803  SCIPdebugMsg(scip, " -> solution of first NLP was integral, feasible, and good enough\n");
1804  *result = SCIP_FOUNDSOL;
1805  }
1806 
1807  return SCIP_OKAY;
1808  }
1809 
1810  /* for guided diving: don't dive, if no feasible solutions exist */
1811  if( heurdata->varselrule == 'g' && SCIPgetNSols(scip) == 0 )
1812  return SCIP_OKAY;
1813 
1814  /* for guided diving: get best solution that should guide the search; if this solution lives in the original variable space,
1815  * we cannot use it since it might violate the global bounds of the current problem
1816  */
1817  if( heurdata->varselrule == 'g' && SCIPsolIsOriginal(SCIPgetBestSol(scip)) )
1818  return SCIP_OKAY;
1819 
1820  nlpstartsol = NULL;
1821  assert(nlpcandsfrac != NULL);
1822  assert(nlpcands != NULL);
1823  assert(nlpcandssol != NULL);
1824 
1825  /* save solution of first NLP, if we may use it later */
1826  if( heurdata->nlpstart != 'n' )
1827  {
1828  SCIP_CALL( SCIPcreateNLPSol(scip, &nlpstartsol, heur) );
1829  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
1830  }
1831 
1832  /* calculate the objective search bound */
1833  if( SCIPgetNSolsFound(scip) == 0 )
1834  {
1835  if( heurdata->maxdiveubquotnosol > 0.0 )
1836  searchubbound = SCIPgetLowerbound(scip)
1837  + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1838  else
1839  searchubbound = SCIPinfinity(scip);
1840  if( heurdata->maxdiveavgquotnosol > 0.0 )
1841  searchavgbound = SCIPgetLowerbound(scip)
1842  + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1843  else
1844  searchavgbound = SCIPinfinity(scip);
1845  }
1846  else
1847  {
1848  if( heurdata->maxdiveubquot > 0.0 )
1849  searchubbound = SCIPgetLowerbound(scip)
1850  + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
1851  else
1852  searchubbound = SCIPinfinity(scip);
1853  if( heurdata->maxdiveavgquot > 0.0 )
1854  searchavgbound = SCIPgetLowerbound(scip)
1855  + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
1856  else
1857  searchavgbound = SCIPinfinity(scip);
1858  }
1859  searchbound = MIN(searchubbound, searchavgbound);
1860  if( SCIPisObjIntegral(scip) )
1861  searchbound = SCIPceil(scip, searchbound);
1862 
1863  /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
1864  maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1865  maxdivedepth = MIN(maxdivedepth, maxdepth);
1866  maxdivedepth *= 10;
1867 
1868  covercomputed = FALSE;
1869  varincover = NULL;
1870 
1871  /* compute cover, if required */
1872  if( heurdata->prefercover || heurdata->solvesubmip )
1873  {
1874  SCIP_Real timelimit;
1875  SCIP_Real memorylimit;
1876 
1877  /* get limits */
1878  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1879  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1880  if( !SCIPisInfinity(scip, timelimit) )
1881  timelimit -= SCIPgetSolvingTime(scip);
1882 
1883  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1884  if( !SCIPisInfinity(scip, memorylimit) )
1885  {
1886  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1887  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1888  }
1889 
1890  /* compute cover */
1891  ncovervars = -1;
1892  SCIP_CALL( SCIPallocBufferArray(scip, &covervars, SCIPgetNVars(scip)) );
1893  if( memorylimit > 2.0*SCIPgetMemExternEstim(scip)/1048576.0 && timelimit > 0.05 )
1894  {
1895  SCIP_CALL( SCIPcomputeCoverUndercover(scip, &ncovervars, covervars, timelimit, memorylimit, SCIPinfinity(scip), FALSE, FALSE, FALSE, 'u', &covercomputed) );
1896  }
1897 
1898  if( covercomputed )
1899  {
1900  /* a cover can be empty, if the cover computation reveals that all nonlinear constraints are linear w.r.t. current variable fixations */
1901  assert(ncovervars >= 0);
1902 
1903  /* create hash map */
1904  SCIP_CALL( SCIPhashmapCreate(&varincover, SCIPblkmem(scip), ncovervars) );
1905 
1906  /* process variables in the cover */
1907  for( c = 0; c < ncovervars; c++ )
1908  {
1909  /* insert variable into hash map */
1910  if( SCIPvarGetType(covervars[c]) < SCIP_VARTYPE_IMPLINT )
1911  {
1912  assert(!SCIPhashmapExists(varincover, covervars[c]));
1913  SCIP_CALL( SCIPhashmapInsertInt(varincover, covervars[c], c+1) );
1914  }
1915 
1916  /* catch bound change events of cover variables */
1917  assert(heurdata->eventhdlr != NULL);
1918  SCIP_CALL( SCIPcatchVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr,
1919  (SCIP_EVENTDATA*) heurdata, NULL) );
1920  assert(!SCIPisFeasEQ(scip, SCIPvarGetLbLocal(covervars[c]), SCIPvarGetUbLocal(covervars[c])));
1921  }
1922  }
1923  }
1924  else
1925  {
1926  covervars = NULL;
1927  ncovervars = 0;
1928  }
1929 
1930  /* start diving */
1931  SCIP_CALL( SCIPstartProbing(scip) );
1932 
1933  /* enables collection of variable statistics during probing */
1934  SCIPenableVarHistory(scip);
1935 
1936  /* get NLP objective value*/
1937  objval = SCIPgetNLPObjval(scip);
1938 
1939  SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing nlpdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
1940  SCIPgetNNodes(scip), SCIPgetDepth(scip), nnlpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
1941 
1942  /* store a copy of the best solution, if guided diving should be used */
1943  if( heurdata->varselrule == 'g' )
1944  {
1945  assert(SCIPgetNSols(scip) > 0);
1946  assert(!SCIPsolIsOriginal(SCIPgetBestSol(scip)));
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_IMPLINT || 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  /* if covervar was implicit integer and fractional, then nlpsolval may be below lower bound now, so adjust to new bound */
2296  nlpsolval = MAX(nlpsolval, SCIPvarGetLbLocal(covervars[c])); /*lint !e666*/
2297  }
2298  if( SCIPisUbBetter(scip, nlpsolval, lb, ub) )
2299  {
2300  SCIP_CALL( SCIPchgVarUbProbing(scip, covervars[c], nlpsolval) );
2301  }
2302 
2303  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
2304  }
2305  }
2306  }
2307 
2308  /* solve sub-MIP or return to standard diving */
2309  if( cutoff )
2310  {
2311  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
2312  }
2313  else
2314  {
2315  SCIP_Bool success;
2316  success = FALSE;
2317 
2318  SCIP_CALL( solveSubMIP(scip, heur, covervars, ncovervars, &success));
2319  if( success )
2320  *result = SCIP_FOUNDSOL;
2321  backtracked = TRUE; /* to avoid backtracking */
2322  nnlpcands = 0; /* to force termination */
2323  cutoff = TRUE;
2324  }
2325  }
2326 
2327  /* resolve the diving LP */
2328  if( !cutoff && !lperror && (heurdata->lp || heurdata->varselrule == 'd')
2329  && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL && SCIPisLPSolBasic(scip) )
2330  {
2331  SCIP_CALL( SCIPsolveProbingLP(scip, 100, &lperror, &cutoff) );
2332 
2333  /* get LP solution status, objective value, and fractional variables, that should be integral */
2334  lpsolstat = SCIPgetLPSolstat(scip);
2335  assert(cutoff || (lpsolstat != SCIP_LPSOLSTAT_OBJLIMIT && lpsolstat != SCIP_LPSOLSTAT_INFEASIBLE &&
2336  (lpsolstat != SCIP_LPSOLSTAT_OPTIMAL || SCIPisLT(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))));
2337 
2338  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
2339  {
2340  nlpbranchcands = SCIPgetNLPBranchCands(scip);
2341 
2342  /* get new objective value */
2343  oldobjval = objval;
2344  objval = SCIPgetLPObjval(scip);
2345 
2346  /* update pseudo cost values */
2347  if( updatepscost && SCIPisGT(scip, objval, oldobjval) )
2348  {
2349  assert(frac != SCIP_INVALID); /*lint !e777*/
2350  if( bestcandroundup )
2351  {
2352  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 1.0-frac, objval - oldobjval, 1.0) );
2353  }
2354  else
2355  {
2356  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, 0.0-frac, objval - oldobjval, 1.0) );
2357  }
2358  }
2359  }
2360  else
2361  {
2362  nlpbranchcands = 0;
2363  }
2364 
2365  if( cutoff )
2366  {
2367  SCIPdebugMsg(scip, " *** cutoff detected in LP solving at level %d, lpsolstat = %d\n", SCIPgetProbingDepth(scip), lpsolstat);
2368  }
2369  }
2370  else
2371  lpsolstat = SCIP_LPSOLSTAT_NOTSOLVED;
2372 
2373  /* check whether we want to solve the NLP, which is the case if
2374  * - we are in backtracking, or
2375  * - we have (actively) fixed/rounded fixquot*nnlpcands variables
2376  * - all fractional variables were rounded/fixed (due to fixing and domain propagation)
2377  */
2378  solvenlp = backtracked;
2379  if( !solvenlp && !cutoff )
2380  {
2381  solvenlp = (lastnlpsolvedepth < divedepth - fixquot * nnlpcands);
2382  if( !solvenlp )
2383  {
2384  /* check if fractional NLP variables are left (some may have been fixed by propagation) */
2385  for( c = 0; c < nnlpcands; ++c )
2386  {
2387  var = nlpcands[c];
2388  if( SCIPisLT(scip, nlpcandssol[c], SCIPvarGetLbLocal(var)) || SCIPisGT(scip, nlpcandssol[c], SCIPvarGetUbLocal(var)) )
2389  continue;
2390  else
2391  break;
2392  }
2393  if( c == nnlpcands )
2394  solvenlp = TRUE;
2395  }
2396  }
2397 
2398  nlpsolstat = SCIP_NLPSOLSTAT_UNKNOWN;
2399 
2400  /* resolve the diving NLP */
2401  if( !cutoff && solvenlp )
2402  {
2403  SCIP_NLPTERMSTAT termstat;
2404  SCIP_NLPSTATISTICS nlpstatistics;
2405 
2406  /* set start solution, if we are in backtracking (previous NLP solve was infeasible) */
2407  if( heurdata->nlpstart != 'n' && backtracked )
2408  {
2409  assert(nlpstartsol != NULL);
2410 
2411  SCIPdebugMsg(scip, "setting NLP initial guess\n");
2412 
2413  SCIP_CALL( SCIPsetNLPInitialGuessSol(scip, nlpstartsol) );
2414  }
2415 
2416  /* solve NLP; allow at least MINNLPITER many iterations */
2417  SCIP_CALL( SCIPsolveNLP(scip,
2418  .iterlimit = MAX(maxnnlpiterations - heurdata->nnlpiterations, MINNLPITER)) ); /*lint !e666*/
2419  SCIPstatistic( ++heurdata->nnlpsolves );
2420 
2421  termstat = SCIPgetNLPTermstat(scip);
2422  if( termstat >= SCIP_NLPTERMSTAT_NUMERICERROR )
2423  {
2424  if( termstat >= SCIP_NLPTERMSTAT_LICENSEERROR )
2425  {
2426  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL,
2427  "Error while solving NLP in nlpdiving heuristic; NLP solve terminated with code <%d>\n", termstat);
2428  }
2429  nlperror = TRUE;
2430  break;
2431  }
2432 
2433  /* update iteration count */
2434  SCIP_CALL( SCIPgetNLPStatistics(scip, &nlpstatistics) );
2435  heurdata->nnlpiterations += nlpstatistics.niterations;
2436 
2437  /* get NLP solution status, objective value, and fractional variables, that should be integral */
2438  nlpsolstat = SCIPgetNLPSolstat(scip);
2439  cutoff = (nlpsolstat > SCIP_NLPSOLSTAT_FEASIBLE);
2440 
2441  if( cutoff )
2442  {
2443  SCIPdebugMsg(scip, " *** cutoff detected in NLP solving at level %d, nlpsolstat: %d\n", SCIPgetProbingDepth(scip), nlpsolstat);
2444  }
2445  else
2446  {
2447  SCIP_CALL( SCIPlinkNLPSol(scip, heurdata->sol) );
2448 
2449  /* remember that we have solve NLP on this depth successfully */
2450  lastnlpsolvedepth = divedepth;
2451  /* forget previous backtrack variable, we will never go back to a depth before the current one */
2452  backtrackdepth = -1;
2453  /* store NLP solution for warmstarting, if nlpstart is 'f' */
2454  if( heurdata->nlpstart == 'f' )
2455  {
2456  assert(nlpstartsol != NULL);
2457 
2458  /* copy NLP solution values into nlpstartsol, is there a better way to do this???? */
2459  SCIP_CALL( SCIPlinkNLPSol(scip, nlpstartsol) );
2460  SCIP_CALL( SCIPunlinkSol(scip, nlpstartsol) );
2461  }
2462  /* increase counter on number of NLP solves with feasible solution */
2463  ++nfeasnlps;
2464  }
2465  }
2466 
2467  /* perform backtracking if a cutoff was detected */
2468  if( cutoff && !backtracked && heurdata->backtrack )
2469  {
2470  if( backtrackdepth == -1 )
2471  {
2472  /* backtrack one step */
2473  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking one step\n", SCIPgetProbingDepth(scip));
2474  SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
2475 
2476  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2477  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2478 
2479  SCIP_CALL( SCIPnewProbingNode(scip) );
2480  }
2481  else
2482  {
2483  /* if we have a stored a depth for backtracking, go there */
2484  SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking to depth %d\n", SCIPgetProbingDepth(scip), backtrackdepth);
2485  SCIP_CALL( SCIPbacktrackProbing(scip, backtrackdepth-1) );
2486 
2487  /* after backtracking there has to be at least one open node without exceeding the maximal tree depth */
2488  assert(SCIP_MAXTREEDEPTH > SCIPgetDepth(scip));
2489 
2490  SCIP_CALL( SCIPnewProbingNode(scip) );
2491  divedepth = backtrackdepth;
2492 
2493  /* do not update pseudocosts if backtracking by more than one level */
2494  updatepscost = FALSE;
2495 
2496  /* in case, we are feasible after backtracking, fix less variables at once in continuing diving
2497  * @todo should we remember the fixquot in heurdata for the next run?
2498  */
2499  fixquot *= 0.5;
2500  }
2501  /* remember that we are backtracking now */
2502  backtracked = TRUE;
2503  }
2504  else
2505  backtracked = FALSE;
2506  }
2507  while( backtracked );
2508 
2509  if( !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2510  {
2511  /* get new fractional variables */
2512  SCIP_CALL( getNLPFracVars(scip, heurdata, &nlpcands, &nlpcandssol, &nlpcandsfrac, &nnlpcands) );
2513  }
2514  SCIPdebugMsg(scip, " -> nlpsolstat=%d, objval=%g/%g, nfrac nlp=%d lp=%d\n", nlpsolstat, objval, searchbound, nnlpcands, nlpbranchcands);
2515  }
2516 
2517  /*lint --e{774}*/
2518  SCIPdebugMsg(scip, "NLP nlpdiving ABORT due to ");
2519  if( nlperror || (nlpsolstat > SCIP_NLPSOLSTAT_LOCINFEASIBLE && nlpsolstat != SCIP_NLPSOLSTAT_UNKNOWN) )
2520  {
2521  SCIPdebugMsgPrint(scip, "NLP bad status - nlperror: %ud nlpsolstat: %d \n", nlperror, nlpsolstat);
2522  SCIPstatistic( heurdata->nfailnlperror++ );
2523  }
2524  else if( SCIPisStopped(scip) || cutoff )
2525  {
2526  SCIPdebugMsgPrint(scip, "LIMIT hit - stop: %ud cutoff: %ud \n", SCIPisStopped(scip), cutoff);
2527  SCIPstatistic( heurdata->nfailcutoff++ );
2528  }
2529  else if(! (divedepth < 10
2530  || nnlpcands <= startnnlpcands - divedepth/2
2531  || (divedepth < maxdivedepth && heurdata->nnlpiterations < maxnnlpiterations && objval < searchbound) ) )
2532  {
2533  SCIPdebugMsgPrint(scip, "TOO DEEP - divedepth: %4d cands halfed: %d ltmaxdepth: %d ltmaxiter: %d bound: %d\n", divedepth,
2534  (nnlpcands > startnnlpcands - divedepth/2), (divedepth >= maxdivedepth), (heurdata->nnlpiterations >= maxnnlpiterations),
2535  (objval >= searchbound));
2536  SCIPstatistic( heurdata->nfaildepth++ );
2537  }
2538  else if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2539  {
2540  SCIPdebugMsgPrint(scip, "SUCCESS\n");
2541  }
2542  else
2543  {
2544  SCIPdebugMsgPrint(scip, "UNKNOWN, very mysterical reason\n"); /* see also special case var == NULL (bestcand == -1) after choose*Var above */
2545  }
2546 
2547  /* check if a solution has been found */
2548  if( nnlpcands == 0 && !nlperror && !cutoff && nlpsolstat <= SCIP_NLPSOLSTAT_FEASIBLE )
2549  {
2550  SCIP_Bool success;
2551 
2552  /* create solution from diving NLP */
2553  SCIPdebugMsg(scip, "nlpdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
2554 
2555  /* try to add solution to SCIP
2556  *
2557  * Note that even if the NLP solver found a feasible solution it does not mean that is satisfy the integrality
2558  * conditions for fixed variables. This happens because the NLP solver uses relative tolerances for the bound
2559  * constraints but SCIP uses absolute tolerances for checking the integrality conditions.
2560  */
2561 #ifdef SCIP_DEBUG
2562  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, TRUE, TRUE, FALSE, TRUE, TRUE, &success) );
2563 #else
2564  SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, TRUE, TRUE, &success) );
2565 #endif
2566 
2567  /* check, if solution was feasible and good enough */
2568  if( success )
2569  {
2570  SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
2571  *result = SCIP_FOUNDSOL;
2572  }
2573  else
2574  {
2575  SCIPdebugMsg(scip, " -> solution was not accepted\n");
2576  }
2577  }
2578 
2579  /* end diving */
2580  SCIP_CALL( SCIPendProbing(scip) );
2581 
2582  /* free hash map and drop variable bound change events */
2583  if( covercomputed )
2584  {
2585  assert(heurdata->eventhdlr != NULL);
2586  assert(heurdata->nfixedcovervars >= 0); /* variables might have been globally fixed in propagation */
2587  assert(varincover != NULL);
2588  assert(covervars != NULL);
2589 
2590  SCIPhashmapFree(&varincover);
2591 
2592  /* drop bound change events of cover variables */
2593  for( c = 0; c < ncovervars; c++ )
2594  {
2595  SCIP_CALL( SCIPdropVarEvent(scip, covervars[c], SCIP_EVENTTYPE_BOUNDCHANGED, heurdata->eventhdlr, (SCIP_EVENTDATA*)heurdata, -1) );
2596  }
2597  }
2598  else
2599  assert(varincover == NULL);
2600 
2601  /* free NLP start solution */
2602  if( nlpstartsol != NULL )
2603  {
2604  SCIP_CALL( SCIPfreeSol(scip, &nlpstartsol) );
2605  }
2606 
2607  /* free copied best solution */
2608  if( heurdata->varselrule == 'g' )
2609  {
2610  assert(bestsol != NULL);
2611  SCIP_CALL( SCIPfreeSol(scip, &bestsol) );
2612  }
2613  else
2614  assert(bestsol == NULL);
2615 
2616  /* free arrays of LP and NLP solution */
2617  if( heurdata->varselrule == 'd' )
2618  {
2619  assert(pseudocandsnlpsol != NULL);
2620  assert(pseudocandsnlpsol != NULL);
2621  SCIPfreeBufferArray(scip, &pseudocandsnlpsol);
2622  SCIPfreeBufferArray(scip, &pseudocandslpsol);
2623  }
2624  else
2625  {
2626  assert(pseudocandsnlpsol == NULL);
2627  assert(pseudocandsnlpsol == NULL);
2628  }
2629 
2630  /* free array of cover variables */
2631  if( heurdata->prefercover || heurdata->solvesubmip )
2632  {
2633  assert(covervars != NULL || !covercomputed);
2634  if( covervars != NULL )
2635  SCIPfreeBufferArray(scip, &covervars);
2636  }
2637  else
2638  assert(covervars == NULL);
2639 
2640  if( *result == SCIP_FOUNDSOL )
2641  heurdata->nsuccess++;
2642 
2643  SCIPdebugMsg(scip, "nlpdiving heuristic finished\n");
2644 
2645  return SCIP_OKAY; /*lint !e438*/
2646 }
2647 
2648 
2649 /*
2650  * heuristic specific interface methods
2651  */
2652 
2653 /** creates the nlpdiving heuristic and includes it in SCIP */
2654 SCIP_RETCODE SCIPincludeHeurNlpdiving(
2655  SCIP* scip /**< SCIP data structure */
2656  )
2657 {
2658  SCIP_HEURDATA* heurdata;
2659  SCIP_HEUR* heur = NULL;
2660 
2661  /* create heuristic data */
2662  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2663 
2664  /* include heuristic */
2665  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
2666  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecNlpdiving, heurdata) );
2667 
2668  assert(heur != NULL);
2669  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyNlpdiving) );
2670  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeNlpdiving) );
2671  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitNlpdiving) );
2672  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitNlpdiving) );
2673 
2674  /* get event handler for bound change events */
2675  heurdata->eventhdlr = NULL;
2676  /* create event handler for bound change events */
2677  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &heurdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
2678  eventExecNlpdiving, NULL) );
2679  if ( heurdata->eventhdlr == NULL )
2680  {
2681  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
2682  return SCIP_PLUGINNOTFOUND;
2683  }
2684 
2685  /* nlpdiving heuristic parameters */
2686  SCIP_CALL( SCIPaddRealParam(scip,
2687  "heuristics/" HEUR_NAME "/minreldepth",
2688  "minimal relative depth to start diving",
2689  &heurdata->minreldepth, TRUE, DEFAULT_MINRELDEPTH, 0.0, 1.0, NULL, NULL) );
2690  SCIP_CALL( SCIPaddRealParam(scip,
2691  "heuristics/" HEUR_NAME "/maxreldepth",
2692  "maximal relative depth to start diving",
2693  &heurdata->maxreldepth, TRUE, DEFAULT_MAXRELDEPTH, 0.0, 1.0, NULL, NULL) );
2694  SCIP_CALL( SCIPaddIntParam(scip,
2695  "heuristics/" HEUR_NAME "/maxnlpiterabs",
2696  "minimial absolute number of allowed NLP iterations",
2697  &heurdata->maxnlpiterabs, FALSE, DEFAULT_MAXNLPITERABS, 0, INT_MAX, NULL, NULL) );
2698  SCIP_CALL( SCIPaddIntParam(scip,
2699  "heuristics/" HEUR_NAME "/maxnlpiterrel",
2700  "additional allowed number of NLP iterations relative to successfully found solutions",
2701  &heurdata->maxnlpiterrel, FALSE, DEFAULT_MAXNLPITERREL, 0, INT_MAX, NULL, NULL) );
2702  SCIP_CALL( SCIPaddRealParam(scip,
2703  "heuristics/" HEUR_NAME "/maxdiveubquot",
2704  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
2705  &heurdata->maxdiveubquot, TRUE, DEFAULT_MAXDIVEUBQUOT, 0.0, 1.0, NULL, NULL) );
2706  SCIP_CALL( SCIPaddRealParam(scip,
2707  "heuristics/" HEUR_NAME "/maxdiveavgquot",
2708  "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
2709  &heurdata->maxdiveavgquot, TRUE, DEFAULT_MAXDIVEAVGQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2710  SCIP_CALL( SCIPaddRealParam(scip,
2711  "heuristics/" HEUR_NAME "/maxdiveubquotnosol",
2712  "maximal UBQUOT when no solution was found yet (0.0: no limit)",
2713  &heurdata->maxdiveubquotnosol, TRUE, DEFAULT_MAXDIVEUBQUOTNOSOL, 0.0, 1.0, NULL, NULL) );
2714  SCIP_CALL( SCIPaddRealParam(scip,
2715  "heuristics/" HEUR_NAME "/maxdiveavgquotnosol",
2716  "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
2717  &heurdata->maxdiveavgquotnosol, TRUE, DEFAULT_MAXDIVEAVGQUOTNOSOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2718  SCIP_CALL( SCIPaddIntParam(scip,
2719  "heuristics/" HEUR_NAME "/maxfeasnlps",
2720  "maximal number of NLPs with feasible solution to solve during one dive",
2721  &heurdata->maxfeasnlps, FALSE, DEFAULT_MAXFEASNLPS, 1, INT_MAX, NULL, NULL) );
2722  SCIP_CALL( SCIPaddBoolParam(scip,
2723  "heuristics/" HEUR_NAME "/backtrack",
2724  "use one level of backtracking if infeasibility is encountered?",
2725  &heurdata->backtrack, FALSE, DEFAULT_BACKTRACK, NULL, NULL) );
2726  SCIP_CALL( SCIPaddBoolParam(scip,
2727  "heuristics/" HEUR_NAME "/lp",
2728  "should the LP relaxation be solved before the NLP relaxation?",
2729  &heurdata->lp, TRUE, DEFAULT_LP, NULL, NULL) );
2730  SCIP_CALL( SCIPaddBoolParam(scip,
2731  "heuristics/" HEUR_NAME "/preferlpfracs",
2732  "prefer variables that are also fractional in LP solution?",
2733  &heurdata->preferlpfracs, TRUE, DEFAULT_PREFERLPFRACS, NULL, NULL) );
2734  SCIP_CALL( SCIPaddRealParam(scip,
2735  "heuristics/" HEUR_NAME "/minsuccquot",
2736  "heuristic will not run if less then this percentage of calls succeeded (0.0: no limit)",
2737  &heurdata->minsuccquot, FALSE, DEFAULT_MINSUCCQUOT, 0.0, 1.0, NULL, NULL) );
2738  SCIP_CALL( SCIPaddRealParam(scip,
2739  "heuristics/" HEUR_NAME "/fixquot",
2740  "percentage of fractional variables that should be fixed before the next NLP solve",
2741  &heurdata->fixquot, FALSE, DEFAULT_FIXQUOT, 0.0, 1.0, NULL, NULL) );
2742  SCIP_CALL( SCIPaddBoolParam(scip,
2743  "heuristics/" HEUR_NAME "/prefercover",
2744  "should variables in a minimal cover be preferred?",
2745  &heurdata->prefercover, FALSE, DEFAULT_PREFERCOVER, NULL, NULL) );
2746  SCIP_CALL( SCIPaddBoolParam(scip,
2747  "heuristics/" HEUR_NAME "/solvesubmip",
2748  "should a sub-MIP be solved if all cover variables are fixed?",
2749  &heurdata->solvesubmip, FALSE, DEFAULT_SOLVESUBMIP, NULL, NULL) );
2750  SCIP_CALL( SCIPaddBoolParam(scip,
2751  "heuristics/" HEUR_NAME "/nlpfastfail",
2752  "should the NLP solver stop early if it converges slow?",
2753  &heurdata->nlpfastfail, FALSE, DEFAULT_NLPFASTFAIL, NULL, NULL) );
2754  SCIP_CALL( SCIPaddCharParam(scip,
2755  "heuristics/" HEUR_NAME "/nlpstart",
2756  "which point should be used as starting point for the NLP solver? ('n'one, last 'f'easible, from dive's'tart)",
2757  &heurdata->nlpstart, TRUE, DEFAULT_NLPSTART, "fns", NULL, NULL) );
2758  SCIP_CALL( SCIPaddCharParam(scip,
2759  "heuristics/" HEUR_NAME "/varselrule",
2760  "which variable selection should be used? ('f'ractionality, 'c'oefficient, 'p'seudocost, 'g'uided, 'd'ouble, 'v'eclen)",
2761  &heurdata->varselrule, FALSE, DEFAULT_VARSELRULE, "fcpgdv", NULL, NULL) );
2762 
2763  return SCIP_OKAY;
2764 }
HEUR_FREQOFS
#define HEUR_FREQOFS
Definition: heur_nlpdiving.c:64
SCIPsolIsOriginal
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2521
SCIPfreeRandom
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
SCIP_DECL_HEUREXIT
static SCIP_DECL_HEUREXIT(heurExitNlpdiving)
Definition: heur_nlpdiving.c:1576
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
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:1220
SCIP_DIDNOTRUN
Definition: type_result.h:33
HEUR_NAME
#define HEUR_NAME
Definition: heur_nlpdiving.c:59
SCIP_FOUNDSOL
Definition: type_result.h:47
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
SCIPsetSeparating
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:949
SCIP_NLPTERMSTAT
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:185
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip_numerics.c:158
SCIP_NLPPARAM_FASTFAIL_AGGRESSIVE
Definition: type_nlpi.h:51
heur_nlpdiving.h
NLP diving heuristic that chooses fixings w.r.t. the fractionalities.
DEFAULT_BACKTRACK
#define DEFAULT_BACKTRACK
Definition: heur_nlpdiving.c:93
SCIP_DELAYED
Definition: type_result.h:34
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_NLPSOLSTAT_LOCINFEASIBLE
Definition: type_nlpi.h:154
DEFAULT_RANDSEED
#define DEFAULT_RANDSEED
Definition: heur_nlpdiving.c:105
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
scip_param.h
public methods for SCIP parameter handling
SCIPvarGetNLocksDownType
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIPbacktrackProbing
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
scip_nodesel.h
public methods for node selector plugins
DEFAULT_MAXFEASNLPS
#define DEFAULT_MAXFEASNLPS
Definition: heur_nlpdiving.c:91
scip_mem.h
public methods for memory management
SCIPcatchVarEvent
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIPgetProbingDepth
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
SCIPgetCutoffbound
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip_solvingstats.c:1576
SCIPisUbBetter
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1136
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
HEUR_TIMING
#define HEUR_TIMING
Definition: heur_nlpdiving.c:66
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIPvarGetNLocksUpType
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
SCIPgetVarPseudocostVal
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8811
DEFAULT_NLPSTART
#define DEFAULT_NLPSTART
Definition: heur_nlpdiving.c:98
SCIPheurGetNBestSolsFound
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
SCIPgetNSolsFound
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip_solvingstats.c:1731
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:416
SCIPsetHeurExit
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
scip_solve.h
public solving methods
DEFAULT_MAXDIVEAVGQUOT
#define DEFAULT_MAXDIVEAVGQUOT
Definition: heur_nlpdiving.c:85
DEFAULT_MAXDIVEAVGQUOTNOSOL
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
Definition: heur_nlpdiving.c:89
SCIPincludeEventhdlrBasic
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
scip_timing.h
public methods for timing
SCIPgetNLPSolstat
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition: scip_nlp.c:532
SCIP_Var
Definition: struct_var.h:198
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
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:240
SCIPvarGetRootSol
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13349
SCIP_NlpStatistics::niterations
int niterations
Definition: type_nlpi.h:190
SCIPgetMaxDepth
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip_solvingstats.c:1193
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:897
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
heur_undercover.h
Undercover primal heuristic for MINLPs.
SCIPgetSols
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
FALSE
#define FALSE
Definition: def.h:87
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_MAXDIVEUBQUOT
Definition: heur_nlpdiving.c:82
SCIPeventhdlrGetName
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
SCIPcopyLimits
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
TRUE
#define TRUE
Definition: def.h:86
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIPgetLocalLowerbound
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
Definition: scip_prob.c:3584
SCIPstatisticMessage
#define SCIPstatisticMessage
Definition: pub_message.h:114
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIPsetPresolving
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIPhashmapInsertInt
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIP_RandNumGen
Definition: struct_misc.h:259
SCIPfindBranchrule
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
SCIPgetAvgLowerbound
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
Definition: scip_solvingstats.c:1315
SCIP_HEURDATA
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
pub_var.h
public methods for problem variables
DEFAULT_MINRELDEPTH
#define DEFAULT_MINRELDEPTH
Definition: heur_nlpdiving.c:78
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
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_heur.c:108
SCIP_NLPTERMSTAT_LICENSEERROR
Definition: type_nlpi.h:172
SCIPrandomGetInt
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
SCIPchgVarLbProbing
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
DEFAULT_MAXRELDEPTH
#define DEFAULT_MAXRELDEPTH
Definition: heur_nlpdiving.c:79
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_LPSOLSTAT
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
SCIPheurSetData
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
DEFAULT_VARSELRULE
#define DEFAULT_VARSELRULE
Definition: heur_nlpdiving.c:99
DEFAULT_SOLVESUBMIP
#define DEFAULT_SOLVESUBMIP
Definition: heur_nlpdiving.c:97
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:37
scip_var.h
public methods for SCIP variables
SCIP_EVENTTYPE_BOUNDCHANGED
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:116
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:69
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_param.c:74
MINNLPITER
#define MINNLPITER
Definition: heur_nlpdiving.c:107
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:910
SCIP_NLPSOLSTAT_UNKNOWN
Definition: type_nlpi.h:157
scip_numerics.h
public methods for numerical tolerances
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:1069
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:898
SCIP_EVENTTYPE_LBCHANGED
#define SCIP_EVENTTYPE_LBCHANGED
Definition: type_event.h:112
scip_solvingstats.h
public methods for querying solving statistics
SCIP_Sol
Definition: struct_sol.h:64
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
SCIPhashmapExists
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_EVENTTYPE_LBRELAXED
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:69
SCIPupdateVarPseudocost
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8777
scip_tree.h
public methods for the branch-and-bound tree
SCIPlinkNLPSol
SCIP_RETCODE SCIPlinkNLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1043
SCIPgetNNlpis
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
SCIPisLbBetter
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip_numerics.c:1121
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:658
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
scip_nlpi.h
public methods for NLPI solver interfaces
SCIP_HashMap
Definition: struct_misc.h:128
SCIPeventGetNewbound
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1233
SCIPcreateSolCopy
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:609
SCIPgetNLPTermstat
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition: scip_nlp.c:554
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:165
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
SCIP_NLPSOLSTAT_FEASIBLE
Definition: type_nlpi.h:153
SCIPheurGetName
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_NlpStatistics
Definition: type_nlpi.h:188
SCIPisParamFixed
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:54
SCIPsetHeurFree
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_NLPTERMSTAT_NUMERICERROR
Definition: type_nlpi.h:169
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIPpropagateProbing
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_NLPSOLSTAT
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:159
scip_event.h
public methods for event handler plugins and event handlers
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
SCIPgetDualbound
SCIP_Real SCIPgetDualbound(SCIP *scip)
Definition: scip_solvingstats.c:1339
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIPendProbing
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
SCIP_EVENTDATA
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIPsetNLPInitialGuessSol
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_nlp.c:459
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:775
SCIP_EVENTTYPE_UBRELAXED
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:71
SCIP_OKAY
Definition: type_retcode.h:33
scip_copy.h
public methods for problem copies
pub_sol.h
public methods for primal CIP solutions
HEUR_PRIORITY
#define HEUR_PRIORITY
Definition: heur_nlpdiving.c:62
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:384
SCIPgetLowerbound
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip_solvingstats.c:1366
SCIP_EVENTTYPE_LBTIGHTENED
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:68
SCIP_NLPPARAM_FASTFAIL_CONSERVATIVE
Definition: type_nlpi.h:50
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIPsolveProbingLP
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
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:3310
DEFAULT_MAXNLPITERREL
#define DEFAULT_MAXNLPITERREL
Definition: heur_nlpdiving.c:81
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
EVENTHDLR_NAME
#define EVENTHDLR_NAME
Definition: heur_nlpdiving.c:70
SCIPheurGetNCalls
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1567
SCIP_PROBINGSCORE_PENALTYRATIO
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition: def.h:326
SCIPgetPseudoBranchCands
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
SCIP_Heur
Definition: struct_heur.h:88
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
scip_heur.h
public methods for primal heuristic plugins and divesets
SCIPgetLastDivenode
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition: scip_lp.c:2730
solveSubMIP
static SCIP_RETCODE solveSubMIP(SCIP *scip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1406
SCIP_DECL_HEUREXEC
static SCIP_DECL_HEUREXEC(heurExecNlpdiving)
Definition: heur_nlpdiving.c:1609
SCIPcreateRandom
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
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 threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2951
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIPsetSolVal
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
pub_misc.h
public data structures and miscellaneous methods
SCIPeventGetVar
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1044
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
SCIPgetNLPStatistics
SCIP_RETCODE SCIPgetNLPStatistics(SCIP *scip, SCIP_NLPSTATISTICS *statistics)
Definition: scip_nlp.c:579
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
HEUR_MAXDEPTH
#define HEUR_MAXDEPTH
Definition: heur_nlpdiving.c:65
SCIPeventGetType
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
SCIProundSol
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
SCIPsetObjlimit
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1421
SCIPvarGetNLPSol
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:18297
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_VERBLEVEL_MINIMAL
Definition: type_message.h:43
MAX
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_DECL_HEURFREE
static SCIP_DECL_HEURFREE(heurFreeNlpdiving)
Definition: heur_nlpdiving.c:1522
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_sol.c:3231
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXDIVEUBQUOTNOSOL
Definition: heur_nlpdiving.c:88
SCIPfreeSol
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIPenableVarHistory
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8738
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIPdropVarEvent
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
SCIP_DECL_EVENTEXEC
static SCIP_DECL_EVENTEXEC(eventExecNlpdiving)
Definition: heur_nlpdiving.c:1443
SCIPgetNSols
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
SCIP_EVENTTYPE_UBTIGHTENED
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:70
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:514
HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP
Definition: heur_nlpdiving.c:67
SCIP_DECL_HEURINIT
static SCIP_DECL_HEURINIT(heurInitNlpdiving)
Definition: heur_nlpdiving.c:1542
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_sol.c:3125
SCIP_MAXTREEDEPTH
#define SCIP_MAXTREEDEPTH
Definition: def.h:320
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
scip_lp.h
public methods for the LP relaxation, rows and columns
SCIPsetCharParam
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:652
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:178
scip_nlp.h
public methods for nonlinear relaxation
DEFAULT_PREFERLPFRACS
#define DEFAULT_PREFERLPFRACS
Definition: heur_nlpdiving.c:95
scip_branch.h
public methods for branching rule plugins and branching
SCIPincludeHeurNlpdiving
SCIP_RETCODE SCIPincludeHeurNlpdiving(SCIP *scip)
Definition: heur_nlpdiving.c:2658
SCIPisObjIntegral
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition: scip_prob.c:1561
pub_event.h
public methods for managing events
scip_general.h
general public methods
SCIPcreateNLPSol
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:389
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
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:510
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_param.c:158
HEUR_DESC
#define HEUR_DESC
Definition: heur_nlpdiving.c:60
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:695
scip_sol.h
public methods for solutions
SCIPgetMemUsed
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
scip_randnumgen.h
public methods for random numbers
DEFAULT_FIXQUOT
#define DEFAULT_FIXQUOT
Definition: heur_nlpdiving.c:92
scip_probing.h
public methods for the probing mode
pub_message.h
public methods for message output
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_heur.c:185
SCIPretransformObj
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1567
SCIPeventGetOldbound
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1209
SCIP_LOCKTYPE_MODEL
Definition: type_var.h:84
SCIPgetMemExternEstim
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:117
SCIPfindNodesel
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
SCIPgetNLPFracVars
SCIP_RETCODE SCIPgetNLPFracVars(SCIP *scip, SCIP_VAR ***fracvars, SCIP_Real **fracvarssol, SCIP_Real **fracvarsfrac, int *nfracvars, int *npriofracvars)
Definition: scip_nlp.c:654
SCIPstatistic
#define SCIPstatistic(x)
Definition: pub_message.h:111
SCIP_Real
#define SCIP_Real
Definition: def.h:177
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
DEFAULT_PREFERCOVER
#define DEFAULT_PREFERCOVER
Definition: heur_nlpdiving.c:96
EVENTHDLR_DESC
#define EVENTHDLR_DESC
Definition: heur_nlpdiving.c:71
scip_message.h
public methods for message handling
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:197
SCIP_Longint
#define SCIP_Longint
Definition: def.h:162
SCIPheurGetNSolsFound
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1577
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
SCIPunlinkSol
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1181
SCIPfrac
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:660
SCIPcheckCopyLimits
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:35
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
HEUR_FREQ
#define HEUR_FREQ
Definition: heur_nlpdiving.c:63
DEFAULT_MAXNLPITERABS
#define DEFAULT_MAXNLPITERABS
Definition: heur_nlpdiving.c:80
subsol
static DPSUBSOL ** subsol
Definition: dptermsinterns.h:148
SCIPsetSolVals
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIPgetNLPObjval
SCIP_Real SCIPgetNLPObjval(SCIP *scip)
Definition: scip_nlp.c:603
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIPsetHeurCopy
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:33
SCIPnewProbingNode
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:874
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip_numerics.c:144
SCIPgetUpperbound
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip_solvingstats.c:1546
SCIPstartProbing
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
pub_heur.h
public methods for primal heuristics
SCIPallocBlockMemory
SCIPallocBlockMemory(scip, subsol))
SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:53
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIP_CALL_ABORT
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:636
SCIPheurGetData
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
SCIPsolveNLP
#define SCIPsolveNLP(...)
Definition: scip_nlp.h:331
SCIP_DECL_HEURCOPY
static SCIP_DECL_HEURCOPY(heurCopyNlpdiving)
Definition: heur_nlpdiving.c:1508
SCIPheurGetTime
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1629
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip_solvingstats.c:203
scip_prob.h
public methods for global and local (sub)problems
SCIPchgVarUbProbing
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
doSolveSubMIP
static SCIP_RETCODE doSolveSubMIP(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **covervars, int ncovervars, SCIP_Bool *success)
Definition: heur_nlpdiving.c:1269
HEUR_DISPCHAR
#define HEUR_DISPCHAR
Definition: heur_nlpdiving.c:61
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_param.c:130
SCIPsetSubscipsOff
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIPvarMayRoundUp
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3445
SCIPsetLongintParam
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
SCIP_Eventhdlr
Definition: struct_event.h:195
SCIPvarMayRoundDown
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3434
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_param.c:48
DEFAULT_MINSUCCQUOT
#define DEFAULT_MINSUCCQUOT
Definition: heur_nlpdiving.c:90
DEFAULT_LP
#define DEFAULT_LP
Definition: heur_nlpdiving.c:94
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
SCIPcreateSol
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
DEFAULT_NLPFASTFAIL
#define DEFAULT_NLPFASTFAIL
Definition: heur_nlpdiving.c:104
SCIP_EVENTTYPE
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
memory.h
memory allocation routines