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