decomp.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-2017 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 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include "decomp.h"
40 #include "gcg.h"
41 #include "cons_decomp.h"
42 #include "scip/scip.h"
43 #include "struct_decomp.h"
44 #include "scip_misc.h"
45 #include "relax_gcg.h"
46 
47 #include <assert.h>
48 
49 typedef struct {
50  SCIP_Real mean;
51  SCIP_Real median;
52  SCIP_Real max;
53  SCIP_Real min;
55 
56 #define ELEM_SWAP(a,b) { register SCIP_Real t=(a);(a)=(b);(b)=t; }
57 
58 static
59 SCIP_Real quick_select_median(SCIP_Real arr[], int n)
60 {
61  int low, high;
62  int median;
63 
64  low = 0;
65  high = n - 1;
66  median = high / 2;
67 
68  for( ;; )
69  {
70  int middle, ll, hh;
71  if( high <= low ) /* One element only */
72  return arr[median];
73 
74  if( high == low + 1 ) /* Two elements only */
75  {
76  if( arr[low] > arr[high] )
77  ELEM_SWAP(arr[low], arr[high]);
78  return arr[median];
79  }
80 
81  /* Find median of low, middle and high items; swap into position low */
82  middle = (low + high) / 2;
83  if( arr[middle] > arr[high] )
84  ELEM_SWAP(arr[middle], arr[high]);
85  if( arr[low] > arr[high] )
86  ELEM_SWAP(arr[low], arr[high]);
87  if( arr[middle] > arr[low] )
88  ELEM_SWAP(arr[middle], arr[low]);
89  /* Swap low item (now in position middle) into position (low+1) */
90  ELEM_SWAP(arr[middle], arr[(size_t) (low + 1)]);
91  /* Nibble from each end towards middle, swapping items when stuck */
92  ll = low + 1;
93  hh = high;
94  for( ;; )
95  {
96  do
97  ll++;
98  while( arr[low] > arr[ll] );
99  do
100  hh--;
101  while( arr[hh] > arr[low] );
102  if( hh < ll )
103  break;
104  ELEM_SWAP(arr[ll], arr[hh]);
105  }
106  /* Swap middle item (in position low) back into correct position */
107  ELEM_SWAP(arr[low], arr[hh]);
108 
109  /* Re-set active partition */
110  if( hh <= median )
111  low = ll;
112  if( hh >= median )
113  high = hh - 1;
114  }
115 }
116 
117 
119 static
121  SCIP* scip,
122  DEC_DECOMP* decomp,
123  SCIP_HASHMAP* vartoblock,
124  int nblocks,
125  SCIP_VAR** vars,
126  int nvars,
127  SCIP_Bool* haslinking
128  )
129 {
130  SCIP_VAR*** subscipvars;
131  int* nsubscipvars;
132 
133  SCIP_VAR** linkingvars;
134  int nlinkingvars;
135  int i;
136 
137  assert(scip != NULL);
138  assert(decomp != NULL);
139  assert(vartoblock != NULL);
140  assert(nblocks >= 0);
141  assert(vars != NULL);
142  assert(nvars > 0);
143 
144  SCIP_CALL( SCIPallocBufferArray(scip, &linkingvars, nvars) );
145  SCIP_CALL( SCIPallocBufferArray(scip, &nsubscipvars, nblocks) );
146  SCIP_CALL( SCIPallocBufferArray(scip, &subscipvars, nblocks) );
147 
148  nlinkingvars = 0;
149 
150  *haslinking = FALSE;
151 
152  for( i = 0; i < nblocks; ++i )
153  {
154  SCIP_CALL( SCIPallocBufferArray(scip, &subscipvars[i], nvars) ); /*lint !e866*/
155  nsubscipvars[i] = 0;
156  }
157 
158  /* handle variables */
159  for( i = 0; i < nvars; ++i )
160  {
161  int block;
162  SCIP_VAR* var;
163 
164  var = vars[i];
165  assert(var != NULL);
166  assert(SCIPvarIsActive(var));
167 
168  if( !SCIPhashmapExists(vartoblock, var) )
169  block = nblocks+1;
170  else
171  {
172  block = (int)(size_t)SCIPhashmapGetImage(vartoblock, var); /*lint !e507*/
173  }
174 
175  assert(block > 0 && block <= nblocks+2);
176 
177  /* if variable belongs to a block */
178  if( block <= nblocks )
179  {
180  SCIPdebugMessage("var %s in block %d.\n", SCIPvarGetName(var), block-1);
181  subscipvars[block-1][nsubscipvars[block-1]] = var;
182  ++(nsubscipvars[block-1]);
183  }
184  else /* variable is linking or master*/
185  {
186  assert(block == nblocks+1 || block == nblocks+2 );
187 
188  if( block == nblocks+2 )
189  SCIPdebugMessage("var %s is linking.\n", SCIPvarGetName(var));
190  else
191  SCIPdebugMessage("var %s is in master only.\n", SCIPvarGetName(var));
192 
193  linkingvars[nlinkingvars] = var;
194  ++nlinkingvars;
195  }
196  }
197 
198  if( nlinkingvars > 0 )
199  {
200  SCIP_CALL( DECdecompSetLinkingvars(scip, decomp, linkingvars, nlinkingvars) );
201  *haslinking = TRUE;
202  }
203 
204  for( i = nblocks-1; i >= 0; --i )
205  {
206  if( nsubscipvars[i] == 0 )
207  {
208  SCIPfreeBufferArray(scip, &subscipvars[i]);
209  subscipvars[i] = NULL;
210  }
211  }
212  if( nblocks > 0 )
213  {
214  SCIP_CALL( DECdecompSetSubscipvars(scip, decomp, subscipvars, nsubscipvars) );
215  }
216  DECdecompSetVartoblock(decomp, vartoblock);
217 
218  for( i = nblocks-1; i >= 0; --i )
219  {
220  SCIPfreeBufferArrayNull(scip, &subscipvars[i]);
221  }
222 
223  SCIPfreeBufferArray(scip, &subscipvars);
224  SCIPfreeBufferArray(scip, &nsubscipvars);
225  SCIPfreeBufferArray(scip, &linkingvars);
226 
227  return SCIP_OKAY;
228 }
229 
230 
232 static
234  SCIP* scip,
235  DEC_DECOMP* decomp,
236  SCIP_HASHMAP* constoblock,
237  int nblocks,
238  SCIP_CONS** conss,
239  int nconss,
240  SCIP_Bool* haslinking
241  )
242 {
243  SCIP_RETCODE retcode;
244 
245  SCIP_CONS*** subscipconss;
246  int* nsubscipconss;
247 
248  SCIP_CONS** linkingconss;
249  int nlinkingconss;
250  int i;
251  assert(scip != NULL);
252  assert(decomp != NULL);
253  assert(constoblock != NULL);
254  assert(nblocks >= 0);
255  assert(conss != NULL);
256  assert(nconss > 0);
257  assert(haslinking != NULL);
258 
259  DECdecompSetConstoblock(decomp, constoblock);
260 
261  SCIP_CALL( SCIPallocBufferArray(scip, &linkingconss, nconss) );
262  SCIP_CALL( SCIPallocBufferArray(scip, &nsubscipconss, nblocks) );
263  SCIP_CALL( SCIPallocBufferArray(scip, &subscipconss, nblocks) );
264 
265  *haslinking = FALSE;
266  retcode = SCIP_OKAY;
267  for( i = 0; i < nblocks; ++i )
268  {
269  SCIP_CALL( SCIPallocBufferArray(scip, &subscipconss[i], nconss) ); /*lint !e866*/
270  nsubscipconss[i] = 0;
271  }
272 
273  nlinkingconss = 0;
274 
275  /* handle constraints */
276  for( i = 0; i < nconss; ++i )
277  {
278  int block;
279  SCIP_CONS* cons;
280  int nvars;
281  SCIP_Bool success;
282 
283  cons = conss[i];
284  assert(cons != NULL);
285 
286  if( !SCIPhashmapExists(decomp->constoblock, cons) )
287  {
288  block = nblocks+1;
289  SCIP_CALL( SCIPhashmapInsert(decomp->constoblock, cons, (void*) (size_t) block) );
290  }
291  else
292  {
293  block = (int)(size_t)SCIPhashmapGetImage(decomp->constoblock, cons); /*lint !e507*/
294  }
295 
296  assert(block > 0 && block <= nblocks+1);
297 
298  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) );
299  assert(success);
300  if( nvars == 0 )
301  continue;
302 
303  /* if constraint belongs to a block */
304  if( block <= nblocks )
305  {
306  SCIPdebugMessage("cons %s in block %d.\n", SCIPconsGetName(cons), block-1);
307  subscipconss[block-1][nsubscipconss[block-1]] = cons;
308  ++(nsubscipconss[block-1]);
309  }
310  else /* constraint is linking */
311  {
312  SCIPdebugMessage("cons %s is linking.\n", SCIPconsGetName(cons));
313  assert(block == nblocks+1);
314  linkingconss[nlinkingconss] = cons;
315  ++nlinkingconss;
316  }
317  }
318 
319  if( nlinkingconss > 0 )
320  {
321  retcode = DECdecompSetLinkingconss(scip, decomp, linkingconss, nlinkingconss);
322  *haslinking = TRUE;
323  }
324  if( nblocks > 0 )
325  {
326  retcode = DECdecompSetSubscipconss(scip, decomp, subscipconss, nsubscipconss);
327  }
328 
329  for( i = nblocks-1; i >= 0; --i )
330  {
331  SCIPfreeBufferArray(scip, &subscipconss[i]);
332  }
333 
334  SCIPfreeBufferArray(scip, &subscipconss);
335  SCIPfreeBufferArray(scip, &nsubscipconss);
336  SCIPfreeBufferArray(scip, &linkingconss);
337 
338  return retcode;
339 }
340 
341 
342 const char *DECgetStrType(
343  DEC_DECTYPE type
344  )
345 {
346  const char * names[] = { "unknown", "arrowhead", "staircase", "diagonal", "bordered" };
347  return names[type];
348 }
349 
351 SCIP_RETCODE DECdecompCreate(
352  SCIP* scip,
353  DEC_DECOMP** decdecomp
354  )
355 {
356  DEC_DECOMP* decomp;
357 
358  assert(scip != NULL);
359  assert(decdecomp != NULL);
360 
361  SCIP_CALL( SCIPallocMemory(scip, decdecomp) );
362  assert(*decdecomp != NULL);
363  decomp = *decdecomp;
364 
365  decomp->type = DEC_DECTYPE_UNKNOWN;
366  decomp->constoblock = NULL;
367  decomp->vartoblock = NULL;
368  decomp->subscipvars = NULL;
369  decomp->subscipconss = NULL;
370  decomp->nsubscipconss = NULL;
371  decomp->nsubscipvars = NULL;
372  decomp->linkingconss = NULL;
373  decomp->nlinkingconss = 0;
374  decomp->linkingvars = NULL;
375  decomp->nlinkingvars = 0;
376  decomp->stairlinkingvars = NULL;
377  decomp->nstairlinkingvars = NULL;
378  decomp->nblocks = 0;
379  decomp->presolved = (SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVING);
380  decomp->consindex = NULL;
381  decomp->varindex = NULL;
382  decomp->detector = NULL;
383 
384  return SCIP_OKAY;
385 }
386 
388 SCIP_RETCODE DECdecompFree(
389  SCIP* scip,
390  DEC_DECOMP** decdecomp
391  )
392 {
393  DEC_DECOMP* decomp;
394  int i;
395  int j;
396 
397  assert( scip!= NULL );
398  assert( decdecomp != NULL);
399  decomp = *decdecomp;
400 
401  assert(decomp != NULL);
402 
403  for( i = 0; i < decomp->nblocks; ++i )
404  {
405  if( decomp->nsubscipvars != NULL )
406  {
407  for( j = 0; j < decomp->nsubscipvars[i]; ++j )
408  {
409  if( decomp->subscipvars[i][j] != NULL )
410  {
411  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->subscipvars[i][j])) );
412  }
413  }
414 
415  SCIPfreeBlockMemoryArrayNull(scip, &(decomp->subscipvars[i]), SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[i])); /*lint !e866*/
416  }
417  if( decomp->nsubscipconss != NULL )
418  {
419  for( j = 0; j < decomp->nsubscipconss[i]; ++j )
420  {
421  if( decomp->subscipconss[i][j] != NULL )
422  {
423  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->subscipconss[i][j])) );
424  }
425  }
426  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipconss[i], SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[i])); /*lint !e866*/
427  }
428  }
429 
430  if( decomp->linkingvars != NULL )
431  {
432  for( i = 0; i < decomp->nlinkingvars; ++i )
433  {
434  if( decomp->linkingvars[i] != NULL )
435  {
436  if( decomp->linkingvars[i] != NULL )
437  {
438  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->linkingvars[i])) );
439  }
440  }
441  }
442  }
443 
444  if( decomp->stairlinkingvars != NULL )
445  for( i = 0; i < decomp->nblocks-1; ++i )
446  {
447  for( j = 0; j < decomp->nstairlinkingvars[i]; ++j )
448  {
449  if( decomp->stairlinkingvars[i][j] != NULL )
450  {
451  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->stairlinkingvars[i][j])) );
452  }
453  }
454  SCIPfreeBlockMemoryArrayNull(scip, &decomp->stairlinkingvars[i], SCIPcalcMemGrowSize(scip, decomp->nstairlinkingvars[i])); /*lint !e866*/
455  }
456 
457  /* free hashmaps if they are not NULL */
458  if( decomp->constoblock != NULL )
459  SCIPhashmapFree(&decomp->constoblock);
460  if( decomp->vartoblock != NULL )
461  SCIPhashmapFree(&decomp->vartoblock);
462  if( decomp->varindex != NULL )
463  SCIPhashmapFree(&decomp->varindex);
464  if( decomp->consindex != NULL )
465  SCIPhashmapFree(&decomp->consindex);
466 
467  for( i = 0; i < decomp->nlinkingconss; ++i )
468  {
469  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->linkingconss[i])) );
470  }
471  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipvars, decomp->nblocks);
472  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nsubscipvars, decomp->nblocks);
473  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipconss, decomp->nblocks);
474  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nsubscipconss, decomp->nblocks);
475  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingvars, SCIPcalcMemGrowSize(scip, decomp->nlinkingvars));
476  SCIPfreeBlockMemoryArrayNull(scip, &decomp->stairlinkingvars, decomp->nblocks);
477  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nstairlinkingvars,decomp->nblocks);
478  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingconss, SCIPcalcMemGrowSize(scip, decomp->nlinkingconss));
479  SCIPfreeMemoryNull(scip, decdecomp);
480 
481  return SCIP_OKAY;
482 }
483 
485 SCIP_RETCODE DECdecompSetType(
486  DEC_DECOMP* decomp,
487  DEC_DECTYPE type
488  )
489 {
490  SCIP_Bool valid;
491 
492  assert(decomp != NULL);
493 
494  switch( type )
495  {
497  valid = decomp->nlinkingconss == 0 && decomp->linkingconss == NULL;
498  valid = valid && decomp->nlinkingvars == 0 && decomp->linkingvars == NULL;
499  break;
501  valid = TRUE;
502  break;
503  case DEC_DECTYPE_UNKNOWN:
504  valid = FALSE;
505  break;
507  valid = decomp->nlinkingvars == 0 && decomp->linkingvars == NULL;
508  break;
510  valid = decomp->nlinkingconss == 0 && decomp->linkingconss == NULL;
511  break;
512  default:
513  valid = FALSE;
514  break;
515  }
516 
517  if( !valid )
518  {
519  SCIPerrorMessage("The decomposition is not of the given type!\n");
520  return SCIP_INVALIDDATA;
521  }
522 
523  decomp->type = type;
524 
525  return SCIP_OKAY;
526 }
527 
530  DEC_DECOMP* decomp
531  )
532 {
533  assert(decomp != NULL);
534 
535  return decomp->type;
536 }
537 
540  DEC_DECOMP* decomp,
541  SCIP_Bool presolved
542  )
543 {
544  assert(decomp != NULL);
545 
546  decomp->presolved = presolved;
547 }
548 
551  DEC_DECOMP* decomp
552  )
553 {
554  assert(decomp != NULL);
555 
556  return decomp->presolved;
557 }
558 
561  DEC_DECOMP* decomp,
562  int nblocks
563  )
564 {
565  assert(decomp != NULL);
566  assert(nblocks >= 0);
567 
568  decomp->nblocks = nblocks;
569 }
570 
573  DEC_DECOMP* decomp
574  )
575 {
576  assert(decomp != NULL);
577 
578  return decomp->nblocks;
579 }
580 
583  SCIP* scip,
584  DEC_DECOMP* decomp,
585  SCIP_VAR*** subscipvars,
586  int* nsubscipvars
587  )
588 {
589  SCIP_Bool valid;
590  int i;
591  int b;
592  assert(scip != NULL);
593  assert(decomp != NULL);
594  assert(subscipvars != NULL);
595  assert(nsubscipvars != NULL);
596  assert(decomp->nblocks > 0);
597 
598  assert(decomp->subscipvars == NULL);
599  assert(decomp->nsubscipvars == NULL);
600 
601  valid = TRUE;
602 
603  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipvars, decomp->nblocks) );
604  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nsubscipvars, decomp->nblocks) );
605 
606  assert(decomp->subscipvars != NULL);
607  assert(decomp->nsubscipvars != NULL);
608 
609  BMSclearMemoryArray(decomp->subscipvars, decomp->nblocks);
610  BMSclearMemoryArray(decomp->nsubscipvars, decomp->nblocks);
611 
612  for( b = 0; b < decomp->nblocks; ++b )
613  {
614  assert((subscipvars[b] == NULL) == (nsubscipvars[b] == 0));
615  decomp->nsubscipvars[b] = nsubscipvars[b];
616 
617  if( nsubscipvars[b] < 0 )
618  {
619  SCIPerrorMessage("Number of variables per subproblem must be nonnegative.\n");
620  valid = FALSE;
621  }
622  else if( nsubscipvars[b] > 0 )
623  {
624  int size;
625  assert(subscipvars[b] != NULL);
626  size = SCIPcalcMemGrowSize(scip, nsubscipvars[b]);
627  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipvars[b], size) ); /*lint !e866*/
628  BMScopyMemoryArray(decomp->subscipvars[b],subscipvars[b], nsubscipvars[b]); /*lint !e866*/
629 
630  for( i = 0; i < nsubscipvars[b]; ++i )
631  {
632  SCIP_CALL( SCIPcaptureVar(scip, decomp->subscipvars[b][i]) );
633  }
634  }
635  }
636 
637  if( !valid )
638  {
639  return SCIP_INVALIDDATA;
640  }
641 
642 
643  return SCIP_OKAY;
644 }
645 
648  DEC_DECOMP* decomp
649  )
650 {
651  assert(decomp != NULL);
652 
653  return decomp->subscipvars;
654 }
655 
658  DEC_DECOMP* decomp
659  )
660 {
661  assert(decomp != NULL);
662 
663  return decomp->nsubscipvars;
664 }
665 
668  SCIP* scip,
669  DEC_DECOMP* decomp,
670  SCIP_CONS*** subscipconss,
671  int* nsubscipconss
672  )
673 {
674  SCIP_Bool valid;
675  int i;
676  int b;
677  assert(scip != NULL);
678  assert(decomp != NULL);
679  assert(subscipconss != NULL);
680  assert(nsubscipconss != NULL);
681 
682  assert(decomp->nblocks > 0);
683  assert(decomp->subscipconss == NULL);
684  assert(decomp->nsubscipconss == NULL);
685 
686  valid = TRUE;
687 
688  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipconss, decomp->nblocks) );
689  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nsubscipconss, decomp->nblocks) );
690 
691  assert(decomp->subscipconss != NULL);
692  assert(decomp->nsubscipconss != NULL);
693 
694  BMSclearMemoryArray(decomp->subscipconss, decomp->nblocks);
695  BMSclearMemoryArray(decomp->nsubscipconss, decomp->nblocks);
696 
697  for( b = 0; b < decomp->nblocks; ++b )
698  {
699  if( nsubscipconss[b] <= 0 || subscipconss[b] == NULL )
700  {
701  SCIPerrorMessage("Block %d is empty and thus invalid. Each block needs at least one constraint.\n", b);
702  valid = FALSE;
703  }
704 
705  decomp->nsubscipconss[b] = nsubscipconss[b];
706 
707  if( nsubscipconss[b] > 0 )
708  {
709  int size;
710 
711  assert(subscipconss[b] != NULL);
712  size = SCIPcalcMemGrowSize(scip, nsubscipconss[b]);
713  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipconss[b], size) ); /*lint !e866*/
714  BMScopyMemoryArray(decomp->subscipconss[b], subscipconss[b], nsubscipconss[b]); /*lint !e866*/
715  for( i = 0; i < nsubscipconss[b]; ++i )
716  {
717  SCIP_CALL( SCIPcaptureCons(scip, decomp->subscipconss[b][i]) );
718  }
719  }
720  }
721 
722  if( !valid )
723  return SCIP_INVALIDDATA;
724 
725  return SCIP_OKAY;
726 }
727 
730  DEC_DECOMP* decomp
731  )
732 {
733  assert(decomp != NULL);
734  return decomp->subscipconss;
735 }
736 
739  DEC_DECOMP* decomp
740  )
741 {
742  assert(decomp != NULL);
743  return decomp->nsubscipconss;
744 }
745 
748  SCIP* scip,
749  DEC_DECOMP* decomp,
750  SCIP_CONS** linkingconss,
751  int nlinkingconss
752  )
753 {
754  assert(scip != NULL);
755  assert(decomp != NULL);
756  assert(linkingconss != NULL);
757  assert(nlinkingconss >= 0);
758 
759  assert(decomp->linkingconss == NULL);
760  assert(decomp->nlinkingconss == 0);
761 
762  decomp->nlinkingconss = nlinkingconss;
763 
764  if( nlinkingconss > 0 )
765  {
766  int i;
767  int size;
768  assert(linkingconss != NULL);
769  size = SCIPcalcMemGrowSize(scip, nlinkingconss);
770  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->linkingconss, size) );
771  BMScopyMemoryArray(decomp->linkingconss, linkingconss, nlinkingconss);
772 
773  for( i = 0; i < nlinkingconss; ++i )
774  {
775  SCIP_CALL( SCIPcaptureCons(scip, decomp->linkingconss[i]) );
776  }
777  }
778 
779  if( (linkingconss == NULL) != (nlinkingconss == 0) )
780  {
781  SCIPerrorMessage("Number of linking constraints and linking constraint array are inconsistent.\n");
782  return SCIP_INVALIDDATA;
783  }
784  return SCIP_OKAY;
785 }
786 
789  DEC_DECOMP* decomp
790  )
791 {
792  assert(decomp != NULL);
793 
794  return decomp->linkingconss;
795 }
796 
799  DEC_DECOMP* decomp
800  )
801 {
802  assert(decomp != NULL);
803  assert(decomp->nlinkingconss >= 0);
804 
805  return decomp->nlinkingconss;
806 }
807 
808 
811  SCIP* scip,
812  DEC_DECOMP* decomp,
813  SCIP_VAR** linkingvars,
814  int nlinkingvars
815  )
816 {
817  assert(scip != NULL);
818  assert(decomp != NULL);
819  assert(linkingvars != NULL || nlinkingvars == 0);
820 
821  assert(decomp->linkingvars == NULL);
822  assert(decomp->nlinkingvars == 0);
823 
824  decomp->nlinkingvars = nlinkingvars;
825 
826  if( nlinkingvars > 0 )
827  {
828  int i;
829  int size;
830  assert(linkingvars != NULL);
831  size = SCIPcalcMemGrowSize(scip, nlinkingvars);
832  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->linkingvars, size) );
833  BMScopyMemoryArray(decomp->linkingvars, linkingvars, nlinkingvars);
834 
835  for( i = 0; i < nlinkingvars; ++i )
836  {
837  SCIP_CALL( SCIPcaptureVar(scip, decomp->linkingvars[i]) );
838  }
839  }
840 
841  if( (linkingvars == NULL) != (nlinkingvars == 0) )
842  {
843  SCIPerrorMessage("Number of linking variables and linking variable array are inconsistent.\n");
844  return SCIP_INVALIDDATA;
845  }
846 
847  return SCIP_OKAY;
848 }
849 
852  DEC_DECOMP* decomp
853  )
854 {
855  assert(decomp != NULL);
856 
857  return decomp->linkingvars;
858 }
859 
862  DEC_DECOMP* decomp
863  )
864 {
865  assert(decomp != NULL);
866  assert(decomp->nlinkingvars >= 0);
867 
868  return decomp->nlinkingvars;
869 }
870 
873  SCIP* scip,
874  DEC_DECOMP* decomp,
875  SCIP_VAR*** stairlinkingvars,
876  int* nstairlinkingvars
877  )
878 {
879  SCIP_Bool valid;
880  int b;
881  int i;
882  assert(scip != NULL);
883  assert(decomp != NULL);
884  assert(stairlinkingvars != NULL);
885  assert(nstairlinkingvars != NULL);
886 
887  assert(decomp->nblocks > 0);
888 
889  assert(decomp->stairlinkingvars == NULL);
890  assert(decomp->nstairlinkingvars == NULL);
891 
892  valid = TRUE;
894  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->stairlinkingvars, decomp->nblocks) ); /* this is more efficient */
895  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nstairlinkingvars, decomp->nblocks) ); /* this is more efficient */
896 
897  assert(decomp->stairlinkingvars != NULL);
898  assert(decomp->nstairlinkingvars != NULL);
899 
900  BMSclearMemoryArray(decomp->stairlinkingvars, decomp->nblocks-1);
901  BMSclearMemoryArray(decomp->nstairlinkingvars, decomp->nblocks-1);
902 
903  for( b = 0; b < decomp->nblocks-1; ++b )
904  {
905  assert(nstairlinkingvars[b] > 0 || stairlinkingvars[b] == NULL);
906  decomp->nstairlinkingvars[b] = nstairlinkingvars[b];
907  if( stairlinkingvars[b] != NULL )
908  {
909  int size = SCIPcalcMemGrowSize(scip, nstairlinkingvars[b]);
910  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(decomp->stairlinkingvars[b]), size) ); /*lint !e866 */
911  BMScopyMemoryArray(decomp->stairlinkingvars[b], stairlinkingvars[b], nstairlinkingvars[b]); /*lint !e866 */
912  }
913  else
914  {
915  decomp->stairlinkingvars[b] = NULL;
916  }
917  }
918 
919  for( b = 0; b < decomp->nblocks-1; ++b )
920  {
921  for( i = 0; i < nstairlinkingvars[b]; ++i )
922  {
923  assert(stairlinkingvars[b] != NULL);
924  SCIP_CALL( SCIPcaptureVar(scip, decomp->stairlinkingvars[b][i]) );
925  }
926  }
927  if( !valid ) /*lint !e774 it is always true, see above */
928  {
929  SCIPerrorMessage("The staircase linking variables are inconsistent.\n");
930  return SCIP_INVALIDDATA;
931  }
932  return SCIP_OKAY;
933 }
934 
937  DEC_DECOMP* decomp
938  )
939 {
940  assert(decomp != NULL);
941  return decomp->stairlinkingvars;
942 }
943 
946  DEC_DECOMP* decomp
947  )
948 {
949  assert(decomp != NULL);
950  assert(decomp->nstairlinkingvars != NULL );
951  return decomp->nstairlinkingvars;
952 }
953 
956  DEC_DECOMP* decomp,
957  SCIP_HASHMAP* vartoblock
958  )
959 {
960  assert(decomp != NULL);
961  assert(vartoblock != NULL);
962 
963  decomp->vartoblock = vartoblock;
964 }
965 
968  DEC_DECOMP* decomp
969  )
970 {
971  assert(decomp != NULL);
972 
973  return decomp->vartoblock;
974 }
975 
978  DEC_DECOMP* decomp,
979  SCIP_HASHMAP* constoblock
980  )
981 {
982  assert(decomp != NULL);
983  assert(constoblock != NULL);
984 
985  decomp->constoblock = constoblock;
986 }
987 
990  DEC_DECOMP* decomp
991  )
992 {
993  assert(decomp != NULL);
994 
995  return decomp->constoblock;
996 }
997 
1000  DEC_DECOMP* decomp,
1001  SCIP_HASHMAP* varindex
1002  )
1003 {
1004  assert(decomp != NULL);
1005  assert(varindex != NULL);
1006  decomp->varindex = varindex;
1007 }
1008 
1010 SCIP_HASHMAP* DECdecompGetVarindex(
1011  DEC_DECOMP* decomp
1012  )
1013 {
1014  assert(decomp != NULL);
1015  return decomp->varindex;
1016 }
1017 
1020  DEC_DECOMP* decomp,
1021  SCIP_HASHMAP* consindex
1022  )
1023 {
1024  assert(decomp != NULL);
1025  assert(consindex != NULL);
1026  decomp->consindex = consindex;
1027 }
1028 
1031  DEC_DECOMP* decomp
1032  )
1033 {
1034  assert(decomp != NULL);
1035  return decomp->consindex;
1036 }
1037 
1040  SCIP* scip,
1041  DEC_DECOMP* decomp,
1042  SCIP_HASHMAP* vartoblock,
1043  SCIP_HASHMAP* constoblock,
1044  int nblocks,
1045  SCIP_Bool staircase
1046  )
1047 {
1048  SCIP_HASHMAP* varindex;
1049  SCIP_HASHMAP* consindex;
1050  int* nsubscipconss;
1051  int* nsubscipvars;
1052  int* nstairlinkingvars;
1053  SCIP_VAR*** stairlinkingvars;
1054  SCIP_CONS*** subscipconss;
1055  SCIP_Bool success;
1056  int cindex;
1057  int cumindex;
1058  SCIP_Bool haslinking;
1059  int i;
1060  int b;
1061  SCIP_VAR** curvars;
1062  int ncurvars;
1063  int j;
1064 
1065  SCIP_VAR** vars;
1066  int nvars;
1067  SCIP_CONS** conss;
1068  int nconss;
1069 
1070  assert(scip != NULL);
1071  assert(decomp != NULL);
1072  assert(vartoblock != NULL);
1073  assert(constoblock != NULL);
1074  assert(nblocks >= 0);
1075 
1076  conss = SCIPgetConss(scip);
1077  nconss = SCIPgetNConss(scip);
1078  vars = SCIPgetVars(scip);
1079  nvars = SCIPgetNVars(scip);
1080 
1081  assert(vars != NULL);
1082  assert(nvars > 0);
1083  assert(conss != NULL);
1084  assert(nconss > 0);
1085 
1086  DECdecompSetNBlocks(decomp, nblocks);
1087 
1088  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_DIAGONAL) );
1089  SCIP_CALL_QUIET( fillOutConsFromConstoblock(scip, decomp, constoblock, nblocks, conss, nconss, &haslinking) );
1090 
1091  if( haslinking )
1092  {
1093  SCIPdebugMessage("Decomposition has linking constraints and is bordered.\n");
1094  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_BORDERED) );
1095  }
1096 
1097  SCIP_CALL( fillOutVarsFromVartoblock(scip, decomp, vartoblock, nblocks, vars, nvars, &haslinking) );
1098 
1099  if( haslinking )
1100  {
1101  SCIPdebugMessage("Decomposition has linking variables and is arrowhead.\n");
1102  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_ARROWHEAD) );
1103  }
1104 
1105  if( !staircase )
1106  {
1107  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
1108  return SCIP_OKAY;
1109  }
1110 
1111  SCIP_CALL( SCIPhashmapCreate(&varindex, SCIPblkmem(scip), nvars) );
1112  SCIP_CALL( SCIPhashmapCreate(&consindex, SCIPblkmem(scip), nconss) );
1113  SCIP_CALL( SCIPallocBufferArray(scip, &stairlinkingvars, nblocks) );
1114  SCIP_CALL( SCIPallocBufferArray(scip, &nstairlinkingvars, nblocks) );
1115 
1116  for( i = 0; i < nblocks; ++i )
1117  {
1118  SCIP_CALL( SCIPallocBufferArray(scip, &(stairlinkingvars[i]), nvars) ); /*lint !e866*/
1119  nstairlinkingvars[i] = 0;
1120  }
1121 
1122  nsubscipconss = DECdecompGetNSubscipconss(decomp);
1123  subscipconss = DECdecompGetSubscipconss(decomp);
1124  nsubscipvars = DECdecompGetNSubscipvars(decomp);
1125 
1126  cindex = 0;
1127  cumindex = 0;
1128 
1129  /* try to deduce staircase map */
1130  for( b = 0; b < nblocks; ++b )
1131  {
1132  int idx = 0;
1133  SCIPdebugMessage("block %d (%d vars):\n", b, nsubscipvars[b]);
1134 
1135  for( i = 0; i < nsubscipconss[b]; ++i )
1136  {
1137 
1138  int linkindex = 0;
1139  SCIP_CONS* cons = subscipconss[b][i];
1140 
1141  SCIP_CALL( SCIPhashmapInsert(consindex, cons, (void*)(size_t) (cindex+1)) );
1142  ++cindex;
1143  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
1144  assert(success);
1145 
1146  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1147 
1148  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
1149  assert(success);
1150 
1151  for( j = 0; j < ncurvars; ++j )
1152  {
1153  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[j]);
1154 
1155  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1156  continue;
1157 
1158  /* if the variable is linking */
1159  if( (int)(size_t)SCIPhashmapGetImage(vartoblock, probvar) >= nblocks+1 ) /*lint !e507*/
1160  {
1161  /* if it has not been already assigned, it links to the next block */
1162  if( !SCIPhashmapExists(varindex, probvar) )
1163  {
1164  int vindex = cumindex+nsubscipvars[b]+linkindex+1;
1165  SCIPdebugMessage("assigning link var <%s> to index <%d>\n", SCIPvarGetName(probvar), vindex);
1166  SCIP_CALL( SCIPhashmapInsert(varindex, probvar, (void*)(size_t)(vindex)) );
1167  stairlinkingvars[b][nstairlinkingvars[b]] = probvar;
1168  ++(nstairlinkingvars[b]);
1169  linkindex++;
1170  }
1171  }
1172  else
1173  {
1174  if( !SCIPhashmapExists(varindex, probvar) )
1175  {
1176  int vindex = cumindex+idx+1;
1177  assert(((int) (size_t) SCIPhashmapGetImage(vartoblock, probvar)) -1 == b); /*lint !e507*/
1178  SCIPdebugMessage("assigning block var <%s> to index <%d>\n", SCIPvarGetName(probvar), vindex);
1179  SCIP_CALL( SCIPhashmapInsert(varindex, probvar, (void*)(size_t)(vindex)) );
1180  ++idx;
1181  }
1182  }
1183  }
1184  SCIPfreeBufferArray(scip, &curvars);
1185  }
1186  if( b < nblocks-1 )
1187  {
1188  cumindex += nsubscipvars[b] + nstairlinkingvars[b];
1189  }
1190  }
1191 
1192  DECdecompSetVarindex(decomp, varindex);
1193  DECdecompSetConsindex(decomp, consindex);
1194  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_STAIRCASE) );
1195 
1196  for( b = nblocks-1; b >= 0; --b )
1197  {
1198  if( nstairlinkingvars[b] == 0 )
1199  {
1200  SCIPfreeBufferArrayNull(scip, &(stairlinkingvars[b]));
1201  }
1202  }
1203 
1204  SCIP_CALL( DECdecompSetStairlinkingvars(scip, decomp, stairlinkingvars, nstairlinkingvars) );
1205 
1206  for( b = nblocks-1; b >= 0; --b )
1207  {
1208  SCIPfreeBufferArrayNull(scip, &stairlinkingvars[b]);
1209  }
1210  SCIPfreeBufferArray(scip, &nstairlinkingvars);
1211  SCIPfreeBufferArray(scip, &stairlinkingvars);
1212 
1213  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
1214 
1215  return SCIP_OKAY;
1216 }
1217 
1226  SCIP* scip,
1227  DEC_DECOMP* decomp,
1228  SCIP_HASHMAP* constoblock,
1229  int nblocks,
1230  SCIP_Bool staircase
1231  )
1232 {
1233  SCIP_HASHMAP* vartoblock;
1234  int i;
1235  int j;
1236  SCIP_VAR** vars;
1237  int nvars;
1238  SCIP_CONS** conss;
1239  int nconss;
1240  SCIP_VAR** curvars;
1241  int ncurvars;
1242  SCIP_Bool success;
1243  SCIP_RETCODE retcode;
1244 
1245  assert(scip != NULL);
1246  assert(decomp != NULL);
1247  assert(constoblock != NULL);
1248  assert(nblocks >= 0);
1249 
1250  conss = SCIPgetConss(scip);
1251  nconss = SCIPgetNConss(scip);
1252  vars = SCIPgetVars(scip);
1253  nvars = SCIPgetNVars(scip);
1254 
1255  assert(vars != NULL);
1256  assert(nvars > 0);
1257  assert(conss != NULL);
1258  assert(nconss > 0);
1259 
1260  SCIP_CALL( SCIPhashmapCreate(&vartoblock, SCIPblkmem(scip), nvars) );
1261  for( i = 0; i < nconss; ++i )
1262  {
1263  int consblock;
1264 
1265  SCIP_CALL( SCIPgetConsNVars(scip, conss[i], &ncurvars, &success) );
1266  assert(success);
1267 
1268  if( ncurvars == 0 )
1269  continue;
1270 
1271  consblock = (int)(size_t)SCIPhashmapGetImage(constoblock, conss[i]); /*lint !e507*/
1272 
1273  assert(consblock > 0 && consblock <= nblocks+1);
1274  if( consblock == nblocks+1 )
1275  {
1276  SCIPdebugMessage("cons <%s> is linking and need not be handled\n", SCIPconsGetName(conss[i]));
1277  continue;
1278  }
1279 
1280  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1281 
1282  SCIP_CALL( SCIPgetConsVars(scip, conss[i], curvars, ncurvars, &success) );
1283  assert(success);
1284  SCIPdebugMessage("cons <%s> (%d vars) is in block %d.\n", SCIPconsGetName(conss[i]), ncurvars, consblock);
1285  assert(consblock <= nblocks);
1286 
1287  for( j = 0; j < ncurvars; ++j )
1288  {
1289  int varblock;
1290  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[j]);
1291 
1292  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1293  continue;
1294 
1295  assert(SCIPvarIsActive(probvar));
1296 
1297  if( SCIPhashmapExists(vartoblock, probvar) )
1298  varblock = (int) (size_t) SCIPhashmapGetImage(vartoblock, probvar); /*lint !e507*/
1299  else
1300  varblock = nblocks+1;
1301 
1302  /* The variable is currently in no block */
1303  if( varblock == nblocks+1 )
1304  {
1305  SCIPdebugMessage(" var <%s> not been handled before, adding to block %d\n", SCIPvarGetName(probvar), consblock);
1306  SCIP_CALL( SCIPhashmapSetImage(vartoblock, probvar, (void*) (size_t) consblock) );
1307  }
1308  /* The variable is already in a different block */
1309  else if( varblock != consblock )
1310  {
1311  assert(varblock <= nblocks || varblock == nblocks+2);
1312  SCIPdebugMessage(" var <%s> has been handled before, adding to linking (%d != %d)\n", SCIPvarGetName(probvar), consblock, varblock);
1313  SCIP_CALL( SCIPhashmapSetImage(vartoblock, probvar, (void*) (size_t) (nblocks+2)) );
1314  }
1315  else
1316  {
1317  assert(consblock == varblock);
1318  SCIPdebugMessage(" var <%s> is handled and in same block as cons (%d == %d).\n", SCIPvarGetName(probvar), consblock, varblock);
1319  }
1320  }
1321 
1322  SCIPfreeBufferArray(scip, &curvars);
1323  }
1324 
1325  /* Handle variables that do not appear in any pricing problem, those will be copied directly to the master */
1326  for( i = 0; i < nvars; ++i )
1327  {
1328  if( !SCIPhashmapExists(vartoblock, vars[i]) )
1329  {
1330  SCIPdebugMessage(" var <%s> not handled at all and now in master\n", SCIPvarGetName(vars[i]));
1331  SCIP_CALL( SCIPhashmapSetImage(vartoblock, vars[i], (void*) (size_t) (nblocks+1)) );
1332  }
1333  }
1334 
1335  retcode = DECfilloutDecompFromHashmaps(scip, decomp, vartoblock, constoblock, nblocks, staircase);
1336  if( retcode != SCIP_OKAY )
1337  {
1338  SCIPhashmapFree(&vartoblock);
1339  return retcode;
1340  }
1341 
1342  return SCIP_OKAY;
1343 }
1344 
1347  DEC_DECOMP* decomp,
1348  DEC_DETECTOR* detector
1349  )
1350 {
1351  assert(decomp != NULL);
1352 
1353  decomp->detector = detector;
1354 }
1355 
1358  DEC_DECOMP* decomp
1359  )
1360 {
1361  assert(decomp != NULL);
1362 
1363  return decomp->detector;
1364 }
1365 
1367 SCIP_RETCODE DECdecompTransform(
1368  SCIP* scip,
1369  DEC_DECOMP* decomp
1370  )
1371 {
1372  int b;
1373  int c;
1374  int v;
1375  SCIP_HASHMAP* newconstoblock;
1376  SCIP_HASHMAP* newvartoblock;
1377  SCIP_VAR* newvar;
1378 
1379  assert(SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED);
1380 
1381  SCIP_CALL( SCIPhashmapCreate(&newconstoblock, SCIPblkmem(scip), SCIPgetNConss(scip)) );
1382  SCIP_CALL( SCIPhashmapCreate(&newvartoblock, SCIPblkmem(scip), SCIPgetNVars(scip)) );
1383 
1384  /* transform all constraints and put them into constoblock */
1385  for( b = 0; b < decomp->nblocks; ++b )
1386  {
1387  for( c = 0; c < decomp->nsubscipconss[b]; ++c )
1388  {
1389  SCIP_CONS* newcons;
1390  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, c, SCIPconsGetName(decomp->subscipconss[b][c]),
1391  (void*) decomp->subscipconss[b][c], SCIPconsIsTransformed(decomp->subscipconss[b][c])?"t":"o" );
1392  assert(decomp->subscipconss[b][c] != NULL);
1393  newcons = SCIPfindCons(scip, SCIPconsGetName(decomp->subscipconss[b][c]));
1394  if( newcons != decomp->subscipconss[b][c] )
1395  {
1396  SCIP_CALL( SCIPcaptureCons(scip, newcons) );
1397  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->subscipconss[b][c])) );
1398  decomp->subscipconss[b][c] = newcons;
1399  }
1400  assert(decomp->subscipconss[b][c] != NULL);
1401  assert(!SCIPhashmapExists(newconstoblock, decomp->subscipconss[b][c]));
1402  SCIP_CALL( SCIPhashmapSetImage(newconstoblock, decomp->subscipconss[b][c], (void*) (size_t) (b+1)) );
1403  }
1404  }
1405  /* transform all variables and put them into vartoblock */
1406  for( b = 0; b < decomp->nblocks; ++b )
1407  {
1408  int idx;
1409  for( v = 0, idx = 0; v < decomp->nsubscipvars[b]; ++v )
1410  {
1411  assert(decomp->subscipvars[b][v] != NULL);
1412 
1413  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, v, SCIPvarGetName(decomp->subscipvars[b][v]),
1414  (void*)decomp->subscipvars[b][v], SCIPvarIsTransformed(decomp->subscipvars[b][v])?"t":"o" );
1415 
1416  /* make sure that newvar is a transformed variable */
1417  SCIP_CALL( SCIPgetTransformedVar(scip, decomp->subscipvars[b][v], &newvar) );
1418  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->subscipvars[b][v])) );
1419 
1420  assert(newvar != NULL);
1421  assert(SCIPvarIsTransformed(newvar));
1422 
1423  newvar = SCIPvarGetProbvar(newvar);
1424  assert(newvar != NULL);
1425 
1426  /* the probvar can also be fixed, in which case we do not need it in the block; furthermore, multiple variables
1427  * can resolve to the same active problem variable, so we check whether we already handled the variable
1428  * @todo: why do we ignore fixed variables? They could still be present in constraints?
1429  */
1430  if( SCIPvarIsActive(newvar) && !SCIPhashmapExists(newvartoblock, newvar) )
1431  {
1432  decomp->subscipvars[b][idx] = newvar;
1433  SCIP_CALL( SCIPcaptureVar(scip, newvar) );
1434  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, v, SCIPvarGetName(decomp->subscipvars[b][idx]),
1435  (void*)decomp->subscipvars[b][idx], SCIPvarIsTransformed(decomp->subscipvars[b][idx])?"t":"o" );
1436 
1437  assert(decomp->subscipvars[b][idx] != NULL);
1438  assert(!SCIPhashmapExists(newvartoblock, decomp->subscipvars[b][idx]));
1439  SCIP_CALL( SCIPhashmapSetImage(newvartoblock, decomp->subscipvars[b][idx], (void*) (size_t) (b+1)) );
1440  ++idx;
1441  }
1442  }
1443  decomp->nsubscipvars[b] = idx;
1444  }
1445 
1446  /* transform all linking constraints */
1447  for( c = 0; c < decomp->nlinkingconss; ++c )
1448  {
1449  SCIP_CONS* newcons;
1450 
1451  SCIPdebugMessage("m, %d: %s (%s)\n", c, SCIPconsGetName(decomp->linkingconss[c]), SCIPconsIsTransformed(decomp->linkingconss[c])?"t":"o" );
1452  assert(decomp->linkingconss[c] != NULL);
1453  newcons = SCIPfindCons(scip, SCIPconsGetName(decomp->linkingconss[c]));
1454  if( newcons != decomp->linkingconss[c] )
1455  {
1456  SCIP_CALL( SCIPcaptureCons(scip, newcons) );
1457  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->linkingconss[c])) );
1458  decomp->linkingconss[c] = newcons;
1459  }
1460  SCIP_CALL( SCIPhashmapSetImage(newconstoblock, decomp->linkingconss[c],(void*) (size_t) (decomp->nblocks+1) ) );
1461 
1462  assert(decomp->linkingconss[c] != NULL);
1463  }
1464 
1465  /* transform all linking variables */
1466  for( v = 0; v < decomp->nlinkingvars; ++v )
1467  {
1468  int block;
1469  SCIPdebugMessage("m, %d: %s (%p, %s)\n", v, SCIPvarGetName(decomp->linkingvars[v]),
1470  (void*)decomp->linkingvars[v], SCIPvarIsTransformed(decomp->linkingvars[v])?"t":"o");
1471  assert(decomp->linkingvars[v] != NULL);
1472 
1473  if( !SCIPvarIsTransformed(decomp->linkingvars[v]) )
1474  {
1475  SCIP_CALL( SCIPgetTransformedVar(scip, decomp->linkingvars[v], &newvar) );
1476  newvar = SCIPvarGetProbvar(newvar);
1477  }
1478  else
1479  newvar = decomp->linkingvars[v];
1480 
1481  block = (int) (size_t) SCIPhashmapGetImage(decomp->vartoblock, decomp->linkingvars[v]); /*lint !e507*/
1482  assert(block == decomp->nblocks +1 || block == decomp->nblocks +2);
1483  assert(newvar != NULL);
1484  assert(SCIPvarIsTransformed(newvar));
1485  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->linkingvars[v])) );
1486 
1487  decomp->linkingvars[v] = newvar;
1488  SCIP_CALL( SCIPcaptureVar(scip, decomp->linkingvars[v]) );
1489  SCIP_CALL( SCIPhashmapSetImage(newvartoblock, decomp->linkingvars[v], (void*) (size_t) (block) ) );
1490  SCIPdebugMessage("m, %d: %s (%p, %s)\n", v, SCIPvarGetName(decomp->linkingvars[v]),
1491  (void*)decomp->linkingvars[v], SCIPvarIsTransformed(decomp->linkingvars[v])?"t":"o");
1492  assert(decomp->linkingvars[v] != NULL);
1493  }
1494 
1495  SCIPhashmapFree(&decomp->constoblock);
1496  decomp->constoblock = newconstoblock;
1497  SCIPhashmapFree(&decomp->vartoblock);
1498  decomp->vartoblock = newvartoblock;
1499 
1500  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
1501 
1502  return SCIP_OKAY;
1503 }
1504 
1509  SCIP* scip,
1510  DEC_DECOMP* decdecomp
1511  )
1512 {
1513  int block;
1514 
1515  int c;
1516  int pos;
1517 
1518  assert(scip != NULL);
1519  assert(decdecomp != NULL);
1520 
1521  for( block = 0; block < decdecomp->nblocks; ++block )
1522  {
1523  for( c = 0, pos = 0; c < decdecomp->nsubscipconss[block]; ++c )
1524  {
1525  if( !SCIPconsIsDeleted(decdecomp->subscipconss[block][c]) )
1526  {
1527  decdecomp->subscipconss[block][pos] = decdecomp->subscipconss[block][c];
1528  ++pos;
1529  }
1530  else
1531  {
1532  SCIP_CALL( SCIPreleaseCons(scip, &decdecomp->subscipconss[block][c]) );
1533  }
1534  }
1535  decdecomp->nsubscipconss[block] = pos;
1536  }
1537 
1538  for( c = 0, pos = 0; c < decdecomp->nlinkingconss; ++c )
1539  {
1540  if( !SCIPconsIsDeleted(decdecomp->linkingconss[c]) )
1541  {
1542  decdecomp->linkingconss[pos] = decdecomp->linkingconss[c];
1543  ++pos;
1544  }
1545  else
1546  {
1547  SCIP_CALL( SCIPreleaseCons(scip, &decdecomp->linkingconss[c]) );
1548  }
1549  }
1550  decdecomp->nlinkingconss = pos;
1551 
1552  return SCIP_OKAY;
1553 }
1554 
1559  SCIP* scip,
1560  DEC_DECOMP* decdecomp
1561  )
1562 {
1563  int c;
1564 
1565  assert(scip != NULL);
1566  assert(decdecomp != NULL);
1567 
1568  for( c = 0; c < SCIPgetNConss(scip); ++c )
1569  {
1570  SCIP_CONS* cons = SCIPgetConss(scip)[c];
1571 
1572  if( !GCGisConsGCGCons(cons) && !SCIPhashmapExists(DECdecompGetConstoblock(decdecomp), cons) )
1573  {
1574  int block;
1575  SCIP_CALL( DECdetermineConsBlock(scip, decdecomp, cons, &block) );
1576  SCIPdebugMessage("cons <%s> in block %d/%d\n", SCIPconsGetName(cons), block, DECdecompGetNBlocks(decdecomp) );
1577 
1578  if( block == DECdecompGetNBlocks(decdecomp) )
1579  {
1580  if( decdecomp->nlinkingconss == 0 )
1581  {
1582  int newsize = SCIPcalcMemGrowSize(scip, 1);
1583  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decdecomp->linkingconss, newsize) );
1584 
1585  switch( decdecomp->type )
1586  {
1587  case DEC_DECTYPE_DIAGONAL:
1588  decdecomp->type = DEC_DECTYPE_BORDERED;
1589  SCIPwarningMessage(scip, "Decomposition type changed to 'bordered' due to an added constraint.\n");
1590  break;
1591  case DEC_DECTYPE_STAIRCASE:
1592  decdecomp->type = DEC_DECTYPE_ARROWHEAD;
1593  SCIPwarningMessage(scip, "Decomposition type changed to 'arrowhead' due to an added constraint.\n");
1594  break;
1595  default:
1596  break;
1597  }
1598  }
1599  else
1600  {
1601  int oldsize = SCIPcalcMemGrowSize(scip, decdecomp->nlinkingconss);
1602  int newsize = SCIPcalcMemGrowSize(scip, decdecomp->nlinkingconss+1);
1603  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->linkingconss, oldsize, newsize) );
1604  }
1605  decdecomp->linkingconss[decdecomp->nlinkingconss] = cons;
1606  decdecomp->nlinkingconss += 1;
1607  SCIP_CALL( SCIPhashmapInsert(decdecomp->constoblock, cons, (void*) (size_t) (DECdecompGetNBlocks(decdecomp)+1)) );
1608  }
1609  else
1610  {
1611  int oldsize = SCIPcalcMemGrowSize(scip, decdecomp->nsubscipconss[block]);
1612  int newsize = SCIPcalcMemGrowSize(scip, decdecomp->nsubscipconss[block]+1);
1613  assert(decdecomp->nsubscipconss[block] > 0);
1614  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->subscipconss[block], oldsize, newsize) ); /*lint !e866*/
1615  decdecomp->subscipconss[block][decdecomp->nsubscipconss[block]] = cons;
1616  decdecomp->nsubscipconss[block] += 1;
1617  SCIP_CALL( SCIPhashmapInsert(decdecomp->constoblock, cons, (void*) (size_t) (block+1)) );
1618  }
1619  SCIP_CALL( SCIPcaptureCons(scip, cons) );
1620  }
1621  }
1622 
1623  return SCIP_OKAY;
1624 }
1625 
1632  SCIP* scip,
1633  DEC_DECOMP* decdecomp
1634  )
1635 {
1636 #ifndef NDEBUG
1637  int c;
1638  int b;
1639  int v;
1640 
1641 
1642  SCIPdebugMessage("Problem is %stransformed\n", SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED ? "": "not ");
1643 
1644  for( v = 0; v < SCIPgetNVars(scip); ++v )
1645  {
1646  assert(SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), SCIPgetVars(scip)[v]));
1647  }
1648 
1649  for( c = 0; c < SCIPgetNConss(scip); ++c )
1650  {
1651  if( !GCGisConsGCGCons(SCIPgetConss(scip)[c]) )
1652  {
1653  assert(SCIPhashmapExists(DECdecompGetConstoblock(decdecomp), SCIPgetConss(scip)[c]));
1654  }
1655  }
1656 
1657  /* Check whether subscipcons are correct */
1658  for( b = 0; b < DECdecompGetNBlocks(decdecomp); ++b )
1659  {
1660  for( c = 0; c < DECdecompGetNSubscipconss(decdecomp)[b]; ++c )
1661  {
1662  SCIP_VAR** curvars;
1663  int ncurvars;
1664  SCIP_CONS* cons = DECdecompGetSubscipconss(decdecomp)[b][c];
1665 
1666  SCIPdebugMessage("Cons <%s> in block %d = %d\n", SCIPconsGetName(cons), b, ((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), cons)) -1); /*lint !e507*/
1667  assert(SCIPfindCons(scip, SCIPconsGetName(cons)) != NULL);
1668  assert(((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), cons)) -1 == b); /*lint !e507*/
1669  ncurvars = GCGconsGetNVars(scip, cons);
1670  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1671  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
1672 
1673  for( v = 0; v < ncurvars; ++v )
1674  {
1675  int varblock;
1676  SCIP_VAR* var = SCIPvarGetProbvar(curvars[v]);
1677 
1678  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
1679  continue;
1680 
1681  varblock = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var)) -1; /*lint !e507*/
1682  SCIPdebugMessage("\tVar <%s> in block %d = %d\n", SCIPvarGetName(var), b, varblock);
1683 
1684  assert(SCIPfindVar(scip, SCIPvarGetName(var)) != NULL);
1685  assert(SCIPvarIsActive(var));
1686  assert(varblock == b || varblock == DECdecompGetNBlocks(decdecomp)+1 );
1687  }
1688  SCIPfreeBufferArray(scip, &curvars);
1689  }
1690 
1691  for( v = 0; v < DECdecompGetNSubscipvars(decdecomp)[b]; ++v )
1692  {
1693  int varblock;
1694  SCIP_VAR* var = DECdecompGetSubscipvars(decdecomp)[b][v];
1695  varblock = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var)) -1; /*lint !e507*/
1696  SCIPdebugMessage("Var <%s> in block %d = %d\n", SCIPvarGetName(var), b, varblock);
1697  assert(SCIPfindVar(scip, SCIPvarGetName(var)) != NULL);
1698  assert(SCIPvarIsActive(var));
1699  assert(varblock == b || varblock == DECdecompGetNBlocks(decdecomp)+1);
1700  }
1701  }
1702 
1703  /* check linking constraints and variables */
1704  for( v = 0; v < DECdecompGetNLinkingvars(decdecomp); ++v )
1705  {
1706  int varblock;
1707  varblock = (int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), DECdecompGetLinkingvars(decdecomp)[v]); /*lint !e507*/
1708  assert( varblock == DECdecompGetNBlocks(decdecomp) +1 || varblock == DECdecompGetNBlocks(decdecomp)+2); /*lint !e507*/
1709  }
1710  for (c = 0; c < DECdecompGetNLinkingconss(decdecomp); ++c)
1711  {
1712  assert(((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), DECdecompGetLinkingconss(decdecomp)[c])) -1 == DECdecompGetNBlocks(decdecomp)); /*lint !e507*/
1713  }
1714 
1715  switch( DECdecompGetType(decdecomp) )
1716  {
1717  case DEC_DECTYPE_UNKNOWN:
1718  assert(FALSE);
1719  break;
1720  case DEC_DECTYPE_ARROWHEAD:
1721  assert(DECdecompGetNLinkingvars(decdecomp) > 0);
1722  break;
1723  case DEC_DECTYPE_BORDERED:
1724  assert(DECdecompGetNLinkingvars(decdecomp) == 0 && DECdecompGetNLinkingconss(decdecomp) > 0);
1725  break;
1726  case DEC_DECTYPE_DIAGONAL:
1727  assert(DECdecompGetNLinkingvars(decdecomp) == 0 && DECdecompGetNLinkingconss(decdecomp) == 0);
1728  break;
1729  case DEC_DECTYPE_STAIRCASE:
1730  assert(DECdecompGetNLinkingvars(decdecomp) > 0 && DECdecompGetNLinkingconss(decdecomp) == 0);
1731  break;
1732  default:
1733  assert(FALSE);
1734  break;
1735  }
1736 
1737 #endif
1738  return SCIP_OKAY;
1739 }
1740 
1743  SCIP* scip,
1744  DEC_DECOMP** decomp
1745  )
1746 {
1747  SCIP_HASHMAP* constoblock;
1748  SCIP_CONS** conss;
1749  int nconss;
1750  int c;
1751 
1752  assert(scip != NULL);
1753  assert(decomp != NULL);
1754 
1755  SCIP_CALL( DECdecompCreate(scip, decomp) );
1756  conss = SCIPgetConss(scip);
1757  nconss = SCIPgetNConss(scip);
1758 
1759  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
1760 
1761  for( c = 0; c < nconss; ++c )
1762  {
1763  if( GCGisConsGCGCons(conss[c]) )
1764  continue;
1765 
1766  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[c], (void*) (size_t) 1 ) );
1767  }
1768 
1769  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, *decomp, constoblock, 0, FALSE) );
1770 
1771  return SCIP_OKAY;
1772 }
1773 
1779 static
1781  int maxblock,
1782  int* blockrepresentative
1783  )
1784 {
1785  int i;
1786  int tempblock = 1;
1787 
1788  assert(maxblock >= 1);
1789  assert(blockrepresentative != NULL );
1790  SCIPdebugPrintf("Blocks: ");
1791 
1792  /* postprocess blockrepresentatives */
1793  for( i = 1; i < maxblock; ++i )
1794  {
1795  /* forward replace the representatives */
1796  assert(blockrepresentative[i] >= 0);
1797  assert(blockrepresentative[i] < maxblock);
1798  if( blockrepresentative[i] != i )
1799  blockrepresentative[i] = blockrepresentative[blockrepresentative[i]];
1800  else
1801  {
1802  blockrepresentative[i] = tempblock;
1803  ++tempblock;
1804  }
1805  /* It is crucial that this condition holds */
1806  assert(blockrepresentative[i] <= i);
1807  SCIPdebugPrintf("%d ", blockrepresentative[i]);
1808  }
1809  SCIPdebugPrintf("\n");
1810  return tempblock-1;
1811 }
1812 
1814 static
1816  SCIP* scip,
1817  SCIP_CONS** conss,
1818  int nconss,
1819  SCIP_Bool* consismaster,
1820  SCIP_HASHMAP* constoblock,
1821  int* vartoblock,
1822  int* nextblock,
1823  int* blockrepresentative
1824  )
1825 {
1826 
1827  int i;
1828  int j;
1829  SCIP_VAR** curvars;
1830  int ncurvars;
1831 
1832  conss = SCIPgetConss(scip);
1833  nconss = SCIPgetNConss(scip);
1834 
1835  /* go through the all constraints */
1836  for( i = 0; i < nconss; ++i )
1837  {
1838  int consblock;
1839  SCIP_CONS* cons = conss[i];
1840 
1841  assert(cons != NULL);
1842  if( GCGisConsGCGCons(cons) )
1843  continue;
1844 
1845  if( consismaster[i] )
1846  continue;
1847 
1848  /* get variables of constraint; ignore empty constraints */
1849  ncurvars = GCGconsGetNVars(scip, cons);
1850  curvars = NULL;
1851  if( ncurvars > 0 )
1852  {
1853  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1854  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
1855  }
1856  assert(ncurvars >= 0);
1857  assert(ncurvars <= SCIPgetNVars(scip));
1858  assert(curvars != NULL || ncurvars == 0);
1859 
1860  assert(SCIPhashmapGetImage(constoblock, cons) == NULL);
1861 
1862  /* if there are no variables, put it in the first block, otherwise put it in the next block */
1863  if( ncurvars == 0 )
1864  consblock = -1;
1865  else
1866  consblock = *nextblock;
1867 
1868  /* go through all variables */
1869  for( j = 0; j < ncurvars; ++j )
1870  {
1871  SCIP_VAR* probvar;
1872  int varindex;
1873  int varblock;
1874 
1875  assert(curvars != NULL);
1876  probvar = SCIPvarGetProbvar(curvars[j]);
1877  assert(probvar != NULL);
1878 
1879  /* ignore variables which have been fixed during presolving */
1880  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1881  continue;
1882 
1883  varindex = SCIPvarGetProbindex(probvar);
1884  assert(varindex >= 0);
1885  assert(varindex < SCIPgetNVars(scip));
1886 
1888  /* get block of variable */
1889  varblock = vartoblock[varindex];
1890 
1891  SCIPdebugMessage("\tVar %s (%d): ", SCIPvarGetName(probvar), varblock);
1892  /* if variable is already assigned to a block, assign constraint to that block */
1893  if( varblock > -1 && varblock != consblock )
1894  {
1895  consblock = MIN(consblock, blockrepresentative[varblock]);
1896  SCIPdebugPrintf("still in block %d.\n", varblock);
1897  }
1898  else if( varblock == -1 )
1899  {
1900  /* if variable is free, assign it to the new block for this constraint */
1901  varblock = consblock;
1902  assert(varblock > 0);
1903  assert(varblock <= *nextblock);
1904  vartoblock[varindex] = varblock;
1905  SCIPdebugPrintf("new in block %d.\n", varblock);
1906  }
1907  else
1908  {
1909  assert((varblock > 0) && (consblock == varblock));
1910  SCIPdebugPrintf("no change.\n");
1911  }
1912 
1913  SCIPdebugPrintf("VARINDEX: %d (%d)\n", varindex, vartoblock[varindex]);
1914  }
1915 
1916  /* if the constraint belongs to a new block, mark it as such */
1917  if( consblock == *nextblock )
1918  {
1919  assert(consblock > 0);
1920  blockrepresentative[consblock] = consblock;
1921  assert(blockrepresentative[consblock] > 0);
1922  assert(blockrepresentative[consblock] <= *nextblock);
1923  ++(*nextblock);
1924  }
1925 
1926  SCIPdebugMessage("Cons %s will be in block %d (next %d)\n", SCIPconsGetName(cons), consblock, *nextblock);
1927 
1928  for( j = 0; j < ncurvars; ++j )
1929  {
1930  SCIP_VAR* probvar;
1931  int varindex;
1932  int oldblock;
1933 
1934  assert(curvars != NULL);
1935  probvar = SCIPvarGetProbvar(curvars[j]);
1936  assert(probvar != NULL);
1937 
1938  /* ignore variables which have been fixed during presolving */
1939  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1940  continue;
1941 
1942  varindex = SCIPvarGetProbindex(probvar);
1943  assert(varindex >= 0);
1944  assert(varindex < SCIPgetNVars(scip));
1945 
1946  oldblock = vartoblock[varindex];
1947  assert((oldblock > 0) && (oldblock <= *nextblock));
1948 
1949  SCIPdebugMessage("\tVar %s ", SCIPvarGetName(probvar));
1950  if( oldblock != consblock )
1951  {
1952  SCIPdebugPrintf("reset from %d to block %d.\n", oldblock, consblock);
1953  vartoblock[varindex] = consblock;
1954  SCIPdebugPrintf("VARINDEX: %d (%d)\n", varindex, consblock);
1955 
1956  if( (blockrepresentative[oldblock] != -1) && (blockrepresentative[oldblock] > blockrepresentative[consblock]) )
1957  {
1958  int oldrepr;
1959  oldrepr = blockrepresentative[oldblock];
1960  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldblock, blockrepresentative[oldblock], consblock);
1961  assert(consblock > 0);
1962  blockrepresentative[oldblock] = consblock;
1963  if( (oldrepr != consblock) && (oldrepr != oldblock) )
1964  {
1965  blockrepresentative[oldrepr] = consblock;
1966  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldrepr, blockrepresentative[oldrepr], consblock);
1967  }
1968  }
1969  }
1970  else
1971  {
1972  SCIPdebugPrintf("will not be changed from %d to %d.\n", oldblock, consblock);
1973  }
1974  }
1975 
1976  SCIPfreeBufferArrayNull(scip, &curvars);
1977  assert(consblock >= 1 || consblock == -1);
1978  assert(consblock <= *nextblock);
1979 
1980  /* store the constraint block */
1981  if( consblock != -1 )
1982  {
1983  SCIPdebugMessage("cons %s in block %d\n", SCIPconsGetName(cons), consblock);
1984  SCIP_CALL( SCIPhashmapInsert(constoblock, cons, (void*)(size_t)consblock) );
1985  }
1986  else
1987  {
1988  SCIPdebugMessage("ignoring %s\n", SCIPconsGetName(cons));
1989  }
1990  }
1991 
1992  return SCIP_OKAY;
1993 }
1994 
1996 static
1997 SCIP_RETCODE fillConstoblock(
1998  SCIP_CONS** conss,
1999  int nconss,
2000  SCIP_Bool* consismaster,
2001  int nblocks,
2002  SCIP_HASHMAP* constoblock,
2003  SCIP_HASHMAP* newconstoblock,
2004  int* blockrepresentative
2005  )
2006 {
2007  int i;
2008 
2009  /* convert temporary data to detectordata */
2010  for( i = 0; i < nconss; ++i )
2011  {
2012  int consblock;
2013 
2014  SCIP_CONS* cons = conss[i];
2015 
2016  if( GCGisConsGCGCons(cons) )
2017  continue;
2018 
2019  if( consismaster[i] )
2020  {
2021  SCIP_CALL( SCIPhashmapInsert(newconstoblock, cons, (void*) (size_t) (nblocks+1)) );
2022  continue;
2023  }
2024 
2025  if( !SCIPhashmapExists(constoblock, cons) )
2026  continue;
2027 
2028  consblock = (int) (size_t) SCIPhashmapGetImage(constoblock, cons); /*lint !e507*/
2029  assert(consblock > 0);
2030  consblock = blockrepresentative[consblock];
2031  assert(consblock <= nblocks);
2032  SCIP_CALL( SCIPhashmapInsert(newconstoblock, cons, (void*)(size_t)consblock) );
2033  SCIPdebugMessage("%d %s\n", consblock, SCIPconsGetName(cons));
2034  }
2035  return SCIP_OKAY;
2036 }
2037 
2043  SCIP* scip,
2044  DEC_DECOMP** decomp,
2045  SCIP_CONS** masterconss,
2046  int nmasterconss
2047  )
2048 {
2049  SCIP_HASHMAP* constoblock;
2050  SCIP_HASHMAP* newconstoblock;
2051  SCIP_CONS** conss;
2052  int nconss;
2053  int nvars;
2054  int nblocks;
2055  int* blockrepresentative;
2056  int nextblock = 1;
2057  SCIP_Bool* consismaster;
2058  int i;
2059  int* vartoblock;
2060 
2061  assert(scip != NULL);
2062  assert(decomp != NULL);
2063  assert(nmasterconss == 0 || masterconss != NULL);
2064  assert(SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED);
2065 
2066  conss = SCIPgetConss(scip);
2067  nconss = SCIPgetNConss(scip);
2068  nvars = SCIPgetNVars(scip);
2069 
2070  assert( nmasterconss <= nconss );
2071 
2072  if( GCGisConsGCGCons(conss[nconss-1]) )
2073  --nconss;
2074 
2075  nblocks = nconss-nmasterconss+1;
2076  assert(nblocks > 0);
2077 
2078  SCIP_CALL( SCIPallocBufferArray(scip, &blockrepresentative, nblocks) );
2079  SCIP_CALL( SCIPallocBufferArray(scip, &consismaster, nconss) );
2080  SCIP_CALL( SCIPallocBufferArray(scip, &vartoblock, nvars) );
2081  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
2082  SCIP_CALL( SCIPhashmapCreate(&newconstoblock, SCIPblkmem(scip), nconss) );
2083 
2084  for( i = 0; i < nmasterconss; ++i )
2085  {
2086  SCIP_CALL( SCIPhashmapInsert(constoblock, masterconss[i], (void*) (size_t) (nblocks+1)) );
2087  }
2088 
2089  for( i = 0; i < nconss; ++i )
2090  {
2091  assert(!GCGisConsGCGCons(conss[i]));
2092  consismaster[i] = SCIPhashmapExists(constoblock, conss[i]);
2093  }
2094 
2095  for( i = 0; i < nvars; ++i )
2096  {
2097  vartoblock[i] = -1;
2098  }
2099 
2100  for( i = 0; i < nblocks; ++i )
2101  {
2102  blockrepresentative[i] = -1;
2103  }
2104 
2105  SCIP_CALL( assignConstraintsToRepresentatives(scip, conss, nconss, consismaster, constoblock, vartoblock, &nextblock, blockrepresentative) );
2106 
2107  /* postprocess blockrepresentatives */
2108  nblocks = processBlockRepresentatives(nextblock, blockrepresentative);
2109 
2110  /* convert temporary data to detectordata */
2111  SCIP_CALL( fillConstoblock(conss, nconss, consismaster, nblocks, constoblock, newconstoblock, blockrepresentative) );
2112  SCIP_CALL( DECdecompCreate(scip, decomp) );
2113  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, *decomp, newconstoblock, nblocks, FALSE) );
2114 
2115  SCIPfreeBufferArray(scip, &vartoblock);
2116  SCIPfreeBufferArray(scip, &consismaster);
2117  SCIPfreeBufferArray(scip, &blockrepresentative);
2118  SCIPhashmapFree(&constoblock);
2119 
2120  return SCIP_OKAY;
2121 }
2122 
2124 static
2126  SCIP_VAR* var,
2127  int* nbinvars,
2128  int* nintvars,
2129  int* nimplvars,
2130  int* ncontvars,
2131  int nproblems,
2132  int i
2133 )
2134 {
2135  assert(var != NULL);
2136  assert(i >= 0);
2137  assert(i < nproblems);
2138 
2139  if( nbinvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarIsBinary(var)) )
2140  {
2141  ++(nbinvars[i]);
2142  assert(nbinvars[i] > 0);
2143  }
2144  if( nintvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER && !SCIPvarIsBinary(var)) )
2145  {
2146  ++(nintvars[i]);
2147  assert(nintvars[i] > 0);
2148  }
2149  if( nimplvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) )
2150  {
2151  ++(nimplvars[i]);
2152  assert(nimplvars[i] > 0);
2153  }
2154  if( ncontvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS) )
2155  {
2156  ++(ncontvars[i]);
2157  assert(ncontvars[i] > 0);
2158  }
2159 }
2160 
2161 /* score methods */
2162 
2165  SCIP* scip,
2166  DEC_DECOMP* decomp,
2167  int* nvars,
2168  int* nbinvars,
2169  int* nintvars,
2170  int* nimplvars,
2171  int* ncontvars,
2172  int nproblems
2173 )
2174 {
2175  int i;
2176  int j;
2177 
2178  assert(scip != NULL);
2179  assert(decomp != NULL);
2180  assert(nproblems > 0);
2181 
2182  assert(DECdecompGetType(decomp) != DEC_DECTYPE_UNKNOWN);
2183  if( nvars != NULL )
2184  BMSclearMemoryArray(nvars, nproblems);
2185  if( nbinvars != NULL )
2186  BMSclearMemoryArray(nbinvars, nproblems);
2187  if( nintvars != NULL )
2188  BMSclearMemoryArray(nintvars, nproblems);
2189  if( nimplvars != NULL )
2190  BMSclearMemoryArray(nimplvars, nproblems);
2191  if( ncontvars != NULL )
2192  BMSclearMemoryArray(ncontvars, nproblems);
2193 
2194  for( i = 0; i < nproblems; ++i )
2195  {
2196  SCIP_VAR*** subscipvars;
2197  int* nsubscipvars;
2198 
2199  nsubscipvars = DECdecompGetNSubscipvars(decomp);
2200  subscipvars = DECdecompGetSubscipvars(decomp);
2201  if( nvars != NULL )
2202  nvars[i] = nsubscipvars[i];
2203 
2204  for( j = 0; j < nsubscipvars[i]; ++j )
2205  {
2206  incVarsData(subscipvars[i][j], nbinvars, nintvars, nimplvars, ncontvars, nproblems, i);
2207  }
2208  }
2209 }
2210 
2211 
2214  SCIP* scip,
2215  DEC_DECOMP* decomp,
2216  int* nvars,
2217  int* nbinvars,
2218  int* nintvars,
2219  int* nimplvars,
2220  int* ncontvars
2221 )
2222 {
2223  int i;
2224  SCIP_VAR** linkingvars;
2225  int nlinkingvars;
2226 
2227  assert(scip != NULL);
2228  assert(decomp != NULL);
2229 
2230  assert(DECdecompGetType(decomp) != DEC_DECTYPE_UNKNOWN);
2231 
2232  nlinkingvars = DECdecompGetNLinkingvars(decomp);
2233  linkingvars = DECdecompGetLinkingvars(decomp);
2234 
2235  if( nvars != NULL )
2236  *nvars = nlinkingvars;
2237  if( nbinvars != NULL )
2238  *nbinvars = 0;
2239  if( nintvars != NULL )
2240  *nintvars = 0;
2241  if( nimplvars != NULL )
2242  *nimplvars = 0;
2243  if( ncontvars != NULL )
2244  *ncontvars = 0;
2245 
2246 
2247  for( i = 0; i < nlinkingvars; ++i )
2248  {
2249  incVarsData(linkingvars[i], nbinvars, nintvars, nimplvars, ncontvars, 1, 0);
2250  }
2251 }
2252 
2263 SCIP_RETCODE DECgetDensityData(
2264  SCIP* scip,
2265  DEC_DECOMP* decomp,
2266  SCIP_VAR** vars,
2267  int nvars,
2268  SCIP_CONS** conss,
2269  int nconss,
2270  int* varsubproblemdensity,
2271  int* varmasterdensity,
2272  int* conssubproblemdensity,
2273  int* consmasterdensity
2274 )
2275 {
2276  int nlinkingconss;
2277  SCIP_HASHMAP* vartoblock;
2278  SCIP_CONS** curconss;
2279 
2280  int ncurvars;
2281  SCIP_VAR** curvars;
2282  SCIP_Bool success;
2283 
2284  int i;
2285  int j;
2286  int v;
2287  int c;
2288 
2289  assert(scip != NULL);
2290  assert(decomp != NULL);
2291  assert(vars != NULL);
2292  assert(nvars > 0);
2293  assert(conss != NULL);
2294  assert(varsubproblemdensity != NULL);
2295  assert(varmasterdensity != NULL);
2296  assert(conssubproblemdensity != NULL);
2297  assert(consmasterdensity != NULL);
2298 
2299  /* make sure the passed data is initialised to 0 */
2300  BMSclearMemoryArray(vars, nvars);
2301  BMSclearMemoryArray(conss, nconss);
2302  BMSclearMemoryArray(varsubproblemdensity, nvars);
2303  BMSclearMemoryArray(varmasterdensity, nvars);
2304  BMSclearMemoryArray(conssubproblemdensity, nconss);
2305  BMSclearMemoryArray(consmasterdensity, nconss);
2306 
2307  BMScopyMemoryArray(vars, SCIPgetVars(scip), nvars);
2308 
2309  vartoblock = DECdecompGetVartoblock(decomp);
2310  c = 0;
2311  for( i = 0; i < DECdecompGetNBlocks(decomp); ++i )
2312  {
2313  curconss = DECdecompGetSubscipconss(decomp)[i];
2314  assert(curconss != NULL);
2315 
2316  for( j = 0; j < DECdecompGetNSubscipconss(decomp)[i]; ++j )
2317  {
2318  assert(c < nconss); /* This assertion and the logic forbids constraints in more than one block */
2319  conss[c] = curconss[j];
2320 
2321  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
2322  assert(success);
2323  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2324  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
2325  assert(success);
2326 
2327  for( v = 0; v < ncurvars; ++v )
2328  {
2329  SCIP_VAR* var;
2330  int block;
2331  int probindex;
2332 
2333  var = curvars[v];
2334  var = SCIPvarGetProbvar(var);
2335  probindex = SCIPvarGetProbindex(var);
2336 
2337  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
2338  continue;
2339 
2340  assert(probindex >= 0);
2341  assert(probindex < nvars);
2342  varsubproblemdensity[probindex] += 1;
2343  assert(varsubproblemdensity[probindex] > 0);
2344  block = (int) (size_t) SCIPhashmapGetImage(vartoblock, var); /*lint !e507*/
2345  assert(block > 0);
2346 
2347  if( block <= DECdecompGetNBlocks(decomp) )
2348  {
2349  conssubproblemdensity[c] +=1;
2350  }
2351  else
2352  {
2353  consmasterdensity[c] += 1;
2354  }
2355  }
2356 
2357  SCIPfreeBufferArray(scip, &curvars);
2358  c++;
2359  }
2360  }
2361 
2362  nlinkingconss = DECdecompGetNLinkingconss(decomp);
2363  curconss = DECdecompGetLinkingconss(decomp);
2364 
2365  for( j = 0; j < nlinkingconss; ++j )
2366  {
2367  assert(c < nconss); /* This assertion and the logic forbids constraints in more than one block */
2368  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
2369  assert(success);
2370  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2371  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
2372  assert(success);
2373 
2374  conss[c] = curconss[j];
2375 
2376  for( v = 0; v < ncurvars; ++v )
2377  {
2378  SCIP_VAR* var;
2379  int probindex;
2380 
2381  var = curvars[v];
2382  var = SCIPvarGetProbvar(var);
2383  probindex = SCIPvarGetProbindex(var);
2384 
2385  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
2386  continue;
2387 
2388  assert(probindex >= 0);
2389  assert(probindex < nvars);
2390  varmasterdensity[probindex] += 1;
2391  assert(varmasterdensity[probindex] > 0);
2392  SCIPdebugMessage("Var <%s> appears in cons <%s>, total count: %d\n", SCIPvarGetName(var), SCIPconsGetName(curconss[j]), varmasterdensity[probindex]);
2393  }
2394 
2395  consmasterdensity[c] = ncurvars;
2396  c++;
2397 
2398  SCIPfreeBufferArray(scip, &curvars);
2399  }
2400 
2401  return SCIP_OKAY;
2402 }
2403 
2405 static
2407  SCIP* scip,
2408  SCIP_Real lhs,
2409  SCIP_Real coef,
2410  SCIP_Real rhs,
2411  int* downlock,
2412  int* uplock
2413  )
2414 {
2415  assert(scip != NULL);
2416  assert(downlock != NULL);
2417  assert(uplock != NULL);
2418 
2419  if( !SCIPisInfinity(scip, -lhs) )
2420  {
2421  if( SCIPisPositive(scip, coef) )
2422  ++(*downlock);
2423  if( SCIPisNegative(scip, coef) )
2424  ++(*uplock);
2425 
2426  }
2427  if( !SCIPisInfinity(scip, rhs) )
2428  {
2429  if( SCIPisPositive(scip, coef) )
2430  ++(*uplock);
2431  if( SCIPisNegative(scip, coef) )
2432  ++(*downlock);
2433  }
2434 
2435 }
2436 
2444 SCIP_RETCODE DECgetVarLockData(
2445  SCIP* scip,
2446  DEC_DECOMP* decomp,
2447  SCIP_VAR** vars,
2448  int nvars,
2449  int nsubproblems,
2450  int** subsciplocksdown,
2451  int** subsciplocksup,
2452  int* masterlocksdown,
2453  int* masterlocksup
2454  )
2455 {
2456  int nlinkingconss;
2457  SCIP_CONS** curconss;
2458  SCIP_VAR** curvars;
2459  SCIP_Real* curvals;
2460  int ncurvars;
2461  SCIP_Real lhs;
2462  SCIP_Real rhs;
2463 
2464  SCIP_Bool success;
2465 
2466  int i;
2467  int j;
2468  int v;
2469 
2470  assert(scip != NULL);
2471  assert(decomp != NULL);
2472  assert(vars != NULL);
2473  assert(nvars > 0);
2474  assert(nvars == SCIPgetNVars(scip));
2475  assert(subsciplocksdown != NULL);
2476  assert(subsciplocksup != NULL);
2477  assert(masterlocksdown != NULL);
2478  assert(masterlocksup != NULL);
2479 
2480  /* make sure the passed data is initialised to 0 */
2481  BMSclearMemoryArray(vars, nvars);
2482  BMScopyMemoryArray(vars, SCIPgetVars(scip), nvars);
2483  BMSclearMemoryArray(masterlocksdown, nvars);
2484  BMSclearMemoryArray(masterlocksup, nvars);
2485  for( i = 0; i < nsubproblems; ++i )
2486  {
2487  BMSclearMemoryArray(subsciplocksdown[i], nvars); /*lint !e866*/
2488  BMSclearMemoryArray(subsciplocksup[i], nvars); /*lint !e866*/
2489  }
2490 
2491  for( i = 0; i < DECdecompGetNBlocks(decomp); ++i )
2492  {
2493  curconss = DECdecompGetSubscipconss(decomp)[i];
2494  assert(curconss != NULL);
2495 
2496  for( j = 0; j < DECdecompGetNSubscipconss(decomp)[i]; ++j )
2497  {
2498 
2499  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
2500  assert(success);
2501  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2502  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
2503 
2504  SCIP_CALL( GCGconsGetVals(scip, curconss[j], curvals, ncurvars) );
2505  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
2506  assert(success);
2507 
2508  rhs = GCGconsGetRhs(scip, curconss[j]);
2509  lhs = GCGconsGetLhs(scip, curconss[j]);
2510 
2511  for( v = 0; v < ncurvars; ++v )
2512  {
2513  SCIP_VAR* var;
2514  int probindex;
2515 
2516  var = curvars[v];
2517  var = SCIPvarGetProbvar(var);
2518  probindex = SCIPvarGetProbindex(var);
2519 
2520  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
2521  continue;
2522 
2523  assert(probindex >= 0);
2524  assert(probindex < nvars);
2525  assert(SCIPhashmapExists(DECdecompGetVartoblock(decomp), var));
2526 
2527  increaseLock(scip, lhs, curvals[v], rhs, &(subsciplocksdown[i][probindex]), &(subsciplocksup[i][probindex]));
2528  }
2529 
2530  SCIPfreeBufferArray(scip, &curvals);
2531  SCIPfreeBufferArray(scip, &curvars);
2532  }
2533  }
2534 
2535  nlinkingconss = DECdecompGetNLinkingvars(decomp);
2536  curconss = DECdecompGetLinkingconss(decomp);
2537  for( j = 0; j < nlinkingconss; ++j )
2538  {
2539  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
2540  assert(success);
2541  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2542  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
2543 
2544  SCIP_CALL( GCGconsGetVals(scip, curconss[j], curvals, ncurvars) );
2545  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
2546  assert(success);
2547 
2548  rhs = GCGconsGetRhs(scip, curconss[j]);
2549  lhs = GCGconsGetLhs(scip, curconss[j]);
2550 
2551  for( v = 0; v < ncurvars; ++v )
2552  {
2553  SCIP_VAR* var;
2554  int probindex;
2555 
2556  var = curvars[v];
2557  var = SCIPvarGetProbvar(var);
2558  probindex = SCIPvarGetProbindex(var);
2559 
2560  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
2561  continue;
2562 
2563  assert(probindex >= 0);
2564  assert(probindex < nvars);
2565 
2566  increaseLock(scip, lhs, curvals[v], rhs, &(masterlocksdown[probindex]), &(masterlocksup[probindex]));
2567  }
2568 
2569  SCIPfreeBufferArray(scip, &curvals);
2570  SCIPfreeBufferArray(scip, &curvars);
2571  }
2572 
2573  return SCIP_OKAY;
2574 }
2575 
2576 
2581  SCIP* scip,
2582  DEC_DECOMP* decdecomp,
2583  DEC_SCORES* score
2584  )
2585 {
2586  int matrixarea;
2587  int borderarea;
2588  int nvars;
2589  int nconss;
2590  int i;
2591  int j;
2592  int k;
2593  /* int blockarea; */
2594  SCIP_Real varratio;
2595  int* nzblocks;
2596  int nblocks;
2597  int* nlinkvarsblocks;
2598  int* nvarsblocks;
2599  SCIP_Real* blockdensities;
2600  int* blocksizes;
2601  SCIP_Real density;
2602 
2603  assert(scip != NULL);
2604  assert(score != NULL);
2605 
2606  nvars = SCIPgetNVars(scip);
2607  nconss = SCIPgetNConss(scip);
2608 
2609  nblocks = DECdecompGetNBlocks(decdecomp);
2610 
2611  SCIP_CALL( SCIPallocBufferArray(scip, &nzblocks, nblocks) );
2612  SCIP_CALL( SCIPallocBufferArray(scip, &nlinkvarsblocks, nblocks) );
2613  SCIP_CALL( SCIPallocBufferArray(scip, &blockdensities, nblocks) );
2614  SCIP_CALL( SCIPallocBufferArray(scip, &blocksizes, nblocks) );
2615  SCIP_CALL( SCIPallocBufferArray(scip, &nvarsblocks, nblocks) );
2616  /*
2617  * 3 Scores
2618  *
2619  * - Area percentage (min)
2620  * - block density (max)
2621  * - \pi_b {v_b|v_b is linking}/#vb (min)
2622  */
2623 
2624  /* calculate matrix area */
2625  matrixarea = nvars*nconss;
2626 
2627  /* calculate slave sizes, nonzeros and linkingvars */
2628  for( i = 0; i < nblocks; ++i )
2629  {
2630  SCIP_CONS** curconss;
2631  int ncurconss;
2632  int nvarsblock;
2633  SCIP_Bool *ishandled;
2634 
2635  SCIP_CALL( SCIPallocBufferArray(scip, &ishandled, nvars) );
2636  nvarsblock = 0;
2637  nzblocks[i] = 0;
2638  nlinkvarsblocks[i] = 0;
2639  for( j = 0; j < nvars; ++j )
2640  {
2641  ishandled[j] = FALSE;
2642  }
2643  curconss = DECdecompGetSubscipconss(decdecomp)[i];
2644  ncurconss = DECdecompGetNSubscipconss(decdecomp)[i];
2645 
2646  for( j = 0; j < ncurconss; ++j )
2647  {
2648  SCIP_VAR** curvars;
2649  SCIP_VAR* var;
2650  int ncurvars;
2651  ncurvars = GCGconsGetNVars(scip, curconss[j]);
2652  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2653  SCIP_CALL( GCGconsGetVars(scip, curconss[j], curvars, ncurvars) );
2654 
2655  for( k = 0; k < ncurvars; ++k )
2656  {
2657  int block;
2658  if( !GCGisVarRelevant(curvars[k]) )
2659  continue;
2660 
2661  var = SCIPvarGetProbvar(curvars[k]);
2662  assert(var != NULL);
2663  if( !GCGisVarRelevant(var) )
2664  continue;
2665 
2666  assert(SCIPvarIsActive(var));
2667  assert(!SCIPvarIsDeleted(var));
2668  ++(nzblocks[i]);
2669  if( !SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), var) )
2670  {
2671  block = (int)(size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), curvars[k]); /*lint !e507*/
2672  }
2673  else
2674  {
2675  assert(SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), var));
2676  block = (int)(size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var); /*lint !e507*/
2677  }
2678 
2679  if( block == nblocks+1 && ishandled[SCIPvarGetProbindex(var)] == FALSE )
2680  {
2681  ++(nlinkvarsblocks[i]);
2682  }
2683  ishandled[SCIPvarGetProbindex(var)] = TRUE;
2684  }
2685 
2686  SCIPfreeBufferArray(scip, &curvars);
2687  }
2688 
2689  for( j = 0; j < nvars; ++j )
2690  {
2691  if( ishandled[j] )
2692  {
2693  ++nvarsblock;
2694  }
2695  }
2696 
2697  blocksizes[i] = nvarsblock*ncurconss;
2698  nvarsblocks[i] = nvarsblock;
2699  if( blocksizes[i] > 0 )
2700  {
2701  blockdensities[i] = 1.0*nzblocks[i]/blocksizes[i];
2702  }
2703  else
2704  {
2705  blockdensities[i] = 0.0;
2706  }
2707 
2708  assert(blockdensities[i] >= 0 && blockdensities[i] <= 1.0);
2709  SCIPfreeBufferArray(scip, &ishandled);
2710  }
2711 
2712  borderarea = DECdecompGetNLinkingconss(decdecomp)*nvars+DECdecompGetNLinkingvars(decdecomp)*(nconss-DECdecompGetNLinkingconss(decdecomp));
2713 
2714  density = 1E20;
2715  varratio = 1.0;
2716  for( i = 0; i < nblocks; ++i )
2717  {
2718  density = MIN(density, blockdensities[i]);
2719 
2720  if( DECdecompGetNLinkingvars(decdecomp) > 0 )
2721  {
2722  varratio *= 1.0*nlinkvarsblocks[i]/DECdecompGetNLinkingvars(decdecomp);
2723  }
2724  else
2725  {
2726  varratio = 0;
2727  }
2728  }
2729 
2730  score->linkingscore = (0.5+0.5*varratio);
2731  score->borderscore = (1.0*(borderarea)/matrixarea);
2732  score->densityscore = (1-density);
2733 
2734  switch( DECdecompGetType(decdecomp) )
2735  {
2736  case DEC_DECTYPE_ARROWHEAD:
2737  score->totalscore = score->borderscore*score->linkingscore*score->densityscore;
2738  break;
2739  case DEC_DECTYPE_BORDERED:
2740  score->totalscore = score->borderscore*score->linkingscore*score->densityscore;
2741  break;
2742  case DEC_DECTYPE_DIAGONAL:
2743  score->totalscore = 0.0;
2744  break;
2745  case DEC_DECTYPE_STAIRCASE:
2746  SCIPwarningMessage(scip, "Decomposition type is %s, cannot compute score\n", DECgetStrType(DECdecompGetType(decdecomp)));
2747  score->totalscore = 0.1;
2748  break;
2749  case DEC_DECTYPE_UNKNOWN:
2750  SCIPerrorMessage("Decomposition type is %s, cannot compute score\n", DECgetStrType(DECdecompGetType(decdecomp)));
2751  assert(FALSE);
2752  break;
2753  default:
2754  SCIPerrorMessage("No rule for this decomposition type, cannot compute score\n");
2755  assert(FALSE);
2756  break;
2757  }
2758 
2759 
2760  SCIPfreeBufferArray(scip, &nvarsblocks);
2761  SCIPfreeBufferArray(scip, &blocksizes);
2762  SCIPfreeBufferArray(scip, &blockdensities);
2763  SCIPfreeBufferArray(scip, &nlinkvarsblocks);
2764  SCIPfreeBufferArray(scip, &nzblocks);
2765  return SCIP_OKAY;
2766 }
2767 
2769 static
2770 SCIP_RETCODE computeVarDensities(
2771  SCIP* scip,
2772  DEC_DECOMP* decomp,
2773  int* varprobdensity,
2774  int* varmasterdensity,
2775  SCIP_VAR** vars,
2776  int nvars,
2777  DEC_STATISTIC* blockvardensities,
2778  DEC_STATISTIC* mastervardensity,
2779  int nblocks
2780  )
2781 {
2782  int v;
2783  int b;
2784  SCIP_Real** vardistribution;
2785  int* nvardistribution;
2786  SCIP_Real* mastervardistribution;
2787 
2788  SCIP_Real max = 0;
2789  SCIP_Real min = 1.0;
2790  SCIP_Real median = 0;
2791  SCIP_Real mean = 0;
2792 
2793  assert(scip != NULL);
2794  assert(decomp != NULL);
2795 
2796  assert(vars != NULL);
2797  assert(nvars > 0);
2798  assert(blockvardensities != NULL);
2799  assert(mastervardensity != NULL);
2800  assert(nblocks >= 0);
2801 
2802  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vardistribution, nblocks) );
2803  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nvardistribution, nblocks) );
2804 
2805  BMSclearMemoryArray(vardistribution, nblocks);
2806  BMSclearMemoryArray(nvardistribution, nblocks);
2807 
2808  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mastervardistribution, nvars) );
2809  BMSclearMemoryArray(mastervardistribution, nvars);
2810 
2811  for( b = 0; b < nblocks; ++b )
2812  {
2813  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]) ); /*lint !e866 !e666*/
2814  BMSclearMemoryArray(vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]); /*lint !e866 */
2815  }
2816 
2817  for( v = 0; v < nvars; ++v )
2818  {
2819  int block = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decomp), (vars[v]))) - 1; /*lint !e507 */
2820  assert(block >= 0);
2821  SCIPdebugMessage("Var <%s>:", SCIPvarGetName(vars[v]));
2822 
2823 
2824  mastervardistribution[v] = 1.0*varmasterdensity[v]/DECdecompGetNLinkingconss(decomp);
2825  SCIPdebugPrintf("master %d ", varmasterdensity[v]);
2826 
2827  if( block < nblocks )
2828  {
2829  vardistribution[block][nvardistribution[block]] = 1.0*varprobdensity[v]/DECdecompGetNSubscipconss(decomp)[block];
2830  SCIPdebugPrintf("block %d %.3f\n", block, vardistribution[block][nvardistribution[block]]);
2831  ++(nvardistribution[block]);
2832  }
2833  else
2834  {
2835  SCIPdebugPrintf("\n");
2836  }
2837  }
2838 
2839  for( b = 0; b < nblocks; ++b )
2840  {
2841  int ncurvars = DECdecompGetNSubscipvars(decomp)[b];
2842 
2843  max = 0;
2844  min = 1.0;
2845  median = 0;
2846  mean = 0;
2847 
2848 
2849 
2850  SCIPdebugMessage("block %d:", b);
2851  for( v = 0; v < ncurvars; ++v )
2852  {
2853 
2854  SCIPdebugPrintf(" <%s> %.3f", SCIPvarGetName(DECdecompGetSubscipvars(decomp)[b][v]), vardistribution[b][v]);
2855  max = MAX(max, vardistribution[b][v]);
2856  min = MIN(min, vardistribution[b][v]);
2857  mean += 1.0*vardistribution[b][v]/ncurvars;
2858 
2859  }
2860  if( ncurvars > 0 )
2861  median = quick_select_median(vardistribution[b], ncurvars);
2862 
2863  SCIPdebugPrintf("\nmin: %.3f, max: %.3f, median: %.3f, mean: %.3f\n", min, max, median, mean);
2864 
2865  blockvardensities[b].max = max;
2866  blockvardensities[b].min = min;
2867  blockvardensities[b].median = median;
2868  blockvardensities[b].mean = mean;
2869  }
2870  max = 0;
2871  min = 1.0;
2872  mean = 0;
2873 
2874  SCIPdebugMessage("master:");
2875 
2876  for( v = 0; v < nvars; ++v )
2877  {
2878 
2879  SCIPdebugPrintf(" <%s> %.3f", SCIPvarGetName(vars[v]), mastervardistribution[v]);
2880  max = MAX(max, mastervardistribution[v]);
2881  min = MIN(min, mastervardistribution[v]);
2882  mean += 1.0*mastervardistribution[v]/nvars;
2883 
2884  }
2885  median = quick_select_median(mastervardistribution, nvars);
2886  SCIPdebugPrintf("\nmin: %.3f, max: %.3f, median: %.3f, mean: %.3f\n", min, max, median, mean);
2887 
2888 
2889  mastervardensity->max = max;
2890  mastervardensity->min = min;
2891  mastervardensity->median = median;
2892  mastervardensity->mean = mean;
2893 
2894  for( b = 0; b < nblocks; ++b )
2895  {
2896  SCIPfreeBlockMemoryArray(scip, &vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]); /*lint !e866 */
2897  }
2898 
2899  SCIPfreeBlockMemoryArray(scip, &mastervardistribution, nvars);
2900 
2901  SCIPfreeBlockMemoryArray(scip, &nvardistribution, nblocks);
2902  SCIPfreeBlockMemoryArray(scip, &vardistribution, nblocks);
2903 
2904  return SCIP_OKAY;
2905 }
2906 
2909  DEC_DECOMP* decomp
2910  )
2911 {
2912  int b;
2913  int nconss = 0;
2914  assert(decomp != NULL);
2915 
2916  for( b = 0; b < DECdecompGetNBlocks(decomp); ++b )
2917  nconss += DECdecompGetNSubscipconss(decomp)[b];
2918 
2919  nconss += DECdecompGetNLinkingconss(decomp);
2920  return nconss;
2921 }
2922 
2924 static
2925 SCIP_RETCODE computeConssNzeros(
2926  SCIP* scip,
2927  DEC_DECOMP* decomp,
2928  SCIP_CONS* cons,
2929  int* nzeros,
2930  int* nintzeros,
2931  int* nbzeros,
2932  int* nintbzeros
2933 )
2934 {
2935  int v;
2936  int ncurvars;
2937  SCIP_VAR** curvars = NULL;
2938  SCIP_Real* curvals = NULL;
2939 
2940  assert(scip != NULL);
2941  assert(decomp != NULL);
2942  assert(cons != NULL);
2943  assert(nzeros != NULL);
2944  assert(nintzeros != NULL);
2945  assert(nbzeros != NULL);
2946  assert(nintbzeros != NULL);
2947 
2948  ncurvars = GCGconsGetNVars(scip, cons);
2949  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2950  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
2951 
2952  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
2953  SCIP_CALL( GCGconsGetVals(scip, cons, curvals, ncurvars) );
2954 
2955  for( v = 0; v < ncurvars; ++v )
2956  {
2957  int block;
2958  SCIP_VAR* curvar;
2959  if( SCIPisZero(scip, curvals[v]) )
2960  continue;
2961 
2962  curvar = SCIPvarGetProbvar(curvars[v]);
2963 
2964  if( SCIPvarGetStatus(curvar) == SCIP_VARSTATUS_FIXED )
2965  continue;
2966 
2967  block = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decomp), (curvar))) - 1; /*lint !e507 */
2968  assert(block >= 0);
2969 
2970  if( block > DECdecompGetNBlocks(decomp) )
2971  {
2972  if( SCIPvarGetType(curvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(curvar) == SCIP_VARTYPE_INTEGER )
2973  *nintbzeros += 1;
2974 
2975  *nbzeros += 1;
2976  }
2977  else
2978  {
2979  if( SCIPvarGetType(curvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(curvar) == SCIP_VARTYPE_INTEGER )
2980  *nintzeros += 1;
2981 
2982  *nzeros += 1;
2983  }
2984  }
2985 
2986  SCIPfreeBufferArrayNull(scip, &curvals);
2987  SCIPfreeBufferArrayNull(scip, &curvars);
2988 
2989  return SCIP_OKAY;
2990 }
2991 
2993 static
2994 SCIP_RETCODE computeNonzeros(
2995  SCIP* scip,
2996  DEC_DECOMP* decomp,
2997  int* mnzeros,
2998  int* mintnzeros,
2999  int* lnzeros,
3000  int* lintnzeros,
3001  int* nonzeros,
3002  int* intnzeros
3003  )
3004 {
3005  int c;
3006  int b;
3007 
3008  assert(scip != NULL);
3009  assert(decomp != NULL);
3010  assert(mnzeros != NULL);
3011  assert(mintnzeros != NULL);
3012  assert(lnzeros != NULL);
3013  assert(lintnzeros != NULL);
3014  assert(nonzeros != NULL);
3015  assert(intnzeros != NULL);
3016 
3017  for( b = 0; b < DECdecompGetNBlocks(decomp); ++b )
3018  {
3019  SCIP_CONS** subscipconss = DECdecompGetSubscipconss(decomp)[b];
3020  int nsubscipconss = DECdecompGetNSubscipconss(decomp)[b];
3021  for( c = 0; c < nsubscipconss; ++c )
3022  {
3023  SCIP_CALL( computeConssNzeros(scip, decomp, subscipconss[c], &(nonzeros[b]), &(intnzeros[b]), lnzeros, lintnzeros ) );
3024  }
3025  }
3026 
3027  for( c = 0; c < DECdecompGetNLinkingconss(decomp); ++c )
3028  {
3029  SCIP_CALL( computeConssNzeros(scip, decomp, DECdecompGetLinkingconss(decomp)[c], mnzeros, mintnzeros, lnzeros, lintnzeros ) );
3030  }
3031 
3032  return SCIP_OKAY;
3033 }
3034 
3037  SCIP* scip,
3038  FILE* file
3039  )
3040 {
3041  DEC_DECOMP* decomp;
3042  DEC_SCORES scores;
3043  SCIP_VAR** vars;
3044  SCIP_CONS** conss;
3045 
3046  int nvars;
3047  int nconss;
3048 
3049  int* nallvars;
3050  int* nbinvars;
3051  int* nintvars;
3052  int* nimplvars;
3053  int* ncontvars;
3054 
3055  int nblocks;
3056  int nblocksrelevant;
3057  int nlinkvars;
3058  int nlinkbinvar;
3059  int nlinkintvars;
3060  int nlinkimplvars;
3061  int nlinkcontvars;
3062  int b;
3063 
3064  int* varprobdensity;
3065  int* varmasterdensity;
3066  int* consprobsensity;
3067  int* consmasterdensity;
3068 
3069  DEC_STATISTIC* blockvardensities;
3070  DEC_STATISTIC* blockconsdensities;
3071  DEC_STATISTIC mastervardensity;
3072 
3073  int mnzeros;
3074  int mintnzeros;
3075  int lnzeros;
3076  int lintnzeros;
3077 
3078  int* nonzeros;
3079  int* intnzeros;
3080 
3081  assert(scip != NULL);
3082 
3083  decomp = DECgetBestDecomp(scip);
3084 
3085  if( decomp == NULL )
3086  {
3087  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "No decomposition available. Cannot output decomposition statistics.\n");
3088  return SCIP_OKAY;
3089  }
3090  assert(decomp != NULL);
3091  nblocks = DECdecompGetNBlocks(decomp);
3092 
3093  nvars = SCIPgetNVars(scip);
3094  nconss = DECdecompGetNConss(decomp);
3095 
3096  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nallvars, nblocks) );
3097  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nbinvars, nblocks) );
3098  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nintvars, nblocks) );
3099  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nimplvars, nblocks) );
3100  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ncontvars, nblocks) );
3101 
3102  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &blockvardensities, nblocks) );
3103  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &blockconsdensities, nblocks) );
3104 
3105  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &varprobdensity, nvars) );
3106  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &varmasterdensity, nvars) );
3107  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, nvars) );
3108  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conss, nconss) );
3109  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consprobsensity, nconss) );
3110  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consmasterdensity, nconss) );
3111 
3112  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nonzeros, nblocks) );
3113  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &intnzeros, nblocks) );
3114 
3115  BMSclearMemoryArray(nonzeros, nblocks);
3116  BMSclearMemoryArray(intnzeros, nblocks);
3117 
3118  mnzeros = 0;
3119  mintnzeros = 0;
3120  lnzeros = 0;
3121  lintnzeros = 0;
3122 
3123  SCIP_CALL( DECevaluateDecomposition(scip, decomp, &scores) );
3124 
3125  DECgetSubproblemVarsData(scip, decomp, nallvars, nbinvars, nintvars, nimplvars, ncontvars, nblocks);
3126  DECgetLinkingVarsData(scip, decomp, &nlinkvars, &nlinkbinvar, &nlinkintvars, &nlinkimplvars, &nlinkcontvars);
3127  SCIP_CALL( DECgetDensityData(scip, decomp, vars, nvars, conss, nconss, varprobdensity, varmasterdensity, consprobsensity, consmasterdensity) );
3128 
3129  SCIP_CALL( computeVarDensities(scip, decomp, varprobdensity, varmasterdensity, vars, nvars, blockvardensities, &mastervardensity, nblocks) );
3130  SCIP_CALL( computeNonzeros(scip, decomp, &mnzeros, &mintnzeros, &lnzeros, &lintnzeros, nonzeros, intnzeros) );
3131 
3132  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Decomp statistics :\n");
3133  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " type : %10s\n", DECgetStrType(DECdecompGetType(decomp)));
3134  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " detector : %10s\n", decomp->detector == NULL? "provided": DECdetectorGetName(decomp->detector));
3135  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " blocks : %10d\n", DECdecompGetNBlocks(decomp));
3136 
3137  nblocksrelevant = nblocks;
3138  if( SCIPgetStage(GCGgetMasterprob(scip)) >= SCIP_STAGE_PRESOLVED )
3139  {
3140  for( b = 0; b < nblocks; ++b )
3141  {
3142  if( GCGgetNIdenticalBlocks(scip, b) == 0 )
3143  nblocksrelevant -= 1;
3144  }
3145  }
3146  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " aggr. blocks : %10d\n", nblocksrelevant);
3147 
3148  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Master statistics : nvars nbinvars nintvars nimplvars ncontvars nconss nonzeros intnzeros bnzeros bintnzeros min(dens) max(dens) medi(dens) mean(dens)\n");
3149  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " master : %10d %10d %10d %10d %10d %10d %10d %10d %10d %10d %10.3f %10.3f %10.3f %10.3f\n", nlinkvars,
3150  nlinkbinvar, nlinkintvars, nlinkimplvars, nlinkcontvars, DECdecompGetNLinkingconss(decomp),
3151  mnzeros, mintnzeros, lnzeros, lintnzeros, mastervardensity.min, mastervardensity.max, mastervardensity.median, mastervardensity.mean);
3152 
3153  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Pricing statistics : nvars nbinvars nintvars nimplvars ncontvars nconss nonzeros intnzeros min(dens) max(dens) medi(dens) mean(dens) identical\n");
3154  for( b = 0; b < nblocks; ++b )
3155  {
3156  int identical = 0;
3157  SCIP_Bool relevant = TRUE;
3158 
3159  if( SCIPgetStage(GCGgetMasterprob(scip)) >= SCIP_STAGE_PRESOLVED )
3160  {
3161  relevant = GCGisPricingprobRelevant(scip, b);
3162  identical = GCGgetNIdenticalBlocks(scip, b);
3163  }
3164  if( relevant )
3165  {
3166  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " %10lld : %10d %10d %10d %10d %10d %10d %10d %10d %10.3f %10.3f %10.3f %10.3f %10d\n", b+1, nallvars[b], nbinvars[b], nintvars[b], nimplvars[b], ncontvars[b],
3167  DECdecompGetNSubscipconss(decomp)[b], nonzeros[b], intnzeros[b], blockvardensities[b].min, blockvardensities[b].max, blockvardensities[b].median, blockvardensities[b].mean, identical);
3168  }
3169  }
3170 
3171  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Decomp Scores :\n");
3172  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " border area : %10.3f\n", scores.borderscore);
3173  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " avg. density : %10.3f\n", scores.densityscore);
3174  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " linking score : %10.3f\n", scores.linkingscore);
3175 
3176  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
3177  SCIPfreeBlockMemoryArray(scip, &conss, nconss);
3178 
3179 
3180  SCIPfreeBlockMemoryArray(scip, &intnzeros, nblocks);
3181  SCIPfreeBlockMemoryArray(scip, &nonzeros, nblocks);
3182 
3183  SCIPfreeBlockMemoryArray(scip, &varprobdensity, nvars);
3184  SCIPfreeBlockMemoryArray(scip, &varmasterdensity, nvars);
3185  SCIPfreeBlockMemoryArray(scip, &consprobsensity, nconss);
3186  SCIPfreeBlockMemoryArray(scip, &consmasterdensity, nconss);
3187 
3188  SCIPfreeBlockMemoryArray(scip, &blockvardensities, nblocks);
3189  SCIPfreeBlockMemoryArray(scip, &blockconsdensities, nblocks);
3190 
3191  SCIPfreeBlockMemoryArray(scip, &nallvars, nblocks);
3192  SCIPfreeBlockMemoryArray(scip, &nbinvars, nblocks);
3193  SCIPfreeBlockMemoryArray(scip, &nintvars, nblocks);
3194  SCIPfreeBlockMemoryArray(scip, &nimplvars, nblocks);
3195  SCIPfreeBlockMemoryArray(scip, &ncontvars, nblocks);
3196 
3197  return SCIP_OKAY;
3198 }
3199 
3202  SCIP* scip,
3203  DEC_DECOMP* decomp1,
3204  DEC_DECOMP* decomp2
3205 )
3206 {
3207  SCIP_HASHMAP* constoblock1;
3208  SCIP_HASHMAP* constoblock2;
3209 
3210  SCIP_HASHMAP* vartoblock1;
3211  SCIP_HASHMAP* vartoblock2;
3212 
3213  SCIP_CONS** conss;
3214  int nconss;
3215 
3216  SCIP_VAR** vars;
3217  int nvars;
3218 
3219  int i;
3220 
3221  assert(scip != NULL);
3222  assert(decomp1 != NULL);
3223  assert(decomp2 != NULL);
3224 
3225  if( DECdecompGetNBlocks(decomp1) != DECdecompGetNBlocks(decomp2) )
3226  {
3227  return FALSE;
3228  }
3229 
3230  conss = SCIPgetConss(scip);
3231  nconss = SCIPgetNConss(scip);
3232 
3233  vars = SCIPgetVars(scip);
3234  nvars = SCIPgetNVars(scip);
3235 
3236  constoblock1 = DECdecompGetConstoblock(decomp1);
3237  constoblock2 = DECdecompGetConstoblock(decomp2);
3238  assert(constoblock1 != NULL);
3239  assert(constoblock2 != NULL);
3240 
3241  vartoblock1 = DECdecompGetVartoblock(decomp1);
3242  vartoblock2 = DECdecompGetVartoblock(decomp2);
3243  assert(vartoblock1 != NULL);
3244  assert(vartoblock2 != NULL);
3245 
3246  for( i = 0; i < nconss; ++i )
3247  {
3248  if( SCIPhashmapGetImage(constoblock1, conss[i]) != SCIPhashmapGetImage(constoblock2, conss[i]) )
3249  return FALSE;
3250  }
3251 
3252  for( i = 0; i < nvars; ++i )
3253  {
3254  if( SCIPhashmapGetImage(vartoblock1, vars[i]) != SCIPhashmapGetImage(vartoblock2, vars[i]) )
3255  return FALSE;
3256  }
3257 
3258  return TRUE;
3259 }
3260 
3265  SCIP* scip,
3266  DEC_DECOMP** decs,
3267  int ndecs
3268 )
3269 {
3270  int i;
3271  int j;
3272  int nunique;
3273  assert(scip != NULL);
3274  assert(decs != NULL);
3275  assert(ndecs > 0);
3276 
3277  nunique = ndecs;
3278  for( i = 0; i < nunique; ++i )
3279  {
3280  /*lint -e{850} j is modified in the body of the for loop */
3281  for( j = i+1; j < nunique; ++j )
3282  {
3283  DEC_DECOMP* tmp;
3284  if( DECdecompositionsAreEqual(scip, decs[i], decs[j]) )
3285  {
3286  tmp = decs[nunique-1];
3287  decs[nunique-1] = decs[j];
3288  decs[j] = tmp;
3289  --nunique;
3290  --j;
3291  }
3292  }
3293  }
3294  return nunique;
3295 }
3296 
3300  SCIP* scip,
3301  DEC_DECOMP* decomp,
3302  SCIP_CONS* cons,
3303  int *block
3304 )
3305 {
3306  SCIP_VAR** curvars = NULL;
3307  int ncurvars = 0;
3308  SCIP_Bool success = FALSE;
3309  int i;
3310  int nblocks ;
3311 
3312  int nmastervars = 0;
3313  int npricingvars = 0;
3314 
3315  SCIP_HASHMAP* vartoblock;
3316  assert(scip != NULL);
3317  assert(decomp != NULL);
3318  assert(cons != NULL);
3319  assert(block != NULL);
3320 
3321  *block = -2;
3322 
3323  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
3324  assert(success);
3325 
3326  if( ncurvars == 0 )
3327  return SCIP_OKAY;
3328 
3329  vartoblock= DECdecompGetVartoblock(decomp);
3330  assert(vartoblock != NULL);
3331 
3332  nblocks = DECdecompGetNBlocks(decomp);
3333 
3334  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3335  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
3336  assert(success);
3337 
3338  for( i = 0; i < ncurvars && *block != nblocks; ++i )
3339  {
3340  SCIP_VAR* var;
3341  int varblock;
3342 
3343  var = SCIPvarGetProbvar(curvars[i]);
3344 
3345  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
3346  continue;
3347 
3348  assert(SCIPhashmapExists(vartoblock, var));
3349  varblock = ((int) (size_t) SCIPhashmapGetImage(vartoblock, var))-1; /*lint !e507 */
3350 
3351  /* if variable is linking skip*/
3352  if( varblock == nblocks+1 )
3353  {
3354  continue;
3355  }
3356  else if( varblock == nblocks )
3357  {
3358  ++nmastervars;
3359  continue;
3360  }
3361  else if( *block != varblock )
3362  {
3363  ++npricingvars;
3364  if( *block < 0 )
3365  *block = varblock;
3366  else
3367  {
3368  assert(*block != nblocks);
3369  *block = nblocks;
3370  break;
3371  }
3372  }
3373  }
3374 
3375  SCIPfreeBufferArrayNull(scip, &curvars);
3376 
3377  if( ncurvars > 0 && *block == -2 )
3378  *block = nblocks;
3379 
3380  if( npricingvars == 0 && nmastervars > 0 )
3381  *block = -1;
3382 
3383  return SCIP_OKAY;
3384 }
3385 
3388  SCIP* scip,
3389  DEC_DECOMP* decomp,
3390  int consindex,
3391  int block
3392  )
3393 {
3394  SCIP_CONS* linkcons;
3395  SCIP_VAR** curvars = NULL;
3396  int ncurvars = 0;
3397  SCIP_Bool success = FALSE;
3398  int oldsize;
3399  int newsize;
3400  int v;
3401 
3402  assert(scip != NULL);
3403  assert(decomp != NULL);
3404  assert(consindex >= 0 && consindex < decomp->nlinkingconss);
3405  assert(block >= 0 && block < decomp->nblocks);
3406 
3407  linkcons = decomp->linkingconss[consindex];
3408 
3409  SCIP_CALL( SCIPgetConsNVars(scip, linkcons, &ncurvars, &success) );
3410  assert(success);
3411  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3412  SCIP_CALL( SCIPgetConsVars(scip, linkcons, curvars, ncurvars, &success) );
3413  assert(success);
3414 
3415  decomp->linkingconss[consindex] = decomp->linkingconss[decomp->nlinkingconss-1];
3416  decomp->nlinkingconss -= 1;
3417 
3418  oldsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[block]);
3419  newsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[block]+1);
3420  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->subscipconss[block], oldsize, newsize) ); /*lint !e866 */
3421  decomp->subscipconss[block][decomp->nsubscipconss[block]] = linkcons;
3422  decomp->nsubscipconss[block] += 1;
3423  SCIP_CALL( SCIPhashmapSetImage(decomp->constoblock, linkcons, (void*) (size_t)((size_t)block+1)) );
3424 
3425  for( v = 0; v < ncurvars; ++v )
3426  {
3427  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[v]);
3428 
3429  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
3430  continue;
3431 
3432  assert(SCIPhashmapExists(decomp->vartoblock, probvar));
3433  /* if variable is in master only, move to subproblem */
3434  if( (int) (size_t) SCIPhashmapGetImage(decomp->vartoblock, probvar) == decomp->nblocks+1 ) /*lint !e507 */
3435  {
3436  oldsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[block]);
3437  newsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[block] + 1);
3438  SCIP_CALL( SCIPhashmapSetImage(decomp->vartoblock, probvar, (void*) (size_t)(block+1)) );
3439  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->subscipvars[block], oldsize, newsize) ) /*lint !e866 */;
3440  decomp->subscipvars[block][decomp->nsubscipvars[block]] = probvar;
3441  decomp->nsubscipvars[block] += 1;
3442  SCIP_CALL( DECdecompRemoveLinkingVar(scip, decomp, probvar, &success) );
3443  assert(success);
3444  }
3445  }
3446 
3447  SCIPfreeBufferArrayNull(scip, &curvars);
3448  return SCIP_OKAY;
3449 }
3450 
3451 
3454  SCIP* scip,
3455  DEC_DECOMP* decomp,
3456  int* transferred
3457  )
3458 {
3459  int c;
3460  int linkingconssize;
3461  assert(scip != NULL);
3462  assert(decomp != NULL);
3463  assert(transferred != NULL);
3464  linkingconssize = decomp->nlinkingconss;
3465  *transferred = 0;
3466 
3467  /*lint -e{850} c is modified in the body of the for loop */
3468  for( c = 0; c < decomp->nlinkingconss; ++c )
3469  {
3470  int block;
3471  SCIP_CALL( DECdetermineConsBlock(scip, decomp, decomp->linkingconss[c], &block) );
3472 
3473  if( block == DECdecompGetNBlocks(decomp) || block < 0 )
3474  {
3475  continue;
3476  }
3477 
3478  SCIP_CALL( DECdecompMoveLinkingConsToPricing(scip, decomp, c, block) );
3479  --c;
3480  *transferred += 1;
3481  }
3482 
3483  if( *transferred > 0 )
3484  {
3485  if( decomp->nlinkingconss > 0 )
3486  {
3487  int oldsize = SCIPcalcMemGrowSize(scip, linkingconssize);
3488  int newsize = SCIPcalcMemGrowSize(scip, decomp->nlinkingconss);
3489  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->linkingconss, oldsize, newsize) );
3490  }
3491  else
3492  {
3493  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingconss, SCIPcalcMemGrowSize(scip, linkingconssize));
3494  }
3495  }
3496 
3497  return SCIP_OKAY;
3498 }
3499 
3502  SCIP* scip,
3503  DEC_DECOMP* decomp,
3504  SCIP_VAR* var,
3505  SCIP_Bool* success
3506  )
3507 {
3508  int v;
3509  int linkingvarsize;
3510  assert(scip != NULL);
3511  assert(decomp != NULL);
3512  assert(var != NULL);
3513  assert(success != NULL);
3514 
3515  *success = FALSE;
3516  linkingvarsize = decomp->nlinkingvars;
3517 
3518  for( v = 0; v < decomp->nlinkingvars; ++v )
3519  {
3520  if( decomp->linkingvars[v] == var )
3521  {
3522  decomp->linkingvars[v] = decomp->linkingvars[decomp->nlinkingvars-1];
3523  decomp->nlinkingvars -= 1;
3524  *success = TRUE;
3525  }
3526  }
3527 
3528  if( *success )
3529  {
3530  if( decomp->nlinkingvars == 0 )
3531  {
3532  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingvars, SCIPcalcMemGrowSize(scip, linkingvarsize));
3533  if( DECdecompGetNLinkingconss(decomp) == 0 )
3534  {
3535  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_DIAGONAL) );
3536  }
3537  else
3538  {
3539  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_BORDERED) );
3540  }
3541  }
3542  else
3543  {
3544  int oldsize = SCIPcalcMemGrowSize(scip, linkingvarsize);
3545  int newsize = SCIPcalcMemGrowSize(scip, decomp->nlinkingvars);
3546  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->linkingvars, oldsize, newsize) );
3547  }
3548  }
3549  return SCIP_OKAY;
3550 }
3551 
3554  SCIP* scip,
3555  DEC_DECOMP* decomp,
3556  DEC_DECOMP** newdecomp,
3557  int* transferred
3558  )
3559 {
3560  int c;
3561 
3562  assert(scip != NULL);
3563  assert(decomp != NULL);
3564  assert(newdecomp != NULL);
3565  assert(transferred != NULL);
3566 
3567  *newdecomp = NULL;
3568  *transferred = 0;
3569 
3570  for( c = 0; c < decomp->nlinkingconss; ++c )
3571  {
3572  int block;
3573  int i;
3574  int nconss;
3575  SCIP_HASHMAP* constoblock;
3576  SCIP_CALL( DECdetermineConsBlock(scip, decomp, decomp->linkingconss[c], &block) );
3577 
3578  if( block >= 0 )
3579  {
3580  continue;
3581  }
3582  SCIPdebugMessage("Cons <%s> in new pricing problem\n", SCIPconsGetName(decomp->linkingconss[c]));
3583  nconss = SCIPgetNConss(scip);
3584  SCIP_CALL( DECdecompCreate(scip, newdecomp) );
3585  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), SCIPgetNConss(scip)) );
3586 
3587  for( i = 0; i < nconss; ++i )
3588  {
3589  int consblock;
3590  SCIP_CONS* cons = SCIPgetConss(scip)[i];
3591  assert(SCIPhashmapExists(decomp->constoblock, cons));
3592  consblock = (int) (size_t) SCIPhashmapGetImage(decomp->constoblock, cons); /*lint !e507 */
3593  SCIPdebugMessage("Cons <%s> %d -> %d\n", SCIPconsGetName(cons), consblock, consblock+1);
3594 
3595  SCIP_CALL( SCIPhashmapSetImage(constoblock, cons, (void*) (size_t) (consblock+1)) );
3596  }
3597  SCIP_CALL( SCIPhashmapSetImage(constoblock, decomp->linkingconss[c], (void*) (size_t) (1)) );
3598  SCIPdebugMessage("Cons <%s> -> %d\n", SCIPconsGetName(decomp->linkingconss[c]), 1);
3599 
3600  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, *newdecomp, constoblock, decomp->nblocks+1, FALSE) );
3601  *transferred += 1;
3602  break;
3603  }
3604 
3605  return SCIP_OKAY;
3606 }
3607 
3610  SCIP* scip,
3611  DEC_DECOMP* decomp,
3612  DEC_DECOMP** newdecomp
3613  )
3614 {
3615  int transferredexisting = 0;
3616  int transferrednew = 0;
3617  DEC_DECOMP* origdecomp = decomp;
3618  DEC_DECOMP* tempdecomp = NULL;
3619 
3620  assert(scip != NULL);
3621  assert(decomp != NULL);
3622  assert(newdecomp != NULL);
3623 
3624  if( DECdecompGetNBlocks(decomp) == 1 )
3625  {
3626  *newdecomp = NULL;
3627  return SCIP_OKAY;
3628  }
3629  *newdecomp = decomp;
3630 
3631  do
3632  {
3633  SCIP_CALL( DECtryAssignMasterconssToExistingPricing(scip, *newdecomp, &transferredexisting) );
3634  SCIPdebugMessage("%d conss transferred to existing pricing\n", transferredexisting);
3635  SCIP_CALL( DECtryAssignMasterconssToNewPricing(scip, *newdecomp, &tempdecomp, &transferrednew) );
3636  SCIPdebugMessage("%d conss transferred to new pricing\n", transferrednew);
3637  if( transferrednew > 0 )
3638  {
3639  if( *newdecomp != origdecomp )
3640  {
3641  SCIP_CALL( DECdecompFree(scip, newdecomp) );
3642  }
3643  *newdecomp = tempdecomp;
3644  }
3645  } while( transferredexisting > 0 || transferrednew > 0 );
3646 
3647  if( *newdecomp == origdecomp )
3648  {
3649  *newdecomp = NULL;
3650  }
3651 
3652  return SCIP_OKAY;
3653 }
3654 
3656 SCIP_RETCODE DECpermuteDecomp(
3657  SCIP* scip,
3658  DEC_DECOMP* decomp,
3659  SCIP_RANDNUMGEN* randnumgen
3660  )
3661 {
3662  int b;
3663  int npricingprobs;
3664  assert(scip != NULL);
3665  assert(decomp != NULL);
3666 
3667  npricingprobs = DECdecompGetNBlocks(decomp);
3668 
3669  /* Permute individual variables and constraints of pricing problems */
3670  for( b = 0; b < npricingprobs; ++b )
3671  {
3672  SCIP_CONS*** subscipconss;
3673  SCIP_VAR*** subscipvars;
3674  int *nsubscipconss = DECdecompGetNSubscipconss(decomp);
3675  int *nsubscipvars = DECdecompGetNSubscipvars(decomp);
3676  subscipconss = DECdecompGetSubscipconss(decomp);
3677 
3678  SCIPrandomPermuteArray(randnumgen, (void**)(subscipconss[b]), 0, nsubscipconss[b]);
3679 
3680  subscipvars = DECdecompGetSubscipvars(decomp);
3681  SCIPrandomPermuteArray(randnumgen, (void**)(subscipvars[b]), 0, nsubscipvars[b]);
3682  }
3683 
3684  if( DECdecompGetNLinkingconss(decomp) > 0 )
3685  {
3686  SCIP_CONS** linkingconss = DECdecompGetLinkingconss(decomp);
3687  SCIPrandomPermuteArray(randnumgen, (void**)linkingconss, 0, DECdecompGetNLinkingconss(decomp));
3688  }
3689 
3690  if( DECdecompGetNLinkingvars(decomp) > 0 )
3691  {
3692  SCIP_VAR** linkingvars = DECdecompGetLinkingvars(decomp);;
3693  SCIPrandomPermuteArray(randnumgen, (void**)linkingvars, 0, DECdecompGetNLinkingvars(decomp));
3694  }
3695 
3696  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
3697  return SCIP_OKAY;
3698 }
SCIP_CONS *** DECdecompGetSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:729
SCIP_Bool DECdecompositionsAreEqual(SCIP *scip, DEC_DECOMP *decomp1, DEC_DECOMP *decomp2)
Definition: decomp.c:3201
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:2948
static SCIP_RETCODE computeVarDensities(SCIP *scip, DEC_DECOMP *decomp, int *varprobdensity, int *varmasterdensity, SCIP_VAR **vars, int nvars, DEC_STATISTIC *blockvardensities, DEC_STATISTIC *mastervardensity, int nblocks)
Definition: decomp.c:2770
SCIP_RETCODE DECgetVarLockData(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR **vars, int nvars, int nsubproblems, int **subsciplocksdown, int **subsciplocksup, int *masterlocksdown, int *masterlocksup)
Definition: decomp.c:2444
struct DEC_Detector DEC_DETECTOR
Definition: type_detector.h:49
static void incVarsData(SCIP_VAR *var, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars, int nproblems, int i)
Definition: decomp.c:2125
int * DECdecompGetNStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:945
const char * DECgetStrType(DEC_DECTYPE type)
Definition: decomp.c:342
SCIP_RETCODE DECdecompSetStairlinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***stairlinkingvars, int *nstairlinkingvars)
Definition: decomp.c:872
GCG interface methods.
SCIP_RETCODE DECdecompMoveLinkingConsToPricing(SCIP *scip, DEC_DECOMP *decomp, int consindex, int block)
Definition: decomp.c:3387
void DECdecompSetVarindex(DEC_DECOMP *decomp, SCIP_HASHMAP *varindex)
Definition: decomp.c:999
DEC_DECOMP * DECgetBestDecomp(SCIP *scip)
Definition: cons_decomp.c:735
const char * DECdetectorGetName(DEC_DETECTOR *detector)
Definition: cons_decomp.c:365
SCIP_HASHMAP * DECdecompGetVartoblock(DEC_DECOMP *decomp)
Definition: decomp.c:967
SCIP_RETCODE DECdecompSetLinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR **linkingvars, int nlinkingvars)
Definition: decomp.c:810
SCIP_RETCODE DECcreatePolishedDecomp(SCIP *scip, DEC_DECOMP *decomp, DEC_DECOMP **newdecomp)
Definition: decomp.c:3609
static SCIP_RETCODE fillOutVarsFromVartoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock, int nblocks, SCIP_VAR **vars, int nvars, SCIP_Bool *haslinking)
Definition: decomp.c:120
SCIP_RETCODE GCGprintDecompStatistics(SCIP *scip, FILE *file)
Definition: decomp.c:3036
static SCIP_RETCODE assignConstraintsToRepresentatives(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *consismaster, SCIP_HASHMAP *constoblock, int *vartoblock, int *nextblock, int *blockrepresentative)
Definition: decomp.c:1815
SCIP_RETCODE DECdetermineConsBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS *cons, int *block)
Definition: decomp.c:3299
void DECgetSubproblemVarsData(SCIP *scip, DEC_DECOMP *decomp, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars, int nproblems)
Definition: decomp.c:2164
SCIP_RETCODE DECtryAssignMasterconssToNewPricing(SCIP *scip, DEC_DECOMP *decomp, DEC_DECOMP **newdecomp, int *transferred)
Definition: decomp.c:3553
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:412
SCIP_VAR *** DECdecompGetStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:936
int DECfilterSimilarDecompositions(SCIP *scip, DEC_DECOMP **decs, int ndecs)
Definition: decomp.c:3264
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:2868
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:388
SCIP_Real min
Definition: decomp.c:53
int DECdecompGetNConss(DEC_DECOMP *decomp)
Definition: decomp.c:2908
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:861
void DECdecompSetNBlocks(DEC_DECOMP *decomp, int nblocks)
Definition: decomp.c:560
static SCIP_Real quick_select_median(SCIP_Real arr[], int n)
Definition: decomp.c:59
SCIP_RETCODE DECcreateDecompFromMasterconss(SCIP *scip, DEC_DECOMP **decomp, SCIP_CONS **masterconss, int nmasterconss)
Definition: decomp.c:2042
static SCIP_RETCODE fillOutConsFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_CONS **conss, int nconss, SCIP_Bool *haslinking)
Definition: decomp.c:233
void DECdecompSetVartoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock)
Definition: decomp.c:955
int DECdecompGetNLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:798
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:582
SCIP_RETCODE DECdecompRemoveDeletedConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:1508
DEC_DECTYPE DECdecompGetType(DEC_DECOMP *decomp)
Definition: decomp.c:529
int DECdecompGetNBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:572
various SCIP helper methods
enum Dectype DEC_DECTYPE
Definition: type_decomp.h:55
SCIP_Real mean
Definition: decomp.c:50
SCIP_VAR *** DECdecompGetSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:647
SCIP_RETCODE DECtryAssignMasterconssToExistingPricing(SCIP *scip, DEC_DECOMP *decomp, int *transferred)
Definition: decomp.c:3453
void DECdecompSetDetector(DEC_DECOMP *decomp, DEC_DETECTOR *detector)
Definition: decomp.c:1346
SCIP_RETCODE DECcreateBasicDecomp(SCIP *scip, DEC_DECOMP **decomp)
Definition: decomp.c:1742
SCIP_RETCODE DECpermuteDecomp(SCIP *scip, DEC_DECOMP *decomp, SCIP_RANDNUMGEN *randnumgen)
Definition: decomp.c:3656
GCG relaxator.
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:351
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:788
SCIP_VAR ** DECdecompGetLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:851
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:462
int * DECdecompGetNSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:738
DEC_DETECTOR * DECdecompGetDetector(DEC_DECOMP *decomp)
Definition: decomp.c:1357
private methods for working with decomp structures
SCIP_RETCODE DECdecompCheckConsistency(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:1631
SCIP_Real borderscore
Definition: pub_decomp.h:54
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:40
SCIP_RETCODE DECdecompTransform(SCIP *scip, DEC_DECOMP *decomp)
Definition: decomp.c:1367
SCIP_RETCODE DECdecompSetType(DEC_DECOMP *decomp, DEC_DECTYPE type)
Definition: decomp.c:485
SCIP_Real median
Definition: decomp.c:51
SCIP_Real totalscore
Definition: pub_decomp.h:57
static int processBlockRepresentatives(int maxblock, int *blockrepresentative)
Definition: decomp.c:1780
SCIP_HASHMAP * DECdecompGetConstoblock(DEC_DECOMP *decomp)
Definition: decomp.c:989
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:102
SCIP_RETCODE DECdecompSetSubscipconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS ***subscipconss, int *nsubscipconss)
Definition: decomp.c:667
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:196
void DECdecompSetConsindex(DEC_DECOMP *decomp, SCIP_HASHMAP *consindex)
Definition: decomp.c:1019
static SCIP_RETCODE computeNonzeros(SCIP *scip, DEC_DECOMP *decomp, int *mnzeros, int *mintnzeros, int *lnzeros, int *lintnzeros, int *nonzeros, int *intnzeros)
Definition: decomp.c:2994
static SCIP_RETCODE fillConstoblock(SCIP_CONS **conss, int nconss, SCIP_Bool *consismaster, int nblocks, SCIP_HASHMAP *constoblock, SCIP_HASHMAP *newconstoblock, int *blockrepresentative)
Definition: decomp.c:1997
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1225
SCIP_RETCODE DECdecompSetLinkingconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS **linkingconss, int nlinkingconss)
Definition: decomp.c:747
SCIP_HASHMAP * DECdecompGetConsindex(DEC_DECOMP *decomp)
Definition: decomp.c:1030
int * DECdecompGetNSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:657
SCIP_RETCODE DECdecompSetSubscipvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***subscipvars, int *nsubscipvars)
Definition: decomp.c:582
SCIP_Real max
Definition: decomp.c:52
static void increaseLock(SCIP *scip, SCIP_Real lhs, SCIP_Real coef, SCIP_Real rhs, int *downlock, int *uplock)
Definition: decomp.c:2406
void DECdecompSetPresolved(DEC_DECOMP *decomp, SCIP_Bool presolved)
Definition: decomp.c:539
SCIP_RETCODE DECevaluateDecomposition(SCIP *scip, DEC_DECOMP *decdecomp, DEC_SCORES *score)
Definition: decomp.c:2580
void DECdecompSetConstoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock)
Definition: decomp.c:977
constraint handler for structure detection
SCIP_RETCODE DECfilloutDecompFromHashmaps(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1039
SCIP_Real linkingscore
Definition: pub_decomp.h:56
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
static SCIP_RETCODE computeConssNzeros(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS *cons, int *nzeros, int *nintzeros, int *nbzeros, int *nintbzeros)
Definition: decomp.c:2925
SCIP_HASHMAP * DECdecompGetVarindex(DEC_DECOMP *decomp)
Definition: decomp.c:1010
SCIP_Bool GCGisConsGCGCons(SCIP_CONS *cons)
Definition: misc.c:464
SCIP_RETCODE DECdecompRemoveLinkingVar(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR *var, SCIP_Bool *success)
Definition: decomp.c:3501
SCIP_Real densityscore
Definition: pub_decomp.h:55
SCIP_RETCODE DECdecompAddRemainingConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:1558
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:2996
SCIP_RETCODE DECgetDensityData(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR **vars, int nvars, SCIP_CONS **conss, int nconss, int *varsubproblemdensity, int *varmasterdensity, int *conssubproblemdensity, int *consmasterdensity)
Definition: decomp.c:2263
void DECgetLinkingVarsData(SCIP *scip, DEC_DECOMP *decomp, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: decomp.c:2213
#define ELEM_SWAP(a, b)
Definition: decomp.c:56
SCIP_Bool DECdecompGetPresolved(DEC_DECOMP *decomp)
Definition: decomp.c:550