Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_restmaster.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_restmaster.c
29  * @brief Restricted Master Heuristic
30  * @author Christian Puchert
31  * @author Jonas Witt
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 
38 #include "heur_restmaster.h"
39 #include "gcg.h"
40 #include "pricer_gcg.h"
41 
42 #include "scip/scipdefplugins.h"
43 
44 
45 #define HEUR_NAME "restmaster"
46 #define HEUR_DESC "LNS heuristic for the master problem that fixes some master variables to zero"
47 #define HEUR_DISPCHAR 'P'
48 #define HEUR_PRIORITY 100
49 #define HEUR_FREQ 30
50 #define HEUR_FREQOFS 0
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
53 #define HEUR_USESSUBSCIP TRUE
54 
55 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */
56 #define DEFAULT_MINFIXINGRATE 0.5 /**< minimum percentage of integer variables that have to be fixed */
57 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which restricted master should at least improve the incumbent */
58 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */
59 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
60 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
61 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
62  * otherwise, the copy constructor of the constraints handlers are used*/
63 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
64  * of the original scip be copied to constraints of the subscip */
65 
66 #define DEFAULT_PBHEUR FALSE /**< default value for using the restricted master heuristic as
67  * price-and-branch heuristic?
68  * (this changes the HEUR_TIMING to SCIP_HEURTIMING_AFTERNODE,
69  * and it changes the HEUR_FREQ to 0. */
70 
71 /*
72  * Data structures
73  */
74 
75 /** primal heuristic data */
76 struct SCIP_HeurData
77 {
78  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
79  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
80  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
81  SCIP_Longint usednodes; /**< nodes already used by restricted master in earlier calls */
82  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
83  SCIP_Real minimprove; /**< factor by which restricted master should at least improve the incumbent */
84  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
85  SCIP_Bool uselprows; /**< should subproblem be created out of the rows in the LP rows? */
86  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
87  * to constraints in subproblem?
88  */
89  SCIP_Bool pbheur; /**< value for using the restricted master heuristic as
90  * price-and-branch heuristic?
91  * (this changes the HEUR_TIMING to SCIP_HEURTIMING_AFTERNODE,
92  * and it changes the HEUR_FREQ to 0. */
93 };
94 
95 
96 
97 
98 /*
99  * Local methods
100  */
101 
102 /** set up the restricted master problem by fixing master variables to zero */
103 static
104 SCIP_RETCODE setupSubproblem(
105  SCIP* scip, /**< SCIP data structure for master problem */
106  SCIP* restmaster, /**< SCIP data structure for restricted master problem */
107  SCIP_VAR** restmastervars, /**< the variables of the restricted */
108  SCIP_Real minfixingrate, /**< percentage of integer variables that have to be fixed */
109  SCIP_Bool uselprows, /**< should subproblem be created out of the rows in the LP rows? */
110  SCIP_Bool pbheur, /**< use heuristic as price-and-branch heuristic? */
111  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
112  )
113 {
114  SCIP_VAR** mastervars;
115  int nmastervars;
116  SCIP_Real fixingrate;
117 
118  int i;
119  int fixingcounter;
120 
121  /* get variable data of the master problem */
122  SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
123  assert(mastervars != NULL);
124  assert(nmastervars >= 0);
125 
126  fixingcounter = 0;
127 
128  /* fix zero variables in the restricted master problem */
129  for( i = 0; i < nmastervars && !pbheur; i++ )
130  {
131  SCIP_Real mastersolval;
132 
133  mastersolval = SCIPgetSolVal(scip, NULL, mastervars[i]);
134 
135  /* if LP solution value of master variable is zero, fix it to zero in restricted master */
136  if( SCIPisFeasZero(scip, mastersolval) )
137  {
138  SCIP_CALL( SCIPchgVarLbGlobal(restmaster, restmastervars[i], 0.0) );
139  SCIP_CALL( SCIPchgVarUbGlobal(restmaster, restmastervars[i], 0.0) );
140  fixingcounter++;
141  }
142  }
143 
144  /* abort, if all variables were fixed (which should not happen) */
145  if( fixingcounter == nmastervars )
146  {
147  SCIPdebugMessage(" -> all master variables fixed, not solving problem.\n");
148  *success = FALSE;
149  return SCIP_OKAY;
150  }
151  else
152  fixingrate = fixingcounter / (SCIP_Real)(MAX(nmastervars, 1));
153 
154  SCIPdebugMessage(" -> %d out of %d (%.2f percent) master variables fixed.\n", fixingcounter, nmastervars, fixingrate * 100.0);
155 
156  /* abort, if the amount of fixed variables is insufficient */
157  if( fixingrate < minfixingrate && !pbheur)
158  {
159  SCIPdebugMessage(" -> not enough variables fixed.\n");
160  *success = FALSE;
161  return SCIP_OKAY;
162  }
163 
164  if( uselprows )
165  {
166  SCIP_ROW** rows; /* original scip rows */
167  int nrows;
168 
169  /* get the rows and their number */
170  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
171 
172  /* copy all rows to linear constraints */
173  for( i = 0; i < nrows; i++ )
174  {
175  SCIP_CONS* cons;
176  SCIP_VAR** consvars;
177  SCIP_COL** cols;
178  SCIP_Real constant;
179  SCIP_Real lhs;
180  SCIP_Real rhs;
181  SCIP_Real* vals;
182  int nnonz;
183  int j;
184 
185  /* ignore rows that are only locally valid */
186  if( SCIProwIsLocal(rows[i]) )
187  continue;
188 
189  /* get the row's data */
190  constant = SCIProwGetConstant(rows[i]);
191  lhs = SCIProwGetLhs(rows[i]) - constant;
192  rhs = SCIProwGetRhs(rows[i]) - constant;
193  vals = SCIProwGetVals(rows[i]);
194  nnonz = SCIProwGetNNonz(rows[i]);
195  cols = SCIProwGetCols(rows[i]);
196 
197  assert(lhs <= rhs);
198 
199  /* allocate memory array to be filled with the corresponding subproblem variables */
200  SCIP_CALL( SCIPallocBufferArray(restmaster, &consvars, nnonz) );
201  for( j = 0; j < nnonz; j++ )
202  consvars[j] = restmastervars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
203 
204  /* create a new linear constraint and add it to the subproblem */
205  SCIP_CALL( SCIPcreateConsLinear(restmaster, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
206  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
207  SCIP_CALL( SCIPaddCons(restmaster, cons) );
208  SCIP_CALL( SCIPreleaseCons(restmaster, &cons) );
209 
210  /* free temporary memory */
211  SCIPfreeBufferArray(restmaster, &consvars);
212  }
213  }
214 
215  *success = TRUE;
216  return SCIP_OKAY;
217 }
218 
219 /** creates a new solution for the original problem by translating the solution of the restricted master problem */
220 static
221 SCIP_RETCODE createNewSol(
222  SCIP* origprob, /**< original SCIP data structure */
223  SCIP* scip, /**< SCIP data structure of master problem */
224  SCIP* restmaster, /**< SCIP structure of restricted master problem */
225  SCIP_VAR** restmastervars, /**< the variables of the restricted master problem */
226  SCIP_HEUR* heur, /**< Restricted Master heuristic structure */
227  SCIP_SOL* restmastersol, /**< solution of the restricted master problem */
228  SCIP_Bool* success /**< used to store whether new solution was found or not */
229  )
230 {
231  SCIP_VAR** vars; /* the original problem's variables */
232  SCIP_VAR** mastervars; /* the master problem's variables */
233  int nvars;
234  int nmastervars;
235  SCIP_Real* restmastervals; /* solution values of the subproblem */
236  SCIP_SOL* newmastersol; /* solution for the master problem */
237 
238  assert(origprob != NULL);
239  assert(scip != NULL);
240  assert(restmaster != NULL);
241  assert(restmastervars != NULL);
242  assert(restmastersol != NULL);
243 
244  /* get variables' data */
245  SCIP_CALL( SCIPgetVarsData(origprob, &vars, &nvars, NULL, NULL, NULL, NULL) );
246  SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
247  assert(nmastervars == SCIPgetNOrigVars(restmaster));
248 
249  SCIP_CALL( SCIPallocBufferArray(scip, &restmastervals, nmastervars) );
250 
251  /* copy the solution */
252  SCIP_CALL( SCIPgetSolVals(restmaster, restmastersol, nmastervars, restmastervars, restmastervals) );
253 
254  /* create new solution for the master problem */
255  SCIP_CALL( SCIPcreateSol(scip, &newmastersol, heur) );
256  SCIP_CALL( SCIPsetSolVals(scip, newmastersol, nmastervars, mastervars, restmastervals) );
257 
258 #ifdef SCIP_DEBUG
259  SCIP_CALL( SCIPtrySolFree(scip, &newmastersol, TRUE, TRUE, TRUE, TRUE, TRUE, success) );
260 #else
261  SCIP_CALL( SCIPtrySolFree(scip, &newmastersol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
262 #endif
263 
264  SCIPfreeBufferArray(scip, &restmastervals);
265 
266  return SCIP_OKAY;
267 }
268 
269 
270 /*
271  * Callback methods of primal heuristic
272  */
273 
274 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
275 #define heurCopyRestmaster NULL
276 
277 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
278 static
279 SCIP_DECL_HEURFREE(heurFreeRestmaster)
280 { /*lint --e{715}*/
281  SCIP_HEURDATA* heurdata;
282 
283  assert(heur != NULL);
284  assert(scip != NULL);
285 
286  /* get heuristic data */
287  heurdata = SCIPheurGetData(heur);
288  assert(heurdata != NULL);
289 
290  /* free heuristic data */
291  SCIPfreeMemory(scip, &heurdata);
292  SCIPheurSetData(heur, NULL);
293 
294  return SCIP_OKAY;
295 }
296 
297 
298 /** initialization method of primal heuristic (called after problem was transformed) */
299 static
300 SCIP_DECL_HEURINIT(heurInitRestmaster)
301 { /*lint --e{715}*/
302  SCIP_HEURDATA* heurdata;
303 
304  assert(heur != NULL);
305  assert(scip != NULL);
306 
307  /* get heuristic's data */
308  heurdata = SCIPheurGetData(heur);
309  assert(heurdata != NULL);
310 
311  /* initialize data */
312  heurdata->usednodes = 0;
313 
314  /* change timing to after node, call heuristic only at root and increase maxnodes for price-and-branch heuristic */
315  if( heurdata->pbheur )
316  {
317  heurdata->maxnodes = INT_MAX;
318 
319  SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERNODE);
320  SCIPheurSetFreq(heur, 0);
321  }
322 
323  return SCIP_OKAY;
324 }
325 
326 
327 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
328 #define heurExitRestmaster NULL
329 
330 
331 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
332 #define heurInitsolRestmaster NULL
333 
334 
335 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
336 #define heurExitsolRestmaster NULL
337 
338 
339 /** execution method of primal heuristic */
340 static
341 SCIP_DECL_HEUREXEC(heurExecRestmaster)
342 { /*lint --e{715}*/
343  SCIP* origprob; /* SCIP structure of original problem */
344  SCIP_HEURDATA* heurdata; /* heuristic's data */
345  SCIP_Real timelimit; /* timelimit for the subproblem */
346  SCIP_Real memorylimit;
347  SCIP_Bool discretization;
348  SCIP_Bool success;
349  SCIP_Longint nstallnodes; /* number of stalling nodes for the restricted master problem */
350 
351  SCIP* restmaster; /* SCIP structure of the restricted master problem */
352  SCIP_HASHMAP* varmapfw; /* mapping of master variables to restricted master variables */
353  SCIP_VAR** mastervars;
354  SCIP_VAR** restmastervars;
355  int nmastervars;
356 
357  int i;
358 
359 #ifdef NDEBUG
360  SCIP_RETCODE retstat;
361 #endif
362 
363  assert(heur != NULL);
364  assert(scip != NULL);
365  assert(result != NULL);
366  assert(SCIPhasCurrentNodeLP(scip));
367 
368  /* get original problem */
369  origprob = GCGmasterGetOrigprob(scip);
370  assert(origprob != NULL);
371 
372  /* get heuristic's data */
373  heurdata = SCIPheurGetData(heur);
374  assert(heurdata != NULL);
375 
376  *result = SCIP_DIDNOTRUN;
377 
378  /* this heuristic works only for the discretization approach */
379  SCIP_CALL( SCIPgetBoolParam(origprob, "relaxing/gcg/discretization", &discretization) );
380  if( !discretization )
381  return SCIP_OKAY;
382 
383  *result = SCIP_DELAYED;
384 
385  /* only call heuristic, if an optimal LP solution is at hand */
386  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
387  return SCIP_OKAY;
388 
389  *result = SCIP_DIDNOTRUN;
390 
391  /* calculate the maximal number of branching nodes until heuristic is aborted */
392  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(origprob));
393 
394  if( !heurdata->pbheur )
395  {
396  /* reward restricted master if it succeeded often */
397  nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
398  nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
399  nstallnodes += heurdata->nodesofs;
400 
401  /* determine the node limit for the current process */
402  nstallnodes -= heurdata->usednodes;
403  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
404 
405 
406  /* check whether we have enough nodes left to call subproblem solving */
407  if( nstallnodes < heurdata->minnodes )
408  {
409  /* SCIPdebugMessage("skipping Restricted Master Heuristic: nstallnodes=%"SCIP_LONGINT_FORMAT", minnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, heurdata->minnodes); */
410  return SCIP_OKAY;
411  }
412  }
413 
414  /* check whether there is enough time and memory left */
415  SCIP_CALL( SCIPgetRealParam(origprob, "limits/time", &timelimit) );
416  if( !SCIPisInfinity(origprob, timelimit) )
417  timelimit -= SCIPgetSolvingTime(origprob);
418  SCIP_CALL( SCIPgetRealParam(origprob, "limits/memory", &memorylimit) );
419  if( !SCIPisInfinity(origprob, memorylimit) )
420  memorylimit -= SCIPgetMemUsed(origprob)/1048576.0;
421  if( timelimit < 10.0 || memorylimit <= 0.0 )
422  return SCIP_OKAY;
423 
424  if( SCIPisStopped(scip) )
425  return SCIP_OKAY;
426 
427  SCIPdebugMessage("Executing Restricted Master Heuristic ...\n");
428 
429  *result = SCIP_DIDNOTFIND;
430 
431  /* get variable data of the master problem */
432  SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
433  assert(mastervars != NULL);
434  assert(nmastervars >= 0);
435 
436  /* initializing the subproblem */
437  SCIP_CALL( SCIPcreate(&restmaster) );
438 
439  /* create the variable mapping hash map */
440  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(restmaster), nmastervars) );
441  SCIP_CALL( SCIPallocBufferArray(scip, &restmastervars, nmastervars) );
442 
443  if( heurdata->uselprows )
444  {
445  char probname[SCIP_MAXSTRLEN];
446 
447  /* copy all plugins */
448  SCIP_CALL( SCIPincludeDefaultPlugins(restmaster) );
449 
450  /* get name of the original problem and add the string "_restricted" */
451  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_restricted", SCIPgetProbName(scip));
452 
453  /* create the subproblem */
454  SCIP_CALL( SCIPcreateProb(restmaster, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
455 
456  /* copy all variables */
457  SCIP_CALL( SCIPcopyVars(scip, restmaster, varmapfw, NULL, NULL, NULL, 0, TRUE) );
458  }
459  else
460  {
461  SCIP_Bool valid;
462 
463  valid = FALSE;
464 
465  SCIP_CALL( SCIPcopy(scip, restmaster, varmapfw, NULL, "restmaster", TRUE, FALSE, FALSE, TRUE, &valid) ); /** @todo check for thread safeness */
466 
467  if( heurdata->copycuts )
468  {
469  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
470  SCIP_CALL( SCIPcopyCuts(scip, restmaster, varmapfw, NULL, TRUE, NULL) );
471  }
472 
473  SCIPdebugMessage("Copying the SCIP instance was %s complete.\n", valid ? "" : "not ");
474  }
475 
476  for( i = 0; i < nmastervars; i++ )
477  restmastervars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, mastervars[i]);
478 
479  /* free hash map */
480  SCIPhashmapFree(&varmapfw);
481 
482  success = FALSE;
483 
484  /* set up restricted master problem by fixing variables to zero */
485  SCIP_CALL( setupSubproblem(scip, restmaster, restmastervars, heurdata->minfixingrate, heurdata->uselprows, heurdata->pbheur, &success) );
486  SCIPdebugMessage("restricted master problem: %d vars, %d cons, success=%u\n", SCIPgetNVars(restmaster), SCIPgetNConss(restmaster), success);
487 
488  /* do not abort subproblem on CTRL-C */
489  SCIP_CALL( SCIPsetBoolParam(restmaster, "misc/catchctrlc", FALSE) );
490 
491  /* disable output to console */
492  SCIP_CALL( SCIPsetIntParam(restmaster, "display/verblevel", 0) );
493 
494  /* if price-and-branch heuristic, set node limits according to original problem */
495  if( heurdata->pbheur )
496  nstallnodes = heurdata->maxnodes;
497 
498  /* set limits for the subproblem */
499  SCIP_CALL( SCIPsetLongintParam(restmaster, "limits/stallnodes", nstallnodes) );
500  SCIP_CALL( SCIPsetLongintParam(restmaster, "limits/nodes", heurdata->maxnodes) );
501  SCIP_CALL( SCIPsetRealParam(restmaster, "limits/time", timelimit) );
502  SCIP_CALL( SCIPsetRealParam(restmaster, "limits/memory", memorylimit) );
503 
504  /* set specific parameters only of price-and-branch is not used */
505  if( !heurdata->pbheur )
506  {
507  /* forbid recursive call of heuristics solving subMIPs */
508  SCIP_CALL( SCIPsetSubscipsOff(restmaster, TRUE) );
509  /* disable cutting plane separation */
510  SCIP_CALL( SCIPsetSeparating(restmaster, SCIP_PARAMSETTING_OFF, TRUE) );
511 
512  /* disable expensive presolving */
513  SCIP_CALL( SCIPsetPresolving(restmaster, SCIP_PARAMSETTING_FAST, TRUE) );
514 
515  /* use best estimate node selection */
516  if( SCIPfindNodesel(scip, "estimate") != NULL )
517  {
518  SCIP_CALL( SCIPsetIntParam(restmaster, "nodeselection/estimate/stdpriority", INT_MAX/4) );
519  }
520 
521  /* use inference branching */
522  if( SCIPfindBranchrule(scip, "inference") != NULL )
523  {
524  SCIP_CALL( SCIPsetIntParam(restmaster, "branching/inference/priority", INT_MAX/4) );
525  }
526 
527  /* disable conflict analysis */
528  if( !SCIPisParamFixed(restmaster, "conflict/enable") )
529  {
530  SCIP_CALL( SCIPsetBoolParam(restmaster, "conflict/enable", FALSE) );
531  }
532  }
533 
534  /* if the subproblem could not be created, free memory and return */
535  if( !success )
536  {
537  SCIPdebugMessage("restricted master problem not created.\n");
538  *result = SCIP_DIDNOTRUN;
539  SCIPfreeBufferArray(scip, &restmastervars);
540  SCIP_CALL( SCIPfree(&restmaster) );
541  return SCIP_OKAY;
542  }
543 
544  /* if there is already a solution, add an objective cutoff */
545  /* @todo origprob or scip? */
546  if( SCIPgetNSols(origprob) > 0 )
547  {
548  SCIP_Real cutoff; /* objective cutoff for the restricted master problem */
549  SCIP_Real upperbound;
550  assert(!SCIPisInfinity(origprob,SCIPgetUpperbound(origprob)));
551 
552  upperbound = SCIPgetUpperbound(origprob) - SCIPsumepsilon(origprob);
553 
554  if( !SCIPisInfinity(origprob,-1.0*SCIPgetLowerbound(origprob)) )
555  {
556  cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(origprob) + heurdata->minimprove*SCIPgetLowerbound(origprob);
557  }
558  else
559  {
560  if( SCIPgetUpperbound ( origprob ) >= 0 )
561  cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( origprob );
562  else
563  cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( origprob );
564  }
565  cutoff = MIN(upperbound, cutoff);
566  SCIP_CALL( SCIPsetObjlimit(restmaster, cutoff) );
567  }
568 
569  /* solve the restricted master problem */
570  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
571  * Hence in optimized mode, the return code is catched and a warning is printed, only in debug mode, SCIP will stop.
572  */
573 #ifdef NDEBUG
574  retstat = SCIPpresolve(restmaster);
575  if( retstat != SCIP_OKAY )
576  {
577  SCIPwarningMessage(scip, "Error while presolving subMIP in Restricted Master Heuristic; Restricted Master terminated with code <%d>\n",retstat);
578  }
579 #else
580  SCIP_CALL( SCIPpresolve(restmaster) );
581 #endif
582 
583  SCIPdebugMessage("presolved restricted master problem: %d vars, %d cons, success=%u\n", SCIPgetNVars(restmaster), SCIPgetNConss(restmaster), success);
584 
585  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
586  * to ensure that not only the MIP but also the LP relaxation is easy enough
587  */
588  if( heurdata->pbheur || ( nmastervars - SCIPgetNVars(restmaster) ) / (SCIP_Real)nmastervars >= heurdata->minfixingrate / 2.0 )
589  {
590  SCIP_SOL** restmastersols;
591  int nrestmastersols;
592 
593  SCIPdebugMessage("solving restricted master problem: nstallnodes=%"SCIP_LONGINT_FORMAT", maxnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, heurdata->maxnodes);
594 
595 #ifdef NDEBUG
596  retstat = SCIPsolve(restmaster);
597  if( retstat != SCIP_OKAY )
598  {
599  SCIPwarningMessage(scip, "Error while solving subMIP in Restricted Master Heuristic; Restricted Master terminated with code <%d>\n",retstat);
600  }
601 #else
602  SCIP_CALL( SCIPsolve(restmaster) );
603 #endif
604 
605  SCIPdebugMessage(" -> %d feasible solution(s) found.\n", SCIPgetNSols(restmaster));
606 
607  /* check, whether a solution was found;
608  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
609  */
610  nrestmastersols = SCIPgetNSols(restmaster);
611  restmastersols = SCIPgetSols(restmaster);
612  success = FALSE;
613  for( i = 0; i < nrestmastersols && !success; ++i )
614  {
615  SCIP_CALL( createNewSol(origprob, scip, restmaster, restmastervars, heur, restmastersols[i], &success) );
616  }
617  if( success )
618  *result = SCIP_FOUNDSOL;
619  }
620 
621  /* free subproblem */
622  SCIPfreeBufferArray(scip, &restmastervars);
623  SCIP_CALL( SCIPfree(&restmaster) );
624 
625 
626  return SCIP_OKAY;
627 }
628 
629 
630 
631 
632 /*
633  * primal heuristic specific interface methods
634  */
635 
636 /** creates the Restricted Master primal heuristic and includes it in SCIP */
638  SCIP* scip /**< SCIP data structure */
639  )
640 {
641  SCIP_HEURDATA* heurdata;
642 
643  /* create Restricted Master primal heuristic data */
644  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
645 
646  /* include primal heuristic */
647  SCIP_CALL( SCIPincludeHeur(scip, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
649  heurCopyRestmaster, heurFreeRestmaster, heurInitRestmaster, heurExitRestmaster,
650  heurInitsolRestmaster, heurExitsolRestmaster, heurExecRestmaster,
651  heurdata) );
652 
653  /* add Restricted Master primal heuristic parameters */
654  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minfixingrate",
655  "minimum percentage of integer variables that have to be fixable ",
656  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
657 
658  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
659  "maximum number of nodes to regard in the subproblem",
660  &heurdata->maxnodes, TRUE,DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
661 
662  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
663  "number of nodes added to the contingent of the total nodes",
664  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
665 
666  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
667  "minimum number of nodes required to start the subproblem",
668  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
669 
670  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
671  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
672  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
673 
674  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
675  "factor by which restricted master should at least improve the incumbent ",
676  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
677 
678  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/uselprows",
679  "should subproblem be created out of the rows in the LP rows?",
680  &heurdata->uselprows, TRUE, DEFAULT_USELPROWS, NULL, NULL) );
681 
682  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
683  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
684  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
685 
686  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/pbheur",
687  "should the restricted master heuristic be used as price-and-branch heuristic?",
688  &heurdata->pbheur, FALSE, DEFAULT_PBHEUR, NULL, NULL) );
689 
690  return SCIP_OKAY;
691 }
#define DEFAULT_MINIMPROVE
GCG interface methods.
#define DEFAULT_USELPROWS
SCIP_Bool pbheur
Restricted Master Heuristic.
SCIP_Real minimprove
Definition: heur_gcgdins.c:80
#define DEFAULT_NODESOFS
#define HEUR_MAXDEPTH
#define heurExitsolRestmaster
#define HEUR_FREQOFS
static SCIP_RETCODE setupSubproblem(SCIP *scip, SCIP *restmaster, SCIP_VAR **restmastervars, SCIP_Real minfixingrate, SCIP_Bool uselprows, SCIP_Bool pbheur, SCIP_Bool *success)
#define DEFAULT_MINNODES
SCIP_Bool copycuts
Definition: heur_gcgdins.c:89
SCIP_Longint nodesofs
Definition: heur_gcgdins.c:76
GCG variable pricer.
#define HEUR_USESSUBSCIP
#define heurInitsolRestmaster
#define HEUR_FREQ
#define DEFAULT_PBHEUR
#define HEUR_DISPCHAR
static SCIP_DECL_HEURINIT(heurInitRestmaster)
#define DEFAULT_MINFIXINGRATE
#define HEUR_PRIORITY
#define HEUR_TIMING
#define HEUR_NAME
static SCIP_DECL_HEURFREE(heurFreeRestmaster)
SCIP_Longint maxnodes
Definition: heur_gcgdins.c:77
#define heurCopyRestmaster
static SCIP_DECL_HEUREXEC(heurExecRestmaster)
#define DEFAULT_NODESQUOT
SCIP * GCGmasterGetOrigprob(SCIP *scip)
#define DEFAULT_MAXNODES
SCIP_RETCODE SCIPincludeHeurRestmaster(SCIP *scip)
#define heurExitRestmaster
static SCIP_RETCODE createNewSol(SCIP *origprob, SCIP *scip, SCIP *restmaster, SCIP_VAR **restmastervars, SCIP_HEUR *heur, SCIP_SOL *restmastersol, SCIP_Bool *success)
#define HEUR_DESC
SCIP_Bool uselprows
Definition: heur_gcgdins.c:88
#define DEFAULT_COPYCUTS
SCIP_Longint usednodes
Definition: heur_gcgdins.c:81
SCIP_Longint minnodes
Definition: heur_gcgdins.c:78
SCIP_Real minfixingrate
Definition: heur_gcgrens.c:84
SCIP_Real nodesquot
Definition: heur_gcgdins.c:82