Scippy

SCIP

Solving Constraint Integer Programs

dcmp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dcmp.c
17  * @ingroup OTHER_CFILES
18  * @brief internal methods for decompositions and the decomposition store
19  * @author Gregor Hendel
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include "scip/dcmp.h"
26 #include "scip/mem.h"
27 #include "scip/pub_cons.h"
28 #include "scip/pub_dcmp.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_var.h"
31 #include "scip/scip_cons.h"
32 #include "scip/scip_dcmp.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_prob.h"
35 #include "scip/scip_var.h"
36 #include "scip/scip_general.h"
37 #include "scip/scip_var.h"
39 #include "scip/scip_message.h"
40 #include "scip/struct_dcmp.h"
41 #include "scip/struct_scip.h"
42 
43 /* create and free a decomposition */
44 #define INIT_MAP_SIZE 2000
45 
46 /** creates a decomposition */
48  SCIP_DECOMP** decomp, /**< pointer to store the decomposition data structure */
49  BMS_BLKMEM* blkmem, /**< block memory */
50  int nblocks, /**< the number of blocks (without the linking block) */
51  SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
52  SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
53  )
54 {
55  int memsize;
56 
57  assert(decomp != NULL);
58  assert(blkmem != NULL);
59 
60  SCIP_ALLOC( BMSallocBlockMemory(blkmem, decomp) );
61  SCIP_CALL( SCIPhashmapCreate(&(*decomp)->var2block, blkmem, INIT_MAP_SIZE) );
62  SCIP_CALL( SCIPhashmapCreate(&(*decomp)->cons2block, blkmem, INIT_MAP_SIZE) );
63 
64  /* we allocate one extra slot for the linking block */
65  memsize = nblocks + 1;
66  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->varssize, memsize) );
67  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->consssize, memsize) );
68  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->labels, memsize) );
69 
70  (*decomp)->memsize = memsize;
71  (*decomp)->nblocks = nblocks;
72  (*decomp)->modularity = -1.0;
73  (*decomp)->idxsmallestblock = -1;
74  (*decomp)->idxlargestblock = -1;
75  (*decomp)->original = original;
76  (*decomp)->benderslabels = benderslabels;
77  (*decomp)->areascore = -1.0;
78  (*decomp)->nedges = 0;
79  (*decomp)->mindegree = 0;
80  (*decomp)->maxdegree = 0;
81  (*decomp)->ncomponents = 0;
82  (*decomp)->narticulations = 0;
83  (*decomp)->statscomplete = FALSE;
84 
85  return SCIP_OKAY;
86 }
87 
88 /** free a decomposition */
90  SCIP_DECOMP** decomp, /**< pointer to free the decomposition data structure */
91  BMS_BLKMEM* blkmem /**< block memory */
92  )
93 {
94  assert(decomp != NULL);
95  assert(blkmem != NULL);
96 
97  if( *decomp == NULL )
98  return;
99 
100  assert((*decomp)->var2block != NULL);
101  SCIPhashmapFree(&(*decomp)->var2block);
102  SCIPhashmapFree(&(*decomp)->cons2block);
103 
104  BMSfreeBlockMemoryArray(blkmem, &(*decomp)->varssize, (*decomp)->memsize);
105  BMSfreeBlockMemoryArray(blkmem, &(*decomp)->consssize, (*decomp)->memsize);
106  BMSfreeBlockMemoryArray(blkmem, &(*decomp)->labels, (*decomp)->memsize);
107 
108  BMSfreeBlockMemory(blkmem, decomp);
109 }
110 
111 /* getter and setter for variable labels */
112 
113 /** sets labels for an array of variables */
115  SCIP_DECOMP* decomp, /**< decomposition data structure */
116  SCIP_VAR** vars, /**< array of variables */
117  int* labels, /**< array of labels, one per variable */
118  int nvars /**< length of variables array */
119  )
120 {
121  int i;
122 
123  assert(decomp != NULL);
124  assert(vars != NULL);
125  assert(labels != NULL);
126 
127  /* store each label in hash map */
128  for( i = 0; i < nvars; ++i )
129  {
130  assert(labels[i] == SCIP_DECOMP_LINKVAR || labels[i] >= 0);
131 
132  SCIP_CALL( SCIPhashmapSetImageInt(decomp->var2block, (void *)vars[i], labels[i]) );
133  }
134 
135  return SCIP_OKAY;
136 }
137 
138 /** queries labels for an array of variables */
140  SCIP_DECOMP* decomp, /**< decomposition data structure */
141  SCIP_VAR** vars, /**< array of variables */
142  int* labels, /**< buffer to store labels, one per variable */
143  int nvars /**< length of variables array */
144  )
145 {
146  int i;
147 
148  assert(decomp != NULL);
149  assert(vars != NULL);
150  assert(labels != NULL);
151 
152  /* store variable labels in buffer array */
153  for( i = 0; i < nvars; ++i )
154  {
155  if( SCIPhashmapExists(decomp->var2block, (void *)vars[i]) )
156  labels[i] = SCIPhashmapGetImageInt(decomp->var2block, (void *)vars[i]);
157  else
158  labels[i] = SCIP_DECOMP_LINKVAR;
159  }
160 }
161 
162 /** sets labels for an array of constraints */
164  SCIP_DECOMP* decomp, /**< decomposition data structure */
165  SCIP_CONS** conss, /**< array of constraints */
166  int* labels, /**< array of labels, one per constraint */
167  int nconss /**< length of constraints array */
168  )
169 {
170  int i;
171 
172  assert(decomp != NULL);
173  assert(conss != NULL);
174  assert(labels != NULL);
175 
176  /* store each label in hash map */
177  for( i = 0; i < nconss; ++i )
178  {
179  assert(labels[i] == SCIP_DECOMP_LINKCONS || labels[i] >= 0);
180 
181  SCIP_CALL( SCIPhashmapSetImageInt(decomp->cons2block, (void *)conss[i], labels[i]) );
182  }
183 
184  return SCIP_OKAY;
185 }
186 
187 /** queries labels for an array of constraints */
189  SCIP_DECOMP* decomp, /**< decomposition data structure */
190  SCIP_CONS** conss, /**< array of constraints */
191  int* labels, /**< array of labels, one per constraint */
192  int nconss /**< length of constraints array */
193  )
194 {
195  int i;
196 
197  assert(decomp != NULL);
198  assert(conss != NULL);
199  assert(labels != NULL);
200 
201  /* store variable labels in buffer array */
202  for( i = 0; i < nconss; ++i )
203  {
204  if( SCIPhashmapExists(decomp->cons2block, (void *)conss[i]) )
205  {
206  labels[i] = SCIPhashmapGetImageInt(decomp->cons2block, (void *)conss[i]);
207  }
208  else
209  labels[i] = SCIP_DECOMP_LINKCONS;
210  }
211 }
212 
213 /** clears the corresponding labeling (constraints, variables, or both) of this decomposition */
215  SCIP_DECOMP* decomp, /**< decomposition data structure */
216  SCIP_Bool clearvarlabels, /**< should the variable labels be cleared? */
217  SCIP_Bool clearconslabels /**< should the constraint labels be cleared? */
218  )
219 {
220  assert(decomp != NULL);
221 
222  if( clearvarlabels )
223  {
225  }
226 
227  if( clearconslabels )
228  {
230  }
231 
232  return SCIP_OKAY;
233 }
234 
235 /** returns TRUE if decomposition is in the original space */
237  SCIP_DECOMP* decomp /**< decomposition data structure */
238  )
239 {
240  assert(decomp != NULL);
241 
242  return decomp->original;
243 }
244 
245 /** sets the parameter that indicates whether the variables must be labeled for the application of Benders'
246  * decomposition
247  */
249  SCIP_DECOMP* decomp, /**< decomposition data structure */
250  SCIP_Bool benderslabels /**< whether Benders' variable labels should be used */
251  )
252 {
253  assert(decomp != NULL);
254 
255  decomp->benderslabels = benderslabels;
256 }
257 
258 /** returns TRUE if the variables must be labeled for the application of Benders' decomposition */
260  SCIP_DECOMP* decomp /**< decomposition data structure */
261  )
262 {
263  assert(decomp != NULL);
264 
265  return decomp->benderslabels;
266 }
267 
268 /** gets number of blocks of this decomposition */
270  SCIP_DECOMP* decomp /**< decomposition data structure */
271  )
272 {
273  assert(decomp != NULL);
274 
275  return decomp->nblocks;
276 }
277 
278 /** gets area score of this decomposition */
280  SCIP_DECOMP* decomp /**< decomposition data structure */
281  )
282 {
283  assert(decomp != NULL);
284 
285  return decomp->areascore;
286 }
287 
288 /** gets modularity of this decomposition */
290  SCIP_DECOMP* decomp /**< decomposition data structure */
291  )
292 {
293  assert(decomp != NULL);
294 
295  return decomp->modularity;
296 }
297 
298 /** gets variable size for each block, sorted by increasing block label
299  *
300  * To get all variable sizes, set nlabels to SCIPdecompGetNBlocks() + 1.
301  * The first entry corresponds to the number of border variables.
302  *
303  * @note Ensure that SCIPcomputeDecompStats() has been called before.
304  * If the decomposition was read from a file, this was done automatically.
305  */
307  SCIP_DECOMP* decomp, /**< decomposition data structure */
308  int* varssize, /**< array to store variable sizes of blocks*/
309  int nlabels /**< length of variable sizes array */
310  )
311 {
312  int i;
313  int nsizes;
314 
315  assert(decomp != NULL);
316  assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR);
317  assert(varssize != NULL);
318  assert(nlabels >= 0);
319 
320  nsizes = MIN(nlabels, decomp->nblocks + 1);
321 
322  /* store variable sizes */
323  for( i = 0; i < nsizes; ++i )
324  {
325  varssize[i] = decomp->varssize[i];
326  }
327 
328  return SCIP_OKAY;
329 }
330 
331 /** gets constraint size for each block, sorted by increasing block label
332  *
333  * To get all constraint sizes, set nlabels to SCIPdecompGetNBlocks() + 1.
334  * The first entry corresponds to the number of border constraints.
335  *
336  * @note Ensure that SCIPcomputeDecompStats() has been called before.
337  * If the decomposition was read from a file, this was done automatically.
338  */
340  SCIP_DECOMP* decomp, /**< decomposition data structure */
341  int* consssize, /**< array to store constraint sizes of blocks*/
342  int nlabels /**< length of constraint sizes array */
343  )
344 {
345  int i;
346  int nsizes;
347 
348  assert(decomp != NULL);
349  assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR);
350  assert(consssize != NULL);
351  assert(nlabels >= 0);
352 
353  nsizes = MIN(nlabels, decomp->nblocks + 1);
354 
355  /* store constraint sizes */
356  for( i = 0; i < nsizes; ++i )
357  {
358  consssize[i] = decomp->consssize[i];
359  }
360 
361  return SCIP_OKAY;
362 }
363 
364 /** gets number of border variables of this decomposition
365  *
366  * @note Ensure that SCIPcomputeDecompStats() has been called before.
367  * If the decomposition was read from a file, this was done automatically.
368  */
370  SCIP_DECOMP* decomp /**< decomposition data structure */
371  )
372 {
373  assert(decomp != NULL);
374  assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR);
375 
376  return decomp->varssize[0];
377 }
378 
379 /** gets number of border constraints of this decomposition
380  *
381  * @note Ensure that SCIPcomputeDecompStats() has been called before.
382  * If the decomposition was read from a file, this was done automatically.
383  */
385  SCIP_DECOMP* decomp /**< decomposition data structure */
386  )
387 {
388  assert(decomp != NULL);
389  assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR);
390 
391  return decomp->consssize[0];
392 }
393 
394 /** gets number of edges in the block-decomposition graph of this decomposition */
396  SCIP_DECOMP* decomp /**< decomposition data structure */
397  )
398 {
399  assert(decomp != NULL);
400 
401  return decomp->nedges;
402 }
403 
404 /** gets number of connected components in the block-decomposition graph of this decomposition */
406  SCIP_DECOMP* decomp /**< decomposition data structure */
407  )
408 {
409  assert(decomp != NULL);
410 
411  return decomp->ncomponents;
412 }
413 
414 /** gets number of articulation points in the block-decomposition graph of this decomposition */
416  SCIP_DECOMP* decomp /**< decomposition data structure */
417  )
418 {
419  assert(decomp != NULL);
420 
421  return decomp->narticulations;
422 }
423 
424 /** gets the maximum degree of the block-decomposition graph of this decomposition */
426  SCIP_DECOMP* decomp /**< decomposition data structure */
427  )
428 {
429  assert(decomp != NULL);
430 
431  return decomp->maxdegree;
432 }
433 
434 /** gets the minimum degree of the block-decomposition graph of this decomposition */
436  SCIP_DECOMP* decomp /**< decomposition data structure */
437  )
438 {
439  assert(decomp != NULL);
440 
441  return decomp->mindegree;
442 }
443 
444 /** prints decomposition statistics into string buffer */
446  SCIP_DECOMP* decomp, /**< decomposition data structure */
447  char* strbuf /**< string buffer storage */
448  )
449 {
450  char* ptr;
451 
452  assert(decomp != NULL);
453  assert(strbuf != NULL);
454 
455  ptr = strbuf;
456 
457  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
458  "Decomposition with %d blocks.\n",
459  decomp->nblocks);
460  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
461  "Largest block: Block %d with %d constraints and %d variables\n",
462  decomp->nblocks == 0 ? -1 : decomp->labels[decomp->idxlargestblock],
463  decomp->nblocks == 0 ? 0 : decomp->consssize[decomp->idxlargestblock],
464  decomp->nblocks == 0 ? 0 : decomp->varssize[decomp->idxlargestblock]);
465  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
466  "Smallest block: Block %d with %d constraints and %d variables\n",
467  decomp->nblocks == 0 ? -1 : decomp->labels[decomp->idxsmallestblock],
468  decomp->nblocks == 0 ? 0 : decomp->consssize[decomp->idxsmallestblock],
469  decomp->nblocks == 0 ? 0 : decomp->varssize[decomp->idxsmallestblock]);
470  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
471  "Border has %d constraints and %d variables\n",
472  decomp->labels[0] == SCIP_DECOMP_LINKVAR ? decomp->consssize[0] : 0,
473  decomp->labels[0] == SCIP_DECOMP_LINKVAR ? decomp->varssize[0] : 0
474  );
475 
476  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
477  "Modularity: %.3f, Area Score: %.3f\n",
478  decomp->modularity, decomp->areascore);
479 
480  (void) SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
481  "Constraint Block Graph: %d edges, %d articulation points, %d connected components, %d min., %d max. degree%s\n",
482  decomp->nedges, decomp->narticulations, decomp->ncomponents, decomp->mindegree, decomp->maxdegree,
483  decomp->statscomplete ? "" :
484  "(approximately: graph construction hit size limit)");
485 
486  return strbuf;
487 }
488 
489 /** creates a decomposition storage */
491  SCIP_DECOMPSTORE** decompstore, /**< pointer to store decomposition storage */
492  BMS_BLKMEM* blkmem, /**< block memory data structure */
493  int nslots /**< maximum number of decomposition slots in storage */
494  )
495 {
496  assert(decompstore != NULL);
497  assert(blkmem != NULL);
498  assert(nslots > 0);
499 
500  SCIP_ALLOC( BMSallocBlockMemory(blkmem, decompstore) );
501 
502  (*decompstore)->ndecomps = 0;
503  (*decompstore)->norigdecomps = 0;
504  (*decompstore)->decompssize = nslots;
505 
506  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decompstore)->decomps, nslots) );
507  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decompstore)->origdecomps, nslots) );
508 
509  return SCIP_OKAY;
510 }
511 
512 /** frees array of decompositions */
513 static
515  BMS_BLKMEM* blkmem, /**< block memory data structure */
516  SCIP_DECOMP** decomps, /**< decomposition array */
517  int* ndecomps /**< pointer for initial number of decompositions, will be set to 0 */
518  )
519 {
520  int d;
521 
522  assert(decomps != NULL);
523  assert(ndecomps != NULL);
524 
525  /* delete all remaining decompositions from this store */
526  for( d = 0; d < *ndecomps; ++d )
527  SCIPdecompFree(&decomps[d], blkmem);
528 
529  *ndecomps = 0;
530 }
531 
532 /** frees all decompositions in transformed space */
534  SCIP* scip /**< SCIP data structure */
535  )
536 {
537  SCIP_DECOMPSTORE* decompstore = scip->decompstore;
538 
539  assert(decompstore != NULL);
540 
541  freeDecompositions(SCIPblkmem(scip), decompstore->decomps, &decompstore->ndecomps);
542 }
543 
544 /** frees a decomposition storage */
546  SCIP_DECOMPSTORE** decompstore, /**< pointer to store decomposition storage */
547  BMS_BLKMEM* blkmem /**< block memory data structure */
548  )
549 {
550  assert(decompstore != NULL);
551 
552  if( *decompstore == NULL )
553  return;
554 
555  freeDecompositions(blkmem, (*decompstore)->origdecomps, &(*decompstore)->norigdecomps);
556  freeDecompositions(blkmem, (*decompstore)->decomps, &(*decompstore)->ndecomps);
557 
558  BMSfreeBlockMemoryArray(blkmem, &(*decompstore)->decomps, (*decompstore)->decompssize);
559  BMSfreeBlockMemoryArray(blkmem, &(*decompstore)->origdecomps, (*decompstore)->decompssize);
560 
561  BMSfreeBlockMemory(blkmem, decompstore);
562 }
563 
564 /** adds decomposition to storage */
566  SCIP_DECOMPSTORE* decompstore, /**< decomposition storage */
567  SCIP_DECOMP* decomp /**< decomposition to add */
568  )
569 {
570  SCIP_DECOMP** decomps;
571  int* ndecompsptr;
572 
573  assert(decompstore != NULL);
574  assert(decomp != NULL);
575 
576  /* distinguish between storage for original or transformed decompositions */
577  if( SCIPdecompIsOriginal(decomp) )
578  {
579  decomps = decompstore->origdecomps;
580  ndecompsptr = &decompstore->norigdecomps;
581  }
582  else
583  {
584  decomps = decompstore->decomps;
585  ndecompsptr = &decompstore->ndecomps;
586  }
587 
588  /* ensure that storage capacity is not exceeded */
589  if( *ndecompsptr == decompstore->decompssize )
590  {
591  SCIPerrorMessage("Error: Decomposition storage size exceeded, maximum is %d decompositions\n", decompstore->decompssize);
592  return SCIP_ERROR;
593  }
594 
595  decomps[(*ndecompsptr)++] = decomp;
596 
597  return SCIP_OKAY;
598 }
599 
600 /** gets decompositions from storage */
602  SCIP_DECOMPSTORE* decompstore /**< decomposition storage */
603  )
604 {
605  assert(decompstore != NULL);
606 
607  return decompstore->decomps;
608 }
609 
610 /** gets number of decompositions in storage */
612  SCIP_DECOMPSTORE* decompstore /**< decomposition storage */
613  )
614 {
615  assert(decompstore != NULL);
616  return decompstore->ndecomps;
617 }
618 
619 /** gets decompositions from storage */
621  SCIP_DECOMPSTORE* decompstore /**< decomposition storage */
622  )
623 {
624  assert(decompstore != NULL);
625 
626  return decompstore->origdecomps;
627 }
628 
629 /** gets number of decompositions in storage */
631  SCIP_DECOMPSTORE* decompstore /**< decomposition storage */
632  )
633 {
634  assert(decompstore != NULL);
635  return decompstore->norigdecomps;
636 }
637 
638 /** transforms all available original decompositions into transformed space */
640  SCIP* scip /**< SCIP data structure */
641  )
642 {
643  int d;
644  int v;
645  SCIP_DECOMPSTORE* decompstore;
646  SCIP_VAR** vars;
647  SCIP_VAR** origvars;
648  SCIP_VAR** varssorted;
649  SCIP_CONS** conss;
650  int nconss;
651  int nvars;
652  int nvarsoriginal;
653  int nvarsintroduced;
654  int* varslabels;
655  SCIP_Bool original = FALSE;
656 
657  assert(scip != NULL);
658  assert(scip->decompstore != NULL);
659 
660  decompstore = scip->decompstore;
661  assert(decompstore->ndecomps == 0);
662 
663  assert(SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVED);
664 
665  nvars = SCIPgetNVars(scip);
666  vars = SCIPgetVars(scip);
667 
668  SCIP_CALL( SCIPallocBufferArray(scip, &varssorted, nvars) );
669  SCIP_CALL( SCIPallocBufferArray(scip, &origvars, nvars) );
670  SCIP_CALL( SCIPallocBufferArray(scip, &varslabels, nvars) );
671 
672  /* determine if variable has an original counterpart or not, and put it into varssorted array at the front or back */
673  nvarsoriginal = nvarsintroduced = 0;
674  for( v = 0; v < nvars; ++v )
675  {
676  SCIP_Real scalar;
677  SCIP_Real constant;
678  SCIP_VAR* origvar;
679 
680  origvar = vars[v];
681  scalar = 1.0;
682  constant = 0.0;
683  SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
684 
685  /* the variable has no original counterpart and is therefore put at the end of the array */
686  if( origvar == NULL )
687  {
688  varssorted[nvars - 1 - nvarsintroduced] = vars[v];
689  ++nvarsintroduced;
690  }
691  else
692  {
693  varssorted[nvarsoriginal] = vars[v];
694  origvars[nvarsoriginal] = origvar;
695  ++nvarsoriginal;
696  }
697 
698  assert(nvarsoriginal + nvarsintroduced <= nvars);
699  }
700 
701  conss = SCIPgetConss(scip);
702  nconss = SCIPgetNConss(scip);
703 
704  /* loop over available, original decompositions, transform and add them to the storage */
705  for( d = 0; d < decompstore->norigdecomps; ++d )
706  {
707  SCIP_DECOMP* origdecomp = decompstore->origdecomps[d];
708  SCIP_DECOMP* decomp;
709  char strbuf[SCIP_MAXSTRLEN];
710 
711  /* 1. query the decomposition labels of the original variables and set them for the transformed variables
712  * that have original counterparts
713  */
714  SCIP_CALL( SCIPcreateDecomp(scip, &decomp, SCIPdecompGetNBlocks(origdecomp), original, SCIPdecompUseBendersLabels(origdecomp)) );
715 
716  SCIPdecompGetVarsLabels(origdecomp, origvars, varslabels, nvarsoriginal);
717 
718  SCIP_CALL( SCIPdecompSetVarsLabels(decomp, varssorted, varslabels, nvarsoriginal) );
719 
720  /* 2. compute the constraint labels based on the preliminary variable labels */
721  SCIP_CALL( SCIPcomputeDecompConsLabels(scip, decomp, conss, nconss) );
722 
723  /* 3. remove the variable labels now that we have constraint labels */
724  SCIP_CALL( SCIPdecompClear(decomp, TRUE, FALSE) );
725 
726  /* 4. use the constraint labels for the final variable labeling */
727  SCIP_CALL( SCIPcomputeDecompVarsLabels(scip, decomp, conss, nconss) );
728 
729  SCIP_CALL( SCIPcomputeDecompStats(scip, decomp, TRUE) );
730 
731  SCIP_CALL( SCIPdecompstoreAdd(decompstore, decomp) );
732 
733  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Transformed Decomposition statistics %d\n%s", d, SCIPdecompPrintStats(decomp, strbuf));
734  }
735 
736  SCIPfreeBufferArray(scip, &varslabels);
737  SCIPfreeBufferArray(scip, &origvars);
738  SCIPfreeBufferArray(scip, &varssorted);
739 
740  return SCIP_OKAY;
741 }
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3297
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:630
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:188
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:444
public methods for memory management
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:601
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1125
SCIP_Real areascore
Definition: struct_dcmp.h:40
SCIP_DECOMP ** origdecomps
Definition: struct_dcmp.h:62
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_Bool original
Definition: struct_dcmp.h:53
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:335
SCIP_RETCODE SCIPtransformDecompstore(SCIP *scip)
Definition: dcmp.c:639
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition: dcmp.c:369
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPdecompGetBlockGraphMaxDegree(SCIP_DECOMP *decomp)
Definition: dcmp.c:425
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:139
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:114
public methods for problem variables
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:36
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:236
public methods for SCIP variables
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:620
SCIP_Real modularity
Definition: struct_dcmp.h:39
public methods for decompositions
public methods for managing constraints
SCIP_RETCODE SCIPdecompGetVarsSize(SCIP_DECOMP *decomp, int *varssize, int nlabels)
Definition: dcmp.c:306
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:611
#define SCIPerrorMessage
Definition: pub_message.h:55
methods for block memory pools and memory buffers
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
Definition: dcmp.c:565
static void freeDecompositions(BMS_BLKMEM *blkmem, SCIP_DECOMP **decomps, int *ndecomps)
Definition: dcmp.c:514
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
int * consssize
Definition: struct_dcmp.h:44
int SCIPdecompGetNBlockGraphComponents(SCIP_DECOMP *decomp)
Definition: dcmp.c:405
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
int ncomponents
Definition: struct_dcmp.h:51
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
#define NULL
Definition: lpi_spx1.cpp:155
int * varssize
Definition: struct_dcmp.h:43
int idxlargestblock
Definition: struct_dcmp.h:41
#define SCIP_CALL(x)
Definition: def.h:384
SCIP main data structure.
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_DECOMPSTORE * decompstore
Definition: struct_scip.h:73
public methods for constraint handler plugins and constraints
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:35
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:458
#define INIT_MAP_SIZE
Definition: dcmp.c:44
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_HASHMAP * cons2block
Definition: struct_dcmp.h:38
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:163
#define SCIP_Bool
Definition: def.h:84
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:447
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3573
data structures for a decomposition and a decomposition store
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:460
SCIP_RETCODE SCIPdecompClear(SCIP_DECOMP *decomp, SCIP_Bool clearvarlabels, SCIP_Bool clearconslabels)
Definition: dcmp.c:214
SCIP_Real SCIPdecompGetAreaScore(SCIP_DECOMP *decomp)
Definition: dcmp.c:279
int SCIPdecompGetNBlockGraphEdges(SCIP_DECOMP *decomp)
Definition: dcmp.c:395
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:47
void SCIPdecompstoreFree(SCIP_DECOMPSTORE **decompstore, BMS_BLKMEM *blkmem)
Definition: dcmp.c:545
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12773
void SCIPexitSolveDecompstore(SCIP *scip)
Definition: dcmp.c:533
int SCIPdecompGetBlockGraphMinDegree(SCIP_DECOMP *decomp)
Definition: dcmp.c:435
int idxsmallestblock
Definition: struct_dcmp.h:42
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
internal methods for decompositions and the decomposition store
general public methods
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition: dcmp.c:445
int * labels
Definition: struct_dcmp.h:45
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
SCIP_Real SCIPdecompGetModularity(SCIP_DECOMP *decomp)
Definition: dcmp.c:289
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
SCIP_Bool benderslabels
Definition: struct_dcmp.h:54
#define SCIP_Real
Definition: def.h:177
public methods for message handling
public methods for data structures
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:208
void SCIPdecompSetUseBendersLabels(SCIP_DECOMP *decomp, SCIP_Bool benderslabels)
Definition: dcmp.c:248
SCIP_DECOMP ** decomps
Definition: struct_dcmp.h:61
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition: dcmp.c:89
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:259
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:444
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition: dcmp.c:339
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
SCIP_Bool statscomplete
Definition: struct_dcmp.h:55
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
public methods for decompositions
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition: dcmp.c:384
#define SCIP_ALLOC(x)
Definition: def.h:395
int SCIPdecompGetNBlockGraphArticulations(SCIP_DECOMP *decomp)
Definition: dcmp.c:415
public methods for global and local (sub)problems
int narticulations
Definition: struct_dcmp.h:52
SCIP_RETCODE SCIPdecompstoreCreate(SCIP_DECOMPSTORE **decompstore, BMS_BLKMEM *blkmem, int nslots)
Definition: dcmp.c:490
SCIP_HASHMAP * var2block
Definition: struct_dcmp.h:37