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