1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2023 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 */
89 struct LexRedPermData
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 */
120 struct NodeDepthBranchIndex
121 {
122 int nodedepth; /**< depth of var domain change */
123 int index; /**< index of var domain change on node at depth */
124 };
125 typedef struct NodeDepthBranchIndex NODEDEPTHBRANCHINDEX;
126
127
128 /** auxiliary struct to pass branch-and-bound tree information to sort function */
129 struct VarArrayNodeDepthBranchIndex
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 };
135 typedef struct VarArrayNodeDepthBranchIndex VARARRAYNODEDEPTHBRANCHINDEX;
136
137
138 /*
139 * Local methods
140 */
141
142 /** frees dynamic lexicographic reduction propagator data */
143 static
144 SCIP_RETCODE lexdataFree(
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
222 SCIP_RETCODE lexdataCreate(
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;
426 NODEDEPTHBRANCHINDEX* nodedepthbranchindices;
427 SCIP_LEXREDDATA* masterdata;
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
466 int varOrderGetIndex(
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
481 SCIP_RETCODE getVarOrder(
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
486 * rooted path to focus node */
487 int nvarstotal, /**< length of that array */
488 SCIP_VAR** branchvars, /**< array populated with variables branched on in the symvarmap hashset */
489 int nbranchvars, /**< number of elements in branchvars array */
490 int* varorder, /**< array to populate with variable order */
491 int* nselvars, /**< pointer to number of variables in the ordering */
492 int maxnselvars /**< maximal size of the number of selected variables */
493 )
494 {
495 SCIP_VAR** vars;
496 int nvars;
497 SCIP_VAR* var;
498 int varindex;
499 int i;
500
501 assert( scip != NULL );
502 assert( masterdata != NULL );
503 assert( lexdata != NULL );
504 assert( nodedepthbranchindices != NULL );
505 assert( nvarstotal >= 0 );
506 assert( branchvars != NULL );
507 assert( nbranchvars >= 0 );
508 assert( varorder != NULL );
509 assert( nselvars != NULL );
510
511 vars = lexdata->vars;
512 assert( vars != NULL );
513 nvars = lexdata->nvars;
514 assert( nvars >= 0 );
515
516 /* first collect every variable that was branched on */
517 *nselvars = 0;
518
519 if ( nvars < nbranchvars )
520 {
521 /* for permutations with small support, just check all support entries */
522 for (i = 0; i < nvars; ++i)
523 {
524 var = vars[i];
525 assert( var != NULL );
526
527 assert( SCIPhashmapExists(masterdata->symvarmap, (void*) var) );
528 varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
529 assert( varindex >= 0 );
530 assert( varindex < masterdata->nsymvars );
531
532 assert( nodedepthbranchindices[varindex].nodedepth >= 0 );
533
534 /* skip variables that have not been used for branching */
535 if ( nodedepthbranchindices[varindex].nodedepth <= 0 )
536 continue;
537
538 /* add index i of branching variable */
539 assert( i >= 0 );
540 assert( i < nvars );
541 assert( (*nselvars) < maxnselvars );
542 varorder[(*nselvars)++] = i;
543 }
544 }
545 else
546 {
547 /* for permutations where the support is larger than the number of branched vars, check for the branched vars */
548 for (i = 0; i < nbranchvars; ++i)
549 {
550 var = branchvars[i];
551 assert( var != NULL );
552
553 #ifndef NDEBUG
554 /* debugging: test if it is indeed a branched variable! */
555 varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
556 assert( varindex >= 0 );
557 assert( varindex < masterdata->nsymvars );
558 assert( nodedepthbranchindices[varindex].nodedepth > 0 );
559 #endif
560
561 /* get the variable index in the lexdata->vars array */
562 varindex = SCIPhashmapGetImageInt(lexdata->varmap, (void*) var);
563 assert( varindex == INT_MAX || (varindex >= 0 && varindex < lexdata->nvars) );
564
565 /* skip variables that are not permuted by the permutation */
566 if ( varindex == INT_MAX )
567 continue;
568 assert( lexdata->vars[varindex] == var );
569
570 /* add index varindex of the branching variable */
571 varorder[(*nselvars)++] = varindex;
572 }
573 }
574
575 if ( *nselvars > 1 )
576 {
577 /* sort the first n elements of varorder by depth, then by index, as indicated by nodedepthbranchindices. */
578 VARARRAYNODEDEPTHBRANCHINDEX vararraynodedepthbranchindices;
579 vararraynodedepthbranchindices.nodedepthbranchindices = nodedepthbranchindices;
580 vararraynodedepthbranchindices.masterdata = masterdata;
581 vararraynodedepthbranchindices.vars = vars;
582 SCIPsortInd(varorder, sortbynodedepthbranchindices, (void*) &vararraynodedepthbranchindices, *nselvars);
583 }
584
585 return SCIP_OKAY;
586 }
587
588
589 /** gerts local variable bounds or reads bound from peek data */
590 static
591 SCIP_RETCODE getVarBounds(
592 SCIP_VAR* var1, /**< first variable in comparison */
593 SCIP_VAR* var2, /**< second variable in comparison */
594 SCIP_Bool peekmode, /**< whether function is called in peek mode */
595 int varidx1, /**< index of var1 (or NULL) */
596 int varidx2, /**< index of var2 (or NULL) */
597 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
598 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
599 SCIP_Bool* peekbdset, /**< whether peek bounds have been set (or NULL) */
600 SCIP_Real* lb1, /**< pointer to store lower bound of var1 */
601 SCIP_Real* ub1, /**< pointer to store upper bound of var1 */
602 SCIP_Real* lb2, /**< pointer to store lower bound of var2 */
603 SCIP_Real* ub2 /**< pointer to store upper bound of var2 */
604 )
605 {
606 assert( var1 != NULL );
607 assert( var2 != NULL );
608 assert( (!peekmode) || peeklbs != NULL );
609 assert( (!peekmode) || peekubs != NULL );
610 assert( (!peekmode) || peekbdset != NULL );
611 assert( lb1 != NULL );
612 assert( ub1 != NULL );
613 assert( lb2 != NULL );
614 assert( ub2 != NULL );
615
616 if ( peekmode && peekbdset[varidx1] )
617 {
618 *ub1 = peekubs[varidx1];
619 *lb1 = peeklbs[varidx1];
620 }
621 else
622 {
623 *ub1 = SCIPvarGetUbLocal(var1);
624 *lb1 = SCIPvarGetLbLocal(var1);
625 }
626 if ( peekmode && peekbdset[varidx2] )
627 {
628 *ub2 = peekubs[varidx2];
629 *lb2 = peeklbs[varidx2];
630 }
631 else
632 {
633 *ub2 = SCIPvarGetUbLocal(var2);
634 *lb2 = SCIPvarGetLbLocal(var2);
635 }
636
637 return SCIP_OKAY;
638 }
639
640 /** returns whether a shifted variable is always smaller than another shifted variable
641 *
642 * Shifts are always (var - shift).
643 */
644 static
645 SCIP_Bool alwaysLTshiftedVars(
646 SCIP* scip, /**< SCIP data structure */
647 SCIP_VAR* var1, /**< first variable in comparison */
648 SCIP_VAR* var2, /**< second variable in comparison */
649 SCIP_Real shift1, /**< shift of var1 */
650 SCIP_Real shift2, /**< shift of var2 */
651 SCIP_Bool isnegated, /**< whether shift of var2 is negated */
652 SCIP_Bool peekmode, /**< whether function is called in peek mode */
653 int varidx1, /**< index of var1 (or NULL) */
654 int varidx2, /**< index of var2 (or NULL) */
655 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
656 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
657 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
658 )
659 {
660 SCIP_Real ub1;
661 SCIP_Real ub2;
662 SCIP_Real lb1;
663 SCIP_Real lb2;
664
665 assert( scip != NULL );
666 assert( var1 != NULL );
667 assert( var2 != NULL );
668 assert( (!peekmode) || peeklbs != NULL );
669 assert( (!peekmode) || peekubs != NULL );
670 assert( (!peekmode) || peekbdset != NULL );
671
672 SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
673 &lb1, &ub1, &lb2, &ub2) );
674
675 /* for negated variables, check: var1 - shift1 < shift2 - var2 */
676 if ( isnegated && SCIPisLT(scip, ub1, shift1 + shift2 - ub2) )
677 return TRUE;
678
679 /* for non-negated variables, check: var1 - center1 < var2 - center2 */
680 if ( (!isnegated) && SCIPisLT(scip, ub1, shift1 - shift2 + lb2) )
681 return TRUE;
682
683 return FALSE;
684 }
685
686
687 /** returns whether a shifted variable can be greater than another shifted variable
688 *
689 * Shifts are always (var - shift).
690 */
691 static
692 SCIP_Bool canGTshiftedVars(
693 SCIP* scip, /**< SCIP data structure */
694 SCIP_VAR* var1, /**< first variable in comparison */
695 SCIP_VAR* var2, /**< second variable in comparison */
696 SCIP_Real shift1, /**< shift of var1 */
697 SCIP_Real shift2, /**< shift of var2 */
698 SCIP_Bool isnegated, /**< whether shift of var2 is negated */
699 SCIP_Bool peekmode, /**< whether function is called in peek mode */
700 int varidx1, /**< index of var1 (or NULL) */
701 int varidx2, /**< index of var2 (or NULL) */
702 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
703 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
704 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
705 )
706 {
707 SCIP_Real ub1;
708 SCIP_Real ub2;
709 SCIP_Real lb1;
710 SCIP_Real lb2;
711
712 assert( scip != NULL );
713 assert( var1 != NULL );
714 assert( var2 != NULL );
715 assert( (!peekmode) || peeklbs != NULL );
716 assert( (!peekmode) || peekubs != NULL );
717 assert( (!peekmode) || peekbdset != NULL );
718
719 SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
720 &lb1, &ub1, &lb2, &ub2) );
721
722 /* for negated variables, check: var1 - shift1 > shift2 - var2 */
723 if ( isnegated && SCIPisGT(scip, ub1, shift1 + shift2 - ub2) )
724 return TRUE;
725
726 /* for non-negated variables, check: var1 - center1 > var2 - center2 */
727 if ( (!isnegated) && SCIPisGT(scip, ub1, shift1 - shift2 + lb2) )
728 return TRUE;
729
730 return FALSE;
731 }
732
733
734 /** propagates lower bound of first variable in relation x >= y for shifted variables */
735 static
736 SCIP_RETCODE propagateLowerBoundVar(
737 SCIP* scip, /**< SCIP data structure */
738 SCIP_VAR* var1, /**< first variable in pair */
739 SCIP_VAR* var2, /**< second variable in pair */
740 SCIP_Real center1, /**< center of var1 (original var domain) */
741 SCIP_Real center2, /**< center of var2 (original var domain) */
742 SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
743 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
744 int* nreductions, /**< pointer to store number of reductions */
745 SCIP_Bool peekmode, /**< whether function is called in peek mode */
746 int varidx1, /**< index of var1 (or NULL) */
747 int varidx2, /**< index of var2 (or NULL) */
748 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
749 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
750 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
751 )
752 {
753 SCIP_Real ub1;
754 SCIP_Real ub2;
755 SCIP_Real lb1;
756 SCIP_Real lb2;
757
758 SCIP_Bool tighten = FALSE;
759 SCIP_Real newbd;
760
761 assert( (!peekmode) || peeklbs != NULL );
762 assert( (!peekmode) || peekubs != NULL );
763 assert( (!peekmode) || peekbdset != NULL );
764
765 SCIP_CALL( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
766 &lb1, &ub1, &lb2, &ub2) );
767
768 /* tighten domain of var1 to ensure that var1 - center1 >= isnegated * (var2 - center2 ) */
769 if ( isnegated )
770 {
771 if ( SCIPisLT(scip, lb1 - center1, center2 - ub2) )
772 {
773 tighten = TRUE;
774 newbd = center1 + center2 - ub2;
775 }
776 }
777 else
778 {
779 if ( SCIPisLT(scip, lb1 - center1, lb2 - center2) )
780 {
781 tighten = TRUE;
782 newbd = center1 + lb2 - center2;
783 }
784 }
785
786 if ( tighten )
787 {
788 /* in peek mode, only store updated bounds */
789 if ( peekmode )
790 {
791 peeklbs[varidx1] = newbd; /*lint !e644*/
792 peekubs[varidx1] = ub1;
793 peekbdset[varidx1] = TRUE;
794 }
795 else
796 {
797 SCIP_CALL( SCIPtightenVarLb(scip, var1, newbd, TRUE, infeasible, &tighten) );
798 if ( tighten )
799 {
800 SCIPdebugMessage("Restricting variable LB %12s to %5.2f\n", SCIPvarGetName(var1), newbd);
801 *nreductions += 1;
802 }
803 else
804 {
805 SCIPdebugMessage("Restricting variable LB %12s to %5.2f (no success)\n",
806 SCIPvarGetName(var1), newbd);
807 }
808 if ( *infeasible )
809 {
810 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
811 SCIPvarGetName(var1), newbd);
812 return SCIP_OKAY;
813 }
814 }
815 }
816
817 return SCIP_OKAY;
818 }
819
820
821 /** propagates upper bound of second variable in relation x >= y for shifted variables */
822 static
823 SCIP_RETCODE propagateUpperBoundSymVar(
824 SCIP* scip, /**< SCIP data structure */
825 SCIP_VAR* var1, /**< first variable in pair */
826 SCIP_VAR* var2, /**< second variable in pair */
827 SCIP_Real center1, /**< center of var1 (original var domain) */
828 SCIP_Real center2, /**< center of var2 (original var domain) */
829 SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
830 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
831 int* nreductions, /**< pointer to store number of reductions */
832 SCIP_Bool peekmode, /**< whether function is called in peek mode */
833 int varidx1, /**< index of var1 (or NULL) */
834 int varidx2, /**< index of var2 (or NULL) */
835 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
836 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
837 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
838 )
839 {
840 SCIP_Real ub1;
841 SCIP_Real ub2;
842 SCIP_Real lb1;
843 SCIP_Real lb2;
844
845 SCIP_Bool tighten = FALSE;
846 SCIP_Real newbd;
847
848 assert( scip != NULL );
849 assert( var1 != NULL );
850 assert( var2 != NULL );
851 assert( infeasible != NULL );
852 assert( nreductions != NULL );
853 assert( (!peekmode) || peeklbs != NULL );
854 assert( (!peekmode) || peekubs != NULL );
855 assert( (!peekmode) || peekbdset != NULL );
856
857 SCIP_CALL( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
858 &lb1, &ub1, &lb2, &ub2) );
859
860 /* tighten domain of var2 to ensure that var1 - center1 >= isnegated * (var2 - center2 ) */
861 if ( isnegated )
862 {
863 if ( SCIPisLT(scip, ub1 - center1, center2 - lb2) )
864 {
865 tighten = TRUE;
866 newbd = center1 + center2 - ub1;
867 }
868 }
869 else
870 {
871 if ( SCIPisLT(scip, ub1 - center1, ub2 - center2) )
872 {
873 tighten = TRUE;
874 newbd = center2 - center1 + ub1;
875 }
876 }
877
878 if ( tighten )
879 {
880 /* in peek mode, only store updated bounds */
881 if ( peekmode )
882 {
883 if ( isnegated )
884 {
885 peeklbs[varidx2] = newbd; /*lint !e644*/
886 peekubs[varidx2] = ub2;
887 peekbdset[varidx2] = TRUE;
888 }
889 else
890 {
891 peeklbs[varidx2] = lb2;
892 peekubs[varidx2] = newbd;
893 peekbdset[varidx2] = TRUE;
894 }
895 }
896 else
897 {
898 if ( isnegated )
899 {
900 SCIP_CALL( SCIPtightenVarLb(scip, var2, newbd, TRUE, infeasible, &tighten) );
901 }
902 else
903 {
904 SCIP_CALL( SCIPtightenVarUb(scip, var2, newbd, TRUE, infeasible, &tighten) );
905 }
906
907 if ( tighten )
908 {
909 SCIPdebugMessage("Restricting variable %sB %12s to %5.2f\n",
910 isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
911 *nreductions += 1;
912 }
913 else
914 {
915 SCIPdebugMessage("Restricting variable %sB %12s to %5.2f (no success)\n",
916 isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
917 }
918 if ( *infeasible )
919 {
920 SCIPdebugMessage("Detected infeasibility restricting variable %sB %12s to %5.2f\n",
921 isnegated ? "L" : "U", SCIPvarGetName(var2), newbd);
922 return SCIP_OKAY;
923 }
924 }
925 }
926
927 return SCIP_OKAY;
928 }
929
930
931 /** propagates x - c >= c - x */
932 static
933 SCIP_RETCODE propagateSelfReflectionVar(
934 SCIP* scip, /**< SCIP data structure */
935 SCIP_VAR* var, /**< variable */
936 SCIP_Real center, /**< center of var (original var domain) */
937 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
938 int* nreductions, /**< pointer to store number of reductions */
939 SCIP_Bool peekmode, /**< whether function is called in peek mode */
940 int varidx, /**< index of var (or NULL) */
941 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
942 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
943 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
944 )
945 {
946 SCIP_Real ub1;
947 SCIP_Real ub2;
948 SCIP_Real lb1;
949 SCIP_Real lb2;
950 SCIP_Bool tighten = FALSE;
951
952 assert( scip != NULL );
953 assert( var != NULL );
954 assert( infeasible != NULL );
955 assert( nreductions != NULL );
956 assert( (!peekmode) || peeklbs != NULL );
957 assert( (!peekmode) || peekubs != NULL );
958 assert( (!peekmode) || peekbdset != NULL );
959
960 SCIP_CALL( getVarBounds(var, var, peekmode, varidx, varidx, peeklbs, peekubs, peekbdset,
961 &lb1, &ub1, &lb2, &ub2) );
962
963 if ( SCIPisLT(scip, ub1, center) )
964 {
965 *infeasible = TRUE;
966 return SCIP_OKAY;
967 }
968 else if ( SCIPisLT(scip, lb1, center) )
969 {
970 if ( peekmode )
971 {
972 peeklbs[varidx] = center;
973 peekubs[varidx] = ub1;
974 peekbdset[varidx] = TRUE;
975 }
976 else
977 {
978 SCIP_CALL( SCIPtightenVarLb(scip, var, center, TRUE, infeasible, &tighten) );
979 if ( tighten )
980 {
981 SCIPdebugMessage("Restricting variable LB %12s to %5.2f\n", SCIPvarGetName(var), center);
982 *nreductions += 1;
983 }
984 else
985 {
986 SCIPdebugMessage("Restricting variable LB %12s to %5.2f (no success)\n",
987 SCIPvarGetName(var), center);
988 }
989 if ( *infeasible )
990 {
991 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
992 SCIPvarGetName(var), center);
993 return SCIP_OKAY;
994 }
995 }
996 }
997
998 return SCIP_OKAY;
999 }
1000
1001
1002 /** propagates lexicographic order for one pair of symmetric variables */
1003 static
1004 SCIP_RETCODE propagateVariablePair(
1005 SCIP* scip, /**< SCIP data structure */
1006 SCIP_VAR* var1, /**< first variable in pair */
1007 SCIP_VAR* var2, /**< second variable in pair */
1008 SCIP_Real center1, /**< center of var1 (original var domain) */
1009 SCIP_Real center2, /**< center of var2 (original var domain) */
1010 SCIP_Bool isnegated, /**< whether var2 is negated by symmetry */
1011 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1012 int* nreductions, /**< pointer to store number of reductions */
1013 SCIP_Bool peekmode, /**< whether function is called in peek mode */
1014 int varidx1, /**< index of var1 (or NULL) */
1015 int varidx2, /**< index of var2 (or NULL) */
1016 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
1017 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
1018 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
1019 )
1020 {
1021 assert( scip != NULL );
1022 assert( var1 != NULL );
1023 assert( var2 != NULL );
1024 assert( infeasible != NULL );
1025 assert( nreductions != NULL );
1026
1027 /* perform lexicographic comparison: var1 - center1 >= +/- (var2 - center2) */
1028 if ( alwaysLTshiftedVars(scip, var1, var2, center1, center2, isnegated, peekmode,
1029 varidx1, varidx2, peeklbs, peekubs, peekbdset) )
1030 {
1031 #ifdef SCIP_DEBUG
1032 SCIP_Real ub1;
1033 SCIP_Real ub2;
1034 SCIP_Real lb1;
1035 SCIP_Real lb2;
1036
1037 /* get bounds of shifted (and possibly negated) variables */
1038 ub1 = SCIPvarGetUbLocal(var1);
1039 lb1 = SCIPvarGetLbLocal(var1);
1040 ub2 = SCIPvarGetUbLocal(var2);
1041 lb2 = SCIPvarGetLbLocal(var2);
1042
1043 SCIPdebugMessage("Detected infeasibility: x < y for "
1044 "x: lb=%5.2f, ub=%5.2f, shift=%5.2f "
1045 "y: lb=%5.2f, ub=%5.2f, shift=%5.2f negated=%u\n",
1046 lb1, ub1, center1, lb2, ub2, center2, isnegated);
1047 #endif
1048
1049 *infeasible = TRUE;
1050 return SCIP_OKAY;
1051 }
1052
1053 /* for signed permutations, a variable might be mapped to itself */
1054 if ( var1 == var2 )
1055 {
1056 SCIP_CALL( propagateSelfReflectionVar(scip, var1, center1, infeasible, nreductions, peekmode, varidx1,
1057 peeklbs, peekubs, peekbdset) );
1058 }
1059 else
1060 {
1061 SCIP_CALL( propagateLowerBoundVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1062 varidx1, varidx2, peeklbs, peekubs, peekbdset) );
1063 if ( *infeasible )
1064 return SCIP_OKAY;
1065
1066 SCIP_CALL( propagateUpperBoundSymVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1067 varidx1, varidx2, peeklbs, peekubs, peekbdset) );
1068 }
1069
1070 return SCIP_OKAY;
1071 }
1072
1073 /** checks if the static lexred with a certain variable ordering is feasible in the hypothetical scenario where
1074 * variables with indices i and j are fixed to fixvalue (i.e., peeking)
1075 */
1076 static
1077 SCIP_RETCODE peekStaticLexredIsFeasible(
1078 SCIP* scip, /**< SCIP data structure */
1079 LEXDATA* lexdata, /**< pointer to data for this permutation */
1080 int* varorder, /**< array populated with variable order (or NULL for static propagation) */
1081 int nselvars, /**< number of variables in the ordering */
1082 int fixi, /**< variable index of left fixed column */
1083 int fixj, /**< variable index of right fixed column */
1084 int fixrow, /**< row index in var ordering, from which to start peeking */
1085 SCIP_Real fixvaluei, /**< value on which variables i is fixed */
1086 SCIP_Real fixvaluej, /**< value on which variables j is fixed */
1087 SCIP_Bool* peekfeasible, /**< pointer to store whether this is feasible or not */
1088 SCIP_Real* peeklbs, /**< lower bounds of variables in peek mode (or NULL) */
1089 SCIP_Real* peekubs, /**< upper bounds of variables in peek mode (or NULL) */
1090 SCIP_Bool* peekbdset /**< whether peek bounds have been set (or NULL) */
1091 )
1092 {
1093 int row;
1094 int i;
1095 int j;
1096 SCIP_VAR* vari;
1097 SCIP_VAR* varj;
1098 SCIP_Real centeri;
1099 SCIP_Real centerj;
1100 SCIP_Bool issigned;
1101 SCIP_Bool isnegated;
1102 SCIP_Bool infeasible = FALSE;
1103 int nreductions;
1104
1105 assert( scip != NULL );
1106 assert( lexdata != NULL );
1107 assert( lexdata->vars != NULL );
1108 assert( lexdata->nvars >= 0 );
1109 assert( nselvars <= lexdata->nvars );
1110 assert( nselvars > 0 );
1111 assert( fixi >= 0 );
1112 assert( fixi < lexdata->nvars );
1113 assert( fixj < lexdata->nvars );
1114 assert( fixi != fixj || lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1115 assert( fixi != fixj || fixvaluei == fixvaluej ); /*lint !e777*/
1116 assert( fixrow >= 0 );
1117 assert( fixrow < nselvars );
1118 assert( peekfeasible != NULL );
1119 assert( fixi == varOrderGetIndex(varorder, fixrow) );
1120 assert( fixj == (lexdata->invperm[varOrderGetIndex(varorder, fixrow)] % lexdata->nvars) );
1121 assert( fixi == (lexdata->perm[fixj] % lexdata->nvars) );
1122
1123 *peekfeasible = TRUE;
1124 issigned = lexdata->symtype == SYM_SYMTYPE_SIGNPERM ? TRUE : FALSE;
1125 assert( (!issigned) || lexdata->vardomaincenter != NULL );
1126
1127 /* intialize peekbdset */
1128 for (i = 0; i < lexdata->nvars; ++i)
1129 peekbdset[i] = FALSE;
1130
1131 peeklbs[fixi] = fixvaluei;
1132 peeklbs[fixj] = fixvaluej;
1133 peekubs[fixi] = fixvaluei;
1134 peekubs[fixj] = fixvaluej;
1135 peekbdset[fixi] = TRUE;
1136 peekbdset[fixj] = TRUE;
1137
1138 for (row = fixrow + 1; row < nselvars; ++row)
1139 {
1140 /* get left and right column indices */
1141 i = varOrderGetIndex(varorder, row);
1142 j = lexdata->invperm[i];
1143 assert( i == lexdata->perm[j] );
1144
1145 /* no fixed points */
1146 assert( i != j );
1147
1148 assert( 0 <= i && i < lexdata->nvars );
1149 assert( 0 <= j && j < 2 * lexdata->nvars );
1150 assert( issigned || j < lexdata->nvars );
1151
1152 vari = lexdata->vars[i];
1153 if ( j >= lexdata->nvars )
1154 {
1155 assert( lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1156 j = j - lexdata->nvars;
1157 varj = lexdata->vars[j];
1158 isnegated = TRUE;
1159 }
1160 else
1161 {
1162 varj = lexdata->vars[j];
1163 isnegated = FALSE;
1164 }
1165
1166 if ( issigned )
1167 {
1168 assert( lexdata->vardomaincenter != NULL );
1169 centeri = lexdata->vardomaincenter[i];
1170 centerj = lexdata->vardomaincenter[j];
1171 }
1172 else
1173 {
1174 centeri = 0.0;
1175 centerj = 0.0;
1176 }
1177
1178 /* propagate that vari >= varj */
1179
1180 /* vari >= varj can never hold if the maximal value of vari is smaller than the minimal value of varj */
1181 if ( alwaysLTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, TRUE, i, j, peeklbs, peekubs, peekbdset) )
1182 {
1183 *peekfeasible = FALSE;
1184 SCIPdebugMessage("PEEK: Detected infeasibility at row %3d.\n", row);
1185 break;
1186 }
1187
1188 SCIP_CALL( propagateLowerBoundVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1189 i, j, peeklbs, peekubs, peekbdset) );
1190
1191 SCIP_CALL( propagateUpperBoundSymVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1192 i, j, peeklbs, peekubs, peekbdset) );
1193
1194 /* if there exists a solution with vari > varj, reductions are feasible w.r.t. lexred */
1195 if ( canGTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, TRUE,
1196 i, j, peeklbs, peekubs, peekbdset) )
1197 break;
1198 }
1199
1200 return SCIP_OKAY;
1201 }
1202
1203 /** propagates static lexicographic reduction with specified variable ordering */
1204 static
1205 SCIP_RETCODE propagateStaticLexred(
1206 SCIP* scip, /**< SCIP data structure */
1207 LEXDATA* lexdata, /**< pointer to data for this permutation */
1208 int* varorder, /**< array populated with variable order (or NULL if static propagation) */
1209 int nselvars, /**< number of variables in the ordering */
1210 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1211 int* nreductions /**< pointer to store the number of found domain reductions */
1212 )
1213 { /*lint --e{771}*/
1214 int row;
1215 int i = -1;
1216 int j = -1;
1217 SCIP_VAR* vari = NULL;
1218 SCIP_VAR* varj = NULL;
1219 SCIP_Real centeri;
1220 SCIP_Real centerj;
1221 SCIP_Bool success;
1222 SCIP_Bool issigned;
1223 SCIP_Bool isnegated;
1224
1225 assert( scip != NULL );
1226 assert( lexdata != NULL );
1227 assert( nselvars >= 0 );
1228 assert( infeasible != NULL );
1229 assert( !*infeasible );
1230 assert( nreductions != NULL );
1231 assert( *nreductions >= 0 );
1232
1233 /* avoid trivial cases */
1234 if ( nselvars <= 0 )
1235 return SCIP_OKAY;
1236
1237 issigned = lexdata->symtype == SYM_SYMTYPE_SIGNPERM ? TRUE : FALSE;
1238 assert( (!issigned) || lexdata->vardomaincenter != NULL );
1239
1240 /* iterate over the variable array entrywise
1241 *
1242 * We see this as two columns, with the left vector being the variable ordering,
1243 * and the right column the permuted variables of this var ordering.
1244 */
1245 for (row = 0; row < nselvars; ++row)
1246 {
1247 /* left and right column indices */
1248 i = varOrderGetIndex(varorder, row);
1249 j = lexdata->invperm[i];
1250 assert( i == lexdata->perm[j] );
1251
1252 /* no fixed points */
1253 assert( i != j );
1254
1255 assert( 0 <= i && i < lexdata->nvars );
1256 assert( 0 <= j && j < 2 * lexdata->nvars );
1257 assert( issigned || j < lexdata->nvars );
1258
1259 vari = lexdata->vars[i];
1260 if ( j >= lexdata->nvars )
1261 {
1262 assert( issigned );
1263 j = j - lexdata->nvars;
1264 varj = lexdata->vars[j];
1265 isnegated = TRUE;
1266 }
1267 else
1268 {
1269 varj = lexdata->vars[j];
1270 isnegated = FALSE;
1271 }
1272
1273 if ( issigned )
1274 {
1275 assert( lexdata->vardomaincenter != NULL );
1276 centeri = lexdata->vardomaincenter[i];
1277 centerj = lexdata->vardomaincenter[j];
1278 }
1279 else
1280 {
1281 centeri = 0.0;
1282 centerj = 0.0;
1283 }
1284
1285 SCIP_CALL( propagateVariablePair(scip, vari, varj, centeri, centerj, isnegated, infeasible, nreductions, FALSE,
1286 0, 0, NULL, NULL, NULL) );
1287
1288 if ( *infeasible )
1289 return SCIP_OKAY;
1290
1291 /* terminate if there exists a solution being lexicographically strictly larger than its image */
1292 if ( canGTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, FALSE,
1293 0, 0, NULL, NULL, NULL) )
1294 break;
1295 }
1296 assert( vari != NULL );
1297 assert( varj != NULL );
1298 assert( 0 <= i && i < lexdata->nvars );
1299 assert( 0 <= j && j < lexdata->nvars );
1300
1301 /* if the variables in "row" are fixed to the same value, we might find further propagations */
1302 if ( row < nselvars )
1303 {
1304 SCIP_Real* peeklbs;
1305 SCIP_Real* peekubs;
1306 SCIP_Bool* peekbdset;
1307 SCIP_Real ub1;
1308 SCIP_Real ub2;
1309 SCIP_Real lb1;
1310 SCIP_Real lb2;
1311 SCIP_Real lbi;
1312 SCIP_Real ubi;
1313 SCIP_Real lbj;
1314 SCIP_Real ubj;
1315 SCIP_Bool peekfeasible;
1316
1317 SCIP_CALL( getVarBounds(vari, varj, FALSE, 0, 0, NULL, NULL, NULL, &lb1, &ub1, &lb2, &ub2) );
1318
1319 /* special treatment if i-th and j-th variable are the same in a signed permutation */
1320 if ( vari == varj )
1321 {
1322 assert( lexdata->symtype == SYM_SYMTYPE_SIGNPERM );
1323 assert( SCIPGE(scip, lb1, lexdata->vardomaincenter[i]) ); /* propagation enforces xi - center >= center - xi */
1324
1325 /* both variables can only be the same if they are fixed to the domain center */
1326 if ( SCIPGT(scip, lb1, lexdata->vardomaincenter[i]) )
1327 return SCIP_OKAY;
1328
1329 SCIP_CALL( SCIPallocBufferArray(scip, &peeklbs, lexdata->nvars) );
1330 SCIP_CALL( SCIPallocBufferArray(scip, &peekubs, lexdata->nvars) );
1331 SCIP_CALL( SCIPallocBufferArray(scip, &peekbdset, lexdata->nvars) );
1332
1333 SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1334 row, lexdata->vardomaincenter[i], lexdata->vardomaincenter[i],
1335 &peekfeasible, peeklbs, peekubs, peekbdset) );
1336 if ( !peekfeasible )
1337 {
1338 /* both variables cannot be the same, so the non-negated variable must be greater than the domain center */
1339 switch ( SCIPvarGetType(vari) )
1340 {
1341 case SCIP_VARTYPE_BINARY:
1342 case SCIP_VARTYPE_IMPLINT:
1343 case SCIP_VARTYPE_INTEGER:
1344 assert( SCIPisIntegral(scip, lb1) );
1345 SCIP_CALL( SCIPtightenVarLb(scip, vari, lexdata->vardomaincenter[i] + 1.0, TRUE, infeasible, &success) );
1346 if ( success )
1347 *nreductions += 1;
1348 if ( *infeasible )
1349 goto FREEMEMORY;
1350 lb1 = lexdata->vardomaincenter[i] + 1.0;
1351 assert( SCIPLE(scip, lb1, ub1) );
1352 break;
1353 case SCIP_VARTYPE_CONTINUOUS:
1354 /* continuous variable type: act as if we increase the variable by a very little bit.
1355 * This is only possible if we're able to increase the variable bound by a bit.
1356 */
1357 if ( SCIPEQ(scip, lb1, ub1) )
1358 {
1359 *infeasible = TRUE;
1360 goto FREEMEMORY;
1361 }
1362 break;
1363 default:
1364 SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1365 return SCIP_ERROR;
1366 }
1367 }
1368 }
1369 else
1370 {
1371 /* The previous loop is broken at row "row", which allows for choosing vari > varj.
1372 *
1373 * Now check if vari == varj is permitted, and if not, tighten the domain further.
1374 *
1375 * @todo We peek twice if vari and varj are unfixed
1376 * But, if the subcycle only contains var1 and var2, a single peek suffices.
1377 * This is similar to orbisack and symresack propagation.
1378 *
1379 * Case 1: vari is minimal (lbi).
1380 * Then, propagation of lbi = vari >= varj can yield two situations:
1381 * Option 1: varj can take a value < lbi. Then no further reductions can be detected.
1382 * Option 2: varj gets fixed to lbi. Then, we must check if feasibility is found, still.
1383 * If it turns out infeasible, then we know vari cannot take value lbi, so we can increase the lower bound.
1384 */
1385 centeri = 0.0;
1386 centerj = 0.0;
1387
1388 if ( lexdata->vardomaincenter != NULL )
1389 {
1390 centeri = lexdata->vardomaincenter[i];
1391 centerj = lexdata->vardomaincenter[j];
1392 }
1393
1394 /* translate variable bounds to shifted variable domain and take negation into account */
1395 lbi = lb1 - centeri;
1396 ubi = ub1 - centeri;
1397 if ( isnegated )
1398 {
1399 lbj = centerj - ub2;
1400 ubj = centerj - lb2;
1401 }
1402 else
1403 {
1404 lbj = lb2 - centerj;
1405 ubj = ub2 - centerj;
1406 }
1407
1408 /* check whether peek is called */
1409 if ( (!SCIPEQ(scip, lbi, lbj)) && (!SCIPEQ(scip, ubi, ubj)) )
1410 return SCIP_OKAY;
1411
1412 SCIP_CALL( SCIPallocBufferArray(scip, &peeklbs, lexdata->nvars) );
1413 SCIP_CALL( SCIPallocBufferArray(scip, &peekubs, lexdata->nvars) );
1414 SCIP_CALL( SCIPallocBufferArray(scip, &peekbdset, lexdata->nvars) );
1415
1416 if ( SCIPEQ(scip, lbj, lbi) )
1417 {
1418 SCIP_Real fixvalj;
1419
1420 /* translate lbj back to original variable domain of variable j */
1421 if ( isnegated )
1422 fixvalj = centerj - lbj;
1423 else
1424 fixvalj = lbj + centerj;
1425
1426 /* this is Option 2: varj gets fixed to lbi by propagation. */
1427 SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1428 row, lbi + centeri, fixvalj, &peekfeasible, peeklbs, peekubs, peekbdset) );
1429 if ( !peekfeasible )
1430 {
1431 /* vari cannot take value lb1, so we increase the lower bound. (do not use lbi as this is a shifted domain bound) */
1432 switch ( SCIPvarGetType(vari) )
1433 {
1434 case SCIP_VARTYPE_BINARY:
1435 case SCIP_VARTYPE_IMPLINT:
1436 case SCIP_VARTYPE_INTEGER:
1437 /* discrete variable type: increase lower bound by 1. */
1438 assert( SCIPisIntegral(scip, lb1) );
1439 SCIP_CALL( SCIPtightenVarLb(scip, vari, lb1 + 1.0, TRUE, infeasible, &success) );
1440 if ( success )
1441 *nreductions += 1;
1442 if ( *infeasible )
1443 goto FREEMEMORY;
1444 lb1 = lb1 + 1.0;
1445 assert( SCIPLE(scip, lb1, ub1) );
1446 break;
1447 case SCIP_VARTYPE_CONTINUOUS:
1448 /* continuous variable type: act as if we increase the variable by a very little bit.
1449 * That is only possible if we're able to increase the variable bound by a bit.
1450 */
1451 if ( SCIPEQ(scip, lbi, ubi) )
1452 {
1453 *infeasible = TRUE;
1454 goto FREEMEMORY;
1455 }
1456 break;
1457 default:
1458 SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1459 return SCIP_ERROR;
1460 }
1461 }
1462 }
1463
1464 /* Case 2: varj is maximal (ubj).
1465 * Then, propagation of vari >= varj = ubj can yield two situatiosn:
1466 * Option 1: vari can take a value > ubj. Then, no further reductions can be detected.
1467 * Option 2: vari gets fixed to ubj. Then, we must check if feasibility is found, still.
1468 * If it turns out infeasible, then we know varj cannot take value ubj, so we can decrease the upper bound.
1469 */
1470 assert( SCIPGE(scip, ubi, ubj) ); /* this must be the case after reductions in the for-loop */
1471 if ( SCIPEQ(scip, ubi, ubj) )
1472 {
1473 SCIP_Real fixvalj;
1474
1475 /* translate ubj back to original variable domain of variable j */
1476 if ( isnegated )
1477 fixvalj = centerj - ubj;
1478 else
1479 fixvalj = ubj + centerj;
1480
1481 /* this is Option 2: vari gets fixed to ubj by propagation. */
1482 SCIP_CALL( peekStaticLexredIsFeasible(scip, lexdata, varorder, nselvars, i, j,
1483 row, ubi + centeri, fixvalj, &peekfeasible, peeklbs, peekubs, peekbdset) );
1484 if ( !peekfeasible )
1485 {
1486 /* varj cannot take value ub2, so we decrease the upper or lower bound. (do not use ubj as this is a shifted domain bound)*/
1487 switch ( SCIPvarGetType(varj) )
1488 {
1489 case SCIP_VARTYPE_BINARY:
1490 case SCIP_VARTYPE_IMPLINT:
1491 case SCIP_VARTYPE_INTEGER:
1492 /* discrete variable type: decrease upper bound by 1. */
1493 if ( isnegated )
1494 {
1495 assert( SCIPisIntegral(scip, lb2) );
1496 SCIP_CALL( SCIPtightenVarUb(scip, varj, lb2 + 1.0, TRUE, infeasible, &success) );
1497 }
1498 else
1499 {
1500 assert( SCIPisIntegral(scip, ub2) );
1501 SCIP_CALL( SCIPtightenVarUb(scip, varj, ub2 - 1.0, TRUE, infeasible, &success) );
1502 }
1503 if ( success )
1504 *nreductions += 1;
1505 if ( *infeasible )
1506 goto FREEMEMORY;
1507 ubj = ubj - 1.0;
1508 assert( SCIPLE(scip, lbj, ubj) );
1509 break;
1510 case SCIP_VARTYPE_CONTINUOUS:
1511 /* continuous variable type: act as if we decrease the variable by a very little bit.
1512 * that is only possible if we're able to decrease the variable bound by a bit. */
1513 if ( SCIPEQ(scip, lbj, ubj) )
1514 {
1515 *infeasible = TRUE;
1516 goto FREEMEMORY;
1517 }
1518 break;
1519 default:
1520 return SCIP_ERROR;
1521 }
1522 }
1523 }
1524 }
1525 FREEMEMORY:
1526 SCIPfreeBufferArray(scip, &peekbdset);
1527 SCIPfreeBufferArray(scip, &peekubs);
1528 SCIPfreeBufferArray(scip, &peeklbs);
1529 }
1530
1531 return SCIP_OKAY;
1532 }
1533
1534
1535 /** propagation method for a dynamic lexicographic reduction */
1536 static
1537 SCIP_RETCODE propagateLexredDynamic(
1538 SCIP* scip, /**< SCIP data structure */
1539 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1540 LEXDATA* lexdata, /**< pointer to data for this permutation */
1541 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in
1542 * rooted path to focus node */
1543 int nvarstotal, /**< length of nodedepthbranchindices array */
1544 SCIP_VAR** branchvars, /**< array populated with variables branched on */
1545 int nbranchvars, /**< number of elements in branchvars array */
1546 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1547 int* nreductions /**< pointer to store the number of found domain reductions */
1548 )
1549 {
1550 int* varorder;
1551 int nvarorder;
1552 int nvars;
1553
1554 assert( scip != NULL );
1555 assert( masterdata != NULL );
1556 assert( lexdata != NULL );
1557 assert( lexdata->isdynamic );
1558 assert( nodedepthbranchindices != NULL );
1559 assert( nvarstotal >= 0 );
1560 assert( branchvars != NULL );
1561 assert( nbranchvars >= 0 );
1562 assert( infeasible != NULL );
1563 assert( nreductions != NULL );
1564
1565 nvars = lexdata->nvars;
1566
1567 /* get variable order */
1568 SCIP_CALL( SCIPallocBufferArray(scip, &varorder, nvars) );
1569
1570 SCIP_CALL( getVarOrder(scip, masterdata, lexdata, nodedepthbranchindices, nvarstotal, branchvars, nbranchvars,
1571 varorder, &nvarorder, nvars) );
1572 assert( nvarorder >= 0 );
1573 assert( nvarorder <= nvars );
1574
1575 /* possibly propagate the constraint with this variable order */
1576 if ( nvarorder > 0 )
1577 {
1578 SCIP_CALL( propagateStaticLexred(scip, lexdata, varorder, nvarorder, infeasible, nreductions) );
1579 }
1580 SCIPfreeBufferArray(scip, &varorder);
1581
1582 return SCIP_OKAY;
1583 }
1584
1585
1586 /** propagation method for a dynamic lexicographic reduction */
1587 static
1588 SCIP_RETCODE propagateLexredStatic(
1589 SCIP* scip, /**< SCIP data structure */
1590 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1591 LEXDATA* lexdata, /**< pointer to data for this permutation */
1592 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1593 int* nreductions /**< pointer to store the number of found domain reductions */
1594 )
1595 {
1596 assert( scip != NULL );
1597 assert( masterdata != NULL );
1598 assert( lexdata != NULL );
1599 assert( ! lexdata->isdynamic );
1600 assert( infeasible != NULL );
1601 assert( nreductions != NULL );
1602
1603 /* skip trivial cases */
1604 if ( lexdata->nvars == 0 )
1605 return SCIP_OKAY;
1606
1607 /* propagate the constraint with this variable order */
1608 SCIP_CALL( propagateStaticLexred(scip, lexdata, NULL, lexdata->nvars, infeasible, nreductions) );
1609
1610 return SCIP_OKAY;
1611 }
1612
1613
1614 /** propagation method for applying dynamic lexicographic reduction for a single permutation */
1615 static
1616 SCIP_RETCODE propagateLexicographicReductionPerm(
1617 SCIP* scip, /**< SCIP data structure */
1618 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1619 LEXDATA* lexdata, /**< pointer to data for this permutation */
1620 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in
1621 * rooted path to focus node */
1622 int nvarstotal, /**< length of that array */
1623 SCIP_VAR** branchvars, /**< array populated with variables branched on */
1624 int nbranchvars, /**< number of elements in branchvars array */
1625 SCIP_Bool* infeasible, /**< pointer to store whether the problem is infeasible */
1626 int* nreductions /**< pointer to store the number of found domain reductions */
1627 )
1628 {
1629 assert( scip != NULL );
1630 assert( masterdata != NULL );
1631 assert( lexdata != NULL );
1632 assert( nodedepthbranchindices != NULL || ! lexdata->isdynamic );
1633 assert( nvarstotal >= 0 || ! lexdata->isdynamic );
1634 assert( branchvars != NULL || ! lexdata->isdynamic );
1635 assert( nbranchvars >= 0 || ! lexdata->isdynamic );
1636 assert( infeasible != NULL );
1637 assert( nreductions != NULL );
1638
1639 *nreductions = 0;
1640 *infeasible = FALSE;
1641
1642 if ( lexdata->isdynamic )
1643 {
1644 SCIP_CALL( propagateLexredDynamic(scip, masterdata, lexdata,
1645 nodedepthbranchindices, nvarstotal, branchvars, nbranchvars, infeasible, nreductions) );
1646 }
1647 else
1648 {
1649 SCIP_CALL( propagateLexredStatic(scip, masterdata, lexdata, infeasible, nreductions) );
1650 }
1651
1652 return SCIP_OKAY;
1653 }
1654
1655
1656 /** populates array with information of first variable change
1657 * @pre assuming nodedepthbranchindices is initially clean
1658 */
1659 static
1660 SCIP_RETCODE shadowtreeFillNodeDepthBranchIndices(
1661 SCIP* scip, /**< SCIP data structure */
1662 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1663 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array to populate */
1664 SCIP_VAR** branchvars, /**< array to populate with variables branched on */
1665 int* nbranchvars, /**< number of elements in branchvars array */
1666 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree structure */
1667 SCIP_NODE* focusnode, /**< focusnode to which the rooted path is evaluated */
1668 SCIP_Bool* inforesolved /**< pointer to store whether information is successfully resolved */
1669 )
1670 {
1671 SCIP_SHADOWNODE* shadownode;
1672 SCIP_SHADOWNODE* shadowchild;
1673 int shadowdepth;
1674 SCIP_VAR* var;
1675 int varindex;
1676 int nlevelvars;
1677 int c;
1678 int i;
1679
1680 assert( scip != NULL );
1681 assert( masterdata != NULL );
1682 assert( masterdata->symvarmap != NULL );
1683 assert( masterdata->nsymvars >= 0 );
1684 assert( nodedepthbranchindices != NULL );
1685 assert( branchvars != NULL );
1686 assert( nbranchvars != NULL );
1687 assert( shadowtree != NULL );
1688 assert( focusnode != NULL );
1689 assert( inforesolved != NULL );
1690
1691 shadownode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1692
1693 if ( shadownode == NULL )
1694 {
1695 /* the arrays to fill are unchanged, so they remain clean */
1696 *inforesolved = FALSE;
1697 if ( !masterdata->treewarninggiven )
1698 {
1699 SCIPwarningMessage(scip, "Attempting lexicographic reduction on nodes not existing in the symmetry shadowtree"
1700 " (and suppressing future warnings)\n");
1701 masterdata->treewarninggiven = TRUE;
1702 }
1703 return SCIP_OKAY;
1704 }
1705 shadowdepth = SCIPnodeGetDepth(focusnode);
1706
1707 /* branchvars array is initially empty */
1708 *nbranchvars = 0;
1709
1710 /* We start looking one level lower, because we consider the branching decisions each time. */
1711 shadownode = shadownode->parent;
1712
1713 /* Now, walk from the leaf to the root. Each time look at all the children of the node considered,
1714 * and save the variable depth and index in the branching array. It is important to consider all children each time,
1715 * because we need to comply with the instance where in different branches it is branched on different variables.
1716 * This has to be consistent.
1717 */
1718 while (shadownode != NULL)
1719 {
1720 assert( shadowdepth > 0 );
1721 nlevelvars = 0;
1722 for (c = 0; c < shadownode->nchildren; ++c)
1723 {
1724 shadowchild = shadownode->children[c];
1725
1726 /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1727 for (i = 0; i < shadowchild->nbranchingdecisions; ++i)
1728 {
1729 var = shadowchild->branchingdecisions[i].var;
1730 assert( SCIPvarIsTransformed(var) );
1731
1732 varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
1733
1734 /* ignore variables that are irrelevant for lexicographic reduction */
1735 if ( varindex == INT_MAX )
1736 continue;
1737
1738 assert( varindex >= 0 );
1739 assert( varindex < masterdata->nsymvars );
1740
1741 /* var already in other child at this level? Continue */
1742 if ( nodedepthbranchindices[varindex].nodedepth == shadowdepth )
1743 continue;
1744
1745 /* the variable is either not seen (nodedepth == 0), or it is at a higher level (nodedepth > shadowdepth) */
1746 assert( nodedepthbranchindices[varindex].nodedepth == 0 ||
1747 nodedepthbranchindices[varindex].nodedepth > shadowdepth);
1748
1749 if ( nodedepthbranchindices[varindex].nodedepth == 0 )
1750 {
1751 /* variable is not featured in branchvars, yet */
1752 assert( *nbranchvars < masterdata->nsymvars );
1753 branchvars[(*nbranchvars)++] = var;
1754 }
1755
1756 /* var is not seen on this level yet. Update */
1757 nodedepthbranchindices[varindex].nodedepth = shadowdepth;
1758 nodedepthbranchindices[varindex].index = nlevelvars++;
1759 }
1760 }
1761
1762 /* prepare for the next iteration */
1763 shadownode = shadownode->parent;
1764 --shadowdepth;
1765 }
1766 /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1767 assert( shadowdepth == 0 );
1768
1769 *inforesolved = TRUE;
1770 return SCIP_OKAY;
1771 }
1772
1773
1774 /** cleans nodedepthbranchindices array */
1775 static
1776 SCIP_RETCODE shadowtreeUndoNodeDepthBranchIndices(
1777 SCIP* scip, /**< SCIP data structure */
1778 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1779 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array populated by nodedepthbranchindices to clean */
1780 SCIP_VAR** branchvars, /**< array populated with variables branched on */
1781 int* nbranchvars, /**< number of elements in branchvars array */
1782 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree structure */
1783 SCIP_NODE* focusnode /**< focusnode to which the rooted path is evaluated */
1784 )
1785 {
1786 /* undo the operations from shadowtreeFillNodeDepthBranchIndices, which makes nodedepthbranchindices clean */
1787 SCIP_SHADOWNODE* shadownode;
1788 SCIP_SHADOWNODE* shadowchild;
1789 #ifndef NDEBUG
1790 int shadowdepth;
1791 #endif
1792 SCIP_VAR* var;
1793 int varindex;
1794 int c;
1795 int i;
1796
1797 assert( scip != NULL );
1798 assert( masterdata != NULL );
1799 assert( masterdata->symvarmap != NULL );
1800 assert( masterdata->nsymvars >= 0 );
1801 assert( nodedepthbranchindices != NULL );
1802 assert( branchvars != NULL );
1803 assert( nbranchvars != NULL );
1804 assert( *nbranchvars >= 0 );
1805 assert( *nbranchvars <= masterdata->nsymvars );
1806 assert( shadowtree != NULL );
1807 assert( focusnode != NULL );
1808
1809 shadownode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1810 #ifndef NDEBUG
1811 shadowdepth = SCIPnodeGetDepth(focusnode);
1812 #endif
1813
1814 /* clean nbranchvars array */
(14) Event cond_true: |
Condition "*nbranchvars > 0", taking true branch. |
(16) Event loop_begin: |
Jumped back to beginning of loop. |
(17) Event cond_true: |
Condition "*nbranchvars > 0", taking true branch. |
(19) Event loop_begin: |
Jumped back to beginning of loop. |
(20) Event cond_false: |
Condition "*nbranchvars > 0", taking false branch. |
1815 while ( *nbranchvars > 0 )
(15) Event loop: |
Jumping back to the beginning of the loop. |
(18) Event loop: |
Jumping back to the beginning of the loop. |
(21) Event loop_end: |
Reached end of loop. |
1816 branchvars[--(*nbranchvars)] = NULL;
1817 assert( *nbranchvars == 0 );
1818
1819 /* we start looking one level lower, because we consider the branching decisions each time */
1820 shadownode = shadownode->parent;
1821
1822 /* now, walk from the leaf to the root. Each time look at all the children of the node considered,
1823 * and save the variable depth and index in the branching array. It is important to consider all children each time,
1824 * because we need to comply with the instance where in different branches it is branched on different variables.
1825 * This has to be consistent.
1826 */
1827 while (shadownode != NULL)
1828 {
1829 #ifndef NDEBUG
1830 assert( shadowdepth > 0 );
1831 #endif
1832 for (c = 0; c < shadownode->nchildren; ++c)
1833 {
1834 shadowchild = shadownode->children[c];
1835 /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1836 for (i = 0; i < shadowchild->nbranchingdecisions; ++i)
1837 {
1838 var = shadowchild->branchingdecisions[i].var;
1839 /* ignore variables not relevant for lexicographic reduction */
1840 if ( !SCIPhashmapExists(masterdata->symvarmap, (void*) var) )
1841 continue;
1842 assert( SCIPhashmapExists(masterdata->symvarmap, (void*) var) );
1843
1844 varindex = SCIPhashmapGetImageInt(masterdata->symvarmap, var);
1845 assert( varindex >= 0 );
1846 assert( varindex < masterdata->nsymvars );
1847
1848 /* reset */
1849 nodedepthbranchindices[varindex].index = 0;
1850 nodedepthbranchindices[varindex].nodedepth = 0;
1851 }
1852 }
1853
1854 /* prepare for the next iteration */
1855 shadownode = shadownode->parent;
1856 #ifndef NDEBUG
1857 --shadowdepth;
1858 #endif
1859 }
1860 /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1861 assert( shadowdepth == 0 );
1862
1863 return SCIP_OKAY;
1864 }
1865
1866
1867 /*
1868 * Interface methods
1869 */
1870
1871
1872 /** prints lexicographic reduction propagation data */
1873 SCIP_RETCODE SCIPlexicographicReductionGetStatistics(
1874 SCIP* scip, /**< SCIP data structure */
1875 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1876 int* nred, /**< total number of reductions applied */
1877 int* ncutoff /**< total number of cutoffs applied */
1878 )
1879 {
1880 assert( scip != NULL );
1881 assert( masterdata != NULL );
1882 assert( nred != NULL );
1883
1884 *nred = masterdata->nred;
1885 *ncutoff = masterdata->ncutoff;
1886
1887 return SCIP_OKAY;
1888 }
1889
1890 /** prints lexicographic reduction propagation data */
1891 SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(
1892 SCIP* scip, /**< SCIP data structure */
1893 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
1894 )
1895 {
1896 int i;
1897
1898 assert( scip != NULL );
1899 assert( masterdata != NULL );
1900
1901 if ( masterdata->nlexdatas == 0 )
1902 {
1903 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: no permutations\n");
1904 return SCIP_OKAY;
1905 }
1906
1907 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: %4d permutations with support sizes ",
1908 masterdata->nlexdatas);
1909
1910 for (i = 0; i < masterdata->nlexdatas; ++i)
1911 {
1912 if ( i > 0 )
1913 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", ");
1914 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", masterdata->lexdatas[i]->nvars);
1915 }
1916
1917 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "\n");
1918
1919 return SCIP_OKAY;
1920 }
1921
1922
1923 /** applies lexicographic reduction propagation */
1924 SCIP_RETCODE SCIPlexicographicReductionPropagate(
1925 SCIP* scip, /**< SCIP data structure */
1926 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1927 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1928 int* nred, /**< pointer to store the number of domain reductions */
1929 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
1930 * only set this to TRUE when a reduction is found, never set to FALSE */
1931 )
1932 {
1933 int nlocalred;
1934 int p;
1935 SCIP_SHADOWTREE* shadowtree = NULL;
1936 SCIP_NODE* focusnode = NULL;
1937 NODEDEPTHBRANCHINDEX* nodedepthbranchindices = NULL;
1938 SCIP_VAR** branchvars = NULL;
1939 int nbranchvars = 0;
1940 SCIP_Bool inforesolved;
1941
1942 assert( scip != NULL );
1943 assert( masterdata != NULL );
1944 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
1945 assert( masterdata->nlexdatas >= 0 );
1946 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
1947 assert( infeasible != NULL );
1948 assert( nred != NULL );
1949 assert( didrun != NULL );
1950
1951 *infeasible = FALSE;
1952 *nred = 0;
1953
1954 /* early termination */
1955 if ( masterdata->nlexdatas == 0 )
1956 return SCIP_OKAY;
1957
1958 /* compute the variable ordering based on the branching decisions
1959 * of the shadowtree if there exist dynamic permutations
1960 */
1961 if ( masterdata->hasdynamicperm )
1962 {
1963 assert( masterdata->shadowtreeeventhdlr != NULL );
1964 shadowtree = SCIPgetShadowTree(masterdata->shadowtreeeventhdlr);
1965 focusnode = SCIPgetFocusNode(scip);
1966
1967 /* fill the node-depth-branch-indices structure
1968 *
1969 * this is an array that maps every variable index to (depth, index) = (0, 0) if the variable is not branched on,
1970 * or (depth, index) is the depth (branching at root node: depth 1) and variable index when it was branched thereon.
1971 * For individual dynamic lexicographic reductions, we use this ordering the following way:
1972 * 1. Choose those variables that have (depth, index) with depth > 0 (these)
1973 * 2. Sort by depth, then by index, in increasing order.
1974 */
1975 SCIP_CALL( SCIPallocCleanBufferArray(scip, &nodedepthbranchindices, masterdata->nsymvars) );
1976 SCIP_CALL( SCIPallocCleanBufferArray(scip, &branchvars, masterdata->nsymvars) );
1977 SCIP_CALL( shadowtreeFillNodeDepthBranchIndices(scip, masterdata, nodedepthbranchindices,
1978 branchvars, &nbranchvars, shadowtree, focusnode, &inforesolved) );
1979
1980 /* if the information cannot be resolved because a node is missing from the shadowtree, do not propagate */
1981 if ( !inforesolved )
1982 {
1983 /* shadowtreeFillNodeDepthBranchIndices keeps the input arrays clean if it terminates early */
1984 SCIPfreeCleanBufferArray(scip, &branchvars);
1985 SCIPfreeCleanBufferArray(scip, &nodedepthbranchindices);
1986 return SCIP_OKAY;
1987 }
1988 /* ... Do everything using this nodedepthbranchindices structure */
1989 }
1990
1991 if ( nbranchvars > 0 || ! masterdata->hasdynamicperm )
1992 {
1993 /* apply lexicographic reduction propagator to all lexdata objects */
1994 for (p = 0; p < masterdata->nlexdatas; ++p)
1995 {
1996 assert( masterdata->lexdatas[p] != NULL );
1997
1998 SCIP_CALL( propagateLexicographicReductionPerm(scip, masterdata, masterdata->lexdatas[p],
1999 nodedepthbranchindices, masterdata->nsymvars, branchvars, nbranchvars, infeasible, &nlocalred) );
2000
2001 /* keep track of the total number of fixed vars */
2002 *nred += nlocalred;
2003
2004 /* a symmetry propagator has ran, so set didrun to TRUE */
2005 *didrun = TRUE;
2006
2007 /* stop if we find infeasibility */
2008 if ( *infeasible )
2009 break;
2010 }
2011
2012 /* maintain total number of reductions made */
2013 masterdata->nred += *nred;
2014 if ( *infeasible )
2015 ++masterdata->ncutoff;
2016 }
2017
2018 /* possibly clean the node-depth-branch-indices structure */
2019 if ( masterdata->hasdynamicperm )
2020 {
2021 assert( shadowtree != NULL );
2022 assert( focusnode != NULL );
2023 SCIP_CALL( shadowtreeUndoNodeDepthBranchIndices(scip, masterdata, nodedepthbranchindices,
2024 branchvars, &nbranchvars, shadowtree, focusnode) );
2025 assert( nbranchvars == 0 );
2026 SCIPfreeCleanBufferArray(scip, &branchvars);
2027 SCIPfreeCleanBufferArray(scip, &nodedepthbranchindices);
2028 }
2029
2030 return SCIP_OKAY;
2031 }
2032
2033
2034 /** adds permutation for lexicographic reduction propagation */
2035 SCIP_RETCODE SCIPlexicographicReductionAddPermutation(
2036 SCIP* scip, /**< SCIP data structure */
2037 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
2038 SCIP_VAR** permvars, /**< variable array of the permutation */
2039 int npermvars, /**< number of variables in that array */
2040 int* perm, /**< permutation */
2041 SYM_SYMTYPE symtype, /**< type of symmetries in perm */
2042 SCIP_Real* permvardomaincenter, /**< array containing center point for each variable domain */
2043 SCIP_Bool usedynamicorder, /**< whether a dynamic variable order shall be used */
2044 SCIP_Bool* success /**< to store whether the component is successfully added */
2045 )
2046 {
2047 assert( scip != NULL );
2048 assert( masterdata != NULL );
2049 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2050 assert( masterdata->nlexdatas >= 0 );
2051 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2052 assert( masterdata->shadowtreeeventhdlr != NULL );
2053 assert( permvars != NULL );
2054 assert( npermvars > 0 );
2055 assert( perm != NULL );
2056
2057 if ( symtype != SYM_SYMTYPE_PERM && symtype != SYM_SYMTYPE_SIGNPERM )
2058 {
2059 *success = FALSE;
2060 return SCIP_OKAY;
2061 }
2062 assert( symtype == SYM_SYMTYPE_PERM || permvardomaincenter != NULL );
2063 assert( SCIPisTransformed(scip) );
2064
2065 /* resize component array if needed */
2066 if ( masterdata->nlexdatas == masterdata->maxnlexdatas )
2067 {
2068 int newsize;
2069
2070 newsize = SCIPcalcMemGrowSize(scip, masterdata->nlexdatas + 1);
2071 assert( newsize >= 0 );
2072
2073 if ( masterdata->nlexdatas == 0 )
2074 {
2075 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &masterdata->lexdatas, newsize) );
2076 }
2077 else
2078 {
2079 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &masterdata->lexdatas,
2080 masterdata->maxnlexdatas, newsize) );
2081 }
2082
2083 masterdata->maxnlexdatas = newsize;
2084 }
2085
2086 /* prepare lexdatas */
2087 SCIP_CALL( lexdataCreate(scip, masterdata, &masterdata->lexdatas[masterdata->nlexdatas],
2088 permvars, npermvars, perm, symtype, permvardomaincenter, usedynamicorder, success) );
2089
2090 /* if not successfully added, undo increasing the counter */
2091 if ( *success )
2092 ++masterdata->nlexdatas;
2093
2094 return SCIP_OKAY;
2095 }
2096
2097
2098 /** resets lexicographic reduction propagation (removes all permutations) */
2099 SCIP_RETCODE SCIPlexicographicReductionReset(
2100 SCIP* scip, /**< SCIP data structure */
2101 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
2102 )
2103 {
2104 assert( scip != NULL );
2105 assert( masterdata != NULL );
2106 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2107 assert( masterdata->nlexdatas >= 0 );
2108 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2109 assert( masterdata->shadowtreeeventhdlr != NULL );
2110
2111 while ( masterdata->nlexdatas > 0 )
2112 {
2113 SCIP_CALL( lexdataFree(scip, &(masterdata->lexdatas[--masterdata->nlexdatas])) );
2114 }
2115 assert( masterdata->nlexdatas == 0 );
2116
2117 SCIPfreeBlockMemoryArrayNull(scip, &masterdata->lexdatas, masterdata->maxnlexdatas);
2118 masterdata->lexdatas = NULL;
2119 masterdata->maxnlexdatas = 0;
2120
2121 assert( masterdata->nsymvars >= 0 );
2122 assert( (masterdata->symvarmap == NULL) == (masterdata->nsymvars == 0) );
2123 if ( masterdata->symvarmap != NULL )
2124 {
2125 SCIPhashmapFree(&masterdata->symvarmap);
2126 masterdata->symvarmap = NULL;
2127 masterdata->nsymvars = 0;
2128 }
2129
2130 masterdata->hasdynamicperm = FALSE;
2131
2132 return SCIP_OKAY;
2133 }
2134
2135
2136 /** frees lexicographic reduction data */
2137 SCIP_RETCODE SCIPlexicographicReductionFree(
2138 SCIP* scip, /**< SCIP data structure */
2139 SCIP_LEXREDDATA** masterdata /**< pointer to global data for lexicographic reduction propagator */
2140 )
2141 {
2142 assert( scip != NULL );
2143 assert( masterdata != NULL );
2144 assert( *masterdata != NULL );
2145
2146 SCIP_CALL( SCIPlexicographicReductionReset(scip, *masterdata) );
2147 assert( (*masterdata)->lexdatas == NULL );
2148 assert( (*masterdata)->symvarmap == NULL );
2149
2150 SCIPfreeBlockMemory(scip, masterdata);
2151 return SCIP_OKAY;
2152 }
2153
2154
2155 /** initializes structures needed for lexicographic reduction propagation
2156 *
2157 *
2158 * This is only done exactly once.
2159 */
2160 SCIP_RETCODE SCIPincludeLexicographicReduction(
2161 SCIP* scip, /**< SCIP data structure */
2162 SCIP_LEXREDDATA** masterdata, /**< pointer to global data for lexicographic reduction propagator */
2163 SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */
2164 )
2165 {
2166 assert( scip != NULL );
2167 assert( masterdata != NULL );
2168 assert( shadowtreeeventhdlr != NULL );
2169
2170 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeLexicographicReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2171 FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2172
2173 SCIP_CALL( SCIPallocBlockMemory(scip, masterdata) );
2174
2175 (*masterdata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
2176 (*masterdata)->symvarmap = NULL;
2177 (*masterdata)->nsymvars = 0;
2178 (*masterdata)->lexdatas = NULL;
2179 (*masterdata)->nlexdatas = 0;
2180 (*masterdata)->maxnlexdatas = 0;
2181 (*masterdata)->nred = 0;
2182 (*masterdata)->ncutoff = 0;
2183 (*masterdata)->hasdynamicperm = FALSE;
2184 (*masterdata)->treewarninggiven = FALSE;
2185
2186 return SCIP_OKAY;
2187 }
2188