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