Scippy

SCIP

Solving Constraint Integer Programs

presol_symmetry.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-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_symmetry.c
17  * @brief presolver for storing symmetry information about current problem
18  * @author Marc Pfetsch
19  * @author Thomas Rehn
20  *
21  * This presolver computes symmetries of the problem and stores this information in adequate form. It does not
22  * perform additional actions. The symmetry information can be accessed through external functions. However, the user
23  * has to declare the type of symmetry that is needed before execution, see SYMsetSpecRequirement().
24  *
25  * @note We treat implict integer variables as if they were continuous/real variables. The reason is that there is
26  * currently no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables
27  * hurt our code more than continuous/real variables (we basically do not handle integral variables at all).
28  *
29  * @note We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
30  * symmetry might inhibit heuristics. But note that solving the a sub-SCIP might then happen without symmetry
31  * information!
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <scip/cons_linear.h>
37 #include <scip/cons_knapsack.h>
38 #include <scip/cons_varbound.h>
39 #include <scip/cons_setppc.h>
40 #include <scip/cons_and.h>
41 #include <scip/cons_logicor.h>
42 #include <scip/cons_or.h>
43 #include <scip/cons_xor.h>
44 
45 #include <scip/presol_symmetry.h>
47 
48 #include <string.h>
49 
50 /* presolver properties */
51 #define PRESOL_NAME "symmetry"
52 #define PRESOL_DESC "presolver for computing and storing symmetry information about current problem"
53 #define PRESOL_PRIORITY 0 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
54 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
55 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
56 
57 /* default parameter values */
58 #define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
59 #define DEFAULT_COMPUTEPRESOLVED TRUE /**< Should the symmetry be computed after presolving (otherwise before presol)? */
60 #define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
61 
62 /* other defines */
63 #define MAXGENNUMERATOR 64000000 /**< determine maximal number of generators by dividing this number by the number of variables */
64 
65 
66 /** presolver data */
67 struct SCIP_PresolData
68 {
69  SCIP_Bool computepresolved; /**< Should the symmetry be computed afer presolving (otherwise before presol)? */
70  int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
71  SCIP_Bool checksymmetries; /**< Should all symmetries be checked after computation? */
72  SYM_HANDLETYPE symtype; /**< type of symmetry of registered calling function */
73  SYM_SPEC symspecrequire; /**< symmetry specification for which we need to compute symmetries */
74  SYM_SPEC symspecrequirefixed;/**< symmetry specification of variables which must be fixed by symmetries */
75  int npermvars; /**< number of variables for permutations */
76  SCIP_VAR** permvars; /**< variables on which permutations act */
77  SCIP_Real* permvarsobj; /**< objective values of permuted variables (for debugging) */
78  int nperms; /**< number of permutations */
79  int nmaxperms; /**< maximal number of permutations (needed for freeing storage) */
80  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
81  SCIP_Real log10groupsize; /**< log10 of size of symmetry group */
82  SCIP_Bool computedsym; /**< Have we already tried to compute symmetries? */
83  SCIP_Bool successful; /**< Was the computation of symmetries successful? */
84  int oldmaxpreroundscomponents; /**< original value of parameter constraints/components/maxprerounds */
85  int oldmaxroundsdomcol; /**< original value of parameter presolving/maxrounds/domcol */
86  int oldmaxpreroundsdualfix; /**< original value of parameter propagating/dualfix/maxprerounds */
87  int oldfreqdualfix; /**< original value of parameter propagating/dualfix/freq */
88  SCIP_Bool changeddefaultparams; /**< whether default parameters were changed */
89 };
90 
91 
92 /*
93  * local data structures
94  */
95 
96 /* ------------------- map for variable types ------------------- */
97 
98 /** gets the key of the given element */
99 static
100 SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
101 { /*lint --e{715}*/
102  return elem;
103 }
104 
105 /** returns TRUE iff both keys are equal
106  *
107  * Compare the types of two variables according to objective, lower and upper bound, and variable type.
108  */
109 static
110 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQVartype)
111 {
112  SCIP* scip;
113  SYM_VARTYPE* k1;
114  SYM_VARTYPE* k2;
115 
116  scip = (SCIP*) userptr;
117  k1 = (SYM_VARTYPE*) key1;
118  k2 = (SYM_VARTYPE*) key2;
119 
120  /* first check objective coefficients */
121  if ( ! SCIPisEQ(scip, k1->obj, k2->obj) )
122  return FALSE;
123 
124  /* if still undecided, take lower bound */
125  if ( ! SCIPisEQ(scip, k1->lb, k2->lb) )
126  return FALSE;
127 
128  /* if still undecided, take upper bound */
129  if ( ! SCIPisEQ(scip, k1->ub, k2->ub) )
130  return FALSE;
131 
132  /* if still undecided, take variable type */
133  if ( k1->type != k2->type )
134  return FALSE;
135 
136  return TRUE;
137 }
138 
139 /** returns the hash value of the key */
140 static
141 SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
142 { /*lint --e{715}*/
143  SYM_VARTYPE* k;
144 
145  k = (SYM_VARTYPE*) key;
146 
148 }
149 
150 
151 /* ------------------- sorting function for rhs types ------------------- */
152 
153 /** data struct to store arrays used for sorting rhs types */
155 {
156  SCIP_Real* vals; /**< array of values */
157  SYM_RHSSENSE* senses; /**< array of senses of rhs */
158  int nrhscoef; /**< size of arrays (for debugging) */
159 };
161 
162 /** sort rhs types - first by sense, then by value
163  *
164  * Due to numerical issues, we first sort by sense, then by value.
165  *
166  * result:
167  * < 0: ind1 comes before (is better than) ind2
168  * = 0: both indices have the same value
169  * > 0: ind2 comes after (is worse than) ind2
170  */
171 static
172 SCIP_DECL_SORTINDCOMP(SYMsortRhsTypes)
173 {
174  SYM_SORTRHSTYPE* data;
175  SCIP_Real diffvals;
176 
177  data = (SYM_SORTRHSTYPE*) dataptr;
178  assert( 0 <= ind1 && ind1 < data->nrhscoef );
179  assert( 0 <= ind2 && ind2 < data->nrhscoef );
180 
181  /* first sort by senses */
182  if ( data->senses[ind1] < data->senses[ind2] )
183  return -1;
184  else if ( data->senses[ind1] > data->senses[ind2] )
185  return 1;
186 
187  /* senses are equal, use values */
188  diffvals = data->vals[ind1] - data->vals[ind2];
189 
190  if ( diffvals < 0.0 )
191  return -1;
192  else if ( diffvals > 0.0 )
193  return 1;
194 
195  return 0;
196 }
197 
198 /** sort matrix coefficients
199  *
200  * result:
201  * < 0: ind1 comes before (is better than) ind2
202  * = 0: both indices have the same value
203  * > 0: ind2 comes after (is worse than) ind2
204  */
205 static
206 SCIP_DECL_SORTINDCOMP(SYMsortMatCoef)
207 {
208  SCIP_Real diffvals;
209  SCIP_Real* vals;
210 
211  vals = (SCIP_Real*) dataptr;
212  diffvals = vals[ind1] - vals[ind2];
213 
214  if ( diffvals < 0.0 )
215  return -1;
216  else if ( diffvals > 0.0 )
217  return 1;
218 
219  return 0;
220 }
221 
222 
223 /*
224  * Local methods
225  */
226 
227 /** determines whether variable should be fixed by permutations */
228 static
230  SYM_SPEC fixedtype, /**< bitset of variable types that should be fixed */
231  SCIP_VAR* var /**< variable to be considered */
232  )
233 {
234  if ( (fixedtype & SYM_SPEC_INTEGER) && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER )
235  return TRUE;
236  if ( (fixedtype & SYM_SPEC_BINARY) && SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
237  return TRUE;
238  if ( (fixedtype & SYM_SPEC_REAL) &&
240  return TRUE;
241  return FALSE;
242 }
243 
244 
245 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
246  *
247  * @note @p constant needs to be initialized!
248  */
249 static
251  SCIP* scip, /**< SCIP data structure */
252  SCIP_VAR*** vars, /**< pointer to vars array to get active variables for */
253  SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
254  int* nvars, /**< pointer to number of variables and values in vars and vals array */
255  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
256  SCIP_Bool transformed /**< transformed constraint? */
257  )
258 {
259  int requiredsize;
260  int v;
261 
262  assert( scip != NULL );
263  assert( vars != NULL );
264  assert( scalars != NULL );
265  assert( *vars != NULL );
266  assert( *scalars != NULL );
267  assert( nvars != NULL );
268  assert( constant != NULL );
269 
270  if ( transformed )
271  {
272  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
273 
274  if ( requiredsize > *nvars )
275  {
276  SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) );
277  SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) );
278 
279  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
280  assert( requiredsize <= *nvars );
281  }
282  }
283  else
284  {
285  for (v = 0; v < *nvars; ++v)
286  {
287  SCIP_CALL( SCIPvarGetOrigvarSum(&(*vars)[v], &(*scalars)[v], constant) );
288  }
289  }
290  return SCIP_OKAY;
291 }
292 
293 
294 /** fill in matrix elements into coefficient arrays */
295 static
297  SCIP* scip, /**< SCIP data structure */
298  SCIP_VAR** linvars, /**< array of linear variables */
299  SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */
300  int nlinvars, /**< number of linear variables */
301  SCIP_Real lhs, /**< left hand side */
302  SCIP_Real rhs, /**< right hand side */
303  SCIP_Bool istransformed, /**< whether the constraint is transformed */
304  SYM_RHSSENSE rhssense, /**< identifier of constraint type */
305  SYM_MATRIXDATA* matrixdata /**< matrix data to be filled in */
306  )
307 {
308  SCIP_VAR** vars;
309  SCIP_Real* vals;
310  SCIP_Real constant = 0.0;
311  int nrhscoef;
312  int nmatcoef;
313  int nvars;
314  int j;
315 
316  assert( scip != NULL );
317  assert( nlinvars == 0 || linvars != NULL );
318  assert( lhs <= rhs );
319 
320  /* do nothing if constraint is empty */
321  if ( nlinvars == 0 )
322  return SCIP_OKAY;
323 
324  /* ignore redundant constraints */
325  if ( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
326  return SCIP_OKAY;
327 
328  /* duplicate variable and value array */
329  nvars = nlinvars;
330  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, linvars, nvars) );
331  if ( linvals != NULL )
332  {
333  SCIP_CALL( SCIPduplicateBufferArray(scip, &vals, linvals, nvars) );
334  }
335  else
336  {
337  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
338  for (j = 0; j < nvars; ++j)
339  vals[j] = 1.0;
340  }
341  assert( vars != NULL );
342  assert( vals != NULL );
343 
344  /* get active variables */
345  SCIP_CALL( getActiveVariables(scip, &vars, &vals, &nvars, &constant, istransformed) );
346 
347  /* check whether constraint is empty after transformation to active variables */
348  if ( nvars <= 0 )
349  {
350  SCIPfreeBufferArray(scip, &vals);
351  SCIPfreeBufferArray(scip, &vars);
352  return SCIP_OKAY;
353  }
354 
355  /* handle constant */
356  if ( ! SCIPisInfinity(scip, -lhs) )
357  lhs -= constant;
358  if ( ! SCIPisInfinity(scip, rhs) )
359  rhs -= constant;
360 
361  /* check whether we have to resize; note that we have to add 2 * nvars since two inequalities may be added */
362  if ( matrixdata->nmatcoef + 2 * nvars > matrixdata->nmaxmatcoef )
363  {
364  int newsize;
365 
366  newsize = SCIPcalcMemGrowSize(scip, matrixdata->nmatcoef + 2 * nvars);
367  assert( newsize >= 0 );
368  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matidx), matrixdata->nmaxmatcoef, newsize) );
369  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matrhsidx), matrixdata->nmaxmatcoef, newsize) );
370  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matvaridx), matrixdata->nmaxmatcoef, newsize) );
371  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matcoef), matrixdata->nmaxmatcoef, newsize) );
372  SCIPdebugMsg(scip, "Resized matrix coefficients from %u to %d.\n", matrixdata->nmaxmatcoef, newsize);
373  matrixdata->nmaxmatcoef = newsize;
374  }
375 
376  nrhscoef = matrixdata->nrhscoef;
377  nmatcoef = matrixdata->nmatcoef;
378 
379  /* check lhs/rhs */
380  if ( SCIPisEQ(scip, lhs, rhs) )
381  {
382  assert( ! SCIPisInfinity(scip, rhs) );
383 
384  /* equality constraint */
385  matrixdata->rhscoef[nrhscoef] = rhs;
386  /* if we deal with special constraints */
387  if ( (int) rhssense >= 3 )
388  matrixdata->rhssense[nrhscoef] = rhssense;
389  else
390  matrixdata->rhssense[nrhscoef] = SYM_SENSE_EQUATION;
391  matrixdata->rhsidx[nrhscoef] = nrhscoef;
392 
393  for (j = 0; j < nvars; ++j)
394  {
395  assert( nmatcoef < matrixdata->nmaxmatcoef );
396 
397  matrixdata->matidx[nmatcoef] = nmatcoef;
398  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
399 
400  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
401 
402  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
403  matrixdata->matcoef[nmatcoef++] = vals[j];
404  }
405  nrhscoef++;
406  }
407  else
408  {
409  if ( ! SCIPisInfinity(scip, -lhs) )
410  {
411  matrixdata->rhscoef[nrhscoef] = -lhs;
412  matrixdata->rhssense[nrhscoef] = SYM_SENSE_INEQUALITY;
413  matrixdata->rhsidx[nrhscoef] = nrhscoef;
414 
415  for (j = 0; j < nvars; ++j)
416  {
417  assert( nmatcoef < matrixdata->nmaxmatcoef );
418  matrixdata->matidx[nmatcoef] = nmatcoef;
419  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
420  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
421 
422  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
423 
424  matrixdata->matcoef[nmatcoef++] = -vals[j];
425  }
426  nrhscoef++;
427  }
428 
429  if ( ! SCIPisInfinity(scip, rhs) )
430  {
431  matrixdata->rhscoef[nrhscoef] = rhs;
432  matrixdata->rhssense[nrhscoef] = SYM_SENSE_INEQUALITY;
433  matrixdata->rhsidx[nrhscoef] = nrhscoef;
434 
435  for (j = 0; j < nvars; ++j)
436  {
437  assert( nmatcoef < matrixdata->nmaxmatcoef );
438  matrixdata->matidx[nmatcoef] = nmatcoef;
439  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
440 
441  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
442 
443  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
444  matrixdata->matcoef[nmatcoef++] = vals[j];
445  }
446  nrhscoef++;
447  }
448  }
449  matrixdata->nrhscoef = nrhscoef;
450  matrixdata->nmatcoef = nmatcoef;
451 
452  SCIPfreeBufferArray(scip, &vals);
453  SCIPfreeBufferArray(scip, &vars);
454 
455  return SCIP_OKAY;
456 }
457 
458 
459 /** checks whether given permutations form a symmetry of a MIP
460  *
461  * We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed
462  * in the right order to easily check rows. The rhs is used because of cache effects.
463  */
464 static
466  SCIP* scip, /**< SCIP data structure */
467  SYM_SPEC fixedtype, /**< variable types that must be fixed by symmetries */
468  SYM_MATRIXDATA* matrixdata, /**< matrix data */
469  int nperms, /**< number of permutations */
470  int** perms /**< permutations */
471  )
472 {
473  SCIP_Real* permrow = 0;
474  int* rhsmatbeg = 0;
475  int oldrhs;
476  int j;
477  int p;
478 
479  SCIPdebugMsg(scip, "Checking whether symmetries are symmetries (generators: %u).\n", nperms);
480 
481  /* set up dense arrow for permuted row */
482  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &permrow, matrixdata->npermvars) );
483 
484  /* set up map between rows and first entry in matcoef array */
485  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rhsmatbeg, matrixdata->nrhscoef) );
486  for (j = 0; j < matrixdata->nrhscoef; ++j)
487  rhsmatbeg[j] = -1;
488 
489  /* build map from rhs into matrix */
490  oldrhs = -1;
491  for (j = 0; j < matrixdata->nmatcoef; ++j)
492  {
493  int rhs;
494 
495  rhs = matrixdata->matrhsidx[j];
496  if ( rhs != oldrhs )
497  {
498  assert( 0 <= rhs && rhs < matrixdata->nrhscoef );
499  rhsmatbeg[rhs] = j;
500  oldrhs = rhs;
501  }
502  }
503 
504  /* create row */
505  for (j = 0; j < matrixdata->npermvars; ++j)
506  permrow[j] = 0.0;
507 
508  /* check all generators */
509  for (p = 0; p < nperms; ++p)
510  {
511  int* P;
512  int r1;
513  int r2;
514 
515  SCIPdebugMsg(scip, "Verifying automorphism group generator #%d ...\n", p);
516  P = perms[p];
517  assert( P != NULL );
518 
519  for (j = 0; j < matrixdata->npermvars; ++j)
520  {
521  if ( SymmetryFixVar(fixedtype, matrixdata->permvars[j]) && P[j] != j )
522  {
523  SCIPdebugMsg(scip, "Permutation does not fix types %u, moving variable %d.\n", fixedtype, j);
524  return SCIP_ERROR;
525  }
526  }
527 
528  /* check all constraints == rhs */
529  for (r1 = 0; r1 < matrixdata->nrhscoef; ++r1)
530  {
531  int npermuted = 0;
532 
533  /* fill row into permrow (dense) */
534  j = rhsmatbeg[r1];
535  assert( 0 <= j && j < matrixdata->nmatcoef );
536  assert( matrixdata->matrhsidx[j] == r1 ); /* note: row cannot be empty by construction */
537 
538  /* loop through row */
539  while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r1 )
540  {
541  int varidx;
542 
543  assert( matrixdata->matvaridx[j] < matrixdata->npermvars );
544  varidx = P[matrixdata->matvaridx[j]];
545  assert( 0 <= varidx && varidx < matrixdata->npermvars );
546  if ( varidx != matrixdata->matvaridx[j] )
547  ++npermuted;
548  assert( SCIPisZero(scip, permrow[varidx]) );
549  permrow[varidx] = matrixdata->matcoef[j];
550  ++j;
551  }
552 
553  /* if row is not affected by permutation, we do not have to check it */
554  if ( npermuted > 0 )
555  {
556  /* check other rows (sparse) */
557  SCIP_Bool found = FALSE;
558  for (r2 = 0; r2 < matrixdata->nrhscoef; ++r2)
559  {
560  /* a permutation must map constraints of the same type and respect rhs coefficients */
561  if ( matrixdata->rhssense[r1] == matrixdata->rhssense[r2] && SCIPisEQ(scip, matrixdata->rhscoef[r1], matrixdata->rhscoef[r2]) )
562  {
563  j = rhsmatbeg[r2];
564  assert( 0 <= j && j < matrixdata->nmatcoef );
565  assert( matrixdata->matrhsidx[j] == r2 );
566  assert( matrixdata->matvaridx[j] < matrixdata->npermvars );
567 
568  /* loop through row r2 and check whether it is equal to permuted row r */
569  while (j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r2 && SCIPisEQ(scip, permrow[matrixdata->matvaridx[j]], matrixdata->matcoef[j]) )
570  ++j;
571 
572  /* check whether rows are completely equal */
573  if ( j >= matrixdata->nmatcoef || matrixdata->matrhsidx[j] != r2 )
574  {
575  /* perm[p] is indeed a symmetry */
576  found = TRUE;
577  break;
578  }
579  }
580  }
581 
582  assert( found );
583  if ( ! found ) /*lint !e774*/
584  {
585  SCIPerrorMessage("Found permutation that is not a symmetry.\n");
586  return SCIP_ERROR;
587  }
588  }
589 
590  /* reset permrow */
591  j = rhsmatbeg[r1];
592  while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r1 )
593  {
594  int varidx;
595  varidx = P[matrixdata->matvaridx[j]];
596  permrow[varidx] = 0.0;
597  ++j;
598  }
599  }
600  }
601 
602  SCIPfreeBlockMemoryArray(scip, &rhsmatbeg, matrixdata->nrhscoef);
603  SCIPfreeBlockMemoryArray(scip, &permrow, matrixdata->npermvars);
604 
605  return SCIP_OKAY;
606 }
607 
608 
609 /** returns the number of active constraints that can be handled by symmetry */
610 static
612  SCIP* scip /**< SCIP instance */
613  )
614 {
615  SCIP_CONSHDLR* conshdlr;
616  int nhandleconss = 0;
617 
618  assert( scip != NULL );
619 
620  conshdlr = SCIPfindConshdlr(scip, "linear");
621  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
622  conshdlr = SCIPfindConshdlr(scip, "setppc");
623  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
624  conshdlr = SCIPfindConshdlr(scip, "xor");
625  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
626  conshdlr = SCIPfindConshdlr(scip, "and");
627  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
628  conshdlr = SCIPfindConshdlr(scip, "or");
629  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
630  conshdlr = SCIPfindConshdlr(scip, "logicor");
631  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
632  conshdlr = SCIPfindConshdlr(scip, "knapsack");
633  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
634  conshdlr = SCIPfindConshdlr(scip, "varbound");
635  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
636  conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
637  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
638 
639  return nhandleconss;
640 }
641 
642 
643 /** compute symmetry group of MIP */
644 static
646  SCIP* scip, /**< SCIP pointer */
647  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
648  SYM_SPEC fixedtype, /**< variable types that must be fixed by symmetries */
649  SCIP_Bool local, /**< Use local variable bounds? */
650  SCIP_Bool checksymmetries, /**< Should all symmetries be checked after computation? */
651  int* npermvars, /**< pointer to store number of variables for permutations */
652  SCIP_VAR*** permvars, /**< pointer to store variables on which permutations act */
653  SCIP_Real** permvarsobj, /**< objective values of permuted variables */
654  int* nperms, /**< pointer to store number of permutations */
655  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
656  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
657  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
658  SCIP_Bool* success /**< pointer to store whether symmetry computation was successful */
659  )
660 {
661  SCIP_CONSHDLR* conshdlr;
662  SYM_MATRIXDATA matrixdata;
663  SCIP_HASHTABLE* vartypemap;
664  SCIP_VAR** consvars;
665  SCIP_Real* consvals;
666  SCIP_CONS** conss;
667  SCIP_VAR** vars;
668  SYM_VARTYPE* uniquevararray;
669  SYM_RHSSENSE oldsense = SYM_SENSE_UNKOWN;
670  SYM_SORTRHSTYPE sortrhstype;
671  SCIP_Real oldcoef = SCIP_INVALID;
672  SCIP_Real val;
673  int nuniquevararray = 0;
674  int nhandleconss;
675  int nactiveconss;
676  int nconss;
677  int nvars;
678  int nallvars;
679  int c;
680  int j;
681 
682  assert( scip != NULL );
683  assert( npermvars != NULL );
684  assert( permvars != NULL );
685  assert( permvarsobj != NULL );
686  assert( nperms != NULL );
687  assert( nmaxperms != NULL );
688  assert( perms != NULL );
689  assert( log10groupsize != NULL );
690  assert( success != NULL );
691 
692  /* init */
693  *npermvars = 0;
694  *permvars = NULL;
695  *permvarsobj = NULL;
696  *nperms = 0;
697  *nmaxperms = 0;
698  *perms = NULL;
699  *log10groupsize = 0;
700  *success = FALSE;
701 
702  /* skip if no symmetry can be computed */
703  if ( ! SYMcanComputeSymmetry() )
704  return SCIP_OKAY;
705 
706  nconss = SCIPgetNConss(scip);
707  nvars = SCIPgetNVars(scip);
708 
709  /* exit if no constraints or no variables are available */
710  if ( nconss == 0 || nvars == 0 )
711  {
712  *success = TRUE;
713  return SCIP_OKAY;
714  }
715 
716  conss = SCIPgetConss(scip);
717  assert( conss != NULL );
718 
719  /* compute the number of active constraints */
720  nactiveconss = SCIPgetNActiveConss(scip);
721 
722  /* exit if no active constraints are available */
723  if ( nactiveconss == 0 )
724  {
725  *success = TRUE;
726  return SCIP_OKAY;
727  }
728 
729  /* before we set up the matrix, check whether we can handle all constraints */
730  nhandleconss = getNSymhandableConss(scip);
731  assert( nhandleconss <= nactiveconss );
732  if ( nhandleconss < nactiveconss )
733  {
734  /* In this case we found unkown constraints and we exit, since we cannot handle them. */
735  *success = FALSE;
736  return SCIP_OKAY;
737  }
738 
739  SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
740 
741  /* copy variables */
742  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
743  assert( vars != NULL );
744 
745  /* fill matrixdata */
746  matrixdata.nmaxmatcoef = 100 * nvars;
747  matrixdata.nmatcoef = 0;
748  matrixdata.nrhscoef = 0;
749  matrixdata.nuniquemat = 0;
750  matrixdata.nuniquevars = 0;
751  matrixdata.nuniquerhs = 0;
752  matrixdata.npermvars = nvars;
753  matrixdata.permvars = vars;
754  matrixdata.permvarcolors = NULL;
755  matrixdata.matcoefcolors = NULL;
756  matrixdata.rhscoefcolors = NULL;
757 
758  /* prepare matrix data (use block memory, since this can become large) */
759  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef) );
760  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef) );
761  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef) );
762  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef) );
763  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhscoef, 2 * nactiveconss) );
764  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhssense, 2 * nactiveconss) );
765  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhsidx, 2 * nactiveconss) );
766 
767  /* prepare temporary constraint data (use block memory, since this can become large);
768  * also allocate memory for fixed vars since some vars might have been deactivated meanwhile */
769  nallvars = nvars + SCIPgetNFixedVars(scip);
770  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consvars, nallvars) );
771  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consvals, nallvars) );
772 
773  /* loop through all constraints */
774  for (c = 0; c < nconss; ++c)
775  {
776  const char* conshdlrname;
777  SCIP_CONS* cons;
778  SCIP_VAR** linvars;
779  int nconsvars;
780 
781  /* get constraint */
782  cons = conss[c];
783  assert( cons != NULL );
784 
785  /* skip non-active constraints */
786  if ( ! SCIPconsIsActive(cons) )
787  continue;
788 
789  /* get constraint handler */
790  conshdlr = SCIPconsGetHdlr(cons);
791  assert( conshdlr != NULL );
792 
793  conshdlrname = SCIPconshdlrGetName(conshdlr);
794  assert( conshdlrname != NULL );
795 
796  /* check type of constraint */
797  if ( strcmp(conshdlrname, "linear") == 0 )
798  {
799  SCIP_CALL( collectCoefficients(scip, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
800  SCIPgetNVarsLinear(scip, cons), SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons),
801  SCIPconsIsTransformed(cons), SYM_SENSE_UNKOWN, &matrixdata) );
802  }
803  else if ( strcmp(conshdlrname, "setppc") == 0 )
804  {
805  linvars = SCIPgetVarsSetppc(scip, cons);
806  nconsvars = SCIPgetNVarsSetppc(scip, cons);
807 
808  switch ( SCIPgetTypeSetppc(scip, cons) )
809  {
811  SCIP_CALL( collectCoefficients(scip, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata) );
812  break;
814  SCIP_CALL( collectCoefficients(scip, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata) );
815  break;
817  SCIP_CALL( collectCoefficients(scip, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata) );
818  break;
819  default:
820  SCIPerrorMessage("Unknown setppc type %d.\n", SCIPgetTypeSetppc(scip, cons));
821  return SCIP_ERROR;
822  }
823  }
824  else if ( strcmp(conshdlrname, "xor") == 0 )
825  {
826  SCIP_VAR** curconsvars;
827  SCIP_VAR* var;
828 
829  /* get number of variables of XOR constraint (without integer variable) */
830  nconsvars = SCIPgetNVarsXor(scip, cons);
831 
832  /* get variables of XOR constraint */
833  curconsvars = SCIPgetVarsXor(scip, cons);
834  for (j = 0; j < nconsvars; ++j)
835  {
836  assert( curconsvars[j] != NULL );
837  consvars[j] = curconsvars[j];
838  consvals[j] = 1.0;
839  }
840 
841  /* intVar of xor constraint might have been removed */
842  var = SCIPgetIntVarXor(scip, cons);
843  if ( var != NULL )
844  {
845  consvars[nconsvars] = var;
846  consvals[nconsvars++] = 2.0;
847  }
848  assert( nconsvars <= nallvars );
849 
850  SCIP_CALL( collectCoefficients(scip, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
851  (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata) );
852  }
853  else if ( strcmp(conshdlrname, "and") == 0 )
854  {
855  SCIP_VAR** curconsvars;
856 
857  /* get number of variables of AND constraint (without resultant) */
858  nconsvars = SCIPgetNVarsAnd(scip, cons);
859 
860  /* get variables of AND constraint */
861  curconsvars = SCIPgetVarsAnd(scip, cons);
862 
863  for (j = 0; j < nconsvars; ++j)
864  {
865  assert( curconsvars[j] != NULL );
866  consvars[j] = curconsvars[j];
867  consvals[j] = 1.0;
868  }
869 
870  assert( SCIPgetResultantAnd(scip, cons) != NULL );
871  consvars[nconsvars] = SCIPgetResultantAnd(scip, cons);
872  consvals[nconsvars++] = 2.0;
873  assert( nconsvars <= nallvars );
874 
875  SCIP_CALL( collectCoefficients(scip, consvars, consvals, nconsvars, 0.0, 0.0,
876  SCIPconsIsTransformed(cons), SYM_SENSE_AND, &matrixdata) );
877  }
878  else if ( strcmp(conshdlrname, "or") == 0 )
879  {
880  SCIP_VAR** curconsvars;
881 
882  /* get number of variables of OR constraint (without resultant) */
883  nconsvars = SCIPgetNVarsOr(scip, cons);
884 
885  /* get variables of OR constraint */
886  curconsvars = SCIPgetVarsOr(scip, cons);
887 
888  for (j = 0; j < nconsvars; ++j)
889  {
890  assert( curconsvars[j] != NULL );
891  consvars[j] = curconsvars[j];
892  consvals[j] = 1.0;
893  }
894 
895  assert( SCIPgetResultantOr(scip, cons) != NULL );
896  consvars[nconsvars] = SCIPgetResultantOr(scip, cons);
897  consvals[nconsvars++] = 2.0;
898  assert( nconsvars <= nallvars );
899 
900  SCIP_CALL( collectCoefficients(scip, consvars, consvals, nconsvars, 0.0, 0.0,
901  SCIPconsIsTransformed(cons), SYM_SENSE_OR, &matrixdata) );
902  }
903  else if ( strcmp(conshdlrname, "logicor") == 0 )
904  {
905  SCIP_CALL( collectCoefficients(scip, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
906  1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata) );
907  }
908  else if ( strcmp(conshdlrname, "knapsack") == 0 )
909  {
910  SCIP_Longint* weights;
911 
912  nconsvars = SCIPgetNVarsKnapsack(scip, cons);
913 
914  /* copy Longint array to SCIP_Real array and get active variables of constraint */
915  weights = SCIPgetWeightsKnapsack(scip, cons);
916  for (j = 0; j < nconsvars; ++j)
917  consvals[j] = (SCIP_Real) weights[j];
918  assert( nconsvars <= nallvars );
919 
920  SCIP_CALL( collectCoefficients(scip, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
921  (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata) );
922  }
923  else if ( strcmp(conshdlrname, "varbound") == 0 )
924  {
925  consvars[0] = SCIPgetVarVarbound(scip, cons);
926  consvals[0] = 1.0;
927 
928  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
929  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
930 
931  SCIP_CALL( collectCoefficients(scip, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
932  SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata) );
933  }
934  else if ( strcmp(conshdlrname, "bounddisjunction") == 0 )
935  {
936  /* currently assume bound disjunctions are o.k. for non local symmetry groups */
937  if ( local )
938  {
939  /* @todo we need to handle bounddisjunctions if local symmetry groups are considered */
940  SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
941  SCIPconsGetName(cons), SCIPconshdlrGetName(conshdlr) );
942  return SCIP_ERROR;
943  }
944  }
945  else
946  {
947  SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
948  SCIPconsGetName(cons), SCIPconshdlrGetName(conshdlr) );
949  return SCIP_ERROR;
950  }
951  }
952  assert( matrixdata.nrhscoef <= 2 * nactiveconss );
953  assert( matrixdata.nrhscoef > 0 ); /* cannot have empty rows! */
954 
955  SCIPfreeBlockMemoryArray(scip, &consvals, nallvars);
956  SCIPfreeBlockMemoryArray(scip, &consvars, nallvars);
957 
958  /* sort matrix coefficients (leave matrix array intact) */
959  SCIPsort(matrixdata.matidx, SYMsortMatCoef, (void*) matrixdata.matcoef, matrixdata.nmatcoef);
960 
961  /* sort rhs types (first by sense, then by value, leave rhscoef intact) */
962  sortrhstype.vals = matrixdata.rhscoef;
963  sortrhstype.senses = matrixdata.rhssense;
964  sortrhstype.nrhscoef = matrixdata.nrhscoef;
965  SCIPsort(matrixdata.rhsidx, SYMsortRhsTypes, (void*) &sortrhstype, matrixdata.nrhscoef);
966 
967  /* create map for variables to indices */
968  SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
969  assert( vartypemap != NULL );
970 
971  /* allocate space for mappings to colors */
972  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.permvarcolors, nvars) );
973  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matcoefcolors, matrixdata.nmatcoef) );
974  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhscoefcolors, matrixdata.nrhscoef) );
975  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniquevararray, nvars) );
976 
977  /* determine number of different coefficents */
978 
979  /* find non-equivalent variables: same objective, lower and upper bounds, and variable type */
980  for (j = 0; j < nvars; ++j)
981  {
982  SCIP_VAR* var;
983 
984  var = vars[j];
985  assert( var != NULL );
986 
987  /* if the variable type should be fixed just increase the color */
988  if ( SymmetryFixVar(fixedtype, var) )
989  {
990  matrixdata.permvarcolors[j] = matrixdata.nuniquevars++;
991 #ifdef SCIP_OUTPUT
992  SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
993 #endif
994  }
995  else
996  {
997  SYM_VARTYPE* vt;
998 
999  vt = &uniquevararray[nuniquevararray];
1000  assert( nuniquevararray <= matrixdata.nuniquevars );
1001 
1002  vt->obj = SCIPvarGetObj(var);
1003  if ( local )
1004  {
1005  vt->lb = SCIPvarGetLbLocal(var);
1006  vt->ub = SCIPvarGetUbLocal(var);
1007  }
1008  else
1009  {
1010  vt->lb = SCIPvarGetLbGlobal(var);
1011  vt->ub = SCIPvarGetUbGlobal(var);
1012  }
1013  vt->type = SCIPvarGetType(var);
1014 
1015  if ( ! SCIPhashtableExists(vartypemap, (void*) vt) )
1016  {
1017  SCIP_CALL( SCIPhashtableInsert(vartypemap, (void*) vt) );
1018  vt->color = matrixdata.nuniquevars;
1019  matrixdata.permvarcolors[j] = matrixdata.nuniquevars++;
1020  ++nuniquevararray;
1021 #ifdef SCIP_OUTPUT
1022  SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
1023  SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
1024 #endif
1025  }
1026  else
1027  {
1028  SYM_VARTYPE* vtr;
1029 
1030  vtr = (SYM_VARTYPE*) SCIPhashtableRetrieve(vartypemap, (void*) vt);
1031  matrixdata.permvarcolors[j] = vtr->color;
1032  }
1033  }
1034  }
1035 
1036  /* find non-equivalent matrix entries (use sorting to avoid too many map calls) */
1037  for (j = 0; j < matrixdata.nmatcoef; ++j)
1038  {
1039  int idx;
1040 
1041  idx = matrixdata.matidx[j];
1042  assert( 0 <= idx && idx < matrixdata.nmatcoef );
1043 
1044  val = matrixdata.matcoef[idx];
1045  assert( oldcoef == SCIP_INVALID || oldcoef <= val ); /*lint !e777*/
1046 
1047  if ( ! SCIPisEQ(scip, val, oldcoef) )
1048  {
1049 #ifdef SCIP_OUTPUT
1050  SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
1051 #endif
1052  matrixdata.matcoefcolors[idx] = matrixdata.nuniquemat++;
1053  oldcoef = val;
1054  }
1055  else
1056  {
1057  assert( matrixdata.nuniquemat > 0 );
1058  matrixdata.matcoefcolors[idx] = matrixdata.nuniquemat - 1;
1059  }
1060  }
1061 
1062  /* find non-equivalent rhs */
1063  oldcoef = SCIP_INVALID;
1064  for (j = 0; j < matrixdata.nrhscoef; ++j)
1065  {
1066  SYM_RHSSENSE sense;
1067  int idx;
1068 
1069  idx = matrixdata.rhsidx[j];
1070  assert( 0 <= idx && idx < matrixdata.nrhscoef );
1071  sense = matrixdata.rhssense[idx];
1072  val = matrixdata.rhscoef[idx];
1073 
1074  /* make sure that new senses are treated with new color */
1075  if ( sense != oldsense )
1076  oldcoef = SCIP_INVALID;
1077  oldsense = sense;
1078  assert( oldcoef == SCIP_INVALID || oldcoef <= val ); /*lint !e777*/
1079 
1080  /* assign new color to new type */
1081  if ( ! SCIPisEQ(scip, val, oldcoef) )
1082  {
1083 #ifdef SCIP_OUTPUT
1084  SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
1085 #endif
1086  matrixdata.rhscoefcolors[idx] = matrixdata.nuniquerhs++;
1087  oldcoef = val;
1088  }
1089  else
1090  {
1091  assert( matrixdata.nuniquerhs > 0 );
1092  matrixdata.rhscoefcolors[idx] = matrixdata.nuniquerhs - 1;
1093  }
1094  }
1095  assert( 0 < matrixdata.nuniquevars && matrixdata.nuniquevars <= nvars );
1096  assert( 0 < matrixdata.nuniquerhs && matrixdata.nuniquerhs <= matrixdata.nrhscoef );
1097  assert( 0 < matrixdata.nuniquemat && matrixdata.nuniquemat <= matrixdata.nmatcoef );
1098 
1099  SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
1100  SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
1101  SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
1102 
1103  /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
1104  if ( matrixdata.nuniquevars < nvars && matrixdata.nuniquemat < matrixdata.nmatcoef )
1105  {
1106  /* determine generators */
1107  SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, nperms, nmaxperms, perms, log10groupsize) );
1108 
1109  if ( ! SCIPisStopped(scip) && checksymmetries )
1110  {
1111  SCIP_CALL( checkSymmetriesAreSymmetries(scip, fixedtype, &matrixdata, *nperms, *perms) );
1112  }
1113  }
1114  *success = TRUE;
1115 
1116  /* free matrix data */
1117  SCIPfreeBlockMemoryArray(scip, &uniquevararray, nvars);
1118 
1119  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoefcolors, matrixdata.nrhscoef);
1120  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoefcolors, matrixdata.nmatcoef);
1121  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.permvarcolors, nvars);
1122  SCIPhashtableFree(&vartypemap);
1123 
1124  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhsidx, 2 * nactiveconss);
1125  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhssense, 2 * nactiveconss);
1126  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoef, 2 * nactiveconss);
1127  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef);
1128  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef);
1129  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef);
1130  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef);
1131 
1132  /* copy variables */
1133  *permvars = vars;
1134  *npermvars = nvars;
1135 
1136  /* symmetric variables are not allowed to be multi-aggregated */
1137  for (j = 0; j < nvars; ++j)
1138  {
1139  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, vars[j]) );
1140  }
1141 
1142 #ifndef NDEBUG
1143  SCIP_CALL( SCIPallocBlockMemoryArray(scip, permvarsobj, nvars) );
1144  for (j = 0; j < nvars; ++j)
1145  (*permvarsobj)[j] = SCIPvarGetObj(vars[j]);
1146 #endif
1147 
1148  return SCIP_OKAY;
1149 }
1150 
1151 
1152 /** determine symmetry */
1153 static
1155  SCIP* scip, /**< SCIP instance */
1156  SCIP_PRESOLDATA* presoldata /**< presolver data */
1157  )
1158 {
1159  int maxgenerators;
1160  int type = 0;
1161  int nvars;
1162 
1163  assert( scip != NULL );
1164  assert( presoldata != NULL );
1165 
1166  assert( ! presoldata->computedsym );
1167  assert( presoldata->npermvars == 0 );
1168  assert( presoldata->permvars == NULL );
1169  assert( presoldata->permvarsobj == NULL );
1170  assert( presoldata->nperms == 0 );
1171  assert( presoldata->nmaxperms == 0 );
1172  assert( presoldata->perms == NULL );
1173 
1174  presoldata->computedsym = TRUE;
1175 
1176 #ifndef NDEBUG
1177  {
1178  int usesymmetry;
1179  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
1180  assert( usesymmetry );
1181  }
1182 #endif
1183 
1184  /* do not compute symmetry if there are active pricers */
1185  if ( SCIPgetNActivePricers(scip) > 0 )
1186  return SCIP_OKAY;
1187 
1188  /* avoid trivial cases */
1189  nvars = SCIPgetNVars(scip);
1190  if ( nvars <= 0 )
1191  return SCIP_OKAY;
1192 
1193  /* determine symmetry specification */
1194  if ( SCIPgetNBinVars(scip) > 0 )
1195  type |= (int) SYM_SPEC_BINARY;
1196  if ( SCIPgetNIntVars(scip) > 0 )
1197  type |= (int) SYM_SPEC_INTEGER;
1198  /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
1199  if ( SCIPgetNContVars(scip) > 0 || SCIPgetNImplVars(scip) > 0 )
1200  type |= (int) SYM_SPEC_REAL;
1201 
1202  /* skip symmetry computation if no graph automorphism code was linked */
1203  if ( ! SYMcanComputeSymmetry() )
1204  {
1205  int nconss = SCIPgetNActiveConss(scip);
1206  int nhandleconss = getNSymhandableConss(scip);
1207 
1208  /* print verbMessage only if problem consists of symmetry handable constraints */
1209  assert( nhandleconss <= nconss );
1210  if ( nhandleconss < nconss )
1211  return SCIP_OKAY;
1212 
1214  " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
1215  return SCIP_OKAY;
1216  }
1217  /* skip symmetry computation if required variables are not present */
1218  else if ( ! (type & presoldata->symspecrequire) )
1219  {
1221  " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c)\n",
1222  SCIPgetSolvingTime(scip),
1223  SCIPgetNBinVars(scip) > 0 ? '+' : '-',
1224  SCIPgetNIntVars(scip) > 0 ? '+' : '-',
1225  SCIPgetNContVars(scip) + SCIPgetNImplVars(scip) > 0 ? '+' : '-',
1226  (presoldata->symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
1227  (presoldata->symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
1228  (presoldata->symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
1229  return SCIP_OKAY;
1230  }
1231  /* skip symmetry computation if there are constraints that cannot be handled by symmetry */
1232  else if ( getNSymhandableConss(scip) < SCIPgetNActiveConss(scip) )
1233  {
1235  " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods\n",
1236  SCIPgetSolvingTime(scip));
1237  return SCIP_OKAY;
1238  }
1239 
1241  " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
1242  SCIPgetSolvingTime(scip),
1243  (presoldata->symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
1244  (presoldata->symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
1245  (presoldata->symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-',
1246  (presoldata->symspecrequirefixed & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
1247  (presoldata->symspecrequirefixed & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
1248  (presoldata->symspecrequirefixed & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
1249 
1250  if ( presoldata->symspecrequire & presoldata->symspecrequirefixed )
1251  SCIPwarningMessage(scip, "Warning: some required symmetries must be fixed.\n");
1252 
1253  /* actually compute (global) symmetry */
1254  /* determine maximal number of generators depending on the number of variables */
1255  maxgenerators = presoldata->maxgenerators;
1256  maxgenerators = MIN(maxgenerators, MAXGENNUMERATOR / nvars);
1257 
1258  SCIP_CALL( computeSymmetryGroup(scip, maxgenerators, presoldata->symspecrequirefixed, FALSE, presoldata->checksymmetries,
1259  &presoldata->npermvars, &presoldata->permvars, &presoldata->permvarsobj, &presoldata->nperms, &presoldata->nmaxperms, &presoldata->perms,
1260  &presoldata->log10groupsize, &presoldata->successful) );
1261 
1262  /* output statistics */
1263  if ( ! presoldata->successful )
1264  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
1265  else if ( presoldata->nperms == 0 )
1266  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
1267  else
1268  {
1269  assert( presoldata->nperms > 0 );
1270 
1271  if ( maxgenerators == 0 )
1272  {
1274  " (%.1fs) symmetry computation finished: %d generators found (max: -, log10 of symmetry group size: %.1f)\n",
1275  SCIPgetSolvingTime(scip), presoldata->nperms, presoldata->log10groupsize);
1276  }
1277  else
1278  {
1280  " (%.1fs) symmetry computation finished: %d generators found (max: %u, log10 of symmetry group size: %.1f)\n",
1281  SCIPgetSolvingTime(scip), presoldata->nperms, maxgenerators, presoldata->log10groupsize);
1282  }
1283 
1284  /* turn off some other presolving methods in order to be sure that they do not destroy symmetry afterwards */
1286  " (%.1fs) turning off presolver <domcol>, constraint handler <components>, and propagator <dualfix> for remaining computations in order to avoid conflicts\n",
1287  SCIPgetSolvingTime(scip));
1288 
1289  /* domcol avoids S_2-symmetries and may not be compatible with other symmetry handling methods */
1290  SCIP_CALL( SCIPsetIntParam(scip, "presolving/domcol/maxrounds", 0) );
1291 
1292  /* components creates sub-SCIPs on which no symmetry handling is installed, thus turn this off */
1293  SCIP_CALL( SCIPsetIntParam(scip, "constraints/components/maxprerounds", 0) );
1294 
1295  /* dual fixing might interfere with symmetry handling methods, thus turn this off */
1296  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", 0) );
1297  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/freq", 0) );
1298 
1299  presoldata->changeddefaultparams = TRUE;
1300  }
1301 
1302  return SCIP_OKAY;
1303 }
1304 
1305 
1306 
1307 /*
1308  * Callback methods of presolver
1309  */
1310 
1311 /** initialization method of presolver (called after problem was transformed) */
1312 static
1313 SCIP_DECL_PRESOLINIT(presolInitSymmetry)
1314 { /*lint --e{715}*/
1315  SCIP_PRESOLDATA* presoldata;
1316 
1317  assert( scip != NULL );
1318  assert( presol != NULL );
1319  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1320 
1321  presoldata = SCIPpresolGetData(presol);
1322 
1323  /* initialize original values of changed parameters in case we do not enter determineSymmetry() */
1324  SCIP_CALL( SCIPgetIntParam(scip, "presolving/domcol/maxrounds", &(presoldata->oldmaxroundsdomcol)) );
1325  SCIP_CALL( SCIPgetIntParam(scip, "constraints/components/maxprerounds", &(presoldata->oldmaxpreroundscomponents)) );
1326  SCIP_CALL( SCIPgetIntParam(scip, "propagating/dualfix/maxprerounds", &(presoldata->oldmaxpreroundsdualfix)) );
1327  SCIP_CALL( SCIPgetIntParam(scip, "propagating/dualfix/freq", &(presoldata->oldfreqdualfix)) );
1328 
1329  return SCIP_OKAY;
1330 }
1331 
1332 
1333 /** presolving initialization method of presolver (called when presolving is about to begin) */
1334 static
1335 SCIP_DECL_PRESOLINITPRE(presolInitpreSymmetry)
1336 {
1337  SCIP_PRESOLDATA* presoldata;
1338 
1339  assert( scip != NULL );
1340  assert( presol != NULL );
1341  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1342 
1343  presoldata = SCIPpresolGetData(presol);
1344  assert( presoldata != NULL );
1345 
1346  SCIPdebugMsg(scip, "Initialization of symmetry presolver.\n");
1347 
1348  /* compute symmetries if not requested during presolving */
1349  if ( ! presoldata->computepresolved && ! presoldata->computedsym && presoldata->symtype != 0 )
1350  {
1351  /* determine symmetry here in initpre, since other plugins specify their problem type in init() */
1352  SCIP_CALL( determineSymmetry(scip, presoldata) );
1353  }
1354 
1355  return SCIP_OKAY;
1356 }
1357 
1358 
1359 /** deinitialization method of presolver (called before transformed problem is freed) */
1360 static
1361 SCIP_DECL_PRESOLEXIT(presolExitSymmetry)
1362 {
1363  SCIP_PRESOLDATA* presoldata;
1364  int i;
1365 
1366  assert( scip != NULL );
1367  assert( presol != NULL );
1368  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1369 
1370  SCIPdebugMsg(scip, "Exiting symmetry presolver.\n");
1371 
1372  presoldata = SCIPpresolGetData(presol);
1373  assert( presoldata != NULL );
1374 
1375  SCIPfreeBlockMemoryArrayNull(scip, &presoldata->permvars, presoldata->npermvars);
1376  SCIPfreeBlockMemoryArrayNull(scip, &presoldata->permvarsobj, presoldata->npermvars);
1377  for (i = 0; i < presoldata->nperms; ++i)
1378  {
1379  SCIPfreeBlockMemoryArray(scip, &presoldata->perms[i], presoldata->npermvars);
1380  }
1381  SCIPfreeBlockMemoryArrayNull(scip, &presoldata->perms, presoldata->nmaxperms);
1382 
1383  /* reset settings */
1384  presoldata->symtype = 0;
1385  presoldata->symspecrequire = 0;
1386  presoldata->symspecrequirefixed = 0;
1387  presoldata->npermvars = 0;
1388  presoldata->nperms = 0;
1389  presoldata->nmaxperms = 0;
1390  presoldata->computedsym = FALSE;
1391  presoldata->successful = FALSE;
1392 
1393  /* reset changed parameters */
1394  if ( presoldata->changeddefaultparams )
1395  {
1396  SCIP_CALL( SCIPsetIntParam(scip, "presolving/domcol/maxrounds", presoldata->oldmaxroundsdomcol) );
1397  SCIP_CALL( SCIPsetIntParam(scip, "constraints/components/maxprerounds", presoldata->oldmaxpreroundscomponents) );
1398  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", presoldata->oldmaxpreroundsdualfix) );
1399  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", presoldata->oldfreqdualfix) );
1400 
1401  presoldata->changeddefaultparams = FALSE;
1402  }
1403 
1404  return SCIP_OKAY;
1405 }
1406 
1407 
1408 /** destructor of presolver to free user data (called when SCIP is exiting) */
1409 static
1410 SCIP_DECL_PRESOLFREE(presolFreeSymmetry)
1411 { /*lint --e{715}*/
1412  SCIP_PRESOLDATA* presoldata;
1413 
1414  assert( scip != NULL );
1415  assert( presol != NULL );
1416  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1417 
1418  SCIPdebugMsg(scip, "Freeing symmetry presolver.\n");
1419 
1420  presoldata = SCIPpresolGetData(presol);
1421  assert( presoldata != NULL );
1422 
1423  SCIPfreeBlockMemory(scip, &presoldata);
1424 
1425  return SCIP_OKAY;
1426 }
1427 
1428 
1429 /** execution method of presolver */
1430 static
1431 SCIP_DECL_PRESOLEXEC(presolExecSymmetry)
1432 { /*lint --e{715}*/
1433  assert( scip != NULL );
1434  assert( presol != NULL );
1435  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1436  assert( result != NULL );
1437 
1438  /* do nothing */
1439  *result = SCIP_DIDNOTRUN;
1440 
1441  return SCIP_OKAY;
1442 }
1443 
1444 
1445 /** presolving deinitialization method of presolver (called after presolving has been finished) */
1446 static
1447 SCIP_DECL_PRESOLEXITPRE(presolExitpreSymmetry)
1448 {
1449  SCIP_PRESOLDATA* presoldata;
1450 
1451  assert( scip != NULL );
1452  assert( presol != NULL );
1453  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1454 
1455  /* skip if we are in a restart */
1456  if ( SCIPgetNRuns(scip) > 1 )
1457  return SCIP_OKAY;
1458 
1459  /* skip if we already terminated */
1461  return SCIP_OKAY;
1462 
1463  /* skip if we are exiting */
1464  if ( SCIPisStopped(scip) )
1465  return SCIP_OKAY;
1466 
1467  SCIPdebugMsg(scip, "Exitpre method of symmetry presolver ...\n");
1468 
1469  presoldata = SCIPpresolGetData(presol);
1470  assert( presoldata != NULL );
1471 
1472  /* compute symmetries if requested during presolving */
1473  if ( presoldata->computepresolved && ! presoldata->computedsym && presoldata->symtype != 0 )
1474  {
1475  SCIP_CALL( determineSymmetry(scip, presoldata) );
1476  }
1477 
1478  return SCIP_OKAY;
1479 }
1480 
1481 
1482 
1483 /*
1484  * External methods
1485  */
1486 
1487 /** include symmetry constraint handler */
1489  SCIP* scip /**< SCIP data structure */
1490  )
1491 {
1492  SCIP_PRESOL* presol = NULL;
1493  SCIP_PRESOLDATA* presoldata = NULL;
1494 
1495  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1496  assert( presoldata != NULL );
1497 
1498  presoldata->symtype = 0;
1499  presoldata->symspecrequire = 0;
1500  presoldata->symspecrequirefixed = 0;
1501  presoldata->npermvars = 0;
1502  presoldata->permvars = NULL;
1503  presoldata->permvarsobj = NULL;
1504  presoldata->perms = NULL;
1505  presoldata->nperms = 0;
1506  presoldata->nmaxperms = 0;
1507  presoldata->computedsym = FALSE;
1508  presoldata->successful = FALSE;
1509  presoldata->changeddefaultparams = FALSE;
1510 
1511  /* include constraint handler */
1513  PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecSymmetry, presoldata) );
1514  assert( presol != NULL );
1515 
1516  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeSymmetry) );
1517  SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitSymmetry) );
1518  SCIP_CALL( SCIPsetPresolExit(scip, presol, presolExitSymmetry) );
1519  SCIP_CALL( SCIPsetPresolInitpre(scip, presol, presolInitpreSymmetry) );
1520  SCIP_CALL( SCIPsetPresolExitpre(scip, presol, presolExitpreSymmetry) );
1521 
1522  /* add parameters */
1524  "presolving/" PRESOL_NAME "/computepresolved",
1525  "Should the symmetry be computed after presolving (otherwise before presol)?",
1526  &presoldata->computepresolved, TRUE, DEFAULT_COMPUTEPRESOLVED, NULL, NULL) );
1527 
1528  SCIP_CALL( SCIPaddIntParam(scip,
1529  "presolving/" PRESOL_NAME "/maxgenerators",
1530  "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
1531  &presoldata->maxgenerators, TRUE, DEFAULT_MAXGENERATORS, 0, INT_MAX, NULL, NULL) );
1532 
1534  "presolving/" PRESOL_NAME "/checksymmetries",
1535  "Should all symmetries be checked after computation?",
1536  &presoldata->checksymmetries, TRUE, DEFAULT_CHECKSYMMETRIES, NULL, NULL) );
1537 
1538  /* possibly add description */
1539  if ( SYMcanComputeSymmetry() )
1540  {
1542  }
1543 
1544  return SCIP_OKAY;
1545 }
1546 
1547 
1548 /** return symmetry group generators */
1550  SCIP* scip, /**< SCIP data structure */
1551  int* npermvars, /**< pointer to store number of variables for permutations */
1552  SCIP_VAR*** permvars, /**< pointer to store variables on which permutations act */
1553  int* nperms, /**< pointer to store number of permutations */
1554  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1555  SCIP_Real* log10groupsize /**< pointer to store log10 of group size (or NULL) */
1556  )
1557 {
1558  SCIP_PRESOLDATA* presoldata;
1559  SCIP_PRESOL* presol;
1560 
1561  assert( scip != NULL );
1562  assert( npermvars != NULL );
1563  assert( permvars != NULL );
1564  assert( nperms != NULL );
1565  assert( perms != NULL );
1566 
1567  /* find symmetry presolver */
1568  presol = SCIPfindPresol(scip, "symmetry");
1569  if ( presol == NULL )
1570  {
1571  SCIPerrorMessage("Could not find symmetry presolver.\n");
1572  return SCIP_PLUGINNOTFOUND;
1573  }
1574  assert( presol != NULL );
1575  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1576 
1577  presoldata = SCIPpresolGetData(presol);
1578  assert( presoldata != NULL );
1579 
1580  if ( ! presoldata->computedsym )
1581  {
1584  {
1585  SCIPerrorMessage("Cannot call symmetry detection outside of presolving.\n");
1586  return SCIP_INVALIDCALL;
1587  }
1588 
1589  /* determine symmetry here */
1590  SCIP_CALL( determineSymmetry(scip, presoldata) );
1591  }
1592 
1593  *npermvars = presoldata->npermvars;
1594  *permvars = presoldata->permvars;
1595  *nperms = presoldata->nperms;
1596  *perms = presoldata->perms;
1597  if ( log10groupsize != NULL )
1598  *log10groupsize = presoldata->log10groupsize;
1599 
1600  return SCIP_OKAY;
1601 }
1602 
1603 
1604 /** return objective coefficients of permuted variables at time of symmetry computation */
1606  SCIP* scip, /**< SCIP data structure */
1607  SCIP_Real** permvarsobj /**< pointer to store objective coefficients of permuted variables (NULL if not available) */
1608  )
1609 {
1610  SCIP_PRESOLDATA* presoldata;
1611  SCIP_PRESOL* presol;
1612 
1613  assert( scip != NULL );
1614  assert( permvarsobj != NULL );
1615 
1616  /* find symmetry presolver */
1617  presol = SCIPfindPresol(scip, "symmetry");
1618  if ( presol == NULL )
1619  {
1620  SCIPerrorMessage("Could not find symmetry presolver.\n");
1621  return SCIP_PLUGINNOTFOUND;
1622  }
1623  assert( presol != NULL );
1624  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1625 
1626  presoldata = SCIPpresolGetData(presol);
1627  assert( presoldata != NULL );
1628 
1629  *permvarsobj = presoldata->permvarsobj;
1630 
1631  return SCIP_OKAY;
1632 }
1633 
1634 
1635 /** register that a specific symmetry is needed */
1637  SCIP* scip, /**< SCIP data structure */
1638  SYM_HANDLETYPE symtype, /**< type of symmetry handling of callee */
1639  SYM_SPEC type, /**< variable types the callee is interested in */
1640  SYM_SPEC fixedtype /**< variable types that callee wants to have fixed */
1641  )
1642 {
1643  SCIP_PRESOLDATA* presoldata;
1644  SCIP_PRESOL* presol;
1645 
1646  assert( scip != NULL );
1647 
1648  /* find symmetry presolver */
1649  presol = SCIPfindPresol(scip, "symmetry");
1650  if ( presol == NULL )
1651  {
1652  SCIPerrorMessage("Could not find symmetry presolver.\n");
1653  return SCIP_PLUGINNOTFOUND;
1654  }
1655  assert( presol != NULL );
1656  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1657 
1658  presoldata = SCIPpresolGetData(presol);
1659  assert( presoldata != NULL );
1660 
1661  /* check if there are conflicting symmetry handling methods */
1662  if ( ( presoldata->symtype & ~ symtype ) != 0 )
1663  {
1664  SCIPerrorMessage("Conflicting symmetry handling methods are activated.\n");
1665  return SCIP_INVALIDDATA;
1666  }
1667 
1668  presoldata->symtype |= symtype;
1669  presoldata->symspecrequire |= type;
1670  presoldata->symspecrequirefixed |= fixedtype;
1671 
1672  return SCIP_OKAY;
1673 }
1674 
1675 
1676 /** return at what time symmetry is computed (before or after presolving) */
1678  SCIP* scip, /**< SCIP data structure */
1679  SCIP_Bool* afterpresolve /**< pointer to store whether symmetry is computed in stage initpre or exitpre */
1680  )
1681 {
1682  SCIP_PRESOLDATA* presoldata;
1683  SCIP_PRESOL* presol;
1684 
1685  assert( scip != NULL );
1686  assert( afterpresolve != NULL );
1687 
1688  /* find symmetry presolver */
1689  presol = SCIPfindPresol(scip, "symmetry");
1690  if ( presol == NULL )
1691  {
1692  SCIPerrorMessage("Could not find symmetry presolver.\n");
1693  return SCIP_PLUGINNOTFOUND;
1694  }
1695  assert( presol != NULL );
1696  assert( strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0 );
1697 
1698  presoldata = SCIPpresolGetData(presol);
1699  assert( presoldata != NULL );
1700 
1701  *afterpresolve = presoldata->computepresolved;
1702 
1703  return SCIP_OKAY;
1704 }
#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
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46300
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Real * matcoef
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6968
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
Constraint handler for variable bound constraints .
#define PRESOL_DESC
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: scip.c:7000
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9230
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:46807
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
static int getNSymhandableConss(SCIP *scip)
#define FALSE
Definition: def.h:64
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:466
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
static SCIP_RETCODE collectCoefficients(SCIP *scip, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8295
int SCIPgetNActiveConss(SCIP *scip)
Definition: scip.c:43174
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define PRESOL_PRIORITY
Constraint handler for AND constraints, .
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip.c:12902
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_VAR ** permvars
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1267
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8047
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11986
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2014
interface for symmetry computations
static SCIP_DECL_PRESOLEXEC(presolExecSymmetry)
#define DEFAULT_MAXGENERATORS
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip.c:12123
Constraint handler for "or" constraints, .
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
#define SYM_SPEC_BINARY
Definition: type_symmetry.h:34
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:22599
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Real ub
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5121
#define PRESOL_MAXROUNDS
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SYM_RHSSENSE * rhssense
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5146
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
#define SYM_SPEC_INTEGER
Definition: type_symmetry.h:33
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:489
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:928
#define DEFAULT_COMPUTEPRESOLVED
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
SYM_RHSSENSE * senses
SCIP_RETCODE SCIPgetTimingSymmetry(SCIP *scip, SCIP_Bool *afterpresolve)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7986
#define MAXGENNUMERATOR
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip.c:6984
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25926
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_PRESOL * SCIPfindPresol(SCIP *scip, const char *name)
Definition: scip.c:7048
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip.c:4451
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIP_CALL(x)
Definition: def.h:350
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:473
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip.c:19249
SCIP_VAR ** SCIPgetVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2167
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
SCIP_Real * vals
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)
static SCIP_DECL_PRESOLINITPRE(presolInitpreSymmetry)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define SCIP_Bool
Definition: def.h:61
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:11941
uint32_t SYM_SPEC
Definition: type_symmetry.h:37
int SCIPgetNVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2146
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9272
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8006
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4688
SCIP_Real lb
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
SCIP_VARTYPE type
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:42044
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2326
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SCIP_Bool SCIPgetRhsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5767
static SCIP_DECL_PRESOLEXITPRE(presolExitpreSymmetry)
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PRESOLDATA *presoldata)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12184
static SCIP_DECL_HASHKEYEQ(SYMhashKeyEQVartype)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, int *npermvars, SCIP_VAR ***permvars, SCIP_Real **permvarsobj, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Bool *success)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9251
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2064
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
SCIP_VAR ** SCIPgetVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5725
enum SYM_Rhssense SYM_RHSSENSE
Definition: type_symmetry.h:49
Constraint handler for XOR constraints, .
int SCIPgetNVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5704
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5081
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
SCIP_RETCODE SCIPgetPermvarsObjSymmetry(SCIP *scip, SCIP_Real **permvarsobj)
static const SCIP_Real scalars[]
Definition: lp.c:5618
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_SORTINDCOMP(SYMsortRhsTypes)
const char * SYMsymmetryGetName(void)
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2188
int SCIPgetNConss(SCIP *scip)
Definition: scip.c:12856
#define PRESOL_NAME
static SCIP_DECL_PRESOLINIT(presolInitSymmetry)
presolver for storing symmetry information about current problem
static SCIP_DECL_PRESOLEXIT(presolExitSymmetry)
#define SYM_SPEC_REAL
Definition: type_symmetry.h:35
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5097
uint32_t SYM_HANDLETYPE
Definition: type_symmetry.h:56
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIP_INVALID
Definition: def.h:169
#define PRESOL_TIMING
#define SCIP_Longint
Definition: def.h:134
const char * SYMsymmetryGetDesc(void)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2377
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip.c:9628
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47070
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:479
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real obj
static SCIP_DECL_PRESOLFREE(presolFreeSymmetry)
SCIP_Real * rhscoef
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetIntVarXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5746
SCIP_RETCODE SCIPgetGeneratorsSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, int *nperms, int ***perms, SCIP_Real *log10groupsize)
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXITPRE((*presolexitpre)))
Definition: scip.c:7032
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
SCIP_RETCODE SCIPincludePresolSymmetry(SCIP *scip)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
#define DEFAULT_CHECKSYMMETRIES