Scippy

SCIP

Solving Constraint Integer Programs

symmetry_orbital.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_orbital.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for handling symmetries by orbital reduction
28 * @author Jasper van Doornmalen
29 *
30 * Orbital fixing is introduced by@n
31 * F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.
32 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
33 * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other
34 * variables in the orbit is fixed to 0 or 1, respectively. This method only works for binary variables.
35 * Margot considers the subgroup that stabilizes the set of one-fixings setwise. We determine a subgroup of this group,
36 * namely the group generated by the given symmetry group component generators, where the generators satisfy the
37 * stabilization condition.
38 *
39 * A generalisation is given in the unified symmetry handling constraint paper, Section 4.3 and 5.1 in [vD,H]:@n
40 * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023,
41 * https://doi.org/10.48550/arXiv.2211.01295.
42 *
43 * We assume that the provided symmetries (given by a generating permutation set) are symmetries for the problem at the
44 * root node. It is possible that dual (presolving) reductions break this symmetry. As an example, in cons_components.c,
45 * if the problem contains an independent component (i.e., variables are not connected logically by constraints), then
46 * these individual 'components' can be solved. If an optimal solution is easily retrieved, the variables of this
47 * component are fixed, even if symmetrically equivalent solutions exist. Another example is 'stuffing' for linear
48 * constraints.
49 *
50 * To illustrate this, consider the example \f$\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b,
51 * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the
52 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
53 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
54 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
55 * values).
56 *
57 * We have observed, and assume, that such dual reductions only take place at presolving or in the root node.
58 * So, to avoid this situation, if we detect that a symmetry-breaking reduction is applied at the root node,
59 * we disable orbital fixing for certain generating permutations based on the bounds of the affected global variables,
60 * see identifyOrbitalSymmetriesBroken.
61 *
62 * With the assumption that the symmetries are actual symmetries at the root node, symmetries are broken by the
63 * branching decisions.
64 * For a branch-and-bound tree node \f$\beta\f$ and variable vector \f$x\f$,
65 * let \f$\sigma_\beta(x)\f$ be the permuted and restricted vector \f$x\f$ that enumerates the branching variables,
66 * following the path of the root node to \f$\beta\f$ (cf., Example 11 in [vD,H]).
67 * Consider a component of the symmetry group, given by a set of generating permutations.
68 * Of this set, we select these permutations (not disabled by identifyOrbitalSymmetriesBroken)
69 * for which te variable domains of the branched variables \f$\sigma_\beta(x)\f$
70 * are smaller or equal to the variable domains of the permuted variable. This defines a group (cf. [vD,H, Lemma 22]).
71 * This group is a subgroup of \f$\delta^\beta\f$ of [vD,H, Section 4.3], meaning that the reductions are valid.
72 *
73 * The reductions are:
74 *
75 * - For each orbit of the group, every variable domains can be shrunk to the intersection of all variable domains in
76 * the orbit.
77 * - The domains of the branching variables are upper bounds to the domains of the variables in its orbits.
78 *
79 * For orbital fixing, it is crucial that the vectors \f$\sigma_\beta(x)\f$ are the branching variables up to node
80 * \f$\beta\f$ in the given order. Since SCIP can change the tree structure during solving (re-writing history),
81 * we store the original branching decisions at the moment they are made. See event_shadowtree.c .
82 */
83
84/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
85
88#include "scip/pub_cons.h"
89#include "scip/pub_message.h"
90#include "scip/pub_var.h"
91#include "scip/struct_var.h"
92#include "scip/type_var.h"
93#include "scip/scip.h"
94#include "scip/scip_branch.h"
95#include "scip/scip_conflict.h"
96#include "scip/scip_cons.h"
97#include "scip/scip_copy.h"
98#include "scip/scip_cut.h"
99#include "scip/scip_general.h"
100#include "scip/scip_lp.h"
101#include "scip/scip_mem.h"
102#include "scip/scip_message.h"
103#include "scip/scip_numerics.h"
104#include "scip/scip_param.h"
105#include "scip/scip_prob.h"
106#include "scip/scip_probing.h"
107#include "scip/scip_sol.h"
108#include "scip/scip_var.h"
109#include "scip/debug.h"
110#include "scip/struct_scip.h"
111#include "scip/struct_mem.h"
112#include "scip/struct_tree.h"
113#include "scip/symmetry.h"
115#include <ctype.h>
116#include <string.h>
117#include <memory.h>
118
119
120/* event handler properties */
121#define EVENTHDLR_SYMMETRY_NAME "symmetry_orbital"
122#define EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction"
123
124
125/*
126 * Data structures
127 */
128
129
130/** data for orbital reduction component propagator */
132{
133 SCIP_NODE* lastnode; /**< last node processed by orbital reduction component */
134 SCIP_Real* globalvarlbs; /**< global variable lower bounds until before branching starts */
135 SCIP_Real* globalvarubs; /**< global variable upper bounds until before branching starts */
136 int** perms; /**< the permutations for orbital reduction */
137 int nperms; /**< the number of permutations in perms */
138 SCIP_VAR** permvars; /**< array consisting of the variables of this component */
139 int npermvars; /**< number of vars in this component */
140 SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */
141
142 SCIP_Bool symmetrybrokencomputed; /**< whether the symmetry broken information is computed already */
143 int* symbrokenvarids; /**< variables to be stabilized because the symmetry is globally broken */
144 int nsymbrokenvarids; /**< symbrokenvarids array length, is 0 iff symbrokenvarids is NULL */
145
146 SCIP_Bool treewarninggiven; /**< whether a warning is given for missing nodes in shadowtree */
147};
149
150
151/** data for orbital reduction propagator */
152struct SCIP_OrbitalReductionData
153{
154 SCIP_EVENTHDLR* shadowtreeeventhdlr;/**< eventhandler for the shadow tree data structure */
155 SCIP_EVENTHDLR* globalfixeventhdlr; /**< event handler for handling global variable bound reductions */
156
157 ORCDATA** componentdatas; /**< array of pointers to individual components for orbital reduction */
158 int ncomponents; /**< number of orbital reduction datas in array */
159 int maxncomponents; /**< allocated orbital reduction datas array size */
160 int nred; /**< total number of reductions */
161 int ncutoff; /**< total number of cutoffs */
162};
163
164
165/*
166 * Local methods
167 */
168
169
170/** identifies the orbits at which symmetry is broken according to the global bounds
171 *
172 * An example of a symmetry-breaking constraint is cons_components.
173 */
174static
176 SCIP* scip, /**< pointer to SCIP data structure */
177 ORCDATA* orcdata /**< pointer to data for orbital reduction data */
178)
179{
180 SCIP_DISJOINTSET* orbitset;
181 int i;
182 int j;
183 int p;
184 int* perm;
185 int* varorbitids;
186 int* varorbitidssort;
187 int orbitbegin;
188 int orbitend;
189 int orbitid;
190 int maxnsymbrokenvarids;
191 SCIP_Real orbitglb;
192 SCIP_Real orbitgub;
193 SCIP_Bool orbitsymbroken;
194
195 assert( scip != NULL );
196 assert( orcdata != NULL );
197 assert( !orcdata->symmetrybrokencomputed );
198 orcdata->symbrokenvarids = NULL;
199 orcdata->nsymbrokenvarids = 0;
200 maxnsymbrokenvarids = 0;
201
202 /* determine all orbits */
203 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) );
204 for (p = 0; p < orcdata->nperms; ++p)
205 {
206 perm = orcdata->perms[p];
207 assert( perm != NULL );
208
209 for (i = 0; i < orcdata->npermvars; ++i)
210 {
211 j = perm[i];
212 if ( i != j )
213 SCIPdisjointsetUnion(orbitset, i, j, FALSE);
214 }
215 }
216
217#ifndef NDEBUG
218 /* no arithmetic is performed on these bounds, so we can compare floats by their value exactly */
219 for (i = 0; i < orcdata->npermvars; ++i)
220 {
221 assert( SCIPvarGetLbGlobal(orcdata->permvars[i]) == orcdata->globalvarlbs[i] ); /*lint !e777*/
222 assert( SCIPvarGetUbGlobal(orcdata->permvars[i]) == orcdata->globalvarubs[i] ); /*lint !e777*/
223 }
224#endif
225
226 /* sort all orbits */
227 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) );
228 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) );
229 for (i = 0; i < orcdata->npermvars; ++i)
230 varorbitids[i] = SCIPdisjointsetFind(orbitset, i);
231 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars);
232
233 /* iterate over all orbits and get the maximal orbit lower bound and minimal orbit upper bound */
234 for (orbitbegin = 0; orbitbegin < orcdata->npermvars; orbitbegin = orbitend)
235 {
236 /* get id of the orbit */
237 orbitid = varorbitids[varorbitidssort[orbitbegin]];
238
239 /* the orbit must have the same bounds */
240 orbitsymbroken = FALSE;
241 j = varorbitidssort[orbitbegin];
242 orbitglb = orcdata->globalvarlbs[j];
243 orbitgub = orcdata->globalvarubs[j];
244 for (i = orbitbegin + 1; i < orcdata->npermvars; ++i)
245 {
246 j = varorbitidssort[i];
247
248 /* stop if j is not the element in the orbit, then it is part of the next orbit */
249 if ( varorbitids[j] != orbitid )
250 break;
251
252 if ( !orbitsymbroken )
253 {
254 if ( !SCIPsymEQ(scip, orbitglb, orcdata->globalvarlbs[j]) || !SCIPsymEQ(scip, orbitgub, orcdata->globalvarubs[j]) )
255 {
256 orbitsymbroken = TRUE;
257 break;
258 }
259 }
260 }
261 assert( orbitsymbroken || i == orcdata->npermvars || varorbitids[j] != orbitid );
262
263 /* in case we terminated the orbit due to broken symmetries, find the correct end of the orbit */
264 if ( orbitsymbroken )
265 {
266 while ( i < orcdata->npermvars && varorbitids[j] == orbitid )
267 j = varorbitidssort[++i];
268 }
269 orbitend = i;
270
271 /* symmetry is broken within this orbit if the intersection of the global variable domains are empty */
272 if ( orbitsymbroken )
273 {
274 /* add all variable ids in the orbit to the symbrokenvarids array: resize if needed */
275 if ( orcdata->nsymbrokenvarids + orbitend - orbitbegin > maxnsymbrokenvarids )
276 {
277 int newsize;
278
279 newsize = SCIPcalcMemGrowSize(scip, orcdata->nsymbrokenvarids + orbitend - orbitbegin);
280 assert( newsize >= 0 );
281
282 if ( orcdata->nsymbrokenvarids == 0 )
283 {
284 assert( orcdata->symbrokenvarids == NULL );
286 }
287 else
288 {
289 assert( orcdata->symbrokenvarids != NULL );
291 maxnsymbrokenvarids, newsize) );
292 }
293
294 maxnsymbrokenvarids = newsize;
295 }
296
297 /* add all variable ids in the orbit to the symbrokenvarids array: add */
298 for (i = orbitbegin; i < orbitend; ++i)
299 {
300 j = varorbitidssort[i];
301 assert( varorbitids[j] == orbitid );
302 assert( orcdata->nsymbrokenvarids < maxnsymbrokenvarids );
303 orcdata->symbrokenvarids[orcdata->nsymbrokenvarids++] = j;
304 }
305 }
306 }
307
308 /* shrink the allocated array size to the actually needed size */
309 assert( orcdata->nsymbrokenvarids <= maxnsymbrokenvarids );
310 if ( orcdata->nsymbrokenvarids > 0 && orcdata->nsymbrokenvarids < maxnsymbrokenvarids )
311 {
313 maxnsymbrokenvarids, orcdata->nsymbrokenvarids) );
314 }
315 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) );
316
317 /* mark that this method is executed for the component */
318 orcdata->symmetrybrokencomputed = TRUE;
319
320 /* output information */
321 if ( orcdata->nsymbrokenvarids > 0 )
322 {
324 "Orbital fixing symmetry for %p broken before symmetry. Requires fixing %d/%d affected variables.\n",
325 (void*) orcdata, orcdata->nsymbrokenvarids, orcdata->npermvars);
326 }
327
328 SCIPfreeBufferArray(scip, &varorbitidssort);
329 SCIPfreeBufferArray(scip, &varorbitids);
330 SCIPfreeDisjointset(scip, &orbitset);
331
332 return SCIP_OKAY;
333}
334
335
336/** populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions
337 *
338 * The symmetry subgroup considered is generated by all permutations where for all branching variables \f$x\f$
339 * with permuted variable \f$y\f$ for all possible variable assignments we have \f$x \leq y\f$.
340 * We restrict ourselves to testing this only for the group generators.
341 */
342static
344 SCIP* scip, /**< pointer to SCIP data structure */
345 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
346 int** chosenperms, /**< pointer to permutations that are chosen */
347 int* nchosenperms, /**< pointer to store the number of chosen permutations */
348 SCIP_Real* varlbs, /**< array of orcdata->permvars variable LBs. If NULL, use local bounds */
349 SCIP_Real* varubs, /**< array of orcdata->permvars variable UBs. If NULL, use local bounds */
350 int* branchedvarindices, /**< array of given branching decisions, in branching order */
351 SCIP_Bool* inbranchedvarindices, /**< array stating whether variable with index in orcdata->permvars is
352 * contained in the branching decisions. */
353 int nbranchedvarindices /**< number of branching decisions */
354 )
355{
356 int i;
357 int p;
358 int* perm;
359 int varid;
360 int varidimage;
361
362 assert( scip != NULL );
363 assert( orcdata != NULL );
364 assert( chosenperms != NULL );
365 assert( nchosenperms != NULL );
366 assert( (varlbs == NULL) == (varubs == NULL) );
367 assert( branchedvarindices != NULL );
368 assert( inbranchedvarindices != NULL );
369 assert( nbranchedvarindices >= 0 );
370 assert( orcdata->symmetrybrokencomputed );
371 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) );
372
373 *nchosenperms = 0;
374
375 for (p = 0; p < orcdata->nperms; ++p)
376 {
377 perm = orcdata->perms[p];
378
379 /* make sure that the symmetry broken orbit variable indices are met with equality */
380 for (i = 0; i < orcdata->nsymbrokenvarids; ++i)
381 {
382 varid = orcdata->symbrokenvarids[i];
383 assert( varid >= 0 );
384 assert( varid < orcdata->npermvars );
385 assert( orcdata->permvars[varid] != NULL );
386 varidimage = perm[varid];
387 assert( varidimage >= 0 );
388 assert( varidimage < orcdata->npermvars );
389 assert( orcdata->permvars[varidimage] != NULL );
390
391 /* branching variable is not affected by this permutation */
392 if ( varidimage == varid )
393 continue;
394
395 /* the variables on which symmetry is broken must be permuted to entries with the same fixed value
396 *
397 * Because we check a whole orbit of the group and perm is part of it, it suffices to compare the upper bound
398 * of varid with the lower bound of varidimage. Namely, for all indices i, \f$lb_i \leq ub_i\f$, so we get
399 * a series of equalities yielding that all expressions must be the same:
400 * \f$ub_i = lb_j <= ub_j = lb_{\cdots} <= \cdots = lb_j < ub_j \f$
401 */
402 if ( ! SCIPsymEQ(scip,
403 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]),
404 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) )
405 )
406 break;
407 }
408 /* if the above loop is broken, this permutation does not qualify for the stabilizer */
409 if ( i < orcdata->nsymbrokenvarids )
410 continue;
411
412 /* iterate over each branched variable and check */
413 for (i = 0; i < nbranchedvarindices; ++i)
414 {
415 varid = branchedvarindices[i];
416 assert( varid >= 0 );
417 assert( varid < orcdata->npermvars );
418 assert( orcdata->permvars[varid] != NULL );
419 varidimage = perm[varid];
420 assert( varidimage >= 0 );
421 assert( varidimage < orcdata->npermvars );
422 assert( orcdata->permvars[varidimage] != NULL );
423
424 /* branching variable is not affected by this permutation */
425 if ( varidimage == varid )
426 continue;
427
428 if ( SCIPsymGT(scip,
429 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]),
430 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) )
431 )
432 break;
433 }
434 /* if the above loop is broken, this permutation does not qualify for the stabilizer */
435 if ( i < nbranchedvarindices )
436 continue;
437
438 /* permutation qualifies for the stabilizer. Add permutation */
439 chosenperms[(*nchosenperms)++] = perm;
440 }
441
442 return SCIP_OKAY;
443}
444
445/** using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid
446 *
447 * If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright.
448 */
449static
451 int* ids, /**< int array with entries */
452 int* idssort, /**< array of indices of ids that sort ids */
453 int frameleft, /**< search in idssort for index range [frameleft, frameright) */
454 int frameright, /**< search in idssort for index range [frameleft, frameright) */
455 int findid /**< entry value to find */
456 )
457{
458 int center;
459 int id;
460
461#ifndef NDEBUG
462 int origframeleft;
463 int origframeright;
464 origframeleft = frameleft;
465 origframeright = frameright;
466#endif
467
468 assert( ids != NULL );
469 assert( idssort != NULL );
470 assert( frameleft >= 0 );
471 assert( frameright >= frameleft );
472
473 /* empty frame case */
474 if ( frameright == frameleft )
475 return frameright;
476
477 while (frameright - frameleft >= 2)
478 {
479 /* split [frameleft, frameright) in [frameleft, center) and [center, frameright) */
480 center = frameleft + ((frameright - frameleft) / 2);
481 assert( center > frameleft );
482 assert( center < frameright );
483 id = idssort[center];
484 if ( ids[id] < findid )
485 {
486 /* first instance greater or equal to findid is in [center, frameright) */
487 frameleft = center;
488 }
489 else
490 {
491 /* first instance greater or equal to findid is in [frameleft, center) */
492 frameright = center;
493 }
494 }
495
496 assert( frameright - frameleft == 1 );
497 id = idssort[frameleft];
498 if ( ids[id] < findid )
499 ++frameleft;
500
501 assert( frameleft >= origframeleft );
502 assert( frameright <= origframeright );
503 assert( frameleft >= origframeright || ids[idssort[frameleft]] >= findid );
504 assert( frameleft - 1 < origframeleft || ids[idssort[frameleft - 1]] < findid );
505 return frameleft;
506}
507
508
509/** applies the orbital reduction steps for precomputed orbits
510 *
511 * Either use the local variable bounds, or variable bounds determined by the varlbs and varubs arrays.
512 * @pre varubs is NULL if and only if varlbs is NULL.
513 */
514static
516 SCIP* scip, /**< pointer to SCIP data structure */
517 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
518 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
519 int* nred, /**< pointer to store the number of determined domain reductions */
520 int* varorbitids, /**< array specifying the orbit IDs for variables in array orcdata->vars */
521 int* varorbitidssort, /**< an index array that sorts the varorbitids array */
522 SCIP_Real* varlbs, /**< array of lower bounds for variable array orcdata->vars to compute with
523 * or NULL, if local bounds are used */
524 SCIP_Real* varubs /**< array of upper bounds for variable array orcdata->vars to compute with
525 * or NULL, if local bounds are used. */
526 )
527{
528 int i;
529 int varid;
530 int orbitid;
531 int orbitbegin;
532 int orbitend;
533 SCIP_Real orbitlb;
534 SCIP_Real orbitub;
535 SCIP_Real lb;
536 SCIP_Real ub;
537
538 assert( scip != NULL );
539 assert( orcdata != NULL );
540 assert( infeasible != NULL );
541 assert( nred != NULL );
542 assert( varorbitids != NULL );
543 assert( varorbitidssort != NULL );
544 assert( ( varlbs == NULL ) == ( varubs == NULL ) );
545
546 /* infeasible and nred are defined by the function that calls this function,
547 * and this function only gets called if no infeasibility is found so far.
548 */
549 assert( !*infeasible );
550 assert( *nred >= 0 );
551
552 for (orbitbegin = 0; orbitbegin < orcdata->npermvars; orbitbegin = orbitend)
553 {
554 /* get id of the orbit, and scan how large the orbit is */
555 orbitid = varorbitids[varorbitidssort[orbitbegin]];
556 for (orbitend = orbitbegin + 1; orbitend < orcdata->npermvars; ++orbitend)
557 {
558 if ( varorbitids[varorbitidssort[orbitend]] != orbitid )
559 break;
560 }
561
562 /* orbits consisting of only one element cannot yield reductions */
563 if ( orbitend - orbitbegin <= 1 )
564 continue;
565
566 /* get upper and lower bounds in orbit */
567 orbitlb = -INFINITY;
568 orbitub = INFINITY;
569 for (i = orbitbegin; i < orbitend; ++i)
570 {
571 varid = varorbitidssort[i];
572 assert( varid >= 0 );
573 assert( varid < orcdata->npermvars );
574 assert( orcdata->permvars[varid] != NULL );
575
576 lb = varlbs ? varlbs[varid] : SCIPvarGetLbLocal(orcdata->permvars[varid]);
577 if ( SCIPsymGT(scip, lb, orbitlb) )
578 orbitlb = lb;
579 ub = varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]);
580 if ( SCIPsymLT(scip, ub, orbitub) )
581 orbitub = ub;
582 }
583
584 /* if bounds are incompatible, infeasibility is detected */
585 if ( SCIPsymGT(scip, orbitlb, orbitub) )
586 {
587 *infeasible = TRUE;
588 return SCIP_OKAY;
589 }
590 assert( SCIPsymLE(scip, orbitlb, orbitub) );
591
592 /* update variable bounds to be in this range */
593 for (i = orbitbegin; i < orbitend; ++i)
594 {
595 varid = varorbitidssort[i];
596 assert( varid >= 0 );
597 assert( varid < orcdata->npermvars );
598
599 if ( varlbs != NULL )
600 {
601 assert( SCIPsymLE(scip, varlbs[varid], orbitlb) );
602 varlbs[varid] = orbitlb;
603 }
604 if ( !SCIPisInfinity(scip, -orbitlb) &&
605 SCIPsymLT(scip, SCIPvarGetLbLocal(orcdata->permvars[varid]), orbitlb) )
606 {
607 SCIP_Bool tightened;
608 SCIP_CALL( SCIPtightenVarLb(scip, orcdata->permvars[varid], orbitlb, TRUE, infeasible, &tightened) );
609
610 /* propagator detected infeasibility in this node */
611 if ( *infeasible )
612 return SCIP_OKAY;
613 assert( tightened );
614 *nred += 1;
615 }
616
617 if ( varubs != NULL )
618 {
619 assert( SCIPsymGE(scip, varubs[varid], orbitub) );
620 varubs[varid] = orbitub;
621 }
622 if ( !SCIPisInfinity(scip, orbitub) &&
623 SCIPsymGT(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), orbitub) )
624 {
625 SCIP_Bool tightened;
626 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], orbitub, TRUE, infeasible, &tightened) );
627
628 /* propagator detected infeasibility in this node */
629 if ( *infeasible )
630 return SCIP_OKAY;
631 assert( tightened );
632 *nred += 1;
633 }
634 }
635 }
636 assert( !*infeasible );
637 return SCIP_OKAY;
638}
639
640
641/** orbital reduction, the orbital branching part */
642static
644 SCIP* scip, /**< pointer to SCIP data structure */
645 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
646 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
647 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
648 int* nred /**< pointer to store the number of determined domain reductions */
649 )
650{
651 SCIP_NODE* focusnode;
652 SCIP_NODE* parentnode;
653 SCIP_SHADOWNODE* shadowfocusnode;
654 SCIP_SHADOWNODE* tmpshadownode;
655 SCIP_SHADOWNODE** rootedshadowpath;
656 int pathlength;
657 int depth;
658 int branchstep;
659 int i;
660 SCIP_Real* varlbs;
661 SCIP_Real* varubs;
663 int* branchedvarindices;
664 SCIP_Bool* inbranchedvarindices;
665 int nbranchedvarindices;
666 int varid;
667 SCIP_SHADOWBOUNDUPDATE* branchingdecision;
668 int branchingdecisionvarid;
669 int** chosenperms;
670 int* perm;
671 int nchosenperms;
672 int p;
673 int* varorbitids;
674 int* varorbitidssort;
675 int idx;
676 int orbitbegin;
677 int orbitend;
678 SCIP_DISJOINTSET* orbitset;
679 int orbitsetcomponentid;
680
681 assert( scip != NULL );
682 assert( orcdata != NULL );
683 assert( shadowtree != NULL );
684 assert( infeasible != NULL );
685 assert( nred != NULL );
686
687 /* infeasible and nred are defined by the function that calls this function,
688 * and this function only gets called if no infeasibility is found so far.
689 */
690 assert( !*infeasible );
691 assert( *nred >= 0 );
692
693 focusnode = SCIPgetFocusNode(scip);
694 assert( focusnode == SCIPgetCurrentNode(scip) );
695 assert( focusnode != NULL );
696
697 /* do nothing if this method has already been called for this node */
698 if ( orcdata->lastnode == focusnode )
699 return SCIP_OKAY;
700
701 orcdata->lastnode = focusnode;
702 parentnode = SCIPnodeGetParent(focusnode);
703
704 /* the root node has not been generated by branching decisions */
705 if ( parentnode == NULL )
706 return SCIP_OKAY;
707
708 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
709
710 /* do not apply orbital reduction if focusnode does not exist in the shadowtree */
711 if ( shadowfocusnode == NULL )
712 {
713 if ( !orcdata->treewarninggiven )
714 {
715 SCIPwarningMessage(scip, "Attempting orbital reduction on nodes not existing in the symmetry shadowtree"
716 " (and suppressing future warnings for this component)\n");
717 orcdata->treewarninggiven = TRUE;
718 }
719 return SCIP_OKAY;
720 }
721
722 /* get the rooted path */
723 /* @todo add depth field to shadow tree node to improve efficiency */
724 pathlength = 0;
725 tmpshadownode = shadowfocusnode;
726 do
727 {
728 tmpshadownode = tmpshadownode->parent;
729 ++pathlength;
730 }
731 while ( tmpshadownode != NULL );
732
733 SCIP_CALL( SCIPallocBufferArray(scip, &rootedshadowpath, pathlength) );
734 i = pathlength;
735 tmpshadownode = shadowfocusnode;
736 while ( i > 0 )
737 {
738 rootedshadowpath[--i] = tmpshadownode;
739 assert( tmpshadownode != NULL );
740 tmpshadownode = tmpshadownode->parent;
741 }
742 assert( tmpshadownode == NULL );
743 assert( i == 0 );
744
745 /* replay bound reductions and propagations made until just before the focusnode */
746 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */
747
748 SCIP_CALL( SCIPallocBufferArray(scip, &varlbs, orcdata->npermvars) );
749 SCIP_CALL( SCIPallocBufferArray(scip, &varubs, orcdata->npermvars) );
750 SCIP_CALL( SCIPallocBufferArray(scip, &branchedvarindices, orcdata->npermvars) );
751 SCIP_CALL( SCIPallocCleanBufferArray(scip, &inbranchedvarindices, orcdata->npermvars) );
752
753 /* start with the bounds found after computing the symmetry group */
754 for (i = 0; i < orcdata->npermvars; ++i)
755 varlbs[i] = orcdata->globalvarlbs[i];
756 for (i = 0; i < orcdata->npermvars; ++i)
757 varubs[i] = orcdata->globalvarubs[i];
758
759 nbranchedvarindices = 0;
760 for (depth = 0; depth < pathlength - 1; ++depth)
761 {
762 tmpshadownode = rootedshadowpath[depth];
763
764 /* receive propagations */
765 for (i = 0; i < tmpshadownode->npropagations; ++i)
766 {
767 update = &(tmpshadownode->propagations[i]);
768 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
769 assert( varid < orcdata->npermvars || varid == INT_MAX );
770 assert( varid >= 0 );
771 if ( varid < orcdata->npermvars )
772 {
773 assert( SCIPsymLE(scip, varlbs[varid], varubs[varid]) );
774 switch (update->boundchgtype)
775 {
777 assert( SCIPsymGE(scip, update->newbound, varlbs[varid]) );
778 varlbs[varid] = update->newbound;
779 break;
781 assert( SCIPsymLE(scip, update->newbound, varubs[varid]) );
782 varubs[varid] = update->newbound;
783 break;
784 default:
785 SCIPABORT();
786 }
787 assert( SCIPsymLE(scip, varlbs[varid], varubs[varid]) );
788 }
789 }
790
791 /* receive variable indices of branched variables */
792 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i)
793 {
794 update = &(tmpshadownode->branchingdecisions[i]);
795 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
796 assert( varid < orcdata->npermvars || varid == INT_MAX );
797 assert( varid >= 0 );
798 if ( varid < orcdata->npermvars )
799 {
800 if ( inbranchedvarindices[varid] )
801 continue;
802 branchedvarindices[nbranchedvarindices++] = varid;
803 inbranchedvarindices[varid] = TRUE;
804 }
805 }
806 }
807
808 /* determine symmetry group at this point, apply branched variable, apply orbital branching for this
809 *
810 * The branching variables are applied one-after-the-other.
811 * So, the group before branching is determined, orbital branching to the branching variable, then the branching
812 * variable is applied, and possibly repeated for other branching variables.
813 */
814 SCIP_CALL( SCIPallocBufferArray(scip, &chosenperms, orcdata->nperms) );
815 for (branchstep = 0; branchstep < shadowfocusnode->nbranchingdecisions; ++branchstep)
816 {
817 branchingdecision = &(shadowfocusnode->branchingdecisions[branchstep]);
818 branchingdecisionvarid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) branchingdecision->var);
819 assert( branchingdecisionvarid < orcdata->npermvars || branchingdecisionvarid == INT_MAX );
820 assert( branchingdecisionvarid >= 0 );
821
822 /* branching decision will not have an effect on this */
823 if ( branchingdecisionvarid >= orcdata->npermvars )
824 continue;
825 assert( branchingdecisionvarid >= 0 && branchingdecisionvarid < orcdata->npermvars );
826 assert( branchingdecision->boundchgtype == SCIP_BOUNDTYPE_LOWER ?
827 SCIPsymLE(scip, varlbs[branchingdecisionvarid], branchingdecision->newbound) :
828 SCIPsymGE(scip, varubs[branchingdecisionvarid], branchingdecision->newbound) );
829 assert( SCIPsymLE(scip, varlbs[branchingdecisionvarid], varubs[branchingdecisionvarid]) );
830
831 /* get the generating set of permutations of a subgroup of a stabilizing symmetry subgroup.
832 *
833 * Note: All information about branching decisions is kept in varlbs, varubs, and the branchedvarindices.
834 */
835 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms,
836 varlbs, varubs, branchedvarindices, inbranchedvarindices, nbranchedvarindices) );
837
838 /* compute orbit containing branching var */
839 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) );
840
841 /* put elements mapping to each other in same orbit */
842 /* @todo a potential performance hazard; quadratic time */
843 for (p = 0; p < nchosenperms; ++p)
844 {
845 perm = chosenperms[p];
846 for (i = 0; i < orcdata->npermvars; ++i)
847 {
848 if ( i != perm[i] )
849 SCIPdisjointsetUnion(orbitset, i, perm[i], FALSE);
850 }
851 }
852
853 /* 1. ensure that the bounds are tightest possible just before the branching step (orbital reduction step)
854 *
855 * If complete propagation was applied in the previous node,
856 * then all variables in the same orbit have the same bounds just before branching,
857 * so the bounds of the branching variable should be the tightest in its orbit by now.
858 * It is possible that that is not the case. In that case, we do it here.
859 */
860 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) );
861 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) );
862 for (i = 0; i < orcdata->npermvars; ++i)
863 varorbitids[i] = SCIPdisjointsetFind(orbitset, i);
864 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars);
865
866 /* apply orbital reduction to these orbits */
867 SCIP_CALL( applyOrbitalReductionPart(scip, orcdata, infeasible, nred, varorbitids,
868 varorbitidssort, varlbs, varubs) );
869 if ( *infeasible )
870 goto FREE;
871 assert( !*infeasible );
872
873 /* 2. apply branching step to varlbs or varubs array
874 *
875 * Due to the steps above, it is possible that the branching step is redundant or infeasible.
876 */
877 assert( SCIPsymLE(scip, varlbs[branchingdecisionvarid], varubs[branchingdecisionvarid]) );
878 switch (branchingdecision->boundchgtype)
879 {
881 /* incompatible upper bound */
882 if ( SCIPsymGT(scip, branchingdecision->newbound, varubs[branchingdecisionvarid]) )
883 {
884 *infeasible = TRUE;
885 goto FREE;
886 }
887
888 assert( SCIPsymLE(scip, varlbs[branchingdecisionvarid], branchingdecision->newbound) );
889 varlbs[branchingdecisionvarid] = branchingdecision->newbound;
890 break;
892 /* incompatible lower bound */
893 if ( SCIPsymLT(scip, branchingdecision->newbound, varlbs[branchingdecisionvarid]) )
894 {
895 *infeasible = TRUE;
896 goto FREE;
897 }
898
899 assert( SCIPsymGE(scip, varubs[branchingdecisionvarid], branchingdecision->newbound) );
900 varubs[branchingdecisionvarid] = branchingdecision->newbound;
901 break;
902 default:
903 SCIPABORT();
904 }
905
906 /* 3. propagate that branching variable is >= the variables in its orbit
907 *
908 * Also apply the updates to the variable arrays
909 */
910
911 /* get the orbit of the branching variable */
912 orbitsetcomponentid = SCIPdisjointsetFind(orbitset, branchingdecisionvarid);
913
914 /* find the orbit in the sorted array of orbits. npermvars can be huge, so use bisection. */
915 orbitbegin = bisectSortedArrayFindFirstGEQ(varorbitids, varorbitidssort, 0, orcdata->npermvars,
916 orbitsetcomponentid);
917 assert( orbitbegin >= 0 && orbitbegin < orcdata->npermvars );
918 assert( varorbitids[varorbitidssort[orbitbegin]] == orbitsetcomponentid );
919 assert( orbitbegin == 0 || varorbitids[varorbitidssort[orbitbegin - 1]] < orbitsetcomponentid );
920
921 orbitend = bisectSortedArrayFindFirstGEQ(varorbitids, varorbitidssort, orbitbegin + 1, orcdata->npermvars,
922 orbitsetcomponentid + 1);
923 assert( orbitend > 0 && orbitend <= orcdata->npermvars && orbitend > orbitbegin );
924 assert( orbitend == orcdata->npermvars || varorbitids[varorbitidssort[orbitend]] > orbitsetcomponentid );
925 assert( varorbitids[varorbitidssort[orbitend - 1]] == orbitsetcomponentid );
926
927 /* propagate that branching variable is >= the variables in its orbit */
928 for (idx = orbitbegin; idx < orbitend; ++idx)
929 {
930 varid = varorbitidssort[idx];
931 assert( varorbitids[varid] == orbitsetcomponentid );
932
933 /* ignore current branching variable */
934 if ( varid == branchingdecisionvarid )
935 continue;
936
937 /* is variable varid in the orbit? */
938 if ( SCIPdisjointsetFind(orbitset, varid) != orbitsetcomponentid )
939 continue;
940
941 /* all variables in the same orbit have the same bounds just before branching,
942 * due to orbital reduction. If that was not the case, these steps are applied just before applying
943 * the branching step above. After the branching step, the branching variable bounds are most restricted.
944 */
945 assert( SCIPisInfinity(scip, -varlbs[branchingdecisionvarid])
946 || SCIPsymGE(scip, varlbs[branchingdecisionvarid], varlbs[varid]) );
947 assert( SCIPisInfinity(scip, varubs[branchingdecisionvarid])
948 || SCIPsymLE(scip, varubs[branchingdecisionvarid], varubs[varid]) );
949 /* bound changes already made could only have tightened the variable domains we are thinking about */
950 assert( SCIPsymGE(scip, SCIPvarGetLbLocal(orcdata->permvars[varid]), varlbs[varid]) );
951 assert( SCIPsymLE(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[varid]) );
952
953 /* for branching variable x and variable y in its orbit, propagate x >= y. */
954 /* modify UB of y-variables */
955 assert( SCIPsymGE(scip, varubs[varid], varubs[branchingdecisionvarid]) );
956 varubs[varid] = varubs[branchingdecisionvarid];
957 if ( SCIPsymGT(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[branchingdecisionvarid]) )
958 {
959 SCIP_Bool tightened;
960 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], varubs[branchingdecisionvarid], TRUE,
961 infeasible, &tightened) );
962
963 /* propagator detected infeasibility in this node. */
964 if ( *infeasible )
965 goto FREE;
966 assert( tightened );
967 *nred += 1;
968 }
969
970 /* because variable domains are initially the same, the LB of the x-variables does not need to be modified. */
971 assert( SCIPsymLE(scip, varlbs[varid], varlbs[branchingdecisionvarid]) );
972 }
973
974 FREE:
975 SCIPfreeBufferArray(scip, &varorbitidssort);
976 SCIPfreeBufferArray(scip, &varorbitids);
977 SCIPfreeDisjointset(scip, &orbitset);
978
979 if ( *infeasible )
980 break;
981
982 /* for the next branched variable at this node, if it's not already added,
983 * mark the branching variable of this iteration as a branching variable. */
984 if ( !inbranchedvarindices[branchingdecisionvarid] )
985 {
986 assert( nbranchedvarindices < orcdata->npermvars );
987 branchedvarindices[nbranchedvarindices++] = branchingdecisionvarid;
988 inbranchedvarindices[branchingdecisionvarid] = TRUE;
989 }
990 }
991 SCIPfreeBufferArray(scip, &chosenperms);
992
993 /* clean inbranchedvarindices array */
994 for (i = 0; i < nbranchedvarindices; ++i)
995 {
996 varid = branchedvarindices[i];
997 assert( varid >= 0 );
998 assert( varid < orcdata->npermvars );
999 assert( inbranchedvarindices[varid] );
1000 inbranchedvarindices[varid] = FALSE;
1001 }
1002#ifndef NDEBUG
1003 for (i = 0; i < orcdata->npermvars; ++i)
1004 {
1005 assert( inbranchedvarindices[i] == FALSE );
1006 }
1007#endif
1008
1009 /* free everything */
1010 SCIPfreeCleanBufferArray(scip, &inbranchedvarindices);
1011 SCIPfreeBufferArray(scip, &branchedvarindices);
1012 SCIPfreeBufferArray(scip, &varubs);
1013 SCIPfreeBufferArray(scip, &varlbs);
1014 SCIPfreeBufferArray(scip, &rootedshadowpath);
1015
1016 return SCIP_OKAY;
1017}
1018
1019/** orbital reduction, the orbital reduction part */
1020static
1022 SCIP* scip, /**< pointer to SCIP data structure */
1023 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
1024 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
1025 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
1026 int* nred /**< pointer to store the number of determined domain reductions */
1027 )
1028{
1029 SCIP_NODE* focusnode;
1030 SCIP_SHADOWNODE* shadowfocusnode;
1031 SCIP_SHADOWNODE* tmpshadownode;
1032 int i;
1033 SCIP_SHADOWBOUNDUPDATE* update;
1034 int* branchedvarindices;
1035 SCIP_Bool* inbranchedvarindices;
1036 int nbranchedvarindices;
1037 int varid;
1038 int** chosenperms;
1039 int* perm;
1040 int nchosenperms;
1041 int p;
1042 SCIP_DISJOINTSET* orbitset;
1043 int* varorbitids;
1044 int* varorbitidssort;
1045
1046 assert( scip != NULL );
1047 assert( orcdata != NULL );
1048 assert( shadowtree != NULL );
1049 assert( infeasible != NULL );
1050 assert( nred != NULL );
1051
1052 /* infeasible and nred are defined by the function that calls this function,
1053 * and this function only gets called if no infeasibility is found so far.
1054 */
1055 assert( !*infeasible );
1056 assert( *nred >= 0 );
1057
1058 focusnode = SCIPgetFocusNode(scip);
1059 assert( focusnode == SCIPgetCurrentNode(scip) );
1060 assert( focusnode != NULL );
1061
1062 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1063 assert( shadowfocusnode != NULL );
1064
1065 /* get the branching variables until present, so including the branchings of the focusnode */
1066 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */
1067
1068 SCIP_CALL( SCIPallocBufferArray(scip, &branchedvarindices, orcdata->npermvars) );
1069 SCIP_CALL( SCIPallocCleanBufferArray(scip, &inbranchedvarindices, orcdata->npermvars) );
1070
1071 nbranchedvarindices = 0;
1072 tmpshadownode = shadowfocusnode;
1073 while ( tmpshadownode != NULL )
1074 {
1075 /* receive variable indices of branched variables */
1076 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i)
1077 {
1078 update = &(tmpshadownode->branchingdecisions[i]);
1079 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
1080 assert( varid < orcdata->npermvars || varid == INT_MAX );
1081 assert( varid >= 0 );
1082 if ( varid < orcdata->npermvars )
1083 {
1084 if ( inbranchedvarindices[varid] )
1085 continue;
1086 branchedvarindices[nbranchedvarindices++] = varid;
1087 inbranchedvarindices[varid] = TRUE;
1088 }
1089 }
1090 tmpshadownode = tmpshadownode->parent;
1091 }
1092
1093 /* 1. compute the orbit of the branching variable of the stabilized symmetry subgroup at this point. */
1094 /* 1.1. identify the permutations of the symmetry group that are permitted */
1095 SCIP_CALL( SCIPallocBufferArray(scip, &chosenperms, orcdata->nperms) );
1096 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms,
1097 NULL, NULL, branchedvarindices, inbranchedvarindices, nbranchedvarindices) );
1098 assert( nchosenperms >= 0 );
1099
1100 /* no reductions can be yielded by orbital reduction if the group is trivial */
1101 if ( nchosenperms == 0 )
1102 goto FREE;
1103
1104 /* 1.2. compute orbits of this subgroup */
1105 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) );
1106
1107 /* put elements mapping to each other in same orbit */
1108 /* @todo this is O(nchosenperms * npermvars), which is a potential performance bottleneck.
1109 Alternative: precompute support per permutation at initialization, and iterate over these.*/
1110 for (p = 0; p < nchosenperms; ++p)
1111 {
1112 perm = chosenperms[p];
1113 for (i = 0; i < orcdata->npermvars; ++i)
1114 {
1115 if ( i != perm[i] )
1116 SCIPdisjointsetUnion(orbitset, i, perm[i], FALSE);
1117 }
1118 }
1119
1120 /* 2. for each orbit, take the intersection of the domains */
1121 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) );
1122 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) );
1123 for (i = 0; i < orcdata->npermvars; ++i)
1124 varorbitids[i] = SCIPdisjointsetFind(orbitset, i);
1125 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars);
1126
1127 /* apply orbital reduction to these orbits */
1128 SCIP_CALL( applyOrbitalReductionPart(scip, orcdata, infeasible, nred, varorbitids, varorbitidssort, NULL, NULL) );
1129
1130 SCIPfreeBufferArray(scip, &varorbitidssort);
1131 SCIPfreeBufferArray(scip, &varorbitids);
1132 SCIPfreeDisjointset(scip, &orbitset);
1133FREE:
1134 SCIPfreeBufferArray(scip, &chosenperms);
1135
1136 /* clean inbranchedvarindices array */
1137 for (i = 0; i < nbranchedvarindices; ++i)
1138 {
1139 varid = branchedvarindices[i];
1140 assert( varid >= 0 );
1141 assert( varid < orcdata->npermvars );
1142 assert( inbranchedvarindices[varid] );
1143 inbranchedvarindices[varid] = FALSE;
1144 }
1145#ifndef NDEBUG
1146 for (i = 0; i < orcdata->npermvars; ++i)
1147 {
1148 assert( inbranchedvarindices[i] == FALSE );
1149 }
1150#endif
1151
1152 SCIPfreeCleanBufferArray(scip, &inbranchedvarindices);
1153 SCIPfreeBufferArray(scip, &branchedvarindices);
1154
1155 return SCIP_OKAY;
1156}
1157
1158
1159/** applies orbital reduction on a symmetry group component using a two step mechanism
1160 *
1161 * 1. At the parent of our focus node (which is the current node, because we're not probing),
1162 * compute the symmetry group just before branching. Then, for our branching variable x with variable y in its
1163 * orbit, we mimic adding the constraint x >= y by variable bound propagations in this node.
1164 *
1165 * In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields
1166 * 1. In the 1-branch: 1 = x >= y is a tautology (since y is in {0, 1}). Nothing happens.
1167 * 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching.
1168 * REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178.
1169 *
1170 * (This only needs to be done once per node.)
1171 *
1172 * 2. At the focus node itself, compute the symmetry group.
1173 * The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group
1174 * as described in the function orbitalReductionGetSymmetryStabilizerSubgroup.
1175 * For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable
1176 * domains in the orbit.
1177 *
1178 * This generalizes orbital fixing in the binary case.
1179 * REF: Margot 2002, Margot 2003, Orbital Branching, Ostrowski's PhD thesis.
1180 */
1181static
1183 SCIP* scip, /**< SCIP data structure */
1184 ORCDATA* orcdata, /**< orbital reduction component data */
1185 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
1186 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1187 int* nred /**< pointer to store the number of domain reductions */
1188 )
1189{
1190 assert( scip != NULL );
1191 assert( orcdata != NULL );
1192 assert( shadowtree != NULL );
1193 assert( infeasible != NULL );
1194 assert( nred != NULL );
1195
1196 /* infeasible and nred are defined by the function that calls this function,
1197 * and this function only gets called if no infeasibility is found so far.
1198 */
1199 assert( !*infeasible );
1200 assert( *nred >= 0 );
1201
1202 /* orbital reduction is only propagated when branching has started */
1204
1205 /* if this is the first call, identify the orbits for which symmetry is broken */
1206 if ( !orcdata->symmetrybrokencomputed )
1207 {
1209 }
1210 assert( orcdata->symmetrybrokencomputed );
1211 assert( orcdata->nsymbrokenvarids <= orcdata->npermvars );
1212
1213 /* If symmetry is broken for all orbits, stop! */
1214 if ( orcdata->nsymbrokenvarids == orcdata->npermvars )
1215 return SCIP_OKAY;
1216
1217 /* step 1 */
1218 SCIP_CALL( applyOrbitalBranchingPropagations(scip, orcdata, shadowtree, infeasible, nred) );
1219 if ( *infeasible )
1220 return SCIP_OKAY;
1221
1222 /* step 2 */
1223 SCIP_CALL( applyOrbitalReductionPropagations(scip, orcdata, shadowtree, infeasible, nred) );
1224 if ( *infeasible )
1225 return SCIP_OKAY;
1226
1227 return SCIP_OKAY;
1228}
1229
1230
1231/** adds component */
1232static
1234 SCIP* scip, /**< SCIP data structure */
1235 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */
1236 SCIP_VAR** permvars, /**< variable array of the permutation */
1237 int npermvars, /**< number of variables in that array */
1238 int** perms, /**< permutations in the component */
1239 int nperms, /**< number of permutations in the component */
1240 SCIP_Bool* success /**< to store whether the component is successfully added */
1241 )
1242{
1243 ORCDATA* orcdata;
1244 int i;
1245 int j;
1246 int p;
1247 int* origperm;
1248 int* newperm;
1249 int newidx;
1250 int newpermidx;
1251
1252 assert( scip != NULL );
1253 assert( orbireddata != NULL );
1254 assert( permvars != NULL );
1255 assert( npermvars > 0 );
1256 assert( perms != NULL );
1257 assert( nperms > 0 );
1258 assert( success != NULL );
1259
1260 *success = TRUE;
1261 SCIP_CALL( SCIPallocBlockMemory(scip, &orcdata) );
1262
1263 /* correct indices by removing fixed points */
1264
1265 /* determine the number of vars that are moved by the component, assign to orcdata->npermvars */
1266 orcdata->npermvars = 0;
1267 for (i = 0; i < npermvars; ++i)
1268 {
1269 /* is index i moved by any of the permutations in the component? */
1270 for (p = 0; p < nperms; ++p)
1271 {
1272 if ( perms[p][i] != i )
1273 {
1274 ++orcdata->npermvars;
1275 break;
1276 }
1277 }
1278 }
1279
1280 /* do not support the setting where the component is empty */
1281 if ( orcdata->npermvars <= 0 )
1282 {
1283 SCIPfreeBlockMemory(scip, &orcdata);
1284 *success = FALSE;
1285 return SCIP_OKAY;
1286 }
1287
1288 /* require that the shadowtree is active */
1289 SCIP_CALL( SCIPactivateShadowTree(scip, orbireddata->shadowtreeeventhdlr) );
1290
1291 /* create index-corrected permvars array and the inverse */
1294
1295 j = 0;
1296 for (i = 0; i < npermvars; ++i)
1297 {
1298 /* permvars array must be unique */
1299 assert( SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]) == INT_MAX );
1300
1301 /* is index i moved by any of the permutations in the component? */
1302 for (p = 0; p < nperms; ++p)
1303 {
1304 if ( perms[p][i] != i )
1305 {
1306 /* var is moved by component; add, disable multiaggregation and capture */
1307 SCIP_CALL( SCIPcaptureVar(scip, permvars[i]) );
1308 orcdata->permvars[j] = permvars[i];
1309 SCIP_CALL( SCIPhashmapInsertInt(orcdata->permvarmap, (void*) permvars[i], j) );
1310 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, permvars[i]) );
1311 ++j;
1312 break;
1313 }
1314 }
1315 }
1316 assert( j == orcdata->npermvars );
1317
1318 /* allocate permutations */
1319 orcdata->nperms = nperms;
1320 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms, nperms) );
1321 for (p = 0; p < nperms; ++p)
1322 {
1323 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms[p], orcdata->npermvars) );
1324 origperm = perms[p];
1325 newperm = orcdata->perms[p];
1326
1327 for (i = 0; i < npermvars; ++i)
1328 {
1329 newidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]);
1330 if ( newidx >= orcdata->npermvars )
1331 continue;
1332 assert( newidx >= 0 );
1333 assert( newidx < orcdata->npermvars );
1334 assert( orcdata->permvars[newidx] == permvars[i] );
1335 newpermidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[origperm[i]]);
1336 assert( newpermidx >= 0 );
1337 assert( newidx < orcdata->npermvars ); /* this is in the orbit of any permutation, so cannot be INT_MAX */
1338 assert( orcdata->permvars[newpermidx] == permvars[origperm[i]] );
1339
1340 newperm[newidx] = newpermidx;
1341 }
1342 }
1343
1344 /* global variable bounds */
1347 for (i = 0; i < orcdata->npermvars; ++i)
1348 {
1349 orcdata->globalvarlbs[i] = SCIPvarGetLbGlobal(orcdata->permvars[i]);
1350 orcdata->globalvarubs[i] = SCIPvarGetUbGlobal(orcdata->permvars[i]);
1351 }
1352
1353 /* catch global variable bound change event */
1354 for (i = 0; i < orcdata->npermvars; ++i)
1355 {
1357 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) orcdata, NULL) );
1358 }
1359
1360 /* lastnode field */
1361 orcdata->lastnode = NULL;
1362
1363 /* symmetry computed field */
1364 orcdata->symmetrybrokencomputed = FALSE;
1365 orcdata->symbrokenvarids = NULL;
1366 orcdata->nsymbrokenvarids = -1;
1367
1368 /* resize component array if needed */
1369 assert( orbireddata->ncomponents >= 0 );
1370 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) );
1371 assert( orbireddata->ncomponents <= orbireddata->maxncomponents );
1372 if ( orbireddata->ncomponents == orbireddata->maxncomponents )
1373 {
1374 int newsize;
1375
1376 newsize = SCIPcalcMemGrowSize(scip, orbireddata->ncomponents + 1);
1377 assert( newsize >= 0 );
1378
1379 if ( orbireddata->ncomponents == 0 )
1380 {
1381 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbireddata->componentdatas, newsize) );
1382 }
1383 else
1384 {
1385 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->componentdatas,
1386 orbireddata->ncomponents, newsize) );
1387 }
1388
1389 orbireddata->maxncomponents = newsize;
1390 }
1391
1392 /* tree warning indicator */
1393 orcdata->treewarninggiven = FALSE;
1394
1395 /* add component */
1396 assert( orbireddata->ncomponents < orbireddata->maxncomponents );
1397 orbireddata->componentdatas[orbireddata->ncomponents++] = orcdata;
1398
1399 return SCIP_OKAY;
1400}
1401
1402
1403/** frees component */
1404static
1406 SCIP* scip, /**< SCIP data structure */
1407 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */
1408 ORCDATA** orcdata /**< pointer to component data */
1409 )
1410{
1411 int i;
1412 int p;
1413
1414 assert( scip != NULL );
1415 assert( orbireddata != NULL );
1416 assert( orcdata != NULL );
1417 assert( *orcdata != NULL );
1418 assert( (*orcdata)->globalvarlbs != NULL );
1419 assert( (*orcdata)->globalvarubs != NULL );
1420 assert( (*orcdata)->nperms > 0 );
1421 assert( (*orcdata)->npermvars > 0 );
1422 assert( (*orcdata)->perms != NULL );
1423 assert( (*orcdata)->permvarmap != NULL );
1424 assert( (*orcdata)->permvars != NULL );
1425 assert( (*orcdata)->npermvars > 0 );
1426
1427 assert( SCIPisTransformed(scip) );
1428
1429 /* free symmetry broken information if it has been computed */
1430 if ( (*orcdata)->symmetrybrokencomputed )
1431 {
1432 assert( ((*orcdata)->nsymbrokenvarids == 0) == ((*orcdata)->symbrokenvarids == NULL) );
1433 SCIPfreeBlockMemoryArrayNull(scip, &(*orcdata)->symbrokenvarids, (*orcdata)->nsymbrokenvarids);
1434 }
1435
1436 /* free global variable bound change event */
1438 {
1439 /* events at the freeing stage may not be dropped, because they are already getting dropped */
1440 for (i = (*orcdata)->npermvars - 1; i >= 0; --i)
1441 {
1442 SCIP_CALL( SCIPdropVarEvent(scip, (*orcdata)->permvars[i],
1444 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) (*orcdata), -1) );
1445 }
1446 }
1447
1448 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarubs, (*orcdata)->npermvars);
1449 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarlbs, (*orcdata)->npermvars);
1450
1451 for (p = (*orcdata)->nperms -1; p >= 0; --p)
1452 {
1453 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms[p], (*orcdata)->npermvars);
1454 }
1455 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms, (*orcdata)->nperms);
1456
1457 /* release variables */
1458 for (i = 0; i < (*orcdata)->npermvars; ++i)
1459 {
1460 assert( (*orcdata)->permvars[i] != NULL );
1461 SCIP_CALL( SCIPreleaseVar(scip, &(*orcdata)->permvars[i]) );
1462 }
1463
1464 SCIPhashmapFree(&(*orcdata)->permvarmap);
1465 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->permvars, (*orcdata)->npermvars);
1466
1467 SCIPfreeBlockMemory(scip, orcdata);
1468
1469 return SCIP_OKAY;
1470}
1471
1472
1473/*
1474 * Event handler callback methods
1475 */
1476
1477/** maintains global variable bound reductions found during presolving or at the root node */
1478static
1479SCIP_DECL_EVENTEXEC(eventExecGlobalBoundChange)
1480{
1481 ORCDATA* orcdata;
1482 SCIP_VAR* var;
1483 int varidx;
1484
1485 assert( eventhdlr != NULL );
1486 assert( eventdata != NULL );
1487 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_SYMMETRY_NAME) == 0 );
1488 assert( event != NULL );
1489
1490 orcdata = (ORCDATA*) eventdata;
1491 assert( orcdata != NULL );
1492
1493 /* only update the global bounds if the propagator has not been called yet */
1494 if ( orcdata->symmetrybrokencomputed )
1495 {
1496 /* identifyOrbitalSymmetriesBroken is only called when we're propagating, which is only done for during solving */
1498 return SCIP_OKAY;
1499 }
1500
1501 var = SCIPeventGetVar(event);
1502 assert( var != NULL );
1503 assert( SCIPvarIsTransformed(var) );
1504
1505 assert( orcdata->permvarmap != NULL );
1506 varidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) var);
1507
1508 switch ( SCIPeventGetType(event) )
1509 {
1511 /* can assert with equality, because no arithmetic must be applied after inheriting the value of oldbound */
1512 assert( orcdata->globalvarubs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */
1513 orcdata->globalvarubs[varidx] = SCIPeventGetNewbound(event);
1514 break;
1516 assert( orcdata->globalvarlbs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */
1517 orcdata->globalvarlbs[varidx] = SCIPeventGetNewbound(event);
1518 break;
1519 default:
1520 SCIPABORT();
1521 return SCIP_ERROR;
1522 }
1523
1524 return SCIP_OKAY;
1525}
1526
1527
1528/*
1529 * Interface methods
1530 */
1531
1532
1533/** prints orbital reduction data */
1535 SCIP* scip, /**< SCIP data structure */
1536 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1537 int* nred, /**< pointer to store the total number of reductions applied */
1538 int* ncutoff /**< pointer to store the total number of cutoffs applied */
1539 )
1540{
1541 assert( scip != NULL );
1542 assert( orbireddata != NULL );
1543
1544 *nred = orbireddata->nred;
1545 *ncutoff = orbireddata->ncutoff;
1546
1547 return SCIP_OKAY;
1548}
1549
1550/** prints orbital reduction data */
1552 SCIP* scip, /**< SCIP data structure */
1553 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */
1554 )
1555{
1556 int i;
1557
1558 assert( scip != NULL );
1559 assert( orbireddata != NULL );
1560
1561 if ( orbireddata->ncomponents == 0 )
1562 {
1563 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbital reduction: no components\n");
1564 return SCIP_OKAY;
1565 }
1566
1568 " orbital reduction: %4d components of sizes ", orbireddata->ncomponents);
1569 for (i = 0; i < orbireddata->ncomponents; ++i)
1570 {
1571 if ( i > 0 )
1573 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", orbireddata->componentdatas[i]->nperms);
1574 }
1576
1577 return SCIP_OKAY;
1578}
1579
1580
1581/** propagates orbital reduction */
1583 SCIP* scip, /**< SCIP data structure */
1584 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1585 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1586 int* nred, /**< pointer to store the number of domain reductions */
1587 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
1588 * only set this to TRUE when a reduction is found, never set to FALSE */
1589 )
1590{
1591 ORCDATA* orcdata;
1592 SCIP_SHADOWTREE* shadowtree;
1593 int c;
1594
1595 assert( scip != NULL );
1596 assert( orbireddata != NULL );
1597 assert( infeasible != NULL );
1598 assert( nred != NULL );
1599 assert( didrun != NULL );
1600
1601 *infeasible = FALSE;
1602 *nred = 0;
1603
1604 /* no components, no orbital reduction */
1605 assert( orbireddata->ncomponents >= 0 );
1606 if ( orbireddata->ncomponents == 0 )
1607 return SCIP_OKAY;
1608
1609 /* do nothing if we are in a probing node */
1610 if ( SCIPinProbing(scip) )
1611 return SCIP_OKAY;
1612
1613 /* do not run again in repropagation, since the path to the root might have changed */
1615 return SCIP_OKAY;
1616
1617 assert( orbireddata->shadowtreeeventhdlr != NULL );
1618 shadowtree = SCIPgetShadowTree(orbireddata->shadowtreeeventhdlr);
1619 assert( shadowtree != NULL );
1620
1621 for (c = 0; c < orbireddata->ncomponents; ++c)
1622 {
1623 orcdata = orbireddata->componentdatas[c];
1624 assert( orcdata != NULL );
1625 assert( orcdata->nperms > 0 );
1626 SCIP_CALL( orbitalReductionPropagateComponent(scip, orcdata, shadowtree, infeasible, nred) );
1627
1628 /* a symmetry propagator has ran, so set didrun to TRUE */
1629 *didrun = TRUE;
1630
1631 if ( *infeasible )
1632 break;
1633 }
1634
1635 orbireddata->nred += *nred;
1636 if ( *infeasible )
1637 ++orbireddata->ncutoff;
1638
1639 return SCIP_OKAY;
1640}
1641
1642
1643/** adds component for orbital reduction */
1645 SCIP* scip, /**< SCIP data structure */
1646 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1647 SCIP_VAR** permvars, /**< variable array of the permutation */
1648 int npermvars, /**< number of variables in that array */
1649 int** perms, /**< permutations in the component */
1650 int nperms, /**< number of permutations in the component */
1651 SCIP_Bool* success /**< to store whether the component is successfully added */
1652 )
1653{
1654 assert( scip != NULL );
1655 assert( orbireddata != NULL );
1656 assert( permvars != NULL );
1657 assert( npermvars > 0 );
1658 assert( perms != NULL );
1659 assert( nperms > 0 );
1660 assert( success != NULL );
1661
1662 /* dynamic symmetry reductions cannot be performed on original problem */
1663 assert( SCIPisTransformed(scip) );
1664
1665 SCIP_CALL( addComponent(scip, orbireddata, permvars, npermvars, perms, nperms, success) );
1666
1667 return SCIP_OKAY;
1668}
1669
1670
1671/** resets orbital reduction data structure (clears all components) */
1673 SCIP* scip, /**< SCIP data structure */
1674 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */
1675 )
1676{
1677 assert( scip != NULL );
1678 assert( orbireddata != NULL );
1679 assert( orbireddata->ncomponents >= 0 );
1680 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) );
1681 assert( orbireddata->ncomponents <= orbireddata->maxncomponents );
1682 assert( orbireddata->shadowtreeeventhdlr != NULL );
1683
1684 while ( orbireddata->ncomponents > 0 )
1685 {
1686 SCIP_CALL( freeComponent(scip, orbireddata, &(orbireddata->componentdatas[--orbireddata->ncomponents])) );
1687 }
1688
1689 assert( orbireddata->ncomponents == 0 );
1690 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->componentdatas, orbireddata->maxncomponents);
1691 orbireddata->componentdatas = NULL;
1692 orbireddata->maxncomponents = 0;
1693
1694 return SCIP_OKAY;
1695}
1696
1697
1698/** frees orbital reduction data */
1700 SCIP* scip, /**< SCIP data structure */
1701 SCIP_ORBITALREDDATA** orbireddata /**< orbital reduction data structure */
1702 )
1703{
1704 assert( scip != NULL );
1705 assert( orbireddata != NULL );
1706 assert( *orbireddata != NULL );
1707
1708 SCIP_CALL( SCIPorbitalReductionReset(scip, *orbireddata) );
1709
1710 SCIPfreeBlockMemory(scip, orbireddata);
1711 return SCIP_OKAY;
1712}
1713
1714
1715/** initializes structures needed for orbital reduction
1716 *
1717 * This is only done exactly once.
1718 */
1720 SCIP* scip, /**< SCIP data structure */
1721 SCIP_ORBITALREDDATA** orbireddata, /**< pointer to orbital reduction data structure to populate */
1722 SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */
1723 )
1724{
1725 assert( scip != NULL );
1726 assert( orbireddata != NULL );
1727 assert( shadowtreeeventhdlr != NULL );
1728
1729 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
1731
1732 SCIP_CALL( SCIPallocBlockMemory(scip, orbireddata) );
1733
1734 (*orbireddata)->componentdatas = NULL;
1735 (*orbireddata)->ncomponents = 0;
1736 (*orbireddata)->maxncomponents = 0;
1737 (*orbireddata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
1738 (*orbireddata)->nred = 0;
1739 (*orbireddata)->ncutoff = 0;
1740
1741 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(*orbireddata)->globalfixeventhdlr,
1742 EVENTHDLR_SYMMETRY_NAME, EVENTHDLR_SYMMETRY_DESC, eventExecGlobalBoundChange,
1743 (SCIP_EVENTHDLRDATA*) (*orbireddata)) );
1744
1745 return SCIP_OKAY;
1746}
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 SCIPABORT()
Definition: def.h:346
#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)
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11269
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11296
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:596
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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_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
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1218
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1053
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1242
#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
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Longint SCIPgetNNodes(SCIP *scip)
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 SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2321
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 SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:72
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
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_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
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 SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5538
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing constraints
public methods for message output
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_BOUNDTYPE boundchgtype
SCIP_SHADOWBOUNDUPDATE * branchingdecisions
SCIP_SHADOWBOUNDUPDATE * propagations
struct SCIP_ShadowNode * parent
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_RETCODE applyOrbitalReductionPropagations(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
static SCIP_RETCODE applyOrbitalBranchingPropagations(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
SCIP_RETCODE SCIPorbitalReductionFree(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitalReductionGetStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
SCIP_RETCODE SCIPincludeOrbitalReduction(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
SCIP_RETCODE SCIPorbitalReductionPrintStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
static SCIP_RETCODE orbitalReductionGetSymmetryStabilizerSubgroup(SCIP *scip, ORCDATA *orcdata, int **chosenperms, int *nchosenperms, SCIP_Real *varlbs, SCIP_Real *varubs, int *branchedvarindices, SCIP_Bool *inbranchedvarindices, int nbranchedvarindices)
SCIP_RETCODE SCIPorbitalReductionAddComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
static SCIP_RETCODE applyOrbitalReductionPart(SCIP *scip, ORCDATA *orcdata, SCIP_Bool *infeasible, int *nred, int *varorbitids, int *varorbitidssort, SCIP_Real *varlbs, SCIP_Real *varubs)
static SCIP_DECL_EVENTEXEC(eventExecGlobalBoundChange)
SCIP_RETCODE SCIPorbitalReductionReset(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
#define EVENTHDLR_SYMMETRY_NAME
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
static SCIP_RETCODE identifyOrbitalSymmetriesBroken(SCIP *scip, ORCDATA *orcdata)
static SCIP_RETCODE orbitalReductionPropagateComponent(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
static int bisectSortedArrayFindFirstGEQ(int *ids, int *idssort, int frameleft, int frameright, int findid)
static SCIP_RETCODE freeComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, ORCDATA **orcdata)
#define EVENTHDLR_SYMMETRY_DESC
static SCIP_RETCODE addComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:76
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:155
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:75
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
@ 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
@ SCIP_STAGE_FREE
Definition: type_set.h:57
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
type definitions for problem variables