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 
460 /* ---------------- Callback methods of event handler ---------------- */
461 
462 /* exec the event handler
463  *
464  * we interrupt the solution process
465  */
466 static
467 SCIP_DECL_EVENTEXEC(eventExecDins)
468 {
469  SCIP_HEURDATA* heurdata;
470 
471  assert(eventhdlr != NULL);
472  assert(eventdata != NULL);
473  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
474  assert(event != NULL);
475  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
476 
477  heurdata = (SCIP_HEURDATA*)eventdata;
478  assert(heurdata != NULL);
479 
480  /* interrupt solution process of sub-SCIP */
481  if( SCIPgetNLPs(scip) > heurdata->lplimfac * heurdata->nodelimit )
482  {
483  SCIPdebugMsg(scip, "interrupt after %" SCIP_LONGINT_FORMAT " LPs\n",SCIPgetNLPs(scip));
485  }
486 
487  return SCIP_OKAY;
488 }
489 
490 
491 /*
492  * Callback methods of primal heuristic
493  */
494 
495 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
496 static
497 SCIP_DECL_HEURCOPY(heurCopyDins)
498 { /*lint --e{715}*/
499  assert(scip != NULL);
500  assert(heur != NULL);
501  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
502 
503  /* call inclusion method of primal heuristic */
505 
506  return SCIP_OKAY;
507 }
508 
509 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
510 static
511 SCIP_DECL_HEURFREE(heurFreeDins)
512 { /*lint --e{715}*/
513  SCIP_HEURDATA* heurdata;
514 
515  assert(heur != NULL);
516  assert(scip != NULL);
517 
518  /* get heuristic data */
519  heurdata = SCIPheurGetData(heur);
520  assert(heurdata != NULL);
521 
522  /* free heuristic data */
523  SCIPfreeBlockMemory(scip, &heurdata);
524  SCIPheurSetData(heur, NULL);
525 
526  return SCIP_OKAY;
527 }
528 
529 
530 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
531 static
532 SCIP_DECL_HEURINITSOL(heurInitsolDins)
533 {
534  SCIP_HEURDATA* heurdata;
535  int i;
536 
537  assert(heur != NULL);
538  assert(scip != NULL);
539 
540  /* get heuristic's data */
541  heurdata = SCIPheurGetData(heur);
542  assert(heurdata != NULL);
543 
544  /* initialize data */
545  heurdata->usednodes = 0;
546  heurdata->lastnsolsfound = 0;
547 
548  /* create flag array */
549  heurdata->deltalength = SCIPgetNBinVars(scip);
550 
551  /* no binvars => no flag array needed */
552  if( heurdata->deltalength > 0 )
553  {
554  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength) );
555  for( i = 0; i < heurdata->deltalength; i++ )
556  heurdata->delta[i] = TRUE;
557  }
558  return SCIP_OKAY;
559 }
560 
561 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
562 static
563 SCIP_DECL_HEUREXITSOL(heurExitsolDins)
564 { /*lint --e{715}*/
565  SCIP_HEURDATA* heurdata;
566 
567  assert(heur != NULL);
568  assert(scip != NULL);
569 
570  /* get heuristic data */
571  heurdata = SCIPheurGetData(heur);
572  assert(heurdata != NULL);
573 
574  /* free flag array if exist */
575  if( heurdata->deltalength > 0 )
576  {
577  SCIPfreeBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength);
578  }
579  return SCIP_OKAY;
580 }
581 
582 /** execution method of primal heuristic */
583 static
584 SCIP_DECL_HEUREXEC(heurExecDins)
585 { /*lint --e{715}*/
586  SCIP_HEURDATA* heurdata;
587  SCIP* subscip; /* the subproblem created by DINS */
588  SCIP_VAR** subvars; /* subproblem's variables */
589  SCIP_VAR** vars; /* variables of the original problem */
590  SCIP_VAR** fixedvars;
591  SCIP_Real* fixedvals;
592 
593  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
594  SCIP_EVENTHDLR* eventhdlr; /* event handler for LP events */
595 
596  SCIP_Longint maxnnodes; /* maximum number of subnodes */
597  SCIP_Longint nsubnodes; /* nodelimit for subscip */
598 
599  SCIP_Real cutoff; /* objective cutoff for the subproblem */
600  SCIP_Real upperbound;
601  int nvars; /* number of variables in original SCIP */
602  int nbinvars; /* number of binary variables in original SCIP */
603  int nintvars; /* number of general integer variables in original SCIP */
604  int nsubsols;
605  int binfixings;
606  int intfixings;
607  int i;
608 
609  SCIP_Bool success; /* used to store whether new solution was found or not */
610 
611  assert(heur != NULL);
612  assert(scip != NULL);
613  assert(result != NULL);
614  assert(SCIPhasCurrentNodeLP(scip));
615 
616  *result = SCIP_DELAYED;
617 
618  /* do not call heuristic of node was already detected to be infeasible */
619  if( nodeinfeasible )
620  return SCIP_OKAY;
621 
622  /* only call heuristic, if a CIP solution is at hand */
623  if( SCIPgetNSols(scip) <= 0 )
624  return SCIP_OKAY;
625 
626  /* only call heuristic, if an optimal LP solution is at hand */
628  return SCIP_OKAY;
629 
630  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
632  return SCIP_OKAY;
633 
634  /* get heuristic's data */
635  heurdata = SCIPheurGetData(heur);
636  assert(heurdata != NULL);
637 
638  /* only call heuristic, if enough nodes were processed since last incumbent */
639  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
640  return SCIP_OKAY;
641 
642  *result = SCIP_DIDNOTRUN;
643 
644  /* determine the node limit for the current process */
645  maxnnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
646 
647  /* reward DINS if it succeeded often */
648  maxnnodes = (SCIP_Longint) (maxnnodes * (1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0) / (SCIPheurGetNCalls(heur) + 1.0)));
649 
650  /* count the setup costs for the sub-MIP as 100 nodes */
651  maxnnodes -= 100 * SCIPheurGetNCalls(heur);
652  maxnnodes += heurdata->nodesofs;
653 
654  /* determine the node limit for the current process */
655  nsubnodes = maxnnodes - heurdata->usednodes;
656  nsubnodes = MIN(nsubnodes , heurdata->maxnodes);
657 
658  /* check whether we have enough nodes left to call sub problem solving */
659  if( nsubnodes < heurdata->minnodes )
660  return SCIP_OKAY;
661 
662  if( SCIPisStopped(scip) )
663  return SCIP_OKAY;
664 
665  /* get required data of the original problem */
666  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
667  assert(nbinvars <= nvars);
668 
669  /* do not run heuristic if only continuous variables are present */
670  if( nbinvars == 0 && nintvars == 0 )
671  return SCIP_OKAY;
672 
673  /* check whether there is enough time and memory left */
674  SCIP_CALL( SCIPcheckCopyLimits(scip, &success) );
675 
676  /* abort if no time is left or not enough memory to create a copy of SCIP */
677  if( !success )
678  return SCIP_OKAY;
679 
680  assert(vars != NULL);
681 
682  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvars, nbinvars + nintvars) );
683  SCIP_CALL( SCIPallocBufferArray(scip, &fixedvals, nbinvars + nintvars) );
684 
685  /* collect variables that should be fixed in the DINS subproblem */
686  binfixings = intfixings = 0;
687  SCIP_CALL( determineVariableFixings(scip, heur, heurdata, vars, fixedvars, fixedvals, nbinvars, nintvars, &binfixings, &intfixings) );
688 
689  /* abort, if all integer variables were fixed (which should not happen for MIP),
690  * but frequently happens for MINLPs using an LP relaxation */
691  if( binfixings + intfixings == nbinvars + nintvars )
692  goto TERMINATE;
693 
694  /* abort, if the amount of fixed variables is insufficient */
695  if( (binfixings + intfixings) / (SCIP_Real)(MAX(nbinvars + nintvars, 1)) < heurdata->minfixingrate )
696  goto TERMINATE;
697 
698  *result = SCIP_DIDNOTFIND;
699 
700  /* initialize the subproblem */
701  SCIP_CALL( SCIPcreate(&subscip) );
702 
703  /* create the variable mapping hash map */
704  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
705  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
706 
707  success = FALSE;
708  eventhdlr = NULL;
709 
710  /* create a problem copy as sub SCIP */
711  SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "dins", fixedvars, fixedvals, binfixings + intfixings,
712  heurdata->uselprows, heurdata->copycuts, &success, NULL) );
713 
714  /* create event handler for LP events */
715  SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecDins, NULL) );
716  if( eventhdlr == NULL )
717  {
718  SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
719  return SCIP_PLUGINNOTFOUND;
720  }
721 
722  SCIPdebugMsg(scip, "Copying the SCIP instance was %ssuccessful.\n", success ? "" : "not ");
723 
724  SCIPdebugMsg(scip, "DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n",
725  SCIPgetNVars(subscip), SCIPgetNBinVars(subscip) , SCIPgetNIntVars(subscip) , SCIPgetNConss(subscip));
726 
727  /* store subproblem variables that correspond to original variables */
728  for( i = 0; i < nvars; i++ )
729  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
730 
731  /* free hash map */
732  SCIPhashmapFree(&varmapfw);
733 
734  /* perform prepared softfixing for all unfixed vars if the number of unfixed vars is larger than the neighborhoodsize (otherwise it will be useless) */
735  if( nbinvars - binfixings > heurdata->neighborhoodsize )
736  {
737  SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata) );
738  }
739 
740  /* rebound integer variables if not all were fixed */
741  if( intfixings < nintvars )
742  {
743  assert(nintvars > 0);
744  SCIP_CALL( reboundIntegerVariables(scip, subscip, vars, subvars, nbinvars, nintvars) );
745  }
746 
747  /* do not abort subproblem on CTRL-C */
748  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
749 
750 #ifdef SCIP_DEBUG
751  /* for debugging, enable full output */
752  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
753  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
754 #else
755  /* disable statistic timing inside sub SCIP and output to console */
756  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
757  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
758 #endif
759 
760  /* set limits for the subproblem */
761  SCIP_CALL( SCIPcopyLimits(scip, subscip) );
762  heurdata->nodelimit = nsubnodes;
763  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
764  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nsubnodes/10)) );
765  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", heurdata->bestsollimit) );
766 
767  /* forbid recursive call of heuristics and separators solving subMIPs */
768  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
769 
770  /* disable cutting plane separation */
772 
773  /* disable expensive presolving */
775 
776  /* use best estimate node selection */
777  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
778  {
779  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
780  }
781 
782  /* activate uct node selection at the top of the tree */
783  if( heurdata->useuct && SCIPfindNodesel(subscip, "uct") != NULL && !SCIPisParamFixed(subscip, "nodeselection/uct/stdpriority") )
784  {
785  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/uct/stdpriority", INT_MAX/2) );
786  }
787 
788  /* use inference branching */
789  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
790  {
791  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
792  }
793 
794  /* enable conflict analysis and restrict conflict pool */
795  if( !SCIPisParamFixed(subscip, "conflict/enable") )
796  {
797  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
798  }
799  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
800  {
801  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
802  }
803 
804  /* speed up sub-SCIP by not checking dual LP feasibility */
805  SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
806 
807  /* employ a limit on the number of enforcement rounds in the quadratic constraint handler; this fixes the issue that
808  * sometimes the quadratic constraint handler needs hundreds or thousands of enforcement rounds to determine the
809  * feasibility status of a single node without fractional branching candidates by separation (namely for uflquad
810  * instances); however, the solution status of the sub-SCIP might get corrupted by this; hence no deductions shall be
811  * made for the original SCIP
812  */
813  if( SCIPfindConshdlr(subscip, "quadratic") != NULL && !SCIPisParamFixed(subscip, "constraints/quadratic/enfolplimit") )
814  {
815  SCIP_CALL( SCIPsetIntParam(subscip, "constraints/quadratic/enfolplimit", 500) );
816  }
817 
818 
819 
820  /* add an objective cutoff */
822 
824  {
825  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
826  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
827  cutoff = MIN(upperbound, cutoff);
828  }
829  else
830  {
831  if( SCIPgetUpperbound(scip) >= 0 )
832  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
833  else
834  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
835  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
836  cutoff = MIN(upperbound, cutoff);
837  }
838  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
839 
840  /* catch LP events of sub-SCIP */
841  if( !heurdata->uselprows )
842  {
843  assert(eventhdlr != NULL);
844 
845  SCIP_CALL( SCIPtransformProb(subscip) );
846  SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
847  }
848 
849  /* solve the subproblem */
850  SCIPdebugMsg(scip, "solving DINS sub-MIP with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n", heurdata->neighborhoodsize, nsubnodes);
851 
852  /* Errors in solving the subproblem should not kill the overall solving process
853  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
854  */
855  SCIP_CALL_ABORT( SCIPsolve(subscip) );
856 
857  /* drop LP events of sub-SCIP */
858  if( !heurdata->uselprows )
859  {
860  assert(eventhdlr != NULL);
861 
862  SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
863  }
864 
865  /* print solving statistics of subproblem if we are in SCIP's debug mode */
867 
868  heurdata->usednodes += SCIPgetNNodes(subscip);
869  nsubsols = SCIPgetNSols(subscip);
870  SCIPdebugMsg(scip, "DINS used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes and found %d solutions\n", SCIPgetNNodes(subscip), nsubnodes, nsubsols);
871 
872  /* check, whether a (new) solution was found */
873  if( nsubsols > 0 )
874  {
875  SCIP_SOL** subsols;
876 
877  /* 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 */
878  subsols = SCIPgetSols(subscip);
879  success = FALSE;
880  for( i = 0; i < nsubsols && !success; ++i )
881  {
882  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
883  }
884  if( success )
885  *result = SCIP_FOUNDSOL;
886  }
887 
888  /* free subproblem */
889  SCIPfreeBufferArray(scip, &subvars);
890  SCIP_CALL( SCIPfree(&subscip) );
891  TERMINATE:
892  SCIPfreeBufferArray(scip, &fixedvals);
893  SCIPfreeBufferArray(scip, &fixedvars);
894 
895  return SCIP_OKAY;
896 }
897 
898 
899 /*
900  * primal heuristic specific interface methods
901  */
902 
903 /** creates the DINS primal heuristic and includes it in SCIP */
905  SCIP* scip /**< SCIP data structure */
906  )
907 {
908  SCIP_HEURDATA* heurdata;
909  SCIP_HEUR* heur;
910 
911  /* create Dins primal heuristic data */
912  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
913 
914  /* include primal heuristic */
915  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
917  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDins, heurdata) );
918 
919  assert(heur != NULL);
920 
921  /* set non-NULL pointers to callback methods */
922  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyDins) );
923  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDins) );
924  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDins) );
925  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDins) );
926 
927  /* add DINS primal heuristic parameters */
928  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
929  "number of nodes added to the contingent of the total nodes",
930  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
931  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
932  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
933  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
934  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
935  "minimum number of nodes required to start the subproblem",
936  &heurdata->minnodes, FALSE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
937  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/solnum",
938  "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)",
939  &heurdata->solnum, FALSE, DEFAULT_SOLNUM, 1, INT_MAX, NULL, NULL) );
940  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/neighborhoodsize",
941  "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
942  &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
943  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
944  "maximum number of nodes to regard in the subproblem",
945  &heurdata->maxnodes,TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
946  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
947  "factor by which " HEUR_NAME " should at least improve the incumbent",
948  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
949  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nwaitingnodes",
950  "number of nodes without incumbent change that heuristic should wait",
951  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
952 
953  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lplimfac",
954  "factor by which the limit on the number of LP depends on the node limit",
955  &heurdata->lplimfac, TRUE, DEFAULT_LPLIMFAC, 1.0, SCIP_REAL_MAX, NULL, NULL) );
956 
957  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate",
958  "minimum percentage of integer variables that have to be fixable",
959  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
960 
961  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselprows",
962  "should subproblem be created out of the rows in the LP rows?",
963  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
964 
965  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
966  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
967  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
968 
969  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useuct",
970  "should uct node selection be used at the beginning of the search?",
971  &heurdata->useuct, TRUE, DEFAULT_USEUCT, NULL, NULL) );
972 
973  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/bestsollimit",
974  "limit on number of improving incumbent solutions in sub-CIP",
975  &heurdata->bestsollimit, FALSE, DEFAULT_BESTSOLLIMIT, -1, INT_MAX, NULL, NULL) );
976 
977  return SCIP_OKAY;
978 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip.c:8124
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11721
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21898
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21877
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:84
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip.c:5095
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
#define DEFAULT_LPLIMFAC
Definition: heur_dins.c:45
#define HEUR_FREQ
Definition: heur_dins.c:34
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
#define EVENTHDLR_NAME
Definition: heur_dins.c:60
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:42664
#define DEFAULT_NODESOFS
Definition: heur_dins.c:40
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip.c:12071
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8526
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:12654
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:38881
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
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:4230
#define DEFAULT_MAXNODES
Definition: heur_dins.c:41
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip.c:4126
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#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:5069
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
static SCIP_DECL_HEURFREE(heurFreeDins)
Definition: heur_dins.c:511
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
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:7999
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21964
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip.c:44425
static SCIP_DECL_HEURINITSOL(heurInitsolDins)
Definition: heur_dins.c:532
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10724
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8108
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
#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:38044
#define DEFAULT_NEIGHBORHOODSIZE
Definition: heur_dins.c:48
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
static SCIP_DECL_HEUREXITSOL(heurExitsolDins)
Definition: heur_dins.c:563
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
#define NULL
Definition: lpi_spx1.cpp:137
#define DEFAULT_NODESQUOT
Definition: heur_dins.c:44
#define REALABS(x)
Definition: def.h:159
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17540
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42323
#define HEUR_FREQOFS
Definition: heur_dins.c:35
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
SCIP_RETCODE SCIPincludeHeurDins(SCIP *scip)
Definition: heur_dins.c:904
static SCIP_DECL_HEURCOPY(heurCopyDins)
Definition: heur_dins.c:497
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#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:40207
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
#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:11078
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:39843
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
#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:40241
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
static SCIP_DECL_HEUREXEC(heurExecDins)
Definition: heur_dins.c:584
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define SCIP_REAL_MAX
Definition: def.h:136
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:28897
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12679
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip.c:8872
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:899
SCIP_HEUR * SCIPgetSolHeur(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38330
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define SCIP_Longint
Definition: def.h:120
#define HEUR_MAXDEPTH
Definition: heur_dins.c:36
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip.c:4090
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:37909
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip.c:13668
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
#define DEFAULT_NWAITINGNODES
Definition: heur_dins.c:47
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip.c:16942
SCIP_Real SCIPgetUpperbound(SCIP *scip)
Definition: scip.c:42472
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41363
#define DEFAULT_USEUCT
Definition: heur_dins.c:56
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
#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:4258
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip.c:5020
static SCIP_DECL_EVENTEXEC(eventExecDins)
Definition: heur_dins.c:467
#define HEUR_USESSUBSCIP
Definition: heur_dins.c:38
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip.c:4683
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:4176
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38303