heur_gcgpscostdiving.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-2018 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 
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_gcgpscostdiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcgpscostdiving"
45 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the pseudo cost values"
46 #define HEUR_DISPCHAR 'p'
47 #define HEUR_PRIORITY -1002000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 2
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 #define DEFAULT_USEMASTERPSCOSTS FALSE
60 /* locally defined diving heuristic data */
61 struct GCG_DivingData
62 {
63  SCIP_Bool usemasterpscosts;
64  SCIP_SOL* rootsol;
65  SCIP_Bool firstrun;
66  SCIP_Real* masterpscosts;
67 };
68 
69 
70 /*
71  * local methods
72  */
73 
75 static
76 SCIP_RETCODE getRootRelaxSol(
77  SCIP* scip,
78  SCIP_SOL** rootsol
79  )
80 {
81  SCIP* masterprob;
82  SCIP_SOL* masterrootsol;
83  SCIP_VAR** mastervars;
84  int nmastervars;
85  int i;
86 
87  /* get master problem */
88  masterprob = GCGgetMasterprob(scip);
89  assert(masterprob != NULL);
90 
91  /* allocate memory for master root LP solution */
92  SCIP_CALL( SCIPcreateSol(masterprob, &masterrootsol, NULL) );
93 
94  /* get master variable information */
95  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
96  assert(mastervars != NULL);
97  assert(nmastervars >= 0);
98 
99  /* store root LP values in working master solution */
100  for( i = 0; i < nmastervars; i++ )
101  SCIP_CALL( SCIPsetSolVal(masterprob, masterrootsol, mastervars[i], SCIPvarGetRootSol(mastervars[i])) );
102 
103  /* calculate original root LP solution */
104  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, masterrootsol, rootsol) );
105 
106  /* free memory */
107  SCIP_CALL( SCIPfreeSol(masterprob, &masterrootsol) );
108 
109  return SCIP_OKAY;
110 }
111 
113 static
114 SCIP_RETCODE calcMasterPscosts(
115  SCIP* scip,
116  SCIP_Real** masterpscosts
117  )
118 {
119  SCIP* masterprob;
120  SCIP_VAR** mastervars;
121  int nbinvars;
122  int nintvars;
123 
124  int i;
125  int j;
126 
127  /* get master problem */
128  masterprob = GCGgetMasterprob(scip);
129  assert(masterprob != NULL);
130 
131  /* get master variable data */
132  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, NULL, &nbinvars, &nintvars, NULL, NULL) );
133 
134  /* allocate memory */
135  SCIP_CALL( SCIPallocBufferArray(scip, masterpscosts, nbinvars + nintvars) );
136 
137  /* calculate pseudocosts */
138  for( i = 0; i < nbinvars + nintvars; ++i )
139  {
140  SCIP_VAR* mastervar;
141  SCIP_VAR** masterorigvars;
142  SCIP_Real* masterorigvals;
143  int nmasterorigvars;
144 
145  mastervar = mastervars[i];
146  masterorigvars = GCGmasterVarGetOrigvars(mastervar);
147  masterorigvals = GCGmasterVarGetOrigvals(mastervar);
148  nmasterorigvars = GCGmasterVarGetNOrigvars(mastervar);
149 
150  (*masterpscosts)[i] = 0.0;
151  for( j = 0; j < nmasterorigvars; ++j )
152  {
153  SCIP_VAR* origvar;
154 
155  origvar = masterorigvars[j];
156  if( !SCIPvarIsBinary(origvar) && !SCIPvarIsIntegral(origvar) )
157  continue;
158  (*masterpscosts)[i] += SCIPgetVarPseudocostVal(scip, origvar, 0.0-masterorigvals[j]);
159  }
160  }
161 
162  return SCIP_OKAY;
163 }
164 
166 static
168  SCIP_VAR* origvar,
169  SCIP_VAR* mastervar
170  )
171 {
172  int origblock;
173  int masterblock;
174 
175  /* get the blocks the variables belong to */
176  origblock = GCGvarGetBlock(origvar);
177  masterblock = GCGvarGetBlock(mastervar);
178 
179  /* the original variable is a linking variable:
180  * check whether the master variable is either its direct copy
181  * or in one of its blocks
182  */
183  if( GCGoriginalVarIsLinking(origvar) )
184  {
185  assert(origblock == -2);
186  if( masterblock == -1 )
187  {
188  SCIP_VAR** mastervars;
189 
190  mastervars = GCGoriginalVarGetMastervars(origvar);
191 
192  return mastervars[0] == mastervar;
193  }
194  else
195  {
196  assert(masterblock >= 0);
197  return GCGisLinkingVarInBlock(origvar, masterblock);
198  }
199  }
200  /* the original variable was directly copied to the master problem:
201  * check whether the master variable is its copy
202  */
203  else if( origblock == -1 )
204  {
205  SCIP_VAR** mastervars;
206 
207  mastervars = GCGoriginalVarGetMastervars(origvar);
208  assert(GCGoriginalVarGetNMastervars(origvar) == 1);
209 
210  return mastervars[0] == mastervar;
211  }
212  /* the original variable belongs to exactly one block */
213  else
214  {
215  assert(origblock >= 0);
216  return origblock == masterblock;
217  }
218 }
219 
221 static
222 SCIP_RETCODE calcPscostDownMaster(
223  SCIP* scip,
224  SCIP_VAR* var,
225  SCIP_Real* masterpscosts,
226  SCIP_Real* pscostdown
227  )
228 {
229  SCIP* masterprob;
230  SCIP_VAR** mastervars;
231  SCIP_VAR** origmastervars;
232  SCIP_Real* origmastervals;
233  int nbinmastervars;
234  int nintmastervars;
235  int norigmastervars;
236  SCIP_Real roundval;
237  SCIP_Real masterlpval;
238  int idx;
239 
240  int i;
241 
242  /* get master problem */
243  masterprob = GCGgetMasterprob(scip);
244  assert(masterprob != NULL);
245 
246  /* get master variable information */
247  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, NULL, &nbinmastervars, &nintmastervars, NULL, NULL) );
248 
249  /* get master variables in which the original variable appears */
250  origmastervars = GCGoriginalVarGetMastervars(var);
251  origmastervals = GCGoriginalVarGetMastervals(var);
252  norigmastervars = GCGoriginalVarGetNMastervars(var);
253 
254  roundval = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var));
255  *pscostdown = 0.0;
256 
257  /* calculate sum of pseudocosts over all master variables
258  * which would violate the new original variable bound
259  */
260  if( SCIPisFeasNegative(masterprob, roundval) )
261  {
262  for( i = 0; i < nbinmastervars + nintmastervars; ++i )
263  {
264  if( areVarsInSameBlock(var, mastervars[i]) )
265  {
266  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
267  *pscostdown += masterpscosts[i] * SCIPfeasFrac(masterprob, masterlpval);
268  }
269  }
270  for( i = 0; i < norigmastervars; ++i )
271  {
272  idx = SCIPvarGetProbindex(origmastervars[i]);
273  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
274  if( (SCIPvarIsBinary(origmastervars[i]) || SCIPvarIsIntegral(origmastervars[i]) )
275  && SCIPisFeasLE(masterprob, origmastervals[i], roundval) )
276  *pscostdown -= masterpscosts[idx] * SCIPfeasFrac(masterprob, masterlpval);
277  }
278  }
279  else
280  {
281  for( i = 0; i < norigmastervars; ++i )
282  {
283  idx = SCIPvarGetProbindex(origmastervars[i]);
284  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
285  if( (SCIPvarIsBinary(origmastervars[i]) || SCIPvarIsIntegral(origmastervars[i]) )
286  && SCIPisFeasGT(masterprob, origmastervals[i], roundval) )
287  *pscostdown += masterpscosts[idx] * SCIPfeasFrac(masterprob, masterlpval);
288  }
289  }
290 
291  return SCIP_OKAY;
292 }
293 
295 static
296 SCIP_RETCODE calcPscostUpMaster(
297  SCIP* scip,
298  SCIP_VAR* var,
299  SCIP_Real* masterpscosts,
300  SCIP_Real* pscostup
301  )
302 {
303  SCIP* masterprob;
304  SCIP_VAR** mastervars;
305  SCIP_VAR** origmastervars;
306  SCIP_Real* origmastervals;
307  int nbinmastervars;
308  int nintmastervars;
309  int norigmastervars;
310  SCIP_Real roundval;
311  SCIP_Real masterlpval;
312  int idx;
313 
314  int i;
315 
316  /* get master problem */
317  masterprob = GCGgetMasterprob(scip);
318  assert(masterprob != NULL);
319 
320  /* get master variable information */
321  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, NULL, &nbinmastervars, &nintmastervars, NULL, NULL) );
322 
323  /* get master variables in which the original variable appears */
324  origmastervars = GCGoriginalVarGetMastervars(var);
325  origmastervals = GCGoriginalVarGetMastervals(var);
326  norigmastervars = GCGoriginalVarGetNMastervars(var);
327 
328  roundval = SCIPfeasCeil(scip, SCIPgetRelaxSolVal(scip, var));
329  *pscostup = 0.0;
330 
331  /* calculate sum of pseudocosts over all master variables
332  * which would violate the new original variable bound
333  */
334  if( SCIPisFeasPositive(masterprob, roundval) )
335  {
336  for( i = 0; i < nbinmastervars + nintmastervars; ++i )
337  {
338  if( areVarsInSameBlock(var, mastervars[i]) )
339  {
340  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
341  *pscostup += masterpscosts[i] * SCIPfeasFrac(masterprob, masterlpval);
342  }
343  }
344  for( i = 0; i < norigmastervars; ++i )
345  {
346  idx = SCIPvarGetProbindex(origmastervars[i]);
347  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
348  if( (SCIPvarIsBinary(origmastervars[i]) || SCIPvarIsIntegral(origmastervars[i]) )
349  && SCIPisFeasGE(masterprob, origmastervals[i], roundval) )
350  *pscostup -= masterpscosts[idx] * SCIPfeasFrac(masterprob, masterlpval);
351  }
352  }
353  else
354  {
355  for( i = 0; i < norigmastervars; ++i )
356  {
357  idx = SCIPvarGetProbindex(origmastervars[i]);
358  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
359  if( (SCIPvarIsBinary(origmastervars[i]) || SCIPvarIsIntegral(origmastervars[i]) )
360  && SCIPisFeasLT(masterprob, origmastervals[i], roundval) )
361  *pscostup += masterpscosts[idx] * SCIPfeasFrac(masterprob, masterlpval);
362  }
363  }
364 
365  return SCIP_OKAY;
366 }
367 
369 static
370 SCIP_RETCODE calcPscostQuot(
371  SCIP* scip,
372  GCG_DIVINGDATA* divingdata,
373  SCIP_VAR* var,
374  SCIP_Real primsol,
375  SCIP_Real rootsolval,
376  SCIP_Real frac,
377  int rounddir,
378  SCIP_Real* pscostquot,
379  SCIP_Bool* roundup
380  )
381 {
382  SCIP_Real pscostdown;
383  SCIP_Real pscostup;
384 
385  assert(pscostquot != NULL);
386  assert(roundup != NULL);
387  assert(SCIPisEQ(scip, frac, primsol - SCIPfeasFloor(scip, primsol)));
388 
389  /* bound fractions to not prefer variables that are nearly integral */
390  frac = MAX(frac, 0.1);
391  frac = MIN(frac, 0.9);
392 
393  /* get pseudo cost quotient */
394  if( divingdata->usemasterpscosts )
395  {
396  SCIP_CALL( calcPscostDownMaster(scip, var, divingdata->masterpscosts, &pscostdown) );
397  SCIP_CALL( calcPscostUpMaster(scip, var, divingdata->masterpscosts, &pscostup) );
398  }
399  else
400  {
401  pscostdown = SCIPgetVarPseudocostVal(scip, var, 0.0-frac);
402  pscostup = SCIPgetVarPseudocostVal(scip, var, 1.0-frac);
403  }
404  SCIPdebugMessage("Pseudocosts of variable %s: %g down, %g up\n", SCIPvarGetName(var), pscostdown, pscostup);
405  assert(!SCIPisNegative(scip, pscostdown) && !SCIPisNegative(scip,pscostup));
406 
407  /* choose rounding direction */
408  if( rounddir == -1 )
409  *roundup = FALSE;
410  else if( rounddir == +1 )
411  *roundup = TRUE;
412  else if( primsol < rootsolval - 0.4 )
413  *roundup = FALSE;
414  else if( primsol > rootsolval + 0.4 )
415  *roundup = TRUE;
416  else if( frac < 0.3 )
417  *roundup = FALSE;
418  else if( frac > 0.7 )
419  *roundup = TRUE;
420  else if( pscostdown < pscostup )
421  *roundup = FALSE;
422  else
423  *roundup = TRUE;
424 
425  /* calculate pseudo cost quotient */
426  if( *roundup )
427  *pscostquot = sqrt(frac) * (1.0+pscostdown) / (1.0+pscostup);
428  else
429  *pscostquot = sqrt(1.0-frac) * (1.0+pscostup) / (1.0+pscostdown);
430 
431  /* prefer decisions on binary variables */
432  if( SCIPvarIsBinary(var) )
433  (*pscostquot) *= 1000.0;
434 
435  return SCIP_OKAY;
436 }
437 
438 
439 /*
440  * Callback methods
441  */
442 
444 static
445 GCG_DECL_DIVINGFREE(heurFreeGcgpscostdiving) /*lint --e{715}*/
446 { /*lint --e{715}*/
447  GCG_DIVINGDATA* divingdata;
448 
449  assert(heur != NULL);
450  assert(scip != NULL);
451 
452  /* free diving rule specific data */
453  divingdata = GCGheurGetDivingDataOrig(heur);
454  assert(divingdata != NULL);
455  SCIPfreeMemory(scip, &divingdata);
456  GCGheurSetDivingDataOrig(heur, NULL);
457 
458  return SCIP_OKAY;
459 }
460 
461 
463 static
464 GCG_DECL_DIVINGINIT(heurInitGcgpscostdiving) /*lint --e{715}*/
465 { /*lint --e{715}*/
466  GCG_DIVINGDATA* divingdata;
467 
468  assert(heur != NULL);
469 
470  /* get diving data */
471  divingdata = GCGheurGetDivingDataOrig(heur);
472  assert(divingdata != NULL);
473 
474  /* initialize data */
475  divingdata->firstrun = TRUE;
476  divingdata->rootsol = NULL;
477  divingdata->masterpscosts = NULL;
478 
479  return SCIP_OKAY;
480 }
481 
482 
484 static
485 GCG_DECL_DIVINGEXIT(heurExitGcgpscostdiving) /*lint --e{715}*/
486 { /*lint --e{715}*/
487  GCG_DIVINGDATA* divingdata;
488 
489  assert(heur != NULL);
490 
491  /* get diving data */
492  divingdata = GCGheurGetDivingDataOrig(heur);
493  assert(divingdata != NULL);
494 
495  assert(divingdata->firstrun == TRUE || divingdata->rootsol != NULL);
496 
497  /* free root relaxation solution */
498  if( divingdata->rootsol != NULL )
499  SCIP_CALL( SCIPfreeSol(scip, &divingdata->rootsol) );
500 
501  return SCIP_OKAY;
502 }
503 
504 
506 static
507 GCG_DECL_DIVINGINITEXEC(heurInitexecGcgpscostdiving) /*lint --e{715}*/
508 { /*lint --e{715}*/
509  GCG_DIVINGDATA* divingdata;
510 
511  assert(heur != NULL);
512 
513  /* get diving data */
514  divingdata = GCGheurGetDivingDataOrig(heur);
515  assert(divingdata != NULL);
516 
517  /* if the heuristic is running for the first time, the root relaxation solution needs to be stored */
518  if( divingdata->firstrun )
519  {
520  assert(divingdata->rootsol == NULL);
521  SCIP_CALL( getRootRelaxSol(scip, &divingdata->rootsol) );
522  assert(divingdata->rootsol != NULL);
523  divingdata->firstrun = FALSE;
524  }
525 
526  SCIP_CALL( calcMasterPscosts(scip, &divingdata->masterpscosts) );
527 
528  return SCIP_OKAY;
529 }
530 
531 
533 static
534 GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgpscostdiving) /*lint --e{715}*/
535 { /*lint --e{715}*/
536  GCG_DIVINGDATA* divingdata;
537 
538  assert(heur != NULL);
539 
540  /* get diving data */
541  divingdata = GCGheurGetDivingDataOrig(heur);
542  assert(divingdata != NULL);
543 
544  /* free memory */
545  SCIPfreeBufferArray(scip, &divingdata->masterpscosts);
546 
547  return SCIP_OKAY;
548 }
549 
550 
560 static
561 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgpscostdiving) /*lint --e{715}*/
562 { /*lint --e{715}*/
563  GCG_DIVINGDATA* divingdata;
564  SCIP_VAR** lpcands;
565  SCIP_Real* lpcandssol;
566  int nlpcands;
567  SCIP_Bool bestcandmayrounddown;
568  SCIP_Bool bestcandmayroundup;
569  SCIP_Real bestpscostquot;
570  int c;
571 
572  /* check preconditions */
573  assert(scip != NULL);
574  assert(heur != NULL);
575  assert(bestcand != NULL);
576  assert(bestcandmayround != NULL);
577  assert(bestcandroundup != NULL);
578 
579  /* get diving data */
580  divingdata = GCGheurGetDivingDataOrig(heur);
581  assert(divingdata != NULL);
582  assert(divingdata->rootsol != NULL);
583 
584  /* get fractional variables that should be integral */
585  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
586  assert(lpcands != NULL);
587  assert(lpcandssol != NULL);
588 
589  bestcandmayrounddown = TRUE;
590  bestcandmayroundup = TRUE;
591  bestpscostquot = -1.0;
592 
593  /* get best candidate */
594  for( c = 0; c < nlpcands; ++c )
595  {
596  SCIP_VAR* var;
597  SCIP_Real primsol;
598 
599  SCIP_Bool mayrounddown;
600  SCIP_Bool mayroundup;
601  SCIP_Bool roundup;
602  SCIP_Real frac;
603  SCIP_Real pscostquot;
604  SCIP_Real rootsolval;
605 
606  int i;
607 
608  var = lpcands[c];
609 
610  /* if the variable is on the tabu list, do not choose it */
611  for( i = 0; i < tabulistsize; ++i )
612  if( tabulist[i] == var )
613  break;
614  if( i < tabulistsize )
615  continue;
616 
617  mayrounddown = SCIPvarMayRoundDown(var);
618  mayroundup = SCIPvarMayRoundUp(var);
619  primsol = lpcandssol[c];
620  rootsolval = SCIPgetSolVal(scip, divingdata->rootsol, var);
621  frac = lpcandssol[c] - SCIPfloor(scip, lpcandssol[c]);
622 
623  if( mayrounddown || mayroundup )
624  {
625  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
626  if( bestcandmayrounddown || bestcandmayroundup )
627  {
628  /* choose rounding direction:
629  * - if variable may be rounded in both directions, round corresponding to the pseudo cost values
630  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
631  * the current fractional solution
632  */
633  roundup = FALSE;
634  if( mayrounddown && mayroundup )
635  {
636  SCIP_CALL( calcPscostQuot(scip, divingdata, var, primsol, rootsolval, frac, 0, &pscostquot, &roundup) );
637  }
638  else if( mayrounddown )
639  {
640  SCIP_CALL( calcPscostQuot(scip, divingdata, var, primsol, rootsolval, frac, +1, &pscostquot, &roundup) );
641  }
642  else
643  {
644  SCIP_CALL( calcPscostQuot(scip, divingdata, var, primsol, rootsolval, frac, -1, &pscostquot, &roundup) );
645  }
646 
647  /* check, if candidate is new best candidate */
648  if( pscostquot > bestpscostquot )
649  {
650  *bestcand = var;
651  bestpscostquot = pscostquot;
652  bestcandmayrounddown = mayrounddown;
653  bestcandmayroundup = mayroundup;
654  *bestcandroundup = roundup;
655  }
656  }
657  }
658  else
659  {
660  /* the candidate may not be rounded: calculate pseudo cost quotient and preferred direction */
661  SCIP_CALL( calcPscostQuot(scip, divingdata, var, primsol, rootsolval, frac, 0, &pscostquot, &roundup) );
662 
663  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
664  if( bestcandmayrounddown || bestcandmayroundup || pscostquot > bestpscostquot )
665  {
666  *bestcand = var;
667  bestpscostquot = pscostquot;
668  bestcandmayrounddown = FALSE;
669  bestcandmayroundup = FALSE;
670  *bestcandroundup = roundup;
671  }
672  }
673  }
674 
675  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
676 
677  return SCIP_OKAY;
678 }
679 
680 
681 /*
682  * heuristic specific interface methods
683  */
684 
687  SCIP* scip
688  )
689 {
690  SCIP_HEUR* heur;
691  GCG_DIVINGDATA* divingdata;
692 
693  /* create gcgpscostdiving primal heuristic data */
694  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
695 
696  /* include diving heuristic */
697  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
699  HEUR_MAXDEPTH, heurFreeGcgpscostdiving, heurInitGcgpscostdiving, heurExitGcgpscostdiving, NULL, NULL,
700  heurInitexecGcgpscostdiving, heurExitexecGcgpscostdiving, heurSelectVarGcgpscostdiving, divingdata) );
701 
702  assert(heur != NULL);
703 
704  /* add gcgpscostdiving specific parameters */
705  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usemasterpscosts",
706  "shall pseudocosts be calculated w.r.t. the master problem?",
707  &divingdata->usemasterpscosts, TRUE, DEFAULT_USEMASTERPSCOSTS, NULL, NULL) );
708 
709  return SCIP_OKAY;
710 }
711 
GCG interface methods.
#define HEUR_DISPCHAR
static SCIP_RETCODE calcMasterPscosts(SCIP *scip, SCIP_Real **masterpscosts)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
static GCG_DECL_DIVINGINITEXEC(heurInitexecGcgpscostdiving)
static SCIP_Bool areVarsInSameBlock(SCIP_VAR *origvar, SCIP_VAR *mastervar)
#define HEUR_PRIORITY
SCIP_RETCODE GCGincludeDivingHeurOrig(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, GCG_DECL_DIVINGFREE((*divingfree)), GCG_DECL_DIVINGINIT((*divinginit)), GCG_DECL_DIVINGEXIT((*divingexit)), GCG_DECL_DIVINGINITSOL((*divinginitsol)), GCG_DECL_DIVINGEXITSOL((*divingexitsol)), GCG_DECL_DIVINGINITEXEC((*divinginitexec)), GCG_DECL_DIVINGEXITEXEC((*divingexitexec)), GCG_DECL_DIVINGSELECTVAR((*divingselectvar)), GCG_DIVINGDATA *divingdata)
SCIP_Real * masterpscosts
LP diving heuristic that chooses fixings w.r.t. the pseudo cost values.
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:965
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
SCIP_Bool usemasterpscosts
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:888
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
static SCIP_RETCODE calcPscostDownMaster(SCIP *scip, SCIP_VAR *var, SCIP_Real *masterpscosts, SCIP_Real *pscostdown)
primal heuristic interface for LP diving heuristics on the original variables
#define HEUR_MAXDEPTH
static SCIP_RETCODE calcPscostQuot(SCIP *scip, GCG_DIVINGDATA *divingdata, SCIP_VAR *var, SCIP_Real primsol, SCIP_Real rootsolval, SCIP_Real frac, int rounddir, SCIP_Real *pscostquot, SCIP_Bool *roundup)
#define HEUR_FREQ
static GCG_DECL_DIVINGFREE(heurFreeGcgpscostdiving)
#define HEUR_NAME
SCIP_RETCODE GCGincludeHeurGcgpscostdiving(SCIP *scip)
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgpscostdiving)
static GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgpscostdiving)
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:846
#define HEUR_FREQOFS
#define HEUR_DESC
static GCG_DECL_DIVINGINIT(heurInitGcgpscostdiving)
static GCG_DECL_DIVINGEXIT(heurExitGcgpscostdiving)
#define DEFAULT_USEMASTERPSCOSTS
static SCIP_RETCODE calcPscostUpMaster(SCIP *scip, SCIP_VAR *var, SCIP_Real *masterpscosts, SCIP_Real *pscostup)
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:545
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:866
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:561
SCIP_Real * GCGoriginalVarGetMastervals(SCIP_VAR *var)
Definition: gcgvar.c:577
void GCGheurSetDivingDataOrig(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
SCIP_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:124
static SCIP_RETCODE getRootRelaxSol(SCIP *scip, SCIP_SOL **rootsol)