Scippy

SCIP

Solving Constraint Integer Programs

prop_orbitalfixing.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_orbitalfixing.c
17  * @brief propagator for orbital fixing
18  * @author Marc Pfetsch
19  *
20  * This propagator implements orbital fixing as introduced by
21  *
22  * F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.
23  *
24  * The method obtains symmetries from the symmetry presolver and then computes orbits of variables with respect to the
25  * subgroup of the symmetry group that stabilizes the variables branched to 1. Then one can fix all variables in an
26  * orbit to 0 or 1 if one of the other variables in the orbit is fixed to 0 or 1, respectively. Different from Margot,
27  * the subgroup is obtained by filtering out generators that do not individually stabilize the variables branched to 1.
28  *
29  * @todo Possibly turn off propagator in subtrees.
30  * @todo Check application of conflict resolution.
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include "prop_orbitalfixing.h"
36 
37 #include <scip/pub_tree.h>
38 #include <scip/pub_table.h>
39 
40 #include "presol_symmetry.h"
41 #include "presol_symbreak.h"
42 
43 /* propagator properties */
44 #define PROP_NAME "orbitalfixing"
45 #define PROP_DESC "propagator for orbital fixing"
46 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask */
47 #define PROP_PRIORITY -1000000 /**< propagator priority */
48 #define PROP_FREQ 1 /**< propagator frequency */
49 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
50 
51 #define PROP_PRESOL_PRIORITY -1000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
52 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
53 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
54 
55 /* parameters */
56 #define DEFAULT_SYMCOMPTIMING 2 /**< timing of symmetry computation for orbital fixing
57  * (0 = before presolving, 1 = during presolving, 2 = at first call) */
58 #define DEFAULT_PERFORMPRESOLVING FALSE /**< Run orbital fixing during presolving? */
59 #define DEFAULT_ENABLEDAFTERRESTARTS FALSE /**< Run orbital fixing after a restart has occured? */
60 
61 
62 /* output table properties */
63 #define TABLE_NAME_ORBITALFIXING "orbitalfixing"
64 #define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"
65 #define TABLE_POSITION_ORBITALFIXING 7001 /**< the position of the statistics table */
66 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
67 
68 
69 /*
70  * Data structures
71  */
72 
73 /** propagator data for orbital branching */
74 struct SCIP_PropData
75 {
76  int npermvars; /**< pointer to store number of variables for permutations */
77  SCIP_VAR** permvars; /**< pointer to store variables on which permutations act */
78  SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */
79  int nperms; /**< pointer to store number of permutations */
80  int** perms; /**< pointer to store permutation generators as (nperms x npermvars) matrix */
81  SCIP_Bool enabled; /**< run orbital branching? */
82  SCIP_Bool performpresolving; /**< Run orbital fixing during presolving? */
83  SCIP_Bool enabledafterrestarts; /**< Run orbital fixing after a restart has occured? */
84  int symcomptiming; /**< timing of symmetry computation for orbital fixing
85  * (0 = before presolving, 1 = during presolving, 2 = at first call) */
86  int lastrestart; /**< last restart for which symmetries have been computed */
87  int nfixedzero; /**< number of variables fixed to 0 */
88  int nfixedone; /**< number of variables fixed to 1 */
89  SCIP_Longint nodenumber; /**< number of node where propagation has been last applied */
90 };
91 
92 
93 
94 /*
95  * Table callback methods
96  */
97 
98 /** table data */
99 struct SCIP_TableData
100 {
101  SCIP_PROPDATA* propdata; /** pass data of propagator for table output function */
102 };
103 
104 
105 /** output method of orbital fixing propagator statistics table to output file stream 'file' */
106 static
107 SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
108 {
109  SCIP_TABLEDATA* tabledata;
110 
111  assert( scip != NULL );
112  assert( table != NULL );
113 
114  tabledata = SCIPtableGetData(table);
115  assert( tabledata != NULL );
116  assert( tabledata->propdata != NULL );
117 
118  if ( tabledata->propdata->nperms > 0 )
119  {
120  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, "Orbital fixing :\n");
121  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
122  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
123  }
124 
125  return SCIP_OKAY;
126 }
127 
128 
129 /** destructor of statistics table to free user data (called when SCIP is exiting) */
130 static
131 SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
132 {
133  SCIP_TABLEDATA* tabledata;
134  tabledata = SCIPtableGetData(table);
135  assert( tabledata != NULL );
136 
137  SCIPfreeBlockMemory(scip, &tabledata);
138 
139  return SCIP_OKAY;
140 }
141 
142 /*
143  * Local methods
144  */
145 
146 
147 /** possibly get symmetries */
148 static
150  SCIP* scip, /**< SCIP pointer */
151  SCIP_PROPDATA* propdata /**< propagator data */
152  )
153 {
154  int v;
155 
156  assert( scip != NULL );
157  assert( propdata != NULL );
158 
159  if ( propdata->nperms < 0 || SCIPgetNRuns(scip) > propdata->lastrestart )
160  {
161  /* recompute symmetries after a restart */
162  if ( SCIPgetNRuns(scip) > propdata->lastrestart )
163  {
164  /* reset symmetry information */
165  if ( propdata->permvarmap != NULL )
166  {
167  SCIPhashmapFree(&propdata->permvarmap);
168  }
169  propdata->nperms = -1;
170  propdata->perms = NULL;
171  propdata->permvars = NULL;
172  propdata->npermvars = -1;
173  propdata->permvarmap = NULL;
174 
175  /* recompute symmetries and update restart counter */
177  &(propdata->npermvars), &(propdata->permvars), &(propdata->nperms), &(propdata->perms), NULL, NULL) );
178 
179  propdata->lastrestart = SCIPgetNRuns(scip);
180  }
181  else
182  {
184  &(propdata->npermvars), &(propdata->permvars), &(propdata->nperms), &(propdata->perms), NULL, NULL) );
185  }
186 
187  if ( propdata->nperms == 0 )
188  return SCIP_OKAY;
189 
190  /* create hashmap for storing the indices of variables */
191  assert( propdata->permvarmap == NULL );
192  SCIP_CALL( SCIPhashmapCreate(&propdata->permvarmap, SCIPblkmem(scip), propdata->npermvars) );
193 
194  /* insert variables */
195  for (v = 0; v < propdata->npermvars; ++v)
196  {
197  SCIP_CALL( SCIPhashmapInsertInt(propdata->permvarmap, propdata->permvars[v], v) );
198  }
199  }
200 
201  return SCIP_OKAY;
202 }
203 
204 /** perform orbital fixing
205  *
206  * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
207  * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
208  * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
209  * fixed.
210  */
211 static
213  SCIP* scip, /**< SCIP pointer */
214  SCIP_VAR** permvars, /**< variables */
215  int npermvars, /**< number of variables */
216  int* orbits, /**< array of non-trivial orbits */
217  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
218  int norbits, /**< number of orbits */
219  SCIP_Bool* infeasible, /**< pointer to store whether problem is infeasible */
220  int* nfixedzero, /**< pointer to store number of variables fixed to 0 */
221  int* nfixedone /**< pointer to store number of variables fixed to 1 */
222  )
223 {
224  SCIP_Bool tightened;
225  int i;
226 
227  assert( scip != NULL );
228  assert( permvars != NULL );
229  assert( orbits != NULL );
230  assert( orbitbegins != NULL );
231  assert( infeasible != NULL );
232  assert( nfixedzero != NULL );
233  assert( nfixedone != NULL );
234  assert( norbits > 0 );
235  assert( orbitbegins[0] == 0 );
236 
237  *infeasible = FALSE;
238  *nfixedzero = 0;
239  *nfixedone = 0;
240 
241  SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits.\n", norbits);
242 
243  /* check all orbits */
244  for (i = 0; i < norbits; ++i)
245  {
246  SCIP_Bool havefixedone = FALSE;
247  SCIP_Bool havefixedzero = FALSE;
248  SCIP_VAR* var;
249  int j;
250 
251  /* we only have nontrivial orbits */
252  assert( orbitbegins[i+1] - orbitbegins[i] >= 2 );
253 
254  /* check all variables in the orbit */
255  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
256  {
257  assert( 0 <= orbits[j] && orbits[j] < npermvars );
258  var = permvars[orbits[j]];
259  assert( var != NULL );
260 
261  /* check whether variable is not binary (and not implicit integer!) */
262  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
263  {
264  /* skip orbit if there are non-binary variables */
265  havefixedone = FALSE;
266  havefixedzero = FALSE;
267  break;
268  }
269 
270  /* if variable is fixed to 1 -> can fix all variables in orbit to 1 */
271  if ( SCIPvarGetLbLocal(var) > 0.5 )
272  havefixedone = TRUE;
273 
274  /* check for zero-fixed variables */
275  if ( SCIPvarGetUbLocal(var) < 0.5 )
276  havefixedzero = TRUE;
277  }
278 
279  /* check consistency */
280  if ( havefixedone && havefixedzero )
281  {
282  *infeasible = TRUE;
283  return SCIP_OKAY;
284  }
285 
286  /* fix all variables to 0 if there is one variable fixed to 0 */
287  if ( havefixedzero )
288  {
289  assert( ! havefixedone );
290 
291  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
292  {
293  assert( 0 <= orbits[j] && orbits[j] < npermvars );
294  var = permvars[orbits[j]];
295  assert( var != NULL );
296 
297  /* only variables that are not yet fixed to 0 */
298  if ( SCIPvarGetUbLocal(var) > 0.5 )
299  {
300  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 0.\n", SCIPvarGetName(var), orbits[j]);
301  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
302  /* due to aggregation, var might already be fixed to 1, so do not put assert here */
303 
304  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
305  SCIP_CALL( SCIPtightenVarUb(scip, var, 0.0, FALSE, infeasible, &tightened) );
306  if ( *infeasible )
307  return SCIP_OKAY;
308  if ( tightened )
309  ++(*nfixedzero);
310  }
311  }
312  }
313 
314  /* fix all variables to 1 if there is one variable fixed to 1 */
315  if ( havefixedone )
316  {
317  assert( ! havefixedzero );
318 
319  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
320  {
321  assert( 0 <= orbits[j] && orbits[j] < npermvars );
322  var = permvars[orbits[j]];
323  assert( var != NULL );
324 
325  /* only variables that are not yet fixed to 1 */
326  if ( SCIPvarGetLbLocal(var) < 0.5)
327  {
328  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 1.\n", SCIPvarGetName(var), orbits[j]);
329  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
330  /* due to aggregation, var might already be fixed to 0, so do not put assert here */
331 
332  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
333  SCIP_CALL( SCIPtightenVarLb(scip, var, 1.0, FALSE, infeasible, &tightened) );
334  if ( *infeasible )
335  return SCIP_OKAY;
336  if ( tightened )
337  ++(*nfixedone);
338  }
339  }
340  }
341  }
342 
343  return SCIP_OKAY;
344 }
345 
346 /** Get branching variables on the path to root */
347 static
349  SCIP* scip, /**< SCIP pointer */
350  int nvars, /**< number of variables */
351  SCIP_HASHMAP* varmap, /**< map of variables to indices in vars array */
352  SCIP_Shortbool* b1, /**< bitset marking the variables branched to 1 */
353  SCIP_Bool* success /**< pointer to store whether branching variables were computed successfully */
354  )
355 {
356  SCIP_NODE* node;
357 
358  assert( scip != NULL );
359  assert( varmap != NULL );
360  assert( b1 != NULL );
361  assert( success != NULL );
362 
363  *success = TRUE;
364 
365  /* get current node */
366  node = SCIPgetCurrentNode(scip);
367 
368 #ifdef SCIP_OUTPUT
369  SCIP_CALL( SCIPprintNodeRootPath(scip, node, NULL) );
370 #endif
371 
372  /* follow path to the root (in the root no domains were changed due to branching) */
373  while ( SCIPnodeGetDepth(node) != 0 )
374  {
375  SCIP_BOUNDCHG* boundchg;
376  SCIP_DOMCHG* domchg;
377  SCIP_VAR* branchvar;
378  int nboundchgs;
379  int i;
380 
381  /* get domain changes of current node */
382  domchg = SCIPnodeGetDomchg(node);
383 
384  /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
385  * cases domchg should not be NULL. */
386  if ( domchg != NULL )
387  {
388  /* loop through all bound changes */
389  nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
390  for (i = 0; i < nboundchgs; ++i)
391  {
392  /* get bound change info */
393  boundchg = SCIPdomchgGetBoundchg(domchg, i);
394  assert( boundchg != NULL );
395 
396  /* branching decisions have to be in the beginning of the bound change array */
398  break;
399 
400  /* get corresponding branching variable */
401  branchvar = SCIPboundchgGetVar(boundchg);
402 
403  /* we only consider binary variables */
404  if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
405  {
406  /* make sure that branching variable is known, since new binary variables may have
407  * been created meanwhile, e.g., by presol_inttobinary */
408  if ( ! SCIPhashmapExists(varmap, (void*) branchvar) )
409  {
410  *success = FALSE;
411  return SCIP_OKAY;
412  }
413 
414  if ( SCIPvarGetLbLocal(branchvar) > 0.5 )
415  {
416  int branchvaridx;
417 
418  branchvaridx = SCIPhashmapGetImageInt(varmap, (void*) branchvar);
419  assert( branchvaridx < nvars );
420  b1[branchvaridx] = TRUE;
421  }
422  }
423  }
424  }
425 
426  node = SCIPnodeGetParent(node);
427  }
428 
429  return SCIP_OKAY;
430 }
431 
432 
433 /** propagate orbital fixing */
434 static
436  SCIP* scip, /**< SCIP pointer */
437  SCIP_PROPDATA* propdata, /**< propagator data */
438  SCIP_Bool* infeasible, /**< pointer to store whether the node is detected to be infeasible */
439  int* nprop /**< pointer to store the number of propagations */
440  )
441 {
442  SCIP_Shortbool* activeperms;
443  SCIP_Shortbool* b1;
444  SCIP_Bool success = TRUE;
445  SCIP_VAR** permvars;
446  int* orbitbegins;
447  int* orbits;
448 #ifndef NDEBUG
449  SCIP_Real* permvarsobj;
450 #endif
451  int norbits;
452  int npermvars;
453  int** perms;
454  int nperms;
455  int p;
456  int v;
457 
458  assert( scip != NULL );
459  assert( propdata != NULL );
460  assert( infeasible != NULL );
461  assert( nprop != NULL );
462 
463  *infeasible = FALSE;
464  *nprop = 0;
465 
466  /* possibly get symmetries */
467  SCIP_CALL( getSymmetries(scip, propdata) );
468 
469  permvars = propdata->permvars;
470  npermvars = propdata->npermvars;
471  perms = propdata->perms;
472  nperms = propdata->nperms;
473 
474  /* return if there is no symmetry available */
475  if ( nperms == 0 )
476  return SCIP_OKAY;
477 
478  assert( propdata->permvars != NULL );
479  assert( propdata->npermvars > 0 );
480  assert( propdata->permvarmap != NULL );
481  assert( propdata->perms != NULL );
482 
483  SCIP_CALL( SCIPallocBufferArray(scip, &activeperms, nperms) );
484 
485  /* init bitset for marking variables branched to 1 */
486  SCIP_CALL( SCIPallocBufferArray(scip, &b1, npermvars) );
487  for (v = 0; v < npermvars; ++v)
488  b1[v] = FALSE;
489 
490  /* get branching variables */
491  SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, b1, &success) );
492 
493  if ( ! success )
494  {
495  SCIPfreeBufferArray(scip, &b1);
496  SCIPfreeBufferArray(scip, &activeperms);
497  return SCIP_OKAY;
498  }
499 
500 #ifndef NDEBUG
501  SCIP_CALL( SCIPgetPermvarsObjSymmetry(scip, &permvarsobj) );
502 #endif
503  assert( permvarsobj != NULL );
504 
505  /* filter out permutations that move variables that are fixed to different values */
506  for (p = 0; p < nperms; ++p)
507  {
508  assert( perms[p] != NULL );
509 
510  for (v = 0; v < npermvars; ++v)
511  {
512  int img;
513 
514  img = perms[p][v];
515 
516  if ( img != v )
517  {
518 #ifndef NDEBUG
519  SCIP_VAR* varv = permvars[v];
520  SCIP_VAR* varimg = permvars[img];
521 
522  /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
523  assert( SCIPvarGetType(varv) == SCIPvarGetType(varimg) ||
524  (SCIPvarIsBinary(varv) && SCIPvarIsBinary(varimg)) ||
526  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
527  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) ||
529  SCIPisEQ(scip, SCIPvarGetLbGlobal(varv), SCIPvarGetLbGlobal(varimg)) &&
530  SCIPisEQ(scip, SCIPvarGetUbGlobal(varv), SCIPvarGetUbGlobal(varimg))) );
531 #endif
532  assert( SCIPisEQ(scip, permvarsobj[v], permvarsobj[img]) );
533 
534  /* we are moving a variable branched to 1 to another variable */
535  if ( b1[v] && ! b1[img] )
536  break;
537 
538  /* Global variable fixings during the solving process might arise because parts of the tree are
539  * pruned. Since these fixings might be caused by orbital fixing, they can be in conflict with
540  * the symmetry handling decisions of orbital fixing in the part of the tree that is not pruned.
541  * Thus, we have to take global fixings into account when filtering out symmetries.
542  */
543  if ( (SCIPvarGetLbGlobal(permvars[v]) > 0.5 && SCIPvarGetLbGlobal(permvars[img]) < 0.5) ||
544  (SCIPvarGetLbGlobal(permvars[v]) < 0.5 && SCIPvarGetLbGlobal(permvars[img]) > 0.5) )
545  break;
546  }
547  }
548 
549  if ( v >= npermvars )
550  activeperms[p] = TRUE;
551  else
552  activeperms[p] = FALSE;
553  }
554 
555  SCIPfreeBufferArray(scip, &b1);
556 
557  /* compute orbits */
558  SCIP_CALL( SCIPallocBufferArray(scip, &orbits, npermvars) );
559  SCIP_CALL( SCIPallocBufferArray(scip, &orbitbegins, npermvars) );
560  SCIP_CALL( SCIPcomputeGroupOrbitsSymbreak(scip, permvars, npermvars, perms, nperms, activeperms, orbits, orbitbegins, &norbits) );
561 
562  if ( norbits > 0 )
563  {
564  int nfixedzero = 0;
565  int nfixedone = 0;
566 
567  SCIP_CALL( performOrbitalFixing(scip, permvars, npermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
568 
569  propdata->nfixedzero += nfixedzero;
570  propdata->nfixedone += nfixedone;
571  *nprop = nfixedzero + nfixedone;
572 
573  SCIPdebugMsg(scip, "Orbital fixings: %d 0s, %d 1s.\n", nfixedzero, nfixedone);
574  }
575 
576  SCIPfreeBufferArray(scip, &orbitbegins);
577  SCIPfreeBufferArray(scip, &orbits);
578  SCIPfreeBufferArray(scip, &activeperms);
579 
580  return SCIP_OKAY;
581 }
582 
583 
584 
585 
586 /*
587  * Callback methods of propagator
588  */
589 
590 
591 /** destructor of propagator to free user data (called when SCIP is exiting) */
592 static
593 SCIP_DECL_PROPFREE(propFreeOrbitalfixing)
594 { /*lint --e{715,818}*/
595  SCIP_PROPDATA* propdata;
596 
597  assert( prop != NULL );
598 
599  SCIPdebugMsg(scip, "Freeing propagator <%s> ...\n", SCIPpropGetName(prop));
600 
601  propdata = SCIPpropGetData(prop);
602  assert( propdata != NULL );
603 
604  SCIPfreeBlockMemory(scip, &propdata);
605 
606  return SCIP_OKAY;
607 }
608 
609 
610 /** initialization method of propagator (called after problem was transformed) */
611 static
612 SCIP_DECL_PROPINIT(propInitOrbitalfixing)
613 { /*lint --e{715}*/
614  SCIP_PROPDATA* propdata;
615  int usesymmetry;
616 
617  assert( prop != NULL );
618 
619  SCIPdebugMsg(scip, "Init propagator <%s> ...\n", SCIPpropGetName(prop));
620 
621  propdata = SCIPpropGetData(prop);
622  assert( propdata != NULL );
623 
624  /* check whether we should run */
625  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
626  if ( usesymmetry == (int) SYM_HANDLETYPE_ORBITALFIXING )
627  propdata->enabled = TRUE;
628  else
629  {
630  propdata->enabled = FALSE;
631  }
632 
633  return SCIP_OKAY;
634 }
635 
636 
637 /** deinitialization method of propagator (called before transformed problem is freed) */
638 static
639 SCIP_DECL_PROPEXIT(propExitOrbitalfixing)
640 { /*lint --e{715}*/
641  SCIP_PROPDATA* propdata;
642 
643  assert( prop != NULL );
644 
645  propdata = SCIPpropGetData(prop);
646  assert( propdata != NULL );
647 
648  if ( propdata->permvarmap != NULL )
649  {
650  SCIPhashmapFree(&propdata->permvarmap);
651  }
652 
653  /* reset propagator variables */
654  propdata->nodenumber = -1;
655  propdata->nfixedzero = 0;
656  propdata->nfixedone = 0;
657 
658  propdata->nperms = -1;
659  propdata->perms = NULL;
660  propdata->permvars = NULL;
661  propdata->npermvars = -1;
662  propdata->permvarmap = NULL;
663  propdata->lastrestart = 0;
664 
665  return SCIP_OKAY;
666 }
667 
668 
669 /** presolving initialization method of propagator (called when presolving is about to begin) */
670 static
671 SCIP_DECL_PROPINITPRE(propInitpreOrbitalfixing)
672 { /*lint --e{715}*/
673  SCIP_PROPDATA* propdata;
674 
675  assert( scip != NULL );
676  assert( prop != NULL );
677 
678  /* get data */
679  propdata = SCIPpropGetData(prop);
680  assert( propdata != NULL );
681 
682  /* possibly skip orbital fixing */
683  if ( ! propdata->enabled || propdata->nperms == 0 )
684  return SCIP_OKAY;
685 
686  /* stop, if problem has already been solved */
687  if ( SCIPgetStatus(scip) != SCIP_STATUS_UNKNOWN )
688  return SCIP_OKAY;
689 
690  /* run only if timing is correct */
691  assert( 0 <= propdata->symcomptiming && propdata->symcomptiming <= 2 );
692  if ( propdata->symcomptiming > 0 )
693  return SCIP_OKAY;
694 
695  assert( SCIPisTransformed(scip) );
696 
697  /* possibly get symmetries */
698  SCIP_CALL( getSymmetries(scip, propdata) );
699 
700  return SCIP_OKAY;
701 }
702 
703 
704 /** presolving method of propagator */
705 static
706 SCIP_DECL_PROPPRESOL(propPresolOrbitalFixing)
707 { /*lint --e{715}*/
708  SCIP_PROPDATA* propdata;
709  SCIP_Bool infeasible = FALSE;
710  int nprop = 0;
711 
712  assert( scip != NULL );
713  assert( nfixedvars != NULL );
714  assert( result != NULL );
715 
716  *result = SCIP_DIDNOTRUN;
717 
718  /* get data */
719  propdata = SCIPpropGetData(prop);
720  assert( propdata != NULL );
721 
722  /* check whether we run after a restart */
723  if ( propdata->enabled && ! propdata->enabledafterrestarts && SCIPgetNRuns(scip) > 1 )
724  propdata->enabled = FALSE;
725 
726  /* do not run if not enabled */
727  if ( ! propdata->enabled )
728  return SCIP_OKAY;
729 
730  /* run only if timing is correct */
731  assert( 0 <= propdata->symcomptiming && propdata->symcomptiming <= 2 );
732  if ( propdata->symcomptiming > 1 )
733  return SCIP_OKAY;
734 
735  /* run if presolving should be performed */
736  if ( propdata->performpresolving )
737  {
738  /* propagate */
739  *result = SCIP_DIDNOTFIND;
740 
741  SCIPdebugMsg(scip, "Presolving <%s>.\n", SCIPpropGetName(prop));
742  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
743  if ( infeasible )
744  *result = SCIP_CUTOFF;
745  else if ( nprop > 0 )
746  {
747  *result = SCIP_SUCCESS;
748  *nfixedvars += nprop;
749  }
750  }
751  else if ( propdata->symcomptiming == 1 )
752  {
753  /* otherwise compute symmetry if timing requests it */
754  SCIP_CALL( getSymmetries(scip, propdata) );
755  }
756 
757  return SCIP_OKAY;
758 }
759 
760 
761 /** execution method of propagator */
762 static
763 SCIP_DECL_PROPEXEC(propExecOrbitalfixing)
764 { /*lint --e{715}*/
765  SCIP_PROPDATA* propdata;
766  SCIP_Bool infeasible = FALSE;
767  SCIP_Longint nodenumber;
768  int nprop = 0;
769 
770  assert( scip != NULL );
771  assert( result != NULL );
772 
773  *result = SCIP_DIDNOTRUN;
774 
775  /* do not run if we are in the root or not yet solving */
776  if ( SCIPgetDepth(scip) <= 0 || SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
777  return SCIP_OKAY;
778 
779  /* do nothing if we are in a probing node */
780  if ( SCIPinProbing(scip) )
781  return SCIP_OKAY;
782 
783  /* get data */
784  propdata = SCIPpropGetData(prop);
785  assert( propdata != NULL );
786 
787  /* check whether we run after a restart */
788  if ( propdata->enabled && ! propdata->enabledafterrestarts && SCIPgetNRuns(scip) > 1 )
789  propdata->enabled = FALSE;
790 
791  /* do not run if not enabled */
792  if ( ! propdata->enabled )
793  return SCIP_OKAY;
794 
795  /* return if there is no symmetry available */
796  if ( propdata->nperms == 0 )
797  return SCIP_OKAY;
798 
799  /* return if we already ran in this node */
800  nodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
801  if ( nodenumber == propdata->nodenumber )
802  return SCIP_OKAY;
803  propdata->nodenumber = nodenumber;
804 
805  /* propagate */
806  *result = SCIP_DIDNOTFIND;
807 
808  SCIPdebugMsg(scip, "Propagating <%s>.\n", SCIPpropGetName(prop));
809  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
810  if ( infeasible )
811  *result = SCIP_CUTOFF;
812  else if ( nprop > 0 )
813  *result = SCIP_REDUCEDDOM;
814 
815  return SCIP_OKAY;
816 }
817 
818 
819 /** propagation conflict resolving method of propagator
820  *
821  * @todo Implement reverse propagation.
822  *
823  * Note that this is relatively difficult to obtain: One needs to include all bounds of variables to would lead to a
824  * different orbit in which the variables that was propagated lies. This includes all variables that are moved by the
825  * permutations which are involved in creating the orbit.
826  */
827 static
828 SCIP_DECL_PROPRESPROP(propRespropOrbitalfixing)
829 { /*lint --e{715,818}*/
830  assert( result != NULL );
831 
832  *result = SCIP_DIDNOTFIND;
833 
834  return SCIP_OKAY;
835 }
836 
837 
838 /** creates the orbitalfixing propagator and includes it in SCIP */
840  SCIP* scip /**< SCIP data structure */
841  )
842 {
843  SCIP_TABLEDATA* tabledata;
844  SCIP_PROPDATA* propdata;
845  SCIP_PROP* prop;
846 
847  /* create orbitalfixing propagator data */
848  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
849 
850  propdata->nodenumber = -1;
851  propdata->nfixedzero = 0;
852  propdata->nfixedone = 0;
853 
854  propdata->nperms = -1;
855  propdata->perms = NULL;
856  propdata->permvars = NULL;
857  propdata->npermvars = -1;
858  propdata->permvarmap = NULL;
859  propdata->lastrestart = 0;
860 
861  /* include propagator */
862  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecOrbitalfixing, propdata) );
863 
864  /* set callbacks */
865  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeOrbitalfixing) );
866  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitOrbitalfixing) );
867  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitOrbitalfixing) );
868  SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreOrbitalfixing) );
869  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropOrbitalfixing) );
871 
872  /* include table */
873  SCIP_CALL( SCIPallocBlockMemory(scip, &tabledata) );
874  tabledata->propdata = propdata;
876  NULL, tableFreeOrbitalfixing, NULL, NULL, NULL, NULL, tableOutputOrbitalfixing,
878 
879  /* add parameters */
881  "propagating/" PROP_NAME "/symcomptiming",
882  "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
883  &propdata->symcomptiming, TRUE, DEFAULT_SYMCOMPTIMING, 0, 2, NULL, NULL) );
884 
886  "propagating/" PROP_NAME "/performpresolving",
887  "Run orbital fixing during presolving?",
888  &propdata->performpresolving, TRUE, DEFAULT_PERFORMPRESOLVING, NULL, NULL) );
889 
891  "propagating/" PROP_NAME "/enabledafterrestarts",
892  "Run orbital fixing after a restart has occured?",
893  &propdata->enabledafterrestarts, TRUE, DEFAULT_ENABLEDAFTERRESTARTS, NULL, NULL) );
894 
895  return SCIP_OKAY;
896 }
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:349
#define NULL
Definition: def.h:246
static SCIP_DECL_PROPINIT(propInitOrbitalfixing)
#define PROP_PRESOL_PRIORITY
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5119
#define TABLE_POSITION_ORBITALFIXING
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:46
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:158
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:411
public methods for branch and bound tree
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17344
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7627
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16910
static SCIP_DECL_PROPRESPROP(propRespropOrbitalfixing)
static SCIP_DECL_PROPINITPRE(propInitpreOrbitalfixing)
#define FALSE
Definition: def.h:72
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2891
#define PROP_PRIORITY
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_RETCODE performOrbitalFixing(SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3009
SCIP_RETCODE SCIPcomputeGroupOrbitsSymbreak(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Shortbool *activeperms, int *orbits, int *orbitbegins, int *norbits)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5235
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
presolver for adding symmetry breaking constraints
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:610
#define PROP_TIMING
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:155
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3240
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7347
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17354
#define SYM_SPEC_BINARY
Definition: type_symmetry.h:34
#define PROP_DELAY
public methods for displaying statistic tables
static SCIP_DECL_PROPEXIT(propExitOrbitalfixing)
#define SYM_SPEC_INTEGER
Definition: type_symmetry.h:33
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:518
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:128
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
SCIP_RETCODE SCIPgetGeneratorsSymmetry(SCIP *scip, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed, SCIP_Bool recompute, int *npermvars, SCIP_VAR ***permvars, int *nperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2925
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7442
#define SCIP_Shortbool
Definition: def.h:77
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:341
#define SCIP_CALL(x)
Definition: def.h:358
static SCIP_DECL_PROPFREE(propFreeOrbitalfixing)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
#define DEFAULT_SYMCOMPTIMING
static SCIP_RETCODE getSymmetries(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_DECL_PROPPRESOL(propPresolOrbitalFixing)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *b1, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:253
#define SCIP_Bool
Definition: def.h:69
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16647
static SCIP_DECL_PROPEXEC(propExecOrbitalfixing)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:715
SCIP_RETCODE SCIPincludePropOrbitalfixing(SCIP *scip)
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16637
propagator for orbital fixing
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:16685
#define DEFAULT_PERFORMPRESOLVING
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
int SCIPgetNRuns(SCIP *scip)
#define PROP_PRESOL_MAXROUNDS
#define TABLE_NAME_ORBITALFIXING
#define PROP_FREQ
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:931
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
static SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:574
#define SYM_HANDLETYPE_ORBITALFIXING
Definition: type_symmetry.h:54
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:382
SCIP_RETCODE SCIPgetPermvarsObjSymmetry(SCIP *scip, SCIP_Real **permvarsobj)
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition: var.c:16677
#define DEFAULT_ENABLEDAFTERRESTARTS
presolver for storing symmetry information about current problem
#define PROP_DESC
#define SCIP_Real
Definition: def.h:157
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define TABLE_EARLIEST_ORBITALFIXING
SCIP_TABLEDATA * SCIPtableGetData(SCIP_TABLE *table)
Definition: table.c:278
#define PROP_PRESOLTIMING
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:237
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:779
#define SCIP_Longint
Definition: def.h:142
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16895
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
#define TABLE_DESC_ORBITALFIXING
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3098
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:317
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:269
#define PROP_NAME
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
struct SCIP_TableData SCIP_TABLEDATA
Definition: type_table.h:44
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:184