Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgdins.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file heur_gcgdins.c
29  * @brief DINS primal heuristic (according to Ghosh)
30  * @author Robert Waniek
31  * @author Christian Puchert
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "heur_gcgdins.h"
40 #include "gcg.h"
41 
42 #include "scip/scipdefplugins.h"
43 #include "scip/cons_linear.h"
44 
45 #define HEUR_NAME "gcgdins"
46 #define HEUR_DESC "distance induced neighborhood search by Ghosh"
47 #define HEUR_DISPCHAR 'D'
48 #define HEUR_PRIORITY -1105000
49 #define HEUR_FREQ -1
50 #define HEUR_FREQOFS 0
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
53 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
54 
55 #define DEFAULT_NODESOFS 5000LL /**< number of nodes added to the contingent of the total nodes */
56 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
57 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
58 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which DINS should at least improve the incumbent */
59 #define DEFAULT_NODESQUOT 0.05 /**< subproblem nodes in relation to nodes of the original problem */
60 #define DEFAULT_NWAITINGNODES 0LL /**< number of nodes without incumbent change that heuristic should wait */
61 #define DEFAULT_NEIGHBORHOODSIZE 18 /**< radius of the incumbents neighborhood to be searched */
62 #define DEFAULT_SOLNUM 5 /**< number of pool-solutions to be checked for flag array update */
63 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
64  * otherwise, the copy constructors of the constraints handlers are used */
65 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
66  * of the original scip be copied to constraints of the subscip */
67 
68 
69 /*
70  * Data structures
71  */
72 
73 /** DINS primal heuristic data */
75 {
76  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
77  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
78  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
79  SCIP_Longint nwaitingnodes; /**< number of nodes without incumbent change that heuristic should wait */
80  SCIP_Real minimprove; /**< factor by which DINS should at least improve the incumbent */
81  SCIP_Longint usednodes; /**< nodes already used by DINS in earlier calls */
82  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
83  int neighborhoodsize; /**< radius of the incumbent's neighborhood to be searched */
84  SCIP_Bool* delta; /**< stores whether a variable kept its value from root LP all the time */
85  int deltalength; /**< if there are no binary variables, we need no flag array */
86  SCIP_Longint lastnsolsfound; /**< solutions found until the last call of DINS */
87  int solnum; /**< number of pool-solutions to be checked for flag array update */
88  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
89  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
90  * to constraints in subproblem?
91  */
92  SCIP_SOL* rootsol; /**< relaxation solution at the root node */
93  SCIP_Bool firstrun; /**< is the heuristic running for the first time? */
94 
95 #ifdef SCIP_STATISTIC
96  SCIP_Real avgfixrate; /**< average rate of variables that are fixed */
97  SCIP_Real avgzerorate; /**< average rate of fixed variables that are zero */
98  SCIP_Longint totalsols; /**< total number of subSCIP solutions (including those which have not
99  * been added)
100  */
101  SCIP_Real subsciptime; /**< total subSCIP solving time in seconds */
102  SCIP_Real bestprimalbd; /**< objective value of best solution found by this heuristic */
103 #endif
104 };
105 
106 
107 /*
108  * Local methods
109  */
110 
111 /** creates a subproblem for subscip by fixing a number of variables */
112 static
113 SCIP_RETCODE createSubproblem(
114  SCIP* scip, /**< SCIP data structure of the original problem */
115  SCIP* subscip, /**< SCIP data structure of the subproblem */
116  SCIP_VAR** vars, /**< variables of the original problem */
117  SCIP_VAR** subvars, /**< variables of the subproblem */
118  int nbinvars, /**< number of binary variables of problem and subproblem */
119  int nintvars, /**< number of general integer variables of problem and subproblem */
120  SCIP_Bool uselprows, /**< should subproblem be created out of the rows in the LP rows? */
121  int* fixingcounter, /**< number of integers that get actually fixed */
122  int* zerocounter /**< number of variables fixed to zero */
123  )
124 {
125  SCIP_SOL* bestsol;
126 
127  int i;
128 
129  assert(scip != NULL);
130  assert(subscip != NULL);
131  assert(vars != NULL);
132  assert(subvars != NULL);
133 
134  /* get the best MIP-solution known so far */
135  bestsol = SCIPgetBestSol(scip);
136  assert(bestsol != NULL);
137 
138  /* create the rebounded general integer variables of the subproblem */
139  for( i = nbinvars; i < nbinvars + nintvars; i++ )
140  {
141  SCIP_Real mipsol;
142  SCIP_Real lpsol;
143 
144  SCIP_Real lbglobal;
145  SCIP_Real ubglobal;
146 
147  /* get the bounds for each variable */
148  lbglobal = SCIPvarGetLbGlobal(vars[i]);
149  ubglobal = SCIPvarGetUbGlobal(vars[i]);
150 
151  assert(SCIPvarGetType(vars[i]) == SCIP_VARTYPE_INTEGER);
152  /* get the current relaxation solution for each variable */
153  lpsol = SCIPgetRelaxSolVal(scip, vars[i]);
154  /* get the current MIP solution for each variable */
155  mipsol = SCIPgetSolVal(scip, bestsol, vars[i]);
156 
157  /* if the solution values differ by 0.5 or more, the variable is rebounded, otherwise it is just copied */
158  if( REALABS(lpsol-mipsol) >= 0.5 )
159  {
160  SCIP_Real lb;
161  SCIP_Real ub;
162  SCIP_Real range;
163 
164  lb = lbglobal;
165  ub = ubglobal;
166 
167  /* create a equally sized range around lpsol for general integers: bounds are lpsol +- (mipsol-lpsol) */
168  range = 2*lpsol-mipsol;
169 
170  if( mipsol >= lpsol )
171  {
172  range = SCIPfeasCeil(scip, range);
173  lb = MAX(lb, 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, lb) )
177  ub = lb;
178  else
179  ub = mipsol;
180  }
181  else
182  {
183  range = SCIPfeasFloor(scip, range);
184  ub = MIN(ub, range);
185 
186  /* when the bound new upper bound is equal to the current MIP solution, we set both bounds to the integral bound (without eps) */
187  if( SCIPisFeasEQ(scip, mipsol, ub) )
188  lb = ub;
189  else
190  lb = mipsol;
191  }
192 
193  /* the global domain of variables might have been reduced since incumbent was found: adjust lb and ub accordingly */
194  lb = MAX(lb, lbglobal);
195  ub = MIN(ub, ubglobal);
196 
197  /* perform the bound change */
198  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
199  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
200  if( SCIPisEQ(scip, lb, ub) )
201  {
202  (*fixingcounter)++;
203  if( SCIPisZero(scip, ub) )
204  (*zerocounter)++;
205  }
206  }
207  else
208  {
209  /* the global domain of variables might have been reduced since incumbent was found: adjust it accordingly */
210  mipsol = MAX(mipsol, lbglobal);
211  mipsol = MIN(mipsol, ubglobal);
212 
213  /* hard fixing for general integer variables with abs(mipsol-lpsol) < 0.5 */
214  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], mipsol) );
215  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], mipsol) );
216  (*fixingcounter)++;
217  if( SCIPisZero(scip, mipsol) )
218  (*zerocounter)++;
219  }
220  }
221 
222  if( uselprows )
223  {
224  SCIP_ROW** rows; /* original scip rows */
225  int nrows;
226 
227  /* get the rows and their number */
228  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
229 
230  /* copy all rows to linear constraints */
231  for( i = 0; i < nrows; i++ )
232  {
233  SCIP_CONS* cons;
234  SCIP_VAR** consvars;
235  SCIP_COL** cols;
236  SCIP_Real constant;
237  SCIP_Real lhs;
238  SCIP_Real rhs;
239  SCIP_Real* vals;
240 
241  int nnonz;
242  int j;
243 
244  /* ignore rows that are only locally valid */
245  if( SCIProwIsLocal(rows[i]) )
246  continue;
247 
248  /* get the row's data */
249  constant = SCIProwGetConstant(rows[i]);
250  lhs = SCIProwGetLhs(rows[i]) - constant;
251  rhs = SCIProwGetRhs(rows[i]) - constant;
252  vals = SCIProwGetVals(rows[i]);
253  nnonz = SCIProwGetNNonz(rows[i]);
254  cols = SCIProwGetCols(rows[i]);
255 
256  assert(lhs <= rhs);
257 
258  /* allocate memory array to be filled with the corresponding subproblem variables */
259  SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
260  for( j = 0; j < nnonz; j++ )
261  consvars[j] = subvars [ SCIPvarGetProbindex(SCIPcolGetVar(cols[j])) ];
262 
263  /* create a new linear constraint and add it to the subproblem */
264  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
265  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
266  SCIP_CALL( SCIPaddCons(subscip, cons) );
267  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
268 
269  /* free temporary memory */
270  SCIPfreeBufferArray(subscip, &consvars);
271  }
272  }
273 
274  return SCIP_OKAY;
275 }
276 
277 /** create the extra constraint of local branching and add it to subscip */
278 static
280  SCIP* scip, /**< SCIP data structure of the original problem */
281  SCIP* subscip, /**< SCIP data structure of the subproblem */
282  SCIP_VAR** subvars, /**< variables of the subproblem */
283  SCIP_HEURDATA* heurdata, /**< heuristic's data structure */
284  SCIP_Bool* fixed /**< TRUE --> include variable in LB constraint */
285  )
286 {
287  SCIP_CONS* cons; /* local branching constraint to create */
288  SCIP_VAR** consvars;
289  SCIP_VAR** vars;
290  SCIP_SOL* bestsol;
291 
292  SCIP_Real* consvals;
293  SCIP_Real solval;
294  SCIP_Real lhs;
295  SCIP_Real rhs;
296 
297  char consname[SCIP_MAXSTRLEN];
298 
299  int nbinvars;
300  int i;
301 
302  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_dinsLBcons", SCIPgetProbName(scip));
303 
304  /* get the data of the variables and the best solution */
305  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, NULL, NULL, NULL) );
306  bestsol = SCIPgetBestSol(scip);
307  assert(bestsol != NULL);
308 
309  /* memory allocation */
310  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nbinvars) );
311  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nbinvars) );
312 
313  /* set initial left and right hand sides of local branching constraint */
314  lhs = 0.0;
315  rhs = (SCIP_Real) heurdata->neighborhoodsize;
316 
317  /* create the distance function of the binary variables (to incumbent solution) */
318  for( i = 0; i < nbinvars; i++ )
319  {
320  consvars[i] = subvars[i];
321  assert(SCIPvarGetType(consvars[i]) == SCIP_VARTYPE_BINARY);
322  if( fixed[i] )
323  {
324  consvals[i]=0.0;
325  continue;
326  }
327 
328  solval = SCIPgetSolVal(scip, bestsol, vars[i]);
329  assert(SCIPisFeasIntegral(scip, solval));
330 
331  /* is variable i part of the binary support of the current solution? */
332  if( SCIPisFeasEQ(scip, solval, 1.0) )
333  {
334  consvals[i] = -1.0;
335  rhs -= 1.0;
336  lhs -= 1.0;
337  }
338  else
339  consvals[i] = 1.0;
340  }
341 
342  /* creates local branching constraint and adds it to subscip */
343  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, consname, nbinvars, consvars, consvals,
344  lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
345  SCIP_CALL( SCIPaddCons(subscip, cons) );
346  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
347 
348  /* free local memory */
349  SCIPfreeBufferArray(scip, &consvals);
350  SCIPfreeBufferArray(scip, &consvars);
351 
352  return SCIP_OKAY;
353 }
354 
355 /** get relaxation solution of root node (in original variables) */
356 static
357 SCIP_RETCODE getRootRelaxSol(
358  SCIP* scip, /**< SCIP data structure */
359  SCIP_SOL** rootsol /**< pointer to store root relaxation solution */
360  )
361 {
362  SCIP* masterprob;
363  SCIP_SOL* masterrootsol;
364  SCIP_VAR** mastervars;
365  int nmastervars;
366  int i;
367 
368  /* get master problem */
369  masterprob = GCGgetMasterprob(scip);
370  assert(masterprob != NULL);
371 
372  /* allocate memory for master root LP solution */
373  SCIP_CALL( SCIPcreateSol(masterprob, &masterrootsol, NULL) );
374 
375  /* get master variable information */
376  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
377  assert(mastervars != NULL);
378  assert(nmastervars >= 0);
379 
380  /* store root LP values in working master solution */
381  for( i = 0; i < nmastervars; i++ )
382  SCIP_CALL( SCIPsetSolVal(masterprob, masterrootsol, mastervars[i], SCIPvarGetRootSol(mastervars[i])) );
383 
384  /* calculate original root LP solution */
385  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, masterrootsol, rootsol) );
386 
387  /* free memory */
388  SCIP_CALL( SCIPfreeSol(masterprob, &masterrootsol) );
389 
390  return SCIP_OKAY;
391 }
392 
393 /** creates a new solution for the original problem by copying the solution of the subproblem */
394 static
395 SCIP_RETCODE createNewSol(
396  SCIP* scip, /**< original SCIP data structure */
397  SCIP* subscip, /**< SCIP structure of the subproblem */
398  SCIP_VAR** subvars, /**< the variables of the subproblem */
399  SCIP_HEUR* heur, /**< DINS heuristic structure */
400  SCIP_SOL* subsol, /**< solution of the subproblem */
401  SCIP_Bool* success /**< used to store whether new solution was found or not */
402  )
403 {
404 #ifdef SCIP_STATISTIC
405  SCIP_HEURDATA* heurdata;
406 #endif
407  SCIP_VAR** vars; /* the original problem's variables */
408  int nvars;
409  SCIP_Real* subsolvals; /* solution values of the subproblem */
410  SCIP_SOL* newsol; /* solution to be created for the original problem */
411 
412  assert(scip != NULL);
413  assert(heur != NULL);
414  assert(subscip != NULL);
415  assert(subvars != NULL);
416  assert(subsol != NULL);
417 
418 #ifdef SCIP_STATISTIC
419  /* get heuristic data */
420  heurdata = SCIPheurGetData(heur);
421  assert( heurdata != NULL );
422 #endif
423 
424  /* get variables' data */
425  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
426  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
427  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
428  */
429  assert(nvars <= SCIPgetNOrigVars(subscip));
430 
431  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
432 
433  /* copy the solution */
434  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
435 
436  /* create new solution for the original problem */
437  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
438  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
439 
440  /* try to add new solution to scip and free it immediately */
441  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
442 
443 #ifdef SCIP_STATISTIC
444  if( *success )
445  {
446  if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
447  heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
448  }
449 #endif
450 
451  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
452 
453  SCIPfreeBufferArray(scip, &subsolvals);
454  return SCIP_OKAY;
455 }
456 
457 
458 /*
459  * Callback methods of primal heuristic
460  */
461 
462 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
463 static
464 SCIP_DECL_HEURFREE(heurFreeGcgdins)
465 { /*lint --e{715}*/
466  SCIP_HEURDATA* heurdata;
467 
468  assert(heur != NULL);
469  assert(scip != NULL);
470 
471  /* get heuristic data */
472  heurdata = SCIPheurGetData(heur);
473  assert(heurdata != NULL);
474 
475  /* free heuristic data */
476  SCIPfreeMemory(scip, &heurdata);
477  SCIPheurSetData(heur, NULL);
478 
479  return SCIP_OKAY;
480 }
481 
482 
483 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
484 static
485 SCIP_DECL_HEURINITSOL(heurInitsolGcgdins)
486 {
487  SCIP_HEURDATA* heurdata;
488 
489  assert(heur != NULL);
490  assert(scip != NULL);
491 
492  /* get heuristic's data */
493  heurdata = SCIPheurGetData(heur);
494  assert(heurdata != NULL);
495 
496  /* initialize data */
497  heurdata->usednodes = 0;
498  heurdata->lastnsolsfound = 0;
499  heurdata->rootsol = NULL;
500  heurdata->firstrun = TRUE;
501 
502  /* create flag array */
503  heurdata->deltalength = SCIPgetNBinVars(scip);
504 
505  /* no binvars => no flag array needed */
506  if( heurdata->deltalength > 0 )
507  {
508  int i;
509 
510  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength) );
511  for( i = 0; i < heurdata->deltalength; i++ )
512  heurdata->delta[i] = TRUE;
513  }
514 
515 #ifdef SCIP_STATISTIC
516  /* initialize statistical data */
517  heurdata->avgfixrate = 0.0;
518  heurdata->avgzerorate = 0.0;
519  heurdata->totalsols = 0;
520  heurdata->subsciptime = 0.0;
521  heurdata->bestprimalbd = SCIPinfinity(scip);
522 #endif
523 
524  return SCIP_OKAY;
525 }
526 
527 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
528 static
529 SCIP_DECL_HEUREXITSOL(heurExitsolGcgdins)
530 { /*lint --e{715}*/
531  SCIP_HEURDATA* heurdata;
532 #ifdef SCIP_STATISTIC
533  SCIP_Longint ncalls;
534 #endif
535 
536  assert(heur != NULL);
537  assert(scip != NULL);
538 
539  /* get heuristic data */
540  heurdata = SCIPheurGetData(heur);
541  assert(heurdata != NULL);
542 
543  /* free flag array if exist */
544  if( heurdata->deltalength > 0 )
545  {
546  SCIPfreeBlockMemoryArray(scip, &(heurdata->delta), heurdata->deltalength);
547  }
548 
549  /* free root relaxation solution */
550  if( heurdata->rootsol != NULL )
551  SCIP_CALL( SCIPfreeSol(scip, &heurdata->rootsol) );
552 
553 #ifdef SCIP_STATISTIC
554  ncalls = SCIPheurGetNCalls(heur);
555  heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
556  heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
557 
558  /* print detailed statistics */
559  SCIPstatisticPrintf("LNS Statistics -- %s:\n", SCIPheurGetName(heur));
560  SCIPstatisticPrintf("Calls : %13"SCIP_LONGINT_FORMAT"\n", ncalls);
561  SCIPstatisticPrintf("Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNSolsFound(heur));
562  SCIPstatisticPrintf("Improving Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNBestSolsFound(heur));
563  SCIPstatisticPrintf("Total Sols : %13"SCIP_LONGINT_FORMAT"\n", heurdata->totalsols);
564  SCIPstatisticPrintf("subSCIP time : %13.2f\n", heurdata->subsciptime);
565  SCIPstatisticPrintf("subSCIP nodes : %13"SCIP_LONGINT_FORMAT"\n", heurdata->usednodes);
566  SCIPstatisticPrintf("Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
567  SCIPstatisticPrintf("Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
568  SCIPstatisticPrintf("Best primal bd. :");
569  if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
570  SCIPstatisticPrintf(" infinity\n");
571  else
572  SCIPstatisticPrintf(" %13.6e\n", heurdata->bestprimalbd);
573  SCIPstatisticPrintf("\n");
574 #endif
575 
576  return SCIP_OKAY;
577 }
578 
579 /** execution method of primal heuristic */
580 static
581 SCIP_DECL_HEUREXEC(heurExecGcgdins)
582 { /*lint --e{715}*/
583  SCIP* masterprob;
584  SCIP_HEURDATA* heurdata;
585  SCIP* subscip; /* the subproblem created by DINS */
586  SCIP_VAR** subvars; /* subproblem's variables */
587  SCIP_VAR** vars; /* variables of the original problem */
588  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
589  SCIP_SOL* bestsol; /* best solution known so far */
590  SCIP_SOL** sols; /* list of known solutions */
591 
592  SCIP_Bool* fixed; /* fixing flag array */
593  SCIP_Bool* delta; /* flag array if variable value changed during solution process */
594 
595 
596  SCIP_Longint maxnnodes; /* maximum number of subnodes */
597  SCIP_Longint nsubnodes; /* nodelimit for subscip */
598  SCIP_Longint nsolsfound;
599 
600  SCIP_Real timelimit; /* timelimit for subscip (equals remaining time of scip) */
601  SCIP_Real cutoff; /* objective cutoff for the subproblem */
602  SCIP_Real upperbound;
603  SCIP_Real memorylimit; /* memory limit for solution process of subscip */
604  SCIP_Real lpsolval;
605  SCIP_Real rootlpsolval;
606  SCIP_Real mipsolval;
607  SCIP_Real solval;
608 #ifdef SCIP_STATISTIC
609  SCIP_Real allfixingrate; /* percentage of all variables fixed */
610  SCIP_Real intfixingrate; /* percentage of integer variables fixed */
611  SCIP_Real zerofixingrate; /* percentage of variables fixed to zero */
612 #endif
613 
614  int ufcount; /* counts the number of true fixing flag entries */
615  int nvars; /* number of variables in original SCIP */
616  int nbinvars; /* number of binary variables in original SCIP */
617  int nintvars; /* number of general integer variables in original SCIP */
618  int nsols; /* number of known solutions */
619  int nsubsols;
620  int checklength;
621  int fixingcounter;
622  int zerocounter;
623  int i;
624  int j;
625 
626  SCIP_Bool success; /* used to store whether new solution was found or not */
627  SCIP_Bool infeasible; /* stores whether the hard fixing of a variables was feasible or not */
628 
629  SCIP_RETCODE retcode;
630 
631  assert(heur != NULL);
632  assert(scip != NULL);
633  assert(result != NULL);
634 
635  /* get master problem */
636  masterprob = GCGgetMasterprob(scip);
637  assert(masterprob != NULL);
638 
639  *result = SCIP_DELAYED;
640 
641  /* do not execute the heuristic on invalid relaxation solutions
642  * (which is the case if the node has been cut off)
643  */
644  if( !SCIPisRelaxSolValid(scip) )
645  return SCIP_OKAY;
646 
647  /* only call heuristic, if feasible solution is available */
648  if( SCIPgetNSols(scip) <= 0 )
649  return SCIP_OKAY;
650 
651  /* only call heuristic, if an optimal LP solution is at hand */
652  if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
653  return SCIP_OKAY;
654 
655  /* get heuristic data */
656  heurdata = SCIPheurGetData(heur);
657  assert(heurdata != NULL);
658  delta = heurdata->delta;
659 
660  /* only call heuristic, if enough nodes were processed since last incumbent */
661  if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip, SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
662  return SCIP_OKAY;
663 
664  *result = SCIP_DIDNOTRUN;
665 
666  /* determine the node limit for the current process */
667  maxnnodes = (SCIP_Longint) (heurdata->nodesquot * SCIPgetNNodes(scip));
668 
669  /* reward DINS if it succeeded often */
670  maxnnodes = (SCIP_Longint) (maxnnodes * (1.0 + 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0) / (SCIPheurGetNCalls(heur) + 1.0)));
671 
672  /* count the setup costs for the sub-MIP as 100 nodes */
673  maxnnodes -= 100 * SCIPheurGetNCalls(heur);
674  maxnnodes += heurdata->nodesofs;
675 
676  /* determine the node limit for the current process */
677  nsubnodes = maxnnodes - heurdata->usednodes;
678  nsubnodes = MIN(nsubnodes , heurdata->maxnodes);
679 
680  /* check whether we have enough nodes left to call sub problem solving */
681  if( nsubnodes < heurdata->minnodes )
682  return SCIP_OKAY;
683 
684  if( SCIPisStopped(scip) )
685  return SCIP_OKAY;
686 
687  /* get required data of the original problem */
688  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
689  assert(nbinvars <= nvars);
690 
691  /* do not run heuristic if only continuous variables are present */
692  if( nbinvars == 0 && nintvars == 0 )
693  return SCIP_OKAY;
694 
695  assert(vars != NULL);
696 
697  /* if the heuristic is running for the first time, the root relaxation solution needs to be stored */
698  if( heurdata->firstrun )
699  {
700  assert(heurdata->rootsol == NULL);
701  SCIP_CALL( getRootRelaxSol(scip, &heurdata->rootsol) );
702  assert(heurdata->rootsol != NULL);
703  heurdata->firstrun = FALSE;
704  }
705 
706  /* initialize the subproblem */
707  SCIP_CALL( SCIPcreate(&subscip) );
708 
709  /* create the variable mapping hash map */
710  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
711  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
712 
713  success = FALSE;
714  if( heurdata->uselprows )
715  {
716  char probname[SCIP_MAXSTRLEN];
717 
718  /* copy all plugins */
719  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
720 
721  /* get name of the original problem and add the string "_gcgdinssub" */
722  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_gcgdinssub", SCIPgetProbName(scip));
723 
724  /* create the subproblem */
725  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
726 
727  /* copy all variables */
728  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
729  }
730  else
731  {
732  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "gcgdins", TRUE, FALSE, FALSE, TRUE, &success) );
733 
734  if( heurdata->copycuts )
735  {
736  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
737  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
738  }
739 
740  SCIPdebugMessage("Copying the SCIP instance was %ssuccessful.\n", success ? "" : "not ");
741  }
742 
743  for( i = 0; i < nvars; i++ )
744  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
745 
746  /* free hash map */
747  SCIPhashmapFree(&varmapfw);
748 
749  fixingcounter = 0;
750  zerocounter = 0;
751 
752  SCIPstatisticPrintf("gcgdins statistic: called at node %"SCIP_LONGINT_FORMAT"\n", SCIPgetNNodes(scip));
753 
754  /* create variables and rebound them if their bounds differ by more than 0.5 */
755  SCIP_CALL( createSubproblem(scip, subscip, vars, subvars, nbinvars, nintvars, heurdata->uselprows, &fixingcounter, &zerocounter) );
756  SCIPdebugMessage("DINS subproblem: %d vars (%d binvars & %d intvars), %d cons\n",
757  SCIPgetNVars(subscip), SCIPgetNBinVars(subscip) , SCIPgetNIntVars(subscip) , SCIPgetNConss(subscip));
758 
759  *result = SCIP_DIDNOTFIND;
760 
761  /* do not abort subproblem on CTRL-C */
762  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
763 
764  /* disable output to console */
765  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
766 
767  /* check whether there is enough time and memory left */
768  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
769  if( !SCIPisInfinity(scip, timelimit) )
770  timelimit -= SCIPgetSolvingTime(scip);
771  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
772 
773  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
774  if( !SCIPisInfinity(scip, memorylimit) )
775  {
776  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
777  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
778  }
779 
780  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
781  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
782  goto TERMINATE;
783 
784  /* set limits for the subproblem */
785  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nsubnodes) );
786  SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 3) );
787  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
788  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
789 
790  /* forbid recursive call of heuristics and separators solving subMIPs */
791  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
792 
793  /* disable cutting plane separation */
794  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
795 
796  /* disable expensive presolving */
797  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
798 
799  /* use best estimate node selection */
800  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
801  {
802  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
803  }
804 
805  /* use inference branching */
806  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
807  {
808  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
809  }
810 
811  /* disable conflict analysis */
812  if( !SCIPisParamFixed(subscip, "conflict/enable") )
813  {
814  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
815  }
816 
817  /* get the best MIP-solution known so far */
818  bestsol = SCIPgetBestSol(scip);
819  assert(bestsol != NULL);
820 
821  /* get solution pool and number of solutions in pool */
822  sols = SCIPgetSols(scip);
823  nsols = SCIPgetNSols(scip);
824  nsolsfound = SCIPgetNSolsFound(scip);
825  checklength = MIN(nsols, heurdata->solnum);
826  assert(sols != NULL);
827  assert(nsols > 0);
828 
829  /* create fixing flag array */
830  SCIP_CALL( SCIPallocBufferArray(scip, &fixed, nbinvars) );
831 
832  /* if new binary variables have been created, e.g., due to column generation, reallocate the delta array */
833  if( heurdata->deltalength < nbinvars )
834  {
835  int newsize;
836 
837  newsize = SCIPcalcMemGrowSize(scip, nbinvars);
838  assert(newsize >= nbinvars);
839 
840  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &heurdata->delta, heurdata->deltalength, newsize) );
841  delta = heurdata->delta;
842 
843  /* initialize new part of delta array */
844  for( i = heurdata->deltalength; i < newsize; i++ )
845  delta[i] = TRUE;
846 
847  heurdata->deltalength = newsize;
848  }
849 
850  /* fixing for binary variables */
851  /* hard fixing for some with mipsol(s)=lpsolval=rootlpsolval and preparation for soft fixing for the remaining */
852  ufcount = 0;
853  for( i = 0; i < nbinvars; i++ )
854  {
855  /* soft fixing if the variable somewhen changed its value or the relaxations differ by adding a local branching constraint */
856  fixed[i] = FALSE;
857 
858  /* get the current relaxation solution for each variable */
859  lpsolval = SCIPgetRelaxSolVal(scip, vars[i]);
860  /* get the current MIP solution for each variable */
861  mipsolval = SCIPgetSolVal(scip, bestsol, vars[i]);
862  /* get the root relaxation solution for each variable */
863  rootlpsolval = SCIPgetSolVal(scip, heurdata->rootsol, vars[i]);
864 
865  if( SCIPisFeasEQ(scip, lpsolval, mipsolval) && SCIPisFeasEQ(scip, mipsolval, rootlpsolval) )
866  {
867  /* update delta */
868  if( nsols > 1 && heurdata->lastnsolsfound != nsolsfound && delta[i] ) /* no need to update delta[i] if already FALSE */
869  {
870  /* 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 */
871  for( j = 0; delta[i] && j < checklength && SCIPgetSolHeur(scip, sols[j]) != heur ; j++ )
872  {
873  solval = SCIPgetSolVal(scip, sols[j], vars[i]);
874  delta[i] = delta[i] && SCIPisFeasEQ(scip, mipsolval, solval);
875  }
876  }
877 
878  /* hard fixing if rootlpsolval=nodelpsolval=mipsolval(s) and delta (is TRUE) */
879  if( delta[i] && SCIPisFeasEQ(scip, mipsolval, lpsolval) && SCIPisFeasEQ(scip, mipsolval, rootlpsolval )
880  && SCIPisFeasEQ(scip, rootlpsolval, lpsolval) )
881  {
882  SCIP_CALL( SCIPfixVar(subscip, subvars[i], mipsolval, &infeasible, &success) );
883  fixed[i] = !infeasible;
884  if( !success )
885  {
886  SCIPdebugMessage("variable %d was already fixed\n", i);
887  }
888  else
889  {
890  ++fixingcounter;
891  if( SCIPisZero(scip, mipsolval) )
892  ++zerocounter;
893  }
894  if( infeasible )
895  {
896  SCIPdebugMessage("fixing of variable %d to value %f was infeasible\n", i, mipsolval);
897  }
898  }
899  }
900  if( !fixed[i] )
901  ufcount++;
902  }
903 
904 #ifdef SCIP_STATISTIC
905  intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
906  zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
907 #endif
908 
909  /* store the number of found solutions for next run */
910  heurdata->lastnsolsfound = nsolsfound;
911 
912  /* perform prepared softfixing for all unfixed vars if the number of unfixed vars is larger than the neighborhoodsize (otherwise it will be useless) */
913  if( ufcount > heurdata->neighborhoodsize )
914  {
915  SCIP_CALL( addLocalBranchingConstraint(scip, subscip, subvars, heurdata, fixed) );
916  }
917 
918  /* free fixing flag array */
919  SCIPfreeBufferArray(scip, &fixed);
920 
921  /* add an objective cutoff */
922  assert(!SCIPisInfinity(scip, SCIPgetUpperbound(scip)));
923 
924  if( !SCIPisInfinity(scip, -1.0*SCIPgetLowerbound(scip)) )
925  {
926  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip) + heurdata->minimprove * SCIPgetLowerbound(scip);
927  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
928  cutoff = MIN(upperbound, cutoff);
929  }
930  else
931  {
932  if( SCIPgetUpperbound(scip) >= 0 )
933  cutoff = (1 - heurdata->minimprove) * SCIPgetUpperbound(scip);
934  else
935  cutoff = (1 + heurdata->minimprove) * SCIPgetUpperbound(scip);
936  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
937  cutoff = MIN(upperbound, cutoff);
938  }
939  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
940 
941 #ifdef SCIP_STATISTIC
942  heurdata->avgfixrate += intfixingrate;
943  heurdata->avgzerorate += zerofixingrate;
944 #endif
945 
946  /* presolve the subproblem */
947  retcode = SCIPpresolve(subscip);
948 
949  /* errors in solving the subproblem should not kill the overall solving process;
950  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
951  */
952  if( retcode != SCIP_OKAY )
953  {
954 #ifndef NDEBUG
955  SCIP_CALL( retcode );
956 #endif
957  SCIPwarningMessage(scip, "Error while presolving subproblem in GCG RINS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
958  goto TERMINATE;
959  }
960 
961  SCIPdebugMessage("GCG DINS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
962 
963 #ifdef SCIP_STATISTIC
964  allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
965 
966  /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
967  allfixingrate = MAX(allfixingrate, 0.0);
968 #endif
969 
970  /* solve the subproblem */
971  SCIPdebugMessage("solving DINS sub-MIP with neighborhoodsize %d and maxnodes %"SCIP_LONGINT_FORMAT"\n", heurdata->neighborhoodsize, nsubnodes);
972  retcode = SCIPsolve(subscip);
973 
974  /* Errors in solving the subproblem should not kill the overall solving process
975  * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
976  */
977  if( retcode != SCIP_OKAY )
978  {
979 #ifndef NDEBUG
980  SCIP_CALL( retcode );
981 #endif
982  SCIPwarningMessage(scip, "Error while solving subproblem in DINS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
983  }
984 
985  heurdata->usednodes += SCIPgetNNodes(subscip);
986  nsubsols = SCIPgetNSols(subscip);
987 #ifdef SCIP_STATISTIC
988  heurdata->subsciptime += SCIPgetTotalTime(subscip);
989  heurdata->totalsols += nsubsols;
990 #endif
991  SCIPdebugMessage("DINS used %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT" nodes and found %d solutions\n", SCIPgetNNodes(subscip), nsubnodes, nsubsols);
992 
993  /* check, whether a (new) solution was found */
994  if( nsubsols > 0 )
995  {
996  SCIP_SOL** subsols;
997 
998  /* 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 */
999  subsols = SCIPgetSols(subscip);
1000  success = FALSE;
1001  for( i = 0; i < nsubsols && !success; ++i )
1002  {
1003  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
1004  if( success )
1005  *result = SCIP_FOUNDSOL;
1006  }
1007 
1008 #ifdef SCIP_STATISTIC
1009  SCIPstatisticPrintf("gcgdins statistic: fixed %6.3f integer variables ( %6.3f zero), %6.3f all variables, needed %6.1f sec (SCIP time: %6.1f sec), %"SCIP_LONGINT_FORMAT" nodes, found %d solutions, solution %10.4f found at node %"SCIP_LONGINT_FORMAT"\n",
1010  intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
1011  success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
1012 #endif
1013 
1014  }
1015 
1016  TERMINATE:
1017  /* free subproblem */
1018  SCIPfreeBufferArray(scip, &subvars);
1019  SCIP_CALL( SCIPfree(&subscip) );
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 
1025 /*
1026  * primal heuristic specific interface methods
1027  */
1028 
1029 /** creates the GCG DINS primal heuristic and includes it in SCIP */
1031  SCIP* scip /**< SCIP data structure */
1032  )
1033 {
1034  SCIP_HEURDATA* heurdata;
1035  SCIP_HEUR* heur;
1036 
1037  /* create Gcgdins primal heuristic data */
1038  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1039 
1040  /* include primal heuristic */
1041  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1043  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGcgdins, heurdata) );
1044 
1045  assert(heur != NULL);
1046 
1047  /* set non-NULL pointers to callback methods */
1048  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGcgdins) );
1049  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolGcgdins) );
1050  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGcgdins) );
1051 
1052  /* add DINS primal heuristic parameters */
1053  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
1054  "number of nodes added to the contingent of the total nodes",
1055  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1056  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
1057  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1058  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1059  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
1060  "minimum number of nodes required to start the subproblem",
1061  &heurdata->minnodes, FALSE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1062  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/solnum",
1063  "number of pool-solutions to be checked for flag array update (for hard fixing of binary variables)",
1064  &heurdata->solnum, FALSE, DEFAULT_SOLNUM, 1, INT_MAX, NULL, NULL) );
1065  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/neighborhoodsize",
1066  "radius (using Manhattan metric) of the incumbent's neighborhood to be searched",
1067  &heurdata->neighborhoodsize, FALSE, DEFAULT_NEIGHBORHOODSIZE, 1, INT_MAX, NULL, NULL) );
1068  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
1069  "maximum number of nodes to regard in the subproblem",
1070  &heurdata->maxnodes,TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1071  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
1072  "factor by which "HEUR_NAME" should at least improve the incumbent",
1073  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1074  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nwaitingnodes",
1075  "number of nodes without incumbent change that heuristic should wait",
1076  &heurdata->nwaitingnodes, TRUE, DEFAULT_NWAITINGNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1077  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
1078  "should subproblem be created out of the rows in the LP rows?",
1079  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
1080  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
1081  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1082  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1083 
1084  return SCIP_OKAY;
1085 }
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_gcgdins.c:395
static SCIP_DECL_HEURINITSOL(heurInitsolGcgdins)
Definition: heur_gcgdins.c:485
GCG interface methods.
SCIP_Real minimprove
Definition: heur_gcgdins.c:80
#define HEUR_NAME
Definition: heur_gcgdins.c:45
static SCIP_DECL_HEUREXEC(heurExecGcgdins)
Definition: heur_gcgdins.c:581
#define DEFAULT_SOLNUM
Definition: heur_gcgdins.c:62
SCIP_Bool copycuts
Definition: heur_gcgdins.c:89
SCIP_Longint nodesofs
Definition: heur_gcgdins.c:76
SCIP_Bool * delta
Definition: heur_gcgdins.c:84
#define DEFAULT_NEIGHBORHOODSIZE
Definition: heur_gcgdins.c:61
#define DEFAULT_NODESOFS
Definition: heur_gcgdins.c:55
#define HEUR_MAXDEPTH
Definition: heur_gcgdins.c:51
static SCIP_DECL_HEURFREE(heurFreeGcgdins)
Definition: heur_gcgdins.c:464
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
SCIP_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:120
#define DEFAULT_MAXNODES
Definition: heur_gcgdins.c:56
SCIP_Longint maxnodes
Definition: heur_gcgdins.c:77
SCIP_Longint lastnsolsfound
Definition: heur_gcgdins.c:86
#define HEUR_PRIORITY
Definition: heur_gcgdins.c:48
#define DEFAULT_MINIMPROVE
Definition: heur_gcgdins.c:58
#define HEUR_TIMING
Definition: heur_gcgdins.c:52
SCIP_Longint nwaitingnodes
Definition: heur_gcgdins.c:79
#define HEUR_DESC
Definition: heur_gcgdins.c:46
SCIP_SOL * rootsol
Definition: heur_gcgdins.c:92
SCIP_Bool firstrun
Definition: heur_gcgdins.c:93
static SCIP_RETCODE addLocalBranchingConstraint(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Bool *fixed)
Definition: heur_gcgdins.c:279
int neighborhoodsize
Definition: heur_gcgdins.c:83
static SCIP_DECL_HEUREXITSOL(heurExitsolGcgdins)
Definition: heur_gcgdins.c:529
SCIP_Bool uselprows
Definition: heur_gcgdins.c:88
#define DEFAULT_USELPROWS
Definition: heur_gcgdins.c:63
#define HEUR_DISPCHAR
Definition: heur_gcgdins.c:47
#define HEUR_FREQ
Definition: heur_gcgdins.c:49
SCIP_RETCODE SCIPincludeHeurGcgdins(SCIP *scip)
#define DEFAULT_MINNODES
Definition: heur_gcgdins.c:57
static SCIP_RETCODE getRootRelaxSol(SCIP *scip, SCIP_SOL **rootsol)
Definition: heur_gcgdins.c:357
DINS primal heuristic.
#define DEFAULT_NODESQUOT
Definition: heur_gcgdins.c:59
SCIP_Longint usednodes
Definition: heur_gcgdins.c:81
SCIP_Longint minnodes
Definition: heur_gcgdins.c:78
#define HEUR_USESSUBSCIP
Definition: heur_gcgdins.c:53
#define DEFAULT_NWAITINGNODES
Definition: heur_gcgdins.c:60
#define DEFAULT_COPYCUTS
Definition: heur_gcgdins.c:65
SCIP_Real nodesquot
Definition: heur_gcgdins.c:82
static SCIP_RETCODE createSubproblem(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, int nbinvars, int nintvars, SCIP_Bool uselprows, int *fixingcounter, int *zerocounter)
Definition: heur_gcgdins.c:113
#define HEUR_FREQOFS
Definition: heur_gcgdins.c:50