Scippy

SCIP

Solving Constraint Integer Programs

scip_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 scip_dcmp.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for working with decompositions
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/struct_dcmp.h"
35#include "scip/debug.h"
36#include "scip/dcmp.h"
37#include "scip/mem.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_var.h"
40#include "scip/scip_cons.h"
41#include "scip/scip_prob.h"
42#include "scip/scip_var.h"
43#include "scip/scip_mem.h"
44#include "scip/struct_scip.h"
45#include "scip/pub_cons.h"
46#include "scip/pub_dcmp.h"
47#include "scip/scip_dcmp.h"
48#include "scip/scip_general.h"
49#include "scip/scip_param.h"
50#include "scip/scip_var.h"
52#include "scip/scip_message.h"
53#include "scip/pub_message.h"
54
55
56#define LABEL_UNASSIGNED INT_MIN /* label constraints or variables as unassigned. Only for internal use */
57
58/** count occurrences of label in array, starting from pos */
59static
61 int* labels, /**< array of labels */
62 int pos, /**< position to start counting from */
63 int nlabels /**< the number of labels */
64 )
65{
66 int endpos = pos;
67 int currlabel;
68
69 assert(labels != NULL);
70 assert(pos < nlabels);
71
72 currlabel = labels[pos];
73
74 do
75 {
76 endpos++;
77 }
78 while( endpos < nlabels && labels[endpos] == currlabel );
79
80 return endpos - pos;
81}
82
83/** raises an error if the condition is not TRUE */
84static
86 SCIP_Bool condition /**< some condition that must hold */
87 )
88{
89 return condition ? SCIP_OKAY : SCIP_ERROR;
90}
91
92/** get variable buffer storage size for the buffer to be large enough to hold all variables */
93static
95 SCIP* scip /**< SCIP data structure */
96 )
97{
98 int norigvars;
99 int ntransvars;
100
101 norigvars = SCIPgetNOrigVars(scip);
102 ntransvars = SCIPgetNVars(scip);
103
104 return 2 * MAX(norigvars, ntransvars);
105}
106
107/** get variables and constraints of the original or transformed problem, to which the decomposition corresponds */
108static
110 SCIP* scip, /**< SCIP data structure */
111 SCIP_DECOMP* decomp, /**< decomposition data structure */
112 SCIP_VAR*** vars, /**< pointer to store original/transformed variables array, or NULL */
113 SCIP_CONS*** conss, /**< pointer to store original/transformed constraints array, or NULL */
114 int* nvars, /**< pointer to store original/transformed variables array's length, or NULL */
115 int* nconss /**< pointer to store original/transformed constraints array's length, or NULL */
116 )
117{
118 SCIP_Bool original;
119 assert(scip != NULL);
120 assert(decomp != NULL);
121
122 original = SCIPdecompIsOriginal(decomp);
123
124 if( vars )
125 *vars = original ? SCIPgetOrigVars(scip) : SCIPgetVars(scip);
126
127 if( nvars )
128 *nvars = original ? SCIPgetNOrigVars(scip) : SCIPgetNVars(scip);
129
130 if( conss )
131 *conss = original ? SCIPgetOrigConss(scip) : SCIPgetConss(scip);
132
133 if( nconss )
134 *nconss = original ? SCIPgetNOrigConss(scip) : SCIPgetNConss(scip);
135}
136
137/** query the constraints active variables and their labels */
138static
140 SCIP* scip, /**< SCIP data structure */
141 SCIP_DECOMP* decomp, /**< decomposition data structure */
142 SCIP_CONS* cons, /**< the constraint */
143 SCIP_VAR** varbuf, /**< variable buffer array */
144 int* labelbuf, /**< buffer to store labels, or NULL if not needed */
145 int bufsize, /**< size of buffer arrays */
146 int* nvars, /**< pointer to store number of variables */
147 int* requiredsize, /**< pointer to store required size */
148 SCIP_Bool* success /**< pointer to store whether variables and labels were successfully inserted */
149 )
150{
151 SCIP_Bool success2;
152
153 assert(scip != NULL);
154 assert(decomp != NULL);
155 assert(cons != NULL);
156 assert(varbuf != NULL);
157 assert(nvars != NULL);
158 assert(requiredsize != NULL);
159 assert(success != NULL);
160
161 *success = FALSE;
162 *requiredsize = 0;
163 *nvars = 0;
164 SCIP_CALL( SCIPgetConsNVars(scip, cons, nvars, &success2) );
165
166 /* the constraint does not have the corresponding callback */
167 if( ! success2 )
168 {
169 return SCIP_OKAY;
170 }
171
172 if( bufsize < *nvars )
173 {
174 *requiredsize = *nvars;
175
176 return SCIP_OKAY;
177 }
178
179 SCIP_CALL( SCIPgetConsVars(scip, cons, varbuf, bufsize, &success2) );
180 /* the constraint does not have the corresponding callback */
181 if( ! success2 )
182 {
183 return SCIP_OKAY;
184 }
185
186 if( ! SCIPdecompIsOriginal(decomp) )
187 {
188 SCIP_CALL( SCIPgetActiveVars(scip, varbuf, nvars, bufsize, requiredsize) );
189
190 if( *requiredsize > bufsize )
191 return SCIP_OKAY;
192 }
193 else
194 {
195 int v;
196 for( v = 0; v < *nvars; ++v )
197 {
198 assert(SCIPvarIsActive(varbuf[v]) || SCIPvarIsNegated(varbuf[v]));
199
200 /* some constraint handlers such as indicator may already return inactive variables */
201 if( SCIPvarIsNegated(varbuf[v]) )
202 varbuf[v] = SCIPvarGetNegatedVar(varbuf[v]);
203 }
204 }
205
206 /* get variables labels, if requested */
207 if( labelbuf != NULL )
208 {
209 SCIPdecompGetVarsLabels(decomp, varbuf, labelbuf, *nvars);
210 }
211
212 *success = TRUE;
213
214 return SCIP_OKAY;
215}
216
217/** creates a decomposition */
219 SCIP* scip, /**< SCIP data structure */
220 SCIP_DECOMP** decomp, /**< pointer to store the decomposition data structure */
221 int nblocks, /**< the number of blocks (without the linking block) */
222 SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
223 SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
224 )
225{
226 assert(scip != NULL);
227
228 SCIP_CALL( SCIPdecompCreate(decomp, SCIPblkmem(scip), nblocks, original, benderslabels) );
229
230 return SCIP_OKAY;
231}
232
233/** frees a decomposition */
235 SCIP* scip, /**< SCIP data structure */
236 SCIP_DECOMP** decomp /**< pointer to free the decomposition data structure */
237 )
238{
239 assert(scip != NULL);
240
242}
243
244/** adds decomposition to SCIP */
246 SCIP* scip, /**< SCIP data structure */
247 SCIP_DECOMP* decomp /**< decomposition to add */
248 )
249{
250 assert(scip != NULL);
251 assert(decomp != NULL);
252
253 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDecomp", FALSE, SCIPdecompIsOriginal(decomp), SCIPdecompIsOriginal(decomp),
256
257 SCIP_CALL( SCIPdecompstoreAdd(scip->decompstore, decomp) );
258
259 return SCIP_OKAY;
260}
261
262/** gets available user decompositions for either the original or transformed problem */
264 SCIP* scip, /**< SCIP data structure */
265 SCIP_DECOMP*** decomps, /**< pointer to store decompositions array */
266 int* ndecomps, /**< pointer to store number of decompositions */
267 SCIP_Bool original /**< should the decompositions for the original problem be returned? */
268 )
269{
270 assert(scip != NULL);
271
272 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDecomps", FALSE, original, original, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
273
274 if( decomps != NULL )
275 *decomps = original ? SCIPdecompstoreGetOrigDecomps(scip->decompstore) : SCIPdecompstoreGetDecomps(scip->decompstore);
276
277 if( ndecomps != NULL )
278 *ndecomps = original ? SCIPdecompstoreGetNOrigDecomps(scip->decompstore) : SCIPdecompstoreGetNDecomps(scip->decompstore);
279}
280
281/** returns TRUE if the constraint \p cons contains only linking variables in decomposition \p decomp */
283 SCIP* scip, /**< SCIP data structure */
284 SCIP_DECOMP* decomp, /**< decomposition data structure */
285 SCIP_CONS* cons, /**< the constraint */
286 SCIP_Bool* hasonlylinkvars /**< will be set to TRUE if this constraint has only linking variables */
287 )
288{
289 SCIP_VAR** consvars;
290 int nvars;
291 int i;
292 SCIP_Bool success;
293
294 assert(scip != NULL);
295 assert(cons != NULL);
296 assert(decomp != NULL);
297 assert(hasonlylinkvars != NULL);
298
299 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, &success) );
300 SCIP_CALL( ensureCondition(success) );
301
302 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
303
304 SCIP_CALL( SCIPgetConsVars(scip, cons, consvars, nvars, &success) );
305 SCIP_CALL( ensureCondition(success) );
306
307 if( ! SCIPdecompIsOriginal(decomp) )
308 {
309 int requiredsize;
310 SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nvars, nvars, &requiredsize) );
311 assert(requiredsize <= nvars);
312 }
313
314 *hasonlylinkvars = TRUE;
315 /* check if variables are all linking variables */
316 for( i = 0; i < nvars && *hasonlylinkvars; ++i )
317 {
318 int label;
319
320 SCIPdecompGetVarsLabels(decomp, &consvars[i], &label, 1);
321
322 *hasonlylinkvars = (label == SCIP_DECOMP_LINKVAR);
323 }
324
325 SCIPfreeBufferArray(scip, &consvars);
326
327 return SCIP_OKAY;
328}
329
330
331/** computes constraint labels from variable labels
332 *
333 * Existing labels for the constraints are simply overridden
334 *
335 * The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set
336 * to FALSE, the labeling assigns
337 *
338 * - label i, if only variables labeled i are present in the constraint (and optionally linking variables)
339 * - SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or
340 * if there are variables with more than one block label.
341 *
342 * If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same
343 * constraint, which is an invalid labeling for the Benders case.
344 */
346 SCIP* scip, /**< SCIP data structure */
347 SCIP_DECOMP* decomp, /**< decomposition data structure */
348 SCIP_CONS** conss, /**< array of constraints */
349 int nconss /**< number of constraints */
350 )
351{
352 SCIP_VAR** varbuffer;
353 int c;
354 int varbufsize;
355 int* varlabels;
356 int* conslabels;
357 SCIP_Bool benderserror;
358 SCIP_Bool benderslabels;
359
360 assert(decomp != NULL);
361
362 if( nconss == 0 )
363 return SCIP_OKAY;
364
365 varbufsize = getVarbufSize(scip);
366
367 SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, varbufsize) );
368 SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, varbufsize) );
369 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
370
371 benderslabels = SCIPdecompUseBendersLabels(decomp);
372 benderserror = FALSE;
373
374 /* assign label to each individual constraint */
375 for( c = 0; c < nconss && ! benderserror; ++c )
376 {
377 int nconsvars;
378 int v;
379 int nlinkingvars = 0;
380 int conslabel;
381 int requiredsize;
382
383 SCIP_Bool success;
384
385 SCIP_CALL( decompGetConsVarsAndLabels(scip, decomp, conss[c], varbuffer, varlabels,
386 varbufsize, &nconsvars, &requiredsize, &success) );
387 SCIP_CALL( ensureCondition(success) );
388
389 /* loop over variable labels to compute the constraint label */
390 conslabel = LABEL_UNASSIGNED;
391 for( v = 0; v < nconsvars; ++v )
392 {
393 int varlabel = varlabels[v];
394
395 /* count the number of linking variables, and keep track if there are two variables with different labels */
396 if( varlabel == SCIP_DECOMP_LINKVAR )
397 ++nlinkingvars;
398 else if( conslabel == LABEL_UNASSIGNED )
399 conslabel = varlabel;
400 else if( conslabel != varlabel )
401 {
402 /* there must not be two variables from different named blocks in a single constraint, since the presence
403 * of named block variables forbids this constraint from the master (linking) block
404 */
405 if( benderslabels )
406 benderserror = TRUE;
407
408 conslabel = SCIP_DECOMP_LINKCONS;
409 break;
410 }
411 }
412
413 assert(nlinkingvars == nconsvars || conslabel != LABEL_UNASSIGNED);
414 assert(v == nconsvars || conslabel == SCIP_DECOMP_LINKCONS);
415 SCIP_UNUSED(nlinkingvars);
416
417 /* if there are only linking variables, the constraint is unassigned */
418 if( conslabel == LABEL_UNASSIGNED )
419 conslabel = SCIP_DECOMP_LINKCONS;
420 conslabels[c] = conslabel;
421 }
422
423 SCIP_CALL( SCIPdecompSetConsLabels(decomp, conss, conslabels, nconss) );
424
425 SCIPfreeBufferArray(scip, &conslabels);
426 SCIPfreeBufferArray(scip, &varlabels);
427 SCIPfreeBufferArray(scip, &varbuffer);
428
429 /* throw an error and inform the user if the variable block decomposition does not allow a benders constraint labeling */
430 if( benderserror )
431 {
432 SCIPerrorMessage("Error in constraint label computation; variables from multiple named blocks in a single constraint\n");
433
434 return SCIP_INVALIDDATA;
435 }
436
437 return SCIP_OKAY;
438}
439
440/** creates a decomposition of the variables from a labeling of the constraints
441 *
442 * NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named
443 * blocks have have precedence over linking constraints. If a variable exists in constraints from
444 * two or more named blocks, then this variable is marked as a linking variable.
445 * If a variable occurs in exactly one named block i>=0, it is assigned label i.
446 * Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will
447 * label them as linking variables.
448 *
449 * If the variables should be labeled for the application of Benders' decomposition, the decomposition must be
450 * flagged explicitly via SCIPdecompSetUseBendersLabels().
451 * With this setting, the presence in linking constraints takes precedence over the presence in named blocks.
452 * Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary
453 * number of constraints from named blocks.
454 */
456 SCIP* scip, /**< SCIP data structure */
457 SCIP_DECOMP* decomp, /**< decomposition data structure */
458 SCIP_CONS** conss, /**< array of constraints */
459 int nconss /**< number of constraints */
460 )
461{
462 int c;
463 int* conslabels;
464 SCIP_VAR** varbuffer;
465 int varbufsize;
466 SCIP_Bool benderslabels;
467
468 assert(scip != NULL);
469 assert(decomp != NULL);
470 assert(conss != NULL);
471
472 /* make the buffer array large enough such that we do not have to reallocate buffer */
473 varbufsize = getVarbufSize(scip);
474
475 /* allocate buffer to store constraint variables and labels */
476 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
477 SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, varbufsize) );
478
479 /* query constraint labels */
480 SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
481
482 benderslabels = SCIPdecompUseBendersLabels(decomp);
483 /* iterate over constraints and query the corresponding constraint labels */
484 for( c = 0; c < nconss; ++c )
485 {
486 int conslabel;
487 int v;
488 int nconsvars;
489 SCIP_Bool success;
490 int requiredsize;
491 int newvarlabel;
492
493 conslabel = conslabels[c];
494
495 if( conslabel == SCIP_DECOMP_LINKCONS )
496 {
497 /* skip linking constraints unless Benders labeling is used */
498 if( ! benderslabels )
499 continue;
500 else
501 newvarlabel = SCIP_DECOMP_LINKVAR;
502 }
503 else
504 newvarlabel = conslabel;
505
506 SCIP_CALL( decompGetConsVarsAndLabels(scip, decomp, conss[c], varbuffer, NULL,
507 varbufsize, &nconsvars, &requiredsize, &success) );
508 SCIP_CALL( ensureCondition(success) );
509
510 /* each variable in this constraint gets the constraint label unless it already has a different label -> make it a linking variable */
511 for( v = 0; v < nconsvars; ++v )
512 {
513 SCIP_VAR* var = varbuffer[v];
514
515 assert(SCIPvarIsActive(var) || (SCIPdecompIsOriginal(decomp) && SCIPvarIsNegated(var)));
516
517 /* some constraint handlers such as indicator may already return inactive variables */
518 if( SCIPvarIsNegated(var) )
519 var = SCIPvarGetNegatedVar(var);
520
521 if( SCIPhashmapExists(decomp->var2block, (void *)var) )
522 {
523 int varlabel = SCIPhashmapGetImageInt(decomp->var2block, (void *)var);
524
525 /* store the label linking variable explicitly to distinguish it from the default */
526 if( varlabel != SCIP_DECOMP_LINKVAR && varlabel != newvarlabel )
528 }
529 else
530 {
531 SCIP_CALL( SCIPhashmapInsertInt(decomp->var2block, (void *)var, newvarlabel) );
532 }
533 }
534 }
535
536 SCIPfreeBufferArray(scip, &varbuffer);
537 SCIPfreeBufferArray(scip, &conslabels);
538
539 return SCIP_OKAY;
540}
541
542/** assigns linking constraints to blocks
543 *
544 * Each linking constraint is assigned to the most frequent block among its variables.
545 * Variables of other blocks are relabeled as linking variables.
546 * Constraints that have only linking variables are skipped.
547 *
548 * @note: In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
549 */
551 SCIP* scip, /**< SCIP data structure */
552 SCIP_DECOMP* decomp, /**< decomposition data structure */
553 SCIP_CONS** conss, /**< array of linking constraints that should be reassigned */
554 int nconss, /**< number of constraints */
555 int* nskipconss /**< pointer to store the number of constraints that were skipped, or NULL */
556 )
557{
558 SCIP_VAR** vars;
559 SCIP_VAR** allvars;
560 int* varslabels;
561 int requiredsize;
562 int nvars;
563 int nconsvars;
564 int varbufsize;
565 int c;
566 int nskipconsslocal;
567 int defaultlabel;
568
569 assert(scip != NULL);
570 assert(decomp != NULL);
571
572 nvars = SCIPgetNVars(scip);
573 varbufsize = getVarbufSize(scip);
574
575 SCIP_CALL( SCIPallocBufferArray(scip, &varslabels, varbufsize) );
576 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varbufsize) );
577
578 /* get one label as default label */
580 SCIPdecompGetVarsLabels(decomp, allvars, varslabels, nvars);
581 for( c = 0; c < nvars; c++ )
582 {
583 if( varslabels[c] != SCIP_DECOMP_LINKVAR )
584 {
585 defaultlabel = varslabels[c];
586 break;
587 }
588 }
589
590 nskipconsslocal = 0;
591 for( c = 0; c < nconss; c++ )
592 {
593 SCIP_Bool success;
594
595 SCIP_CALL( decompGetConsVarsAndLabels(scip, decomp, conss[c], vars, varslabels, varbufsize,
596 &nconsvars, &requiredsize, &success) );
597 SCIP_CALL( ensureCondition(success) );
598
599 SCIPsortIntPtr(varslabels, (void **)vars, nconsvars);
600 /* constraint contains no (active) variables */
601 if( nconsvars == 0 )
602 {
603 SCIP_CALL( SCIPdecompSetConsLabels(decomp, &conss[c], &defaultlabel, 1) );
604 }
605 /* constraint contains only linking variables */
606 else if( varslabels[nconsvars - 1] == SCIP_DECOMP_LINKVAR )
607 {
608 nskipconsslocal++;
609
610 continue;
611 }
612 else
613 {
614 int startposs[2];
615 int endposs[2];
616 int nlinkvars;
617 int block;
618 int maxnblockvars;
619 int curr;
620 int v;
621 int p;
622
623 /* count linking variables */
624 if( varslabels[0] == SCIP_DECOMP_LINKVAR )
625 {
626 nlinkvars = countLabelFromPos(varslabels, 0, nconsvars);
627 }
628 else
629 {
630 nlinkvars = 0;
631 }
632
633 assert(nlinkvars < nconsvars);
634
635 curr = nlinkvars;
636 /* find the most frequent block label among the nonlinking variables */
637 maxnblockvars = 0;
638 block = -1;
639 do
640 {
641 int nblockvars = countLabelFromPos(varslabels, curr, nconsvars);
642 if( nblockvars > maxnblockvars )
643 {
644 maxnblockvars = nblockvars;
645 block = curr;
646 }
647 curr += nblockvars;
648 }
649 while( curr < nconsvars );
650
651 /* reassign all variables from other blocks as linking variables */
652 startposs[0] = nlinkvars;
653 endposs[0] = block;
654 startposs[1] = block + maxnblockvars;
655 endposs[1] = nconsvars;
656
657 /* loop over all variables before (p==0) and after (p==1) the most frequent block label */
658 for( p = 0; p < 2; ++p )
659 {
660 /* relabel */
661 for( v = startposs[p]; v < endposs[p]; ++v )
662 varslabels[v] = SCIP_DECOMP_LINKVAR;
663
664 /* set labels in the decomposition */
665 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &vars[startposs[p]], &varslabels[startposs[p]], endposs[p] - startposs[p]) );
666 }
667
668 SCIP_CALL( SCIPdecompSetConsLabels(decomp, &conss[c], &varslabels[block], 1) );
669 }
670 }
671
672 if( nskipconss != NULL )
673 *nskipconss = nskipconsslocal;
674
676 SCIPfreeBufferArray(scip, &varslabels);
677
678 return SCIP_OKAY;
679}
680
681/** return position of a label in decomp array */
682static
684 SCIP_DECOMP* decomp, /**< decomposition data structure */
685 int label /**< the label */
686 )
687{
688 int pos;
689
690 (void)SCIPsortedvecFindInt(decomp->labels, label, decomp->nblocks + 1, &pos);
691
692 return pos;
693}
694
695/** compute decomposition modularity (comparison of within block edges against a random decomposition) */
696static
698 SCIP* scip, /**< SCIP data structure */
699 SCIP_DECOMP* decomp, /**< decomposition data structure */
700 SCIP_Real* modularity /**< pointer to store modularity value */
701 )
702{
703 SCIP_CONS** conss;
704 SCIP_VAR** varbuf;
705 int* varslabels;
706 int* conslabels;
707 int* totaldegrees; /* the total degree for every block */
708 int* withinedges; /* the number of edges within each block */
709 int nnonzeroes = 0;
710 int varbufsize;
711 int nconss;
712 int c;
713 int b;
714
715 /* allocate buffer arrays to hold constraint and variable labels, and store within-edges and total community degrees */
716 getDecompVarsConssData(scip, decomp, NULL, &conss, NULL, &nconss);
717 varbufsize = getVarbufSize(scip);
718
719 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
720 SCIP_CALL( SCIPallocBufferArray(scip, &varslabels, varbufsize) );
721 SCIP_CALL( SCIPallocBufferArray(scip, &varbuf, varbufsize) );
722
723 SCIP_CALL( SCIPallocClearBufferArray(scip, &totaldegrees, decomp->nblocks + 1) );
724 SCIP_CALL( SCIPallocClearBufferArray(scip, &withinedges, decomp->nblocks + 1) );
725
726 SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
727
728 /*
729 * loop over all nonzeros, consider the labels of the incident nodes (cons and variable)
730 * and increase the corresponding counters
731 */
732 for( c = 0; c < nconss; ++c )
733 {
734 int nconsvars;
735 int conslabel = conslabels[c];
736 int blockpos;
737 int varblockstart;
738 int requiredsize;
739 SCIP_Bool success;
740
741 /* linking constraints do not contribute to the modularity */
742 if( conslabel == SCIP_DECOMP_LINKCONS )
743 continue;
744
745 /* find the position of the constraint label. Constraints of the border always belong to the first block at index 0 */
746 blockpos = findLabelIdx(decomp, conslabel);
747
748 SCIP_CALL( decompGetConsVarsAndLabels(scip, decomp, conss[c], varbuf, varslabels,
749 varbufsize, &nconsvars, &requiredsize, &success) );
750 SCIP_CALL( ensureCondition(success) );
751
752 SCIPsortInt(varslabels, nconsvars);
753
754 /* count occurrences of labels (blocks) in the sorted labels array */
755 varblockstart = 0;
756 while( varblockstart < nconsvars )
757 {
758 int varblockpos;
759 int nblockvars = countLabelFromPos(varslabels, varblockstart, nconsvars);
760
761 varblockpos = findLabelIdx(decomp, varslabels[varblockstart]);
762
763 /* don't consider linking variables for modularity statistics */
764 if( varslabels[varblockstart] != SCIP_DECOMP_LINKVAR )
765 {
766 /* increase the number of within edges for variable and constraints from the same block */
767 if( varblockpos == blockpos )
768 withinedges[varblockpos] += nblockvars;
769
770 /* increase the total degrees and nonzero (edge) counts; it is intended that the total degrees sum up
771 * to twice the number of edges
772 */
773 totaldegrees[blockpos] += nblockvars;
774 totaldegrees[varblockpos] += nblockvars;
775 nnonzeroes += nblockvars;
776 }
777
778 varblockstart += nblockvars;
779 }
780 }
781
782/* ensure that total degrees sum up to twice the number of edges */
783#ifndef NDEBUG
784 {
785 int totaldegreesum = 0;
786 for( b = 1; b < decomp->nblocks + 1; ++b )
787 totaldegreesum += totaldegrees[b];
788
789 assert(totaldegreesum == 2 * nnonzeroes);
790 }
791#endif
792
793 /* compute modularity */
794 *modularity = 0.0;
795 nnonzeroes = MAX(nnonzeroes, 1);
796 for( b = 1; b < decomp->nblocks + 1; ++b )
797 {
798 SCIP_Real expectedval;
799 expectedval = totaldegrees[b] / (2.0 * nnonzeroes);
800 expectedval = SQR(expectedval);
801 *modularity += (withinedges[b] / (SCIP_Real)nnonzeroes) - expectedval;
802 }
803
804 SCIPfreeBufferArray(scip, &withinedges);
805 SCIPfreeBufferArray(scip, &totaldegrees);
806 SCIPfreeBufferArray(scip, &varbuf);
807 SCIPfreeBufferArray(scip, &varslabels);
808 SCIPfreeBufferArray(scip, &conslabels);
809
810 return SCIP_OKAY;
811}
812
813/** compute the area score */
814static
816 SCIP* scip, /**< SCIP data structure */
817 SCIP_DECOMP* decomp /**< decomposition data structure */
818 )
819{
820 SCIP_Real areascore = 1.0;
821 int nvars;
822 int nconss;
823
824 getDecompVarsConssData(scip, decomp, NULL, NULL, &nvars, &nconss);
825
826 if( nvars > 0 && nconss > 0 )
827 {
828 int nlinkconss = decomp->consssize[0];
829 int nlinkvars = decomp->varssize[0];
830 SCIP_Real factor = 1.0 / ((SCIP_Real)nvars * nconss);
831
832 int i;
833
834 /* compute diagonal contributions to the area score */
835 for( i = 1; i < decomp->nblocks + 1; ++i )
836 {
837 areascore -= (factor * decomp->consssize[i]) * decomp->varssize[i];
838 }
839
840 areascore -= ((SCIP_Real)nlinkconss * nvars + (SCIP_Real)nconss * nlinkvars - (SCIP_Real)nlinkconss * nlinkvars) * factor;
841 }
842
843 decomp->areascore = areascore;
844}
845
846/** build the block decomposition graph */
847static
849 SCIP* scip, /**< SCIP data structure */
850 SCIP_DECOMP* decomp, /**< decomposition data structure */
851 int maxgraphedge /**< maximum number of edges in block graph computation (-1: no limit, 0: disable block graph computation) */
852 )
853{
854 SCIP_VAR** vars;
855 SCIP_CONS** conss;
856 SCIP_VAR** consvars;
857 SCIP_DIGRAPH* blocklinkingvargraph;
858 SCIP_DIGRAPH* blockgraph = NULL;
859 int* varlabels;
860 int* conslabels;
861 SCIP_CONS** consscopy; /* working copy of the constraints */
862 int* linkvaridx;
863 int* succnodesblk;
864 int* succnodesvar;
865 SCIP_Bool success;
866 int varbufsize;
867 int nvars;
868 int nconss;
869 int nblocks;
870 int nlinkingvars = 0;
871 int nconsvars;
872 int conspos;
873 int tempmin;
874 int tempmax;
875 int nblockgraphedges;
876 int blocknodeidx;
877 int i;
878 int j;
879 int v;
880 int n;
881
882 if( maxgraphedge == -1 )
883 maxgraphedge = INT_MAX;
884
885 assert(scip != NULL);
886 assert(decomp != NULL);
887 assert(decomp->statscomplete == FALSE);
888
889 /* capture the trivial case that no linking variables are present */
890 if( decomp->varssize[0] == 0 || decomp->nblocks == 0 )
891 {
892 decomp->mindegree = 0;
893 decomp->maxdegree = 0;
894 decomp->nedges = 0;
895 decomp->ncomponents = SCIPdecompGetNBlocks(decomp);
896 decomp->narticulations = 0;
897 decomp->statscomplete = TRUE;
898
899 return SCIP_OKAY;
900 }
901
902 getDecompVarsConssData(scip, decomp, &vars, &conss, &nvars, &nconss);
903 varbufsize = getVarbufSize(scip);
904 nblocks = SCIPdecompGetNBlocks(decomp);
905
906 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
907 SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, varbufsize) );
908 SCIP_CALL( SCIPallocBufferArray(scip, &linkvaridx, varbufsize) );
909 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, varbufsize) );
910
911 /* store variable and constraint labels in buffer arrays */
912 SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
913 SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars);
914
915 /* create a mapping of all linking variables to 0,..,nlinkingvars -1 and store it in array linkvaridx */
916 for( v = 0; v < nvars; ++v )
917 {
918 if( varlabels[v] == SCIP_DECOMP_LINKVAR )
919 {
920 linkvaridx[v] = nlinkingvars;
921 assert(SCIPvarGetProbindex(vars[v]) == v);
922 ++nlinkingvars;
923 }
924 else
925 linkvaridx[v] = -1;
926 }
927
928 /* create a bipartite graph composed of block and linking var nodes */
929 SCIP_CALL( SCIPcreateDigraph(scip, &blocklinkingvargraph, nblocks + nlinkingvars) );/* nblocks does not include the linking constraints block */
930
931 /* initialize position to start after the linking constraints, which we skip anyway */
932 SCIP_CALL( SCIPduplicateBufferArray(scip, &consscopy, conss, nconss) );
933 SCIPsortIntPtr(conslabels, (void**)consscopy, nconss);
934 if( conslabels[0] == SCIP_DECOMP_LINKCONS )
935 conspos = countLabelFromPos(conslabels, 0, nconss);
936 else
937 /* no linking constraints present */
938 conspos = 0;
939
940 blocknodeidx = -1;
941 /* loop over each block */
942 while( conspos < nconss )
943 {
944 SCIP_Bool* adjacent;
945 int* adjacentidxs;
946 int nblockconss = countLabelFromPos(conslabels, conspos, nconss);
947 int nblocklinkingvars = 0;
948 int c;
949
950 ++blocknodeidx;
951 /* allocate buffer storage to store all linking variable indices adjacent to this block */
952 SCIP_CALL( SCIPallocCleanBufferArray(scip, &adjacent, nlinkingvars) );
953 SCIP_CALL( SCIPallocBufferArray(scip, &adjacentidxs, nlinkingvars) );
954
955 /* loop over the constraints of this block; stop if the block vertex has maximum degree */
956 for( c = conspos; c < conspos + nblockconss && nblocklinkingvars < nlinkingvars; ++c )
957 {
958 int requiredsize;
959 SCIP_CONS* cons = consscopy[c];
960 assert(conslabels[c] != SCIP_DECOMP_LINKCONS);
961
962 SCIP_CALL( decompGetConsVarsAndLabels(scip, decomp, cons, consvars, varlabels,
963 varbufsize, &nconsvars, &requiredsize, &success) );
964 SCIP_CALL( ensureCondition(success) );
965
966 /* search for linking variables that are not connected so far; stop as soon as block vertex has max degree */
967 for( j = 0; j < nconsvars && nblocklinkingvars < nlinkingvars; ++j )
968 {
969 int linkingvarnodeidx;
970 /* consider only linking variables */
971 if( varlabels[j] != SCIP_DECOMP_LINKVAR )
972 continue;
973
974 linkingvarnodeidx = linkvaridx[SCIPvarGetProbindex(consvars[j])];
975 assert(linkingvarnodeidx >= 0);
976
977 if( !adjacent[linkingvarnodeidx] )
978 {
979 adjacent[linkingvarnodeidx] = TRUE;
980 adjacentidxs[nblocklinkingvars++] = linkingvarnodeidx;
981 }
982 }
983 }
984
985 /* connect block and linking variables in the digraph */
986 assert(blocknodeidx == findLabelIdx(decomp, conslabels[conspos]) - 1);
987 for( i = 0; i < nblocklinkingvars; ++i )
988 {
989 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, blocknodeidx, nblocks + adjacentidxs[i], NULL) );
990 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, nblocks + adjacentidxs[i], blocknodeidx, NULL) );
991 }
992
993 /* clean up the adjacent array before freeing */
994 for( i = 0; i < nblocklinkingvars; ++i )
995 adjacent[adjacentidxs[i]] = FALSE;
996
997 /* check that adjacent has been entirely cleaned up */
998#ifndef NDEBUG
999 for( i = 0; i < nlinkingvars; ++i )
1000 assert(adjacent[i] == FALSE);
1001#endif
1002
1003 SCIPfreeBufferArray(scip, &adjacentidxs);
1004 SCIPfreeCleanBufferArray(scip, &adjacent);
1005
1006 conspos += nblockconss;
1007 }
1008
1009 SCIPfreeBufferArray(scip, &consscopy);
1010
1011 assert(SCIPdigraphGetNNodes(blocklinkingvargraph) > 0);
1012 /* check first if any of the linking variables is connected with all blocks -> block graph is complete and connected */
1013 for( n = nblocks; n < SCIPdigraphGetNNodes(blocklinkingvargraph); ++n )
1014 {
1015 int nsuccvar;
1016 nsuccvar = (int) SCIPdigraphGetNSuccessors(blocklinkingvargraph, n);
1017
1018 if( nsuccvar == nblocks )
1019 {
1020 decomp->nedges = nblocks * (nblocks - 1) / 2;
1021 decomp->mindegree = decomp->maxdegree = nblocks - 1;
1022 decomp->narticulations = 0;
1023 decomp->ncomponents = 1;
1024 decomp->statscomplete = TRUE;
1025
1026 goto TERMINATE;
1027 }
1028 }
1029
1030 /* from the information of the above bipartite graph, build the block-decomposition graph: nodes -> blocks and double-direction arcs -> linking variables */
1031 SCIP_CALL( SCIPcreateDigraph(scip, &blockgraph, nblocks) );
1032
1033 /* we count the number of block graph edges manually, because SCIPdigraphGetNArcs() iterates over all nodes */
1034 nblockgraphedges = 0;
1035 for( n = 0; n < nblocks - 1 && nblockgraphedges < maxgraphedge; ++n )
1036 {
1037 SCIP_Bool* adjacent; /* an array to mark the adjacent blocks to the current block */
1038 int* adjacentidxs;
1039 int nsuccblk;
1040 int nadjacentblks = 0;
1041 SCIP_CALL( SCIPallocCleanBufferArray(scip, &adjacent, nblocks) );
1042 SCIP_CALL( SCIPallocBufferArray(scip, &adjacentidxs, nblocks) );
1043
1044 assert(n < SCIPdigraphGetNNodes(blocklinkingvargraph));
1045
1046 /* loop over the connected linking variables to the current block and their connected blocks to update the adjacency array */
1047 nsuccblk = SCIPdigraphGetNSuccessors(blocklinkingvargraph, n);
1048 succnodesblk = SCIPdigraphGetSuccessors(blocklinkingvargraph, n);
1049 for( i = 0; i < nsuccblk && nadjacentblks < nblocks - (n + 1); ++i )
1050 {
1051 int startpos;
1052 int nsuccvar;
1053
1054 assert(succnodesblk[i] < SCIPdigraphGetNNodes(blocklinkingvargraph));
1055
1056 nsuccvar = SCIPdigraphGetNSuccessors(blocklinkingvargraph, succnodesblk[i]);
1057 succnodesvar = SCIPdigraphGetSuccessors(blocklinkingvargraph, succnodesblk[i]);
1058
1059 /* previously visited blocks can be skipped in this step */
1060 if( ! SCIPsortedvecFindInt(succnodesvar, n, nsuccvar, &startpos) )
1061 SCIPABORT();
1062 for( j = startpos + 1; j < nsuccvar; ++j )
1063 {
1064 assert( succnodesvar[j] > n );
1065 if( !adjacent[succnodesvar[j]] )
1066 {
1067 adjacent[succnodesvar[j]] = TRUE;
1068 adjacentidxs[nadjacentblks] = succnodesvar[j];
1069 ++nadjacentblks;
1070 }
1071 }
1072 }
1073
1074 /* double-direction arcs are added in this step between the current block and its adjacent block nodes */
1075 for( i = 0; i < nadjacentblks && nblockgraphedges < maxgraphedge; ++i )
1076 {
1077 SCIP_CALL( SCIPdigraphAddArc(blockgraph, n, adjacentidxs[i], NULL) );
1078 SCIP_CALL( SCIPdigraphAddArc(blockgraph, adjacentidxs[i], n, NULL) );
1079
1080 ++nblockgraphedges;
1081 }
1082
1083 /* clean up the adjacent array and free it */
1084 for( i = 0; i < nadjacentblks; ++i )
1085 adjacent[adjacentidxs[i]] = FALSE;
1086
1087 SCIPfreeBufferArray(scip, &adjacentidxs);
1088 SCIPfreeCleanBufferArray(scip, &adjacent);
1089 }
1090
1091 assert(SCIPdigraphGetNNodes(blockgraph) > 0);
1092
1093 /* Get the number of edges in the block-decomposition graph.*/
1094 decomp->nedges = nblockgraphedges;
1095 decomp->statscomplete = nblockgraphedges < maxgraphedge;
1096
1097 /* Get the minimum and maximum degree of the block-decomposition graph */
1098 tempmin = (int) SCIPdigraphGetNSuccessors(blockgraph, 0);
1099 tempmax = (int) SCIPdigraphGetNSuccessors(blockgraph, 0);
1100 for( n = 1; n < SCIPdigraphGetNNodes(blockgraph); ++n )
1101 {
1102 int nsuccblk = SCIPdigraphGetNSuccessors(blockgraph, n);
1103
1104 if( nsuccblk < tempmin )
1105 tempmin = nsuccblk;
1106 else if( nsuccblk > tempmax )
1107 tempmax = nsuccblk;
1108 }
1109
1110 decomp->mindegree = tempmin;
1111 decomp->maxdegree = tempmax;
1112
1113 /* Get the number of connected components in the block-decomposition graph.*/
1115 decomp->ncomponents = SCIPdigraphGetNComponents(blockgraph);
1116
1117 /* Get the number of articulation points in the block-decomposition graph using DFS.*/
1119
1120TERMINATE:
1121 SCIPfreeBufferArray(scip, &consvars);
1122 SCIPfreeBufferArray(scip, &linkvaridx);
1123 SCIPfreeBufferArray(scip, &varlabels);
1124 SCIPfreeBufferArray(scip, &conslabels);
1125
1126 /* blockgraph has probably not been allocated */
1127 if( blockgraph != NULL)
1128 SCIPdigraphFree(&blockgraph);
1129
1130 SCIPdigraphFree(&blocklinkingvargraph);
1131
1132 return SCIP_OKAY;
1133}
1134
1135/** computes decomposition statistics and store them in the decomposition object */
1137 SCIP* scip, /**< SCIP data structure */
1138 SCIP_DECOMP* decomp, /**< decomposition data structure */
1139 SCIP_Bool uselimits /**< respect user limits on potentially expensive graph statistics? */
1140 )
1141{
1142 SCIP_VAR** vars;
1143 SCIP_CONS** conss;
1144 SCIP_CONS** conssarray;
1145 SCIP_VAR** varsarray;
1146 int* varslabels;
1147 int* conslabels;
1148 int nvars;
1149 int nconss;
1150 int varblockstart;
1151 int consblockstart;
1152 int currlabelidx;
1153 int varidx;
1154 int considx;
1155 int i;
1156 int maxgraphedge;
1157 SCIP_Bool disablemeasures;
1158
1159 assert(scip != NULL);
1160 assert(decomp != NULL);
1161
1162 getDecompVarsConssData(scip, decomp, &vars, &conss, &nvars, &nconss);
1163
1164 /* return if problem is empty
1165 *
1166 * TODO ensure that statistics reflect this correctly
1167 */
1168 if( nvars == 0 || nconss == 0 )
1169 {
1170 decomp->nblocks = 0;
1171 decomp->varssize[0] = nvars;
1172 decomp->consssize[0] = nconss;
1173 decomp->labels[0] = SCIP_DECOMP_LINKVAR;
1174 return SCIP_OKAY;
1175 }
1176
1177 decomp->statscomplete = FALSE;
1178
1179 /* store variable and constraint labels in buffer arrays */
1180 SCIP_CALL( SCIPduplicateBufferArray(scip, &conssarray, conss, nconss) );
1181 SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
1182 SCIP_CALL( SCIPduplicateBufferArray(scip, &varsarray, vars, nvars) );
1183 SCIP_CALL( SCIPallocBufferArray(scip, &varslabels, nvars) );
1184
1185 SCIPdecompGetVarsLabels(decomp, varsarray, varslabels, nvars);
1186 SCIPdecompGetConsLabels(decomp, conssarray, conslabels, nconss);
1187
1188 /* sort both buffer arrays for quick counting */
1189 SCIPsortIntPtr(varslabels, (void**)varsarray, nvars);
1190 SCIPsortIntPtr(conslabels, (void**)conssarray, nconss);
1191
1192 /* the first label is always LINKVAR, even if Benders' variable labels are used. We can ignore the variables
1193 * labelled as LINKCONS since this label is only required when computing the variable labels for Benders'
1194 * decomposition.
1195 */
1196 decomp->labels[0] = SCIP_DECOMP_LINKVAR;
1197
1198 /* treating the linking variables first */
1199 if( varslabels[0] == SCIP_DECOMP_LINKVAR )
1200 decomp->varssize[0] = countLabelFromPos(varslabels, 0, nvars);
1201 else
1202 decomp->varssize[0] = 0;
1203
1204 /* count border constraints and store their number */
1205 if( conslabels[0] == SCIP_DECOMP_LINKCONS )
1206 decomp->consssize[0] = countLabelFromPos(conslabels, 0, nconss);
1207 else
1208 decomp->consssize[0] = 0;
1209
1210 /* merge labels (except for border at position 0) since neither variable nor constraint labels by themselves need to be complete */
1211 currlabelidx = 1;
1212 varidx = decomp->varssize[0];
1213 considx = decomp->consssize[0];
1214
1215 while( varidx < nvars || considx < nconss )
1216 {
1217 int varlabel;
1218 int conslabel;
1219
1220 varlabel = varidx < nvars ? varslabels[varidx] : INT_MAX;
1221 conslabel = considx < nconss ? conslabels[considx] : INT_MAX;
1222
1223 assert(currlabelidx < decomp->memsize);
1224 /* store the smaller of the two current labels */
1225 decomp->labels[currlabelidx] = MIN(varlabel, conslabel);
1226
1227 /* a strictly larger variable label means that there are no variables for the current label */
1228 if( varlabel <= conslabel )
1229 decomp->varssize[currlabelidx] = countLabelFromPos(varslabels, varidx, nvars);
1230 else
1231 decomp->varssize[currlabelidx] = 0;
1232
1233 /* the same for constraint labels */
1234 if( conslabel <= varlabel )
1235 decomp->consssize[currlabelidx] = countLabelFromPos(conslabels, considx, nconss);
1236 else
1237 decomp->consssize[currlabelidx] = 0;
1238
1239 /* increase indices appropriately */
1240 varidx += decomp->varssize[currlabelidx];
1241 considx += decomp->consssize[currlabelidx];
1242
1243 currlabelidx++;
1244 }
1245
1246 SCIPdebugMsg(scip, "Counted %d different labels (should be %d)\n", currlabelidx, decomp->nblocks + 1);
1247
1248 /* strip the remaining, unused blocks */
1249 if( currlabelidx < decomp->nblocks + 1 )
1250 decomp->nblocks = currlabelidx - 1;
1251
1252 /* delete empty blocks from statistics, relabel the corresponding constraints/variables as linking */
1253 varblockstart = decomp->varssize[0];
1254 consblockstart = decomp->consssize[0];
1255
1256 for( i = 1; i < decomp->nblocks + 1; ++i )
1257 {
1258 assert(MAX(decomp->varssize[i], decomp->consssize[i]) > 0);
1259 /* relabel constraint blocks as linking, if there are no corresponding variables */
1260 if( decomp->varssize[i] == 0 )
1261 {
1262 int nblockconss = decomp->consssize[i];
1263 int c;
1264 /* relabel these constraints as linking */
1265 for( c = consblockstart; c < consblockstart + nblockconss; ++c )
1266 conslabels[c] = SCIP_DECOMP_LINKCONS;
1267
1268 SCIP_CALL( SCIPdecompSetConsLabels(decomp, &conssarray[consblockstart], &conslabels[consblockstart], nblockconss) );
1269
1270 /* increase number of linking constraints */
1271 decomp->consssize[0] += nblockconss;
1272 }
1273
1274 /* same for constraints */
1275 if( decomp->consssize[i] == 0 )
1276 {
1277 int nblockvars = decomp->varssize[i];
1278 int v;
1279
1280 /* relabel the variables as linking variables */
1281 for( v = varblockstart; v < varblockstart + nblockvars; ++v )
1282 varslabels[v] = SCIP_DECOMP_LINKVAR;
1283
1284 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &varsarray[varblockstart], &varslabels[varblockstart], nblockvars) );
1285
1286 /* increase number of linking variables */
1287 decomp->varssize[0] += nblockvars;
1288 }
1289
1290 varblockstart += decomp->varssize[i];
1291 consblockstart += decomp->consssize[i];
1292 }
1293
1294 currlabelidx = 1;
1295
1296 /* delete empty blocks; they are no longer present */
1297 for( i = 1; i < decomp->nblocks + 1; ++i )
1298 {
1299 /* keep only nonempty blocks */
1300 if( decomp->varssize[i] > 0 && decomp->consssize[i] > 0 )
1301 {
1302 decomp->labels[currlabelidx] = decomp->labels[i];
1303 decomp->varssize[currlabelidx] = decomp->varssize[i];
1304 decomp->consssize[currlabelidx] = decomp->consssize[i];
1305
1306 currlabelidx++;
1307 }
1308 }
1309
1310 decomp->nblocks = currlabelidx - 1;
1311
1312 decomp->idxsmallestblock = decomp->idxlargestblock = -1;
1313 /* now that indices are fixed, store indices with largest and smallest number of constraints */
1314 for( i = 1; i < decomp->nblocks + 1; ++i )
1315 {
1316 if( decomp->idxsmallestblock == -1 )
1317 decomp->idxsmallestblock = decomp->idxlargestblock = i;
1318 else if( decomp->consssize[decomp->idxsmallestblock] > decomp->consssize[i] )
1319 decomp->idxsmallestblock = i;
1320 else if( decomp->consssize[decomp->idxlargestblock] < decomp->consssize[i] )
1321 decomp->idxlargestblock = i;
1322 }
1323
1324 /* compute more involved statistics such as the area score, the modularity, and the block graph statistics */
1325 SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/disablemeasures", &disablemeasures) );
1326 if( !disablemeasures )
1327 {
1328 SCIP_CALL( computeModularity(scip, decomp, &decomp->modularity) );
1329 computeAreaScore(scip, decomp);
1330 }
1331
1332 if( uselimits )
1333 {
1334 SCIP_CALL( SCIPgetIntParam(scip, "decomposition/maxgraphedge", &maxgraphedge) );
1335 }
1336 else
1337 maxgraphedge = -1;
1338
1339 /* do not start computation of the block graph if maxgraphedge is set to 0 */
1340 if( maxgraphedge != 0 )
1341 {
1342 SCIP_CALL( buildBlockGraph(scip, decomp, maxgraphedge) );
1343 }
1344
1345 SCIPfreeBufferArray(scip, &varslabels);
1346 SCIPfreeBufferArray(scip, &varsarray);
1347 SCIPfreeBufferArray(scip, &conslabels);
1348 SCIPfreeBufferArray(scip, &conssarray);
1349
1350 return SCIP_OKAY;
1351}
SCIP_VAR ** b
Definition: circlepacking.c:65
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:640
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:611
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:630
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
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_UNUSED(x)
Definition: def.h:428
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define SQR(x)
Definition: def.h:214
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIPABORT()
Definition: def.h:346
#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
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
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
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 SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:550
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:57
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:234
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:245
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:282
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
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
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:246
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
Definition: misc.c:7746
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7568
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:8000
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3134
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
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
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIP_CONS ** SCIPgetOrigConss(SCIP *scip)
Definition: scip_prob.c:3161
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip_var.c:1830
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortInt(int *intarray, int len)
methods for block memory pools and memory buffers
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
static SCIP_RETCODE computeModularity(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Real *modularity)
Definition: scip_dcmp.c:697
static SCIP_RETCODE ensureCondition(SCIP_Bool condition)
Definition: scip_dcmp.c:85
static void getDecompVarsConssData(SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss)
Definition: scip_dcmp.c:109
static int findLabelIdx(SCIP_DECOMP *decomp, int label)
Definition: scip_dcmp.c:683
static void computeAreaScore(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:815
static int getVarbufSize(SCIP *scip)
Definition: scip_dcmp.c:94
#define LABEL_UNASSIGNED
Definition: scip_dcmp.c:56
static SCIP_RETCODE buildBlockGraph(SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge)
Definition: scip_dcmp.c:848
static SCIP_RETCODE decompGetConsVarsAndLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_VAR **varbuf, int *labelbuf, int bufsize, int *nvars, int *requiredsize, SCIP_Bool *success)
Definition: scip_dcmp.c:139
static int countLabelFromPos(int *labels, int pos, int nlabels)
Definition: scip_dcmp.c:60
public methods for decompositions
general public methods
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for SCIP variables
int idxlargestblock
Definition: struct_dcmp.h:50
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
int * consssize
Definition: struct_dcmp.h:53
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_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63