Scippy

SCIP

Solving Constraint Integer Programs

presol_symbreak.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_symbreak.c
17  * @brief presolver for adding symmetry breaking constraints
18  * @author Marc Pfetsch
19  * @author Thomas Rehn
20  * @author Christopher Hojny
21  *
22  * This presolver adds the following symmetry breaking constraints:
23  *
24  * - minimal cover inequalities for symresacks via a constraint handler
25  *
26  * @note It is important to control the order of presolvers within SCIP in order to avoid contraditions. First, one needs
27  * to take care of presolvers that have an effect on symmetry, e.g., presol_domcol. If symmetry is computed on the
28  * original formulation, we perform this presolver at the very beginning. Otherwise, we try to compute symmetry as late
29  * as possible and then add constraints based on this information.
30  *
31  * @note Currently, we only allocate memory for pointers to symresack constraints for group generators. If further
32  * constraints are considered, we have to reallocate memory.
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #include <assert.h>
38 
39 #include <scip/cons_linear.h>
40 #include <scip/cons_orbitope.h>
41 #include <scip/cons_setppc.h>
42 #include <scip/cons_symresack.h>
43 #include <scip/misc.h>
44 #include <scip/prop_probing.h>
45 #include <scip/presol_symbreak.h>
46 #include <scip/presol_symmetry.h>
47 #include <symmetry/type_symmetry.h>
48 
49 /* presolver properties */
50 #define PRESOL_NAME "symbreak"
51 #define PRESOL_DESC "presolver for adding symmetry breaking constraints"
52 #define PRESOL_PRIORITY -10000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
53 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
54 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /**< timing for presolving */
55 
56 /* default parameters */
57 #define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
58 #define DEFAULT_ADDSYMRESACKS TRUE /**< Add inequalities for symresacks for each generator? */
59 #define DEFAULT_COMPUTEORBITS FALSE /**< Should the orbits of the symmetry group be computed? */
60 #define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
61 
62 /*
63  * Data structures
64  */
65 
66 /** presolver data */
67 struct SCIP_PresolData
68 {
69  int** perms; /**< list of permutations */
70  int nperms; /**< number of permutations in perms */
71  int npermvars; /**< number of variables affected by permutations */
72  SCIP_Real log10groupsize; /**< log10 of group size */
73  SCIP_VAR** permvars; /**< array of variables on which permutations act */
74  SCIP_Bool addedconss; /**< whether we already added symmetry breaking constraints */
75  SCIP_Bool computedsymmetry; /**< whether symmetry has been computed already */
76  SCIP_Bool conssaddlp; /**< Should the symmetry breaking constraints be added to the LP? */
77  SCIP_Bool addsymresacks; /**< Add symresack constraints for each generator? */
78  SCIP_Bool enabled; /**< run presolver? */
79  SCIP_Bool early; /**< run presolver as early as possible if symmetry has been detected in initpre() */
80  SCIP_CONS** genconss; /**< list of generated constraints */
81  int ngenconss; /**< number of generated constraints */
82  int nsymresacks; /**< number of symresack constraints */
83  SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
84  int norbitopes; /**< number of orbitope constraints */
85  int norbits; /**< number of non-trivial orbits of permutation group */
86  SCIP_Bool computeorbits; /**< whether the orbits of the symmetry group should be computed */
87  int* orbits; /**< array containing the indices of variables sorted by orbits */
88  int* orbitbegins; /**< array containing in i-th position the first position of orbit i in orbits array */
89  int ncomponents; /**< number of components of symmetry group */
90  int* npermsincomponent; /**< array containing number of permutations per component */
91  int** components; /**< array containing for each components the corresponding permutations */
92  SCIP_Shortbool* componentblocked; /**< array to store whether a component is blocked to be considered by symmetry handling techniques */
93 };
94 
95 
96 
97 /*
98  * Local methods
99  */
100 
101 
102 /** compute components of symmetry group */
103 static
105  SCIP* scip, /**< SCIP instance */
106  SCIP_PRESOLDATA* presoldata /**< data of symmetry breaking presolver */
107  )
108 {
109  SCIP_DISJOINTSET* componentstoperm = NULL;
110  SCIP_Bool startchanged;
111  int** perms;
112  int npermsincomponent;
113  int curcomponent;
114  int ncomponents;
115  int componentcnt;
116  int npermvars;
117  int nperms;
118  int newstart;
119  int start;
120  int i;
121  int j;
122  int k;
123 
124  assert( scip != NULL );
125  assert( presoldata != NULL );
126 
127  nperms = presoldata->nperms;
128 
129  presoldata->ncomponents = -1;
130 
131  if ( nperms <= 0 )
132  return SCIP_OKAY;
133 
134  /* at this point, we have at least one non-trivial permutation */
135  npermvars = presoldata->npermvars;
136  perms = presoldata->perms;
137 
138  /* if there exists only one orbit, we have exactly one component */
139  if ( presoldata->norbits == 1 )
140  ncomponents = 1;
141  else
142  {
143  /* init array that assigns to each permutation its component of the group */
144  SCIP_CALL( SCIPdisjointsetCreate(&componentstoperm, SCIPblkmem(scip), nperms) );
145  ncomponents = nperms;
146 
147  /* check whether two permutations belong to the same component */
148  for (i = 0; i < nperms && ncomponents > 1; ++i)
149  {
150  for (j = i + 1; j < nperms && ncomponents > 1; ++j)
151  {
152  int componentI;
153  int componentJ;
154  int* permI;
155  int* permJ;
156 
157  componentI = SCIPdisjointsetFind(componentstoperm, i);
158  componentJ = SCIPdisjointsetFind(componentstoperm, j);
159  if ( componentI == componentJ )
160  continue;
161 
162  permI = perms[i];
163  permJ = perms[j];
164 
165  /* Do perms[i] and perms[j] belong to the same component? */
166  for (k = 0; k < npermvars; ++k)
167  {
168  /* both permutations belong to the same component */
169  if ( permI[k] != k && permJ[k] != k )
170  {
171  /* Keep the smallest identifier to keep track of where a new component starts.
172  * Note that it is necessary to store the smaller identifier to be able to iterate
173  * over all ordered pairs (i,j), i < j, of permutations, instead of all unordered
174  * pairs {i,j}. */
175  if ( componentI < componentJ )
176  SCIPdisjointsetUnion(componentstoperm, i, j, TRUE);
177  else
178  SCIPdisjointsetUnion(componentstoperm, j, i, TRUE);
179 
180  --ncomponents;
181  break;
182  }
183  }
184  }
185  }
186  assert( ncomponents > 0 );
187  }
188 
189  /* store data */
190  presoldata->ncomponents = ncomponents;
191 
192  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &presoldata->npermsincomponent, ncomponents) );
193  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &presoldata->components, ncomponents) );
194 
195  /* copy componentstoperm adequatly to components and npermsincomponent */
196  if ( ncomponents == 1 )
197  {
198  presoldata->npermsincomponent[0] = nperms;
199 
200  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->components[0]), nperms) );
201  for (i = 0; i < nperms; ++i)
202  presoldata->components[0][i] = i;
203  }
204  else
205  {
206  componentcnt = 0;
207  start = 0;
208  newstart = 0;
209  startchanged = TRUE;
210  while ( startchanged )
211  {
212  startchanged = FALSE;
213  npermsincomponent = 0;
214  assert( componentstoperm != NULL );
215  curcomponent = SCIPdisjointsetFind(componentstoperm, start);
216 
217  /* find number of permutations in current component and detect first perm in another permutation */
218  for (i = start; i < nperms; ++i)
219  {
220  if ( SCIPdisjointsetFind(componentstoperm, i) == curcomponent )
221  ++npermsincomponent;
222  /* only store other component if it has the same identifier as its node (mark that new component starts) */
223  else if ( ! startchanged && SCIPdisjointsetFind(componentstoperm, i) == i )
224  {
225  newstart = i;
226  startchanged = TRUE;
227  }
228  }
229 
230  /* store number of permutations and permutation per component */
231  presoldata->npermsincomponent[componentcnt] = npermsincomponent;
232 
233  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->components[componentcnt]), npermsincomponent) );
234 
235  j = 0;
236  for (i = start; i < nperms; ++i)
237  {
238  if ( SCIPdisjointsetFind(componentstoperm, i) == curcomponent )
239  presoldata->components[componentcnt][j++] = i;
240  }
241 
242  ++componentcnt;
243  start = newstart;
244  }
245  }
246 
247  if ( presoldata->norbits != 1 )
248  SCIPdisjointsetFree(&componentstoperm, SCIPblkmem(scip));
249 
250  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->componentblocked), ncomponents) );
251  for (i = 0; i < ncomponents; ++i)
252  presoldata->componentblocked[i] = FALSE;
253 
254 #ifdef SCIP_OUTPUT
255  printf("\n\n\nTESTS\n\n");
256  printf("Number of components:\t\t%d\n", presoldata->ncomponents);
257  for (i = 0; i < presoldata->ncomponents; ++i)
258  {
259  printf("Component %d: Number of perms: %d\n", i, presoldata->npermsincomponent[i]);
260  for (j = 0; j < presoldata->npermsincomponent[i]; ++j)
261  {
262  printf("%d ", presoldata->components[i][j]);
263  }
264  printf("\n");
265  }
266 
267  printf("GENERATORS:");
268  for (i = 0; i < presoldata->nperms; ++i)
269  {
270  printf("generator %d:\n", i);
271  for (j = 0; j < presoldata->npermvars; ++j)
272  {
273  if ( presoldata->perms[i][j] != j )
274  printf("%d ", presoldata->perms[i][j]);
275  }
276  printf("\n");
277  }
278 #endif
279 
280  return SCIP_OKAY;
281 }
282 
283 
284 /** check whether a permutation is a composition of 2-cycles of binary variables and in this case determines the number of 2-cycles */
285 static
287  int* perm, /**< permutation */
288  SCIP_VAR** vars, /**< array of variables perm is acting on */
289  int nvars, /**< number of variables */
290  SCIP_Bool* iscompoftwocycles, /**< pointer to store whether permutation is a composition of 2-cycles */
291  int* ntwocyclesperm, /**< pointer to store number of 2-cycles */
292  SCIP_Bool* allvarsbinary /**< pointer to store whether perm is acting on binary variables only */
293  )
294 {
295  int ntwocycles = 0;
296  int i;
297 
298  assert( perm != NULL );
299  assert( iscompoftwocycles != NULL );
300  assert( ntwocyclesperm != NULL );
301  assert( allvarsbinary != NULL );
302 
303  *iscompoftwocycles = FALSE;
304  *ntwocyclesperm = 0;
305  *allvarsbinary = TRUE;
306  for (i = 0; i < nvars; ++i)
307  {
308  /* skip fixed points and avoid treating the same 2-cycle twice */
309  if ( perm[i] <= i )
310  continue;
311 
312  if ( perm[perm[i]] == i )
313  {
314  if ( SCIPvarIsBinary(vars[i]) && SCIPvarIsBinary(vars[perm[i]]) )
315  ++ntwocycles;
316  else
317  {
318  /* at least one variable is not binary */
319  *allvarsbinary = FALSE;
320  return SCIP_OKAY;
321  }
322  }
323  else
324  {
325  /* we do not have a 2-cycle */
326  return SCIP_OKAY;
327  }
328  }
329 
330  /* at this point the permutation is a composition of 2-cycles on binary variables */
331  *iscompoftwocycles = TRUE;
332  *ntwocyclesperm = ntwocycles;
333 
334  return SCIP_OKAY;
335 }
336 
337 
338 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
339  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
340  * we add one column to the suborbitope of the first nfilledcols columns.
341  *
342  * @pre Every non-trivial cycle of perm is a 2-cycle.
343  * @pre perm has nrows many 2-cycles
344  */
345 static
347  int** suborbitope, /**< matrix containing suborbitope entries */
348  int nrows, /**< number of rows of suborbitope */
349  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
350  int coltoextend, /**< index of column that should be extended by perm */
351  int* perm, /**< permutation */
352  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
353  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
354  SCIP_Bool* success, /**< pointer to store whether extension was successful */
355  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
356  )
357 {
358  int nintersections = 0;
359  int row;
360  int idx1;
361  int idx2;
362 
363  assert( suborbitope != NULL );
364  assert( nfilledcols > 0 );
365  assert( perm != NULL );
366  assert( nusedelems != NULL );
367  assert( success != NULL );
368  assert( infeasible != NULL );
369 
370  *success = FALSE;
371  *infeasible = FALSE;
372 
373  /* if we try to extend the first orbitope generator by another one,
374  * we can change the order of entries in each row of suborbitope */
375  if ( nfilledcols == 2 )
376  {
377  /* check whether each cycle of perm intersects with a row of suborbitope */
378  for (row = 0; row < nrows; ++row)
379  {
380  idx1 = suborbitope[row][0];
381  idx2 = suborbitope[row][1];
382 
383  /* if idx1 or idx2 is affected by perm, we can extend the row of the orbitope */
384  if ( idx1 != perm[idx1] )
385  {
386  /* change order of idx1 and idx2 for right extensions */
387  if ( ! leftextension )
388  {
389  suborbitope[row][0] = idx2;
390  suborbitope[row][1] = idx1;
391  }
392  suborbitope[row][2] = perm[idx1];
393  ++nintersections;
394 
395  (*nusedelems)[idx1] += 1;
396  (*nusedelems)[perm[idx1]] += 1;
397 
398  /* if an element appears too often in the orbitope matrix */
399  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
400  {
401  *infeasible = TRUE;
402  break;
403  }
404  }
405  else if ( idx2 != perm[idx2] )
406  {
407  /* change order of idx1 and idx2 for left extensions */
408  if ( leftextension )
409  {
410  suborbitope[row][0] = idx2;
411  suborbitope[row][1] = idx1;
412  }
413  suborbitope[row][2] = perm[idx2];
414  ++nintersections;
415 
416  (*nusedelems)[idx2] += 1;
417  (*nusedelems)[perm[idx2]] += 1;
418 
419  /* if an element appears too often in the orbitope matrix */
420  if ( (*nusedelems)[idx2] > 2 || (*nusedelems)[perm[idx2]] > 2 )
421  {
422  *infeasible = TRUE;
423  break;
424  }
425  }
426  }
427  }
428  else
429  {
430  /* check whether each cycle of perm intersects with a row of suborbitope */
431  for (row = 0; row < nrows; ++row)
432  {
433  idx1 = suborbitope[row][coltoextend];
434 
435  /* if idx1 is affected by perm, we can extend the row of the orbitope */
436  if ( idx1 != perm[idx1] )
437  {
438  suborbitope[row][nfilledcols] = perm[idx1];
439  ++nintersections;
440 
441  (*nusedelems)[idx1] += 1;
442  (*nusedelems)[perm[idx1]] += 1;
443 
444  /* if an element appears to often in the orbitope matrix */
445  if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
446  {
447  *infeasible = TRUE;
448  break;
449  }
450 
451  }
452  }
453  }
454 
455  /* if there are too few intersection, this is not an orbitope */
456  if ( nintersections > 0 && nintersections < nrows )
457  *infeasible = TRUE;
458  else if ( nintersections == nrows )
459  *success = TRUE;
460 
461  return SCIP_OKAY;
462 }
463 
464 
465 /** generate variable matrix for orbitope constraint handler */
466 static
468  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
469  int nrows, /**< number of rows of orbitope */
470  int ncols, /**< number of columns of orbitope */
471  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
472  int npermvars, /**< number of variables in permvars array */
473  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
474  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
475  int* nusedelems, /**< array storing how often an element was used in the orbitope */
476  SCIP_Bool* infeasible /**< pointer to store whether the potential orbitope is not an orbitope */
477  )
478 {
479  int nfilledcols = 0;
480  int curcolumn;
481  int i;
482 
483  assert( vars != NULL );
484  assert( nrows > 0 );
485  assert( ncols > 0 );
486  assert( permvars != NULL );
487  assert( npermvars > 0 );
488  assert( orbitopevaridx != NULL );
489  assert( columnorder != NULL );
490  assert( nusedelems != NULL );
491  assert( infeasible != NULL );
492 
493  curcolumn = ncols - 1;
494 
495  /* start filling vars matrix with the right-most column w.r.t. columnorder */
496  while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 )
497  {
498  for (i = 0; i < nrows; ++i)
499  {
500  assert( orbitopevaridx[i][curcolumn] < npermvars );
501  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
502 
503  /* elements in first column of orbitope have to appear exactly once in the orbitope */
504  if ( nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
505  {
506  *infeasible = TRUE;
507  break;
508  }
509 
510  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
511  }
512  --curcolumn;
513  ++nfilledcols;
514  }
515 
516  /* There are three possibilities for the structure of columnorder:
517  * 1) [0, 1, -1, -1, ..., -1]
518  * 2) [0, 1, 1, 1, ..., 1]
519  * 3) [0, 1, -1, -1, ...., -1, 1, 1, ..., 1]
520  */
521  /* Either we are in case 1) or case 3), or all columns should have been added to vars in case 2) */
522  assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
523 
524  if ( curcolumn > 1 )
525  {
526  /* add column with columnorder 1 to vars */
527  for (i = 0; i < nrows; ++i)
528  {
529  assert( orbitopevaridx[i][1] < npermvars );
530  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][1]]) );
531 
532  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][1]];
533  }
534  ++nfilledcols;
535 
536  /* add column with columnorder 0 to vars */
537  for (i = 0; i < nrows; ++i)
538  {
539  assert( orbitopevaridx[i][0] < npermvars );
540  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][0]]) );
541 
542  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][0]];
543  }
544  ++nfilledcols;
545 
546  /* add columns with a negative column order to vars */
547  if ( nfilledcols < ncols )
548  {
549  assert( ncols > 2 );
550 
551  curcolumn = 2;
552  while ( nfilledcols < ncols )
553  {
554  assert( columnorder[curcolumn] < 0 );
555 
556  for (i = 0; i < nrows; ++i)
557  {
558  assert( orbitopevaridx[i][curcolumn] < npermvars );
559  assert( SCIPvarIsBinary(permvars[orbitopevaridx[i][curcolumn]]) );
560 
561  /* elements in last column of orbitope have to appear exactly once in the orbitope */
562  if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
563  {
564  *infeasible = TRUE;
565  break;
566  }
567 
568  (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
569  }
570  ++curcolumn;
571  ++nfilledcols;
572  }
573  }
574  }
575 
576  return SCIP_OKAY;
577 }
578 
579 
580 /** check whether components of the symmetry group can be completely handled by orbitopes */
581 static
583  SCIP* scip, /**< SCIP instance */
584  SCIP_PRESOLDATA* presoldata /**< pointer to data of symbreak presolver */
585  )
586 {
587  SCIP_VAR** permvars;
588  int** components;
589  int** perms;
590  int* npermsincomponent;
591  int ncomponents;
592  int npermvars;
593  int i;
594 
595  assert( scip != NULL );
596  assert( presoldata != NULL );
597 
598  /* exit if no symmetry is present */
599  if ( presoldata->nperms == 0 )
600  return SCIP_OKAY;
601 
602  /* compute components if not done yet */
603  if ( presoldata->ncomponents == -1 )
604  {
605  SCIP_CALL( computeComponents(scip, presoldata) );
606  }
607  assert( presoldata->nperms > 0 );
608  assert( presoldata->perms != NULL );
609  assert( presoldata->npermvars > 0 );
610  assert( presoldata->permvars != NULL );
611  assert( presoldata->ncomponents > 0 );
612  assert( presoldata->components != NULL );
613  assert( presoldata->npermsincomponent != NULL );
614 
615  perms = presoldata->perms;
616  npermvars = presoldata->npermvars;
617  permvars = presoldata->permvars;
618  ncomponents = presoldata->ncomponents;
619  npermsincomponent = presoldata->npermsincomponent;
620  components = presoldata->components;
621 
622  /* iterate over components */
623  for (i = 0; i < ncomponents; ++i)
624  {
625  SCIP_VAR*** vars;
626  SCIP_CONS* cons;
627  SCIP_Bool isorbitope = TRUE;
628  SCIP_Bool* usedperm;
629  int** orbitopevaridx;
630  int* columnorder;
631  int ntwocyclescomp = -1;
632  int nfilledcols;
633  int nusedperms;
634  int* nusedelems;
635  int coltoextend;
636  int j;
637  int row;
638  SCIP_Bool infeasibleorbitope;
639 
640  /* get properties of permutations */
641  assert( npermsincomponent[i] > 0 );
642  for (j = 0; j < npermsincomponent[i]; ++j)
643  {
644  SCIP_Bool iscompoftwocycles = FALSE;
645  SCIP_Bool allvarsbinary = TRUE;
646  int ntwocyclesperm = 0;
647 
648  SCIP_CALL( getPermProperties(perms[components[i][j]], permvars, npermvars, &iscompoftwocycles, &ntwocyclesperm, &allvarsbinary) );
649 
650  /* if we are checking the first permutation */
651  if ( ntwocyclescomp == - 1 )
652  ntwocyclescomp = ntwocyclesperm;
653 
654  /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
655  if ( ntwocyclescomp == 0 || ntwocyclescomp != ntwocyclesperm || ! allvarsbinary )
656  {
657  isorbitope = FALSE;
658  break;
659  }
660  }
661 
662  /* if no orbitope was detected or orbitope has too few rows */
663  if ( ! isorbitope )
664  continue;
665  assert( ntwocyclescomp > 0 );
666 
667  /* iterate over permutations and check whether for each permutation there exists
668  * another permutation whose 2-cycles intersect pairwise in exactly one element */
669 
670  /* whether a permutation was considered to contribute to orbitope */
671  SCIP_CALL( SCIPallocBufferArray(scip, &usedperm, npermsincomponent[i]) );
672  for (j = 0; j < npermsincomponent[i]; ++j)
673  usedperm[j] = FALSE;
674  nusedperms = 0;
675 
676  /* orbitope matrix for indices of variables in permvars array */
677  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx, ntwocyclescomp) );
678  for (j = 0; j < ntwocyclescomp; ++j)
679  {
680  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent[i] + 1) ); /*lint !e866*/
681  }
682 
683  /* order of columns of orbitopevaridx */
684  SCIP_CALL( SCIPallocBufferArray(scip, &columnorder, npermsincomponent[i] + 1) );
685  for (j = 0; j < npermsincomponent[i] + 1; ++j)
686  columnorder[j] = npermsincomponent[i] + 2;
687 
688  /* count how often an element was used in the potential orbitope */
689  SCIP_CALL( SCIPallocBufferArray(scip, &nusedelems, npermvars) );
690  for (j = 0; j < npermvars; ++j)
691  nusedelems[j] = 0;
692 
693  /* fill first two columns of orbitopevaridx matrix */
694  row = 0;
695  for (j = 0; j < npermvars; ++j)
696  {
697  int permidx = components[i][0];
698 
699  /* avoid adding the same 2-cycle twice */
700  if ( perms[permidx][j] > j )
701  {
702  orbitopevaridx[row][0] = j;
703  orbitopevaridx[row++][1] = perms[permidx][j];
704  nusedelems[j] += 1;
705  nusedelems[perms[permidx][j]] += 1;
706  }
707 
708  if ( row == ntwocyclescomp )
709  break;
710  }
711  assert( row == ntwocyclescomp );
712 
713  usedperm[0] = TRUE;
714  ++nusedperms;
715  columnorder[0] = 0;
716  columnorder[1] = 1;
717  nfilledcols = 2;
718 
719  /* extend orbitopevaridx matrix to the left, i.e., iteratively find new permutations that
720  * intersect the last added left column in each row in exactly one entry, starting with
721  * column 0 */
722  coltoextend = 0;
723  for (j = 0; j < npermsincomponent[i]; ++j)
724  { /* lint --e{850} */
725  SCIP_Bool success = FALSE;
726  SCIP_Bool infeasible = FALSE;
727 
728  if ( nusedperms == npermsincomponent[i] )
729  break;
730 
731  if ( usedperm[j] )
732  continue;
733 
734  SCIP_CALL( extendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
735  perms[components[i][j]], TRUE, &nusedelems, &success, &infeasible) );
736 
737  if ( infeasible )
738  {
739  isorbitope = FALSE;
740  break;
741  }
742  else if ( success )
743  {
744  usedperm[j] = TRUE;
745  ++nusedperms;
746  coltoextend = nfilledcols;
747  columnorder[nfilledcols++] = -1; /* mark column to be filled from the left */
748  j = 0; /* reset j since previous permutations can now intersect with the latest added column */
749  }
750  }
751 
752  if ( ! isorbitope ) /*lint !e850*/
753  goto FREEDATASTRUCTURES;
754 
755  coltoextend = 1;
756  for (j = 0; j < npermsincomponent[i]; ++j)
757  { /*lint --e(850)*/
758  SCIP_Bool success = FALSE;
759  SCIP_Bool infeasible = FALSE;
760 
761  if ( nusedperms == npermsincomponent[i] )
762  break;
763 
764  if ( usedperm[j] )
765  continue;
766 
767  SCIP_CALL( extendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
768  perms[components[i][j]], FALSE, &nusedelems, &success, &infeasible) );
769 
770  if ( infeasible )
771  {
772  isorbitope = FALSE;
773  break;
774  }
775  else if ( success )
776  {
777  usedperm[j] = TRUE;
778  ++nusedperms;
779  coltoextend = nfilledcols;
780  columnorder[nfilledcols] = 1; /* mark column to be filled from the right */
781  ++nfilledcols;
782  j = 0; /* reset j since previous permutations can now intersect with the latest added column */
783  }
784  }
785 
786  if ( nusedperms < npermsincomponent[i] ) /*lint !e850*/
787  isorbitope = FALSE;
788 
789  if ( ! isorbitope )
790  goto FREEDATASTRUCTURES;
791 
792  /* we have found a potential orbitope, prepare data for orbitope conshdlr */
793  SCIP_CALL( SCIPallocBufferArray(scip, &vars, ntwocyclescomp) );
794  for (j = 0; j < ntwocyclescomp; ++j)
795  {
796  SCIP_CALL( SCIPallocBufferArray(scip, &vars[j], npermsincomponent[i] + 1) ); /*lint !e866*/
797  }
798 
799  /* prepare variable matrix (reorder columns of orbitopevaridx) */
800  infeasibleorbitope = FALSE;
801  SCIP_CALL( generateOrbitopeVarsMatrix(&vars, ntwocyclescomp, npermsincomponent[i] + 1, permvars, npermvars,
802  orbitopevaridx, columnorder, nusedelems, &infeasibleorbitope) );
803 
804  if ( ! infeasibleorbitope )
805  {
806  SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, "orbitope", vars, SCIP_ORBITOPETYPE_FULL, ntwocyclescomp, npermsincomponent[i] + 1, TRUE,
807  presoldata->conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
808 
809  SCIP_CALL( SCIPaddCons(scip, cons) );
810 
811  /* do not release constraint here - will be done later */
812  presoldata->genconss[presoldata->ngenconss] = cons;
813  ++presoldata->ngenconss;
814  ++presoldata->norbitopes;
815  presoldata->componentblocked[i] = TRUE;
816  }
817 
818  /* free data structures */
819  for (j = 0; j < ntwocyclescomp; ++j)
820  SCIPfreeBufferArray(scip, &vars[j]);
821  SCIPfreeBufferArray(scip, &vars);
822 
823  FREEDATASTRUCTURES:
824  SCIPfreeBufferArray(scip, &nusedelems);
825  SCIPfreeBufferArray(scip, &columnorder);
826  for (j = 0; j < ntwocyclescomp; ++j)
827  SCIPfreeBufferArray(scip, &orbitopevaridx[j]);
828  SCIPfreeBufferArray(scip, &orbitopevaridx);
829  SCIPfreeBufferArray(scip, &usedperm);
830  }
831 
832  return SCIP_OKAY;
833 }
834 
835 
836 /** add symresack constraints */
837 static
839  SCIP* scip, /**< SCIP instance */
840  SCIP_PRESOL* presol /**< symmetry breaking presolver */
841  )
842 {
843  SCIP_PRESOLDATA* presoldata;
844  SCIP_VAR** permvars;
845  SCIP_Bool conssaddlp;
846  int** perms;
847  int nperms;
848  int nsymresackcons = 0;
849  int npermvars;
850  int ncomponents;
851  int i;
852  int p;
853 
854  assert( scip != NULL );
855  assert( presol != NULL );
856 
857  presoldata = SCIPpresolGetData(presol);
858  assert( presoldata != NULL );
859 
860  perms = presoldata->perms;
861  nperms = presoldata->nperms;
862  permvars = presoldata->permvars;
863  npermvars = presoldata->npermvars;
864  conssaddlp = presoldata->conssaddlp;
865  ncomponents = presoldata->ncomponents;
866 
867  assert( nperms <= 0 || perms != NULL );
868  assert( permvars != NULL );
869  assert( npermvars > 0 );
870 
871  /* if we use different approaches for components of symmetry group */
872  if ( ncomponents > 0 )
873  {
874  /* loop through components */
875  for (i = 0; i < ncomponents; ++i)
876  {
877  /* skip components that were treated by different symemtry handling techniques */
878  if ( presoldata->componentblocked[i] )
879  continue;
880 
881  /* loop through perms in component i and add symresack constraints */
882  for (p = 0; p < presoldata->npermsincomponent[i]; ++p)
883  {
884  SCIP_CONS* cons;
885  int permidx = presoldata->components[i][p];
886  char name[SCIP_MAXSTRLEN];
887 
888  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_component%d_perm%d", i, p);
889  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars,
890  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
891 
892  SCIP_CALL( SCIPaddCons(scip, cons) );
893 
894  /* do not release constraint here - will be done later */
895  presoldata->genconss[presoldata->ngenconss] = cons;
896  ++presoldata->ngenconss;
897  ++presoldata->nsymresacks;
898  ++nsymresackcons;
899  SCIPdebugMsg(scip, "Added symresack constraint: %d.\n", nsymresackcons);
900  }
901  }
902  }
903  else
904  {
905  /* loop through perms and add symresack constraints */
906  for (p = 0; p < nperms; ++p)
907  {
908  SCIP_CONS* cons;
909  char name[SCIP_MAXSTRLEN];
910 
911  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_perm%d", p);
912  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[p], permvars, npermvars,
913  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
914 
915  SCIP_CALL( SCIPaddCons(scip, cons) );
916 
917  /* do not release constraint here - will be done later */
918  presoldata->genconss[presoldata->ngenconss] = cons;
919  ++presoldata->ngenconss;
920  ++presoldata->nsymresacks;
921  ++nsymresackcons;
922  SCIPdebugMsg(scip, "Added symresack constraint: %d.\n", nsymresackcons);
923  }
924  }
925 
926  return SCIP_OKAY;
927 }
928 
929 
930 /** analyze generators and add symmetry breaking constraints */
931 static
933  SCIP* scip, /**< SCIP instance */
934  SCIP_PRESOL* presol /**< presolver */
935  )
936 {
937  SCIP_PRESOLDATA* presoldata;
938 
939  assert( scip != NULL );
940  assert( presol != NULL );
941 
942  presoldata = SCIPpresolGetData(presol);
943  assert( presoldata != NULL );
944 
945  /* exit if no or only trivial symmetry group is available */
946  if ( presoldata->nperms < 1 )
947  return SCIP_OKAY;
948 
949  if ( presoldata->addsymresacks )
950  {
951  SCIP_CALL( addSymresackConss(scip, presol) );
952  }
953 
954  return SCIP_OKAY;
955 }
956 
957 
958 /*
959  * Callback methods of presolver
960  */
961 
962 
963 /** destructor of presolver to free user data (called when SCIP is exiting) */
964 static
965 SCIP_DECL_PRESOLFREE(presolFreeSymbreak)
966 { /*lint --e{715}*/
967  SCIP_PRESOLDATA* presoldata;
968 
969  assert( scip != NULL );
970  assert( presol != NULL );
971 
972  presoldata = SCIPpresolGetData(presol);
973  assert( presoldata != NULL );
974 
975  SCIPfreeMemory(scip, &presoldata);
976 
977  return SCIP_OKAY;
978 }
979 
980 
981 /** initialization method of presolver (called after problem was transformed) */
982 static
983 SCIP_DECL_PRESOLINIT(presolInitSymbreak)
984 {
985  SCIP_PRESOLDATA* presoldata;
986  int usesymmetry;
987 
988  assert( scip != NULL );
989  assert( presol != NULL );
990 
991  SCIPdebugMsg(scip, "Init method of symmetry breaking presolver ...\n");
992 
993  presoldata = SCIPpresolGetData(presol);
994  assert( presoldata != NULL );
995 
996  /* check whether we should run */
997  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
998  if ( usesymmetry == (int) SYM_HANDLETYPE_SYMBREAK )
999  presoldata->enabled = TRUE;
1000  else
1001  {
1002  presoldata->enabled = FALSE;
1003  }
1004 
1005  if ( presoldata->enabled )
1006  {
1007  /* register presolver for symmetry information */
1009  }
1010 
1011  return SCIP_OKAY;
1012 }
1013 
1014 
1015 /** deinitialization method of presolver (called before transformed problem is freed) */
1016 static
1017 SCIP_DECL_PRESOLEXIT(presolExitSymbreak)
1018 {
1019  SCIP_PRESOLDATA* presoldata;
1020  SCIP_CONS** genconss;
1021  int ngenconss;
1022  int i;
1023 
1024  assert( scip != NULL );
1025  assert( presol != NULL );
1026 
1027  SCIPdebugMsg(scip, "Exit method of symmetry breaking presolver ...\n");
1028 
1029  presoldata = SCIPpresolGetData(presol);
1030  assert( presoldata != NULL );
1031 
1032  ngenconss = presoldata->ngenconss;
1033 
1034  /* release constraints */
1035  genconss = presoldata->genconss;
1036  for (i = 0; i < ngenconss; ++i)
1037  {
1038  assert( genconss[i] != NULL );
1039  SCIP_CALL( SCIPreleaseCons(scip, &genconss[i]) );
1040  }
1041 
1042  /* reset data (necessary if another problem is read in the SCIP shell) */
1043 
1044  /* free pointers to symmetry group and binary variables */
1045  SCIPfreeBlockMemoryArrayNull(scip, &presoldata->genconss, presoldata->nperms);
1046 
1047  presoldata->genconss = NULL;
1048  presoldata->ngenconss = 0;
1049 
1050  /* free orbit structures */
1051  if ( presoldata->norbits >= 0 )
1052  {
1053  SCIPfreeBlockMemoryArray(scip, &presoldata->orbitbegins, presoldata->npermvars);
1054  SCIPfreeBlockMemoryArray(scip, &presoldata->orbits, presoldata->npermvars);
1055  }
1056 
1057  presoldata->orbitbegins = NULL;
1058  presoldata->orbits = NULL;
1059  presoldata->norbits = -1;
1060 
1061  /* free components */
1062  if ( presoldata->ncomponents > 0 )
1063  {
1064  SCIPfreeBlockMemoryArray(scip, &presoldata->componentblocked, presoldata->ncomponents);
1065  for (i = 0; i < presoldata->ncomponents; ++i)
1066  SCIPfreeBlockMemoryArray(scip, &presoldata->components[i], presoldata->npermsincomponent[i]);
1067  SCIPfreeBlockMemoryArray(scip, &presoldata->components, presoldata->ncomponents);
1068  SCIPfreeBlockMemoryArray(scip, &presoldata->npermsincomponent, presoldata->ncomponents);
1069  }
1070 
1071  presoldata->componentblocked = NULL;
1072  presoldata->components = NULL;
1073  presoldata->npermsincomponent = NULL;
1074  presoldata->ncomponents = -1;
1075 
1076  /* reset basic data */
1077  presoldata->addedconss = FALSE;
1078  presoldata->computedsymmetry = FALSE;
1079  presoldata->enabled = TRUE;
1080  presoldata->early = FALSE;
1081  presoldata->nperms = -1;
1082  presoldata->log10groupsize = -1.0;
1083  presoldata->norbitopes = 0;
1084  presoldata->nsymresacks = 0;
1085 
1086  return SCIP_OKAY;
1087 }
1088 
1089 
1090 /** presolving initialization method of presolver (called when presolving is about to begin) */
1091 static
1092 SCIP_DECL_PRESOLINITPRE(presolInitpreSymbreak)
1093 { /*lint --e{715}*/
1094  SCIP_PRESOLDATA* presoldata;
1095  int usesymmetry;
1096 
1097  assert( scip != NULL );
1098  assert( presol != NULL );
1099 
1100  presoldata = SCIPpresolGetData(presol);
1101  assert( presoldata != NULL );
1102 
1103  /* check whether we have to run the presolver at the beginning of presolving */
1104  SCIP_CALL( SCIPgetTimingSymmetry(scip, &presoldata->early) );
1105  presoldata->early = ! presoldata->early;
1106 
1107  /* check whether we should run */
1108  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1109  if ( usesymmetry == (int) SYM_HANDLETYPE_SYMBREAK )
1110  presoldata->enabled = TRUE;
1111  else
1112  {
1113  SCIP_CALL( SCIPsetIntParam(scip, "presolving/symbreak/maxrounds", 0) );
1114  presoldata->enabled = FALSE;
1115  }
1116 
1117  if ( presoldata->enabled )
1118  {
1119  /* register presolver for symmetry information */
1121  }
1122 
1123  if ( presoldata->early && presoldata->enabled )
1124  {
1125  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Executing presolver <%s> early, since symmetries are computed early.\n\n", SCIPpresolGetName(presol));
1126 
1127  SCIP_CALL( SCIPsetIntParam(scip, "presolving/" PRESOL_NAME "/priority", 90000000) );
1128  }
1129 
1130  return SCIP_OKAY;
1131 }
1132 
1133 
1134 /** execution method of presolver */
1135 static
1136 SCIP_DECL_PRESOLEXEC(presolExecSymbreak)
1137 { /*lint --e{715}*/
1138  SCIP_PRESOLDATA* presoldata;
1139  int noldfixedvars = *nfixedvars;
1140  int noldaggrvars = *naggrvars;
1141  int noldbdchgs = *nchgbds;
1142  int noldaddconss = *naddconss;
1143  int i;
1144 
1145  assert( scip != NULL );
1146  assert( presol != NULL );
1147  assert( result != NULL );
1148  assert( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING );
1149 
1150  *result = SCIP_DIDNOTRUN;
1151 
1152  presoldata = SCIPpresolGetData(presol);
1153  assert( presoldata != NULL );
1154 
1155  /* possibly skip presolver */
1156  if ( ! presoldata->enabled )
1157  return SCIP_OKAY;
1158 
1159  /* skip presolving if we are not at the end */
1160  if ( ! presoldata->early && ! SCIPisPresolveFinished(scip) )
1161  return SCIP_OKAY;
1162 
1163  /* possibly stop */
1164  if ( SCIPisStopped(scip) )
1165  return SCIP_OKAY;
1166 
1167  SCIPdebugMsg(scip, "Presolving method of symmetry breaking presolver ...\n");
1168 
1169  /* get symmetry information, if not already computed */
1170  if ( ! presoldata->computedsymmetry )
1171  {
1172  SCIPdebugMsg(scip, "Symmetry breaking presolver: computing symmetry ...\n");
1173  assert( presoldata->nperms < 0 );
1174 
1175  /* get symmetries */
1176  SCIP_CALL( SCIPgetGeneratorsSymmetry(scip, &(presoldata->npermvars), &(presoldata->permvars),
1177  &(presoldata->nperms), &(presoldata->perms), &(presoldata->log10groupsize)) );
1178 
1179  presoldata->computedsymmetry = TRUE;
1180 
1181  if ( presoldata->nperms <= 0 )
1182  {
1183  SCIPdebugMsg(scip, "Symmetry breaking presolver: no symmetry has been found, turning presolver off.\n");
1184  presoldata->enabled = FALSE;
1185  return SCIP_OKAY;
1186  }
1187  else
1188  {
1189  assert( presoldata->nperms > 0 );
1190 
1191  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->genconss), presoldata->nperms) );
1192 
1193  if ( presoldata->computeorbits )
1194  {
1195  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &presoldata->orbits, presoldata->npermvars) );
1196  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &presoldata->orbitbegins, presoldata->npermvars) );
1197 
1198  SCIP_CALL( SCIPcomputeGroupOrbitsSymbreak(scip, presoldata->permvars, presoldata->npermvars, presoldata->perms, presoldata->nperms, NULL,
1199  presoldata->orbits, presoldata->orbitbegins, &presoldata->norbits) );
1200  }
1201 
1202  if ( presoldata->detectorbitopes )
1203  {
1204  SCIP_CALL( detectOrbitopes(scip, presoldata) );
1205  }
1206  }
1207  }
1208  else if ( presoldata->nperms <= 0 )
1209  return SCIP_OKAY;
1210 
1211  /* at this point, the symmetry group should be computed and nontrivial */
1212  assert( presoldata->nperms > 0 );
1213  *result = SCIP_DIDNOTFIND;
1214 
1215  /* deactivate presolvers that may conflict with symmetry handling routines */
1216  SCIP_CALL( SCIPsetIntParam(scip, "presolving/domcol/maxrounds", 0) );
1217 
1218  /* possibly stop */
1219  if ( SCIPisStopped(scip) )
1220  return SCIP_OKAY;
1221 
1222  /* if not already done, add symmetry breaking constraints */
1223  if ( ! presoldata->addedconss )
1224  {
1225  /* add symmetry breaking constraints */
1226  int noldngenconns = presoldata->ngenconss;
1227 
1229 
1230  presoldata->addedconss = TRUE;
1231  *naddconss += presoldata->ngenconss - noldngenconns;
1232  SCIPdebugMsg(scip, "Added symmetry breaking constraints: %d.\n", presoldata->ngenconss - noldngenconns);
1233 
1234  /* if constraints have been added, loop through generated constraints and presolve each */
1235  for (i = 0; i < presoldata->ngenconss; ++i)
1236  {
1237  SCIP_CALL( SCIPpresolCons(scip, presoldata->genconss[i], nrounds, SCIP_PRESOLTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
1238  nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
1239  nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
1240 
1241  /* exit if cutoff has been detected */
1242  if ( *result == SCIP_CUTOFF || *result == SCIP_UNBOUNDED )
1243  {
1244  SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(presoldata->genconss[i]));
1245  return SCIP_OKAY;
1246  }
1247  }
1248  SCIPdebugMsg(scip, "Presolved %d constraints generated by symbreak.\n", presoldata->ngenconss);
1249  }
1250 
1251  /* determine success */
1252  if ( *naddconss + *nchgbds + *naggrvars + *nfixedvars > noldaddconss + noldbdchgs + noldaggrvars + noldfixedvars )
1253  *result = SCIP_SUCCESS;
1254 
1255  return SCIP_OKAY;
1256 }
1257 
1258 
1259 /*
1260  * presolver specific interface methods
1261  */
1262 
1263 /** creates the symbreak presolver and includes it in SCIP */
1265  SCIP* scip /**< SCIP data structure */
1266  )
1267 {
1268  SCIP_PRESOLDATA* presoldata = NULL;
1269  SCIP_PRESOL* presol;
1270 
1271  /* create presolver data */
1272  SCIP_CALL( SCIPallocMemory(scip, &presoldata) );
1273 
1274  /* we must call the constructor explictly, because memory was m'alloced and not new'ed */
1275  presoldata->addedconss = FALSE;
1276  presoldata->computedsymmetry = FALSE;
1277  presoldata->enabled = TRUE;
1278  presoldata->early = FALSE;
1279  presoldata->nsymresacks = 0;
1280  presoldata->norbitopes = 0;
1281  presoldata->ngenconss = 0;
1282  presoldata->genconss = NULL;
1283  presoldata->nperms = -1;
1284  presoldata->log10groupsize = -1.0;
1285  presoldata->norbits = -1;
1286  presoldata->orbits = NULL;
1287  presoldata->orbitbegins = NULL;
1288  presoldata->ncomponents = -1;
1289  presoldata->npermsincomponent = NULL;
1290  presoldata->components = NULL;
1291  presoldata->componentblocked = NULL;
1292 
1293  /* include presolver */
1295  presolExecSymbreak, presoldata) );
1296 
1297  /* set additional callbacks */
1298  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeSymbreak) );
1299  SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitSymbreak) );
1300  SCIP_CALL( SCIPsetPresolExit(scip, presol, presolExitSymbreak) );
1301  SCIP_CALL( SCIPsetPresolInitpre(scip, presol, presolInitpreSymbreak) );
1302 
1303  /* add symmetry breaking presolver parameters */
1305  "presolving/" PRESOL_NAME "/conssaddlp",
1306  "Should the symmetry breaking constraints be added to the LP?",
1307  &presoldata->conssaddlp, TRUE, DEFAULT_CONSSADDLP, NULL, NULL) );
1308 
1310  "presolving/" PRESOL_NAME "/addsymresacks",
1311  "Add inequalities for symresacks for each generator?",
1312  &presoldata->addsymresacks, TRUE, DEFAULT_ADDSYMRESACKS, NULL, NULL) );
1313 
1315  "presolving/" PRESOL_NAME "/computeorbits",
1316  "Should the orbits of the symmetry group be computed?",
1317  &presoldata->computeorbits, TRUE, DEFAULT_COMPUTEORBITS, NULL, NULL) );
1318 
1320  "presolving/" PRESOL_NAME "/detectorbitopes",
1321  "Should we check whether the components of the symmetry group can be handled by orbitopes?",
1322  &presoldata->detectorbitopes, TRUE, DEFAULT_DETECTORBITOPES, NULL, NULL) );
1323 
1324  return SCIP_OKAY;
1325 }
1326 
1327 
1328 /** compute non-trivial orbits of symmetry group
1329  *
1330  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
1331  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
1332  * consecutively in the orbits array. The variables of the i-th orbit have indices
1333  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
1334  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
1335  */
1337  SCIP* scip, /**< SCIP instance */
1338  SCIP_VAR** permvars, /**< variables considered by symbreak presolver */
1339  int npermvars, /**< length of a permutation array */
1340  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
1341  int nperms, /**< number of permutations encoded in perms */
1342  SCIP_Shortbool* activeperms, /**< array for marking active permutations (or NULL) */
1343  int* orbits, /**< array of non-trivial orbits */
1344  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
1345  int* norbits /**< pointer to number of orbits currently stored in orbits */
1346  )
1347 {
1348  SCIP_Shortbool* varadded;
1349  int* curorbit;
1350  int i;
1351  int curorbitsize;
1352  int beginneworbit = 0;
1353 
1354  assert( scip != NULL );
1355  assert( permvars != NULL );
1356  assert( perms != NULL );
1357  assert( nperms > 0 );
1358  assert( npermvars > 0 );
1359  assert( orbits != NULL );
1360  assert( norbits != NULL );
1361 
1362  /* init data structures*/
1363  SCIP_CALL( SCIPallocBufferArray(scip, &curorbit, npermvars) );
1364  SCIP_CALL( SCIPallocBufferArray(scip, &varadded, npermvars) );
1365 
1366  /* initially, every variable is contained in no orbit */
1367  for (i = 0; i < npermvars; ++i)
1368  varadded[i] = FALSE;
1369 
1370  /* find variable orbits */
1371  *norbits = 0;
1372  for (i = 0; i < npermvars; ++i)
1373  {
1374  /* if variable is not contained in an orbit of a previous variable */
1375  if ( ! varadded[i] )
1376  {
1377  int j;
1378  int p;
1379  int curelem;
1380  int image;
1381 
1382  /* compute and store orbit if it is non-trivial */
1383  curorbit[0] = i;
1384  curorbitsize = 1;
1385  varadded[i] = TRUE;
1386 
1387  /* iterate over variables in curorbit and compute their images */
1388  for (j = 0; j < curorbitsize; ++j)
1389  {
1390  curelem = curorbit[j];
1391 
1392  for (p = 0; p < nperms; ++p)
1393  {
1394  if ( activeperms == NULL || activeperms[p] )
1395  {
1396  image = perms[p][curelem];
1397 
1398  /* found new element of the orbit of i */
1399  if ( ! varadded[image] )
1400  {
1401  curorbit[curorbitsize++] = image;
1402  varadded[image] = TRUE;
1403  }
1404  }
1405  }
1406  }
1407 
1408  if ( curorbitsize > 1 )
1409  {
1410  orbitbegins[*norbits] = beginneworbit;
1411  for (j = 0; j < curorbitsize; ++j)
1412  orbits[beginneworbit++] = curorbit[j];
1413 
1414  ++(*norbits);
1415  }
1416  }
1417  }
1418 
1419  /* store end in "last" orbitbegins entry */
1420  assert( *norbits < npermvars );
1421  orbitbegins[*norbits] = beginneworbit;
1422 
1423 #ifdef SCIP_OUTPUT
1424  printf("Orbits (total number: %d):\n", *norbits);
1425  for (i = 0; i < *norbits; ++i)
1426  {
1427  int j;
1428 
1429  printf("%d: ", i);
1430  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
1431  printf("%d ", orbits[j]);
1432  printf("\n");
1433  }
1434 #endif
1435 
1436  /* free memory */
1437  SCIPfreeBufferArray(scip, &varadded);
1438  SCIPfreeBufferArray(scip, &curorbit);
1439 
1440  return SCIP_OKAY;
1441 }
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip.c:6917
#define PRESOL_MAXROUNDS
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6968
#define PRESOL_DESC
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:10403
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: scip.c:7000
static SCIP_DECL_PRESOLEXIT(presolExitSymbreak)
#define PRESOL_TIMING
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
static SCIP_DECL_PRESOLINIT(presolInitSymbreak)
#define FALSE
Definition: def.h:64
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_RETCODE getPermProperties(int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
#define SYM_HANDLETYPE_SYMBREAK
Definition: type_symmetry.h:53
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:466
SCIP_RETCODE SCIPcomputeGroupOrbitsSymbreak(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Shortbool *activeperms, int *orbits, int *orbitbegins, int *norbits)
presolver for adding symmetry breaking constraints
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPdebugMsg
Definition: scip.h:455
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PRESOLDATA *presoldata)
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
constraint handler for symresack constraints
#define SYM_SPEC_BINARY
Definition: type_symmetry.h:34
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
Definition: scip.c:1054
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:22551
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12585
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:10455
#define PRESOL_NAME
#define SYM_SPEC_INTEGER
Definition: type_symmetry.h:33
SCIP_RETCODE SCIPpresolCons(SCIP *scip, SCIP_CONS *cons, int nrounds, SCIP_PRESOLTIMING presoltiming, int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, int *nfixedvars, int *naggrvars, int *nchgvartypes, int *nchgbds, int *naddholes, int *ndelconss, int *naddconss, int *nupgdconss, int *nchgcoefs, int *nchgsides, SCIP_RESULT *result)
Definition: scip.c:28955
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
static SCIP_DECL_PRESOLEXEC(presolExecSymbreak)
SCIP_RETCODE SCIPgetTimingSymmetry(SCIP *scip, SCIP_Bool *afterpresolve)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip.c:6984
#define PRESOL_PRIORITY
internal miscellaneous methods
#define SCIP_Shortbool
Definition: def.h:69
static SCIP_RETCODE generateOrbitopeVarsMatrix(SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip.c:4451
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:10376
#define SCIP_CALL(x)
Definition: def.h:350
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
static SCIP_DECL_PRESOLFREE(presolFreeSymbreak)
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINITPRE((*presolinitpre)))
Definition: scip.c:7016
SCIP_RETCODE SCIPregisterSymmetry(SCIP *scip, SYM_HANDLETYPE symtype, SYM_SPEC type, SYM_SPEC fixedtype)
#define DEFAULT_CONSSADDLP
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
static SCIP_DECL_PRESOLINITPRE(presolInitpreSymbreak)
static SCIP_RETCODE extendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
#define SCIP_Bool
Definition: def.h:61
#define DEFAULT_ADDSYMRESACKS
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
static SCIP_RETCODE addSymmetryBreakingConstraints(SCIP *scip, SCIP_PRESOL *presol)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
static SCIP_RETCODE computeComponents(SCIP *scip, SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PRESOL *presol)
#define SCIP_PRESOLTIMING_ALWAYS
Definition: type_timing.h:49
Constraint handler for linear constraints in their most general form, .
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:22567
type definitions for symmetry computations
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27755
probing propagator
presolver for storing symmetry information about current problem
#define SYM_SPEC_REAL
Definition: type_symmetry.h:35
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define DEFAULT_DETECTORBITOPES
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:10336
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
#define DEFAULT_COMPUTEORBITS
SCIP_RETCODE SCIPincludePresolSymbreak(SCIP *scip)
SCIP_RETCODE SCIPgetGeneratorsSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, int *nperms, int ***perms, SCIP_Real *log10groupsize)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239