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