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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file symmetry.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for handling symmetries
28 * @author Jasper van Doornmalen
29 * @author Christopher Hojny
30 * @author Marc Pfetsch
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#include "scip/symmetry.h"
36#include "scip/scip.h"
37#include "scip/cons_setppc.h"
38#include "scip/cons_orbitope.h"
39#include "scip/misc.h"
42
43
44/** compute non-trivial orbits of symmetry group
45 *
46 * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
47 * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
48 * consecutively in the orbits array. The variables of the i-th orbit have indices
49 * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
50 * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
51 */
53 SCIP* scip, /**< SCIP instance */
54 SCIP_Bool issigned, /**< whether orbits for signed permutations shall be computed */
55 SCIP_VAR** permvars, /**< variables considered in a permutation */
56 int npermvars, /**< length of a permutation array */
57 int** perms, /**< matrix containing in each row a permutation of the symmetry group */
58 int nperms, /**< number of permutations encoded in perms */
59 int* orbits, /**< array of non-trivial orbits */
60 int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
61 int* norbits /**< pointer to number of orbits currently stored in orbits */
62 )
63{
64 SCIP_Shortbool* varadded;
65 int permlen;
66 int orbitidx = 0;
67 int i;
68
69 assert( scip != NULL );
70 assert( permvars != NULL );
71 assert( perms != NULL );
72 assert( nperms > 0 );
73 assert( npermvars > 0 );
74 assert( orbits != NULL );
75 assert( orbitbegins != NULL );
76 assert( norbits != NULL );
77
78 permlen = npermvars;
79 if ( issigned )
80 permlen *= 2;
81
82 /* init data structures*/
83 SCIP_CALL( SCIPallocBufferArray(scip, &varadded, permlen) );
84
85 /* initially, every variable is contained in no orbit */
86 for (i = 0; i < permlen; ++i)
87 varadded[i] = FALSE;
88
89 /* find variable orbits */
90 *norbits = 0;
91 for (i = 0; i < permlen; ++i)
92 {
93 int beginorbitidx;
94 int j;
95
96 /* skip variable already contained in an orbit of a previous variable */
97 if ( varadded[i] )
98 continue;
99
100 /* store first variable */
101 beginorbitidx = orbitidx;
102 orbits[orbitidx++] = i;
103 varadded[i] = TRUE;
104
105 /* iterate over variables in curorbit and compute their images */
106 j = beginorbitidx;
107 while ( j < orbitidx )
108 {
109 int curelem;
110 int image;
111 int p;
112
113 curelem = orbits[j];
114
115 for (p = 0; p < nperms; ++p)
116 {
117 image = perms[p][curelem];
118
119 /* found new element of the orbit of i */
120 if ( ! varadded[image] )
121 {
122 orbits[orbitidx++] = image;
123 assert( orbitidx <= permlen );
124 varadded[image] = TRUE;
125 }
126 }
127 ++j;
128 }
129
130 /* if the orbit is trivial, reset storage, otherwise store orbit */
131 if ( orbitidx <= beginorbitidx + 1 )
132 orbitidx = beginorbitidx;
133 else
134 orbitbegins[(*norbits)++] = beginorbitidx;
135 }
136
137 /* store end in "last" orbitbegins entry */
138 assert( *norbits < permlen );
139 orbitbegins[*norbits] = orbitidx;
140
141#ifdef SCIP_OUTPUT
142 printf("Orbits (total number: %d):\n", *norbits);
143 for (i = 0; i < *norbits; ++i)
144 {
145 int j;
146
147 printf("%d: ", i);
148 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
149 printf("%d ", orbits[j]);
150 printf("\n");
151 }
152#endif
153
154 /* free memory */
155 SCIPfreeBufferArray(scip, &varadded);
156
157 return SCIP_OKAY;
158}
159
160
161/** compute non-trivial orbits of symmetry group using filtered generators
162 *
163 * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
164 * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
165 * consecutively in the orbits array. The variables of the i-th orbit have indices
166 * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
167 * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
168 *
169 * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
170 * filter out permutations.
171 */
173 SCIP* scip, /**< SCIP instance */
174 int npermvars, /**< length of a permutation array */
175 int** permstrans, /**< transposed matrix containing in each column a
176 * permutation of the symmetry group */
177 int nperms, /**< number of permutations encoded in perms */
178 SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
179 int* orbits, /**< array of non-trivial orbits */
180 int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
181 int* norbits, /**< pointer to number of orbits currently stored in orbits */
182 int* components, /**< array containing the indices of permutations sorted by components */
183 int* componentbegins, /**< array containing in i-th position the first position of
184 * component i in components array */
185 int* vartocomponent, /**< array containing for each permvar the index of the component it is
186 * contained in (-1 if not affected) */
187 unsigned* componentblocked, /**< array to store which symmetry methods have been used on a component
188 * using the same bitset information as for misc/usesymmetry */
189 int ncomponents, /**< number of components of symmetry group */
190 int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
191 * that is handled by orbital fixing */
192 )
193{
194 SCIP_Shortbool* varadded;
195 int nvaradded = 0;
196 int orbitidx = 0;
197 int i;
198
199 assert( scip != NULL );
200 assert( permstrans != NULL );
201 assert( nperms > 0 );
202 assert( npermvars > 0 );
203 assert( inactiveperms != NULL );
204 assert( orbits != NULL );
205 assert( orbitbegins != NULL );
206 assert( norbits != NULL );
207 assert( components != NULL );
208 assert( componentbegins != NULL );
209 assert( vartocomponent != NULL );
210 assert( ncomponents > 0 );
211 assert( nmovedpermvars > 0 );
212
213 /* init data structures */
214 SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
215
216 /* initially, every variable is contained in no orbit */
217 for (i = 0; i < npermvars; ++i)
218 varadded[i] = FALSE;
219
220 /* find variable orbits */
221 *norbits = 0;
222 for (i = 0; i < npermvars; ++i)
223 {
224 int beginorbitidx;
225 int componentidx;
226 int j;
227
228 /* skip unaffected variables and blocked components */
229 componentidx = vartocomponent[i];
230 if ( componentidx < 0 || componentblocked[componentidx] )
231 continue;
232
233 /* skip variable already contained in an orbit of a previous variable */
234 if ( varadded[i] )
235 continue;
236
237 /* store first variable */
238 beginorbitidx = orbitidx;
239 orbits[orbitidx++] = i;
240 varadded[i] = TRUE;
241 ++nvaradded;
242
243 /* iterate over variables in curorbit and compute their images */
244 j = beginorbitidx;
245 while ( j < orbitidx )
246 {
247 int* pt;
248 int curelem;
249 int image;
250 int p;
251
252 curelem = orbits[j];
253
254 pt = permstrans[curelem];
255 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
256 {
257 int perm;
258
259 perm = components[p];
260
261 if ( ! inactiveperms[perm] )
262 {
263 image = pt[perm];
264 assert( vartocomponent[image] == componentidx );
265
266 /* found new element of the orbit of i */
267 if ( ! varadded[image] )
268 {
269 orbits[orbitidx++] = image;
270 assert( orbitidx <= npermvars );
271 varadded[image] = TRUE;
272 ++nvaradded;
273 }
274 }
275 }
276 ++j;
277 }
278
279 /* if the orbit is trivial, reset storage, otherwise store orbit */
280 if ( orbitidx <= beginorbitidx + 1 )
281 orbitidx = beginorbitidx;
282 else
283 orbitbegins[(*norbits)++] = beginorbitidx;
284
285 /* stop if all variables are covered */
286 if ( nvaradded >= nmovedpermvars )
287 break;
288 }
289
290 /* store end in "last" orbitbegins entry */
291 assert( *norbits < npermvars );
292 orbitbegins[*norbits] = orbitidx;
293
294#ifdef SCIP_OUTPUT
295 printf("Orbits (total number: %d):\n", *norbits);
296 for (i = 0; i < *norbits; ++i)
297 {
298 int j;
299
300 printf("%d: ", i);
301 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
302 printf("%d ", orbits[j]);
303 printf("\n");
304 }
305#endif
306
307 /* free memory */
308 SCIPfreeBufferArray(scip, &varadded);
309
310 return SCIP_OKAY;
311}
312
313/** Compute orbit of a given variable and store it in @p orbit. The first entry of the orbit will
314 * be the given variable index and the rest is filled with the remaining variables excluding
315 * the ones specified in @p ignoredvars.
316 *
317 * @pre orbit is an initialized array of size propdata->npermvars
318 * @pre at least one of @p perms and @p permstrans should not be NULL
319 */
321 SCIP* scip, /**< SCIP instance */
322 int npermvars, /**< number of variables in permvars */
323 int** perms, /**< the generators of the permutation group (or NULL) */
324 int** permstrans, /**< the transposed matrix of generators (or NULL) */
325 int* components, /**< the components of the permutation group */
326 int* componentbegins, /**< array containing the starting index of each component */
327 SCIP_Shortbool* ignoredvars, /**< array indicating which variables should be ignored */
328 SCIP_Shortbool* varfound, /**< bitmap to mark which variables have been added (or NULL) */
329 int varidx, /**< index of variable for which the orbit is requested */
330 int component, /**< component that var is in */
331 int* orbit, /**< array in which the orbit should be stored */
332 int* orbitsize /**< buffer to store the size of the orbit */
333 )
334{ /*lint --e{571}*/
335 SCIP_Shortbool* varadded;
336 int* varstotest;
337 int nvarstotest;
338 int j;
339 int p;
340
341 assert( scip != NULL );
342 assert( perms != NULL || permstrans != NULL );
343 assert( components != NULL );
344 assert( componentbegins != NULL );
345 assert( ignoredvars != NULL );
346 assert( orbit != NULL );
347 assert( orbitsize != NULL );
348 assert( 0 <= varidx && varidx < npermvars );
349 assert( component >= 0 );
350 assert( npermvars > 0 );
351
352 /* init data structures*/
353 SCIP_CALL( SCIPallocClearBufferArray(scip, &varadded, npermvars) );
354 SCIP_CALL( SCIPallocClearBufferArray(scip, &varstotest, npermvars) );
355
356 /* compute and store orbit if it is non-trivial */
357 orbit[0] = varidx;
358 varstotest[0] = varidx;
359 *orbitsize = 1;
360 nvarstotest = 1;
361 varadded[varidx] = TRUE;
362
363 if ( varfound != NULL )
364 varfound[varidx] = TRUE;
365
366 /* iterate over variables in orbit and compute their images */
367 j = 0;
368 while ( j < nvarstotest )
369 {
370 int currvar;
371
372 currvar = varstotest[j++];
373
374 for (p = componentbegins[component]; p < componentbegins[component+1]; ++p)
375 {
376 int image;
377 int comp;
378
379 comp = components[p];
380
381 if ( perms != NULL )
382 image = perms[comp][currvar]; /*lint !e613*/
383 else
384 image = permstrans[currvar][comp];
385
386 /* found new element of the orbit of varidx */
387 if ( ! varadded[image] )
388 {
389 varstotest[nvarstotest++] = image;
390 varadded[image] = TRUE;
391
392 if ( ! ignoredvars[image] )
393 {
394 orbit[(*orbitsize)++] = image;
395
396 if ( varfound != NULL )
397 varfound[image] = TRUE;
398 }
399 }
400 }
401 }
402
403 /* free memory */
404 SCIPfreeBufferArray(scip, &varstotest);
405 SCIPfreeBufferArray(scip, &varadded);
406
407 return SCIP_OKAY;
408}
409
410/** compute non-trivial orbits of symmetry group
411 *
412 * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
413 * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
414 * consecutively in the orbits array. The variables of the i-th orbit have indices
415 * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
416 * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
417 *
418 * This function is adapted from computeGroupOrbitsFilter().
419 */
421 SCIP* scip, /**< SCIP instance */
422 int npermvars, /**< length of a permutation array */
423 int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
424 int nperms, /**< number of permutations encoded in perms */
425 int* components, /**< array containing the indices of permutations sorted by components */
426 int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
427 int* vartocomponent, /**< array containing for each permvar the index of the component it is
428 * contained in (-1 if not affected) */
429 int ncomponents, /**< number of components of symmetry group */
430 int* orbits, /**< array of non-trivial orbits */
431 int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
432 int* norbits, /**< pointer to number of orbits currently stored in orbits */
433 int* varorbitmap /**< array for storing the orbits for each variable */
434 )
435{
436 SCIP_Shortbool* varadded;
437 int orbitidx = 0;
438 int i;
439
440 assert( scip != NULL );
441 assert( permstrans != NULL );
442 assert( nperms > 0 );
443 assert( npermvars > 0 );
444 assert( components != NULL );
445 assert( componentbegins != NULL );
446 assert( vartocomponent != NULL );
447 assert( ncomponents > 0 );
448 assert( orbits != NULL );
449 assert( orbitbegins != NULL );
450 assert( norbits != NULL );
451 assert( varorbitmap != NULL );
452
453 /* init data structures */
454 SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
455
456 /* initially, every variable is contained in no orbit */
457 for (i = 0; i < npermvars; ++i)
458 {
459 varadded[i] = FALSE;
460 varorbitmap[i] = -1;
461 }
462
463 /* find variable orbits */
464 *norbits = 0;
465 for (i = 0; i < npermvars; ++i)
466 {
467 int beginorbitidx;
468 int componentidx;
469 int j;
470
471 /* skip unaffected variables - note that we also include blocked components */
472 componentidx = vartocomponent[i];
473 if ( componentidx < 0 )
474 continue;
475
476 /* skip variable already contained in an orbit of a previous variable */
477 if ( varadded[i] )
478 continue;
479
480 /* store first variable */
481 beginorbitidx = orbitidx;
482 orbits[orbitidx++] = i;
483 varadded[i] = TRUE;
484 varorbitmap[i] = *norbits;
485
486 /* iterate over variables in curorbit and compute their images */
487 j = beginorbitidx;
488 while ( j < orbitidx )
489 {
490 int* pt;
491 int curelem;
492 int image;
493 int p;
494
495 curelem = orbits[j];
496
497 pt = permstrans[curelem];
498 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
499 {
500 int perm;
501
502 perm = components[p];
503 image = pt[perm];
504 assert( vartocomponent[image] == componentidx );
505
506 /* found new element of the orbit of i */
507 if ( ! varadded[image] )
508 {
509 orbits[orbitidx++] = image;
510 assert( orbitidx <= npermvars );
511 varadded[image] = TRUE;
512 varorbitmap[image] = *norbits;
513 }
514 }
515 ++j;
516 }
517
518 /* if the orbit is trivial, reset storage, otherwise store orbit */
519 if ( orbitidx <= beginorbitidx + 1 )
520 {
521 orbitidx = beginorbitidx;
522 varorbitmap[i] = -1;
523 }
524 else
525 orbitbegins[(*norbits)++] = beginorbitidx;
526 }
527
528 /* store end in "last" orbitbegins entry */
529 assert( *norbits < npermvars );
530 orbitbegins[*norbits] = orbitidx;
531
532 /* free memory */
533 SCIPfreeBufferArray(scip, &varadded);
534
535 return SCIP_OKAY;
536}
537
538
539/** Checks whether a permutation is a composition of 2-cycles and in this case determines the number of overall
540 * 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff @p ntwocyclesperm > 0 upon termination.
541 */
543 int* perm, /**< permutation */
544 SCIP_VAR** vars, /**< array of variables perm is acting on */
545 int nvars, /**< number of variables */
546 int* ntwocyclesperm, /**< pointer to store number of 2-cycles or 0 if perm is not an involution */
547 int* nbincyclesperm, /**< pointer to store number of binary cycles */
548 SCIP_Bool earlytermination /**< whether we terminate early if not all affected variables are binary */
549 )
550{
551 int ntwocycles = 0;
552 int i;
553
554 assert( perm != NULL );
555 assert( vars != NULL );
556 assert( ntwocyclesperm != NULL );
557 assert( nbincyclesperm != NULL );
558
559 *ntwocyclesperm = 0;
560 *nbincyclesperm = 0;
561 for (i = 0; i < nvars; ++i)
562 {
563 assert( 0 <= perm[i] && perm[i] < nvars );
564
565 /* skip fixed points and avoid treating the same 2-cycle twice */
566 if ( perm[i] <= i )
567 continue;
568
569 if ( perm[perm[i]] == i )
570 {
571 if ( SCIPvarIsBinary(vars[i]) && SCIPvarIsBinary(vars[perm[i]]) )
572 ++(*nbincyclesperm);
573 else if ( earlytermination )
574 return SCIP_OKAY;
575
576 ++ntwocycles;
577 }
578 else
579 {
580 /* we do not have only 2-cycles */
581 return SCIP_OKAY;
582 }
583 }
584
585 /* at this point the permutation is a composition of 2-cycles */
586 *ntwocyclesperm = ntwocycles;
587
588 return SCIP_OKAY;
589}
590
591
592/** determine number of variables affected by symmetry group */
594 SCIP* scip, /**< SCIP instance */
595 int** perms, /**< permutations */
596 int nperms, /**< number of permutations in perms */
597 SCIP_VAR** permvars, /**< variables corresponding to permutations */
598 int npermvars, /**< number of permvars in perms */
599 int* nvarsaffected /**< pointer to store number of all affected variables */
600 )
601{
602 SCIP_Shortbool* affected;
603 int i;
604 int p;
605
606 assert( scip != NULL );
607 assert( perms != NULL );
608 assert( nperms > 0 );
609 assert( permvars != NULL );
610 assert( npermvars > 0 );
611 assert( nvarsaffected != NULL );
612
613 *nvarsaffected = 0;
614
615 SCIP_CALL( SCIPallocClearBufferArray(scip, &affected, npermvars) );
616
617 /* iterate over permutations and check which variables are affected by some symmetry */
618 for (p = 0; p < nperms; ++p)
619 {
620 for (i = 0; i < npermvars; ++i)
621 {
622 if ( affected[i] )
623 continue;
624
625 if ( perms[p][i] != i )
626 {
627 affected[i] = TRUE;
628 ++(*nvarsaffected);
629 }
630 }
631 }
632 SCIPfreeBufferArray(scip, &affected);
633
634 return SCIP_OKAY;
635}
636
637
638/** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
639 * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
640 * we add one column to the suborbitope of the first nfilledcols columns.
641 *
642 * @pre Every non-trivial cycle of perm is a 2-cycle.
643 * @pre perm has nrows many 2-cycles
644 */
646 int** suborbitope, /**< matrix containing suborbitope entries */
647 int nrows, /**< number of rows of suborbitope */
648 int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
649 int coltoextend, /**< index of column that should be extended by perm */
650 int* perm, /**< permutation */
651 SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
652 int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
653 SCIP_VAR** permvars, /**< permutation vars array */
654 SCIP_Shortbool* rowisbinary, /**< array encoding whether variables in an orbitope row are binary (or NULL) */
655 SCIP_Bool* success, /**< pointer to store whether extension was successful */
656 SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
657 )
658{
659 int nintersections = 0;
660 int row;
661 int idx1;
662 int idx2;
663
664 assert( suborbitope != NULL );
665 assert( nrows > 0 );
666 assert( nfilledcols > 0 );
667 assert( coltoextend >= 0 );
668 assert( perm != NULL );
669 assert( nusedelems != NULL );
670 assert( permvars != NULL );
671 assert( success != NULL );
672 assert( infeasible != NULL );
673
674 *success = FALSE;
675 *infeasible = FALSE;
676
677 /* if we try to extend the first orbitope generator by another one,
678 * we can change the order of entries in each row of suborbitope */
679 if ( nfilledcols == 2 )
680 {
681 /* check whether each cycle of perm intersects with a row of suborbitope */
682 for (row = 0; row < nrows; ++row)
683 {
684 idx1 = suborbitope[row][0];
685 idx2 = suborbitope[row][1];
686
687 /* if idx1 or idx2 is affected by perm, we can extend the row of the orbitope */
688 if ( idx1 != perm[idx1] )
689 {
690 /* change order of idx1 and idx2 for right extensions */
691 if ( ! leftextension )
692 {
693 suborbitope[row][0] = idx2;
694 suborbitope[row][1] = idx1;
695 }
696 assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
697
698 suborbitope[row][2] = perm[idx1];
699 ++nintersections;
700
701 ++(*nusedelems)[idx1];
702 ++(*nusedelems)[perm[idx1]];
703
704 /* if an element appears too often in the orbitope matrix */
705 if ( (*nusedelems)[idx1] + (*nusedelems)[perm[idx1]] > 3 )
706 {
707 *infeasible = TRUE;
708 break;
709 }
710 }
711 else if ( idx2 != perm[idx2] )
712 {
713 /* change order of idx1 and idx2 for left extensions */
714 if ( leftextension )
715 {
716 suborbitope[row][0] = idx2;
717 suborbitope[row][1] = idx1;
718 }
719 assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
720
721 suborbitope[row][2] = perm[idx2];
722 ++nintersections;
723
724 ++(*nusedelems)[idx2];
725 ++(*nusedelems)[perm[idx2]];
726
727 /* if an element appears too often in the orbitope matrix */
728 if ( (*nusedelems)[idx2] + (*nusedelems)[perm[idx2]] > 3 )
729 {
730 *infeasible = TRUE;
731 break;
732 }
733 }
734 }
735 }
736 else
737 {
738 /* check whether each cycle of perm intersects with a row of suborbitope */
739 for (row = 0; row < nrows; ++row)
740 {
741 idx1 = suborbitope[row][coltoextend];
742
743 /* if idx1 is affected by perm, we can extend the row of the orbitope */
744 if ( idx1 != perm[idx1] )
745 {
746 assert( rowisbinary == NULL || rowisbinary[row] == SCIPvarIsBinary(permvars[perm[idx1]]) );
747
748 suborbitope[row][nfilledcols] = perm[idx1];
749 ++nintersections;
750
751 ++(*nusedelems)[idx1];
752 ++(*nusedelems)[perm[idx1]];
753
754 /* if an element appears to often in the orbitope matrix */
755 if ( (*nusedelems)[idx1] + (*nusedelems)[perm[idx1]] > 3 )
756 {
757 *infeasible = TRUE;
758 break;
759 }
760 }
761 }
762 }
763
764 /* if there are too few intersection, this is not an orbitope */
765 if ( nintersections > 0 && nintersections < nrows )
766 *infeasible = TRUE;
767 else if ( nintersections == nrows )
768 *success = TRUE;
769
770 return SCIP_OKAY;
771}
772
773
774/** compute components of symmetry group */
776 SCIP* scip, /**< SCIP instance */
777 SYM_SYMTYPE symtype, /**< type of symmetries in perms */
778 int** perms, /**< permutation generators as
779 * (either nperms x npermvars or npermvars x nperms) matrix */
780 int nperms, /**< number of permutations */
781 SCIP_VAR** permvars, /**< variables on which permutations act */
782 int npermvars, /**< number of variables for permutations */
783 SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
784 int** components, /**< array containing the indices of permutations sorted by components */
785 int** componentbegins, /**< array containing in i-th position the first position of
786 * component i in components array */
787 int** vartocomponent, /**< array containing for each permvar the index of the component it is
788 * contained in (-1 if not affected) */
789 unsigned** componentblocked, /**< array to store which symmetry methods have been used on a component
790 * using the same bitset information as for misc/usesymmetry */
791 int* ncomponents /**< pointer to store number of components of symmetry group */
792 )
793{
794 SCIP_DISJOINTSET* componentstovar = NULL;
795 int* permtovarcomp;
796 int* permtocomponent;
797 int p;
798 int i;
799 int idx;
800
801 assert( scip != NULL );
802 assert( permvars != NULL );
803 assert( npermvars > 0 );
804 assert( perms != NULL );
805 assert( components != NULL );
806 assert( componentbegins != NULL );
807 assert( vartocomponent != NULL );
808 assert( componentblocked != NULL );
809 assert( ncomponents != NULL );
810
811 if ( nperms <= 0 )
812 return SCIP_OKAY;
813
814 SCIP_CALL( SCIPdisjointsetCreate(&componentstovar, SCIPblkmem(scip), npermvars) );
815 *ncomponents = npermvars;
816
817 /* init array that stores for each permutation the representative of its affected variables */
818 SCIP_CALL( SCIPallocBufferArray(scip, &permtovarcomp, nperms) );
819 for (p = 0; p < nperms; ++p)
820 permtovarcomp[p] = -1;
821
822 /* find permutation components and store for each variable an affecting permutation (or -1) */
823 SCIP_CALL( SCIPallocBlockMemoryArray(scip, vartocomponent, npermvars) );
824 for (i = 0; i < npermvars; ++i)
825 {
826 (*vartocomponent)[i] = -1;
827
828 for (p = 0; p < nperms; ++p)
829 {
830 int img;
831
832 img = transposed ? perms[i][p] : perms[p][i];
833
834 /* perm p affects i -> possibly merge var components */
835 if ( img != i )
836 {
837 int component1;
838 int component2;
839 int representative;
840
841 if ( img >= npermvars )
842 {
843 assert( symtype == SYM_SYMTYPE_SIGNPERM );
844 img -= npermvars;
845 assert( 0 <= img && img < npermvars );
846 }
847
848 component1 = SCIPdisjointsetFind(componentstovar, i);
849 component2 = SCIPdisjointsetFind(componentstovar, img);
850 (*vartocomponent)[i] = p;
851 (*vartocomponent)[img] = p;
852
853 /* ensure component1 <= component2 */
854 if ( component2 < component1 )
855 {
856 int swap;
857
858 swap = component1;
859 component1 = component2;
860 component2 = swap;
861 }
862
863 /* init permtovarcomp[p] to component of first moved variable or update the value */
864 if ( permtovarcomp[p] == -1 )
865 {
866 permtovarcomp[p] = component1;
867 representative = component1;
868 }
869 else
870 {
871 permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
872 representative = permtovarcomp[p];
873 }
874
875 /* merge both components if they differ */
876 if ( component1 != component2 )
877 {
878 SCIPdisjointsetUnion(componentstovar, component1, component2, TRUE);
879 --(*ncomponents);
880 }
881
882 /* possibly merge new component and permvartocom[p] and ensure the latter
883 * to have the smallest value */
884 if ( representative != component1 && representative != component2 )
885 {
886 if ( representative > component1 )
887 {
888 SCIPdisjointsetUnion(componentstovar, component1, representative, TRUE);
889 permtovarcomp[p] = component1;
890 }
891 else
892 SCIPdisjointsetUnion(componentstovar, representative, component1, TRUE);
893 --(*ncomponents);
894 }
895 else if ( representative > component1 )
896 {
897 assert( representative == component2 );
898 permtovarcomp[p] = component1;
899 }
900 }
901 }
902
903 /* reduce number of components by singletons */
904 if ( (*vartocomponent)[i] == -1 )
905 --(*ncomponents);
906 }
907 assert( *ncomponents > 0 );
908
909 /* update permvartocomp array to final variable representatives */
910 for (p = 0; p < nperms; ++p)
911 permtovarcomp[p] = SCIPdisjointsetFind(componentstovar, permtovarcomp[p]);
912
913 /* init components array by trivial natural order of permutations */
914 SCIP_CALL( SCIPallocBlockMemoryArray(scip, components, nperms) );
915 for (p = 0; p < nperms; ++p)
916 (*components)[p] = p;
917
918 /* get correct order of components array */
919 SCIPsortIntInt(permtovarcomp, *components, nperms);
920
921 /* determine componentbegins and store components for each permutation */
922 SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentbegins, *ncomponents + 1) );
923 SCIP_CALL( SCIPallocBufferArray(scip, &permtocomponent, nperms) );
924
925 (*componentbegins)[0] = 0;
926 permtocomponent[(*components)[0]] = 0;
927 idx = 0;
928
929 for (p = 1; p < nperms; ++p)
930 {
931 if ( permtovarcomp[p] > permtovarcomp[p - 1] )
932 (*componentbegins)[++idx] = p;
933
934 assert( (*components)[p] >= 0 );
935 assert( (*components)[p] < nperms );
936 permtocomponent[(*components)[p]] = idx;
937 }
938 assert( *ncomponents == idx + 1 );
939 (*componentbegins)[++idx] = nperms;
940
941 /* determine vartocomponent */
942 for (i = 0; i < npermvars; ++i)
943 {
944 int permidx;
945 permidx = (*vartocomponent)[i];
946 assert( -1 <= permidx && permidx < nperms );
947
948 if ( permidx != -1 )
949 {
950 assert( 0 <= permtocomponent[permidx] );
951 assert( permtocomponent[permidx] < *ncomponents );
952
953 (*vartocomponent)[i] = permtocomponent[permidx];
954 }
955 }
956
957 /* init componentblocked */
958 SCIP_CALL( SCIPallocBlockMemoryArray(scip, componentblocked, *ncomponents) );
959 for (i = 0; i < *ncomponents; ++i)
960 (*componentblocked)[i] = 0;
961
962 SCIPfreeBufferArray(scip, &permtocomponent);
963 SCIPfreeBufferArray(scip, &permtovarcomp);
964 SCIPdisjointsetFree(&componentstovar, SCIPblkmem(scip));
965
966#ifdef SCIP_OUTPUT
967 printf("number of components: %d\n", *ncomponents);
968 for (i = 0; i < *ncomponents; ++i)
969 {
970 printf("Component %d contains the following permutations:\n\t", i);
971 for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
972 {
973 printf("%d, ", (*components)[p]);
974 }
975 printf("\n");
976 }
977#endif
978
979 return SCIP_OKAY;
980}
981
982
983/** generate variable matrix for orbitope constraint handler
984 *
985 * @pre if storelexorder is TRUE, then the permutations define an orbitope
986 */
988 SCIP* scip, /**< SCIP instance */
989 SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
990 int nrows, /**< number of rows of orbitope */
991 int ncols, /**< number of columns of orbitope */
992 SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
993 int npermvars, /**< number of variables in permvars array */
994 int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
995 int* columnorder, /**< permutation to reorder column of orbitopevaridx */
996 int* nusedelems, /**< array storing how often an element was used in the orbitope */
997 SCIP_Shortbool* rowisbinary, /**< array encoding whether a row contains only binary variables (or NULL) */
998 SCIP_Bool* infeasible, /**< pointer to store whether the potential orbitope is not an orbitope */
999 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
1000 int** lexorder, /**< pointer to array storing the lexorder (or NULL) */
1001 int* nvarsorder, /**< pointer to store number of variables in lexorder (or NULL) */
1002 int* maxnvarsorder /**< pointer to store maximum number of variables in lexorder (or NULL) */
1003 )
1004{
1005 int nfilledcols = 0;
1006 int curcolumn;
1007 int i;
1008 int cnt;
1009 int nvarsorderold = 0;
1010
1011 assert( vars != NULL );
1012 assert( nrows > 0 );
1013 assert( ncols > 0 );
1014 assert( permvars != NULL );
1015 assert( npermvars > 0 );
1016 assert( orbitopevaridx != NULL );
1017 assert( columnorder != NULL );
1018 assert( nusedelems != NULL );
1019 assert( infeasible != NULL );
1020 assert( ! storelexorder || lexorder != NULL );
1021 assert( ! storelexorder || nvarsorder != NULL );
1022 assert( ! storelexorder || maxnvarsorder != NULL );
1023
1024 /* possibly store lexicographic order defined by orbitope
1025 *
1026 * position (i,j) of orbitope has position nrows * j + i in lexicographic order
1027 */
1028 if ( storelexorder )
1029 {
1030 assert( *nvarsorder == *maxnvarsorder );
1031 assert( lexorder != NULL );
1032
1033 *maxnvarsorder += nrows * ncols;
1034 nvarsorderold = *nvarsorder;
1035
1036 if ( *lexorder == NULL )
1037 {
1038 SCIP_CALL( SCIPallocBlockMemoryArray(scip, lexorder, *maxnvarsorder) );
1039 }
1040 else
1041 {
1042 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, lexorder, *nvarsorder, *maxnvarsorder) );
1043 }
1044 }
1045
1046 curcolumn = ncols - 1;
1047
1048 /* start filling vars matrix with the right-most column w.r.t. columnorder */
1049 while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 && ! *infeasible )
1050 {
1051 cnt = 0;
1052 for (i = 0; i < nrows; ++i)
1053 {
1054 /* skip rows containing non-binary variables */
1055 if ( rowisbinary != NULL && ! rowisbinary[i] )
1056 continue;
1057
1058 assert( 0 <= orbitopevaridx[i][curcolumn] && orbitopevaridx[i][curcolumn] < npermvars );
1059 assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
1060
1061 /* elements in first column of orbitope have to appear exactly once in the orbitope */
1062 if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1063 {
1064 *infeasible = TRUE;
1065 assert( ! storelexorder );
1066 break;
1067 }
1068
1069 if ( storelexorder )
1070 {
1071 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1072 ++(*nvarsorder);
1073 }
1074 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1075 }
1076 --curcolumn;
1077 ++nfilledcols;
1078 }
1079
1080 /* There are three possibilities for the structure of columnorder:
1081 * 1) [0, 1, -1, -1, ..., -1]
1082 * 2) [0, 1, 1, 1, ..., 1]
1083 * 3) [0, 1, -1, -1, ...., -1, 1, 1, ..., 1]
1084 */
1085 /* Either we are in case 1) or case 3), or all columns should have been added to vars in case 2) */
1086 assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
1087
1088 if ( curcolumn > 1 && ! *infeasible )
1089 {
1090 /* add column with columnorder 1 to vars */
1091 cnt = 0;
1092 for (i = 0; i < nrows; ++i)
1093 {
1094 /* skip rows containing non-binary variables*/
1095 if ( rowisbinary != NULL && ! rowisbinary[i] )
1096 continue;
1097
1098 assert( orbitopevaridx[i][1] < npermvars );
1099 assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][1]]) );
1100
1101 if ( storelexorder )
1102 {
1103 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][1];
1104 ++(*nvarsorder);
1105 }
1106 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][1]];
1107 }
1108 ++nfilledcols;
1109
1110 /* add column with columnorder 0 to vars */
1111 cnt = 0;
1112 for (i = 0; i < nrows; ++i)
1113 {
1114 /* skip rows containing non-binary variables*/
1115 if ( rowisbinary != NULL && ! rowisbinary[i] )
1116 continue;
1117
1118 assert( orbitopevaridx[i][0] < npermvars );
1119 assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][0]]) );
1120
1121 if ( storelexorder )
1122 {
1123 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][0];
1124 ++(*nvarsorder);
1125 }
1126 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][0]];
1127 }
1128 ++nfilledcols;
1129
1130 /* add columns with a negative column order to vars */
1131 if ( nfilledcols < ncols )
1132 {
1133 assert( ncols > 2 );
1134
1135 curcolumn = 2;
1136 while ( nfilledcols < ncols && ! *infeasible )
1137 {
1138 assert( columnorder[curcolumn] < 0 );
1139
1140 cnt = 0;
1141 for (i = 0; i < nrows; ++i)
1142 {
1143 /* skip rows containing non-binary variables*/
1144 if ( rowisbinary != NULL && ! rowisbinary[i] )
1145 continue;
1146
1147 assert( orbitopevaridx[i][curcolumn] < npermvars );
1148 assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
1149
1150 /* elements in last column of orbitope have to appear exactly once in the orbitope */
1151 if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1152 {
1153 *infeasible = TRUE;
1154 assert( ! storelexorder );
1155 break;
1156 }
1157
1158 if ( storelexorder )
1159 {
1160 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1161 ++(*nvarsorder);
1162 }
1163 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1164 }
1165 ++curcolumn;
1166 ++nfilledcols;
1167 }
1168 }
1169 }
1170
1171 return SCIP_OKAY;
1172}
1173
1174
1175/** checks whether an orbitope is a packing or partitioning orbitope; if npprows != NULL,
1176 * count how many rows are contained in packing/partitioning constraints
1177 */
1179 SCIP* scip, /**< SCIP data structure */
1180 SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
1181 int nrows, /**< pointer to number of rows of variable matrix */
1182 int ncols, /**< number of columns of variable matrix */
1183 SCIP_Bool** pprows, /**< pointer to store which rows are are contained in
1184 * packing/partitioning constraints or NULL if not needed */
1185 int* npprows, /**< pointer to store how many rows are contained
1186 * in packing/partitioning constraints or NULL if not needed */
1187 SCIP_ORBITOPETYPE* type /**< pointer to store type of orbitope constraint after strengthening */
1188 )
1189{
1190 SCIP_CONSHDLR* setppcconshdlr;
1191 SCIP_CONS** setppcconss;
1192 int nsetppcconss;
1193 int* covered;
1194 int nprobvars;
1195 int* rowidxvar;
1196 int* rowcoveragesetppc;
1197 int* rowsinsetppc;
1198 int ncovered;
1199 int ncoveredpart;
1200 int i;
1201 int j;
1202 int c;
1203
1204 assert( scip != NULL );
1205 assert( vars != NULL );
1206 assert( vars != NULL );
1207 assert( nrows > 0 );
1208 assert( ncols > 0 );
1209 assert( type != NULL );
1210
1211 *type = SCIP_ORBITOPETYPE_FULL;
1212 if ( npprows != NULL )
1213 *npprows = 0;
1214
1215 setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
1216 if ( setppcconshdlr == NULL )
1217 return SCIP_OKAY;
1218
1219 setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
1220 nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
1221
1222 /* we can terminate early if there are not sufficiently many setppc conss
1223 * (for orbitopes treating a full component, we might allow to remove rows
1224 * not contained in setppc cons; for this reason we need the second check)
1225 */
1226 if ( nsetppcconss == 0 || (nsetppcconss < nrows && npprows == NULL ))
1227 return SCIP_OKAY;
1228 assert( setppcconss != NULL );
1229
1230 /* whether a row is contained in packing/partitioning constraint */
1231 SCIP_CALL( SCIPallocClearBufferArray(scip, &covered, nrows) );
1232 ncovered = 0;
1233 ncoveredpart = 0;
1234
1235 nprobvars = SCIPgetNTotalVars(scip);
1236
1237 /* array storing index of orbitope row a variable is contained in */
1238 SCIP_CALL( SCIPallocBufferArray(scip, &rowidxvar, nprobvars) );
1239
1240 for (i = 0; i < nprobvars; ++i)
1241 rowidxvar[i] = -1;
1242
1243 for (i = 0; i < nrows; ++i)
1244 {
1245 for (j = 0; j < ncols; ++j)
1246 {
1247 assert( 0 <= SCIPvarGetIndex(vars[i][j]) && SCIPvarGetIndex(vars[i][j]) < nprobvars );
1248 rowidxvar[SCIPvarGetIndex(vars[i][j])] = i;
1249 }
1250 }
1251
1252 /* storage for number of vars per row that are contained in current setppc cons and
1253 * labels of rows intersecting with current setppc cons
1254 */
1255 SCIP_CALL( SCIPallocCleanBufferArray(scip, &rowcoveragesetppc, nrows) );
1256 SCIP_CALL( SCIPallocClearBufferArray(scip, &rowsinsetppc, nrows) );
1257
1258 /* iterate over set packing and partitioning constraints and check whether the constraint's
1259 * support is a row r of the orbitope (covered[r] = 2) or contains row r (covered[r] = 1)
1260 *
1261 * @todo Check whether we can improve the following loop by using a hash value to check
1262 * whether the setppccons intersects the orbitope matrix
1263 */
1264 for (c = 0; c < nsetppcconss && ncoveredpart < ncols; ++c)
1265 {
1266 int nsetppcvars;
1267 SCIP_VAR** setppcvars;
1268 int nrowintersect = 0;
1269 int nvarsinorbitope;
1270
1271 /* skip covering constraints */
1272 if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
1273 continue;
1274
1275 /* get number of set packing/partitioning variables */
1276 nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
1277
1278 /* constraint does not contain enough variables */
1279 if ( nsetppcvars < ncols )
1280 continue;
1281
1282 setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
1283 assert( setppcvars != NULL );
1284
1285 /* upper bound on variables potentially contained in orbitope */
1286 nvarsinorbitope = nsetppcvars;
1287
1288 /* for each setppc var, check whether it appears in a row of the orbitope and store
1289 * for each row the number of such variables; can be terminated early, if less than
1290 * ncols variables are contained in the orbitope
1291 */
1292 for (i = 0; i < nsetppcvars && nvarsinorbitope >= ncols; ++i)
1293 {
1294 SCIP_VAR* var;
1295 int idx;
1296 int rowidx;
1297
1298 var = setppcvars[i];
1299 idx = SCIPvarGetIndex(var);
1300
1301 assert( 0 <= idx && idx < nprobvars );
1302
1303 rowidx = rowidxvar[idx];
1304
1305 /* skip variables not contained in the orbitope */
1306 if ( rowidx < 0 )
1307 {
1308 --nvarsinorbitope;
1309 continue;
1310 }
1311
1312 /* skip variables corresponding to already treated rows */
1313 if ( covered[rowidx] == 2 || (covered[rowidx] == 1 && (nsetppcvars > ncols || nrowintersect > 1)) )
1314 {
1315 --nvarsinorbitope;
1316 continue;
1317 }
1318
1319 /* store information which rows intersect the setppc cons's support */
1320 if ( rowcoveragesetppc[rowidx] == 0 )
1321 rowsinsetppc[nrowintersect++] = rowidx;
1322 ++(rowcoveragesetppc[rowidx]);
1323
1324 /* we can stop early if not enough variables are left to completely cover one of the rows that
1325 * intersect the setppc cons
1326 */
1327 if ( nsetppcvars - nrowintersect < ncols - 1 )
1328 break;
1329 }
1330
1331 /* store whether rows coincide with set partitioning cons's support or whether
1332 * row is covered by a set packing/partitioning cons's support
1333 */
1334 if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING
1335 && nrowintersect == 1 && rowcoveragesetppc[rowsinsetppc[0]] == ncols && nsetppcvars == ncols )
1336 {
1337 if ( covered[rowsinsetppc[0]] == 1 )
1338 --ncovered;
1339 covered[rowsinsetppc[0]] = 2;
1340 ++ncoveredpart;
1341 ++ncovered;
1342 }
1343 else
1344 {
1345 for (i = 0; i < nrowintersect; ++i)
1346 {
1347 if ( covered[rowsinsetppc[i]] == 0 && rowcoveragesetppc[rowsinsetppc[i]] >= ncols )
1348 {
1349 covered[rowsinsetppc[i]] = 1;
1350 ++ncovered;
1351 }
1352 }
1353 }
1354
1355 /* reset data */
1356 for (i = 0; i < nrowintersect; ++i)
1357 rowcoveragesetppc[rowsinsetppc[i]] = 0;
1358 }
1359
1360 /* check type of orbitope */
1361 if ( ncovered == nrows )
1362 {
1363 if ( ncoveredpart == nrows )
1365 else
1367 }
1368
1369 if ( npprows != NULL )
1370 *npprows = ncovered;
1371
1372 if ( pprows != NULL )
1373 {
1374 SCIP_CALL( SCIPallocBlockMemoryArray(scip, pprows, nrows) );
1375 for (i = 0; i < nrows; ++i)
1376 (*pprows)[i] = covered[i] > 0 ? 1 : 0;
1377 }
1378
1379 SCIPfreeBufferArray(scip, &rowsinsetppc);
1380 SCIPfreeCleanBufferArray(scip, &rowcoveragesetppc);
1381 SCIPfreeBufferArray(scip, &rowidxvar);
1382 SCIPfreeBufferArray(scip, &covered);
1383
1384 return SCIP_OKAY;
1385}
1386
1387/** checks whether a (signed) permutation is an involution */
1388static
1390 int* perm, /**< permutation */
1391 int permlen, /**< number of original (non-negated) variables in a permutation */
1392 SCIP_Bool* isinvolution, /**< pointer to store whether perm is an involution */
1393 int* ntwocycles /**< pointer to store number of 2-cycles in an involution */
1394 )
1395{
1396 int v;
1397
1398 assert( perm != NULL );
1399 assert( permlen > 0 );
1400 assert( isinvolution != NULL );
1401 assert( ntwocycles != NULL );
1402
1403 *ntwocycles = 0;
1404 *isinvolution = TRUE;
1405 for (v = 0; v < permlen && *isinvolution; ++v)
1406 {
1407 /* do not handle variables twice */
1408 if ( perm[v] <= v )
1409 continue;
1410
1411 /* detect two cycles */
1412 if ( perm[perm[v]] == v )
1413 ++(*ntwocycles);
1414 else
1415 *isinvolution = FALSE;
1416 }
1417
1418 return SCIP_OKAY;
1419}
1420
1421/** checks whether selected permutations define orbitopal symmetries */
1422static
1424 SCIP* scip, /**< SCIP pointer */
1425 int** perms, /**< array of permutations */
1426 int* selectedperms, /**< indices of permutations in perm that shall be considered */
1427 int nselectedperms, /**< number of permutations in selectedperms */
1428 int permlen, /**< number of variables in a permutation */
1429 int nrows, /**< number of rows of potential orbitopal symmetries */
1430 SCIP_Bool* success, /**< pointer to store if orbitopal symmetries could be found */
1431 int**** matrices, /**< pointer to store matrices of orbitopal symmetries */
1432 int** ncols, /**< pointer to store number of columns of matrices in matrices */
1433 int* nmatrices /**< pointer to store the number of matrices in matrices */
1434 )
1435{ /*lint --e{771}*/
1436 SCIP_DISJOINTSET* conncomps;
1437 SCIP_DISJOINTSET* compcolors;
1438 int* complastperm;
1439 int* permstoconsider;
1440 int* colorbegins;
1441 int* compidx;
1442 int* colidx;
1443 int* varidx;
1444 int* degrees;
1445 int* perm;
1446 int nposdegree = 0;
1447 int npermstoconsider;
1448 int colorrepresentative1 = -1;
1449 int colorrepresentative2 = -1;
1450 int elemtomove;
1451 int ncurcols;
1452 int curcomp1;
1453 int curcomp2;
1454 int curdeg1;
1455 int curdeg2;
1456 int curcolor1;
1457 int curcolor2;
1458 int ncolors;
1459 int cnt;
1460 int c;
1461 int p;
1462 int v;
1463 int w;
1464
1465 assert( scip != NULL );
1466 assert( perms != NULL );
1467 assert( selectedperms != NULL );
1468 assert( nselectedperms >= 0 );
1469 assert( permlen > 0 );
1470 assert( nrows > 0 || nselectedperms == 0 );
1471 assert( success != NULL );
1472 assert( matrices != NULL );
1473 assert( ncols != NULL );
1474 assert( nmatrices != NULL );
1475
1476 /* initialize data */
1477 *success = TRUE;
1478 *matrices = NULL;
1479 *ncols = NULL;
1480 *nmatrices = 0;
1481
1482 /* we have found the empty set of orbitopal symmetries */
1483 if ( nselectedperms == 0 )
1484 return SCIP_OKAY;
1485
1486 /* build a graph to encode potential orbitopal symmetries
1487 *
1488 * The 2-cycles of a permutation define a set of edges that need to be added simultaneously. We encode
1489 * this as a disjoint set data structure to only encode the connected components of the graph. To ensure
1490 * correctness, we keep track of the degrees of each node and extend a component by a permutation only if
1491 * all nodes to be extended have the same degree. We also make sure that each connected component is a
1492 * path. Although this might not detect all orbitopal symmetries, it seems to cover most of the cases when
1493 * computing symmetries using bliss. We also keep track of which variables are affected by the same
1494 * permutations by coloring the connected components.
1495 */
1496 SCIP_CALL( SCIPcreateDisjointset(scip, &conncomps, permlen) );
1497 SCIP_CALL( SCIPcreateDisjointset(scip, &compcolors, permlen) );
1498 SCIP_CALL( SCIPallocClearBufferArray(scip, &degrees, permlen) );
1499 SCIP_CALL( SCIPallocBufferArray(scip, &complastperm, permlen) );
1500 for (v = 0; v < permlen; ++v)
1501 complastperm[v] = -1;
1502
1503 /* try to add edges of permutations to graph */
1504 for (p = 0; p < nselectedperms; ++p)
1505 {
1506 perm = perms[selectedperms[p]];
1507 curdeg1 = -1;
1508 curdeg2 = -1;
1509
1510 /* check whether all potential edges can be added */
1511 for (v = 0; v < permlen; ++v)
1512 {
1513 /* treat each cycle exactly once */
1514 if ( perm[v] <= v )
1515 continue;
1516 w = perm[v];
1517
1518 curcomp1 = SCIPdisjointsetFind(conncomps, v);
1519 curcomp2 = SCIPdisjointsetFind(conncomps, w);
1520
1521 /* an edge is not allowed to connect nodes from the same connected component */
1522 if ( curcomp1 == curcomp2 )
1523 break;
1524
1525 /* permutation p is not allowed to add two edges to the same connected component */
1526 if ( complastperm[curcomp1] == p || complastperm[curcomp2] == p )
1527 break;
1528
1529 /* get colors of nodes */
1530 curcolor1 = SCIPdisjointsetFind(compcolors, v);
1531 curcolor2 = SCIPdisjointsetFind(compcolors, w);
1532
1533 /* an edge is not allowed to connect two nodes with the same color */
1534 if ( curcolor1 == curcolor2 )
1535 break;
1536
1537 if ( curdeg1 == -1 )
1538 {
1539 assert( curdeg2 == -1 );
1540
1541 curdeg1 = degrees[v];
1542 curdeg2 = degrees[w];
1543 colorrepresentative1 = curcolor1;
1544 colorrepresentative2 = curcolor2;
1545
1546 /* stop, we will generate a vertex with degree 3 */
1547 if ( curdeg1 == 2 || curdeg2 == 2 )
1548 break;
1549 }
1550 else
1551 {
1552 /* check whether nodes have compatible degrees */
1553 if ( ! ((curdeg1 == degrees[v] && curdeg2 == degrees[w])
1554 || (curdeg1 == degrees[w] && curdeg2 == degrees[v])) )
1555 break;
1556 assert( colorrepresentative1 >= 0 );
1557 assert( colorrepresentative2 >= 0 || curdeg2 == -1 );
1558
1559 /* check whether all components have compatible colors */
1560 if ( curdeg1 > 0 && curcolor1 != colorrepresentative1 && curcolor2 != colorrepresentative1 )
1561 break;
1562 if ( curdeg2 > 0 && curcolor1 != colorrepresentative2 && curcolor2 != colorrepresentative2 )
1563 break;
1564 }
1565
1566 /* store that permutation p extends the connected components */
1567 complastperm[curcomp1] = p;
1568 complastperm[curcomp2] = p;
1569 }
1570
1571 /* terminate if not all edges can be added */
1572 if ( v < permlen )
1573 {
1574 *success = FALSE;
1575 goto FREEMEMORY;
1576 }
1577 assert( curdeg1 >= 0 && curdeg2 >= 0 );
1578
1579 /* add edges to graph */
1580 for (v = 0; v < permlen; ++v)
1581 {
1582 /* treat each cycle exactly once */
1583 if ( perm[v] <= v )
1584 continue;
1585 w = perm[v];
1586
1587#ifndef NDEBUG
1588 curcomp1 = SCIPdisjointsetFind(conncomps, v);
1589 curcomp2 = SCIPdisjointsetFind(conncomps, w);
1590 assert( curcomp1 != curcomp2 );
1591#endif
1592
1593 /* add edge */
1594 SCIPdisjointsetUnion(conncomps, v, w, FALSE);
1595 ++degrees[v];
1596 ++degrees[w];
1597
1598 /* possibly update colors */
1599 curcolor1 = SCIPdisjointsetFind(compcolors, v);
1600 curcolor2 = SCIPdisjointsetFind(compcolors, w);
1601
1602 if ( curcolor1 != curcolor2 )
1603 {
1604 /* coverity[negative_returns] */
1605 SCIPdisjointsetUnion(compcolors, colorrepresentative1, v, TRUE);
1606 SCIPdisjointsetUnion(compcolors, colorrepresentative1, w, TRUE);
1607 }
1608 }
1609 }
1610
1611 /* find non-trivial components */
1612 for (v = 0; v < permlen; ++v)
1613 {
1614 if ( degrees[v] > 0 )
1615 ++nposdegree;
1616 }
1617
1618 SCIP_CALL( SCIPallocBufferArray(scip, &compidx, nposdegree) );
1619 SCIP_CALL( SCIPallocBufferArray(scip, &colidx, nposdegree) );
1620 SCIP_CALL( SCIPallocBufferArray(scip, &varidx, nposdegree) );
1621
1622 for (v = 0, w = 0; v < permlen; ++v)
1623 {
1624 if ( degrees[v] > 0 )
1625 {
1626 compidx[w] = SCIPdisjointsetFind(conncomps, v);
1627 colidx[w] = SCIPdisjointsetFind(compcolors, v);
1628#ifndef NDEBUG
1629 if ( w > 0 && compidx[w] == compidx[w-1] )
1630 assert( colidx[w] == colidx[w-1]);
1631#endif
1632 varidx[w++] = v;
1633 }
1634 }
1635 assert( w == nposdegree );
1636
1637 /* sort variable indices: first by colors, then by components */
1638 SCIP_CALL( SCIPallocBufferArray(scip, &colorbegins, permlen + 1) );
1639
1640 SCIPsortIntIntInt(colidx, compidx, varidx, nposdegree);
1641 w = 0;
1642 ncolors = 0;
1643 colorbegins[0] = 0;
1644 for (v = 1; v < nposdegree; ++v)
1645 {
1646 if ( colidx[v] != colidx[w] )
1647 {
1648 SCIPsortIntInt(&compidx[w], &varidx[w], v - w);
1649 colorbegins[++ncolors] = v;
1650 w = v;
1651 }
1652 }
1653 SCIPsortIntInt(&compidx[w], &varidx[w], nposdegree - w);
1654 colorbegins[++ncolors] = nposdegree;
1655
1656 /* try to find the correct order of variable indices per color class */
1657 SCIP_CALL( SCIPallocBufferArray(scip, &permstoconsider, nselectedperms) );
1658
1659 SCIP_CALL( SCIPallocBlockMemoryArray(scip, matrices, ncolors) );
1660 SCIP_CALL( SCIPallocBlockMemoryArray(scip, ncols, ncolors) );
1661 *nmatrices = ncolors;
1662
1663 for (c = 0; c < ncolors; ++c)
1664 {
1665 /* find an element in the first connected component with degree 1 */
1666 for (v = colorbegins[c]; compidx[v] == compidx[colorbegins[c]]; ++v)
1667 {
1668 assert( v < nposdegree ); /* there should be a node of degree 1 */
1669
1670 if ( degrees[varidx[v]] == 1 )
1671 break;
1672 }
1673 assert( compidx[v] == compidx[colorbegins[c]] );
1674 elemtomove = varidx[v];
1675
1676 /* find the permutations affecting the variables in the first connected component */
1677 npermstoconsider = 0;
1678 for (p = 0; p < nselectedperms; ++p)
1679 {
1680 perm = perms[selectedperms[p]];
1681 for (v = colorbegins[c]; v < nposdegree && compidx[v] == compidx[colorbegins[c]]; ++v)
1682 {
1683 if ( perm[varidx[v]] != varidx[v] )
1684 {
1685 permstoconsider[npermstoconsider++] = selectedperms[p];
1686 break;
1687 }
1688 }
1689 }
1690
1691 /* allocate memory for matrix */
1692 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*matrices)[c], nrows) );
1693 (*ncols)[c] = npermstoconsider + 1;
1694 for (p = 0; p < nrows; ++p)
1695 {
1696 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*matrices)[c][p], (*ncols)[c]) );
1697 }
1698
1699 /* find a permutation that moves the degree-1 element and iteratively extend this to a matrix */
1700 assert( degrees[elemtomove] == 1 );
1701
1702 /* find the first and second column */
1703 for (p = 0; p < npermstoconsider; ++p)
1704 {
1705 perm = perms[permstoconsider[p]];
1706 if ( perm[elemtomove] != elemtomove )
1707 break;
1708 }
1709 assert( p < npermstoconsider );
1710
1711 /* elements moved by perm that have degree 1 are in the first column */
1712 for (v = 0, cnt = 0; v < permlen; ++v)
1713 {
1714 if ( perm[v] > v ) /*lint !e771*/
1715 {
1716 if ( degrees[v] == 1 )
1717 {
1718 (*matrices)[c][cnt][0] = v;
1719 (*matrices)[c][cnt++][1] = perm[v];
1720 }
1721 else
1722 {
1723 (*matrices)[c][cnt][0] = perm[v];
1724 (*matrices)[c][cnt++][1] = v;
1725 }
1726 }
1727 }
1728
1729 /* if the selected permutation do not form orbitopal symmetries */
1730 if ( cnt < nrows )
1731 {
1732 *success = FALSE;
1733 for (p = nrows - 1; p >= 0; --p)
1734 {
1735 SCIPfreeBufferArray(scip, &(*matrices)[c][p]);
1736 }
1737 SCIPfreeBlockMemoryArray(scip, &(*matrices)[c], nrows);
1738 SCIPfreeBlockMemoryArray(scip, matrices, ncolors);
1739 SCIPfreeBlockMemoryArray(scip, ncols, ncolors);
1740 *matrices = NULL;
1741 *ncols = NULL;
1742 goto FREEMOREMEMORY;
1743 }
1744 assert( cnt == nrows );
1745
1746 /* remove p from the list of permutations to be considered */
1747 permstoconsider[p] = permstoconsider[--npermstoconsider];
1748
1749 ncurcols = 1;
1750 while ( npermstoconsider > 0 )
1751 {
1752 elemtomove = (*matrices)[c][0][ncurcols];
1753
1754 /* find permutation moving the elemtomove */
1755 for (p = 0; p < npermstoconsider; ++p)
1756 {
1757 perm = perms[permstoconsider[p]];
1758 if ( perm[elemtomove] != elemtomove )
1759 break;
1760 }
1761 assert( p < npermstoconsider );
1762
1763 /* extend matrix */
1764 for (v = 0; v < nrows; ++v)
1765 {
1766 assert( perm[(*matrices)[c][v][ncurcols]] != (*matrices)[c][v][ncurcols] );
1767 (*matrices)[c][v][ncurcols + 1] = perm[(*matrices)[c][v][ncurcols]];
1768 }
1769 ++ncurcols;
1770 permstoconsider[p] = permstoconsider[--npermstoconsider];
1771 }
1772 }
1773
1774 FREEMOREMEMORY:
1775 SCIPfreeBufferArray(scip, &permstoconsider);
1776 SCIPfreeBufferArray(scip, &colorbegins);
1777 SCIPfreeBufferArray(scip, &varidx);
1778 SCIPfreeBufferArray(scip, &colidx);
1779 SCIPfreeBufferArray(scip, &compidx);
1780
1781 FREEMEMORY:
1782 SCIPfreeBufferArray(scip, &complastperm);
1783 SCIPfreeBufferArray(scip, &degrees);
1784 SCIPfreeDisjointset(scip, &compcolors);
1785 SCIPfreeDisjointset(scip, &conncomps);
1786
1787 return SCIP_OKAY;
1788}
1789
1790/** checks whether two families of orbitopal symmetries define a double lex matrix, and in case of success, generates matrix
1791 *
1792 * The columns of matrix1 will serve as the columns of the matrix to be generated, the columns of matrix2 will
1793 * serve as rows.
1794 */
1795static
1797 SCIP* scip, /**< SCIP pointer */
1798 int nsymvars, /**< number of variables on which symmetries act */
1799 int*** matrices1, /**< first list of matrices associated with orbitopal symmetries */
1800 int nrows1, /**< number of rows of first family of matrices */
1801 int* ncols1, /**< for each matrix in the first family, its number of columns */
1802 int nmatrices1, /**< number of matrices in the first family */
1803 int*** matrices2, /**< second list of matrices associated with orbitopal symmetries */
1804 int nrows2, /**< number of rows of second family of matrices */
1805 int* ncols2, /**< for each matrix in the second family, its number of columns */
1806 int nmatrices2, /**< number of matrices in the second family */
1807 int*** doublelexmatrix, /**< pointer to store combined matrix */
1808 int* nrows, /**< pointer to store number of rows in combined matrix */
1809 int* ncols, /**< pointer to store number of columns in combined matrix */
1810 int** rowsbegin, /**< pointer to store the begin positions of a new lex subset of rows */
1811 int** colsbegin, /**< pointer to store the begin positions of a new lex subset of columns */
1812 SCIP_Bool* success /**< pointer to store whether combined matrix could be generated */
1813 )
1814{
1815 int* idxtomatrix1;
1816 int* idxtomatrix2;
1817 int* idxtorow1;
1818 int* idxtorow2;
1819 int* idxtocol1;
1820 int* idxtocol2;
1821 int* sortvals;
1822 int elem;
1823 int mat;
1824 int col;
1825 int col2;
1826 int mat2;
1827 int cnt;
1828 int c;
1829 int d;
1830 int i;
1831 int j;
1832
1833 assert( scip != NULL );
1834 assert( nsymvars >= 0 );
1835 assert( matrices1 != NULL );
1836 assert( nrows1 > 0 );
1837 assert( ncols1 != NULL );
1838 assert( nmatrices1 > 0 );
1839 assert( matrices2 != NULL );
1840 assert( nrows2 > 0 || nmatrices2 == 0 );
1841 assert( ncols2 != NULL );
1842 assert( nmatrices2 >= 0 );
1843 assert( doublelexmatrix != NULL );
1844 assert( nrows != NULL );
1845 assert( ncols != NULL );
1846 assert( rowsbegin != NULL );
1847 assert( colsbegin != NULL );
1848 assert( success != NULL );
1849
1850 /* initialize data */
1851 *nrows = nrows1;
1852 *ncols = nrows2;
1853 *success = TRUE;
1854
1855 /* check whether expecteded sizes of matrix match */
1856 for (j = 0, cnt = 0; j < nmatrices1; ++j)
1857 cnt += ncols1[j];
1858 if ( cnt != *ncols )
1859 {
1860 *success = FALSE;
1861 return SCIP_OKAY;
1862 }
1863
1864 for (i = 0, cnt = 0; i < nmatrices2; ++i)
1865 cnt += ncols2[i];
1866 if ( cnt != *nrows )
1867 {
1868 *success = FALSE;
1869 return SCIP_OKAY;
1870 }
1871
1872 /* collect information about entries in matrices */
1873 SCIP_CALL( SCIPallocBufferArray(scip, &idxtomatrix1, nsymvars) );
1874 SCIP_CALL( SCIPallocBufferArray(scip, &idxtomatrix2, nsymvars) );
1875 SCIP_CALL( SCIPallocBufferArray(scip, &idxtorow1, nsymvars) );
1876 SCIP_CALL( SCIPallocBufferArray(scip, &idxtorow2, nsymvars) );
1877 SCIP_CALL( SCIPallocBufferArray(scip, &idxtocol1, nsymvars) );
1878 SCIP_CALL( SCIPallocBufferArray(scip, &idxtocol2, nsymvars) );
1879
1880 /* use separate loops for efficiency reasons */
1881 for (i = 0; i < nsymvars; ++i)
1882 idxtomatrix1[i] = -1;
1883 for (i = 0; i < nsymvars; ++i)
1884 idxtomatrix2[i] = -1;
1885 for (i = 0; i < nsymvars; ++i)
1886 idxtorow1[i] = -1;
1887 for (i = 0; i < nsymvars; ++i)
1888 idxtorow2[i] = -1;
1889 for (i = 0; i < nsymvars; ++i)
1890 idxtocol1[i] = -1;
1891 for (i = 0; i < nsymvars; ++i)
1892 idxtocol2[i] = -1;
1893
1894 for (c = 0; c < nmatrices1; ++c)
1895 {
1896 for (i = 0; i < nrows1; ++i)
1897 {
1898 for (j = 0; j < ncols1[c]; ++j)
1899 {
1900 idxtomatrix1[matrices1[c][i][j]] = c;
1901 idxtorow1[matrices1[c][i][j]] = i;
1902 idxtocol1[matrices1[c][i][j]] = j;
1903 }
1904 }
1905 }
1906 for (c = 0; c < nmatrices2; ++c)
1907 {
1908 for (i = 0; i < nrows2; ++i)
1909 {
1910 for (j = 0; j < ncols2[c]; ++j)
1911 {
1912 idxtomatrix2[matrices2[c][i][j]] = c;
1913 idxtorow2[matrices2[c][i][j]] = i;
1914 idxtocol2[matrices2[c][i][j]] = j;
1915 }
1916 }
1917 }
1918
1919 /* check whether the variables of the two orbitopes coincide */
1920 for (i = 0; i < nsymvars; ++i)
1921 {
1922 if ( (idxtomatrix1[i] == -1) != (idxtomatrix2[i] == -1) )
1923 {
1924 *success = FALSE;
1925 goto FREEINITMEMORY;
1926 }
1927 }
1928
1929 /* Find a big matrix such that the columns of this matrix correspond to the columns of matrices in matrices1
1930 * and the rows of this matrix correspond to the columns of matrices in matrices2. In total, this leads to
1931 * a matrix of block shape
1932 *
1933 * A | B | ... | C
1934 * D | E | ... | F
1935 * . | . | | .
1936 * G | H | ... | I
1937 *
1938 * We start by filling the first column of the big matrix by the first column in matrices1. Sort the column
1939 * according to the matrices in matrices2.
1940 */
1941 SCIP_CALL( SCIPallocBufferArray(scip, &sortvals, MAX(*nrows, *ncols)) );
1942 SCIP_CALL( SCIPallocBlockMemoryArray(scip, doublelexmatrix, *nrows) );
1943 for (i = 0; i < *nrows; ++i)
1944 {
1945 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*doublelexmatrix)[i], *ncols) );
1946 (*doublelexmatrix)[i][0] = matrices1[0][i][0];
1947 sortvals[i] = idxtomatrix2[matrices1[0][i][0]];
1948 }
1949 SCIPsortIntPtr(sortvals, (void*) (*doublelexmatrix), *nrows);
1950
1951 /* fill first row of big matrix */
1952 mat = idxtomatrix2[(*doublelexmatrix)[0][0]];
1953 col = idxtocol2[(*doublelexmatrix)[0][0]];
1954 cnt = 0;
1955 for (j = 0; j < *ncols; ++j)
1956 {
1957 /* skip the entry that is already contained in the first column */
1958 if ( matrices2[mat][j][col] == (*doublelexmatrix)[0][0] )
1959 continue;
1960
1961 sortvals[cnt++] = idxtomatrix1[matrices2[mat][j][col]];
1962 (*doublelexmatrix)[0][cnt] = matrices2[mat][j][col];
1963 }
1964 assert( cnt == nrows2 - 1);
1965 SCIPsortIntInt(sortvals, &((*doublelexmatrix)[0][1]), cnt);
1966
1967 /* fill the remaining entries of the big matrix */
1968 for (i = 1; i < *nrows; ++i)
1969 {
1970 for (j = 1; j < *ncols; ++j)
1971 {
1972 /* get the matrices and column/row of the entry */
1973 mat = idxtomatrix1[(*doublelexmatrix)[0][j]];
1974 mat2 = idxtomatrix2[(*doublelexmatrix)[i][0]];
1975 col = idxtocol1[(*doublelexmatrix)[0][j]];
1976 col2 = idxtocol2[(*doublelexmatrix)[i][0]];
1977
1978 /* find the unique element in the col column of matrix mat and the row column of matrix mat2 */
1979 /* @todo improve this by first sorting the columns */
1980 cnt = 0;
1981 elem = -1;
1982 for (c = 0; c < *nrows; ++c)
1983 {
1984 for (d = 0; d < *ncols; ++d)
1985 {
1986 if ( matrices1[mat][c][col] == matrices2[mat2][d][col2] )
1987 {
1988 ++cnt;
1989 elem = matrices1[mat][c][col];
1990 break;
1991 }
1992 }
1993 }
1994
1995 /* stop: the columns do not overlap properly */
1996 if ( cnt != 1 )
1997 {
1998 *success = FALSE;
1999 goto FREEMEMORY;
2000 }
2001 (*doublelexmatrix)[i][j] = elem;
2002 }
2003 }
2004
2005 /* store begin positions of row and column blocks */
2006 if ( *success )
2007 {
2008 assert( nmatrices2 > 0 );
2009 SCIP_CALL( SCIPallocBlockMemoryArray(scip, rowsbegin, nmatrices2 + 1) );
2010 SCIP_CALL( SCIPallocBlockMemoryArray(scip, colsbegin, nmatrices1 + 1) );
2011 (*rowsbegin)[0] = 0;
2012 (*colsbegin)[0] = 0;
2013 for (j = 0; j < nmatrices2; ++j)
2014 (*rowsbegin)[j + 1] = (*rowsbegin)[j] + ncols2[j];
2015 for (j = 0; j < nmatrices1; ++j)
2016 (*colsbegin)[j + 1] = (*colsbegin)[j] + ncols1[j];
2017 }
2018
2019 FREEMEMORY:
2020 SCIPfreeBufferArray(scip, &sortvals);
2021
2022 if ( !(*success) )
2023 {
2024 for (i = *nrows - 1; i >= 0; --i)
2025 {
2026 SCIPfreeBlockMemoryArray(scip, &(*doublelexmatrix)[i], *ncols);
2027 }
2028 SCIPfreeBlockMemoryArray(scip, doublelexmatrix, *nrows);
2029 *doublelexmatrix = NULL;
2030 *rowsbegin = NULL;
2031 *colsbegin = NULL;
2032 }
2033
2034 FREEINITMEMORY:
2035 SCIPfreeBufferArray(scip, &idxtocol2);
2036 SCIPfreeBufferArray(scip, &idxtocol1);
2037 SCIPfreeBufferArray(scip, &idxtorow2);
2038 SCIPfreeBufferArray(scip, &idxtorow1);
2039 SCIPfreeBufferArray(scip, &idxtomatrix2);
2040 SCIPfreeBufferArray(scip, &idxtomatrix1);
2041
2042 return SCIP_OKAY;
2043}
2044
2045/** detects whether permutations define single or double lex matrices
2046 *
2047 * A single lex matrix is a matrix whose columns can be partitioned into blocks such that the
2048 * columns within each block can be permuted arbitrarily. A double lex matrix is a single lex
2049 * matrix such that also blocks of rows have the aforementioned property.
2050 */
2052 SCIP* scip, /**< SCIP pointer */
2053 SCIP_Bool detectsinglelex, /**< whether single lex matrices shall be detected */
2054 int** perms, /**< array of permutations */
2055 int nperms, /**< number of permutations in perms */
2056 int permlen, /**< number of variables in a permutation */
2057 SCIP_Bool* success, /**< pointer to store whether structure could be detected */
2058 SCIP_Bool* isorbitope, /**< pointer to store whether detected matrix is orbitopal */
2059 int*** lexmatrix, /**< pointer to store single or double lex matrix */
2060 int* nrows, /**< pointer to store number of rows of lexmatrix */
2061 int* ncols, /**< pointer to store number of columns of lexmatrix */
2062 int** lexrowsbegin, /**< pointer to store array indicating begin of new row-lexmatrix */
2063 int** lexcolsbegin, /**< pointer to store array indicating begin of new col-lexmatrix */
2064 int* nrowmatrices, /**< pointer to store number of single lex row matrices in rows */
2065 int* ncolmatrices /**< pointer to store number of single lex column matrices in rows */
2066 )
2067{
2068 int*** matricestype1 = NULL;
2069 int*** matricestype2 = NULL;
2070 int* ncolstype1 = NULL;
2071 int* ncolstype2 = NULL;
2072 int nmatricestype1 = 0;
2073 int nmatricestype2 = 0;
2074 int* permstype1;
2075 int* permstype2;
2076 int npermstype1 = 0;
2077 int npermstype2 = 0;
2078 int ncycs1 = -1;
2079 int ncycs2 = -1;
2080 int tmpncycs;
2081 int p;
2082 int i;
2083 SCIP_Bool isinvolution;
2084
2085 assert( scip != NULL );
2086 assert( perms != NULL );
2087 assert( nperms > 0 );
2088 assert( permlen > 0 );
2089 assert( success != NULL );
2090 assert( lexmatrix != NULL );
2091 assert( nrows != NULL );
2092 assert( ncols != NULL );
2093 assert( lexrowsbegin != NULL );
2094 assert( lexcolsbegin != NULL );
2095 assert( nrowmatrices != NULL );
2096 assert( ncolmatrices != NULL );
2097
2098 *success = TRUE;
2099 *isorbitope = FALSE;
2100 *nrowmatrices = 0;
2101 *ncolmatrices = 0;
2102
2103 /* arrays to store the different types of involutions */
2104 SCIP_CALL( SCIPallocBufferArray(scip, &permstype1, nperms) );
2105 SCIP_CALL( SCIPallocBufferArray(scip, &permstype2, nperms) );
2106
2107 /* check whether we can expect lexicographically sorted rows and columns */
2108 for (p = 0; p < nperms; ++p)
2109 {
2110 SCIP_CALL( isPermInvolution(perms[p], permlen, &isinvolution, &tmpncycs) );
2111
2112 /* terminate if not all permutations are involutions */
2113 if ( ! isinvolution )
2114 {
2115 *success = FALSE;
2116 goto FREEMEMORY;
2117 }
2118
2119 /* store number of cycles or terminate if too many different types of involutions */
2120 if ( ncycs1 == -1 || ncycs1 == tmpncycs )
2121 {
2122 ncycs1 = tmpncycs;
2123 permstype1[npermstype1++] = p;
2124 }
2125 else if ( ncycs2 == -1 || ncycs2 == tmpncycs )
2126 {
2127 ncycs2 = tmpncycs;
2128 permstype2[npermstype2++] = p;
2129 }
2130 else
2131 {
2132 *success = FALSE;
2133 goto FREEMEMORY;
2134 }
2135 }
2136
2137 /* for each type, check whether permutations define (disjoint) orbitopal symmetries */
2138 SCIP_CALL( detectOrbitopalSymmetries(scip, perms, permstype1, npermstype1, permlen, ncycs1, success,
2139 &matricestype1, &ncolstype1, &nmatricestype1) );
2140 if ( ! *success )
2141 goto FREEMEMORY;
2142
2143 SCIP_CALL( detectOrbitopalSymmetries(scip, perms, permstype2, npermstype2, permlen, ncycs2, success,
2144 &matricestype2, &ncolstype2, &nmatricestype2) );
2145 if ( ! *success )
2146 goto FREEMEMORY;
2147
2148 /* check whether a double lex matrix is defined */
2149 *success = FALSE;
2150 if ( !detectsinglelex && ncycs2 != -1 )
2151 {
2152 assert( ncycs1 > 0 );
2153
2154 SCIP_CALL( isDoublelLexSym(scip, permlen, matricestype1, ncycs1, ncolstype1, nmatricestype1,
2155 matricestype2, ncycs2, ncolstype2, nmatricestype2,
2156 lexmatrix, nrows, ncols, lexrowsbegin, lexcolsbegin, success) );
2157
2158 if ( *success )
2159 {
2160 *nrowmatrices = nmatricestype2;
2161 *ncolmatrices = nmatricestype1;
2162 }
2163 }
2164
2165 /* if no double lex matrix is detected, possibly return orbitope */
2166 if ( !(*success) && ncycs2 == -1 && nmatricestype1 == 1 )
2167 {
2168 SCIP_CALL( SCIPallocBlockMemoryArray(scip, lexmatrix, ncycs1) );
2169 for (i = 0; i < ncycs1; ++i)
2170 {
2171 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*lexmatrix)[i], ncolstype1[0]) );
2172 for (p = 0; p < ncolstype1[0]; ++p)
2173 (*lexmatrix)[i][p] = matricestype1[0][i][p];
2174 }
2175 *nrows = ncycs1;
2176 *ncols = ncolstype1[0];
2177 *success = TRUE;
2178 *isorbitope = TRUE;
2179 }
2180
2181 FREEMEMORY:
2182 for (p = nmatricestype2 - 1; p >= 0; --p)
2183 {
2184 for (i = ncycs2 - 1; i >= 0; --i)
2185 {
2186 SCIPfreeBlockMemoryArray(scip, &matricestype2[p][i], ncolstype2[p]);
2187 }
2188 SCIPfreeBlockMemoryArray(scip, &matricestype2[p], ncycs2);
2189 }
2190 SCIPfreeBlockMemoryArrayNull(scip, &matricestype2, nmatricestype2);
2191 SCIPfreeBlockMemoryArrayNull(scip, &ncolstype2, nmatricestype2);
2192 for (p = nmatricestype1 - 1; p >= 0; --p)
2193 {
2194 for (i = ncycs1 - 1; i >= 0; --i)
2195 {
2196 SCIPfreeBlockMemoryArray(scip, &matricestype1[p][i], ncolstype1[p]);
2197 }
2198 SCIPfreeBlockMemoryArray(scip, &matricestype1[p], ncycs1);
2199 }
2200 SCIPfreeBlockMemoryArrayNull(scip, &matricestype1, nmatricestype1);
2201 SCIPfreeBlockMemoryArrayNull(scip, &ncolstype1, nmatricestype1);
2202
2203 SCIPfreeBufferArray(scip, &permstype2);
2204 SCIPfreeBufferArray(scip, &permstype1);
2205
2206 return SCIP_OKAY;
2207}
2208
2209
2210/** helper function to test if val1 = val2 while permitting infinity-values */
2212 SCIP* scip, /**< SCIP data structure */
2213 SCIP_Real val1, /**< left-hand side value */
2214 SCIP_Real val2 /**< right-hand side value */
2215 )
2216{
2217 SCIP_Bool inf1;
2218 SCIP_Bool inf2;
2219 SCIP_Bool minf1;
2220 SCIP_Bool minf2;
2221
2222 inf1 = SCIPisInfinity(scip, val1);
2223 inf2 = SCIPisInfinity(scip, val2);
2224 if ( inf1 && inf2 )
2225 return TRUE;
2226 if ( inf1 != inf2 )
2227 return FALSE;
2228 assert( !inf1 );
2229 assert( !inf2 );
2230
2231 minf1 = SCIPisInfinity(scip, -val1);
2232 minf2 = SCIPisInfinity(scip, -val2);
2233 if ( minf1 && minf2 )
2234 return TRUE;
2235 if ( minf1 != minf2 )
2236 return FALSE;
2237 assert( !minf1 );
2238 assert( !minf2 );
2239
2240 return SCIPisEQ(scip, val1, val2);
2241}
2242
2243
2244/** helper function to test if val1 <= val2 while permitting infinity-values */
2246 SCIP* scip, /**< SCIP data structure */
2247 SCIP_Real val1, /**< left-hand side value */
2248 SCIP_Real val2 /**< right-hand side value */
2249 )
2250{
2251 SCIP_Bool inf1;
2252 SCIP_Bool inf2;
2253 SCIP_Bool minf1;
2254 SCIP_Bool minf2;
2255
2256 inf1 = SCIPisInfinity(scip, val1);
2257 inf2 = SCIPisInfinity(scip, val2);
2258 if ( inf1 && inf2 )
2259 return TRUE;
2260 if ( !inf1 && inf2 )
2261 return TRUE;
2262 if ( inf1 && !inf2 )
2263 return FALSE;
2264 assert( !inf1 );
2265 assert( !inf2 );
2266
2267 minf1 = SCIPisInfinity(scip, -val1);
2268 minf2 = SCIPisInfinity(scip, -val2);
2269 if ( minf1 && minf2 )
2270 return TRUE;
2271 if ( !minf1 && minf2 )
2272 return FALSE;
2273 if ( minf1 && !minf2 )
2274 return TRUE;
2275 assert( !minf1 );
2276 assert( !minf2 );
2277
2278 return SCIPisLE(scip, val1, val2);
2279}
2280
2281
2282/** helper function to test if val1 >= val2 while permitting infinity-values */
2284 SCIP* scip, /**< SCIP data structure */
2285 SCIP_Real val1, /**< left-hand side value */
2286 SCIP_Real val2 /**< right-hand side value */
2287 )
2288{
2289 SCIP_Bool inf1;
2290 SCIP_Bool inf2;
2291 SCIP_Bool minf1;
2292 SCIP_Bool minf2;
2293
2294 inf1 = SCIPisInfinity(scip, val1);
2295 inf2 = SCIPisInfinity(scip, val2);
2296 if ( inf1 && inf2 )
2297 return TRUE;
2298 if ( !inf1 && inf2 )
2299 return FALSE;
2300 if ( inf1 && !inf2 )
2301 return TRUE;
2302 assert( !inf1 );
2303 assert( !inf2 );
2304
2305 minf1 = SCIPisInfinity(scip, -val1);
2306 minf2 = SCIPisInfinity(scip, -val2);
2307 if ( minf1 && minf2 )
2308 return TRUE;
2309 if ( !minf1 && minf2 )
2310 return TRUE;
2311 if ( minf1 && !minf2 )
2312 return FALSE;
2313 assert( !minf1 );
2314 assert( !minf2 );
2315
2316 return SCIPisGE(scip, val1, val2);
2317}
2318
2319
2320/** helper function to test if val1 < val2 while permitting infinity-values */
2322 SCIP* scip, /**< SCIP data structure */
2323 SCIP_Real val1, /**< left-hand side value */
2324 SCIP_Real val2 /**< right-hand side value */
2325 )
2326{
2327 SCIP_Bool inf1;
2328 SCIP_Bool inf2;
2329 SCIP_Bool minf1;
2330 SCIP_Bool minf2;
2331
2332 inf1 = SCIPisInfinity(scip, val1);
2333 inf2 = SCIPisInfinity(scip, val2);
2334 if ( inf1 && inf2 )
2335 return FALSE;
2336 if ( !inf1 && inf2 )
2337 return TRUE;
2338 if ( inf1 && !inf2 )
2339 return FALSE;
2340 assert( !inf1 );
2341 assert( !inf2 );
2342
2343 minf1 = SCIPisInfinity(scip, -val1);
2344 minf2 = SCIPisInfinity(scip, -val2);
2345 if ( minf1 && minf2 )
2346 return FALSE;
2347 if ( !minf1 && minf2 )
2348 return FALSE;
2349 if ( minf1 && !minf2 )
2350 return TRUE;
2351 assert( !minf1 );
2352 assert( !minf2 );
2353
2354 return SCIPisLT(scip, val1, val2);
2355}
2356
2357
2358/** helper function to test if val1 > val2 while permitting infinity-values */
2360 SCIP* scip, /**< SCIP data structure */
2361 SCIP_Real val1, /**< left-hand side value */
2362 SCIP_Real val2 /**< right-hand side value */
2363 )
2364{
2365 SCIP_Bool inf1;
2366 SCIP_Bool inf2;
2367 SCIP_Bool minf1;
2368 SCIP_Bool minf2;
2369
2370 inf1 = SCIPisInfinity(scip, val1);
2371 inf2 = SCIPisInfinity(scip, val2);
2372 if ( inf1 && inf2 )
2373 return FALSE;
2374 if ( !inf1 && inf2 )
2375 return FALSE;
2376 if ( inf1 && !inf2 )
2377 return TRUE;
2378 assert( !inf1 );
2379 assert( !inf2 );
2380
2381 minf1 = SCIPisInfinity(scip, -val1);
2382 minf2 = SCIPisInfinity(scip, -val2);
2383 if ( minf1 && minf2 )
2384 return FALSE;
2385 if ( !minf1 && minf2 )
2386 return TRUE;
2387 if ( minf1 && !minf2 )
2388 return FALSE;
2389 assert( !minf1 );
2390 assert( !minf2 );
2391
2392 return SCIPisGT(scip, val1, val2);
2393}
SCIP_VAR * w
Definition: circlepacking.c:67
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
Constraint handler for the set partitioning / packing / covering constraints .
#define NULL
Definition: def.h:267
#define SCIP_Shortbool
Definition: def.h:99
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9591
@ SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:89
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11269
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11296
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2569
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4636
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:593
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, SYM_SYMTYPE symtype, 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:775
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:320
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:542
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2283
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:420
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2211
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_Bool issigned, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:52
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2321
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2359
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2245
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
Definition: symmetry.c:2051
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:987
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1178
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:172
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:645
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11347
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:11229
internal miscellaneous methods
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP callable library.
structs for symmetry computations
static SCIP_RETCODE detectOrbitopalSymmetries(SCIP *scip, int **perms, int *selectedperms, int nselectedperms, int permlen, int nrows, SCIP_Bool *success, int ****matrices, int **ncols, int *nmatrices)
Definition: symmetry.c:1423
static SCIP_RETCODE isPermInvolution(int *perm, int permlen, SCIP_Bool *isinvolution, int *ntwocycles)
Definition: symmetry.c:1389
static SCIP_RETCODE isDoublelLexSym(SCIP *scip, int nsymvars, int ***matrices1, int nrows1, int *ncols1, int nmatrices1, int ***matrices2, int nrows2, int *ncols2, int nmatrices2, int ***doublelexmatrix, int *nrows, int *ncols, int **rowsbegin, int **colsbegin, SCIP_Bool *success)
Definition: symmetry.c:1796
methods for handling symmetries
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for symmetry computations
@ SCIP_ORBITOPETYPE_PACKING
@ SCIP_ORBITOPETYPE_FULL
@ SCIP_ORBITOPETYPE_PARTITIONING
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62