SCIP

Solving Constraint Integer Programs

symmetry.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file symmetry.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for handling symmetries
19  * @author Christopher Hojny
20  * @author Marc Pfetsch
21  */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include "scip/symmetry.h"
26 #include "scip/scip.h"
27 #include "scip/misc.h"
28
29
30 /** compute non-trivial orbits of symmetry group
31  *
32  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
33  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
34  * consecutively in the orbits array. The variables of the i-th orbit have indices
35  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
36  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
37  */
39  SCIP* scip, /**< SCIP instance */
40  SCIP_VAR** permvars, /**< variables considered in a permutation */
41  int npermvars, /**< length of a permutation array */
42  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
43  int nperms, /**< number of permutations encoded in perms */
44  int* orbits, /**< array of non-trivial orbits */
45  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
46  int* norbits /**< pointer to number of orbits currently stored in orbits */
47  )
48 {
50  int orbitidx = 0;
51  int i;
52
53  assert( scip != NULL );
54  assert( permvars != NULL );
55  assert( perms != NULL );
56  assert( nperms > 0 );
57  assert( npermvars > 0 );
58  assert( orbits != NULL );
59  assert( orbitbegins != NULL );
60  assert( norbits != NULL );
61
62  /* init data structures*/
63  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
64
65  /* initially, every variable is contained in no orbit */
66  for (i = 0; i < npermvars; ++i)
68
69  /* find variable orbits */
70  *norbits = 0;
71  for (i = 0; i < npermvars; ++i)
72  {
73  int beginorbitidx;
74  int j;
75
76  /* skip variable already contained in an orbit of a previous variable */
78  continue;
79
80  /* store first variable */
81  beginorbitidx = orbitidx;
82  orbits[orbitidx++] = i;
84
85  /* iterate over variables in curorbit and compute their images */
86  j = beginorbitidx;
87  while ( j < orbitidx )
88  {
89  int curelem;
90  int image;
91  int p;
92
93  curelem = orbits[j];
94
95  for (p = 0; p < nperms; ++p)
96  {
97  image = perms[p][curelem];
98
99  /* found new element of the orbit of i */
100  if ( ! varadded[image] )
101  {
102  orbits[orbitidx++] = image;
103  assert( orbitidx <= npermvars );
105  }
106  }
107  ++j;
108  }
109
110  /* if the orbit is trivial, reset storage, otherwise store orbit */
111  if ( orbitidx <= beginorbitidx + 1 )
112  orbitidx = beginorbitidx;
113  else
114  orbitbegins[(*norbits)++] = beginorbitidx;
115  }
116
117  /* store end in "last" orbitbegins entry */
118  assert( *norbits < npermvars );
119  orbitbegins[*norbits] = orbitidx;
120
121 #ifdef SCIP_OUTPUT
122  printf("Orbits (total number: %d):\n", *norbits);
123  for (i = 0; i < *norbits; ++i)
124  {
125  int j;
126
127  printf("%d: ", i);
128  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
129  printf("%d ", orbits[j]);
130  printf("\n");
131  }
132 #endif
133
134  /* free memory */
136
137  return SCIP_OKAY;
138 }
139
140
141 /** compute non-trivial orbits of symmetry group using filtered generators
142  *
143  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
144  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
145  * consecutively in the orbits array. The variables of the i-th orbit have indices
146  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
147  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
148  *
149  * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
150  * filter out permutations.
151  */
153  SCIP* scip, /**< SCIP instance */
154  int npermvars, /**< length of a permutation array */
155  int** permstrans, /**< transposed matrix containing in each column a
156  * permutation of the symmetry group */
157  int nperms, /**< number of permutations encoded in perms */
158  SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
159  int* orbits, /**< array of non-trivial orbits */
160  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
161  int* norbits, /**< pointer to number of orbits currently stored in orbits */
162  int* components, /**< array containing the indices of permutations sorted by components */
163  int* componentbegins, /**< array containing in i-th position the first position of
164  * component i in components array */
165  int* vartocomponent, /**< array containing for each permvar the index of the component it is
166  * contained in (-1 if not affected) */
167  SCIP_Shortbool* componentblocked, /**< array to store whether a component is blocked to be considered by
168  * further symmetry handling techniques */
169  int ncomponents, /**< number of components of symmetry group */
170  int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
171  * that is handled by orbital fixing */
172  )
173 {
176  int orbitidx = 0;
177  int i;
178
179  assert( scip != NULL );
180  assert( permstrans != NULL );
181  assert( nperms > 0 );
182  assert( npermvars > 0 );
183  assert( inactiveperms != NULL );
184  assert( orbits != NULL );
185  assert( orbitbegins != NULL );
186  assert( norbits != NULL );
187  assert( components != NULL );
188  assert( componentbegins != NULL );
189  assert( vartocomponent != NULL );
190  assert( ncomponents > 0 );
191  assert( nmovedpermvars > 0 );
192
193  /* init data structures */
194  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
195
196  /* initially, every variable is contained in no orbit */
197  for (i = 0; i < npermvars; ++i)
199
200  /* find variable orbits */
201  *norbits = 0;
202  for (i = 0; i < npermvars; ++i)
203  {
204  int beginorbitidx;
205  int componentidx;
206  int j;
207
208  /* skip unaffected variables and blocked components */
209  componentidx = vartocomponent[i];
210  if ( componentidx < 0 || componentblocked[componentidx] )
211  continue;
212
213  /* skip variable already contained in an orbit of a previous variable */
215  continue;
216
217  /* store first variable */
218  beginorbitidx = orbitidx;
219  orbits[orbitidx++] = i;
222
223  /* iterate over variables in curorbit and compute their images */
224  j = beginorbitidx;
225  while ( j < orbitidx )
226  {
227  int* pt;
228  int curelem;
229  int image;
230  int p;
231
232  curelem = orbits[j];
233
234  pt = permstrans[curelem];
235  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
236  {
237  int perm;
238
239  perm = components[p];
240
241  if ( ! inactiveperms[perm] )
242  {
243  image = pt[perm];
244  assert( vartocomponent[image] == componentidx );
245
246  /* found new element of the orbit of i */
247  if ( ! varadded[image] )
248  {
249  orbits[orbitidx++] = image;
250  assert( orbitidx <= npermvars );
253  }
254  }
255  }
256  ++j;
257  }
258
259  /* if the orbit is trivial, reset storage, otherwise store orbit */
260  if ( orbitidx <= beginorbitidx + 1 )
261  orbitidx = beginorbitidx;
262  else
263  orbitbegins[(*norbits)++] = beginorbitidx;
264
265  /* stop if all variables are covered */
266  if ( nvaradded >= nmovedpermvars )
267  break;
268  }
269
270  /* store end in "last" orbitbegins entry */
271  assert( *norbits < npermvars );
272  orbitbegins[*norbits] = orbitidx;
273
274 #ifdef SCIP_OUTPUT
275  printf("Orbits (total number: %d):\n", *norbits);
276  for (i = 0; i < *norbits; ++i)
277  {
278  int j;
279
280  printf("%d: ", i);
281  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
282  printf("%d ", orbits[j]);
283  printf("\n");
284  }
285 #endif
286
287  /* free memory */
289
290  return SCIP_OKAY;
291 }
292
293
294 /** compute non-trivial orbits of symmetry group
295  *
296  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
297  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
298  * consecutively in the orbits array. The variables of the i-th orbit have indices
299  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
300  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
301  *
302  * This function is adapted from computeGroupOrbitsFilter().
303  */
305  SCIP* scip, /**< SCIP instance */
306  int npermvars, /**< length of a permutation array */
307  int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
308  int nperms, /**< number of permutations encoded in perms */
309  int* components, /**< array containing the indices of permutations sorted by components */
310  int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
311  int* vartocomponent, /**< array containing for each permvar the index of the component it is
312  * contained in (-1 if not affected) */
313  int ncomponents, /**< number of components of symmetry group */
314  int* orbits, /**< array of non-trivial orbits */
315  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
316  int* norbits, /**< pointer to number of orbits currently stored in orbits */
317  int* varorbitmap /**< array for storing the orbits for each variable */
318  )
319 {
321  int orbitidx = 0;
322  int i;
323
324  assert( scip != NULL );
325  assert( permstrans != NULL );
326  assert( nperms > 0 );
327  assert( npermvars > 0 );
328  assert( components != NULL );
329  assert( componentbegins != NULL );
330  assert( vartocomponent != NULL );
331  assert( ncomponents > 0 );
332  assert( orbits != NULL );
333  assert( orbitbegins != NULL );
334  assert( norbits != NULL );
335  assert( varorbitmap != NULL );
336
337  /* init data structures */
338  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
339
340  /* initially, every variable is contained in no orbit */
341  for (i = 0; i < npermvars; ++i)
342  {
344  varorbitmap[i] = -1;
345  }
346
347  /* find variable orbits */
348  *norbits = 0;
349  for (i = 0; i < npermvars; ++i)
350  {
351  int beginorbitidx;
352  int componentidx;
353  int j;
354
355  /* skip unaffected variables - note that we also include blocked components */
356  componentidx = vartocomponent[i];
357  if ( componentidx < 0 )
358  continue;
359
360  /* skip variable already contained in an orbit of a previous variable */
362  continue;
363
364  /* store first variable */
365  beginorbitidx = orbitidx;
366  orbits[orbitidx++] = i;
368  varorbitmap[i] = *norbits;
369
370  /* iterate over variables in curorbit and compute their images */
371  j = beginorbitidx;
372  while ( j < orbitidx )
373  {
374  int* pt;
375  int curelem;
376  int image;
377  int p;
378
379  curelem = orbits[j];
380
381  pt = permstrans[curelem];
382  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
383  {
384  int perm;
385
386  perm = components[p];
387  image = pt[perm];
388  assert( vartocomponent[image] == componentidx );
389
390  /* found new element of the orbit of i */
391  if ( ! varadded[image] )
392  {
393  orbits[orbitidx++] = image;
394  assert( orbitidx <= npermvars );
396  varorbitmap[image] = *norbits;
397  }
398  }
399  ++j;
400  }
401
402  /* if the orbit is trivial, reset storage, otherwise store orbit */
403  if ( orbitidx <= beginorbitidx + 1 )
404  {
405  orbitidx = beginorbitidx;
406  varorbitmap[i] = -1;
407  }
408  else
409  orbitbegins[(*norbits)++] = beginorbitidx;
410  }
411
412  /* store end in "last" orbitbegins entry */
413  assert( *norbits < npermvars );
414  orbitbegins[*norbits] = orbitidx;
415
416  /* free memory */
418
419  return SCIP_OKAY;
420 }
421
422
423 /** check whether a permutation is a composition of 2-cycles of binary variables and in this case determine the number of 2-cycles */
425  int* perm, /**< permutation */
426  SCIP_VAR** vars, /**< array of variables perm is acting on */
427  int nvars, /**< number of variables */
428  SCIP_Bool* iscompoftwocycles, /**< pointer to store whether permutation is a composition of 2-cycles */
429  int* ntwocyclesperm, /**< pointer to store number of 2-cycles */
430  SCIP_Bool* allvarsbinary /**< pointer to store whether perm is acting on binary variables only */
431  )
432 {
433  int ntwocycles = 0;
434  int i;
435
436  assert( perm != NULL );
437  assert( vars != NULL );
438  assert( iscompoftwocycles != NULL );
439  assert( ntwocyclesperm != NULL );
440  assert( allvarsbinary != NULL );
441
442  *iscompoftwocycles = FALSE;
443  *ntwocyclesperm = 0;
444  *allvarsbinary = TRUE;
445  for (i = 0; i < nvars; ++i)
446  {
447  /* skip fixed points and avoid treating the same 2-cycle twice */
448  if ( perm[i] <= i )
449  continue;
450
451  if ( perm[perm[i]] == i )
452  {
453  if ( SCIPvarIsBinary(vars[i]) && SCIPvarIsBinary(vars[perm[i]]) )
454  ++ntwocycles;
455  else
456  {
457  /* at least one variable is not binary */
458  *allvarsbinary = FALSE;
459  return SCIP_OKAY;
460  }
461  }
462  else
463  {
464  /* we do not have a 2-cycle */
465  return SCIP_OKAY;
466  }
467  }
468
469  /* at this point the permutation is a composition of 2-cycles on binary variables */
470  *iscompoftwocycles = TRUE;
471  *ntwocyclesperm = ntwocycles;
472
473  return SCIP_OKAY;
474 }
475
476
477 /** determine number of variables affected by symmetry group */
479  SCIP* scip, /**< SCIP instance */
480  int** perms, /**< permutations */
481  int nperms, /**< number of permutations in perms */
482  SCIP_VAR** permvars, /**< variables corresponding to permutations */
483  int npermvars, /**< number of permvars in perms */
484  int* nvarsaffected /**< pointer to store number of all affected variables */
485  )
486 {
487  SCIP_Shortbool* affected;
488  int i;
489  int p;
490
491  assert( scip != NULL );
492  assert( perms != NULL );
493  assert( nperms > 0 );
494  assert( permvars != NULL );
495  assert( npermvars > 0 );
496  assert( nvarsaffected != NULL );
497
498  *nvarsaffected = 0;
499
500  SCIP_CALL( SCIPallocClearBufferArray(scip, &affected, npermvars) );
501
502  /* iterate over permutations and check which variables are affected by some symmetry */
503  for (p = 0; p < nperms; ++p)
504  {
505  for (i = 0; i < npermvars; ++i)
506  {
507  if ( affected[i] )
508  continue;
509
510  if ( perms[p][i] != i )
511  {
512  affected[i] = TRUE;
513  ++(*nvarsaffected);
514  }
515  }
516  }
517  SCIPfreeBufferArray(scip, &affected);
518
519  return SCIP_OKAY;
520 }
521
522
523 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
524  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
525  * we add one column to the suborbitope of the first nfilledcols columns.
526  *
527  * @pre Every non-trivial cycle of perm is a 2-cycle.
528  * @pre perm has nrows many 2-cycles
529  */
531  int** suborbitope, /**< matrix containing suborbitope entries */
532  int nrows, /**< number of rows of suborbitope */
533  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
534  int coltoextend, /**< index of column that should be extended by perm */
535  int* perm, /**< permutation */
536  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
537  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
538  SCIP_Bool* success, /**< pointer to store whether extension was successful */
539  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
540  )
541 {
542  int nintersections = 0;
543  int row;
544  int idx1;
545  int idx2;
546
547  assert( suborbitope != NULL );
548  assert( nrows > 0 );
549  assert( nfilledcols > 0 );
550  assert( coltoextend >= 0 );
551  assert( perm != NULL );
552  assert( nusedelems != NULL );
553  assert( success != NULL );
554  assert( infeasible != NULL );
555
556  *success = FALSE;
557  *infeasible = FALSE;
558
559  /* if we try to extend the first orbitope generator by another one,
560  * we can change the order of entries in each row of suborbitope */
561  if ( nfilledcols == 2 )
562  {
563  /* check whether each cycle of perm intersects with a row of suborbitope */
564  for (row = 0; row < nrows; ++row)
565  {
566  idx1 = suborbitope[row][0];
567  idx2 = suborbitope[row][1];
568
569  /* if idx1 or idx2 is affected by perm, we can extend the row of the orbitope */
570  if ( idx1 != perm[idx1] )
571  {
572  /* change order of idx1 and idx2 for right extensions */
573  if ( ! leftextension )
574  {
575  suborbitope[row][0] = idx2;
576  suborbitope[row][1] = idx1;
577  }
578  suborbitope[row][2] = perm[idx1];
579  ++nintersections;
580
581  (*nusedelems)[idx1] += 1;
582  (*nusedelems)[perm[idx1]] += 1;
583
584  /* if an element appears too often in the orbitope matrix */
585  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
586  {
587  *infeasible = TRUE;
588  break;
589  }
590  }
591  else if ( idx2 != perm[idx2] )
592  {
593  /* change order of idx1 and idx2 for left extensions */
594  if ( leftextension )
595  {
596  suborbitope[row][0] = idx2;
597  suborbitope[row][1] = idx1;
598  }
599  suborbitope[row][2] = perm[idx2];
600  ++nintersections;
601
602  (*nusedelems)[idx2] += 1;
603  (*nusedelems)[perm[idx2]] += 1;
604
605  /* if an element appears too often in the orbitope matrix */
606  if ( (*nusedelems)[idx2] > 2 || (*nusedelems)[perm[idx2]] > 2 )
607  {
608  *infeasible = TRUE;
609  break;
610  }
611  }
612  }
613  }
614  else
615  {
616  /* check whether each cycle of perm intersects with a row of suborbitope */
617  for (row = 0; row < nrows; ++row)
618  {
619  idx1 = suborbitope[row][coltoextend];
620
621  /* if idx1 is affected by perm, we can extend the row of the orbitope */
622  if ( idx1 != perm[idx1] )
623  {
624  suborbitope[row][nfilledcols] = perm[idx1];
625  ++nintersections;
626
627  (*nusedelems)[idx1] += 1;
628  (*nusedelems)[perm[idx1]] += 1;
629
630  /* if an element appears to often in the orbitope matrix */
631  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
632  {
633  *infeasible = TRUE;
634  break;
635  }
636  }
637  }
638  }
639
640  /* if there are too few intersection, this is not an orbitope */
641  if ( nintersections > 0 && nintersections < nrows )
642  *infeasible = TRUE;
643  else if ( nintersections == nrows )
644  *success = TRUE;
645
646  return SCIP_OKAY;
647 }
648
649
650 /** compute components of symmetry group */
652  SCIP* scip, /**< SCIP instance */
653  int** perms, /**< permutation generators as
654  * (either nperms x npermvars or npermvars x nperms) matrix */
655  int nperms, /**< number of permutations */
656  SCIP_VAR** permvars, /**< variables on which permutations act */
657  int npermvars, /**< number of variables for permutations */
658  SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
659  int** components, /**< array containing the indices of permutations sorted by components */
660  int** componentbegins, /**< array containing in i-th position the first position of
661  * component i in components array */
662  int** vartocomponent, /**< array containing for each permvar the index of the component it is
663  * contained in (-1 if not affected) */
664  SCIP_Shortbool** componentblocked, /**< array to store whether a component is blocked to be considered by
665  * further symmetry handling techniques */
666  int* ncomponents /**< pointer to store number of components of symmetry group */
667  )
668 {
669  SCIP_DISJOINTSET* componentstovar = NULL;
670  int* permtovarcomp;
671  int* permtocomponent;
672  int p;
673  int i;
674  int idx;
675
676  assert( scip != NULL );
677  assert( permvars != NULL );
678  assert( npermvars > 0 );
679  assert( perms != NULL );
680  assert( components != NULL );
681  assert( componentbegins != NULL );
682  assert( vartocomponent != NULL );
683  assert( componentblocked != NULL );
684  assert( ncomponents != NULL );
685
686  if ( nperms <= 0 )
687  return SCIP_OKAY;
688
689  SCIP_CALL( SCIPdisjointsetCreate(&componentstovar, SCIPblkmem(scip), npermvars) );
690  *ncomponents = npermvars;
691
692  /* init array that stores for each permutation the representative of its affected variables */
693  SCIP_CALL( SCIPallocBufferArray(scip, &permtovarcomp, nperms) );
694  for (p = 0; p < nperms; ++p)
695  permtovarcomp[p] = -1;
696
697  /* find permutation components and store for each variable an affecting permutation (or -1) */
698  SCIP_CALL( SCIPallocBlockMemoryArray(scip, vartocomponent, npermvars) );
699  for (i = 0; i < npermvars; ++i)
700  {
701  (*vartocomponent)[i] = -1;
702
703  for (p = 0; p < nperms; ++p)
704  {
705  int img;
706
707  img = transposed ? perms[i][p] : perms[p][i];
708
709  /* perm p affects i -> possibly merge var components */
710  if ( img != i )
711  {
712  int component1;
713  int component2;
714  int representative;
715
716  component1 = SCIPdisjointsetFind(componentstovar, i);
717  component2 = SCIPdisjointsetFind(componentstovar, img);
718  (*vartocomponent)[i] = p;
719  (*vartocomponent)[img] = p;
720
721  /* ensure component1 <= component2 */
722  if ( component2 < component1 )
723  {
724  int swap;
725
726  swap = component1;
727  component1 = component2;
728  component2 = swap;
729  }
730
731  /* init permtovarcomp[p] to component of first moved variable or update the value */
732  if ( permtovarcomp[p] == -1 )
733  {
734  permtovarcomp[p] = component1;
735  representative = component1;
736  }
737  else
738  {
739  permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
740  representative = permtovarcomp[p];
741  }
742
743  /* merge both components if they differ */
744  if ( component1 != component2 )
745  {
746  SCIPdisjointsetUnion(componentstovar, component1, component2, TRUE);
747  --(*ncomponents);
748  }
749
750  /* possibly merge new component and permvartocom[p] and ensure the latter
751  * to have the smallest value */
752  if ( representative != component1 && representative != component2 )
753  {
754  if ( representative > component1 )
755  {
756  SCIPdisjointsetUnion(componentstovar, component1, representative, TRUE);
757  permtovarcomp[p] = component1;
758  }
759  else
760  SCIPdisjointsetUnion(componentstovar, representative, component1, TRUE);
761  --(*ncomponents);
762  }
763  else if ( representative > component1 )
764  {
765  assert( representative == component2 );
766  permtovarcomp[p] = component1;
767  }
768  }
769  }
770
771  /* reduce number of components by singletons */
772  if ( (*vartocomponent)[i] == -1 )
773  --(*ncomponents);
774  }
775  assert( *ncomponents > 0 );
776
777  /* update permvartocomp array to final variable representatives */
778  for (p = 0; p < nperms; ++p)
779  permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
780
781  /* init components array by trivial natural order of permutations */
782  SCIP_CALL( SCIPallocBlockMemoryArray(scip, components, nperms) );
783  for (p = 0; p < nperms; ++p)
784  (*components)[p] = p;
785
786  /* get correct order of components array */
787  SCIPsortIntInt(permtovarcomp, *components, nperms);
788
789  /* determine componentbegins and store components for each permutation */
790  SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentbegins, *ncomponents + 1) );
791  SCIP_CALL( SCIPallocBufferArray(scip, &permtocomponent, nperms) );
792
793  (*componentbegins)[0] = 0;
794  permtocomponent[(*components)[0]] = 0;
795  idx = 0;
796
797  for (p = 1; p < nperms; ++p)
798  {
799  if ( permtovarcomp[p] > permtovarcomp[p - 1] )
800  (*componentbegins)[++idx] = p;
801
802  assert( (*components)[p] >= 0 );
803  assert( (*components)[p] < nperms );
804  permtocomponent[(*components)[p]] = idx;
805  }
806  assert( *ncomponents == idx + 1 );
807  (*componentbegins)[++idx] = nperms;
808
809  /* determine vartocomponent */
810  for (i = 0; i < npermvars; ++i)
811  {
812  int permidx;
813  permidx = (*vartocomponent)[i];
814  assert( -1 <= permidx && permidx < nperms );
815
816  if ( permidx != -1 )
817  {
818  assert( 0 <= permtocomponent[permidx] );
819  assert( permtocomponent[permidx] < *ncomponents );
820
821  (*vartocomponent)[i] = permtocomponent[permidx];
822  }
823  }
824
825  /* init componentblocked */
826  SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentblocked, *ncomponents) );
827  for (i = 0; i < *ncomponents; ++i)
828  (*componentblocked)[i] = FALSE;
829
830  SCIPfreeBufferArray(scip, &permtocomponent);
831  SCIPfreeBufferArray(scip, &permtovarcomp);
832  SCIPdisjointsetFree(&componentstovar, SCIPblkmem(scip));
833
834 #ifdef SCIP_OUTPUT
835  printf("number of components: %d\n", propdata->ncomponents);
836  for (i = 0; i < *ncomponents; ++i)
837  {
838  printf("Component %d contains the following permutations:\n\t", i);
839  for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
840  {
841  printf("%d, ", (*components)[p]);
842  }
843  printf("\n");
844  }
845 #endif
846
847  return SCIP_OKAY;
848 }
849
850
851 /** generate variable matrix for orbitope constraint handler */
853  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
854  int nrows, /**< number of rows of orbitope */
855  int ncols, /**< number of columns of orbitope */
856  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
857  int npermvars, /**< number of variables in permvars array */
858  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
859  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
860  int* nusedelems, /**< array storing how often an element was used in the orbitope */
861  SCIP_Bool* infeasible /**< pointer to store whether the potential orbitope is not an orbitope */
862  )
863 {
864  int nfilledcols = 0;
865  int curcolumn;
866  int i;
867
868  assert( vars != NULL );
869  assert( nrows > 0 );
870  assert( ncols > 0 );
871  assert( permvars != NULL );
872  assert( npermvars > 0 );
873  assert( orbitopevaridx != NULL );
874  assert( columnorder != NULL );
875  assert( nusedelems != NULL );
876  assert( infeasible != NULL );
877
878  curcolumn = ncols - 1;
879
880  /* start filling vars matrix with the right-most column w.r.t. columnorder */
881  while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 )
882  {
883  for (i = 0; i < nrows; ++i)
884  {
885  assert( orbitopevaridx[i][curcolumn] < npermvars );
886  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
887
888  /* elements in first column of orbitope have to appear exactly once in the orbitope */
889  if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
890  {
891  *infeasible = TRUE;
892  break;
893  }
894
895  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
896  }
897  --curcolumn;
898  ++nfilledcols;
899  }
900
901  /* There are three possibilities for the structure of columnorder:
902  * 1) [0, 1, -1, -1, ..., -1]
903  * 2) [0, 1, 1, 1, ..., 1]
904  * 3) [0, 1, -1, -1, ...., -1, 1, 1, ..., 1]
905  */
906  /* Either we are in case 1) or case 3), or all columns should have been added to vars in case 2) */
907  assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
908
909  if ( curcolumn > 1 )
910  {
911  /* add column with columnorder 1 to vars */
912  for (i = 0; i < nrows; ++i)
913  {
914  assert( orbitopevaridx[i][1] < npermvars );
915  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][1]]) );
916
917  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][1]];
918  }
919  ++nfilledcols;
920
921  /* add column with columnorder 0 to vars */
922  for (i = 0; i < nrows; ++i)
923  {
924  assert( orbitopevaridx[i][0] < npermvars );
925  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][0]]) );
926
927  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][0]];
928  }
929  ++nfilledcols;
930
931  /* add columns with a negative column order to vars */
932  if ( nfilledcols < ncols )
933  {
934  assert( ncols > 2 );
935
936  curcolumn = 2;
937  while ( nfilledcols < ncols )
938  {
939  assert( columnorder[curcolumn] < 0 );
940
941  for (i = 0; i < nrows; ++i)
942  {
943  assert( orbitopevaridx[i][curcolumn] < npermvars );
944  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
945
946  /* elements in last column of orbitope have to appear exactly once in the orbitope */
947  if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
948  {
949  *infeasible = TRUE;
950  break;
951  }
952
953  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
954  }
955  ++curcolumn;
956  ++nfilledcols;
957  }
958  }
959  }
960
961  return SCIP_OKAY;
962 }
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:10997
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:478
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, SCIP_Shortbool *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:152
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:38
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11075
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11024
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
Definition: symmetry.c:852
SCIP_RETCODE SCIPgetPropertiesPerm(int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
Definition: symmetry.c:424
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_Shortbool
Definition: def.h:78
#define SCIP_CALL(x)
Definition: def.h:370
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:530
SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(SCIP *scip, int npermvars, int **permstrans, int nperms, int *components, int *componentbegins, int *vartocomponent, int ncomponents, int *orbits, int *orbitbegins, int *norbits, int *varorbitmap)
Definition: symmetry.c:304
methods for handling symmetries
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, SCIP_Shortbool **componentblocked, int *ncomponents)
Definition: symmetry.c:651
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:10957
SCIP callable library.