Scippy

SCIP

Solving Constraint Integer Programs

symmetry_lexred.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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file symmetry_lexred.c
26  * @ingroup OTHER_CFILES
27  * @brief methods for handling symmetries by dynamic lexicographic ordering reduction
28  * @author Jasper van Doornmalen
29  *
30  * This implements lexicographic reduction, which generalizes symresack propagation to work for non-binary variable
31  * domains, and is dynamified. Whereas static lexicographic reduction propagates that a vector \f$x\f$ is
32  * lexicographically larger than its permuted counterpart (i.e., \f$x \succeq \gamma(x)\f$ with \f$\succeq\f$ being
33  * standard elementwise lexicographic comparison), the dynamic variant determines the variable vector ordering
34  * dynamically. Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables
35  * branched on from the root node to the focus node.
36  * Thus, in node \f$\beta\f$, we propagate \f$\sigma_\beta(x) \succeq \sigma_\beta(\gamma(x))\f$,
37  * where \f$\sigma_\beta(\cdot)\f$ permutes and restricts the variable vector such that it corresponds to the branched
38  * variables in the order from the rooted path to \f$\beta\f$.
39  *
40  * See Section 4.1 and Example 11 in [vD,H]:@n
41  * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023,
42  * https://doi.org/10.48550/arXiv.2211.01295.
43  *
44  * For dynamic lexicographic reduction, it is crucial that the vectors \f$\sigma_\beta(x)\f$ are the branching
45  * variables up to node \f$\beta\f$ in the given order. Since SCIP can change the tree structure during solving
46  * (re-writing history), we store the original branching decisions at the moment they are made. See event_shadowtree.c .
47  */
48 
49 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
50 
51 #include "blockmemshell/memory.h"
52 #include "scip/symmetry_lexred.h"
53 #include "scip/pub_cons.h"
54 #include "scip/pub_message.h"
55 #include "scip/pub_var.h"
56 #include "scip/struct_var.h"
57 #include "scip/type_var.h"
58 #include "scip/scip.h"
59 #include "scip/scip_branch.h"
60 #include "scip/scip_conflict.h"
61 #include "scip/scip_cons.h"
62 #include "scip/scip_copy.h"
63 #include "scip/scip_cut.h"
64 #include "scip/scip_general.h"
65 #include "scip/scip_lp.h"
66 #include "scip/scip_mem.h"
67 #include "scip/scip_message.h"
68 #include "scip/scip_numerics.h"
69 #include "scip/scip_param.h"
70 #include "scip/scip_prob.h"
71 #include "scip/scip_probing.h"
72 #include "scip/scip_sol.h"
73 #include "scip/scip_var.h"
74 #include "scip/debug.h"
75 #include "scip/struct_scip.h"
76 #include "scip/struct_mem.h"
77 #include "scip/struct_tree.h"
78 #include "scip/symmetry.h"
79 #include "scip/event_shadowtree.h"
80 #include <string.h>
81 
82 
83 /*
84  * Data structures
85  */
86 
87 
88 /** data per permutation for lexicographic reduction propagator */
90 {
91  SCIP_Bool isdynamic; /**< whether permutation shall be propagated with dynamic variable order */
92  SCIP_VAR** vars; /**< variables affected by permutation */
93  int nvars; /**< number of variables */
94  int* perm; /**< permutation for lexicographic reduction */
95  int* invperm; /**< inverse permutation */
96  SCIP_HASHMAP* varmap; /**< map of variables to indices in vars array */
97  SYM_SYMTYPE symtype; /**< type of symmetries in perm */
98  SCIP_Real* vardomaincenter; /**< array of centers of variable domains */
99 };
100 typedef struct LexRedPermData LEXDATA;
101 
102 
103 /** data for dynamic lexicographic reduction propagator */
104 struct SCIP_LexRedData
105 {
106  SCIP_EVENTHDLR* shadowtreeeventhdlr;/**< eventhandler for the shadow tree data structure */
107  SCIP_HASHMAP* symvarmap; /**< map of variables affected by some permutation handled by a LEXDATA */
108  int nsymvars; /**< number of variables in symvarmap */
109  LEXDATA** lexdatas; /**< array of pointers to individual LEXDATA's */
110  int nlexdatas; /**< number of datas in array */
111  int maxnlexdatas; /**< allocated datas array size */
112  int nred; /**< total number of reductions */
113  int ncutoff; /**< total number of cutoffs */
114  SCIP_Bool hasdynamicperm; /**< whether there exists a permutation that is treated dynamically */
115  SCIP_Bool treewarninggiven; /**< whether a warning is given for missing nodes in shadowtree */
116 };
117 
118 
119 /** to store branch-and-bound tree paths, (depth, index)-information per variable in rooted path */
121 {
122  int nodedepth; /**< depth of var domain change */
123  int index; /**< index of var domain change on node at depth */
124 };
126 
127 
128 /** auxiliary struct to pass branch-and-bound tree information to sort function */
130 {
131  NODEDEPTHBRANCHINDEX* nodedepthbranchindices; /**< pointer to branch-and-bound tree information */
132  SCIP_LEXREDDATA* masterdata; /**< pointer to global data for lexicographic reduction propagator */
133  SCIP_VAR** vars; /**< pointer to variable array */
134 };
136 
137 
138 /*
139  * Local methods
140  */
141 
142 /** frees dynamic lexicographic reduction propagator data */
143 static
145  SCIP* scip, /**< SCIP data structure */
146  LEXDATA** lexdata /**< pointer to individual lexicographic reduction propagator datas */
147  )
148 {
149  SCIP_Bool issigned;
150  int permlen;
151  int i;
152 
153  assert( scip != NULL );
154  assert( lexdata != NULL );
155  assert( (*lexdata) != NULL );
156 
157  if ( (*lexdata)->symtype == SYM_SYMTYPE_SIGNPERM )
158  {
159  issigned = TRUE;
160  permlen = 2 * (*lexdata)->nvars;
161  }
162  else
163  {
164  issigned = FALSE;
165  permlen = (*lexdata)->nvars;
166  }
167 
168  if ( (*lexdata)->nvars > 0 )
169  {
170  assert( (*lexdata)->invperm != NULL );
171  assert( (*lexdata)->perm != NULL );
172  assert( (*lexdata)->vars != NULL );
173 
174  /* free hashmap */
175  if ( (*lexdata)->isdynamic )
176  {
177  assert( (*lexdata)->varmap != NULL );
178  SCIPhashmapFree(&((*lexdata)->varmap));
179  }
180 
181  /* release variables */
182  for (i = 0; i < (*lexdata)->nvars; ++i)
183  {
184  SCIP_CALL( SCIPreleaseVar(scip, &(*lexdata)->vars[i]) );
185  }
186 
187  SCIPfreeBlockMemoryArray(scip, &(*lexdata)->invperm, permlen);
188  SCIPfreeBlockMemoryArray(scip, &(*lexdata)->perm, permlen);
189  SCIPfreeBlockMemoryArray(scip, &(*lexdata)->vars, (*lexdata)->nvars);
190 
191  if ( issigned )
192  {
193  SCIPfreeBlockMemoryArray(scip, &(*lexdata)->vardomaincenter, (*lexdata)->nvars);
194  }
195  else
196  {
197  assert( (*lexdata)->vardomaincenter == NULL );
198  }
199  }
200 #ifndef NDEBUG
201  else
202  {
203  assert( (*lexdata)->nvars == 0 );
204  assert( (*lexdata)->invperm == NULL );
205  assert( (*lexdata)->vardomaincenter == NULL );
206  assert( (*lexdata)->perm == NULL );
207  assert( (*lexdata)->vars == NULL );
208  assert( (*lexdata)->varmap == NULL );
209  }
210 #endif
211  SCIPfreeBlockMemory(scip, lexdata);
212 
213  return SCIP_OKAY;
214 }
215 
216 
217 /** creates dynamic lexicographic reduction propagator data
218  *
219  * Fixed points are removed.
220  */
221 static
223  SCIP* scip, /**< SCIP data structure */
224  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
225  LEXDATA** lexdata, /**< pointer to store data for permutation to be added */
226  SCIP_VAR*const* vars, /**< input variables of the lexicographic reduction propagator */
227  int nvars, /**< input number of variables of the lexicographic reduction propagator */
228  int* perm, /**< input permutation of the lexicographic reduction propagator */
229  SYM_SYMTYPE symtype, /**< type of symmetries in perm */
230  SCIP_Real* permvardomaincenter, /**< array containing center point for each variable domain */
231  SCIP_Bool usedynamicorder, /**< whether a dynamic variable order shall be used */
232  SCIP_Bool* success /**< to store whether the component is successfully added */
233  )
234 {
235  SCIP_VAR* var;
236  SCIP_Bool issignedperm;
237  int* indexcorrection;
238  int naffectedvariables;
239  int permlen;
240  int i;
241  int j;
242 
243  assert( scip != NULL );
244  assert( masterdata != NULL );
245  assert( lexdata != NULL );
246  assert( vars != NULL );
247  assert( nvars >= 0 );
248  assert( perm != NULL );
249  assert( symtype == SYM_SYMTYPE_PERM || permvardomaincenter != NULL );
250  assert( success != NULL );
251  assert( SCIPisTransformed(scip) );
252  assert( masterdata->shadowtreeeventhdlr != NULL );
253 
254  *success = TRUE;
255  issignedperm = symtype == SYM_SYMTYPE_PERM ? FALSE : TRUE;
256 
257  /* initialize the data structures */
258  SCIP_CALL( SCIPallocBlockMemory(scip, lexdata) );
259  (*lexdata)->symtype = symtype;
260 
261  (*lexdata)->isdynamic = usedynamicorder;
262 
263  /* remove fixed points */
264  naffectedvariables = 0;
265  SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, nvars) );
266  for (i = 0; i < nvars; ++i)
267  {
268  if ( perm[i] == i )
269  indexcorrection[i] = -1; /* fixed points get an entry < 0 in the indexcorrection array */
270  else
271  indexcorrection[i] = naffectedvariables++;
272  }
273 
274  /* do nothing if reductions would be trivial */
275  if ( naffectedvariables <= 0 )
276  {
277  assert( naffectedvariables == 0 );
278  SCIPfreeBufferArray(scip, &indexcorrection);
279 
280  *success = FALSE;
281  SCIPfreeBlockMemory(scip, lexdata);
282  return SCIP_OKAY;
283  }
284 
285  /* require that the shadowtree is active if dynamic propagation is used */
286  if ( usedynamicorder )
287  {
288  masterdata->hasdynamicperm = TRUE;
289 
290  SCIP_CALL( SCIPactivateShadowTree(scip, masterdata->shadowtreeeventhdlr) );
291  }
292 
293  /* initialize variable arrays */
294  (*lexdata)->nvars = naffectedvariables;
295  permlen = issignedperm ? 2 * (*lexdata)->nvars : (*lexdata)->nvars;
296 
297  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*lexdata)->vars, (*lexdata)->nvars) );
298  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*lexdata)->perm, permlen) );
299  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*lexdata)->invperm, permlen) );
300  if ( issignedperm )
301  {
302  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*lexdata)->vardomaincenter, (*lexdata)->nvars) );
303  }
304  else
305  (*lexdata)->vardomaincenter = NULL;
306 
307  /* determine the vars, perm, and centers */
308  for (j = 0; j < nvars; ++j)
309  {
310  i = indexcorrection[j];
311  if ( i < 0 )
312  continue;
313 
314  /* j is the original index, i is the relabeled index */
315  (*lexdata)->vars[i] = vars[j];
316 
317  if ( issignedperm )
318  {
319  if ( perm[j] >= nvars )
320  {
321  (*lexdata)->perm[i] = indexcorrection[perm[j] - nvars] + (*lexdata)->nvars;
322  (*lexdata)->perm[i + (*lexdata)->nvars] = indexcorrection[perm[j] - nvars];
323  assert( (*lexdata)->nvars <= (*lexdata)->perm[i] && (*lexdata)->perm[i] < 2 * (*lexdata)->nvars );
324  }
325  else
326  {
327  (*lexdata)->perm[i] = indexcorrection[perm[j]];
328  (*lexdata)->perm[i + (*lexdata)->nvars] = indexcorrection[perm[j]] + (*lexdata)->nvars;
329  }
330  }
331  else
332  (*lexdata)->perm[i] = indexcorrection[perm[j]];
333 
334  if ( issignedperm )
335  (*lexdata)->vardomaincenter[i] = permvardomaincenter[j];
336 
337  assert( perm[j] != j );
338  assert( (*lexdata)->perm[i] != i );
339  assert( (*lexdata)->perm[i] >= 0 );
340  assert( (*lexdata)->perm[i] < permlen );
341  }
342 
343  /* determine invperm */
344  for (i = 0; i < (*lexdata)->nvars; ++i)
345  {
346  if ( (*lexdata)->perm[i] >= (*lexdata)->nvars )
347  {
348  assert( issignedperm );
349 
350  (*lexdata)->invperm[(*lexdata)->perm[i]] = i;
351  (*lexdata)->invperm[(*lexdata)->perm[i] - (*lexdata)->nvars] = i + (*lexdata)->nvars;
352  }
353  else
354  {
355  (*lexdata)->invperm[(*lexdata)->perm[i]] = i;
356 
357  if ( issignedperm )
358  (*lexdata)->invperm[(*lexdata)->perm[i] + (*lexdata)->nvars] = i + (*lexdata)->nvars;
359  }
360  }
361  SCIPfreeBufferArray(scip, &indexcorrection);
362 
363  /* make sure that we deal with transformed variables and that variables cannot be multi-aggregated, and capture */
364  for (i = 0; i < (*lexdata)->nvars; ++i)
365  {
366  assert( SCIPvarIsTransformed((*lexdata)->vars[i]) );
367  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*lexdata)->vars[i]) );
368  SCIP_CALL( SCIPcaptureVar(scip, (*lexdata)->vars[i]) );
369  }
370 
371  /* create hashmap for all variables, both globally and just for this lexdata */
372  assert( (masterdata->symvarmap == NULL) == (masterdata->nsymvars == 0) );
373  if ( usedynamicorder )
374  {
375  if ( masterdata->symvarmap == NULL )
376  {
377  SCIP_CALL( SCIPhashmapCreate(&masterdata->symvarmap, SCIPblkmem(scip), (*lexdata)->nvars) );
378  }
379  assert( masterdata->symvarmap != NULL );
380 
381  SCIP_CALL( SCIPhashmapCreate(&(*lexdata)->varmap, SCIPblkmem(scip), (*lexdata)->nvars) );
382  assert( (*lexdata)->varmap != NULL );
383 
384  for (i = 0; i < (*lexdata)->nvars; ++i)
385  {
386  var = (*lexdata)->vars[i];
387  assert( var != NULL );
388  assert( SCIPvarIsTransformed(var) );
389 
390  /* the hashmap in lexdata maps to the index in the vars array */
391  SCIP_CALL( SCIPhashmapInsertInt((*lexdata)->varmap, (void*) var, i) );
392 
393  /* var already added to hashmap */
394  if ( SCIPhashmapExists(masterdata->symvarmap, (void*) var) )
395  continue;
396 
397  /* the hashmap in symvarmap maps to a unique index */
398  SCIP_CALL( SCIPhashmapInsertInt(masterdata->symvarmap, (void*) var, masterdata->nsymvars++) );
399  }
400  }
401  else
402  (*lexdata)->varmap = NULL;
403 
404  return SCIP_OKAY;
405 }
406 
407 
408 /** comparator used in the getVarOrder() function, for sorting an array of NODEDEPTHBRANCHINDEX by depth, then by index
409  *
410  * @warning this function is only meant to be used in the getVarOrder() function
411  *
412  * @pre datapointer is populated with a VARARRAYNODEDEPTHBRANCHINDEX pointer
413  * @pre the comparator is only called on entries with set (depth, index)-information
414  * @pre the (depth, index)-informations are all different
415  *
416  * result:
417  * 0: the same index is compared, so the (depth, index)-informations are the same
418  * -1: the depth of ind1 is smaller than the depth of ind2, or it's equal and the index is smaller
419  * 1: the depth of ind2 is smaller than the depth of ind1, or it's equal and the index is smaller
420  */
421 static
422 SCIP_DECL_SORTINDCOMP(sortbynodedepthbranchindices)
423 {
424  /* unpack the dataptr */
425  VARARRAYNODEDEPTHBRANCHINDEX* vararraynodedepthbranchindices;
428  SCIP_VAR** vars;
429  NODEDEPTHBRANCHINDEX* index1;
430  NODEDEPTHBRANCHINDEX* index2;
431 
432  vararraynodedepthbranchindices = (VARARRAYNODEDEPTHBRANCHINDEX*) dataptr;
433  nodedepthbranchindices = vararraynodedepthbranchindices->nodedepthbranchindices;
434  masterdata = vararraynodedepthbranchindices->masterdata;
435  vars = vararraynodedepthbranchindices->vars;
436 
437  /* comparing the same element is an identity operation */
438  if ( ind1 == ind2 )
439  return 0;
440 
441  /* sort by depth, then by index, in increasing order */
442  index1 = &(nodedepthbranchindices[SCIPhashmapGetImageInt(masterdata->symvarmap, vars[ind1])]);
443  index2 = &(nodedepthbranchindices[SCIPhashmapGetImageInt(masterdata->symvarmap, vars[ind2])]);
444 
445  if ( index1->nodedepth < index2->nodedepth )
446  return -1;
447  if ( index1->nodedepth > index2->nodedepth )
448  return 1;
449  assert( index1->index != index2->index );
450 
451  /* depth is the same, sort by index */
452  if ( index1->index < index2->index )
453  return -1;
454  if ( index1->index > index2->index )
455  return 1;
456 
457  /* this may not happen, since all elements must be different */
458  assert( index1->index == index2->index );
459 
460  return 0;
461 }
462 
463 
464 /** return the index of a variable at a specific position of a variable order */
465 static
467  int* varorder, /**< variable order (or NULL) */
468  int pos /**< position for which index is returned */
469  )
470 {
471  assert( pos >= 0 );
472 
473  if ( varorder == NULL )
474  return pos;
475  return varorder[pos];
476 }
477 
478 
479 /** gets the variable ordering based on the branching decisions at the node */
480 static
482  SCIP* scip, /**< SCIP data structure */
483  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
484  LEXDATA* lexdata, /**< pointer to data for this permutation */
485  NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
486  int nvarstotal, /**< length of that array */
487  SCIP_VAR** branchvars, /**< array populated with variables branched on in the symvarmap hashset */
488  int nbranchvars, /**< number of elements in branchvars array */
489  int* varorder, /**< array to populate with variable order */
490  int* nselvars, /**< pointer to number of variables in the ordering */
491  int maxnselvars /**< maximal size of the number of selected variables */
492  )
493 {
494  SCIP_VAR** vars;
495  int nvars;
496  SCIP_VAR* var;
497  int varindex;
498  int i;
499 
500  assert( scip != NULL );
501  assert( masterdata != NULL );
502  assert( lexdata != NULL );
503  assert( nodedepthbranchindices != NULL );
504  assert( nvarstotal >= 0 );
505  assert( branchvars != NULL );
506  assert( nbranchvars >= 0 );
507  assert( varorder != NULL );
508  assert( nselvars != NULL );
509 
510  vars = lexdata->vars;
511  assert( vars != NULL );
512  nvars = lexdata->nvars;
513  assert( nvars >= 0 );
514 
515  /* first collect every variable that was branched on */
516  *nselvars = 0;
517 
518  if ( nvars < nbranchvars )
519  {
520  /* for permutations with small support, just check all support entries */
521  for (i = 0; i < nvars; ++i)
522  {
523  var = vars[i];
524  assert( var != NULL );
525 
526  assert( SCIPhashmapExists(masterdata->symvarmap, (void*) var) );
527  varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
528  assert( varindex >= 0 );
529  assert( varindex < masterdata->nsymvars );
530 
531  assert( nodedepthbranchindices[varindex].nodedepth >= 0 );
532 
533  /* skip variables that have not been used for branching */
534  if ( nodedepthbranchindices[varindex].nodedepth <= 0 )
535  continue;
536 
537  /* add index i of branching variable */
538  assert( i >= 0 );
539  assert( i < nvars );
540  assert( (*nselvars) < maxnselvars );
541  varorder[(*nselvars)++] = i;
542  }
543  }
544  else
545  {
546  /* for permutations where the support is larger than the number of branched vars, check for the branched vars */
547  for (i = 0; i < nbranchvars; ++i)
548  {
549  var = branchvars[i];
550  assert( var != NULL );
551 
552 #ifndef NDEBUG
553  /* debugging: test if it is indeed a branched variable! */
554  varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
555  assert( varindex >= 0 );
556  assert( varindex < masterdata->nsymvars );
557  assert( nodedepthbranchindices[varindex].nodedepth > 0 );
558 #endif
559 
560  /* get the variable index in the lexdata->vars array */
561  varindex = SCIPhashmapGetImageInt(lexdata->varmap, (void*) var);
562  assert( varindex == INT_MAX || (varindex >= 0 && varindex < lexdata->nvars) );
563 
564  /* skip variables that are not permuted by the permutation */
565  if ( varindex == INT_MAX )
566  continue;
567  assert( lexdata->vars[varindex] == var );
568 
569  /* add index varindex of the branching variable */
570  varorder[(*nselvars)++] = varindex;
571  }
572  }
573 
574  if ( *nselvars > 1 )
575  {
576  /* sort the first n elements of varorder by depth, then by index, as indicated by nodedepthbranchindices. */
577  VARARRAYNODEDEPTHBRANCHINDEX vararraynodedepthbranchindices;
578  vararraynodedepthbranchindices.nodedepthbranchindices = nodedepthbranchindices;
579  vararraynodedepthbranchindices.masterdata = masterdata;
580  vararraynodedepthbranchindices.vars = vars;
581  SCIPsortInd(varorder, sortbynodedepthbranchindices, (void*) &vararraynodedepthbranchindices, *nselvars);
582  }
583 
584  return SCIP_OKAY;
585 }
586 
587 
588 /** gerts local variable bounds or reads bound from peek data */
589 static
591  SCIP_VAR* var1, /**< first variable in comparison */
592  SCIP_VAR* var2, /**< second variable in comparison */
593  SCIP_Bool peekmode, /**< whether function is called in peek mode */
594  int varidx1, /**< index of var1 (or NULL) */
595  int varidx2, /**< index of var2 (or NULL) */
596  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
597  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
598  SCIP_Bool* peekbdset, /**< whether peek bounds have been set (or NULL) */
599  SCIP_Real* lb1, /**< pointer to store lower bound of var1 */
600  SCIP_Real* ub1, /**< pointer to store upper bound of var1 */
601  SCIP_Real* lb2, /**< pointer to store lower bound of var2 */
602  SCIP_Real* ub2 /**< pointer to store upper bound of var2 */
603  )
604 {
605  assert( var1 != NULL );
606  assert( var2 != NULL );
607  assert( (!peekmode) || peeklbs != NULL );
608  assert( (!peekmode) || peekubs != NULL );
609  assert( (!peekmode) || peekbdset != NULL );
610  assert( lb1 != NULL );
611  assert( ub1 != NULL );
612  assert( lb2 != NULL );
613  assert( ub2 != NULL );
614 
615  if ( peekmode && peekbdset[varidx1] )
616  {
617  *ub1 = peekubs[varidx1];
618  *lb1 = peeklbs[varidx1];
619  }
620  else
621  {
622  *ub1 = SCIPvarGetUbLocal(var1);
623  *lb1 = SCIPvarGetLbLocal(var1);
624  }
625  if ( peekmode && peekbdset[varidx2] )
626  {
627  *ub2 = peekubs[varidx2];
628  *lb2 = peeklbs[varidx2];
629  }
630  else
631  {
632  *ub2 = SCIPvarGetUbLocal(var2);
633  *lb2 = SCIPvarGetLbLocal(var2);
634  }
635 
636  return SCIP_OKAY;
637 }
638 
639 /** returns whether a shifted variable is always smaller than another shifted variable
640  *
641  * Shifts are always (var - shift).
642  */
643 static
645  SCIP* scip, /**< SCIP data structure */
646  SCIP_VAR* var1, /**< first variable in comparison */
647  SCIP_VAR* var2, /**< second variable in comparison */
648  SCIP_Real shift1, /**< shift of var1 */
649  SCIP_Real shift2, /**< shift of var2 */
650  SCIP_Bool isnegated, /**< whether shift of var2 is negated */
651  SCIP_Bool peekmode, /**< whether function is called in peek mode */
652  int varidx1, /**< index of var1 (or NULL) */
653  int varidx2, /**< index of var2 (or NULL) */
654  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
655  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
656  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
657  )
658 {
659  SCIP_Real ub1;
660  SCIP_Real ub2;
661  SCIP_Real lb1;
662  SCIP_Real lb2;
663 
664  assert( scip != NULL );
665  assert( var1 != NULL );
666  assert( var2 != NULL );
667  assert( (!peekmode) || peeklbs != NULL );
668  assert( (!peekmode) || peekubs != NULL );
669  assert( (!peekmode) || peekbdset != NULL );
670 
671  SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
672  &lb1, &ub1, &lb2, &ub2) );
673 
674  /* for negated variables, check: var1 - shift1 < shift2 - var2 */
675  if ( isnegated && SCIPisLT(scip, ub1, shift1 + shift2 - ub2) )
676  return TRUE;
677 
678  /* for non-negated variables, check: var1 - center1 < var2 - center2 */
679  if ( (!isnegated) && SCIPisLT(scip, ub1, shift1 - shift2 + lb2) )
680  return TRUE;
681 
682  return FALSE;
683 }
684 
685 
686 /** returns whether a shifted variable can be greater than another shifted variable
687  *
688  * Shifts are always (var - shift).
689  */
690 static
692  SCIP* scip, /**< SCIP data structure */
693  SCIP_VAR* var1, /**< first variable in comparison */
694  SCIP_VAR* var2, /**< second variable in comparison */
695  SCIP_Real shift1, /**< shift of var1 */
696  SCIP_Real shift2, /**< shift of var2 */
697  SCIP_Bool isnegated, /**< whether shift of var2 is negated */
698  SCIP_Bool peekmode, /**< whether function is called in peek mode */
699  int varidx1, /**< index of var1 (or NULL) */
700  int varidx2, /**< index of var2 (or NULL) */
701  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
702  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
703  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
704  )
705 {
706  SCIP_Real ub1;
707  SCIP_Real ub2;
708  SCIP_Real lb1;
709  SCIP_Real lb2;
710 
711  assert( scip != NULL );
712  assert( var1 != NULL );
713  assert( var2 != NULL );
714  assert( (!peekmode) || peeklbs != NULL );
715  assert( (!peekmode) || peekubs != NULL );
716  assert( (!peekmode) || peekbdset != NULL );
717 
718  SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
719  &lb1, &ub1, &lb2, &ub2) );
720 
721  /* for negated variables, check: var1 - shift1 > shift2 - var2 */
722  if ( isnegated && SCIPisGT(scip, ub1, shift1 + shift2 - ub2) )
723  return TRUE;
724 
725  /* for non-negated variables, check: var1 - center1 > var2 - center2 */
726  if ( (!isnegated) && SCIPisGT(scip, ub1, shift1 - shift2 + lb2) )
727  return TRUE;
728 
729  return FALSE;
730 }
731 
732 
733 /** propagates lower bound of first variable in relation x >= y for shifted variables */
734 static
736  SCIP* scip, /**< SCIP data structure */
737  SCIP_VAR* var1, /**< first variable in pair */
738  SCIP_VAR* var2, /**< second variable in pair */
739  SCIP_Real center1, /**< center of var1 (original var domain) */
740  SCIP_Real center2, /**< center of var2 (original var domain) */
741  SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
742  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
743  int* nreductions, /**< pointer to store number of reductions */
744  SCIP_Bool peekmode, /**< whether function is called in peek mode */
745  int varidx1, /**< index of var1 (or NULL) */
746  int varidx2, /**< index of var2 (or NULL) */
747  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
748  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
749  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
750  )
751 {
752  SCIP_Real ub1;
753  SCIP_Real ub2;
754  SCIP_Real lb1;
755  SCIP_Real lb2;
756 
757  SCIP_Bool tighten = FALSE;
758  SCIP_Real newbd;
759 
760  assert( (!peekmode) || peeklbs != NULL );
761  assert( (!peekmode) || peekubs != NULL );
762  assert( (!peekmode) || peekbdset != NULL );
763 
764  SCIP_CALL( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
765  &lb1, &ub1, &lb2, &ub2) );
766 
767  /* tighten domain of var1 to ensure that var1 - center1 >= isnegated * (var2 - center2 ) */
768  if ( isnegated )
769  {
770  if ( SCIPisLT(scip, lb1 - center1, center2 - ub2) )
771  {
772  tighten = TRUE;
773  newbd = center1 + center2 - ub2;
774  }
775  }
776  else
777  {
778  if ( SCIPisLT(scip, lb1 - center1, lb2 - center2) )
779  {
780  tighten = TRUE;
781  newbd = center1 + lb2 - center2;
782  }
783  }
784 
785  if ( tighten )
786  {
787  /* in peek mode, only store updated bounds */
788  if ( peekmode )
789  {
790  peeklbs[varidx1] = newbd; /*lint !e644*/
791  peekubs[varidx1] = ub1;
792  peekbdset[varidx1] = TRUE;
793  }
794  else
795  {
796  SCIP_CALL( SCIPtightenVarLb(scip, var1, newbd, TRUE, infeasible, &tighten) );
797  if ( tighten )
798  {
799  SCIPdebugMessage("Restricting variable LB %12s to %5.2f\n", SCIPvarGetName(var1), newbd);
800  *nreductions += 1;
801  }
802  else
803  {
804  SCIPdebugMessage("Restricting variable LB %12s to %5.2f (no success)\n",
805  SCIPvarGetName(var1), newbd);
806  }
807  if ( *infeasible )
808  {
809  SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
810  SCIPvarGetName(var1), newbd);
811  return SCIP_OKAY;
812  }
813  }
814  }
815 
816  return SCIP_OKAY;
817 }
818 
819 
820 /** propagates upper bound of second variable in relation x >= y for shifted variables */
821 static
823  SCIP* scip, /**< SCIP data structure */
824  SCIP_VAR* var1, /**< first variable in pair */
825  SCIP_VAR* var2, /**< second variable in pair */
826  SCIP_Real center1, /**< center of var1 (original var domain) */
827  SCIP_Real center2, /**< center of var2 (original var domain) */
828  SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
829  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
830  int* nreductions, /**< pointer to store number of reductions */
831  SCIP_Bool peekmode, /**< whether function is called in peek mode */
832  int varidx1, /**< index of var1 (or NULL) */
833  int varidx2, /**< index of var2 (or NULL) */
834  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
835  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
836  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
837  )
838 {
839  SCIP_Real ub1;
840  SCIP_Real ub2;
841  SCIP_Real lb1;
842  SCIP_Real lb2;
843 
844  SCIP_Bool tighten = FALSE;
845  SCIP_Real newbd;
846 
847  assert( scip != NULL );
848  assert( var1 != NULL );
849  assert( var2 != NULL );
850  assert( infeasible != NULL );
851  assert( nreductions != NULL );
852  assert( (!peekmode) || peeklbs != NULL );
853  assert( (!peekmode) || peekubs != NULL );
854  assert( (!peekmode) || peekbdset != NULL );
855 
856  SCIP_CALL( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
857  &lb1, &ub1, &lb2, &ub2) );
858 
859  /* tighten domain of var2 to ensure that var1 - center1 >= isnegated * (var2 - center2 ) */
860  if ( isnegated )
861  {
862  if ( SCIPisLT(scip, ub1 - center1, center2 - lb2) )
863  {
864  tighten = TRUE;
865  newbd = center1 + center2 - ub1;
866  }
867  }
868  else
869  {
870  if ( SCIPisLT(scip, ub1 - center1, ub2 - center2) )
871  {
872  tighten = TRUE;
873  newbd = center2 - center1 + ub1;
874  }
875  }
876 
877  if ( tighten )
878  {
879  /* in peek mode, only store updated bounds */
880  if ( peekmode )
881  {
882  if ( isnegated )
883  {
884  peeklbs[varidx2] = newbd; /*lint !e644*/
885  peekubs[varidx2] = ub2;
886  peekbdset[varidx2] = TRUE;
887  }
888  else
889  {
890  peeklbs[varidx2] = lb2;
891  peekubs[varidx2] = newbd;
892  peekbdset[varidx2] = TRUE;
893  }
894  }
895  else
896  {
897  if ( isnegated )
898  {
899  SCIP_CALL( SCIPtightenVarLb(scip, var2, newbd, TRUE, infeasible, &tighten) );
900  }
901  else
902  {
903  SCIP_CALL( SCIPtightenVarUb(scip, var2, newbd, TRUE, infeasible, &tighten) );
904  }
905 
906  if ( tighten )
907  {
908  SCIPdebugMessage("Restricting variable %sB %12s to %5.2f\n",
909  isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
910  *nreductions += 1;
911  }
912  else
913  {
914  SCIPdebugMessage("Restricting variable %sB %12s to %5.2f (no success)\n",
915  isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
916  }
917  if ( *infeasible )
918  {
919  SCIPdebugMessage("Detected infeasibility restricting variable %sB %12s to %5.2f\n",
920  isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
921  return SCIP_OKAY;
922  }
923  }
924  }
925 
926  return SCIP_OKAY;
927 }
928 
929 
930 /** propagates x - c >= c - x */
931 static
933  SCIP* scip, /**< SCIP data structure */
934  SCIP_VAR* var, /**< variable */
935  SCIP_Real center, /**< center of var (original var domain) */
936  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
937  int* nreductions, /**< pointer to store number of reductions */
938  SCIP_Bool peekmode, /**< whether function is called in peek mode */
939  int varidx, /**< index of var (or NULL) */
940  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
941  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
942  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
943  )
944 {
945  SCIP_Real ub1;
946  SCIP_Real ub2;
947  SCIP_Real lb1;
948  SCIP_Real lb2;
949  SCIP_Bool tighten = FALSE;
950 
951  assert( scip != NULL );
952  assert( var != NULL );
953  assert( infeasible != NULL );
954  assert( nreductions != NULL );
955  assert( (!peekmode) || peeklbs != NULL );
956  assert( (!peekmode) || peekubs != NULL );
957  assert( (!peekmode) || peekbdset != NULL );
958 
959  SCIP_CALL( getVarBounds(var, var, peekmode, varidx, varidx, peeklbs, peekubs, peekbdset,
960  &lb1, &ub1, &lb2, &ub2) );
961 
962  if ( SCIPisLT(scip, ub1, center) )
963  {
964  *infeasible = TRUE;
965  return SCIP_OKAY;
966  }
967  else if ( SCIPisLT(scip, lb1, center) )
968  {
969  if ( peekmode )
970  {
971  peeklbs[varidx] = center;
972  peekubs[varidx] = ub1;
973  peekbdset[varidx] = TRUE;
974  }
975  else
976  {
977  SCIP_CALL( SCIPtightenVarLb(scip, var, center, TRUE, infeasible, &tighten) );
978  if ( tighten )
979  {
980  SCIPdebugMessage("Restricting variable LB %12s to %5.2f\n", SCIPvarGetName(var), center);
981  *nreductions += 1;
982  }
983  else
984  {
985  SCIPdebugMessage("Restricting variable LB %12s to %5.2f (no success)\n",
986  SCIPvarGetName(var), center);
987  }
988  if ( *infeasible )
989  {
990  SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
991  SCIPvarGetName(var), center);
992  return SCIP_OKAY;
993  }
994  }
995  }
996 
997  return SCIP_OKAY;
998 }
999 
1000 
1001 /** propagates lexicographic order for one pair of symmetric variables */
1002 static
1004  SCIP* scip, /**< SCIP data structure */
1005  SCIP_VAR* var1, /**< first variable in pair */
1006  SCIP_VAR* var2, /**< second variable in pair */
1007  SCIP_Real center1, /**< center of var1 (original var domain) */
1008  SCIP_Real center2, /**< center of var2 (original var domain) */
1009  SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
1010  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1011  int* nreductions, /**< pointer to store number of reductions */
1012  SCIP_Bool peekmode, /**< whether function is called in peek mode */
1013  int varidx1, /**< index of var1 (or NULL) */
1014  int varidx2, /**< index of var2 (or NULL) */
1015  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
1016  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
1017  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
1018  )
1019 {
1020  assert( scip != NULL );
1021  assert( var1 != NULL );
1022  assert( var2 != NULL );
1023  assert( infeasible != NULL );
1024  assert( nreductions != NULL );
1025 
1026  /* perform lexicographic comparison: var1 - center1 >= +/- (var2 - center2) */
1027  if ( alwaysLTshiftedVars(scip, var1, var2, center1, center2, isnegated, peekmode,
1028  varidx1, varidx2, peeklbs, peekubs, peekbdset) )
1029  {
1030 #ifdef SCIP_DEBUG
1031  SCIP_Real ub1;
1032  SCIP_Real ub2;
1033  SCIP_Real lb1;
1034  SCIP_Real lb2;
1035 
1036  /* get bounds of shifted (and possibly negated) variables */
1037  ub1 = SCIPvarGetUbLocal(var1);
1038  lb1 = SCIPvarGetLbLocal(var1);
1039  ub2 = SCIPvarGetUbLocal(var2);
1040  lb2 = SCIPvarGetLbLocal(var2);
1041 
1042  SCIPdebugMessage("Detected infeasibility: x < y for "
1043  "x: lb=%5.2f, ub=%5.2f, shift=%5.2f "
1044  "y: lb=%5.2f, ub=%5.2f, shift=%5.2f negated=%u\n",
1045  lb1, ub1, center1, lb2, ub2, center2, isnegated);
1046 #endif
1047 
1048  *infeasible = TRUE;
1049  return SCIP_OKAY;
1050  }
1051 
1052  /* for signed permutations, a variable might be mapped to itself */
1053  if ( var1 == var2 )
1054  {
1055  SCIP_CALL( propagateSelfReflectionVar(scip, var1, center1, infeasible, nreductions, peekmode, varidx1,
1056  peeklbs, peekubs, peekbdset) );
1057  }
1058  else
1059  {
1060  SCIP_CALL( propagateLowerBoundVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1061  varidx1, varidx2, peeklbs, peekubs, peekbdset) );
1062  if ( *infeasible )
1063  return SCIP_OKAY;
1064 
1065  SCIP_CALL( propagateUpperBoundSymVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1066  varidx1, varidx2, peeklbs, peekubs, peekbdset) );
1067  }
1068 
1069  return SCIP_OKAY;
1070 }
1071 
1072 /** checks if the static lexred with a certain variable ordering is feasible in the hypothetical scenario where
1073  * variables with indices i and j are fixed to fixvalue (i.e., peeking)
1074  */
1075 static
1077  SCIP* scip, /**< SCIP data structure */
1078  LEXDATA* lexdata, /**< pointer to data for this permutation */
1079  int* varorder, /**< array populated with variable order (or NULL for static propagation) */
1080  int nselvars, /**< number of variables in the ordering */
1081  int fixi, /**< variable index of left fixed column */
1082  int fixj, /**< variable index of right fixed column */
1083  int fixrow, /**< row index in var ordering, from which to start peeking */
1084  SCIP_Real fixvaluei, /**< value on which variables i is fixed */
1085  SCIP_Real fixvaluej, /**< value on which variables j is fixed */
1086  SCIP_Bool* peekfeasible, /**< pointer to store whether this is feasible or not */
1087  SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
1088  SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
1089  SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
1090  )
1091 {
1092  int row;
1093  int i;
1094  int j;
1095  SCIP_VAR* vari;
1096  SCIP_VAR* varj;
1097  SCIP_Real centeri;
1098  SCIP_Real centerj;
1099  SCIP_Bool issigned;
1100  SCIP_Bool isnegated;
1101  SCIP_Bool infeasible = FALSE;
1102  int nreductions;
1103 
1104  assert( scip != NULL );
1105  assert( lexdata != NULL );
1106  assert( lexdata->vars != NULL );
1107  assert( lexdata->nvars >= 0 );
1108  assert( nselvars <= lexdata->nvars );
1109  assert( nselvars > 0 );
1110  assert( fixi >= 0 );
1111  assert( fixi < lexdata->nvars );
1112  assert( fixj < lexdata->nvars );
1113  assert( fixi != fixj || lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1114  assert( fixi != fixj || fixvaluei == fixvaluej ); /*lint !e777*/
1115  assert( fixrow >= 0 );
1116  assert( fixrow < nselvars );
1117  assert( peekfeasible != NULL );
1118  assert( fixi == varOrderGetIndex(varorder, fixrow) );
1119  assert( fixj == (lexdata->invperm[varOrderGetIndex(varorder, fixrow)] % lexdata->nvars) );
1120  assert( fixi == (lexdata->perm[fixj] % lexdata->nvars) );
1121 
1122  *peekfeasible = TRUE;
1123  issigned = lexdata->symtype == SYM_SYMTYPE_SIGNPERM ? TRUE : FALSE;
1124  assert( (!issigned) || lexdata->vardomaincenter != NULL );
1125 
1126  /* intialize peekbdset */
1127  for (i = 0; i < lexdata->nvars; ++i)
1128  peekbdset[i] = FALSE;
1129 
1130  peeklbs[fixi] = fixvaluei;
1131  peeklbs[fixj] = fixvaluej;
1132  peekubs[fixi] = fixvaluei;
1133  peekubs[fixj] = fixvaluej;
1134  peekbdset[fixi] = TRUE;
1135  peekbdset[fixj] = TRUE;
1136 
1137  for (row = fixrow + 1; row < nselvars; ++row)
1138  {
1139  /* get left and right column indices */
1140  i = varOrderGetIndex(varorder, row);
1141  j = lexdata->invperm[i];
1142  assert( i == lexdata->perm[j] );
1143 
1144  /* no fixed points */
1145  assert( i != j );
1146 
1147  assert( 0 <= i && i < lexdata->nvars );
1148  assert( 0 <= j && j < 2 * lexdata->nvars );
1149  assert( issigned || j < lexdata->nvars );
1150 
1151  vari = lexdata->vars[i];
1152  if ( j >= lexdata->nvars )
1153  {
1154  assert( lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1155  j = j - lexdata->nvars;
1156  varj = lexdata->vars[j];
1157  isnegated = TRUE;
1158  }
1159  else
1160  {
1161  varj = lexdata->vars[j];
1162  isnegated = FALSE;
1163  }
1164 
1165  if ( issigned )
1166  {
1167  assert( lexdata->vardomaincenter != NULL );
1168  centeri = lexdata->vardomaincenter[i];
1169  centerj = lexdata->vardomaincenter[j];
1170  }
1171  else
1172  {
1173  centeri = 0.0;
1174  centerj = 0.0;
1175  }
1176 
1177  /* propagate that vari >= varj */
1178 
1179  /* vari >= varj can never hold if the maximal value of vari is smaller than the minimal value of varj */
1180  if ( alwaysLTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, TRUE, i, j, peeklbs, peekubs, peekbdset) )
1181  {
1182  *peekfeasible = FALSE;
1183  SCIPdebugMessage("PEEK: Detected infeasibility at row %3d.\n", row);
1184  break;
1185  }
1186 
1187  SCIP_CALL( propagateLowerBoundVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1188  i, j, peeklbs, peekubs, peekbdset) );
1189 
1190  SCIP_CALL( propagateUpperBoundSymVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1191  i, j, peeklbs, peekubs, peekbdset) );
1192 
1193  /* if there exists a solution with vari > varj, reductions are feasible w.r.t. lexred */
1194  if ( canGTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, TRUE,
1195  i, j, peeklbs, peekubs, peekbdset) )
1196  break;
1197  }
1198 
1199  return SCIP_OKAY;
1200 }
1201 
1202 /** propagates static lexicographic reduction with specified variable ordering */
1203 static
1205  SCIP* scip, /**< SCIP data structure */
1206  LEXDATA* lexdata, /**< pointer to data for this permutation */
1207  int* varorder, /**< array populated with variable order (or NULL if static propagation) */
1208  int nselvars, /**< number of variables in the ordering */
1209  SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1210  int* nreductions /**< pointer to store the number of found domain reductions */
1211  )
1212 { /*lint --e{771}*/
1213  int row;
1214  int i = -1;
1215  int j = -1;
1216  SCIP_VAR* vari = NULL;
1217  SCIP_VAR* varj = NULL;
1218  SCIP_Real centeri;
1219  SCIP_Real centerj;
1220  SCIP_Bool success;
1221  SCIP_Bool issigned;
1222  SCIP_Bool isnegated;
1223 
1224  assert( scip != NULL );
1225  assert( lexdata != NULL );
1226  assert( nselvars >= 0 );
1227  assert( infeasible != NULL );
1228  assert( !*infeasible );
1229  assert( nreductions != NULL );
1230  assert( *nreductions >= 0 );
1231 
1232  /* avoid trivial cases */
1233  if ( nselvars <= 0 )
1234  return SCIP_OKAY;
1235 
1236  issigned = lexdata->symtype == SYM_SYMTYPE_SIGNPERM ? TRUE : FALSE;
1237  assert( (!issigned) || lexdata->vardomaincenter != NULL );
1238 
1239  /* iterate over the variable array entrywise
1240  *
1241  * We see this as two columns, with the left vector being the variable ordering,
1242  * and the right column the permuted variables of this var ordering.
1243  */
1244  for (row = 0; row < nselvars; ++row)
1245  {
1246  /* left and right column indices */
1247  i = varOrderGetIndex(varorder, row);
1248  j = lexdata->invperm[i];
1249  assert( i == lexdata->perm[j] );
1250 
1251  /* no fixed points */
1252  assert( i != j );
1253 
1254  assert( 0 <= i && i < lexdata->nvars );
1255  assert( 0 <= j && j < 2 * lexdata->nvars );
1256  assert( issigned || j < lexdata->nvars );
1257 
1258  vari = lexdata->vars[i];
1259  if ( j >= lexdata->nvars )
1260  {
1261  assert( issigned );
1262  j = j - lexdata->nvars;
1263  varj = lexdata->vars[j];
1264  isnegated = TRUE;
1265  }
1266  else
1267  {
1268  varj = lexdata->vars[j];
1269  isnegated = FALSE;
1270  }
1271 
1272  if ( issigned )
1273  {
1274  assert( lexdata->vardomaincenter != NULL );
1275  centeri = lexdata->vardomaincenter[i];
1276  centerj = lexdata->vardomaincenter[j];
1277  }
1278  else
1279  {
1280  centeri = 0.0;
1281  centerj = 0.0;
1282  }
1283 
1284  SCIP_CALL( propagateVariablePair(scip, vari, varj, centeri, centerj, isnegated, infeasible, nreductions, FALSE,
1285  0, 0, NULL, NULL, NULL) );
1286 
1287  if ( *infeasible )
1288  return SCIP_OKAY;
1289 
1290  /* terminate if there exists a solution being lexicographically strictly larger than its image */
1291  if ( canGTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, FALSE,
1292  0, 0, NULL, NULL, NULL) )
1293  break;
1294  }
1295  assert( vari != NULL );
1296  assert( varj != NULL );
1297  assert( 0 <= i && i < lexdata->nvars );
1298  assert( 0 <= j && j < lexdata->nvars );
1299 
1300  /* if the variables in "row" are fixed to the same value, we might find further propagations */
1301  if ( row < nselvars )
1302  {
1303  SCIP_Real* peeklbs;
1304  SCIP_Real* peekubs;
1305  SCIP_Bool* peekbdset;
1306  SCIP_Real ub1;
1307  SCIP_Real ub2;
1308  SCIP_Real lb1;
1309  SCIP_Real lb2;
1310  SCIP_Real lbi;
1311  SCIP_Real ubi;
1312  SCIP_Real lbj;
1313  SCIP_Real ubj;
1314  SCIP_Bool peekfeasible;
1315 
1316  SCIP_CALL( getVarBounds(vari, varj, FALSE, 0, 0, NULL, NULL, NULL, &lb1, &ub1, &lb2, &ub2) );
1317 
1318  /* special treatment if i-th and j-th variable are the same in a signed permutation */
1319  if ( vari == varj )
1320  {
1321  assert( lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1322  assert( SCIPsymGE(scip, lb1, lexdata->vardomaincenter[i]) ); /* propagation enforces xi - center >= center - xi */
1323 
1324  /* both variables can only be the same if they are fixed to the domain center */
1325  if ( SCIPsymGT(scip, lb1, lexdata->vardomaincenter[i]) )
1326  return SCIP_OKAY;
1327 
1328  SCIP_CALL( SCIPallocBufferArray(scip, &peeklbs, lexdata->nvars) );
1329  SCIP_CALL( SCIPallocBufferArray(scip, &peekubs, lexdata->nvars) );
1330  SCIP_CALL( SCIPallocBufferArray(scip, &peekbdset, lexdata->nvars) );
1331 
1332  SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1333  row, lexdata->vardomaincenter[i], lexdata->vardomaincenter[i],
1334  &peekfeasible, peeklbs, peekubs, peekbdset) );
1335  if ( !peekfeasible )
1336  {
1337  /* both variables cannot be the same, so the non-negated variable must be greater than the domain center */
1338  switch ( SCIPvarGetType(vari) )
1339  {
1340  case SCIP_VARTYPE_BINARY:
1341  case SCIP_VARTYPE_IMPLINT:
1342  case SCIP_VARTYPE_INTEGER:
1343  assert( SCIPisIntegral(scip, lb1) );
1344  SCIP_CALL( SCIPtightenVarLb(scip, vari, lexdata->vardomaincenter[i] + 1.0, TRUE, infeasible, &success) );
1345  if ( success )
1346  *nreductions += 1;
1347  if ( *infeasible )
1348  goto FREEMEMORY;
1349  lb1 = lexdata->vardomaincenter[i] + 1.0;
1350  assert( SCIPsymLE(scip, lb1, ub1) );
1351  break;
1353  /* continuous variable type: act as if we increase the variable by a very little bit.
1354  * This is only possible if we're able to increase the variable bound by a bit.
1355  */
1356  if ( SCIPsymEQ(scip, lb1, ub1) )
1357  {
1358  *infeasible = TRUE;
1359  goto FREEMEMORY;
1360  }
1361  break;
1362  default:
1363  SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1364  return SCIP_ERROR;
1365  }
1366  }
1367  }
1368  else
1369  {
1370  /* The previous loop is broken at row "row", which allows for choosing vari > varj.
1371  *
1372  * Now check if vari == varj is permitted, and if not, tighten the domain further.
1373  *
1374  * @todo We peek twice if vari and varj are unfixed
1375  * But, if the subcycle only contains var1 and var2, a single peek suffices.
1376  * This is similar to orbisack and symresack propagation.
1377  *
1378  * Case 1: vari is minimal (lbi).
1379  * Then, propagation of lbi = vari >= varj can yield two situations:
1380  * Option 1: varj can take a value < lbi. Then no further reductions can be detected.
1381  * Option 2: varj gets fixed to lbi. Then, we must check if feasibility is found, still.
1382  * If it turns out infeasible, then we know vari cannot take value lbi, so we can increase the lower bound.
1383  */
1384  centeri = 0.0;
1385  centerj = 0.0;
1386 
1387  if ( lexdata->vardomaincenter != NULL )
1388  {
1389  centeri = lexdata->vardomaincenter[i];
1390  centerj = lexdata->vardomaincenter[j];
1391  }
1392 
1393  /* translate variable bounds to shifted variable domain and take negation into account */
1394  lbi = lb1 - centeri;
1395  ubi = ub1 - centeri;
1396  if ( isnegated )
1397  {
1398  lbj = centerj - ub2;
1399  ubj = centerj - lb2;
1400  }
1401  else
1402  {
1403  lbj = lb2 - centerj;
1404  ubj = ub2 - centerj;
1405  }
1406 
1407  /* check whether peek is called */
1408  if ( (!SCIPsymEQ(scip, lbi, lbj)) && (!SCIPsymEQ(scip, ubi, ubj)) )
1409  return SCIP_OKAY;
1410 
1411  SCIP_CALL( SCIPallocBufferArray(scip, &peeklbs, lexdata->nvars) );
1412  SCIP_CALL( SCIPallocBufferArray(scip, &peekubs, lexdata->nvars) );
1413  SCIP_CALL( SCIPallocBufferArray(scip, &peekbdset, lexdata->nvars) );
1414 
1415  if ( SCIPsymEQ(scip, lbj, lbi) )
1416  {
1417  SCIP_Real fixvalj;
1418 
1419  /* translate lbj back to original variable domain of variable j */
1420  if ( isnegated )
1421  fixvalj = centerj - lbj;
1422  else
1423  fixvalj = lbj + centerj;
1424 
1425  /* this is Option 2: varj gets fixed to lbi by propagation. */
1426  SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1427  row, lbi + centeri, fixvalj, &peekfeasible, peeklbs, peekubs, peekbdset) );
1428  if ( !peekfeasible )
1429  {
1430  /* vari cannot take value lb1, so we increase the lower bound. (do not use lbi as this is a shifted domain bound) */
1431  switch ( SCIPvarGetType(vari) )
1432  {
1433  case SCIP_VARTYPE_BINARY:
1434  case SCIP_VARTYPE_IMPLINT:
1435  case SCIP_VARTYPE_INTEGER:
1436  /* discrete variable type: increase lower bound by 1. */
1437  assert( SCIPisIntegral(scip, lb1) );
1438  SCIP_CALL( SCIPtightenVarLb(scip, vari, lb1 + 1.0, TRUE, infeasible, &success) );
1439  if ( success )
1440  *nreductions += 1;
1441  if ( *infeasible )
1442  goto FREEMEMORY;
1443  lb1 = lb1 + 1.0;
1444  assert( SCIPsymLE(scip, lb1, ub1) );
1445  break;
1447  /* continuous variable type: act as if we increase the variable by a very little bit.
1448  * That is only possible if we're able to increase the variable bound by a bit.
1449  */
1450  if ( SCIPsymEQ(scip, lbi, ubi) )
1451  {
1452  *infeasible = TRUE;
1453  goto FREEMEMORY;
1454  }
1455  break;
1456  default:
1457  SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1458  return SCIP_ERROR;
1459  }
1460  }
1461  }
1462 
1463  /* Case 2: varj is maximal (ubj).
1464  * Then, propagation of vari >= varj = ubj can yield two situatiosn:
1465  * Option 1: vari can take a value > ubj. Then, no further reductions can be detected.
1466  * Option 2: vari gets fixed to ubj. Then, we must check if feasibility is found, still.
1467  * If it turns out infeasible, then we know varj cannot take value ubj, so we can decrease the upper bound.
1468  */
1469  assert( SCIPsymGE(scip, ubi, ubj) ); /* this must be the case after reductions in the for-loop */
1470  if ( SCIPsymEQ(scip, ubi, ubj) )
1471  {
1472  SCIP_Real fixvalj;
1473 
1474  /* translate ubj back to original variable domain of variable j */
1475  if ( isnegated )
1476  fixvalj = centerj - ubj;
1477  else
1478  fixvalj = ubj + centerj;
1479 
1480  /* this is Option 2: vari gets fixed to ubj by propagation. */
1481  SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1482  row, ubi + centeri, fixvalj, &peekfeasible, peeklbs, peekubs, peekbdset) );
1483  if ( !peekfeasible )
1484  {
1485  /* varj cannot take value ub2, so we decrease the upper or lower bound. (do not use ubj as this is a shifted domain bound)*/
1486  switch ( SCIPvarGetType(varj) )
1487  {
1488  case SCIP_VARTYPE_BINARY:
1489  case SCIP_VARTYPE_IMPLINT:
1490  case SCIP_VARTYPE_INTEGER:
1491  /* discrete variable type: decrease upper bound by 1. */
1492  if ( isnegated )
1493  {
1494  assert( SCIPisIntegral(scip, lb2) );
1495  SCIP_CALL( SCIPtightenVarUb(scip, varj, lb2 + 1.0, TRUE, infeasible, &success) );
1496  }
1497  else
1498  {
1499  assert( SCIPisIntegral(scip, ub2) );
1500  SCIP_CALL( SCIPtightenVarUb(scip, varj, ub2 - 1.0, TRUE, infeasible, &success) );
1501  }
1502  if ( success )
1503  *nreductions += 1;
1504  if ( *infeasible )
1505  goto FREEMEMORY;
1506  ubj = ubj - 1.0;
1507  assert( SCIPsymLE(scip, lbj, ubj) );
1508  break;
1510  /* continuous variable type: act as if we decrease the variable by a very little bit.
1511  * that is only possible if we're able to decrease the variable bound by a bit. */
1512  if ( SCIPsymEQ(scip, lbj, ubj) )
1513  {
1514  *infeasible = TRUE;
1515  goto FREEMEMORY;
1516  }
1517  break;
1518  default:
1519  return SCIP_ERROR;
1520  }
1521  }
1522  }
1523  }
1524  FREEMEMORY:
1525  SCIPfreeBufferArray(scip, &peekbdset);
1526  SCIPfreeBufferArray(scip, &peekubs);
1527  SCIPfreeBufferArray(scip, &peeklbs);
1528  }
1529 
1530  return SCIP_OKAY;
1531 }
1532 
1533 
1534 /** propagation method for a dynamic lexicographic reduction */
1535 static
1537  SCIP* scip, /**< SCIP data structure */
1538  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1539  LEXDATA* lexdata, /**< pointer to data for this permutation */
1540  NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
1541  int nvarstotal, /**< length of nodedepthbranchindices array */
1542  SCIP_VAR** branchvars, /**< array populated with variables branched on */
1543  int nbranchvars, /**< number of elements in branchvars array */
1544  SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1545  int* nreductions /**< pointer to store the number of found domain reductions */
1546  )
1547 {
1548  int* varorder;
1549  int nvarorder;
1550  int nvars;
1551 
1552  assert( scip != NULL );
1553  assert( masterdata != NULL );
1554  assert( lexdata != NULL );
1555  assert( lexdata->isdynamic );
1556  assert( nodedepthbranchindices != NULL );
1557  assert( nvarstotal >= 0 );
1558  assert( branchvars != NULL );
1559  assert( nbranchvars >= 0 );
1560  assert( infeasible != NULL );
1561  assert( nreductions != NULL );
1562 
1563  nvars = lexdata->nvars;
1564 
1565  /* get variable order */
1566  SCIP_CALL( SCIPallocBufferArray(scip, &varorder, nvars) );
1567 
1568  SCIP_CALL( getVarOrder(scip, masterdata, lexdata, nodedepthbranchindices, nvarstotal, branchvars, nbranchvars,
1569  varorder, &nvarorder, nvars) );
1570  assert( nvarorder >= 0 );
1571  assert( nvarorder <= nvars );
1572 
1573  /* possibly propagate the constraint with this variable order */
1574  if ( nvarorder > 0 )
1575  {
1576  SCIP_CALL( propagateStaticLexred(scip, lexdata, varorder, nvarorder, infeasible, nreductions) );
1577  }
1578  SCIPfreeBufferArray(scip, &varorder);
1579 
1580  return SCIP_OKAY;
1581 }
1582 
1583 
1584 /** propagation method for a dynamic lexicographic reduction */
1585 static
1587  SCIP* scip, /**< SCIP data structure */
1588  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1589  LEXDATA* lexdata, /**< pointer to data for this permutation */
1590  SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1591  int* nreductions /**< pointer to store the number of found domain reductions */
1592  )
1593 {
1594  assert( scip != NULL );
1595  assert( masterdata != NULL );
1596  assert( lexdata != NULL );
1597  assert( ! lexdata->isdynamic );
1598  assert( infeasible != NULL );
1599  assert( nreductions != NULL );
1600 
1601  /* skip trivial cases */
1602  if ( lexdata->nvars == 0 )
1603  return SCIP_OKAY;
1604 
1605  /* propagate the constraint with this variable order */
1606  SCIP_CALL( propagateStaticLexred(scip, lexdata, NULL, lexdata->nvars, infeasible, nreductions) );
1607 
1608  return SCIP_OKAY;
1609 }
1610 
1611 
1612 /** propagation method for applying dynamic lexicographic reduction for a single permutation */
1613 static
1615  SCIP* scip, /**< SCIP data structure */
1616  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1617  LEXDATA* lexdata, /**< pointer to data for this permutation */
1618  NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
1619  int nvarstotal, /**< length of that array */
1620  SCIP_VAR** branchvars, /**< array populated with variables branched on */
1621  int nbranchvars, /**< number of elements in branchvars array */
1622  SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1623  int* nreductions /**< pointer to store the number of found domain reductions */
1624  )
1625 {
1626  assert( scip != NULL );
1627  assert( masterdata != NULL );
1628  assert( lexdata != NULL );
1629  assert( nodedepthbranchindices != NULL || ! lexdata->isdynamic );
1630  assert( nvarstotal >= 0 || ! lexdata->isdynamic );
1631  assert( branchvars != NULL || ! lexdata->isdynamic );
1632  assert( nbranchvars >= 0 || ! lexdata->isdynamic );
1633  assert( infeasible != NULL );
1634  assert( nreductions != NULL );
1635 
1636  *nreductions = 0;
1637  *infeasible = FALSE;
1638 
1639  if ( lexdata->isdynamic )
1640  {
1641  SCIP_CALL( propagateLexredDynamic(scip, masterdata, lexdata,
1642  nodedepthbranchindices, nvarstotal, branchvars, nbranchvars, infeasible, nreductions) );
1643  }
1644  else
1645  {
1646  SCIP_CALL( propagateLexredStatic(scip, masterdata, lexdata, infeasible, nreductions) );
1647  }
1648 
1649  return SCIP_OKAY;
1650 }
1651 
1652 
1653 /** populates array with information of first variable change
1654  * @pre assuming nodedepthbranchindices is initially clean
1655  */
1656 static
1658  SCIP* scip, /**< SCIP data structure */
1659  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1660  NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array to populate */
1661  SCIP_VAR** branchvars, /**< array to populate with variables branched on */
1662  int* nbranchvars, /**< number of elements in branchvars array */
1663  SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree structure */
1664  SCIP_NODE* focusnode, /**< focusnode to which the rooted path is evaluated */
1665  SCIP_Bool* inforesolved /**< pointer to store whether information is successfully resolved */
1666  )
1667 {
1668  SCIP_SHADOWNODE* shadownode;
1669  SCIP_SHADOWNODE* shadowchild;
1670  int shadowdepth;
1671  SCIP_VAR* var;
1672  int varindex;
1673  int nlevelvars;
1674  int c;
1675  int i;
1676 
1677  assert( scip != NULL );
1678  assert( masterdata != NULL );
1679  assert( masterdata->symvarmap != NULL );
1680  assert( masterdata->nsymvars >= 0 );
1681  assert( nodedepthbranchindices != NULL );
1682  assert( branchvars != NULL );
1683  assert( nbranchvars != NULL );
1684  assert( shadowtree != NULL );
1685  assert( focusnode != NULL );
1686  assert( inforesolved != NULL );
1687 
1688  shadownode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1689 
1690  if ( shadownode == NULL )
1691  {
1692  /* the arrays to fill are unchanged, so they remain clean */
1693  *inforesolved = FALSE;
1694  if ( !masterdata->treewarninggiven )
1695  {
1696  SCIPwarningMessage(scip, "Attempting lexicographic reduction on nodes not existing in the symmetry shadowtree"
1697  " (and suppressing future warnings)\n");
1698  masterdata->treewarninggiven = TRUE;
1699  }
1700  return SCIP_OKAY;
1701  }
1702  shadowdepth = SCIPnodeGetDepth(focusnode);
1703 
1704  /* branchvars array is initially empty */
1705  *nbranchvars = 0;
1706 
1707  /* We start looking one level lower, because we consider the branching decisions each time. */
1708  shadownode = shadownode->parent;
1709 
1710  /* Now, walk from the leaf to the root. Each time look at all the children of the node considered,
1711  * and save the variable depth and index in the branching array. It is important to consider all children each time,
1712  * because we need to comply with the instance where in different branches it is branched on different variables.
1713  * This has to be consistent.
1714  */
1715  while (shadownode != NULL)
1716  {
1717  assert( shadowdepth > 0 );
1718  nlevelvars = 0;
1719  for (c = 0; c < shadownode->nchildren; ++c)
1720  {
1721  shadowchild = shadownode->children[c];
1722 
1723  /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1724  for (i = 0; i < shadowchild->nbranchingdecisions; ++i)
1725  {
1726  var = shadowchild->branchingdecisions[i].var;
1727  assert( SCIPvarIsTransformed(var) );
1728 
1729  varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
1730 
1731  /* ignore variables that are irrelevant for lexicographic reduction */
1732  if ( varindex == INT_MAX )
1733  continue;
1734 
1735  assert( varindex >= 0 );
1736  assert( varindex < masterdata->nsymvars );
1737 
1738  /* var already in other child at this level? Continue */
1739  if ( nodedepthbranchindices[varindex].nodedepth == shadowdepth )
1740  continue;
1741 
1742  /* the variable is either not seen (nodedepth == 0), or it is at a higher level (nodedepth > shadowdepth) */
1743  assert( nodedepthbranchindices[varindex].nodedepth == 0 ||
1744  nodedepthbranchindices[varindex].nodedepth > shadowdepth);
1745 
1746  if ( nodedepthbranchindices[varindex].nodedepth == 0 )
1747  {
1748  /* variable is not featured in branchvars, yet */
1749  assert( *nbranchvars < masterdata->nsymvars );
1750  branchvars[(*nbranchvars)++] = var;
1751  }
1752 
1753  /* var is not seen on this level yet. Update */
1754  nodedepthbranchindices[varindex].nodedepth = shadowdepth;
1755  nodedepthbranchindices[varindex].index = nlevelvars++;
1756  }
1757  }
1758 
1759  /* prepare for the next iteration */
1760  shadownode = shadownode->parent;
1761  --shadowdepth;
1762  }
1763  /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1764  assert( shadowdepth == 0 );
1765 
1766  *inforesolved = TRUE;
1767  return SCIP_OKAY;
1768 }
1769 
1770 
1771 /** cleans nodedepthbranchindices array */
1772 static
1774  SCIP* scip, /**< SCIP data structure */
1775  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1776  NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array populated by nodedepthbranchindices to clean */
1777  SCIP_VAR** branchvars, /**< array populated with variables branched on */
1778  int* nbranchvars, /**< number of elements in branchvars array */
1779  SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree structure */
1780  SCIP_NODE* focusnode /**< focusnode to which the rooted path is evaluated */
1781  )
1782 {
1783  /* undo the operations from shadowtreeFillNodeDepthBranchIndices, which makes nodedepthbranchindices clean */
1784  SCIP_SHADOWNODE* shadownode;
1785  SCIP_SHADOWNODE* shadowchild;
1786 #ifndef NDEBUG
1787  int shadowdepth;
1788 #endif
1789  SCIP_VAR* var;
1790  int varindex;
1791  int c;
1792  int i;
1793 
1794  assert( scip != NULL );
1795  assert( masterdata != NULL );
1796  assert( masterdata->symvarmap != NULL );
1797  assert( masterdata->nsymvars >= 0 );
1798  assert( nodedepthbranchindices != NULL );
1799  assert( branchvars != NULL );
1800  assert( nbranchvars != NULL );
1801  assert( *nbranchvars >= 0 );
1802  assert( *nbranchvars <= masterdata->nsymvars );
1803  assert( shadowtree != NULL );
1804  assert( focusnode != NULL );
1805 
1806  shadownode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1807 #ifndef NDEBUG
1808  shadowdepth = SCIPnodeGetDepth(focusnode);
1809 #endif
1810 
1811  /* clean nbranchvars array */
1812  while ( *nbranchvars > 0 )
1813  branchvars[--(*nbranchvars)] = NULL;
1814  assert( *nbranchvars == 0 );
1815 
1816  /* we start looking one level lower, because we consider the branching decisions each time */
1817  /* coverity[dereference] */
1818  shadownode = shadownode->parent;
1819 
1820  /* now, walk from the leaf to the root. Each time look at all the children of the node considered,
1821  * and save the variable depth and index in the branching array. It is important to consider all children each time,
1822  * because we need to comply with the instance where in different branches it is branched on different variables.
1823  * This has to be consistent.
1824  */
1825  while (shadownode != NULL)
1826  {
1827 #ifndef NDEBUG
1828  assert( shadowdepth > 0 );
1829 #endif
1830  for (c = 0; c < shadownode->nchildren; ++c)
1831  {
1832  shadowchild = shadownode->children[c];
1833  /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1834  for (i = 0; i < shadowchild->nbranchingdecisions; ++i)
1835  {
1836  var = shadowchild->branchingdecisions[i].var;
1837  /* ignore variables not relevant for lexicographic reduction */
1838  if ( !SCIPhashmapExists(masterdata->symvarmap, (void*) var) )
1839  continue;
1840  assert( SCIPhashmapExists(masterdata->symvarmap, (void*) var) );
1841 
1842  varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
1843  assert( varindex >= 0 );
1844  assert( varindex < masterdata->nsymvars );
1845 
1846  /* reset */
1847  nodedepthbranchindices[varindex].index = 0;
1848  nodedepthbranchindices[varindex].nodedepth = 0;
1849  }
1850  }
1851 
1852  /* prepare for the next iteration */
1853  shadownode = shadownode->parent;
1854 #ifndef NDEBUG
1855  --shadowdepth;
1856 #endif
1857  }
1858  /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1859  assert( shadowdepth == 0 );
1860 
1861  return SCIP_OKAY;
1862 }
1863 
1864 
1865 /*
1866  * Interface methods
1867  */
1868 
1869 
1870 /** prints lexicographic reduction propagation data */
1872  SCIP* scip, /**< SCIP data structure */
1873  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1874  int* nred, /**< total number of reductions applied */
1875  int* ncutoff /**< total number of cutoffs applied */
1876  )
1877 {
1878  assert( scip != NULL );
1879  assert( masterdata != NULL );
1880  assert( nred != NULL );
1881 
1882  *nred = masterdata->nred;
1883  *ncutoff = masterdata->ncutoff;
1884 
1885  return SCIP_OKAY;
1886 }
1887 
1888 /** prints lexicographic reduction propagation data */
1890  SCIP* scip, /**< SCIP data structure */
1891  SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
1892  )
1893 {
1894  int i;
1895 
1896  assert( scip != NULL );
1897  assert( masterdata != NULL );
1898 
1899  if ( masterdata->nlexdatas == 0 )
1900  {
1901  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: no permutations\n");
1902  return SCIP_OKAY;
1903  }
1904 
1905  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: %4d permutations with support sizes ",
1906  masterdata->nlexdatas);
1907 
1908  for (i = 0; i < masterdata->nlexdatas; ++i)
1909  {
1910  if ( i > 0 )
1912  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", masterdata->lexdatas[i]->nvars);
1913  }
1914 
1916 
1917  return SCIP_OKAY;
1918 }
1919 
1920 
1921 /** applies lexicographic reduction propagation */
1923  SCIP* scip, /**< SCIP data structure */
1924  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1925  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1926  int* nred, /**< pointer to store the number of domain reductions */
1927  SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
1928  * only set this to TRUE when a reduction is found, never set to FALSE */
1929  )
1930 {
1931  int nlocalred;
1932  int p;
1933  SCIP_SHADOWTREE* shadowtree = NULL;
1934  SCIP_NODE* focusnode = NULL;
1936  SCIP_VAR** branchvars = NULL;
1937  int nbranchvars = 0;
1938  SCIP_Bool inforesolved;
1939 
1940  assert( scip != NULL );
1941  assert( masterdata != NULL );
1942  assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
1943  assert( masterdata->nlexdatas >= 0 );
1944  assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
1945  assert( infeasible != NULL );
1946  assert( nred != NULL );
1947  assert( didrun != NULL );
1948 
1949  *infeasible = FALSE;
1950  *nred = 0;
1951 
1952  /* early termination */
1953  if ( masterdata->nlexdatas == 0 )
1954  return SCIP_OKAY;
1955 
1956  /* compute the variable ordering based on the branching decisions
1957  * of the shadowtree if there exist dynamic permutations
1958  */
1959  if ( masterdata->hasdynamicperm )
1960  {
1961  assert( masterdata->shadowtreeeventhdlr != NULL );
1962  shadowtree = SCIPgetShadowTree(masterdata->shadowtreeeventhdlr);
1963  focusnode = SCIPgetFocusNode(scip);
1964 
1965  /* fill the node-depth-branch-indices structure
1966  *
1967  * this is an array that maps every variable index to (depth, index) = (0, 0) if the variable is not branched on,
1968  * or (depth, index) is the depth (branching at root node: depth 1) and variable index when it was branched thereon.
1969  * For individual dynamic lexicographic reductions, we use this ordering the following way:
1970  * 1. Choose those variables that have (depth, index) with depth > 0 (these)
1971  * 2. Sort by depth, then by index, in increasing order.
1972  */
1973  SCIP_CALL( SCIPallocCleanBufferArray(scip, &nodedepthbranchindices, masterdata->nsymvars) );
1974  SCIP_CALL( SCIPallocCleanBufferArray(scip, &branchvars, masterdata->nsymvars) );
1975  SCIP_CALL( shadowtreeFillNodeDepthBranchIndices(scip, masterdata, nodedepthbranchindices,
1976  branchvars, &nbranchvars, shadowtree, focusnode, &inforesolved) );
1977 
1978  /* if the information cannot be resolved because a node is missing from the shadowtree, do not propagate */
1979  if ( !inforesolved )
1980  {
1981  /* shadowtreeFillNodeDepthBranchIndices keeps the input arrays clean if it terminates early */
1982  SCIPfreeCleanBufferArray(scip, &branchvars);
1983  SCIPfreeCleanBufferArray(scip, &nodedepthbranchindices);
1984  return SCIP_OKAY;
1985  }
1986  /* ... Do everything using this nodedepthbranchindices structure */
1987  }
1988 
1989  if ( nbranchvars > 0 || ! masterdata->hasdynamicperm )
1990  {
1991  /* apply lexicographic reduction propagator to all lexdata objects */
1992  for (p = 0; p < masterdata->nlexdatas; ++p)
1993  {
1994  assert( masterdata->lexdatas[p] != NULL );
1995 
1996  SCIP_CALL( propagateLexicographicReductionPerm(scip, masterdata, masterdata->lexdatas[p],
1997  nodedepthbranchindices, masterdata->nsymvars, branchvars, nbranchvars, infeasible, &nlocalred) );
1998 
1999  /* keep track of the total number of fixed vars */
2000  *nred += nlocalred;
2001 
2002  /* a symmetry propagator has ran, so set didrun to TRUE */
2003  *didrun = TRUE;
2004 
2005  /* stop if we find infeasibility */
2006  if ( *infeasible )
2007  break;
2008  }
2009 
2010  /* maintain total number of reductions made */
2011  masterdata->nred += *nred;
2012  if ( *infeasible )
2013  ++masterdata->ncutoff;
2014  }
2015 
2016  /* possibly clean the node-depth-branch-indices structure */
2017  if ( masterdata->hasdynamicperm )
2018  {
2019  assert( shadowtree != NULL );
2020  assert( focusnode != NULL );
2021  SCIP_CALL( shadowtreeUndoNodeDepthBranchIndices(scip, masterdata, nodedepthbranchindices,
2022  branchvars, &nbranchvars, shadowtree, focusnode) );
2023  assert( nbranchvars == 0 );
2024  SCIPfreeCleanBufferArray(scip, &branchvars);
2025  SCIPfreeCleanBufferArray(scip, &nodedepthbranchindices);
2026  }
2027 
2028  return SCIP_OKAY;
2029 }
2030 
2031 
2032 /** adds permutation for lexicographic reduction propagation */
2034  SCIP* scip, /**< SCIP data structure */
2035  SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
2036  SCIP_VAR** permvars, /**< variable array of the permutation */
2037  int npermvars, /**< number of variables in that array */
2038  int* perm, /**< permutation */
2039  SYM_SYMTYPE symtype, /**< type of symmetries in perm */
2040  SCIP_Real* permvardomaincenter, /**< array containing center point for each variable domain */
2041  SCIP_Bool usedynamicorder, /**< whether a dynamic variable order shall be used */
2042  SCIP_Bool* success /**< to store whether the component is successfully added */
2043  )
2044 {
2045  assert( scip != NULL );
2046  assert( masterdata != NULL );
2047  assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2048  assert( masterdata->nlexdatas >= 0 );
2049  assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2050  assert( masterdata->shadowtreeeventhdlr != NULL );
2051  assert( permvars != NULL );
2052  assert( npermvars > 0 );
2053  assert( perm != NULL );
2054 
2055  if ( symtype != SYM_SYMTYPE_PERM && symtype != SYM_SYMTYPE_SIGNPERM )
2056  {
2057  *success = FALSE;
2058  return SCIP_OKAY;
2059  }
2060  assert( symtype == SYM_SYMTYPE_PERM || permvardomaincenter != NULL );
2061  assert( SCIPisTransformed(scip) );
2062 
2063  /* resize component array if needed */
2064  if ( masterdata->nlexdatas == masterdata->maxnlexdatas )
2065  {
2066  int newsize;
2067 
2068  newsize = SCIPcalcMemGrowSize(scip, masterdata->nlexdatas + 1);
2069  assert( newsize >= 0 );
2070 
2071  if ( masterdata->nlexdatas == 0 )
2072  {
2073  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &masterdata->lexdatas, newsize) );
2074  }
2075  else
2076  {
2077  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &masterdata->lexdatas,
2078  masterdata->maxnlexdatas, newsize) );
2079  }
2080 
2081  masterdata->maxnlexdatas = newsize;
2082  }
2083 
2084  /* prepare lexdatas */
2085  SCIP_CALL( lexdataCreate(scip, masterdata, &masterdata->lexdatas[masterdata->nlexdatas],
2086  permvars, npermvars, perm, symtype, permvardomaincenter, usedynamicorder, success) );
2087 
2088  /* if not successfully added, undo increasing the counter */
2089  if ( *success )
2090  ++masterdata->nlexdatas;
2091 
2092  return SCIP_OKAY;
2093 }
2094 
2095 
2096 /** resets lexicographic reduction propagation (removes all permutations) */
2098  SCIP* scip, /**< SCIP data structure */
2099  SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
2100  )
2101 {
2102  assert( scip != NULL );
2103  assert( masterdata != NULL );
2104  assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2105  assert( masterdata->nlexdatas >= 0 );
2106  assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2107  assert( masterdata->shadowtreeeventhdlr != NULL );
2108 
2109  while ( masterdata->nlexdatas > 0 )
2110  {
2111  SCIP_CALL( lexdataFree(scip, &(masterdata->lexdatas[--masterdata->nlexdatas])) );
2112  }
2113  assert( masterdata->nlexdatas == 0 );
2114 
2115  SCIPfreeBlockMemoryArrayNull(scip, &masterdata->lexdatas, masterdata->maxnlexdatas);
2116  masterdata->lexdatas = NULL;
2117  masterdata->maxnlexdatas = 0;
2118 
2119  assert( masterdata->nsymvars >= 0 );
2120  assert( (masterdata->symvarmap == NULL) == (masterdata->nsymvars == 0) );
2121  if ( masterdata->symvarmap != NULL )
2122  {
2123  SCIPhashmapFree(&masterdata->symvarmap);
2124  masterdata->symvarmap = NULL;
2125  masterdata->nsymvars = 0;
2126  }
2127 
2128  masterdata->hasdynamicperm = FALSE;
2129 
2130  return SCIP_OKAY;
2131 }
2132 
2133 
2134 /** frees lexicographic reduction data */
2136  SCIP* scip, /**< SCIP data structure */
2137  SCIP_LEXREDDATA** masterdata /**< pointer to global data for lexicographic reduction propagator */
2138  )
2139 {
2140  assert( scip != NULL );
2141  assert( masterdata != NULL );
2142  assert( *masterdata != NULL );
2143 
2144  SCIP_CALL( SCIPlexicographicReductionReset(scip, *masterdata) );
2145  assert( (*masterdata)->lexdatas == NULL );
2146  assert( (*masterdata)->symvarmap == NULL );
2147 
2148  SCIPfreeBlockMemory(scip, masterdata);
2149  return SCIP_OKAY;
2150 }
2151 
2152 
2153 /** initializes structures needed for lexicographic reduction propagation
2154  *
2155  *
2156  * This is only done exactly once.
2157  */
2159  SCIP* scip, /**< SCIP data structure */
2160  SCIP_LEXREDDATA** masterdata, /**< pointer to global data for lexicographic reduction propagator */
2161  SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */
2162  )
2163 {
2164  assert( scip != NULL );
2165  assert( masterdata != NULL );
2166  assert( shadowtreeeventhdlr != NULL );
2167 
2168  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeLexicographicReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2169  FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2170 
2171  SCIP_CALL( SCIPallocBlockMemory(scip, masterdata) );
2172 
2173  (*masterdata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
2174  (*masterdata)->symvarmap = NULL;
2175  (*masterdata)->nsymvars = 0;
2176  (*masterdata)->lexdatas = NULL;
2177  (*masterdata)->nlexdatas = 0;
2178  (*masterdata)->maxnlexdatas = 0;
2179  (*masterdata)->nred = 0;
2180  (*masterdata)->ncutoff = 0;
2181  (*masterdata)->hasdynamicperm = FALSE;
2182  (*masterdata)->treewarninggiven = FALSE;
2183 
2184  return SCIP_OKAY;
2185 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
static SCIP_RETCODE shadowtreeFillNodeDepthBranchIndices(SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode, SCIP_Bool *inforesolved)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPlexicographicReductionAddPermutation(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_VAR **permvars, int npermvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success)
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
static SCIP_RETCODE getVarOrder(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, int *varorder, int *nselvars, int maxnselvars)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5202
public methods for SCIP parameter handling
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2212
SCIP_HASHMAP * varmap
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
public methods for memory management
public methods for conflict handler plugins and conflict analysis
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
static SCIP_Bool alwaysLTshiftedVars(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
static SCIP_RETCODE propagateUpperBoundSymVar(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1247
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
static SCIP_RETCODE lexdataFree(SCIP *scip, LEXDATA **lexdata)
static SCIP_RETCODE propagateStaticLexred(SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, SCIP_Bool *infeasible, int *nreductions)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
public methods for problem variables
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5319
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPdebugMessage
Definition: pub_message.h:96
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7500
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:596
public methods for SCIP variables
SCIP_RETCODE SCIPincludeLexicographicReduction(SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
static SCIP_RETCODE shadowtreeUndoNodeDepthBranchIndices(SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode)
static SCIP_Bool canGTshiftedVars(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
public methods for numerical tolerances
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
static SCIP_RETCODE propagateLexredStatic(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, SCIP_Bool *infeasible, int *nreductions)
public methods for managing constraints
SCIP_RETCODE SCIPlexicographicReductionPropagate(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE propagateVariablePair(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
SCIP_RETCODE SCIPlexicographicReductionGetStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_RETCODE SCIPactivateShadowTree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE peekStaticLexredIsFeasible(SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, int fixi, int fixj, int fixrow, SCIP_Real fixvaluei, SCIP_Real fixvaluej, SCIP_Bool *peekfeasible, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8714
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
data structures for branch and bound tree
public methods for problem copies
static int varOrderGetIndex(int *varorder, int pos)
#define SCIP_CALL(x)
Definition: def.h:380
SCIP main data structure.
static SCIP_DECL_SORTINDCOMP(sortbynodedepthbranchindices)
type definitions for problem variables
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
struct SCIP_ShadowNode * parent
SCIP_Bool isdynamic
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:91
SCIP_VAR ** vars
methods for debugging
datastructures for block memory pools and memory buffers
public methods for cuts and aggregation rows
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2284
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
SCIP_RETCODE SCIPlexicographicReductionFree(SCIP *scip, SCIP_LEXREDDATA **masterdata)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:72
public methods for the LP relaxation, rows and columns
static SCIP_RETCODE getVarBounds(SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset, SCIP_Real *lb1, SCIP_Real *ub1, SCIP_Real *lb2, SCIP_Real *ub2)
NODEDEPTHBRANCHINDEX * nodedepthbranchindices
SCIP_SHADOWBOUNDUPDATE * branchingdecisions
public methods for branching rule plugins and branching
general public methods
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2360
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE propagateSelfReflectionVar(SCIP *scip, SCIP_VAR *var, SCIP_Real center, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
public methods for solutions
static SCIP_RETCODE lexdataCreate(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA **lexdata, SCIP_VAR *const *vars, int nvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success)
methods for handling symmetries
public methods for the probing mode
public methods for message output
datastructures for problem variables
methods for handling symmetries by dynamic lexicographic ordering reduction
struct SCIP_LexRedData SCIP_LEXREDDATA
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1213
#define SCIP_Real
Definition: def.h:173
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
public methods for message handling
static SCIP_RETCODE propagateLexicographicReductionPerm(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
static SCIP_RETCODE propagateLowerBoundVar(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE propagateLexredDynamic(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions)
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2246
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17562
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
SCIP_SHADOWNODE * SCIPshadowTreeGetShadowNode(SCIP_SHADOWTREE *shadowtree, SCIP_NODE *node)
public methods for global and local (sub)problems
SYM_SYMTYPE symtype
SCIP_Real * vardomaincenter
SCIP_RETCODE SCIPlexicographicReductionReset(SCIP *scip, SCIP_LEXREDDATA *masterdata)
struct SCIP_ShadowNode ** children
SCIP callable library.
SCIP_SHADOWTREE * SCIPgetShadowTree(SCIP_EVENTHDLR *eventhdlr)
memory allocation routines