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 */
59 static
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 */
84 static
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 */
93 static
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 */
108 static
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 */
138 static
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 
241  SCIPdecompFree(decomp, SCIPblkmem(scip));
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),
255  !SCIPdecompIsOriginal(decomp), !SCIPdecompIsOriginal(decomp), FALSE, FALSE, FALSE) );
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 )
276 
277  if( ndecomps != NULL )
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 */
579  allvars = SCIPdecompIsOriginal(decomp) ? SCIPgetOrigVars(scip) : SCIPgetVars(scip);
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 
675  SCIPfreeBufferArray(scip, &vars);
676  SCIPfreeBufferArray(scip, &varslabels);
677 
678  return SCIP_OKAY;
679 }
680 
681 /** return position of a label in decomp array */
682 static
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) */
696 static
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 */
814 static
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 */
847 static
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 
1120 TERMINATE:
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 }
#define NULL
Definition: def.h:267
public methods for SCIP parameter handling
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:640
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:198
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:455
public methods for memory management
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:550
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:611
#define SQR(x)
Definition: def.h:214
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIP_Real areascore
Definition: struct_dcmp.h:49
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
static void getDecompVarsConssData(SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss)
Definition: scip_dcmp.c:109
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:345
static SCIP_RETCODE ensureCondition(SCIP_Bool condition)
Definition: scip_dcmp.c:85
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
#define SCIP_UNUSED(x)
Definition: def.h:434
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:124
public methods for problem variables
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:45
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:234
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:246
#define LABEL_UNASSIGNED
Definition: scip_dcmp.c:56
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17895
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
Definition: misc.c:7746
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:630
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
SCIP_Real modularity
Definition: struct_dcmp.h:48
public methods for decompositions
public methods for managing constraints
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:621
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
static int findLabelIdx(SCIP_DECOMP *decomp, int label)
Definition: scip_dcmp.c:683
methods for block memory pools and memory buffers
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
Definition: dcmp.c:575
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
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
int * consssize
Definition: struct_dcmp.h:53
SCIP_CONS ** SCIPgetOrigConss(SCIP *scip)
Definition: scip_prob.c:3161
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
int ncomponents
Definition: struct_dcmp.h:60
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:279
int * varssize
Definition: struct_dcmp.h:52
int idxlargestblock
Definition: struct_dcmp.h:50
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
#define SCIP_CALL(x)
Definition: def.h:380
static SCIP_RETCODE computeModularity(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Real *modularity)
Definition: scip_dcmp.c:697
SCIP main data structure.
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3134
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_DECOMPSTORE * decompstore
Definition: struct_scip.h:83
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
public methods for constraint handler plugins and constraints
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:44
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:173
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
static void computeAreaScore(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:815
#define SCIP_Bool
Definition: def.h:91
static SCIP_RETCODE buildBlockGraph(SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge)
Definition: scip_dcmp.c:848
data structures for a decomposition and a decomposition store
#define MIN(x, y)
Definition: def.h:243
methods for debugging
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:57
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:8000
int idxsmallestblock
Definition: struct_dcmp.h:51
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:282
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
internal methods for decompositions and the decomposition store
SCIP_VAR ** b
Definition: circlepacking.c:65
general public methods
#define MAX(x, y)
Definition: def.h:239
int * labels
Definition: struct_dcmp.h:54
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
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
#define SCIP_Real
Definition: def.h:173
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
public methods for message handling
public methods for data structures
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:218
void SCIPsortInt(int *intarray, int len)
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:245
static int countLabelFromPos(int *labels, int pos, int nlabels)
Definition: scip_dcmp.c:60
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition: dcmp.c:99
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
SCIP_Bool statscomplete
Definition: struct_dcmp.h:64
static int getVarbufSize(SCIP *scip)
Definition: scip_dcmp.c:94
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
public methods for decompositions
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7568
#define SCIPABORT()
Definition: def.h:352
public methods for global and local (sub)problems
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip_var.c:1832
int narticulations
Definition: struct_dcmp.h:61
SCIP_HASHMAP * var2block
Definition: struct_dcmp.h:46
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17749
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17575