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