Scippy

SCIP

Solving Constraint Integer Programs

prop_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-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_symmetry.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief propagator for handling symmetries
19  * @author Marc Pfetsch
20  * @author Thomas Rehn
21  * @author Christopher Hojny
22  *
23  * This propagator combines the following symmetry handling functionalities:
24  * - It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry
25  * information can be accessed through external functions.
26  * - It allows to add the following symmetry breaking constraints:
27  * - symresack constraints, which separate minimal cover inequalities
28  * - orbitope constraints, if special symmetry group structures are detected
29  * - It allows to apply orbital fixing.
30  *
31  *
32  * @section SYMCOMP Symmetry Computation
33  *
34  * The following comments apply to symmetry computation.
35  *
36  * - The generic functionality of the compute_symmetry.h interface is used.
37  * - We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently
38  * no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt
39  * our code more than continuous/real variables (we basically do not handle integral variables at all).
40  * - We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
41  * symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
42  *
43  *
44  * @section SYMBREAK Symmetry Handling Constraints
45  *
46  * The following comments apply to adding symmetry handling constraints.
47  *
48  * - The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly
49  * adds the corresponding constraints.
50  * - If orbital fixing is active, only orbitopes are added (if present) and no symresacks.
51  * - We try to compute symmetry as late as possible and then add constraints based on this information.
52  * - Currently, we only allocate memory for pointers to symresack constraints for group generators. If further
53  * constraints are considered, we have to reallocate memory.
54  *
55  *
56  * @section OF Orbital Fixing
57  *
58  * Orbital fixing is implemented as introduced by@n
59  * F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.
60  *
61  * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
62  * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other
63  * variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering
64  * out generators that do not individually stabilize the variables branched to 1.
65  *
66  * @pre All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to
67  * a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.@n
68  * F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.
69  *
70  * To illustrate this, consider the example \f$\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b,
71  * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the
72  * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
73  * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
74  * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
75  * values). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we
76  * can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to
77  * consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have
78  * been fixed globally to different values.
79  *
80  * @pre All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.
81  *
82  * @pre No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to
83  * wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing
84  * \f$x_2 = 0\f$ and is interrupted afterwards, orbital fixing detects that the orbit \f$\{x_1, x_2\}\f$ contains
85  * one variable that is fixed to 0, and thus, it fixes \f$x_1\f$ to 0 as well. Thus, after these reductions, every
86  * feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is
87  * complete, because then \f$x_1\f$ is globally fixed to 1, and thus, is stabilized in orbital fixing.
88  *
89  * Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path
90  * from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the
91  * initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot
92  * be called in repropagation.
93  *
94  * @note If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied
95  * to symmetry components that are not handled by orbitope constraints.
96  *
97  * @todo Possibly turn off propagator in subtrees.
98  * @todo Check application of conflict resolution.
99  * @todo Check whether one should switch the role of 0 and 1
100  * @todo Implement stablizer computation?
101  * @todo Implement isomorphism pruning?
102  * @todo Implement particular preprocessing rules
103  * @todo Separate permuted cuts (first experiments not successful)
104  * @todo Allow the computation of local symmetries
105  * @todo Order rows of orbitopes (in particular packing/partitioning) w.r.t. cliques in conflict graph.
106  */
107 /* #define SCIP_OUTPUT */
108 /* #define SCIP_OUTPUT_COMPONENT */
109 
110 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
111 
112 #include <scip/cons_linear.h>
113 #include <scip/cons_knapsack.h>
114 #include <scip/cons_varbound.h>
115 #include <scip/cons_setppc.h>
116 #include <scip/cons_and.h>
117 #include <scip/cons_logicor.h>
118 #include <scip/cons_or.h>
119 #include "scip/cons_orbitope.h"
120 #include "scip/cons_symresack.h"
121 #include <scip/cons_xor.h>
122 #include <scip/cons_linking.h>
124 #include <scip/misc.h>
125 
126 #include <scip/prop_symmetry.h>
128 #include <scip/symmetry.h>
129 
130 #include <string.h>
131 
132 /* propagator properties */
133 #define PROP_NAME "symmetry"
134 #define PROP_DESC "propagator for handling symmetry"
135 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask */
136 #define PROP_PRIORITY -1000000 /**< propagator priority */
137 #define PROP_FREQ 1 /**< propagator frequency */
138 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
139 
140 #define PROP_PRESOL_PRIORITY -10000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
141 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
142 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
143 
144 
145 /* default parameter values for symmetry computation */
146 #define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
147 #define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
148 #define DEFAULT_DISPLAYNORBITVARS FALSE /**< Should the number of variables affected by some symmetry be displayed? */
149 #define DEFAULT_USECOLUMNSPARSITY FALSE /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
150 #define DEFAULT_DOUBLEEQUATIONS FALSE /**< Double equations to positive/negative version? */
151 #define DEFAULT_COMPRESSSYMMETRIES TRUE /**< Should non-affected variables be removed from permutation to save memory? */
152 #define DEFAULT_COMPRESSTHRESHOLD 0.5 /**< Compression is used if percentage of moved vars is at most the threshold. */
153 #define DEFAULT_SYMFIXNONBINARYVARS FALSE /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
154 
155 /* default parameters for symmetry constraints */
156 #define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
157 #define DEFAULT_ADDSYMRESACKS TRUE /**< Add inequalities for symresacks for each generator? */
158 #define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
159 #define DEFAULT_ADDCONSSTIMING 2 /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
160 
161 /* default parameters for orbital fixing */
162 #define DEFAULT_OFSYMCOMPTIMING 2 /**< timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
163 #define DEFAULT_PERFORMPRESOLVING FALSE /**< Run orbital fixing during presolving? */
164 #define DEFAULT_RECOMPUTERESTART FALSE /**< Recompute symmetries after a restart has occurred? */
165 #define DEFAULT_DISABLEOFRESTART FALSE /**< whether OF shall be disabled if OF has found a reduction and a restart occurs */
166 
167 
168 /* event handler properties */
169 #define EVENTHDLR_SYMMETRY_NAME "symmetry"
170 #define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"
171 
172 /* output table properties */
173 #define TABLE_NAME_ORBITALFIXING "orbitalfixing"
174 #define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"
175 #define TABLE_POSITION_ORBITALFIXING 7001 /**< the position of the statistics table */
176 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
177 
178 
179 /* other defines */
180 #define MAXGENNUMERATOR 64000000 /**< determine maximal number of generators by dividing this number by the number of variables */
181 #define SCIP_SPECIALVAL 1.12345678912345e+19 /**< special floating point value for handling zeros in bound disjunctions */
182 #define COMPRESSNVARSLB 25000 /**< lower bound on the number of variables above which compression could be performed */
183 
184 /* macros for getting activeness of symmetry handling methods */
185 #define ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
186 #define ISORBITALFIXINGACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0)
187 
188 
189 
190 /** propagator data */
191 struct SCIP_PropData
192 {
193  /* symmetry group information */
194  int npermvars; /**< number of variables for permutations */
195  int nbinpermvars; /**< number of binary variables for permuations */
196  SCIP_VAR** permvars; /**< variables on which permutations act */
197 #ifndef NDEBUG
198  SCIP_Real* permvarsobj; /**< objective values of permuted variables (for debugging) */
199 #endif
200  int nperms; /**< number of permutations */
201  int nmaxperms; /**< maximal number of permutations (needed for freeing storage) */
202  int** perms; /**< pointer to store permutation generators as (nperms x npermvars) matrix */
203  int** permstrans; /**< pointer to store transposed permutation generators as (npermvars x nperms) matrix */
204  SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */
205 
206  /* components of symmetry group */
207  int ncomponents; /**< number of components of symmetry group */
208  int* components; /**< array containing the indices of permutations sorted by components */
209  int* componentbegins; /**< array containing in i-th position the first position of
210  * component i in components array */
211  int* vartocomponent; /**< array containing for each permvar the index of the component it is
212  * contained in (-1 if not affected) */
213  SCIP_Shortbool* componentblocked; /**< array to store whether a component is blocked to be considered by
214  * further symmetry handling techniques */
215 
216  /* further symmetry information */
217  int nmovedvars; /**< number of variables moved by some permutation */
218  SCIP_Real log10groupsize; /**< log10 of size of symmetry group */
219  SCIP_Bool binvaraffected; /**< whether binary variables are affected by some symmetry */
220 
221  /* for symmetry computation */
222  int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
223  SCIP_Bool checksymmetries; /**< Should all symmetries be checked after computation? */
224  SCIP_Bool displaynorbitvars; /**< Whether the number of variables in non-trivial orbits shall be computed */
225  SCIP_Bool compresssymmetries; /**< Should non-affected variables be removed from permutation to save memory? */
226  SCIP_Real compressthreshold; /**< Compression is used if percentage of moved vars is at most the threshold. */
227  SCIP_Bool compressed; /**< Whether symmetry data has been compressed */
228  SCIP_Bool computedsymmetry; /**< Have we already tried to compute symmetries? */
229  int usesymmetry; /**< encoding of active symmetry handling methods (for debugging) */
230  SCIP_Bool usecolumnsparsity; /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
231  SCIP_Bool doubleequations; /**< Double equations to positive/negative version? */
232  SCIP_Bool symfixnonbinaryvars; /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
233 
234  /* for symmetry constraints */
235  SCIP_Bool symconsenabled; /**< Should symmetry constraints be added? */
236  SCIP_Bool triedaddconss; /**< whether we already tried to add symmetry breaking constraints */
237  SCIP_Bool conssaddlp; /**< Should the symmetry breaking constraints be added to the LP? */
238  SCIP_Bool addsymresacks; /**< Add symresack constraints for each generator? */
239  int addconsstiming; /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
240  SCIP_CONS** genconss; /**< list of generated constraints */
241  int ngenconss; /**< number of generated constraints */
242  int nsymresacks; /**< number of symresack constraints */
243  SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
244  int norbitopes; /**< number of orbitope constraints */
245 
246  /* data necessary for orbital fixing */
247  SCIP_Bool ofenabled; /**< Run orbital fixing? */
248  SCIP_EVENTHDLR* eventhdlr; /**< event handler for handling global variable fixings */
249  SCIP_Shortbool* bg0; /**< bitset to store variables globally fixed to 0 */
250  int* bg0list; /**< list of variables globally fixed to 0 */
251  int nbg0; /**< number of variables in bg0 and bg0list */
252  SCIP_Shortbool* bg1; /**< bitset to store variables globally fixed or branched to 1 */
253  int* bg1list; /**< list of variables globally fixed or branched to 1 */
254  int nbg1; /**< number of variables in bg1 and bg1list */
255  int* permvarsevents; /**< stores events caught for permvars */
256  SCIP_Shortbool* inactiveperms; /**< array to store whether permutations are inactive */
257  int nmovedpermvars; /**< number of variables moved by any permutation in a symmetry component that is handled by OF */
258  SCIP_Bool performpresolving; /**< Run orbital fixing during presolving? */
259  SCIP_Bool recomputerestart; /**< Recompute symmetries after a restart has occured? */
260  int ofsymcomptiming; /**< timing of orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
261  int lastrestart; /**< last restart for which symmetries have been computed */
262  int nfixedzero; /**< number of variables fixed to 0 */
263  int nfixedone; /**< number of variables fixed to 1 */
264  SCIP_Longint nodenumber; /**< number of node where propagation has been last applied */
265  SCIP_Bool offoundreduction; /**< whether orbital fixing has found a reduction since the last time computing symmetries */
266  SCIP_Bool disableofrestart; /**< whether OF shall be disabled if OF has found a reduction and a restart occurs */
267 };
268 
269 
270 
271 /*
272  * Event handler callback methods
273  */
274 
275 /** exec the event handler for handling global variable bound changes (necessary for orbital fixing)
276  *
277  * Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain
278  * preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be
279  * caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of
280  * orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when
281  * filtering out symmetries.
282  */
283 static
284 SCIP_DECL_EVENTEXEC(eventExecSymmetry)
285 {
286  SCIP_PROPDATA* propdata;
287  SCIP_VAR* var;
288  int varidx;
289 
290  assert( eventhdlr != NULL );
291  assert( eventdata != NULL );
292  assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_SYMMETRY_NAME) == 0 );
293  assert( event != NULL );
294 
295  propdata = (SCIP_PROPDATA*) eventdata;
296  assert( propdata != NULL );
297  assert( propdata->permvarmap != NULL );
298  assert( propdata->permstrans != NULL );
299  assert( propdata->nperms > 0 );
300  assert( propdata->permvars != NULL );
301  assert( propdata->npermvars > 0 );
302 
303  /* get fixed variable */
304  var = SCIPeventGetVar(event);
305  assert( var != NULL );
306  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
307 
308  if ( ! SCIPhashmapExists(propdata->permvarmap, (void*) var) )
309  {
310  SCIPerrorMessage("Invalid variable.\n");
311  SCIPABORT();
312  return SCIP_INVALIDDATA; /*lint !e527*/
313  }
314  varidx = SCIPhashmapGetImageInt(propdata->permvarmap, (void*) var);
315  assert( 0 <= varidx && varidx < propdata->npermvars );
316 
318  {
319  assert( SCIPisEQ(scip, SCIPeventGetNewbound(event), 0.0) );
320  assert( SCIPisEQ(scip, SCIPeventGetOldbound(event), 1.0) );
321 
322  SCIPdebugMsg(scip, "Mark variable <%s> as globally fixed to 0.\n", SCIPvarGetName(var));
323  assert( ! propdata->bg0[varidx] );
324  propdata->bg0[varidx] = TRUE;
325  propdata->bg0list[propdata->nbg0++] = varidx;
326  assert( propdata->nbg0 <= propdata->npermvars );
327  }
328 
330  {
331  assert( SCIPisEQ(scip, SCIPeventGetNewbound(event), 1.0) );
332  assert( SCIPisEQ(scip, SCIPeventGetOldbound(event), 0.0) );
333 
334  SCIPdebugMsg(scip, "Mark variable <%s> as globally fixed to 1.\n", SCIPvarGetName(var));
335  assert( ! propdata->bg1[varidx] );
336  propdata->bg1[varidx] = TRUE;
337  propdata->bg1list[propdata->nbg1++] = varidx;
338  assert( propdata->nbg1 <= propdata->npermvars );
339  }
340 
341  return SCIP_OKAY;
342 }
343 
344 
345 
346 
347 /*
348  * Table callback methods
349  */
350 
351 /** table data */
352 struct SCIP_TableData
353 {
354  SCIP_PROPDATA* propdata; /** pass data of propagator for table output function */
355 };
356 
357 
358 /** output method of orbital fixing propagator statistics table to output file stream 'file' */
359 static
360 SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
361 {
362  SCIP_TABLEDATA* tabledata;
363 
364  assert( scip != NULL );
365  assert( table != NULL );
366 
367  tabledata = SCIPtableGetData(table);
368  assert( tabledata != NULL );
369  assert( tabledata->propdata != NULL );
370 
371  if ( tabledata->propdata->nperms > 0 )
372  {
373  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, "Orbital fixing :\n");
374  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
375  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
376  }
377 
378  return SCIP_OKAY;
379 }
380 
381 
382 /** destructor of statistics table to free user data (called when SCIP is exiting) */
383 static
384 SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
385 {
386  SCIP_TABLEDATA* tabledata;
387  tabledata = SCIPtableGetData(table);
388  assert( tabledata != NULL );
389 
390  SCIPfreeBlockMemory(scip, &tabledata);
391 
392  return SCIP_OKAY;
393 }
394 
395 
396 
397 /*
398  * local data structures
399  */
400 
401 /** gets the key of the given element */
402 static
403 SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
404 { /*lint --e{715}*/
405  return elem;
406 }
407 
408 /** returns TRUE iff both keys are equal
409  *
410  * Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.
411  */
412 static
413 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQVartype)
414 {
415  SCIP* scip;
416  SYM_VARTYPE* k1;
417  SYM_VARTYPE* k2;
418 
419  scip = (SCIP*) userptr;
420  k1 = (SYM_VARTYPE*) key1;
421  k2 = (SYM_VARTYPE*) key2;
422 
423  /* first check objective coefficients */
424  if ( ! SCIPisEQ(scip, k1->obj, k2->obj) )
425  return FALSE;
426 
427  /* if still undecided, take lower bound */
428  if ( ! SCIPisEQ(scip, k1->lb, k2->lb) )
429  return FALSE;
430 
431  /* if still undecided, take upper bound */
432  if ( ! SCIPisEQ(scip, k1->ub, k2->ub) )
433  return FALSE;
434 
435  /* if still undecided, take variable type */
436  if ( k1->type != k2->type )
437  return FALSE;
438 
439  /* if still undecided, take number of conss var is contained in */
440  if ( k1->nconss != k2->nconss )
441  return FALSE;
442 
443  return TRUE;
444 }
445 
446 /** returns the hash value of the key */
447 static
448 SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
449 { /*lint --e{715}*/
450  SYM_VARTYPE* k;
451 
452  k = (SYM_VARTYPE*) key;
453 
455 }
456 
457 /** data struct to store arrays used for sorting rhs types */
459 {
460  SCIP_Real* vals; /**< array of values */
461  SYM_RHSSENSE* senses; /**< array of senses of rhs */
462  int nrhscoef; /**< size of arrays (for debugging) */
463 };
465 
466 /** sorts rhs types - first by sense, then by value
467  *
468  * Due to numerical issues, we first sort by sense, then by value.
469  *
470  * result:
471  * < 0: ind1 comes before (is better than) ind2
472  * = 0: both indices have the same value
473  * > 0: ind2 comes after (is worse than) ind2
474  */
475 static
476 SCIP_DECL_SORTINDCOMP(SYMsortRhsTypes)
477 {
478  SYM_SORTRHSTYPE* data;
479  SCIP_Real diffvals;
480 
481  data = (SYM_SORTRHSTYPE*) dataptr;
482  assert( 0 <= ind1 && ind1 < data->nrhscoef );
483  assert( 0 <= ind2 && ind2 < data->nrhscoef );
484 
485  /* first sort by senses */
486  if ( data->senses[ind1] < data->senses[ind2] )
487  return -1;
488  else if ( data->senses[ind1] > data->senses[ind2] )
489  return 1;
490 
491  /* senses are equal, use values */
492  diffvals = data->vals[ind1] - data->vals[ind2];
493 
494  if ( diffvals < 0.0 )
495  return -1;
496  else if ( diffvals > 0.0 )
497  return 1;
498 
499  return 0;
500 }
501 
502 /** sorts matrix coefficients
503  *
504  * result:
505  * < 0: ind1 comes before (is better than) ind2
506  * = 0: both indices have the same value
507  * > 0: ind2 comes after (is worse than) ind2
508  */
509 static
510 SCIP_DECL_SORTINDCOMP(SYMsortMatCoef)
511 {
512  SCIP_Real diffvals;
513  SCIP_Real* vals;
514 
515  vals = (SCIP_Real*) dataptr;
516  diffvals = vals[ind1] - vals[ind2];
517 
518  if ( diffvals < 0.0 )
519  return -1;
520  else if ( diffvals > 0.0 )
521  return 1;
522 
523  return 0;
524 }
525 
526 
527 
528 
529 /*
530  * Local methods
531  */
532 
533 #ifndef NDEBUG
534 /** checks that symmetry data is all freed */
535 static
537  SCIP_PROPDATA* propdata /**< propagator data */
538  )
539 {
540  assert( propdata->permvarmap == NULL );
541  assert( propdata->permvarsevents == NULL );
542  assert( propdata->bg0list == NULL );
543  assert( propdata->bg0 == NULL );
544  assert( propdata->bg1list == NULL );
545  assert( propdata->bg1 == NULL );
546  assert( propdata->nbg0 == 0 );
547  assert( propdata->nbg1 == 0 );
548  assert( propdata->genconss == NULL );
549 
550  assert( propdata->permvars == NULL );
551  assert( propdata->permvarsobj == NULL );
552  assert( propdata->inactiveperms == NULL );
553  assert( propdata->perms == NULL );
554  assert( propdata->permstrans == NULL );
555  assert( propdata->npermvars == 0 );
556  assert( propdata->nbinpermvars == 0 );
557  assert( propdata->nperms == -1 || propdata->nperms == 0 );
558  assert( propdata->nmaxperms == 0 );
559  assert( propdata->nmovedpermvars == 0 );
560  assert( propdata->nmovedvars == -1 );
561  assert( propdata->binvaraffected == FALSE );
562 
563  assert( propdata->componentblocked == NULL );
564  assert( propdata->componentbegins == NULL );
565  assert( propdata->components == NULL );
566  assert( propdata->ncomponents == -1 );
567 
568  return TRUE;
569 }
570 #endif
571 
572 
573 /** frees symmetry data */
574 static
576  SCIP* scip, /**< SCIP pointer */
577  SCIP_PROPDATA* propdata /**< propagator data */
578  )
579 {
580  int i;
581 
582  assert( scip != NULL );
583  assert( propdata != NULL );
584 
585  if ( propdata->permvarmap != NULL )
586  {
587  SCIPhashmapFree(&propdata->permvarmap);
588  }
589 
590  /* drop events */
591  if ( propdata->permvarsevents != NULL )
592  {
593  assert( propdata->permvars != NULL );
594  assert( propdata->npermvars > 0 );
595 
596  for (i = 0; i < propdata->npermvars; ++i)
597  {
598  if ( SCIPvarGetType(propdata->permvars[i]) == SCIP_VARTYPE_BINARY )
599  {
600  /* If symmetry is computed before presolving, it might happen that some variables are turned into binary
601  * variables, for which no event has been catched. Since there currently is no way of checking whether a var
602  * event has been caught for a particular variable, we use the stored eventfilter positions. */
603  if ( propdata->permvarsevents[i] >= 0 )
604  {
606  propdata->eventhdlr, (SCIP_EVENTDATA*) propdata, propdata->permvarsevents[i]) );
607  }
608  }
609  }
610  SCIPfreeBlockMemoryArray(scip, &propdata->permvarsevents, propdata->npermvars);
611  }
612 
613  /* release variables */
614  if ( propdata->binvaraffected )
615  {
616  for (i = 0; i < propdata->nbinpermvars; ++i)
617  {
618  SCIP_CALL( SCIPreleaseVar(scip, &propdata->permvars[i]) );
619  }
620  }
621 
622  /* free lists for orbitopal fixing */
623  if ( propdata->bg0list != NULL )
624  {
625  assert( propdata->bg0 != NULL );
626  assert( propdata->bg1list != NULL );
627  assert( propdata->bg1 != NULL );
628 
629  SCIPfreeBlockMemoryArray(scip, &propdata->bg0list, propdata->npermvars);
630  SCIPfreeBlockMemoryArray(scip, &propdata->bg0, propdata->npermvars);
631  SCIPfreeBlockMemoryArray(scip, &propdata->bg1list, propdata->npermvars);
632  SCIPfreeBlockMemoryArray(scip, &propdata->bg1, propdata->npermvars);
633 
634  propdata->nbg0 = 0;
635  propdata->nbg1 = 0;
636  }
637 
638  /* other data */
639  SCIPfreeBlockMemoryArrayNull(scip, &propdata->inactiveperms, propdata->nperms);
640 
641  /* free permstrans matrix*/
642  if ( propdata->permstrans != NULL )
643  {
644  assert( propdata->nperms > 0 );
645  assert( propdata->permvars != NULL );
646  assert( propdata->npermvars > 0 );
647  assert( propdata->nmaxperms > 0 );
648 
649  for (i = 0; i < propdata->npermvars; ++i)
650  {
651  SCIPfreeBlockMemoryArray(scip, &propdata->permstrans[i], propdata->nmaxperms);
652  }
653  SCIPfreeBlockMemoryArray(scip, &propdata->permstrans, propdata->npermvars);
654  }
655 
656  /* free data of added constraints */
657  if ( propdata->genconss != NULL )
658  {
659  assert( propdata->ngenconss > 0 || (ISORBITALFIXINGACTIVE(propdata->usesymmetry) && propdata->norbitopes == 0) );
660 
661  /* release constraints */
662  for (i = 0; i < propdata->ngenconss; ++i)
663  {
664  assert( propdata->genconss[i] != NULL );
665  SCIP_CALL( SCIPreleaseCons(scip, &propdata->genconss[i]) );
666  }
667 
668  /* free pointers to symmetry group and binary variables */
669  SCIPfreeBlockMemoryArray(scip, &propdata->genconss, propdata->nperms);
670  propdata->ngenconss = 0;
671  }
672 
673  /* free components */
674  if ( propdata->ncomponents > 0 )
675  {
676  assert( propdata->componentblocked != NULL );
677  assert( propdata->vartocomponent != NULL );
678  assert( propdata->componentbegins != NULL );
679  assert( propdata->components != NULL );
680 
681  SCIPfreeBlockMemoryArray(scip, &propdata->componentblocked, propdata->ncomponents);
682  SCIPfreeBlockMemoryArray(scip, &propdata->vartocomponent, propdata->npermvars);
683  SCIPfreeBlockMemoryArray(scip, &propdata->componentbegins, propdata->ncomponents + 1);
684  SCIPfreeBlockMemoryArray(scip, &propdata->components, propdata->nperms);
685 
686  propdata->ncomponents = -1;
687  }
688 
689  /* free main symmetry data */
690  if ( propdata->nperms > 0 )
691  {
692  assert( propdata->permvars != NULL );
693 
694  SCIPfreeBlockMemoryArray(scip, &propdata->permvars, propdata->npermvars);
695 
696  /* if orbital fixing runs exclusively, propdata->perms was already freed in determineSymmetry() */
697  if ( propdata->perms != NULL )
698  {
699  for (i = 0; i < propdata->nperms; ++i)
700  {
701  SCIPfreeBlockMemoryArray(scip, &propdata->perms[i], propdata->npermvars);
702  }
703  SCIPfreeBlockMemoryArray(scip, &propdata->perms, propdata->nmaxperms);
704  }
705 
706 #ifndef NDEBUG
707  SCIPfreeBlockMemoryArrayNull(scip, &propdata->permvarsobj, propdata->npermvars);
708 #endif
709 
710  propdata->npermvars = 0;
711  propdata->nbinpermvars = 0;
712  propdata->nperms = -1;
713  propdata->nmaxperms = 0;
714  propdata->nmovedpermvars = 0;
715  propdata->nmovedvars = -1;
716  propdata->log10groupsize = -1.0;
717  propdata->binvaraffected = FALSE;
718  }
719  propdata->nperms = -1;
720 
721  assert( checkSymmetryDataFree(propdata) );
722 
723  propdata->computedsymmetry = FALSE;
724  propdata->compressed = FALSE;
725 
726  return SCIP_OKAY;
727 }
728 
729 
730 /** deletes symmetry handling constraints */
731 static
733  SCIP* scip, /**< SCIP pointer */
734  SCIP_PROPDATA* propdata /**< propagator data */
735  )
736 {
737  int i;
738 
739  assert( scip != NULL );
740  assert( propdata != NULL );
741 
742  if ( propdata->ngenconss == 0 )
743  {
744  if ( propdata->genconss != NULL )
745  SCIPfreeBlockMemoryArray(scip, &propdata->genconss, propdata->nperms);
746  propdata->triedaddconss = FALSE;
747 
748  return SCIP_OKAY;
749  }
750  assert( propdata->genconss != NULL );
751  assert( propdata->nperms > 0 );
752  assert( propdata->nperms >= propdata->ngenconss );
753 
754  for (i = 0; i < propdata->ngenconss; ++i)
755  {
756  assert( propdata->genconss[i] != NULL );
757 
758  SCIP_CALL( SCIPdelCons(scip, propdata->genconss[i]) );
759  SCIP_CALL( SCIPreleaseCons(scip, &propdata->genconss[i]) );
760  }
761 
762  /* free pointers to symmetry group and binary variables */
763  SCIPfreeBlockMemoryArray(scip, &propdata->genconss, propdata->nperms);
764  propdata->ngenconss = 0;
765  propdata->triedaddconss = FALSE;
766 
767  return SCIP_OKAY;
768 }
769 
770 
771 /** determines whether variable should be fixed by permutations */
772 static
774  SYM_SPEC fixedtype, /**< bitset of variable types that should be fixed */
775  SCIP_VAR* var /**< variable to be considered */
776  )
777 {
778  if ( (fixedtype & SYM_SPEC_INTEGER) && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER )
779  return TRUE;
780  if ( (fixedtype & SYM_SPEC_BINARY) && SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
781  return TRUE;
782  if ( (fixedtype & SYM_SPEC_REAL) &&
784  return TRUE;
785  return FALSE;
786 }
787 
788 
789 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
790  *
791  * @note @p constant needs to be initialized!
792  */
793 static
795  SCIP* scip, /**< SCIP data structure */
796  SCIP_VAR*** vars, /**< pointer to vars array to get active variables for */
797  SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
798  int* nvars, /**< pointer to number of variables and values in vars and vals array */
799  SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
800  SCIP_Bool transformed /**< transformed constraint? */
801  )
802 {
803  int requiredsize;
804  int v;
805 
806  assert( scip != NULL );
807  assert( vars != NULL );
808  assert( scalars != NULL );
809  assert( *vars != NULL );
810  assert( *scalars != NULL );
811  assert( nvars != NULL );
812  assert( constant != NULL );
813 
814  if ( transformed )
815  {
816  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
817 
818  if ( requiredsize > *nvars )
819  {
820  SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) );
821  SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) );
822 
823  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
824  assert( requiredsize <= *nvars );
825  }
826  }
827  else
828  {
829  for (v = 0; v < *nvars; ++v)
830  {
831  SCIP_CALL( SCIPvarGetOrigvarSum(&(*vars)[v], &(*scalars)[v], constant) );
832  }
833  }
834  return SCIP_OKAY;
835 }
836 
837 
838 /** fills in matrix elements into coefficient arrays */
839 static
841  SCIP* scip, /**< SCIP data structure */
842  SCIP_Bool doubleequations, /**< Double equations to positive/negative version? */
843  SCIP_VAR** linvars, /**< array of linear variables */
844  SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */
845  int nlinvars, /**< number of linear variables */
846  SCIP_Real lhs, /**< left hand side */
847  SCIP_Real rhs, /**< right hand side */
848  SCIP_Bool istransformed, /**< whether the constraint is transformed */
849  SYM_RHSSENSE rhssense, /**< identifier of constraint type */
850  SYM_MATRIXDATA* matrixdata, /**< matrix data to be filled in */
851  int* nconssforvar /**< pointer to array to store for each var the number of conss */
852  )
853 {
854  SCIP_VAR** vars;
855  SCIP_Real* vals;
856  SCIP_Real constant = 0.0;
857  int nrhscoef;
858  int nmatcoef;
859  int nvars;
860  int j;
861 
862  assert( scip != NULL );
863  assert( nlinvars == 0 || linvars != NULL );
864  assert( lhs <= rhs );
865 
866  /* do nothing if constraint is empty */
867  if ( nlinvars == 0 )
868  return SCIP_OKAY;
869 
870  /* ignore redundant constraints */
871  if ( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
872  return SCIP_OKAY;
873 
874  /* duplicate variable and value array */
875  nvars = nlinvars;
876  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, linvars, nvars) );
877  if ( linvals != NULL )
878  {
879  SCIP_CALL( SCIPduplicateBufferArray(scip, &vals, linvals, nvars) );
880  }
881  else
882  {
883  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
884  for (j = 0; j < nvars; ++j)
885  vals[j] = 1.0;
886  }
887  assert( vars != NULL );
888  assert( vals != NULL );
889 
890  /* get active variables */
891  SCIP_CALL( getActiveVariables(scip, &vars, &vals, &nvars, &constant, istransformed) );
892 
893  /* check whether constraint is empty after transformation to active variables */
894  if ( nvars <= 0 )
895  {
896  SCIPfreeBufferArray(scip, &vals);
897  SCIPfreeBufferArray(scip, &vars);
898  return SCIP_OKAY;
899  }
900 
901  /* handle constant */
902  if ( ! SCIPisInfinity(scip, -lhs) )
903  lhs -= constant;
904  if ( ! SCIPisInfinity(scip, rhs) )
905  rhs -= constant;
906 
907  /* check whether we have to resize; note that we have to add 2 * nvars since two inequalities may be added */
908  if ( matrixdata->nmatcoef + 2 * nvars > matrixdata->nmaxmatcoef )
909  {
910  int newsize;
911 
912  newsize = SCIPcalcMemGrowSize(scip, matrixdata->nmatcoef + 2 * nvars);
913  assert( newsize >= 0 );
914  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matidx), matrixdata->nmaxmatcoef, newsize) );
915  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matrhsidx), matrixdata->nmaxmatcoef, newsize) );
916  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matvaridx), matrixdata->nmaxmatcoef, newsize) );
917  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matcoef), matrixdata->nmaxmatcoef, newsize) );
918  SCIPdebugMsg(scip, "Resized matrix coefficients from %u to %d.\n", matrixdata->nmaxmatcoef, newsize);
919  matrixdata->nmaxmatcoef = newsize;
920  }
921 
922  nrhscoef = matrixdata->nrhscoef;
923  nmatcoef = matrixdata->nmatcoef;
924 
925  /* check lhs/rhs */
926  if ( SCIPisEQ(scip, lhs, rhs) )
927  {
928  SCIP_Bool poscoef = FALSE;
929  SCIP_Bool negcoef = FALSE;
930 
931  assert( ! SCIPisInfinity(scip, rhs) );
932 
933  /* equality constraint */
934  matrixdata->rhscoef[nrhscoef] = rhs;
935 
936  /* if we deal with special constraints */
937  if ( rhssense >= SYM_SENSE_XOR )
938  matrixdata->rhssense[nrhscoef] = rhssense;
939  else
940  matrixdata->rhssense[nrhscoef] = SYM_SENSE_EQUATION;
941  matrixdata->rhsidx[nrhscoef] = nrhscoef;
942 
943  for (j = 0; j < nvars; ++j)
944  {
945  assert( nmatcoef < matrixdata->nmaxmatcoef );
946 
947  matrixdata->matidx[nmatcoef] = nmatcoef;
948  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
949 
950  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
951 
952  if ( nconssforvar != NULL )
953  nconssforvar[SCIPvarGetProbindex(vars[j])] += 1;
954  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
955  matrixdata->matcoef[nmatcoef++] = vals[j];
956  if ( SCIPisPositive(scip, vals[j]) )
957  poscoef = TRUE;
958  else
959  negcoef = TRUE;
960  }
961  nrhscoef++;
962 
963  /* add negative of equation; increases chance to detect symmetry, but might increase time to compute symmetry. */
964  if ( doubleequations && poscoef && negcoef )
965  {
966  for (j = 0; j < nvars; ++j)
967  {
968  assert( nmatcoef < matrixdata->nmaxmatcoef );
969  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
970 
971  matrixdata->matidx[nmatcoef] = nmatcoef;
972  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
973  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
974  matrixdata->matcoef[nmatcoef++] = -vals[j];
975  }
976  matrixdata->rhssense[nrhscoef] = SYM_SENSE_EQUATION;
977  matrixdata->rhsidx[nrhscoef] = nrhscoef;
978  matrixdata->rhscoef[nrhscoef++] = -rhs;
979  }
980  }
981  else
982  {
983 #ifndef NDEBUG
984  if ( rhssense == SYM_SENSE_BOUNDIS_TYPE_2 )
985  {
986  assert( ! SCIPisInfinity(scip, -lhs) );
987  assert( ! SCIPisInfinity(scip, rhs) );
988  }
989 #endif
990 
991  if ( ! SCIPisInfinity(scip, -lhs) )
992  {
993  matrixdata->rhscoef[nrhscoef] = -lhs;
994  if ( rhssense >= SYM_SENSE_XOR )
995  {
996  assert( rhssense == SYM_SENSE_BOUNDIS_TYPE_2 );
997  matrixdata->rhssense[nrhscoef] = rhssense;
998  }
999  else
1000  matrixdata->rhssense[nrhscoef] = SYM_SENSE_INEQUALITY;
1001 
1002  matrixdata->rhsidx[nrhscoef] = nrhscoef;
1003 
1004  for (j = 0; j < nvars; ++j)
1005  {
1006  assert( nmatcoef < matrixdata->nmaxmatcoef );
1007  matrixdata->matidx[nmatcoef] = nmatcoef;
1008  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
1009  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
1010 
1011  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1012 
1013  if ( nconssforvar != NULL )
1014  nconssforvar[SCIPvarGetProbindex(vars[j])] += 1;
1015 
1016  matrixdata->matcoef[nmatcoef++] = -vals[j];
1017  }
1018  nrhscoef++;
1019  }
1020 
1021  if ( ! SCIPisInfinity(scip, rhs) )
1022  {
1023  matrixdata->rhscoef[nrhscoef] = rhs;
1024  if ( rhssense >= SYM_SENSE_XOR )
1025  {
1026  assert( rhssense == SYM_SENSE_BOUNDIS_TYPE_2 );
1027  matrixdata->rhssense[nrhscoef] = rhssense;
1028  }
1029  else
1030  matrixdata->rhssense[nrhscoef] = SYM_SENSE_INEQUALITY;
1031 
1032  matrixdata->rhsidx[nrhscoef] = nrhscoef;
1033 
1034  for (j = 0; j < nvars; ++j)
1035  {
1036  assert( nmatcoef < matrixdata->nmaxmatcoef );
1037  matrixdata->matidx[nmatcoef] = nmatcoef;
1038  matrixdata->matrhsidx[nmatcoef] = nrhscoef;
1039 
1040  assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1041 
1042  if ( nconssforvar != NULL )
1043  nconssforvar[SCIPvarGetProbindex(vars[j])] += 1;
1044 
1045  matrixdata->matvaridx[nmatcoef] = SCIPvarGetProbindex(vars[j]);
1046  matrixdata->matcoef[nmatcoef++] = vals[j];
1047  }
1048  nrhscoef++;
1049  }
1050  }
1051  matrixdata->nrhscoef = nrhscoef;
1052  matrixdata->nmatcoef = nmatcoef;
1053 
1054  SCIPfreeBufferArray(scip, &vals);
1055  SCIPfreeBufferArray(scip, &vars);
1056 
1057  return SCIP_OKAY;
1058 }
1059 
1060 
1061 /** checks whether given permutations form a symmetry of a MIP
1062  *
1063  * We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed
1064  * in the right order to easily check rows. The rhs is used because of cache effects.
1065  */
1066 static
1068  SCIP* scip, /**< SCIP data structure */
1069  SYM_SPEC fixedtype, /**< variable types that must be fixed by symmetries */
1070  SYM_MATRIXDATA* matrixdata, /**< matrix data */
1071  int nperms, /**< number of permutations */
1072  int** perms /**< permutations */
1073  )
1074 {
1075  SCIP_Real* permrow = 0;
1076  int* rhsmatbeg = 0;
1077  int oldrhs;
1078  int j;
1079  int p;
1080 
1081  SCIPdebugMsg(scip, "Checking whether symmetries are symmetries (generators: %u).\n", nperms);
1082 
1083  /* set up dense row for permuted row */
1084  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &permrow, matrixdata->npermvars) );
1085 
1086  /* set up map between rows and first entry in matcoef array */
1087  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rhsmatbeg, matrixdata->nrhscoef) );
1088  for (j = 0; j < matrixdata->nrhscoef; ++j)
1089  rhsmatbeg[j] = -1;
1090 
1091  /* build map from rhs into matrix */
1092  oldrhs = -1;
1093  for (j = 0; j < matrixdata->nmatcoef; ++j)
1094  {
1095  int rhs;
1096 
1097  rhs = matrixdata->matrhsidx[j];
1098  if ( rhs != oldrhs )
1099  {
1100  assert( 0 <= rhs && rhs < matrixdata->nrhscoef );
1101  rhsmatbeg[rhs] = j;
1102  oldrhs = rhs;
1103  }
1104  }
1105 
1106  /* create row */
1107  for (j = 0; j < matrixdata->npermvars; ++j)
1108  permrow[j] = 0.0;
1109 
1110  /* check all generators */
1111  for (p = 0; p < nperms; ++p)
1112  {
1113  int* P;
1114  int r1;
1115  int r2;
1116 
1117  SCIPdebugMsg(scip, "Verifying automorphism group generator #%d ...\n", p);
1118  P = perms[p];
1119  assert( P != NULL );
1120 
1121  for (j = 0; j < matrixdata->npermvars; ++j)
1122  {
1123  if ( SymmetryFixVar(fixedtype, matrixdata->permvars[j]) && P[j] != j )
1124  {
1125  SCIPdebugMsg(scip, "Permutation does not fix types %u, moving variable %d.\n", fixedtype, j);
1126  return SCIP_ERROR;
1127  }
1128  }
1129 
1130  /* check all constraints == rhs */
1131  for (r1 = 0; r1 < matrixdata->nrhscoef; ++r1)
1132  {
1133  int npermuted = 0;
1134 
1135  /* fill row into permrow (dense) */
1136  j = rhsmatbeg[r1];
1137  assert( 0 <= j && j < matrixdata->nmatcoef );
1138  assert( matrixdata->matrhsidx[j] == r1 ); /* note: row cannot be empty by construction */
1139 
1140  /* loop through row */
1141  while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r1 )
1142  {
1143  int varidx;
1144 
1145  assert( matrixdata->matvaridx[j] < matrixdata->npermvars );
1146  varidx = P[matrixdata->matvaridx[j]];
1147  assert( 0 <= varidx && varidx < matrixdata->npermvars );
1148  if ( varidx != matrixdata->matvaridx[j] )
1149  ++npermuted;
1150  assert( SCIPisZero(scip, permrow[varidx]) );
1151  permrow[varidx] = matrixdata->matcoef[j];
1152  ++j;
1153  }
1154 
1155  /* if row is not affected by permutation, we do not have to check it */
1156  if ( npermuted > 0 )
1157  {
1158  /* check other rows (sparse) */
1159  SCIP_Bool found = FALSE;
1160  for (r2 = 0; r2 < matrixdata->nrhscoef; ++r2)
1161  {
1162  /* a permutation must map constraints of the same type and respect rhs coefficients */
1163  if ( matrixdata->rhssense[r1] == matrixdata->rhssense[r2] && SCIPisEQ(scip, matrixdata->rhscoef[r1], matrixdata->rhscoef[r2]) )
1164  {
1165  j = rhsmatbeg[r2];
1166  assert( 0 <= j && j < matrixdata->nmatcoef );
1167  assert( matrixdata->matrhsidx[j] == r2 );
1168  assert( matrixdata->matvaridx[j] < matrixdata->npermvars );
1169 
1170  /* loop through row r2 and check whether it is equal to permuted row r */
1171  while (j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r2 && SCIPisEQ(scip, permrow[matrixdata->matvaridx[j]], matrixdata->matcoef[j]) )
1172  ++j;
1173 
1174  /* check whether rows are completely equal */
1175  if ( j >= matrixdata->nmatcoef || matrixdata->matrhsidx[j] != r2 )
1176  {
1177  /* perm[p] is indeed a symmetry */
1178  found = TRUE;
1179  break;
1180  }
1181  }
1182  }
1183 
1184  assert( found );
1185  if ( ! found ) /*lint !e774*/
1186  {
1187  SCIPerrorMessage("Found permutation that is not a symmetry.\n");
1188  return SCIP_ERROR;
1189  }
1190  }
1191 
1192  /* reset permrow */
1193  j = rhsmatbeg[r1];
1194  while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r1 )
1195  {
1196  int varidx;
1197  varidx = P[matrixdata->matvaridx[j]];
1198  permrow[varidx] = 0.0;
1199  ++j;
1200  }
1201  }
1202  }
1203 
1204  SCIPfreeBlockMemoryArray(scip, &rhsmatbeg, matrixdata->nrhscoef);
1205  SCIPfreeBlockMemoryArray(scip, &permrow, matrixdata->npermvars);
1206 
1207  return SCIP_OKAY;
1208 }
1209 
1210 
1211 /** returns the number of active constraints that can be handled by symmetry */
1212 static
1214  SCIP* scip /**< SCIP instance */
1215  )
1216 {
1217  SCIP_CONSHDLR* conshdlr;
1218  int nhandleconss = 0;
1219 
1220  assert( scip != NULL );
1221 
1222  conshdlr = SCIPfindConshdlr(scip, "linear");
1223  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1224  conshdlr = SCIPfindConshdlr(scip, "linking");
1225  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1226  conshdlr = SCIPfindConshdlr(scip, "setppc");
1227  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1228  conshdlr = SCIPfindConshdlr(scip, "xor");
1229  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1230  conshdlr = SCIPfindConshdlr(scip, "and");
1231  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1232  conshdlr = SCIPfindConshdlr(scip, "or");
1233  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1234  conshdlr = SCIPfindConshdlr(scip, "logicor");
1235  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1236  conshdlr = SCIPfindConshdlr(scip, "knapsack");
1237  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1238  conshdlr = SCIPfindConshdlr(scip, "varbound");
1239  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1240  conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
1241  nhandleconss += SCIPconshdlrGetNActiveConss(conshdlr);
1242 
1243  return nhandleconss;
1244 }
1245 
1246 
1247 /** set symmetry data */
1248 static
1250  SCIP* scip, /**< SCIP pointer */
1251  SCIP_VAR** vars, /**< vars present at time of symmetry computation */
1252  int nvars, /**< number of vars present at time of symmetry computation */
1253  int nbinvars, /**< number of binary vars present at time of symmetry computation */
1254  SCIP_VAR*** permvars, /**< pointer to permvars array */
1255  int* npermvars, /**< pointer to store number of permvars */
1256  int* nbinpermvars, /**< pointer to store number of binary permvars */
1257  int** perms, /**< permutations matrix (nperms x nvars) */
1258  int nperms, /**< number of permutations */
1259  int* nmovedvars, /**< pointer to store number of vars affected by symmetry (if usecompression) or NULL */
1260  SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
1261  SCIP_Bool usecompression, /**< whether symmetry data shall be compressed */
1262  SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1263  SCIP_Bool* compressed /**< pointer to store whether compression has been performed */
1264  )
1265 {
1266  int i;
1267  int p;
1268 
1269  assert( scip != NULL );
1270  assert( vars != NULL );
1271  assert( nvars > 0 );
1272  assert( permvars != NULL );
1273  assert( npermvars != NULL );
1274  assert( nbinpermvars != NULL );
1275  assert( perms != NULL );
1276  assert( nperms > 0 );
1277  assert( binvaraffected != NULL );
1278  assert( SCIPisGE(scip, compressthreshold, 0.0) );
1279  assert( SCIPisLE(scip, compressthreshold, 1.0) );
1280  assert( compressed != NULL );
1281 
1282  /* set default return values */
1283  *permvars = vars;
1284  *npermvars = nvars;
1285  *nbinpermvars = nbinvars;
1286  *binvaraffected = FALSE;
1287  *compressed = FALSE;
1288 
1289  /* if we possibly perform compression */
1290  if ( usecompression && SCIPgetNVars(scip) >= COMPRESSNVARSLB )
1291  {
1292  SCIP_Real percentagemovedvars;
1293  int* labelmovedvars;
1294  int* labeltopermvaridx;
1295  int nbinvarsaffected = 0;
1296 
1297  assert( nmovedvars != NULL );
1298 
1299  *nmovedvars = 0;
1300 
1301  /* detect number of moved vars and label moved vars */
1302  SCIP_CALL( SCIPallocBufferArray(scip, &labelmovedvars, nvars) );
1303  SCIP_CALL( SCIPallocBufferArray(scip, &labeltopermvaridx, nvars) );
1304  for (i = 0; i < nvars; ++i)
1305  {
1306  labelmovedvars[i] = -1;
1307 
1308  for (p = 0; p < nperms; ++p)
1309  {
1310  if ( perms[p][i] != i )
1311  {
1312  labeltopermvaridx[*nmovedvars] = i;
1313  labelmovedvars[i] = (*nmovedvars)++;
1314 
1315  if ( SCIPvarIsBinary(vars[i]) )
1316  ++nbinvarsaffected;
1317  break;
1318  }
1319  }
1320  }
1321 
1322  if ( nbinvarsaffected > 0 )
1323  *binvaraffected = TRUE;
1324 
1325  /* check whether compression should be performed */
1326  percentagemovedvars = (SCIP_Real) *nmovedvars / (SCIP_Real) nvars;
1327  if ( *nmovedvars > 0 && SCIPisLE(scip, percentagemovedvars, compressthreshold) )
1328  {
1329  /* remove variables from permutations that are not affected by any permutation */
1330  for (p = 0; p < nperms; ++p)
1331  {
1332  /* iterate over labels and adapt permutation */
1333  for (i = 0; i < *nmovedvars; ++i)
1334  {
1335  assert( i <= labeltopermvaridx[i] );
1336  perms[p][i] = labelmovedvars[perms[p][labeltopermvaridx[i]]];
1337  }
1338 
1339  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &perms[p], nvars, *nmovedvars) );
1340  }
1341 
1342  /* remove variables from permvars array that are not affected by any symmetry */
1343  SCIP_CALL( SCIPallocBlockMemoryArray(scip, permvars, *nmovedvars) );
1344  for (i = 0; i < *nmovedvars; ++i)
1345  {
1346  (*permvars)[i] = vars[labeltopermvaridx[i]];
1347  }
1348  *npermvars = *nmovedvars;
1349  *nbinpermvars = nbinvarsaffected;
1350  *compressed = TRUE;
1351 
1352  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
1353  }
1354  SCIPfreeBufferArray(scip, &labeltopermvaridx);
1355  SCIPfreeBufferArray(scip, &labelmovedvars);
1356  }
1357  else
1358  {
1359  /* detect whether binary variable is affected by symmetry and count number of binary permvars */
1360  for (i = 0; i < nbinvars; ++i)
1361  {
1362  for (p = 0; p < nperms && ! *binvaraffected; ++p)
1363  {
1364  if ( perms[p][i] != i )
1365  {
1366  if ( SCIPvarIsBinary(vars[i]) )
1367  *binvaraffected = TRUE;
1368  break;
1369  }
1370  }
1371  }
1372  }
1373 
1374  return SCIP_OKAY;
1375 }
1376 
1377 
1378 /** computes symmetry group of a MIP */
1379 static
1381  SCIP* scip, /**< SCIP pointer */
1382  SCIP_Bool doubleequations, /**< Double equations to positive/negative version? */
1383  SCIP_Bool compresssymmetries, /**< Should non-affected variables be removed from permutation to save memory? */
1384  SCIP_Real compressthreshold, /**< Compression is used if percentage of moved vars is at most the threshold. */
1385  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1386  SYM_SPEC fixedtype, /**< variable types that must be fixed by symmetries */
1387  SCIP_Bool local, /**< Use local variable bounds? */
1388  SCIP_Bool checksymmetries, /**< Should all symmetries be checked after computation? */
1389  SCIP_Bool usecolumnsparsity, /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
1390  int* npermvars, /**< pointer to store number of variables for permutations */
1391  int* nbinpermvars, /**< pointer to store number of binary variables for permutations */
1392  SCIP_VAR*** permvars, /**< pointer to store variables on which permutations act */
1393  int* nperms, /**< pointer to store number of permutations */
1394  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1395  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1396  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
1397  int* nmovedvars, /**< pointer to store number of moved vars */
1398  SCIP_Bool* binvaraffected, /**< pointer to store wether a binary variable is affected by symmetry */
1399  SCIP_Bool* compressed, /**< pointer to store whether compression has been performed */
1400  SCIP_Bool* success /**< pointer to store whether symmetry computation was successful */
1401  )
1402 {
1403  SCIP_CONSHDLR* conshdlr;
1404  SYM_MATRIXDATA matrixdata;
1405  SCIP_HASHTABLE* vartypemap;
1406  SCIP_VAR** consvars;
1407  SCIP_Real* consvals;
1408  SCIP_CONS** conss;
1409  SCIP_VAR** vars;
1410  SYM_VARTYPE* uniquevararray;
1411  SYM_RHSSENSE oldsense = SYM_SENSE_UNKOWN;
1412  SYM_SORTRHSTYPE sortrhstype;
1413  SCIP_Real oldcoef = SCIP_INVALID;
1414  SCIP_Real val;
1415  int* nconssforvar = NULL;
1416  int nuniquevararray = 0;
1417  int nhandleconss;
1418  int nactiveconss;
1419  int nconss;
1420  int nvars;
1421  int nbinvars;
1422  int nvarsorig;
1423  int nallvars;
1424  int c;
1425  int j;
1426 
1427  assert( scip != NULL );
1428  assert( npermvars != NULL );
1429  assert( nbinpermvars != NULL );
1430  assert( permvars != NULL );
1431  assert( nperms != NULL );
1432  assert( nmaxperms != NULL );
1433  assert( perms != NULL );
1434  assert( log10groupsize != NULL );
1435  assert( binvaraffected != NULL );
1436  assert( compressed != NULL );
1437  assert( success != NULL );
1438  assert( SYMcanComputeSymmetry() );
1439 
1440  /* init */
1441  *npermvars = 0;
1442  *nbinpermvars = 0;
1443  *permvars = NULL;
1444  *nperms = 0;
1445  *nmaxperms = 0;
1446  *perms = NULL;
1447  *log10groupsize = 0;
1448  *nmovedvars = -1;
1449  *binvaraffected = FALSE;
1450  *compressed = FALSE;
1451  *success = FALSE;
1452 
1453  nconss = SCIPgetNConss(scip);
1454  nvars = SCIPgetNVars(scip);
1455  nbinvars = SCIPgetNBinVars(scip);
1456  nvarsorig = nvars;
1457 
1458  /* exit if no constraints or no variables are available */
1459  if ( nconss == 0 || nvars == 0 )
1460  {
1461  *success = TRUE;
1462  return SCIP_OKAY;
1463  }
1464 
1465  conss = SCIPgetConss(scip);
1466  assert( conss != NULL );
1467 
1468  /* compute the number of active constraints */
1469  nactiveconss = SCIPgetNActiveConss(scip);
1470 
1471  /* exit if no active constraints are available */
1472  if ( nactiveconss == 0 )
1473  {
1474  *success = TRUE;
1475  return SCIP_OKAY;
1476  }
1477 
1478  /* before we set up the matrix, check whether we can handle all constraints */
1479  nhandleconss = getNSymhandableConss(scip);
1480  assert( nhandleconss <= nactiveconss );
1481  if ( nhandleconss < nactiveconss )
1482  {
1483  /* In this case we found unkown constraints and we exit, since we cannot handle them. */
1484  *success = FALSE;
1485  *nperms = -1;
1486  return SCIP_OKAY;
1487  }
1488 
1489  SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
1490 
1491  /* copy variables */
1492  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
1493  assert( vars != NULL );
1494 
1495  /* fill matrixdata */
1496 
1497  /* use a staggered scheme for allocating space for non-zeros of constraint matrix since it can become large */
1498  if ( nvars <= 100000 )
1499  matrixdata.nmaxmatcoef = 100 * nvars;
1500  else if ( nvars <= 1000000 )
1501  matrixdata.nmaxmatcoef = 32 * nvars;
1502  else if ( nvars <= 16700000 )
1503  matrixdata.nmaxmatcoef = 16 * nvars;
1504  else
1505  matrixdata.nmaxmatcoef = INT_MAX / 10;
1506 
1507  matrixdata.nmatcoef = 0;
1508  matrixdata.nrhscoef = 0;
1509  matrixdata.nuniquemat = 0;
1510  matrixdata.nuniquevars = 0;
1511  matrixdata.nuniquerhs = 0;
1512  matrixdata.npermvars = nvars;
1513  matrixdata.permvars = vars;
1514  matrixdata.permvarcolors = NULL;
1515  matrixdata.matcoefcolors = NULL;
1516  matrixdata.rhscoefcolors = NULL;
1517 
1518  /* prepare matrix data (use block memory, since this can become large) */
1519  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef) );
1520  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef) );
1521  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef) );
1522  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef) );
1523  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhscoef, 2 * nactiveconss) );
1524  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhssense, 2 * nactiveconss) );
1525  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhsidx, 2 * nactiveconss) );
1526 
1527  /* prepare temporary constraint data (use block memory, since this can become large);
1528  * also allocate memory for fixed vars since some vars might have been deactivated meanwhile */
1529  nallvars = nvars + SCIPgetNFixedVars(scip);
1530  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consvars, nallvars) );
1531  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consvals, nallvars) );
1532 
1533  /* allocate memory for getting the number of constraints that contain a variable */
1534  if ( usecolumnsparsity )
1535  {
1536  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &nconssforvar, nvars) );
1537  }
1538 
1539  /* loop through all constraints */
1540  for (c = 0; c < nconss; ++c)
1541  {
1542  const char* conshdlrname;
1543  SCIP_CONS* cons;
1544  SCIP_VAR** linvars;
1545  int nconsvars;
1546 
1547  /* get constraint */
1548  cons = conss[c];
1549  assert( cons != NULL );
1550 
1551  /* skip non-active constraints */
1552  if ( ! SCIPconsIsActive(cons) )
1553  continue;
1554 
1555  /* Skip conflict constraints if we are late in the solving process */
1556  if ( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPconsIsConflict(cons) )
1557  continue;
1558 
1559  /* get constraint handler */
1560  conshdlr = SCIPconsGetHdlr(cons);
1561  assert( conshdlr != NULL );
1562 
1563  conshdlrname = SCIPconshdlrGetName(conshdlr);
1564  assert( conshdlrname != NULL );
1565 
1566  /* check type of constraint */
1567  if ( strcmp(conshdlrname, "linear") == 0 )
1568  {
1569  SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
1570  SCIPgetNVarsLinear(scip, cons), SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons),
1571  SCIPconsIsTransformed(cons), SYM_SENSE_UNKOWN, &matrixdata, nconssforvar) );
1572  }
1573  else if ( strcmp(conshdlrname, "linking") == 0 )
1574  {
1575  SCIP_VAR** curconsvars;
1576  SCIP_Real* curconsvals;
1577  int i;
1578 
1579  /* get constraint variables and their coefficients */
1580  curconsvals = SCIPgetValsLinking(scip, cons);
1581  SCIP_CALL( SCIPgetBinvarsLinking(scip, cons, &curconsvars, &nconsvars) );
1582  /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
1583  nconsvars++;
1584 
1585  /* copy vars and vals for binary variables */
1586  for( i = 0; i < nconsvars - 1; i++ )
1587  {
1588  consvars[i] = curconsvars[i];
1589  consvals[i] = (SCIP_Real) curconsvals[i];
1590  }
1591 
1592  /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
1593  consvars[nconsvars - 1] = SCIPgetLinkvarLinking(scip, cons);
1594  consvals[nconsvars - 1] = -1.0;
1595 
1596  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, 0.0, 0.0,
1597  SCIPconsIsTransformed(cons), SYM_SENSE_UNKOWN, &matrixdata, nconssforvar) );
1598  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, NULL, nconsvars - 1, 1.0, 1.0,
1599  SCIPconsIsTransformed(cons), SYM_SENSE_UNKOWN, &matrixdata, nconssforvar) );
1600  }
1601  else if ( strcmp(conshdlrname, "setppc") == 0 )
1602  {
1603  linvars = SCIPgetVarsSetppc(scip, cons);
1604  nconsvars = SCIPgetNVarsSetppc(scip, cons);
1605 
1606  switch ( SCIPgetTypeSetppc(scip, cons) )
1607  {
1609  SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata, nconssforvar) );
1610  break;
1612  SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1613  break;
1615  SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1616  break;
1617  default:
1618  SCIPerrorMessage("Unknown setppc type %d.\n", SCIPgetTypeSetppc(scip, cons));
1619  return SCIP_ERROR;
1620  }
1621  }
1622  else if ( strcmp(conshdlrname, "xor") == 0 )
1623  {
1624  SCIP_VAR** curconsvars;
1625  SCIP_VAR* var;
1626 
1627  /* get number of variables of XOR constraint (without integer variable) */
1628  nconsvars = SCIPgetNVarsXor(scip, cons);
1629 
1630  /* get variables of XOR constraint */
1631  curconsvars = SCIPgetVarsXor(scip, cons);
1632  for (j = 0; j < nconsvars; ++j)
1633  {
1634  assert( curconsvars[j] != NULL );
1635  consvars[j] = curconsvars[j];
1636  consvals[j] = 1.0;
1637  }
1638 
1639  /* intVar of xor constraint might have been removed */
1640  var = SCIPgetIntVarXor(scip, cons);
1641  if ( var != NULL )
1642  {
1643  consvars[nconsvars] = var;
1644  consvals[nconsvars++] = 2.0;
1645  }
1646  assert( nconsvars <= nallvars );
1647 
1648  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
1649  (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata, nconssforvar) );
1650  }
1651  else if ( strcmp(conshdlrname, "and") == 0 )
1652  {
1653  SCIP_VAR** curconsvars;
1654 
1655  /* get number of variables of AND constraint (without resultant) */
1656  nconsvars = SCIPgetNVarsAnd(scip, cons);
1657 
1658  /* get variables of AND constraint */
1659  curconsvars = SCIPgetVarsAnd(scip, cons);
1660 
1661  for (j = 0; j < nconsvars; ++j)
1662  {
1663  assert( curconsvars[j] != NULL );
1664  consvars[j] = curconsvars[j];
1665  consvals[j] = 1.0;
1666  }
1667 
1668  assert( SCIPgetResultantAnd(scip, cons) != NULL );
1669  consvars[nconsvars] = SCIPgetResultantAnd(scip, cons);
1670  consvals[nconsvars++] = 2.0;
1671  assert( nconsvars <= nallvars );
1672 
1673  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, 0.0, 0.0,
1674  SCIPconsIsTransformed(cons), SYM_SENSE_AND, &matrixdata, nconssforvar) );
1675  }
1676  else if ( strcmp(conshdlrname, "or") == 0 )
1677  {
1678  SCIP_VAR** curconsvars;
1679 
1680  /* get number of variables of OR constraint (without resultant) */
1681  nconsvars = SCIPgetNVarsOr(scip, cons);
1682 
1683  /* get variables of OR constraint */
1684  curconsvars = SCIPgetVarsOr(scip, cons);
1685 
1686  for (j = 0; j < nconsvars; ++j)
1687  {
1688  assert( curconsvars[j] != NULL );
1689  consvars[j] = curconsvars[j];
1690  consvals[j] = 1.0;
1691  }
1692 
1693  assert( SCIPgetResultantOr(scip, cons) != NULL );
1694  consvars[nconsvars] = SCIPgetResultantOr(scip, cons);
1695  consvals[nconsvars++] = 2.0;
1696  assert( nconsvars <= nallvars );
1697 
1698  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, 0.0, 0.0,
1699  SCIPconsIsTransformed(cons), SYM_SENSE_OR, &matrixdata, nconssforvar) );
1700  }
1701  else if ( strcmp(conshdlrname, "logicor") == 0 )
1702  {
1703  SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
1704  1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1705  }
1706  else if ( strcmp(conshdlrname, "knapsack") == 0 )
1707  {
1708  SCIP_Longint* weights;
1709 
1710  nconsvars = SCIPgetNVarsKnapsack(scip, cons);
1711 
1712  /* copy Longint array to SCIP_Real array and get active variables of constraint */
1713  weights = SCIPgetWeightsKnapsack(scip, cons);
1714  for (j = 0; j < nconsvars; ++j)
1715  consvals[j] = (SCIP_Real) weights[j];
1716  assert( nconsvars <= nallvars );
1717 
1718  SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
1719  (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1720  }
1721  else if ( strcmp(conshdlrname, "varbound") == 0 )
1722  {
1723  consvars[0] = SCIPgetVarVarbound(scip, cons);
1724  consvals[0] = 1.0;
1725 
1726  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
1727  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
1728 
1729  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
1730  SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1731  }
1732  else if ( strcmp(conshdlrname, "bounddisjunction") == 0 )
1733  {
1734  /* To model bound disjunctions, we normalize each constraint
1735  * \f[
1736  * (x_1 \{\leq,\geq\} b_1) \vee \ldots \vee (x_n \{\leq,\geq\} b_n)
1737  * \f]
1738  * to a constraint of type
1739  * \f[
1740  * (x_1 \leq b'_1 \vee \ldots \vee (x_n \leq b'_n).
1741  * \f]
1742  *
1743  * If no variable appears twice in such a normalized constraint, we say this bound disjunction
1744  * is of type 1. If the bound disjunction has length two and both disjunctions contain the same variable,
1745  * we say the bound disjunction is of type 2. Further bound disjunctions are possible, but can currently
1746  * not be handled.
1747  *
1748  * Bound disjunctions of type 1 are modeled as the linear constraint
1749  * \f[
1750  * b'_1 \cdot x_1 + \ldots + b'_n \cdot x_n = 0
1751  * \f]
1752  * and bound disjunctions of type 2 are modeled as the linear constraint
1753  * \f[
1754  * \min\{b'_1, b'_2\} \leq x_1 \leq \max\{b'_1, b'_2\}.
1755  * \f]
1756  * Note that problems arise if \fb'_i = 0\f for some variable \fx_i\f, because its coefficient in the
1757  * linear constraint is 0. To avoid this, we replace 0 by a special number.
1758  */
1759  SCIP_VAR** bounddisjvars;
1760  SCIP_BOUNDTYPE* boundtypes;
1761  SCIP_Real* bounds;
1762  SCIP_Bool repetition = FALSE;
1763  int nbounddisjvars;
1764  int k;
1765 
1766  /* collect coefficients for normalized constraint */
1767  nbounddisjvars = SCIPgetNVarsBounddisjunction(scip, cons);
1768  bounddisjvars = SCIPgetVarsBounddisjunction(scip, cons);
1769  boundtypes = SCIPgetBoundtypesBounddisjunction(scip, cons);
1770  bounds = SCIPgetBoundsBounddisjunction(scip, cons);
1771 
1772  /* copy data */
1773  for (j = 0; j < nbounddisjvars; ++j)
1774  {
1775  consvars[j] = bounddisjvars[j];
1776 
1777  /* normalize bounddisjunctions to SCIP_BOUNDTYPE_LOWER */
1778  if ( boundtypes[j] == SCIP_BOUNDTYPE_LOWER )
1779  consvals[j] = - bounds[j];
1780  else
1781  consvals[j] = bounds[j];
1782 
1783  /* special treatment of 0 values */
1784  if ( SCIPisZero(scip, consvals[j]) )
1785  consvals[j] = SCIP_SPECIALVAL;
1786 
1787  /* detect whether a variable appears in two literals */
1788  for (k = 0; k < j && ! repetition; ++k)
1789  {
1790  if ( consvars[j] == consvars[k] )
1791  repetition = TRUE;
1792  }
1793 
1794  /* stop, we cannot handle bounddisjunctions with more than two variables that contain a variable twice */
1795  if ( repetition && nbounddisjvars > 2 )
1796  {
1797  *success = FALSE;
1798 
1800  " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
1801 
1802  if ( usecolumnsparsity )
1803  SCIPfreeBlockMemoryArrayNull(scip, &nconssforvar, nvars);
1804 
1805  SCIPfreeBlockMemoryArrayNull(scip, &consvals, nallvars);
1806  SCIPfreeBlockMemoryArrayNull(scip, &consvars, nallvars);
1807  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhsidx, 2 * nactiveconss);
1808  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhssense, 2 * nactiveconss);
1809  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoef, 2 * nactiveconss);
1810  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef);
1811  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef);
1812  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef);
1813  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef);
1814  SCIPfreeBlockMemoryArrayNull(scip, &vars, nvars);
1815 
1816  return SCIP_OKAY;
1817  }
1818  }
1819  assert( ! repetition || nbounddisjvars == 2 );
1820 
1821  /* if no variable appears twice */
1822  if ( ! repetition )
1823  {
1824  /* add information for bounddisjunction of type 1 */
1825  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nbounddisjvars, 0.0, 0.0,
1826  SCIPconsIsTransformed(cons), SYM_SENSE_BOUNDIS_TYPE_1, &matrixdata, nconssforvar) );
1827  }
1828  else
1829  {
1830  /* add information for bounddisjunction of type 2 */
1831  SCIP_Real lhs;
1832  SCIP_Real rhs;
1833 
1834  lhs = MIN(consvals[0], consvals[1]);
1835  rhs = MAX(consvals[0], consvals[1]);
1836 
1837  consvals[0] = 1.0;
1838 
1839  SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 1, lhs, rhs,
1840  SCIPconsIsTransformed(cons), SYM_SENSE_BOUNDIS_TYPE_2, &matrixdata, nconssforvar) );
1841  }
1842  }
1843  else
1844  {
1845  SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
1846  SCIPconsGetName(cons), SCIPconshdlrGetName(conshdlr) );
1847  return SCIP_ERROR;
1848  }
1849  }
1850  assert( matrixdata.nrhscoef <= 2 * nactiveconss );
1851  assert( matrixdata.nrhscoef >= 0 );
1852 
1853  SCIPfreeBlockMemoryArray(scip, &consvals, nallvars);
1854  SCIPfreeBlockMemoryArray(scip, &consvars, nallvars);
1855 
1856  /* if no active constraint contains active variables */
1857  if ( matrixdata.nrhscoef == 0 )
1858  {
1859  *success = TRUE;
1860 
1861  if ( usecolumnsparsity )
1862  SCIPfreeBlockMemoryArrayNull(scip, &nconssforvar, nvars);
1863 
1864  /* free matrix data */
1865  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhsidx, 2 * nactiveconss);
1866  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhssense, 2 * nactiveconss);
1867  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoef, 2 * nactiveconss);
1868  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef);
1869  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef);
1870  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef);
1871  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef);
1872 
1873  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
1874 
1875  return SCIP_OKAY;
1876  }
1877 
1878  /* sort matrix coefficients (leave matrix array intact) */
1879  SCIPsort(matrixdata.matidx, SYMsortMatCoef, (void*) matrixdata.matcoef, matrixdata.nmatcoef);
1880 
1881  /* sort rhs types (first by sense, then by value, leave rhscoef intact) */
1882  sortrhstype.vals = matrixdata.rhscoef;
1883  sortrhstype.senses = matrixdata.rhssense;
1884  sortrhstype.nrhscoef = matrixdata.nrhscoef;
1885  SCIPsort(matrixdata.rhsidx, SYMsortRhsTypes, (void*) &sortrhstype, matrixdata.nrhscoef);
1886 
1887  /* create map for variables to indices */
1888  SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
1889  assert( vartypemap != NULL );
1890 
1891  /* allocate space for mappings to colors */
1892  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.permvarcolors, nvars) );
1893  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.matcoefcolors, matrixdata.nmatcoef) );
1894  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &matrixdata.rhscoefcolors, matrixdata.nrhscoef) );
1895  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniquevararray, nvars) );
1896 
1897  /* determine number of different coefficents */
1898 
1899  /* find non-equivalent variables: same objective, lower and upper bounds, and variable type */
1900  for (j = 0; j < nvars; ++j)
1901  {
1902  SCIP_VAR* var;
1903 
1904  var = vars[j];
1905  assert( var != NULL );
1906 
1907  /* if the variable type should be fixed, just increase the color */
1908  if ( SymmetryFixVar(fixedtype, var) )
1909  {
1910  matrixdata.permvarcolors[j] = matrixdata.nuniquevars++;
1911 #ifdef SCIP_OUTPUT
1912  SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
1913 #endif
1914  }
1915  else
1916  {
1917  SYM_VARTYPE* vt;
1918 
1919  vt = &uniquevararray[nuniquevararray];
1920  assert( nuniquevararray <= matrixdata.nuniquevars );
1921 
1922  vt->obj = SCIPvarGetObj(var);
1923  if ( local )
1924  {
1925  vt->lb = SCIPvarGetLbLocal(var);
1926  vt->ub = SCIPvarGetUbLocal(var);
1927  }
1928  else
1929  {
1930  vt->lb = SCIPvarGetLbGlobal(var);
1931  vt->ub = SCIPvarGetUbGlobal(var);
1932  }
1933  vt->type = SCIPvarGetType(var);
1934  vt->nconss = usecolumnsparsity ? nconssforvar[j] : 0; /*lint !e613*/
1935 
1936  if ( ! SCIPhashtableExists(vartypemap, (void*) vt) )
1937  {
1938  SCIP_CALL( SCIPhashtableInsert(vartypemap, (void*) vt) );
1939  vt->color = matrixdata.nuniquevars;
1940  matrixdata.permvarcolors[j] = matrixdata.nuniquevars++;
1941  ++nuniquevararray;
1942 #ifdef SCIP_OUTPUT
1943  SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
1944  SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
1945 #endif
1946  }
1947  else
1948  {
1949  SYM_VARTYPE* vtr;
1950 
1951  vtr = (SYM_VARTYPE*) SCIPhashtableRetrieve(vartypemap, (void*) vt);
1952  matrixdata.permvarcolors[j] = vtr->color;
1953  }
1954  }
1955  }
1956 
1957  /* If every variable is unique, terminate. -> no symmetries can be present */
1958  if ( matrixdata.nuniquevars == nvars )
1959  {
1960  *success = TRUE;
1961 
1962  /* free matrix data */
1963  SCIPfreeBlockMemoryArray(scip, &uniquevararray, nvars);
1964 
1965  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoefcolors, matrixdata.nrhscoef);
1966  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoefcolors, matrixdata.nmatcoef);
1967  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.permvarcolors, nvars);
1968  SCIPhashtableFree(&vartypemap);
1969 
1970  if ( usecolumnsparsity )
1971  SCIPfreeBlockMemoryArrayNull(scip, &nconssforvar, nvars);
1972 
1973  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhsidx, 2 * nactiveconss);
1974  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhssense, 2 * nactiveconss);
1975  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoef, 2 * nactiveconss);
1976  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef);
1977  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef);
1978  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef);
1979  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef);
1980 
1981  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
1982 
1983  return SCIP_OKAY;
1984  }
1985 
1986  /* find non-equivalent matrix entries (use sorting to avoid too many map calls) */
1987  for (j = 0; j < matrixdata.nmatcoef; ++j)
1988  {
1989  int idx;
1990 
1991  idx = matrixdata.matidx[j];
1992  assert( 0 <= idx && idx < matrixdata.nmatcoef );
1993 
1994  val = matrixdata.matcoef[idx];
1995  assert( oldcoef == SCIP_INVALID || oldcoef <= val ); /*lint !e777*/
1996 
1997  if ( ! SCIPisEQ(scip, val, oldcoef) )
1998  {
1999 #ifdef SCIP_OUTPUT
2000  SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
2001 #endif
2002  matrixdata.matcoefcolors[idx] = matrixdata.nuniquemat++;
2003  oldcoef = val;
2004  }
2005  else
2006  {
2007  assert( matrixdata.nuniquemat > 0 );
2008  matrixdata.matcoefcolors[idx] = matrixdata.nuniquemat - 1;
2009  }
2010  }
2011 
2012  /* find non-equivalent rhs */
2013  oldcoef = SCIP_INVALID;
2014  for (j = 0; j < matrixdata.nrhscoef; ++j)
2015  {
2016  SYM_RHSSENSE sense;
2017  int idx;
2018 
2019  idx = matrixdata.rhsidx[j];
2020  assert( 0 <= idx && idx < matrixdata.nrhscoef );
2021  sense = matrixdata.rhssense[idx];
2022  val = matrixdata.rhscoef[idx];
2023 
2024  /* make sure that new senses are treated with new color */
2025  if ( sense != oldsense )
2026  oldcoef = SCIP_INVALID;
2027  oldsense = sense;
2028  assert( oldcoef == SCIP_INVALID || oldcoef <= val ); /*lint !e777*/
2029 
2030  /* assign new color to new type */
2031  if ( ! SCIPisEQ(scip, val, oldcoef) )
2032  {
2033 #ifdef SCIP_OUTPUT
2034  SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
2035 #endif
2036  matrixdata.rhscoefcolors[idx] = matrixdata.nuniquerhs++;
2037  oldcoef = val;
2038  }
2039  else
2040  {
2041  assert( matrixdata.nuniquerhs > 0 );
2042  matrixdata.rhscoefcolors[idx] = matrixdata.nuniquerhs - 1;
2043  }
2044  }
2045  assert( 0 < matrixdata.nuniquevars && matrixdata.nuniquevars <= nvars );
2046  assert( 0 < matrixdata.nuniquerhs && matrixdata.nuniquerhs <= matrixdata.nrhscoef );
2047  assert( 0 < matrixdata.nuniquemat && matrixdata.nuniquemat <= matrixdata.nmatcoef );
2048 
2049  SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
2050  SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
2051  SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
2052 
2053  /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
2054  if ( matrixdata.nuniquevars < nvars && matrixdata.nuniquemat < matrixdata.nmatcoef )
2055  {
2056  /* determine generators */
2057  SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, nperms, nmaxperms, perms, log10groupsize) );
2058  assert( *nperms <= *nmaxperms );
2059 
2060  /* SCIPisStopped() might call SCIPgetGap() which is only available after initpresolve */
2061  if ( checksymmetries && SCIPgetStage(scip) > SCIP_STAGE_INITPRESOLVE && ! SCIPisStopped(scip) )
2062  {
2063  SCIP_CALL( checkSymmetriesAreSymmetries(scip, fixedtype, &matrixdata, *nperms, *perms) );
2064  }
2065 
2066  if ( *nperms > 0 )
2067  {
2068  SCIP_CALL( setSymmetryData(scip, vars, nvars, nbinvars, permvars, npermvars, nbinpermvars, *perms, *nperms,
2069  nmovedvars, binvaraffected, compresssymmetries, compressthreshold, compressed) );
2070  }
2071  else
2072  {
2073  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
2074  }
2075  }
2076  else
2077  {
2078  SCIPfreeBlockMemoryArray(scip, &vars, nvars);
2079  }
2080  *success = TRUE;
2081 
2082  /* free matrix data */
2083  SCIPfreeBlockMemoryArray(scip, &uniquevararray, nvarsorig);
2084 
2085  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoefcolors, matrixdata.nrhscoef);
2086  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoefcolors, matrixdata.nmatcoef);
2087  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.permvarcolors, nvarsorig);
2088  SCIPhashtableFree(&vartypemap);
2089 
2090  if ( usecolumnsparsity )
2091  SCIPfreeBlockMemoryArrayNull(scip, &nconssforvar, nvarsorig);
2092 
2093  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhsidx, 2 * nactiveconss);
2094  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhssense, 2 * nactiveconss);
2095  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.rhscoef, 2 * nactiveconss);
2096  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matvaridx, matrixdata.nmaxmatcoef);
2097  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matrhsidx, matrixdata.nmaxmatcoef);
2098  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matidx, matrixdata.nmaxmatcoef);
2099  SCIPfreeBlockMemoryArrayNull(scip, &matrixdata.matcoef, matrixdata.nmaxmatcoef);
2100 
2101  return SCIP_OKAY;
2102 }
2103 
2104 
2105 /** determines symmetry */
2106 static
2108  SCIP* scip, /**< SCIP instance */
2109  SCIP_PROPDATA* propdata, /**< propagator data */
2110  SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2111  SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2112  )
2113 {
2114  SCIP_Bool successful;
2115  int maxgenerators;
2116  int nhandleconss;
2117  int nconss;
2118  unsigned int type = 0;
2119  int nvars;
2120  int j;
2121  int p;
2122 
2123  assert( scip != NULL );
2124  assert( propdata != NULL );
2125  assert( propdata->usesymmetry >= 0 );
2126  assert( propdata->ofenabled || propdata->symconsenabled );
2127 
2128  /* do not compute symmetry if reoptimization is enabled */
2129  if ( SCIPisReoptEnabled(scip) )
2130  {
2131  propdata->ofenabled = FALSE;
2132  propdata->symconsenabled = FALSE;
2133  return SCIP_OKAY;
2134  }
2135 
2136  /* do not compute symmetry if Benders decomposition enabled */
2137  if ( SCIPgetNActiveBenders(scip) > 0 )
2138  {
2139  propdata->ofenabled = FALSE;
2140  propdata->symconsenabled = FALSE;
2141  return SCIP_OKAY;
2142  }
2143 
2144  /* skip symmetry computation if no graph automorphism code was linked */
2145  if ( ! SYMcanComputeSymmetry() )
2146  {
2147  propdata->ofenabled = FALSE;
2148  propdata->symconsenabled = FALSE;
2149 
2150  nconss = SCIPgetNActiveConss(scip);
2151  nhandleconss = getNSymhandableConss(scip);
2152 
2153  /* print verbMessage only if problem consists of symmetry handable constraints */
2154  assert( nhandleconss <= nconss );
2155  if ( nhandleconss < nconss )
2156  return SCIP_OKAY;
2157 
2159  " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2160 
2161  return SCIP_OKAY;
2162  }
2163 
2164  /* do not compute symmetry if there are active pricers */
2165  if ( SCIPgetNActivePricers(scip) > 0 )
2166  {
2167  propdata->ofenabled = FALSE;
2168  propdata->symconsenabled = FALSE;
2169  return SCIP_OKAY;
2170  }
2171 
2172  /* avoid trivial cases */
2173  nvars = SCIPgetNVars(scip);
2174  if ( nvars <= 0 )
2175  {
2176  propdata->ofenabled = FALSE;
2177  propdata->symconsenabled = FALSE;
2178 
2179  return SCIP_OKAY;
2180  }
2181 
2182  /* do not compute symmetry if there are no binary variables */
2183  if ( SCIPgetNBinVars(scip) == 0 )
2184  {
2185  propdata->ofenabled = FALSE;
2186  propdata->symconsenabled = FALSE;
2187 
2188  return SCIP_OKAY;
2189  }
2190 
2191  /* determine symmetry specification */
2192  if ( SCIPgetNBinVars(scip) > 0 )
2193  type |= (int) SYM_SPEC_BINARY;
2194  if ( SCIPgetNIntVars(scip) > 0 )
2195  type |= (int) SYM_SPEC_INTEGER;
2196  /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2197  if ( SCIPgetNContVars(scip) > 0 || SCIPgetNImplVars(scip) > 0 )
2198  type |= (int) SYM_SPEC_REAL;
2199 
2200  /* skip symmetry computation if required variables are not present */
2201  if ( ! (type & symspecrequire) )
2202  {
2204  " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2205  SCIPgetSolvingTime(scip),
2206  SCIPgetNBinVars(scip) > 0 ? '+' : '-',
2207  SCIPgetNIntVars(scip) > 0 ? '+' : '-',
2208  SCIPgetNContVars(scip) + SCIPgetNImplVars(scip) > 0 ? '+' : '-',
2209  (symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2210  (symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2211  (symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
2212 
2213  propdata->ofenabled = FALSE;
2214  propdata->symconsenabled = FALSE;
2215 
2216  return SCIP_OKAY;
2217  }
2218 
2219  /* if a restart occured, either disable orbital fixing... */
2220  if ( propdata->offoundreduction && propdata->disableofrestart && SCIPgetNRuns(scip) > propdata->lastrestart )
2221  propdata->ofenabled = FALSE;
2222  /* ... or free symmetries after a restart to recompute them later */
2223  else if ( (propdata->offoundreduction || propdata->recomputerestart)
2224  && propdata->nperms > 0 && SCIPgetNRuns(scip) > propdata->lastrestart )
2225  {
2226  assert( propdata->npermvars > 0 );
2227  assert( propdata->permvars != NULL );
2228  assert( ! propdata->ofenabled || propdata->permvarmap != NULL );
2229  assert( ! propdata->ofenabled || propdata->bg0list != NULL );
2230 
2231  /* reset symmetry information */
2232  SCIP_CALL( delSymConss(scip, propdata) );
2233  SCIP_CALL( freeSymmetryData(scip, propdata) );
2234  }
2235 
2236  /* skip computation if symmetry has already been computed */
2237  if ( propdata->computedsymmetry )
2238  return SCIP_OKAY;
2239 
2240  /* skip symmetry computation if there are constraints that cannot be handled by symmetry */
2241  nconss = SCIPgetNActiveConss(scip);
2242  nhandleconss = getNSymhandableConss(scip);
2243  if ( nhandleconss < nconss )
2244  {
2246  " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2247  SCIPgetSolvingTime(scip));
2248 
2249  propdata->ofenabled = FALSE;
2250  propdata->symconsenabled = FALSE;
2251 
2252  return SCIP_OKAY;
2253  }
2254 
2255  assert( propdata->npermvars == 0 );
2256  assert( propdata->permvars == NULL );
2257 #ifndef NDEBUG
2258  assert( propdata->permvarsobj == NULL );
2259 #endif
2260  assert( propdata->nperms < 0 );
2261  assert( propdata->nmaxperms == 0 );
2262  assert( propdata->perms == NULL );
2263 
2264  /* output message */
2266  " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2267  SCIPgetSolvingTime(scip),
2268  (symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2269  (symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2270  (symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-',
2271  (symspecrequirefixed & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2272  (symspecrequirefixed & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2273  (symspecrequirefixed & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
2274 
2275  /* output warning if we want to fix certain symmetry parts that we also want to compute */
2276  if ( symspecrequire & symspecrequirefixed )
2277  SCIPwarningMessage(scip, "Warning: some required symmetries must be fixed.\n");
2278 
2279  /* determine maximal number of generators depending on the number of variables */
2280  maxgenerators = propdata->maxgenerators;
2281  maxgenerators = MIN(maxgenerators, MAXGENNUMERATOR / nvars);
2282 
2283  /* actually compute (global) symmetry */
2284  SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2285  maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity,
2286  &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2287  &propdata->perms, &propdata->log10groupsize, &propdata->nmovedvars, &propdata->binvaraffected,
2288  &propdata->compressed, &successful) );
2289 
2290  /* mark that we have computed the symmetry group */
2291  propdata->computedsymmetry = TRUE;
2292 
2293  /* store restart level */
2294  propdata->lastrestart = SCIPgetNRuns(scip);
2295 
2296  /* return if not successful */
2297  if ( ! successful )
2298  {
2299  assert( checkSymmetryDataFree(propdata) );
2300  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2301 
2302  propdata->ofenabled = FALSE;
2303  propdata->symconsenabled = FALSE;
2304 
2305  return SCIP_OKAY;
2306  }
2307 
2308  /* return if no symmetries found */
2309  if ( propdata->nperms == 0 )
2310  {
2311  assert( checkSymmetryDataFree(propdata) );
2312  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
2313 
2314  propdata->ofenabled = FALSE;
2315  propdata->symconsenabled = FALSE;
2316 
2317  return SCIP_OKAY;
2318  }
2319 
2320  /* display statistics */
2321  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2322  SCIPgetSolvingTime(scip), propdata->nperms);
2323 
2324  /* display statistics: maximum number of generators */
2325  if ( maxgenerators == 0 )
2327  else
2328  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%u", maxgenerators);
2329 
2330  /* display statistics: log10 group size, number of affected vars*/
2331  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2332 
2333  if ( propdata->displaynorbitvars )
2334  {
2335  if ( propdata->nmovedvars == -1 )
2336  {
2337  SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2338  propdata->npermvars, &(propdata->nmovedvars)) );
2339  }
2340  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2341  }
2342  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ")\n");
2343 
2344  /* exit if no binary variables are affected by symmetry */
2345  if ( ! propdata->binvaraffected )
2346  {
2347  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2348 
2349  /* free data and exit */
2350  SCIP_CALL( freeSymmetryData(scip, propdata) );
2351 
2352  /* disable OF and symmetry handling constraints */
2353  propdata->ofenabled = FALSE;
2354  propdata->symconsenabled = FALSE;
2355 
2356  return SCIP_OKAY;
2357  }
2358 
2359  assert( propdata->nperms > 0 );
2360  assert( propdata->npermvars > 0 );
2361 
2362  /* compute components */
2363  assert( propdata->components == NULL );
2364  assert( propdata->componentbegins == NULL );
2365  assert( propdata->vartocomponent == NULL );
2366 
2367 #ifdef SCIP_OUTPUT_COMPONENT
2368  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2369 #endif
2370 
2371  /* we only need the components for orbital fixing and orbitope detection */
2372  if ( propdata->ofenabled || ( propdata->symconsenabled && propdata->detectorbitopes ) )
2373  {
2374  SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2375  propdata->npermvars, FALSE, &propdata->components, &propdata->componentbegins,
2376  &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
2377  }
2378 
2379 #ifdef SCIP_OUTPUT_COMPONENT
2380  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
2381 #endif
2382 
2383  /* set up data for OF */
2384  if ( propdata->ofenabled )
2385  {
2386  int componentidx;
2387  int v;
2388 
2389  /* transpose symmetries matrix here if necessary */
2390  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permstrans, propdata->npermvars) );
2391  for (v = 0; v < propdata->npermvars; ++v)
2392  {
2393  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->permstrans[v]), propdata->nmaxperms) );
2394  for (p = 0; p < propdata->nperms; ++p)
2395  {
2396  if ( SCIPvarIsBinary(propdata->permvars[v]) )
2397  propdata->permstrans[v][p] = propdata->perms[p][v];
2398  else
2399  propdata->permstrans[v][p] = v; /* ignore symmetry information on non-binary variables */
2400  }
2401  }
2402 
2403  /* prepare array for active permutations */
2404  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inactiveperms, propdata->nperms) );
2405  for (v = 0; v < propdata->nperms; ++v)
2406  propdata->inactiveperms[v] = FALSE;
2407 
2408  /* create hashmap for storing the indices of variables */
2409  assert( propdata->permvarmap == NULL );
2410  SCIP_CALL( SCIPhashmapCreate(&propdata->permvarmap, SCIPblkmem(scip), propdata->npermvars) );
2411 
2412  /* prepare data structures */
2413  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permvarsevents, propdata->npermvars) );
2414  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg0, propdata->npermvars) );
2415  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg0list, propdata->npermvars) );
2416  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg1, propdata->npermvars) );
2417  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg1list, propdata->npermvars) );
2418 
2419  /* insert variables into hashmap */
2420  for (v = 0; v < propdata->npermvars; ++v)
2421  {
2422  SCIP_CALL( SCIPhashmapInsertInt(propdata->permvarmap, propdata->permvars[v], v) );
2423 
2424  propdata->bg0[v] = FALSE;
2425  propdata->bg1[v] = FALSE;
2426  propdata->permvarsevents[v] = -1;
2427 
2428  /* collect number of moved permvars that are handled by OF */
2429  componentidx = propdata->vartocomponent[v];
2430  if ( componentidx > -1 && ! propdata->componentblocked[componentidx] )
2431  propdata->nmovedpermvars += 1;
2432 
2433  /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
2434  * are not branched on. */
2435  if ( SCIPvarGetType(propdata->permvars[v]) == SCIP_VARTYPE_BINARY )
2436  {
2437  /* catch whether binary variables are globally fixed; also store filter position */
2439  propdata->eventhdlr, (SCIP_EVENTDATA*) propdata, &propdata->permvarsevents[v]) );
2440  }
2441  }
2442  assert( propdata->nbg1 == 0 );
2443  }
2444 
2445 #ifndef NDEBUG
2446  /* store objective coefficients for debug purposes */
2447  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permvarsobj, propdata->npermvars) );
2448  for (j = 0; j < propdata->npermvars; ++j)
2449  propdata->permvarsobj[j] = SCIPvarGetObj(propdata->permvars[j]);
2450 #endif
2451 
2452  /* capture binary variables and forbid multi-aggregation of symmetric variables
2453  *
2454  * note: binary variables are in the beginning of pervars
2455  */
2456  for (j = 0; j < propdata->nbinpermvars; ++j)
2457  {
2458  SCIP_CALL( SCIPcaptureVar(scip, propdata->permvars[j]) );
2459 
2460  if ( propdata->compressed )
2461  {
2462  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->permvars[j]) );
2463  }
2464  else
2465  {
2466  for (p = 0; p < propdata->nperms; ++p)
2467  {
2468  if ( propdata->perms[p][j] != j )
2469  {
2470  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->permvars[j]) );
2471  break;
2472  }
2473  }
2474  }
2475  }
2476 
2477  /* free original perms matrix if no symmetry constraints are added */
2478  if ( ! propdata->symconsenabled )
2479  {
2480  for (p = 0; p < propdata->nperms; ++p)
2481  {
2482  SCIPfreeBlockMemoryArray(scip, &(propdata->perms)[p], propdata->npermvars);
2483  }
2484  SCIPfreeBlockMemoryArrayNull(scip, &propdata->perms, propdata->nmaxperms);
2485  }
2486 
2487  return SCIP_OKAY;
2488 }
2489 
2490 
2491 
2492 /*
2493  * Functions for symmetry constraints
2494  */
2495 
2496 
2497 /** checks whether components of the symmetry group can be completely handled by orbitopes */
2498 static
2500  SCIP* scip, /**< SCIP instance */
2501  SCIP_PROPDATA* propdata, /**< pointer to data of symmetry propagator */
2502  int* components, /**< array containing components of symmetry group */
2503  int* componentbegins, /**< array containing begin positions of components in components array */
2504  int ncomponents /**< number of components */
2505  )
2506 {
2507  SCIP_VAR** permvars;
2508  int** perms;
2509  int npermvars;
2510  int i;
2511 
2512  assert( scip != NULL );
2513  assert( propdata != NULL );
2514  assert( components != NULL );
2515  assert( componentbegins != NULL );
2516  assert( ncomponents > 0 );
2517  assert( propdata->nperms >= 0 );
2518 
2519  /* exit if no symmetry is present */
2520  if ( propdata->nperms == 0 )
2521  return SCIP_OKAY;
2522 
2523  assert( propdata->nperms > 0 );
2524  assert( propdata->perms != NULL );
2525  assert( propdata->nbinpermvars >= 0 );
2526  assert( propdata->npermvars >= 0 );
2527  assert( propdata->permvars != NULL );
2528 
2529  /* exit if no symmetry on binary variables is present */
2530  if ( propdata->nbinpermvars == 0 )
2531  {
2532  assert( ! propdata->binvaraffected );
2533  return SCIP_OKAY;
2534  }
2535 
2536  perms = propdata->perms;
2537  npermvars = propdata->npermvars;
2538  permvars = propdata->permvars;
2539 
2540  /* iterate over components */
2541  for (i = 0; i < ncomponents; ++i)
2542  {
2543  SCIP_VAR*** vars;
2544  SCIP_VAR*** varsallocorder;
2545  SCIP_CONS* cons;
2546  SCIP_Bool* usedperm;
2547  SCIP_Bool isorbitope = TRUE;
2548  SCIP_Bool infeasibleorbitope;
2549  int** orbitopevaridx;
2550  int* columnorder;
2551  int npermsincomponent;
2552  int ntwocyclescomp = INT_MAX;
2553  int nfilledcols;
2554  int nusedperms;
2555  int* nusedelems;
2556  int coltoextend;
2557  int j;
2558  int row;
2559 
2560  /* get properties of permutations */
2561  npermsincomponent = componentbegins[i + 1] - componentbegins[i];
2562  assert( npermsincomponent > 0 );
2563  for (j = componentbegins[i]; j < componentbegins[i + 1]; ++j)
2564  {
2565  SCIP_Bool iscompoftwocycles = FALSE;
2566  SCIP_Bool allvarsbinary = TRUE;
2567  int ntwocyclesperm = 0;
2568 
2569  SCIP_CALL( SCIPgetPropertiesPerm(perms[components[j]], permvars, npermvars, &iscompoftwocycles, &ntwocyclesperm, &allvarsbinary) );
2570 
2571  /* if we are checking the first permutation */
2572  if ( ntwocyclescomp == INT_MAX )
2573  ntwocyclescomp = ntwocyclesperm;
2574 
2575  /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
2576  if ( ntwocyclescomp == 0 || ntwocyclescomp != ntwocyclesperm || ! allvarsbinary )
2577  {
2578  isorbitope = FALSE;
2579  break;
2580  }
2581  }
2582 
2583  /* if no orbitope was detected */
2584  if ( ! isorbitope )
2585  continue;
2586  assert( ntwocyclescomp > 0 );
2587  assert( ntwocyclescomp < INT_MAX );
2588 
2589  /* iterate over permutations and check whether for each permutation there exists
2590  * another permutation whose 2-cycles intersect pairwise in exactly one element */
2591 
2592  /* whether a permutation was considered to contribute to orbitope */
2593  SCIP_CALL( SCIPallocClearBufferArray(scip, &usedperm, npermsincomponent) );
2594  nusedperms = 0;
2595 
2596  /* orbitope matrix for indices of variables in permvars array */
2597  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx, ntwocyclescomp) );
2598  for (j = 0; j < ntwocyclescomp; ++j)
2599  {
2600  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
2601  }
2602 
2603  /* order of columns of orbitopevaridx */
2604  SCIP_CALL( SCIPallocBufferArray(scip, &columnorder, npermsincomponent + 1) );
2605  for (j = 0; j < npermsincomponent + 1; ++j)
2606  columnorder[j] = npermsincomponent + 2;
2607 
2608  /* count how often an element was used in the potential orbitope */
2609  SCIP_CALL( SCIPallocClearBufferArray(scip, &nusedelems, npermvars) );
2610 
2611  /* fill first two columns of orbitopevaridx matrix */
2612  row = 0;
2613  for (j = 0; j < npermvars; ++j)
2614  {
2615  int permidx;
2616 
2617  permidx = components[componentbegins[i]];
2618 
2619  /* avoid adding the same 2-cycle twice */
2620  if ( perms[permidx][j] > j )
2621  {
2622  orbitopevaridx[row][0] = j;
2623  orbitopevaridx[row++][1] = perms[permidx][j];
2624  nusedelems[j] += 1;
2625  nusedelems[perms[permidx][j]] += 1;
2626  }
2627 
2628  if ( row == ntwocyclescomp )
2629  break;
2630  }
2631  assert( row == ntwocyclescomp );
2632 
2633  usedperm[0] = TRUE;
2634  ++nusedperms;
2635  columnorder[0] = 0;
2636  columnorder[1] = 1;
2637  nfilledcols = 2;
2638 
2639  /* extend orbitopevaridx matrix to the left, i.e., iteratively find new permutations that
2640  * intersect the last added left column in each row in exactly one entry, starting with
2641  * column 0 */
2642  coltoextend = 0;
2643  for (j = 0; j < npermsincomponent; ++j)
2644  { /* lint --e{850} */
2645  SCIP_Bool success = FALSE;
2646  SCIP_Bool infeasible = FALSE;
2647 
2648  if ( nusedperms == npermsincomponent )
2649  break;
2650 
2651  if ( usedperm[j] )
2652  continue;
2653 
2654  SCIP_CALL( SCIPextendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
2655  perms[components[componentbegins[i] + j]], TRUE, &nusedelems, &success, &infeasible) );
2656 
2657  if ( infeasible )
2658  {
2659  isorbitope = FALSE;
2660  break;
2661  }
2662  else if ( success )
2663  {
2664  usedperm[j] = TRUE;
2665  ++nusedperms;
2666  coltoextend = nfilledcols;
2667  columnorder[nfilledcols++] = -1; /* mark column to be filled from the left */
2668  j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2669  }
2670  }
2671 
2672  if ( ! isorbitope ) /*lint !e850*/
2673  goto FREEDATASTRUCTURES;
2674 
2675  coltoextend = 1;
2676  for (j = 0; j < npermsincomponent; ++j)
2677  { /*lint --e(850)*/
2678  SCIP_Bool success = FALSE;
2679  SCIP_Bool infeasible = FALSE;
2680 
2681  if ( nusedperms == npermsincomponent )
2682  break;
2683 
2684  if ( usedperm[j] )
2685  continue;
2686 
2687  SCIP_CALL( SCIPextendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
2688  perms[components[componentbegins[i] + j]], FALSE, &nusedelems, &success, &infeasible) );
2689 
2690  if ( infeasible )
2691  {
2692  isorbitope = FALSE;
2693  break;
2694  }
2695  else if ( success )
2696  {
2697  usedperm[j] = TRUE;
2698  ++nusedperms;
2699  coltoextend = nfilledcols;
2700  columnorder[nfilledcols] = 1; /* mark column to be filled from the right */
2701  ++nfilledcols;
2702  j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2703  }
2704  }
2705 
2706  if ( nusedperms < npermsincomponent ) /*lint !e850*/
2707  isorbitope = FALSE;
2708 
2709  if ( ! isorbitope )
2710  goto FREEDATASTRUCTURES;
2711 
2712  /* we have found a potential orbitope, prepare data for orbitope conshdlr */
2713  SCIP_CALL( SCIPallocBufferArray(scip, &vars, ntwocyclescomp) );
2714  SCIP_CALL( SCIPallocBufferArray(scip, &varsallocorder, ntwocyclescomp) );
2715  for (j = 0; j < ntwocyclescomp; ++j)
2716  {
2717  SCIP_CALL( SCIPallocBufferArray(scip, &vars[j], npermsincomponent + 1) ); /*lint !e866*/
2718  varsallocorder[j] = vars[j]; /* to ensure that we can free the buffer in reverse order */
2719  }
2720 
2721  /* prepare variable matrix (reorder columns of orbitopevaridx) */
2722  infeasibleorbitope = FALSE;
2723  SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(&vars, ntwocyclescomp, npermsincomponent + 1, permvars, npermvars,
2724  orbitopevaridx, columnorder, nusedelems, &infeasibleorbitope) );
2725 
2726  if ( ! infeasibleorbitope )
2727  {
2728  SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, "orbitope", vars, SCIP_ORBITOPETYPE_FULL,
2729  ntwocyclescomp, npermsincomponent + 1, TRUE, FALSE,
2730  propdata->conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2731 
2732  SCIP_CALL( SCIPaddCons(scip, cons) );
2733 
2734  /* do not release constraint here - will be done later */
2735  propdata->genconss[propdata->ngenconss++] = cons;
2736  ++propdata->norbitopes;
2737 
2738  propdata->componentblocked[i] = TRUE;
2739  }
2740 
2741  /* free data structures */
2742  for (j = ntwocyclescomp - 1; j >= 0; --j)
2743  {
2744  SCIPfreeBufferArray(scip, &varsallocorder[j]);
2745  }
2746  SCIPfreeBufferArray(scip, &varsallocorder);
2747  SCIPfreeBufferArray(scip, &vars);
2748 
2749  FREEDATASTRUCTURES:
2750  SCIPfreeBufferArray(scip, &nusedelems);
2751  SCIPfreeBufferArray(scip, &columnorder);
2752  for (j = ntwocyclescomp - 1; j >= 0; --j)
2753  {
2754  SCIPfreeBufferArray(scip, &orbitopevaridx[j]);
2755  }
2756  SCIPfreeBufferArray(scip, &orbitopevaridx);
2757  SCIPfreeBufferArray(scip, &usedperm);
2758  }
2759 
2760  return SCIP_OKAY;
2761 }
2762 
2763 
2764 /** adds symresack constraints */
2765 static
2767  SCIP* scip, /**< SCIP instance */
2768  SCIP_PROP* prop, /**< symmetry breaking propagator */
2769  int* components, /**< array containing components of symmetry group */
2770  int* componentbegins, /**< array containing begin positions of components in components array */
2771  int ncomponents /**< number of components */
2772  )
2773 {
2774  SCIP_PROPDATA* propdata;
2775  SCIP_VAR** permvars;
2776  SCIP_Bool conssaddlp;
2777  int** perms;
2778  int nsymresackcons = 0;
2779  int npermvars;
2780  int i;
2781  int p;
2782 
2783  assert( scip != NULL );
2784  assert( prop != NULL );
2785 
2786  propdata = SCIPpropGetData(prop);
2787  assert( propdata != NULL );
2788  assert( propdata->npermvars >= 0 );
2789  assert( propdata->nbinpermvars >= 0 );
2790 
2791  /* if no symmetries on binary variables are present */
2792  if ( propdata->nbinpermvars == 0 )
2793  {
2794  assert( propdata->binvaraffected == 0 );
2795  return SCIP_OKAY;
2796  }
2797 
2798  perms = propdata->perms;
2799  permvars = propdata->permvars;
2800  npermvars = propdata->npermvars;
2801  conssaddlp = propdata->conssaddlp;
2802 
2803  assert( propdata->nperms <= 0 || perms != NULL );
2804  assert( permvars != NULL );
2805  assert( npermvars > 0 );
2806 
2807  /* if components have not been computed */
2808  if ( ncomponents == -1 )
2809  {
2810  assert( ! propdata->ofenabled );
2811  assert( ! propdata->detectorbitopes );
2812 
2813  /* loop through perms and add symresack constraints */
2814  for (p = 0; p < propdata->nperms; ++p)
2815  {
2816  SCIP_CONS* cons;
2817  char name[SCIP_MAXSTRLEN];
2818 
2819  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_perm%d", p);
2820  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[p], permvars, npermvars, FALSE,
2821  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2822 
2823  SCIP_CALL( SCIPaddCons(scip, cons) );
2824 
2825  /* do not release constraint here - will be done later */
2826  propdata->genconss[propdata->ngenconss++] = cons;
2827  ++propdata->nsymresacks;
2828  ++nsymresackcons;
2829  }
2830  }
2831  else
2832  {
2833  /* loop through components */
2834  for (i = 0; i < ncomponents; ++i)
2835  {
2836  /* skip components that were treated by different symmetry handling techniques */
2837  if ( propdata->componentblocked[i] )
2838  continue;
2839 
2840  /* loop through perms in component i and add symresack constraints */
2841  for (p = componentbegins[i]; p < componentbegins[i + 1]; ++p)
2842  {
2843  SCIP_CONS* cons;
2844  int permidx;
2845  char name[SCIP_MAXSTRLEN];
2846 
2847  permidx = components[p];
2848 
2849  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_component%d_perm%d", i, permidx);
2850  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
2851  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2852 
2853  SCIP_CALL( SCIPaddCons(scip, cons) );
2854 
2855  /* do not release constraint here - will be done later */
2856  propdata->genconss[propdata->ngenconss++] = cons;
2857  ++propdata->nsymresacks;
2858  ++nsymresackcons;
2859  }
2860  }
2861  }
2862 
2863  SCIPdebugMsg(scip, "Added %d symresack constraints.\n", nsymresackcons);
2864 
2865  return SCIP_OKAY;
2866 }
2867 
2868 
2869 /** finds problem symmetries */
2870 static
2872  SCIP* scip, /**< SCIP instance */
2873  SCIP_PROP* prop, /**< symmetry breaking propagator */
2874  SCIP_Bool* earlyterm /**< pointer to store whether we terminated early (or NULL) */
2875  )
2876 {
2877  SCIP_PROPDATA* propdata;
2878 
2879  assert( prop != NULL );
2880  assert( scip != NULL );
2881 
2882  propdata = SCIPpropGetData(prop);
2883  assert( propdata != NULL );
2884  assert( propdata->symconsenabled );
2885 
2886  /* possibly compute symmetry */
2887  if ( propdata->ofenabled )
2888  {
2889  if ( propdata->symfixnonbinaryvars )
2890  {
2892  }
2893  else
2894  {
2896  }
2897  }
2898  else
2899  {
2901  }
2902  assert( propdata->binvaraffected || ! propdata->symconsenabled );
2903 
2904  /* if constraints have already been added */
2905  if ( propdata->triedaddconss )
2906  {
2907  assert( propdata->nperms > 0 );
2908 
2909  if ( earlyterm != NULL )
2910  *earlyterm = TRUE;
2911 
2912  return SCIP_OKAY;
2913  }
2914 
2915  if ( propdata->nperms <= 0 || ! propdata->symconsenabled )
2916  return SCIP_OKAY;
2917 
2918  assert( propdata->nperms > 0 );
2919  assert( propdata->binvaraffected );
2920  propdata->triedaddconss = TRUE;
2921 
2922  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->genconss, propdata->nperms) );
2923 
2924  if ( propdata->detectorbitopes )
2925  {
2926  SCIP_CALL( detectOrbitopes(scip, propdata, propdata->components, propdata->componentbegins, propdata->ncomponents) );
2927  }
2928 
2929  /* disable orbital fixing if all components are handled by orbitopes */
2930  if ( propdata->ncomponents == propdata->norbitopes )
2931  propdata->ofenabled = FALSE;
2932 
2933  /* possibly stop */
2934  if ( SCIPisStopped(scip) )
2935  {
2936  if ( propdata->ngenconss == 0 )
2937  {
2938  SCIPfreeBlockMemoryArrayNull(scip, &propdata->genconss, propdata->nperms);
2939  }
2940  return SCIP_OKAY;
2941  }
2942 
2943  /* add symmetry breaking constraints if orbital fixing is not used outside orbitopes */
2944  if ( ! propdata->ofenabled )
2945  {
2946  /* exit if no or only trivial symmetry group is available */
2947  if ( propdata->nperms <= 0 || ! propdata->binvaraffected )
2948  return SCIP_OKAY;
2949 
2950  if ( propdata->addsymresacks )
2951  {
2952  SCIP_CALL( addSymresackConss(scip, prop, propdata->components, propdata->componentbegins, propdata->ncomponents) );
2953  }
2954  }
2955 
2956  return SCIP_OKAY;
2957 }
2958 
2959 
2960 
2961 /*
2962  * Local methods for orbital fixing
2963  */
2964 
2965 
2966 /** performs orbital fixing
2967  *
2968  * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
2969  * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
2970  * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
2971  * fixed.
2972  */
2973 static
2975  SCIP* scip, /**< SCIP pointer */
2976  SCIP_VAR** permvars, /**< variables */
2977  int npermvars, /**< number of variables */
2978  int* orbits, /**< array of non-trivial orbits */
2979  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
2980  int norbits, /**< number of orbits */
2981  SCIP_Bool* infeasible, /**< pointer to store whether problem is infeasible */
2982  int* nfixedzero, /**< pointer to store number of variables fixed to 0 */
2983  int* nfixedone /**< pointer to store number of variables fixed to 1 */
2984  )
2985 {
2986  SCIP_Bool tightened;
2987  int i;
2988 
2989  assert( scip != NULL );
2990  assert( permvars != NULL );
2991  assert( orbits != NULL );
2992  assert( orbitbegins != NULL );
2993  assert( infeasible != NULL );
2994  assert( nfixedzero != NULL );
2995  assert( nfixedone != NULL );
2996  assert( norbits > 0 );
2997  assert( orbitbegins[0] == 0 );
2998 
2999  *infeasible = FALSE;
3000  *nfixedzero = 0;
3001  *nfixedone = 0;
3002 
3003  /* check all orbits */
3004  for (i = 0; i < norbits; ++i)
3005  {
3006  SCIP_Bool havefixedone = FALSE;
3007  SCIP_Bool havefixedzero = FALSE;
3008  SCIP_VAR* var;
3009  int j;
3010 
3011  /* we only have nontrivial orbits */
3012  assert( orbitbegins[i+1] - orbitbegins[i] >= 2 );
3013 
3014  /* check all variables in the orbit */
3015  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3016  {
3017  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3018  var = permvars[orbits[j]];
3019  assert( var != NULL );
3020 
3021  /* check whether variable is not binary (and not implicit integer!) */
3022  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3023  {
3024  /* skip orbit if there are non-binary variables */
3025  havefixedone = FALSE;
3026  havefixedzero = FALSE;
3027  break;
3028  }
3029 
3030  /* if variable is fixed to 1 -> can fix all variables in orbit to 1 */
3031  if ( SCIPvarGetLbLocal(var) > 0.5 )
3032  havefixedone = TRUE;
3033 
3034  /* check for zero-fixed variables */
3035  if ( SCIPvarGetUbLocal(var) < 0.5 )
3036  havefixedzero = TRUE;
3037  }
3038 
3039  /* check consistency */
3040  if ( havefixedone && havefixedzero )
3041  {
3042  *infeasible = TRUE;
3043  return SCIP_OKAY;
3044  }
3045 
3046  /* fix all variables to 0 if there is one variable fixed to 0 */
3047  if ( havefixedzero )
3048  {
3049  assert( ! havefixedone );
3050 
3051  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3052  {
3053  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3054  var = permvars[orbits[j]];
3055  assert( var != NULL );
3056 
3057  /* only variables that are not yet fixed to 0 */
3058  if ( SCIPvarGetUbLocal(var) > 0.5 )
3059  {
3060  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 0.\n", SCIPvarGetName(var), orbits[j]);
3061  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
3062  /* due to aggregation, var might already be fixed to 1, so do not put assert here */
3063 
3064  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
3065  SCIP_CALL( SCIPtightenVarUb(scip, var, 0.0, FALSE, infeasible, &tightened) );
3066  if ( *infeasible )
3067  return SCIP_OKAY;
3068  if ( tightened )
3069  ++(*nfixedzero);
3070  }
3071  }
3072  }
3073 
3074  /* fix all variables to 1 if there is one variable fixed to 1 */
3075  if ( havefixedone )
3076  {
3077  assert( ! havefixedzero );
3078 
3079  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3080  {
3081  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3082  var = permvars[orbits[j]];
3083  assert( var != NULL );
3084 
3085  /* only variables that are not yet fixed to 1 */
3086  if ( SCIPvarGetLbLocal(var) < 0.5)
3087  {
3088  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 1.\n", SCIPvarGetName(var), orbits[j]);
3089  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
3090  /* due to aggregation, var might already be fixed to 0, so do not put assert here */
3091 
3092  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
3093  SCIP_CALL( SCIPtightenVarLb(scip, var, 1.0, FALSE, infeasible, &tightened) );
3094  if ( *infeasible )
3095  return SCIP_OKAY;
3096  if ( tightened )
3097  ++(*nfixedone);
3098  }
3099  }
3100  }
3101  }
3102 
3103  return SCIP_OKAY;
3104 }
3105 
3106 
3107 /** Gets branching variables on the path to root
3108  *
3109  * The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
3110  */
3111 static
3113  SCIP* scip, /**< SCIP pointer */
3114  int nvars, /**< number of variables */
3115  SCIP_HASHMAP* varmap, /**< map of variables to indices in vars array */
3116  SCIP_Shortbool* bg1, /**< bitset marking the variables globally fixed or branched to 1 */
3117  int* bg1list, /**< array to store the variable indices globally fixed or branched to 1 */
3118  int* nbg1 /**< pointer to store the number of variables in bg1 and bg1list */
3119  )
3120 {
3121  SCIP_NODE* node;
3122 
3123  assert( scip != NULL );
3124  assert( varmap != NULL );
3125  assert( bg1 != NULL );
3126  assert( bg1list != NULL );
3127  assert( nbg1 != NULL );
3128  assert( *nbg1 >= 0 );
3129 
3130  /* get current node */
3131  node = SCIPgetCurrentNode(scip);
3132 
3133 #ifdef SCIP_OUTPUT
3134  SCIP_CALL( SCIPprintNodeRootPath(scip, node, NULL) );
3135 #endif
3136 
3137  /* follow path to the root (in the root no domains were changed due to branching) */
3138  while ( SCIPnodeGetDepth(node) != 0 )
3139  {
3140  SCIP_BOUNDCHG* boundchg;
3141  SCIP_DOMCHG* domchg;
3142  SCIP_VAR* branchvar;
3143  int nboundchgs;
3144  int i;
3145 
3146  /* get domain changes of current node */
3147  domchg = SCIPnodeGetDomchg(node);
3148 
3149  /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
3150  * cases domchg should not be NULL. */
3151  if ( domchg != NULL )
3152  {
3153  /* loop through all bound changes */
3154  nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
3155  for (i = 0; i < nboundchgs; ++i)
3156  {
3157  /* get bound change info */
3158  boundchg = SCIPdomchgGetBoundchg(domchg, i);
3159  assert( boundchg != NULL );
3160 
3161  /* branching decisions have to be in the beginning of the bound change array */
3163  break;
3164 
3165  /* get corresponding branching variable */
3166  branchvar = SCIPboundchgGetVar(boundchg);
3167 
3168  /* we only consider binary variables */
3169  if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
3170  {
3171  /* if branching variable is not known (may have been created meanwhile,
3172  * e.g., by prop_inttobinary; may have been removed from symmetry data
3173  * due to compression), continue with parent node */
3174  if ( ! SCIPhashmapExists(varmap, (void*) branchvar) )
3175  break;
3176 
3177  if ( SCIPvarGetLbLocal(branchvar) > 0.5 )
3178  {
3179  int branchvaridx;
3180 
3181  branchvaridx = SCIPhashmapGetImageInt(varmap, (void*) branchvar);
3182  assert( branchvaridx < nvars );
3183 
3184  /* the variable might already be fixed to 1 */
3185  if ( ! bg1[branchvaridx] )
3186  {
3187  bg1[branchvaridx] = TRUE;
3188  bg1list[(*nbg1)++] = branchvaridx;
3189  }
3190  }
3191  }
3192  }
3193  }
3194 
3195  node = SCIPnodeGetParent(node);
3196  }
3197 
3198  return SCIP_OKAY;
3199 }
3200 
3201 
3202 /** propagates orbital fixing */
3203 static
3205  SCIP* scip, /**< SCIP pointer */
3206  SCIP_PROPDATA* propdata, /**< data of symmetry breaking propagator */
3207  SCIP_Bool* infeasible, /**< pointer to store whether the node is detected to be infeasible */
3208  int* nprop /**< pointer to store the number of propagations */
3209  )
3210 {
3211  SCIP_Shortbool* inactiveperms;
3212  SCIP_Shortbool* bg0;
3213  SCIP_Shortbool* bg1;
3214  SCIP_VAR** permvars;
3215  int* orbitbegins;
3216  int* orbits;
3217  int* components;
3218  int* componentbegins;
3219  int* vartocomponent;
3220  int ncomponents;
3221  int* bg0list;
3222  int nbg0;
3223  int* bg1list;
3224  int nbg1;
3225  int nactiveperms;
3226  int norbits;
3227  int npermvars;
3228  int nbinpermvars;
3229  int** permstrans;
3230  int nperms;
3231  int p;
3232  int v;
3233  int j;
3234  int componentidx;
3235 
3236  assert( scip != NULL );
3237  assert( propdata != NULL );
3238  assert( propdata->ofenabled );
3239  assert( infeasible != NULL );
3240  assert( nprop != NULL );
3241 
3242  *infeasible = FALSE;
3243  *nprop = 0;
3244 
3245  /* possibly compute symmetry */
3246  if ( propdata->symfixnonbinaryvars )
3247  {
3249  }
3250  else
3251  {
3253  }
3254  assert( propdata->binvaraffected || ! propdata->ofenabled );
3255 
3256  /* return if there is no symmetry available */
3257  nperms = propdata->nperms;
3258  if ( nperms <= 0 || ! propdata->ofenabled )
3259  return SCIP_OKAY;
3260 
3261  assert( propdata->permvars != NULL );
3262  assert( propdata->npermvars > 0 );
3263  assert( propdata->permvarmap != NULL );
3264  assert( propdata->permstrans != NULL );
3265  assert( propdata->inactiveperms != NULL );
3266  assert( propdata->components != NULL );
3267  assert( propdata->componentbegins != NULL );
3268  assert( propdata->vartocomponent != NULL );
3269  assert( propdata->ncomponents > 0 );
3270 
3271  permvars = propdata->permvars;
3272  npermvars = propdata->npermvars;
3273  nbinpermvars = propdata->nbinpermvars;
3274  permstrans = propdata->permstrans;
3275  inactiveperms = propdata->inactiveperms;
3276  components = propdata->components;
3277  componentbegins = propdata->componentbegins;
3278  vartocomponent = propdata->vartocomponent;
3279  ncomponents = propdata->ncomponents;
3280 
3281  /* init bitset for marking variables (globally fixed or) branched to 1 */
3282  assert( propdata->bg1 != NULL );
3283  assert( propdata->bg1list != NULL );
3284  assert( propdata->nbg1 >= 0 );
3285  assert( propdata->nbg1 <= npermvars );
3286 
3287  bg1 = propdata->bg1;
3288  bg1list = propdata->bg1list;
3289  nbg1 = propdata->nbg1;
3290 
3291  /* get branching variables */
3292  SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, bg1, bg1list, &nbg1) );
3293  assert( nbg1 >= propdata->nbg1 );
3294 
3295  /* reset inactive permutations */
3296  nactiveperms = nperms;
3297  for (p = 0; p < nperms; ++p)
3298  propdata->inactiveperms[p] = FALSE;
3299 
3300  /* get pointers for bg0 */
3301  assert( propdata->bg0 != NULL );
3302  assert( propdata->bg0list != NULL );
3303  assert( propdata->nbg0 >= 0 );
3304  assert( propdata->nbg0 <= npermvars );
3305 
3306  bg0 = propdata->bg0;
3307  bg0list = propdata->bg0list;
3308  nbg0 = propdata->nbg0;
3309 
3310  /* filter out permutations that move variables that are fixed to 0 */
3311  for (j = 0; j < nbg0 && nactiveperms > 0; ++j)
3312  {
3313  int* pt;
3314 
3315  v = bg0list[j];
3316  assert( 0 <= v && v < npermvars );
3317  assert( bg0[v] );
3318 
3319  componentidx = vartocomponent[v];
3320 
3321  /* skip unaffected variables and blocked components */
3322  if ( componentidx < 0 || propdata->componentblocked[componentidx] )
3323  continue;
3324 
3325  pt = permstrans[v];
3326  assert( pt != NULL );
3327 
3328  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
3329  {
3330  int img;
3331  int perm;
3332 
3333  perm = components[p];
3334 
3335  /* skip inactive permutations */
3336  if ( inactiveperms[perm] )
3337  continue;
3338 
3339  img = pt[perm];
3340 
3341  if ( img != v )
3342  {
3343 #ifndef NDEBUG
3344  SCIP_VAR* varv = permvars[v];
3345  SCIP_VAR* varimg = permvars[img];
3346 
3347  /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
3348  assert( SCIPvarGetType(varv) == SCIPvarGetType(varimg) ||
3349  (SCIPvarIsBinary(varv) && SCIPvarIsBinary(varimg)) ||
3351  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3352  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) ||
3354  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3355  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) );
3356  assert( SCIPisEQ(scip, propdata->permvarsobj[v], propdata->permvarsobj[img]) );
3357 #endif
3358 
3359  /* we are moving a variable globally fixed to 0 to a variable not of this type */
3360  if ( ! bg0[img] )
3361  {
3362  inactiveperms[perm] = TRUE; /* mark as inactive */
3363  --nactiveperms;
3364  }
3365  }
3366  }
3367  }
3368 
3369  /* filter out permutations that move variables that are fixed to different values */
3370  for (j = 0; j < nbg1 && nactiveperms > 0; ++j)
3371  {
3372  int* pt;
3373 
3374  v = bg1list[j];
3375  assert( 0 <= v && v < npermvars );
3376  assert( bg1[v] );
3377 
3378  componentidx = vartocomponent[v];
3379 
3380  /* skip unaffected variables and blocked components */
3381  if ( componentidx < 0 || propdata->componentblocked[componentidx] )
3382  continue;
3383 
3384  pt = permstrans[v];
3385  assert( pt != NULL );
3386 
3387  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
3388  {
3389  int img;
3390  int perm;
3391 
3392  perm = components[p];
3393 
3394  /* skip inactive permutations */
3395  if ( inactiveperms[perm] )
3396  continue;
3397 
3398  img = pt[perm];
3399 
3400  if ( img != v )
3401  {
3402 #ifndef NDEBUG
3403  SCIP_VAR* varv = permvars[v];
3404  SCIP_VAR* varimg = permvars[img];
3405 
3406  /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
3407  assert( SCIPvarGetType(varv) == SCIPvarGetType(varimg) ||
3408  (SCIPvarIsBinary(varv) && SCIPvarIsBinary(varimg)) ||
3410  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3411  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) ||
3413  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3414  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) );
3415  assert( SCIPisEQ(scip, propdata->permvarsobj[v], propdata->permvarsobj[img]) );
3416 #endif
3417 
3418  /* we are moving a variable globally fixed or branched to 1 to a variable not of this type */
3419  if ( ! bg1[img] )
3420  {
3421  inactiveperms[perm] = TRUE; /* mark as inactive */
3422  --nactiveperms;
3423  }
3424  }
3425  }
3426  }
3427 
3428  /* Clean bg1 list - need to do this after the main loop! (Not needed for bg0.)
3429  * Note that variables globally fixed to 1 are not resetted, since the loop starts at propdata->nbg1. */
3430  for (j = propdata->nbg1; j < nbg1; ++j)
3431  bg1[bg1list[j]] = FALSE;
3432 
3433  /* exit if no active permuations left */
3434  if ( nactiveperms == 0 )
3435  return SCIP_OKAY;
3436 
3437  /* compute orbits of binary variables */
3438  SCIP_CALL( SCIPallocBufferArray(scip, &orbits, nbinpermvars) );
3439  SCIP_CALL( SCIPallocBufferArray(scip, &orbitbegins, nbinpermvars) );
3440  SCIP_CALL( SCIPcomputeOrbitsFilterSym(scip, nbinpermvars, permstrans, nperms, inactiveperms,
3441  orbits, orbitbegins, &norbits, components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
3442 
3443  if ( norbits > 0 )
3444  {
3445  int nfixedzero = 0;
3446  int nfixedone = 0;
3447 
3448  SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits (%d active perms).\n", norbits, nactiveperms);
3449  SCIP_CALL( performOrbitalFixing(scip, permvars, nbinpermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
3450 
3451  propdata->nfixedzero += nfixedzero;
3452  propdata->nfixedone += nfixedone;
3453  *nprop = nfixedzero + nfixedone;
3454 
3455  SCIPdebugMsg(scip, "Orbital fixings: %d 0s, %d 1s.\n", nfixedzero, nfixedone);
3456  }
3457 
3458  SCIPfreeBufferArray(scip, &orbitbegins);
3459  SCIPfreeBufferArray(scip, &orbits);
3460 
3461  return SCIP_OKAY;
3462 }
3463 
3464 
3465 
3466 /*
3467  * Callback methods of propagator
3468  */
3469 
3470 /** presolving initialization method of propagator (called when presolving is about to begin) */
3471 static
3472 SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
3473 { /*lint --e{715}*/
3474  SCIP_PROPDATA* propdata;
3475 
3476  assert( scip != NULL );
3477  assert( prop != NULL );
3478 
3479  propdata = SCIPpropGetData(prop);
3480  assert( propdata != NULL );
3481 
3482  /* check whether we should run */
3483  if ( propdata->usesymmetry < 0 )
3484  {
3485  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &propdata->usesymmetry) );
3486 
3487  if ( ISSYMRETOPESACTIVE(propdata->usesymmetry) )
3488  propdata->symconsenabled = TRUE;
3489  else
3490  propdata->symconsenabled = FALSE;
3491 
3492  if ( ISORBITALFIXINGACTIVE(propdata->usesymmetry) )
3493  propdata->ofenabled = TRUE;
3494  else
3495  propdata->ofenabled = FALSE;
3496  }
3497 
3498  /* add symmetry handling constraints if required */
3499  if ( propdata->symconsenabled && propdata->addconsstiming == 0 )
3500  {
3501  SCIPdebugMsg(scip, "Try to add symmetry handling constraints before presolving.");
3502 
3504  }
3505 
3506  return SCIP_OKAY;
3507 }
3508 
3509 
3510 /** presolving deinitialization method of propagator (called after presolving has been finished) */
3511 static
3512 SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
3513 { /*lint --e{715}*/
3514  SCIP_PROPDATA* propdata;
3515 
3516  assert( scip != NULL );
3517  assert( prop != NULL );
3518  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3519 
3520  SCIPdebugMsg(scip, "Exitpre method of propagator <%s> ...\n", PROP_NAME);
3521 
3522  propdata = SCIPpropGetData(prop);
3523  assert( propdata != NULL );
3524  assert( propdata->usesymmetry >= 0 );
3525 
3526  /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
3527  * and even if presolving has been disabled */
3528  if ( propdata->symconsenabled && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
3529  {
3531  }
3532 
3533  return SCIP_OKAY;
3534 }
3535 
3536 
3537 /** presolving method of propagator */
3538 static
3539 SCIP_DECL_PROPPRESOL(propPresolSymmetry)
3540 { /*lint --e{715}*/
3541  SCIP_PROPDATA* propdata;
3542  int i;
3543 
3544  assert( scip != NULL );
3545  assert( prop != NULL );
3546  assert( result != NULL );
3547  assert( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING );
3548 
3549  *result = SCIP_DIDNOTRUN;
3550 
3551  propdata = SCIPpropGetData(prop);
3552  assert( propdata != NULL );
3553  assert( propdata->usesymmetry >= 0 );
3554 
3555  /* possibly create symmetry handling constraints */
3556  if ( propdata->symconsenabled )
3557  {
3558  int noldngenconns;
3559  SCIP_Bool earlyterm = FALSE;
3560 
3561  /* skip presolving if we are not at the end if addconsstiming == 2 */
3562  assert( 0 <= propdata->addconsstiming && propdata->addconsstiming <= 2 );
3563  if ( propdata->addconsstiming > 1 && ! SCIPisPresolveFinished(scip) )
3564  return SCIP_OKAY;
3565 
3566  /* possibly stop */
3567  if ( SCIPisStopped(scip) )
3568  return SCIP_OKAY;
3569 
3570  noldngenconns = propdata->ngenconss;
3571 
3572  SCIP_CALL( tryAddSymmetryHandlingConss(scip, prop, &earlyterm) );
3573 
3574  /* if we actually tried to add symmetry handling constraints */
3575  if ( ! earlyterm )
3576  {
3577  *result = SCIP_DIDNOTFIND;
3578 
3579  /* if symmetry handling constraints have been added, presolve each */
3580  if ( propdata->ngenconss > 0 )
3581  {
3582  /* at this point, the symmetry group should be computed and nontrivial */
3583  assert( propdata->nperms > 0 );
3584  assert( propdata->triedaddconss );
3585 
3586  /* we have added at least one symmetry handling constraints, i.e., we were successful */
3587  *result = SCIP_SUCCESS;
3588 
3589  *naddconss += propdata->ngenconss - noldngenconns;
3590  SCIPdebugMsg(scip, "Added symmetry breaking constraints: %d.\n", propdata->ngenconss - noldngenconns);
3591 
3592  /* if constraints have been added, loop through generated constraints and presolve each */
3593  for (i = 0; i < propdata->ngenconss; ++i)
3594  {
3595  SCIP_CALL( SCIPpresolCons(scip, propdata->genconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
3596  nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
3597  nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
3598 
3599  /* exit if cutoff or unboundedness has been detected */
3600  if ( *result == SCIP_CUTOFF || *result == SCIP_UNBOUNDED )
3601  {
3602  SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genconss[i]));
3603  return SCIP_OKAY;
3604  }
3605  }
3606  SCIPdebugMsg(scip, "Presolved %d generated constraints.\n", propdata->ngenconss);
3607  }
3608  }
3609  }
3610 
3611  /* run OF presolving */
3612  assert( 0 <= propdata->ofsymcomptiming && propdata->ofsymcomptiming <= 2 );
3613  if ( propdata->ofenabled && propdata->performpresolving && propdata->ofsymcomptiming <= 1 )
3614  {
3615  SCIP_Bool infeasible;
3616  int nprop;
3617 
3618  /* if we did not tried to add symmetry handling constraints */
3619  if ( *result == SCIP_DIDNOTRUN )
3620  *result = SCIP_DIDNOTFIND;
3621 
3622  SCIPdebugMsg(scip, "Presolving <%s>.\n", PROP_NAME);
3623 
3624  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
3625 
3626  if ( infeasible )
3627  {
3628  *result = SCIP_CUTOFF;
3629  propdata->offoundreduction = TRUE;
3630  }
3631  else if ( nprop > 0 )
3632  {
3633  *result = SCIP_SUCCESS;
3634  *nfixedvars += nprop;
3635  propdata->offoundreduction = TRUE;
3636  }
3637  }
3638  else if ( propdata->ofenabled && propdata->ofsymcomptiming == 1 )
3639  {
3640  /* otherwise compute symmetry if timing requests it */
3641  if ( propdata->symfixnonbinaryvars )
3642  {
3644  }
3645  else
3646  {
3648  }
3649  assert( propdata->binvaraffected || ! propdata->ofenabled );
3650  }
3651 
3652  return SCIP_OKAY;
3653 }
3654 
3655 
3656 /** execution method of propagator */
3657 static
3658 SCIP_DECL_PROPEXEC(propExecSymmetry)
3659 { /*lint --e{715}*/
3660  SCIP_PROPDATA* propdata;
3661  SCIP_Bool infeasible = FALSE;
3662  SCIP_Longint nodenumber;
3663  int nprop = 0;
3664 
3665  assert( scip != NULL );
3666  assert( result != NULL );
3667 
3668  *result = SCIP_DIDNOTRUN;
3669 
3670  /* do not run if we are in the root or not yet solving */
3672  return SCIP_OKAY;
3673 
3674  /* do nothing if we are in a probing node */
3675  if ( SCIPinProbing(scip) )
3676  return SCIP_OKAY;
3677 
3678  /* do not run again in repropagation, since the path to the root might have changed */
3679  if ( SCIPinRepropagation(scip) )
3680  return SCIP_OKAY;
3681 
3682  /* get data */
3683  propdata = SCIPpropGetData(prop);
3684  assert( propdata != NULL );
3685 
3686  /* if usesymmetry has not been read so far */
3687  if ( propdata->usesymmetry < 0 )
3688  {
3689  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &propdata->usesymmetry) );
3690  if ( ISSYMRETOPESACTIVE(propdata->usesymmetry) )
3691  propdata->symconsenabled = TRUE;
3692  else
3693  propdata->symconsenabled = FALSE;
3694 
3695  if ( ISORBITALFIXINGACTIVE(propdata->usesymmetry) )
3696  propdata->ofenabled = TRUE;
3697  else
3698  propdata->ofenabled = FALSE;
3699  }
3700 
3701  /* do not propagate if orbital fixing is not enabled */
3702  if ( ! propdata->ofenabled )
3703  return SCIP_OKAY;
3704 
3705  /* return if there is no symmetry available */
3706  if ( propdata->nperms == 0 )
3707  return SCIP_OKAY;
3708 
3709  /* return if we already ran in this node */
3710  nodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
3711  if ( nodenumber == propdata->nodenumber )
3712  return SCIP_OKAY;
3713  propdata->nodenumber = nodenumber;
3714 
3715  /* propagate */
3716  *result = SCIP_DIDNOTFIND;
3717 
3718  SCIPdebugMsg(scip, "Propagating <%s>.\n", SCIPpropGetName(prop));
3719 
3720  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
3721 
3722  if ( infeasible )
3723  {
3724  *result = SCIP_CUTOFF;
3725  propdata->offoundreduction = TRUE;
3726  }
3727  else if ( nprop > 0 )
3728  {
3729  *result = SCIP_REDUCEDDOM;
3730  propdata->offoundreduction = TRUE;
3731  }
3732 
3733  return SCIP_OKAY;
3734 }
3735 
3736 
3737 /** deinitialization method of propagator (called before transformed problem is freed) */
3738 static
3739 SCIP_DECL_PROPEXIT(propExitSymmetry)
3740 {
3741  SCIP_PROPDATA* propdata;
3742 
3743  assert( scip != NULL );
3744  assert( prop != NULL );
3745  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3746 
3747  SCIPdebugMsg(scip, "Exiting propagator <%s>.\n", PROP_NAME);
3748 
3749  propdata = SCIPpropGetData(prop);
3750  assert( propdata != NULL );
3751 
3752  SCIP_CALL( freeSymmetryData(scip, propdata) );
3753 
3754  /* reset basic data */
3755  propdata->usesymmetry = -1;
3756  propdata->symconsenabled = FALSE;
3757  propdata->triedaddconss = FALSE;
3758  propdata->nsymresacks = 0;
3759  propdata->norbitopes = 0;
3760  propdata->ofenabled = FALSE;
3761  propdata->lastrestart = 0;
3762  propdata->nfixedzero = 0;
3763  propdata->nfixedone = 0;
3764  propdata->nodenumber = -1;
3765  propdata->offoundreduction = FALSE;
3766 
3767  return SCIP_OKAY;
3768 }
3769 
3770 
3771 /** propagation conflict resolving method of propagator
3772  *
3773  * @todo Implement reverse propagation.
3774  *
3775  * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
3776  * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
3777  * by the permutations which are involved in creating the orbit.
3778  */
3779 static
3780 SCIP_DECL_PROPRESPROP(propRespropSymmetry)
3781 { /*lint --e{715,818}*/
3782  assert( result != NULL );
3783 
3784  *result = SCIP_DIDNOTFIND;
3785 
3786  return SCIP_OKAY;
3787 }
3788 
3789 
3790 /** destructor of propagator to free user data (called when SCIP is exiting) */
3791 static
3792 SCIP_DECL_PROPFREE(propFreeSymmetry)
3793 { /*lint --e{715}*/
3794  SCIP_PROPDATA* propdata;
3795 
3796  assert( scip != NULL );
3797  assert( prop != NULL );
3798  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3799 
3800  SCIPdebugMsg(scip, "Freeing symmetry propagator.\n");
3801 
3802  propdata = SCIPpropGetData(prop);
3803  assert( propdata != NULL );
3804 
3805  SCIPfreeBlockMemory(scip, &propdata);
3806 
3807  return SCIP_OKAY;
3808 }
3809 
3810 
3811 /*
3812  * External methods
3813  */
3814 
3815 /** include symmetry propagator */
3817  SCIP* scip /**< SCIP data structure */
3818  )
3819 {
3820  SCIP_TABLEDATA* tabledata;
3821  SCIP_PROPDATA* propdata = NULL;
3822  SCIP_PROP* prop = NULL;
3823 
3824  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3825  assert( propdata != NULL );
3826 
3827  propdata->npermvars = 0;
3828  propdata->nbinpermvars = 0;
3829  propdata->permvars = NULL;
3830 #ifndef NDEBUG
3831  propdata->permvarsobj = NULL;
3832 #endif
3833  propdata->nperms = -1;
3834  propdata->nmaxperms = 0;
3835  propdata->perms = NULL;
3836  propdata->permstrans = NULL;
3837  propdata->permvarmap = NULL;
3838 
3839  propdata->ncomponents = -1;
3840  propdata->components = NULL;
3841  propdata->componentbegins = NULL;
3842  propdata->vartocomponent = NULL;
3843  propdata->componentblocked = NULL;
3844 
3845  propdata->log10groupsize = -1.0;
3846  propdata->nmovedvars = -1;
3847  propdata->binvaraffected = FALSE;
3848  propdata->computedsymmetry = FALSE;
3849 
3850  propdata->usesymmetry = -1;
3851  propdata->symconsenabled = FALSE;
3852  propdata->triedaddconss = FALSE;
3853  propdata->genconss = NULL;
3854  propdata->ngenconss = 0;
3855  propdata->nsymresacks = 0;
3856  propdata->norbitopes = 0;
3857 
3858  propdata->ofenabled = FALSE;
3859  propdata->bg0 = NULL;
3860  propdata->bg0list = NULL;
3861  propdata->nbg0 = 0;
3862  propdata->bg1 = NULL;
3863  propdata->bg1list = NULL;
3864  propdata->nbg1 = 0;
3865  propdata->permvarsevents = NULL;
3866  propdata->inactiveperms = NULL;
3867  propdata->nmovedpermvars = 0;
3868  propdata->lastrestart = 0;
3869  propdata->nfixedzero = 0;
3870  propdata->nfixedone = 0;
3871  propdata->nodenumber = -1;
3872  propdata->offoundreduction = FALSE;
3873 
3874  /* create event handler */
3875  propdata->eventhdlr = NULL;
3877  eventExecSymmetry, NULL) );
3878  assert( propdata->eventhdlr != NULL );
3879 
3880  /* include constraint handler */
3882  PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecSymmetry, propdata) );
3883  assert( prop != NULL );
3884 
3885  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSymmetry) );
3886  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitSymmetry) );
3887  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreSymmetry) );
3888  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreSymmetry) );
3889  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropSymmetry) );
3891 
3892  /* include table */
3893  SCIP_CALL( SCIPallocBlockMemory(scip, &tabledata) );
3894  tabledata->propdata = propdata;
3896  NULL, tableFreeOrbitalfixing, NULL, NULL, NULL, NULL, tableOutputOrbitalfixing,
3898 
3899  /* add parameters for computing symmetry */
3900  SCIP_CALL( SCIPaddIntParam(scip,
3901  "propagating/" PROP_NAME "/maxgenerators",
3902  "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
3903  &propdata->maxgenerators, TRUE, DEFAULT_MAXGENERATORS, 0, INT_MAX, NULL, NULL) );
3904 
3906  "propagating/" PROP_NAME "/checksymmetries",
3907  "Should all symmetries be checked after computation?",
3908  &propdata->checksymmetries, TRUE, DEFAULT_CHECKSYMMETRIES, NULL, NULL) );
3909 
3911  "propagating/" PROP_NAME "/displaynorbitvars",
3912  "Should the number of variables affected by some symmetry be displayed?",
3913  &propdata->displaynorbitvars, TRUE, DEFAULT_DISPLAYNORBITVARS, NULL, NULL) );
3914 
3916  "propagating/" PROP_NAME "/doubleequations",
3917  "Double equations to positive/negative version?",
3918  &propdata->doubleequations, TRUE, DEFAULT_DOUBLEEQUATIONS, NULL, NULL) );
3919 
3920  /* add parameters for adding symmetry handling constraints */
3922  "propagating/" PROP_NAME "/conssaddlp",
3923  "Should the symmetry breaking constraints be added to the LP?",
3924  &propdata->conssaddlp, TRUE, DEFAULT_CONSSADDLP, NULL, NULL) );
3925 
3927  "propagating/" PROP_NAME "/addsymresacks",
3928  "Add inequalities for symresacks for each generator?",
3929  &propdata->addsymresacks, TRUE, DEFAULT_ADDSYMRESACKS, NULL, NULL) );
3930 
3932  "propagating/" PROP_NAME "/detectorbitopes",
3933  "Should we check whether the components of the symmetry group can be handled by orbitopes?",
3934  &propdata->detectorbitopes, TRUE, DEFAULT_DETECTORBITOPES, NULL, NULL) );
3935 
3936  SCIP_CALL( SCIPaddIntParam(scip,
3937  "propagating/" PROP_NAME "/addconsstiming",
3938  "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
3939  &propdata->addconsstiming, TRUE, DEFAULT_ADDCONSSTIMING, 0, 2, NULL, NULL) );
3940 
3941  /* add parameters for orbital fixing */
3942  SCIP_CALL( SCIPaddIntParam(scip,
3943  "propagating/" PROP_NAME "/ofsymcomptiming",
3944  "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
3945  &propdata->ofsymcomptiming, TRUE, DEFAULT_OFSYMCOMPTIMING, 0, 2, NULL, NULL) );
3946 
3948  "propagating/" PROP_NAME "/performpresolving",
3949  "run orbital fixing during presolving?",
3950  &propdata->performpresolving, TRUE, DEFAULT_PERFORMPRESOLVING, NULL, NULL) );
3951 
3953  "propagating/" PROP_NAME "/recomputerestart",
3954  "recompute symmetries after a restart has occured?",
3955  &propdata->recomputerestart, TRUE, DEFAULT_RECOMPUTERESTART, NULL, NULL) );
3956 
3958  "propagating/" PROP_NAME "/compresssymmetries",
3959  "Should non-affected variables be removed from permutation to save memory?",
3960  &propdata->compresssymmetries, TRUE, DEFAULT_COMPRESSSYMMETRIES, NULL, NULL) );
3961 
3963  "propagating/" PROP_NAME "/compressthreshold",
3964  "Compression is used if percentage of moved vars is at most the threshold.",
3965  &propdata->compressthreshold, TRUE, DEFAULT_COMPRESSTHRESHOLD, 0.0, 1.0, NULL, NULL) );
3966 
3968  "propagating/" PROP_NAME "/usecolumnsparsity",
3969  "Should the number of conss a variable is contained in be exploited in symmetry detection?",
3970  &propdata->usecolumnsparsity, TRUE, DEFAULT_USECOLUMNSPARSITY, NULL, NULL) );
3971 
3973  "propagating/" PROP_NAME "/disableofrestart",
3974  "Shall orbital fixing be disabled if orbital fixing has found a reduction and a restart occurs?",
3975  &propdata->disableofrestart, TRUE, DEFAULT_DISABLEOFRESTART, NULL, NULL) );
3976 
3978  "propagating/" PROP_NAME "/symfixnonbinaryvars",
3979  "Whether all non-binary variables shall be not affected by symmetries if OF is active?",
3980  &propdata->symfixnonbinaryvars, TRUE, DEFAULT_SYMFIXNONBINARYVARS, NULL, NULL) );
3981 
3982  /* possibly add description */
3983  if ( SYMcanComputeSymmetry() )
3984  {
3986  }
3987 
3988  return SCIP_OKAY;
3989 }
3990 
3991 
3992 /** return currently available symmetry group information */
3994  SCIP* scip, /**< SCIP data structure */
3995  int* npermvars, /**< pointer to store number of variables for permutations */
3996  SCIP_VAR*** permvars, /**< pointer to store variables on which permutations act */
3997  SCIP_HASHMAP** permvarmap, /**< pointer to store hash map of permvars (or NULL) */
3998  int* nperms, /**< pointer to store number of permutations */
3999  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
4000  int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
4001  SCIP_Real* log10groupsize, /**< pointer to store log10 of group size (or NULL) */
4002  SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected */
4003  int** components, /**< pointer to store components of symmetry group (or NULL) */
4004  int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
4005  int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
4006  int* ncomponents /**< pointer to store number of components (or NULL) */
4007  )
4008 {
4009  SCIP_PROPDATA* propdata;
4010  SCIP_PROP* prop;
4011 
4012  assert( scip != NULL );
4013  assert( npermvars != NULL );
4014  assert( permvars != NULL );
4015  assert( nperms != NULL );
4016  assert( perms != NULL || permstrans != NULL );
4017  assert( ncomponents != NULL || (components == NULL && componentbegins == NULL && vartocomponent == NULL) );
4018 
4019  /* find symmetry propagator */
4020  prop = SCIPfindProp(scip, "symmetry");
4021  if ( prop == NULL )
4022  {
4023  SCIPerrorMessage("Could not find symmetry propagator.\n");
4024  return SCIP_PLUGINNOTFOUND;
4025  }
4026  assert( prop != NULL );
4027  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
4028 
4029  propdata = SCIPpropGetData(prop);
4030  assert( propdata != NULL );
4031 
4032  *npermvars = propdata->npermvars;
4033  *permvars = propdata->permvars;
4034 
4035  if ( permvarmap != NULL )
4036  *permvarmap = propdata->permvarmap;
4037 
4038  *nperms = propdata->nperms;
4039  if ( perms != NULL )
4040  {
4041  *perms = propdata->perms;
4042  assert( *perms != NULL || *nperms <= 0 );
4043  }
4044 
4045  if ( permstrans != NULL )
4046  {
4047  *permstrans = propdata->permstrans;
4048  assert( *permstrans != NULL || *nperms <= 0 );
4049  }
4050 
4051  if ( log10groupsize != NULL )
4052  *log10groupsize = propdata->log10groupsize;
4053 
4054  if ( binvaraffected != NULL )
4055  *binvaraffected = propdata->binvaraffected;
4056 
4057  if ( components != NULL )
4058  *components = propdata->components;
4059 
4060  if ( componentbegins != NULL )
4061  *componentbegins = propdata->componentbegins;
4062 
4063  if ( vartocomponent )
4064  *vartocomponent = propdata->vartocomponent;
4065 
4066  if ( ncomponents )
4067  *ncomponents = propdata->ncomponents;
4068 
4069  return SCIP_OKAY;
4070 }
4071 
4072 /** return whether orbital fixing is enabled */
4074  SCIP* scip /**< SCIP data structure */
4075  )
4076 {
4077  SCIP_PROP* prop;
4078  SCIP_PROPDATA* propdata;
4079 
4080  assert( scip != NULL );
4081 
4082  prop = SCIPfindProp(scip, PROP_NAME);
4083  if ( prop == NULL )
4084  return FALSE;
4085 
4086  propdata = SCIPpropGetData(prop);
4087  assert( propdata != NULL );
4088 
4089  return propdata->ofenabled;
4090 }
4091 
4092 /** return number of the symmetry group's generators */
4094  SCIP* scip /**< SCIP data structure */
4095  )
4096 {
4097  SCIP_PROP* prop;
4098  SCIP_PROPDATA* propdata;
4099 
4100  assert( scip != NULL );
4101 
4102  prop = SCIPfindProp(scip, PROP_NAME);
4103  if ( prop == NULL )
4104  return 0;
4105 
4106  propdata = SCIPpropGetData(prop);
4107  assert( propdata != NULL );
4108 
4109  if ( propdata->nperms < 0 )
4110  return 0;
4111  else
4112  return propdata->nperms;
4113 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:47
SCIP_VAR * SCIPgetIntVarXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5962
#define DEFAULT_COMPRESSTHRESHOLD
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:497
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_Real * matcoef
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2215
SCIP_VAR ** SCIPgetVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2192
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:238
#define DEFAULT_CHECKSYMMETRIES
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Bool *success)
Constraint handler for variable bound constraints .
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5177
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents)
static SCIP_DECL_EVENTEXEC(eventExecSymmetry)
static SCIP_DECL_PROPPRESOL(propPresolSymmetry)
#define DEFAULT_CONSSADDLP
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:467
static SCIP_DECL_PROPEXEC(propExecSymmetry)
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5160
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3474
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2599
#define SCIP_MAXSTRLEN
Definition: def.h:279
SCIP_RETCODE SCIPgetSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5294
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7438
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
#define PROP_TIMING
static SCIP_DECL_PROPRESPROP(propRespropSymmetry)
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
#define DEFAULT_DISPLAYNORBITVARS
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8138
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
SCIP_EXPORT int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition: var.c:16964
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7448
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3082
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPgetSymmetryNGenerators(SCIP *scip)
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:66
#define DEFAULT_RECOMPUTERESTART
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9273
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2121
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:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
Constraint handler for AND constraints, .
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:478
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT const char * SYMsymmetryGetName(void)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:136
static int getNSymhandableConss(SCIP *scip)
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** permvars
SCIP_EXPORT SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7718
SCIP_VAR ** SCIPgetVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5939
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
#define SCIPdebugMsg
Definition: scip_message.h:69
#define TABLE_DESC_ORBITALFIXING
static SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, SCIP_Shortbool *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:152
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5185
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2076
#define DEFAULT_COMPRESSSYMMETRIES
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:2236
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2837
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
interface for symmetry computations
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
constraint handler for symresack constraints
Constraint handler for "or" constraints, .
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
#define SYM_SPEC_BINARY
Definition: type_symmetry.h:34
SCIP_EXPORT SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8643
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Real ub
#define TABLE_EARLIEST_ORBITALFIXING
SCIP_EXPORT SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:16972
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:1735
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7533
int SCIPgetNVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2169
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
#define ISORBITALFIXINGACTIVE(x)
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:514
SYM_RHSSENSE * rhssense
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_Bool SCIPisOrbitalfixingEnabled(SCIP *scip)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *bg1, int *bg1list, int *nbg1)
SCIP_EXPORT SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16934
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
#define SYM_SPEC_INTEGER
Definition: type_symmetry.h:33
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
Definition: scip_general.c:596
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:254
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:534
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SYM_RHSSENSE * senses
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
Definition: symmetry.c:852
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
#define DEFAULT_PERFORMPRESOLVING
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_PROPEXIT(propExitSymmetry)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPgetNActiveConss(SCIP *scip)
#define PROP_PRESOL_MAXROUNDS
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
SCIP_RETCODE SCIPgetPropertiesPerm(int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
Definition: symmetry.c:424
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2303
#define DEFAULT_ADDSYMRESACKS
internal miscellaneous methods
#define PROP_PRESOL_PRIORITY
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_Shortbool
Definition: def.h:78
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:697
#define EVENTHDLR_SYMMETRY_NAME
static SCIP_DECL_HASHKEYEQ(SYMhashKeyEQVartype)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIP_PROPTIMING_ALWAYS
Definition: type_timing.h:64
#define PROP_FREQ
#define SCIP_CALL(x)
Definition: def.h:370
#define TABLE_POSITION_ORBITALFIXING
#define DEFAULT_OFSYMCOMPTIMING
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
#define SCIP_SPECIALVAL
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1233
propagator for symmetry handling
Definition: grphload.c:88
SCIP_Real * vals
SCIP_Bool SCIPconsIsConflict(SCIP_CONS *cons)
Definition: cons.c:8226
static SCIP_RETCODE delSymConss(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
#define TABLE_NAME_ORBITALFIXING
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_Bool SYMcanComputeSymmetry(void)
constraint handler for linking binary variables to a linking (continuous or integer) variable ...
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1209
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
static SCIP_RETCODE setSymmetryData(SCIP *scip, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
uint32_t SYM_SPEC
Definition: type_symmetry.h:37
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:530
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
#define MAX(x, y)
Definition: tclique_def.h:83
int SCIPgetNActiveBenders(SCIP *scip)
Definition: scip_benders.c:523
SCIP_EXPORT SCIP_TABLEDATA * SCIPtableGetData(SCIP_TABLE *table)
Definition: table.c:279
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:320
SCIP_Real lb
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5440
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8386
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5136
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4616
SCIP_VARTYPE type
static SCIP_RETCODE tryAddSymmetryHandlingConss(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *earlyterm)
Constraint handler for linear constraints in their most general form, .
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
#define DEFAULT_MAXGENERATORS
#define PROP_NAME
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:190
enum SYM_Rhssense SYM_RHSSENSE
Definition: type_symmetry.h:51
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
#define COMPRESSNVARSLB
Constraint handler for XOR constraints, .
#define DEFAULT_DOUBLEEQUATIONS
#define PROP_PRIORITY
#define DEFAULT_DISABLEOFRESTART
#define PROP_DELAY
#define PROP_DESC
static const SCIP_Real scalars[]
Definition: lp.c:5731
methods for handling symmetries
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPgetRhsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5985
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_EXPORT const char * SYMsymmetryGetDesc(void)
#define MAXGENNUMERATOR
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SYM_SPEC_REAL
Definition: type_symmetry.h:35
#define ISSYMRETOPESACTIVE(x)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10604
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9250
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:74
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8077
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define SCIP_Real
Definition: def.h:163
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8097
#define DEFAULT_SYMFIXNONBINARYVARS
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
SCIP_EXPORT SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12545
#define SCIP_INVALID
Definition: def.h:183
#define DEFAULT_ADDCONSSTIMING
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, SCIP_Shortbool **componentblocked, int *ncomponents)
Definition: symmetry.c:651
#define SCIP_Longint
Definition: def.h:148
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4167
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
static SCIP_RETCODE performOrbitalFixing(SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone)
static SCIP_RETCODE collectCoefficients(SCIP *scip, SCIP_Bool doubleequations, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata, int *nconssforvar)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9296
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1044
SCIP_EXPORT SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16924
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
#define EVENTHDLR_SYMMETRY_DESC
#define PROP_PRESOLTIMING
static SCIP_DECL_SORTINDCOMP(SYMsortRhsTypes)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:67
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
constraint handler for bound disjunction constraints
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
int SCIPgetNVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5916
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIPABORT()
Definition: def.h:342
SCIP_Real obj
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * rhscoef
static SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
#define DEFAULT_USECOLUMNSPARSITY
#define DEFAULT_DETECTORBITOPES
SCIP_RETCODE SCIPpresolCons(SCIP *scip, SCIP_CONS *cons, int nrounds, SCIP_PRESOLTIMING presoltiming, int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, int *nfixedvars, int *naggrvars, int *nchgvartypes, int *nchgbds, int *naddholes, int *ndelconss, int *naddconss, int *nupgdconss, int *nchgcoefs, int *nchgsides, SCIP_RESULT *result)
Definition: scip_cons.c:2343
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
struct SCIP_TableData SCIP_TABLEDATA
Definition: type_table.h:49
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
int SCIPgetNRuns(SCIP *scip)
static SCIP_DECL_PROPFREE(propFreeSymmetry)