SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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"
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};
100typedef struct LexRedPermData LEXDATA;
101
102
103/** data for dynamic lexicographic reduction propagator */
104struct 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 */
143static
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
212
213 return SCIP_OKAY;
214}
215
216
217/** creates dynamic lexicographic reduction propagator data
218 *
219 * Fixed points are removed.
220 */
221static
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;
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 );
252 assert( masterdata->shadowtreeeventhdlr != NULL );
253
254 *success = TRUE;
255 issignedperm = symtype == SYM_SYMTYPE_PERM ? FALSE : TRUE;
256
257 /* initialize the data structures */
259 (*lexdata)->symtype = symtype;
260
261 (*lexdata)->isdynamic = usedynamicorder;
262
263 /* remove fixed points */
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
272 }
273
274 /* do nothing if reductions would be trivial */
275 if ( naffectedvariables <= 0 )
276 {
279
280 *success = FALSE;
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 {
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 {
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 }
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 );
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 */
421static
423{
424 /* unpack the dataptr */
428 SCIP_VAR** vars;
431
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 */
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 */
465static
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 */
480static
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 );
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) );
529 assert( varindex >= 0 );
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 );
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! */
556 assert( varindex >= 0 );
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);
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. */
583 }
584
585 return SCIP_OKAY;
586}
587
588
589/** gerts local variable bounds or reads bound from peek data */
590static
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 {
625 }
626 if ( peekmode && peekbdset[varidx2] )
627 {
628 *ub2 = peekubs[varidx2];
629 *lb2 = peeklbs[varidx2];
630 }
631 else
632 {
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 */
644static
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
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 */
691static
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
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 */
735static
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
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*/
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",
807 }
808 if ( *infeasible )
809 {
810 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
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 */
822static
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
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*/
888 }
889 else
890 {
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 */
932static
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
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 {
973 peekubs[varidx] = ub1;
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",
988 }
989 if ( *infeasible )
990 {
991 SCIPdebugMessage("Detected infeasibility restricting variable LB %12s to %5.2f\n",
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 */
1003static
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) */
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 */
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",
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 {
1058 }
1059 else
1060 {
1063 if ( *infeasible )
1064 return SCIP_OKAY;
1065
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 */
1076static
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 );
1110 assert( nselvars > 0 );
1111 assert( fixi >= 0 );
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 );
1120 assert( fixj == (lexdata->invperm[varOrderGetIndex(varorder, fixrow)] % lexdata->nvars) );
1121 assert( fixi == (lexdata->perm[fixj] % lexdata->nvars) );
1122
1123 *peekfeasible = TRUE;
1125 assert( (!issigned) || lexdata->vardomaincenter != NULL );
1126
1127 /* intialize peekbdset */
1128 for (i = 0; i < lexdata->nvars; ++i)
1129 peekbdset[i] = FALSE;
1130
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 );
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 */
1182 {
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 */
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 */
1204static
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
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 );
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 */
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( SCIPsymGE(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 ( SCIPsymGT(scip, lb1, lexdata->vardomaincenter[i]) )
1327 return SCIP_OKAY;
1328
1332
1334 row, lexdata->vardomaincenter[i], lexdata->vardomaincenter[i],
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 {
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( SCIPsymLE(scip, lb1, ub1) );
1352 break;
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 ( SCIPsymEQ(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 ( (!SCIPsymEQ(scip, lbi, lbj)) && (!SCIPsymEQ(scip, ubi, ubj)) )
1410 return SCIP_OKAY;
1411
1415
1416 if ( SCIPsymEQ(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. */
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 {
1437 /* discrete variable type: increase lower bound by 1. */
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( SCIPsymLE(scip, lb1, ub1) );
1446 break;
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 ( SCIPsymEQ(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( SCIPsymGE(scip, ubi, ubj) ); /* this must be the case after reductions in the for-loop */
1471 if ( SCIPsymEQ(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. */
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 {
1492 /* discrete variable type: decrease upper bound by 1. */
1493 if ( isnegated )
1494 {
1496 SCIP_CALL( SCIPtightenVarUb(scip, varj, lb2 + 1.0, TRUE, infeasible, &success) );
1497 }
1498 else
1499 {
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( SCIPsymLE(scip, lbj, ubj) );
1509 break;
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 ( SCIPsymEQ(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:
1529 }
1530
1531 return SCIP_OKAY;
1532}
1533
1534
1535/** propagation method for a dynamic lexicographic reduction */
1536static
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 );
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 */
1569
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 }
1581
1582 return SCIP_OKAY;
1583}
1584
1585
1586/** propagation method for a dynamic lexicographic reduction */
1587static
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 */
1615static
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 {
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 */
1659static
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{
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 );
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 */
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;
1731
1733
1734 /* ignore variables that are irrelevant for lexicographic reduction */
1735 if ( varindex == INT_MAX )
1736 continue;
1737
1738 assert( varindex >= 0 );
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 ||
1748
1749 if ( nodedepthbranchindices[varindex].nodedepth == 0 )
1750 {
1751 /* variable is not featured in branchvars, yet */
1753 branchvars[(*nbranchvars)++] = var;
1754 }
1755
1756 /* var is not seen on this level yet. Update */
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 */
1775static
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 */
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 );
1802 assert( branchvars != NULL );
1803 assert( nbranchvars != NULL );
1804 assert( *nbranchvars >= 0 );
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 */
1815 while ( *nbranchvars > 0 )
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 /* coverity[dereference] */
1821 shadownode = shadownode->parent;
1822
1823 /* now, walk from the leaf to the root. Each time look at all the children of the node considered,
1824 * and save the variable depth and index in the branching array. It is important to consider all children each time,
1825 * because we need to comply with the instance where in different branches it is branched on different variables.
1826 * This has to be consistent.
1827 */
1828 while (shadownode != NULL)
1829 {
1830#ifndef NDEBUG
1831 assert( shadowdepth > 0 );
1832#endif
1833 for (c = 0; c < shadownode->nchildren; ++c)
1834 {
1835 shadowchild = shadownode->children[c];
1836 /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1837 for (i = 0; i < shadowchild->nbranchingdecisions; ++i)
1838 {
1839 var = shadowchild->branchingdecisions[i].var;
1840 /* ignore variables not relevant for lexicographic reduction */
1841 if ( !SCIPhashmapExists(masterdata->symvarmap, (void*) var) )
1842 continue;
1843 assert( SCIPhashmapExists(masterdata->symvarmap, (void*) var) );
1844
1846 assert( varindex >= 0 );
1848
1849 /* reset */
1852 }
1853 }
1854
1855 /* prepare for the next iteration */
1856 shadownode = shadownode->parent;
1857#ifndef NDEBUG
1858 --shadowdepth;
1859#endif
1860 }
1861 /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1862 assert( shadowdepth == 0 );
1863
1864 return SCIP_OKAY;
1865}
1866
1867
1868/*
1869 * Interface methods
1870 */
1871
1872
1873/** prints lexicographic reduction propagation data */
1875 SCIP* scip, /**< SCIP data structure */
1876 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1877 int* nred, /**< total number of reductions applied */
1878 int* ncutoff /**< total number of cutoffs applied */
1879 )
1880{
1881 assert( scip != NULL );
1882 assert( masterdata != NULL );
1883 assert( nred != NULL );
1884
1885 *nred = masterdata->nred;
1886 *ncutoff = masterdata->ncutoff;
1887
1888 return SCIP_OKAY;
1889}
1890
1891/** prints lexicographic reduction propagation data */
1893 SCIP* scip, /**< SCIP data structure */
1894 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
1895 )
1896{
1897 int i;
1898
1899 assert( scip != NULL );
1900 assert( masterdata != NULL );
1901
1902 if ( masterdata->nlexdatas == 0 )
1903 {
1904 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: no permutations\n");
1905 return SCIP_OKAY;
1906 }
1907
1908 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: %4d permutations with support sizes ",
1909 masterdata->nlexdatas);
1910
1911 for (i = 0; i < masterdata->nlexdatas; ++i)
1912 {
1913 if ( i > 0 )
1915 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", masterdata->lexdatas[i]->nvars);
1916 }
1917
1919
1920 return SCIP_OKAY;
1921}
1922
1923
1924/** applies lexicographic reduction propagation */
1926 SCIP* scip, /**< SCIP data structure */
1927 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1928 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1929 int* nred, /**< pointer to store the number of domain reductions */
1930 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
1931 * only set this to TRUE when a reduction is found, never set to FALSE */
1932 )
1933{
1934 int nlocalred;
1935 int p;
1936 SCIP_SHADOWTREE* shadowtree = NULL;
1937 SCIP_NODE* focusnode = NULL;
1940 int nbranchvars = 0;
1941 SCIP_Bool inforesolved;
1942
1943 assert( scip != NULL );
1944 assert( masterdata != NULL );
1945 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
1946 assert( masterdata->nlexdatas >= 0 );
1947 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
1948 assert( infeasible != NULL );
1949 assert( nred != NULL );
1950 assert( didrun != NULL );
1951
1952 *infeasible = FALSE;
1953 *nred = 0;
1954
1955 /* early termination */
1956 if ( masterdata->nlexdatas == 0 )
1957 return SCIP_OKAY;
1958
1959 /* compute the variable ordering based on the branching decisions
1960 * of the shadowtree if there exist dynamic permutations
1961 */
1962 if ( masterdata->hasdynamicperm )
1963 {
1964 assert( masterdata->shadowtreeeventhdlr != NULL );
1965 shadowtree = SCIPgetShadowTree(masterdata->shadowtreeeventhdlr);
1966 focusnode = SCIPgetFocusNode(scip);
1967
1968 /* fill the node-depth-branch-indices structure
1969 *
1970 * this is an array that maps every variable index to (depth, index) = (0, 0) if the variable is not branched on,
1971 * or (depth, index) is the depth (branching at root node: depth 1) and variable index when it was branched thereon.
1972 * For individual dynamic lexicographic reductions, we use this ordering the following way:
1973 * 1. Choose those variables that have (depth, index) with depth > 0 (these)
1974 * 2. Sort by depth, then by index, in increasing order.
1975 */
1979 branchvars, &nbranchvars, shadowtree, focusnode, &inforesolved) );
1980
1981 /* if the information cannot be resolved because a node is missing from the shadowtree, do not propagate */
1982 if ( !inforesolved )
1983 {
1984 /* shadowtreeFillNodeDepthBranchIndices keeps the input arrays clean if it terminates early */
1987 return SCIP_OKAY;
1988 }
1989 /* ... Do everything using this nodedepthbranchindices structure */
1990 }
1991
1992 if ( nbranchvars > 0 || ! masterdata->hasdynamicperm )
1993 {
1994 /* apply lexicographic reduction propagator to all lexdata objects */
1995 for (p = 0; p < masterdata->nlexdatas; ++p)
1996 {
1997 assert( masterdata->lexdatas[p] != NULL );
1998
2001
2002 /* keep track of the total number of fixed vars */
2003 *nred += nlocalred;
2004
2005 /* a symmetry propagator has ran, so set didrun to TRUE */
2006 *didrun = TRUE;
2007
2008 /* stop if we find infeasibility */
2009 if ( *infeasible )
2010 break;
2011 }
2012
2013 /* maintain total number of reductions made */
2014 masterdata->nred += *nred;
2015 if ( *infeasible )
2016 ++masterdata->ncutoff;
2017 }
2018
2019 /* possibly clean the node-depth-branch-indices structure */
2020 if ( masterdata->hasdynamicperm )
2021 {
2022 assert( shadowtree != NULL );
2023 assert( focusnode != NULL );
2025 branchvars, &nbranchvars, shadowtree, focusnode) );
2026 assert( nbranchvars == 0 );
2029 }
2030
2031 return SCIP_OKAY;
2032}
2033
2034
2035/** adds permutation for lexicographic reduction propagation */
2037 SCIP* scip, /**< SCIP data structure */
2038 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
2039 SCIP_VAR** permvars, /**< variable array of the permutation */
2040 int npermvars, /**< number of variables in that array */
2041 int* perm, /**< permutation */
2042 SYM_SYMTYPE symtype, /**< type of symmetries in perm */
2043 SCIP_Real* permvardomaincenter, /**< array containing center point for each variable domain */
2044 SCIP_Bool usedynamicorder, /**< whether a dynamic variable order shall be used */
2045 SCIP_Bool* success /**< to store whether the component is successfully added */
2046 )
2047{
2048 assert( scip != NULL );
2049 assert( masterdata != NULL );
2050 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2051 assert( masterdata->nlexdatas >= 0 );
2052 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2053 assert( masterdata->shadowtreeeventhdlr != NULL );
2054 assert( permvars != NULL );
2055 assert( npermvars > 0 );
2056 assert( perm != NULL );
2057
2058 if ( symtype != SYM_SYMTYPE_PERM && symtype != SYM_SYMTYPE_SIGNPERM )
2059 {
2060 *success = FALSE;
2061 return SCIP_OKAY;
2062 }
2063 assert( symtype == SYM_SYMTYPE_PERM || permvardomaincenter != NULL );
2065
2066 /* resize component array if needed */
2067 if ( masterdata->nlexdatas == masterdata->maxnlexdatas )
2068 {
2069 int newsize;
2070
2071 newsize = SCIPcalcMemGrowSize(scip, masterdata->nlexdatas + 1);
2072 assert( newsize >= 0 );
2073
2074 if ( masterdata->nlexdatas == 0 )
2075 {
2077 }
2078 else
2079 {
2081 masterdata->maxnlexdatas, newsize) );
2082 }
2083
2084 masterdata->maxnlexdatas = newsize;
2085 }
2086
2087 /* prepare lexdatas */
2088 SCIP_CALL( lexdataCreate(scip, masterdata, &masterdata->lexdatas[masterdata->nlexdatas],
2089 permvars, npermvars, perm, symtype, permvardomaincenter, usedynamicorder, success) );
2090
2091 /* if not successfully added, undo increasing the counter */
2092 if ( *success )
2093 ++masterdata->nlexdatas;
2094
2095 return SCIP_OKAY;
2096}
2097
2098
2099/** resets lexicographic reduction propagation (removes all permutations) */
2101 SCIP* scip, /**< SCIP data structure */
2102 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
2103 )
2104{
2105 assert( scip != NULL );
2106 assert( masterdata != NULL );
2107 assert( (masterdata->lexdatas == NULL) == (masterdata->nlexdatas == 0) );
2108 assert( masterdata->nlexdatas >= 0 );
2109 assert( masterdata->nlexdatas <= masterdata->maxnlexdatas );
2110 assert( masterdata->shadowtreeeventhdlr != NULL );
2111
2112 while ( masterdata->nlexdatas > 0 )
2113 {
2114 SCIP_CALL( lexdataFree(scip, &(masterdata->lexdatas[--masterdata->nlexdatas])) );
2115 }
2116 assert( masterdata->nlexdatas == 0 );
2117
2118 SCIPfreeBlockMemoryArrayNull(scip, &masterdata->lexdatas, masterdata->maxnlexdatas);
2119 masterdata->lexdatas = NULL;
2120 masterdata->maxnlexdatas = 0;
2121
2122 assert( masterdata->nsymvars >= 0 );
2123 assert( (masterdata->symvarmap == NULL) == (masterdata->nsymvars == 0) );
2124 if ( masterdata->symvarmap != NULL )
2125 {
2126 SCIPhashmapFree(&masterdata->symvarmap);
2127 masterdata->symvarmap = NULL;
2128 masterdata->nsymvars = 0;
2129 }
2130
2131 masterdata->hasdynamicperm = FALSE;
2132
2133 return SCIP_OKAY;
2134}
2135
2136
2137/** frees lexicographic reduction data */
2139 SCIP* scip, /**< SCIP data structure */
2140 SCIP_LEXREDDATA** masterdata /**< pointer to global data for lexicographic reduction propagator */
2141 )
2142{
2143 assert( scip != NULL );
2144 assert( masterdata != NULL );
2145 assert( *masterdata != NULL );
2146
2148 assert( (*masterdata)->lexdatas == NULL );
2149 assert( (*masterdata)->symvarmap == NULL );
2150
2152 return SCIP_OKAY;
2153}
2154
2155
2156/** initializes structures needed for lexicographic reduction propagation
2157 *
2158 *
2159 * This is only done exactly once.
2160 */
2162 SCIP* scip, /**< SCIP data structure */
2163 SCIP_LEXREDDATA** masterdata, /**< pointer to global data for lexicographic reduction propagator */
2164 SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */
2165 )
2166{
2167 assert( scip != NULL );
2168 assert( masterdata != NULL );
2169 assert( shadowtreeeventhdlr != NULL );
2170
2171 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeLexicographicReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2173
2175
2176 (*masterdata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
2177 (*masterdata)->symvarmap = NULL;
2178 (*masterdata)->nsymvars = 0;
2179 (*masterdata)->lexdatas = NULL;
2180 (*masterdata)->nlexdatas = 0;
2181 (*masterdata)->maxnlexdatas = 0;
2182 (*masterdata)->nred = 0;
2183 (*masterdata)->ncutoff = 0;
2184 (*masterdata)->hasdynamicperm = FALSE;
2185 (*masterdata)->treewarninggiven = FALSE;
2186
2187 return SCIP_OKAY;
2188}
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
methods for debugging
#define NULL
Definition def.h:267
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPactivateShadowTree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
SCIP_SHADOWTREE * SCIPgetShadowTree(SCIP_EVENTHDLR *eventhdlr)
SCIP_SHADOWNODE * SCIPshadowTreeGetShadowNode(SCIP_SHADOWTREE *shadowtree, SCIP_NODE *node)
SCIP_Bool SCIPisTransformed(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition misc.c:3192
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition scip_mem.h:146
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition scip_mem.h:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7454
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2264
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2192
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2340
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2226
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition scip_tree.c:72
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5205
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition var.c:17561
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5322
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:8717
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebugMessage
Definition pub_message.h:96
public methods for problem variables
SCIP callable library.
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for SCIP variables
SCIP_Bool isdynamic
SCIP_Real * vardomaincenter
SCIP_HASHMAP * varmap
SYM_SYMTYPE symtype
SCIP_VAR ** vars
NODEDEPTHBRANCHINDEX * nodedepthbranchindices
datastructures for block memory pools and memory buffers
SCIP main data structure.
data structures for branch and bound tree
datastructures for problem variables
methods for handling symmetries
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)
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 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)
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_RETCODE SCIPlexicographicReductionPropagate(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
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_RETCODE SCIPlexicographicReductionGetStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
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 SCIPlexicographicReductionReset(SCIP *scip, SCIP_LEXREDDATA *masterdata)
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)
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)
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata)
static SCIP_RETCODE propagateLexredStatic(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE lexdataFree(SCIP *scip, LEXDATA **lexdata)
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)
static SCIP_RETCODE shadowtreeUndoNodeDepthBranchIndices(SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode)
SCIP_RETCODE SCIPlexicographicReductionFree(SCIP *scip, SCIP_LEXREDDATA **masterdata)
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_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)
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)
static SCIP_RETCODE propagateStaticLexred(SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, SCIP_Bool *infeasible, int *nreductions)
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)
SCIP_RETCODE SCIPincludeLexicographicReduction(SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
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)
static int varOrderGetIndex(int *varorder, int pos)
methods for handling symmetries by dynamic lexicographic ordering reduction
struct SCIP_LexRedData SCIP_LEXREDDATA
@ SCIP_VERBLEVEL_HIGH
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:180
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM
type definitions for problem variables
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62