relax_gcg.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 
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 
44 //#define SCIP_DEBUG
45 
46 #include <string.h>
47 
48 #include "scip/scipdefplugins.h"
49 #include "scip/cons_linear.h"
50 #include "scip/cons_setppc.h"
51 #include "scip/scip.h"
52 #include "scip/misc.h"
53 
54 #include "relax_gcg.h"
55 
56 #include "struct_branchgcg.h"
57 
58 #include "cons_origbranch.h"
59 #include "cons_masterbranch.h"
60 #include "pricer_gcg.h"
61 #include "benders_gcg.h"
62 #include "masterplugins.h"
63 #include "bendersplugins.h"
64 #include "cons_decomp.h"
65 #include "scip_misc.h"
66 
67 
68 #include "gcg.h"
69 
70 #ifdef WITH_BLISS
71 #include "pub_bliss.h"
72 #include "bliss_automorph.h"
73 #endif
74 
75 #define RELAX_NAME "gcg"
76 #define RELAX_DESC "relaxator for gcg project representing the master lp"
77 #define RELAX_PRIORITY -1
78 #define RELAX_FREQ 1
79 #define RELAX_INCLUDESLP TRUE
80 
81 #define DEFAULT_DISCRETIZATION TRUE
82 #define DEFAULT_AGGREGATION TRUE
83 #define DEFAULT_DISPINFOS FALSE
84 #define DEFAULT_MODE DEC_DECMODE_DANTZIGWOLFE
86 #define DELVARS
87 
88 /*
89  * Data structures
90  */
91 
94 struct SCIP_RelaxData
95 {
96  /* problems and convexity constraints */
97  SCIP* masterprob;
98  SCIP* altmasterprob;
99  SCIP** pricingprobs;
104  SCIP_CONS** convconss;
110  /* hashmaps for transformation */
111  SCIP_HASHMAP* hashorig2origvar;
113  /* constraint data */
114  SCIP_CONS** masterconss;
115  SCIP_CONS** origmasterconss;
117  SCIP_CONS** linearmasterconss;
119  SCIP_CONS** varlinkconss;
124  SCIP_SOL* currentorigsol;
125  SCIP_Bool origsolfeasible;
126  SCIP_Longint lastmasterlpiters;
127  SCIP_SOL* lastmastersol;
128  SCIP_CONS** markedmasterconss;
130  SCIP_Longint lastsolvednodenr;
132  /* branchrule data */
136  /* parameter data */
137  SCIP_Bool discretization;
138  SCIP_Bool aggregation;
139  SCIP_Bool masterissetpart;
140  SCIP_Bool masterissetcover;
141  SCIP_Bool dispinfos;
145  /* data for probing */
146  SCIP_Bool masterinprobing;
147  SCIP_HEUR* probingheur;
148  SCIP_SOL* storedorigsol;
149  SCIP_Bool storedfeasibility;
151  /* structure information */
153  SCIP_Bool relaxisinitialized;
155  /* statistical information */
156  SCIP_Longint simplexiters;
158  /* filename information */
159  const char* filename;
160 };
161 
162 
163 /*
164  * Local methods
165  */
166 
168 static
169 SCIP_RETCODE setOriginalVarBlockNr(
170  SCIP* scip,
171  SCIP_RELAXDATA* relaxdata,
172  SCIP_VAR* var,
173  int newblock
174  )
175 {
176  int blocknr;
177 
178  assert(scip != NULL);
179  assert(var != NULL);
180  assert(newblock >= 0 || (GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS && newblock == -2));
181 
182  assert(SCIPvarIsOriginal(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
183  assert(relaxdata != NULL);
184 
185  blocknr = GCGvarGetBlock(var);
186  assert(GCGvarIsOriginal(var));
187 
188  assert(relaxdata->npricingprobs > 0);
189  assert(newblock < relaxdata->npricingprobs);
190  assert(blocknr >= -2 && blocknr < relaxdata->npricingprobs);
191 
192  /* var belongs to no block so far, just set the new block number */
193  if( blocknr == -1 )
194  {
195  assert(newblock >= 0);
196  GCGvarSetBlock(var, newblock);
197  }
198  /* if var already belongs to another block, it is a linking variable */
199  else if( blocknr != newblock )
200  {
201  SCIP_CALL( GCGoriginalVarAddBlock(scip, var, newblock, relaxdata->npricingprobs, relaxdata->mode) );
202  assert(newblock == -2 || GCGisLinkingVarInBlock(var, newblock));
203  assert(GCGoriginalVarIsLinking(var));
204  }
205  blocknr = GCGvarGetBlock(var);
206  assert(blocknr == -2 || blocknr == newblock);
207 
208  return SCIP_OKAY;
209 }
210 
212 static
213 SCIP_RETCODE markConsMaster(
214  SCIP* scip,
215  SCIP_RELAXDATA* relaxdata,
216  SCIP_CONS* cons
217  )
218 {
219 #ifndef NDEBUG
220  int i;
221 #endif
222  assert(scip != NULL);
223  assert(cons != NULL);
224  assert(relaxdata != NULL);
225 
226  /* allocate array, if not yet done */
227  if( relaxdata->markedmasterconss == NULL )
228  {
229  int nconss;
230  nconss = SCIPgetNConss(scip);
231  SCIP_CALL( SCIPallocMemoryArray(scip, &(relaxdata->markedmasterconss), nconss) );
232  relaxdata->nmarkedmasterconss = 0;
233  }
234  assert(relaxdata->nmarkedmasterconss <= SCIPgetNConss(scip));
235 
236 #ifndef NDEBUG
237  /* check that constraints are not marked more than one time */
238  for( i = 0; i < relaxdata->nmarkedmasterconss; i++ )
239  assert(relaxdata->markedmasterconss[i] != cons);
240 #endif
241 
242  /* save constraint */
243  relaxdata->markedmasterconss[relaxdata->nmarkedmasterconss] = cons;
244  relaxdata->nmarkedmasterconss++;
245 
246  return SCIP_OKAY;
247 }
248 
249 
251 static
252 SCIP_RETCODE convertStructToGCG(
253  SCIP* scip,
254  SCIP_RELAXDATA* relaxdata,
256  )
257 {
258  int i;
259  int j;
260  int k;
261  int v;
262  int nblocks;
263  int nvars;
264  SCIP_VAR** origvars;
265  SCIP_HASHMAP* transvar2origvar;
266  SCIP_CONS** linkingconss;
267  int nlinkingconss;
268  SCIP_VAR** linkingvars;
269  int nlinkingvars;
270  SCIP_VAR*** subscipvars;
271  int* nsubscipvars;
272  SCIP_CONS*** subscipconss;
273  int* nsubscipconss;
274 
275  assert(decdecomp != NULL);
276  assert(relaxdata != NULL);
277  assert(scip != NULL);
278 
281 
282 
285 
286 
287 
288  origvars = SCIPgetOrigVars(scip);
289  nvars = SCIPgetNOrigVars(scip);
290  linkingconss = DECdecompGetLinkingconss(decdecomp);
291  nlinkingconss = DECdecompGetNLinkingconss(decdecomp);
292  linkingvars = DECdecompGetLinkingvars(decdecomp);
294  subscipvars = DECdecompGetSubscipvars(decdecomp);
295  nsubscipvars = DECdecompGetNSubscipvars(decdecomp);
296 
297  subscipconss = DECdecompGetSubscipconss(decdecomp);
298  nsubscipconss = DECdecompGetNSubscipconss(decdecomp);
299  nblocks = DECdecompGetNBlocks(decdecomp);
300 
301  SCIP_CALL( SCIPhashmapCreate(&transvar2origvar, SCIPblkmem(scip), nvars) );
302  relaxdata->npricingprobs = nblocks;
303  SCIP_CALL( GCGcreateOrigVarsData(scip) );
304 
305  SCIPdebugMessage("Copying structure with %d blocks, %d linking vars and %d linking constraints.\n", nblocks, nlinkingvars, nlinkingconss);
306 
307  /* set master constraints */
308  for( i = 0; i < nlinkingconss; ++i )
309  {
310  assert(linkingconss[i] != NULL);
311  /* SCIPdebugMessage("\tProcessing linking constraint %s.\n", SCIPconsGetName(linkingconss[i])); */
312  if( SCIPconsIsActive(linkingconss[i]) )
313  {
314  SCIP_CALL( markConsMaster(scip, relaxdata, linkingconss[i]) );
315  }
316  }
317 
318  /* prepare the map from transformed to original variables */
319  for( i = 0; i < nvars; ++i )
320  {
321  SCIP_VAR* transvar;
322 
323  SCIP_CALL( SCIPgetTransformedVar(scip, origvars[i], &transvar) );
324  assert(transvar != NULL);
325 
326  SCIP_CALL( SCIPhashmapInsert(transvar2origvar, transvar, origvars[i]) );
327  }
328 
329  for( i = 0; i < nblocks; ++i )
330  {
331  /* SCIPdebugMessage("\tProcessing block %d (%d conss, %d vars).\n", i, nsubscipconss[i], nsubscipvars[i]); */
332  assert((subscipvars[i] == NULL) == (nsubscipvars[i] == 0));
333  for( j = 0; j < nsubscipvars[i]; ++j )
334  {
335  SCIP_VAR* relevantvar;
336  assert(subscipvars[i][j] != NULL);
337  relevantvar = SCIPvarGetProbvar(subscipvars[i][j]);
338 
339  /* If there is a corresponding original (untransformed) variable, assign it to the block */
340  if( SCIPhashmapGetImage(transvar2origvar, subscipvars[i][j]) != NULL )
341  {
342  SCIP_VAR* origvar;
343 
344  origvar = (SCIP_VAR*) SCIPhashmapGetImage(transvar2origvar, subscipvars[i][j]);
345  assert(SCIPvarGetData(origvar) != NULL);
346 
347  SCIP_CALL( setOriginalVarBlockNr(scip, relaxdata, origvar, i) );
348  SCIPdebugMessage("\t\tOriginal var %s (%p) in block %d\n", SCIPvarGetName(subscipvars[i][j]), (void*) subscipvars[i][j], i);
349  }
350 
351  /* Assign the corresponding problem variable to the block */
352  if( SCIPvarGetData(relevantvar) == NULL )
353  SCIP_CALL( GCGorigVarCreateData(scip, relevantvar) );
354  SCIP_CALL( setOriginalVarBlockNr(scip, relaxdata, relevantvar, i) );
355 
356  SCIPdebugMessage("\t\tTransformed var %s (%p) in block %d\n", SCIPvarGetName(relevantvar), (void*) relevantvar, i);
357 
358  assert(SCIPvarGetData(subscipvars[i][j]) != NULL || SCIPvarGetData(relevantvar) != NULL);
359  }
360  }
361  SCIPdebugMessage("\tProcessing linking variables.\n");
362  for( i = 0; i < nlinkingvars; ++i )
363  {
364  int nfound = 0;
365 
366  if( GCGoriginalVarIsLinking(linkingvars[i]) )
367  continue;
368 
369  SCIPdebugMessage("\tDetecting constraint blocks of linking var %s\n", SCIPvarGetName(linkingvars[i]));
370  /* HACK; @todo find out constraint blocks more intelligently */
371  for( j = 0; j < nblocks; ++j )
372  {
373  int found = FALSE;
374  for( k = 0; k < nsubscipconss[j]; ++k )
375  {
376  SCIP_VAR** curvars;
377  int ncurvars;
378  if( SCIPconsIsDeleted(subscipconss[j][k]) )
379  continue;
380  ncurvars = GCGconsGetNVars(scip, subscipconss[j][k]);
381  curvars = NULL;
382  if( ncurvars > 0 )
383  {
384  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
385  SCIP_CALL( GCGconsGetVars(scip, subscipconss[j][k], curvars, ncurvars) );
386 
387  for( v = 0; v < ncurvars; ++v )
388  {
389  if( SCIPvarGetProbvar(curvars[v]) == linkingvars[i] || curvars[v] == linkingvars[i] )
390  {
391  SCIPdebugMessage("\t\t%s is in %d\n", SCIPvarGetName(SCIPvarGetProbvar(curvars[v])), j);
392  assert(SCIPvarGetData(linkingvars[i]) != NULL);
393  SCIP_CALL( setOriginalVarBlockNr(scip, relaxdata, SCIPvarGetProbvar(linkingvars[i]), j) );
394  found = TRUE;
395  break;
396  }
397  }
398 
399  SCIPfreeBufferArray(scip, &curvars);
400  }
401 
402  if( found )
403  {
404  nfound++;
405  break;
406  }
407 
408  }
409  }
410 
411  /* if the linking variable is only in one block, then it would not have been flagged as a linking variable. In
412  * the Benders' decomposition case, then linking variable needs to be flagged as linking so that it is added to
413  * the master problem.
414  */
415  if( nfound == 1 && GCGgetDecompositionMode(scip) == DEC_DECMODE_BENDERS )
416  {
417  SCIP_CALL( setOriginalVarBlockNr(scip, relaxdata, SCIPvarGetProbvar(linkingvars[i]), -2) );
418  }
419  }
420 
421  SCIPhashmapFree(&transvar2origvar);
422  return SCIP_OKAY;
423 }
424 
426 static
427 SCIP_RETCODE ensureSizeMasterConss(
428  SCIP* scip,
429  SCIP_RELAXDATA* relaxdata,
430  int size
431  )
432 {
433  assert(scip != NULL);
434  assert(relaxdata != NULL);
435  assert(relaxdata->masterconss != NULL);
436 
437  if( relaxdata->maxmasterconss < size )
438  {
439  int newsize = SCIPcalcMemGrowSize(scip, size);
440  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(relaxdata->masterconss), relaxdata->maxmasterconss, newsize) );
441  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(relaxdata->origmasterconss), relaxdata->maxmasterconss, newsize) );
442  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(relaxdata->linearmasterconss), relaxdata->maxmasterconss, newsize) );
443  relaxdata->maxmasterconss = newsize;
444 
445  }
446  assert(relaxdata->maxmasterconss >= size);
447 
448  return SCIP_OKAY;
449 }
450 
452 static
453 SCIP_RETCODE ensureSizeBranchrules(
454  SCIP* scip,
455  SCIP_RELAXDATA* relaxdata
456  )
457 {
458  assert(scip != NULL);
459  assert(relaxdata != NULL);
460  assert((relaxdata->branchrules == NULL) == (relaxdata->nbranchrules == 0));
461 
462  if( relaxdata->nbranchrules == 0 )
463  {
464  SCIP_CALL( SCIPallocMemoryArray(scip, &(relaxdata->branchrules), 1) ); /*lint !e506*/
465  }
466  else
467  {
468  SCIP_CALL( SCIPreallocMemoryArray(scip, &(relaxdata->branchrules), (size_t)relaxdata->nbranchrules+1) );
469  }
470 
471  return SCIP_OKAY;
472 }
473 
474 
476 static
477 SCIP_RETCODE checkSetppcStructure(
478  SCIP* scip,
479  SCIP_RELAXDATA* relaxdata
480  )
481 {
482  SCIP_CONS** masterconss;
483  int nmasterconss;
484 
485  int i;
486 
487  assert(relaxdata->decdecomp != NULL);
488 
489  masterconss = DECdecompGetLinkingconss(relaxdata->decdecomp);
490  nmasterconss = DECdecompGetNLinkingconss(relaxdata->decdecomp);
491  assert(nmasterconss >= 0);
492  assert(masterconss != NULL || nmasterconss == 0);
493 
494  if( nmasterconss == 0 || relaxdata->nvarlinkconss > 0 )
495  {
496  relaxdata->masterissetcover = FALSE;
497  relaxdata->masterissetpart = FALSE;
498  return SCIP_OKAY;
499  }
500 
501  relaxdata->masterissetcover = TRUE;
502  relaxdata->masterissetpart = TRUE;
503 
504  for( i = 0; i < nmasterconss; ++i )
505  {
506  assert(masterconss != NULL);
507 
508  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(masterconss[i])), "setppc") == 0 )
509  {
510  switch( SCIPgetTypeSetppc(scip, masterconss[i]) )
511  {
512  case SCIP_SETPPCTYPE_COVERING:
513  relaxdata->masterissetpart = FALSE;
514  break;
515  case SCIP_SETPPCTYPE_PARTITIONING:
516  relaxdata->masterissetcover = FALSE;
517  break;
518  case SCIP_SETPPCTYPE_PACKING:
519  relaxdata->masterissetcover = FALSE;
520  relaxdata->masterissetpart = FALSE;
521  break;
522  }
523  }
524  else if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(masterconss[i])), "logicor") == 0 )
525  {
526  relaxdata->masterissetpart = FALSE;
527  break;
528  }
529  else if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(masterconss[i])), "linear") == 0 )
530  {
531  SCIP_SETPPCTYPE type;
532 
533  if( GCGgetConsIsSetppc(scip, masterconss[i], &type) )
534  {
535  switch( type )
536  {
537  case SCIP_SETPPCTYPE_COVERING:
538  relaxdata->masterissetpart = FALSE;
539  break;
540  case SCIP_SETPPCTYPE_PARTITIONING:
541  relaxdata->masterissetcover = FALSE;
542  break;
543  case SCIP_SETPPCTYPE_PACKING:
544  relaxdata->masterissetcover = FALSE;
545  relaxdata->masterissetpart = FALSE;
546  break;
547  }
548  }
549  else
550  {
551  relaxdata->masterissetcover = FALSE;
552  relaxdata->masterissetpart = FALSE;
553  break;
554  }
555  }
556  else
557  {
558  relaxdata->masterissetcover = FALSE;
559  relaxdata->masterissetpart = FALSE;
560  break;
561  }
562  }
563 
564  if( relaxdata->masterissetcover )
565  {
566  assert(!relaxdata->masterissetpart);
567  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Master problem is a set covering problem.\n");
568  }
569  if( relaxdata->masterissetpart )
570  {
571  assert(!relaxdata->masterissetcover);
572  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Master problem is a set partitioning problem.\n");
573  }
574 
575  return SCIP_OKAY;
576 }
577 
578 #ifndef WITH_BLISS
579 
580 static
581 SCIP_Bool realArraysAreEqual(
582  SCIP* scip,
583  SCIP_Real* array1,
584  int array1length,
585  SCIP_Real* array2,
586  int array2length
587  )
588 {
589  int i;
590 
591  if( array1length != array2length )
592  return FALSE;
593 
594  if( array1length == 0 )
595  return TRUE;
596 
597  assert(array1 != NULL);
598  assert(array2 != NULL);
599 
600  for( i = 0; i < array1length; i++ )
601  {
602  if( !SCIPisEQ(scip, array1[i], array2[i]) )
603  return FALSE;
604  }
605 
606  return TRUE;
607 }
608 
609 
611 static
612 SCIP_RETCODE checkIdentical(
613  SCIP* scip,
614  SCIP_RELAXDATA* relaxdata,
615  int probnr1,
616  int probnr2,
617  SCIP_HASHMAP* varmap,
619  SCIP_Bool* identical,
620  SCIP* scip1,
621  SCIP* scip2
622  )
623 {
624  SCIP_VAR** vars1;
625  SCIP_VAR** vars2;
626  int nvars1;
627  int nvars2;
628 
629  SCIP_CONS** conss1;
630  SCIP_CONS** conss2;
631  int nconss;
632 
633  int i;
634  int j;
635 
636  SCIPdebugMessage("check block %d and block %d for identity...\n", probnr1, probnr2);
637 
638  if( SCIPgetNVars(scip1) != SCIPgetNVars(scip2) )
639  {
640  SCIPdebugMessage("--> number of variables differs!\n");
641  return SCIP_OKAY;
642  }
643  if( SCIPgetNConss(scip1) != SCIPgetNConss(scip2) )
644  {
645  SCIPdebugMessage("--> number of constraints differs!\n");
646  return SCIP_OKAY;
647  }
648  /* get variables */
649  SCIP_CALL( SCIPgetVarsData(scip1, &vars1, &nvars1, NULL, NULL, NULL, NULL) );
650  SCIP_CALL( SCIPgetVarsData(scip2, &vars2, &nvars2, NULL, NULL, NULL, NULL) );
651 
652  for( i = 0; i < nvars1; i++ )
653  {
654  SCIP_Real* coefs1;
655  int ncoefs1;
656  SCIP_Real* coefs2;
657  int ncoefs2;
658  SCIP_VAR** origvars1;
659  SCIP_VAR** origvars2;
660 
661  if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetObj(vars1[i]), SCIPvarGetObj(vars2[i])) )
662  {
663  SCIPdebugMessage("--> obj differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
664  return SCIP_OKAY;
665  }
666  if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetLbOriginal(vars1[i]), SCIPvarGetLbOriginal(vars2[i])) )
667  {
668  SCIPdebugMessage("--> lb differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
669  return SCIP_OKAY;
670  }
671  if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetUbOriginal(vars1[i]), SCIPvarGetUbOriginal(vars2[i])) )
672  {
673  SCIPdebugMessage("--> ub differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
674  return SCIP_OKAY;
675  }
676  if( SCIPvarGetType(vars1[i]) != SCIPvarGetType(vars2[i]) )
677  {
678  SCIPdebugMessage("--> type differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
679  return SCIP_OKAY;
680  }
681 
682  assert(GCGvarIsPricing(vars1[i]));
683  assert(GCGvarIsPricing(vars2[i]));
684 
685  origvars1 = GCGpricingVarGetOrigvars(vars1[i]);
686  origvars2 = GCGpricingVarGetOrigvars(vars2[i]);
687 
688  if( !SCIPisEQ(relaxdata->masterprob, SCIPvarGetObj(origvars1[0]),SCIPvarGetObj(origvars2[0])) )
689  {
690  SCIPdebugMessage("--> orig obj differs for var %s and var %s!\n", SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
691  return SCIP_OKAY;
692  }
693 
694  assert(GCGvarIsOriginal(origvars1[0]));
695  assert(GCGvarIsOriginal(origvars2[0]));
696 
697  ncoefs1 = GCGoriginalVarGetNCoefs(origvars1[0]);
698  ncoefs2 = GCGoriginalVarGetNCoefs(origvars2[0]);
699 
700  /* nunber of coefficients differs */
701  if( ncoefs1 != ncoefs2 )
702  {
703  SCIPdebugMessage("--> number of coefficients differs for var %s and var %s!\n",
704  SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
705  return SCIP_OKAY;
706  }
707 
708  /* get master constraints and corresponding coefficients of both variables */
709  conss1 = GCGoriginalVarGetMasterconss(origvars1[0]);
710  conss2 = GCGoriginalVarGetMasterconss(origvars2[0]);
711  coefs1 = GCGoriginalVarGetCoefs(origvars1[0]);
712  coefs2 = GCGoriginalVarGetCoefs(origvars2[0]);
713 
714  /* check that the master constraints and the coefficients are the same */
715  for( j = 0; j < ncoefs1; ++j )
716  {
717  if( conss1[j] != conss2[j] )
718  {
719  SCIPdebugMessage("--> constraints differ for var %s and var %s!\n",
720  SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
721  return SCIP_OKAY;
722  }
723 
724  if( !SCIPisEQ(scip, coefs1[j], coefs2[j]) )
725  {
726  SCIPdebugMessage("--> coefficients differ for var %s and var %s!\n",
727  SCIPvarGetName(vars1[i]), SCIPvarGetName(vars2[i]));
728  return SCIP_OKAY;
729  }
730  }
731 
732  SCIP_CALL( SCIPhashmapInsert(varmap, (void*) vars1[i], (void*) vars2[i]) );
733  }
734 
735  /* check whether the conss are the same */
736  conss1 = SCIPgetConss(scip1);
737  conss2 = SCIPgetConss(scip2);
738  nconss = SCIPgetNConss(scip1);
739  assert(nconss == SCIPgetNConss(scip2));
740  for( i = 0; i < nconss; i++ )
741  {
742  if( SCIPgetNVarsLinear(scip1, conss1[i]) != SCIPgetNVarsLinear(scip2, conss2[i]) )
743  {
744  SCIPdebugMessage("--> nvars differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
745  return SCIP_OKAY;
746  }
747  if( !SCIPisEQ(relaxdata->masterprob, SCIPgetLhsLinear(scip1, conss1[i]), SCIPgetLhsLinear(scip2, conss2[i])) )
748  {
749  SCIPdebugMessage("--> lhs differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
750  return SCIP_OKAY;
751  }
752  if( !SCIPisEQ(relaxdata->masterprob, SCIPgetRhsLinear(scip1, conss1[i]), SCIPgetRhsLinear(scip2, conss2[i])) )
753  {
754  SCIPdebugMessage("--> rhs differs for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
755  return SCIP_OKAY;
756  }
757  if( !realArraysAreEqual(scip, SCIPgetValsLinear(scip1, conss1[i]), SCIPgetNVarsLinear(scip1, conss1[i]),
758  SCIPgetValsLinear(scip2, conss2[i]), SCIPgetNVarsLinear(scip2, conss2[i])) )
759  {
760  SCIPdebugMessage("--> coefs differ for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
761  return SCIP_OKAY;
762  }
763  vars1 = SCIPgetVarsLinear(scip1, conss1[i]);
764  vars2 = SCIPgetVarsLinear(scip2, conss2[i]);
765  for( j = 0; j < SCIPgetNVarsLinear(scip1, conss1[i]); j++ )
766  {
767  if( (SCIP_VAR*) SCIPhashmapGetImage(varmap, (void*) vars1[j]) != vars2[j] )
768  {
769  SCIPdebugMessage("--> vars differ for cons %s and cons %s!\n", SCIPconsGetName(conss1[i]), SCIPconsGetName(conss2[i]));
770  return SCIP_OKAY;
771  }
772  }
773 
774  }
775 
776  SCIPdebugMessage("--> blocks are identical!\n");
777 
778  *identical = TRUE;
779  return SCIP_OKAY;
780 }
781 #endif
782 
783 /* checks whether two pricingproblems represent identical blocks */
784 static
786  SCIP* scip,
787  SCIP_RELAXDATA* relaxdata,
788  SCIP_HASHMAP** hashorig2pricingvar,
789  int probnr1,
790  int probnr2,
791  SCIP_HASHMAP* varmap,
793  SCIP_Bool* identical
794  )
795 {
796  SCIP* scip1;
797  SCIP* scip2;
798  int seeedid;
799 
800 
801  assert(relaxdata != NULL);
802  assert(0 <= probnr1 && probnr1 < relaxdata->npricingprobs);
803  assert(0 <= probnr2 && probnr2 < relaxdata->npricingprobs);
804  assert(varmap != NULL);
805  assert(identical != NULL);
806 
807  scip1 = relaxdata->pricingprobs[probnr1];
808  scip2 = relaxdata->pricingprobs[probnr2];
809  assert(scip1 != NULL);
810  assert(scip2 != NULL);
811 
812  *identical = FALSE;
813 
814  /* 1) find seeed number */
815 
816  seeedid = DECdecompGetSeeedID(relaxdata->decdecomp);
817 
818  /* 2) are pricingproblems identical for this seeed? */
819  SCIP_CALL(SCIPconshdlrDecompArePricingprobsIdenticalForSeeedid(scip, seeedid, probnr2, probnr1, identical) );
820 
821  /* 3) create varmap if pricing probs are identical */
822  if( *identical )
823  {
824  SCIP_CALL(SCIPconshdlrDecompCreateVarmapForSeeedId(scip, hashorig2pricingvar, seeedid, probnr2, probnr1, scip2, scip1, varmap) );
825  }
826 
827  return SCIP_OKAY;
828 }
829 
830 
831 
832 
833 
834 static
835 SCIP_RETCODE pricingprobsAreIdentical(
836  SCIP* scip,
837  SCIP_RELAXDATA* relaxdata,
838  int probnr1,
839  int probnr2,
840  SCIP_HASHMAP* varmap,
842  SCIP_Bool* identical
843  )
844 {
845  SCIP* scip1;
846  SCIP* scip2;
847 
848 #ifdef WITH_BLISS
849  SCIP_RESULT result;
850  SCIP_HASHMAP* consmap;
851 #endif
852 
853  assert(relaxdata != NULL);
854  assert(0 <= probnr1 && probnr1 < relaxdata->npricingprobs);
855  assert(0 <= probnr2 && probnr2 < relaxdata->npricingprobs);
856  assert(varmap != NULL);
857  assert(identical != NULL);
858 
859  scip1 = relaxdata->pricingprobs[probnr1];
860  scip2 = relaxdata->pricingprobs[probnr2];
861  assert(scip1 != NULL);
862  assert(scip2 != NULL);
863 
864  *identical = FALSE;
865 
866 #ifndef WITH_BLISS
867  checkIdentical(scip, relaxdata, probnr1, probnr2, varmap, identical, scip1, scip2);
868 #else
869  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), SCIPgetNConss(scip1)+1) );
870  SCIP_CALL( cmpGraphPair(scip, scip2, scip1, probnr2, probnr1, &result, varmap, consmap) );
871 
872  *identical = (result == SCIP_SUCCESS);
873 
874  SCIPhashmapFree(&consmap);
875 #endif
876 
877  return SCIP_OKAY;
878 }
879 
881 static
882 SCIP_RETCODE checkIdenticalBlocks(
883  SCIP* scip,
884  SCIP_RELAXDATA* relaxdata,
885  SCIP_HASHMAP** hashorig2pricingvar
886  )
887 {
888  SCIP_HASHMAP* varmap;
889  SCIP_VAR** vars;
890  SCIP_VAR* origvar;
891  SCIP_VAR* pricingvar;
892  int nvars;
893  SCIP_Bool identical;
894 
895  int i;
896  int j;
897  int k;
898 
899  int nrelevant;
900 
901  SCIPdebugMessage("checking identical blocks \n");
902  assert(scip != NULL);
903  assert(relaxdata != NULL);
904 
905  for( i = 0; i < relaxdata->npricingprobs; i++ )
906  {
907  relaxdata->blockrepresentative[i] = i;
908  relaxdata->nblocksidentical[i] = 1;
909  }
910 
911  relaxdata->nrelpricingprobs = relaxdata->npricingprobs;
912  nrelevant = 0;
913 
914  if( ( !relaxdata->discretization || !relaxdata->aggregation ) )
915  {
916  SCIPdebugMessage("discretization is off, aggregation is off\n");
917  return SCIP_OKAY;
918  }
919 
920 
921  if( relaxdata->nlinkingvars != 0 )
922  {
923  SCIPdebugMessage("aggregation is off in presence of linking vars\n");
924  return SCIP_OKAY;
925  }
926 
927 
928 
929  for( i = 0; i < relaxdata->npricingprobs; i++ )
930  {
931  for( j = 0; j < i && relaxdata->blockrepresentative[i] == i; j++ )
932  {
933  if( relaxdata->blockrepresentative[j] != j )
934  continue;
935 
936  SCIP_CALL( SCIPhashmapCreate(&varmap,
937  SCIPblkmem(scip),
938  5 * SCIPgetNVars(relaxdata->pricingprobs[i])+1) ); /* +1 to deal with empty subproblems */
939 
941  if( SCIPgetNConss(scip) != SCIPconshdlrDecompGetNFormerDetectionConssForID(scip, DECdecompGetSeeedID(relaxdata->decdecomp) ) )
942  {
943  SCIPdebugMessage("nconss: %d; ndetectionconss: %d -> using classical identity test \n", SCIPgetNConss(scip), SCIPconshdlrDecompGetNFormerDetectionConssForID(scip, DECdecompGetSeeedID(relaxdata->decdecomp) ));
944  SCIP_CALL( pricingprobsAreIdentical(scip, relaxdata, i, j, varmap, &identical) );
945  }
946  else
947  {
948  SCIPdebugMessage( "nconss: %d; ndetectionconss: %d -> using seeed information for identity test \n", SCIPgetNConss(scip), SCIPconshdlrDecompGetNFormerDetectionConssForID(scip, DECdecompGetSeeedID(relaxdata->decdecomp) ) );
949  SCIP_CALL( pricingprobsAreIdenticalFromDetectionInfo( scip, relaxdata, hashorig2pricingvar, i, j, varmap, &identical ) );
950  }
951 
952 
961  if( identical )
962  {
963  SCIPdebugMessage("Block %d is identical to block %d!\n", i, j);
964 
965  /* save variables in pricing problem variable */
966  vars = SCIPgetVars(relaxdata->pricingprobs[i]);
967  nvars = SCIPgetNVars(relaxdata->pricingprobs[i]);
968 
969  /*
970  * quick check whether some of the variables are linking in which case we cannot aggregate
971  * this is suboptimal but we use bliss anyway
972  */
973 
974  for( k = 0; k < nvars; k++ )
975  {
976  assert(GCGvarIsPricing(vars[k]));
977  origvar = GCGpricingVarGetOrigvars(vars[k])[0];
978  if( GCGoriginalVarIsLinking(origvar) )
979  {
980  SCIPdebugMessage("Var <%s> is linking and can not be aggregated.\n", SCIPvarGetName(origvar));
981  identical = FALSE;
982  break;
983  }
984  }
985 
986  if( !identical )
987  {
988  break;
989  }
990 
991 
992  /* block i will be represented by block j */
993  relaxdata->blockrepresentative[i] = j;
994  relaxdata->nblocksidentical[i] = 0;
995  relaxdata->nblocksidentical[j]++;
996 
997  for( k = 0; k < nvars; k++ )
998  {
999  int blocknr;
1000  assert(GCGvarIsPricing(vars[k]));
1001  origvar = GCGpricingVarGetOrigvars(vars[k])[0];
1002 
1003  pricingvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (void*) vars[k]);
1004  assert(pricingvar != NULL);
1005  blocknr = GCGvarGetBlock(pricingvar);
1006 
1007  assert(GCGvarIsPricing(pricingvar));
1008  assert(GCGvarIsOriginal(origvar));
1009  assert(GCGoriginalVarGetPricingVar(origvar) != NULL);
1010  GCGoriginalVarSetPricingVar(origvar, pricingvar);
1011  SCIP_CALL( GCGpricingVarAddOrigVar(relaxdata->pricingprobs[blocknr], pricingvar, origvar) );
1012  }
1013 
1014  }
1015  SCIPhashmapFree(&varmap);
1016 
1017  }
1018  if( relaxdata->blockrepresentative[i] == i )
1019  {
1020  SCIPdebugMessage("Block %d is relevant!\n", i);
1021  nrelevant++;
1022  }
1023  }
1024 
1025  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Matrix has %d blocks, using %d%s pricing problem%s.\n",
1026  relaxdata->npricingprobs, nrelevant, (relaxdata->npricingprobs == nrelevant ? "" : " aggregated"), (nrelevant == 1 ? "" : "s"));
1027 
1028  relaxdata->nrelpricingprobs = nrelevant;
1029 
1030  return SCIP_OKAY;
1031 }
1032 
1034 static
1035 SCIP_RETCODE setPricingProblemParameters(
1036  SCIP* scip,
1037  int clocktype,
1038  SCIP_Real infinity,
1039  SCIP_Real epsilon,
1040  SCIP_Real sumepsilon,
1041  SCIP_Real feastol,
1042  SCIP_Real lpfeastol,
1043  SCIP_Real dualfeastol,
1044  SCIP_Bool enableppcuts
1045  )
1046 {
1047  assert(scip != NULL);
1048 
1049  /* disable conflict analysis */
1050  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/useprop", FALSE) );
1051  SCIP_CALL( SCIPsetCharParam(scip, "conflict/useinflp", 'o') );
1052  SCIP_CALL( SCIPsetCharParam(scip, "conflict/useboundlp", 'o') );
1053  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/usesb", FALSE) );
1054  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/usepseudo", FALSE) );
1055 
1056  /* reduce the effort spent for hash tables */
1057  SCIP_CALL( SCIPsetBoolParam(scip, "misc/usevartable", FALSE) );
1058  SCIP_CALL( SCIPsetBoolParam(scip, "misc/useconstable", FALSE) );
1059  SCIP_CALL( SCIPsetBoolParam(scip, "misc/usesmalltables", TRUE) );
1060 
1061  /* disable expensive presolving */
1062  /* @todo test whether this really helps, perhaps set presolving emphasis to fast? */
1063  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/linear/presolpairwise", FALSE) );
1064  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/setppc/presolpairwise", FALSE) );
1065  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/logicor/presolpairwise", FALSE) );
1066  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/linear/presolusehashing", FALSE) );
1067  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/setppc/presolusehashing", FALSE) );
1068  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/logicor/presolusehashing", FALSE) );
1069 
1070  /* disable dual fixing presolver for the moment, because we want to avoid variables fixed to infinity */
1071  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/freq", -1) );
1072  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", 0) );
1073  SCIP_CALL( SCIPfixParam(scip, "propagating/dualfix/freq") );
1074  SCIP_CALL( SCIPfixParam(scip, "propagating/dualfix/maxprerounds") );
1075 
1076 
1077  /* disable solution storage ! */
1078  SCIP_CALL( SCIPsetIntParam(scip, "limits/maxorigsol", 0) );
1079 
1080  /* disable multiaggregation because of infinite values */
1081  SCIP_CALL( SCIPsetBoolParam(scip, "presolving/donotmultaggr", TRUE) );
1082 
1083  /* @todo enable presolving and propagation of xor constraints if bug is fixed */
1084 
1085  /* disable presolving and propagation of xor constraints as work-around for a SCIP bug */
1086  SCIP_CALL( SCIPsetIntParam(scip, "constraints/xor/maxprerounds", 0) );
1087  SCIP_CALL( SCIPsetIntParam(scip, "constraints/xor/propfreq", -1) );
1088 
1089  /* disable output to console */
1090  SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
1091 #if SCIP_VERSION > 210
1092  SCIP_CALL( SCIPsetBoolParam(scip, "misc/printreason", FALSE) );
1093 #endif
1094  SCIP_CALL( SCIPsetIntParam(scip, "limits/maxorigsol", 0) );
1095  SCIP_CALL( SCIPfixParam(scip, "limits/maxorigsol") );
1096 
1097  /* do not abort subproblem on CTRL-C */
1098  SCIP_CALL( SCIPsetBoolParam(scip, "misc/catchctrlc", FALSE) );
1099 
1100  /* set clock type */
1101  SCIP_CALL( SCIPsetIntParam(scip, "timing/clocktype", clocktype) );
1102 
1103  SCIP_CALL( SCIPsetBoolParam(scip, "misc/calcintegral", FALSE) );
1104  SCIP_CALL( SCIPsetBoolParam(scip, "misc/finitesolutionstore", TRUE) );
1105 
1106  SCIP_CALL( SCIPsetRealParam(scip, "numerics/infinity", infinity) );
1107  SCIP_CALL( SCIPsetRealParam(scip, "numerics/epsilon", epsilon) );
1108  SCIP_CALL( SCIPsetRealParam(scip, "numerics/sumepsilon", sumepsilon) );
1109  SCIP_CALL( SCIPsetRealParam(scip, "numerics/feastol", feastol) );
1110  SCIP_CALL( SCIPsetRealParam(scip, "numerics/lpfeastol", lpfeastol) );
1111  SCIP_CALL( SCIPsetRealParam(scip, "numerics/dualfeastol", dualfeastol) );
1112 
1113  /* jonas' stuff */
1114  if( enableppcuts )
1115  {
1116  int pscost;
1117  int prop;
1118 
1119  SCIP_CALL( SCIPgetIntParam(scip, "branching/pscost/priority", &pscost) );
1120  SCIP_CALL( SCIPgetIntParam(scip, "propagating/maxroundsroot", &prop) );
1121  SCIP_CALL( SCIPsetIntParam(scip, "branching/pscost/priority", 11000) );
1122  SCIP_CALL( SCIPsetIntParam(scip, "propagating/maxroundsroot", 0) );
1123  SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) );
1124  }
1125  return SCIP_OKAY;
1126 }
1127 
1128 
1130 static
1131 SCIP_RETCODE createPricingVar(
1132  SCIP_RELAXDATA* relaxdata,
1133  SCIP_VAR* origvar
1134  )
1135 {
1136  SCIP_VAR* var;
1137  int pricingprobnr;
1138 
1139  assert(relaxdata != NULL);
1140  assert(origvar != NULL);
1141 
1142  pricingprobnr = GCGvarGetBlock(origvar);
1143  assert(pricingprobnr >= 0);
1144 
1145  SCIP_CALL( GCGoriginalVarCreatePricingVar(relaxdata->pricingprobs[pricingprobnr], origvar, &var) );
1146  assert(var != NULL);
1147 
1148  GCGoriginalVarSetPricingVar(origvar, var);
1149  SCIP_CALL( SCIPaddVar(relaxdata->pricingprobs[pricingprobnr], var) );
1150  assert(GCGvarIsPricing(var));
1151  /* because the variable was added to the problem,
1152  * it is captured by SCIP and we can safely release it right now
1153  */
1154  SCIP_CALL( SCIPreleaseVar(relaxdata->pricingprobs[pricingprobnr], &var) );
1155 
1156  return SCIP_OKAY;
1157 }
1158 
1160 static
1161 SCIP_RETCODE createLinkingPricingVars(
1162  SCIP* scip,
1163  SCIP_RELAXDATA* relaxdata,
1164  SCIP_VAR* origvar
1165  )
1166 {
1167  SCIP_VAR* var;
1168  SCIP_CONS* linkcons;
1169 #ifndef NDEBUG
1170  SCIP_CONS** linkconss;
1171  int nblocks;
1172 #endif
1173  SCIP_VAR** pricingvars;
1174  int i;
1175 
1176  assert(origvar != NULL);
1177  assert(relaxdata != NULL);
1178 
1179  /* get variable data of the original variable */
1180  assert(GCGvarIsOriginal(origvar));
1181  assert(GCGoriginalVarIsLinking(origvar));
1182  pricingvars = GCGlinkingVarGetPricingVars(origvar);
1183 
1184 #ifndef NDEBUG
1185  nblocks = GCGlinkingVarGetNBlocks(origvar);
1186  /* checks that GCGrelaxSetOriginalVarBlockNr() worked correctly */
1187  {
1188  int count;
1189 
1190  linkconss = GCGlinkingVarGetLinkingConss(origvar);
1191  /* the linking constraints could be NULL if the Benders' decomposition is used. */
1192  if( linkconss != NULL )
1193  {
1194  count = 0;
1195  for( i = 0; i < relaxdata->npricingprobs; i++ )
1196  {
1197  assert(linkconss[i] == NULL);
1198 
1199  if( pricingvars[i] != NULL )
1200  count++;
1201  }
1202  assert(nblocks == count);
1203  }
1204  }
1205 #endif
1206 
1207  for( i = 0; i < relaxdata->npricingprobs; ++i )
1208  {
1209  if( pricingvars[i] == NULL )
1210  continue;
1211 
1212  SCIP_CALL( GCGlinkingVarCreatePricingVar(relaxdata->pricingprobs[i], i, origvar, &var) );
1213 
1214  GCGlinkingVarSetPricingVar(origvar, i, var);
1215 
1216  assert(GCGvarIsPricing(var));
1217  SCIP_CALL( SCIPaddVar(relaxdata->pricingprobs[i], var) );
1218 
1219 
1220  if( relaxdata->mode != DEC_DECMODE_BENDERS )
1221  {
1222  SCIP_CALL( GCGlinkingVarCreateMasterCons(relaxdata->masterprob, i, origvar, &linkcons) );
1223  GCGlinkingVarSetLinkingCons(origvar, linkcons, i);
1224  SCIP_CALL( SCIPaddCons(relaxdata->masterprob, linkcons) );
1225 
1226  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &relaxdata->varlinkconss, relaxdata->nvarlinkconss, (size_t)relaxdata->nvarlinkconss+1) );
1227  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &relaxdata->varlinkconsblock, relaxdata->nvarlinkconss, (size_t)relaxdata->nvarlinkconss+1) );
1228 
1229  relaxdata->varlinkconss[relaxdata->nvarlinkconss] = linkcons;
1230  relaxdata->varlinkconsblock[relaxdata->nvarlinkconss] = i;
1231  relaxdata->nvarlinkconss++;
1232  }
1233 
1234  /* because the variable was added to the problem,
1235  * it is captured by SCIP and we can safely release it right now
1236  */
1237  SCIP_CALL( SCIPreleaseVar(relaxdata->pricingprobs[i], &var) );
1238  }
1239 
1240 #ifndef NDEBUG
1241  /* checks that createLinkingPricingVars() worked correctly */
1242  {
1243  int count;
1244 
1245  linkconss = GCGlinkingVarGetLinkingConss(origvar);
1246  /* the linking constraints could be NULL if the Benders' decomposition is used. */
1247  if( linkconss != NULL )
1248  {
1249  count = 0;
1250  for( i = 0; i < relaxdata->npricingprobs; i++ )
1251  {
1252  if( pricingvars[i] != NULL )
1253  {
1254  count++;
1255  assert(GCGvarIsPricing(pricingvars[i]));
1256  assert(relaxdata->mode == DEC_DECMODE_BENDERS || linkconss[i] != NULL);
1257  }
1258  else
1259  assert(linkconss[i] == NULL);
1260  }
1261  assert(nblocks == count);
1262  }
1263  }
1264 #endif
1265 
1266 
1267  return SCIP_OKAY;
1268 }
1269 
1271 static
1272 SCIP_RETCODE createPricingVariables(
1273  SCIP* scip,
1274  SCIP_RELAXDATA* relaxdata,
1275  SCIP_HASHMAP** hashorig2pricingvar
1276  )
1277 {
1278  SCIP_VAR** vars;
1279  int nvars;
1280  int v;
1281  int i;
1282  int npricingprobs;
1283 
1284  assert(scip != NULL);
1285  assert(relaxdata != NULL);
1286 
1287  /* create pricing variables and map them to the original variables */
1288  vars = SCIPgetVars(scip);
1289  nvars = SCIPgetNVars(scip);
1290  npricingprobs = relaxdata->npricingprobs;
1291 
1292  for( v = 0; v < nvars; v++ )
1293  {
1294  int blocknr;
1295  SCIP_VAR* probvar;
1296 
1297  assert(SCIPvarIsTransformed(vars[v]));
1298 
1299  probvar = SCIPvarGetProbvar(vars[v]);
1300  assert(SCIPvarIsTransformed(probvar));
1301  blocknr = GCGvarGetBlock(probvar);
1302  if( blocknr == -1 )
1303  {
1304  int tempblock;
1305  tempblock = (int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(relaxdata->decdecomp), probvar)-1; /*lint !e507*/
1306  if( tempblock >= DECdecompGetNBlocks(relaxdata->decdecomp) )
1307  {
1308  blocknr = -1;
1309  }
1310  else
1311  {
1312  SCIPinfoMessage(scip, NULL, " changed block number to %d \n", tempblock );
1313  blocknr = tempblock; /*lint !e806*/
1314  }
1315  }
1316 
1317  SCIPdebugMessage("Creating map for (%p, %p) var %s:", (void*)(vars[v]), (void*)(probvar), SCIPvarGetName(probvar));
1318  assert( !SCIPhashmapExists(relaxdata->hashorig2origvar, probvar) );
1319  SCIP_CALL( SCIPhashmapInsert(relaxdata->hashorig2origvar, (void*)(probvar), (void*)(probvar)) );
1320 
1321  /* variable belongs to exactly one block --> create corresponding pricing variable*/
1322  if( blocknr >= 0 )
1323  {
1324  SCIPdebugPrintf("block %d", blocknr);
1325 
1326  assert(GCGoriginalVarGetPricingVar(probvar) == NULL);
1327  SCIP_CALL( createPricingVar(relaxdata, probvar) );
1328  assert(GCGoriginalVarGetPricingVar(probvar) != NULL);
1329  assert(hashorig2pricingvar != NULL);
1330  assert(hashorig2pricingvar[blocknr] != NULL);
1331 
1332  SCIPdebugPrintf("-> %p\n", (void*) GCGoriginalVarGetPricingVar(probvar));
1333 
1334  assert(!SCIPhashmapExists(hashorig2pricingvar[blocknr], probvar));
1335  SCIP_CALL( SCIPhashmapInsert(hashorig2pricingvar[blocknr], (void*)(probvar),
1336  (void*)(GCGoriginalVarGetPricingVar(probvar)) ));
1337 
1338  assert(GCGvarIsPricing((SCIP_VAR*) SCIPhashmapGetImage(hashorig2pricingvar[blocknr], probvar)));
1339  }
1340  /* variable is a linking variable --> create corresponding pricing variable in all linked blocks
1341  * and create corresponding linking constraints */
1342  else if( GCGoriginalVarIsLinking(probvar) )
1343  {
1344  SCIP_VAR** pricingvars;
1345  SCIPdebugPrintf("linking.\n");
1346  relaxdata->nlinkingvars++;
1347  SCIP_CALL( createLinkingPricingVars(scip, relaxdata, probvar) );
1348  assert(GCGlinkingVarGetPricingVars(probvar) != NULL);
1349 
1350 
1351  pricingvars = GCGlinkingVarGetPricingVars(probvar);
1352 
1353  for( i = 0; i < npricingprobs; i++ )
1354  {
1355  if( pricingvars[i] != NULL )
1356  {
1357  assert(GCGvarIsPricing(pricingvars[i]));
1358  assert(hashorig2pricingvar != NULL);
1359  assert(hashorig2pricingvar[i] != NULL);
1360  assert(!SCIPhashmapExists(hashorig2pricingvar[i], probvar));
1361  SCIP_CALL( SCIPhashmapInsert(hashorig2pricingvar[i], (void*)(probvar),
1362  (void*)(pricingvars[i])) );
1363  assert(GCGvarIsPricing((SCIP_VAR*) SCIPhashmapGetImage(hashorig2pricingvar[i], probvar)));
1364  }
1365  }
1366  }
1367  else
1368  {
1369  assert(GCGvarGetBlock(probvar) == -1);
1370  assert(GCGoriginalVarGetPricingVar(probvar) == NULL);
1371  SCIPdebugPrintf("master!\n");
1372  relaxdata->ntransvars++;
1373  }
1374  assert(SCIPhashmapExists(relaxdata->hashorig2origvar, probvar));
1375  }
1376 
1377  return SCIP_OKAY;
1378 }
1379 
1380 
1382 static
1383 SCIP_RETCODE displayPricingStatistics(
1384  SCIP* scip,
1385  SCIP** pricingprobs,
1386  int npricingprobs,
1387  int* blockrepresentative
1388 )
1389 {
1390  char name[SCIP_MAXSTRLEN];
1391  int i;
1392 
1393  assert(scip != NULL);
1394  assert(pricingprobs != NULL);
1395  assert(blockrepresentative != NULL);
1396  assert(npricingprobs > 0);
1397  for( i = 0; i < npricingprobs; i++ )
1398  {
1399  int nbin;
1400  int nint;
1401  int nimpl;
1402  int ncont;
1403 
1404  if( blockrepresentative[i] != i )
1405  continue;
1406 
1407  SCIP_CALL( SCIPgetVarsData(pricingprobs[i], NULL, NULL, &nbin, &nint, &nimpl, &ncont) );
1408 
1409  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "pricing problem %d: %d conss, %d vars (%d bins, %d ints, %d impls and %d cont)\n", i,
1410  SCIPgetNConss(pricingprobs[i]), SCIPgetNVars(pricingprobs[i]), nbin, nint, nimpl, ncont);
1411 
1412  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pricingprob_%d.lp", i);
1413  SCIP_CALL( SCIPwriteOrigProblem(pricingprobs[i], name, NULL, FALSE) );
1414  }
1415 
1416  return SCIP_OKAY;
1417 }
1418 
1419 
1421 static
1422 SCIP_RETCODE initRelaxProblemdata(
1423  SCIP* scip,
1424  SCIP_RELAXDATA* relaxdata
1425  )
1426 {
1427  assert(scip != NULL);
1428  assert(relaxdata != NULL);
1429 
1430  /* initialize relaxator data */
1431  relaxdata->maxmasterconss = 16;
1432  relaxdata->nmasterconss = 0;
1433 
1434  /* arrays of constraints belonging to the master problems */
1435  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->masterconss), relaxdata->maxmasterconss) );
1436  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->origmasterconss), relaxdata->maxmasterconss) );
1437  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->linearmasterconss), relaxdata->maxmasterconss) );
1438 
1439  if( relaxdata->npricingprobs > 0 )
1440  {
1441  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->pricingprobs), relaxdata->npricingprobs) );
1442  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->blockrepresentative), relaxdata->npricingprobs) );
1443  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->nblocksidentical), relaxdata->npricingprobs) );
1444 
1445  /* array for saving convexity constraints belonging to one of the pricing problems */
1446  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(relaxdata->convconss), relaxdata->npricingprobs) );
1447  }
1448 
1449  SCIP_CALL( SCIPhashmapCreate(&(relaxdata->hashorig2origvar), SCIPblkmem(scip), 10*SCIPgetNVars(scip)+1) );
1450 
1451  return SCIP_OKAY;
1452 }
1453 
1454 
1456 static
1457 SCIP_RETCODE createMasterProblem(
1458  SCIP* masterscip,
1459  const char* name,
1460  int clocktype,
1461  SCIP_Real infinity,
1462  SCIP_Real epsilon,
1463  SCIP_Real sumepsilon,
1464  SCIP_Real feastol,
1465  SCIP_Real lpfeastol,
1466  SCIP_Real dualfeastol,
1467  DEC_DECMODE mode
1468  )
1469 {
1470  assert(masterscip != NULL);
1471  assert(name != NULL);
1472 
1473  SCIP_CALL( SCIPcreateProb(masterscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
1474 
1475  /* set clocktype */
1476  SCIP_CALL( SCIPsetIntParam(masterscip, "timing/clocktype", clocktype) );
1477 
1478  /* set numerical tolerances */
1479  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/infinity", infinity) );
1480  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/epsilon", epsilon) );
1481  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/sumepsilon", sumepsilon) );
1482  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/feastol", feastol) );
1483  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/lpfeastol", lpfeastol) );
1484  SCIP_CALL( SCIPsetRealParam(masterscip, "numerics/dualfeastol", dualfeastol) );
1485 
1486  /* disable aggregation and multiaggregation of variables, as this might lead to issues with copied original variables */
1487  SCIP_CALL( SCIPsetBoolParam(masterscip, "presolving/donotaggr", TRUE) );
1488  SCIP_CALL( SCIPsetBoolParam(masterscip, "presolving/donotmultaggr", TRUE) );
1489 
1490  /* the following settings are for decomposition, so if the original problem is solved directly, then these settings
1491  * are not required
1492  */
1493  if( mode == DEC_DECMODE_ORIGINAL )
1494  {
1495  return SCIP_OKAY;
1496  }
1497 
1499  SCIP_CALL( SCIPactivatePricer(masterscip, SCIPfindPricer(masterscip, "gcg")) );
1500 
1501  /* do not modify the time limit after solving the master problem */
1502  SCIP_CALL( SCIPsetBoolParam(masterscip, "reoptimization/commontimelimit", FALSE) );
1503 
1504  /* disable aggregation and multiaggregation of variables, as this might lead to issues with copied original variables */
1505  SCIP_CALL( SCIPsetBoolParam(masterscip, "presolving/donotaggr", TRUE) );
1506  SCIP_CALL( SCIPsetBoolParam(masterscip, "presolving/donotmultaggr", TRUE) );
1507 
1508  /* for Benders' decomposition, some additional parameter settings are required for the master problem. */
1509  if( mode == DEC_DECMODE_BENDERS )
1510  {
1511  SCIP_CALL( SCIPsetSeparating(masterscip, SCIP_PARAMSETTING_OFF, TRUE) );
1512  SCIP_CALL( SCIPsetPresolving(masterscip, SCIP_PARAMSETTING_OFF, TRUE) );
1513  SCIP_CALL( SCIPsetIntParam(masterscip, "presolving/maxrestarts", 0) );
1514  SCIP_CALL( SCIPsetIntParam(masterscip, "propagating/maxroundsroot", 0) );
1515  SCIP_CALL( SCIPsetIntParam(masterscip, "heuristics/trysol/freq", 1) );
1516  SCIP_CALL( SCIPsetBoolParam(masterscip, "constraints/benders/active", TRUE) );
1517  SCIP_CALL( SCIPsetBoolParam(masterscip, "constraints/benderslp/active", TRUE) );
1518  SCIP_CALL( SCIPsetBoolParam(masterscip, "benders/gcg/lnscheck", FALSE) );
1519  SCIP_CALL( SCIPsetIntParam(masterscip, "presolving/maxrounds", 1) );
1520  SCIP_CALL( SCIPsetIntParam(masterscip, "constraints/benders/maxprerounds", 1) );
1521 
1522  /* the trysol heuristic must have a high priority to ensure the solutions found by the relaxator are added to the
1523  * original problem
1524  */
1525  SCIP_CALL( SCIPsetIntParam(GCGgetOriginalprob(masterscip), "heuristics/trysol/freq", 1) );
1526  }
1527 
1528  return SCIP_OKAY;
1529 }
1530 
1531 
1533 static
1534 SCIP_RETCODE createPricingProblem(
1535  SCIP** pricingscip,
1536  const char* name,
1537  int clocktype,
1538  SCIP_Real infinity,
1539  SCIP_Real epsilon,
1540  SCIP_Real sumepsilon,
1541  SCIP_Real feastol,
1542  SCIP_Real lpfeastol,
1543  SCIP_Real dualfeastol,
1544  SCIP_Bool enableppcuts
1545  )
1546 {
1547  assert(pricingscip != NULL);
1548  assert(name != NULL);
1549 
1550  SCIP_CALL( SCIPcreate(pricingscip) );
1551  SCIP_CALL( SCIPincludeDefaultPlugins(*pricingscip) );
1552  SCIP_CALL( setPricingProblemParameters(*pricingscip, clocktype, infinity, epsilon, sumepsilon, feastol, lpfeastol, dualfeastol, enableppcuts) );
1553  SCIP_CALL( SCIPcreateProb(*pricingscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
1554 
1555  return SCIP_OKAY;
1556 }
1557 
1558 
1560 static
1561 SCIP_RETCODE saveOriginalVarMastercoeffs(
1562  SCIP* scip,
1563  SCIP_VAR** origvars,
1564  int norigvars,
1565  int nmasterconss,
1566  SCIP_CONS** linearmasterconss,
1567  SCIP_CONS** masterconss
1568  )
1569 {
1570  int v;
1571  int i;
1572 
1573  assert(scip != NULL);
1574  assert(origvars != NULL || norigvars == 0);
1575  assert(norigvars >= 0);
1576  assert(nmasterconss >= 0);
1577  assert(masterconss != NULL);
1578  assert(linearmasterconss != NULL);
1579 
1580  /* for original variables, save the coefficients in the master problem */
1581  for( v = 0; v < norigvars; v++ )
1582  {
1583  SCIP_VAR* var;
1584  var = SCIPvarGetProbvar(origvars[v]); /*lint !e613*/
1585  assert(GCGvarIsOriginal(var));
1586  assert(GCGoriginalVarGetCoefs(var) == NULL);
1587  GCGoriginalVarSetNCoefs(var, 0);
1588  }
1589 
1590  /* save coefs */
1591  for( i = 0; i < nmasterconss; i++ )
1592  {
1593  SCIP_VAR** vars;
1594  SCIP_Real* vals;
1595  int nvars;
1596 
1597  vars = SCIPgetVarsLinear(scip, linearmasterconss[i]);
1598  nvars = SCIPgetNVarsLinear(scip, linearmasterconss[i]);
1599  vals = SCIPgetValsLinear(scip, linearmasterconss[i]);
1600  for( v = 0; v < nvars; v++ )
1601  {
1602  SCIP_CALL( GCGoriginalVarAddCoef(scip, vars[v], vals[v], masterconss[i]) );
1603  }
1604  }
1605 
1606  return SCIP_OKAY;
1607 }
1608 
1610 static
1611 SCIP_RETCODE createMasterprobConss(
1612  SCIP* scip,
1613  SCIP_RELAXDATA* relaxdata
1614  )
1615 {
1616  SCIP_CONS** masterconss;
1617  int nmasterconss;
1618  SCIP_CONS* newcons;
1619  SCIP_CONS* mastercons;
1620  int c;
1621  SCIP_Bool success;
1622  char name[SCIP_MAXSTRLEN];
1623 
1624  masterconss = DECdecompGetLinkingconss(relaxdata->decdecomp);
1625  nmasterconss = DECdecompGetNLinkingconss(relaxdata->decdecomp);
1626  newcons = NULL;
1627 
1628  // assert(SCIPhashmapGetNElements(relaxdata->hashorig2origvar) == SCIPgetNVars(scip));
1629  for( c = 0; c < nmasterconss; ++c )
1630  {
1631  int nconsvars;
1632  int consvarssize;
1633  SCIP_VAR** consvars;
1634  SCIP_Real* consvals;
1635  SCIP_Bool* releasevars;
1636  int i;
1637 
1638  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(masterconss[c])), "origbranch") == 0 )
1639  continue;
1640 
1641  /* TODO: In the Benders' decomposition case the copy of the constraint could be used.
1642  * Current implementation creates the constraints with the master variables. */
1643  success = FALSE;
1644  /* copy the constraint (dirty trick, we only need lhs and rhs, because variables are added later) */
1645  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear_%s", SCIPconsGetName(masterconss[c]));
1646  SCIP_CALL( SCIPgetConsCopy(scip, scip, masterconss[c], &newcons, SCIPconsGetHdlr(masterconss[c]),
1647  relaxdata->hashorig2origvar, NULL, name,
1648  FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
1649  assert(success);
1650 
1651  /* in the Benders' decomposition mode, all variables from the linking constraints need to be added to the master
1652  * problem. Additionally, if the original problem is solved directly, then we must ensure that all variables are
1653  * added to the master problem.
1654  */
1656  {
1657  nconsvars = GCGconsGetNVars(scip, newcons);
1658  consvarssize = nconsvars;
1659 
1660  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, consvarssize) );
1661  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, consvarssize) );
1662  SCIP_CALL( SCIPallocClearBufferArray(scip, &releasevars, consvarssize) );
1663 
1664  SCIP_CALL( GCGconsGetVars(scip, newcons, consvars, nconsvars) );
1665  SCIP_CALL( GCGconsGetVals(scip, newcons, consvals, nconsvars) );
1666 
1667  for( i = 0; i < nconsvars; i++ )
1668  {
1669  SCIP_VAR* origvar;
1670 
1671  /* if the variable is a linking variable or is directly transferred to the master problem, then it is not
1672  * added to the constraint. This is because the linking variables and the transferred variables are added
1673  * later in GCGmasterCreateInitialMastervars().
1674  */
1675  while( i < nconsvars && (GCGoriginalVarIsLinking(consvars[i]) || GCGoriginalVarIsTransVar(consvars[i])) )
1676  {
1677  consvars[i] = consvars[nconsvars - 1];
1678  consvals[i] = consvals[nconsvars - 1];
1679  nconsvars--;
1680  }
1681 
1682  if( i >= nconsvars )
1683  break;
1684 
1685  /* assigning the origvar to the next variables that is not a linking variable */
1686  origvar = consvars[i];
1687 
1688  assert(GCGoriginalVarGetNMastervars(origvar) <= 1);
1689 
1690  /* if the original has already has a copy in the master problem, then this is used. Otherwise, the master
1691  * problem variable is created.
1692  */
1693  if( GCGoriginalVarGetNMastervars(origvar) > 0 )
1694  {
1695  consvars[i] = GCGoriginalVarGetMastervars(origvar)[0];
1696  releasevars[i] = FALSE;
1697  }
1698  else
1699  {
1700  SCIP_CALL( GCGcreateInitialMasterVar(relaxdata->masterprob, consvars[i], &consvars[i]) );
1701  SCIP_CALL( SCIPaddVar(relaxdata->masterprob, consvars[i]) );
1702 
1703  SCIP_CALL( GCGoriginalVarAddMasterVar(scip, origvar, consvars[i], 1.0) );
1704 
1705  releasevars[i] = TRUE;
1706  }
1707 
1708  assert(GCGoriginalVarGetNMastervars(origvar) <= 1);
1709  }
1710  }
1711  else
1712  {
1713  nconsvars = 0;
1714  consvars = NULL;
1715  consvals = NULL;
1716  releasevars = NULL;
1717  }
1718 
1719  /* create and add corresponding linear constraint in the master problem */
1720  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "m_%s", SCIPconsGetName(masterconss[c]));
1721  SCIP_CALL( SCIPcreateConsLinear(relaxdata->masterprob, &mastercons, name, nconsvars, consvars, consvals,
1722  SCIPgetLhsLinear(scip, newcons), SCIPgetRhsLinear(scip, newcons),
1723  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE) );
1724 
1725  SCIP_CALL( SCIPaddCons(relaxdata->masterprob, mastercons) );
1726  SCIPdebugMessage("Copying %s to masterproblem\n", SCIPconsGetName(masterconss[c]));
1727  /* store the constraints in the arrays origmasterconss and masterconss in the problem data */
1728  SCIP_CALL( ensureSizeMasterConss(scip, relaxdata, relaxdata->nmasterconss+1) );
1729  SCIP_CALL( SCIPcaptureCons(scip, masterconss[c]) );
1730  relaxdata->origmasterconss[relaxdata->nmasterconss] = masterconss[c];
1731  relaxdata->linearmasterconss[relaxdata->nmasterconss] = newcons;
1732  relaxdata->masterconss[relaxdata->nmasterconss] = mastercons;
1733  relaxdata->nmasterconss++;
1734 
1735  /* in the Benders' decomposition mode, the consvars and consvals arrays need to be freed */
1737  {
1738  assert(releasevars != NULL);
1739  assert(consvars != NULL);
1740  for( i = 0; i < nconsvars; i++ )
1741  {
1742  if( releasevars[i] )
1743  {
1744  SCIP_CALL( SCIPreleaseVar(relaxdata->masterprob, &consvars[i]) );
1745  }
1746  }
1747 
1748  SCIPfreeBufferArray(scip, &releasevars);
1749  SCIPfreeBufferArray(scip, &consvals);
1750  SCIPfreeBufferArray(scip, &consvars);
1751  }
1752  }
1753  assert(relaxdata->nmasterconss == nmasterconss);
1754  SCIP_CALL( saveOriginalVarMastercoeffs(scip, SCIPgetVars(scip), SCIPgetNVars(scip), relaxdata->nmasterconss, relaxdata->linearmasterconss, relaxdata->masterconss) );
1755 
1756  return SCIP_OKAY;
1757 }
1758 
1760 static
1761 SCIP_RETCODE createPricingprobConss(
1762  SCIP* scip,
1763  SCIP_RELAXDATA* relaxdata,
1764  SCIP_HASHMAP** hashorig2pricingvar
1765  )
1766 {
1767  SCIP_CONS*** subscipconss;
1768  int* nsubscipconss;
1769  SCIP_CONS* newcons;
1770  SCIP_HASHMAP* hashorig2pricingconstmp;
1771  int nblocks;
1772  int b;
1773  int c;
1774  char name[SCIP_MAXSTRLEN];
1775  SCIP_Bool success;
1776 
1777  assert(scip != NULL);
1778  assert(relaxdata != NULL);
1779 
1780  subscipconss = DECdecompGetSubscipconss(relaxdata->decdecomp);
1781  nsubscipconss = DECdecompGetNSubscipconss(relaxdata->decdecomp);
1782  nblocks = DECdecompGetNBlocks(relaxdata->decdecomp);
1783 
1784  SCIP_CALL( SCIPhashmapCreate(&hashorig2pricingconstmp, SCIPblkmem(scip), SCIPgetNConss(scip)) ); /*lint !e613*/
1785 
1786  for( b = 0; b < nblocks; ++b )
1787  {
1788  assert(hashorig2pricingvar != NULL);
1789  for( c = 0; c < nsubscipconss[b]; ++c )
1790  {
1791  SCIPdebugMessage("copying %s to pricing problem %d\n", SCIPconsGetName(subscipconss[b][c]), b);
1792  if( !SCIPconsIsActive(subscipconss[b][c]) )
1793  {
1794  SCIPdebugMessage("skipping, cons <%s> inactive\n", SCIPconsGetName(subscipconss[b][c]));
1795  continue;
1796  }
1797  SCIP_CALL( SCIPgetTransformedCons(scip, subscipconss[b][c], &subscipconss[b][c]) );
1798  assert(subscipconss[b][c] != NULL);
1799 
1800  /* copy the constraint */
1801  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "p%d_%s", b, SCIPconsGetName(subscipconss[b][c]));
1802  SCIP_CALL( SCIPgetConsCopy(scip, relaxdata->pricingprobs[b], subscipconss[b][c], &newcons, SCIPconsGetHdlr(subscipconss[b][c]),
1803  hashorig2pricingvar[b], hashorig2pricingconstmp, name,
1804  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, &success) );
1805 
1806  /* constraint was successfully copied */
1807  assert(success);
1808 
1809  SCIP_CALL( SCIPaddCons(relaxdata->pricingprobs[b], newcons) );
1810 
1811 
1812 #ifndef NDEBUG
1813  {
1814  SCIP_VAR** curvars;
1815  int ncurvars;
1816 
1817  ncurvars = GCGconsGetNVars(relaxdata->pricingprobs[b], newcons);
1818  curvars = NULL;
1819  if( ncurvars > 0 )
1820  {
1821  int i;
1822 
1823  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1824  SCIP_CALL( GCGconsGetVars(relaxdata->pricingprobs[b], newcons, curvars, ncurvars) );
1825 
1826  for( i = 0; i < ncurvars; ++i )
1827  {
1828  if( SCIPisFeasEQ( scip, SCIPvarGetLbGlobal(curvars[i]), SCIPvarGetUbGlobal(curvars[i]) ) && SCIPisFeasEQ( scip, SCIPvarGetUbGlobal(curvars[i]), 0. ) )
1829  continue;
1830 
1831  assert(GCGvarIsPricing(curvars[i]) || ( SCIPvarIsNegated(curvars[i]) && GCGvarIsPricing(SCIPvarGetNegatedVar(curvars[i]) ) ) );
1832  }
1833 
1834  SCIPfreeBufferArrayNull(scip, &curvars);
1835  }
1836  }
1837 #endif
1838  SCIP_CALL( SCIPreleaseCons(relaxdata->pricingprobs[b], &newcons) );
1839  }
1840  }
1841 
1842  SCIPhashmapFree(&hashorig2pricingconstmp);
1843 
1844  return SCIP_OKAY;
1845 }
1846 
1848 static
1849 SCIP_RETCODE createMaster(
1850  SCIP* scip,
1851  SCIP_RELAXDATA* relaxdata
1852  )
1853 {
1854  int npricingprobs;
1855  SCIP_HASHMAP** hashorig2pricingvar;
1856  SCIP_Bool enableppcuts;
1857  char name[SCIP_MAXSTRLEN];
1858  int clocktype;
1859  SCIP_Real infinity;
1860  SCIP_Real epsilon;
1861  SCIP_Real sumepsilon;
1862  SCIP_Real feastol;
1863  SCIP_Real lpfeastol;
1864  SCIP_Real dualfeastol;
1865  int i;
1866 
1867  assert(scip != NULL);
1868  assert(relaxdata != NULL);
1869 
1870  assert(relaxdata->decdecomp != NULL);
1871 
1872 
1873  SCIP_CALL( convertStructToGCG(scip, relaxdata, relaxdata->decdecomp) );
1874 
1875  /* if there are no pricing problems, then the original problem will be solved directly. */
1876  if( relaxdata->npricingprobs == 0 )
1877  {
1878  int origmode;
1879 
1880  /* setting the mode to ORIGINAL */
1881  SCIP_CALL( SCIPunfixParam(scip, "relaxing/gcg/mode") );
1882  SCIP_CALL( SCIPgetIntParam(scip, "relaxing/gcg/mode", &origmode) );
1883  SCIP_CALL( SCIPsetIntParam(scip, "relaxing/gcg/mode", (int) DEC_DECMODE_ORIGINAL) );
1884  SCIP_CALL( SCIPfixParam(scip, "relaxing/gcg/mode") );
1885 
1886  /* if the original problem is to be solved, then we need to free the currently master problem and create a new
1887  * SCIP instance
1888  */
1889 
1890  if( origmode == DEC_DECMODE_DANTZIGWOLFE )
1891  {
1892  SCIP* tmpscip;
1893 
1894  /* initialising the master problem */
1895  SCIP_CALL( SCIPsetIntParam(relaxdata->altmasterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
1896  SCIP_CALL( SCIPsetBoolParam(relaxdata->altmasterprob, "display/relevantstats", FALSE) );
1897 
1898  /* disabling unnecessary display columns */
1899  SCIP_CALL( SCIPsetIntParam(scip, "display/sumlpiterations/active", 0) );
1900  SCIP_CALL( SCIPsetIntParam(scip, "display/lpiterations/active", 0) );
1901  SCIP_CALL( SCIPsetIntParam(scip, "display/degeneracy/active", 0) );
1902 
1903  /* setting the total node limit to 1 for the original SCIP instance. This is because Benders' decomposition solves
1904  * the MIP within the relaxator of the root node. So no branching in the original problem is required.
1905  */
1906  SCIP_CALL( SCIPsetLongintParam(scip, "limits/totalnodes", 1) );
1907 
1908  /* swapping the master problem with the original master problem */
1909  tmpscip = relaxdata->altmasterprob;
1910  relaxdata->altmasterprob = relaxdata->masterprob;
1911  relaxdata->masterprob = tmpscip;
1912  }
1913 
1914  SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "constraints/components/maxprerounds", 0) );
1915  SCIP_CALL( SCIPsetBoolParam(scip, "relaxing/gcg/discretization", FALSE) );
1916  }
1917 
1918 
1919  npricingprobs = relaxdata->npricingprobs;
1920  hashorig2pricingvar = NULL;
1921 
1922  if( npricingprobs > 0 )
1923  {
1924  /* create hashmaps for mapping from original to pricing variables */
1925  SCIP_CALL( SCIPallocBufferArray(scip, &(hashorig2pricingvar), npricingprobs) );
1926  }
1927 
1928  SCIPdebugMessage("Creating master problem...\n");
1929 
1930  SCIP_CALL( initRelaxProblemdata(scip, relaxdata) );
1931 
1932  /* get clocktype of the original SCIP instance in order to use the same clocktype in master and pricing problems */
1933  SCIP_CALL( SCIPgetIntParam(scip, "timing/clocktype", &clocktype) );
1934 
1935  /* get numerical tolerances of the original SCIP instance in order to use the same numerical tolerances in master and pricing problems */
1936  SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infinity) );
1937  SCIP_CALL( SCIPgetRealParam(scip, "numerics/epsilon", &epsilon) );
1938  SCIP_CALL( SCIPgetRealParam(scip, "numerics/sumepsilon", &sumepsilon) );
1939  SCIP_CALL( SCIPgetRealParam(scip, "numerics/feastol", &feastol) );
1940  SCIP_CALL( SCIPgetRealParam(scip, "numerics/lpfeastol", &lpfeastol) );
1941  SCIP_CALL( SCIPgetRealParam(scip, "numerics/dualfeastol", &dualfeastol) );
1942 
1943  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "master_%s", SCIPgetProbName(scip));
1944  SCIP_CALL( createMasterProblem(relaxdata->masterprob, name, clocktype, infinity, epsilon, sumepsilon, feastol,
1945  lpfeastol, dualfeastol, relaxdata->mode) );
1946 
1947  enableppcuts = FALSE;
1948  SCIP_CALL( SCIPgetBoolParam(scip, "sepa/basis/enableppcuts", &enableppcuts) );
1949 
1950  /* create the pricing problems */
1951  for( i = 0; i < npricingprobs; i++ )
1952  {
1953  relaxdata->convconss[i] = NULL;
1954  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pricing_block_%d", i);
1955  SCIP_CALL( createPricingProblem(&(relaxdata->pricingprobs[i]), name, clocktype, infinity, epsilon, sumepsilon,
1956  feastol, lpfeastol, dualfeastol, enableppcuts) );
1957  SCIP_CALL( SCIPhashmapCreate(&(hashorig2pricingvar[i]), SCIPblkmem(scip), SCIPgetNVars(scip)) ); /*lint !e613*/
1958  }
1959 
1960  SCIP_CALL( createPricingVariables(scip, relaxdata, hashorig2pricingvar) );
1961 
1962  /* create master and pricing problem constraints
1963  * If the master problem is solved directly, then we can still call methods creating the pricing problems. These
1964  * methods check the number of pricing problems and number of blocks. As such, if the original problem is solved
1965  * directly, then nothing will happen in these methods
1966  */
1967  SCIP_CALL( createMasterprobConss(scip, relaxdata) );
1968  SCIP_CALL( createPricingprobConss(scip, relaxdata, hashorig2pricingvar) );
1969  SCIP_CALL( GCGmasterCreateInitialMastervars(relaxdata->masterprob) );
1970 
1971  /* check if the master problem is a set partitioning or set covering problem */
1972  SCIP_CALL( checkSetppcStructure(scip, relaxdata) );
1973 
1974  /* check for identity of blocks */
1975  SCIP_CALL( checkIdenticalBlocks(scip, relaxdata, hashorig2pricingvar) );
1976 
1977  /* the convexity constraints are only added in the Dantzig-Wolfe mode */
1978  if( relaxdata->mode == DEC_DECMODE_DANTZIGWOLFE )
1979  {
1980  for( i = 0; i < relaxdata->npricingprobs; i++ )
1981  {
1982  if( relaxdata->blockrepresentative[i] != i )
1983  continue;
1984 
1985  /* create the corresponding convexity constraint */
1986  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "conv_block_%d", i);
1987  SCIP_CALL( SCIPcreateConsLinear(relaxdata->masterprob, &(relaxdata->convconss[i]), name, 0, NULL, NULL,
1988  relaxdata->nblocksidentical[i]*1.0, relaxdata->nblocksidentical[i]*1.0,
1989  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, FALSE) );
1990  SCIP_CALL( SCIPaddCons(relaxdata->masterprob, relaxdata->convconss[i]) );
1991  }
1992  }
1993 
1994  /* set integral objective status in the extended problem, if possible */
1995  if( SCIPisObjIntegral(scip) && relaxdata->discretization && SCIPgetNContVars(scip) == 0
1996  && relaxdata->mode == DEC_DECMODE_DANTZIGWOLFE )
1997  {
1998  SCIP_CALL( SCIPsetObjIntegral(relaxdata->masterprob) );
1999  }
2000 
2001  /* display statistics */
2002  if( relaxdata->dispinfos )
2003  {
2004  SCIP_CALL( displayPricingStatistics(scip, relaxdata->pricingprobs, relaxdata->npricingprobs, relaxdata->blockrepresentative) );
2005  SCIP_CALL( SCIPwriteOrigProblem(relaxdata->masterprob, "masterprob.lp", "lp", FALSE) );
2006  }
2007 
2008  if( hashorig2pricingvar != NULL )
2009  {
2010  for( i = 0; i < npricingprobs; i++ )
2011  SCIPhashmapFree(&(hashorig2pricingvar[i]));
2012 
2013  SCIPfreeBufferArray(scip, &(hashorig2pricingvar));
2014  }
2015 
2016  /* get used memory and save it for reference */
2017  for( i = 0; i < npricingprobs; ++i )
2018  {
2019  relaxdata->pricingprobsmemused += SCIPgetMemUsed(relaxdata->pricingprobs[i])/1048576.0;
2020  }
2021 
2022  return SCIP_OKAY;
2023 }
2024 
2026 static
2027 SCIP_RETCODE combineSolutions(
2028  SCIP* scip,
2029  SCIP_SOL** newsol,
2030  SCIP** probs,
2031  int nprobs
2032  )
2033 {
2034 #ifdef SCIP_DEBUG
2035  int i;
2036 #endif
2037 
2038  int v;
2039  int nvars;
2040 
2041  SCIP_VAR** vars;
2042  assert(scip != NULL);
2043  assert(newsol != NULL);
2044  assert(probs != NULL);
2045  assert(nprobs > 0);
2046 
2047  SCIP_CALL( SCIPcreateSol(scip, newsol, NULL) );
2048  nvars = SCIPgetNVars(scip);
2049  vars = SCIPgetVars(scip);
2050 
2051 #ifdef SCIP_DEBUG
2052  for( i = 0; i < nprobs; ++i )
2053  {
2054  if( probs[i] == NULL )
2055  continue;
2056 
2057  SCIPprintOrigProblem(probs[i], NULL, "lp", FALSE);
2058  SCIPprintSol(probs[i], SCIPgetBestSol(probs[i]), NULL, FALSE );
2059  }
2060 #endif
2061 
2062  for( v = 0; v < nvars; ++v )
2063  {
2064  SCIP_VAR* pricingvar;
2065  int block;
2066 
2067  pricingvar = GCGoriginalVarGetPricingVar(vars[v]);
2068  block = GCGvarGetBlock(pricingvar);
2069  assert(block >= 0);
2070  assert(block < nprobs);
2071  assert(probs[block] != NULL);
2072 
2073  /* @todo solval should be 0 before, anyway, check it with an assert */
2074  SCIP_CALL( SCIPincSolVal(scip, *newsol, vars[v], SCIPgetSolVal(probs[block], SCIPgetBestSol(probs[block]), pricingvar)) );
2075  }
2076  return SCIP_OKAY;
2077 }
2078 
2080 static
2081 SCIP_RETCODE setPricingObjsOriginal(
2082  SCIP* scip,
2083  SCIP** probs,
2084  int nprobs
2085  )
2086 {
2087  int v;
2088  int nvars;
2089  SCIP_VAR** vars;
2090  int i;
2091 
2092  assert(scip != NULL);
2093  assert(probs != NULL);
2094  assert(nprobs > 0);
2095 
2096  nvars = SCIPgetNVars(scip);
2097  vars = SCIPgetVars(scip);
2098 
2099  /* if the Benders' decomposition is used, then the transformed problem of the subproblems must be freed.
2100  * This is because the within the create subproblem stage, if the subproblem is an LP, then the SCIP instance is put
2101  * into probing mode.
2102  */
2104  {
2105  for( i = 0; i < nprobs; i++ )
2106  {
2107  /* if the problem is not in SCIP_STAGE_PROBLEM, then the transformed problem must be freed. The subproblem
2108  * should also be in probing mode.
2109  */
2110  if( SCIPgetStage(probs[i]) != SCIP_STAGE_PROBLEM )
2111  {
2112  if( SCIPinProbing(probs[i]) )
2113  {
2114  SCIP_CALL( SCIPendProbing(probs[i]) );
2115  }
2116 
2117  SCIP_CALL( SCIPfreeTransform(probs[i]) );
2118  }
2119  }
2120  }
2121 
2122  for( v = 0; v < nvars; ++v )
2123  {
2124  SCIP_VAR* pricingvar;
2125  SCIP_VAR* origvar;
2126  SCIP_Real objvalue;
2127 
2128  assert(GCGvarIsOriginal(vars[v]));
2129  origvar = SCIPvarGetProbvar(vars[v]);
2130 
2131  if( !GCGisPricingprobRelevant(scip, GCGvarGetBlock(origvar)) )
2132  continue;
2133 
2134  pricingvar = GCGoriginalVarGetPricingVar(origvar);
2135  assert(pricingvar != NULL);
2136 
2137  objvalue = SCIPvarGetObj(origvar);
2138  /* SCIPinfoMessage(scip, NULL, "%s: %f block %d\n", SCIPvarGetName(origvar), SCIPvarGetObj(origvar),
2139  GCGvarGetBlock(origvar)); */
2140  SCIP_CALL( SCIPchgVarObj(probs[GCGvarGetBlock(pricingvar)], pricingvar, objvalue) );
2141  }
2142  return SCIP_OKAY;
2143 }
2144 
2146 static
2147 SCIP_RETCODE solveBlockProblem(
2148  SCIP* scip,
2149  SCIP* blockprob,
2150  SCIP_RELAXDATA* relaxdata,
2151  SCIP_Real timelimit,
2152  int blocknum,
2153  SCIP_RESULT* result,
2154  SCIP_Real* objvalue
2155  )
2156 {
2157  SCIP_Real blocktimelimit;
2158 
2159  assert(scip != NULL);
2160  assert(result != NULL);
2161  assert(objvalue != NULL);
2162 
2163  (*result) = SCIP_DIDNOTRUN;
2164 
2165 #ifdef SCIP_DEBUG
2166  char name[SCIP_MAXSTRLEN];
2167 #endif
2168 
2169  if( blockprob == NULL )
2170  {
2171  (*result) = SCIP_SUCCESS;
2172  return SCIP_OKAY;
2173  }
2174 
2176  {
2177  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Solving block %i.\n", blocknum+1);
2178  }
2179 
2180  SCIP_CALL( SCIPsetIntParam(blockprob, "display/verblevel", (int)SCIP_VERBLEVEL_NORMAL) );
2181 
2182  /* give the pricing problem 2% more time then the original scip has left */
2183  if( SCIPgetStage(blockprob) > SCIP_STAGE_PROBLEM )
2184  {
2185  if( SCIPisInfinity(scip, timelimit) )
2186  {
2187  blocktimelimit = SCIPinfinity(blockprob);
2188  }
2189  else
2190  {
2191  blocktimelimit = (timelimit - SCIPgetSolvingTime(scip)) * 1.02 + SCIPgetSolvingTime(blockprob);
2192  blocktimelimit = MIN(SCIPinfinity(blockprob), blocktimelimit); /*lint !e666*/
2193  }
2194  }
2195  else
2196  {
2197  if( SCIPisInfinity(scip, timelimit) )
2198  {
2199  blocktimelimit = SCIPinfinity(blockprob);
2200  }
2201  else
2202  {
2203  blocktimelimit = (timelimit - SCIPgetSolvingTime(scip)) * 1.02;
2204  blocktimelimit = MIN(SCIPinfinity(blockprob), blocktimelimit); /*lint !e666*/
2205  }
2206  }
2207 
2208  if( blocktimelimit < 0 )
2209  {
2210  (*result) = SCIP_DIDNOTRUN;
2211  return SCIP_OKAY;
2212  }
2213 
2214  SCIP_CALL( SCIPsetRealParam(blockprob, "limits/time", blocktimelimit) );
2215 
2216 #ifdef SCIP_DEBUG
2217  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "block_%i.lp", blocknum);
2218  SCIP_CALL( SCIPwriteOrigProblem(blockprob, name, "lp", FALSE) );
2219 #endif
2220 
2222  {
2223  SCIP_CALL( SCIPsolve(blockprob) );
2224  }
2225  else
2226  {
2227  SCIP_BENDERS* benders;
2228  SCIP_Bool infeasible;
2229 
2231 
2232  /* retrieving the Benders' decomposition */
2233  benders = SCIPfindBenders(relaxdata->masterprob, "gcg");
2234 
2235  /* since the diagonal blocks are being solved, this indicates that the subproblems are independent. As such, we
2236  * can declare this in the Benders' decomposition framework. This allows us to call
2237  * SCIPsolveBendersSubproblem() without setting up the problem
2238  */
2239  SCIPbendersSetSubproblemIsIndependent(benders, blocknum, TRUE);
2240 
2241  /* solving the Benders' decomposition subproblem */
2242  SCIP_CALL( SCIPsolveBendersSubproblem(relaxdata->masterprob, benders, NULL, blocknum, &infeasible,
2243  SCIP_BENDERSENFOTYPE_CHECK, TRUE, NULL) );
2244  }
2245 
2246 
2247  switch( SCIPgetStatus(blockprob) )
2248  {
2249  case SCIP_STATUS_UNBOUNDED:
2250  case SCIP_STATUS_INFORUNBD:
2251  case SCIP_STATUS_INFEASIBLE:
2252  /* no other blocks should be solved. */
2253  *result = SCIP_CUTOFF;
2254  break;
2255  case SCIP_STATUS_BESTSOLLIMIT:
2256  case SCIP_STATUS_MEMLIMIT:
2257  case SCIP_STATUS_STALLNODELIMIT:
2258  case SCIP_STATUS_NODELIMIT:
2259  case SCIP_STATUS_SOLLIMIT:
2260  case SCIP_STATUS_TIMELIMIT:
2261  /* no other blocks should be solved. */
2262  *result = SCIP_DIDNOTRUN;
2263  break;
2264  case SCIP_STATUS_GAPLIMIT:
2265  case SCIP_STATUS_OPTIMAL:
2266  (*result) = SCIP_SUCCESS;
2267  (*objvalue) += SCIPgetDualbound(blockprob);
2268  break;
2269  default:
2270  break;
2271  } /*lint !e788*/
2272 
2273  return SCIP_OKAY;
2274 }
2275 
2277 static
2278 SCIP_RETCODE freeBlockProblem(
2279  SCIP* scip,
2280  SCIP* blockprob,
2281  SCIP_RELAXDATA* relaxdata,
2282  int blocknum
2283  )
2284 {
2285  assert(scip != NULL);
2286 
2287  if( blockprob == NULL )
2288  return SCIP_OKAY;
2289 
2291  {
2292  SCIP_CALL( SCIPfreeTransform(blockprob) );
2293  }
2294  else
2295  {
2296  SCIP_BENDERS* benders;
2297 
2299 
2300  /* retrieving the Benders' decomposition */
2301  benders = SCIPfindBenders(relaxdata->masterprob, "gcg");
2302 
2303  /* freeing the Benders' decomposition subproblems */
2304  SCIP_CALL( SCIPfreeBendersSubproblem(relaxdata->masterprob, benders, blocknum) );
2305  }
2306 
2307  return SCIP_OKAY;
2308 }
2309 
2311 static
2312 SCIP_RETCODE solveDiagonalBlocks(
2313  SCIP* scip,
2314  SCIP_RELAXDATA* relaxdata,
2315  SCIP_RESULT* result,
2316  SCIP_Real* lowerbound
2317  )
2318 {
2319  int i;
2320  SCIP_Real timelimit;
2321  SCIP_Real objvalue;
2322  SCIP_SOL *newsol;
2323  SCIP_Bool isfeasible;
2324  SCIP_RESULT solveresult;
2325 
2326  /* set objective of pricing problems to original objective */
2328  {
2329  SCIP_CALL( setPricingObjsOriginal(scip, relaxdata->pricingprobs, relaxdata->npricingprobs) );
2330  }
2331 
2332  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2333 
2334  objvalue = 0.0;
2335 
2337  {
2338  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Block diagonal structure detected, solving blocks individually.\n");
2339  }
2340 
2341  /* if the original problem is solved directly, then we call solveBlockProblem with the master problem */
2343  {
2344  SCIP_CALL( solveBlockProblem(scip, relaxdata->masterprob, relaxdata, timelimit, -1, &solveresult, &objvalue) );
2345 
2346  if( solveresult == SCIP_CUTOFF || solveresult == SCIP_DIDNOTRUN )
2347  {
2348  (*result) = solveresult;
2349  return SCIP_OKAY;
2350  }
2351  }
2352  else
2353  {
2354  /* solve pricing problems one after the other */
2355  for( i = 0; i < relaxdata->npricingprobs; ++i )
2356  {
2357  SCIP_CALL( solveBlockProblem(scip, relaxdata->pricingprobs[i], relaxdata, timelimit, i, &solveresult, &objvalue) );
2358 
2359  if( solveresult == SCIP_CUTOFF || solveresult == SCIP_DIDNOTRUN )
2360  {
2361  (*result) = solveresult;
2362  return SCIP_OKAY;
2363  }
2364  }
2365  }
2366 
2367  /* get solution and glue it together */
2368 
2370  {
2371  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, SCIPgetBestSol(relaxdata->masterprob), &newsol) );
2372  }
2373  else
2374  {
2375  SCIP_CALL( combineSolutions(scip, &newsol, relaxdata->pricingprobs, relaxdata->npricingprobs) );
2376  }
2377 
2378  /* update lower bound pointer and add solution such that this node will be cut off automatically */
2379  if( SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE )
2380  *lowerbound = -objvalue;
2381  else
2382  *lowerbound = objvalue;
2383 
2384  SCIP_CALL( SCIPcheckSol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &isfeasible) );
2385  assert(isfeasible);
2386 
2387  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &isfeasible) );
2388 
2391  /* if the original problem is solved directly, then we call freeBlockProblem with the master problem */
2393  {
2394  /* solve pricing problems one after the other */
2395  for( i = 0; i < relaxdata->npricingprobs; ++i )
2396  {
2397  SCIP_CALL( freeBlockProblem(scip, relaxdata->pricingprobs[i], relaxdata, i) );
2398  }
2399  }
2400 
2401  *result = SCIP_SUCCESS;
2402 
2403  return SCIP_OKAY;
2404 
2405 }
2406 
2408 static
2409 SCIP_RETCODE initRelaxator(
2410  SCIP* scip,
2411  SCIP_RELAX* relax
2412  )
2413 {
2414  SCIP* masterprob;
2415  SCIP_VAR** vars;
2416  SCIP_CONS** oldconss;
2417  SCIP_RELAXDATA* relaxdata;
2418  int i;
2419  int nvars;
2420  int permutationseed;
2421  int oxfordcomma;
2422 
2423  assert(scip != NULL);
2424  assert(relax != NULL);
2425 
2426  relaxdata = SCIPrelaxGetData(relax);
2427  assert(relaxdata != NULL);
2428 
2429  /* when the original problem should be solved directly, then a decomposition must be made with zero blocks */
2431  {
2432  DEC_DECOMP* decomp;
2433  SCIP_RETCODE retcode;
2434 
2435  assert(relaxdata->decdecomp == NULL);
2436 
2437  retcode = DECcreateBasicDecomp(scip, &decomp, TRUE);
2438  assert(retcode == SCIP_OKAY);
2439  if( retcode != SCIP_OKAY )
2440  {
2441  SCIPerrorMessage("Could not add decomp to cons_decomp!\n");
2442  return SCIP_ERROR;
2443  }
2444 
2445  assert(decomp != NULL );
2446 
2447  GCGsetStructDecdecomp(scip, decomp);
2448  }
2449 
2450  if( relaxdata->decdecomp == NULL )
2451  {
2452  relaxdata->decdecomp = DECgetBestDecomp(scip);
2453  if( relaxdata->decdecomp == NULL )
2454  {
2456  relaxdata->decdecomp = DECgetBestDecomp(scip);
2457  if( relaxdata->decdecomp == NULL )
2458  {
2459  SCIP_Bool createbasicdecomp;
2460  SCIP_CALL( SCIPgetBoolParam(scip, "constraints/decomp/createbasicdecomp", &createbasicdecomp) );
2461  if( createbasicdecomp )
2462  {
2463  DEC_DECOMP* decomp;
2464  SCIP_RETCODE retcode;
2465  SCIPinfoMessage(scip, NULL, " CREATE BASIC DECOMP!\n");
2466  retcode = DECcreateBasicDecomp(scip, &decomp, FALSE);
2467  if( retcode != SCIP_OKAY )
2468  {
2469  SCIPerrorMessage("Could not add decomp to cons_decomp!\n");
2470  SCIPABORT();
2471  return SCIP_ERROR;
2472  }
2473 
2474 
2475  assert(decomp != NULL );
2476 
2477  SCIP_CALL( SCIPconshdlrDecompAddDecdecomp(scip, decomp) );
2478  relaxdata->decdecomp = DECgetBestDecomp(scip);
2479 
2480  }
2481  else
2482  {
2483  SCIPerrorMessage("No decomposition specified!\n");
2484  return SCIP_ERROR;
2485  }
2486 
2487  assert( relaxdata->decdecomp != NULL );
2488  }
2489  }
2490  }
2491 
2492  oxfordcomma = 0;
2493  SCIPinfoMessage(scip, NULL, "Chosen structure has %d blocks", DECdecompGetNBlocks(relaxdata->decdecomp));
2494  /* every master-only variable internally also counts as linking, but should not be reported as linking variable */
2495  if ( DECdecompGetNLinkingvars(relaxdata->decdecomp) - DECdecompGetNMastervars(relaxdata->decdecomp) > 0)
2496  {
2497  SCIPinfoMessage(scip, NULL, ", %d linking variables", DECdecompGetNLinkingvars(relaxdata->decdecomp) - DECdecompGetNMastervars(relaxdata->decdecomp));
2498  ++oxfordcomma;
2499  }
2500  if ( DECdecompGetNMastervars(relaxdata->decdecomp) > 0 )
2501  {
2502  SCIPinfoMessage(scip, NULL, ", %d master-only (static) variables", DECdecompGetNMastervars(relaxdata->decdecomp));
2503  ++oxfordcomma;
2504  }
2505  if ( oxfordcomma > 0 )
2506  {
2507  SCIPinfoMessage(scip, NULL, ",");
2508  }
2509  SCIPinfoMessage(scip, NULL, " and %d linking constraints.\n", DECdecompGetNLinkingconss(relaxdata->decdecomp));
2510  SCIPinfoMessage(scip, NULL, "This decomposition has a maxwhite score of %f.\n", DECdecompGetMaxwhiteScore(relaxdata->decdecomp));
2511 
2512  /* permute the decomposition if the permutation seed is set */
2513  SCIP_CALL( SCIPgetIntParam(scip, "randomization/permutationseed", &permutationseed) );
2514 
2515  if( permutationseed > 0 )
2516  {
2517  SCIP_RANDNUMGEN* randnumgen;
2518 
2519  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, (unsigned int) permutationseed, TRUE) );
2520  SCIP_CALL( DECpermuteDecomp(scip, relaxdata->decdecomp, randnumgen) );
2521  SCIPfreeRandom(scip, &randnumgen);
2522  }
2523 
2524  if( relaxdata->discretization && (SCIPgetNContVars(scip) > 0) )
2525  {
2526  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Warning: Discretization with continuous variables is only an experimental feature.\n");
2527  }
2528 
2529  SCIP_CALL( createMaster(scip, relaxdata) );
2530 
2531  /* for Benders' decomposition, the Benders' plugin must be activated */
2532  if( relaxdata->mode == DEC_DECMODE_BENDERS )
2533  {
2534  SCIP_CALL( SCIPactivateBenders(relaxdata->masterprob, SCIPfindBenders(relaxdata->masterprob, "gcg"),
2535  relaxdata->npricingprobs) );
2536  }
2537 
2538  masterprob = relaxdata->masterprob;
2539  assert(masterprob != NULL);
2540 
2541  relaxdata->lastsolvednodenr = -1;
2542 
2543  SCIP_CALL( SCIPtransformProb(masterprob) );
2544  SCIP_CALL( SCIPduplicateMemoryArray(scip, &oldconss, relaxdata->masterconss, relaxdata->nmasterconss) );
2545 
2546  /* transform the master constraints */
2547  SCIP_CALL( SCIPtransformConss(masterprob, relaxdata->nmasterconss,
2548  relaxdata->masterconss, relaxdata->masterconss) );
2549  for( i = 0; i < relaxdata->nmasterconss; ++i )
2550  {
2551  SCIP_CALL( SCIPreleaseCons(masterprob, &(oldconss[i])) );
2552  }
2553  SCIPfreeMemoryArray(scip, &oldconss);
2554 
2555  /* transform the decomposition */
2556  SCIP_CALL( DECdecompTransform(scip, relaxdata->decdecomp) );
2557 
2558  /* transform the convexity constraints */
2559  for( i = 0; i < relaxdata->npricingprobs; i++ )
2560  {
2561  if( relaxdata->convconss[i] != NULL )
2562  {
2563  SCIP_CONS* oldcons = relaxdata->convconss[i];
2564  SCIP_CALL( SCIPreleaseCons(masterprob, &oldcons) );
2565  SCIP_CALL( SCIPtransformCons(masterprob, relaxdata->convconss[i], &(relaxdata->convconss[i])) );
2566  }
2567  }
2568 
2569  nvars = SCIPgetNVars(scip);
2570  vars = SCIPgetVars(scip);
2571 
2572  /* transform the linking variable constraints */
2573  for( i = 0; i < nvars; ++i )
2574  {
2575  assert(GCGvarIsOriginal(vars[i]));
2576 
2577  if( GCGoriginalVarIsLinking(vars[i]) )
2578  {
2579  int j;
2580  SCIP_CONS** linkconss;
2581  linkconss = GCGlinkingVarGetLinkingConss(vars[i]);
2582  /* the linking constraints could be NULL if the Benders' decomposition is used. */
2583  if( linkconss != NULL )
2584  {
2585  for( j = 0; j < relaxdata->npricingprobs; ++j )
2586  {
2587  if( linkconss[j] != NULL )
2588  {
2589  SCIP_CONS* tempcons;
2590  SCIP_CALL( SCIPtransformCons(masterprob, linkconss[j], &(tempcons)) );
2591  GCGlinkingVarSetLinkingCons(vars[i], tempcons, j);
2592  }
2593  }
2594  }
2595  }
2596  }
2597  for( i = 0; i < relaxdata->nvarlinkconss; ++i )
2598  {
2599  SCIP_CONS* transcons;
2600 
2601  SCIP_CALL( SCIPgetTransformedCons(masterprob, relaxdata->varlinkconss[i], &transcons) );
2602  assert(transcons != NULL);
2603 
2604  SCIP_CALL( SCIPreleaseCons(masterprob, &relaxdata->varlinkconss[i]) );
2605  relaxdata->varlinkconss[i] = transcons;
2606  }
2607 
2608  /* set objective limit in master problem if objective limit in original problem is finite */
2609  if( !SCIPisInfinity(scip, (int) SCIPgetObjsense(scip) * SCIPgetObjlimit(scip)) )
2610  {
2611  SCIP_CALL( SCIPsetObjlimit(masterprob, (int) SCIPgetObjsense(scip) * SCIPgetObjlimit(scip)) );
2612  }
2613 
2614  return SCIP_OKAY;
2615 }
2616 
2618 static
2619 void initRelaxdata(
2620  SCIP_RELAXDATA* relaxdata
2621  )
2622 {
2623  assert(relaxdata != NULL);
2624 
2625  relaxdata->decdecomp = NULL;
2626 
2627  relaxdata->blockrepresentative = NULL;
2628  relaxdata->convconss = NULL;
2629  relaxdata->hashorig2origvar = NULL;
2630  relaxdata->lastsolvednodenr = 0;
2631 
2632  relaxdata->linearmasterconss = NULL;
2633  relaxdata->origmasterconss = NULL;
2634  relaxdata->masterconss = NULL;
2635  relaxdata->nmasterconss = 0;
2636 
2637  relaxdata->npricingprobs = -1;
2638  relaxdata->pricingprobs = NULL;
2639  relaxdata->nrelpricingprobs = 0;
2640  relaxdata->currentorigsol = NULL;
2641  relaxdata->storedorigsol = NULL;
2642  relaxdata->origsolfeasible = FALSE;
2643  relaxdata->storedfeasibility = FALSE;
2644  relaxdata->nblocksidentical = NULL;
2645 
2646  relaxdata->lastmastersol = NULL;
2647  relaxdata->lastmasterlpiters = 0;
2648  relaxdata->markedmasterconss = NULL;
2649  relaxdata->masterinprobing = FALSE;
2650  relaxdata->probingheur = NULL;
2651 
2652  relaxdata->ntransvars = 0;
2653  relaxdata->nlinkingvars = 0;
2654  relaxdata->nvarlinkconss = 0;
2655  relaxdata->varlinkconss = NULL;
2656  relaxdata->varlinkconsblock = NULL;
2657  relaxdata->pricingprobsmemused = 0.0;
2658 
2659  relaxdata->relaxisinitialized = FALSE;
2660  relaxdata->simplexiters = 0;
2661 
2662  relaxdata->filename = NULL;
2663 }
2664 
2665 /*
2666  * Callback methods of relaxator
2667  */
2668 
2670 static
2671 SCIP_DECL_RELAXFREE(relaxFreeGcg)
2673  SCIP_RELAXDATA* relaxdata;
2674 
2675  relaxdata = SCIPrelaxGetData(relax);
2676  assert(relaxdata != NULL);
2677 
2678  /* free master problem */
2679  if( relaxdata->masterprob != NULL )
2680  {
2681  SCIP_CALL( SCIPfree(&(relaxdata->masterprob)) );
2682  }
2683 
2684  /* free the alternate master problem */
2685  if( relaxdata->altmasterprob != NULL )
2686  {
2687  SCIP_CALL( SCIPfree(&(relaxdata->altmasterprob)) );
2688  }
2689 
2690  /* free used decomposition */
2691  if( relaxdata->decdecomp != NULL )
2692  {
2693  SCIP_CALL( DECdecompFree(scip, &relaxdata->decdecomp) );
2694  }
2695 
2696  SCIPfreeBlockMemoryArrayNull( scip, & relaxdata->filename, SCIP_MAXSTRLEN);
2697  SCIPfreeMemory(scip, &relaxdata);
2698 
2699  return SCIP_OKAY;
2700 }
2701 
2704 static
2705 SCIP_DECL_RELAXEXIT(relaxExitGcg)
2707  SCIP_RELAXDATA* relaxdata;
2708 
2709  assert(scip != NULL);
2710  assert(relax != NULL);
2711 
2712  relaxdata = SCIPrelaxGetData(relax);
2713  assert(relaxdata != NULL);
2714 
2715  if( relaxdata->decdecomp != NULL )
2716  {
2717  SCIP_CALL( DECdecompFree(scip, &relaxdata->decdecomp) );
2718  relaxdata->decdecomp = NULL;
2719  }
2720 
2721  /* free array for branchrules*/
2722  if( relaxdata->nbranchrules > 0 )
2723  {
2724  int i;
2725 
2726  for( i = 0; i < relaxdata->nbranchrules; i++ )
2727  {
2728  SCIPfreeMemory(scip, &(relaxdata->branchrules[i]));
2729  }
2730  SCIPfreeMemoryArray(scip, &(relaxdata->branchrules));
2731  }
2732 
2733  relaxdata->nbranchrules = 0;
2734  relaxdata->relaxisinitialized = FALSE;
2735 
2736  return SCIP_OKAY;
2737 }
2738 
2739 
2741 static
2742 SCIP_DECL_RELAXINITSOL(relaxInitsolGcg)
2744  SCIP_RELAXDATA* relaxdata;
2745 
2746  assert(scip != NULL);
2747  assert(relax != NULL);
2748 
2749  relaxdata = SCIPrelaxGetData(relax);
2750  assert(relaxdata != NULL);
2751  assert(relaxdata->masterprob != NULL);
2752 
2753  initRelaxdata(relaxdata);
2754 
2755  /* if the master problem decomposition mode is the same as the original SCIP instance mode, then the master problem
2756  * must be swapped with the alternate master problem.
2757  */
2758  if( GCGgetMasterDecompMode(relaxdata->masterprob) != DEC_DECMODE_ORIGINAL &&
2759  GCGgetMasterDecompMode(relaxdata->masterprob) != GCGgetDecompositionMode(scip) )
2760  {
2761  SCIP* tmpscip;
2762 
2763  tmpscip = relaxdata->masterprob;
2764  relaxdata->masterprob = relaxdata->altmasterprob;
2765  relaxdata->altmasterprob = tmpscip;
2766  }
2767 
2768  /* alternative verbosity levels are used for the Benders' decomposition and original mode compared to the Dantzig-Wolfe
2769  * decomposition mode.
2770  */
2772  {
2773  /* first getting the verbosity level for the original problem before setting it to none. While the verbosity level
2774  * was collected previously, the user may have changed this in the mean time.
2775  */
2776  SCIP_CALL( SCIPgetIntParam(scip, "display/verblevel", &relaxdata->origverblevel) );
2777 
2778  /* deactivating display columns */
2779  SCIP_CALL( SCIPsetIntParam(scip, "display/sumlpiterations/active", 0) );
2780  SCIP_CALL( SCIPsetIntParam(scip, "display/lpiterations/active", 0) );
2781  SCIP_CALL( SCIPsetIntParam(scip, "display/degeneracy/active", 0) );
2782 
2783  /* setting the total node limit to 1 for the original SCIP instance. This is because Benders' decomposition solves
2784  * the MIP within the relaxator of the root node. So no branching in the original problem is required.
2785  */
2786  SCIP_CALL( SCIPsetLongintParam(scip, "limits/totalnodes", 1LL) );
2787  }
2788 
2789  /* fixing the GCG mode parameter. This ensure that the user does not change this during the solution process. If the
2790  * mode parameter were to change, the behaviour is unknown.
2791  */
2792  SCIP_CALL( SCIPfixParam(scip, "relaxing/gcg/mode") );
2793 
2794  /* Informing the user of the decomposition technique that is being used to solve the original problem */
2795  SCIPinfoMessage(scip, NULL, "\n");
2796  if( relaxdata->mode == DEC_DECMODE_DANTZIGWOLFE )
2797  {
2798  SCIPinfoMessage(scip, NULL, "A Dantzig-Wolfe reformulation is applied to solve the original problem.\n");
2799  }
2800  else if( relaxdata->mode == DEC_DECMODE_BENDERS )
2801  {
2802  SCIPinfoMessage(scip, NULL, "A Benders' decomposition is applied to solve the original problem.\n");
2803  }
2804  else if( relaxdata->mode == DEC_DECMODE_ORIGINAL )
2805  {
2806  SCIPinfoMessage(scip, NULL, "No reformulation will be performed. Solving the original model.\n");
2807  }
2808 
2809  return SCIP_OKAY;
2810 }
2811 
2812 
2814 static
2815 SCIP_DECL_RELAXEXITSOL(relaxExitsolGcg)
2817  SCIP_RELAXDATA* relaxdata;
2818  int i;
2819 
2820  assert(scip != NULL);
2821  assert(relax != NULL);
2822 
2823  relaxdata = SCIPrelaxGetData(relax);
2824  assert(relaxdata != NULL);
2825 
2826  if( relaxdata->hashorig2origvar != NULL )
2827  {
2828  SCIPhashmapFree(&(relaxdata->hashorig2origvar));
2829  relaxdata->hashorig2origvar = NULL;
2830  }
2831 
2832  SCIPfreeMemoryArrayNull(scip, &(relaxdata->markedmasterconss));
2833  relaxdata->markedmasterconss = NULL;
2834 
2835  /* free arrays for constraints */
2836  for( i = 0; i < relaxdata->nmasterconss; i++ )
2837  {
2838  SCIP_CALL( SCIPreleaseCons(scip, &relaxdata->origmasterconss[i]) );
2839  SCIP_CALL( SCIPreleaseCons(scip, &relaxdata->linearmasterconss[i]) );
2840  SCIP_CALL( SCIPreleaseCons(relaxdata->masterprob, &relaxdata->masterconss[i]) );
2841  }
2842  for( i = 0; i < relaxdata->npricingprobs; i++ )
2843  {
2844  if( relaxdata->convconss[i] != NULL )
2845  SCIP_CALL( SCIPreleaseCons(relaxdata->masterprob, &relaxdata->convconss[i]) );
2846  }
2847  for( i = 0; i < relaxdata->nvarlinkconss; i++ )
2848  {
2849  SCIP_CALL( SCIPreleaseCons(relaxdata->masterprob, &relaxdata->varlinkconss[i]) );
2850  }
2851  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->varlinkconss), relaxdata->nvarlinkconss);
2852  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->varlinkconsblock), relaxdata->nvarlinkconss);
2853  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->origmasterconss), relaxdata->maxmasterconss);
2854  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->linearmasterconss), relaxdata->maxmasterconss);
2855  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->masterconss), relaxdata->maxmasterconss);
2856  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->convconss), relaxdata->npricingprobs);
2857 
2858  /* free master problem */
2859  if( relaxdata->masterprob != NULL )
2860  {
2861  SCIP_CALL( SCIPfreeProb(relaxdata->masterprob) );
2862  }
2863 
2864  /* free pricing problems */
2865  for( i = relaxdata->npricingprobs - 1; i >= 0 ; i-- )
2866  {
2867  SCIP_CALL( SCIPfree(&(relaxdata->pricingprobs[i])) );
2868  }
2869  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->pricingprobs), relaxdata->npricingprobs);
2870  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->blockrepresentative), relaxdata->npricingprobs);
2871  SCIPfreeBlockMemoryArrayNull(scip, &(relaxdata->nblocksidentical), relaxdata->npricingprobs);
2872 
2873  /* free solutions */
2874  if( relaxdata->currentorigsol != NULL )
2875  {
2876  SCIP_CALL( SCIPfreeSol(scip, &relaxdata->currentorigsol) );
2877  }
2878  if( relaxdata->storedorigsol != NULL )
2879  {
2880  SCIP_CALL( SCIPfreeSol(scip, &relaxdata->storedorigsol) );
2881  }
2882 
2883  if( relaxdata->decdecomp != NULL )
2884  {
2885  SCIP_CALL( DECdecompFree(scip, &relaxdata->decdecomp) );
2886  relaxdata->decdecomp = NULL;
2887  }
2888 
2889  SCIP_CALL( GCGfreeOrigVarsData(scip) );
2890 
2891  relaxdata->relaxisinitialized = FALSE;
2892 
2893  return SCIP_OKAY;
2894 }
2895 
2896 
2900 static
2901 SCIP_RETCODE initializeMasterProblemSolve(
2902  SCIP* scip,
2903  SCIP_RELAX* relax
2904  )
2905 {
2906  SCIP_RELAXDATA* relaxdata;
2907  SCIP_Bool cutoff;
2908 
2909  assert(scip != NULL);
2910  assert(relax != NULL);
2911 
2912  relaxdata = SCIPrelaxGetData(relax);
2913  assert(relaxdata != NULL);
2914 
2915  /* the relaxator is initialised if it has not been previously initialised */
2916  if( !relaxdata->relaxisinitialized )
2917  {
2918  SCIP_CALL( initRelaxator(scip, relax) );
2919  SCIP_CALL( GCGconsOrigbranchAddRootCons(scip) );
2920  relaxdata->relaxisinitialized = TRUE;
2921  assert(relaxdata->decdecomp != NULL);
2922  }
2923 
2924  /* construct the LP in the original problem */
2925  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
2926  assert(!cutoff);
2927  SCIP_CALL( SCIPflushLP(scip) );
2928 
2929  return SCIP_OKAY;
2930 }
2931 
2932 
2934 static
2935 SCIP_RETCODE solveMasterProblem(
2936  SCIP* scip,
2937  SCIP* masterprob,
2938  SCIP_RELAXDATA* relaxdata,
2939  SCIP_Longint nodelimit,
2940  SCIP_Real* lowerbound,
2941  SCIP_RESULT* result
2942  )
2943 {
2944  SCIP_Real timelimit;
2945  SCIP_Real memorylimit;
2946 
2947  assert(scip != NULL);
2948  assert(masterprob != NULL);
2949  assert(relaxdata != NULL);
2950 
2951  /* update the number of the last solved node */
2952  relaxdata->lastsolvednodenr = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
2953 
2954  /* increase the node limit for the master problem by 1 */
2955  SCIP_CALL( SCIPsetLongintParam(masterprob, "limits/nodes", nodelimit) );
2956 
2957 
2958  /* loop to solve the master problem, this is a workaround and does not fix any problem */
2959  while( !SCIPisStopped(scip) )
2960  {
2961  SCIP_Real mastertimelimit = SCIPinfinity(scip);
2962 
2963  /* set memorylimit for master */
2964  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
2965  if( !SCIPisInfinity(scip, memorylimit) )
2966  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
2967 
2968  SCIP_CALL( SCIPsetRealParam(masterprob, "limits/memory", memorylimit) );
2969 
2970  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2971  if( !SCIPisInfinity(scip, timelimit) )
2972  {
2973 
2974  /* give the master 2% more time then the original scip has left */
2975  mastertimelimit = (timelimit - SCIPgetSolvingTime(scip)) * 1.02 + SCIPgetSolvingTime(masterprob);
2976  SCIP_CALL( SCIPsetRealParam(masterprob, "limits/time", mastertimelimit) );
2977 
2978  SCIPdebugMessage(" time limit for master: %f, left: %f, left for original problem: %f\n",
2979  mastertimelimit,
2980  mastertimelimit - SCIPgetSolvingTime(masterprob),
2981  timelimit - SCIPgetSolvingTime(scip));
2982  }
2983 
2984  /* if we have a blockdetection, see whether the node is block diagonal. Additionally, the solveDiagonalBlocks can
2985  * be called when the original problem is solved directly.
2986  */
2988  {
2989  SCIP_CALL( solveDiagonalBlocks(scip, relaxdata, result, lowerbound) );
2990  if( *result == SCIP_SUCCESS || *result == SCIP_CUTOFF )
2991  {
2992  *result = SCIP_CUTOFF;
2993  return SCIP_OKAY;
2994  }
2995  }
2996  /* We are solving the masterproblem regularly */
2997  else
2998  {
2999  SCIP_CALL( SCIPsolve(masterprob) );
3000  }
3001 
3002 
3003  if( SCIPgetStatus(masterprob) != SCIP_STATUS_TIMELIMIT )
3004  {
3005  break;
3006  }
3007 
3008  if( !SCIPisInfinity(scip, timelimit) && !SCIPisStopped(scip) )
3009  SCIPinfoMessage(scip, NULL, "time for master problem was too short, extending time by %f.\n", mastertimelimit - SCIPgetSolvingTime(masterprob));
3010  }
3011  if( SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT && SCIPisStopped(scip) )
3012  {
3013  *result = SCIP_DIDNOTRUN;
3014  return SCIP_OKAY;
3015  }
3016 
3017  /* set the lower bound pointer */
3018  if( SCIPgetStage(masterprob) == SCIP_STAGE_SOLVING && GCGmasterIsCurrentSolValid(masterprob) )
3019  {
3020  *lowerbound = SCIPgetLocalDualbound(masterprob);
3021  }
3022  else
3023  {
3024  SCIPdebugMessage(" stage: %d\n", SCIPgetStage(masterprob));
3025  assert(SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || SCIPgetBestSol(masterprob) != NULL || SCIPgetStatus(masterprob) == SCIP_STATUS_INFEASIBLE || SCIPgetStatus(masterprob) == SCIP_STATUS_UNKNOWN);
3026  if( SCIPgetStatus(masterprob) == SCIP_STATUS_OPTIMAL && GCGmasterIsCurrentSolValid(masterprob) )
3027  *lowerbound = SCIPgetSolOrigObj(masterprob, SCIPgetBestSol(masterprob));
3028  else if( SCIPgetStatus(masterprob) == SCIP_STATUS_INFEASIBLE || SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || !GCGmasterIsCurrentSolValid(masterprob) )
3029  {
3030  SCIP_Real tilim;
3031  SCIP_CALL( SCIPgetRealParam(masterprob, "limits/time", &tilim) );
3032  if( tilim-SCIPgetSolvingTime(masterprob) < 0 )
3033  {
3034  *result = SCIP_DIDNOTRUN;
3035  return SCIP_OKAY;
3036  }
3037  *lowerbound = SCIPinfinity(scip);
3038  }
3039  else if( SCIPgetStatus(masterprob) == SCIP_STATUS_UNKNOWN )
3040  {
3041  *result = SCIP_DIDNOTRUN;
3042  return SCIP_OKAY;
3043  }
3044  else
3045  {
3046  SCIPwarningMessage(scip, "Stage <%d> is not handled!\n", SCIPgetStage(masterprob));
3047  *result = SCIP_DIDNOTRUN;
3048  return SCIP_OKAY;
3049  }
3050  }
3051 
3052  SCIPdebugMessage(" update lower bound (value = %g).\n", *lowerbound);
3053 
3054  /* NOTE: All other points when result is set, the function is exited immediately. Ensure that this is checked for
3055  * future changes to this function
3056  */
3057  *result = SCIP_SUCCESS;
3058 
3059  return SCIP_OKAY;
3060 }
3061 
3062 
3063 
3064 
3066 static
3067 SCIP_RETCODE relaxExecGcgDantzigWolfe(
3068  SCIP* scip,
3069  SCIP_RELAX* relax,
3070  SCIP_Real* lowerbound,
3071  SCIP_RESULT* result
3072  )
3073 {
3074  SCIP* masterprob;
3075  SCIP_RELAXDATA* relaxdata;
3076  SCIP_Longint oldnnodes;
3077  SCIP_Longint nodelimit;
3078  SCIP_Bool stored;
3079 
3080  assert(scip != NULL);
3081  assert(relax != NULL);
3082  assert(result != NULL);
3084 
3085  relaxdata = SCIPrelaxGetData(relax);
3086  assert(relaxdata != NULL);
3087  *result = SCIP_DIDNOTRUN;
3088 
3089  masterprob = relaxdata->masterprob;
3090  assert(masterprob != NULL);
3091 
3092  /* solve the next node in the master problem */
3093  SCIPdebugMessage("Solving node %"SCIP_LONGINT_FORMAT"'s relaxation.\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
3094 
3095  /* only solve the relaxation if it was not yet solved at the current node */
3096  if( SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) != relaxdata->lastsolvednodenr )
3097  {
3098  /* increase the node limit for the master problem by 1 */
3099  SCIP_CALL( SCIPgetLongintParam(masterprob, "limits/nodes", &oldnnodes) );
3100 
3101  nodelimit = (SCIPgetRootNode(scip) == SCIPgetCurrentNode(scip) ? 1 : oldnnodes + 1);
3102  /* solving the master problem */
3103  SCIP_CALL( solveMasterProblem(scip, masterprob, relaxdata, nodelimit, lowerbound, result) );
3104 
3105  if( relaxdata->currentorigsol != NULL )
3106  {
3107  SCIP_CALL( SCIPtrySol(scip, relaxdata->currentorigsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
3108  }
3109 
3110  /* if a new primal solution was found in the master problem, transfer it to the original problem */
3111  if( SCIPgetBestSol(relaxdata->masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(relaxdata->masterprob) && GCGmasterIsCurrentSolValid(masterprob) )
3112  {
3113  SCIP_SOL* newsol;
3114 
3115  relaxdata->lastmastersol = SCIPgetBestSol(relaxdata->masterprob);
3116 
3117  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, relaxdata->lastmastersol, &newsol) );
3118  #ifdef SCIP_DEBUG
3119  SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
3120  #else
3121  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
3122  #endif
3123  /* only check failed solution if best master solution is valid */
3124  if( !stored && GCGmasterIsBestsolValid(relaxdata->masterprob) )
3125  {
3126  SCIP_CALL( SCIPcheckSolOrig(scip, newsol, &stored, TRUE, TRUE) );
3127  }
3131  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
3132 
3133  if( stored )
3134  SCIPdebugMessage(" updated current best primal feasible solution.\n");
3135  }
3136 
3138  {
3141  }
3142  }
3143  else
3144  {
3145  SCIPdebugMessage("Problem has been already solved at this node\n");
3146  }
3147 
3148  return SCIP_OKAY;
3149 }
3150 
3152 static
3153 SCIP_RETCODE solveMasterProblemAndEvaluate(
3154  SCIP* scip,
3155  SCIP_RELAX* relax,
3156  SCIP_Real* lowerbound,
3157  SCIP_RESULT* result
3158  )
3159 {
3160  SCIP* masterprob;
3161  SCIP_RELAXDATA* relaxdata;
3162  SCIP_Longint nodelimit;
3163 
3164  assert(scip != NULL);
3165  assert(relax != NULL);
3166  assert(result != NULL);
3167 
3168  relaxdata = SCIPrelaxGetData(relax);
3169  assert(relaxdata != NULL);
3170  *result = SCIP_DIDNOTRUN;
3171 
3172  masterprob = relaxdata->masterprob;
3173  assert(masterprob != NULL);
3174 
3175  /* solve the next node in the master problem */
3176  SCIPdebugMessage("Solving node %"SCIP_LONGINT_FORMAT"'s relaxation.\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
3177 
3178  /* prior to performing the decomposition the original problem verbosity is changed to NONE. This avoids output from
3179  * the original problem before the decomposition output. Once the decomposition has been performed, then the
3180  * verbosity level of the original problem is returned to the original verbosity level.
3181  */
3182  SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", relaxdata->origverblevel) );
3183  SCIP_CALL( SCIPsetIntParam(masterprob, "display/verblevel", relaxdata->origverblevel) );
3184 
3185  /* getting the node limit from the original problem. This is because the master problem is solved to optimality in
3186  * the execution of the relaxator.
3187  */
3188  SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) );
3189 
3190  /* solving the master problem */
3191  SCIP_CALL( solveMasterProblem(scip, masterprob, relaxdata, nodelimit, lowerbound, result) );
3192 
3193  /* if the master problem has been detected as infeasible, then the result must be set to SCIP_CUTOFF. */
3194  if( SCIPgetStatus(masterprob) == SCIP_STATUS_INFEASIBLE )
3195  (*result) = SCIP_CUTOFF;
3196 
3197  /* if the master problem has been solved to optimality, the we cutoff the root node. This informs that original
3198  * problem that no further processing is required.
3199  */
3200  if( SCIPgetStatus(masterprob) == SCIP_STATUS_OPTIMAL )
3201  {
3202  (*result) = SCIP_CUTOFF;
3203  }
3204 
3205  /* if there is no primal solution for the original problem, then the master solution is transferred */
3206  if( SCIPgetBestSol(relaxdata->masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(relaxdata->masterprob) )
3207  {
3208  SCIP_SOL* newsol;
3209  SCIP_Bool stored;
3210 
3211  relaxdata->lastmastersol = SCIPgetBestSol(relaxdata->masterprob);
3212 
3213  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, SCIPgetBestSol(relaxdata->masterprob), &newsol) );
3214 #ifdef SCIP_DEBUG
3215  SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
3216 #else
3217  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
3218 #endif
3219  /* only check failed solution if best master solution is valid */
3220  if( !stored && GCGmasterIsBestsolValid(relaxdata->masterprob) )
3221  {
3222  SCIP_CALL( SCIPcheckSolOrig(scip, newsol, &stored, TRUE, TRUE) );
3223  }
3227  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
3228 
3229  if( stored )
3230  SCIPdebugMessage(" updated current best primal feasible solution.\n");
3231  }
3232 
3233  /* set the lower bound pointer */
3235  && (SCIPgetStage(masterprob) == SCIP_STAGE_SOLVED || SCIPgetStage(masterprob) == SCIP_STAGE_SOLVING) )
3236  {
3237  *lowerbound = SCIPgetDualbound(masterprob);
3238  }
3239 
3240  /* if the time, memory or node limit is hit in the Original or Benders mode, then we need to interrupt the solve.
3241  * This is required because the original problem is not solved in either of these modes, so it is not certain that
3242  * the original SCIP will also exceed the limit (definitely not for the node limit).
3243  */
3244  if( SCIPgetStatus(masterprob) == SCIP_STATUS_TIMELIMIT || SCIPgetStatus(masterprob) == SCIP_STATUS_NODELIMIT
3245  || SCIPgetStatus(masterprob) == SCIP_STATUS_MEMLIMIT )
3246  {
3247  SCIP_CALL( SCIPinterruptSolve(scip) );
3248  }
3249 
3250  /* if the result pointer is DIDNOTRUN, this implies that the master problem was interrupted during solving. Since
3251  * Benders' decomposition uses a one-tree approach, then the user limits must be adhered to. This means, the if a
3252  * limit is exceeded, this is still a success for the solving.
3253  */
3254  if( (*result) == SCIP_DIDNOTRUN )
3255  (*result) = SCIP_SUCCESS;
3256 
3257  return SCIP_OKAY;
3258 }
3259 
3261 static
3263  SCIP* scip,
3264  SCIP_RELAX* relax,
3265  SCIP_Real* lowerbound,
3266  SCIP_RESULT* result
3267  )
3268 {
3269  assert(scip != NULL);
3270  assert(relax != NULL);
3271  assert(result != NULL);
3272 
3273  SCIP_CALL( solveMasterProblemAndEvaluate(scip, relax, lowerbound, result) );
3274 
3275  return SCIP_OKAY;
3276 }
3277 
3279 static
3280 SCIP_RETCODE relaxExecGcgOriginalProblem(
3281  SCIP* scip,
3282  SCIP_RELAX* relax,
3283  SCIP_Real* lowerbound,
3284  SCIP_RESULT* result
3285  )
3286 {
3287  assert(scip != NULL);
3288  assert(relax != NULL);
3289  assert(result != NULL);
3290 
3291  SCIP_CALL( solveMasterProblemAndEvaluate(scip, relax, lowerbound, result) );
3292 
3293  return SCIP_OKAY;
3294 }
3295 
3296 
3298 static
3299 SCIP_DECL_RELAXEXEC(relaxExecGcg)
3301  SCIP_RELAXDATA* relaxdata;
3302 
3303  assert(scip != NULL);
3304  assert(relax != NULL);
3305  assert(result != NULL);
3306 
3307  relaxdata = SCIPrelaxGetData(relax);
3308  assert(relaxdata != NULL);
3309 
3310  /* checking whether the relaxator needs to be initialised. If so, then the master problem and pricing problems will
3311  * be created.
3312  */
3313  SCIP_CALL( initializeMasterProblemSolve(scip, relax) );
3314 
3315  /* selecting the solving algorithm based upon the decomposition mode selected by the user, or whether the original
3316  * problem should be solved directly
3317  */
3319  {
3320  SCIPinfoMessage(scip, NULL, "There are no pricing problems in the decomposition. The original problem will be solved directly.\n");
3321  SCIP_CALL( relaxExecGcgOriginalProblem(scip, relax, lowerbound, result) );
3322  }
3323  else if( relaxdata->mode == DEC_DECMODE_DANTZIGWOLFE )
3324  {
3325  SCIP_CALL( relaxExecGcgDantzigWolfe(scip, relax, lowerbound, result) );
3326  }
3327  else if( relaxdata->mode == DEC_DECMODE_BENDERS )
3328  {
3329  SCIP_CALL( relaxExecGcgBendersDecomposition(scip, relax, lowerbound, result) );
3330  }
3331  else
3332  {
3333  SCIPinfoMessage(scip, NULL, "Sorry, the automatic selection is not currently available\n");
3334  }
3335 
3336  return SCIP_OKAY;
3337 }
3338 
3339 #define relaxCopyGcg NULL
3340 #define relaxInitGcg NULL
3342 
3343 /*
3344  * relaxator specific interface methods
3345  */
3346 
3348 SCIP_RETCODE SCIPincludeRelaxGcg(
3349  SCIP* scip
3350  )
3351 {
3352  SCIP_RELAXDATA* relaxdata;
3353 
3354 #ifdef WITH_BLISS
3355  {
3356  char name[SCIP_MAXSTRLEN];
3357  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "bliss %s", GCGgetBlissVersion());
3358  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name, "A Tool for Computing Automorphism Groups of Graphs by T. Junttila and P. Kaski (http://www.tcs.hut.fi/Software/bliss/)") );
3359  }
3360 #endif
3361 
3362 #ifdef WITH_CLIQUER
3363  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, "Cliquer", "A set of C routines for finding cliques in an arbitrary weighted graph by S. Niskanen and P. Ostergard (https://users.aalto.fi/~pat/cliquer.html)") );
3364 #endif
3365 
3366  /* create GCG relaxator data */
3367  SCIP_CALL( SCIPallocMemory(scip, &relaxdata) );
3368 
3369  relaxdata->decdecomp = NULL;
3370  relaxdata->nbranchrules = 0;
3371  relaxdata->branchrules = NULL;
3372  relaxdata->masterprob = NULL;
3373  relaxdata->altmasterprob = NULL;
3374 
3375  initRelaxdata(relaxdata);
3376 
3377  /* include relaxator */
3378  SCIP_CALL( SCIPincludeRelax(scip, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ, relaxCopyGcg, relaxFreeGcg, relaxInitGcg,
3379  relaxExitGcg, relaxInitsolGcg, relaxExitsolGcg, relaxExecGcg, relaxdata) );
3380 
3381  /* inform the main scip, that no LPs should be solved */
3382  SCIP_CALL( SCIPsetIntParam(scip, "lp/solvefreq", 0) );
3383 
3384  /* Disable restarts */
3385  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
3386  SCIP_CALL( SCIPsetBoolParam(scip, "misc/calcintegral", FALSE) );
3387 
3388  /* initialize the scip data structure for the master problem. The master problem is initialized as the Dantzig-Wolfe
3389  * master problem. The alternate master problem is initialized as the Benders' decomposition master problem.
3390  */
3391  SCIP_CALL( SCIPcreate(&(relaxdata->masterprob)) );
3392  SCIP_CALL( SCIPincludePricerGcg(relaxdata->masterprob, scip) );
3393  SCIP_CALL( GCGincludeMasterPlugins(relaxdata->masterprob) );
3394  SCIP_CALL( SCIPsetMessagehdlr(relaxdata->masterprob, SCIPgetMessagehdlr(scip)) );
3395 
3396  /* getting the verbosity level of the original problem */
3397  SCIP_CALL( SCIPgetIntParam(scip, "display/verblevel", &relaxdata->origverblevel) );
3398 
3399  /* disable display output in the master problem */
3400  SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3401 
3402  /* set parameters in master problem */
3403  SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "pricing/maxvars", INT_MAX) );
3404  SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "pricing/maxvarsroot", INT_MAX) );
3405  SCIP_CALL( SCIPsetRealParam(relaxdata->masterprob, "pricing/abortfac", 1.0) );
3406  SCIP_CALL( SCIPsetIntParam(relaxdata->masterprob, "lp/disablecutoff", 1) );
3407 #ifdef DELVARS
3408  /* set paramteters to allow deletion of variables */
3409  SCIP_CALL( SCIPsetBoolParam(relaxdata->masterprob, "pricing/delvars", TRUE) );
3410  SCIP_CALL( SCIPsetBoolParam(relaxdata->masterprob, "pricing/delvarsroot", TRUE) );
3411  SCIP_CALL( SCIPsetBoolParam(relaxdata->masterprob, "lp/cleanupcols", TRUE) );
3412  SCIP_CALL( SCIPsetBoolParam(relaxdata->masterprob, "lp/cleanupcolsroot", TRUE) );
3413 #endif
3414 
3415  /* initializing the alternate master problem. The alternate master problem is initially the Benders' decomposition
3416  * master problem
3417  */
3418  SCIP_CALL( SCIPcreate(&(relaxdata->altmasterprob)) );
3419  SCIP_CALL( SCIPincludeBendersGcg(relaxdata->altmasterprob, scip) );
3420  SCIP_CALL( GCGincludeBendersPlugins(relaxdata->altmasterprob) );
3421  SCIP_CALL( SCIPsetMessagehdlr(relaxdata->altmasterprob, SCIPgetMessagehdlr(scip)) );
3422 
3423  SCIP_CALL( SCIPsetIntParam(relaxdata->altmasterprob, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
3424  SCIP_CALL( SCIPsetBoolParam(relaxdata->altmasterprob, "display/relevantstats", FALSE) );
3425 
3426  /* add GCG relaxator parameters */
3427  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/gcg/discretization",
3428  "should discretization (TRUE) or convexification (FALSE) approach be used?",
3429  &(relaxdata->discretization), FALSE, DEFAULT_DISCRETIZATION, NULL, NULL) );
3430  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/gcg/aggregation",
3431  "should identical blocks be aggregated (only for discretization approach)?",
3432  &(relaxdata->aggregation), FALSE, DEFAULT_AGGREGATION, NULL, NULL) );
3433  SCIP_CALL( SCIPaddBoolParam(scip, "relaxing/gcg/dispinfos",
3434  "should additional information about the blocks be displayed?",
3435  &(relaxdata->dispinfos), FALSE, DEFAULT_DISPINFOS, NULL, NULL) );
3436  SCIP_CALL( SCIPaddIntParam(scip, "relaxing/gcg/mode",
3437  "the decomposition mode that GCG will use. (0: Dantzig-Wolfe (default), 1: Benders' decomposition, "
3438  "2: no decomposition will be performed)",
3439  (int*)&(relaxdata->mode), FALSE, (int)DEFAULT_MODE, 0, 2, NULL, NULL) );
3440 
3441  return SCIP_OKAY;
3442 }
3443 
3444 
3445 /*
3446  * relaxator specific interface methods for coordination of branching rules
3447  */
3448 
3450 SCIP_RETCODE GCGrelaxIncludeBranchrule(
3451  SCIP* scip,
3452  SCIP_BRANCHRULE* branchrule,
3453  GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)),
3454  GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)),
3455  GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)),
3456  GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)),
3457  GCG_DECL_BRANCHDATADELETE((*branchdatadelete))
3458  )
3459 {
3460  SCIP_RELAX* relax;
3461  SCIP_RELAXDATA* relaxdata;
3462  int pos;
3463 
3464  assert(scip != NULL);
3465  assert(branchrule != NULL);
3466 
3467  relax = SCIPfindRelax(scip, RELAX_NAME);
3468  assert(relax != NULL);
3469 
3470  relaxdata = SCIPrelaxGetData(relax);
3471  assert(relaxdata != NULL);
3472 
3473  SCIP_CALL( ensureSizeBranchrules(scip, relaxdata) );
3474 
3475  pos = relaxdata->nbranchrules;
3476 
3477  /* store callback functions */
3478  SCIP_CALL( SCIPallocMemory(scip, &(relaxdata->branchrules[pos])) ); /*lint !e866*/
3479  relaxdata->branchrules[pos]->branchrule = branchrule;
3480  relaxdata->branchrules[pos]->branchactivemaster = branchactivemaster;
3481  relaxdata->branchrules[pos]->branchdeactivemaster = branchdeactivemaster;
3482  relaxdata->branchrules[pos]->branchpropmaster = branchpropmaster;
3483  relaxdata->branchrules[pos]->branchmastersolved = branchmastersolved;
3484  relaxdata->branchrules[pos]->branchdatadelete = branchdatadelete;
3485  relaxdata->nbranchrules++;
3486 
3487  return SCIP_OKAY;
3488 }
3489 
3491 SCIP_RETCODE GCGrelaxBranchActiveMaster(
3492  SCIP* scip,
3493  SCIP_BRANCHRULE* branchrule,
3494  GCG_BRANCHDATA* branchdata
3495  )
3496 {
3497  SCIP_RELAX* relax;
3498  SCIP_RELAXDATA* relaxdata;
3499  int i;
3500 
3501  assert(scip != NULL);
3502  assert(branchrule != NULL);
3503 
3504  relax = SCIPfindRelax(scip, RELAX_NAME);
3505  assert(relax != NULL);
3506 
3507  relaxdata = SCIPrelaxGetData(relax);
3508  assert(relaxdata != NULL);
3509 
3510  /* search for the branching rule in the branchrules array */
3511  for( i = 0; i < relaxdata->nbranchrules; i++ )
3512  {
3513  if( branchrule == relaxdata->branchrules[i]->branchrule )
3514  {
3515  /* call activation method of branching rule */
3516  if( relaxdata->branchrules[i]->branchactivemaster != NULL )
3517  SCIP_CALL( relaxdata->branchrules[i]->branchactivemaster(relaxdata->masterprob, branchdata) );
3518 
3519  break;
3520  }
3521  }
3522 
3523  assert(i < relaxdata->nbranchrules);
3524 
3525  return SCIP_OKAY;
3526 }
3527 
3529 SCIP_RETCODE GCGrelaxBranchDeactiveMaster(
3530  SCIP* scip,
3531  SCIP_BRANCHRULE* branchrule,
3532  GCG_BRANCHDATA* branchdata
3533  )
3534 {
3535  SCIP_RELAX* relax;
3536  SCIP_RELAXDATA* relaxdata;
3537  int i;
3538 
3539  assert(scip != NULL);
3540  assert(branchrule != NULL);
3541 
3542  relax = SCIPfindRelax(scip, RELAX_NAME);
3543  assert(relax != NULL);
3544 
3545  relaxdata = SCIPrelaxGetData(relax);
3546  assert(relaxdata != NULL);
3547 
3548  /* search for the branching rule in the branchrules array */
3549  for( i = 0; i < relaxdata->nbranchrules; i++ )
3550  {
3551  if( branchrule == relaxdata->branchrules[i]->branchrule )
3552  {
3553  /* call deactivation method of branching rule */
3554  if( relaxdata->branchrules[i]->branchdeactivemaster != NULL )
3555  SCIP_CALL( relaxdata->branchrules[i]->branchdeactivemaster(relaxdata->masterprob, branchdata) );
3556 
3557  break;
3558  }
3559  }
3560 
3561  assert(i < relaxdata->nbranchrules);
3562 
3563  return SCIP_OKAY;
3564 }
3565 
3567 SCIP_RETCODE GCGrelaxBranchPropMaster(
3568  SCIP* scip,
3569  SCIP_BRANCHRULE* branchrule,
3570  GCG_BRANCHDATA* branchdata,
3571  SCIP_RESULT* result
3572  )
3573 {
3574  SCIP_RELAX* relax;
3575  SCIP_RELAXDATA* relaxdata;
3576  int i;
3577 
3578  assert(scip != NULL);
3579  assert(branchrule != NULL);
3580  assert(result != NULL);
3581 
3582  relax = SCIPfindRelax(scip, RELAX_NAME);
3583  assert(relax != NULL);
3584 
3585  relaxdata = SCIPrelaxGetData(relax);
3586  assert(relaxdata != NULL);
3587 
3588  *result = SCIP_DIDNOTRUN;
3589 
3590  /* search for the branching rule in the branchrules array */
3591  for( i = 0; i < relaxdata->nbranchrules; i++ )
3592  {
3593  if( branchrule == relaxdata->branchrules[i]->branchrule )
3594  {
3595  /* call propagation method of branching rule*/
3596  if( relaxdata->branchrules[i]->branchpropmaster != NULL )
3597  SCIP_CALL( relaxdata->branchrules[i]->branchpropmaster(relaxdata->masterprob, branchdata, result) );
3598 
3599  break;
3600  }
3601  }
3602 
3603  assert(i < relaxdata->nbranchrules);
3604 
3605  return SCIP_OKAY;
3606 }
3607 
3609 SCIP_RETCODE GCGrelaxBranchDataDelete(
3610  SCIP* scip,
3611  SCIP_BRANCHRULE* branchrule,
3612  GCG_BRANCHDATA** branchdata
3613  )
3614 {
3615  SCIP_RELAX* relax;
3616  SCIP_RELAXDATA* relaxdata;
3617  int i;
3618 
3619  assert(scip != NULL);
3620  assert(branchrule != NULL);
3621  assert(branchdata != NULL);
3622 
3623  relax = SCIPfindRelax(scip, RELAX_NAME);
3624  assert(relax != NULL);
3625 
3626  relaxdata = SCIPrelaxGetData(relax);
3627  assert(relaxdata != NULL);
3628 
3629  /* search for the branching rule in the branchrules array */
3630  for( i = 0; i < relaxdata->nbranchrules; i++ )
3631  {
3632  if( branchrule == relaxdata->branchrules[i]->branchrule )
3633  {
3634  /* call branchrule data deletion method of the branching rule */
3635  if( relaxdata->branchrules[i]->branchdatadelete != NULL )
3636  SCIP_CALL( relaxdata->branchrules[i]->branchdatadelete(scip, branchdata) );
3637  else
3638  {
3639  if( *branchdata != NULL )
3640  {
3641  SCIPfreeMemory(GCGgetMasterprob(scip), branchdata);
3642  }
3643  }
3644  break;
3645  }
3646  }
3647 
3648  assert(i < relaxdata->nbranchrules);
3649 
3650  return SCIP_OKAY;
3651 }
3652 
3654 SCIP_RETCODE GCGrelaxBranchMasterSolved(
3655  SCIP* scip,
3656  SCIP_BRANCHRULE* branchrule,
3657  GCG_BRANCHDATA* branchdata,
3658  SCIP_Real newlowerbound
3659  )
3660 {
3661  SCIP_RELAX* relax;
3662  SCIP_RELAXDATA* relaxdata;
3663  int i;
3664 
3665  assert(scip != NULL);
3666  assert(branchrule != NULL);
3667 
3668  relax = SCIPfindRelax(scip, RELAX_NAME);
3669  assert(relax != NULL);
3670 
3671  relaxdata = SCIPrelaxGetData(relax);
3672  assert(relaxdata != NULL);
3673 
3674  /* search for the branching rule in the branchrules array */
3675  for( i = 0; i < relaxdata->nbranchrules; i++ )
3676  {
3677  if( branchrule == relaxdata->branchrules[i]->branchrule )
3678  {
3679  /* call master problem solved method of the branching rule */
3680  if( relaxdata->branchrules[i]->branchmastersolved != NULL )
3681  SCIP_CALL( relaxdata->branchrules[i]->branchmastersolved(scip, branchdata, newlowerbound) );
3682 
3683  break;
3684  }
3685  }
3686 
3687  assert(i < relaxdata->nbranchrules);
3688 
3689  return SCIP_OKAY;
3690 }
3691 
3694 SCIP_RETCODE GCGrelaxTransOrigToMasterCons(
3695  SCIP* scip,
3696  SCIP_CONS* cons,
3697  SCIP_CONS** transcons
3698  )
3699 {
3700 
3701  SCIP_RELAX* relax;
3702  SCIP_RELAXDATA* relaxdata;
3703  SCIP_CONS* newcons;
3704  SCIP_CONS* mastercons;
3705  char name[SCIP_MAXSTRLEN];
3706 
3707  SCIP_VAR** mastervars;
3708  int nmastervars;
3709  SCIP_VAR** consvars;
3710  SCIP_Real* consvals;
3711  int nconsvars;
3712  int v;
3713  int i;
3714  int j;
3715 
3716  SCIP_Bool success;
3717 
3718  assert(scip != NULL);
3719  assert(cons != NULL);
3720 
3721  relax = SCIPfindRelax(scip, RELAX_NAME);
3722  assert(relax != NULL);
3723 
3724  relaxdata = SCIPrelaxGetData(relax);
3725  assert(relaxdata != NULL);
3726 
3727  newcons = NULL;
3728 
3729  /* copy the constraint (dirty trick, we only need lhs and rhs, because variables are added later) */
3730  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear_%s", SCIPconsGetName(cons));
3731  SCIP_CALL( SCIPgetConsCopy(scip, scip, cons, &newcons, SCIPconsGetHdlr(cons),
3732  relaxdata->hashorig2origvar, NULL, name,
3733  FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, &success) );
3734 
3735  assert(success && newcons != NULL);
3736 
3737  /* create and add corresponding linear constraint in the master problem */
3738  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "m_%s", SCIPconsGetName(cons));
3739  SCIP_CALL( SCIPcreateConsLinear(relaxdata->masterprob, &mastercons, name, 0, NULL, NULL,
3740  SCIPgetLhsLinear(scip, newcons), SCIPgetRhsLinear(scip, newcons),
3741  TRUE, TRUE, TRUE, TRUE, TRUE, SCIPconsIsLocal(cons), TRUE, FALSE, FALSE,
3742  SCIPconsIsStickingAtNode(cons)) );
3743 
3744  /* now compute coefficients of the master variables in the master constraint */
3745  mastervars = SCIPgetVars(relaxdata->masterprob);
3746  nmastervars = SCIPgetNVars(relaxdata->masterprob);
3747 
3748  consvars = SCIPgetVarsLinear(scip, cons);
3749  nconsvars = SCIPgetNVarsLinear(scip, cons);
3750  consvals = SCIPgetValsLinear(scip, cons);
3751 
3752 
3753  /* add coefs of the original variables in the constraint to their variable data */
3754  for( v = 0; v < nconsvars; v++ )
3755  {
3756  SCIP_CALL( GCGoriginalVarAddCoef(scip, consvars[v], consvals[v], mastercons) );
3757  }
3758 
3759  /* add master variables to the corresponding master constraint */
3760  for( v = 0; v < nmastervars; v++ )
3761  {
3762  SCIP_VAR** origvars;
3763  SCIP_Real* origvals;
3764  int norigvars;
3765  SCIP_Real coef = 0.0;
3766 
3767  origvars = GCGmasterVarGetOrigvars(mastervars[v]);
3768  norigvars = GCGmasterVarGetNOrigvars(mastervars[v]);
3769  origvals = GCGmasterVarGetOrigvals(mastervars[v]);
3770 
3771  for( i = 0; i < norigvars; i++ )
3772  for( j = 0; j < nconsvars; j++ )
3773  if( consvars[j] == origvars[i] )
3774  coef += consvals[j] * origvals[i];
3775 
3776  if( !SCIPisFeasZero(scip, coef) )
3777  {
3778  SCIP_CALL( SCIPaddCoefLinear(relaxdata->masterprob, mastercons, mastervars[v], coef) );
3779  }
3780  }
3781 
3782  /* store the constraints in the arrays origmasterconss and masterconss in the problem data */
3783  SCIP_CALL( ensureSizeMasterConss(scip, relaxdata, relaxdata->nmasterconss+1) );
3784  SCIP_CALL( SCIPcaptureCons(scip, cons) );
3785  relaxdata->origmasterconss[relaxdata->nmasterconss] = cons;
3786  relaxdata->linearmasterconss[relaxdata->nmasterconss] = newcons;
3787  relaxdata->masterconss[relaxdata->nmasterconss] = mastercons;
3788 
3789  SCIP_CALL( GCGmasterAddMasterconsToHashmap(relaxdata->masterprob, relaxdata->masterconss[relaxdata->nmasterconss],
3790  relaxdata->nmasterconss) );
3791 
3792  relaxdata->nmasterconss++;
3793 
3794  *transcons = mastercons;
3795 
3796  return SCIP_OKAY;
3797 }
3798 
3800 SCIP* GCGgetOriginalprob(
3801  SCIP* masterprob
3802  )
3803 {
3804  SCIP* origprob;
3805  SCIP_BENDERS* benders;
3806  SCIP_PRICER* pricer;
3807 
3808  assert(masterprob != NULL);
3809 
3810  /* retrieving the Benders' decomposition and the pricer plugins. There should only be one or the other for a given
3811  * master problem. If there are both, then an error is returned */
3812  benders = SCIPfindBenders(masterprob, "gcg");
3813  pricer = SCIPfindPricer(masterprob, "gcg");
3814  assert((benders != NULL && pricer == NULL) || (pricer != NULL && benders == NULL));
3815 
3816  origprob = NULL;
3817  if( benders != NULL && pricer == NULL )
3818  {
3819  origprob = GCGbendersGetOrigprob(masterprob);
3820  assert(GCGgetDecompositionMode(origprob) == DEC_DECMODE_BENDERS
3822  }
3823  else if( pricer != NULL && benders == NULL )
3824  {
3825  origprob = GCGmasterGetOrigprob(masterprob);
3827  }
3828  else
3829  {
3830  SCIPerrorMessage("There must exist either a pricer or a benders or neither, not both.\n");
3831  }
3832 
3833  return origprob;
3834 }
3835 
3837 SCIP* GCGgetMasterprob(
3838  SCIP* scip
3839  )
3840 {
3841  SCIP_RELAX* relax;
3842  SCIP_RELAXDATA* relaxdata;
3843 
3844  assert(scip != NULL);
3845 
3846  relax = SCIPfindRelax(scip, RELAX_NAME);
3847  assert(relax != NULL);
3848 
3849  relaxdata = SCIPrelaxGetData(relax);
3850  assert(relaxdata != NULL);
3851 
3852  return relaxdata->masterprob;
3853 }
3854 
3856 SCIP* GCGgetPricingprob(
3857  SCIP* scip,
3858  int pricingprobnr
3859  )
3860 {
3861  SCIP_RELAX* relax;
3862  SCIP_RELAXDATA* relaxdata;
3863 
3864  assert(scip != NULL);
3865 
3866  relax = SCIPfindRelax(scip, RELAX_NAME);
3867  assert(relax != NULL);
3868 
3869  relaxdata = SCIPrelaxGetData(relax);
3870  assert(relaxdata != NULL);
3871 
3872  return relaxdata->pricingprobs[pricingprobnr];
3873 }
3874 
3877  SCIP* scip
3878  )
3879 {
3880  SCIP_RELAX* relax;
3881  SCIP_RELAXDATA* relaxdata;
3882 
3883  assert(scip != NULL);
3884 
3885  relax = SCIPfindRelax(scip, RELAX_NAME);
3886  assert(relax != NULL);
3887 
3888  relaxdata = SCIPrelaxGetData(relax);
3889  assert(relaxdata != NULL);
3890 
3891  assert(relaxdata->nrelpricingprobs >= -1);
3892  return relaxdata->nrelpricingprobs;
3893 }
3894 
3897  SCIP* scip
3898  )
3899 {
3900  SCIP_RELAX* relax;
3901  SCIP_RELAXDATA* relaxdata;
3902 
3903  assert(scip != NULL);
3904 
3905  relax = SCIPfindRelax(scip, RELAX_NAME);
3906  assert(relax != NULL);
3907 
3908  relaxdata = SCIPrelaxGetData(relax);
3909  assert(relaxdata != NULL);
3910 
3911  assert(relaxdata->npricingprobs >= -1);
3912  return relaxdata->npricingprobs;
3913 }
3914 
3917 SCIP_Bool GCGisPricingprobRelevant(
3918  SCIP* scip,
3919  int pricingprobnr
3920  )
3921 {
3922  SCIP_RELAX* relax;
3923  SCIP_RELAXDATA* relaxdata;
3924 
3925  assert(scip != NULL);
3926 
3927  relax = SCIPfindRelax(scip, RELAX_NAME);
3928  assert(relax != NULL);
3929 
3930  relaxdata = SCIPrelaxGetData(relax);
3931  assert(relaxdata != NULL);
3932 
3933  return (relaxdata->blockrepresentative[pricingprobnr] == pricingprobnr);
3934 
3935 }
3936 
3941  SCIP* scip,
3942  int pricingprobnr
3943  )
3944 {
3945  SCIP_RELAX* relax;
3946  SCIP_RELAXDATA* relaxdata;
3947 
3948  assert(scip != NULL);
3949 
3950  relax = SCIPfindRelax(scip, RELAX_NAME);
3951  assert(relax != NULL);
3952 
3953  relaxdata = SCIPrelaxGetData(relax);
3954  assert(relaxdata != NULL);
3955 
3956  assert(relaxdata->nblocksidentical[pricingprobnr] >= 0);
3957  assert((relaxdata->blockrepresentative[pricingprobnr] == pricingprobnr)
3958  == (relaxdata->nblocksidentical[pricingprobnr] > 0));
3959 
3960  return relaxdata->blockrepresentative[pricingprobnr];
3961 }
3962 
3966  SCIP* scip,
3967  int pricingprobnr
3968  )
3969 {
3970  SCIP_RELAX* relax;
3971  SCIP_RELAXDATA* relaxdata;
3972 
3973  assert(scip != NULL);
3974 
3975  relax = SCIPfindRelax(scip, RELAX_NAME);
3976  assert(relax != NULL);
3977  assert(pricingprobnr >= 0);
3978 
3979  relaxdata = SCIPrelaxGetData(relax);
3980  assert(relaxdata != NULL);
3981  assert(pricingprobnr <= relaxdata->npricingprobs);
3982  assert(relaxdata->nblocksidentical[pricingprobnr] >= 0);
3983  assert((relaxdata->blockrepresentative[pricingprobnr] == pricingprobnr)
3984  == (relaxdata->nblocksidentical[pricingprobnr] > 0));
3985 
3986  return relaxdata->nblocksidentical[pricingprobnr];
3987 
3988 }
3989 
3991 int GCGgetNMasterConss(
3992  SCIP* scip
3993  )
3994 {
3995  SCIP_RELAX* relax;
3996  SCIP_RELAXDATA* relaxdata;
3997 
3998  assert(scip != NULL);
3999 
4000  relax = SCIPfindRelax(scip, RELAX_NAME);
4001  assert(relax != NULL);
4002 
4003  relaxdata = SCIPrelaxGetData(relax);
4004  assert(relaxdata != NULL);
4005 
4006  return relaxdata->nmasterconss;
4007 }
4008 
4010 SCIP_CONS** GCGgetMasterConss(
4011  SCIP* scip
4012  )
4013 {
4014  SCIP_RELAX* relax;
4015  SCIP_RELAXDATA* relaxdata;
4016 
4017  assert(scip != NULL);
4018 
4019  relax = SCIPfindRelax(scip, RELAX_NAME);
4020  assert(relax != NULL);
4021 
4022  relaxdata = SCIPrelaxGetData(relax);
4023  assert(relaxdata != NULL);
4024 
4025  return relaxdata->masterconss;
4026 }
4027 
4029 SCIP_CONS** GCGgetOrigMasterConss(
4030  SCIP* scip
4031  )
4032 {
4033  SCIP_RELAX* relax;
4034  SCIP_RELAXDATA* relaxdata;
4035 
4036  assert(scip != NULL);
4037 
4038  relax = SCIPfindRelax(scip, RELAX_NAME);
4039  assert(relax != NULL);
4040 
4041  relaxdata = SCIPrelaxGetData(relax);
4042  assert(relaxdata != NULL);
4043 
4044  return relaxdata->origmasterconss;
4045 }
4046 
4050 SCIP_CONS** GCGgetLinearOrigMasterConss(
4051  SCIP* scip
4052  )
4053 {
4054  SCIP_RELAX* relax;
4055  SCIP_RELAXDATA* relaxdata;
4056 
4057  assert(scip != NULL);
4058 
4059  relax = SCIPfindRelax(scip, RELAX_NAME);
4060  assert(relax != NULL);
4061 
4062  relaxdata = SCIPrelaxGetData(relax);
4063  assert(relaxdata != NULL);
4064 
4065  return relaxdata->linearmasterconss;
4066 }
4067 
4069 SCIP_CONS* GCGgetConvCons(
4070  SCIP* scip,
4071  int blocknr
4073  )
4074 {
4075  SCIP_RELAX* relax;
4076  SCIP_RELAXDATA* relaxdata;
4077 
4078  assert(scip != NULL);
4079  assert(blocknr >= 0);
4080 
4081  relax = SCIPfindRelax(scip, RELAX_NAME);
4082  assert(relax != NULL);
4083 
4084  relaxdata = SCIPrelaxGetData(relax);
4085  assert(relaxdata != NULL);
4086  assert(blocknr < relaxdata->npricingprobs);
4087 
4088  return relaxdata->convconss[blocknr];
4089 }
4090 
4092 SCIP_SOL* GCGrelaxGetCurrentOrigSol(
4093  SCIP* scip
4094  )
4095 {
4096  SCIP_RELAX* relax;
4097  SCIP_RELAXDATA* relaxdata;
4098 
4099  assert(scip != NULL);
4100 
4101  relax = SCIPfindRelax(scip, RELAX_NAME);
4102  assert(relax != NULL);
4103 
4104  relaxdata = SCIPrelaxGetData(relax);
4105  assert(relaxdata != NULL);
4106 
4107  return relaxdata->currentorigsol;
4108 }
4109 
4111 SCIP_Bool GCGrelaxIsOrigSolFeasible(
4112  SCIP* scip
4113  )
4114 {
4115  SCIP_RELAX* relax;
4116  SCIP_RELAXDATA* relaxdata;
4117 
4118  assert(scip != NULL);
4119 
4120  relax = SCIPfindRelax(scip, RELAX_NAME);
4121  assert(relax != NULL);
4122 
4123  relaxdata = SCIPrelaxGetData(relax);
4124  assert(relaxdata != NULL);
4125 
4126  return relaxdata->origsolfeasible;
4127 }
4128 
4130 SCIP_Bool GCGisMasterSetCovering(
4131  SCIP* scip
4132  )
4133 {
4134  SCIP_RELAX* relax;
4135  SCIP_RELAXDATA* relaxdata;
4136 
4137  assert(scip != NULL);
4138 
4139  relax = SCIPfindRelax(scip, RELAX_NAME);
4140  assert(relax != NULL);
4141 
4142  relaxdata = SCIPrelaxGetData(relax);
4143  assert(relaxdata != NULL);
4144 
4145  return relaxdata->masterissetcover;
4146 }
4147 
4149 SCIP_Bool GCGisMasterSetPartitioning(
4150  SCIP* scip
4151  )
4152 {
4153  SCIP_RELAX* relax;
4154  SCIP_RELAXDATA* relaxdata;
4155 
4156  assert(scip != NULL);
4157 
4158  relax = SCIPfindRelax(scip, RELAX_NAME);
4159  assert(relax != NULL);
4160 
4161  relaxdata = SCIPrelaxGetData(relax);
4162  assert(relaxdata != NULL);
4163 
4164  return relaxdata->masterissetpart;
4165 }
4166 
4173 SCIP_RETCODE GCGrelaxStartProbing(
4174  SCIP* scip,
4175  SCIP_HEUR* probingheur
4176  )
4177 {
4178  SCIP_RELAX* relax;
4179  SCIP_RELAXDATA* relaxdata;
4180  SCIP* masterprob;
4181 
4182  assert(scip != NULL);
4183 
4184  relax = SCIPfindRelax(scip, RELAX_NAME);
4185  assert(relax != NULL);
4186 
4187  relaxdata = SCIPrelaxGetData(relax);
4188  assert(relaxdata != NULL);
4189 
4190  if( relaxdata->masterinprobing )
4191  {
4192  SCIPerrorMessage("already in GCG probing mode\n");
4193  return SCIP_INVALIDCALL;
4194  }
4195 
4196  masterprob = relaxdata->masterprob;
4197  assert(masterprob != NULL);
4198 
4199  /* start probing in both the original and the master problem */
4200  SCIP_CALL( SCIPstartProbing(scip) );
4201  SCIP_CALL( SCIPstartProbing(masterprob) );
4202 
4203  relaxdata->masterinprobing = TRUE;
4204  relaxdata->probingheur = probingheur;
4205 
4206  /* remember the current original solution */
4207  assert(relaxdata->storedorigsol == NULL);
4208  if( relaxdata->currentorigsol != NULL )
4209  {
4210  SCIP_CALL( SCIPcreateSolCopy(scip, &relaxdata->storedorigsol, relaxdata->currentorigsol) );
4211  relaxdata->storedfeasibility = relaxdata->origsolfeasible;
4212  }
4213 
4214  return SCIP_OKAY;
4215 }
4216 
4218 SCIP_HEUR* GCGrelaxGetProbingheur(
4219  SCIP* scip
4220  )
4221 {
4222  SCIP_RELAX* relax;
4223  SCIP_RELAXDATA* relaxdata;
4224 
4225  assert(scip != NULL);
4226 
4227  relax = SCIPfindRelax(scip, RELAX_NAME);
4228  assert(relax != NULL);
4229 
4230  relaxdata = SCIPrelaxGetData(relax);
4231  assert(relaxdata != NULL);
4232 
4233  return relaxdata->probingheur;
4234 }
4235 
4240 SCIP_RETCODE GCGrelaxNewProbingnodeOrig(
4241  SCIP* scip
4242  )
4243 {
4244  SCIP_RELAX* relax;
4245  SCIP_RELAXDATA* relaxdata;
4246  SCIP_CONS* probingcons;
4247  SCIP_NODE* probingnode;
4248 
4249  assert(scip != NULL);
4250 
4251  relax = SCIPfindRelax(scip, RELAX_NAME);
4252  assert(relax != NULL);
4253 
4254  relaxdata = SCIPrelaxGetData(relax);
4255  assert(relaxdata != NULL);
4256 
4257  if( !relaxdata->masterinprobing )
4258  {
4259  SCIPerrorMessage("not in GCG probing mode\n");
4260  return SCIP_INVALIDCALL;
4261  }
4262 
4263  if( SCIPgetProbingDepth(scip) != SCIPgetProbingDepth(GCGgetMasterprob(scip)) )
4264  {
4265  SCIPerrorMessage("original and master problem not at same probing depth\n");
4266  return SCIP_INVALIDCALL;
4267  }
4268 
4269  /* add a probing node in the original problem together with an original branching constraint */
4270  SCIP_CALL( SCIPnewProbingNode(scip) );
4271  probingnode = SCIPgetCurrentNode(scip);
4272  SCIP_CALL( GCGcreateConsOrigbranch(scip, &probingcons, "probingcons", probingnode,
4273  GCGconsOrigbranchGetActiveCons(scip), NULL, NULL) );
4274  SCIP_CALL( SCIPaddConsNode(scip, probingnode, probingcons, NULL) );
4275  SCIP_CALL( SCIPreleaseCons(scip, &probingcons) );
4276 
4277 
4278  return SCIP_OKAY;
4279 }
4280 
4287 SCIP_RETCODE GCGrelaxNewProbingnodeMaster(
4288  SCIP* scip
4289  )
4290 {
4291  SCIP_RELAX* relax;
4292  SCIP_RELAXDATA* relaxdata;
4293  SCIP* masterprob;
4294  SCIP_CONS* probingcons;
4295  SCIP_NODE* probingnode;
4296 
4297  assert(scip != NULL);
4298 
4299  relax = SCIPfindRelax(scip, RELAX_NAME);
4300  assert(relax != NULL);
4301 
4302  relaxdata = SCIPrelaxGetData(relax);
4303  assert(relaxdata != NULL);
4304 
4305  if( !relaxdata->masterinprobing )
4306  {
4307  SCIPerrorMessage("not in GCG probing mode\n");
4308  return SCIP_INVALIDCALL;
4309  }
4310 
4311  masterprob = relaxdata->masterprob;
4312  assert(masterprob != NULL);
4313 
4314  if( SCIPgetProbingDepth(scip) != SCIPgetProbingDepth(masterprob) + 1 )
4315  {
4316  SCIPerrorMessage("master probing node must be created after original probing node\n");
4317  return SCIP_INVALIDCALL;
4318  }
4319 
4320  /* add a probing node in the master problem together with a master branching constraint */
4321  SCIP_CALL( SCIPnewProbingNode(masterprob) );
4322  probingnode = SCIPgetCurrentNode(masterprob);
4324  SCIP_CALL( GCGcreateConsMasterbranch(masterprob, &probingcons, "mprobingcons", probingnode,
4325  GCGconsMasterbranchGetActiveCons(masterprob), NULL, NULL, NULL, 0) );
4326  SCIP_CALL( SCIPaddConsNode(masterprob, probingnode, probingcons, NULL) );
4327  SCIP_CALL( SCIPreleaseCons(masterprob, &probingcons) );
4328 
4329  return SCIP_OKAY;
4330 }
4331 
4336 SCIP_RETCODE GCGrelaxBacktrackProbing(
4337  SCIP* scip,
4338  int probingdepth
4339  )
4340 {
4341  SCIP_RELAX* relax;
4342  SCIP_RELAXDATA* relaxdata;
4343  SCIP* masterprob;
4344 
4345  assert(scip != NULL);
4346 
4347  relax = SCIPfindRelax(scip, RELAX_NAME);
4348  assert(relax != NULL);
4349 
4350  relaxdata = SCIPrelaxGetData(relax);
4351  assert(relaxdata != NULL);
4352 
4353  if( !relaxdata->masterinprobing )
4354  {
4355  SCIPerrorMessage("not in GCG probing mode\n");
4356  return SCIP_INVALIDCALL;
4357  }
4358 
4359  masterprob = relaxdata->masterprob;
4360  assert(masterprob != NULL);
4361 
4362  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
4363  SCIP_CALL( SCIPbacktrackProbing(masterprob, probingdepth) );
4364 
4365  return SCIP_OKAY;
4366 }
4367 
4369 static
4370 SCIP_RETCODE performProbing(
4371  SCIP* scip,
4372  int maxlpiterations,
4373  int maxpricerounds,
4374  SCIP_Bool usepricing,
4375  SCIP_Longint* nlpiterations,
4376  int* npricerounds,
4377  SCIP_Real* lpobjvalue,
4378  SCIP_Bool* lpsolved,
4379  SCIP_Bool* lperror,
4381  SCIP_Bool* cutoff
4382  )
4383 {
4384  SCIP_RELAX* relax;
4385  SCIP_RELAXDATA* relaxdata;
4386  SCIP* masterprob;
4387  SCIP_LPSOLSTAT lpsolstat;
4388  SCIP_Longint oldnlpiters;
4389  int oldpricerounds;
4390  SCIP_Longint nodelimit;
4391 
4392  assert(scip != NULL);
4393 
4394  /* get the relaxator */
4395  relax = SCIPfindRelax(scip, RELAX_NAME);
4396  assert(relax != NULL);
4397 
4398  /* get the relaxator data */
4399  relaxdata = SCIPrelaxGetData(relax);
4400  assert(relaxdata != NULL);
4401 
4402  if( !relaxdata->masterinprobing )
4403  {
4404  SCIPerrorMessage("not in GCG probing mode\n");
4405  return SCIP_INVALIDCALL;
4406  }
4407 
4408  /* get master problem */
4409  masterprob = relaxdata->masterprob;
4410  assert(masterprob != NULL);
4411 
4412  /* increase node limit for the master problem by 1 */
4413  SCIP_CALL( SCIPgetLongintParam(masterprob, "limits/nodes", &nodelimit) );
4414  SCIP_CALL( SCIPsetLongintParam(masterprob, "limits/nodes", nodelimit + 1) );
4415 
4416  /* propagate probing bound changes to the master problem */
4417  SCIP_CALL( SCIPpropagateProbing(masterprob, -1, cutoff, NULL) );
4418  assert(!(*cutoff));
4419 
4420  /* remember LP iterations and pricing rounds before LP solving */
4421  oldnlpiters = SCIPgetNLPIterations(masterprob);
4422  oldpricerounds = SCIPgetNPriceRounds(masterprob);
4423 
4424  *lpobjvalue = 0.0;
4425  *lpsolved = FALSE;
4426 
4427  /* solve the probing LP */
4428  if( usepricing )
4429  {
4430  /* LP iterations are unlimited when probing LP is solved with pricing */
4431  assert(maxlpiterations == -1);
4432  SCIP_CALL( SCIPsolveProbingLPWithPricing(masterprob, FALSE, TRUE, maxpricerounds, lperror, NULL) );
4433  }
4434  else
4435  {
4436  assert(maxpricerounds == 0);
4437  SCIP_CALL( SCIPsolveProbingLP(masterprob, maxlpiterations, lperror, NULL) );
4438  }
4439  lpsolstat = SCIPgetLPSolstat(masterprob);
4440 
4441  /* reset the node limit */
4442  SCIP_CALL( SCIPsetLongintParam(masterprob, "limits/nodes", nodelimit) );
4443 
4444  /* calculate number of LP iterations and pricing rounds performed */
4445  if( nlpiterations != NULL )
4446  *nlpiterations = SCIPgetNLPIterations(masterprob) - oldnlpiters;
4447  if( npricerounds != NULL )
4448  *npricerounds = SCIPgetNPriceRounds(masterprob) - oldpricerounds;
4449 
4450  if( !(*lperror) )
4451  {
4452  /* get LP solution status, objective value */
4453  *cutoff = *cutoff || (lpsolstat == SCIP_LPSOLSTAT_OBJLIMIT || lpsolstat == SCIP_LPSOLSTAT_INFEASIBLE);
4454  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
4455  {
4456  SCIPdebugMessage("lpobjval = %g\n", SCIPgetLPObjval(masterprob));
4457  *lpobjvalue = SCIPgetLPObjval(masterprob);
4458  *lpsolved = TRUE;
4459  SCIP_CALL( GCGrelaxUpdateCurrentSol(scip) );
4460  }
4461  }
4462  else
4463  {
4464  SCIPdebugMessage("something went wrong, an lp error occurred\n");
4465  }
4466 
4467  return SCIP_OKAY;
4468 }
4469 
4470 
4472 SCIP_RETCODE GCGrelaxPerformProbing(
4473  SCIP* scip,
4474  int maxlpiterations,
4475  SCIP_Longint* nlpiterations,
4476  SCIP_Real* lpobjvalue,
4477  SCIP_Bool* lpsolved,
4478  SCIP_Bool* lperror,
4480  SCIP_Bool* cutoff
4481  )
4482 {
4483  SCIP_CALL( performProbing(scip, maxlpiterations, 0, FALSE, nlpiterations,
4484  NULL, lpobjvalue, lpsolved, lperror, cutoff) );
4485 
4486  return SCIP_OKAY;
4487 }
4488 
4489 
4492  SCIP* scip,
4493  int maxpricerounds,
4494  SCIP_Longint* nlpiterations,
4495  int* npricerounds,
4496  SCIP_Real* lpobjvalue,
4497  SCIP_Bool* lpsolved,
4498  SCIP_Bool* lperror,
4500  SCIP_Bool* cutoff
4501  )
4502 {
4503  SCIP_CALL( performProbing(scip, -1, maxpricerounds, TRUE, nlpiterations,
4504  npricerounds, lpobjvalue, lpsolved, lperror, cutoff) );
4505 
4506  return SCIP_OKAY;
4507 }
4508 
4509 
4511 SCIP_RETCODE GCGrelaxEndProbing(
4512  SCIP* scip
4513  )
4514 {
4515  SCIP_RELAX* relax;
4516  SCIP_RELAXDATA* relaxdata;
4517  SCIP* masterprob;
4518 
4519  SCIP_VAR** vars;
4520  int nvars;
4521 
4522  assert(scip != NULL);
4523 
4524  relax = SCIPfindRelax(scip, RELAX_NAME);
4525  assert(relax != NULL);
4526 
4527  relaxdata = SCIPrelaxGetData(relax);
4528  assert(relaxdata != NULL);
4529 
4530  if( !relaxdata->masterinprobing )
4531  {
4532  SCIPerrorMessage("not in GCG probing mode\n");
4533  return SCIP_INVALIDCALL;
4534  }
4535 
4536  masterprob = relaxdata->masterprob;
4537  assert(masterprob != NULL);
4538 
4539  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
4540  assert(vars != NULL);
4541  assert(nvars >= 0);
4542 
4543  SCIP_CALL( SCIPendProbing(masterprob) );
4544  SCIP_CALL( SCIPendProbing(scip) );
4545 
4546  relaxdata->masterinprobing = FALSE;
4547  relaxdata->probingheur = NULL;
4548 
4549  /* if a new primal solution was found in the master problem, transfer it to the original problem
4550  * @todo: this is probably not necessary anymore since it is done by an event handler
4551  */
4552  if( SCIPgetBestSol(masterprob) != NULL && relaxdata->lastmastersol != SCIPgetBestSol(masterprob) )
4553  {
4554  SCIP_SOL* newsol;
4555  SCIP_Bool stored;
4556 
4557  relaxdata->lastmastersol = SCIPgetBestSol(masterprob);
4558 
4559  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, relaxdata->lastmastersol, &newsol) );
4560 
4561  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4562  if( !stored )
4563  {
4564  SCIP_CALL( SCIPcheckSolOrig(scip, newsol, &stored, TRUE, TRUE) );
4565  }
4566  assert(stored);
4567  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
4568 
4569  SCIPdebugMessage("probing finished in master problem\n");
4570  }
4571 
4572  /* restore old relaxation solution and branching candidates */
4573  if( relaxdata->currentorigsol != NULL )
4574  {
4575  SCIPdebugMessage("Freeing previous solution origsol\n");
4576  SCIP_CALL( SCIPfreeSol(scip, &(relaxdata->currentorigsol)) );
4577  }
4578  SCIPclearExternBranchCands(scip);
4579 
4580  if( relaxdata->storedorigsol != NULL )
4581  {
4582  int i;
4583 
4584  SCIP_CALL( SCIPcreateSol(scip, &relaxdata->currentorigsol, NULL) );
4585  SCIP_CALL( SCIPsetRelaxSolValsSol(scip, relaxdata->storedorigsol, RELAX_INCLUDESLP) );
4586 
4587  for( i = 0; i < nvars; i++ )
4588  {
4589  SCIP_VAR* var;
4590  SCIP_Real solval;
4591 
4592  var = vars[i];
4593  solval = SCIPgetSolVal(scip, relaxdata->storedorigsol, var);
4594 
4595  SCIP_CALL( SCIPsetSolVal(scip, relaxdata->currentorigsol, var, solval) );
4596 
4597  if( SCIPvarGetType(var) <= SCIP_VARTYPE_INTEGER && !SCIPisFeasIntegral(scip, solval) )
4598  {
4599  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
4600  SCIP_CALL( SCIPaddExternBranchCand(scip, var, solval - SCIPfloor(scip, solval), solval) );
4601  }
4602  }
4603  assert(SCIPisFeasEQ(scip, SCIPgetRelaxSolObj(scip), SCIPgetSolTransObj(scip, relaxdata->currentorigsol)));
4604 
4605  SCIP_CALL( SCIPfreeSol(scip, &relaxdata->storedorigsol) );
4606 
4607  relaxdata->origsolfeasible = relaxdata->storedfeasibility;
4608  }
4609 
4612  return SCIP_OKAY;
4613 }
4614 
4615 
4617 static
4619  SCIP* scip,
4620  SCIP_VAR* var
4621  )
4622 {
4623  assert(scip != NULL);
4624  assert(var != NULL);
4625 
4626  if( SCIPvarGetType(var) <= SCIP_VARTYPE_INTEGER && !SCIPisFeasIntegral(scip, SCIPgetRelaxSolVal(scip, var)) )
4627  {
4628  if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
4629  {
4630  SCIPdebugMessage("lblocal = %g, ublocal = %g\n", SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
4631  SCIPdebugMessage("var = %s, vartype = %d, val = %g\n", SCIPvarGetName(var), SCIPvarGetType(var),
4632  SCIPgetRelaxSolVal(scip, var));
4633  }
4634 
4635  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
4636 
4637  SCIP_CALL( SCIPaddExternBranchCand(scip, var, SCIPgetRelaxSolVal(scip, var) -
4638  SCIPfloor(scip, SCIPgetRelaxSolVal(scip, var)), SCIPgetRelaxSolVal(scip, var)) );
4639  }
4640 
4641  return SCIP_OKAY;
4642 }
4643 
4644 
4645 
4649 SCIP_RETCODE GCGrelaxUpdateCurrentSol(
4650  SCIP* scip
4651  )
4652 {
4653  SCIP_RELAX* relax;
4654  SCIP_RELAXDATA* relaxdata;
4655  SCIP_VAR** origvars;
4656  int norigvars;
4657  SCIP_Bool stored;
4658 
4659  assert(scip != NULL);
4660 
4661  relax = SCIPfindRelax(scip, RELAX_NAME);
4662  assert(relax != NULL);
4663 
4664  relaxdata = SCIPrelaxGetData(relax);
4665  assert(relaxdata != NULL);
4666 
4667  origvars = SCIPgetVars(scip);
4668  norigvars = SCIPgetNVars(scip);
4669  assert(origvars != NULL);
4670 
4671  relaxdata->origsolfeasible = FALSE;
4672 
4673  /* if the master problem has not been solved, don't try to update the solution */
4674  if( SCIPgetStage(relaxdata->masterprob) == SCIP_STAGE_TRANSFORMED )
4675  return SCIP_OKAY;
4676 
4677  /* free previous solution and clear branching candidates */
4678  if( relaxdata->currentorigsol != NULL )
4679  {
4680  SCIPdebugMessage("Freeing previous solution origsol\n");
4681  SCIP_CALL( SCIPfreeSol(scip, &(relaxdata->currentorigsol)) );
4682  }
4683  SCIPclearExternBranchCands(scip);
4684 
4685  if( SCIPgetStage(relaxdata->masterprob) == SCIP_STAGE_SOLVED || SCIPgetLPSolstat(relaxdata->masterprob) == SCIP_LPSOLSTAT_OPTIMAL )
4686  {
4687  SCIP_SOL* mastersol;
4688 
4689  relaxdata->lastmasterlpiters = SCIPgetNLPIterations(relaxdata->masterprob);
4690 
4691  /* create new solution */
4692  if( SCIPgetStage(relaxdata->masterprob) == SCIP_STAGE_SOLVING )
4693  {
4694  SCIPdebugMessage("Masterproblem still solving, mastersol = NULL\n");
4695  mastersol = NULL;
4696  }
4697  else if( SCIPgetStage(relaxdata->masterprob) == SCIP_STAGE_SOLVED )
4698  {
4699  mastersol = SCIPgetBestSol(relaxdata->masterprob);
4700  if( mastersol == NULL )
4701  {
4702  SCIPdebugMessage("Masterproblem solved, no master sol present\n");
4703  return SCIP_OKAY;
4704  }
4705  SCIPdebugMessage("Masterproblem solved, mastersol = %pd\n", (void*) mastersol);
4706  }
4707  else
4708  {
4709  SCIPdebugMessage("stage in master not solving and not solved!\n");
4710  return SCIP_OKAY;
4711  }
4712 
4713  if( !SCIPisInfinity(scip, SCIPgetSolOrigObj(relaxdata->masterprob, mastersol)) && GCGmasterIsSolValid(relaxdata->masterprob, mastersol) )
4714  {
4715  int i;
4716  int j;
4717 
4718  /* transform the master solution to the original variable space */
4719  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, mastersol, &(relaxdata->currentorigsol)) );
4720 
4721  /* store the solution as relaxation solution */
4722  SCIP_CALL( SCIPsetRelaxSolValsSol(scip, relaxdata->currentorigsol, RELAX_INCLUDESLP) );
4723  assert(SCIPisEQ(scip, SCIPgetRelaxSolObj(scip), SCIPgetSolTransObj(scip, relaxdata->currentorigsol)));
4724 
4726  SCIP_CALL( SCIPtrySol(scip, relaxdata->currentorigsol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
4727  else
4728  SCIP_CALL( SCIPcheckSolOrig(scip, relaxdata->currentorigsol, &stored, FALSE, TRUE) );
4729 
4730  SCIPdebugMessage("updated current original LP solution, %s feasible in the original problem!\n",
4731  (stored ? "" : "not"));
4732 
4733  if( stored )
4734  relaxdata->origsolfeasible = TRUE;
4735 
4736  /* in the case of Benders decomposition, only the master variables can be added as branching candidates */
4738  {
4739  SCIP* masterprob;
4740  SCIP_VAR** mastervars;
4741  SCIP_VAR** masterorigvars;
4742  int nmastervars;
4743  int nmasterorigvars;
4744 
4745  /* retrieving the master problem */
4746  masterprob = GCGgetMasterprob(scip);
4747 
4748  /* get variables of the master problem and their solution values */
4749  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
4750 
4751  /* looping over all master variables to get the original variable for branching candidates */
4752  for( i = 0; i < nmastervars; i++ )
4753  {
4754  masterorigvars = GCGmasterVarGetOrigvars(mastervars[i]);
4755  nmasterorigvars = GCGmasterVarGetNOrigvars(mastervars[i]);
4756 
4757  for( j = 0; j < nmasterorigvars; j++ )
4758  SCIP_CALL( checkAndAddExternalBranchingCandidate(scip, masterorigvars[j]) );
4759  }
4760  }
4761  else
4762  {
4764  /* store branching candidates */
4765  for( i = 0; i < norigvars; i++ )
4766  SCIP_CALL( checkAndAddExternalBranchingCandidate(scip, origvars[i]) );
4767  }
4768 
4769  SCIPdebugMessage("updated relaxation branching candidates\n");
4770  }
4771  }
4772 
4773  return SCIP_OKAY;
4774 }
4775 
4777 SCIP_RETCODE GCGsetStructDecdecomp(
4778  SCIP* scip,
4780  )
4781 {
4782  SCIP_RELAX* relax;
4783  SCIP_RELAXDATA* relaxdata;
4784 
4785  assert(scip != NULL);
4786  assert(decdecomp != NULL);
4787 
4788  relax = SCIPfindRelax(scip, RELAX_NAME);
4789  assert(relax != NULL);
4790 
4791  relaxdata = SCIPrelaxGetData(relax);
4792  assert(relaxdata != NULL);
4793 
4794  if( relaxdata->decdecomp != NULL )
4795  SCIP_CALL( DECdecompFree(scip, &relaxdata->decdecomp ) );
4796 
4797  relaxdata->decdecomp = decdecomp;
4798 
4799  return SCIP_OKAY;
4800 }
4801 
4803 SCIP_RETCODE GCGsetFilename(
4804  SCIP* scip,
4805  const char* filename
4806  )
4807 {
4808  SCIP_RELAX* relax;
4809  SCIP_RELAXDATA* relaxdata;
4810 
4811  assert(scip != NULL);
4812  assert(filename != NULL);
4813 
4814  relax = SCIPfindRelax(scip, RELAX_NAME);
4815  assert(relax != NULL);
4816 
4817  relaxdata = SCIPrelaxGetData(relax);
4818  assert(relaxdata != NULL);
4819  if (relaxdata->filename != NULL)
4820  SCIPfreeBlockMemoryArray(scip, &(relaxdata->filename), SCIP_MAXSTRLEN);
4821 
4822  SCIP_CALL( SCIPduplicateBlockMemoryArray( scip, & relaxdata->filename, filename, SCIP_MAXSTRLEN ) );
4823 
4824  return SCIP_OKAY;
4825 }
4826 
4827 
4828 
4831  SCIP* scip
4832  )
4833 {
4834  SCIP_RELAX* relax;
4835  SCIP_RELAXDATA* relaxdata;
4836 
4837  assert(scip != NULL);
4838 
4839  relax = SCIPfindRelax(scip, RELAX_NAME);
4840  assert(relax != NULL);
4841 
4842  relaxdata = SCIPrelaxGetData(relax);
4843  assert(relaxdata != NULL);
4844 
4845  return relaxdata->decdecomp;
4846 }
4847 
4849 const char* GCGgetFilename(
4850  SCIP* scip
4851 )
4852 {
4853  SCIP_RELAX* relax;
4854  SCIP_RELAXDATA* relaxdata;
4855 
4856  assert(scip != NULL);
4857 
4858  relax = SCIPfindRelax(scip, RELAX_NAME);
4859  assert(relax != NULL);
4860 
4861  relaxdata = SCIPrelaxGetData(relax);
4862  assert(relaxdata != NULL);
4863 
4864  if( relaxdata->filename == NULL )
4865  {
4866  char help[SCIP_MAXSTRLEN];
4867  (void) strncat( help, "unknown", 8 );
4868  SCIP_CALL_ABORT(SCIPduplicateBlockMemoryArray( scip, & relaxdata->filename, help, SCIP_MAXSTRLEN ) );
4869  }
4870 
4871  return relaxdata->filename;
4872 
4873 }
4874 
4876 SCIP_Real GCGgetPricingprobsMemUsed(
4877  SCIP* scip
4878  )
4879 {
4880  SCIP_RELAX* relax;
4881  SCIP_RELAXDATA* relaxdata;
4882 
4883  int p;
4884  SCIP_Real memused;
4885 
4886  assert(scip != NULL);
4887 
4888  relax = SCIPfindRelax(scip, RELAX_NAME);
4889  assert(relax != NULL);
4890 
4891  relaxdata = SCIPrelaxGetData(relax);
4892  assert(relaxdata != NULL);
4893 
4894  memused = 0.0;
4895 
4896  /* @todo replace the computation by relaxdata->pricingprobsmemused if we can assure that the memory
4897  * used by the pricing problems is constant */
4898 
4899  /* compute memory that is used by all pricing problems */
4900  for( p = 0; p < relaxdata->npricingprobs; ++p )
4901  {
4902  memused += SCIPgetMemUsed(relaxdata->pricingprobs[p])/1048576.0;
4903  }
4904 
4905  return memused;
4906 }
4907 
4909 SCIP_Bool GCGrelaxIsInitialized(
4910  SCIP* scip
4911  )
4912 {
4913 
4914  SCIP_RELAX* relax;
4915  SCIP_RELAXDATA* relaxdata;
4916 
4917  assert(scip != NULL);
4918 
4919  relax = SCIPfindRelax(scip, RELAX_NAME);
4920  assert(relax != NULL);
4921 
4922  relaxdata = SCIPrelaxGetData(relax);
4923  assert(relaxdata != NULL);
4924 
4925  return relaxdata->relaxisinitialized;
4926 }
4927 
4929 SCIP_Real GCGgetDegeneracy(
4930  SCIP* scip
4931  )
4932 {
4933 
4934  SCIP_Real degeneracy;
4935  SCIP_RELAX* relax;
4936  SCIP_RELAXDATA* relaxdata;
4937 
4938  assert(scip != NULL);
4939 
4940  relax = SCIPfindRelax(scip, RELAX_NAME);
4941  assert(relax != NULL);
4942 
4943  relaxdata = SCIPrelaxGetData(relax);
4944  assert(relaxdata != NULL);
4945  degeneracy = 0.0;
4946  if( relaxdata->masterprob != NULL )
4947  {
4948  degeneracy = GCGmasterGetDegeneracy(relaxdata->masterprob);
4949  if( SCIPisInfinity(relaxdata->masterprob, degeneracy) )
4950  degeneracy = SCIPinfinity(scip);
4951  }
4952  return degeneracy;
4953 }
4954 
4956 SCIP_CONS** GCGgetVarLinkingconss(
4957  SCIP* scip
4958  )
4959 {
4960  SCIP_RELAX* relax;
4961  SCIP_RELAXDATA* relaxdata;
4962 
4963  assert(scip != NULL);
4964 
4965  relax = SCIPfindRelax(scip, RELAX_NAME);
4966  assert(relax != NULL);
4967 
4968  relaxdata = SCIPrelaxGetData(relax);
4969  assert(relaxdata != NULL);
4970 
4971  return relaxdata->varlinkconss;
4972 }
4973 
4976  SCIP* scip
4977  )
4978 {
4979  SCIP_RELAX* relax;
4980  SCIP_RELAXDATA* relaxdata;
4981 
4982  assert(scip != NULL);
4983 
4984  relax = SCIPfindRelax(scip, RELAX_NAME);
4985  assert(relax != NULL);
4986 
4987  relaxdata = SCIPrelaxGetData(relax);
4988  assert(relaxdata != NULL);
4989 
4990  return relaxdata->varlinkconsblock;
4991 }
4992 
4995  SCIP* scip
4996  )
4997 {
4998  SCIP_RELAX* relax;
4999  SCIP_RELAXDATA* relaxdata;
5000 
5001  assert(scip != NULL);
5002 
5003  relax = SCIPfindRelax(scip, RELAX_NAME);
5004  assert(relax != NULL);
5005 
5006  relaxdata = SCIPrelaxGetData(relax);
5007  assert(relaxdata != NULL);
5008 
5009  return relaxdata->nvarlinkconss;
5010 }
5011 
5013 int GCGgetNLinkingvars(
5014  SCIP* scip
5015  )
5016 {
5017  SCIP_RELAX* relax;
5018  SCIP_RELAXDATA* relaxdata;
5019 
5020  assert(scip != NULL);
5021 
5022  relax = SCIPfindRelax(scip, RELAX_NAME);
5023  assert(relax != NULL);
5024 
5025  relaxdata = SCIPrelaxGetData(relax);
5026  assert(relaxdata != NULL);
5027 
5028  return relaxdata->nlinkingvars;
5029 }
5030 
5032 int GCGgetNTransvars(
5033  SCIP* scip
5034  )
5035 {
5036  SCIP_RELAX* relax;
5037  SCIP_RELAXDATA* relaxdata;
5038 
5039  assert(scip != NULL);
5040 
5041  relax = SCIPfindRelax(scip, RELAX_NAME);
5042  assert(relax != NULL);
5043 
5044  relaxdata = SCIPrelaxGetData(relax);
5045  assert(relaxdata != NULL);
5046 
5047  return relaxdata->ntransvars;
5048 }
5049 
5051 SCIP_SOL* GCGgetBendersRelaxationSol(
5052  SCIP* scip
5053  )
5054 {
5055  SCIP_RELAX* relax;
5056  SCIP_RELAXDATA* relaxdata;
5057  SCIP_BENDERS* benders;
5058 
5059  assert(scip != NULL);
5060 
5061  relax = SCIPfindRelax(scip, RELAX_NAME);
5062  assert(relax != NULL);
5063 
5064  relaxdata = SCIPrelaxGetData(relax);
5065  assert(relaxdata != NULL);
5066 
5067  benders = SCIPfindBenders(relaxdata->masterprob, "gcg");
5068  assert(benders != NULL);
5069 
5070  return SCIPbendersGetRelaxSol(benders);
5071 }
5072 
5075  SCIP* scip
5076  )
5077 {
5078  SCIP_RELAX* relax;
5079  SCIP_RELAXDATA* relaxdata;
5080 
5081  assert(scip != NULL);
5082 
5083  relax = SCIPfindRelax(scip, RELAX_NAME);
5084  assert(relax != NULL);
5085 
5086  relaxdata = SCIPrelaxGetData(relax);
5087  assert(relaxdata != NULL);
5088 
5089  return (DEC_DECMODE)relaxdata->mode;
5090 }
5091 
5096  SCIP* masterprob
5097  )
5098 {
5099  SCIP_BENDERS* benders;
5100  SCIP_PRICER* pricer;
5101  DEC_DECMODE mode;
5102 
5103  assert(masterprob != NULL);
5104 
5105  /* retrieving the Benders' decomposition and the pricer plugins. There should only be one or the other for a given
5106  * master problem. If there are both, then an error is returned */
5107  benders = SCIPfindBenders(masterprob, "gcg");
5108  pricer = SCIPfindPricer(masterprob, "gcg");
5109  assert((benders != NULL && pricer == NULL) || (pricer != NULL && benders == NULL));
5110 
5111  if( benders != NULL )
5112  {
5113  /* both the Benders' master and the original master have the Benders' decomposition included. */
5114  if( SCIPgetNActiveBenders(masterprob) > 0 )
5116  else
5118  }
5119  else if( pricer != NULL )
5121  else
5122  {
5124  SCIPerrorMessage("Sorry, the decomposition mode of the master problem is invalid. This should not happen.");
5125  SCIPABORT();
5126  }
5127 
5128  return mode;
5129 }
int GCGgetNMasterConss(SCIP *scip)
Definition: relax_gcg.c:3992
SCIP_RETCODE GCGrelaxPerformProbing(SCIP *scip, int maxlpiterations, SCIP_Longint *nlpiterations, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4473
SCIP_CONS *** DECdecompGetSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:903
SCIP_CONS ** GCGlinkingVarGetLinkingConss(SCIP_VAR *var)
Definition: gcgvar.c:753
static SCIP_DECL_RELAXINITSOL(relaxInitsolGcg)
Definition: relax_gcg.c:2743
SCIP_RETCODE GCGlinkingVarCreateMasterCons(SCIP *masterscip, int pricingprobnr, SCIP_VAR *origvar, SCIP_CONS **linkcons)
Definition: gcgvar.c:1185
#define RELAX_NAME
Definition: relax_gcg.c:75
static SCIP_RETCODE checkSetppcStructure(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:478
SCIP_Bool masterinprobing
Definition: relax_gcg.c:147
DEC_DECOMP * DECgetBestDecomp(SCIP *scip)
static SCIP_RETCODE performProbing(SCIP *scip, int maxlpiterations, int maxpricerounds, SCIP_Bool usepricing, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4371
GCG_BRANCHDATA * GCGconsOrigbranchGetBranchdata(SCIP_CONS *cons)
#define DEFAULT_AGGREGATION
Definition: relax_gcg.c:82
static SCIP_RETCODE createMaster(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1850
static SCIP_DECL_RELAXEXIT(relaxExitGcg)
Definition: relax_gcg.c:2706
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:162
static SCIP_RETCODE initRelaxProblemdata(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1423
#define RELAX_PRIORITY
Definition: relax_gcg.c:77
SCIP_RETCODE SCIPincludePricerGcg(SCIP *scip, SCIP *origprob)
SCIP ** pricingprobs
Definition: relax_gcg.c:100
SCIP_CONS ** masterconss
Definition: relax_gcg.c:115
SCIP_Real GCGmasterGetDegeneracy(SCIP *scip)
SCIP_Bool GCGisMasterSetCovering(SCIP *scip)
Definition: relax_gcg.c:4131
SCIP_RETCODE GCGfreeOrigVarsData(SCIP *scip)
Definition: gcgvar.c:268
GCG interface methods.
SCIP_RETCODE SCIPconshdlrDecompAddDecdecomp(SCIP *scip, DEC_DECOMP *decdecomp)
sets (and adds) the decomposition structure
SCIP_RETCODE GCGrelaxBranchDataDelete(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA **branchdata)
Definition: relax_gcg.c:3610
GCG_BRANCHRULE ** branchrules
Definition: relax_gcg.c:134
static SCIP_RETCODE setPricingObjsOriginal(SCIP *scip, SCIP **probs, int nprobs)
Definition: relax_gcg.c:2082
#define RELAX_INCLUDESLP
Definition: relax_gcg.c:79
#define GCG_DECL_BRANCHMASTERSOLVED(x)
static SCIP_DECL_RELAXEXITSOL(relaxExitsolGcg)
Definition: relax_gcg.c:2816
SCIP_Real * GCGoriginalVarGetCoefs(SCIP_VAR *var)
Definition: gcgvar.c:593
SCIP_HASHMAP * DECdecompGetVartoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1196
SCIP_RETCODE GCGrelaxBacktrackProbing(SCIP *scip, int probingdepth)
Definition: relax_gcg.c:4337
int DECdecompGetNMastervars(DEC_DECOMP *decomp)
Definition: decomp.c:1066
int * blockrepresentative
Definition: relax_gcg.c:103
SCIP plugins for generic column generation.
SCIP * GCGbendersGetOrigprob(SCIP *masterprob)
Definition: benders_gcg.c:768
SCIP_Bool discretization
Definition: relax_gcg.c:138
static SCIP_DECL_RELAXEXEC(relaxExecGcg)
Definition: relax_gcg.c:3300
int nrelpricingprobs
Definition: relax_gcg.c:102
SCIP_Bool masterissetcover
Definition: relax_gcg.c:141
DEC_DECMODE GCGgetMasterDecompMode(SCIP *masterprob)
Definition: relax_gcg.c:5096
helper functions for automorphism detection
static SCIP_RETCODE createMasterprobConss(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:1612
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
int GCGgetNRelPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3877
static SCIP_RETCODE relaxExecGcgDantzigWolfe(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3068
SCIP_RETCODE cmpGraphPair(SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap)
SCIP_RETCODE SCIPconshdlrDecompChooseCandidatesFromSelected(SCIP *scip, SCIP_Bool updatelist)
initilizes the candidates data structures with selected seeeds (or all if there are no selected seeed...
static SCIP_RETCODE createPricingProblem(SCIP **pricingscip, const char *name, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastol, SCIP_Real dualfeastol, SCIP_Bool enableppcuts)
Definition: relax_gcg.c:1535
SCIP_RETCODE GCGcreateInitialMasterVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **newvar)
Definition: gcgvar.c:1365
SCIP_Bool GCGmasterIsSolValid(SCIP *scip, SCIP_SOL *mastersol)
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
SCIP_Real DECdecompGetMaxwhiteScore(DEC_DECOMP *decomp)
Definition: decomp.c:696
SCIP_RETCODE GCGcreateOrigVarsData(SCIP *scip)
Definition: gcgvar.c:244
static SCIP_RETCODE displayPricingStatistics(SCIP *scip, SCIP **pricingprobs, int npricingprobs, int *blockrepresentative)
Definition: relax_gcg.c:1384
SCIP plugins for the master problem running in Benders&#39; decomposition mode.
int GCGgetNVarLinkingconss(SCIP *scip)
Definition: relax_gcg.c:4995
SCIP_RETCODE GCGsetFilename(SCIP *scip, const char *filename)
Definition: relax_gcg.c:4804
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:525
SCIP_RETCODE GCGoriginalVarAddBlock(SCIP *scip, SCIP_VAR *var, int newblock, int nblocks, DEC_DECMODE mode)
Definition: gcgvar.c:692
static SCIP_RETCODE solveMasterProblem(SCIP *scip, SCIP *masterprob, SCIP_RELAXDATA *relaxdata, SCIP_Longint nodelimit, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:2936
static SCIP_RETCODE freeBlockProblem(SCIP *scip, SCIP *blockprob, SCIP_RELAXDATA *relaxdata, int blocknum)
Definition: relax_gcg.c:2279
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4150
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1043
SCIP_RETCODE GCGorigVarCreateData(SCIP *scip, SCIP_VAR *var)
Definition: gcgvar.c:302
void GCGvarSetBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:950
int GCGoriginalVarGetNCoefs(SCIP_VAR *var)
Definition: gcgvar.c:609
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4093
SCIP_RETCODE SCIPincludeBendersGcg(SCIP *scip, SCIP *origprob)
Definition: benders_gcg.c:719
SCIP_Bool origsolfeasible
Definition: relax_gcg.c:126
int * varlinkconsblock
Definition: relax_gcg.c:121
SCIP_HASHMAP * hashorig2origvar
Definition: relax_gcg.c:112
int nmarkedmasterconss
Definition: relax_gcg.c:130
SCIP_RETCODE GCGconsOrigbranchAddRootCons(SCIP *scip)
SCIP_SOL * storedorigsol
Definition: relax_gcg.c:149
SCIP_RETCODE SCIPconshdlrDecompArePricingprobsIdenticalForSeeedid(SCIP *scip, int seeedid, int probnr1, int probnr2, SCIP_Bool *identical)
DEC_DECOMP * GCGgetStructDecdecomp(SCIP *scip)
Definition: relax_gcg.c:4831
const char * filename
Definition: relax_gcg.c:160
SCIP_RETCODE GCGoriginalVarAddCoef(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_CONS *cons)
Definition: gcgvar.c:646
SCIP_RETCODE GCGrelaxUpdateCurrentSol(SCIP *scip)
Definition: relax_gcg.c:4650
int DECdecompGetNLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:972
SCIP_CONS ** GCGgetOrigMasterConss(SCIP *scip)
Definition: relax_gcg.c:4030
enum Decmode DEC_DECMODE
Definition: type_decomp.h:67
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:620
int GCGgetNLinkingvars(SCIP *scip)
Definition: relax_gcg.c:5014
SCIP_Longint lastmasterlpiters
Definition: relax_gcg.c:127
static SCIP_RETCODE pricingprobsAreIdentical(SCIP *scip, SCIP_RELAXDATA *relaxdata, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical)
Definition: relax_gcg.c:836
static SCIP_RETCODE createPricingVariables(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:1273
SCIP_RETCODE GCGrelaxTransOrigToMasterCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: relax_gcg.c:3695
static SCIP_RETCODE saveOriginalVarMastercoeffs(SCIP *scip, SCIP_VAR **origvars, int norigvars, int nmasterconss, SCIP_CONS **linearmasterconss, SCIP_CONS **masterconss)
Definition: relax_gcg.c:1562
SCIP_BRANCHRULE * GCGconsOrigbranchGetBranchrule(SCIP_CONS *cons)
DEC_DECTYPE DECdecompGetType(DEC_DECOMP *decomp)
Definition: decomp.c:686
static SCIP_RETCODE relaxExecGcgOriginalProblem(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3281
int DECdecompGetNBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:740
static SCIP_RETCODE relaxExecGcgBendersDecomposition(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3263
int DECdecompGetSeeedID(DEC_DECOMP *decomp)
Definition: decomp.c:1633
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:920
static SCIP_DECL_RELAXFREE(relaxFreeGcg)
Definition: relax_gcg.c:2672
static SCIP_RETCODE ensureSizeMasterConss(SCIP *scip, SCIP_RELAXDATA *relaxdata, int size)
Definition: relax_gcg.c:428
static SCIP_Bool realArraysAreEqual(SCIP *scip, SCIP_Real *array1, int array1length, SCIP_Real *array2, int array2length)
Definition: relax_gcg.c:582
SCIP_CONS ** GCGgetLinearOrigMasterConss(SCIP *scip)
Definition: relax_gcg.c:4051
various SCIP helper methods
struct GCG_Branchrule GCG_BRANCHRULE
SCIP_Bool masterissetpart
Definition: relax_gcg.c:140
SCIP_Bool dispinfos
Definition: relax_gcg.c:142
static SCIP_RETCODE createLinkingPricingVars(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_VAR *origvar)
Definition: relax_gcg.c:1162
int GCGlinkingVarGetNBlocks(SCIP_VAR *var)
Definition: gcgvar.c:473
SCIP_CONS * GCGconsOrigbranchGetActiveCons(SCIP *scip)
const char * GCGgetBlissVersion(void)
Definition: bliss.cpp:469
SCIP_RETCODE GCGrelaxPerformProbingWithPricing(SCIP *scip, int maxpricerounds, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4492
#define DEFAULT_DISPINFOS
Definition: relax_gcg.c:83
SCIP_VAR *** DECdecompGetSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:818
static SCIP_RETCODE initializeMasterProblemSolve(SCIP *scip, SCIP_RELAX *relax)
Definition: relax_gcg.c:2902
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:965
#define RELAX_FREQ
Definition: relax_gcg.c:78
SCIP_RETCODE DECpermuteDecomp(SCIP *scip, DEC_DECOMP *decomp, SCIP_RANDNUMGEN *randnumgen)
Definition: decomp.c:4302
SCIP_Real GCGgetDegeneracy(SCIP *scip)
Definition: relax_gcg.c:4930
GCG relaxator.
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:391
SCIP_RETCODE SCIPincludeRelaxGcg(SCIP *scip)
Definition: relax_gcg.c:3349
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:962
SCIP_VAR ** DECdecompGetLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1033
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
int * DECdecompGetNSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:912
void GCGoriginalVarSetNCoefs(SCIP_VAR *var, int ncoefs)
Definition: gcgvar.c:625
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
GCG variable pricer.
SCIP_Bool GCGrelaxIsInitialized(SCIP *scip)
Definition: relax_gcg.c:4910
SCIP_SOL * lastmastersol
Definition: relax_gcg.c:128
#define relaxCopyGcg
Definition: relax_gcg.c:3340
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:888
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
SCIP_Bool GCGmasterIsBestsolValid(SCIP *scip)
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3857
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966
SCIP_CONS ** varlinkconss
Definition: relax_gcg.c:120
static SCIP_RETCODE ensureSizeBranchrules(SCIP *scip, SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:454
#define GCG_DECL_BRANCHDATADELETE(x)
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3918
GCG Benders&#39; decomposition.
SCIP_RETCODE DECdecompCheckConsistency(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2242
automorphism recognition of SCIPs
void GCGlinkingVarSetPricingVar(SCIP_VAR *origvar, int pricingprobnr, SCIP_VAR *var)
Definition: gcgvar.c:408
SCIP * altmasterprob
Definition: relax_gcg.c:99
SCIP_RETCODE GCGsetStructDecdecomp(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: relax_gcg.c:4778
SCIP_Bool relaxisinitialized
Definition: relax_gcg.c:154
SCIP_SOL * currentorigsol
Definition: relax_gcg.c:125
SCIP_HEUR * probingheur
Definition: relax_gcg.c:148
#define relaxInitGcg
Definition: relax_gcg.c:3341
static SCIP_RETCODE checkIdenticalBlocks(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:883
SCIP_RETCODE GCGincludeBendersPlugins(SCIP *scip)
SCIP_CONS * GCGgetConvCons(SCIP *scip, int blocknr)
Definition: relax_gcg.c:4070
SCIP_RETCODE DECdecompTransform(SCIP *scip, DEC_DECOMP *decomp)
Definition: decomp.c:1957
SCIP_SOL * SCIPbendersGetRelaxSol(SCIP_BENDERS *benders)
Definition: benders_gcg.c:753
static SCIP_RETCODE createPricingprobConss(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar)
Definition: relax_gcg.c:1762
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_RETCODE GCGcreateConsOrigbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
int GCGgetNTransvars(SCIP *scip)
Definition: relax_gcg.c:5033
SCIP_Real GCGgetPricingprobsMemUsed(SCIP *scip)
Definition: relax_gcg.c:4877
SCIP_Real pricingprobsmemused
Definition: relax_gcg.c:109
static SCIP_RETCODE initRelaxator(SCIP *scip, SCIP_RELAX *relax)
Definition: relax_gcg.c:2410
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:133
SCIP_Bool GCGoriginalVarIsTransVar(SCIP_VAR *var)
Definition: gcgvar.c:191
static SCIP_RETCODE setOriginalVarBlockNr(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_VAR *var, int newblock)
Definition: relax_gcg.c:170
SCIP_CONS ** GCGgetMasterConss(SCIP *scip)
Definition: relax_gcg.c:4011
#define GCG_DECL_BRANCHACTIVEMASTER(x)
DEC_DECOMP * decdecomp
Definition: relax_gcg.c:153
SCIP_RETCODE GCGrelaxStartProbing(SCIP *scip, SCIP_HEUR *probingheur)
Definition: relax_gcg.c:4174
SCIP_Longint simplexiters
Definition: relax_gcg.c:157
static SCIP_RETCODE setPricingProblemParameters(SCIP *scip, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastol, SCIP_Real dualfeastol, SCIP_Bool enableppcuts)
Definition: relax_gcg.c:1036
void GCGoriginalVarSetPricingVar(SCIP_VAR *var, SCIP_VAR *pricingvar)
Definition: gcgvar.c:224
SCIP_CONS ** GCGgetVarLinkingconss(SCIP *scip)
Definition: relax_gcg.c:4957
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
SCIP_RETCODE GCGrelaxNewProbingnodeOrig(SCIP *scip)
Definition: relax_gcg.c:4241
DEC_DECMODE GCGgetDecompositionMode(SCIP *scip)
Definition: relax_gcg.c:5075
SCIP_RETCODE GCGrelaxBranchDeactiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3530
static SCIP_RETCODE markConsMaster(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_CONS *cons)
Definition: relax_gcg.c:214
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss)
#define GCG_DECL_BRANCHDEACTIVEMASTER(x)
SCIP_CONS ** origmasterconss
Definition: relax_gcg.c:116
SCIP_Longint lastsolvednodenr
Definition: relax_gcg.c:131
SCIP_RETCODE SCIPconshdlrDecompCreateVarmapForSeeedId(SCIP *scip, SCIP_HASHMAP **hashorig2pricingvar, int seeedid, int probnr1, int probnr2, SCIP *scip1, SCIP *scip2, SCIP_HASHMAP *varmap)
for two identical pricing problems a corresponding varmap is created
constraint handler for storing the branching decisions at each node of the tree
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:846
SCIP_RETCODE GCGmasterCreateInitialMastervars(SCIP *scip)
SCIP_RETCODE GCGoriginalVarCreatePricingVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR **var)
Definition: gcgvar.c:1113
int * DECdecompGetNSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:828
static SCIP_RETCODE convertStructToGCG(SCIP *scip, SCIP_RELAXDATA *relaxdata, DEC_DECOMP *decdecomp)
Definition: relax_gcg.c:253
void GCGlinkingVarSetLinkingCons(SCIP_VAR *var, SCIP_CONS *cons, int index)
Definition: gcgvar.c:771
static SCIP_RETCODE combineSolutions(SCIP *scip, SCIP_SOL **newsol, SCIP **probs, int nprobs)
Definition: relax_gcg.c:2028
SCIP_RETCODE GCGrelaxBranchMasterSolved(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_Real newlowerbound)
Definition: relax_gcg.c:3655
SCIP * masterprob
Definition: relax_gcg.c:98
SCIP_Bool GCGgetConsIsSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_SETPPCTYPE *setppctype)
Definition: scip_misc.c:762
int maxmasterconss
Definition: relax_gcg.c:122
SCIP_RETCODE DECcreateBasicDecomp(SCIP *scip, DEC_DECOMP **decomp, SCIP_Bool solveorigprob)
Definition: decomp.c:2361
SCIP_RETCODE GCGoriginalVarAddMasterVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR *var, SCIP_Real val)
Definition: gcgvar.c:1021
SCIP_RETCODE GCGrelaxIncludeBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)), GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)), GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)), GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)), GCG_DECL_BRANCHDATADELETE((*branchdatadelete)))
Definition: relax_gcg.c:3451
SCIP_CONS ** linearmasterconss
Definition: relax_gcg.c:118
static SCIP_RETCODE checkIdentical(SCIP *scip, SCIP_RELAXDATA *relaxdata, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical, SCIP *scip1, SCIP *scip2)
Definition: relax_gcg.c:613
#define GCG_DECL_BRANCHPROPMASTER(x)
static SCIP_RETCODE pricingprobsAreIdenticalFromDetectionInfo(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_HASHMAP **hashorig2pricingvar, int probnr1, int probnr2, SCIP_HASHMAP *varmap, SCIP_Bool *identical)
Definition: relax_gcg.c:786
#define RELAX_DESC
Definition: relax_gcg.c:76
static SCIP_RETCODE solveMasterProblemAndEvaluate(SCIP *scip, SCIP_RELAX *relax, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax_gcg.c:3154
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:545
constraint handler for storing the branching decisions at each node of the tree
static SCIP_RETCODE solveDiagonalBlocks(SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_RESULT *result, SCIP_Real *lowerbound)
Definition: relax_gcg.c:2313
SCIP_RETCODE GCGlinkingVarCreatePricingVar(SCIP *pricingscip, int pricingprobnr, SCIP_VAR *origvar, SCIP_VAR **var)
Definition: gcgvar.c:1150
static SCIP_RETCODE createPricingVar(SCIP_RELAXDATA *relaxdata, SCIP_VAR *origvar)
Definition: relax_gcg.c:1132
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:866
static void initRelaxdata(SCIP_RELAXDATA *relaxdata)
Definition: relax_gcg.c:2620
SCIP_SOL * GCGgetBendersRelaxationSol(SCIP *scip)
Definition: relax_gcg.c:5052
SCIP * GCGgetOriginalprob(SCIP *masterprob)
Definition: relax_gcg.c:3801
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:561
#define DEFAULT_MODE
Definition: relax_gcg.c:84
int * nblocksidentical
Definition: relax_gcg.c:104
static SCIP_RETCODE checkAndAddExternalBranchingCandidate(SCIP *scip, SCIP_VAR *var)
Definition: relax_gcg.c:4619
SCIP_CONS ** GCGoriginalVarGetMasterconss(SCIP_VAR *var)
Definition: gcgvar.c:677
int SCIPconshdlrDecompGetNFormerDetectionConssForID(SCIP *scip, int id)
returns the number of constraints that were active while detecting the decomposition originating from...
SCIP_CONS ** markedmasterconss
Definition: relax_gcg.c:129
constraint handler for structure detection
SCIP_RETCODE GCGmasterAddMasterconsToHashmap(SCIP *scip, SCIP_CONS *cons, int pos)
SCIP_Bool storedfeasibility
Definition: relax_gcg.c:150
SCIP_Bool aggregation
Definition: relax_gcg.c:139
SCIP_RETCODE GCGrelaxBranchPropMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_RESULT *result)
Definition: relax_gcg.c:3568
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3897
int GCGgetBlockRepresentative(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3941
#define DEFAULT_DISCRETIZATION
Definition: relax_gcg.c:81
SCIP_Bool GCGmasterIsCurrentSolValid(SCIP *scip)
SCIP_CONS ** convconss
Definition: relax_gcg.c:105
const char * GCGgetFilename(SCIP *scip)
Definition: relax_gcg.c:4850
SCIP_RETCODE GCGrelaxEndProbing(SCIP *scip)
Definition: relax_gcg.c:4512
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:206
static SCIP_RETCODE createMasterProblem(SCIP *masterscip, const char *name, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastol, SCIP_Real dualfeastol, DEC_DECMODE mode)
Definition: relax_gcg.c:1458
DEC_DECMODE mode
Definition: relax_gcg.c:143
SCIP_RETCODE GCGrelaxBranchActiveMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata)
Definition: relax_gcg.c:3492
SCIP_RETCODE DECdecompAddRemainingConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2154
int * GCGgetVarLinkingconssBlock(SCIP *scip)
Definition: relax_gcg.c:4976
SCIP_RETCODE GCGrelaxNewProbingnodeMaster(SCIP *scip)
Definition: relax_gcg.c:4288
SCIP_HEUR * GCGrelaxGetProbingheur(SCIP *scip)
Definition: relax_gcg.c:4219
static SCIP_RETCODE solveBlockProblem(SCIP *scip, SCIP *blockprob, SCIP_RELAXDATA *relaxdata, SCIP_Real timelimit, int blocknum, SCIP_RESULT *result, SCIP_Real *objvalue)
Definition: relax_gcg.c:2148
SCIP_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:124
SCIP_RETCODE GCGpricingVarAddOrigVar(SCIP *scip, SCIP_VAR *pricingvar, SCIP_VAR *origvar)
Definition: gcgvar.c:508
SCIP_RETCODE GCGincludeMasterPlugins(SCIP *scip)