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