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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file 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 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 /* output table properties */
52 #define TABLE_NAME_ORBITALFIXING "orbitalfixing"
53 #define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"
54 #define TABLE_POSITION_ORBITALFIXING 7001 /**< the position of the statistics table */
55 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
56 
57 
58 /*
59  * Data structures
60  */
61 
62 /** propagator data for orbital branching */
63 struct SCIP_PropData
64 {
65  int npermvars; /**< pointer to store number of variables for permutations */
66  SCIP_VAR** permvars; /**< pointer to store variables on which permutations act */
67  SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */
68  int nperms; /**< pointer to store number of permutations */
69  int** perms; /**< pointer to store permutation generators as (nperms x npermvars) matrix */
70  SCIP_Bool enabled; /**< run orbital branching? */
71  int nfixedzero; /**< number of variables fixed to 0 */
72  int nfixedone; /**< number of variables fixed to 1 */
73  SCIP_Longint nodenumber; /**< number of node where propagation has been last applied */
74 };
75 
76 
77 
78 /*
79  * Table callback methods
80  */
81 
82 /** table data */
83 struct SCIP_TableData
84 {
85  SCIP_PROPDATA* propdata; /** pass data of propagator for table output function */
86 };
87 
88 
89 /** output method of orbital fixing propagator statistics table to output file stream 'file' */
90 static
91 SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
92 {
93  SCIP_TABLEDATA* tabledata;
94 
95  assert( scip != NULL );
96  assert( table != NULL );
97 
98  tabledata = SCIPtableGetData(table);
99  assert( tabledata != NULL );
100  assert( tabledata->propdata != NULL );
101 
102  if ( tabledata->propdata->enabled )
103  {
104  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, "Orbital fixing :\n");
105  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
106  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
107  }
108 
109  return SCIP_OKAY;
110 }
111 
112 
113 /** destructor of statistics table to free user data (called when SCIP is exiting) */
114 static
115 SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
116 {
117  SCIP_TABLEDATA* tabledata;
118  tabledata = SCIPtableGetData(table);
119  assert( tabledata != NULL );
120 
121  SCIPfreeBlockMemory(scip, &tabledata);
122 
123  return SCIP_OKAY;
124 }
125 
126 /*
127  * Local methods
128  */
129 
130 
131 /** perform orbital fixing
132  *
133  * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
134  * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
135  * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
136  * fixed.
137  */
138 static
140  SCIP* scip, /**< SCIP pointer */
141  SCIP_VAR** permvars, /**< variables */
142  int npermvars, /**< number of variables */
143  int* orbits, /**< array of non-trivial orbits */
144  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
145  int norbits, /**< number of orbits */
146  SCIP_Bool* infeasible, /**< pointer to store whether problem is infeasible */
147  int* nfixedzero, /**< pointer to store number of variables fixed to 0 */
148  int* nfixedone /**< pointer to store number of variables fixed to 1 */
149  )
150 {
151  SCIP_Bool tightened;
152  int i;
153 
154  assert( scip != NULL );
155  assert( permvars != NULL );
156  assert( orbits != NULL );
157  assert( orbitbegins != NULL );
158  assert( infeasible != NULL );
159  assert( nfixedzero != NULL );
160  assert( nfixedone != NULL );
161  assert( norbits > 0 );
162  assert( orbitbegins[0] == 0 );
163 
164  *infeasible = FALSE;
165  *nfixedzero = 0;
166  *nfixedone = 0;
167 
168  SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits.\n", norbits);
169 
170  /* check all orbits */
171  for (i = 0; i < norbits; ++i)
172  {
173  SCIP_Bool havefixedone = FALSE;
174  SCIP_Bool havefixedzero = FALSE;
175  SCIP_VAR* var;
176  int j;
177 
178  /* we only have nontrivial orbits */
179  assert( orbitbegins[i+1] - orbitbegins[i] >= 2 );
180 
181  /* check all variables in the orbit */
182  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
183  {
184  assert( 0 <= orbits[j] && orbits[j] < npermvars );
185  var = permvars[orbits[j]];
186  assert( var != NULL );
187 
188  /* check whether variable is not binary (and not implicit integer!) */
189  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
190  {
191  /* skip orbit if there are non-binary variables */
192  havefixedone = FALSE;
193  havefixedzero = FALSE;
194  break;
195  }
196 
197  /* if variable is fixed to 1 -> can fix all variables in orbit to 1 */
198  if ( SCIPvarGetLbLocal(var) > 0.5 )
199  havefixedone = TRUE;
200 
201  /* check for zero-fixed variables */
202  if ( SCIPvarGetUbLocal(var) < 0.5 )
203  havefixedzero = TRUE;
204  }
205 
206  /* check consistency */
207  if ( havefixedone && havefixedzero )
208  {
209  *infeasible = TRUE;
210  return SCIP_OKAY;
211  }
212 
213  /* fix all variables to 0 if there is one variable fixed to 0 */
214  if ( havefixedzero )
215  {
216  assert( ! havefixedone );
217 
218  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
219  {
220  assert( 0 <= orbits[j] && orbits[j] < npermvars );
221  var = permvars[orbits[j]];
222  assert( var != NULL );
223 
224  /* only variables that are not yet fixed to 0 */
225  if ( SCIPvarGetUbLocal(var) > 0.5 )
226  {
227  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 0.\n", SCIPvarGetName(var), orbits[j]);
228  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
229  /* due to aggregation, var might already be fixed to 1, so do not put assert here */
230 
231  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
232  SCIP_CALL( SCIPtightenVarUb(scip, var, 0.0, FALSE, infeasible, &tightened) );
233  if ( *infeasible )
234  return SCIP_OKAY;
235  if ( tightened )
236  ++(*nfixedzero);
237  }
238  }
239  }
240 
241  /* fix all variables to 1 if there is one variable fixed to 1 */
242  if ( havefixedone )
243  {
244  assert( ! havefixedzero );
245 
246  for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
247  {
248  assert( 0 <= orbits[j] && orbits[j] < npermvars );
249  var = permvars[orbits[j]];
250  assert( var != NULL );
251 
252  /* only variables that are not yet fixed to 1 */
253  if ( SCIPvarGetLbLocal(var) < 0.5)
254  {
255  SCIPdebugMsg(scip, "can fix <%s> (index %d) to 1.\n", SCIPvarGetName(var), orbits[j]);
256  assert( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY );
257  /* due to aggregation, var might already be fixed to 0, so do not put assert here */
258 
259  /* do not use SCIPinferBinvarProp(), since conflict analysis is not valid */
260  SCIP_CALL( SCIPtightenVarLb(scip, var, 1.0, FALSE, infeasible, &tightened) );
261  if ( *infeasible )
262  return SCIP_OKAY;
263  if ( tightened )
264  ++(*nfixedone);
265  }
266  }
267  }
268  }
269 
270  return SCIP_OKAY;
271 }
272 
273 /** Get branching variables on the path to root */
274 static
276  SCIP* scip, /**< SCIP pointer */
277  int nvars, /**< number of variables */
278  SCIP_HASHMAP* varmap, /**< map of variables to indices in vars array */
279  SCIP_Shortbool* b1, /**< bitset marking the variables branched to 1 */
280  SCIP_Bool* success /**< pointer to store whether branching variables were computed successfully */
281  )
282 {
283  SCIP_NODE* node;
284 
285  assert( scip != NULL );
286  assert( varmap != NULL );
287  assert( b1 != NULL );
288  assert( success != NULL );
289 
290  *success = TRUE;
291 
292  /* get current node */
293  node = SCIPgetCurrentNode(scip);
294 
295 #ifdef SCIP_OUTPUT
296  SCIP_CALL( SCIPprintNodeRootPath(scip, node, NULL) );
297 #endif
298 
299  /* follow path to the root (in the root no domains were changed due to branching) */
300  while ( SCIPnodeGetDepth(node) != 0 )
301  {
302  SCIP_BOUNDCHG* boundchg;
303  SCIP_DOMCHG* domchg;
304  SCIP_VAR* branchvar;
305  int nboundchgs;
306  int i;
307 
308  /* get domain changes of current node */
309  domchg = SCIPnodeGetDomchg(node);
310  assert( domchg != NULL );
311 
312  /* loop through all bound changes */
313  nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
314  for (i = 0; i < nboundchgs; ++i)
315  {
316  /* get bound change info */
317  boundchg = SCIPdomchgGetBoundchg(domchg, i);
318  assert( boundchg != 0 );
319 
320  /* branching decisions have to be in the beginning of the bound change array */
322  break;
323 
324  /* get corresponding branching variable */
325  branchvar = SCIPboundchgGetVar(boundchg);
326 
327  /* we only consider binary variables */
328  if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
329  {
330  /* make sure that branching variable is known, since new binary variables may have
331  * been created meanwhile, e.g., by presol_inttobinary */
332  if ( ! SCIPhashmapExists(varmap, (void*) branchvar) )
333  {
334  *success = FALSE;
335  return SCIP_OKAY;
336  }
337 
338 
339  if ( SCIPvarGetLbLocal(branchvar) > 0.5 )
340  {
341  int branchvaridx;
342 
343  branchvaridx = (int) (size_t) SCIPhashmapGetImage(varmap, (void*) branchvar);
344  assert( branchvaridx < nvars );
345  b1[branchvaridx] = TRUE;
346  }
347  }
348  }
349 
350  node = SCIPnodeGetParent(node);
351  }
352 
353  return SCIP_OKAY;
354 }
355 
356 
357 /** propagate orbital fixing */
358 static
360  SCIP* scip, /**< SCIP pointer */
361  SCIP_PROPDATA* propdata, /**< propagator data */
362  SCIP_Bool* infeasible, /**< pointer to store whether the node is detected to be infeasible */
363  int* nprop /**< pointer to store the number of propagations */
364  )
365 {
366  SCIP_Shortbool* activeperms;
367  SCIP_Shortbool* b1;
368  SCIP_Bool success = TRUE;
369  SCIP_VAR** permvars;
370  int* orbitbegins;
371  int* orbits;
372 #ifndef NDEBUG
373  SCIP_Real* permvarsobj;
374 #endif
375  int norbits;
376  int npermvars;
377  int** perms;
378  int nperms;
379  int p;
380  int v;
381 
382  assert( scip != NULL );
383  assert( propdata != NULL );
384  assert( infeasible != NULL );
385  assert( nprop != NULL );
386 
387  *infeasible = FALSE;
388  *nprop = 0;
389 
390  assert( propdata->permvars != NULL );
391  assert( propdata->npermvars > 0 );
392  assert( propdata->permvarmap != NULL );
393  assert( propdata->perms != NULL );
394 
395  permvars = propdata->permvars;
396  npermvars = propdata->npermvars;
397  perms = propdata->perms;
398  nperms = propdata->nperms;
399 
400  SCIP_CALL( SCIPallocBufferArray(scip, &activeperms, nperms) );
401 
402  /* init bitset for marking variables branched to 1 */
403  SCIP_CALL( SCIPallocBufferArray(scip, &b1, npermvars) );
404  for (v = 0; v < npermvars; ++v)
405  b1[v] = FALSE;
406 
407  /* get branching variables */
408  SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, b1, &success) );
409 
410  if ( ! success )
411  {
412  SCIPfreeBufferArray(scip, &b1);
413  SCIPfreeBufferArray(scip, &activeperms);
414  return SCIP_OKAY;
415  }
416 
417 #ifndef NDEBUG
418  SCIP_CALL( SCIPgetPermvarsObjSymmetry(scip, &permvarsobj) );
419 #endif
420  assert( permvarsobj != NULL );
421 
422  /* filter out permutations that move variables that are fixed to different values */
423  for (p = 0; p < nperms; ++p)
424  {
425  assert( perms[p] != NULL );
426 
427  for (v = 0; v < npermvars; ++v)
428  {
429  int img;
430 
431  img = perms[p][v];
432 
433  if ( img != v )
434  {
435  assert( SCIPvarGetType(permvars[v]) == SCIPvarGetType(permvars[img]) );
436  assert( SCIPisEQ(scip, permvarsobj[v], permvarsobj[img]) );
437 
438  /* we are moving a variable branched to 1 to another variable */
439  if ( b1[v] && ! b1[img] )
440  break;
441  }
442  }
443 
444  if ( v >= npermvars )
445  activeperms[p] = TRUE;
446  else
447  activeperms[p] = FALSE;
448  }
449 
450  SCIPfreeBufferArray(scip, &b1);
451 
452  /* compute orbits */
453  SCIP_CALL( SCIPallocBufferArray(scip, &orbits, npermvars) );
454  SCIP_CALL( SCIPallocBufferArray(scip, &orbitbegins, npermvars) );
455  SCIP_CALL( SCIPcomputeGroupOrbitsSymbreak(scip, permvars, npermvars, perms, nperms, activeperms, orbits, orbitbegins, &norbits) );
456 
457  SCIPfreeBufferArray(scip, &activeperms);
458 
459  if ( norbits > 0 )
460  {
461  int nfixedzero = 0;
462  int nfixedone = 0;
463 
464  SCIP_CALL( performOrbitalFixing(scip, permvars, npermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
465 
466  propdata->nfixedzero += nfixedzero;
467  propdata->nfixedone += nfixedone;
468  *nprop = nfixedzero + nfixedone;
469 
470  SCIPdebugMsg(scip, "Orbital fixings: %d 0s, %d 1s.\n", nfixedzero, nfixedone);
471  }
472 
473  SCIPfreeBufferArray(scip, &orbitbegins);
474  SCIPfreeBufferArray(scip, &orbits);
475 
476  return SCIP_OKAY;
477 }
478 
479 
480 
481 
482 /*
483  * Callback methods of propagator
484  */
485 
486 
487 /** destructor of propagator to free user data (called when SCIP is exiting) */
488 static
489 SCIP_DECL_PROPFREE(propFreeOrbitalfixing)
490 { /*lint --e{715,818}*/
491  SCIP_PROPDATA* propdata;
492 
493  assert( prop != NULL );
494 
495  SCIPdebugMsg(scip, "Freeing propagator <%s> ...\n", SCIPpropGetName(prop));
496 
497  propdata = SCIPpropGetData(prop);
498  assert( propdata != NULL );
499 
500  SCIPfreeBlockMemory(scip, &propdata);
501 
502  return SCIP_OKAY;
503 }
504 
505 
506 /** initialization method of propagator (called after problem was transformed) */
507 static
508 SCIP_DECL_PROPINIT(propInitOrbitalfixing)
509 { /*lint --e{715}*/
510  SCIP_PROPDATA* propdata;
511  int usesymmetry;
512 
513  assert( prop != NULL );
514 
515  SCIPdebugMsg(scip, "Init propagator <%s> ...\n", SCIPpropGetName(prop));
516 
517  propdata = SCIPpropGetData(prop);
518  assert( propdata != NULL );
519 
520  /* check whether we should run */
521  SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) );
522  if ( usesymmetry == (int) SYM_HANDLETYPE_ORBITALFIXING )
523  propdata->enabled = TRUE;
524  else
525  {
526  propdata->enabled = FALSE;
527  }
528 
529  if ( propdata->enabled )
530  {
531  /* register presolver for symmetry information, work on binary variables while fixing integer variables */
532  SCIP_CALL( SCIPregisterSymmetry(scip, SYM_HANDLETYPE_ORBITALFIXING, SYM_SPEC_BINARY, SYM_SPEC_INTEGER) );
533  }
534 
535  return SCIP_OKAY;
536 }
537 
538 
539 /** deinitialization method of propagator (called before transformed problem is freed) */
540 static
541 SCIP_DECL_PROPEXIT(propExitOrbitalfixing)
542 { /*lint --e{715}*/
543  SCIP_PROPDATA* propdata;
544 
545  assert( prop != NULL );
546 
547  propdata = SCIPpropGetData(prop);
548  assert( propdata != NULL );
549 
550  if ( propdata->permvarmap != NULL )
551  {
552  SCIPhashmapFree(&propdata->permvarmap);
553  }
554 
555  /* reset propagator variables */
556  propdata->nodenumber = -1;
557  propdata->nfixedzero = 0;
558  propdata->nfixedone = 0;
559 
560  propdata->permvars = NULL;
561  propdata->npermvars = -1;
562  propdata->permvarmap = NULL;
563 
564  return SCIP_OKAY;
565 }
566 
567 
568 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
569 static
570 SCIP_DECL_PROPINITSOL(propInitsolOrbitalfixing)
571 { /*lint --e{715}*/
572  SCIP_PROPDATA* propdata;
573 
574  assert( scip != NULL );
575  assert( prop != NULL );
576 
577  /* get data */
578  propdata = SCIPpropGetData(prop);
579  assert( propdata != NULL );
580 
581  /* possibly skip orbital fixing */
582  if ( ! propdata->enabled )
583  return SCIP_OKAY;
584 
585  /* stop, if problem has already been solved */
587  return SCIP_OKAY;
588 
589  if ( SCIPisStopped(scip) )
590  return SCIP_OKAY;
591 
592  assert( SCIPisTransformed(scip) );
593 
594  /* possibly get symmetries */
595  if ( propdata->npermvars < 0 )
596  {
597  SCIP_CALL( SCIPgetGeneratorsSymmetry(scip, &(propdata->npermvars), &(propdata->permvars), &(propdata->nperms), &(propdata->perms), NULL) );
598 
599  if ( propdata->nperms <= 0 )
600  {
601  /* Skip orbital fixing, since no symmetries were found. */
602  propdata->enabled = FALSE;
603  }
604  else
605  {
606  int j;
607 
608  /* create hashmap for storing the indices of variables */
609  assert( propdata->permvarmap == NULL );
610  SCIP_CALL( SCIPhashmapCreate(&propdata->permvarmap, SCIPblkmem(scip), propdata->npermvars) );
611 
612  /* insert variables */
613  for (j = 0; j < propdata->npermvars; ++j)
614  {
615  SCIP_CALL( SCIPhashmapInsert(propdata->permvarmap, propdata->permvars[j], (void*) (size_t) j) );
616  }
617  }
618  }
619 
620  return SCIP_OKAY;
621 }
622 
623 
624 /** execution method of propagator */
625 static
626 SCIP_DECL_PROPEXEC(propExecOrbitalfixing)
627 { /*lint --e{715}*/
628  SCIP_PROPDATA* propdata;
629  SCIP_Bool infeasible = FALSE;
630  SCIP_Longint nodenumber;
631  int nprop = 0;
632 
633  assert( scip != NULL );
634  assert( result != NULL );
635 
636  *result = SCIP_DIDNOTRUN;
637 
638  /* do not run if we are in the root or not yet solving */
640  return SCIP_OKAY;
641 
642  /* do nothing if we are in a probing node */
643  if ( SCIPinProbing(scip) )
644  return SCIP_OKAY;
645 
646  /* do not run after a restart */
647  /* @todo recompute symmetries after a restart */
648  if ( SCIPgetNRuns(scip) > 1 )
649  return SCIP_OKAY;
650 
651  /* get data */
652  propdata = SCIPpropGetData(prop);
653  assert( propdata != NULL );
654 
655  /* do not run if not enabled */
656  if ( ! propdata->enabled )
657  return SCIP_OKAY;
658 
659  /* return if there is no symmetry available */
660  if ( propdata->npermvars == 0 || propdata->permvars == NULL )
661  return SCIP_OKAY;
662 
663  /* return if we already ran in this node */
665  if ( nodenumber == propdata->nodenumber )
666  return SCIP_OKAY;
667  propdata->nodenumber = nodenumber;
668 
669  /* propagate */
670  *result = SCIP_DIDNOTFIND;
671 
672  SCIPdebugMsg(scip, "Propagating <%s>.\n", SCIPpropGetName(prop));
673  SCIP_CALL( propagateOrbitalFixing(scip, propdata, &infeasible, &nprop) );
674  if ( infeasible )
675  *result = SCIP_CUTOFF;
676  else if ( nprop > 0 )
677  *result = SCIP_REDUCEDDOM;
678 
679  return SCIP_OKAY;
680 }
681 
682 
683 /** propagation conflict resolving method of propagator
684  *
685  * @todo Implement reverse propagation.
686  *
687  * Note that this is relatively difficult to obtain: One needs to include all bounds of variables to would lead to a
688  * different orbit in which the variables that was propagated lies. This includes all variables that are moved by the
689  * permutations which are involved in creating the orbit.
690  */
691 static
692 SCIP_DECL_PROPRESPROP(propRespropOrbitalfixing)
693 { /*lint --e{715,818}*/
694  assert( result != NULL );
695 
696  *result = SCIP_DIDNOTFIND;
697 
698  return SCIP_OKAY;
699 }
700 
701 
702 /** creates the orbitalfixing propagator and includes it in SCIP */
704  SCIP* scip /**< SCIP data structure */
705  )
706 {
707  SCIP_TABLEDATA* tabledata;
708  SCIP_PROPDATA* propdata;
709  SCIP_PROP* prop;
710 
711  /* create orbitalfixing propagator data */
712  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
713 
714  propdata->nodenumber = -1;
715  propdata->nfixedzero = 0;
716  propdata->nfixedone = 0;
717 
718  propdata->permvars = NULL;
719  propdata->npermvars = -1;
720  propdata->permvarmap = NULL;
721 
722  /* include propagator */
723  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecOrbitalfixing, propdata) );
724 
725  /* set callbacks */
726  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeOrbitalfixing) );
727  SCIP_CALL( SCIPsetPropInit(scip, prop, propInitOrbitalfixing) );
728  SCIP_CALL( SCIPsetPropExit(scip, prop, propExitOrbitalfixing) );
729  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolOrbitalfixing) );
730  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropOrbitalfixing) );
731 
732  /* include table */
733  SCIP_CALL( SCIPallocBlockMemory(scip, &tabledata) );
734  tabledata->propdata = propdata;
736  NULL, tableFreeOrbitalfixing, NULL, NULL, NULL, NULL, tableOutputOrbitalfixing,
738 
739  return SCIP_OKAY;
740 }
static SCIP_DECL_PROPINIT(propInitOrbitalfixing)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22517
#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.c:9452
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
public methods for branch and bound tree
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7620
static SCIP_DECL_PROPRESPROP(propRespropOrbitalfixing)
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
#define PROP_PRIORITY
#define TRUE
Definition: def.h:63
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 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.c:22633
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
presolver for adding symmetry breaking constraints
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7350
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1017
#define PROP_TIMING
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
#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.c:928
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46725
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7435
#define SCIP_Shortbool
Definition: def.h:69
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip.c:4451
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_DECL_PROPFREE(propFreeOrbitalfixing)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
SCIP_RETCODE SCIPregisterSymmetry(SCIP *scip, SYM_HANDLETYPE symtype, SYM_SPEC type, SYM_SPEC fixedtype)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *b1, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip.c:7727
#define SCIP_Bool
Definition: def.h:61
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16579
static SCIP_DECL_PROPEXEC(propExecOrbitalfixing)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SCIP_RETCODE SCIPincludePropOrbitalfixing(SCIP *scip)
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition: var.c:16569
propagator for orbital fixing
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:16617
static SCIP_DECL_PROPINITSOL(propInitsolOrbitalfixing)
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
int SCIPgetNRuns(SCIP *scip)
Definition: scip.c:42044
#define TABLE_NAME_ORBITALFIXING
#define PROP_FREQ
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
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.c:41814
#define SYM_HANDLETYPE_ORBITALFIXING
Definition: type_symmetry.h:54
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip.c:7856
SCIP_RETCODE SCIPgetPermvarsObjSymmetry(SCIP *scip, SCIP_Real **permvarsobj)
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition: var.c:16609
presolver for storing symmetry information about current problem
#define PROP_DESC
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip.c:7759
#define SCIP_Real
Definition: def.h:149
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define TABLE_EARLIEST_ORBITALFIXING
SCIP_TABLEDATA * SCIPtableGetData(SCIP_TABLE *table)
Definition: table.c:241
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7711
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
#define SCIP_Longint
Definition: def.h:134
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define TABLE_DESC_ORBITALFIXING
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip.c:7743
#define PROP_NAME
SCIP_RETCODE SCIPgetGeneratorsSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, int *nperms, int ***perms, SCIP_Real *log10groupsize)
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.c:7658