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