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