SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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 */
522static
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
673
676
677 SCIP_CALL( SCIPallocBufferArray(scip, &varssorted, nvars) );
680
681 /* determine if variable has an original counterpart or not, and put it into varssorted array at the front or back */
683 for( v = 0; v < nvars; ++v )
684 {
685 SCIP_Real scalar;
686 SCIP_Real constant;
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];
699 }
700 else
701 {
702 varssorted[nvarsoriginal] = vars[v];
703 origvars[nvarsoriginal] = origvar;
705 }
706
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 */
724
726
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
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
746 SCIPfreeBufferArray(scip, &origvars);
747 SCIPfreeBufferArray(scip, &varssorted);
748
749 return SCIP_OKAY;
750}
void SCIPexitSolveDecompstore(SCIP *scip)
Definition dcmp.c:542
SCIP_RETCODE SCIPdecompstoreCreate(SCIP_DECOMPSTORE **decompstore, BMS_BLKMEM *blkmem, int nslots)
Definition dcmp.c:499
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition dcmp.c:639
#define INIT_MAP_SIZE
Definition dcmp.c:53
void SCIPdecompstoreFree(SCIP_DECOMPSTORE **decompstore, BMS_BLKMEM *blkmem)
Definition dcmp.c:554
static void freeDecompositions(BMS_BLKMEM *blkmem, SCIP_DECOMP **decomps, int *ndecomps)
Definition dcmp.c:523
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition dcmp.c:610
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition dcmp.c:629
SCIP_RETCODE SCIPtransformDecompstore(SCIP *scip)
Definition dcmp.c:648
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
Definition dcmp.c:574
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
Definition dcmp.c:620
internal methods for decompositions and the decomposition store
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_ALLOC(x)
Definition def.h:399
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition scip_dcmp.c:344
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition dcmp.c:123
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition dcmp.c:278
int SCIPdecompGetBlockGraphMinDegree(SCIP_DECOMP *decomp)
Definition dcmp.c:444
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition scip_dcmp.c:454
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition dcmp.c:172
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition dcmp.c:56
SCIP_RETCODE SCIPdecompGetVarsSize(SCIP_DECOMP *decomp, int *varssize, int nlabels)
Definition dcmp.c:315
int SCIPdecompGetNBlockGraphEdges(SCIP_DECOMP *decomp)
Definition dcmp.c:404
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition scip_dcmp.c:1135
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition dcmp.c:454
SCIP_RETCODE SCIPdecompClear(SCIP_DECOMP *decomp, SCIP_Bool clearvarlabels, SCIP_Bool clearconslabels)
Definition dcmp.c:223
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition dcmp.c:348
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition dcmp.c:197
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition scip_dcmp.c:217
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition dcmp.c:98
int SCIPdecompGetBlockGraphMaxDegree(SCIP_DECOMP *decomp)
Definition dcmp.c:434
void SCIPdecompSetUseBendersLabels(SCIP_DECOMP *decomp, SCIP_Bool benderslabels)
Definition dcmp.c:257
SCIP_Real SCIPdecompGetModularity(SCIP_DECOMP *decomp)
Definition dcmp.c:298
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition dcmp.c:378
SCIP_Real SCIPdecompGetAreaScore(SCIP_DECOMP *decomp)
Definition dcmp.c:288
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition dcmp.c:148
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition dcmp.c:268
int SCIPdecompGetNBlockGraphArticulations(SCIP_DECOMP *decomp)
Definition dcmp.c:424
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition dcmp.c:393
int SCIPdecompGetNBlockGraphComponents(SCIP_DECOMP *decomp)
Definition dcmp.c:414
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition dcmp.c:245
SCIP_STAGE SCIPgetStage(SCIP *scip)
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:3058
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3231
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition misc.c:3583
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition misc.c:3307
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#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:12763
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
methods for block memory pools and memory buffers
#define BMSfreeBlockMemory(mem, ptr)
Definition memory.h:467
#define BMSallocBlockMemory(mem, ptr)
Definition memory.h:453
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition memory.h:456
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition memory.h:469
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:439
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for decompositions
#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
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
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
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_PRESOLVED
Definition type_set.h:51