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-2020 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  /* skip symmetry computation if no graph automorphism code was linked */
2137  if ( ! SYMcanComputeSymmetry() )
2138  {
2139  propdata->ofenabled = FALSE;
2140  propdata->symconsenabled = FALSE;
2141 
2142  nconss = SCIPgetNActiveConss(scip);
2143  nhandleconss = getNSymhandableConss(scip);
2144 
2145  /* print verbMessage only if problem consists of symmetry handable constraints */
2146  assert( nhandleconss <= nconss );
2147  if ( nhandleconss < nconss )
2148  return SCIP_OKAY;
2149 
2151  " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2152 
2153  return SCIP_OKAY;
2154  }
2155 
2156  /* do not compute symmetry if there are active pricers */
2157  if ( SCIPgetNActivePricers(scip) > 0 )
2158  {
2159  propdata->ofenabled = FALSE;
2160  propdata->symconsenabled = FALSE;
2161  return SCIP_OKAY;
2162  }
2163 
2164  /* avoid trivial cases */
2165  nvars = SCIPgetNVars(scip);
2166  if ( nvars <= 0 )
2167  {
2168  propdata->ofenabled = FALSE;
2169  propdata->symconsenabled = FALSE;
2170 
2171  return SCIP_OKAY;
2172  }
2173 
2174  /* do not compute symmetry if there are no binary variables */
2175  if ( SCIPgetNBinVars(scip) == 0 )
2176  {
2177  propdata->ofenabled = FALSE;
2178  propdata->symconsenabled = FALSE;
2179 
2180  return SCIP_OKAY;
2181  }
2182 
2183  /* determine symmetry specification */
2184  if ( SCIPgetNBinVars(scip) > 0 )
2185  type |= (int) SYM_SPEC_BINARY;
2186  if ( SCIPgetNIntVars(scip) > 0 )
2187  type |= (int) SYM_SPEC_INTEGER;
2188  /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2189  if ( SCIPgetNContVars(scip) > 0 || SCIPgetNImplVars(scip) > 0 )
2190  type |= (int) SYM_SPEC_REAL;
2191 
2192  /* skip symmetry computation if required variables are not present */
2193  if ( ! (type & symspecrequire) )
2194  {
2196  " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2197  SCIPgetSolvingTime(scip),
2198  SCIPgetNBinVars(scip) > 0 ? '+' : '-',
2199  SCIPgetNIntVars(scip) > 0 ? '+' : '-',
2200  SCIPgetNContVars(scip) + SCIPgetNImplVars(scip) > 0 ? '+' : '-',
2201  (symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2202  (symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2203  (symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
2204 
2205  propdata->ofenabled = FALSE;
2206  propdata->symconsenabled = FALSE;
2207 
2208  return SCIP_OKAY;
2209  }
2210 
2211  /* if a restart occured, either disable orbital fixing... */
2212  if ( propdata->offoundreduction && propdata->disableofrestart && SCIPgetNRuns(scip) > propdata->lastrestart )
2213  propdata->ofenabled = FALSE;
2214  /* ... or free symmetries after a restart to recompute them later */
2215  else if ( (propdata->offoundreduction || propdata->recomputerestart)
2216  && propdata->nperms > 0 && SCIPgetNRuns(scip) > propdata->lastrestart )
2217  {
2218  assert( propdata->npermvars > 0 );
2219  assert( propdata->permvars != NULL );
2220  assert( ! propdata->ofenabled || propdata->permvarmap != NULL );
2221  assert( ! propdata->ofenabled || propdata->bg0list != NULL );
2222 
2223  /* reset symmetry information */
2224  SCIP_CALL( delSymConss(scip, propdata) );
2225  SCIP_CALL( freeSymmetryData(scip, propdata) );
2226  }
2227 
2228  /* skip computation if symmetry has already been computed */
2229  if ( propdata->computedsymmetry )
2230  return SCIP_OKAY;
2231 
2232  /* skip symmetry computation if there are constraints that cannot be handled by symmetry */
2233  nconss = SCIPgetNActiveConss(scip);
2234  nhandleconss = getNSymhandableConss(scip);
2235  if ( nhandleconss < nconss )
2236  {
2238  " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2239  SCIPgetSolvingTime(scip));
2240 
2241  propdata->ofenabled = FALSE;
2242  propdata->symconsenabled = FALSE;
2243 
2244  return SCIP_OKAY;
2245  }
2246 
2247  assert( propdata->npermvars == 0 );
2248  assert( propdata->permvars == NULL );
2249 #ifndef NDEBUG
2250  assert( propdata->permvarsobj == NULL );
2251 #endif
2252  assert( propdata->nperms < 0 );
2253  assert( propdata->nmaxperms == 0 );
2254  assert( propdata->perms == NULL );
2255 
2256  /* output message */
2258  " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2259  SCIPgetSolvingTime(scip),
2260  (symspecrequire & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2261  (symspecrequire & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2262  (symspecrequire & (int) SYM_SPEC_REAL) != 0 ? '+' : '-',
2263  (symspecrequirefixed & (int) SYM_SPEC_BINARY) != 0 ? '+' : '-',
2264  (symspecrequirefixed & (int) SYM_SPEC_INTEGER) != 0 ? '+' : '-',
2265  (symspecrequirefixed & (int) SYM_SPEC_REAL) != 0 ? '+' : '-');
2266 
2267  /* output warning if we want to fix certain symmetry parts that we also want to compute */
2268  if ( symspecrequire & symspecrequirefixed )
2269  SCIPwarningMessage(scip, "Warning: some required symmetries must be fixed.\n");
2270 
2271  /* determine maximal number of generators depending on the number of variables */
2272  maxgenerators = propdata->maxgenerators;
2273  maxgenerators = MIN(maxgenerators, MAXGENNUMERATOR / nvars);
2274 
2275  /* actually compute (global) symmetry */
2276  SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2277  maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity,
2278  &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2279  &propdata->perms, &propdata->log10groupsize, &propdata->nmovedvars, &propdata->binvaraffected,
2280  &propdata->compressed, &successful) );
2281 
2282  /* mark that we have computed the symmetry group */
2283  propdata->computedsymmetry = TRUE;
2284 
2285  /* store restart level */
2286  propdata->lastrestart = SCIPgetNRuns(scip);
2287 
2288  /* return if not successful */
2289  if ( ! successful )
2290  {
2291  assert( checkSymmetryDataFree(propdata) );
2292  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2293 
2294  propdata->ofenabled = FALSE;
2295  propdata->symconsenabled = FALSE;
2296 
2297  return SCIP_OKAY;
2298  }
2299 
2300  /* return if no symmetries found */
2301  if ( propdata->nperms == 0 )
2302  {
2303  assert( checkSymmetryDataFree(propdata) );
2304  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
2305 
2306  propdata->ofenabled = FALSE;
2307  propdata->symconsenabled = FALSE;
2308 
2309  return SCIP_OKAY;
2310  }
2311 
2312  /* display statistics */
2313  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2314  SCIPgetSolvingTime(scip), propdata->nperms);
2315 
2316  /* display statistics: maximum number of generators */
2317  if ( maxgenerators == 0 )
2319  else
2320  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%u", maxgenerators);
2321 
2322  /* display statistics: log10 group size, number of affected vars*/
2323  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2324 
2325  if ( propdata->displaynorbitvars )
2326  {
2327  if ( propdata->nmovedvars == -1 )
2328  {
2329  SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2330  propdata->npermvars, &(propdata->nmovedvars)) );
2331  }
2332  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2333  }
2334  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ")\n");
2335 
2336  /* exit if no binary variables are affected by symmetry */
2337  if ( ! propdata->binvaraffected )
2338  {
2339  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2340 
2341  /* free data and exit */
2342  SCIP_CALL( freeSymmetryData(scip, propdata) );
2343 
2344  /* disable OF and symmetry handling constraints */
2345  propdata->ofenabled = FALSE;
2346  propdata->symconsenabled = FALSE;
2347 
2348  return SCIP_OKAY;
2349  }
2350 
2351  assert( propdata->nperms > 0 );
2352  assert( propdata->npermvars > 0 );
2353 
2354  /* compute components */
2355  assert( propdata->components == NULL );
2356  assert( propdata->componentbegins == NULL );
2357  assert( propdata->vartocomponent == NULL );
2358 
2359 #ifdef SCIP_OUTPUT_COMPONENT
2360  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2361 #endif
2362 
2363  /* we only need the components for orbital fixing and orbitope detection */
2364  if ( propdata->ofenabled || ( propdata->symconsenabled && propdata->detectorbitopes ) )
2365  {
2366  SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2367  propdata->npermvars, FALSE, &propdata->components, &propdata->componentbegins,
2368  &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
2369  }
2370 
2371 #ifdef SCIP_OUTPUT_COMPONENT
2372  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
2373 #endif
2374 
2375  /* set up data for OF */
2376  if ( propdata->ofenabled )
2377  {
2378  int componentidx;
2379  int v;
2380 
2381  /* transpose symmetries matrix here if necessary */
2382  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permstrans, propdata->npermvars) );
2383  for (v = 0; v < propdata->npermvars; ++v)
2384  {
2385  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->permstrans[v]), propdata->nmaxperms) );
2386  for (p = 0; p < propdata->nperms; ++p)
2387  {
2388  if ( SCIPvarIsBinary(propdata->permvars[v]) )
2389  propdata->permstrans[v][p] = propdata->perms[p][v];
2390  else
2391  propdata->permstrans[v][p] = v; /* ignore symmetry information on non-binary variables */
2392  }
2393  }
2394 
2395  /* prepare array for active permutations */
2396  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inactiveperms, propdata->nperms) );
2397  for (v = 0; v < propdata->nperms; ++v)
2398  propdata->inactiveperms[v] = FALSE;
2399 
2400  /* create hashmap for storing the indices of variables */
2401  assert( propdata->permvarmap == NULL );
2402  SCIP_CALL( SCIPhashmapCreate(&propdata->permvarmap, SCIPblkmem(scip), propdata->npermvars) );
2403 
2404  /* prepare data structures */
2405  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permvarsevents, propdata->npermvars) );
2406  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg0, propdata->npermvars) );
2407  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg0list, propdata->npermvars) );
2408  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg1, propdata->npermvars) );
2409  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bg1list, propdata->npermvars) );
2410 
2411  /* insert variables into hashmap */
2412  for (v = 0; v < propdata->npermvars; ++v)
2413  {
2414  SCIP_CALL( SCIPhashmapInsertInt(propdata->permvarmap, propdata->permvars[v], v) );
2415 
2416  propdata->bg0[v] = FALSE;
2417  propdata->bg1[v] = FALSE;
2418  propdata->permvarsevents[v] = -1;
2419 
2420  /* collect number of moved permvars that are handled by OF */
2421  componentidx = propdata->vartocomponent[v];
2422  if ( componentidx > -1 && ! propdata->componentblocked[componentidx] )
2423  propdata->nmovedpermvars += 1;
2424 
2425  /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
2426  * are not branched on. */
2427  if ( SCIPvarGetType(propdata->permvars[v]) == SCIP_VARTYPE_BINARY )
2428  {
2429  /* catch whether binary variables are globally fixed; also store filter position */
2431  propdata->eventhdlr, (SCIP_EVENTDATA*) propdata, &propdata->permvarsevents[v]) );
2432  }
2433  }
2434  assert( propdata->nbg1 == 0 );
2435  }
2436 
2437 #ifndef NDEBUG
2438  /* store objective coefficients for debug purposes */
2439  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->permvarsobj, propdata->npermvars) );
2440  for (j = 0; j < propdata->npermvars; ++j)
2441  propdata->permvarsobj[j] = SCIPvarGetObj(propdata->permvars[j]);
2442 #endif
2443 
2444  /* capture binary variables and forbid multi-aggregation of symmetric variables
2445  *
2446  * note: binary variables are in the beginning of pervars
2447  */
2448  for (j = 0; j < propdata->nbinpermvars; ++j)
2449  {
2450  SCIP_CALL( SCIPcaptureVar(scip, propdata->permvars[j]) );
2451 
2452  if ( propdata->compressed )
2453  {
2454  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->permvars[j]) );
2455  }
2456  else
2457  {
2458  for (p = 0; p < propdata->nperms; ++p)
2459  {
2460  if ( propdata->perms[p][j] != j )
2461  {
2462  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->permvars[j]) );
2463  break;
2464  }
2465  }
2466  }
2467  }
2468 
2469  /* free original perms matrix if no symmetry constraints are added */
2470  if ( ! propdata->symconsenabled )
2471  {
2472  for (p = 0; p < propdata->nperms; ++p)
2473  {
2474  SCIPfreeBlockMemoryArray(scip, &(propdata->perms)[p], propdata->npermvars);
2475  }
2476  SCIPfreeBlockMemoryArrayNull(scip, &propdata->perms, propdata->nmaxperms);
2477  }
2478 
2479  return SCIP_OKAY;
2480 }
2481 
2482 
2483 
2484 /*
2485  * Functions for symmetry constraints
2486  */
2487 
2488 
2489 /** checks whether components of the symmetry group can be completely handled by orbitopes */
2490 static
2492  SCIP* scip, /**< SCIP instance */
2493  SCIP_PROPDATA* propdata, /**< pointer to data of symmetry propagator */
2494  int* components, /**< array containing components of symmetry group */
2495  int* componentbegins, /**< array containing begin positions of components in components array */
2496  int ncomponents /**< number of components */
2497  )
2498 {
2499  SCIP_VAR** permvars;
2500  int** perms;
2501  int npermvars;
2502  int i;
2503 
2504  assert( scip != NULL );
2505  assert( propdata != NULL );
2506  assert( components != NULL );
2507  assert( componentbegins != NULL );
2508  assert( ncomponents > 0 );
2509  assert( propdata->nperms >= 0 );
2510 
2511  /* exit if no symmetry is present */
2512  if ( propdata->nperms == 0 )
2513  return SCIP_OKAY;
2514 
2515  assert( propdata->nperms > 0 );
2516  assert( propdata->perms != NULL );
2517  assert( propdata->nbinpermvars >= 0 );
2518  assert( propdata->npermvars >= 0 );
2519  assert( propdata->permvars != NULL );
2520 
2521  /* exit if no symmetry on binary variables is present */
2522  if ( propdata->nbinpermvars == 0 )
2523  {
2524  assert( ! propdata->binvaraffected );
2525  return SCIP_OKAY;
2526  }
2527 
2528  perms = propdata->perms;
2529  npermvars = propdata->npermvars;
2530  permvars = propdata->permvars;
2531 
2532  /* iterate over components */
2533  for (i = 0; i < ncomponents; ++i)
2534  {
2535  SCIP_VAR*** vars;
2536  SCIP_VAR*** varsallocorder;
2537  SCIP_CONS* cons;
2538  SCIP_Bool* usedperm;
2539  SCIP_Bool isorbitope = TRUE;
2540  SCIP_Bool infeasibleorbitope;
2541  int** orbitopevaridx;
2542  int* columnorder;
2543  int npermsincomponent;
2544  int ntwocyclescomp = INT_MAX;
2545  int nfilledcols;
2546  int nusedperms;
2547  int* nusedelems;
2548  int coltoextend;
2549  int j;
2550  int row;
2551 
2552  /* get properties of permutations */
2553  npermsincomponent = componentbegins[i + 1] - componentbegins[i];
2554  assert( npermsincomponent > 0 );
2555  for (j = componentbegins[i]; j < componentbegins[i + 1]; ++j)
2556  {
2557  SCIP_Bool iscompoftwocycles = FALSE;
2558  SCIP_Bool allvarsbinary = TRUE;
2559  int ntwocyclesperm = 0;
2560 
2561  SCIP_CALL( SCIPgetPropertiesPerm(perms[components[j]], permvars, npermvars, &iscompoftwocycles, &ntwocyclesperm, &allvarsbinary) );
2562 
2563  /* if we are checking the first permutation */
2564  if ( ntwocyclescomp == INT_MAX )
2565  ntwocyclescomp = ntwocyclesperm;
2566 
2567  /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
2568  if ( ntwocyclescomp == 0 || ntwocyclescomp != ntwocyclesperm || ! allvarsbinary )
2569  {
2570  isorbitope = FALSE;
2571  break;
2572  }
2573  }
2574 
2575  /* if no orbitope was detected */
2576  if ( ! isorbitope )
2577  continue;
2578  assert( ntwocyclescomp > 0 );
2579  assert( ntwocyclescomp < INT_MAX );
2580 
2581  /* iterate over permutations and check whether for each permutation there exists
2582  * another permutation whose 2-cycles intersect pairwise in exactly one element */
2583 
2584  /* whether a permutation was considered to contribute to orbitope */
2585  SCIP_CALL( SCIPallocClearBufferArray(scip, &usedperm, npermsincomponent) );
2586  nusedperms = 0;
2587 
2588  /* orbitope matrix for indices of variables in permvars array */
2589  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx, ntwocyclescomp) );
2590  for (j = 0; j < ntwocyclescomp; ++j)
2591  {
2592  SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
2593  }
2594 
2595  /* order of columns of orbitopevaridx */
2596  SCIP_CALL( SCIPallocBufferArray(scip, &columnorder, npermsincomponent + 1) );
2597  for (j = 0; j < npermsincomponent + 1; ++j)
2598  columnorder[j] = npermsincomponent + 2;
2599 
2600  /* count how often an element was used in the potential orbitope */
2601  SCIP_CALL( SCIPallocClearBufferArray(scip, &nusedelems, npermvars) );
2602 
2603  /* fill first two columns of orbitopevaridx matrix */
2604  row = 0;
2605  for (j = 0; j < npermvars; ++j)
2606  {
2607  int permidx;
2608 
2609  permidx = components[componentbegins[i]];
2610 
2611  /* avoid adding the same 2-cycle twice */
2612  if ( perms[permidx][j] > j )
2613  {
2614  orbitopevaridx[row][0] = j;
2615  orbitopevaridx[row++][1] = perms[permidx][j];
2616  nusedelems[j] += 1;
2617  nusedelems[perms[permidx][j]] += 1;
2618  }
2619 
2620  if ( row == ntwocyclescomp )
2621  break;
2622  }
2623  assert( row == ntwocyclescomp );
2624 
2625  usedperm[0] = TRUE;
2626  ++nusedperms;
2627  columnorder[0] = 0;
2628  columnorder[1] = 1;
2629  nfilledcols = 2;
2630 
2631  /* extend orbitopevaridx matrix to the left, i.e., iteratively find new permutations that
2632  * intersect the last added left column in each row in exactly one entry, starting with
2633  * column 0 */
2634  coltoextend = 0;
2635  for (j = 0; j < npermsincomponent; ++j)
2636  { /* lint --e{850} */
2637  SCIP_Bool success = FALSE;
2638  SCIP_Bool infeasible = FALSE;
2639 
2640  if ( nusedperms == npermsincomponent )
2641  break;
2642 
2643  if ( usedperm[j] )
2644  continue;
2645 
2646  SCIP_CALL( SCIPextendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
2647  perms[components[componentbegins[i] + j]], TRUE, &nusedelems, &success, &infeasible) );
2648 
2649  if ( infeasible )
2650  {
2651  isorbitope = FALSE;
2652  break;
2653  }
2654  else if ( success )
2655  {
2656  usedperm[j] = TRUE;
2657  ++nusedperms;
2658  coltoextend = nfilledcols;
2659  columnorder[nfilledcols++] = -1; /* mark column to be filled from the left */
2660  j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2661  }
2662  }
2663 
2664  if ( ! isorbitope ) /*lint !e850*/
2665  goto FREEDATASTRUCTURES;
2666 
2667  coltoextend = 1;
2668  for (j = 0; j < npermsincomponent; ++j)
2669  { /*lint --e(850)*/
2670  SCIP_Bool success = FALSE;
2671  SCIP_Bool infeasible = FALSE;
2672 
2673  if ( nusedperms == npermsincomponent )
2674  break;
2675 
2676  if ( usedperm[j] )
2677  continue;
2678 
2679  SCIP_CALL( SCIPextendSubOrbitope(orbitopevaridx, ntwocyclescomp, nfilledcols, coltoextend,
2680  perms[components[componentbegins[i] + j]], FALSE, &nusedelems, &success, &infeasible) );
2681 
2682  if ( infeasible )
2683  {
2684  isorbitope = FALSE;
2685  break;
2686  }
2687  else if ( success )
2688  {
2689  usedperm[j] = TRUE;
2690  ++nusedperms;
2691  coltoextend = nfilledcols;
2692  columnorder[nfilledcols] = 1; /* mark column to be filled from the right */
2693  ++nfilledcols;
2694  j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2695  }
2696  }
2697 
2698  if ( nusedperms < npermsincomponent ) /*lint !e850*/
2699  isorbitope = FALSE;
2700 
2701  if ( ! isorbitope )
2702  goto FREEDATASTRUCTURES;
2703 
2704  /* we have found a potential orbitope, prepare data for orbitope conshdlr */
2705  SCIP_CALL( SCIPallocBufferArray(scip, &vars, ntwocyclescomp) );
2706  SCIP_CALL( SCIPallocBufferArray(scip, &varsallocorder, ntwocyclescomp) );
2707  for (j = 0; j < ntwocyclescomp; ++j)
2708  {
2709  SCIP_CALL( SCIPallocBufferArray(scip, &vars[j], npermsincomponent + 1) ); /*lint !e866*/
2710  varsallocorder[j] = vars[j]; /* to ensure that we can free the buffer in reverse order */
2711  }
2712 
2713  /* prepare variable matrix (reorder columns of orbitopevaridx) */
2714  infeasibleorbitope = FALSE;
2715  SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(&vars, ntwocyclescomp, npermsincomponent + 1, permvars, npermvars,
2716  orbitopevaridx, columnorder, nusedelems, &infeasibleorbitope) );
2717 
2718  if ( ! infeasibleorbitope )
2719  {
2720  SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, "orbitope", vars, SCIP_ORBITOPETYPE_FULL,
2721  ntwocyclescomp, npermsincomponent + 1, TRUE, FALSE,
2722  propdata->conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2723 
2724  SCIP_CALL( SCIPaddCons(scip, cons) );
2725 
2726  /* do not release constraint here - will be done later */
2727  propdata->genconss[propdata->ngenconss++] = cons;
2728  ++propdata->norbitopes;
2729 
2730  propdata->componentblocked[i] = TRUE;
2731  }
2732 
2733  /* free data structures */
2734  for (j = ntwocyclescomp - 1; j >= 0; --j)
2735  {
2736  SCIPfreeBufferArray(scip, &varsallocorder[j]);
2737  }
2738  SCIPfreeBufferArray(scip, &varsallocorder);
2739  SCIPfreeBufferArray(scip, &vars);
2740 
2741  FREEDATASTRUCTURES:
2742  SCIPfreeBufferArray(scip, &nusedelems);
2743  SCIPfreeBufferArray(scip, &columnorder);
2744  for (j = ntwocyclescomp - 1; j >= 0; --j)
2745  {
2746  SCIPfreeBufferArray(scip, &orbitopevaridx[j]);
2747  }
2748  SCIPfreeBufferArray(scip, &orbitopevaridx);
2749  SCIPfreeBufferArray(scip, &usedperm);
2750  }
2751 
2752  return SCIP_OKAY;
2753 }
2754 
2755 
2756 /** adds symresack constraints */
2757 static
2759  SCIP* scip, /**< SCIP instance */
2760  SCIP_PROP* prop, /**< symmetry breaking propagator */
2761  int* components, /**< array containing components of symmetry group */
2762  int* componentbegins, /**< array containing begin positions of components in components array */
2763  int ncomponents /**< number of components */
2764  )
2765 {
2766  SCIP_PROPDATA* propdata;
2767  SCIP_VAR** permvars;
2768  SCIP_Bool conssaddlp;
2769  int** perms;
2770  int nsymresackcons = 0;
2771  int npermvars;
2772  int i;
2773  int p;
2774 
2775  assert( scip != NULL );
2776  assert( prop != NULL );
2777 
2778  propdata = SCIPpropGetData(prop);
2779  assert( propdata != NULL );
2780  assert( propdata->npermvars >= 0 );
2781  assert( propdata->nbinpermvars >= 0 );
2782 
2783  /* if no symmetries on binary variables are present */
2784  if ( propdata->nbinpermvars == 0 )
2785  {
2786  assert( propdata->binvaraffected == 0 );
2787  return SCIP_OKAY;
2788  }
2789 
2790  perms = propdata->perms;
2791  permvars = propdata->permvars;
2792  npermvars = propdata->npermvars;
2793  conssaddlp = propdata->conssaddlp;
2794 
2795  assert( propdata->nperms <= 0 || perms != NULL );
2796  assert( permvars != NULL );
2797  assert( npermvars > 0 );
2798 
2799  /* if components have not been computed */
2800  if ( ncomponents == -1 )
2801  {
2802  assert( ! propdata->ofenabled );
2803  assert( ! propdata->detectorbitopes );
2804 
2805  /* loop through perms and add symresack constraints */
2806  for (p = 0; p < propdata->nperms; ++p)
2807  {
2808  SCIP_CONS* cons;
2809  char name[SCIP_MAXSTRLEN];
2810 
2811  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_perm%d", p);
2812  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[p], permvars, npermvars, FALSE,
2813  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2814 
2815  SCIP_CALL( SCIPaddCons(scip, cons) );
2816 
2817  /* do not release constraint here - will be done later */
2818  propdata->genconss[propdata->ngenconss++] = cons;
2819  ++propdata->nsymresacks;
2820  ++nsymresackcons;
2821  }
2822  }
2823  else
2824  {
2825  /* loop through components */
2826  for (i = 0; i < ncomponents; ++i)
2827  {
2828  /* skip components that were treated by different symmetry handling techniques */
2829  if ( propdata->componentblocked[i] )
2830  continue;
2831 
2832  /* loop through perms in component i and add symresack constraints */
2833  for (p = componentbegins[i]; p < componentbegins[i + 1]; ++p)
2834  {
2835  SCIP_CONS* cons;
2836  int permidx;
2837  char name[SCIP_MAXSTRLEN];
2838 
2839  permidx = components[p];
2840 
2841  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symbreakcons_component%d_perm%d", i, permidx);
2842  SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
2843  conssaddlp, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2844 
2845  SCIP_CALL( SCIPaddCons(scip, cons) );
2846 
2847  /* do not release constraint here - will be done later */
2848  propdata->genconss[propdata->ngenconss++] = cons;
2849  ++propdata->nsymresacks;
2850  ++nsymresackcons;
2851  }
2852  }
2853  }
2854 
2855  SCIPdebugMsg(scip, "Added %d symresack constraints.\n", nsymresackcons);
2856 
2857  return SCIP_OKAY;
2858 }
2859 
2860 
2861 /** finds problem symmetries */
2862 static
2864  SCIP* scip, /**< SCIP instance */
2865  SCIP_PROP* prop, /**< symmetry breaking propagator */
2866  SCIP_Bool* earlyterm /**< pointer to store whether we terminated early (or NULL) */
2867  )
2868 {
2869  SCIP_PROPDATA* propdata;
2870 
2871  assert( prop != NULL );
2872  assert( scip != NULL );
2873 
2874  propdata = SCIPpropGetData(prop);
2875  assert( propdata != NULL );
2876  assert( propdata->symconsenabled );
2877 
2878  /* possibly compute symmetry */
2879  if ( propdata->ofenabled )
2880  {
2881  if ( propdata->symfixnonbinaryvars )
2882  {
2884  }
2885  else
2886  {
2888  }
2889  }
2890  else
2891  {
2893  }
2894  assert( propdata->binvaraffected || ! propdata->symconsenabled );
2895 
2896  /* if constraints have already been added */
2897  if ( propdata->triedaddconss )
2898  {
2899  assert( propdata->nperms > 0 );
2900 
2901  if ( earlyterm != NULL )
2902  *earlyterm = TRUE;
2903 
2904  return SCIP_OKAY;
2905  }
2906 
2907  if ( propdata->nperms <= 0 || ! propdata->symconsenabled )
2908  return SCIP_OKAY;
2909 
2910  assert( propdata->nperms > 0 );
2911  assert( propdata->binvaraffected );
2912  propdata->triedaddconss = TRUE;
2913 
2914  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->genconss, propdata->nperms) );
2915 
2916  if ( propdata->detectorbitopes )
2917  {
2918  SCIP_CALL( detectOrbitopes(scip, propdata, propdata->components, propdata->componentbegins, propdata->ncomponents) );
2919  }
2920 
2921  /* disable orbital fixing if all components are handled by orbitopes */
2922  if ( propdata->ncomponents == propdata->norbitopes )
2923  propdata->ofenabled = FALSE;
2924 
2925  /* possibly stop */
2926  if ( SCIPisStopped(scip) )
2927  return SCIP_OKAY;
2928 
2929  /* add symmetry breaking constraints if orbital fixing is not used outside orbitopes */
2930  if ( ! propdata->ofenabled )
2931  {
2932  /* exit if no or only trivial symmetry group is available */
2933  if ( propdata->nperms <= 0 || ! propdata->binvaraffected )
2934  return SCIP_OKAY;
2935 
2936  if ( propdata->addsymresacks )
2937  {
2938  SCIP_CALL( addSymresackConss(scip, prop, propdata->components, propdata->componentbegins, propdata->ncomponents) );
2939  }
2940  }
2941 
2942  return SCIP_OKAY;
2943 }
2944 
2945 
2946 
2947 /*
2948  * Local methods for orbital fixing
2949  */
2950 
2951 
2952 /** performs orbital fixing
2953  *
2954  * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
2955  * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
2956  * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
2957  * fixed.
2958  */
2959 static
2961  SCIP* scip, /**< SCIP pointer */
2962  SCIP_VAR** permvars, /**< variables */
2963  int npermvars, /**< number of variables */
2964  int* orbits, /**< array of non-trivial orbits */
2965  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
2966  int norbits, /**< number of orbits */
2967  SCIP_Bool* infeasible, /**< pointer to store whether problem is infeasible */
2968  int* nfixedzero, /**< pointer to store number of variables fixed to 0 */
2969  int* nfixedone /**< pointer to store number of variables fixed to 1 */
2970  )
2971 {
2972  SCIP_Bool tightened;
2973  int i;
2974 
2975  assert( scip != NULL );
2976  assert( permvars != NULL );
2977  assert( orbits != NULL );
2978  assert( orbitbegins != NULL );
2979  assert( infeasible != NULL );
2980  assert( nfixedzero != NULL );
2981  assert( nfixedone != NULL );
2982  assert( norbits > 0 );
2983  assert( orbitbegins[0] == 0 );
2984 
2985  *infeasible = FALSE;
2986  *nfixedzero = 0;
2987  *nfixedone = 0;
2988 
2989  /* check all orbits */
2990  for (i = 0; i < norbits; ++i)
2991  {
2992  SCIP_Bool havefixedone = FALSE;
2993  SCIP_Bool havefixedzero = FALSE;
2994  SCIP_VAR* var;
2995  int j;
2996 
2997  /* we only have nontrivial orbits */
2998  assert( orbitbegins[i+1] - orbitbegins[i] >= 2 );
2999 
3000  /* check all variables in the orbit */
3001  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3002  {
3003  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3004  var = permvars[orbits[j]];
3005  assert( var != NULL );
3006 
3007  /* check whether variable is not binary (and not implicit integer!) */
3008  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3009  {
3010  /* skip orbit if there are non-binary variables */
3011  havefixedone = FALSE;
3012  havefixedzero = FALSE;
3013  break;
3014  }
3015 
3016  /* if variable is fixed to 1 -> can fix all variables in orbit to 1 */
3017  if ( SCIPvarGetLbLocal(var) > 0.5 )
3018  havefixedone = TRUE;
3019 
3020  /* check for zero-fixed variables */
3021  if ( SCIPvarGetUbLocal(var) < 0.5 )
3022  havefixedzero = TRUE;
3023  }
3024 
3025  /* check consistency */
3026  if ( havefixedone && havefixedzero )
3027  {
3028  *infeasible = TRUE;
3029  return SCIP_OKAY;
3030  }
3031 
3032  /* fix all variables to 0 if there is one variable fixed to 0 */
3033  if ( havefixedzero )
3034  {
3035  assert( ! havefixedone );
3036 
3037  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3038  {
3039  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3040  var = permvars[orbits[j]];
3041  assert( var != NULL );
3042 
3043  /* only variables that are not yet fixed to 0 */
3044  if ( SCIPvarGetUbLocal(var) > 0.5 )
3045  {
3046  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 0.\n", SCIPvarGetName(var), orbits[j]);
3047  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
3048  /* due to aggregation, var might already be fixed to 1, so do not put assert here */
3049 
3050  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
3051  SCIP_CALL( SCIPtightenVarUb(scip, var, 0.0, FALSE, infeasible, &tightened) );
3052  if ( *infeasible )
3053  return SCIP_OKAY;
3054  if ( tightened )
3055  ++(*nfixedzero);
3056  }
3057  }
3058  }
3059 
3060  /* fix all variables to 1 if there is one variable fixed to 1 */
3061  if ( havefixedone )
3062  {
3063  assert( ! havefixedzero );
3064 
3065  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
3066  {
3067  assert( 0 <= orbits[j] && orbits[j] < npermvars );
3068  var = permvars[orbits[j]];
3069  assert( var != NULL );
3070 
3071  /* only variables that are not yet fixed to 1 */
3072  if ( SCIPvarGetLbLocal(var) < 0.5)
3073  {
3074  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 1.\n", SCIPvarGetName(var), orbits[j]);
3075  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
3076  /* due to aggregation, var might already be fixed to 0, so do not put assert here */
3077 
3078  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
3079  SCIP_CALL( SCIPtightenVarLb(scip, var, 1.0, FALSE, infeasible, &tightened) );
3080  if ( *infeasible )
3081  return SCIP_OKAY;
3082  if ( tightened )
3083  ++(*nfixedone);
3084  }
3085  }
3086  }
3087  }
3088 
3089  return SCIP_OKAY;
3090 }
3091 
3092 
3093 /** Gets branching variables on the path to root
3094  *
3095  * The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
3096  */
3097 static
3099  SCIP* scip, /**< SCIP pointer */
3100  int nvars, /**< number of variables */
3101  SCIP_HASHMAP* varmap, /**< map of variables to indices in vars array */
3102  SCIP_Shortbool* bg1, /**< bitset marking the variables globally fixed or branched to 1 */
3103  int* bg1list, /**< array to store the variable indices globally fixed or branched to 1 */
3104  int* nbg1 /**< pointer to store the number of variables in bg1 and bg1list */
3105  )
3106 {
3107  SCIP_NODE* node;
3108 
3109  assert( scip != NULL );
3110  assert( varmap != NULL );
3111  assert( bg1 != NULL );
3112  assert( bg1list != NULL );
3113  assert( nbg1 != NULL );
3114  assert( *nbg1 >= 0 );
3115 
3116  /* get current node */
3117  node = SCIPgetCurrentNode(scip);
3118 
3119 #ifdef SCIP_OUTPUT
3120  SCIP_CALL( SCIPprintNodeRootPath(scip, node, NULL) );
3121 #endif
3122 
3123  /* follow path to the root (in the root no domains were changed due to branching) */
3124  while ( SCIPnodeGetDepth(node) != 0 )
3125  {
3126  SCIP_BOUNDCHG* boundchg;
3127  SCIP_DOMCHG* domchg;
3128  SCIP_VAR* branchvar;
3129  int nboundchgs;
3130  int i;
3131 
3132  /* get domain changes of current node */
3133  domchg = SCIPnodeGetDomchg(node);
3134 
3135  /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
3136  * cases domchg should not be NULL. */
3137  if ( domchg != NULL )
3138  {
3139  /* loop through all bound changes */
3140  nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
3141  for (i = 0; i < nboundchgs; ++i)
3142  {
3143  /* get bound change info */
3144  boundchg = SCIPdomchgGetBoundchg(domchg, i);
3145  assert( boundchg != NULL );
3146 
3147  /* branching decisions have to be in the beginning of the bound change array */
3149  break;
3150 
3151  /* get corresponding branching variable */
3152  branchvar = SCIPboundchgGetVar(boundchg);
3153 
3154  /* we only consider binary variables */
3155  if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
3156  {
3157  /* if branching variable is not known (may have been created meanwhile,
3158  * e.g., by prop_inttobinary; may have been removed from symmetry data
3159  * due to compression), continue with parent node */
3160  if ( ! SCIPhashmapExists(varmap, (void*) branchvar) )
3161  break;
3162 
3163  if ( SCIPvarGetLbLocal(branchvar) > 0.5 )
3164  {
3165  int branchvaridx;
3166 
3167  branchvaridx = SCIPhashmapGetImageInt(varmap, (void*) branchvar);
3168  assert( branchvaridx < nvars );
3169 
3170  /* the variable might already be fixed to 1 */
3171  if ( ! bg1[branchvaridx] )
3172  {
3173  bg1[branchvaridx] = TRUE;
3174  bg1list[(*nbg1)++] = branchvaridx;
3175  }
3176  }
3177  }
3178  }
3179  }
3180 
3181  node = SCIPnodeGetParent(node);
3182  }
3183 
3184  return SCIP_OKAY;
3185 }
3186 
3187 
3188 /** propagates orbital fixing */
3189 static
3191  SCIP* scip, /**< SCIP pointer */
3192  SCIP_PROPDATA* propdata, /**< data of symmetry breaking propagator */
3193  SCIP_Bool* infeasible, /**< pointer to store whether the node is detected to be infeasible */
3194  int* nprop /**< pointer to store the number of propagations */
3195  )
3196 {
3197  SCIP_Shortbool* inactiveperms;
3198  SCIP_Shortbool* bg0;
3199  SCIP_Shortbool* bg1;
3200  SCIP_VAR** permvars;
3201  int* orbitbegins;
3202  int* orbits;
3203  int* components;
3204  int* componentbegins;
3205  int* vartocomponent;
3206  int ncomponents;
3207  int* bg0list;
3208  int nbg0;
3209  int* bg1list;
3210  int nbg1;
3211  int nactiveperms;
3212  int norbits;
3213  int npermvars;
3214  int nbinpermvars;
3215  int** permstrans;
3216  int nperms;
3217  int p;
3218  int v;
3219  int j;
3220  int componentidx;
3221 
3222  assert( scip != NULL );
3223  assert( propdata != NULL );
3224  assert( propdata->ofenabled );
3225  assert( infeasible != NULL );
3226  assert( nprop != NULL );
3227 
3228  *infeasible = FALSE;
3229  *nprop = 0;
3230 
3231  /* possibly compute symmetry */
3232  if ( propdata->symfixnonbinaryvars )
3233  {
3235  }
3236  else
3237  {
3239  }
3240  assert( propdata->binvaraffected || ! propdata->ofenabled );
3241 
3242  /* return if there is no symmetry available */
3243  nperms = propdata->nperms;
3244  if ( nperms <= 0 || ! propdata->ofenabled )
3245  return SCIP_OKAY;
3246 
3247  assert( propdata->permvars != NULL );
3248  assert( propdata->npermvars > 0 );
3249  assert( propdata->permvarmap != NULL );
3250  assert( propdata->permstrans != NULL );
3251  assert( propdata->inactiveperms != NULL );
3252  assert( propdata->components != NULL );
3253  assert( propdata->componentbegins != NULL );
3254  assert( propdata->vartocomponent != NULL );
3255  assert( propdata->ncomponents > 0 );
3256 
3257  permvars = propdata->permvars;
3258  npermvars = propdata->npermvars;
3259  nbinpermvars = propdata->nbinpermvars;
3260  permstrans = propdata->permstrans;
3261  inactiveperms = propdata->inactiveperms;
3262  components = propdata->components;
3263  componentbegins = propdata->componentbegins;
3264  vartocomponent = propdata->vartocomponent;
3265  ncomponents = propdata->ncomponents;
3266 
3267  /* init bitset for marking variables (globally fixed or) branched to 1 */
3268  assert( propdata->bg1 != NULL );
3269  assert( propdata->bg1list != NULL );
3270  assert( propdata->nbg1 >= 0 );
3271  assert( propdata->nbg1 <= npermvars );
3272 
3273  bg1 = propdata->bg1;
3274  bg1list = propdata->bg1list;
3275  nbg1 = propdata->nbg1;
3276 
3277  /* get branching variables */
3278  SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, bg1, bg1list, &nbg1) );
3279  assert( nbg1 >= propdata->nbg1 );
3280 
3281  /* reset inactive permutations */
3282  nactiveperms = nperms;
3283  for (p = 0; p < nperms; ++p)
3284  propdata->inactiveperms[p] = FALSE;
3285 
3286  /* get pointers for bg0 */
3287  assert( propdata->bg0 != NULL );
3288  assert( propdata->bg0list != NULL );
3289  assert( propdata->nbg0 >= 0 );
3290  assert( propdata->nbg0 <= npermvars );
3291 
3292  bg0 = propdata->bg0;
3293  bg0list = propdata->bg0list;
3294  nbg0 = propdata->nbg0;
3295 
3296  /* filter out permutations that move variables that are fixed to 0 */
3297  for (j = 0; j < nbg0 && nactiveperms > 0; ++j)
3298  {
3299  int* pt;
3300 
3301  v = bg0list[j];
3302  assert( 0 <= v && v < npermvars );
3303  assert( bg0[v] );
3304 
3305  componentidx = vartocomponent[v];
3306 
3307  /* skip unaffected variables and blocked components */
3308  if ( componentidx < 0 || propdata->componentblocked[componentidx] )
3309  continue;
3310 
3311  pt = permstrans[v];
3312  assert( pt != NULL );
3313 
3314  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
3315  {
3316  int img;
3317  int perm;
3318 
3319  perm = components[p];
3320 
3321  /* skip inactive permutations */
3322  if ( inactiveperms[perm] )
3323  continue;
3324 
3325  img = pt[perm];
3326 
3327  if ( img != v )
3328  {
3329 #ifndef NDEBUG
3330  SCIP_VAR* varv = permvars[v];
3331  SCIP_VAR* varimg = permvars[img];
3332 
3333  /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
3334  assert( SCIPvarGetType(varv) == SCIPvarGetType(varimg) ||
3335  (SCIPvarIsBinary(varv) && SCIPvarIsBinary(varimg)) ||
3337  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3338  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) ||
3340  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3341  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) );
3342  assert( SCIPisEQ(scip, propdata->permvarsobj[v], propdata->permvarsobj[img]) );
3343 #endif
3344 
3345  /* we are moving a variable globally fixed to 0 to a variable not of this type */
3346  if ( ! bg0[img] )
3347  {
3348  inactiveperms[perm] = TRUE; /* mark as inactive */
3349  --nactiveperms;
3350  }
3351  }
3352  }
3353  }
3354 
3355  /* filter out permutations that move variables that are fixed to different values */
3356  for (j = 0; j < nbg1 && nactiveperms > 0; ++j)
3357  {
3358  int* pt;
3359 
3360  v = bg1list[j];
3361  assert( 0 <= v && v < npermvars );
3362  assert( bg1[v] );
3363 
3364  componentidx = vartocomponent[v];
3365 
3366  /* skip unaffected variables and blocked components */
3367  if ( componentidx < 0 || propdata->componentblocked[componentidx] )
3368  continue;
3369 
3370  pt = permstrans[v];
3371  assert( pt != NULL );
3372 
3373  for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
3374  {
3375  int img;
3376  int perm;
3377 
3378  perm = components[p];
3379 
3380  /* skip inactive permutations */
3381  if ( inactiveperms[perm] )
3382  continue;
3383 
3384  img = pt[perm];
3385 
3386  if ( img != v )
3387  {
3388 #ifndef NDEBUG
3389  SCIP_VAR* varv = permvars[v];
3390  SCIP_VAR* varimg = permvars[img];
3391 
3392  /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
3393  assert( SCIPvarGetType(varv) == SCIPvarGetType(varimg) ||
3394  (SCIPvarIsBinary(varv) && SCIPvarIsBinary(varimg)) ||
3396  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3397  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) ||
3399  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
3400  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) );
3401  assert( SCIPisEQ(scip, propdata->permvarsobj[v], propdata->permvarsobj[img]) );
3402 #endif
3403 
3404  /* we are moving a variable globally fixed or branched to 1 to a variable not of this type */
3405  if ( ! bg1[img] )
3406  {
3407  inactiveperms[perm] = TRUE; /* mark as inactive */
3408  --nactiveperms;
3409  }
3410  }
3411  }
3412  }
3413 
3414  /* Clean bg1 list - need to do this after the main loop! (Not needed for bg0.)
3415  * Note that variables globally fixed to 1 are not resetted, since the loop starts at propdata->nbg1. */
3416  for (j = propdata->nbg1; j < nbg1; ++j)
3417  bg1[bg1list[j]] = FALSE;
3418 
3419  /* exit if no active permuations left */
3420  if ( nactiveperms == 0 )
3421  return SCIP_OKAY;
3422 
3423  /* compute orbits of binary variables */
3424  SCIP_CALL( SCIPallocBufferArray(scip, &orbits, nbinpermvars) );
3425  SCIP_CALL( SCIPallocBufferArray(scip, &orbitbegins, nbinpermvars) );
3426  SCIP_CALL( SCIPcomputeOrbitsFilterSym(scip, nbinpermvars, permstrans, nperms, inactiveperms,
3427  orbits, orbitbegins, &norbits, components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
3428 
3429  if ( norbits > 0 )
3430  {
3431  int nfixedzero = 0;
3432  int nfixedone = 0;
3433 
3434  SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits (%d active perms).\n", norbits, nactiveperms);
3435  SCIP_CALL( performOrbitalFixing(scip, permvars, nbinpermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
3436 
3437  propdata->nfixedzero += nfixedzero;
3438  propdata->nfixedone += nfixedone;
3439  *nprop = nfixedzero + nfixedone;
3440 
3441  SCIPdebugMsg(scip, "Orbital fixings: %d 0s, %d 1s.\n", nfixedzero, nfixedone);
3442  }
3443 
3444  SCIPfreeBufferArray(scip, &orbitbegins);
3445  SCIPfreeBufferArray(scip, &orbits);
3446 
3447  return SCIP_OKAY;
3448 }
3449 
3450 
3451 
3452 /*
3453  * Callback methods of propagator
3454  */
3455 
3456 /** presolving initialization method of propagator (called when presolving is about to begin) */
3457 static
3458 SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
3459 { /*lint --e{715}*/
3460  SCIP_PROPDATA* propdata;
3461 
3462  assert( scip != NULL );
3463  assert( prop != NULL );
3464 
3465  propdata = SCIPpropGetData(prop);
3466  assert( propdata != NULL );
3467 
3468  /* check whether we should run */
3469  if ( propdata->usesymmetry < 0 )
3470  {
3471  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &propdata->usesymmetry) );
3472 
3473  if ( ISSYMRETOPESACTIVE(propdata->usesymmetry) )
3474  propdata->symconsenabled = TRUE;
3475  else
3476  propdata->symconsenabled = FALSE;
3477 
3478  if ( ISORBITALFIXINGACTIVE(propdata->usesymmetry) )
3479  propdata->ofenabled = TRUE;
3480  else
3481  propdata->ofenabled = FALSE;
3482  }
3483 
3484  /* add symmetry handling constraints if required */
3485  if ( propdata->symconsenabled && propdata->addconsstiming == 0 )
3486  {
3487  SCIPdebugMsg(scip, "Try to add symmetry handling constraints before presolving.");
3488 
3490  }
3491 
3492  return SCIP_OKAY;
3493 }
3494 
3495 
3496 /** presolving deinitialization method of propagator (called after presolving has been finished) */
3497 static
3498 SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
3499 { /*lint --e{715}*/
3500  SCIP_PROPDATA* propdata;
3501 
3502  assert( scip != NULL );
3503  assert( prop != NULL );
3504  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3505 
3506  SCIPdebugMsg(scip, "Exitpre method of propagator <%s> ...\n", PROP_NAME);
3507 
3508  propdata = SCIPpropGetData(prop);
3509  assert( propdata != NULL );
3510  assert( propdata->usesymmetry >= 0 );
3511 
3512  /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
3513  * and even if presolving has been disabled */
3514  if ( propdata->symconsenabled && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
3515  {
3517  }
3518 
3519  return SCIP_OKAY;
3520 }
3521 
3522 
3523 /** presolving method of propagator */
3524 static
3525 SCIP_DECL_PROPPRESOL(propPresolSymmetry)
3526 { /*lint --e{715}*/
3527  SCIP_PROPDATA* propdata;
3528  int i;
3529 
3530  assert( scip != NULL );
3531  assert( prop != NULL );
3532  assert( result != NULL );
3533  assert( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING );
3534 
3535  *result = SCIP_DIDNOTRUN;
3536 
3537  propdata = SCIPpropGetData(prop);
3538  assert( propdata != NULL );
3539  assert( propdata->usesymmetry >= 0 );
3540 
3541  /* possibly create symmetry handling constraints */
3542  if ( propdata->symconsenabled )
3543  {
3544  int noldngenconns;
3545  SCIP_Bool earlyterm = FALSE;
3546 
3547  /* skip presolving if we are not at the end if addconsstiming == 2 */
3548  assert( 0 <= propdata->addconsstiming && propdata->addconsstiming <= 2 );
3549  if ( propdata->addconsstiming > 1 && ! SCIPisPresolveFinished(scip) )
3550  return SCIP_OKAY;
3551 
3552  /* possibly stop */
3553  if ( SCIPisStopped(scip) )
3554  return SCIP_OKAY;
3555 
3556  noldngenconns = propdata->ngenconss;
3557 
3558  SCIP_CALL( tryAddSymmetryHandlingConss(scip, prop, &earlyterm) );
3559 
3560  /* if we actually tried to add symmetry handling constraints */
3561  if ( ! earlyterm )
3562  {
3563  *result = SCIP_DIDNOTFIND;
3564 
3565  /* if symmetry handling constraints have been added, presolve each */
3566  if ( propdata->ngenconss > 0 )
3567  {
3568  /* at this point, the symmetry group should be computed and nontrivial */
3569  assert( propdata->nperms > 0 );
3570  assert( propdata->triedaddconss );
3571 
3572  /* we have added at least one symmetry handling constraints, i.e., we were successful */
3573  *result = SCIP_SUCCESS;
3574 
3575  *naddconss += propdata->ngenconss - noldngenconns;
3576  SCIPdebugMsg(scip, "Added symmetry breaking constraints: %d.\n", propdata->ngenconss - noldngenconns);
3577 
3578  /* if constraints have been added, loop through generated constraints and presolve each */
3579  for (i = 0; i < propdata->ngenconss; ++i)
3580  {
3581  SCIP_CALL( SCIPpresolCons(scip, propdata->genconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
3582  nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
3583  nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
3584 
3585  /* exit if cutoff or unboundedness has been detected */
3586  if ( *result == SCIP_CUTOFF || *result == SCIP_UNBOUNDED )
3587  {
3588  SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genconss[i]));
3589  return SCIP_OKAY;
3590  }
3591  }
3592  SCIPdebugMsg(scip, "Presolved %d generated constraints.\n", propdata->ngenconss);
3593  }
3594  }
3595  }
3596 
3597  /* run OF presolving */
3598  assert( 0 <= propdata->ofsymcomptiming && propdata->ofsymcomptiming <= 2 );
3599  if ( propdata->ofenabled && propdata->performpresolving && propdata->ofsymcomptiming <= 1 )
3600  {
3601  SCIP_Bool infeasible;
3602  int nprop;
3603 
3604  /* if we did not tried to add symmetry handling constraints */
3605  if ( *result == SCIP_DIDNOTRUN )
3606  *result = SCIP_DIDNOTFIND;
3607 
3608  SCIPdebugMsg(scip, "Presolving <%s>.\n", PROP_NAME);
3609 
3610  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
3611 
3612  if ( infeasible )
3613  {
3614  *result = SCIP_CUTOFF;
3615  propdata->offoundreduction = TRUE;
3616  }
3617  else if ( nprop > 0 )
3618  {
3619  *result = SCIP_SUCCESS;
3620  *nfixedvars += nprop;
3621  propdata->offoundreduction = TRUE;
3622  }
3623  }
3624  else if ( propdata->ofenabled && propdata->ofsymcomptiming == 1 )
3625  {
3626  /* otherwise compute symmetry if timing requests it */
3627  if ( propdata->symfixnonbinaryvars )
3628  {
3630  }
3631  else
3632  {
3634  }
3635  assert( propdata->binvaraffected || ! propdata->ofenabled );
3636  }
3637 
3638  return SCIP_OKAY;
3639 }
3640 
3641 
3642 /** execution method of propagator */
3643 static
3644 SCIP_DECL_PROPEXEC(propExecSymmetry)
3645 { /*lint --e{715}*/
3646  SCIP_PROPDATA* propdata;
3647  SCIP_Bool infeasible = FALSE;
3648  SCIP_Longint nodenumber;
3649  int nprop = 0;
3650 
3651  assert( scip != NULL );
3652  assert( result != NULL );
3653 
3654  *result = SCIP_DIDNOTRUN;
3655 
3656  /* do not run if we are in the root or not yet solving */
3658  return SCIP_OKAY;
3659 
3660  /* do nothing if we are in a probing node */
3661  if ( SCIPinProbing(scip) )
3662  return SCIP_OKAY;
3663 
3664  /* do not run again in repropagation, since the path to the root might have changed */
3665  if ( SCIPinRepropagation(scip) )
3666  return SCIP_OKAY;
3667 
3668  /* get data */
3669  propdata = SCIPpropGetData(prop);
3670  assert( propdata != NULL );
3671 
3672  /* if usesymmetry has not been read so far */
3673  if ( propdata->usesymmetry < 0 )
3674  {
3675  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &propdata->usesymmetry) );
3676  if ( ISSYMRETOPESACTIVE(propdata->usesymmetry) )
3677  propdata->symconsenabled = TRUE;
3678  else
3679  propdata->symconsenabled = FALSE;
3680 
3681  if ( ISORBITALFIXINGACTIVE(propdata->usesymmetry) )
3682  propdata->ofenabled = TRUE;
3683  else
3684  propdata->ofenabled = FALSE;
3685  }
3686 
3687  /* do not propagate if orbital fixing is not enabled */
3688  if ( ! propdata->ofenabled )
3689  return SCIP_OKAY;
3690 
3691  /* return if there is no symmetry available */
3692  if ( propdata->nperms == 0 )
3693  return SCIP_OKAY;
3694 
3695  /* return if we already ran in this node */
3696  nodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
3697  if ( nodenumber == propdata->nodenumber )
3698  return SCIP_OKAY;
3699  propdata->nodenumber = nodenumber;
3700 
3701  /* propagate */
3702  *result = SCIP_DIDNOTFIND;
3703 
3704  SCIPdebugMsg(scip, "Propagating <%s>.\n", SCIPpropGetName(prop));
3705 
3706  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
3707 
3708  if ( infeasible )
3709  {
3710  *result = SCIP_CUTOFF;
3711  propdata->offoundreduction = TRUE;
3712  }
3713  else if ( nprop > 0 )
3714  {
3715  *result = SCIP_REDUCEDDOM;
3716  propdata->offoundreduction = TRUE;
3717  }
3718 
3719  return SCIP_OKAY;
3720 }
3721 
3722 
3723 /** deinitialization method of propagator (called before transformed problem is freed) */
3724 static
3725 SCIP_DECL_PROPEXIT(propExitSymmetry)
3726 {
3727  SCIP_PROPDATA* propdata;
3728 
3729  assert( scip != NULL );
3730  assert( prop != NULL );
3731  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3732 
3733  SCIPdebugMsg(scip, "Exiting propagator <%s>.\n", PROP_NAME);
3734 
3735  propdata = SCIPpropGetData(prop);
3736  assert( propdata != NULL );
3737 
3738  SCIP_CALL( freeSymmetryData(scip, propdata) );
3739 
3740  /* reset basic data */
3741  propdata->usesymmetry = -1;
3742  propdata->symconsenabled = FALSE;
3743  propdata->triedaddconss = FALSE;
3744  propdata->nsymresacks = 0;
3745  propdata->norbitopes = 0;
3746  propdata->ofenabled = FALSE;
3747  propdata->lastrestart = 0;
3748  propdata->nfixedzero = 0;
3749  propdata->nfixedone = 0;
3750  propdata->nodenumber = -1;
3751  propdata->offoundreduction = FALSE;
3752 
3753  return SCIP_OKAY;
3754 }
3755 
3756 
3757 /** propagation conflict resolving method of propagator
3758  *
3759  * @todo Implement reverse propagation.
3760  *
3761  * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
3762  * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
3763  * by the permutations which are involved in creating the orbit.
3764  */
3765 static
3766 SCIP_DECL_PROPRESPROP(propRespropSymmetry)
3767 { /*lint --e{715,818}*/
3768  assert( result != NULL );
3769 
3770  *result = SCIP_DIDNOTFIND;
3771 
3772  return SCIP_OKAY;
3773 }
3774 
3775 
3776 /** destructor of propagator to free user data (called when SCIP is exiting) */
3777 static
3778 SCIP_DECL_PROPFREE(propFreeSymmetry)
3779 { /*lint --e{715}*/
3780  SCIP_PROPDATA* propdata;
3781 
3782  assert( scip != NULL );
3783  assert( prop != NULL );
3784  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
3785 
3786  SCIPdebugMsg(scip, "Freeing symmetry propagator.\n");
3787 
3788  propdata = SCIPpropGetData(prop);
3789  assert( propdata != NULL );
3790 
3791  SCIPfreeBlockMemory(scip, &propdata);
3792 
3793  return SCIP_OKAY;
3794 }
3795 
3796 
3797 /*
3798  * External methods
3799  */
3800 
3801 /** include symmetry propagator */
3803  SCIP* scip /**< SCIP data structure */
3804  )
3805 {
3806  SCIP_TABLEDATA* tabledata;
3807  SCIP_PROPDATA* propdata = NULL;
3808  SCIP_PROP* prop = NULL;
3809 
3810  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3811  assert( propdata != NULL );
3812 
3813  propdata->npermvars = 0;
3814  propdata->nbinpermvars = 0;
3815  propdata->permvars = NULL;
3816 #ifndef NDEBUG
3817  propdata->permvarsobj = NULL;
3818 #endif
3819  propdata->nperms = -1;
3820  propdata->nmaxperms = 0;
3821  propdata->perms = NULL;
3822  propdata->permstrans = NULL;
3823  propdata->permvarmap = NULL;
3824 
3825  propdata->ncomponents = -1;
3826  propdata->components = NULL;
3827  propdata->componentbegins = NULL;
3828  propdata->vartocomponent = NULL;
3829  propdata->componentblocked = NULL;
3830 
3831  propdata->log10groupsize = -1.0;
3832  propdata->nmovedvars = -1;
3833  propdata->binvaraffected = FALSE;
3834  propdata->computedsymmetry = FALSE;
3835 
3836  propdata->usesymmetry = -1;
3837  propdata->symconsenabled = FALSE;
3838  propdata->triedaddconss = FALSE;
3839  propdata->genconss = NULL;
3840  propdata->ngenconss = 0;
3841  propdata->nsymresacks = 0;
3842  propdata->norbitopes = 0;
3843 
3844  propdata->ofenabled = FALSE;
3845  propdata->bg0 = NULL;
3846  propdata->bg0list = NULL;
3847  propdata->nbg0 = 0;
3848  propdata->bg1 = NULL;
3849  propdata->bg1list = NULL;
3850  propdata->nbg1 = 0;
3851  propdata->permvarsevents = NULL;
3852  propdata->inactiveperms = NULL;
3853  propdata->nmovedpermvars = 0;
3854  propdata->lastrestart = 0;
3855  propdata->nfixedzero = 0;
3856  propdata->nfixedone = 0;
3857  propdata->nodenumber = -1;
3858  propdata->offoundreduction = FALSE;
3859 
3860  /* create event handler */
3861  propdata->eventhdlr = NULL;
3863  eventExecSymmetry, NULL) );
3864  assert( propdata->eventhdlr != NULL );
3865 
3866  /* include constraint handler */
3868  PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecSymmetry, propdata) );
3869  assert( prop != NULL );
3870 
3871  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSymmetry) );
3872  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitSymmetry) );
3873  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreSymmetry) );
3874  SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreSymmetry) );
3875  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropSymmetry) );
3877 
3878  /* include table */
3879  SCIP_CALL( SCIPallocBlockMemory(scip, &tabledata) );
3880  tabledata->propdata = propdata;
3882  NULL, tableFreeOrbitalfixing, NULL, NULL, NULL, NULL, tableOutputOrbitalfixing,
3884 
3885  /* add parameters for computing symmetry */
3886  SCIP_CALL( SCIPaddIntParam(scip,
3887  "propagating/" PROP_NAME "/maxgenerators",
3888  "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
3889  &propdata->maxgenerators, TRUE, DEFAULT_MAXGENERATORS, 0, INT_MAX, NULL, NULL) );
3890 
3892  "propagating/" PROP_NAME "/checksymmetries",
3893  "Should all symmetries be checked after computation?",
3894  &propdata->checksymmetries, TRUE, DEFAULT_CHECKSYMMETRIES, NULL, NULL) );
3895 
3897  "propagating/" PROP_NAME "/displaynorbitvars",
3898  "Should the number of variables affected by some symmetry be displayed?",
3899  &propdata->displaynorbitvars, TRUE, DEFAULT_DISPLAYNORBITVARS, NULL, NULL) );
3900 
3902  "propagating/" PROP_NAME "/doubleequations",
3903  "Double equations to positive/negative version?",
3904  &propdata->doubleequations, TRUE, DEFAULT_DOUBLEEQUATIONS, NULL, NULL) );
3905 
3906  /* add parameters for adding symmetry handling constraints */
3908  "propagating/" PROP_NAME "/conssaddlp",
3909  "Should the symmetry breaking constraints be added to the LP?",
3910  &propdata->conssaddlp, TRUE, DEFAULT_CONSSADDLP, NULL, NULL) );
3911 
3913  "propagating/" PROP_NAME "/addsymresacks",
3914  "Add inequalities for symresacks for each generator?",
3915  &propdata->addsymresacks, TRUE, DEFAULT_ADDSYMRESACKS, NULL, NULL) );
3916 
3918  "propagating/" PROP_NAME "/detectorbitopes",
3919  "Should we check whether the components of the symmetry group can be handled by orbitopes?",
3920  &propdata->detectorbitopes, TRUE, DEFAULT_DETECTORBITOPES, NULL, NULL) );
3921 
3922  SCIP_CALL( SCIPaddIntParam(scip,
3923  "propagating/" PROP_NAME "/addconsstiming",
3924  "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
3925  &propdata->addconsstiming, TRUE, DEFAULT_ADDCONSSTIMING, 0, 2, NULL, NULL) );
3926 
3927  /* add parameters for orbital fixing */
3928  SCIP_CALL( SCIPaddIntParam(scip,
3929  "propagating/" PROP_NAME "/ofsymcomptiming",
3930  "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
3931  &propdata->ofsymcomptiming, TRUE, DEFAULT_OFSYMCOMPTIMING, 0, 2, NULL, NULL) );
3932 
3934  "propagating/" PROP_NAME "/performpresolving",
3935  "run orbital fixing during presolving?",
3936  &propdata->performpresolving, TRUE, DEFAULT_PERFORMPRESOLVING, NULL, NULL) );
3937 
3939  "propagating/" PROP_NAME "/recomputerestart",
3940  "recompute symmetries after a restart has occured?",
3941  &propdata->recomputerestart, TRUE, DEFAULT_RECOMPUTERESTART, NULL, NULL) );
3942 
3944  "propagating/" PROP_NAME "/compresssymmetries",
3945  "Should non-affected variables be removed from permutation to save memory?",
3946  &propdata->compresssymmetries, TRUE, DEFAULT_COMPRESSSYMMETRIES, NULL, NULL) );
3947 
3949  "propagating/" PROP_NAME "/compressthreshold",
3950  "Compression is used if percentage of moved vars is at most the threshold.",
3951  &propdata->compressthreshold, TRUE, DEFAULT_COMPRESSTHRESHOLD, 0.0, 1.0, NULL, NULL) );
3952 
3954  "propagating/" PROP_NAME "/usecolumnsparsity",
3955  "Should the number of conss a variable is contained in be exploited in symmetry detection?",
3956  &propdata->usecolumnsparsity, TRUE, DEFAULT_USECOLUMNSPARSITY, NULL, NULL) );
3957 
3959  "propagating/" PROP_NAME "/disableofrestart",
3960  "Shall orbital fixing be disabled if orbital fixing has found a reduction and a restart occurs?",
3961  &propdata->disableofrestart, TRUE, DEFAULT_DISABLEOFRESTART, NULL, NULL) );
3962 
3964  "propagating/" PROP_NAME "/symfixnonbinaryvars",
3965  "Whether all non-binary variables shall be not affected by symmetries if OF is active?",
3966  &propdata->symfixnonbinaryvars, TRUE, DEFAULT_SYMFIXNONBINARYVARS, NULL, NULL) );
3967 
3968  /* possibly add description */
3969  if ( SYMcanComputeSymmetry() )
3970  {
3972  }
3973 
3974  return SCIP_OKAY;
3975 }
3976 
3977 
3978 /** return currently available symmetry group information */
3980  SCIP* scip, /**< SCIP data structure */
3981  int* npermvars, /**< pointer to store number of variables for permutations */
3982  SCIP_VAR*** permvars, /**< pointer to store variables on which permutations act */
3983  SCIP_HASHMAP** permvarmap, /**< pointer to store hash map of permvars (or NULL) */
3984  int* nperms, /**< pointer to store number of permutations */
3985  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
3986  int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
3987  SCIP_Real* log10groupsize, /**< pointer to store log10 of group size (or NULL) */
3988  SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected */
3989  int** components, /**< pointer to store components of symmetry group (or NULL) */
3990  int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
3991  int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
3992  int* ncomponents /**< pointer to store number of components (or NULL) */
3993  )
3994 {
3995  SCIP_PROPDATA* propdata;
3996  SCIP_PROP* prop;
3997 
3998  assert( scip != NULL );
3999  assert( npermvars != NULL );
4000  assert( permvars != NULL );
4001  assert( nperms != NULL );
4002  assert( perms != NULL || permstrans != NULL );
4003  assert( ncomponents != NULL || (components == NULL && componentbegins == NULL && vartocomponent == NULL) );
4004 
4005  /* find symmetry propagator */
4006  prop = SCIPfindProp(scip, "symmetry");
4007  if ( prop == NULL )
4008  {
4009  SCIPerrorMessage("Could not find symmetry propagator.\n");
4010  return SCIP_PLUGINNOTFOUND;
4011  }
4012  assert( prop != NULL );
4013  assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );
4014 
4015  propdata = SCIPpropGetData(prop);
4016  assert( propdata != NULL );
4017 
4018  *npermvars = propdata->npermvars;
4019  *permvars = propdata->permvars;
4020 
4021  if ( permvarmap != NULL )
4022  *permvarmap = propdata->permvarmap;
4023 
4024  *nperms = propdata->nperms;
4025  if ( perms != NULL )
4026  {
4027  *perms = propdata->perms;
4028  assert( *perms != NULL || *nperms <= 0 );
4029  }
4030 
4031  if ( permstrans != NULL )
4032  {
4033  *permstrans = propdata->permstrans;
4034  assert( *permstrans != NULL || *nperms <= 0 );
4035  }
4036 
4037  if ( log10groupsize != NULL )
4038  *log10groupsize = propdata->log10groupsize;
4039 
4040  if ( binvaraffected != NULL )
4041  *binvaraffected = propdata->binvaraffected;
4042 
4043  if ( components != NULL )
4044  *components = propdata->components;
4045 
4046  if ( componentbegins != NULL )
4047  *componentbegins = propdata->componentbegins;
4048 
4049  if ( vartocomponent )
4050  *vartocomponent = propdata->vartocomponent;
4051 
4052  if ( ncomponents )
4053  *ncomponents = propdata->ncomponents;
4054 
4055  return SCIP_OKAY;
4056 }
4057 
4058 /** return whether orbital fixing is enabled */
4060  SCIP* scip /**< SCIP data structure */
4061  )
4062 {
4063  SCIP_PROP* prop;
4064  SCIP_PROPDATA* propdata;
4065 
4066  assert( scip != NULL );
4067 
4068  prop = SCIPfindProp(scip, PROP_NAME);
4069  if ( prop == NULL )
4070  return FALSE;
4071 
4072  propdata = SCIPpropGetData(prop);
4073  assert( propdata != NULL );
4074 
4075  return propdata->ofenabled;
4076 }
4077 
4078 /** return number of the symmetry group's generators */
4080  SCIP* scip /**< SCIP data structure */
4081  )
4082 {
4083  SCIP_PROP* prop;
4084  SCIP_PROPDATA* propdata;
4085 
4086  assert( scip != NULL );
4087 
4088  prop = SCIPfindProp(scip, PROP_NAME);
4089  if ( prop == NULL )
4090  return 0;
4091 
4092  propdata = SCIPpropGetData(prop);
4093  assert( propdata != NULL );
4094 
4095  if ( propdata->nperms < 0 )
4096  return 0;
4097  else
4098  return propdata->nperms;
4099 }
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:5958
#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:2486
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:5184
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:3446
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2598
#define SCIP_MAXSTRLEN
Definition: def.h:273
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:2547
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1218
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5301
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7420
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:3131
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:8150
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:7430
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:9272
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:7700
SCIP_VAR ** SCIPgetVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_xor.c:5935
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:2235
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:3220
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:3362
#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:8648
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:1742
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPORT SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7515
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:364
#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:8238
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:2285
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:3013
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
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:5439
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8398
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:4628
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:5981
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:10590
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9249
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:3047
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8089
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
#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:8109
#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:4179
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:9295
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:5912
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
#define SCIPABORT()
Definition: def.h:336
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)