Scippy

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 /* */
6 /* Copyright (C) 2002-2022 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 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 #include "scip/cons_setppc.h"
29 #include <symmetry/type_symmetry.h>
30 
31 
32 /** compute non-trivial orbits of symmetry group
33  *
34  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
35  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
36  * consecutively in the orbits array. The variables of the i-th orbit have indices
37  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
38  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
39  */
41  SCIP* scip, /**< SCIP instance */
42  SCIP_VAR** permvars, /**< variables considered in a permutation */
43  int npermvars, /**< length of a permutation array */
44  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
45  int nperms, /**< number of permutations encoded in perms */
46  int* orbits, /**< array of non-trivial orbits */
47  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
48  int* norbits /**< pointer to number of orbits currently stored in orbits */
49  )
50 {
51  SCIP_Shortbool* varadded;
52  int orbitidx = 0;
53  int i;
54 
55  assert( scip != NULL );
56  assert( permvars != NULL );
57  assert( perms != NULL );
58  assert( nperms > 0 );
59  assert( npermvars > 0 );
60  assert( orbits != NULL );
61  assert( orbitbegins != NULL );
62  assert( norbits != NULL );
63 
64  /* init data structures*/
65  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
66 
67  /* initially, every variable is contained in no orbit */
68  for (i = 0; i < npermvars; ++i)
69  varadded[i] = FALSE;
70 
71  /* find variable orbits */
72  *norbits = 0;
73  for (i = 0; i < npermvars; ++i)
74  {
75  int beginorbitidx;
76  int j;
77 
78  /* skip variable already contained in an orbit of a previous variable */
79  if ( varadded[i] )
80  continue;
81 
82  /* store first variable */
83  beginorbitidx = orbitidx;
84  orbits[orbitidx++] = i;
85  varadded[i] = TRUE;
86 
87  /* iterate over variables in curorbit and compute their images */
88  j = beginorbitidx;
89  while ( j < orbitidx )
90  {
91  int curelem;
92  int image;
93  int p;
94 
95  curelem = orbits[j];
96 
97  for (p = 0; p < nperms; ++p)
98  {
99  image = perms[p][curelem];
100 
101  /* found new element of the orbit of i */
102  if ( ! varadded[image] )
103  {
104  orbits[orbitidx++] = image;
105  assert( orbitidx <= npermvars );
106  varadded[image] = TRUE;
107  }
108  }
109  ++j;
110  }
111 
112  /* if the orbit is trivial, reset storage, otherwise store orbit */
113  if ( orbitidx <= beginorbitidx + 1 )
114  orbitidx = beginorbitidx;
115  else
116  orbitbegins[(*norbits)++] = beginorbitidx;
117  }
118 
119  /* store end in "last" orbitbegins entry */
120  assert( *norbits < npermvars );
121  orbitbegins[*norbits] = orbitidx;
122 
123 #ifdef SCIP_OUTPUT
124  printf("Orbits (total number: %d):\n", *norbits);
125  for (i = 0; i < *norbits; ++i)
126  {
127  int j;
128 
129  printf("%d: ", i);
130  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
131  printf("%d ", orbits[j]);
132  printf("\n");
133  }
134 #endif
135 
136  /* free memory */
137  SCIPfreeBufferArray(scip, &varadded);
138 
139  return SCIP_OKAY;
140 }
141 
142 
143 /** compute non-trivial orbits of symmetry group using filtered generators
144  *
145  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
146  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
147  * consecutively in the orbits array. The variables of the i-th orbit have indices
148  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
149  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
150  *
151  * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
152  * filter out permutations.
153  */
155  SCIP* scip, /**< SCIP instance */
156  int npermvars, /**< length of a permutation array */
157  int** permstrans, /**< transposed matrix containing in each column a
158  * permutation of the symmetry group */
159  int nperms, /**< number of permutations encoded in perms */
160  SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
161  int* orbits, /**< array of non-trivial orbits */
162  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
163  int* norbits, /**< pointer to number of orbits currently stored in orbits */
164  int* components, /**< array containing the indices of permutations sorted by components */
165  int* componentbegins, /**< array containing in i-th position the first position of
166  * component i in components array */
167  int* vartocomponent, /**< array containing for each permvar the index of the component it is
168  * contained in (-1 if not affected) */
169  unsigned* componentblocked, /**< array to store which symmetry methods have been used on a component
170  * using the same bitset information as for misc/usesymmetry */
171  int ncomponents, /**< number of components of symmetry group */
172  int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
173  * that is handled by orbital fixing */
174  )
175 {
176  SCIP_Shortbool* varadded;
177  int nvaradded = 0;
178  int orbitidx = 0;
179  int i;
180 
181  assert( scip != NULL );
182  assert( permstrans != NULL );
183  assert( nperms > 0 );
184  assert( npermvars > 0 );
185  assert( inactiveperms != NULL );
186  assert( orbits != NULL );
187  assert( orbitbegins != NULL );
188  assert( norbits != NULL );
189  assert( components != NULL );
190  assert( componentbegins != NULL );
191  assert( vartocomponent != NULL );
192  assert( ncomponents > 0 );
193  assert( nmovedpermvars > 0 );
194 
195  /* init data structures */
196  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
197 
198  /* initially, every variable is contained in no orbit */
199  for (i = 0; i < npermvars; ++i)
200  varadded[i] = FALSE;
201 
202  /* find variable orbits */
203  *norbits = 0;
204  for (i = 0; i < npermvars; ++i)
205  {
206  int beginorbitidx;
207  int componentidx;
208  int j;
209 
210  /* skip unaffected variables and blocked components */
211  componentidx = vartocomponent[i];
212  if ( componentidx < 0 || componentblocked[componentidx] )
213  continue;
214 
215  /* skip variable already contained in an orbit of a previous variable */
216  if ( varadded[i] )
217  continue;
218 
219  /* store first variable */
220  beginorbitidx = orbitidx;
221  orbits[orbitidx++] = i;
222  varadded[i] = TRUE;
223  ++nvaradded;
224 
225  /* iterate over variables in curorbit and compute their images */
226  j = beginorbitidx;
227  while ( j < orbitidx )
228  {
229  int* pt;
230  int curelem;
231  int image;
232  int p;
233 
234  curelem = orbits[j];
235 
236  pt = permstrans[curelem];
237  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
238  {
239  int perm;
240 
241  perm = components[p];
242 
243  if ( ! inactiveperms[perm] )
244  {
245  image = pt[perm];
246  assert( vartocomponent[image] == componentidx );
247 
248  /* found new element of the orbit of i */
249  if ( ! varadded[image] )
250  {
251  orbits[orbitidx++] = image;
252  assert( orbitidx <= npermvars );
253  varadded[image] = TRUE;
254  ++nvaradded;
255  }
256  }
257  }
258  ++j;
259  }
260 
261  /* if the orbit is trivial, reset storage, otherwise store orbit */
262  if ( orbitidx <= beginorbitidx + 1 )
263  orbitidx = beginorbitidx;
264  else
265  orbitbegins[(*norbits)++] = beginorbitidx;
266 
267  /* stop if all variables are covered */
268  if ( nvaradded >= nmovedpermvars )
269  break;
270  }
271 
272  /* store end in "last" orbitbegins entry */
273  assert( *norbits < npermvars );
274  orbitbegins[*norbits] = orbitidx;
275 
276 #ifdef SCIP_OUTPUT
277  printf("Orbits (total number: %d):\n", *norbits);
278  for (i = 0; i < *norbits; ++i)
279  {
280  int j;
281 
282  printf("%d: ", i);
283  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
284  printf("%d ", orbits[j]);
285  printf("\n");
286  }
287 #endif
288 
289  /* free memory */
290  SCIPfreeBufferArray(scip, &varadded);
291 
292  return SCIP_OKAY;
293 }
294 
295 /** Compute orbit of a given variable and store it in @p orbit. The first entry of the orbit will
296  * be the given variable index and the rest is filled with the remaining variables excluding
297  * the ones specified in @p ignoredvars.
298  *
299  * @pre orbit is an initialized array of size propdata->npermvars
300  * @pre at least one of @p perms and @p permstrans should not be NULL
301  */
303  SCIP* scip, /**< SCIP instance */
304  int npermvars, /**< number of variables in permvars */
305  int** perms, /**< the generators of the permutation group (or NULL) */
306  int** permstrans, /**< the transposed matrix of generators (or NULL) */
307  int* components, /**< the components of the permutation group */
308  int* componentbegins, /**< array containing the starting index of each component */
309  SCIP_Shortbool* ignoredvars, /**< array indicating which variables should be ignored */
310  SCIP_Shortbool* varfound, /**< bitmap to mark which variables have been added (or NULL) */
311  int varidx, /**< index of variable for which the orbit is requested */
312  int component, /**< component that var is in */
313  int* orbit, /**< array in which the orbit should be stored */
314  int* orbitsize /**< buffer to store the size of the orbit */
315  )
316 { /*lint --e{571}*/
317  SCIP_Shortbool* varadded;
318  int* varstotest;
319  int nvarstotest;
320  int j;
321  int p;
322 
323  assert( scip != NULL );
324  assert( perms != NULL || permstrans != NULL );
325  assert( components != NULL );
326  assert( componentbegins != NULL );
327  assert( ignoredvars != NULL );
328  assert( orbit != NULL );
329  assert( orbitsize != NULL );
330  assert( 0 <= varidx && varidx < npermvars );
331  assert( component >= 0 );
332  assert( npermvars > 0 );
333 
334  /* init data structures*/
335  SCIP_CALL( SCIPallocClearBufferArray(scip, &varadded, npermvars) );
336  SCIP_CALL( SCIPallocClearBufferArray(scip, &varstotest, npermvars) );
337 
338  /* compute and store orbit if it is non-trivial */
339  orbit[0] = varidx;
340  varstotest[0] = varidx;
341  *orbitsize = 1;
342  nvarstotest = 1;
343  varadded[varidx] = TRUE;
344 
345  if ( varfound != NULL )
346  varfound[varidx] = TRUE;
347 
348  /* iterate over variables in orbit and compute their images */
349  j = 0;
350  while ( j < nvarstotest )
351  {
352  int currvar;
353 
354  currvar = varstotest[j++];
355 
356  for (p = componentbegins[component]; p < componentbegins[component+1]; ++p)
357  {
358  int image;
359  int comp;
360 
361  comp = components[p];
362 
363  if ( perms != NULL )
364  image = perms[comp][currvar]; /*lint !e613*/
365  else
366  image = permstrans[currvar][comp];
367 
368  /* found new element of the orbit of varidx */
369  if ( ! varadded[image] )
370  {
371  varstotest[nvarstotest++] = image;
372  varadded[image] = TRUE;
373 
374  if ( ! ignoredvars[image] )
375  {
376  orbit[(*orbitsize)++] = image;
377 
378  if ( varfound != NULL )
379  varfound[image] = TRUE;
380  }
381  }
382  }
383  }
384 
385  /* free memory */
386  SCIPfreeBufferArray(scip, &varstotest);
387  SCIPfreeBufferArray(scip, &varadded);
388 
389  return SCIP_OKAY;
390 }
391 
392 /** compute non-trivial orbits of symmetry group
393  *
394  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
395  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
396  * consecutively in the orbits array. The variables of the i-th orbit have indices
397  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
398  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
399  *
400  * This function is adapted from computeGroupOrbitsFilter().
401  */
403  SCIP* scip, /**< SCIP instance */
404  int npermvars, /**< length of a permutation array */
405  int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
406  int nperms, /**< number of permutations encoded in perms */
407  int* components, /**< array containing the indices of permutations sorted by components */
408  int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
409  int* vartocomponent, /**< array containing for each permvar the index of the component it is
410  * contained in (-1 if not affected) */
411  int ncomponents, /**< number of components of symmetry group */
412  int* orbits, /**< array of non-trivial orbits */
413  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
414  int* norbits, /**< pointer to number of orbits currently stored in orbits */
415  int* varorbitmap /**< array for storing the orbits for each variable */
416  )
417 {
418  SCIP_Shortbool* varadded;
419  int orbitidx = 0;
420  int i;
421 
422  assert( scip != NULL );
423  assert( permstrans != NULL );
424  assert( nperms > 0 );
425  assert( npermvars > 0 );
426  assert( components != NULL );
427  assert( componentbegins != NULL );
428  assert( vartocomponent != NULL );
429  assert( ncomponents > 0 );
430  assert( orbits != NULL );
431  assert( orbitbegins != NULL );
432  assert( norbits != NULL );
433  assert( varorbitmap != NULL );
434 
435  /* init data structures */
436  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
437 
438  /* initially, every variable is contained in no orbit */
439  for (i = 0; i < npermvars; ++i)
440  {
441  varadded[i] = FALSE;
442  varorbitmap[i] = -1;
443  }
444 
445  /* find variable orbits */
446  *norbits = 0;
447  for (i = 0; i < npermvars; ++i)
448  {
449  int beginorbitidx;
450  int componentidx;
451  int j;
452 
453  /* skip unaffected variables - note that we also include blocked components */
454  componentidx = vartocomponent[i];
455  if ( componentidx < 0 )
456  continue;
457 
458  /* skip variable already contained in an orbit of a previous variable */
459  if ( varadded[i] )
460  continue;
461 
462  /* store first variable */
463  beginorbitidx = orbitidx;
464  orbits[orbitidx++] = i;
465  varadded[i] = TRUE;
466  varorbitmap[i] = *norbits;
467 
468  /* iterate over variables in curorbit and compute their images */
469  j = beginorbitidx;
470  while ( j < orbitidx )
471  {
472  int* pt;
473  int curelem;
474  int image;
475  int p;
476 
477  curelem = orbits[j];
478 
479  pt = permstrans[curelem];
480  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
481  {
482  int perm;
483 
484  perm = components[p];
485  image = pt[perm];
486  assert( vartocomponent[image] == componentidx );
487 
488  /* found new element of the orbit of i */
489  if ( ! varadded[image] )
490  {
491  orbits[orbitidx++] = image;
492  assert( orbitidx <= npermvars );
493  varadded[image] = TRUE;
494  varorbitmap[image] = *norbits;
495  }
496  }
497  ++j;
498  }
499 
500  /* if the orbit is trivial, reset storage, otherwise store orbit */
501  if ( orbitidx <= beginorbitidx + 1 )
502  {
503  orbitidx = beginorbitidx;
504  varorbitmap[i] = -1;
505  }
506  else
507  orbitbegins[(*norbits)++] = beginorbitidx;
508  }
509 
510  /* store end in "last" orbitbegins entry */
511  assert( *norbits < npermvars );
512  orbitbegins[*norbits] = orbitidx;
513 
514  /* free memory */
515  SCIPfreeBufferArray(scip, &varadded);
516 
517  return SCIP_OKAY;
518 }
519 
520 
521 /** Checks whether a permutation is a composition of 2-cycles and in this case determines the number of overall
522  * 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff @p ntwocyclesperm > 0 upon termination.
523  */
525  int* perm, /**< permutation */
526  SCIP_VAR** vars, /**< array of variables perm is acting on */
527  int nvars, /**< number of variables */
528  int* ntwocyclesperm, /**< pointer to store number of 2-cycles or 0 if perm is not an involution */
529  int* nbincyclesperm, /**< pointer to store number of binary cycles */
530  SCIP_Bool earlytermination /**< whether we terminate early if not all affected variables are binary */
531  )
532 {
533  int ntwocycles = 0;
534  int i;
535 
536  assert( perm != NULL );
537  assert( vars != NULL );
538  assert( ntwocyclesperm != NULL );
539  assert( nbincyclesperm != NULL );
540 
541  *ntwocyclesperm = 0;
542  *nbincyclesperm = 0;
543  for (i = 0; i < nvars; ++i)
544  {
545  assert( 0 <= perm[i] && perm[i] < nvars );
546 
547  /* skip fixed points and avoid treating the same 2-cycle twice */
548  if ( perm[i] <= i )
549  continue;
550 
551  if ( perm[perm[i]] == i )
552  {
553  if ( SCIPvarIsBinary(vars[i]) && SCIPvarIsBinary(vars[perm[i]]) )
554  ++(*nbincyclesperm);
555  else if ( earlytermination )
556  return SCIP_OKAY;
557 
558  ++ntwocycles;
559  }
560  else
561  {
562  /* we do not have only 2-cycles */
563  return SCIP_OKAY;
564  }
565  }
566 
567  /* at this point the permutation is a composition of 2-cycles */
568  *ntwocyclesperm = ntwocycles;
569 
570  return SCIP_OKAY;
571 }
572 
573 
574 /** determine number of variables affected by symmetry group */
576  SCIP* scip, /**< SCIP instance */
577  int** perms, /**< permutations */
578  int nperms, /**< number of permutations in perms */
579  SCIP_VAR** permvars, /**< variables corresponding to permutations */
580  int npermvars, /**< number of permvars in perms */
581  int* nvarsaffected /**< pointer to store number of all affected variables */
582  )
583 {
584  SCIP_Shortbool* affected;
585  int i;
586  int p;
587 
588  assert( scip != NULL );
589  assert( perms != NULL );
590  assert( nperms > 0 );
591  assert( permvars != NULL );
592  assert( npermvars > 0 );
593  assert( nvarsaffected != NULL );
594 
595  *nvarsaffected = 0;
596 
597  SCIP_CALL( SCIPallocClearBufferArray(scip, &affected, npermvars) );
598 
599  /* iterate over permutations and check which variables are affected by some symmetry */
600  for (p = 0; p < nperms; ++p)
601  {
602  for (i = 0; i < npermvars; ++i)
603  {
604  if ( affected[i] )
605  continue;
606 
607  if ( perms[p][i] != i )
608  {
609  affected[i] = TRUE;
610  ++(*nvarsaffected);
611  }
612  }
613  }
614  SCIPfreeBufferArray(scip, &affected);
615 
616  return SCIP_OKAY;
617 }
618 
619 
620 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
621  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
622  * we add one column to the suborbitope of the first nfilledcols columns.
623  *
624  * @pre Every non-trivial cycle of perm is a 2-cycle.
625  * @pre perm has nrows many 2-cycles
626  */
628  int** suborbitope, /**< matrix containing suborbitope entries */
629  int nrows, /**< number of rows of suborbitope */
630  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
631  int coltoextend, /**< index of column that should be extended by perm */
632  int* perm, /**< permutation */
633  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
634  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
635  SCIP_VAR** permvars, /**< permutation vars array */
636  SCIP_Shortbool* rowisbinary, /**< array encoding whether variables in an orbitope row are binary (or NULL) */
637  SCIP_Bool* success, /**< pointer to store whether extension was successful */
638  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
639  )
640 {
641  int nintersections = 0;
642  int row;
643  int idx1;
644  int idx2;
645 
646  assert( suborbitope != NULL );
647  assert( nrows > 0 );
648  assert( nfilledcols > 0 );
649  assert( coltoextend >= 0 );
650  assert( perm != NULL );
651  assert( nusedelems != NULL );
652  assert( permvars != NULL );
653  assert( success != NULL );
654  assert( infeasible != NULL );
655 
656  *success = FALSE;
657  *infeasible = FALSE;
658 
659  /* if we try to extend the first orbitope generator by another one,
660  * we can change the order of entries in each row of suborbitope */
661  if ( nfilledcols == 2 )
662  {
663  /* check whether each cycle of perm intersects with a row of suborbitope */
664  for (row = 0; row < nrows; ++row)
665  {
666  idx1 = suborbitope[row][0];
667  idx2 = suborbitope[row][1];
668 
669  /* if idx1 or idx2 is affected by perm, we can extend the row of the orbitope */
670  if ( idx1 != perm[idx1] )
671  {
672  /* change order of idx1 and idx2 for right extensions */
673  if ( ! leftextension )
674  {
675  suborbitope[row][0] = idx2;
676  suborbitope[row][1] = idx1;
677  }
678  assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
679 
680  suborbitope[row][2] = perm[idx1];
681  ++nintersections;
682 
683  ++(*nusedelems)[idx1];
684  ++(*nusedelems)[perm[idx1]];
685 
686  /* if an element appears too often in the orbitope matrix */
687  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
688  {
689  *infeasible = TRUE;
690  break;
691  }
692  }
693  else if ( idx2 != perm[idx2] )
694  {
695  /* change order of idx1 and idx2 for left extensions */
696  if ( leftextension )
697  {
698  suborbitope[row][0] = idx2;
699  suborbitope[row][1] = idx1;
700  }
701  assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
702 
703  suborbitope[row][2] = perm[idx2];
704  ++nintersections;
705 
706  ++(*nusedelems)[idx2];
707  ++(*nusedelems)[perm[idx2]];
708 
709  /* if an element appears too often in the orbitope matrix */
710  if ( (*nusedelems)[idx2] > 2 || (*nusedelems)[perm[idx2]] > 2 )
711  {
712  *infeasible = TRUE;
713  break;
714  }
715  }
716  }
717  }
718  else
719  {
720  /* check whether each cycle of perm intersects with a row of suborbitope */
721  for (row = 0; row < nrows; ++row)
722  {
723  idx1 = suborbitope[row][coltoextend];
724 
725  /* if idx1 is affected by perm, we can extend the row of the orbitope */
726  if ( idx1 != perm[idx1] )
727  {
728  assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
729 
730  suborbitope[row][nfilledcols] = perm[idx1];
731  ++nintersections;
732 
733  ++(*nusedelems)[idx1];
734  ++(*nusedelems)[perm[idx1]];
735 
736  /* if an element appears to often in the orbitope matrix */
737  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
738  {
739  *infeasible = TRUE;
740  break;
741  }
742  }
743  }
744  }
745 
746  /* if there are too few intersection, this is not an orbitope */
747  if ( nintersections > 0 && nintersections < nrows )
748  *infeasible = TRUE;
749  else if ( nintersections == nrows )
750  *success = TRUE;
751 
752  return SCIP_OKAY;
753 }
754 
755 
756 /** compute components of symmetry group */
758  SCIP* scip, /**< SCIP instance */
759  int** perms, /**< permutation generators as
760  * (either nperms x npermvars or npermvars x nperms) matrix */
761  int nperms, /**< number of permutations */
762  SCIP_VAR** permvars, /**< variables on which permutations act */
763  int npermvars, /**< number of variables for permutations */
764  SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
765  int** components, /**< array containing the indices of permutations sorted by components */
766  int** componentbegins, /**< array containing in i-th position the first position of
767  * component i in components array */
768  int** vartocomponent, /**< array containing for each permvar the index of the component it is
769  * contained in (-1 if not affected) */
770  unsigned** componentblocked, /**< array to store which symmetry methods have been used on a component
771  * using the same bitset information as for misc/usesymmetry */
772  int* ncomponents /**< pointer to store number of components of symmetry group */
773  )
774 {
775  SCIP_DISJOINTSET* componentstovar = NULL;
776  int* permtovarcomp;
777  int* permtocomponent;
778  int p;
779  int i;
780  int idx;
781 
782  assert( scip != NULL );
783  assert( permvars != NULL );
784  assert( npermvars > 0 );
785  assert( perms != NULL );
786  assert( components != NULL );
787  assert( componentbegins != NULL );
788  assert( vartocomponent != NULL );
789  assert( componentblocked != NULL );
790  assert( ncomponents != NULL );
791 
792  if ( nperms <= 0 )
793  return SCIP_OKAY;
794 
795  SCIP_CALL( SCIPdisjointsetCreate(&componentstovar, SCIPblkmem(scip), npermvars) );
796  *ncomponents = npermvars;
797 
798  /* init array that stores for each permutation the representative of its affected variables */
799  SCIP_CALL( SCIPallocBufferArray(scip, &permtovarcomp, nperms) );
800  for (p = 0; p < nperms; ++p)
801  permtovarcomp[p] = -1;
802 
803  /* find permutation components and store for each variable an affecting permutation (or -1) */
804  SCIP_CALL( SCIPallocBlockMemoryArray(scip, vartocomponent, npermvars) );
805  for (i = 0; i < npermvars; ++i)
806  {
807  (*vartocomponent)[i] = -1;
808 
809  for (p = 0; p < nperms; ++p)
810  {
811  int img;
812 
813  img = transposed ? perms[i][p] : perms[p][i];
814 
815  /* perm p affects i -> possibly merge var components */
816  if ( img != i )
817  {
818  int component1;
819  int component2;
820  int representative;
821 
822  component1 = SCIPdisjointsetFind(componentstovar, i);
823  component2 = SCIPdisjointsetFind(componentstovar, img);
824  (*vartocomponent)[i] = p;
825  (*vartocomponent)[img] = p;
826 
827  /* ensure component1 <= component2 */
828  if ( component2 < component1 )
829  {
830  int swap;
831 
832  swap = component1;
833  component1 = component2;
834  component2 = swap;
835  }
836 
837  /* init permtovarcomp[p] to component of first moved variable or update the value */
838  if ( permtovarcomp[p] == -1 )
839  {
840  permtovarcomp[p] = component1;
841  representative = component1;
842  }
843  else
844  {
845  permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
846  representative = permtovarcomp[p];
847  }
848 
849  /* merge both components if they differ */
850  if ( component1 != component2 )
851  {
852  SCIPdisjointsetUnion(componentstovar, component1, component2, TRUE);
853  --(*ncomponents);
854  }
855 
856  /* possibly merge new component and permvartocom[p] and ensure the latter
857  * to have the smallest value */
858  if ( representative != component1 && representative != component2 )
859  {
860  if ( representative > component1 )
861  {
862  SCIPdisjointsetUnion(componentstovar, component1, representative, TRUE);
863  permtovarcomp[p] = component1;
864  }
865  else
866  SCIPdisjointsetUnion(componentstovar, representative, component1, TRUE);
867  --(*ncomponents);
868  }
869  else if ( representative > component1 )
870  {
871  assert( representative == component2 );
872  permtovarcomp[p] = component1;
873  }
874  }
875  }
876 
877  /* reduce number of components by singletons */
878  if ( (*vartocomponent)[i] == -1 )
879  --(*ncomponents);
880  }
881  assert( *ncomponents > 0 );
882 
883  /* update permvartocomp array to final variable representatives */
884  for (p = 0; p < nperms; ++p)
885  permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
886 
887  /* init components array by trivial natural order of permutations */
888  SCIP_CALL( SCIPallocBlockMemoryArray(scip, components, nperms) );
889  for (p = 0; p < nperms; ++p)
890  (*components)[p] = p;
891 
892  /* get correct order of components array */
893  SCIPsortIntInt(permtovarcomp, *components, nperms);
894 
895  /* determine componentbegins and store components for each permutation */
896  SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentbegins, *ncomponents + 1) );
897  SCIP_CALL( SCIPallocBufferArray(scip, &permtocomponent, nperms) );
898 
899  (*componentbegins)[0] = 0;
900  permtocomponent[(*components)[0]] = 0;
901  idx = 0;
902 
903  for (p = 1; p < nperms; ++p)
904  {
905  if ( permtovarcomp[p] > permtovarcomp[p - 1] )
906  (*componentbegins)[++idx] = p;
907 
908  assert( (*components)[p] >= 0 );
909  assert( (*components)[p] < nperms );
910  permtocomponent[(*components)[p]] = idx;
911  }
912  assert( *ncomponents == idx + 1 );
913  (*componentbegins)[++idx] = nperms;
914 
915  /* determine vartocomponent */
916  for (i = 0; i < npermvars; ++i)
917  {
918  int permidx;
919  permidx = (*vartocomponent)[i];
920  assert( -1 <= permidx && permidx < nperms );
921 
922  if ( permidx != -1 )
923  {
924  assert( 0 <= permtocomponent[permidx] );
925  assert( permtocomponent[permidx] < *ncomponents );
926 
927  (*vartocomponent)[i] = permtocomponent[permidx];
928  }
929  }
930 
931  /* init componentblocked */
932  SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentblocked, *ncomponents) );
933  for (i = 0; i < *ncomponents; ++i)
934  (*componentblocked)[i] = 0;
935 
936  SCIPfreeBufferArray(scip, &permtocomponent);
937  SCIPfreeBufferArray(scip, &permtovarcomp);
938  SCIPdisjointsetFree(&componentstovar, SCIPblkmem(scip));
939 
940 #ifdef SCIP_OUTPUT
941  printf("number of components: %d\n", propdata->ncomponents);
942  for (i = 0; i < *ncomponents; ++i)
943  {
944  printf("Component %d contains the following permutations:\n\t", i);
945  for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
946  {
947  printf("%d, ", (*components)[p]);
948  }
949  printf("\n");
950  }
951 #endif
952 
953  return SCIP_OKAY;
954 }
955 
956 
957 /** generate variable matrix for orbitope constraint handler
958  *
959  * @pre if storelexorder is TRUE, then the permutations define an orbitope
960  */
962  SCIP* scip, /**< SCIP instance */
963  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
964  int nrows, /**< number of rows of orbitope */
965  int ncols, /**< number of columns of orbitope */
966  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
967  int npermvars, /**< number of variables in permvars array */
968  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
969  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
970  int* nusedelems, /**< array storing how often an element was used in the orbitope */
971  SCIP_Shortbool* rowisbinary, /**< array encoding whether a row contains only binary variables (or NULL) */
972  SCIP_Bool* infeasible, /**< pointer to store whether the potential orbitope is not an orbitope */
973  SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
974  int** lexorder, /**< pointer to array storing the lexorder (or NULL) */
975  int* nvarsorder, /**< pointer to store number of variables in lexorder (or NULL) */
976  int* maxnvarsorder /**< pointer to store maximum number of variables in lexorder (or NULL) */
977  )
978 {
979  int nfilledcols = 0;
980  int curcolumn;
981  int i;
982  int cnt;
983  int nvarsorderold = 0;
984 
985  assert( vars != NULL );
986  assert( nrows > 0 );
987  assert( ncols > 0 );
988  assert( permvars != NULL );
989  assert( npermvars > 0 );
990  assert( orbitopevaridx != NULL );
991  assert( columnorder != NULL );
992  assert( nusedelems != NULL );
993  assert( infeasible != NULL );
994  assert( ! storelexorder || lexorder != NULL );
995  assert( ! storelexorder || nvarsorder != NULL );
996  assert( ! storelexorder || maxnvarsorder != NULL );
997 
998  /* possibly store lexicographic order defined by orbitope
999  *
1000  * position (i,j) of orbitope has position nrows * j + i in lexicographic order
1001  */
1002  if ( storelexorder )
1003  {
1004  assert( *nvarsorder == *maxnvarsorder );
1005  assert( lexorder != NULL );
1006 
1007  *maxnvarsorder += nrows * ncols;
1008  nvarsorderold = *nvarsorder;
1009 
1010  if ( *lexorder == NULL )
1011  {
1012  SCIP_CALL( SCIPallocBlockMemoryArray(scip, lexorder, *maxnvarsorder) );
1013  }
1014  else
1015  {
1016  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, lexorder, *nvarsorder, *maxnvarsorder) );
1017  }
1018  }
1019 
1020  curcolumn = ncols - 1;
1021 
1022  /* start filling vars matrix with the right-most column w.r.t. columnorder */
1023  while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 && ! *infeasible )
1024  {
1025  cnt = 0;
1026  for (i = 0; i < nrows; ++i)
1027  {
1028  /* skip rows containing non-binary variables */
1029  if ( rowisbinary != NULL && ! rowisbinary[i] )
1030  continue;
1031 
1032  assert( 0 <= orbitopevaridx[i][curcolumn] && orbitopevaridx[i][curcolumn] < npermvars );
1033  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
1034 
1035  /* elements in first column of orbitope have to appear exactly once in the orbitope */
1036  if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1037  {
1038  *infeasible = TRUE;
1039  assert( ! storelexorder );
1040  break;
1041  }
1042 
1043  if ( storelexorder )
1044  {
1045  (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1046  ++(*nvarsorder);
1047  }
1048  (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1049  }
1050  --curcolumn;
1051  ++nfilledcols;
1052  }
1053 
1054  /* There are three possibilities for the structure of columnorder:
1055  * 1) [0, 1, -1, -1, ..., -1]
1056  * 2) [0, 1, 1, 1, ..., 1]
1057  * 3) [0, 1, -1, -1, ...., -1, 1, 1, ..., 1]
1058  */
1059  /* Either we are in case 1) or case 3), or all columns should have been added to vars in case 2) */
1060  assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
1061 
1062  if ( curcolumn > 1 && ! *infeasible )
1063  {
1064  /* add column with columnorder 1 to vars */
1065  cnt = 0;
1066  for (i = 0; i < nrows; ++i)
1067  {
1068  /* skip rows containing non-binary variables*/
1069  if ( rowisbinary != NULL && ! rowisbinary[i] )
1070  continue;
1071 
1072  assert( orbitopevaridx[i][1] < npermvars );
1073  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][1]]) );
1074 
1075  if ( storelexorder )
1076  {
1077  (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][1];
1078  ++(*nvarsorder);
1079  }
1080  (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][1]];
1081  }
1082  ++nfilledcols;
1083 
1084  /* add column with columnorder 0 to vars */
1085  cnt = 0;
1086  for (i = 0; i < nrows; ++i)
1087  {
1088  /* skip rows containing non-binary variables*/
1089  if ( rowisbinary != NULL && ! rowisbinary[i] )
1090  continue;
1091 
1092  assert( orbitopevaridx[i][0] < npermvars );
1093  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][0]]) );
1094 
1095  if ( storelexorder )
1096  {
1097  (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][0];
1098  ++(*nvarsorder);
1099  }
1100  (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][0]];
1101  }
1102  ++nfilledcols;
1103 
1104  /* add columns with a negative column order to vars */
1105  if ( nfilledcols < ncols )
1106  {
1107  assert( ncols > 2 );
1108 
1109  curcolumn = 2;
1110  while ( nfilledcols < ncols && ! *infeasible )
1111  {
1112  assert( columnorder[curcolumn] < 0 );
1113 
1114  cnt = 0;
1115  for (i = 0; i < nrows; ++i)
1116  {
1117  /* skip rows containing non-binary variables*/
1118  if ( rowisbinary != NULL && ! rowisbinary[i] )
1119  continue;
1120 
1121  assert( orbitopevaridx[i][curcolumn] < npermvars );
1122  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
1123 
1124  /* elements in last column of orbitope have to appear exactly once in the orbitope */
1125  if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1126  {
1127  *infeasible = TRUE;
1128  assert( ! storelexorder );
1129  break;
1130  }
1131 
1132  if ( storelexorder )
1133  {
1134  (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1135  ++(*nvarsorder);
1136  }
1137  (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1138  }
1139  ++curcolumn;
1140  ++nfilledcols;
1141  }
1142  }
1143  }
1144 
1145  return SCIP_OKAY;
1146 }
1147 
1148 
1149 /** checks whether an orbitope is a packing or partitioning orbitope; if npprows != NULL,
1150  * count how many rows are contained in packing/partitioning constraints
1151  */
1153  SCIP* scip, /**< SCIP data structure */
1154  SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
1155  int nrows, /**< pointer to number of rows of variable matrix */
1156  int ncols, /**< number of columns of variable matrix */
1157  SCIP_Bool** pprows, /**< pointer to store which rows are are contained in
1158  * packing/partitioning constraints or NULL if not needed */
1159  int* npprows, /**< pointer to store how many rows are contained
1160  * in packing/partitioning constraints or NULL if not needed */
1161  SCIP_ORBITOPETYPE* type /**< pointer to store type of orbitope constraint after strengthening */
1162  )
1163 {
1164  SCIP_CONSHDLR* setppcconshdlr;
1165  SCIP_CONS** setppcconss;
1166  int nsetppcconss;
1167  int* covered;
1168  int nprobvars;
1169  int* rowidxvar;
1170  int* rowcoveragesetppc;
1171  int* rowsinsetppc;
1172  int ncovered;
1173  int ncoveredpart;
1174  int i;
1175  int j;
1176  int c;
1177 
1178  assert( scip != NULL );
1179  assert( vars != NULL );
1180  assert( vars != NULL );
1181  assert( nrows > 0 );
1182  assert( ncols > 0 );
1183  assert( type != NULL );
1184 
1185  *type = SCIP_ORBITOPETYPE_FULL;
1186  if ( npprows != NULL )
1187  *npprows = 0;
1188 
1189  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
1190  if ( setppcconshdlr == NULL )
1191  return SCIP_OKAY;
1192 
1193  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
1194  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
1195 
1196  /* we can terminate early if there are not sufficiently many setppc conss
1197  * (for orbitopes treating a full component, we might allow to remove rows
1198  * not contained in setppc cons; for this reason we need the second check)
1199  */
1200  if ( nsetppcconss == 0 || (nsetppcconss < nrows && npprows == NULL ))
1201  return SCIP_OKAY;
1202  assert( setppcconss != NULL );
1203 
1204  /* whether a row is contained in packing/partitioning constraint */
1205  SCIP_CALL( SCIPallocClearBufferArray(scip, &covered, nrows) );
1206  ncovered = 0;
1207  ncoveredpart = 0;
1208 
1209  nprobvars = SCIPgetNTotalVars(scip);
1210 
1211  /* array storing index of orbitope row a variable is contained in */
1212  SCIP_CALL( SCIPallocBufferArray(scip, &rowidxvar, nprobvars) );
1213 
1214  for (i = 0; i < nprobvars; ++i)
1215  rowidxvar[i] = -1;
1216 
1217  for (i = 0; i < nrows; ++i)
1218  {
1219  for (j = 0; j < ncols; ++j)
1220  {
1221  assert( 0 <= SCIPvarGetIndex(vars[i][j]) && SCIPvarGetIndex(vars[i][j]) < nprobvars );
1222  rowidxvar[SCIPvarGetIndex(vars[i][j])] = i;
1223  }
1224  }
1225 
1226  /* storage for number of vars per row that are contained in current setppc cons and
1227  * labels of rows intersecting with current setppc cons
1228  */
1229  SCIP_CALL( SCIPallocCleanBufferArray(scip, &rowcoveragesetppc, nrows) );
1230  SCIP_CALL( SCIPallocClearBufferArray(scip, &rowsinsetppc, nrows) );
1231 
1232  /* iterate over set packing and partitioning constraints and check whether the constraint's
1233  * support is a row r of the orbitope (covered[r] = 2) or contains row r (covered[r] = 1)
1234  *
1235  * @todo Check whether we can improve the following loop by using a hash value to check
1236  * whether the setppccons intersects the orbitope matrix
1237  */
1238  for (c = 0; c < nsetppcconss && ncoveredpart < ncols; ++c)
1239  {
1240  int nsetppcvars;
1241  SCIP_VAR** setppcvars;
1242  int nrowintersect = 0;
1243  int nvarsinorbitope;
1244 
1245  /* skip covering constraints */
1246  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
1247  continue;
1248 
1249  /* get number of set packing/partitioning variables */
1250  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
1251 
1252  /* constraint does not contain enough variables */
1253  if ( nsetppcvars < ncols )
1254  continue;
1255 
1256  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
1257  assert( setppcvars != NULL );
1258 
1259  /* upper bound on variables potentially contained in orbitope */
1260  nvarsinorbitope = nsetppcvars;
1261 
1262  /* for each setppc var, check whether it appears in a row of the orbitope and store
1263  * for each row the number of such variables; can be terminated early, if less than
1264  * ncols variables are contained in the orbitope
1265  */
1266  for (i = 0; i < nsetppcvars && nvarsinorbitope >= ncols; ++i)
1267  {
1268  SCIP_VAR* var;
1269  int idx;
1270  int rowidx;
1271 
1272  var = setppcvars[i];
1273  idx = SCIPvarGetIndex(var);
1274 
1275  assert( 0 <= idx && idx < nprobvars );
1276 
1277  rowidx = rowidxvar[idx];
1278 
1279  /* skip variables not contained in the orbitope */
1280  if ( rowidx < 0 )
1281  {
1282  --nvarsinorbitope;
1283  continue;
1284  }
1285 
1286  /* skip variables corresponding to already treated rows */
1287  if ( covered[rowidx] == 2 || (covered[rowidx] == 1 && (nsetppcvars > ncols || nrowintersect > 1)) )
1288  {
1289  --nvarsinorbitope;
1290  continue;
1291  }
1292 
1293  /* store information which rows intersect the setppc cons's support */
1294  if ( rowcoveragesetppc[rowidx] == 0 )
1295  rowsinsetppc[nrowintersect++] = rowidx;
1296  ++(rowcoveragesetppc[rowidx]);
1297 
1298  /* we can stop early if not enough variables are left to completely cover one of the rows that
1299  * intersect the setppc cons
1300  */
1301  if ( nsetppcvars - nrowintersect < ncols - 1 )
1302  break;
1303  }
1304 
1305  /* store whether rows coincide with set partitioning cons's support or whether
1306  * row is covered by a set packing/partitioning cons's support
1307  */
1308  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING
1309  && nrowintersect == 1 && rowcoveragesetppc[rowsinsetppc[0]] == ncols && nsetppcvars == ncols )
1310  {
1311  if ( covered[rowsinsetppc[0]] == 1 )
1312  --ncovered;
1313  covered[rowsinsetppc[0]] = 2;
1314  ++ncoveredpart;
1315  ++ncovered;
1316  }
1317  else
1318  {
1319  for (i = 0; i < nrowintersect; ++i)
1320  {
1321  if ( covered[rowsinsetppc[i]] == 0 && rowcoveragesetppc[rowsinsetppc[i]] >= ncols )
1322  {
1323  covered[rowsinsetppc[i]] = 1;
1324  ++ncovered;
1325  }
1326  }
1327  }
1328 
1329  /* reset data */
1330  for (i = 0; i < nrowintersect; ++i)
1331  rowcoveragesetppc[rowsinsetppc[i]] = 0;
1332  }
1333 
1334  /* check type of orbitope */
1335  if ( ncovered == nrows )
1336  {
1337  if ( ncoveredpart == nrows )
1339  else
1340  *type = SCIP_ORBITOPETYPE_PACKING;
1341  }
1342 
1343  if ( npprows != NULL )
1344  *npprows = ncovered;
1345 
1346  if ( pprows != NULL )
1347  {
1348  SCIP_CALL( SCIPallocBlockMemoryArray(scip, pprows, nrows) );
1349  for (i = 0; i < nrows; ++i)
1350  (*pprows)[i] = covered[i] > 0 ? 1 : 0;
1351  }
1352 
1353  SCIPfreeBufferArray(scip, &rowsinsetppc);
1354  SCIPfreeCleanBufferArray(scip, &rowcoveragesetppc);
1355  SCIPfreeBufferArray(scip, &rowidxvar);
1356  SCIPfreeBufferArray(scip, &covered);
1357 
1358  return SCIP_OKAY;
1359 }
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
Definition: symmetry.c:757
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11175
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9395
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:40
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, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:154
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11226
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1152
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_Shortbool
Definition: def.h:92
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11148
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2568
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:575
#define SCIP_Bool
Definition: def.h:84
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9441
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:524
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: symmetry.c:961
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:627
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9418
type definitions for symmetry computations
methods for handling symmetries
SCIP_RETCODE SCIPcomputeOrbitVar(SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
Definition: symmetry.c:302
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:402
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:11108
SCIP callable library.