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