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