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-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 //#define SCIP_DEBUG
41 
42 #include "decomp.h"
43 #include "gcg.h"
44 #include "cons_decomp.h"
45 #include "scip/scip.h"
46 #include "struct_decomp.h"
47 #include "scip_misc.h"
48 #include "relax_gcg.h"
49 
50 
51 #include <assert.h>
52 
53 typedef struct {
54  SCIP_Real mean;
55  SCIP_Real median;
56  SCIP_Real max;
57  SCIP_Real min;
59 
60 #define ELEM_SWAP(a,b) { register SCIP_Real t=(a);(a)=(b);(b)=t; }
61 
62 static
63 SCIP_Real quick_select_median(SCIP_Real arr[], int n)
64 {
65  int low, high;
66  int median;
67 
68  low = 0;
69  high = n - 1;
70  median = high / 2;
71 
72  for( ;; )
73  {
74  int middle, ll, hh;
75  if( high <= low ) /* One element only */
76  return arr[median];
77 
78  if( high == low + 1 ) /* Two elements only */
79  {
80  if( arr[low] > arr[high] )
81  ELEM_SWAP(arr[low], arr[high]);
82  return arr[median];
83  }
84 
85  /* Find median of low, middle and high items; swap into position low */
86  middle = (low + high) / 2;
87  if( arr[middle] > arr[high] )
88  ELEM_SWAP(arr[middle], arr[high]);
89  if( arr[low] > arr[high] )
90  ELEM_SWAP(arr[low], arr[high]);
91  if( arr[middle] > arr[low] )
92  ELEM_SWAP(arr[middle], arr[low]);
93  /* Swap low item (now in position middle) into position (low+1) */
94  ELEM_SWAP(arr[middle], arr[(size_t) (low + 1)]);
95  /* Nibble from each end towards middle, swapping items when stuck */
96  ll = low + 1;
97  hh = high;
98  for( ;; )
99  {
100  do
101  ll++;
102  while( arr[low] > arr[ll] );
103  do
104  hh--;
105  while( arr[hh] > arr[low] );
106  if( hh < ll )
107  break;
108  ELEM_SWAP(arr[ll], arr[hh]);
109  }
110  /* Swap middle item (in position low) back into correct position */
111  ELEM_SWAP(arr[low], arr[hh]);
112 
113  /* Re-set active partition */
114  if( hh <= median )
115  low = ll;
116  if( hh >= median )
117  high = hh - 1;
118  }
119 }
120 
121 
123 static
125  SCIP* scip,
126  DEC_DECOMP* decomp,
127  SCIP_HASHMAP* vartoblock,
128  int nblocks,
129  SCIP_VAR** vars,
130  int nvars,
131  SCIP_Bool* haslinking
132  )
133 {
134  SCIP_VAR*** subscipvars;
135  int* nsubscipvars;
136 
137  SCIP_VAR** linkingvars;
138  int nlinkingvars;
139  int nmastervars;
140  int i;
141 
142  assert(scip != NULL);
143  assert(decomp != NULL);
144  assert(vartoblock != NULL);
145  assert(nblocks >= 0);
146  assert(vars != NULL);
147  assert(nvars > 0);
148 
149  SCIP_CALL( SCIPallocBufferArray(scip, &linkingvars, nvars) );
150  SCIP_CALL( SCIPallocBufferArray(scip, &nsubscipvars, nblocks) );
151  SCIP_CALL( SCIPallocBufferArray(scip, &subscipvars, nblocks) );
152 
153  nlinkingvars = 0;
154  nmastervars = 0;
155 
156  *haslinking = FALSE;
157 
158  for( i = 0; i < nblocks; ++i )
159  {
160  SCIP_CALL( SCIPallocBufferArray(scip, &subscipvars[i], nvars) ); /*lint !e866*/
161  nsubscipvars[i] = 0;
162  }
163 
164  /* handle variables */
165  for( i = 0; i < nvars; ++i )
166  {
167  int block;
168  SCIP_VAR* var;
169 
170  var = vars[i];
171  assert(var != NULL);
172  assert(SCIPvarIsActive(var));
173 
174  if( !SCIPhashmapExists(vartoblock, var) )
175  block = nblocks+1;
176  else
177  {
178  block = (int)(size_t)SCIPhashmapGetImage(vartoblock, var); /*lint !e507*/
179  }
180 
181  assert(block > 0 && block <= nblocks+2);
182 
183  /* if variable belongs to a block */
184  if( block <= nblocks )
185  {
186  SCIPdebugMessage("var %s in block %d.\n", SCIPvarGetName(var), block-1);
187  subscipvars[block-1][nsubscipvars[block-1]] = var;
188  ++(nsubscipvars[block-1]);
189  }
190  else /* variable is linking or master*/
191  {
192  assert(block == nblocks+1 || block == nblocks+2 );
193 
194  if( block == nblocks+2 )
195  SCIPdebugMessage("var %s is linking.\n", SCIPvarGetName(var));
196  else
197  {
198  SCIPdebugMessage("var %s is in master only.\n", SCIPvarGetName(var));
199  ++nmastervars;
200  }
201  linkingvars[nlinkingvars] = var;
202  ++nlinkingvars;
203  }
204  }
205 
206  if( nlinkingvars > 0 )
207  {
208  SCIP_CALL( DECdecompSetLinkingvars(scip, decomp, linkingvars, nlinkingvars, 0, nmastervars) );
209  *haslinking = TRUE;
210  }
211 
212  for( i = nblocks-1; i >= 0; --i )
213  {
214  if( nsubscipvars[i] == 0 )
215  {
216  SCIPfreeBufferArray(scip, &subscipvars[i]);
217  subscipvars[i] = NULL;
218  }
219  }
220  if( nblocks > 0 )
221  {
222  SCIP_CALL( DECdecompSetSubscipvars(scip, decomp, subscipvars, nsubscipvars) );
223  }
224  DECdecompSetVartoblock(decomp, vartoblock);
225 
226  for( i = nblocks-1; i >= 0; --i )
227  {
228  SCIPfreeBufferArrayNull(scip, &subscipvars[i]);
229  }
230 
231  SCIPfreeBufferArray(scip, &subscipvars);
232  SCIPfreeBufferArray(scip, &nsubscipvars);
233  SCIPfreeBufferArray(scip, &linkingvars);
234 
235  return SCIP_OKAY;
236 }
237 
238 
240 static
242  SCIP* scip,
243  DEC_DECOMP* decomp,
244  SCIP_HASHMAP* constoblock,
245  int nblocks,
246  SCIP_CONS** conss,
247  int nconss,
248  SCIP_Bool* haslinking
249  )
250 {
251  SCIP_RETCODE retcode;
252 
253  SCIP_CONS*** subscipconss;
254  int* nsubscipconss;
255 
256  SCIP_CONS** linkingconss;
257  int nlinkingconss;
258  int i;
259  assert(scip != NULL);
260  assert(decomp != NULL);
261  assert(constoblock != NULL);
262  assert(nblocks >= 0);
263  assert(conss != NULL);
264  assert(nconss > 0);
265  assert(haslinking != NULL);
266 
267  DECdecompSetConstoblock(decomp, constoblock);
268 
269  SCIP_CALL( SCIPallocBufferArray(scip, &linkingconss, nconss) );
270  SCIP_CALL( SCIPallocBufferArray(scip, &nsubscipconss, nblocks) );
271  SCIP_CALL( SCIPallocBufferArray(scip, &subscipconss, nblocks) );
272 
273  *haslinking = FALSE;
274  retcode = SCIP_OKAY;
275  for( i = 0; i < nblocks; ++i )
276  {
277  SCIP_CALL( SCIPallocBufferArray(scip, &subscipconss[i], nconss) ); /*lint !e866*/
278  nsubscipconss[i] = 0;
279  }
280 
281  nlinkingconss = 0;
282 
283  /* handle constraints */
284  for( i = 0; i < nconss; ++i )
285  {
286  int block;
287  SCIP_CONS* cons;
288  int nvars;
289  SCIP_Bool success;
290 
291  cons = conss[i];
292  assert(cons != NULL);
293 
294  if( !SCIPhashmapExists(decomp->constoblock, cons) )
295  {
296  block = nblocks+1;
297  SCIP_CALL( SCIPhashmapInsert(decomp->constoblock, cons, (void*) (size_t) block) );
298  }
299  else
300  {
301  block = (int)(size_t)SCIPhashmapGetImage(decomp->constoblock, cons); /*lint !e507*/
302  }
303 
304  assert(block > 0 && block <= nblocks+1);
305 
306  SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) );
307  assert(success);
308  if( nvars == 0 )
309  continue;
310 
311  /* if constraint belongs to a block */
312  if( block <= nblocks )
313  {
314  SCIPdebugMessage("cons %s in block %d.\n", SCIPconsGetName(cons), block-1);
315  subscipconss[block-1][nsubscipconss[block-1]] = cons;
316  ++(nsubscipconss[block-1]);
317  }
318  else /* constraint is linking */
319  {
320  SCIPdebugMessage("cons %s is linking.\n", SCIPconsGetName(cons));
321  assert(block == nblocks+1);
322  linkingconss[nlinkingconss] = cons;
323  ++nlinkingconss;
324  }
325  }
326 
327  if( nlinkingconss > 0 )
328  {
329  retcode = DECdecompSetLinkingconss(scip, decomp, linkingconss, nlinkingconss);
330  *haslinking = TRUE;
331  }
332  if( nblocks > 0 )
333  {
334  retcode = DECdecompSetSubscipconss(scip, decomp, subscipconss, nsubscipconss);
335  }
336 
337  for( i = nblocks-1; i >= 0; --i )
338  {
339  SCIPfreeBufferArray(scip, &subscipconss[i]);
340  }
341 
342  SCIPfreeBufferArray(scip, &subscipconss);
343  SCIPfreeBufferArray(scip, &nsubscipconss);
344  SCIPfreeBufferArray(scip, &linkingconss);
345 
346  return retcode;
347 }
348 
350 static
352  SCIP* scip,
353  DEC_DECOMP* decomp,
354  SCIP_VAR* var,
355  SCIP_Bool* success
356  )
357 {
358  int v;
359  int linkingvarsize;
360  assert(scip != NULL);
361  assert(decomp != NULL);
362  assert(var != NULL);
363  assert(success != NULL);
364 
365  *success = FALSE;
366  linkingvarsize = decomp->nlinkingvars;
367 
368  for( v = 0; v < decomp->nlinkingvars; ++v )
369  {
370  if( decomp->linkingvars[v] == var )
371  {
372  decomp->linkingvars[v] = decomp->linkingvars[decomp->nlinkingvars-1];
373  decomp->nlinkingvars -= 1;
374  *success = TRUE;
375  }
376  }
377 
378  if( *success )
379  {
380  if( decomp->nlinkingvars == 0 )
381  {
382  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingvars, SCIPcalcMemGrowSize(scip, linkingvarsize));
383  if( DECdecompGetNLinkingconss(decomp) == 0 )
384  {
385  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_DIAGONAL) );
386  }
387  else
388  {
389  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_BORDERED) );
390  }
391  }
392  else
393  {
394  int oldsize = SCIPcalcMemGrowSize(scip, linkingvarsize);
395  int newsize = SCIPcalcMemGrowSize(scip, decomp->nlinkingvars);
396  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->linkingvars, oldsize, newsize) );
397  }
398  }
399  return SCIP_OKAY;
400 }
401 
405 static
407  SCIP* scip,
408  DEC_DECOMP* decomp,
409  SCIP_CONS* cons,
410  int block
411  )
412 {
413  SCIP_VAR** curvars;
414  int ncurvars;
415 
416  SCIP_Bool success;
417  int v;
418 
419  curvars = NULL;
420  ncurvars = 0;
421 
422  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
423  assert(success);
424  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
425  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
426  assert(success);
427 
428  for( v = 0; v < ncurvars; ++v )
429  {
430  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[v]);
431 
432  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
433  continue;
434 
435  assert(SCIPhashmapExists(decomp->vartoblock, probvar));
436  /* if variable is in master only, move to subproblem */
437  if( (int) (size_t) SCIPhashmapGetImage(decomp->vartoblock, probvar) == decomp->nblocks+1 ) /*lint !e507 */
438  {
439  int oldsize;
440  int newsize;
441  oldsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[block]);
442  newsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[block] + 1);
443  SCIP_CALL( SCIPhashmapSetImage(decomp->vartoblock, probvar, (void*) (size_t)(block+1)) );
444  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->subscipvars[block], oldsize, newsize) ) /*lint !e866 */;
445  decomp->subscipvars[block][decomp->nsubscipvars[block]] = probvar;
446  decomp->nsubscipvars[block] += 1;
447  SCIP_CALL( removeFromLinkingvars(scip, decomp, probvar, &success) );
448  assert(success);
449  }
450  }
451 
452  SCIPfreeBufferArrayNull(scip, &curvars);
453 
454  return SCIP_OKAY;
455 }
456 
457 
458 const char *DECgetStrType(
459  DEC_DECTYPE type
460  )
461 {
462  const char * names[] = { "unknown", "arrowhead", "staircase", "diagonal", "bordered" };
463  return names[type];
464 }
465 
467 SCIP_RETCODE DECdecompCreate(
468  SCIP* scip,
469  DEC_DECOMP** decdecomp
470  )
471 {
472  DEC_DECOMP* decomp;
473 
474  int ncalls;
475 
476  assert(scip != NULL);
477  assert(decdecomp != NULL);
478 
479  SCIP_CALL( SCIPallocMemory(scip, decdecomp) );
480  assert(*decdecomp != NULL);
481  decomp = *decdecomp;
482 
483  decomp->type = DEC_DECTYPE_UNKNOWN;
484  decomp->constoblock = NULL;
485  decomp->vartoblock = NULL;
486  decomp->subscipvars = NULL;
487  decomp->subscipconss = NULL;
488  decomp->nsubscipconss = NULL;
489  decomp->nsubscipvars = NULL;
490  decomp->linkingconss = NULL;
491  decomp->nlinkingconss = 0;
492  decomp->linkingvars = NULL;
493  decomp->nlinkingvars = 0;
494  decomp->nfixedlinkingvars = 0;
495  decomp->stairlinkingvars = NULL;
496  decomp->nstairlinkingvars = NULL;
497  decomp->nblocks = 0;
498  decomp->presolved = (SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVING);
499  decomp->consindex = NULL;
500  decomp->varindex = NULL;
501  decomp->detector = NULL;
502 
503  decomp->detectorchain = NULL;
504  decomp->sizedetectorchain = 0;
505  decomp->detectorchainstring = NULL;
506  decomp->seeedid = -1;
507  decomp->detectorclocktimes = NULL;
508  decomp->pctvarstoborder= NULL;
509  decomp->pctconsstoborder= NULL;
510  decomp->pctvarstoblock= NULL;
511  decomp->pctconsstoblock= NULL;
512  decomp->pctvarsfromopen= NULL;
513  decomp->pctconssfromopen= NULL;
514  decomp->nnewblocks= NULL;
515  decomp->maxwhitescore = -1.;
516 
518 
519  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "ncalls of createdecompfromseeed: %d \n", ncalls);
520 
521  return SCIP_OKAY;
522 }
523 
525 SCIP_RETCODE DECdecompFree(
526  SCIP* scip,
527  DEC_DECOMP** decdecomp
528  )
529 {
530  DEC_DECOMP* decomp;
531  int i;
532  int j;
533  int ncalls;
534 
535  assert( scip!= NULL );
536  assert( decdecomp != NULL);
537  decomp = *decdecomp;
538 
539  assert(decomp != NULL);
540 
541  for( i = 0; i < decomp->nblocks; ++i )
542  {
543  if( decomp->nsubscipvars != NULL )
544  {
545  for( j = 0; j < decomp->nsubscipvars[i]; ++j )
546  {
547  if( decomp->subscipvars[i][j] != NULL )
548  {
549  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->subscipvars[i][j])) );
550  }
551  }
552 
553  SCIPfreeBlockMemoryArrayNull(scip, &(decomp->subscipvars[i]), SCIPcalcMemGrowSize(scip, decomp->nsubscipvars[i])); /*lint !e866*/
554 
555  }
556  if( decomp->nsubscipconss != NULL )
557  {
558  for( j = 0; j < decomp->nsubscipconss[i]; ++j )
559  {
560  if( decomp->subscipconss[i][j] != NULL )
561  {
562  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->subscipconss[i][j])) );
563  }
564  }
565  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipconss[i], SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[i])); /*lint !e866*/
566  }
567  }
568 
569  if( decomp->linkingvars != NULL )
570  {
571  for( i = 0; i < decomp->nlinkingvars; ++i )
572  {
573  if( decomp->linkingvars[i] != NULL )
574  {
575  if( decomp->linkingvars[i] != NULL )
576  {
577  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->linkingvars[i])) );
578  }
579  }
580  }
581  }
582 
583  if( decomp->stairlinkingvars != NULL )
584  for( i = 0; i < decomp->nblocks-1; ++i )
585  {
586  for( j = 0; j < decomp->nstairlinkingvars[i]; ++j )
587  {
588  if( decomp->stairlinkingvars[i][j] != NULL )
589  {
590  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->stairlinkingvars[i][j])) );
591  }
592  }
593  SCIPfreeBlockMemoryArrayNull(scip, &decomp->stairlinkingvars[i], SCIPcalcMemGrowSize(scip, decomp->nstairlinkingvars[i])); /*lint !e866*/
594  }
595 
596  /* free hashmaps if they are not NULL */
597  if( decomp->constoblock != NULL )
598  SCIPhashmapFree(&decomp->constoblock);
599  if( decomp->vartoblock != NULL )
600  SCIPhashmapFree(&decomp->vartoblock);
601  if( decomp->varindex != NULL )
602  SCIPhashmapFree(&decomp->varindex);
603  if( decomp->consindex != NULL )
604  SCIPhashmapFree(&decomp->consindex);
605 
606  for( i = 0; i < decomp->nlinkingconss; ++i )
607  {
608  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->linkingconss[i])) );
609  }
610  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipvars, decomp->nblocks);
611  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nsubscipvars, decomp->nblocks);
612  SCIPfreeBlockMemoryArrayNull(scip, &decomp->subscipconss, decomp->nblocks);
613  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nsubscipconss, decomp->nblocks);
614  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingvars, SCIPcalcMemGrowSize(scip, decomp->nlinkingvars));
615  SCIPfreeBlockMemoryArrayNull(scip, &decomp->stairlinkingvars, decomp->nblocks);
616  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nstairlinkingvars,decomp->nblocks);
617  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingconss, SCIPcalcMemGrowSize(scip, decomp->nlinkingconss));
618  if( decomp->detectorchain != NULL )
619  {
620  SCIPfreeBlockMemoryArrayNull(scip, &decomp->detectorchain, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
621  SCIPfreeBlockMemoryArrayNull(scip, &decomp->detectorclocktimes, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
622  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctvarstoborder, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
623  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctconsstoborder, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
624  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctvarstoblock, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
625  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctconsstoblock, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
626  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctvarsfromopen, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
627  SCIPfreeBlockMemoryArrayNull(scip, &decomp->pctconssfromopen, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
628  SCIPfreeBlockMemoryArrayNull(scip, &decomp->nnewblocks, SCIPcalcMemGrowSize(scip,decomp->sizedetectorchain ) );
629  SCIPfreeBlockMemoryArrayNull(scip, &decomp->detectorchainstring, SCIP_MAXSTRLEN );
630  }
631 
632  SCIPfreeMemoryNull(scip, decdecomp);
633 
635 
636  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "ncalls of createdecompfromseeed: %d \n", ncalls);
637 
638  return SCIP_OKAY;
639 }
640 
642 SCIP_RETCODE DECdecompSetType(
643  DEC_DECOMP* decomp,
644  DEC_DECTYPE type
645  )
646 {
647  SCIP_Bool valid;
648 
649  assert(decomp != NULL);
650 
651  switch( type )
652  {
654  valid = decomp->nlinkingconss == 0 && decomp->linkingconss == NULL;
655  valid = valid && decomp->nlinkingvars == 0 && decomp->linkingvars == NULL;
656  break;
658  valid = TRUE;
659  break;
660  case DEC_DECTYPE_UNKNOWN:
661  valid = FALSE;
662  break;
664  valid = decomp->nlinkingvars == 0 && decomp->linkingvars == NULL;
665  break;
667  valid = decomp->nlinkingconss == 0 && decomp->linkingconss == NULL;
668  break;
669  default:
670  valid = FALSE;
671  break;
672  }
673 
674  if( !valid )
675  {
676  SCIPerrorMessage("The decomposition is not of the given type!\n");
677  return SCIP_INVALIDDATA;
678  }
679 
680  decomp->type = type;
681 
682  return SCIP_OKAY;
683 }
684 
687  DEC_DECOMP* decomp
688  )
689 {
690  assert(decomp != NULL);
691 
692  return decomp->type;
693 }
694 
695 
697  DEC_DECOMP* decomp
698  )
699 {
700  assert(decomp != NULL);
701 
702  return decomp->maxwhitescore;
703 }
704 
705 
708  DEC_DECOMP* decomp,
709  SCIP_Bool presolved
710  )
711 {
712  assert(decomp != NULL);
713 
714  decomp->presolved = presolved;
715 }
716 
719  DEC_DECOMP* decomp
720  )
721 {
722  assert(decomp != NULL);
723 
724  return decomp->presolved;
725 }
726 
729  DEC_DECOMP* decomp,
730  int nblocks
731  )
732 {
733  assert(decomp != NULL);
734  assert(nblocks >= 0);
735 
736  decomp->nblocks = nblocks;
737 }
738 
741  DEC_DECOMP* decomp
742  )
743 {
744  assert(decomp != NULL);
745 
746  return decomp->nblocks;
747 }
748 
751  SCIP* scip,
752  DEC_DECOMP* decomp,
753  SCIP_VAR*** subscipvars,
754  int* nsubscipvars
755  )
756 {
757  SCIP_Bool valid;
758  int i;
759  int b;
760  assert(scip != NULL);
761  assert(decomp != NULL);
762  assert(subscipvars != NULL);
763  assert(nsubscipvars != NULL);
764  assert(decomp->nblocks >= 0);
765 
766  assert(decomp->subscipvars == NULL);
767  assert(decomp->nsubscipvars == NULL);
768 
769  if( decomp->nblocks == 0 )
770  return SCIP_OKAY;
771 
772  valid = TRUE;
773 
774  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipvars, decomp->nblocks) );
775  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nsubscipvars, decomp->nblocks) );
776 
777  assert(decomp->subscipvars != NULL);
778  assert(decomp->nsubscipvars != NULL);
779 
780  BMSclearMemoryArray(decomp->subscipvars, decomp->nblocks);
781  BMSclearMemoryArray(decomp->nsubscipvars, decomp->nblocks);
782 
783  for( b = 0; b < decomp->nblocks; ++b )
784  {
785  assert((subscipvars[b] == NULL) == (nsubscipvars[b] == 0));
786  decomp->nsubscipvars[b] = nsubscipvars[b];
787 
788  if( nsubscipvars[b] < 0 )
789  {
790  SCIPerrorMessage("Number of variables per subproblem must be nonnegative.\n");
791  valid = FALSE;
792  }
793  else if( nsubscipvars[b] > 0 )
794  {
795  int size;
796  assert(subscipvars[b] != NULL);
797  size = SCIPcalcMemGrowSize(scip, nsubscipvars[b]);
798  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipvars[b], size) ); /*lint !e866*/
799  BMScopyMemoryArray(decomp->subscipvars[b],subscipvars[b], nsubscipvars[b]); /*lint !e866*/
800 
801  for( i = 0; i < nsubscipvars[b]; ++i )
802  {
803  SCIP_CALL( SCIPcaptureVar(scip, decomp->subscipvars[b][i]) );
804  }
805  }
806  }
807 
808  if( !valid )
809  {
810  return SCIP_INVALIDDATA;
811  }
812 
813 
814  return SCIP_OKAY;
815 }
816 
819  DEC_DECOMP* decomp
820  )
821 {
822  assert(decomp != NULL);
823 
824  return decomp->subscipvars;
825 }
826 
829  DEC_DECOMP* decomp
830  )
831 {
832  assert(decomp != NULL);
833 
834  return decomp->nsubscipvars;
835 }
836 
839  SCIP* scip,
840  DEC_DECOMP* decomp,
841  SCIP_CONS*** subscipconss,
842  int* nsubscipconss
843  )
844 {
845  SCIP_Bool valid;
846  int i;
847  int b;
848  assert(scip != NULL);
849  assert(decomp != NULL);
850  assert(subscipconss != NULL);
851  assert(nsubscipconss != NULL);
852 
853  assert(decomp->nblocks >= 0);
854  assert(decomp->subscipconss == NULL);
855  assert(decomp->nsubscipconss == NULL);
856 
857  valid = TRUE;
858 
859  if( decomp->nblocks == 0)
860  return SCIP_OKAY;
861 
862  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipconss, decomp->nblocks) );
863  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nsubscipconss, decomp->nblocks) );
864 
865  assert(decomp->subscipconss != NULL);
866  assert(decomp->nsubscipconss != NULL);
867 
868  BMSclearMemoryArray(decomp->subscipconss, decomp->nblocks);
869  BMSclearMemoryArray(decomp->nsubscipconss, decomp->nblocks);
870 
871  for( b = 0; b < decomp->nblocks; ++b )
872  {
873  if( nsubscipconss[b] <= 0 || subscipconss[b] == NULL )
874  {
875  SCIPerrorMessage("Block %d is empty and thus invalid. Each block needs at least one constraint.\n", b);
876  valid = FALSE;
877  }
878 
879  decomp->nsubscipconss[b] = nsubscipconss[b];
880 
881  if( nsubscipconss[b] > 0 )
882  {
883  int size;
884 
885  assert(subscipconss[b] != NULL);
886  size = SCIPcalcMemGrowSize(scip, nsubscipconss[b]);
887  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->subscipconss[b], size) ); /*lint !e866*/
888  BMScopyMemoryArray(decomp->subscipconss[b], subscipconss[b], nsubscipconss[b]); /*lint !e866*/
889  for( i = 0; i < nsubscipconss[b]; ++i )
890  {
891  SCIP_CALL( SCIPcaptureCons(scip, decomp->subscipconss[b][i]) );
892  }
893  }
894  }
895 
896  if( !valid )
897  return SCIP_INVALIDDATA;
898 
899  return SCIP_OKAY;
900 }
901 
904  DEC_DECOMP* decomp
905  )
906 {
907  assert(decomp != NULL);
908  return decomp->subscipconss;
909 }
910 
913  DEC_DECOMP* decomp
914  )
915 {
916  assert(decomp != NULL);
917  return decomp->nsubscipconss;
918 }
919 
922  SCIP* scip,
923  DEC_DECOMP* decomp,
924  SCIP_CONS** linkingconss,
925  int nlinkingconss
926  )
927 {
928  assert(scip != NULL);
929  assert(decomp != NULL);
930  assert(linkingconss != NULL);
931  assert(nlinkingconss >= 0);
932 
933  assert(decomp->linkingconss == NULL);
934  assert(decomp->nlinkingconss == 0);
935 
936  decomp->nlinkingconss = nlinkingconss;
937 
938  if( nlinkingconss > 0 )
939  {
940  int i;
941  int size;
942  assert(linkingconss != NULL);
943  size = SCIPcalcMemGrowSize(scip, nlinkingconss);
944  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->linkingconss, size) );
945  BMScopyMemoryArray(decomp->linkingconss, linkingconss, nlinkingconss);
946 
947  for( i = 0; i < nlinkingconss; ++i )
948  {
949  SCIP_CALL( SCIPcaptureCons(scip, decomp->linkingconss[i]) );
950  }
951  }
952 
953  if( (linkingconss == NULL) != (nlinkingconss == 0) )
954  {
955  SCIPerrorMessage("Number of linking constraints and linking constraint array are inconsistent.\n");
956  return SCIP_INVALIDDATA;
957  }
958  return SCIP_OKAY;
959 }
960 
963  DEC_DECOMP* decomp
964  )
965 {
966  assert(decomp != NULL);
967 
968  return decomp->linkingconss;
969 }
970 
973  DEC_DECOMP* decomp
974  )
975 {
976  assert(decomp != NULL);
977  assert(decomp->nlinkingconss >= 0);
978 
979  return decomp->nlinkingconss;
980 }
981 
982 
985  SCIP* scip,
986  DEC_DECOMP* decomp,
987  SCIP_VAR** linkingvars,
988  int nlinkingvars,
989  int nfixedlinkingvars,
990  int nmastervars
992  )
993 {
994  assert(scip != NULL);
995  assert(decomp != NULL);
996  assert(linkingvars != NULL || nlinkingvars == 0);
997 
998  assert(decomp->linkingvars == NULL);
999  assert(decomp->nlinkingvars == 0);
1000 
1001  decomp->nlinkingvars = nlinkingvars;
1002  decomp->nmastervars = nmastervars;
1003  decomp->nfixedlinkingvars = nfixedlinkingvars;
1004 
1005  if( nlinkingvars > 0 )
1006  {
1007  int i;
1008  int size;
1009  assert(linkingvars != NULL);
1010  size = SCIPcalcMemGrowSize(scip, nlinkingvars);
1011  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->linkingvars, size) );
1012  BMScopyMemoryArray(decomp->linkingvars, linkingvars, nlinkingvars);
1013 
1014  for( i = 0; i < nlinkingvars; ++i )
1015  {
1016  SCIP_CALL( SCIPcaptureVar(scip, decomp->linkingvars[i]) );
1017  }
1018  }
1019 
1020  if( (linkingvars == NULL) != (nlinkingvars == 0) )
1021  {
1022  SCIPerrorMessage("Number of linking variables and linking variable array are inconsistent.\n");
1023  return SCIP_INVALIDDATA;
1024  }
1025 
1026  return SCIP_OKAY;
1027 }
1028 
1029 
1030 
1031 
1034  DEC_DECOMP* decomp
1035  )
1036 {
1037  assert(decomp != NULL);
1038 
1039  return decomp->linkingvars;
1040 }
1041 
1044  DEC_DECOMP* decomp
1045  )
1046 {
1047  assert(decomp != NULL);
1048  assert(decomp->nlinkingvars >= 0);
1049 
1050  return decomp->nlinkingvars;
1051 }
1052 
1055  DEC_DECOMP* decomp
1056  )
1057 {
1058  assert(decomp != NULL);
1059  assert(decomp->nfixedlinkingvars >= 0);
1060 
1061  return decomp->nfixedlinkingvars;
1062 }
1063 
1064 
1067  DEC_DECOMP* decomp
1068  )
1069 {
1070  assert(decomp != NULL);
1071  assert(decomp->nmastervars >= 0);
1072 
1073  return decomp->nmastervars;
1074 }
1075 
1076 
1079  SCIP* scip,
1080  DEC_DECOMP* decomp,
1081  SCIP_VAR*** stairlinkingvars,
1082  int* nstairlinkingvars
1083  )
1084 {
1085  SCIP_Bool valid;
1086  int b;
1087  int i;
1088  assert(scip != NULL);
1089  assert(decomp != NULL);
1090  assert(stairlinkingvars != NULL);
1091  assert(nstairlinkingvars != NULL);
1092 
1093  assert(decomp->nblocks >= 0);
1094 
1095  assert(decomp->stairlinkingvars == NULL);
1096  assert(decomp->nstairlinkingvars == NULL);
1097 
1098  valid = TRUE;
1100  if( decomp->nblocks == 0 )
1101  return SCIP_OKAY;
1102 
1103  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->stairlinkingvars, decomp->nblocks) ); /* this is more efficient */
1104  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decomp->nstairlinkingvars, decomp->nblocks) ); /* this is more efficient */
1105 
1106  assert(decomp->stairlinkingvars != NULL);
1107  assert(decomp->nstairlinkingvars != NULL);
1108 
1109  BMSclearMemoryArray(decomp->stairlinkingvars, decomp->nblocks);
1110  BMSclearMemoryArray(decomp->nstairlinkingvars, decomp->nblocks);
1111 
1112  for( b = 0; b < decomp->nblocks-1; ++b )
1113  {
1114  assert(nstairlinkingvars[b] > 0 || stairlinkingvars[b] == NULL);
1115  decomp->nstairlinkingvars[b] = nstairlinkingvars[b];
1116  if( stairlinkingvars[b] != NULL )
1117  {
1118  int size = SCIPcalcMemGrowSize(scip, nstairlinkingvars[b]);
1119  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(decomp->stairlinkingvars[b]), size) ); /*lint !e866 */
1120  BMScopyMemoryArray(decomp->stairlinkingvars[b], stairlinkingvars[b], nstairlinkingvars[b]); /*lint !e866 */
1121  }
1122  else
1123  {
1124  decomp->stairlinkingvars[b] = NULL;
1125  }
1126  }
1127 
1128  decomp->nstairlinkingvars[decomp->nblocks - 1] = 0;
1129  decomp->stairlinkingvars[decomp->nblocks -1] = NULL;
1130 
1131  for( b = 0; b < decomp->nblocks-1; ++b )
1132  {
1133  for( i = 0; i < nstairlinkingvars[b]; ++i )
1134  {
1135  assert(stairlinkingvars[b] != NULL);
1136  SCIP_CALL( SCIPcaptureVar(scip, decomp->stairlinkingvars[b][i]) );
1137  }
1138  }
1139  if( !valid ) /*lint !e774 it is always true, see above */
1140  {
1141  SCIPerrorMessage("The staircase linking variables are inconsistent.\n");
1142  return SCIP_INVALIDDATA;
1143  }
1144  return SCIP_OKAY;
1145 }
1146 
1149  DEC_DECOMP* decomp
1150  )
1151 {
1152  assert(decomp != NULL);
1153  return decomp->stairlinkingvars;
1154 }
1155 
1158  DEC_DECOMP* decomp
1159  )
1160 {
1161  assert(decomp != NULL);
1162  assert(decomp->nstairlinkingvars != NULL );
1163  return decomp->nstairlinkingvars;
1164 }
1165 
1168  DEC_DECOMP* decomp
1169  )
1170 {
1171  int sum;
1172  int b;
1173 
1174  sum = 0;
1175 
1176  for ( b = 0; b < DECdecompGetNBlocks(decomp); ++b)
1177  sum += DECdecompGetNStairlinkingvars(decomp)[b];
1178 
1179  return sum;
1180 }
1181 
1182 
1185  DEC_DECOMP* decomp,
1186  SCIP_HASHMAP* vartoblock
1187  )
1188 {
1189  assert(decomp != NULL);
1190  assert(vartoblock != NULL);
1191 
1192  decomp->vartoblock = vartoblock;
1193 }
1194 
1197  DEC_DECOMP* decomp
1198  )
1199 {
1200  assert(decomp != NULL);
1201 
1202  return decomp->vartoblock;
1203 }
1204 
1207  DEC_DECOMP* decomp,
1208  SCIP_HASHMAP* constoblock
1209  )
1210 {
1211  assert(decomp != NULL);
1212  assert(constoblock != NULL);
1213 
1214  decomp->constoblock = constoblock;
1215 }
1216 
1219  DEC_DECOMP* decomp
1220  )
1221 {
1222  assert(decomp != NULL);
1223 
1224  return decomp->constoblock;
1225 }
1226 
1229  DEC_DECOMP* decomp,
1230  SCIP_HASHMAP* varindex
1231  )
1232 {
1233  assert(decomp != NULL);
1234  assert(varindex != NULL);
1235  decomp->varindex = varindex;
1236 }
1237 
1239 SCIP_HASHMAP* DECdecompGetVarindex(
1240  DEC_DECOMP* decomp
1241  )
1242 {
1243  assert(decomp != NULL);
1244  return decomp->varindex;
1245 }
1246 
1249  DEC_DECOMP* decomp,
1250  SCIP_HASHMAP* consindex
1251  )
1252 {
1253  assert(decomp != NULL);
1254  assert(consindex != NULL);
1255  decomp->consindex = consindex;
1256 }
1257 
1260  DEC_DECOMP* decomp
1261  )
1262 {
1263  assert(decomp != NULL);
1264  return decomp->consindex;
1265 }
1266 
1269  SCIP* scip,
1270  DEC_DECOMP* decomp,
1271  SCIP_HASHMAP* vartoblock,
1272  SCIP_HASHMAP* constoblock,
1273  int nblocks,
1274  SCIP_Bool staircase
1275  )
1276 {
1277  SCIP_HASHMAP* varindex;
1278  SCIP_HASHMAP* consindex;
1279  int* nsubscipconss;
1280  int* nsubscipvars;
1281  int* nstairlinkingvars;
1282  SCIP_VAR*** stairlinkingvars;
1283  SCIP_CONS*** subscipconss;
1284  SCIP_Bool success;
1285  int cindex;
1286  int cumindex;
1287  SCIP_Bool haslinking;
1288  int i;
1289  int b;
1290  SCIP_VAR** curvars;
1291  int ncurvars;
1292  int j;
1293 
1294  SCIP_VAR** vars;
1295  int nvars;
1296  SCIP_CONS** conss;
1297  int nconss;
1298 
1299  assert(scip != NULL);
1300  assert(decomp != NULL);
1301  assert(vartoblock != NULL);
1302  assert(constoblock != NULL);
1303  assert(nblocks >= 0);
1304 
1305  conss = SCIPgetConss(scip);
1306  nconss = SCIPgetNConss(scip);
1307  vars = SCIPgetVars(scip);
1308  nvars = SCIPgetNVars(scip);
1309 
1310  assert(vars != NULL);
1311  assert(nvars > 0);
1312  assert(conss != NULL);
1313  assert(nconss > 0);
1314 
1315  DECdecompSetNBlocks(decomp, nblocks);
1316 
1317  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_DIAGONAL) );
1318  SCIP_CALL_QUIET( fillOutConsFromConstoblock(scip, decomp, constoblock, nblocks, conss, nconss, &haslinking) );
1319 
1320  if( haslinking )
1321  {
1322  SCIPdebugMessage("Decomposition has linking constraints and is bordered.\n");
1323  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_BORDERED) );
1324  }
1325 
1326  SCIP_CALL( fillOutVarsFromVartoblock(scip, decomp, vartoblock, nblocks, vars, nvars, &haslinking) );
1327 
1328  if( haslinking )
1329  {
1330  SCIPdebugMessage("Decomposition has linking variables and is arrowhead.\n");
1331  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_ARROWHEAD) );
1332  }
1333 
1334  if( !staircase )
1335  {
1336  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
1337  return SCIP_OKAY;
1338  }
1339 
1340  SCIP_CALL( SCIPhashmapCreate(&varindex, SCIPblkmem(scip), nvars) );
1341  SCIP_CALL( SCIPhashmapCreate(&consindex, SCIPblkmem(scip), nconss) );
1342  SCIP_CALL( SCIPallocBufferArray(scip, &stairlinkingvars, nblocks) );
1343  SCIP_CALL( SCIPallocBufferArray(scip, &nstairlinkingvars, nblocks) );
1344 
1345  for( i = 0; i < nblocks; ++i )
1346  {
1347  SCIP_CALL( SCIPallocBufferArray(scip, &(stairlinkingvars[i]), nvars) ); /*lint !e866*/
1348  nstairlinkingvars[i] = 0;
1349  }
1350 
1351  nsubscipconss = DECdecompGetNSubscipconss(decomp);
1352  subscipconss = DECdecompGetSubscipconss(decomp);
1353  nsubscipvars = DECdecompGetNSubscipvars(decomp);
1354 
1355  cindex = 0;
1356  cumindex = 0;
1357 
1358  /* try to deduce staircase map */
1359  for( b = 0; b < nblocks; ++b )
1360  {
1361  int idx = 0;
1362  SCIPdebugMessage("block %d (%d vars):\n", b, nsubscipvars[b]);
1363 
1364  for( i = 0; i < nsubscipconss[b]; ++i )
1365  {
1366 
1367  int linkindex = 0;
1368  SCIP_CONS* cons = subscipconss[b][i];
1369 
1370  SCIP_CALL( SCIPhashmapInsert(consindex, cons, (void*)(size_t) (cindex+1)) );
1371  ++cindex;
1372  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
1373  assert(success);
1374 
1375  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1376 
1377  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
1378  assert(success);
1379 
1380  for( j = 0; j < ncurvars; ++j )
1381  {
1382  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[j]);
1383 
1384  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1385  continue;
1386 
1387  /* if the variable is linking */
1388  if( (int)(size_t)SCIPhashmapGetImage(vartoblock, probvar) >= nblocks+1 ) /*lint !e507*/
1389  {
1390  /* if it has not been already assigned, it links to the next block */
1391  if( !SCIPhashmapExists(varindex, probvar) )
1392  {
1393  int vindex = cumindex+nsubscipvars[b]+linkindex+1;
1394  SCIPdebugMessage("assigning link var <%s> to index <%d>\n", SCIPvarGetName(probvar), vindex);
1395  SCIP_CALL( SCIPhashmapInsert(varindex, probvar, (void*)(size_t)(vindex)) );
1396  stairlinkingvars[b][nstairlinkingvars[b]] = probvar;
1397  ++(nstairlinkingvars[b]);
1398  linkindex++;
1399  }
1400  }
1401  else
1402  {
1403  if( !SCIPhashmapExists(varindex, probvar) )
1404  {
1405  int vindex = cumindex+idx+1;
1406  assert(((int) (size_t) SCIPhashmapGetImage(vartoblock, probvar)) -1 == b); /*lint !e507*/
1407  SCIPdebugMessage("assigning block var <%s> to index <%d>\n", SCIPvarGetName(probvar), vindex);
1408  SCIP_CALL( SCIPhashmapInsert(varindex, probvar, (void*)(size_t)(vindex)) );
1409  ++idx;
1410  }
1411  }
1412  }
1413  SCIPfreeBufferArray(scip, &curvars);
1414  }
1415  if( b < nblocks-1 )
1416  {
1417  cumindex += nsubscipvars[b] + nstairlinkingvars[b];
1418  }
1419  }
1420 
1421  DECdecompSetVarindex(decomp, varindex);
1422  DECdecompSetConsindex(decomp, consindex);
1423  SCIP_CALL( DECdecompSetType(decomp, DEC_DECTYPE_STAIRCASE) );
1424 
1425  for( b = nblocks-1; b >= 0; --b )
1426  {
1427  if( nstairlinkingvars[b] == 0 )
1428  {
1429  SCIPfreeBufferArrayNull(scip, &(stairlinkingvars[b]));
1430  }
1431  }
1432 
1433  SCIP_CALL( DECdecompSetStairlinkingvars(scip, decomp, stairlinkingvars, nstairlinkingvars) );
1434 
1435  for( b = nblocks-1; b >= 0; --b )
1436  {
1437  SCIPfreeBufferArrayNull(scip, &stairlinkingvars[b]);
1438  }
1439  SCIPfreeBufferArray(scip, &nstairlinkingvars);
1440  SCIPfreeBufferArray(scip, &stairlinkingvars);
1441 
1442  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
1443 
1444  return SCIP_OKAY;
1445 }
1446 
1455  SCIP* scip,
1456  DEC_DECOMP* decomp,
1457  SCIP_HASHMAP* constoblock,
1458  int nblocks,
1459  SCIP_Bool staircase
1460  )
1461 {
1462  SCIP_HASHMAP* vartoblock;
1463  int i;
1464  int j;
1465  SCIP_VAR** vars;
1466  int nvars;
1467  SCIP_CONS** conss;
1468  int nconss;
1469  SCIP_VAR** curvars;
1470  int ncurvars;
1471  SCIP_Bool haslinking;
1472  SCIP_Bool success;
1473  SCIP_RETCODE retcode;
1474 
1475  assert(scip != NULL);
1476  assert(decomp != NULL);
1477  assert(constoblock != NULL);
1478  assert(nblocks >= 0);
1479 
1480  conss = SCIPgetConss(scip);
1481  nconss = SCIPgetNConss(scip);
1482  vars = SCIPgetVars(scip);
1483  nvars = SCIPgetNVars(scip);
1484 
1485  assert(vars != NULL);
1486  assert(nvars > 0);
1487  assert(conss != NULL);
1488  assert(nconss > 0);
1489 
1490  SCIP_CALL( SCIPhashmapCreate(&vartoblock, SCIPblkmem(scip), nvars) );
1491  haslinking = FALSE;
1492  for( i = 0; i < nconss; ++i )
1493  {
1494  int consblock;
1495 
1496  SCIP_CALL( SCIPgetConsNVars(scip, conss[i], &ncurvars, &success) );
1497  assert(success);
1498 
1499  if( ncurvars == 0 )
1500  continue;
1501 
1502  consblock = (int)(size_t)SCIPhashmapGetImage(constoblock, conss[i]); /*lint !e507*/
1503 
1504  assert(consblock > 0 && consblock <= nblocks+1);
1505  if( consblock == nblocks+1 )
1506  {
1507  SCIPdebugMessage("cons <%s> is linking and need not be handled\n", SCIPconsGetName(conss[i]));
1508  continue;
1509  }
1510 
1511  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
1512 
1513  SCIP_CALL( SCIPgetConsVars(scip, conss[i], curvars, ncurvars, &success) );
1514  assert(success);
1515  SCIPdebugMessage("cons <%s> (%d vars) is in block %d.\n", SCIPconsGetName(conss[i]), ncurvars, consblock);
1516  assert(consblock <= nblocks);
1517 
1518  for( j = 0; j < ncurvars; ++j )
1519  {
1520  int varblock;
1521  SCIP_VAR* probvar = SCIPvarGetProbvar(curvars[j]);
1522 
1523  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
1524  continue;
1525 
1526  assert(SCIPvarIsActive(probvar));
1527 
1528  if( SCIPhashmapExists(vartoblock, probvar) )
1529  varblock = (int) (size_t) SCIPhashmapGetImage(vartoblock, probvar); /*lint !e507*/
1530  else
1531  varblock = nblocks+1;
1532 
1533  /* The variable is currently in no block */
1534  if( varblock == nblocks+1 )
1535  {
1536  SCIPdebugMessage(" var <%s> not been handled before, adding to block %d\n", SCIPvarGetName(probvar), consblock);
1537  SCIP_CALL( SCIPhashmapSetImage(vartoblock, probvar, (void*) (size_t) consblock) );
1538  }
1539  /* The variable is already in a different block */
1540  else if( varblock != consblock )
1541  {
1542  assert(varblock <= nblocks || varblock == nblocks+2);
1543  SCIPdebugMessage(" var <%s> has been handled before, adding to linking (%d != %d)\n", SCIPvarGetName(probvar), consblock, varblock);
1544  SCIP_CALL( SCIPhashmapSetImage(vartoblock, probvar, (void*) (size_t) (nblocks+2)) );
1545  haslinking = TRUE;
1546  }
1547  else
1548  {
1549  assert(consblock == varblock);
1550  SCIPdebugMessage(" var <%s> is handled and in same block as cons (%d == %d).\n", SCIPvarGetName(probvar), consblock, varblock);
1551  }
1552  }
1553 
1554  SCIPfreeBufferArray(scip, &curvars);
1555  }
1556 
1557  /* Handle variables that do not appear in any pricing problem, those will be copied directly to the master */
1558  for( i = 0; i < nvars; ++i )
1559  {
1560  if( !SCIPhashmapExists(vartoblock, vars[i]) )
1561  {
1562  SCIPdebugMessage(" var <%s> not handled at all and now in master\n", SCIPvarGetName(vars[i]));
1563  SCIP_CALL( SCIPhashmapSetImage(vartoblock, vars[i], (void*) (size_t) (nblocks+1)) );
1564  }
1565  }
1566 
1567  retcode = DECfilloutDecompFromHashmaps(scip, decomp, vartoblock, constoblock, nblocks, staircase && haslinking);
1568  if( retcode != SCIP_OKAY )
1569  {
1570  SCIPhashmapFree(&vartoblock);
1571  return retcode;
1572  }
1573 
1574  return SCIP_OKAY;
1575 }
1576 
1579  DEC_DECOMP* decomp,
1580  DEC_DETECTOR* detector
1581  )
1582 {
1583  assert(decomp != NULL);
1584 
1585  decomp->detector = detector;
1586 }
1587 
1590  DEC_DECOMP* decomp
1591  )
1592 {
1593  assert(decomp != NULL);
1594 
1595  return decomp->detector;
1596 }
1597 
1600  DEC_DECOMP* decomp
1601  )
1602 {
1603  assert(decomp != NULL);
1604 
1605  return decomp->detectorchain;
1606 }
1607 
1610  DEC_DECOMP* decomp
1611  )
1612 {
1613  assert(decomp != NULL);
1614 
1615  return decomp->sizedetectorchain;
1616 }
1617 
1620  DEC_DECOMP* decomp,
1621  int seeedID
1622  )
1623 {
1624 
1625  assert(decomp != NULL);
1626  assert(seeedID >= 0);
1627 
1628  decomp->seeedid = seeedID;
1629 
1630 }
1631 
1634  DEC_DECOMP* decomp
1635  )
1636 {
1637  assert(decomp != NULL);
1638  return decomp->seeedid;
1639 }
1640 
1641 
1643 extern
1645  SCIP* scip,
1646  DEC_DECOMP* decomp,
1647  SCIP_Real* detectorClockTimes
1648  )
1649 {
1650  int d;
1651 
1652  int size;
1653  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1654 
1655  assert(decomp->sizedetectorchain > 0);
1656  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->detectorclocktimes, size) );
1657 
1658  BMSclearMemoryArray(decomp->detectorclocktimes, size);
1659 
1660  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1661  {
1662  decomp->detectorclocktimes[d] = detectorClockTimes[d];
1663  }
1664 
1665  return;
1666 
1667 }
1668 
1671  DEC_DECOMP* decomp
1672  )
1673 {
1674  return decomp->detectorclocktimes;
1675 }
1676 
1678 extern
1680  SCIP* scip,
1681  DEC_DECOMP* decomp,
1682  char* detectorchainstring
1683  )
1684 {
1685 
1686  SCIP_CALL (SCIPduplicateBlockMemoryArray(scip, &(decomp->detectorchainstring), detectorchainstring, SCIP_MAXSTRLEN ) );
1687  return SCIP_OKAY;
1688 
1689 }
1690 
1692 extern
1694  SCIP* scip,
1695  DEC_DECOMP* decomp
1696  )
1697 {
1698  return decomp->detectorchainstring;
1699 }
1700 
1701 
1704  SCIP* scip,
1705  DEC_DECOMP* decomp,
1706  SCIP_Real* pctVarsToBorder
1707  )
1708 {
1709  int d;
1710  int size;
1711  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1712 
1713  assert(decomp->sizedetectorchain > 0);
1714 
1715  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctvarstoborder, size) );
1716 
1717  BMSclearMemoryArray(decomp->pctvarstoborder, size);
1718 
1719  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1720  {
1721  decomp->pctvarstoborder[d] = pctVarsToBorder[d];
1722  }
1723 
1724  return;
1725 
1726 
1727 }
1728 
1730 extern
1732  DEC_DECOMP* decomp
1733  )
1734 {
1735  return decomp->pctvarstoborder;
1736 }
1737 
1740  SCIP* scip,
1741  DEC_DECOMP* decomp,
1742  SCIP_Real* pctConssToBorder
1743  )
1744 {
1745 
1746  int d;
1747  int size;
1748  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1749 
1750 
1751  assert(decomp->sizedetectorchain > 0);
1752 
1753  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctconsstoborder, size) );
1754 
1755  BMSclearMemoryArray(decomp->pctconsstoborder, size);
1756 
1757  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1758  {
1759  decomp->pctconsstoborder[d] = pctConssToBorder[d];
1760  }
1761 
1762  return;
1763 }
1764 
1767  DEC_DECOMP* decomp
1768  )
1769 {
1770  return decomp->pctconsstoborder;
1771 }
1772 
1775  SCIP* scip,
1776  DEC_DECOMP* decomp,
1777  SCIP_Real* pctVarsToBlock
1778  )
1779 {
1780  int d;
1781  int size;
1782 
1783  assert(decomp->sizedetectorchain > 0);
1784 
1785  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1786 
1787 
1788  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctvarstoblock, size) );
1789 
1790  BMSclearMemoryArray(decomp->pctvarstoblock, size);
1791 
1792  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1793  {
1794  decomp->pctvarstoblock[d] = pctVarsToBlock[d];
1795  }
1796 
1797  return;
1798  }
1799 
1802  DEC_DECOMP* decomp
1803  )
1804 {
1805  return decomp->pctvarstoblock;
1806 }
1807 
1810  SCIP* scip,
1811  DEC_DECOMP* decomp,
1812  SCIP_Real* pctConssToBlock
1813  )
1814 {
1815  int d;
1816 
1817  int size;
1818 
1819  assert(decomp->sizedetectorchain > 0);
1820 
1821  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1822 
1823  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctconsstoblock, size) );
1824 
1825  BMSclearMemoryArray(decomp->pctconsstoblock, size);
1826 
1827  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1828  {
1829  decomp->pctconsstoblock[d] = pctConssToBlock[d];
1830  }
1831 
1832  return;
1833 }
1834 
1836 extern
1838  DEC_DECOMP* decomp
1839  )
1840 {
1841  return decomp->pctconsstoblock;
1842 }
1843 
1844 
1847  SCIP* scip,
1848  DEC_DECOMP* decomp,
1849  SCIP_Real* pctVarsFromOpen
1850  )
1851 {
1852  int d;
1853  int size;
1854 
1855  assert(decomp->sizedetectorchain > 0);
1856 
1857 
1858  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1859 
1860 
1861  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctvarsfromopen, size) );
1862 
1863  BMSclearMemoryArray(decomp->pctvarsfromopen, size);
1864 
1865  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1866  {
1867  decomp->pctvarsfromopen[d] = pctVarsFromOpen[d];
1868  }
1869 
1870  return;
1871 }
1872 
1875  DEC_DECOMP* decomp
1876  )
1877 {
1878  return decomp->pctvarsfromopen;
1879 }
1880 
1883  SCIP* scip,
1884  DEC_DECOMP* decomp,
1885  SCIP_Real* pctConssFromOpen
1886  )
1887 {
1888  int d;
1889  int size;
1890 
1891  assert(decomp->sizedetectorchain > 0);
1892 
1893 
1894  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1895 
1896 
1897  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->pctconssfromopen, size) );
1898 
1899  BMSclearMemoryArray(decomp->pctconssfromopen, size);
1900 
1901  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1902  {
1903  decomp->pctconssfromopen[d] = pctConssFromOpen[d];
1904  }
1905 
1906  return;
1907 }
1908 
1912  DEC_DECOMP* decomp
1913  )
1914 {
1915  return decomp->pctconssfromopen;
1916 }
1917 
1920  SCIP* scip,
1921  DEC_DECOMP* decomp,
1922  int* nNewBlocks
1923  )
1924 {
1925  int d;
1926  int size;
1927 
1928  assert(decomp->sizedetectorchain > 0);
1929 
1930  size = SCIPcalcMemGrowSize(scip, decomp->sizedetectorchain);
1931 
1932  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip, &decomp->nnewblocks, size) );
1933 
1934  BMSclearMemoryArray(decomp->nnewblocks, size);
1935 
1936  for ( d = 0; d < decomp->sizedetectorchain; ++d )
1937  {
1938  decomp->nnewblocks[d] = nNewBlocks[d];
1939  }
1940 
1941  return;
1942 }
1943 
1946  DEC_DECOMP* decomp
1947  )
1948 {
1949  return decomp->nnewblocks;
1950 }
1951 
1952 
1953 
1954 
1955 
1957 SCIP_RETCODE DECdecompTransform(
1958  SCIP* scip,
1959  DEC_DECOMP* decomp
1960  )
1961 {
1962  int b;
1963  int c;
1964  int v;
1965  SCIP_HASHMAP* newconstoblock;
1966  SCIP_HASHMAP* newvartoblock;
1967  SCIP_VAR* newvar;
1968 
1969  assert(SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED);
1970 
1971  SCIP_CALL( SCIPhashmapCreate(&newconstoblock, SCIPblkmem(scip), SCIPgetNConss(scip)) );
1972  SCIP_CALL( SCIPhashmapCreate(&newvartoblock, SCIPblkmem(scip), SCIPgetNVars(scip)) );
1973 
1974  /* transform all constraints and put them into constoblock */
1975  for( b = 0; b < decomp->nblocks; ++b )
1976  {
1977  for( c = 0; c < decomp->nsubscipconss[b]; ++c )
1978  {
1979  SCIP_CONS* newcons;
1980  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, c, SCIPconsGetName(decomp->subscipconss[b][c]),
1981  (void*) decomp->subscipconss[b][c], SCIPconsIsTransformed(decomp->subscipconss[b][c])?"t":"o" );
1982  assert(decomp->subscipconss[b][c] != NULL);
1983  newcons = SCIPfindCons(scip, SCIPconsGetName(decomp->subscipconss[b][c]));
1984  if( newcons != decomp->subscipconss[b][c] )
1985  {
1986  SCIP_CALL( SCIPcaptureCons(scip, newcons) );
1987  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->subscipconss[b][c])) );
1988  decomp->subscipconss[b][c] = newcons;
1989  }
1990  assert(decomp->subscipconss[b][c] != NULL);
1991  assert(!SCIPhashmapExists(newconstoblock, decomp->subscipconss[b][c]));
1992  SCIP_CALL( SCIPhashmapSetImage(newconstoblock, decomp->subscipconss[b][c], (void*) (size_t) (b+1)) );
1993  }
1994  }
1995  /* transform all variables and put them into vartoblock */
1996  for( b = 0; b < decomp->nblocks; ++b )
1997  {
1998  int idx;
1999  for( v = 0, idx = 0; v < decomp->nsubscipvars[b]; ++v )
2000  {
2001  assert(decomp->subscipvars[b][v] != NULL);
2002 
2003  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, v, SCIPvarGetName(decomp->subscipvars[b][v]),
2004  (void*)decomp->subscipvars[b][v], SCIPvarIsTransformed(decomp->subscipvars[b][v])?"t":"o" );
2005 
2006  /* make sure that newvar is a transformed variable */
2007  SCIP_CALL( SCIPgetTransformedVar(scip, decomp->subscipvars[b][v], &newvar) );
2008  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->subscipvars[b][v])) );
2009 
2010  assert(newvar != NULL);
2011  assert(SCIPvarIsTransformed(newvar));
2012 
2013  newvar = SCIPvarGetProbvar(newvar);
2014  assert(newvar != NULL);
2015 
2016  /* the probvar can also be fixed, in which case we do not need it in the block; furthermore, multiple variables
2017  * can resolve to the same active problem variable, so we check whether we already handled the variable
2018  * @todo: why do we ignore fixed variables? They could still be present in constraints?
2019  */
2020  if( SCIPvarIsActive(newvar) && !SCIPhashmapExists(newvartoblock, newvar) )
2021  {
2022  decomp->subscipvars[b][idx] = newvar;
2023  SCIP_CALL( SCIPcaptureVar(scip, newvar) );
2024  SCIPdebugMessage("%d, %d: %s (%p, %s)\n", b, v, SCIPvarGetName(decomp->subscipvars[b][idx]),
2025  (void*)decomp->subscipvars[b][idx], SCIPvarIsTransformed(decomp->subscipvars[b][idx])?"t":"o" );
2026 
2027  assert(decomp->subscipvars[b][idx] != NULL);
2028  assert(!SCIPhashmapExists(newvartoblock, decomp->subscipvars[b][idx]));
2029  SCIP_CALL( SCIPhashmapSetImage(newvartoblock, decomp->subscipvars[b][idx], (void*) (size_t) (b+1)) );
2030  ++idx;
2031  }
2032  }
2033  decomp->nsubscipvars[b] = idx;
2034  }
2035 
2036  /* transform all linking constraints */
2037  for( c = 0; c < decomp->nlinkingconss; ++c )
2038  {
2039  SCIP_CONS* newcons;
2040 
2041  SCIPdebugMessage("m, %d: %s (%s)\n", c, SCIPconsGetName(decomp->linkingconss[c]), SCIPconsIsTransformed(decomp->linkingconss[c])?"t":"o" );
2042  assert(decomp->linkingconss[c] != NULL);
2043  newcons = SCIPfindCons(scip, SCIPconsGetName(decomp->linkingconss[c]));
2044  if( newcons != decomp->linkingconss[c] )
2045  {
2046  SCIP_CALL( SCIPcaptureCons(scip, newcons) );
2047  SCIP_CALL( SCIPreleaseCons(scip, &(decomp->linkingconss[c])) );
2048  decomp->linkingconss[c] = newcons;
2049  }
2050  SCIP_CALL( SCIPhashmapSetImage(newconstoblock, decomp->linkingconss[c],(void*) (size_t) (decomp->nblocks+1) ) );
2051 
2052  assert(decomp->linkingconss[c] != NULL);
2053  }
2054 
2055  /* transform all linking variables */
2056  for( v = 0; v < decomp->nlinkingvars; ++v )
2057  {
2058  int block;
2059  SCIPdebugMessage("m, %d: %s (%p, %s)\n", v, SCIPvarGetName(decomp->linkingvars[v]),
2060  (void*)decomp->linkingvars[v], SCIPvarIsTransformed(decomp->linkingvars[v])?"t":"o");
2061  assert(decomp->linkingvars[v] != NULL);
2062 
2063  if( !SCIPvarIsTransformed(decomp->linkingvars[v]) )
2064  {
2065  SCIP_CALL( SCIPgetTransformedVar(scip, decomp->linkingvars[v], &newvar) );
2066  newvar = SCIPvarGetProbvar(newvar);
2067  }
2068  else
2069  newvar = decomp->linkingvars[v];
2070 
2071  block = (int) (size_t) SCIPhashmapGetImage(decomp->vartoblock, decomp->linkingvars[v]); /*lint !e507*/
2072  assert(block == decomp->nblocks +1 || block == decomp->nblocks +2);
2073  assert(newvar != NULL);
2074  assert(SCIPvarIsTransformed(newvar));
2075  SCIP_CALL( SCIPreleaseVar(scip, &(decomp->linkingvars[v])) );
2076 
2077  decomp->linkingvars[v] = newvar;
2078  SCIP_CALL( SCIPcaptureVar(scip, decomp->linkingvars[v]) );
2079  SCIP_CALL( SCIPhashmapSetImage(newvartoblock, decomp->linkingvars[v], (void*) (size_t) (block) ) );
2080  SCIPdebugMessage("m, %d: %s (%p, %s)\n", v, SCIPvarGetName(decomp->linkingvars[v]),
2081  (void*)decomp->linkingvars[v], SCIPvarIsTransformed(decomp->linkingvars[v])?"t":"o");
2082  assert(decomp->linkingvars[v] != NULL);
2083  }
2084 
2085  SCIPhashmapFree(&decomp->constoblock);
2086  decomp->constoblock = newconstoblock;
2087  SCIPhashmapFree(&decomp->vartoblock);
2088  decomp->vartoblock = newvartoblock;
2089 
2090  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
2091 
2092  return SCIP_OKAY;
2093 }
2094 
2099  SCIP* scip,
2100  DEC_DECOMP* decdecomp
2101  )
2102 {
2103  int block;
2104 
2105  int c;
2106  int pos;
2107 
2108  assert(scip != NULL);
2109  assert(decdecomp != NULL);
2110 
2111  for( block = 0; block < decdecomp->nblocks; ++block )
2112  {
2113  for( c = 0, pos = 0; c < decdecomp->nsubscipconss[block]; ++c )
2114  {
2115  if( !SCIPconsIsDeleted(decdecomp->subscipconss[block][c]) )
2116  {
2117  decdecomp->subscipconss[block][pos] = decdecomp->subscipconss[block][c];
2118  ++pos;
2119  }
2120  else
2121  {
2122  SCIP_CALL( SCIPreleaseCons(scip, &decdecomp->subscipconss[block][c]) );
2123  }
2124  }
2125  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->subscipconss[block],
2126  SCIPcalcMemGrowSize(scip, decdecomp->nsubscipconss[block]), SCIPcalcMemGrowSize(scip, pos)) );
2127  decdecomp->nsubscipconss[block] = pos;
2128  }
2129 
2130  for( c = 0, pos = 0; c < decdecomp->nlinkingconss; ++c )
2131  {
2132  if( !SCIPconsIsDeleted(decdecomp->linkingconss[c]) )
2133  {
2134  decdecomp->linkingconss[pos] = decdecomp->linkingconss[c];
2135  ++pos;
2136  }
2137  else
2138  {
2139  SCIP_CALL( SCIPreleaseCons(scip, &decdecomp->linkingconss[c]) );
2140  }
2141  }
2142 
2143  if( pos != decdecomp->nlinkingconss && decdecomp->linkingconss != NULL )
2144  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->linkingconss,
2145  SCIPcalcMemGrowSize(scip, decdecomp->nlinkingconss), SCIPcalcMemGrowSize(scip, pos)) );
2146  decdecomp->nlinkingconss = pos;
2147 
2148  return SCIP_OKAY;
2149 }
2150 
2155  SCIP* scip,
2156  DEC_DECOMP* decdecomp
2157  )
2158 {
2159  int c;
2160 
2161  assert(scip != NULL);
2162  assert(decdecomp != NULL);
2163 
2164  for( c = 0; c < SCIPgetNConss(scip); ++c )
2165  {
2166  SCIP_CONS* cons;
2167  cons = SCIPgetConss(scip)[c];
2168 
2169 
2170  if( !GCGisConsGCGCons(cons) && !SCIPhashmapExists(DECdecompGetConstoblock(decdecomp), cons) )
2171  {
2172  int block;
2173  SCIP_CALL( DECdetermineConsBlock(scip, decdecomp, cons, &block) );
2174  SCIPdebugMessage("add remaining: cons <%s> in block %d/%d\n", SCIPconsGetName(cons), block, DECdecompGetNBlocks(decdecomp) );
2175 
2176  /* If the constraint has only variables appearing in the master only,
2177  * we assign it to the master rather than creating a new block
2178  */
2179  if( block == -1 || (block >= 0 && block == DECdecompGetNBlocks(decdecomp) ) )
2180  {
2181  if( decdecomp->nlinkingconss == 0 )
2182  {
2183  int newsize;
2184  newsize = SCIPcalcMemGrowSize(scip, 1);
2185  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decdecomp->linkingconss, newsize) );
2186 
2187  switch( decdecomp->type )
2188  {
2189  case DEC_DECTYPE_DIAGONAL:
2190  decdecomp->type = DEC_DECTYPE_BORDERED;
2191  SCIPwarningMessage(scip, "Decomposition type changed to 'bordered' due to an added constraint.\n");
2192  break;
2193  case DEC_DECTYPE_STAIRCASE:
2194  decdecomp->type = DEC_DECTYPE_ARROWHEAD;
2195  SCIPwarningMessage(scip, "Decomposition type changed to 'arrowhead' due to an added constraint.\n");
2196  break;
2197  default:
2198  break;
2199  }
2200  }
2201  else
2202  {
2203  int oldsize;
2204  int newsize;
2205  oldsize = SCIPcalcMemGrowSize(scip, decdecomp->nlinkingconss);
2206  newsize = SCIPcalcMemGrowSize(scip, decdecomp->nlinkingconss+1);
2207  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->linkingconss, oldsize, newsize) );
2208  }
2209  decdecomp->linkingconss[decdecomp->nlinkingconss] = cons;
2210  decdecomp->nlinkingconss += 1;
2211  SCIP_CALL( SCIPhashmapInsert(decdecomp->constoblock, cons, (void*) (size_t) (DECdecompGetNBlocks(decdecomp)+1)) );
2212  }
2213  else
2214  {
2215  int oldsize;
2216  int newsize;
2217  assert(block>=0);
2218 
2219  oldsize = SCIPcalcMemGrowSize(scip, decdecomp->nsubscipconss[block]);
2220  newsize = SCIPcalcMemGrowSize(scip, decdecomp->nsubscipconss[block]+1);
2221 
2222  assert(decdecomp->nsubscipconss[block] > 0);
2223  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decdecomp->subscipconss[block], oldsize, newsize) ); /*lint !e866*/
2224  decdecomp->subscipconss[block][decdecomp->nsubscipconss[block]] = cons;
2225  decdecomp->nsubscipconss[block] += 1;
2226  SCIP_CALL( SCIPhashmapInsert(decdecomp->constoblock, cons, (void*) (size_t) (block+1)) );
2227  SCIP_CALL( assignConsvarsToBlock(scip, decdecomp, cons, block) );
2228  }
2229  SCIP_CALL( SCIPcaptureCons(scip, cons) );
2230  }
2231  }
2232 
2233 
2234  return SCIP_OKAY;
2235 }
2236 
2243  SCIP* scip,
2244  DEC_DECOMP* decdecomp
2245  )
2246 {
2247 #ifndef NDEBUG
2248  int c;
2249  int b;
2250  int v;
2251 
2252 
2253  SCIPdebugMessage("Problem is %stransformed\n", SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED ? "": "not ");
2254 
2255  for( v = 0; v < SCIPgetNVars(scip); ++v )
2256  {
2257  if( SCIPisEQ(scip, SCIPvarGetLbGlobal(SCIPgetVars(scip)[v]), SCIPvarGetUbGlobal(SCIPgetVars(scip)[v]) ) && SCIPisEQ(scip, SCIPvarGetUbGlobal(SCIPgetVars(scip)[v]), 0. ) )
2258  continue;
2259  assert(SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), SCIPgetVars(scip)[v]));
2260  }
2261 
2262  for( c = 0; c < SCIPgetNConss(scip); ++c )
2263  {
2264  if( !GCGisConsGCGCons(SCIPgetConss(scip)[c]) )
2265  {
2266  assert(SCIPhashmapExists(DECdecompGetConstoblock(decdecomp), SCIPgetConss(scip)[c]));
2267  }
2268  }
2269 
2270  /* Check whether subscipcons are correct */
2271  for( b = 0; b < DECdecompGetNBlocks(decdecomp); ++b )
2272  {
2273  for( c = 0; c < DECdecompGetNSubscipconss(decdecomp)[b]; ++c )
2274  {
2275  SCIP_VAR** curvars;
2276  int ncurvars;
2277  SCIP_CONS* cons = DECdecompGetSubscipconss(decdecomp)[b][c];
2278 
2279  SCIPdebugMessage("Cons <%s> in block %d = %d\n", SCIPconsGetName(cons), b, ((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), cons)) -1); /*lint !e507*/
2280  assert(SCIPfindCons(scip, SCIPconsGetName(cons)) != NULL);
2281  assert(((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), cons)) - 1 == b); /*lint !e507*/
2282  ncurvars = GCGconsGetNVars(scip, cons);
2283  if ( ncurvars == 0 )
2284  continue;
2285  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2286  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
2287 
2288  for( v = 0; v < ncurvars; ++v )
2289  {
2290  int varblock;
2291  SCIP_VAR* var = SCIPvarGetProbvar(curvars[v]);
2292 
2293  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetLbGlobal(var) == SCIPvarGetUbGlobal(var) )
2294  continue;
2295 
2296  varblock = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var)) - 1; /*lint !e507*/
2297  SCIPdebugMessage("\tVar <%s> in block %d = %d\n", SCIPvarGetName(var), b, varblock);
2298 
2299  assert(SCIPfindVar(scip, SCIPvarGetName(var)) != NULL);
2300  assert(SCIPvarIsActive(var));
2301  assert(varblock == b || varblock == DECdecompGetNBlocks(decdecomp)+1 );
2302 
2303  }
2304  SCIPfreeBufferArray(scip, &curvars);
2305  }
2306 
2307  assert((DECdecompGetSubscipvars(decdecomp)[b] == NULL) == (DECdecompGetNSubscipvars(decdecomp)[b] == 0));
2308 
2309 
2310  for( v = 0; v < DECdecompGetNSubscipvars(decdecomp)[b]; ++v )
2311  {
2312  int varblock;
2313  SCIP_VAR* var = DECdecompGetSubscipvars(decdecomp)[b][v];
2314  varblock = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var)) - 1; /*lint !e507*/
2315  SCIPdebugMessage("Var <%s> in block %d = %d\n", SCIPvarGetName(var), b, varblock);
2316  assert(SCIPfindVar(scip, SCIPvarGetName(var)) != NULL);
2317  assert(SCIPvarIsActive(var));
2318  assert(varblock == b || varblock == DECdecompGetNBlocks(decdecomp)+1);
2319  }
2320  }
2321 
2322  /* check linking constraints and variables */
2323  for( v = 0; v < DECdecompGetNLinkingvars(decdecomp); ++v )
2324  {
2325  int varblock;
2326  varblock = (int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), DECdecompGetLinkingvars(decdecomp)[v]); /*lint !e507*/
2327  assert( varblock == DECdecompGetNBlocks(decdecomp) +1 || varblock == DECdecompGetNBlocks(decdecomp)+2); /*lint !e507*/
2328  }
2329  for (c = 0; c < DECdecompGetNLinkingconss(decdecomp); ++c)
2330  {
2331  assert(((int) (size_t) SCIPhashmapGetImage(DECdecompGetConstoblock(decdecomp), DECdecompGetLinkingconss(decdecomp)[c])) -1 == DECdecompGetNBlocks(decdecomp)); /*lint !e507*/
2332  }
2333 
2334  switch( DECdecompGetType(decdecomp) )
2335  {
2336  case DEC_DECTYPE_UNKNOWN:
2337  assert(FALSE);
2338  break;
2339  case DEC_DECTYPE_ARROWHEAD:
2340  assert(DECdecompGetNLinkingvars(decdecomp) > 0 || DECdecompGetNTotalStairlinkingvars(decdecomp) > 0);
2341  break;
2342  case DEC_DECTYPE_BORDERED:
2343  assert(DECdecompGetNLinkingvars(decdecomp) == 0 && DECdecompGetNLinkingconss(decdecomp) > 0);
2344  break;
2345  case DEC_DECTYPE_DIAGONAL:
2346  assert(DECdecompGetNLinkingvars(decdecomp) == 0 && DECdecompGetNLinkingconss(decdecomp) == 0);
2347  break;
2348  case DEC_DECTYPE_STAIRCASE:
2349  assert(DECdecompGetNLinkingvars(decdecomp) > 0 && DECdecompGetNLinkingconss(decdecomp) == 0);
2350  break;
2351  default:
2352  assert(FALSE);
2353  break;
2354  }
2355 
2356 #endif
2357  return SCIP_OKAY;
2358 }
2359 
2362  SCIP* scip,
2363  DEC_DECOMP** decomp,
2364  SCIP_Bool solveorigprob
2365  )
2366 {
2367  SCIP_HASHMAP* constoblock;
2368  SCIP_HASHMAP* vartoblock;
2369  SCIP_CONS** conss;
2370  SCIP_VAR** vars;
2371  SCIP_Bool haslinking;
2372  int nblocks;
2373  int nconss;
2374  int nvars;
2375  int c;
2376  int v;
2377 
2378  assert(scip != NULL);
2379  assert(decomp != NULL);
2380 
2381  SCIP_CALL( DECdecompCreate(scip, decomp) );
2382  conss = SCIPgetConss(scip);
2383  nconss = SCIPgetNConss(scip);
2384  vars = SCIPgetVars(scip);
2385  nvars = SCIPgetNVars(scip);
2386 
2387  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
2388  SCIP_CALL( SCIPhashmapCreate(&vartoblock, SCIPblkmem(scip), nvars) );
2389  haslinking = FALSE;
2390 
2391 
2392  for( c = 0; c < nconss; ++c )
2393  {
2394  if( GCGisConsGCGCons(conss[c]) )
2395  continue;
2396  SCIP_CALL( SCIPhashmapInsert(constoblock, conss[c], (void*) (size_t) 1 ) );
2397  }
2398 
2399  for( v = 0; v < nvars; ++v )
2400  {
2401  SCIP_VAR* probvar = SCIPvarGetProbvar(vars[v]);
2402 
2403  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
2404  continue;
2405  SCIP_CALL( SCIPhashmapInsert(vartoblock, probvar, (void*) (size_t) 1 ) );
2406  }
2407 
2408  if( solveorigprob )
2409  nblocks = 0;
2410  else
2411  nblocks = 1;
2412 
2413  DECfilloutDecompFromHashmaps(scip, *decomp, vartoblock, constoblock, nblocks, haslinking);
2414 
2415  DECdecompSetPresolved(*decomp, TRUE);
2416 
2417  return SCIP_OKAY;
2418 }
2419 
2425 static
2427  int maxblock,
2428  int* blockrepresentative
2429  )
2430 {
2431  int i;
2432  int tempblock = 1;
2433 
2434  assert(maxblock >= 1);
2435  assert(blockrepresentative != NULL );
2436  SCIPdebugPrintf("Blocks: ");
2437 
2438  /* postprocess blockrepresentatives */
2439  for( i = 1; i < maxblock; ++i )
2440  {
2441  /* forward replace the representatives */
2442  assert(blockrepresentative[i] >= 0);
2443  assert(blockrepresentative[i] < maxblock);
2444  if( blockrepresentative[i] != i )
2445  blockrepresentative[i] = blockrepresentative[blockrepresentative[i]];
2446  else
2447  {
2448  blockrepresentative[i] = tempblock;
2449  ++tempblock;
2450  }
2451  /* It is crucial that this condition holds */
2452  assert(blockrepresentative[i] <= i);
2453  SCIPdebugPrintf("%d ", blockrepresentative[i]);
2454  }
2455  SCIPdebugPrintf("\n");
2456  return tempblock-1;
2457 }
2458 
2460 static
2462  SCIP* scip,
2463  SCIP_CONS** conss,
2464  int nconss,
2465  SCIP_Bool* consismaster,
2466  SCIP_HASHMAP* constoblock,
2467  int* vartoblock,
2468  int* nextblock,
2469  int* blockrepresentative
2470  )
2471 {
2472 
2473  int i;
2474  int j;
2475  SCIP_VAR** curvars;
2476  int ncurvars;
2477 
2478  conss = SCIPgetConss(scip);
2479  nconss = SCIPgetNConss(scip);
2480 
2481  /* go through the all constraints */
2482  for( i = 0; i < nconss; ++i )
2483  {
2484  int consblock;
2485  SCIP_CONS* cons = conss[i];
2486 
2487  assert(cons != NULL);
2488  if( GCGisConsGCGCons(cons) )
2489  continue;
2490 
2491  if( consismaster[i] )
2492  continue;
2493 
2494  /* get variables of constraint; ignore empty constraints */
2495  ncurvars = GCGconsGetNVars(scip, cons);
2496  curvars = NULL;
2497  if( ncurvars > 0 )
2498  {
2499  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2500  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
2501  }
2502  assert(ncurvars >= 0);
2503  assert(ncurvars <= SCIPgetNVars(scip));
2504  assert(curvars != NULL || ncurvars == 0);
2505 
2506  assert(SCIPhashmapGetImage(constoblock, cons) == NULL);
2507 
2508  /* if there are no variables, put it in the first block, otherwise put it in the next block */
2509  if( ncurvars == 0 )
2510  consblock = -1;
2511  else
2512  consblock = *nextblock;
2513 
2514  /* go through all variables */
2515  for( j = 0; j < ncurvars; ++j )
2516  {
2517  SCIP_VAR* probvar;
2518  int varindex;
2519  int varblock;
2520 
2521  assert(curvars != NULL);
2522  probvar = SCIPvarGetProbvar(curvars[j]);
2523  assert(probvar != NULL);
2524 
2525  /* ignore variables which have been fixed during presolving */
2526  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
2527  continue;
2528 
2529  varindex = SCIPvarGetProbindex(probvar);
2530  assert(varindex >= 0);
2531  assert(varindex < SCIPgetNVars(scip));
2532 
2534  /* get block of variable */
2535  varblock = vartoblock[varindex];
2536 
2537  SCIPdebugMessage("\tVar %s (%d): ", SCIPvarGetName(probvar), varblock);
2538  /* if variable is already assigned to a block, assign constraint to that block */
2539  if( varblock > -1 && varblock != consblock )
2540  {
2541  consblock = MIN(consblock, blockrepresentative[varblock]);
2542  SCIPdebugPrintf("still in block %d.\n", varblock);
2543  }
2544  else if( varblock == -1 )
2545  {
2546  /* if variable is free, assign it to the new block for this constraint */
2547  varblock = consblock;
2548  assert(varblock > 0);
2549  assert(varblock <= *nextblock);
2550  vartoblock[varindex] = varblock;
2551  SCIPdebugPrintf("new in block %d.\n", varblock);
2552  }
2553  else
2554  {
2555  assert((varblock > 0) && (consblock == varblock));
2556  SCIPdebugPrintf("no change.\n");
2557  }
2558 
2559  SCIPdebugPrintf("VARINDEX: %d (%d)\n", varindex, vartoblock[varindex]);
2560  }
2561 
2562  /* if the constraint belongs to a new block, mark it as such */
2563  if( consblock == *nextblock )
2564  {
2565  assert(consblock > 0);
2566  blockrepresentative[consblock] = consblock;
2567  assert(blockrepresentative[consblock] > 0);
2568  assert(blockrepresentative[consblock] <= *nextblock);
2569  ++(*nextblock);
2570  }
2571 
2572  SCIPdebugMessage("Cons %s will be in block %d (next %d)\n", SCIPconsGetName(cons), consblock, *nextblock);
2573 
2574  for( j = 0; j < ncurvars; ++j )
2575  {
2576  SCIP_VAR* probvar;
2577  int varindex;
2578  int oldblock;
2579 
2580  assert(curvars != NULL);
2581  probvar = SCIPvarGetProbvar(curvars[j]);
2582  assert(probvar != NULL);
2583 
2584  /* ignore variables which have been fixed during presolving */
2585  if( SCIPvarGetStatus(probvar) == SCIP_VARSTATUS_FIXED )
2586  continue;
2587 
2588  varindex = SCIPvarGetProbindex(probvar);
2589  assert(varindex >= 0);
2590  assert(varindex < SCIPgetNVars(scip));
2591 
2592  oldblock = vartoblock[varindex];
2593  assert((oldblock > 0) && (oldblock <= *nextblock));
2594 
2595  SCIPdebugMessage("\tVar %s ", SCIPvarGetName(probvar));
2596  if( oldblock != consblock )
2597  {
2598  SCIPdebugPrintf("reset from %d to block %d.\n", oldblock, consblock);
2599  vartoblock[varindex] = consblock;
2600  SCIPdebugPrintf("VARINDEX: %d (%d)\n", varindex, consblock);
2601 
2602  if( (blockrepresentative[oldblock] != -1) && (blockrepresentative[oldblock] > blockrepresentative[consblock]) )
2603  {
2604  int oldrepr;
2605  oldrepr = blockrepresentative[oldblock];
2606  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldblock, blockrepresentative[oldblock], consblock);
2607  assert(consblock > 0);
2608  blockrepresentative[oldblock] = consblock;
2609  if( (oldrepr != consblock) && (oldrepr != oldblock) )
2610  {
2611  blockrepresentative[oldrepr] = consblock;
2612  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldrepr, blockrepresentative[oldrepr], consblock);
2613  }
2614  }
2615  }
2616  else
2617  {
2618  SCIPdebugPrintf("will not be changed from %d to %d.\n", oldblock, consblock);
2619  }
2620  }
2621 
2622  SCIPfreeBufferArrayNull(scip, &curvars);
2623  assert(consblock >= 1 || consblock == -1);
2624  assert(consblock <= *nextblock);
2625 
2626  /* store the constraint block */
2627  if( consblock != -1 )
2628  {
2629  SCIPdebugMessage("cons %s in block %d\n", SCIPconsGetName(cons), consblock);
2630  SCIP_CALL( SCIPhashmapInsert(constoblock, cons, (void*)(size_t)consblock) );
2631  }
2632  else
2633  {
2634  SCIPdebugMessage("ignoring %s\n", SCIPconsGetName(cons));
2635  }
2636  }
2637 
2638  return SCIP_OKAY;
2639 }
2640 
2642 static
2643 SCIP_RETCODE fillConstoblock(
2644  SCIP_CONS** conss,
2645  int nconss,
2646  SCIP_Bool* consismaster,
2647  int nblocks,
2648  SCIP_HASHMAP* constoblock,
2649  SCIP_HASHMAP* newconstoblock,
2650  int* blockrepresentative
2651  )
2652 {
2653  int i;
2654 
2655  /* convert temporary data to detectordata */
2656  for( i = 0; i < nconss; ++i )
2657  {
2658  int consblock;
2659 
2660  SCIP_CONS* cons = conss[i];
2661 
2662  if( GCGisConsGCGCons(cons) )
2663  continue;
2664 
2665  if( consismaster[i] )
2666  {
2667  SCIP_CALL( SCIPhashmapInsert(newconstoblock, cons, (void*) (size_t) (nblocks+1)) );
2668  continue;
2669  }
2670 
2671  if( !SCIPhashmapExists(constoblock, cons) )
2672  continue;
2673 
2674  consblock = (int) (size_t) SCIPhashmapGetImage(constoblock, cons); /*lint !e507*/
2675  assert(consblock > 0);
2676  consblock = blockrepresentative[consblock];
2677  assert(consblock <= nblocks);
2678  SCIP_CALL( SCIPhashmapInsert(newconstoblock, cons, (void*)(size_t)consblock) );
2679  SCIPdebugMessage("%d %s\n", consblock, SCIPconsGetName(cons));
2680  }
2681  return SCIP_OKAY;
2682 }
2683 
2689  SCIP* scip,
2690  DEC_DECOMP** decomp,
2691  SCIP_CONS** masterconss,
2692  int nmasterconss
2693  )
2694 {
2695  SCIP_HASHMAP* constoblock;
2696  SCIP_HASHMAP* newconstoblock;
2697  SCIP_CONS** conss;
2698  int nconss;
2699  int nvars;
2700  int nblocks;
2701  int* blockrepresentative;
2702  int nextblock = 1;
2703  SCIP_Bool* consismaster;
2704  int i;
2705  int* vartoblock;
2706 
2707  assert(scip != NULL);
2708  assert(decomp != NULL);
2709  assert(nmasterconss == 0 || masterconss != NULL);
2710  assert(SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED);
2711 
2712  conss = SCIPgetConss(scip);
2713  nconss = SCIPgetNConss(scip);
2714  nvars = SCIPgetNVars(scip);
2715 
2716  assert( nmasterconss <= nconss );
2717 
2718  if( GCGisConsGCGCons(conss[nconss-1]) )
2719  --nconss;
2720 
2721  nblocks = nconss-nmasterconss+1;
2722  assert(nblocks > 0);
2723 
2724  SCIP_CALL( SCIPallocBufferArray(scip, &blockrepresentative, nblocks) );
2725  SCIP_CALL( SCIPallocBufferArray(scip, &consismaster, nconss) );
2726  SCIP_CALL( SCIPallocBufferArray(scip, &vartoblock, nvars) );
2727  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), nconss) );
2728  SCIP_CALL( SCIPhashmapCreate(&newconstoblock, SCIPblkmem(scip), nconss) );
2729 
2730  for( i = 0; i < nmasterconss; ++i )
2731  {
2732  SCIP_CALL( SCIPhashmapInsert(constoblock, masterconss[i], (void*) (size_t) (nblocks+1)) );
2733  }
2734 
2735  for( i = 0; i < nconss; ++i )
2736  {
2737  assert(!GCGisConsGCGCons(conss[i]));
2738  consismaster[i] = SCIPhashmapExists(constoblock, conss[i]);
2739  }
2740 
2741  for( i = 0; i < nvars; ++i )
2742  {
2743  vartoblock[i] = -1;
2744  }
2745 
2746  for( i = 0; i < nblocks; ++i )
2747  {
2748  blockrepresentative[i] = -1;
2749  }
2750 
2751  SCIP_CALL( assignConstraintsToRepresentatives(scip, conss, nconss, consismaster, constoblock, vartoblock, &nextblock, blockrepresentative) );
2752 
2753  /* postprocess blockrepresentatives */
2754  nblocks = processBlockRepresentatives(nextblock, blockrepresentative);
2755 
2756  /* convert temporary data to detectordata */
2757  SCIP_CALL( fillConstoblock(conss, nconss, consismaster, nblocks, constoblock, newconstoblock, blockrepresentative) );
2758  SCIP_CALL( DECdecompCreate(scip, decomp) );
2759  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, *decomp, newconstoblock, nblocks, FALSE) );
2760 
2761  SCIPfreeBufferArray(scip, &vartoblock);
2762  SCIPfreeBufferArray(scip, &consismaster);
2763  SCIPfreeBufferArray(scip, &blockrepresentative);
2764  SCIPhashmapFree(&constoblock);
2765 
2766  return SCIP_OKAY;
2767 }
2768 
2770 static
2772  SCIP_VAR* var,
2773  int* nbinvars,
2774  int* nintvars,
2775  int* nimplvars,
2776  int* ncontvars,
2777  int nproblems,
2778  int i
2779 )
2780 {
2781  assert(var != NULL);
2782  assert(i >= 0);
2783  assert(i < nproblems);
2784 
2785  if( nbinvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarIsBinary(var)) )
2786  {
2787  ++(nbinvars[i]);
2788  assert(nbinvars[i] > 0);
2789  }
2790  if( nintvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER && !SCIPvarIsBinary(var)) )
2791  {
2792  ++(nintvars[i]);
2793  assert(nintvars[i] > 0);
2794  }
2795  if( nimplvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) )
2796  {
2797  ++(nimplvars[i]);
2798  assert(nimplvars[i] > 0);
2799  }
2800  if( ncontvars != NULL && (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS) )
2801  {
2802  ++(ncontvars[i]);
2803  assert(ncontvars[i] > 0);
2804  }
2805 }
2806 
2807 /* score methods */
2808 
2811  SCIP* scip,
2812  DEC_DECOMP* decomp,
2813  int* nvars,
2814  int* nbinvars,
2815  int* nintvars,
2816  int* nimplvars,
2817  int* ncontvars,
2818  int nproblems
2819 )
2820 {
2821  int i;
2822  int j;
2823 
2824  assert(scip != NULL);
2825  assert(decomp != NULL);
2826  assert(nproblems > 0);
2827 
2828  assert(DECdecompGetType(decomp) != DEC_DECTYPE_UNKNOWN);
2829  if( nvars != NULL )
2830  BMSclearMemoryArray(nvars, nproblems);
2831  if( nbinvars != NULL )
2832  BMSclearMemoryArray(nbinvars, nproblems);
2833  if( nintvars != NULL )
2834  BMSclearMemoryArray(nintvars, nproblems);
2835  if( nimplvars != NULL )
2836  BMSclearMemoryArray(nimplvars, nproblems);
2837  if( ncontvars != NULL )
2838  BMSclearMemoryArray(ncontvars, nproblems);
2839 
2840  for( i = 0; i < nproblems; ++i )
2841  {
2842  SCIP_VAR*** subscipvars;
2843  int* nsubscipvars;
2844 
2845  nsubscipvars = DECdecompGetNSubscipvars(decomp);
2846  subscipvars = DECdecompGetSubscipvars(decomp);
2847  if( nvars != NULL )
2848  nvars[i] = nsubscipvars[i];
2849 
2850  for( j = 0; j < nsubscipvars[i]; ++j )
2851  {
2852  incVarsData(subscipvars[i][j], nbinvars, nintvars, nimplvars, ncontvars, nproblems, i);
2853  }
2854  }
2855 }
2856 
2857 
2860  SCIP* scip,
2861  DEC_DECOMP* decomp,
2862  int* nvars,
2863  int* nbinvars,
2864  int* nintvars,
2865  int* nimplvars,
2866  int* ncontvars
2867 )
2868 {
2869  int i;
2870  SCIP_VAR** linkingvars;
2871  int nlinkingvars;
2872 
2873  assert(scip != NULL);
2874  assert(decomp != NULL);
2875 
2876  assert(DECdecompGetType(decomp) != DEC_DECTYPE_UNKNOWN);
2877 
2878  nlinkingvars = DECdecompGetNLinkingvars(decomp);
2879  linkingvars = DECdecompGetLinkingvars(decomp);
2880 
2881  if( nvars != NULL )
2882  *nvars = nlinkingvars;
2883  if( nbinvars != NULL )
2884  *nbinvars = 0;
2885  if( nintvars != NULL )
2886  *nintvars = 0;
2887  if( nimplvars != NULL )
2888  *nimplvars = 0;
2889  if( ncontvars != NULL )
2890  *ncontvars = 0;
2891 
2892 
2893  for( i = 0; i < nlinkingvars; ++i )
2894  {
2895  incVarsData(linkingvars[i], nbinvars, nintvars, nimplvars, ncontvars, 1, 0);
2896  }
2897 }
2898 
2909 SCIP_RETCODE DECgetDensityData(
2910  SCIP* scip,
2911  DEC_DECOMP* decomp,
2912  SCIP_VAR** vars,
2913  int nvars,
2914  SCIP_CONS** conss,
2915  int nconss,
2916  int* varsubproblemdensity,
2917  int* varmasterdensity,
2918  int* conssubproblemdensity,
2919  int* consmasterdensity
2920 )
2921 {
2922  int nlinkingconss;
2923  SCIP_HASHMAP* vartoblock;
2924  SCIP_CONS** curconss;
2925 
2926  int ncurvars;
2927  SCIP_VAR** curvars;
2928  SCIP_Bool success;
2929 
2930  int i;
2931  int j;
2932  int v;
2933  int c;
2934 
2935  assert(scip != NULL);
2936  assert(decomp != NULL);
2937  assert(vars != NULL);
2938  assert(nvars > 0);
2939  assert(conss != NULL);
2940  assert(varsubproblemdensity != NULL);
2941  assert(varmasterdensity != NULL);
2942  assert(conssubproblemdensity != NULL);
2943  assert(consmasterdensity != NULL);
2944 
2945  /* make sure the passed data is initialised to 0 */
2946  BMSclearMemoryArray(vars, nvars);
2947  BMSclearMemoryArray(conss, nconss);
2948  BMSclearMemoryArray(varsubproblemdensity, nvars);
2949  BMSclearMemoryArray(varmasterdensity, nvars);
2950  BMSclearMemoryArray(conssubproblemdensity, nconss);
2951  BMSclearMemoryArray(consmasterdensity, nconss);
2952 
2953  BMScopyMemoryArray(vars, SCIPgetVars(scip), nvars);
2954 
2955  vartoblock = DECdecompGetVartoblock(decomp);
2956  c = 0;
2957  for( i = 0; i < DECdecompGetNBlocks(decomp); ++i )
2958  {
2959  curconss = DECdecompGetSubscipconss(decomp)[i];
2960  assert(curconss != NULL);
2961 
2962  for( j = 0; j < DECdecompGetNSubscipconss(decomp)[i]; ++j )
2963  {
2964  assert(c < nconss); /* This assertion and the logic forbids constraints in more than one block */
2965  conss[c] = curconss[j];
2966 
2967  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
2968  assert(success);
2969  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
2970  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
2971  assert(success);
2972 
2973  for( v = 0; v < ncurvars; ++v )
2974  {
2975  SCIP_VAR* var;
2976  int block;
2977  int probindex;
2978 
2979  var = curvars[v];
2980  var = SCIPvarGetProbvar(var);
2981  probindex = SCIPvarGetProbindex(var);
2982 
2983  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
2984  continue;
2985 
2986  assert(probindex >= 0);
2987  assert(probindex < nvars);
2988  varsubproblemdensity[probindex] += 1;
2989  assert(varsubproblemdensity[probindex] > 0);
2990  block = (int) (size_t) SCIPhashmapGetImage(vartoblock, var); /*lint !e507*/
2991  assert(block > 0);
2992 
2993  if( block <= DECdecompGetNBlocks(decomp) )
2994  {
2995  conssubproblemdensity[c] +=1;
2996  }
2997  else
2998  {
2999  consmasterdensity[c] += 1;
3000  }
3001  }
3002 
3003  SCIPfreeBufferArray(scip, &curvars);
3004  c++;
3005  }
3006  }
3007 
3008  nlinkingconss = DECdecompGetNLinkingconss(decomp);
3009  curconss = DECdecompGetLinkingconss(decomp);
3010 
3011  for( j = 0; j < nlinkingconss; ++j )
3012  {
3013  assert(c < nconss); /* This assertion and the logic forbids constraints in more than one block */
3014  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
3015  assert(success);
3016  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3017  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
3018  assert(success);
3019 
3020  conss[c] = curconss[j];
3021 
3022  for( v = 0; v < ncurvars; ++v )
3023  {
3024  SCIP_VAR* var;
3025  int probindex;
3026 
3027  var = curvars[v];
3028  var = SCIPvarGetProbvar(var);
3029  probindex = SCIPvarGetProbindex(var);
3030 
3031  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
3032  continue;
3033 
3034  assert(probindex >= 0);
3035  assert(probindex < nvars);
3036  varmasterdensity[probindex] += 1;
3037  assert(varmasterdensity[probindex] > 0);
3038  SCIPdebugMessage("Var <%s> appears in cons <%s>, total count: %d\n", SCIPvarGetName(var), SCIPconsGetName(curconss[j]), varmasterdensity[probindex]);
3039  }
3040 
3041  consmasterdensity[c] = ncurvars;
3042  c++;
3043 
3044  SCIPfreeBufferArray(scip, &curvars);
3045  }
3046 
3047  return SCIP_OKAY;
3048 }
3049 
3051 static
3053  SCIP* scip,
3054  SCIP_Real lhs,
3055  SCIP_Real coef,
3056  SCIP_Real rhs,
3057  int* downlock,
3058  int* uplock
3059  )
3060 {
3061  assert(scip != NULL);
3062  assert(downlock != NULL);
3063  assert(uplock != NULL);
3064 
3065  if( !SCIPisInfinity(scip, -lhs) )
3066  {
3067  if( SCIPisPositive(scip, coef) )
3068  ++(*downlock);
3069  if( SCIPisNegative(scip, coef) )
3070  ++(*uplock);
3071 
3072  }
3073  if( !SCIPisInfinity(scip, rhs) )
3074  {
3075  if( SCIPisPositive(scip, coef) )
3076  ++(*uplock);
3077  if( SCIPisNegative(scip, coef) )
3078  ++(*downlock);
3079  }
3080 
3081 }
3082 
3090 SCIP_RETCODE DECgetVarLockData(
3091  SCIP* scip,
3092  DEC_DECOMP* decomp,
3093  SCIP_VAR** vars,
3094  int nvars,
3095  int nsubproblems,
3096  int** subsciplocksdown,
3097  int** subsciplocksup,
3098  int* masterlocksdown,
3099  int* masterlocksup
3100  )
3101 {
3102  int nlinkingconss;
3103  SCIP_CONS** curconss;
3104  SCIP_VAR** curvars;
3105  SCIP_Real* curvals;
3106  int ncurvars;
3107  SCIP_Real lhs;
3108  SCIP_Real rhs;
3109 
3110  SCIP_Bool success;
3111 
3112  int i;
3113  int j;
3114  int v;
3115 
3116  assert(scip != NULL);
3117  assert(decomp != NULL);
3118  assert(vars != NULL);
3119  assert(nvars > 0);
3120  assert(nvars == SCIPgetNVars(scip));
3121  assert(subsciplocksdown != NULL);
3122  assert(subsciplocksup != NULL);
3123  assert(masterlocksdown != NULL);
3124  assert(masterlocksup != NULL);
3125 
3126  /* make sure the passed data is initialised to 0 */
3127  BMSclearMemoryArray(vars, nvars);
3128  BMScopyMemoryArray(vars, SCIPgetVars(scip), nvars);
3129  BMSclearMemoryArray(masterlocksdown, nvars);
3130  BMSclearMemoryArray(masterlocksup, nvars);
3131  for( i = 0; i < nsubproblems; ++i )
3132  {
3133  BMSclearMemoryArray(subsciplocksdown[i], nvars); /*lint !e866*/
3134  BMSclearMemoryArray(subsciplocksup[i], nvars); /*lint !e866*/
3135  }
3136 
3137  for( i = 0; i < DECdecompGetNBlocks(decomp); ++i )
3138  {
3139  curconss = DECdecompGetSubscipconss(decomp)[i];
3140  assert(curconss != NULL);
3141 
3142  for( j = 0; j < DECdecompGetNSubscipconss(decomp)[i]; ++j )
3143  {
3144 
3145  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
3146  assert(success);
3147  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3148  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
3149 
3150  SCIP_CALL( GCGconsGetVals(scip, curconss[j], curvals, ncurvars) );
3151  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
3152  assert(success);
3153 
3154  rhs = GCGconsGetRhs(scip, curconss[j]);
3155  lhs = GCGconsGetLhs(scip, curconss[j]);
3156 
3157  for( v = 0; v < ncurvars; ++v )
3158  {
3159  SCIP_VAR* var;
3160  int probindex;
3161 
3162  var = curvars[v];
3163  var = SCIPvarGetProbvar(var);
3164  probindex = SCIPvarGetProbindex(var);
3165 
3166  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
3167  continue;
3168 
3169  assert(probindex >= 0);
3170  assert(probindex < nvars);
3171  assert(SCIPhashmapExists(DECdecompGetVartoblock(decomp), var));
3172 
3173  increaseLock(scip, lhs, curvals[v], rhs, &(subsciplocksdown[i][probindex]), &(subsciplocksup[i][probindex]));
3174  }
3175 
3176  SCIPfreeBufferArray(scip, &curvals);
3177  SCIPfreeBufferArray(scip, &curvars);
3178  }
3179  }
3180 
3181  nlinkingconss = DECdecompGetNLinkingvars(decomp);
3182  curconss = DECdecompGetLinkingconss(decomp);
3183  for( j = 0; j < nlinkingconss; ++j )
3184  {
3185  SCIP_CALL( SCIPgetConsNVars(scip, curconss[j], &ncurvars, &success) );
3186  assert(success);
3187  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3188  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
3189 
3190  SCIP_CALL( GCGconsGetVals(scip, curconss[j], curvals, ncurvars) );
3191  SCIP_CALL( SCIPgetConsVars(scip, curconss[j], curvars, ncurvars, &success) );
3192  assert(success);
3193 
3194  rhs = GCGconsGetRhs(scip, curconss[j]);
3195  lhs = GCGconsGetLhs(scip, curconss[j]);
3196 
3197  for( v = 0; v < ncurvars; ++v )
3198  {
3199  SCIP_VAR* var;
3200  int probindex;
3201 
3202  var = curvars[v];
3203  var = SCIPvarGetProbvar(var);
3204  probindex = SCIPvarGetProbindex(var);
3205 
3206  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
3207  continue;
3208 
3209  assert(probindex >= 0);
3210  assert(probindex < nvars);
3211 
3212  increaseLock(scip, lhs, curvals[v], rhs, &(masterlocksdown[probindex]), &(masterlocksup[probindex]));
3213  }
3214 
3215  SCIPfreeBufferArray(scip, &curvals);
3216  SCIPfreeBufferArray(scip, &curvars);
3217  }
3218 
3219  return SCIP_OKAY;
3220 }
3221 
3222 
3227  SCIP* scip,
3228  DEC_DECOMP* decdecomp,
3229  SCIP_Real maxwhitescore
3230  )
3231 {
3232  assert(maxwhitescore >= 0);
3233 
3234  decdecomp->maxwhitescore = maxwhitescore;
3235 
3236  return;
3237 }
3238 
3239 
3244  SCIP* scip,
3245  DEC_DECOMP* decdecomp
3246  )
3247 {
3248  DEC_SCORES score;
3249 
3250  if( decdecomp->maxwhitescore == -1.)
3251  DECevaluateDecomposition(scip, decdecomp, &score);
3252 
3253  assert(decdecomp->maxwhitescore >= 0);
3254 
3255  return decdecomp->maxwhitescore;
3256 }
3257 
3262  SCIP* scip,
3263  DEC_DECOMP* decdecomp,
3264  DEC_SCORES* score
3265  )
3266 {
3267  SCIP_Longint matrixarea;
3268  SCIP_Longint borderarea;
3269  int nvars;
3270  int nconss;
3271  int i;
3272  int j;
3273  int k;
3274  /* int blockarea; */
3275  SCIP_Real varratio;
3276  int* nzblocks;
3277  int nblocks;
3278  int* nlinkvarsblocks;
3279  int* nvarsblocks;
3280  SCIP_Real* blockdensities;
3281  int* blocksizes;
3282  SCIP_Real density;
3283  SCIP_Real blackarea;
3284 
3285  SCIP_Real alphaborderarea;
3286  SCIP_Real alphalinking;
3287  SCIP_Real alphadensity;
3288 
3289  alphaborderarea = 0.6;
3290  alphalinking = 0.2 ;
3291  alphadensity = 0.2;
3292  blackarea = 0.;
3293 
3294 
3295  assert(scip != NULL);
3296  assert(score != NULL);
3297 
3298  nvars = SCIPgetNVars(scip);
3299  nconss = SCIPgetNConss(scip);
3300 
3301  nblocks = DECdecompGetNBlocks(decdecomp);
3302 
3303  SCIP_CALL( SCIPallocBufferArray(scip, &nzblocks, nblocks) );
3304  SCIP_CALL( SCIPallocBufferArray(scip, &nlinkvarsblocks, nblocks) );
3305  SCIP_CALL( SCIPallocBufferArray(scip, &blockdensities, nblocks) );
3306  SCIP_CALL( SCIPallocBufferArray(scip, &blocksizes, nblocks) );
3307  SCIP_CALL( SCIPallocBufferArray(scip, &nvarsblocks, nblocks) );
3308  /*
3309  * 3 Scores
3310  *
3311  * - Area percentage (min)
3312  * - block density (max)
3313  * - \pi_b {v_b|v_b is linking}/#vb (min)
3314  */
3315 
3316  /* calculate matrix area */
3317  matrixarea = (SCIP_Longint) nvars*nconss;
3318 
3319  blackarea += ( DECdecompGetNLinkingvars(decdecomp) - DECdecompGetNMastervars(decdecomp) ) * nconss;
3320  blackarea += DECdecompGetNLinkingconss(decdecomp) * nvars;
3321 
3322  blackarea -= (DECdecompGetNLinkingvars(decdecomp) - DECdecompGetNMastervars(decdecomp) ) * DECdecompGetNLinkingconss(decdecomp);
3323 
3324 
3325  /* calculate slave sizes, nonzeros and linkingvars */
3326  for( i = 0; i < nblocks; ++i )
3327  {
3328  SCIP_CONS** curconss;
3329  int ncurconss;
3330  int nvarsblock;
3331  SCIP_Bool *ishandled;
3332 
3333  SCIP_CALL( SCIPallocBufferArray(scip, &ishandled, nvars) );
3334  nvarsblock = 0;
3335  nzblocks[i] = 0;
3336  nlinkvarsblocks[i] = 0;
3337  blackarea += DECdecompGetNSubscipconss(decdecomp)[i] * ( DECdecompGetNSubscipvars(decdecomp)[i] );
3338 
3339  for( j = 0; j < nvars; ++j )
3340  {
3341  ishandled[j] = FALSE;
3342  }
3343  curconss = DECdecompGetSubscipconss(decdecomp)[i];
3344  ncurconss = DECdecompGetNSubscipconss(decdecomp)[i];
3345 
3346  for( j = 0; j < ncurconss; ++j )
3347  {
3348  SCIP_VAR** curvars;
3349  SCIP_VAR* var;
3350  int ncurvars;
3351  ncurvars = GCGconsGetNVars(scip, curconss[j]);
3352  if ( ncurvars == 0 )
3353  continue;
3354  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3355  SCIP_CALL( GCGconsGetVars(scip, curconss[j], curvars, ncurvars) );
3356 
3357  for( k = 0; k < ncurvars; ++k )
3358  {
3359  int block;
3360  if( !GCGisVarRelevant(curvars[k]) )
3361  continue;
3362 
3363  var = SCIPvarGetProbvar(curvars[k]);
3364  assert(var != NULL);
3365  if( !GCGisVarRelevant(var) )
3366  continue;
3367 
3368  assert(SCIPvarIsActive(var));
3369  assert(!SCIPvarIsDeleted(var));
3370  ++(nzblocks[i]);
3371  if( !SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), var) )
3372  {
3373  block = (int)(size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), curvars[k]); /*lint !e507*/
3374  }
3375  else
3376  {
3377  assert(SCIPhashmapExists(DECdecompGetVartoblock(decdecomp), var));
3378  block = (int)(size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decdecomp), var); /*lint !e507*/
3379  }
3380 
3381  if( block == nblocks+1 && ishandled[SCIPvarGetProbindex(var)] == FALSE )
3382  {
3383  ++(nlinkvarsblocks[i]);
3384  }
3385  ishandled[SCIPvarGetProbindex(var)] = TRUE;
3386  }
3387 
3388  SCIPfreeBufferArray(scip, &curvars);
3389  }
3390 
3391  for( j = 0; j < nvars; ++j )
3392  {
3393  if( ishandled[j] )
3394  {
3395  ++nvarsblock;
3396  }
3397  }
3398 
3399  blocksizes[i] = nvarsblock*ncurconss;
3400  nvarsblocks[i] = nvarsblock;
3401  if( blocksizes[i] > 0 )
3402  {
3403  blockdensities[i] = 1.0*nzblocks[i]/blocksizes[i];
3404  }
3405  else
3406  {
3407  blockdensities[i] = 0.0;
3408  }
3409 
3410  assert(blockdensities[i] >= 0 && blockdensities[i] <= 1.0);
3411  SCIPfreeBufferArray(scip, &ishandled);
3412  }
3413 
3414  borderarea = (SCIP_Longint) DECdecompGetNLinkingconss(decdecomp)*nvars + (SCIP_Longint) DECdecompGetNLinkingvars(decdecomp)*(nconss-DECdecompGetNLinkingconss(decdecomp));
3415 
3416  density = 1E20;
3417  varratio = 1.0;
3418  for( i = 0; i < nblocks; ++i )
3419  {
3420  density = MIN(density, blockdensities[i]);
3421 
3422  if( DECdecompGetNLinkingvars(decdecomp) > 0 )
3423  {
3424  varratio *= 1.0*nlinkvarsblocks[i]/DECdecompGetNLinkingvars(decdecomp);
3425  }
3426  else
3427  {
3428  varratio = 0;
3429  }
3430  }
3431 
3432  score->linkingscore = (0.5+0.5*varratio);
3433  score->borderscore = (1.0*(borderarea)/matrixarea);
3434  score->densityscore = (1-density);
3435  //score->maxwhitescore = blackarea/( nconss * nvars );
3436 
3437  //decdecomp->maxwhitescore = score->maxwhitescore;
3438 
3439 
3440  switch( DECdecompGetType(decdecomp) )
3441  {
3442  case DEC_DECTYPE_ARROWHEAD:
3443  score->totalscore = alphaborderarea*(score->borderscore) + alphalinking*(score->linkingscore) + alphadensity*(score->densityscore);
3444 /* score->totalscore = score->borderscore*score->linkingscore*score->densityscore; */
3445  break;
3446  case DEC_DECTYPE_BORDERED:
3447  score->totalscore = alphaborderarea*(score->borderscore) + alphalinking*(score->linkingscore) + alphadensity*(score->densityscore);
3448  /* score->totalscore = score->borderscore*score->linkingscore*score->densityscore; */
3449  break;
3450  case DEC_DECTYPE_DIAGONAL:
3451  if(nblocks == 1 || nblocks == 0)
3452  score->totalscore = 1.0;
3453  else
3454  score->totalscore = 0.0;
3455  break;
3456  case DEC_DECTYPE_STAIRCASE:
3457  score->totalscore = alphaborderarea*(score->borderscore) + alphalinking*(score->linkingscore) + 0.2*(score->densityscore);
3458 /* score->totalscore = score->borderscore*score->linkingscore*score->densityscore; */
3459  break;
3460  case DEC_DECTYPE_UNKNOWN:
3461  SCIPerrorMessage("Decomposition type is %s, cannot compute score\n", DECgetStrType(DECdecompGetType(decdecomp)));
3462  assert(FALSE);
3463  break;
3464  default:
3465  SCIPerrorMessage("No rule for this decomposition type, cannot compute score\n");
3466  assert(FALSE);
3467  break;
3468  }
3469  if(nblocks == 1 || nblocks == 0)
3470  score->totalscore = 1.0;
3471 
3472  if( nblocks == 0 || nblocks == 1)
3473  score->totalscore = 1;
3474 
3475  SCIPfreeBufferArray(scip, &nvarsblocks);
3476  SCIPfreeBufferArray(scip, &blocksizes);
3477  SCIPfreeBufferArray(scip, &blockdensities);
3478  SCIPfreeBufferArray(scip, &nlinkvarsblocks);
3479  SCIPfreeBufferArray(scip, &nzblocks);
3480  return SCIP_OKAY;
3481 }
3482 
3484 static
3485 SCIP_RETCODE computeVarDensities(
3486  SCIP* scip,
3487  DEC_DECOMP* decomp,
3488  int* varprobdensity,
3489  int* varmasterdensity,
3490  SCIP_VAR** vars,
3491  int nvars,
3492  DEC_STATISTIC* blockvardensities,
3493  DEC_STATISTIC* mastervardensity,
3494  int nblocks
3495  )
3496 {
3497  int v;
3498  int b;
3499  SCIP_Real** vardistribution;
3500  int* nvardistribution;
3501  SCIP_Real* mastervardistribution;
3502 
3503  SCIP_Real max = 0;
3504  SCIP_Real min = 1.0;
3505  SCIP_Real median = 0;
3506  SCIP_Real mean = 0;
3507 
3508  assert(scip != NULL);
3509  assert(decomp != NULL);
3510 
3511  assert(vars != NULL);
3512  assert(nvars > 0);
3513  assert(blockvardensities != NULL);
3514  assert(mastervardensity != NULL);
3515  assert(nblocks >= 0);
3516 
3517  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vardistribution, nblocks) );
3518  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nvardistribution, nblocks) );
3519 
3520  BMSclearMemoryArray(vardistribution, nblocks);
3521  BMSclearMemoryArray(nvardistribution, nblocks);
3522 
3523  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mastervardistribution, nvars) );
3524  BMSclearMemoryArray(mastervardistribution, nvars);
3525 
3526  for( b = 0; b < nblocks; ++b )
3527  {
3528  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]) ); /*lint !e866 !e666*/
3529  BMSclearMemoryArray(vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]); /*lint !e866 */
3530  }
3531 
3532  for( v = 0; v < nvars; ++v )
3533  {
3534  int block = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decomp), (vars[v]))) - 1; /*lint !e507 */
3535  assert(block >= 0);
3536  SCIPdebugMessage("Var <%s>:", SCIPvarGetName(vars[v]));
3537 
3538 
3539  mastervardistribution[v] = 1.0*varmasterdensity[v]/DECdecompGetNLinkingconss(decomp);
3540  SCIPdebugPrintf("master %d ", varmasterdensity[v]);
3541 
3542  if( block < nblocks )
3543  {
3544  vardistribution[block][nvardistribution[block]] = 1.0*varprobdensity[v]/DECdecompGetNSubscipconss(decomp)[block];
3545  SCIPdebugPrintf("block %d %.3f\n", block, vardistribution[block][nvardistribution[block]]);
3546  ++(nvardistribution[block]);
3547  }
3548  else
3549  {
3550  SCIPdebugPrintf("\n");
3551  }
3552  }
3553 
3554  for( b = 0; b < nblocks; ++b )
3555  {
3556  int ncurvars = DECdecompGetNSubscipvars(decomp)[b];
3557 
3558  max = 0;
3559  min = 1.0;
3560  median = 0;
3561  mean = 0;
3562 
3563 
3564 
3565  SCIPdebugMessage("block %d:", b);
3566  for( v = 0; v < ncurvars; ++v )
3567  {
3568 
3569  SCIPdebugPrintf(" <%s> %.3f", SCIPvarGetName(DECdecompGetSubscipvars(decomp)[b][v]), vardistribution[b][v]);
3570  max = MAX(max, vardistribution[b][v]);
3571  min = MIN(min, vardistribution[b][v]);
3572  mean += 1.0*vardistribution[b][v]/ncurvars;
3573 
3574  }
3575  if( ncurvars > 0 )
3576  median = quick_select_median(vardistribution[b], ncurvars);
3577 
3578  SCIPdebugPrintf("\nmin: %.3f, max: %.3f, median: %.3f, mean: %.3f\n", min, max, median, mean);
3579 
3580  blockvardensities[b].max = max;
3581  blockvardensities[b].min = min;
3582  blockvardensities[b].median = median;
3583  blockvardensities[b].mean = mean;
3584  }
3585  max = 0;
3586  min = 1.0;
3587  mean = 0;
3588 
3589  SCIPdebugMessage("master:");
3590 
3591  for( v = 0; v < nvars; ++v )
3592  {
3593 
3594  SCIPdebugPrintf(" <%s> %.3f", SCIPvarGetName(vars[v]), mastervardistribution[v]);
3595  max = MAX(max, mastervardistribution[v]);
3596  min = MIN(min, mastervardistribution[v]);
3597  mean += 1.0*mastervardistribution[v]/nvars;
3598 
3599  }
3600  median = quick_select_median(mastervardistribution, nvars);
3601  SCIPdebugPrintf("\nmin: %.3f, max: %.3f, median: %.3f, mean: %.3f\n", min, max, median, mean);
3602 
3603 
3604  mastervardensity->max = max;
3605  mastervardensity->min = min;
3606  mastervardensity->median = median;
3607  mastervardensity->mean = mean;
3608 
3609  for( b = 0; b < nblocks; ++b )
3610  {
3611  SCIPfreeBlockMemoryArray(scip, &vardistribution[b], DECdecompGetNSubscipvars(decomp)[b]); /*lint !e866 */
3612  }
3613 
3614  SCIPfreeBlockMemoryArray(scip, &mastervardistribution, nvars);
3615 
3616  SCIPfreeBlockMemoryArray(scip, &nvardistribution, nblocks);
3617  SCIPfreeBlockMemoryArray(scip, &vardistribution, nblocks);
3618 
3619  return SCIP_OKAY;
3620 }
3621 
3624  DEC_DECOMP* decomp
3625  )
3626 {
3627  int b;
3628  int nconss = 0;
3629  assert(decomp != NULL);
3630 
3631  for( b = 0; b < DECdecompGetNBlocks(decomp); ++b )
3632  nconss += DECdecompGetNSubscipconss(decomp)[b];
3633 
3634  nconss += DECdecompGetNLinkingconss(decomp);
3635  return nconss;
3636 }
3637 
3639 static
3640 SCIP_RETCODE computeConssNzeros(
3641  SCIP* scip,
3642  DEC_DECOMP* decomp,
3643  SCIP_CONS* cons,
3644  int* nzeros,
3645  int* nintzeros,
3646  int* nbzeros,
3647  int* nintbzeros
3648 )
3649 {
3650  int v;
3651  int ncurvars;
3652  SCIP_VAR** curvars = NULL;
3653  SCIP_Real* curvals = NULL;
3654 
3655  assert(scip != NULL);
3656  assert(decomp != NULL);
3657  assert(cons != NULL);
3658  assert(nzeros != NULL);
3659  assert(nintzeros != NULL);
3660  assert(nbzeros != NULL);
3661  assert(nintbzeros != NULL);
3662 
3663  ncurvars = GCGconsGetNVars(scip, cons);
3664  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
3665  SCIP_CALL( SCIPallocBufferArray(scip, &curvals, ncurvars) );
3666 
3667  SCIP_CALL( GCGconsGetVars(scip, cons, curvars, ncurvars) );
3668  SCIP_CALL( GCGconsGetVals(scip, cons, curvals, ncurvars) );
3669 
3670  for( v = 0; v < ncurvars; ++v )
3671  {
3672  int block;
3673  SCIP_VAR* curvar;
3674  if( SCIPisZero(scip, curvals[v]) )
3675  continue;
3676 
3677  curvar = SCIPvarGetProbvar(curvars[v]);
3678 
3679  if( SCIPvarGetStatus(curvar) == SCIP_VARSTATUS_FIXED )
3680  continue;
3681 
3682  block = ((int) (size_t) SCIPhashmapGetImage(DECdecompGetVartoblock(decomp), (curvar))) - 1; /*lint !e507 */
3683  assert(block >= 0);
3684 
3685  if( block > DECdecompGetNBlocks(decomp) )
3686  {
3687  if( SCIPvarGetType(curvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(curvar) == SCIP_VARTYPE_INTEGER )
3688  *nintbzeros += 1;
3689 
3690  *nbzeros += 1;
3691  }
3692  else
3693  {
3694  if( SCIPvarGetType(curvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(curvar) == SCIP_VARTYPE_INTEGER )
3695  *nintzeros += 1;
3696 
3697  *nzeros += 1;
3698  }
3699  }
3700 
3701  SCIPfreeBufferArrayNull(scip, &curvals);
3702  SCIPfreeBufferArrayNull(scip, &curvars);
3703 
3704  return SCIP_OKAY;
3705 }
3706 
3708 static
3709 SCIP_RETCODE computeNonzeros(
3710  SCIP* scip,
3711  DEC_DECOMP* decomp,
3712  int* mnzeros,
3713  int* mintnzeros,
3714  int* lnzeros,
3715  int* lintnzeros,
3716  int* nonzeros,
3717  int* intnzeros
3718  )
3719 {
3720  int c;
3721  int b;
3722 
3723  assert(scip != NULL);
3724  assert(decomp != NULL);
3725  assert(mnzeros != NULL);
3726  assert(mintnzeros != NULL);
3727  assert(lnzeros != NULL);
3728  assert(lintnzeros != NULL);
3729  assert(nonzeros != NULL);
3730  assert(intnzeros != NULL);
3731 
3732  for( b = 0; b < DECdecompGetNBlocks(decomp); ++b )
3733  {
3734  SCIP_CONS** subscipconss = DECdecompGetSubscipconss(decomp)[b];
3735  int nsubscipconss = DECdecompGetNSubscipconss(decomp)[b];
3736  for( c = 0; c < nsubscipconss; ++c )
3737  {
3738  SCIP_CALL( computeConssNzeros(scip, decomp, subscipconss[c], &(nonzeros[b]), &(intnzeros[b]), lnzeros, lintnzeros ) );
3739  }
3740  }
3741 
3742  for( c = 0; c < DECdecompGetNLinkingconss(decomp); ++c )
3743  {
3744  SCIP_CALL( computeConssNzeros(scip, decomp, DECdecompGetLinkingconss(decomp)[c], mnzeros, mintnzeros, lnzeros, lintnzeros ) );
3745  }
3746 
3747  return SCIP_OKAY;
3748 }
3749 
3752  SCIP* scip,
3753  FILE* file
3754  )
3755 {
3756  DEC_DECOMP* decomp;
3757  DEC_SCORES scores;
3758  SCIP_VAR** vars;
3759  SCIP_CONS** conss;
3760 
3761  int nvars;
3762  int nconss;
3763 
3764  int* nallvars;
3765  int* nbinvars;
3766  int* nintvars;
3767  int* nimplvars;
3768  int* ncontvars;
3769 
3770  int nblocks;
3771  int nblocksrelevant;
3772  int nlinkvars;
3773  int nlinkbinvar;
3774  int nlinkintvars;
3775  int nlinkimplvars;
3776  int nlinkcontvars;
3777  int b;
3778 
3779  int* varprobdensity;
3780  int* varmasterdensity;
3781  int* consprobsensity;
3782  int* consmasterdensity;
3783 
3784  DEC_STATISTIC* blockvardensities;
3785  DEC_STATISTIC* blockconsdensities;
3786  DEC_STATISTIC mastervardensity;
3787 
3788  int mnzeros;
3789  int mintnzeros;
3790  int lnzeros;
3791  int lintnzeros;
3792 
3793  int* nonzeros;
3794  int* intnzeros;
3795 
3796  assert(scip != NULL);
3797 
3798  decomp = DECgetBestDecomp(scip);
3799 
3800  if( decomp == NULL )
3801  {
3802  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "No decomposition available. Cannot output decomposition statistics.\n");
3803  return SCIP_OKAY;
3804  }
3805  assert(decomp != NULL);
3806  nblocks = DECdecompGetNBlocks(decomp);
3807 
3808  nvars = SCIPgetNVars(scip);
3809  nconss = DECdecompGetNConss(decomp);
3810 
3811  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nallvars, nblocks) );
3812  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nbinvars, nblocks) );
3813  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nintvars, nblocks) );
3814  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nimplvars, nblocks) );
3815  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ncontvars, nblocks) );
3816 
3817  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &blockvardensities, nblocks) );
3818  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &blockconsdensities, nblocks) );
3819 
3820  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &varprobdensity, nvars) );
3821  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &varmasterdensity, nvars) );
3822  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, nvars) );
3823  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conss, nconss) );
3824  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consprobsensity, nconss) );
3825  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consmasterdensity, nconss) );
3826 
3827  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nonzeros, nblocks) );
3828  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &intnzeros, nblocks) );
3829 
3830  BMSclearMemoryArray(nonzeros, nblocks);
3831  BMSclearMemoryArray(intnzeros, nblocks);
3832 
3833  mnzeros = 0;
3834  mintnzeros = 0;
3835  lnzeros = 0;
3836  lintnzeros = 0;
3837 
3838  SCIP_CALL( DECevaluateDecomposition(scip, decomp, &scores) );
3839 
3840  DECgetSubproblemVarsData(scip, decomp, nallvars, nbinvars, nintvars, nimplvars, ncontvars, nblocks);
3841  DECgetLinkingVarsData(scip, decomp, &nlinkvars, &nlinkbinvar, &nlinkintvars, &nlinkimplvars, &nlinkcontvars);
3842  SCIP_CALL( DECgetDensityData(scip, decomp, vars, nvars, conss, nconss, varprobdensity, varmasterdensity, consprobsensity, consmasterdensity) );
3843 
3844  SCIP_CALL( computeVarDensities(scip, decomp, varprobdensity, varmasterdensity, vars, nvars, blockvardensities, &mastervardensity, nblocks) );
3845  SCIP_CALL( computeNonzeros(scip, decomp, &mnzeros, &mintnzeros, &lnzeros, &lintnzeros, nonzeros, intnzeros) );
3846 
3847  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Decomp statistics :\n");
3848  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " type : %10s\n", DECgetStrType(DECdecompGetType(decomp)));
3849  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " detector : %10s\n", decomp->detectorchainstring == NULL? "provided": decomp->detectorchainstring);
3850  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " blocks : %10d\n", DECdecompGetNBlocks(decomp));
3851 
3852  nblocksrelevant = nblocks;
3853  if( SCIPgetStage(GCGgetMasterprob(scip)) >= SCIP_STAGE_PRESOLVED )
3854  {
3855  for( b = 0; b < nblocks; ++b )
3856  {
3857  if( GCGgetNIdenticalBlocks(scip, b) == 0 )
3858  nblocksrelevant -= 1;
3859  }
3860  }
3861  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " aggr. blocks : %10d\n", nblocksrelevant);
3862 
3863  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");
3864  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,
3865  nlinkbinvar, nlinkintvars, nlinkimplvars, nlinkcontvars, DECdecompGetNLinkingconss(decomp),
3866  mnzeros, mintnzeros, lnzeros, lintnzeros, mastervardensity.min, mastervardensity.max, mastervardensity.median, mastervardensity.mean);
3867 
3868  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Pricing statistics : nvars nbinvars nintvars nimplvars ncontvars nconss nonzeros intnzeros min(dens) max(dens) medi(dens) mean(dens) identical\n");
3869  for( b = 0; b < nblocks; ++b )
3870  {
3871  int identical = 0;
3872  SCIP_Bool relevant = TRUE;
3873 
3874  if( SCIPgetStage(GCGgetMasterprob(scip)) >= SCIP_STAGE_PRESOLVED )
3875  {
3876  relevant = GCGisPricingprobRelevant(scip, b);
3877  identical = GCGgetNIdenticalBlocks(scip, b);
3878  }
3879  if( relevant )
3880  {
3881  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],
3882  DECdecompGetNSubscipconss(decomp)[b], nonzeros[b], intnzeros[b], blockvardensities[b].min, blockvardensities[b].max, blockvardensities[b].median, blockvardensities[b].mean, identical);
3883  }
3884  }
3885 
3886  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Decomp Scores :\n");
3887  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " border area : %10.3f\n", scores.borderscore);
3888  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " avg. density : %10.3f\n", scores.densityscore);
3889  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " linking score : %10.3f\n", scores.linkingscore);
3890 
3891  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
3892  SCIPfreeBlockMemoryArray(scip, &conss, nconss);
3893 
3894 
3895  SCIPfreeBlockMemoryArray(scip, &intnzeros, nblocks);
3896  SCIPfreeBlockMemoryArray(scip, &nonzeros, nblocks);
3897 
3898  SCIPfreeBlockMemoryArray(scip, &varprobdensity, nvars);
3899  SCIPfreeBlockMemoryArray(scip, &varmasterdensity, nvars);
3900  SCIPfreeBlockMemoryArray(scip, &consprobsensity, nconss);
3901  SCIPfreeBlockMemoryArray(scip, &consmasterdensity, nconss);
3902 
3903  SCIPfreeBlockMemoryArray(scip, &blockvardensities, nblocks);
3904  SCIPfreeBlockMemoryArray(scip, &blockconsdensities, nblocks);
3905 
3906  SCIPfreeBlockMemoryArray(scip, &nallvars, nblocks);
3907  SCIPfreeBlockMemoryArray(scip, &nbinvars, nblocks);
3908  SCIPfreeBlockMemoryArray(scip, &nintvars, nblocks);
3909  SCIPfreeBlockMemoryArray(scip, &nimplvars, nblocks);
3910  SCIPfreeBlockMemoryArray(scip, &ncontvars, nblocks);
3911 
3912  DECdecompFree(scip, &decomp);
3913 
3914  return SCIP_OKAY;
3915 }
3916 
3919  SCIP* scip,
3920  DEC_DECOMP* decomp1,
3921  DEC_DECOMP* decomp2
3922 )
3923 {
3924  SCIP_HASHMAP* constoblock1;
3925  SCIP_HASHMAP* constoblock2;
3926 
3927  SCIP_HASHMAP* vartoblock1;
3928  SCIP_HASHMAP* vartoblock2;
3929 
3930  SCIP_CONS** conss;
3931  int nconss;
3932 
3933  SCIP_VAR** vars;
3934  int nvars;
3935  int i;
3936 
3937  assert(scip != NULL);
3938  assert(decomp1 != NULL);
3939  assert(decomp2 != NULL);
3940 
3941  if( DECdecompGetNBlocks(decomp1) != DECdecompGetNBlocks(decomp2) )
3942  {
3943  return FALSE;
3944  }
3945 
3946  conss = SCIPgetConss(scip);
3947  nconss = SCIPgetNConss(scip);
3948 
3949  vars = SCIPgetVars(scip);
3950  nvars = SCIPgetNVars(scip);
3951 
3952  constoblock1 = DECdecompGetConstoblock(decomp1);
3953  constoblock2 = DECdecompGetConstoblock(decomp2);
3954  assert(constoblock1 != NULL);
3955  assert(constoblock2 != NULL);
3956 
3957  vartoblock1 = DECdecompGetVartoblock(decomp1);
3958  vartoblock2 = DECdecompGetVartoblock(decomp2);
3959  assert(vartoblock1 != NULL);
3960  assert(vartoblock2 != NULL);
3961 
3962  vartoblock1 = DECdecompGetVartoblock(decomp1);
3963  vartoblock2 = DECdecompGetVartoblock(decomp2);
3964 
3965  for( i = 0; i < nconss; ++i )
3966  {
3967  if( SCIPhashmapGetImage(constoblock1, conss[i]) != SCIPhashmapGetImage(constoblock2, conss[i]) )
3968  return FALSE;
3969  }
3970 
3971  for( i = 0; i < nvars; ++i )
3972  {
3973  if( SCIPhashmapGetImage(vartoblock1, vars[i]) != SCIPhashmapGetImage(vartoblock2, vars[i]) )
3974  return FALSE;
3975  }
3976 
3977  return TRUE;
3978 }
3979 
3984  SCIP* scip,
3985  DEC_DECOMP** decs,
3986  int ndecs
3987 )
3988 {
3989  int i;
3990  int j;
3991  int nunique;
3992  assert(scip != NULL);
3993  assert(decs != NULL);
3994  assert(ndecs > 0);
3995 
3996  nunique = ndecs;
3997  for( i = 0; i < nunique; ++i )
3998  {
3999  /*lint -e{850} j is modified in the body of the for loop */
4000  for( j = i+1; j < nunique; ++j )
4001  {
4002  DEC_DECOMP* tmp;
4003  if( DECdecompositionsAreEqual(scip, decs[i], decs[j]) )
4004  {
4005  tmp = decs[nunique-1];
4006  decs[nunique-1] = decs[j];
4007  decs[j] = tmp;
4008  --nunique;
4009  --j;
4010  }
4011  }
4012  }
4013  return nunique;
4014 }
4015 
4027  SCIP* scip,
4028  DEC_DECOMP* decomp,
4029  SCIP_CONS* cons,
4030  int* block
4031 )
4032 {
4033  SCIP_VAR** curvars = NULL;
4034  int ncurvars = 0;
4035  SCIP_Bool success = FALSE;
4036  int i;
4037  int nblocks ;
4038 
4039  int nmastervars = 0;
4040  int npricingvars = 0;
4041 
4042  SCIP_HASHMAP* vartoblock;
4043  assert(scip != NULL);
4044  assert(decomp != NULL);
4045  assert(cons != NULL);
4046  assert(block != NULL);
4047 
4048  *block = -2;
4049 
4050  SCIP_CALL( SCIPgetConsNVars(scip, cons, &ncurvars, &success) );
4051  assert(success);
4052 
4053  if( ncurvars == 0 )
4054  return SCIP_OKAY;
4055 
4056  vartoblock= DECdecompGetVartoblock(decomp);
4057  assert(vartoblock != NULL);
4058 
4059  nblocks = DECdecompGetNBlocks(decomp);
4060 
4061  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
4062  SCIP_CALL( SCIPgetConsVars(scip, cons, curvars, ncurvars, &success) );
4063  assert(success);
4064 
4065  for( i = 0; i < ncurvars && *block != nblocks; ++i )
4066  {
4067  SCIP_VAR* var;
4068  int varblock;
4069 
4070  var = SCIPvarGetProbvar(curvars[i]);
4071 
4072  if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
4073  continue;
4074 
4075  assert(SCIPhashmapExists(vartoblock, var));
4076  varblock = ((int) (size_t) SCIPhashmapGetImage(vartoblock, var))-1; /*lint !e507 */
4077 
4078  /* if variable is linking skip*/
4079  if( varblock == nblocks+1 )
4080  {
4081  continue;
4082  }
4083  else if( varblock == nblocks )
4084  {
4085  ++nmastervars;
4086  continue;
4087  }
4088  else if( *block != varblock )
4089  {
4090  ++npricingvars;
4091  if( *block < 0 )
4092  *block = varblock;
4093  else
4094  {
4095  assert(*block != nblocks);
4096  *block = nblocks;
4097  break;
4098  }
4099  }
4100  }
4101 
4102  SCIPfreeBufferArrayNull(scip, &curvars);
4103 
4104  if( ncurvars > 0 && *block == -2 )
4105  *block = nblocks;
4106 
4107  if( npricingvars == 0 && nmastervars > 0 )
4108  *block = -1;
4109 
4110 
4111 
4112  return SCIP_OKAY;
4113 }
4114 
4117  SCIP* scip,
4118  DEC_DECOMP* decomp,
4119  int consindex,
4120  int block
4121  )
4122 {
4123  SCIP_CONS* linkcons;
4124  int oldsize;
4125  int newsize;
4126 
4127  assert(scip != NULL);
4128  assert(decomp != NULL);
4129  assert(consindex >= 0 && consindex < decomp->nlinkingconss);
4130  assert(block >= 0 && block < decomp->nblocks);
4131 
4132  linkcons = decomp->linkingconss[consindex];
4133 
4134  decomp->linkingconss[consindex] = decomp->linkingconss[decomp->nlinkingconss-1];
4135  decomp->nlinkingconss -= 1;
4136 
4137  oldsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[block]);
4138  newsize = SCIPcalcMemGrowSize(scip, decomp->nsubscipconss[block]+1);
4139  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->subscipconss[block], oldsize, newsize) ); /*lint !e866 */
4140  decomp->subscipconss[block][decomp->nsubscipconss[block]] = linkcons;
4141  decomp->nsubscipconss[block] += 1;
4142 
4143  SCIP_CALL( SCIPhashmapSetImage(decomp->constoblock, linkcons, (void*) (size_t)((size_t)block+1)) );
4144  SCIP_CALL( assignConsvarsToBlock(scip, decomp, linkcons, block) );
4145 
4146  return SCIP_OKAY;
4147 }
4148 
4149 
4152  SCIP* scip,
4153  DEC_DECOMP* decomp,
4154  int* transferred
4155  )
4156 {
4157  int c;
4158  int linkingconssize;
4159  assert(scip != NULL);
4160  assert(decomp != NULL);
4161  assert(transferred != NULL);
4162  linkingconssize = decomp->nlinkingconss;
4163  *transferred = 0;
4164 
4165  /*lint -e{850} c is modified in the body of the for loop */
4166  for( c = 0; c < decomp->nlinkingconss; ++c )
4167  {
4168  int block;
4169  SCIP_CALL( DECdetermineConsBlock(scip, decomp, decomp->linkingconss[c], &block) );
4170 
4171  if( block == DECdecompGetNBlocks(decomp) || block < 0 )
4172  {
4173  continue;
4174  }
4175 
4176  SCIP_CALL( DECdecompMoveLinkingConsToPricing(scip, decomp, c, block) );
4177  --c;
4178  *transferred += 1;
4179  }
4180 
4181  if( *transferred > 0 )
4182  {
4183  if( decomp->nlinkingconss > 0 )
4184  {
4185  int oldsize = SCIPcalcMemGrowSize(scip, linkingconssize);
4186  int newsize = SCIPcalcMemGrowSize(scip, decomp->nlinkingconss);
4187  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &decomp->linkingconss, oldsize, newsize) );
4188  }
4189  else
4190  {
4191  SCIPfreeBlockMemoryArrayNull(scip, &decomp->linkingconss, SCIPcalcMemGrowSize(scip, linkingconssize));
4192  }
4193  }
4194 
4195  return SCIP_OKAY;
4196 }
4197 
4200  SCIP* scip,
4201  DEC_DECOMP* decomp,
4202  DEC_DECOMP** newdecomp,
4203  int* transferred
4204  )
4205 {
4206  int c;
4207 
4208  assert(scip != NULL);
4209  assert(decomp != NULL);
4210  assert(newdecomp != NULL);
4211  assert(transferred != NULL);
4212 
4213  *newdecomp = NULL;
4214  *transferred = 0;
4215 
4216  for( c = 0; c < decomp->nlinkingconss; ++c )
4217  {
4218  int block;
4219  int i;
4220  int nconss;
4221  SCIP_HASHMAP* constoblock;
4222  SCIP_CALL( DECdetermineConsBlock(scip, decomp, decomp->linkingconss[c], &block) );
4223 
4224  if( block >= 0 )
4225  {
4226  continue;
4227  }
4228  SCIPdebugMessage("Cons <%s> in new pricing problem\n", SCIPconsGetName(decomp->linkingconss[c]));
4229  nconss = SCIPgetNConss(scip);
4230  SCIP_CALL( DECdecompCreate(scip, newdecomp) );
4231  SCIP_CALL( SCIPhashmapCreate(&constoblock, SCIPblkmem(scip), SCIPgetNConss(scip)) );
4232 
4233  for( i = 0; i < nconss; ++i )
4234  {
4235  int consblock;
4236  SCIP_CONS* cons = SCIPgetConss(scip)[i];
4237  assert(SCIPhashmapExists(decomp->constoblock, cons));
4238  consblock = (int) (size_t) SCIPhashmapGetImage(decomp->constoblock, cons); /*lint !e507 */
4239  SCIPdebugMessage("Cons <%s> %d -> %d\n", SCIPconsGetName(cons), consblock, consblock+1);
4240 
4241  SCIP_CALL( SCIPhashmapSetImage(constoblock, cons, (void*) (size_t) (consblock+1)) );
4242  }
4243  SCIP_CALL( SCIPhashmapSetImage(constoblock, decomp->linkingconss[c], (void*) (size_t) (1)) );
4244  SCIPdebugMessage("Cons <%s> -> %d\n", SCIPconsGetName(decomp->linkingconss[c]), 1);
4245 
4246  SCIP_CALL( DECfilloutDecompFromConstoblock(scip, *newdecomp, constoblock, decomp->nblocks+1, FALSE) );
4247  *transferred += 1;
4248  break;
4249  }
4250 
4251  return SCIP_OKAY;
4252 }
4253 
4256  SCIP* scip,
4257  DEC_DECOMP* decomp,
4258  DEC_DECOMP** newdecomp
4259  )
4260 {
4261  int transferredexisting = 0;
4262  int transferrednew = 0;
4263  DEC_DECOMP* origdecomp = decomp;
4264  DEC_DECOMP* tempdecomp = NULL;
4265 
4266  assert(scip != NULL);
4267  assert(decomp != NULL);
4268  assert(newdecomp != NULL);
4269 
4270  if( DECdecompGetNBlocks(decomp) == 1 )
4271  {
4272  *newdecomp = NULL;
4273  return SCIP_OKAY;
4274  }
4275  *newdecomp = decomp;
4276 
4277  do
4278  {
4279  SCIP_CALL( DECtryAssignMasterconssToExistingPricing(scip, *newdecomp, &transferredexisting) );
4280  SCIPdebugMessage("%d conss transferred to existing pricing\n", transferredexisting);
4281  SCIP_CALL( DECtryAssignMasterconssToNewPricing(scip, *newdecomp, &tempdecomp, &transferrednew) );
4282  SCIPdebugMessage("%d conss transferred to new pricing\n", transferrednew);
4283  if( transferrednew > 0 )
4284  {
4285  if( *newdecomp != origdecomp )
4286  {
4287  SCIP_CALL( DECdecompFree(scip, newdecomp) );
4288  }
4289  *newdecomp = tempdecomp;
4290  }
4291  } while( transferredexisting > 0 || transferrednew > 0 );
4292 
4293  if( *newdecomp == origdecomp )
4294  {
4295  *newdecomp = NULL;
4296  }
4297 
4298  return SCIP_OKAY;
4299 }
4300 
4302 SCIP_RETCODE DECpermuteDecomp(
4303  SCIP* scip,
4304  DEC_DECOMP* decomp,
4305  SCIP_RANDNUMGEN* randnumgen
4306  )
4307 {
4308  int b;
4309  int npricingprobs;
4310  assert(scip != NULL);
4311  assert(decomp != NULL);
4312 
4313  npricingprobs = DECdecompGetNBlocks(decomp);
4314 
4315  /* Permute individual variables and constraints of pricing problems */
4316  for( b = 0; b < npricingprobs; ++b )
4317  {
4318  SCIP_CONS*** subscipconss;
4319  SCIP_VAR*** subscipvars;
4320  int *nsubscipconss = DECdecompGetNSubscipconss(decomp);
4321  int *nsubscipvars = DECdecompGetNSubscipvars(decomp);
4322  subscipconss = DECdecompGetSubscipconss(decomp);
4323 
4324  SCIPrandomPermuteArray(randnumgen, (void**)(subscipconss[b]), 0, nsubscipconss[b]);
4325 
4326  subscipvars = DECdecompGetSubscipvars(decomp);
4327  SCIPrandomPermuteArray(randnumgen, (void**)(subscipvars[b]), 0, nsubscipvars[b]);
4328  }
4329 
4330  if( DECdecompGetNLinkingconss(decomp) > 0 )
4331  {
4332  SCIP_CONS** linkingconss = DECdecompGetLinkingconss(decomp);
4333  SCIPrandomPermuteArray(randnumgen, (void**)linkingconss, 0, DECdecompGetNLinkingconss(decomp));
4334  }
4335 
4336  if( DECdecompGetNLinkingvars(decomp) > 0 )
4337  {
4338  SCIP_VAR** linkingvars = DECdecompGetLinkingvars(decomp);;
4339  SCIPrandomPermuteArray(randnumgen, (void**)linkingvars, 0, DECdecompGetNLinkingvars(decomp));
4340  }
4341 
4342  SCIP_CALL( DECdecompCheckConsistency(scip, decomp) );
4343  return SCIP_OKAY;
4344 }
SCIP_CONS *** DECdecompGetSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:903
SCIP_Bool DECdecompositionsAreEqual(SCIP *scip, DEC_DECOMP *decomp1, DEC_DECOMP *decomp2)
Definition: decomp.c:3918
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3918
int DECdecompGetNTotalStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1167
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:3485
DEC_DECOMP * DECgetBestDecomp(SCIP *scip)
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:3090
struct DEC_Detector DEC_DETECTOR
Definition: type_detector.h:46
void DECdecompSetDetectorPctConssToBorder(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssToBorder)
Definition: decomp.c:1739
static void incVarsData(SCIP_VAR *var, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars, int nproblems, int i)
Definition: decomp.c:2771
int * DECdecompGetNStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1157
const char * DECgetStrType(DEC_DECTYPE type)
Definition: decomp.c:458
char * DECdecompGetDetectorChainString(SCIP *scip, DEC_DECOMP *decomp)
Definition: decomp.c:1693
SCIP_RETCODE DECdecompSetLinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR **linkingvars, int nlinkingvars, int nfixedlinkingvars, int nmastervars)
Definition: decomp.c:984
SCIP_RETCODE DECdecompSetStairlinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***stairlinkingvars, int *nstairlinkingvars)
Definition: decomp.c:1078
GCG interface methods.
SCIP_RETCODE DECdecompMoveLinkingConsToPricing(SCIP *scip, DEC_DECOMP *decomp, int consindex, int block)
Definition: decomp.c:4116
SCIP_Real * DECdecompGetDetectorPctVarsToBorder(DEC_DECOMP *decomp)
Definition: decomp.c:1731
void DECdecompSetVarindex(DEC_DECOMP *decomp, SCIP_HASHMAP *varindex)
Definition: decomp.c:1228
void DECdecompSetDetectorPctVarsToBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsToBlock)
Definition: decomp.c:1774
int DECdecompGetDetectorChainSize(DEC_DECOMP *decomp)
Definition: decomp.c:1609
SCIP_Real * DECdecompGetDetectorClockTimes(DEC_DECOMP *decomp)
Definition: decomp.c:1670
SCIP_Real * DECdecompGetDetectorPctConssFromOpen(DEC_DECOMP *decomp)
Definition: decomp.c:1911
SCIP_HASHMAP * DECdecompGetVartoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1196
int DECdecompGetNMastervars(DEC_DECOMP *decomp)
Definition: decomp.c:1066
SCIP_RETCODE DECcreatePolishedDecomp(SCIP *scip, DEC_DECOMP *decomp, DEC_DECOMP **newdecomp)
Definition: decomp.c:4255
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:124
SCIP_Real * DECdecompGetDetectorPctConssToBlock(DEC_DECOMP *decomp)
Definition: decomp.c:1837
SCIP_RETCODE GCGprintDecompStatistics(SCIP *scip, FILE *file)
Definition: decomp.c:3751
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:2461
SCIP_RETCODE DECdetermineConsBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS *cons, int *block)
Definition: decomp.c:4026
void DECgetSubproblemVarsData(SCIP *scip, DEC_DECOMP *decomp, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars, int nproblems)
Definition: decomp.c:2810
SCIP_RETCODE DECtryAssignMasterconssToNewPricing(SCIP *scip, DEC_DECOMP *decomp, DEC_DECOMP **newdecomp, int *transferred)
Definition: decomp.c:4199
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
SCIP_Real DECdecompGetMaxwhiteScore(DEC_DECOMP *decomp)
Definition: decomp.c:696
SCIP_Real * DECdecompGetDetectorPctVarsToBlock(DEC_DECOMP *decomp)
Definition: decomp.c:1801
SCIP_VAR *** DECdecompGetStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1148
int SCIPconshdlrDecompIncreaseAndGetNCallsCreateDecomp(SCIP *scip)
counts up the counter for created decompositions and returns it
int DECfilterSimilarDecompositions(SCIP *scip, DEC_DECOMP **decs, int ndecs)
Definition: decomp.c:3983
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:525
SCIP_Real min
Definition: decomp.c:57
void DECdecompSetNNewBlocks(SCIP *scip, DEC_DECOMP *decomp, int *nNewBlocks)
Definition: decomp.c:1919
int DECdecompGetNConss(DEC_DECOMP *decomp)
Definition: decomp.c:3623
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1043
void DECdecompSetNBlocks(DEC_DECOMP *decomp, int nblocks)
Definition: decomp.c:728
void DECdecompSetDetectorPctConssFromOpen(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssFromOpen)
Definition: decomp.c:1882
static SCIP_Real quick_select_median(SCIP_Real arr[], int n)
Definition: decomp.c:63
int DECdecompGetNFixedLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1054
SCIP_RETCODE DECcreateDecompFromMasterconss(SCIP *scip, DEC_DECOMP **decomp, SCIP_CONS **masterconss, int nmasterconss)
Definition: decomp.c:2688
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:241
void DECdecompSetVartoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock)
Definition: decomp.c:1184
int DECdecompGetNLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:972
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:620
SCIP_RETCODE DECdecompRemoveDeletedConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2098
DEC_DECTYPE DECdecompGetType(DEC_DECOMP *decomp)
Definition: decomp.c:686
int DECdecompGetNBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:740
int DECdecompGetSeeedID(DEC_DECOMP *decomp)
Definition: decomp.c:1633
various SCIP helper methods
enum Dectype DEC_DECTYPE
Definition: type_decomp.h:55
SCIP_Real mean
Definition: decomp.c:54
DEC_DETECTOR ** DECdecompGetDetectorChain(DEC_DECOMP *decomp)
Definition: decomp.c:1599
SCIP_VAR *** DECdecompGetSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:818
SCIP_RETCODE DECtryAssignMasterconssToExistingPricing(SCIP *scip, DEC_DECOMP *decomp, int *transferred)
Definition: decomp.c:4151
void DECdecompSetDetector(DEC_DECOMP *decomp, DEC_DETECTOR *detector)
Definition: decomp.c:1578
SCIP_RETCODE DECpermuteDecomp(SCIP *scip, DEC_DECOMP *decomp, SCIP_RANDNUMGEN *randnumgen)
Definition: decomp.c:4302
GCG relaxator.
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:962
SCIP_VAR ** DECdecompGetLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1033
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
int * DECdecompGetNSubscipconss(DEC_DECOMP *decomp)
Definition: decomp.c:912
DEC_DETECTOR * DECdecompGetDetector(DEC_DECOMP *decomp)
Definition: decomp.c:1589
private methods for working with decomp structures
SCIP_RETCODE DECdecompSetDetectorChainString(SCIP *scip, DEC_DECOMP *decomp, char *detectorchainstring)
Definition: decomp.c:1679
int * DECdecompGetNNewBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:1945
SCIP_Real DECgetMaxWhiteScore(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:3243
void DECdecompSetDetectorPctConssToBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssToBlock)
Definition: decomp.c:1809
SCIP_RETCODE DECdecompCheckConsistency(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2242
SCIP_Real borderscore
Definition: pub_decomp.h:54
SCIP_Bool GCGisVarRelevant(SCIP_VAR *var)
Definition: scip_misc.c:41
SCIP_RETCODE DECdecompTransform(SCIP *scip, DEC_DECOMP *decomp)
Definition: decomp.c:1957
SCIP_RETCODE DECdecompSetType(DEC_DECOMP *decomp, DEC_DECTYPE type)
Definition: decomp.c:642
SCIP_Real median
Definition: decomp.c:55
int SCIPconshdlrDecompDecreaseAndGetNCallsCreateDecomp(SCIP *scip)
decreases the counter for created decompositions and returns it
SCIP_Real totalscore
Definition: pub_decomp.h:57
static SCIP_RETCODE assignConsvarsToBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS *cons, int block)
Definition: decomp.c:406
static int processBlockRepresentatives(int maxblock, int *blockrepresentative)
Definition: decomp.c:2426
SCIP_HASHMAP * DECdecompGetConstoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1218
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:107
SCIP_RETCODE DECdecompSetSubscipconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS ***subscipconss, int *nsubscipconss)
Definition: decomp.c:838
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:205
void DECdecompSetConsindex(DEC_DECOMP *decomp, SCIP_HASHMAP *consindex)
Definition: decomp.c:1248
static SCIP_RETCODE removeFromLinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR *var, SCIP_Bool *success)
Definition: decomp.c:351
void DECdecompSetDetectorClockTimes(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *detectorClockTimes)
Definition: decomp.c:1644
static SCIP_RETCODE computeNonzeros(SCIP *scip, DEC_DECOMP *decomp, int *mnzeros, int *mintnzeros, int *lnzeros, int *lintnzeros, int *nonzeros, int *intnzeros)
Definition: decomp.c:3709
SCIP_Real * DECdecompGetDetectorPctVarsFromOpen(DEC_DECOMP *decomp)
Definition: decomp.c:1874
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:2643
SCIP_RETCODE DECfilloutDecompFromConstoblock(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1454
SCIP_RETCODE DECdecompSetLinkingconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS **linkingconss, int nlinkingconss)
Definition: decomp.c:921
SCIP_HASHMAP * DECdecompGetConsindex(DEC_DECOMP *decomp)
Definition: decomp.c:1259
int * DECdecompGetNSubscipvars(DEC_DECOMP *decomp)
Definition: decomp.c:828
SCIP_RETCODE DECdecompSetSubscipvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***subscipvars, int *nsubscipvars)
Definition: decomp.c:750
SCIP_Real max
Definition: decomp.c:56
static void increaseLock(SCIP *scip, SCIP_Real lhs, SCIP_Real coef, SCIP_Real rhs, int *downlock, int *uplock)
Definition: decomp.c:3052
void DECdecompSetPresolved(DEC_DECOMP *decomp, SCIP_Bool presolved)
Definition: decomp.c:707
void DECdecompSetDetectorPctVarsFromOpen(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsFromOpen)
Definition: decomp.c:1846
SCIP_RETCODE DECevaluateDecomposition(SCIP *scip, DEC_DECOMP *decdecomp, DEC_SCORES *score)
Definition: decomp.c:3261
SCIP_RETCODE DECcreateBasicDecomp(SCIP *scip, DEC_DECOMP **decomp, SCIP_Bool solveorigprob)
Definition: decomp.c:2361
void DECsetMaxWhiteScore(SCIP *scip, DEC_DECOMP *decdecomp, SCIP_Real maxwhitescore)
Definition: decomp.c:3226
void DECdecompSetConstoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock)
Definition: decomp.c:1206
constraint handler for structure detection
void DECdecompSetDetectorPctVarsToBorder(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsToBorder)
Definition: decomp.c:1703
SCIP_RETCODE DECfilloutDecompFromHashmaps(SCIP *scip, DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock, SCIP_HASHMAP *constoblock, int nblocks, SCIP_Bool staircase)
Definition: decomp.c:1268
SCIP_Real * DECdecompGetDetectorPctConssToBorder(DEC_DECOMP *decomp)
Definition: decomp.c:1766
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:3640
SCIP_HASHMAP * DECdecompGetVarindex(DEC_DECOMP *decomp)
Definition: decomp.c:1239
SCIP_Bool GCGisConsGCGCons(SCIP_CONS *cons)
Definition: misc.c:796
SCIP_Real densityscore
Definition: pub_decomp.h:55
SCIP_RETCODE DECdecompAddRemainingConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2154
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966
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:2909
void DECdecompSetSeeedID(DEC_DECOMP *decomp, int seeedID)
Definition: decomp.c:1619
void DECgetLinkingVarsData(SCIP *scip, DEC_DECOMP *decomp, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: decomp.c:2859
#define ELEM_SWAP(a, b)
Definition: decomp.c:60
SCIP_Bool DECdecompGetPresolved(DEC_DECOMP *decomp)
Definition: decomp.c:718