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