Scippy

SCIP

Solving Constraint Integer Programs

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