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"
47   	#include "scip/scip_datastructures.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 */
56   	SCIP_RETCODE SCIPdecompCreate(
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 */
98   	void SCIPdecompFree(
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 */
123  	SCIP_RETCODE SCIPdecompSetVarsLabels(
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 */
148  	void SCIPdecompGetVarsLabels(
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 */
172  	SCIP_RETCODE SCIPdecompSetConsLabels(
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 */
197  	void SCIPdecompGetConsLabels(
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 */
223  	SCIP_RETCODE SCIPdecompClear(
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  	   {
233  	      SCIP_CALL( SCIPhashmapRemoveAll(decomp->var2block) );
234  	   }
235  	
236  	   if( clearconslabels )
237  	   {
238  	      SCIP_CALL( SCIPhashmapRemoveAll(decomp->cons2block) );
239  	   }
240  	
241  	   return SCIP_OKAY;
242  	}
243  	
244  	/** returns TRUE if decomposition is in the original space */
245  	SCIP_Bool SCIPdecompIsOriginal(
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  	 */
257  	void SCIPdecompSetUseBendersLabels(
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 */
268  	SCIP_Bool SCIPdecompUseBendersLabels(
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 */
278  	int SCIPdecompGetNBlocks(
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 */
288  	SCIP_Real SCIPdecompGetAreaScore(
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 */
298  	SCIP_Real SCIPdecompGetModularity(
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  	 */
315  	SCIP_RETCODE SCIPdecompGetVarsSize(
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  	 */
348  	SCIP_RETCODE SCIPdecompGetConssSize(
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  	 */
378  	int SCIPdecompGetNBorderVars(
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  	 */
393  	int SCIPdecompGetNBorderConss(
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 */
404  	int SCIPdecompGetNBlockGraphEdges(
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 */
414  	int SCIPdecompGetNBlockGraphComponents(
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 */
424  	int SCIPdecompGetNBlockGraphArticulations(
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 */
434  	int SCIPdecompGetBlockGraphMaxDegree(
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 */
444  	int SCIPdecompGetBlockGraphMinDegree(
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 */
454  	char* SCIPdecompPrintStats(
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 */
499  	SCIP_RETCODE SCIPdecompstoreCreate(
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
523  	void freeDecompositions(
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 */
542  	void SCIPexitSolveDecompstore(
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 */
554  	void SCIPdecompstoreFree(
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 */
574  	SCIP_RETCODE SCIPdecompstoreAdd(
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 */
610  	SCIP_DECOMP** SCIPdecompstoreGetDecomps(
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 */
620  	int SCIPdecompstoreGetNDecomps(
621  	   SCIP_DECOMPSTORE*     decompstore         /**< decomposition storage */
622  	   )
623  	{
624  	   assert(decompstore != NULL);
625  	   return decompstore->ndecomps;
626  	}
627  	
628  	/** gets decompositions from storage */
629  	SCIP_DECOMP** SCIPdecompstoreGetOrigDecomps(
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 */
639  	int SCIPdecompstoreGetNOrigDecomps(
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 */
648  	SCIP_RETCODE SCIPtransformDecompstore(
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  	}
751