Scippy

SCIP

Solving Constraint Integer Programs

heur_dins.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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_dins.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief DINS primal heuristic (according to Ghosh)
19  * @author Timo Berthold
20  * @author Robert Waniek
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "blockmemshell/memory.h"
26 #include "scip/cons_linear.h"
27 #include "scip/heur_dins.h"
28 #include "scip/heuristics.h"
29 #include "scip/pub_event.h"
30 #include "scip/pub_heur.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc.h"
33 #include "scip/pub_var.h"
34 #include "scip/scip_branch.h"
35 #include "scip/scip_cons.h"
36 #include "scip/scip_copy.h"
37 #include "scip/scip_event.h"
38 #include "scip/scip_general.h"
39 #include "scip/scip_heur.h"
40 #include "scip/scip_lp.h"
41 #include "scip/scip_mem.h"
42 #include "scip/scip_message.h"
43 #include "scip/scip_nodesel.h"
44 #include "scip/scip_numerics.h"
45 #include "scip/scip_param.h"
46 #include "scip/scip_prob.h"
47 #include "scip/scip_sol.h"
48 #include "scip/scip_solve.h"
49 #include "scip/scip_solvingstats.h"
50 #include "scip/scip_var.h"
51 #include <string.h>
52 
53 #define HEUR_NAME "dins"
54 #define HEUR_DESC "distance induced neighborhood search by Ghosh"
55 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
56 #define HEUR_PRIORITY -1105000
57 #define HEUR_FREQ -1
58 #define HEUR_FREQOFS 0
59 #define HEUR_MAXDEPTH -1
60 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
61 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
62 
63 #define DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */
64 #define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */
65 #define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */
66 #define DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */
67 #define DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */
68 #define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */
69 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */
70 #define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */
71 #define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */
72 #define DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */
73 #define DEFAULT_USELPROWS FALSE /* should subproblem be created out of the rows in the LP rows,
74  * otherwise, the copy constructors of the constraints handlers are used */
75 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
76  * of the original scip be copied to constraints of the subscip */
77 
78 #define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */
79 #define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */
80 
81 
82 /* event handler properties */
83 #define EVENTHDLR_NAME "Dins"
84 #define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
85 
86 /*
87  * Data structures
88  */
89 
90 /** DINS primal heuristic data */
91 struct SCIP_HeurData
92 {
93  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
94  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
95  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
96  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
97  SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
98  SCIP_Real minimprove; /**< factor by which DINS should at least improve the incumbent */
99  SCIP_Longint usednodes; /**< nodes already used by DINS in earlier calls */
100  SCIP_Longint lastnsolsfound; /**< total number of found solutions at previous execution of DINS */
101  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
102  SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
103  SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
104  int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */
105  SCIP_Bool* delta; /**< stores whether a variable kept its value from root LP all the time */
106  int deltalength; /**< if there are no binary variables, we need no flag array */
107  int solnum; /**< number of pool-solutions to be checked for flag array update */
108  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
109  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
110  * to constraints in subproblem?
111  */
112  int bestsollimit; /**< limit on number of improving incumbent solutions in sub-CIP */
113  SCIP_Bool useuct; /**< should uct node selection be used at the beginning of the search? */
114 };
115 
116 
117 /*
118  * Local methods
119  */
120 
121 /** compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ */
122 static
124  SCIP* scip, /**< SCIP data structure of the original problem */
125  SCIP_VAR* var, /**< the variable for which bounds should be computed */
126  SCIP_Real* lbptr, /**< pointer to store the lower bound in the DINS sub-SCIP */
127  SCIP_Real* ubptr /**< pointer to store the upper bound in the DINS sub-SCIP */
128  )
129 {
130  SCIP_Real mipsol;
131  SCIP_Real lpsol;
132 
133  SCIP_Real lbglobal;
134  SCIP_Real ubglobal;
135  SCIP_SOL* bestsol;
136 
137  /* get the bounds for each variable */
138  lbglobal = SCIPvarGetLbGlobal(var);
139  ubglobal = SCIPvarGetUbGlobal(var);
140 
141  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
142  /* get the current LP solution for each variable */
143  lpsol = SCIPvarGetLPSol(var);
144 
145  /* get the current MIP solution for each variable */
146  bestsol = SCIPgetBestSol(scip);
147  mipsol = SCIPgetSolVal(scip, bestsol, var);
148 
149  /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
150  if( REALABS(lpsol - mipsol) >= 0.5 )
151  {
152  SCIP_Real range;
153 
154  *lbptr = lbglobal;
155  *ubptr = ubglobal;
156 
157  /* create a equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
158  range = 2*lpsol-mipsol;
159 
160  if( mipsol >= lpsol )
161  {
162  range = SCIPfeasCeil(scip, range);
163  *lbptr = MAX(*lbptr, range);
164 
165  /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
166  if( SCIPisFeasEQ(scip, mipsol, *lbptr) )
167  *ubptr = *lbptr;
168  else
169  *ubptr = mipsol;
170  }
171  else
172  {
173  range = SCIPfeasFloor(scip, range);
174  *ubptr = MIN(*ubptr, range);
175 
176  /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
177  if( SCIPisFeasEQ(scip, mipsol, *ubptr) )
178  *lbptr = *ubptr;
179  else
180  *lbptr = mipsol;
181  }
182 
183  /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
184  *lbptr = MAX(*lbptr, lbglobal);
185  *ubptr = MIN(*ubptr, ubglobal);
186  }
187  else
188  {
189  /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
190  *lbptr = MAX(mipsol, lbglobal);
191  *ubptr = MIN(mipsol, ubglobal);
192  }
193 }
194 
195 /** creates a subproblem for subscip by fixing a number of variables */
196 static
198  SCIP* scip, /**< SCIP data structure of the original problem */
199  SCIP_HEUR* heur, /**< DINS heuristic structure */
200  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
201  SCIP_VAR** vars, /**< variables of the original problem */
202  SCIP_VAR** fixedvars, /**< array to store variables that should be fixed in the sub-SCIP */
203  SCIP_Real* fixedvals, /**< array to store fixing values for fixed variables */
204  int nbinvars, /**< number of binary variables of problem and subproblem */
205  int nintvars, /**< number of general integer variables of problem and subproblem */
206  int* binfixings, /**< pointer to store number of binary variables that should be fixed */
207  int* intfixings /**< pointer to store number of integer variables that should be fixed */
208  )
209 {
210  SCIP_SOL* bestsol;
211  SCIP_SOL** sols;
212  SCIP_Bool* delta;
213  int i;
214  int nsols;
215  SCIP_Longint nsolsfound;
216  int checklength;
217  int nfixedvars;
218 
219  assert(scip != NULL);
220  assert(vars != NULL);
221  assert(fixedvars != NULL);
222  assert(fixedvals != NULL);
223  assert(binfixings != NULL);
224  assert(intfixings != NULL);
225  assert(heur != NULL);
226 
227  /* get the best MIP-solution known so far */
228  bestsol = SCIPgetBestSol(scip);
229  assert(bestsol != NULL);
230 
231  /* get solution pool and number of solutions in pool */
232  sols = SCIPgetSols(scip);
233  nsols = SCIPgetNSols(scip);
234  nsolsfound = SCIPgetNSolsFound(scip);
235  checklength = MIN(nsols, heurdata->solnum);
236  assert(sols != NULL);
237  assert(nsols > 0);
238 
239  /* if new binary variables have been created, e.g., due to column generation, reallocate the delta array */
240  if( heurdata->deltalength < nbinvars )
241  {
242  int newsize;
243 
244  newsize = SCIPcalcMemGrowSize(scip, nbinvars);
245  assert(newsize >= nbinvars);
246 
247  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->delta, heurdata->deltalength, newsize) );
248 
249  /* initialize new part of delta array */
250  for( i = heurdata->deltalength; i < newsize; i++ )
251  heurdata->delta[i] = TRUE;
252 
253  heurdata->deltalength = newsize;
254  }
255 
256  delta = heurdata->delta;
257  /* fixing for binary variables */
258  /* hard fixing for some with mipsol(s)=lpsolval=rootlpsolval and preparation for soft fixing for the remaining */
259  nfixedvars = 0;
260  *intfixings = *binfixings = 0;
261  for( i = 0; i < nbinvars; i++ )
262  {
263  SCIP_Real lpsolval;
264  SCIP_Real mipsolval;
265  SCIP_Real rootlpsolval;
266  int j;
267 
268  /* get the current LP solution for each variable */
269  lpsolval = SCIPvarGetLPSol(vars[i]);
270  /* get the current MIP solution for each variable */
271  mipsolval = SCIPgetSolVal(scip, bestsol, vars[i]);
272  /* get the root LP solution for each variable */
273  rootlpsolval = SCIPvarGetRootSol(vars[i]);
274 
275  if( SCIPisFeasEQ(scip, lpsolval, mipsolval) && SCIPisFeasEQ(scip, mipsolval, rootlpsolval) )
276  {
277  /* update delta */
278  if( nsols > 1 && heurdata->lastnsolsfound != nsolsfound && delta[i] ) /* no need to update delta[i] if already FALSE */
279  {
280  /* no need to update delta[i] if already FALSE or sols[i] already checked on previous run or worse than DINS-solution of last run */
281  for( j = 1; delta[i] && j < checklength && SCIPgetSolHeur(scip, sols[j]) != heur ; j++ )
282  {
283  SCIP_Real solval;
284  solval = SCIPgetSolVal(scip, sols[j], vars[i]);
285  delta[i] = delta[i] && SCIPisFeasEQ(scip, mipsolval, solval);
286  }
287  }
288 
289  /* hard fixing if rootlpsolval=nodelpsolval=mipsolval(s) and delta (is TRUE) */
290  if( delta[i] )
291  {
292  fixedvars[nfixedvars] = vars[i];
293  fixedvals[nfixedvars] = mipsolval;
294  ++nfixedvars;
295  }
296  }
297  }
298 
299  *binfixings = nfixedvars;
300 
301  /* store the number of found solutions for next run */
302  heurdata->lastnsolsfound = nsolsfound;
303 
304  /* compute a tighter bound for the variable in the subproblem; */
305  for( i = nbinvars; i < nbinvars + nintvars; ++i )
306  {
307  SCIP_Real lb;
308  SCIP_Real ub;
309  computeIntegerVariableBounds(scip, vars[i], &lb, &ub);
310 
311  /* hard fixing if heuristic bounds coincide */
312  if( ub - lb < 0.5 )
313  {
314  fixedvars[(nfixedvars)] = vars[i];
315  fixedvals[(nfixedvars)] = lb;
316  ++nfixedvars;
317  }
318  }
319 
320  *intfixings = nfixedvars - *binfixings;
321 
322  return SCIP_OKAY;
323 }
324 
325 /** creates a subproblem for subscip by fixing a number of variables */
326 static
328  SCIP* scip, /**< SCIP data structure of the original problem */
329  SCIP* subscip, /**< SCIP data structure of the subproblem */
330  SCIP_VAR** vars, /**< variables of the original problem */
331  SCIP_VAR** subvars, /**< variables of the DINS sub-SCIP */
332  int nbinvars, /**< number of binary variables of problem and subproblem */
333  int nintvars /**< number of general integer variables of problem and subproblem */
334  )
335 {
336  int i;
337  /* compute a tighter bound for the variable in the subproblem; */
338  for( i = nbinvars; i < nbinvars + nintvars; ++i )
339  {
340  SCIP_Real lb;
341  SCIP_Real ub;
342 
343  if( subvars[i] == NULL )
344  continue;
345 
346  computeIntegerVariableBounds(scip, vars[i], &lb, &ub);
347 
348  /* change variable bounds in the DINS subproblem; if bounds coincide, variable should already be fixed */
349  if( ub - lb >= 0.5 )
350  {
351  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
352  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
353  }
354  else
355  {
356  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(subvars[i]), SCIPvarGetUbGlobal(subvars[i])));
357  }
358  }
359 
360  return SCIP_OKAY;
361 }
362 
363 /** create the extra constraint of local branching and add it to subscip */
364 static
366  SCIP* scip, /**< SCIP data structure of the original problem */
367  SCIP* subscip, /**< SCIP data structure of the subproblem */
368  SCIP_VAR** subvars, /**< variables of the subproblem */
369  SCIP_HEURDATA* heurdata /**< heuristic's data structure */
370  )
371 {
372  SCIP_CONS* cons; /* local branching constraint to create */
373  SCIP_VAR** vars;
374  SCIP_SOL* bestsol;
375 
376  SCIP_VAR** consvars;
377  SCIP_Real* consvals;
378  SCIP_Real solval;
379  SCIP_Real lhs;
380  SCIP_Real rhs;
381 
382  char consname[SCIP_MAXSTRLEN];
383 
384  int nbinvars;
385  int i;
386  int nconsvars;
387 
388  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_dinsLBcons", SCIPgetProbName(scip));
389 
390  /* get the data of the variables and the best solution */
391  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) );
392  bestsol = SCIPgetBestSol(scip);
393  assert(bestsol != NULL);
394 
395  /* memory allocation */
396  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
397  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
398  nconsvars = 0;
399 
400  /* set initial left and right hand sides of local branching constraint */
401  lhs = 0.0;
402  rhs = (SCIP_Real) heurdata->neighborhoodsize;
403 
404  /* create the distance function of the binary variables (to incumbent solution) */
405  for( i = 0; i < nbinvars; i++ )
406  {
407  if( subvars[i] == NULL )
408  continue;
409 
410  assert(SCIPvarGetType(subvars[i]) == SCIP_VARTYPE_BINARY);
411  if( SCIPvarGetUbGlobal(subvars[i]) - SCIPvarGetLbGlobal(subvars[i]) < 0.5 )
412  continue;
413 
414  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
415  assert(SCIPisFeasIntegral(scip, solval));
416 
417  /* is variable i part of the binary support of the current solution? */
418  if( SCIPisFeasEQ(scip, solval, 1.0) )
419  {
420  consvals[nconsvars] = -1.0;
421  rhs -= 1.0;
422  lhs -= 1.0;
423  }
424  else
425  consvals[nconsvars] = 1.0;
426  consvars[nconsvars++] = subvars[i];
427  }
428 
429  /* creates local branching constraint and adds it to subscip */
430  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nconsvars, consvars, consvals,
431  lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
432  SCIP_CALL( SCIPaddCons(subscip, cons) );
433  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
434 
435  /* free local memory */
436  SCIPfreeBufferArray(scip, &consvars);
437  SCIPfreeBufferArray(scip, &consvals);
438 
439  return SCIP_OKAY;
440 }
441 
442 static
443 SCIP_DECL_EVENTEXEC(eventExecDins);
444 
445 /** wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks */
446 static
448  SCIP* scip, /**< original SCIP data structure */
449  SCIP* subscip, /**< SCIP structure of the subproblem */
450  SCIP_HEUR* heur, /**< Heuristic pointer */
451  SCIP_HEURDATA* heurdata, /**< Heuristic's data */
452  SCIP_VAR** vars, /**< original problem's variables */
453  SCIP_VAR** fixedvars, /**< Fixed variables of original SCIP */
454  SCIP_Real* fixedvals, /**< Fixed values of original SCIP */
455  SCIP_RESULT* result, /**< Result pointer */
456  int nvars, /**< Number of variables */
457  int nbinvars, /**< Number of binary variables in original SCIP */
458  int nintvars, /**< Number of integer variables in original SCIP */
459  int binfixings, /**< Number of binary fixing in original SCIP */
460  int intfixings, /**< Number of integer fixings in original SCIP */
461  SCIP_Longint nsubnodes /**< Number of nodes in the subscip */
462  )
463 {
464  SCIP_VAR** subvars; /* variables of the subscip */
465  SCIP_HASHMAP* varmapfw; /* hashmap for mapping between vars of scip and subscip */
466  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
467  SCIP_Real upperbound; /* upperbound of the original SCIP */
468  SCIP_Real cutoff; /* objective cutoff for the subproblem */
469 
470  SCIP_Bool success;
471 
472  int i;
473  int nsubsols;
474 
475  /* create the variable mapping hash map */
476  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
477  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
478 
479  success = FALSE;
480  eventhdlr = NULL;
481 
482  /* create a problem copy as sub SCIP */
483  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "dins", fixedvars, fixedvals, binfixings + intfixings,
484  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
485 
486  /* create event handler for LP events */
487  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecDins, NULL) );
488  if( eventhdlr == NULL )
489  {
490  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
491  return SCIP_PLUGINNOTFOUND;
492  }
493 
494  SCIPdebugMsg(scip, "Copying the SCIP instance was %ssuccessful.\n", success ? "" : "not ");
495 
496  SCIPdebugMsg(scip, "DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n",
497  SCIPgetNVars(subscip), SCIPgetNBinVars(subscip) , SCIPgetNIntVars(subscip) , SCIPgetNConss(subscip));
498 
499  /* store subproblem variables that correspond to original variables */
500  for( i = 0; i < nvars; i++ )
501  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
502 
503  /* free hash map */
504  SCIPhashmapFree(&varmapfw);
505 
506  /* perform prepared softfixing for all unfixed vars if the number of unfixed vars is larger than the neighborhoodsize (otherwise it will be useless) */
507  if( nbinvars - binfixings > heurdata->neighborhoodsize )
508  {
509  SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata) );
510  }
511 
512  /* rebound integer variables if not all were fixed */
513  if( intfixings < nintvars )
514  {
515  assert(nintvars > 0);
516  SCIP_CALL( reboundIntegerVariables(scip, subscip, vars, subvars, nbinvars, nintvars) );
517  }
518 
519  /* do not abort subproblem on CTRL-C */
520  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
521 
522 #ifdef SCIP_DEBUG
523  /* for debugging, enable full output */
524  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
525  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
526 #else
527  /* disable statistic timing inside sub SCIP and output to console */
528  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
529  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
530 #endif
531 
532  /* set limits for the subproblem */
533  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
534  heurdata->nodelimit = nsubnodes;
535  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
536  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nsubnodes/10)) );
537  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
538 
539  /* forbid recursive call of heuristics and separators solving subMIPs */
540  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
541 
542  /* disable cutting plane separation */
544 
545  /* disable expensive presolving */
547 
548  /* use best estimate node selection */
549  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
550  {
551  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
552  }
553 
554  /* activate uct node selection at the top of the tree */
555  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
556  {
557  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
558  }
559 
560  /* use inference branching */
561  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
562  {
563  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
564  }
565 
566  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
567  if( !SCIPisParamFixed(subscip, "conflict/enable") )
568  {
569  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
570  }
571  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
572  {
573  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
574  }
575  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
576  {
577  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
578  }
579 
580  /* speed up sub-SCIP by not checking dual LP feasibility */
581  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
582 
583  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
584  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
585  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
586  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
587  * made for the original SCIP
588  */
589  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
590  {
591  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
592  }
593 
594  /* add an objective cutoff */
595  assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
596 
597  if( !SCIPisInfinity(scip, -1.0*SCIPgetLowerbound(scip)) )
598  {
599  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
600  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
601  cutoff = MIN(upperbound, cutoff);
602  }
603  else
604  {
605  if( SCIPgetUpperbound(scip) >= 0 )
606  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
607  else
608  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
609  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
610  cutoff = MIN(upperbound, cutoff);
611  }
612  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
613 
614  /* catch LP events of sub-SCIP */
615  if( !heurdata->uselprows )
616  {
617  assert(eventhdlr != NULL);
618 
619  SCIP_CALL( SCIPtransformProb(subscip) );
620  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
621  }
622 
623  /* solve the subproblem */
624  SCIPdebugMsg(scip, "solving DINS sub-MIP with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n", heurdata->neighborhoodsize, nsubnodes);
625 
626  /* Errors in solving the subproblem should not kill the overall solving process
627  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
628  */
629  SCIP_CALL_ABORT( SCIPsolve(subscip) );
630 
631  /* drop LP events of sub-SCIP */
632  if( !heurdata->uselprows )
633  {
634  assert(eventhdlr != NULL);
635 
636  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
637  }
638 
639  /* print solving statistics of subproblem if we are in SCIP's debug mode */
641 
642  heurdata->usednodes += SCIPgetNNodes(subscip);
643  nsubsols = SCIPgetNSols(subscip);
644  SCIPdebugMsg(scip, "DINS used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes and found %d solutions\n", SCIPgetNNodes(subscip), nsubnodes, nsubsols);
645 
646  /* check, whether a (new) solution was found */
647  if( nsubsols > 0 )
648  {
649  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
650  SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) );
651  if( success )
652  {
653  SCIPdebugMsg(scip, "DINS successfully found new solution\n");
654  *result = SCIP_FOUNDSOL;
655  }
656  }
657 
658  /* free subproblem */
659  SCIPfreeBufferArray(scip, &subvars);
660 
661  return SCIP_OKAY;
662 }
663 
664 
665 /* ---------------- Callback methods of event handler ---------------- */
666 
667 /* exec the event handler
668  *
669  * we interrupt the solution process
670  */
671 static
672 SCIP_DECL_EVENTEXEC(eventExecDins)
673 {
674  SCIP_HEURDATA* heurdata;
675 
676  assert(eventhdlr != NULL);
677  assert(eventdata != NULL);
678  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
679  assert(event != NULL);
680  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
681 
682  heurdata = (SCIP_HEURDATA*)eventdata;
683  assert(heurdata != NULL);
684 
685  /* interrupt solution process of sub-SCIP */
686  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
687  {
688  SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
690  }
691 
692  return SCIP_OKAY;
693 }
694 
695 
696 /*
697  * Callback methods of primal heuristic
698  */
699 
700 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
701 static
702 SCIP_DECL_HEURCOPY(heurCopyDins)
703 { /*lint --e{715}*/
704  assert(scip != NULL);
705  assert(heur != NULL);
706  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
707 
708  /* call inclusion method of primal heuristic */
710 
711  return SCIP_OKAY;
712 }
713 
714 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
715 static
716 SCIP_DECL_HEURFREE(heurFreeDins)
717 { /*lint --e{715}*/
718  SCIP_HEURDATA* heurdata;
719 
720  assert(heur != NULL);
721  assert(scip != NULL);
722 
723  /* get heuristic data */
724  heurdata = SCIPheurGetData(heur);
725  assert(heurdata != NULL);
726 
727  /* free heuristic data */
728  SCIPfreeBlockMemory(scip, &heurdata);
729  SCIPheurSetData(heur, NULL);
730 
731  return SCIP_OKAY;
732 }
733 
734 
735 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
736 static
737 SCIP_DECL_HEURINITSOL(heurInitsolDins)
738 {
739  SCIP_HEURDATA* heurdata;
740  int i;
741 
742  assert(heur != NULL);
743  assert(scip != NULL);
744 
745  /* get heuristic's data */
746  heurdata = SCIPheurGetData(heur);
747  assert(heurdata != NULL);
748 
749  /* initialize data */
750  heurdata->usednodes = 0;
751  heurdata->lastnsolsfound = 0;
752 
753  /* create flag array */
754  heurdata->deltalength = SCIPgetNBinVars(scip);
755 
756  /* no binvars => no flag array needed */
757  if( heurdata->deltalength > 0 )
758  {
759  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength) );
760  for( i = 0; i < heurdata->deltalength; i++ )
761  heurdata->delta[i] = TRUE;
762  }
763  return SCIP_OKAY;
764 }
765 
766 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
767 static
768 SCIP_DECL_HEUREXITSOL(heurExitsolDins)
769 { /*lint --e{715}*/
770  SCIP_HEURDATA* heurdata;
771 
772  assert(heur != NULL);
773  assert(scip != NULL);
774 
775  /* get heuristic data */
776  heurdata = SCIPheurGetData(heur);
777  assert(heurdata != NULL);
778 
779  /* free flag array if exist */
780  if( heurdata->deltalength > 0 )
781  {
782  SCIPfreeBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength);
783  }
784  return SCIP_OKAY;
785 }
786 
787 /** execution method of primal heuristic */
788 static
789 SCIP_DECL_HEUREXEC(heurExecDins)
790 { /*lint --e{715}*/
791  SCIP_HEURDATA* heurdata;
792  SCIP* subscip; /* the subproblem created by DINS */
793  SCIP_VAR** vars; /* variables of the original problem */
794  SCIP_VAR** fixedvars;
795  SCIP_Real* fixedvals;
796 
797  SCIP_Longint maxnnodes; /* maximum number of subnodes */
798  SCIP_Longint nsubnodes; /* nodelimit for subscip */
799 
800  SCIP_RETCODE retcode;
801 
802  int nvars; /* number of variables in original SCIP */
803  int nbinvars; /* number of binary variables in original SCIP */
804  int nintvars; /* number of general integer variables in original SCIP */
805  int binfixings;
806  int intfixings;
807 
808  SCIP_Bool success; /* used to store whether new solution was found or not */
809 
810  assert(heur != NULL);
811  assert(scip != NULL);
812  assert(result != NULL);
813  assert(SCIPhasCurrentNodeLP(scip));
814 
815  *result = SCIP_DELAYED;
816 
817  /* do not call heuristic of node was already detected to be infeasible */
818  if( nodeinfeasible )
819  return SCIP_OKAY;
820 
821  /* only call heuristic, if a CIP solution is at hand */
822  if( SCIPgetNSols(scip) <= 0 )
823  return SCIP_OKAY;
824 
825  /* only call heuristic, if an optimal LP solution is at hand */
827  return SCIP_OKAY;
828 
829  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
831  return SCIP_OKAY;
832 
833  /* get heuristic's data */
834  heurdata = SCIPheurGetData(heur);
835  assert(heurdata != NULL);
836 
837  /* only call heuristic, if enough nodes were processed since last incumbent */
838  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
839  return SCIP_OKAY;
840 
841  *result = SCIP_DIDNOTRUN;
842 
843  /* determine the node limit for the current process */
844  maxnnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
845 
846  /* reward DINS if it succeeded often */
847  maxnnodes = (SCIP_Longint) (maxnnodes * (1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0) / (SCIPheurGetNCalls(heur) + 1.0)));
848 
849  /* count the setup costs for the sub-MIP as 100 nodes */
850  maxnnodes -= 100 * SCIPheurGetNCalls(heur);
851  maxnnodes += heurdata->nodesofs;
852 
853  /* determine the node limit for the current process */
854  nsubnodes = maxnnodes - heurdata->usednodes;
855  nsubnodes = MIN(nsubnodes , heurdata->maxnodes);
856 
857  /* check whether we have enough nodes left to call sub problem solving */
858  if( nsubnodes < heurdata->minnodes )
859  return SCIP_OKAY;
860 
861  if( SCIPisStopped(scip) )
862  return SCIP_OKAY;
863 
864  /* get required data of the original problem */
865  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
866  assert(nbinvars <= nvars);
867 
868  /* do not run heuristic if only continuous variables are present */
869  if( nbinvars == 0 && nintvars == 0 )
870  return SCIP_OKAY;
871 
872  /* check whether there is enough time and memory left */
873  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
874 
875  /* abort if no time is left or not enough memory to create a copy of SCIP */
876  if( !success )
877  return SCIP_OKAY;
878 
879  assert(vars != NULL);
880 
881  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
882  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
883 
884  /* collect variables that should be fixed in the DINS subproblem */
885  binfixings = intfixings = 0;
886  SCIP_CALL( determineVariableFixings(scip, heur, heurdata, vars, fixedvars, fixedvals, nbinvars, nintvars, &binfixings, &intfixings) );
887 
888  /* abort, if all integer variables were fixed (which should not happen for MIP),
889  * but frequently happens for MINLPs using an LP relaxation */
890  if( binfixings + intfixings == nbinvars + nintvars )
891  goto TERMINATE;
892 
893  /* abort, if the amount of fixed variables is insufficient */
894  if( (binfixings + intfixings) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)) < heurdata->minfixingrate )
895  goto TERMINATE;
896 
897  *result = SCIP_DIDNOTFIND;
898 
899  /* initialize the subproblem */
900  SCIP_CALL( SCIPcreate(&subscip) );
901 
902  retcode = wrapperDins(scip, subscip, heur, heurdata, vars, fixedvars, fixedvals, result, nvars, nbinvars, nintvars, binfixings, intfixings, nsubnodes);
903  SCIP_CALL( SCIPfree(&subscip) );
904 
905  SCIP_CALL( retcode );
906 
907  TERMINATE:
908  SCIPfreeBufferArray(scip, &fixedvals);
909  SCIPfreeBufferArray(scip, &fixedvars);
910 
911  return SCIP_OKAY;
912 }
913 
914 
915 /*
916  * primal heuristic specific interface methods
917  */
918 
919 /** creates the DINS primal heuristic and includes it in SCIP */
921  SCIP* scip /**< SCIP data structure */
922  )
923 {
924  SCIP_HEURDATA* heurdata;
925  SCIP_HEUR* heur;
926 
927  /* create Dins primal heuristic data */
928  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
929 
930  /* include primal heuristic */
931  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
933  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDins, heurdata) );
934 
935  assert(heur != NULL);
936 
937  /* set non-NULL pointers to callback methods */
938  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyDins) );
939  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDins) );
940  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDins) );
941  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDins) );
942 
943  /* add DINS primal heuristic parameters */
944  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
945  "number of nodes added to the contingent of the total nodes",
946  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
947  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
948  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
949  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
950  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
951  "minimum number of nodes required to start the subproblem",
952  &heurdata->minnodes, FALSE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
953  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solnum",
954  "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)",
955  &heurdata->solnum, FALSE, DEFAULT_SOLNUM, 1, INT_MAX, NULL, NULL) );
956  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
957  "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
958  &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
959  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
960  "maximum number of nodes to regard in the subproblem",
961  &heurdata->maxnodes,TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
962  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
963  "factor by which " HEUR_NAME " should at least improve the incumbent",
964  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
965  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
966  "number of nodes without incumbent change that heuristic should wait",
967  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
968 
969  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
970  "factor by which the limit on the number of LP depends on the node limit",
971  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
972 
973  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
974  "minimum percentage of integer variables that have to be fixable",
975  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
976 
977  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
978  "should subproblem be created out of the rows in the LP rows?",
979  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
980 
981  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
982  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
983  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
984 
985  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
986  "should uct node selection be used at the beginning of the search?",
987  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
988 
989  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
990  "limit on number of improving incumbent solutions in sub-CIP",
991  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
992 
993  return SCIP_OKAY;
994 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:92
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
SCIP_Real SCIPsumepsilon(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for SCIP parameter handling
#define DEFAULT_LPLIMFAC
Definition: heur_dins.c:68
static SCIP_RETCODE wrapperDins(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, SCIP_RESULT *result, int nvars, int nbinvars, int nintvars, int binfixings, int intfixings, SCIP_Longint nsubnodes)
Definition: heur_dins.c:447
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_FREQ
Definition: heur_dins.c:57
public methods for node selector plugins
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define EVENTHDLR_NAME
Definition: heur_dins.c:83
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3407
#define SCIP_MAXSTRLEN
Definition: def.h:273
#define DEFAULT_NODESOFS
Definition: heur_dins.c:63
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18041
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
public solving methods
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:357
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nbinvars, int nintvars, int *binfixings, int *intfixings)
Definition: heur_dins.c:197
#define EVENTHDLR_DESC
Definition: heur_dins.c:84
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1396
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
#define FALSE
Definition: def.h:73
#define DEFAULT_MAXNODES
Definition: heur_dins.c:64
#define DEFAULT_MINFIXINGRATE
Definition: heur_dins.c:69
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
methods commonly used by primal heuristics
#define HEUR_DISPCHAR
Definition: heur_dins.c:55
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
static SCIP_DECL_HEURFREE(heurFreeDins)
Definition: heur_dins.c:716
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:899
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define SCIP_LONGINT_MAX
Definition: def.h:149
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3192
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
static SCIP_DECL_HEURINITSOL(heurInitsolDins)
Definition: heur_dins.c:737
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeHeurDins(SCIP *scip)
Definition: heur_dins.c:920
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2076
public methods for numerical tolerances
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:916
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1420
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
SCIP_EXPORT SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:13119
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
#define SCIPerrorMessage
Definition: pub_message.h:55
#define HEUR_NAME
Definition: heur_dins.c:53
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
public methods for event handler plugins and event handlers
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
#define DEFAULT_NEIGHBORHOODSIZE
Definition: heur_dins.c:71
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
static SCIP_DECL_HEUREXITSOL(heurExitsolDins)
Definition: heur_dins.c:768
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
#define DEFAULT_NODESQUOT
Definition: heur_dins.c:67
#define REALABS(x)
Definition: def.h:187
public methods for problem copies
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:948
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:677
#define HEUR_FREQOFS
Definition: heur_dins.c:58
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_HEUR * SCIPgetSolHeur(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1676
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1649
static SCIP_DECL_HEURCOPY(heurCopyDins)
Definition: heur_dins.c:702
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
public data structures and miscellaneous methods
#define DEFAULT_BESTSOLLIMIT
Definition: heur_dins.c:78
#define SCIP_Bool
Definition: def.h:70
#define DEFAULT_MINNODES
Definition: heur_dins.c:65
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
#define DEFAULT_USELPROWS
Definition: heur_dins.c:73
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
static void computeIntegerVariableBounds(SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr)
Definition: heur_dins.c:123
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_RETCODE reboundIntegerVariables(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, int nbinvars, int nintvars)
Definition: heur_dins.c:327
#define DEFAULT_COPYCUTS
Definition: heur_dins.c:75
#define HEUR_PRIORITY
Definition: heur_dins.c:56
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4943
Constraint handler for linear constraints in their most general form, .
static SCIP_DECL_HEUREXEC(heurExecDins)
Definition: heur_dins.c:789
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3228
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
public methods for the LP relaxation, rows and columns
#define SCIP_REAL_MAX
Definition: def.h:164
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:561
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata)
Definition: heur_dins.c:365
public methods for branching rule plugins and branching
DINS primal heuristic.
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5030
#define DEFAULT_SOLNUM
Definition: heur_dins.c:72
public methods for managing events
#define HEUR_TIMING
Definition: heur_dins.c:60
general public methods
#define DEFAULT_MINIMPROVE
Definition: heur_dins.c:66
public methods for solutions
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2255
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10604
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define SCIP_Real
Definition: def.h:163
public methods for message handling
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:445
#define HEUR_MAXDEPTH
Definition: heur_dins.c:59
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
#define DEFAULT_NWAITINGNODES
Definition: heur_dins.c:70
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for primal heuristics
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
public methods for global and local (sub)problems
#define DEFAULT_USEUCT
Definition: heur_dins.c:79
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
#define HEUR_DESC
Definition: heur_dins.c:54
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:503
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:974
static SCIP_DECL_EVENTEXEC(eventExecDins)
Definition: heur_dins.c:672
#define HEUR_USESSUBSCIP
Definition: heur_dins.c:61
memory allocation routines