Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgrens.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_gcgrens.c
29  * @brief LNS heuristic that finds the optimal rounding to a given point
30  * @author Timo Berthold
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 #include <stdio.h>
39 
40 #include "heur_gcgrens.h"
41 #include "gcg.h"
42 
43 #include "scip/scipdefplugins.h"
44 #include "scip/cons_linear.h"
45 
46 /* default values for standard parameters that every primal heuristic has in SCIP */
47 #define HEUR_NAME "gcgrens"
48 #define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum"
49 #define HEUR_DISPCHAR 'E'
50 #define HEUR_PRIORITY -1100000
51 #define HEUR_FREQ 0
52 #define HEUR_FREQOFS 0
53 #define HEUR_MAXDEPTH -1
54 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
55 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
56 
57 /* default values for RENS-specific plugins */
58 #define DEFAULT_BINARYBOUNDS TRUE /**< should general integers get binary bounds [floor(.),ceil(.)] ? */
59 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
60 #define DEFAULT_MINFIXINGRATE 0.5 /**< minimum percentage of integer variables that have to be fixed */
61 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which RENS should at least improve the incumbent */
62 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
63 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
64 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
65 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
66  * otherwise, the copy constructors of the constraints handlers are used */
67 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
68  * of the original scip be copied to constraints of the subscip
69  */
70 #define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */
71 
72 
73 /*
74  * Data structures
75  */
76 
77 /** primal heuristic data */
78 struct SCIP_HeurData
79 {
80  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
81  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
82  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
83  SCIP_Longint usednodes; /**< nodes already used by RENS in earlier calls */
84  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
85  SCIP_Real minimprove; /**< factor by which RENS should at least improve the incumbent */
86  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
87  SCIP_Bool binarybounds; /**< should general integers get binary bounds [floor(.),ceil(.)] ? */
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_Bool addallsols; /**< should all subproblem solutions be added to the original SCIP? */
93 
94 #ifdef SCIP_STATISTIC
95  SCIP_Longint nfixfails; /**< number of abortions due to a bad fixing rate */
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 by fixing a number of variables */
112 static
113 SCIP_RETCODE createSubproblem(
114  SCIP* scip, /**< original SCIP data structure */
115  SCIP* subscip, /**< SCIP data structure for the subproblem */
116  SCIP_VAR** subvars, /**< the variables of the subproblem */
117  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
118  SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)] ? */
119  SCIP_Bool uselprows, /**< should subproblem be created out of the rows in the LP rows? */
120  SCIP_Real* intfixingrate, /**< percentage of integers that get actually fixed */
121  SCIP_Real* zerofixingrate, /**< percentage of variables fixed to zero */
122  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
123  )
124 {
125  SCIP_VAR** vars; /* original SCIP variables */
126 
127  int nbinvars;
128  int nintvars;
129  int i;
130 
131  int fixingcounter;
132  int zerocounter;
133 
134  assert(scip != NULL);
135  assert(subscip != NULL);
136  assert(subvars != NULL);
137 
138  assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
139 
140  /* get required variable data */
141  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
142 
143  fixingcounter = 0;
144  zerocounter = 0;
145 
146  /* change bounds of variables of the subproblem */
147  for( i = 0; i < nbinvars + nintvars; i++ )
148  {
149  SCIP_Real lpsolval;
150  SCIP_Real lb;
151  SCIP_Real ub;
152 
153  /* get the current LP solution for each variable */
154  lpsolval = SCIPgetRelaxSolVal(scip, vars[i]);
155 
156  if( SCIPisFeasIntegral(scip, lpsolval) )
157  {
158  /* fix variables to current LP solution if it is integral,
159  * use exact integral value, if the variable is only integral within numerical tolerances
160  */
161  lb = SCIPfloor(scip, lpsolval+0.5);
162  ub = lb;
163  fixingcounter++;
164  if( SCIPisZero(scip, lb) )
165  zerocounter++;
166  }
167  else if( binarybounds )
168  {
169  /* if the sub problem should be a binary problem, change the bounds to nearest integers */
170  lb = SCIPfeasFloor(scip,lpsolval);
171  ub = SCIPfeasCeil(scip,lpsolval);
172  }
173  else
174  {
175  /* otherwise just copy bounds */
176  lb = SCIPvarGetLbGlobal(vars[i]);
177  ub = SCIPvarGetUbGlobal(vars[i]);
178  }
179 
180  /* perform the bound change */
181  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
182  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
183  }
184 
185  /* abort, if all integer variables were fixed (which should not happen for MIP) */
186  if( fixingcounter == nbinvars + nintvars )
187  {
188  *intfixingrate = 1.0;
189  *zerofixingrate = 1.0;
190  *success = FALSE;
191  return SCIP_OKAY;
192  }
193  else
194  {
195  *intfixingrate = fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
196  *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
197  }
198 
199  /* abort, if the amount of fixed variables is insufficient */
200  if( *intfixingrate < minfixingrate )
201  {
202  *success = FALSE;
203  SCIPstatisticPrintf("gcgrens statistic: fixed only %5.2f ( %5.2f zero) integer variables --> abort \n", *intfixingrate, *zerofixingrate);
204  return SCIP_OKAY;
205  }
206 
207  if( uselprows )
208  {
209  SCIP_ROW** rows; /* original scip rows */
210  int nrows;
211 
212  /* get the rows and their number */
213  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
214 
215  /* copy all rows to linear constraints */
216  for( i = 0; i < nrows; i++ )
217  {
218  SCIP_CONS* cons;
219  SCIP_VAR** consvars;
220  SCIP_COL** cols;
221  SCIP_Real constant;
222  SCIP_Real lhs;
223  SCIP_Real rhs;
224  SCIP_Real* vals;
225  int nnonz;
226  int j;
227 
228  /* ignore rows that are only locally valid */
229  if( SCIProwIsLocal(rows[i]) )
230  continue;
231 
232  /* get the row's data */
233  constant = SCIProwGetConstant(rows[i]);
234  lhs = SCIProwGetLhs(rows[i]) - constant;
235  rhs = SCIProwGetRhs(rows[i]) - constant;
236  vals = SCIProwGetVals(rows[i]);
237  nnonz = SCIProwGetNNonz(rows[i]);
238  cols = SCIProwGetCols(rows[i]);
239 
240  assert(lhs <= rhs);
241 
242  /* allocate memory array to be filled with the corresponding subproblem variables */
243  SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
244  for( j = 0; j < nnonz; j++ )
245  consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
246 
247  /* create a new linear constraint and add it to the subproblem */
248  SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
249  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
250  SCIP_CALL( SCIPaddCons(subscip, cons) );
251  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
252 
253  /* free temporary memory */
254  SCIPfreeBufferArray(subscip, &consvars);
255  }
256  }
257 
258  *success = TRUE;
259  return SCIP_OKAY;
260 }
261 
262 
263 /** creates a new solution for the original problem by copying the solution of the subproblem */
264 static
265 SCIP_RETCODE createNewSol(
266  SCIP* scip, /**< original SCIP data structure */
267  SCIP* subscip, /**< SCIP structure of the subproblem */
268  SCIP_VAR** subvars, /**< the variables of the subproblem */
269  SCIP_HEUR* heur, /**< RENS heuristic structure */
270  SCIP_SOL* subsol, /**< solution of the subproblem */
271  SCIP_Bool* success /**< used to store whether new solution was found or not */
272  )
273 {
274 #ifdef SCIP_STATISTIC
275  SCIP_HEURDATA* heurdata;
276 #endif
277  SCIP_VAR** vars; /* the original problem's variables */
278  int nvars; /* the original problem's number of variables */
279  SCIP_Real* subsolvals; /* solution values of the subproblem */
280  SCIP_SOL* newsol; /* solution to be created for the original problem */
281 
282  assert(scip != NULL);
283  assert(subscip != NULL);
284  assert(subvars != NULL);
285  assert(subsol != NULL);
286 
287 #ifdef SCIP_STATISTIC
288  /* get heuristic data */
289  heurdata = SCIPheurGetData(heur);
290  assert( heurdata != NULL );
291 #endif
292 
293  /* get variables' data */
294  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
295 
296  /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
297  * since constraint copying may have required the copy of variables that are fixed in the main SCIP
298  */
299  assert(nvars <= SCIPgetNOrigVars(subscip));
300 
301  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
302 
303  /* copy the solution */
304  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
305 
306  /* create new solution for the original problem */
307  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
308  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
309 
310  /* try to add new solution to scip */
311 #ifdef SCIP_STATISTIC
312  if( !*success || heurdata->addallsols )
313 #endif
314  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
315 
316 #ifdef SCIP_STATISTIC
317  if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
318  heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
319 
320  SCIPstatisticPrintf("gcgrens statistic: Solution %13.6e found at node %"SCIP_LONGINT_FORMAT"\n",
321  SCIPgetSolTransObj(scip, newsol), SCIPsolGetNodenum(subsol));
322 #endif
323 
324  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
325 
326  SCIPfreeBufferArray(scip, &subsolvals);
327 
328  return SCIP_OKAY;
329 }
330 
331 /** main procedure of the GCG RENS heuristic, creates and solves a sub-SCIP */
332 SCIP_RETCODE GCGapplyGcgrens(
333  SCIP* scip, /**< original SCIP data structure */
334  SCIP_HEUR* heur, /**< heuristic data structure */
335  SCIP_RESULT* result, /**< result data structure */
336  SCIP_Real minfixingrate, /**< minimum percentage of integer variables that have to be fixed */
337  SCIP_Real minimprove, /**< factor by which RENS should at least improve the incumbent */
338  SCIP_Longint maxnodes, /**< maximum number of nodes for the subproblem */
339  SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
340  SCIP_Bool binarybounds, /**< should general integers get binary bounds [floor(.),ceil(.)]? */
341  SCIP_Bool uselprows /**< should subproblem be created out of the rows in the LP rows? */
342  )
343 {
344  SCIP* subscip; /* the subproblem created by RENS */
345  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */
346  SCIP_VAR** vars; /* original problem's variables */
347  SCIP_VAR** subvars; /* subproblem's variables */
348  SCIP_HEURDATA* heurdata; /* heuristic's private data structure */
349 
350  SCIP_Real timelimit; /* time limit for RENS subproblem */
351  SCIP_Real memorylimit; /* memory limit for RENS subproblem */
352  SCIP_Real allfixingrate; /* percentage of all variables fixed */
353  SCIP_Real intfixingrate; /* percentage of integer variables fixed */
354  SCIP_Real zerofixingrate; /* percentage of variables fixed to zero */
355 
356  int nvars; /* number of original problem's variables */
357  int i;
358 
359  SCIP_Bool success;
360  SCIP_RETCODE retcode;
361 
362  assert(scip != NULL);
363  assert(heur != NULL);
364  assert(result != NULL);
365 
366  assert(maxnodes >= 0);
367  assert(nstallnodes >= 0);
368 
369  assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
370  assert(0.0 <= minimprove && minimprove <= 1.0);
371 
372  /* get heuristic data */
373  heurdata = SCIPheurGetData(heur);
374  assert(heurdata != NULL);
375 
376  /* check whether there is enough time and memory left */
377  timelimit = 0.0;
378  memorylimit = 0.0;
379  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
380  if( !SCIPisInfinity(scip, timelimit) )
381  timelimit -= SCIPgetSolvingTime(scip);
382  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
383 
384  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
385  if( !SCIPisInfinity(scip, memorylimit) )
386  {
387  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
388  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
389  }
390 
391  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
392  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
393  return SCIP_OKAY;
394 
395  *result = SCIP_DIDNOTFIND;
396 
397  /* get variable data */
398  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
399 
400  /* initialize the subproblem */
401  SCIP_CALL( SCIPcreate(&subscip) );
402 
403  /* create the variable mapping hash map */
404  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
405  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
406 
407  /* different methods to create sub-problem: either copy LP relaxation or the CIP with all constraints */
408  if( uselprows )
409  {
410  char probname[SCIP_MAXSTRLEN];
411 
412  /* copy all plugins */
413  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
414 
415  /* get name of the original problem and add the string "_gcgrenssub" */
416  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_gcgrenssub", SCIPgetProbName(scip));
417 
418  /* create the subproblem */
419  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
420 
421  /* copy all variables */
422  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
423  }
424  else
425  {
426  SCIP_Bool valid;
427 
428  valid = FALSE;
429 
430  /* copy complete SCIP instance */
431  SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "gcgrens", TRUE, FALSE, FALSE, TRUE, &valid) ); /** @todo check for thread safeness */
432 
433  if( heurdata->copycuts )
434  {
435  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
436  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
437  }
438 
439  SCIPdebugMessage("Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
440  }
441 
442  for( i = 0; i < nvars; i++ )
443  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
444 
445  /* free hash map */
446  SCIPhashmapFree(&varmapfw);
447 
448  SCIPstatisticPrintf("gcgrens statistic: called at node %"SCIP_LONGINT_FORMAT"\n", SCIPgetNNodes(scip));
449 
450  /* create a new problem, which fixes variables with same value in bestsol and LP relaxation */
451  SCIP_CALL( createSubproblem(scip, subscip, subvars, minfixingrate, binarybounds, uselprows, &intfixingrate, &zerofixingrate, &success) );
452  SCIPdebugMessage("RENS subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
453 
454  /* do not abort subproblem on CTRL-C */
455  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
456 
457  /* disable output to console */
458  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
459 
460  /* set limits for the subproblem */
461  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
462  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
463  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
464  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
465 
466  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
467  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
468 
469  /* disable cutting plane separation */
470  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
471 
472  /* disable expensive presolving */
473  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
474 
475  /* use best estimate node selection */
476  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
477  {
478  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
479  }
480 
481  /* use inference branching */
482  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
483  {
484  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
485  }
486 
487  /* disable conflict analysis */
488  if( !SCIPisParamFixed(subscip, "conflict/enable") )
489  {
490  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
491  }
492 
493 #ifdef SCIP_DEBUG
494  /* for debugging RENS, enable MIP output */
495  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
496  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
497 #endif
498 
499 #ifdef SCIP_STATISTIC
500  heurdata->avgfixrate += intfixingrate;
501  heurdata->avgzerorate += zerofixingrate;
502 #endif
503 
504  /* if the subproblem could not be created, free memory and return */
505  if( !success )
506  {
507  *result = SCIP_DIDNOTRUN;
508  SCIPfreeBufferArray(scip, &subvars);
509  SCIP_CALL( SCIPfree(&subscip) );
510 #ifdef SCIP_STATISTIC
511  ++heurdata->nfixfails;
512 #endif
513  return SCIP_OKAY;
514  }
515 
516  /* if there is already a solution, add an objective cutoff */
517  if( SCIPgetNSols(scip) > 0 )
518  {
519  SCIP_Real cutoff; /* objective cutoff for the subproblem */
520  SCIP_Real upperbound;
521  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
522 
523  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
524 
525  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
526  {
527  cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
528  }
529  else
530  {
531  if( SCIPgetUpperbound ( scip ) >= 0 )
532  cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
533  else
534  cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
535  }
536  cutoff = MIN(upperbound, cutoff);
537  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
538  }
539  /* presolve the subproblem */
540  retcode = SCIPpresolve(subscip);
541 
542  /* errors in solving the subproblem should not kill the overall solving process;
543  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
544  */
545  if( retcode != SCIP_OKAY )
546  {
547 #ifndef NDEBUG
548  SCIP_CALL( retcode );
549 #endif
550  SCIPwarningMessage(scip, "Error while presolving subproblem in GCG RENS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
551 
552  /* free */
553  SCIPfreeBufferArray(scip, &subvars);
554  SCIP_CALL( SCIPfree(&subscip) );
555  return SCIP_OKAY;
556  }
557 
558  SCIPdebugMessage("GCG RENS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
559 
560  allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
561 
562  /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
563  allfixingrate = MAX(allfixingrate, 0.0);
564 
565  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
566  * to ensure that not only the MIP but also the LP relaxation is easy enough
567  */
568  if( allfixingrate >= minfixingrate / 2.0 )
569  {
570  SCIP_SOL** subsols;
571  int nsubsols;
572 
573  /* solve the subproblem */
574  SCIPdebugMessage("solving subproblem: nstallnodes=%"SCIP_LONGINT_FORMAT", maxnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, maxnodes);
575  retcode = SCIPsolve(subscip);
576 
577  /* errors in solving the subproblem should not kill the overall solving process;
578  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
579  */
580  if( retcode != SCIP_OKAY )
581  {
582 #ifndef NDEBUG
583  SCIP_CALL( retcode );
584 #endif
585  SCIPwarningMessage(scip, "Error while solving subproblem in GCG RENS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
586  }
587 
588 #ifdef SCIP_STATISTIC
589  heurdata->usednodes += SCIPgetNNodes(subscip);
590  heurdata->subsciptime += SCIPgetTotalTime(subscip);
591 #endif
592 
593  /* check, whether a solution was found;
594  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
595  */
596  nsubsols = SCIPgetNSols(subscip);
597  subsols = SCIPgetSols(subscip);
598  success = FALSE;
599 #ifdef SCIP_STATISTIC
600  heurdata->totalsols += nsubsols;
601  for( i = 0; i < nsubsols; ++i )
602 #else
603  for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
604 #endif
605  {
606  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
607  if( success )
608  *result = SCIP_FOUNDSOL;
609  }
610 
611  SCIPstatisticPrintf("gcgrens 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",
612  intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
613  success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
614  }
615  else
616  {
617  SCIPstatisticPrintf("gcgrens statistic: fixed only %6.3f integer variables ( %6.3f zero), %6.3f all variables --> abort \n", intfixingrate, zerofixingrate, allfixingrate);
618  }
619 
620  /* free subproblem */
621  SCIPfreeBufferArray(scip, &subvars);
622  SCIP_CALL( SCIPfree(&subscip) );
623 
624  return SCIP_OKAY;
625 }
626 
627 /*
628  * Callback methods of primal heuristic
629  */
630 
631 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
632 static
633 SCIP_DECL_HEURFREE(heurFreeGcgrens)
634 { /*lint --e{715}*/
635  SCIP_HEURDATA* heurdata;
636 
637  assert( heur != NULL );
638  assert( scip != NULL );
639 
640  /* get heuristic data */
641  heurdata = SCIPheurGetData(heur);
642  assert( heurdata != NULL );
643 
644  /* free heuristic data */
645  SCIPfreeMemory(scip, &heurdata);
646  SCIPheurSetData(heur, NULL);
647 
648  return SCIP_OKAY;
649 }
650 
651 
652 /** initialization method of primal heuristic (called after problem was transformed) */
653 static
654 SCIP_DECL_HEURINIT(heurInitGcgrens)
655 { /*lint --e{715}*/
656  SCIP_HEURDATA* heurdata;
657 
658  assert( heur != NULL );
659  assert( scip != NULL );
660 
661  /* get heuristic data */
662  heurdata = SCIPheurGetData(heur);
663  assert( heurdata != NULL );
664 
665  /* initialize data */
666  heurdata->usednodes = 0;
667 
668  return SCIP_OKAY;
669 }
670 
671 #ifdef SCIP_STATISTIC
672 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
673 static
674 SCIP_DECL_HEURINITSOL(heurInitsolGcgrens)
675 { /*lint --e{715}*/
676  SCIP_HEURDATA* heurdata;
677 
678  assert(heur != NULL);
679  assert(scip != NULL);
680 
681  /* get heuristic data */
682  heurdata = SCIPheurGetData(heur);
683  assert(heurdata != NULL);
684 
685  /* initialize statistical data */
686  heurdata->avgfixrate = 0.0;
687  heurdata->avgzerorate = 0.0;
688  heurdata->totalsols = 0;
689  heurdata->subsciptime = 0.0;
690  heurdata->bestprimalbd = SCIPinfinity(scip);
691 
692  return SCIP_OKAY;
693 }
694 
695 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
696 static
697 SCIP_DECL_HEUREXITSOL(heurExitsolGcgrens)
698 { /*lint --e{715}*/
699  SCIP_HEURDATA* heurdata;
700  SCIP_Longint ncalls;
701 
702  assert(heur != NULL);
703  assert(scip != NULL);
704 
705  /* get heuristic data */
706  heurdata = SCIPheurGetData(heur);
707  assert(heurdata != NULL);
708 
709  ncalls = SCIPheurGetNCalls(heur);
710  heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
711  heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
712 
713  /* print detailed statistics */
714  SCIPstatisticPrintf("LNS Statistics -- %s:\n", SCIPheurGetName(heur));
715  SCIPstatisticPrintf("Calls : %13"SCIP_LONGINT_FORMAT"\n", ncalls);
716  SCIPstatisticPrintf("Failed Fixings : %13"SCIP_LONGINT_FORMAT"\n", heurdata->nfixfails);
717  SCIPstatisticPrintf("Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNSolsFound(heur));
718  SCIPstatisticPrintf("Improving Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNBestSolsFound(heur));
719  SCIPstatisticPrintf("Total Sols : %13"SCIP_LONGINT_FORMAT"\n", heurdata->totalsols);
720  SCIPstatisticPrintf("subSCIP time : %13.2f\n", heurdata->subsciptime);
721  SCIPstatisticPrintf("subSCIP nodes : %13"SCIP_LONGINT_FORMAT"\n", heurdata->usednodes);
722  SCIPstatisticPrintf("Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
723  SCIPstatisticPrintf("Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
724  SCIPstatisticPrintf("Best primal bd. :");
725  if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
726  SCIPstatisticPrintf(" infinity\n");
727  else
728  SCIPstatisticPrintf(" %13.6e\n", heurdata->bestprimalbd);
729  SCIPstatisticPrintf("\n");
730 
731  return SCIP_OKAY;
732 }
733 #endif
734 
735 /** execution method of primal heuristic */
736 static
737 SCIP_DECL_HEUREXEC(heurExecGcgrens)
738 { /*lint --e{715}*/
739 
740  SCIP* masterprob;
741  SCIP_HEURDATA* heurdata; /* heuristic's data */
742  SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */
743 
744  assert( heur != NULL );
745  assert( scip != NULL );
746  assert( result != NULL );
747 
748  /* get master problem */
749  masterprob = GCGgetMasterprob(scip);
750  assert( masterprob != NULL);
751 
752  /* get heuristic data */
753  heurdata = SCIPheurGetData(heur);
754  assert( heurdata != NULL );
755 
756  *result = SCIP_DELAYED;
757 
758  /* do not execute the heuristic on invalid relaxation solutions
759  * (which is the case if the node has been cut off)
760  */
761  if( !SCIPisRelaxSolValid(scip) )
762  {
763  SCIPdebugMessage("skipping GCG RENS: invalid relaxation solution\n");
764  return SCIP_OKAY;
765  }
766 
767  /* only call heuristic, if an optimal LP solution is at hand */
768  if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
769  return SCIP_OKAY;
770 
771  *result = SCIP_DIDNOTRUN;
772 
773  /* only continue with some fractional variables */
774  if( SCIPgetNExternBranchCands(scip) == 0 )
775  return SCIP_OKAY;
776 
777  *result = SCIP_DIDNOTRUN;
778 
779  /* calculate the maximal number of branching nodes until heuristic is aborted */
780  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
781 
782  /* reward RENS if it succeeded often */
783  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
784  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-SCIP as 100 nodes */
785  nstallnodes += heurdata->nodesofs;
786 
787  /* determine the node limit for the current process */
788  nstallnodes -= heurdata->usednodes;
789  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
790 
791  /* check whether we have enough nodes left to call subproblem solving */
792  if( nstallnodes < heurdata->minnodes )
793  {
794  SCIPdebugMessage("skipping RENS: nstallnodes=%"SCIP_LONGINT_FORMAT", minnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, heurdata->minnodes);
795  return SCIP_OKAY;
796  }
797 
798  if( SCIPisStopped(scip) )
799  return SCIP_OKAY;
800 
801  SCIP_CALL( GCGapplyGcgrens(scip, heur, result, heurdata->minfixingrate, heurdata->minimprove,
802  heurdata->maxnodes, nstallnodes, heurdata->binarybounds, heurdata->uselprows) );
803 
804  return SCIP_OKAY;
805 }
806 
807 
808 
809 /*
810  * primal heuristic specific interface methods
811  */
812 
813 /** creates GCG RENS primal heuristic and includes it in SCIP */
815  SCIP* scip /**< SCIP data structure */
816  )
817 {
818  SCIP_HEURDATA* heurdata;
819  SCIP_HEUR* heur;
820 
821  /* create GCG RENS primal heuristic data */
822  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
823 
824  /* include primal heuristic */
825  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
827  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecGcgrens, heurdata) );
828 
829  assert(heur != NULL);
830 
831  /* set non-NULL pointers to callback methods */
832  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGcgrens) );
833  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGcgrens) );
834 #ifdef SCIP_STATISTIC
835  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolGcgrens) );
836  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGcgrens) );
837 #endif
838 
839  /* add rens primal heuristic parameters */
840 
841  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minfixingrate",
842  "minimum percentage of integer variables that have to be fixable",
843  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
844 
845  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
846  "maximum number of nodes to regard in the subproblem",
847  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
848 
849  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
850  "number of nodes added to the contingent of the total nodes",
851  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
852 
853  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
854  "minimum number of nodes required to start the subproblem",
855  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
856 
857  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
858  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
859  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
860 
861  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
862  "factor by which RENS should at least improve the incumbent",
863  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
864 
865  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/binarybounds",
866  "should general integers get binary bounds [floor(.),ceil(.)] ?",
867  &heurdata->binarybounds, TRUE, DEFAULT_BINARYBOUNDS, NULL, NULL) );
868 
869  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
870  "should subproblem be created out of the rows in the LP rows?",
871  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
872 
873  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
874  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
875  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
876 
877  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/addallsols",
878  "should all subproblem solutions be added to the original SCIP?",
879  &heurdata->addallsols, TRUE, DEFAULT_ADDALLSOLS, NULL, NULL) );
880 
881  return SCIP_OKAY;
882 }
#define DEFAULT_MINIMPROVE
Definition: heur_gcgrens.c:61
#define DEFAULT_MINNODES
Definition: heur_gcgrens.c:62
#define DEFAULT_MAXNODES
Definition: heur_gcgrens.c:59
#define HEUR_PRIORITY
Definition: heur_gcgrens.c:50
static SCIP_DECL_HEURINITSOL(heurInitsolGcgdins)
Definition: heur_gcgdins.c:485
#define HEUR_DISPCHAR
Definition: heur_gcgrens.c:49
GCG interface methods.
static SCIP_RETCODE createSubproblem(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Real minfixingrate, SCIP_Bool binarybounds, SCIP_Bool uselprows, SCIP_Real *intfixingrate, SCIP_Real *zerofixingrate, SCIP_Bool *success)
Definition: heur_gcgrens.c:113
SCIP_Real minimprove
Definition: heur_gcgdins.c:80
#define HEUR_DESC
Definition: heur_gcgrens.c:48
#define DEFAULT_USELPROWS
Definition: heur_gcgrens.c:65
#define DEFAULT_BINARYBOUNDS
Definition: heur_gcgrens.c:58
static SCIP_DECL_HEUREXEC(heurExecGcgrens)
Definition: heur_gcgrens.c:737
SCIP_Bool copycuts
Definition: heur_gcgdins.c:89
SCIP_Longint nodesofs
Definition: heur_gcgdins.c:76
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
Definition: heur_gcgrens.c:265
SCIP_Bool addallsols
Definition: heur_gcgrens.c:92
#define DEFAULT_MINFIXINGRATE
Definition: heur_gcgrens.c:60
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
static SCIP_DECL_HEURFREE(heurFreeGcgrens)
Definition: heur_gcgrens.c:633
SCIP_RETCODE SCIPincludeHeurGcgrens(SCIP *scip)
Definition: heur_gcgrens.c:814
SCIP_Longint maxnodes
Definition: heur_gcgdins.c:77
#define HEUR_USESSUBSCIP
Definition: heur_gcgrens.c:55
#define HEUR_FREQOFS
Definition: heur_gcgrens.c:52
LNS heuristic that finds the optimal rounding to a given point.
#define HEUR_MAXDEPTH
Definition: heur_gcgrens.c:53
#define HEUR_FREQ
Definition: heur_gcgrens.c:51
#define DEFAULT_COPYCUTS
Definition: heur_gcgrens.c:67
#define DEFAULT_ADDALLSOLS
Definition: heur_gcgrens.c:70
static SCIP_DECL_HEURINIT(heurInitGcgrens)
Definition: heur_gcgrens.c:654
#define DEFAULT_NODESQUOT
Definition: heur_gcgrens.c:64
static SCIP_DECL_HEUREXITSOL(heurExitsolGcgdins)
Definition: heur_gcgdins.c:529
#define HEUR_NAME
Definition: heur_gcgrens.c:47
#define HEUR_TIMING
Definition: heur_gcgrens.c:54
SCIP_Bool uselprows
Definition: heur_gcgdins.c:88
SCIP_Longint usednodes
Definition: heur_gcgdins.c:81
SCIP_Longint minnodes
Definition: heur_gcgdins.c:78
SCIP_Real minfixingrate
Definition: heur_gcgrens.c:84
#define DEFAULT_NODESOFS
Definition: heur_gcgrens.c:63
SCIP_Real nodesquot
Definition: heur_gcgdins.c:82
SCIP_RETCODE GCGapplyGcgrens(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minfixingrate, SCIP_Real minimprove, SCIP_Longint maxnodes, SCIP_Longint nstallnodes, SCIP_Bool binarybounds, SCIP_Bool uselprows)
Definition: heur_gcgrens.c:332
SCIP_Bool binarybounds
Definition: heur_gcgrens.c:87