Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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