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