SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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{
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;
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;
201
202 /* determine all orbits */
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 )
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 */
229 for (i = 0; i < orcdata->npermvars; ++i)
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 */
238
239 /* the orbit must have the same bounds */
242 orbitglb = orcdata->globalvarlbs[j];
243 orbitgub = orcdata->globalvarubs[j];
244 for (i = orbitbegin + 1; i < orcdata->npermvars; ++i)
245 {
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 {
257 break;
258 }
259 }
260 }
261 /* the loop above has terminated, so i is either orcdata->npermvars or varorbitidssort[i] is in the next orbit,
262 * and orbitglb and orbitgub are the maximal global lower bound and minimal global upper bound in orbit orbitid */
263 orbitend = i;
264
265 /* symmetry is broken within this orbit if the intersection of the global variable domains are empty */
266 if ( orbitsymbroken )
267 {
268 /* add all variable ids in the orbit to the symbrokenvarids array: resize if needed */
269 if ( orcdata->nsymbrokenvarids + orbitend - orbitbegin > maxnsymbrokenvarids )
270 {
271 int newsize;
272
273 newsize = SCIPcalcMemGrowSize(scip, orcdata->nsymbrokenvarids + orbitend - orbitbegin);
274 assert( newsize >= 0 );
275
276 if ( orcdata->nsymbrokenvarids == 0 )
277 {
278 assert( orcdata->symbrokenvarids == NULL );
280 }
281 else
282 {
283 assert( orcdata->symbrokenvarids != NULL );
286 }
287
289 }
290
291 /* add all variable ids in the orbit to the symbrokenvarids array: add */
292 for (i = orbitbegin; i < orbitend; ++i)
293 {
296 assert( orcdata->nsymbrokenvarids < maxnsymbrokenvarids );
297 orcdata->symbrokenvarids[orcdata->nsymbrokenvarids++] = j;
298 }
299 }
300 }
301
302 /* shrink the allocated array size to the actually needed size */
303 assert( orcdata->nsymbrokenvarids <= maxnsymbrokenvarids );
304 if ( orcdata->nsymbrokenvarids > 0 && orcdata->nsymbrokenvarids < maxnsymbrokenvarids )
305 {
307 maxnsymbrokenvarids, orcdata->nsymbrokenvarids) );
308 }
309 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) );
310
311 /* mark that this method is executed for the component */
312 orcdata->symmetrybrokencomputed = TRUE;
313
314 /* output information */
315 if ( orcdata->nsymbrokenvarids > 0 )
316 {
318 "Orbital fixing symmetry for %p broken before symmetry. Requires fixing %d/%d affected variables.\n",
319 (void*) orcdata, orcdata->nsymbrokenvarids, orcdata->npermvars);
320 }
321
325
326 return SCIP_OKAY;
327}
328
329
330/** populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions
331 *
332 * The symmetry subgroup considered is generated by all permutations where for all branching variables \f$x$
333 * with permuted variable \f$y$ for all possible variable assignments we have \f$x \leq y$.
334 * We restrict ourselves to testing this only for the group generators.
335 */
336static
338 SCIP* scip, /**< pointer to SCIP data structure */
339 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
340 int** chosenperms, /**< pointer to permutations that are chosen */
341 int* nchosenperms, /**< pointer to store the number of chosen permutations */
342 SCIP_Real* varlbs, /**< array of orcdata->permvars variable LBs. If NULL, use local bounds */
343 SCIP_Real* varubs, /**< array of orcdata->permvars variable UBs. If NULL, use local bounds */
344 int* branchedvarindices, /**< array of given branching decisions, in branching order */
345 SCIP_Bool* inbranchedvarindices, /**< array stating whether variable with index in orcdata->permvars is
346 * contained in the branching decisions. */
347 int nbranchedvarindices /**< number of branching decisions */
348 )
349{
350 int i;
351 int p;
352 int* perm;
353 int varid;
354 int varidimage;
355
356 assert( scip != NULL );
357 assert( orcdata != NULL );
358 assert( chosenperms != NULL );
360 assert( (varlbs == NULL) == (varubs == NULL) );
364 assert( orcdata->symmetrybrokencomputed );
365 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) );
366
367 *nchosenperms = 0;
368
369 for (p = 0; p < orcdata->nperms; ++p)
370 {
371 perm = orcdata->perms[p];
372
373 /* make sure that the symmetry broken orbit variable indices are met with equality */
374 for (i = 0; i < orcdata->nsymbrokenvarids; ++i)
375 {
376 varid = orcdata->symbrokenvarids[i];
377 assert( varid >= 0 );
378 assert( varid < orcdata->npermvars );
379 assert( orcdata->permvars[varid] != NULL );
380 varidimage = perm[varid];
381 assert( varidimage >= 0 );
382 assert( varidimage < orcdata->npermvars );
383 assert( orcdata->permvars[varidimage] != NULL );
384
385 /* branching variable is not affected by this permutation */
386 if ( varidimage == varid )
387 continue;
388
389 /* the variables on which symmetry is broken must be permuted to entries with the same fixed value
390 *
391 * Because we check a whole orbit of the group and perm is part of it, it suffices to compare the upper bound
392 * of varid with the lower bound of varidimage. Namely, for all indices i, \f$lb_i \leq ub_i\f$, so we get
393 * a series of equalities yielding that all expressions must be the same:
394 * \f$ub_i = lb_j <= ub_j = lb_{\cdots} <= \cdots = lb_j < ub_j \f$
395 */
396 if ( ! SCIPsymEQ(scip,
397 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]),
398 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) )
399 )
400 break;
401 }
402 /* if the above loop is broken, this permutation does not qualify for the stabilizer */
403 if ( i < orcdata->nsymbrokenvarids )
404 continue;
405
406 /* iterate over each branched variable and check */
407 for (i = 0; i < nbranchedvarindices; ++i)
408 {
410 assert( varid >= 0 );
411 assert( varid < orcdata->npermvars );
412 assert( orcdata->permvars[varid] != NULL );
413 varidimage = perm[varid];
414 assert( varidimage >= 0 );
415 assert( varidimage < orcdata->npermvars );
416 assert( orcdata->permvars[varidimage] != NULL );
417
418 /* branching variable is not affected by this permutation */
419 if ( varidimage == varid )
420 continue;
421
422 if ( SCIPsymGT(scip,
423 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]),
424 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) )
425 )
426 break;
427 }
428 /* if the above loop is broken, this permutation does not qualify for the stabilizer */
429 if ( i < nbranchedvarindices )
430 continue;
431
432 /* permutation qualifies for the stabilizer. Add permutation */
433 chosenperms[(*nchosenperms)++] = perm;
434 }
435
436 return SCIP_OKAY;
437}
438
439/** using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid
440 *
441 * If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright.
442 */
443static
445 int* ids, /**< int array with entries */
446 int* idssort, /**< array of indices of ids that sort ids */
447 int frameleft, /**< search in idssort for index range [frameleft, frameright) */
448 int frameright, /**< search in idssort for index range [frameleft, frameright) */
449 int findid /**< entry value to find */
450 )
451{
452 int center;
453 int id;
454
455#ifndef NDEBUG
456 int origframeleft;
457 int origframeright;
460#endif
461
462 assert( ids != NULL );
463 assert( idssort != NULL );
464 assert( frameleft >= 0 );
466
467 /* empty frame case */
468 if ( frameright == frameleft )
469 return frameright;
470
471 while (frameright - frameleft >= 2)
472 {
473 /* split [frameleft, frameright) in [frameleft, center) and [center, frameright) */
474 center = frameleft + ((frameright - frameleft) / 2);
477 id = idssort[center];
478 if ( ids[id] < findid )
479 {
480 /* first instance greater or equal to findid is in [center, frameright) */
482 }
483 else
484 {
485 /* first instance greater or equal to findid is in [frameleft, center) */
487 }
488 }
489
490 assert( frameright - frameleft == 1 );
491 id = idssort[frameleft];
492 if ( ids[id] < findid )
493 ++frameleft;
494
498 assert( frameleft - 1 < origframeleft || ids[idssort[frameleft - 1]] < findid );
499 return frameleft;
500}
501
502
503/** applies the orbital reduction steps for precomputed orbits
504 *
505 * Either use the local variable bounds, or variable bounds determined by the @param varlbs and @param varubs arrays.
506 * @pre @param varubs is NULL if and only if @param varlbs is NULL.
507 */
508static
510 SCIP* scip, /**< pointer to SCIP data structure */
511 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
512 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
513 int* nred, /**< pointer to store the number of determined domain reductions */
514 int* varorbitids, /**< array specifying the orbit IDs for variables in array orcdata->vars */
515 int* varorbitidssort, /**< an index array that sorts the varorbitids array */
516 SCIP_Real* varlbs, /**< array of lower bounds for variable array orcdata->vars to compute with
517 * or NULL, if local bounds are used */
518 SCIP_Real* varubs /**< array of upper bounds for variable array orcdata->vars to compute with
519 * or NULL, if local bounds are used. */
520 )
521{
522 int i;
523 int varid;
524 int orbitid;
525 int orbitbegin;
526 int orbitend;
527 SCIP_Real orbitlb;
528 SCIP_Real orbitub;
529 SCIP_Real lb;
530 SCIP_Real ub;
531
532 assert( scip != NULL );
533 assert( orcdata != NULL );
534 assert( infeasible != NULL );
535 assert( nred != NULL );
536 assert( varorbitids != NULL );
538 assert( ( varlbs == NULL ) == ( varubs == NULL ) );
539
540 /* infeasible and nred are defined by the function that calls this function,
541 * and this function only gets called if no infeasibility is found so far.
542 */
543 assert( !*infeasible );
544 assert( *nred >= 0 );
545
546 for (orbitbegin = 0; orbitbegin < orcdata->npermvars; orbitbegin = orbitend)
547 {
548 /* get id of the orbit, and scan how large the orbit is */
550 for (orbitend = orbitbegin + 1; orbitend < orcdata->npermvars; ++orbitend)
551 {
553 break;
554 }
555
556 /* orbits consisting of only one element cannot yield reductions */
557 if ( orbitend - orbitbegin <= 1 )
558 continue;
559
560 /* get upper and lower bounds in orbit */
561 orbitlb = -INFINITY;
563 for (i = orbitbegin; i < orbitend; ++i)
564 {
566 assert( varid >= 0 );
567 assert( varid < orcdata->npermvars );
568 assert( orcdata->permvars[varid] != NULL );
569
570 lb = varlbs ? varlbs[varid] : SCIPvarGetLbLocal(orcdata->permvars[varid]);
571 if ( SCIPsymGT(scip, lb, orbitlb) )
572 orbitlb = lb;
573 ub = varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]);
574 if ( SCIPsymLT(scip, ub, orbitub) )
575 orbitub = ub;
576 }
577
578 /* if bounds are incompatible, infeasibility is detected */
579 if ( SCIPsymGT(scip, orbitlb, orbitub) )
580 {
581 *infeasible = TRUE;
582 return SCIP_OKAY;
583 }
585
586 /* update variable bounds to be in this range */
587 for (i = orbitbegin; i < orbitend; ++i)
588 {
590 assert( varid >= 0 );
591 assert( varid < orcdata->npermvars );
592
593 if ( varlbs != NULL )
594 {
595 assert( SCIPsymLE(scip, varlbs[varid], orbitlb) );
596 varlbs[varid] = orbitlb;
597 }
598 if ( !SCIPisInfinity(scip, -orbitlb) &&
600 {
601 SCIP_Bool tightened;
602 SCIP_CALL( SCIPtightenVarLb(scip, orcdata->permvars[varid], orbitlb, TRUE, infeasible, &tightened) );
603
604 /* propagator detected infeasibility in this node */
605 if ( *infeasible )
606 return SCIP_OKAY;
607 assert( tightened );
608 *nred += 1;
609 }
610
611 if ( varubs != NULL )
612 {
613 assert( SCIPsymGE(scip, varubs[varid], orbitub) );
614 varubs[varid] = orbitub;
615 }
616 if ( !SCIPisInfinity(scip, orbitub) &&
618 {
619 SCIP_Bool tightened;
620 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], orbitub, TRUE, infeasible, &tightened) );
621
622 /* propagator detected infeasibility in this node */
623 if ( *infeasible )
624 return SCIP_OKAY;
625 assert( tightened );
626 *nred += 1;
627 }
628 }
629 }
630 assert( !*infeasible );
631 return SCIP_OKAY;
632}
633
634
635/** orbital reduction, the orbital branching part */
636static
638 SCIP* scip, /**< pointer to SCIP data structure */
639 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
640 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
641 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
642 int* nred /**< pointer to store the number of determined domain reductions */
643 )
644{
645 SCIP_NODE* focusnode;
650 int pathlength;
651 int depth;
652 int branchstep;
653 int i;
654 SCIP_Real* varlbs;
655 SCIP_Real* varubs;
658 SCIP_Bool* inbranchedvarindices;
660 int varid;
663 int** chosenperms;
664 int* perm;
665 int nchosenperms;
666 int p;
667 int* varorbitids;
668 int* varorbitidssort;
669 int idx;
670 int orbitbegin;
671 int orbitend;
674
675 assert( scip != NULL );
676 assert( orcdata != NULL );
677 assert( shadowtree != NULL );
678 assert( infeasible != NULL );
679 assert( nred != NULL );
680
681 /* infeasible and nred are defined by the function that calls this function,
682 * and this function only gets called if no infeasibility is found so far.
683 */
684 assert( !*infeasible );
685 assert( *nred >= 0 );
686
687 focusnode = SCIPgetFocusNode(scip);
688 assert( focusnode == SCIPgetCurrentNode(scip) );
689 assert( focusnode != NULL );
690
691 /* do nothing if this method has already been called for this node */
692 if ( orcdata->lastnode == focusnode )
693 return SCIP_OKAY;
694
695 orcdata->lastnode = focusnode;
696 parentnode = SCIPnodeGetParent(focusnode);
697
698 /* the root node has not been generated by branching decisions */
699 if ( parentnode == NULL )
700 return SCIP_OKAY;
701
702 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
703
704 /* do not apply orbital reduction if focusnode does not exist in the shadowtree */
705 if ( shadowfocusnode == NULL )
706 {
707 if ( !orcdata->treewarninggiven )
708 {
709 SCIPwarningMessage(scip, "Attempting orbital reduction on nodes not existing in the symmetry shadowtree"
710 " (and suppressing future warnings for this component)\n");
711 orcdata->treewarninggiven = TRUE;
712 }
713 return SCIP_OKAY;
714 }
715
716 /* get the rooted path */
717 /* @todo add depth field to shadow tree node to improve efficiency */
718 pathlength = 0;
720 do
721 {
723 ++pathlength;
724 }
725 while ( tmpshadownode != NULL );
726
728 i = pathlength;
730 while ( i > 0 )
731 {
735 }
737 assert( i == 0 );
738
739 /* replay bound reductions and propagations made until just before the focusnode */
740 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */
741
742 SCIP_CALL( SCIPallocBufferArray(scip, &varlbs, orcdata->npermvars) );
743 SCIP_CALL( SCIPallocBufferArray(scip, &varubs, orcdata->npermvars) );
746
747 /* start with the bounds found after computing the symmetry group */
748 for (i = 0; i < orcdata->npermvars; ++i)
749 varlbs[i] = orcdata->globalvarlbs[i];
750 for (i = 0; i < orcdata->npermvars; ++i)
751 varubs[i] = orcdata->globalvarubs[i];
752
754 for (depth = 0; depth < pathlength - 1; ++depth)
755 {
757
758 /* receive propagations */
759 for (i = 0; i < tmpshadownode->npropagations; ++i)
760 {
761 update = &(tmpshadownode->propagations[i]);
762 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
763 assert( varid < orcdata->npermvars || varid == INT_MAX );
764 assert( varid >= 0 );
765 if ( varid < orcdata->npermvars )
766 {
767 assert( SCIPsymLE(scip, varlbs[varid], varubs[varid]) );
768 switch (update->boundchgtype)
769 {
771 assert( SCIPsymGE(scip, update->newbound, varlbs[varid]) );
772 varlbs[varid] = update->newbound;
773 break;
775 assert( SCIPsymLE(scip, update->newbound, varubs[varid]) );
776 varubs[varid] = update->newbound;
777 break;
778 default:
779 assert( FALSE );
780 }
781 assert( SCIPsymLE(scip, varlbs[varid], varubs[varid]) );
782 }
783 }
784
785 /* receive variable indices of branched variables */
786 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i)
787 {
788 update = &(tmpshadownode->branchingdecisions[i]);
789 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
790 assert( varid < orcdata->npermvars || varid == INT_MAX );
791 assert( varid >= 0 );
792 if ( varid < orcdata->npermvars )
793 {
795 continue;
798 }
799 }
800 }
801
802 /* determine symmetry group at this point, apply branched variable, apply orbital branching for this
803 *
804 * The branching variables are applied one-after-the-other.
805 * So, the group before branching is determined, orbital branching to the branching variable, then the branching
806 * variable is applied, and possibly repeated for other branching variables.
807 */
809 for (branchstep = 0; branchstep < shadowfocusnode->nbranchingdecisions; ++branchstep)
810 {
811 branchingdecision = &(shadowfocusnode->branchingdecisions[branchstep]);
815
816 /* branching decision will not have an effect on this */
817 if ( branchingdecisionvarid >= orcdata->npermvars )
818 continue;
824
825 /* get the generating set of permutations of a subgroup of a stabilizing symmetry subgroup.
826 *
827 * Note: All information about branching decisions is kept in varlbs, varubs, and the branchedvarindices.
828 */
831
832 /* compute orbit containing branching var */
834
835 /* put elements mapping to each other in same orbit */
836 /* @todo a potential performance hazard; quadratic time */
837 for (p = 0; p < nchosenperms; ++p)
838 {
839 perm = chosenperms[p];
840 for (i = 0; i < orcdata->npermvars; ++i)
841 {
842 if ( i != perm[i] )
844 }
845 }
846
847 /* 1. ensure that the bounds are tightest possible just before the branching step (orbital reduction step)
848 *
849 * If complete propagation was applied in the previous node,
850 * then all variables in the same orbit have the same bounds just before branching,
851 * so the bounds of the branching variable should be the tightest in its orbit by now.
852 * It is possible that that is not the case. In that case, we do it here.
853 */
856 for (i = 0; i < orcdata->npermvars; ++i)
859
860 /* apply orbital reduction to these orbits */
862 varorbitidssort, varlbs, varubs) );
863 if ( *infeasible )
864 goto FREE;
865 assert( !*infeasible );
866
867 /* 2. apply branching step to varlbs or varubs array
868 *
869 * Due to the steps above, it is possible that the branching step is redundant or infeasible.
870 */
872 switch (branchingdecision->boundchgtype)
873 {
875 /* incompatible upper bound */
876 if ( SCIPsymGT(scip, branchingdecision->newbound, varubs[branchingdecisionvarid]) )
877 {
878 *infeasible = TRUE;
879 goto FREE;
880 }
881
883 varlbs[branchingdecisionvarid] = branchingdecision->newbound;
884 break;
886 /* incompatible lower bound */
887 if ( SCIPsymLT(scip, branchingdecision->newbound, varlbs[branchingdecisionvarid]) )
888 {
889 *infeasible = TRUE;
890 goto FREE;
891 }
892
894 varubs[branchingdecisionvarid] = branchingdecision->newbound;
895 break;
896 default:
897 assert( FALSE );
898 }
899
900 /* 3. propagate that branching variable is >= the variables in its orbit
901 *
902 * Also apply the updates to the variable arrays
903 */
904
905 /* get the orbit of the branching variable */
907
908 /* find the orbit in the sorted array of orbits. npermvars can be huge, so use bisection. */
911 assert( orbitbegin >= 0 && orbitbegin < orcdata->npermvars );
914
920
921 /* propagate that branching variable is >= the variables in its orbit */
922 for (idx = orbitbegin; idx < orbitend; ++idx)
923 {
924 varid = varorbitidssort[idx];
926
927 /* ignore current branching variable */
929 continue;
930
931 /* is variable varid in the orbit? */
933 continue;
934
935 /* all variables in the same orbit have the same bounds just before branching,
936 * due to orbital reduction. If that was not the case, these steps are applied just before applying
937 * the branching step above. After the branching step, the branching variable bounds are most restricted.
938 */
940 || SCIPsymGE(scip, varlbs[branchingdecisionvarid], varlbs[varid]) );
942 || SCIPsymLE(scip, varubs[branchingdecisionvarid], varubs[varid]) );
943 /* bound changes already made could only have tightened the variable domains we are thinking about */
944 assert( SCIPsymGE(scip, SCIPvarGetLbLocal(orcdata->permvars[varid]), varlbs[varid]) );
945 assert( SCIPsymLE(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[varid]) );
946
947 /* for branching variable x and variable y in its orbit, propagate x >= y. */
948 /* modify UB of y-variables */
949 assert( SCIPsymGE(scip, varubs[varid], varubs[branchingdecisionvarid]) );
950 varubs[varid] = varubs[branchingdecisionvarid];
952 {
953 SCIP_Bool tightened;
955 infeasible, &tightened) );
956
957 /* propagator detected infeasibility in this node. */
958 if ( *infeasible )
959 goto FREE;
960 assert( tightened );
961 *nred += 1;
962 }
963
964 /* because variable domains are initially the same, the LB of the x-variables does not need to be modified. */
965 assert( SCIPsymLE(scip, varlbs[varid], varlbs[branchingdecisionvarid]) );
966 }
967
968 FREE:
972
973 if ( *infeasible )
974 break;
975
976 /* for the next branched variable at this node, if it's not already added,
977 * mark the branching variable of this iteration as a branching variable. */
979 {
983 }
984 }
986
987 /* clean inbranchedvarindices array */
988 for (i = 0; i < nbranchedvarindices; ++i)
989 {
991 assert( varid >= 0 );
992 assert( varid < orcdata->npermvars );
995 }
996#ifndef NDEBUG
997 for (i = 0; i < orcdata->npermvars; ++i)
998 {
1000 }
1001#endif
1002
1003 /* free everything */
1006 SCIPfreeBufferArray(scip, &varubs);
1007 SCIPfreeBufferArray(scip, &varlbs);
1009
1010 return SCIP_OKAY;
1011}
1012
1013/** orbital reduction, the orbital reduction part */
1014static
1016 SCIP* scip, /**< pointer to SCIP data structure */
1017 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */
1018 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
1019 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */
1020 int* nred /**< pointer to store the number of determined domain reductions */
1021 )
1022{
1023 SCIP_NODE* focusnode;
1026 int i;
1027 SCIP_SHADOWBOUNDUPDATE* update;
1028 int* branchedvarindices;
1029 SCIP_Bool* inbranchedvarindices;
1031 int varid;
1032 int** chosenperms;
1033 int* perm;
1034 int nchosenperms;
1035 int p;
1037 int* varorbitids;
1038 int* varorbitidssort;
1039
1040 assert( scip != NULL );
1041 assert( orcdata != NULL );
1042 assert( shadowtree != NULL );
1043 assert( infeasible != NULL );
1044 assert( nred != NULL );
1045
1046 /* infeasible and nred are defined by the function that calls this function,
1047 * and this function only gets called if no infeasibility is found so far.
1048 */
1049 assert( !*infeasible );
1050 assert( *nred >= 0 );
1051
1052 focusnode = SCIPgetFocusNode(scip);
1053 assert( focusnode == SCIPgetCurrentNode(scip) );
1054 assert( focusnode != NULL );
1055
1056 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode);
1058
1059 /* get the branching variables until present, so including the branchings of the focusnode */
1060 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */
1061
1064
1067 while ( tmpshadownode != NULL )
1068 {
1069 /* receive variable indices of branched variables */
1070 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i)
1071 {
1072 update = &(tmpshadownode->branchingdecisions[i]);
1073 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var);
1074 assert( varid < orcdata->npermvars || varid == INT_MAX );
1075 assert( varid >= 0 );
1076 if ( varid < orcdata->npermvars )
1077 {
1079 continue;
1082 }
1083 }
1084 tmpshadownode = tmpshadownode->parent;
1085 }
1086
1087 /* 1. compute the orbit of the branching variable of the stabilized symmetry subgroup at this point. */
1088 /* 1.1. identify the permutations of the symmetry group that are permitted */
1092 assert( nchosenperms >= 0 );
1093
1094 /* no reductions can be yielded by orbital reduction if the group is trivial */
1095 if ( nchosenperms == 0 )
1096 goto FREE;
1097
1098 /* 1.2. compute orbits of this subgroup */
1100
1101 /* put elements mapping to each other in same orbit */
1102 /* @todo this is O(nchosenperms * npermvars), which is a potential performance bottleneck.
1103 Alternative: precompute support per permutation at initialization, and iterate over these.*/
1104 for (p = 0; p < nchosenperms; ++p)
1105 {
1106 perm = chosenperms[p];
1107 for (i = 0; i < orcdata->npermvars; ++i)
1108 {
1109 if ( i != perm[i] )
1111 }
1112 }
1113
1114 /* 2. for each orbit, take the intersection of the domains */
1117 for (i = 0; i < orcdata->npermvars; ++i)
1120
1121 /* apply orbital reduction to these orbits */
1123
1127FREE:
1129
1130 /* clean inbranchedvarindices array */
1131 for (i = 0; i < nbranchedvarindices; ++i)
1132 {
1134 assert( varid >= 0 );
1135 assert( varid < orcdata->npermvars );
1138 }
1139#ifndef NDEBUG
1140 for (i = 0; i < orcdata->npermvars; ++i)
1141 {
1143 }
1144#endif
1145
1148
1149 return SCIP_OKAY;
1150}
1151
1152
1153/** applies orbital reduction on a symmetry group component using a two step mechanism
1154 *
1155 * 1. At the parent of our focus node (which is the current node, because we're not probing),
1156 * compute the symmetry group just before branching. Then, for our branching variable x with variable y in its
1157 * orbit, we mimic adding the constraint x >= y by variable bound propagations in this node.
1158 *
1159 * In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields
1160 * 1. In the 1-branch: 1 = x >= y is a tautology (since y is in {0, 1}). Nothing happens.
1161 * 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching.
1162 * REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178.
1163 *
1164 * (This only needs to be done once per node.)
1165 *
1166 * 2. At the focus node itself, compute the symmetry group.
1167 * The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group
1168 * as described in the function orbitalReductionGetSymmetryStabilizerSubgroup.
1169 * For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable
1170 * domains in the orbit.
1171 *
1172 * This generalizes orbital fixing in the binary case.
1173 * REF: Margot 2002, Margot 2003, Orbital Branching, Ostrowski's PhD thesis.
1174 */
1175static
1177 SCIP* scip, /**< SCIP data structure */
1178 ORCDATA* orcdata, /**< orbital reduction component data */
1179 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */
1180 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1181 int* nred /**< pointer to store the number of domain reductions */
1182 )
1183{
1184 assert( scip != NULL );
1185 assert( orcdata != NULL );
1186 assert( shadowtree != NULL );
1187 assert( infeasible != NULL );
1188 assert( nred != NULL );
1189
1190 /* infeasible and nred are defined by the function that calls this function,
1191 * and this function only gets called if no infeasibility is found so far.
1192 */
1193 assert( !*infeasible );
1194 assert( *nred >= 0 );
1195
1196 /* orbital reduction is only propagated when branching has started */
1198
1199 /* if this is the first call, identify the orbits for which symmetry is broken */
1200 if ( !orcdata->symmetrybrokencomputed )
1201 {
1203 }
1204 assert( orcdata->symmetrybrokencomputed );
1205 assert( orcdata->nsymbrokenvarids <= orcdata->npermvars );
1206
1207 /* If symmetry is broken for all orbits, stop! */
1208 if ( orcdata->nsymbrokenvarids == orcdata->npermvars )
1209 return SCIP_OKAY;
1210
1211 /* step 1 */
1212 SCIP_CALL( applyOrbitalBranchingPropagations(scip, orcdata, shadowtree, infeasible, nred) );
1213 if ( *infeasible )
1214 return SCIP_OKAY;
1215
1216 /* step 2 */
1217 SCIP_CALL( applyOrbitalReductionPropagations(scip, orcdata, shadowtree, infeasible, nred) );
1218 if ( *infeasible )
1219 return SCIP_OKAY;
1220
1221 return SCIP_OKAY;
1222}
1223
1224
1225/** adds component */
1226static
1228 SCIP* scip, /**< SCIP data structure */
1229 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */
1230 SCIP_VAR** permvars, /**< variable array of the permutation */
1231 int npermvars, /**< number of variables in that array */
1232 int** perms, /**< permutations in the component */
1233 int nperms, /**< number of permutations in the component */
1234 SCIP_Bool* success /**< to store whether the component is successfully added */
1235 )
1236{
1238 int i;
1239 int j;
1240 int p;
1241 int* origperm;
1242 int* newperm;
1243 int newidx;
1244 int newpermidx;
1245
1246 assert( scip != NULL );
1247 assert( orbireddata != NULL );
1248 assert( permvars != NULL );
1249 assert( npermvars > 0 );
1250 assert( perms != NULL );
1251 assert( nperms > 0 );
1252 assert( success != NULL );
1253
1254 *success = TRUE;
1256
1257 /* correct indices by removing fixed points */
1258
1259 /* determine the number of vars that are moved by the component, assign to orcdata->npermvars */
1260 orcdata->npermvars = 0;
1261 for (i = 0; i < npermvars; ++i)
1262 {
1263 /* is index i moved by any of the permutations in the component? */
1264 for (p = 0; p < nperms; ++p)
1265 {
1266 if ( perms[p][i] != i )
1267 {
1268 ++orcdata->npermvars;
1269 break;
1270 }
1271 }
1272 }
1273
1274 /* do not support the setting where the component is empty */
1275 if ( orcdata->npermvars <= 0 )
1276 {
1278 *success = FALSE;
1279 return SCIP_OKAY;
1280 }
1281
1282 /* require that the shadowtree is active */
1283 SCIP_CALL( SCIPactivateShadowTree(scip, orbireddata->shadowtreeeventhdlr) );
1284
1285 /* create index-corrected permvars array and the inverse */
1286 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->permvars, orcdata->npermvars) );
1287 SCIP_CALL( SCIPhashmapCreate(&orcdata->permvarmap, SCIPblkmem(scip), orcdata->npermvars) );
1288
1289 j = 0;
1290 for (i = 0; i < npermvars; ++i)
1291 {
1292 /* permvars array must be unique */
1293 assert( SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]) == INT_MAX );
1294
1295 /* is index i moved by any of the permutations in the component? */
1296 for (p = 0; p < nperms; ++p)
1297 {
1298 if ( perms[p][i] != i )
1299 {
1300 /* var is moved by component; add, disable multiaggregation and capture */
1301 SCIP_CALL( SCIPcaptureVar(scip, permvars[i]) );
1302 orcdata->permvars[j] = permvars[i];
1303 SCIP_CALL( SCIPhashmapInsertInt(orcdata->permvarmap, (void*) permvars[i], j) );
1305 ++j;
1306 break;
1307 }
1308 }
1309 }
1310 assert( j == orcdata->npermvars );
1311
1312 /* allocate permutations */
1313 orcdata->nperms = nperms;
1314 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms, nperms) );
1315 for (p = 0; p < nperms; ++p)
1316 {
1317 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms[p], orcdata->npermvars) );
1318 origperm = perms[p];
1319 newperm = orcdata->perms[p];
1320
1321 for (i = 0; i < npermvars; ++i)
1322 {
1323 newidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]);
1324 if ( newidx >= orcdata->npermvars )
1325 continue;
1326 assert( newidx >= 0 );
1327 assert( newidx < orcdata->npermvars );
1328 assert( orcdata->permvars[newidx] == permvars[i] );
1329 newpermidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[origperm[i]]);
1330 assert( newpermidx >= 0 );
1331 assert( newidx < orcdata->npermvars ); /* this is in the orbit of any permutation, so cannot be INT_MAX */
1332 assert( orcdata->permvars[newpermidx] == permvars[origperm[i]] );
1333
1335 }
1336 }
1337
1338 /* global variable bounds */
1339 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->globalvarlbs, orcdata->npermvars) );
1340 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->globalvarubs, orcdata->npermvars) );
1341 for (i = 0; i < orcdata->npermvars; ++i)
1342 {
1343 orcdata->globalvarlbs[i] = SCIPvarGetLbGlobal(orcdata->permvars[i]);
1344 orcdata->globalvarubs[i] = SCIPvarGetUbGlobal(orcdata->permvars[i]);
1345 }
1346
1347 /* catch global variable bound change event */
1348 for (i = 0; i < orcdata->npermvars; ++i)
1349 {
1351 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) orcdata, NULL) );
1352 }
1353
1354 /* lastnode field */
1355 orcdata->lastnode = NULL;
1356
1357 /* symmetry computed field */
1358 orcdata->symmetrybrokencomputed = FALSE;
1359 orcdata->symbrokenvarids = NULL;
1360 orcdata->nsymbrokenvarids = -1;
1361
1362 /* resize component array if needed */
1363 assert( orbireddata->ncomponents >= 0 );
1364 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) );
1365 assert( orbireddata->ncomponents <= orbireddata->maxncomponents );
1366 if ( orbireddata->ncomponents == orbireddata->maxncomponents )
1367 {
1368 int newsize;
1369
1370 newsize = SCIPcalcMemGrowSize(scip, orbireddata->ncomponents + 1);
1371 assert( newsize >= 0 );
1372
1373 if ( orbireddata->ncomponents == 0 )
1374 {
1376 }
1377 else
1378 {
1380 orbireddata->ncomponents, newsize) );
1381 }
1382
1383 orbireddata->maxncomponents = newsize;
1384 }
1385
1386 /* tree warning indicator */
1387 orcdata->treewarninggiven = FALSE;
1388
1389 /* add component */
1390 assert( orbireddata->ncomponents < orbireddata->maxncomponents );
1391 orbireddata->componentdatas[orbireddata->ncomponents++] = orcdata;
1392
1393 return SCIP_OKAY;
1394}
1395
1396
1397/** frees component */
1398static
1400 SCIP* scip, /**< SCIP data structure */
1401 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */
1402 ORCDATA** orcdata /**< pointer to component data */
1403 )
1404{
1405 int i;
1406 int p;
1407
1408 assert( scip != NULL );
1409 assert( orbireddata != NULL );
1410 assert( orcdata != NULL );
1411 assert( *orcdata != NULL );
1412 assert( (*orcdata)->globalvarlbs != NULL );
1413 assert( (*orcdata)->globalvarubs != NULL );
1414 assert( (*orcdata)->nperms > 0 );
1415 assert( (*orcdata)->npermvars > 0 );
1416 assert( (*orcdata)->perms != NULL );
1417 assert( (*orcdata)->permvarmap != NULL );
1418 assert( (*orcdata)->permvars != NULL );
1419 assert( (*orcdata)->npermvars > 0 );
1420
1422
1423 /* free symmetry broken information if it has been computed */
1424 if ( (*orcdata)->symmetrybrokencomputed )
1425 {
1426 assert( ((*orcdata)->nsymbrokenvarids == 0) == ((*orcdata)->symbrokenvarids == NULL) );
1427 SCIPfreeBlockMemoryArrayNull(scip, &(*orcdata)->symbrokenvarids, (*orcdata)->nsymbrokenvarids);
1428 }
1429
1430 /* free global variable bound change event */
1432 {
1433 /* events at the freeing stage may not be dropped, because they are already getting dropped */
1434 for (i = (*orcdata)->npermvars - 1; i >= 0; --i)
1435 {
1436 SCIP_CALL( SCIPdropVarEvent(scip, (*orcdata)->permvars[i],
1438 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) (*orcdata), -1) );
1439 }
1440 }
1441
1442 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarubs, (*orcdata)->npermvars);
1443 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarlbs, (*orcdata)->npermvars);
1444
1445 for (p = (*orcdata)->nperms -1; p >= 0; --p)
1446 {
1447 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms[p], (*orcdata)->npermvars);
1448 }
1449 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms, (*orcdata)->nperms);
1450
1451 /* release variables */
1452 for (i = 0; i < (*orcdata)->npermvars; ++i)
1453 {
1454 assert( (*orcdata)->permvars[i] != NULL );
1455 SCIP_CALL( SCIPreleaseVar(scip, &(*orcdata)->permvars[i]) );
1456 }
1457
1458 SCIPhashmapFree(&(*orcdata)->permvarmap);
1459 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->permvars, (*orcdata)->npermvars);
1460
1462
1463 return SCIP_OKAY;
1464}
1465
1466
1467/*
1468 * Event handler callback methods
1469 */
1470
1471/** maintains global variable bound reductions found during presolving or at the root node */
1472static
1474{
1476 SCIP_VAR* var;
1477 int varidx;
1478
1479 assert( eventhdlr != NULL );
1480 assert( eventdata != NULL );
1482 assert( event != NULL );
1483
1484 orcdata = (ORCDATA*) eventdata;
1485 assert( orcdata != NULL );
1486
1487 /* only update the global bounds if the propagator has not been called yet */
1488 if ( orcdata->symmetrybrokencomputed )
1489 {
1490 /* identifyOrbitalSymmetriesBroken is only called when we're propagating, which is only done for during solving */
1492 return SCIP_OKAY;
1493 }
1494
1496 assert( var != NULL );
1498
1499 assert( orcdata->permvarmap != NULL );
1500 varidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) var);
1501
1502 switch ( SCIPeventGetType(event) )
1503 {
1505 /* can assert with equality, because no arithmetic must be applied after inheriting the value of oldbound */
1506 assert( orcdata->globalvarubs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */
1507 orcdata->globalvarubs[varidx] = SCIPeventGetNewbound(event);
1508 break;
1510 assert( orcdata->globalvarlbs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */
1511 orcdata->globalvarlbs[varidx] = SCIPeventGetNewbound(event);
1512 break;
1513 default:
1514 SCIPABORT();
1515 return SCIP_ERROR;
1516 }
1517
1518 return SCIP_OKAY;
1519}
1520
1521
1522/*
1523 * Interface methods
1524 */
1525
1526
1527/** prints orbital reduction data */
1529 SCIP* scip, /**< SCIP data structure */
1530 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1531 int* nred, /**< pointer to store the total number of reductions applied */
1532 int* ncutoff /**< pointer to store the total number of cutoffs applied */
1533 )
1534{
1535 assert( scip != NULL );
1536 assert( orbireddata != NULL );
1537
1538 *nred = orbireddata->nred;
1539 *ncutoff = orbireddata->ncutoff;
1540
1541 return SCIP_OKAY;
1542}
1543
1544/** prints orbital reduction data */
1546 SCIP* scip, /**< SCIP data structure */
1547 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */
1548 )
1549{
1550 int i;
1551
1552 assert( scip != NULL );
1553 assert( orbireddata != NULL );
1554
1555 if ( orbireddata->ncomponents == 0 )
1556 {
1557 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbital reduction: no components\n");
1558 return SCIP_OKAY;
1559 }
1560
1562 " orbital reduction: %4d components of sizes ", orbireddata->ncomponents);
1563 for (i = 0; i < orbireddata->ncomponents; ++i)
1564 {
1565 if ( i > 0 )
1567 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", orbireddata->componentdatas[i]->nperms);
1568 }
1570
1571 return SCIP_OKAY;
1572}
1573
1574
1575/** propagates orbital reduction */
1577 SCIP* scip, /**< SCIP data structure */
1578 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1579 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */
1580 int* nred, /**< pointer to store the number of domain reductions */
1581 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run
1582 * only set this to TRUE when a reduction is found, never set to FALSE */
1583 )
1584{
1586 SCIP_SHADOWTREE* shadowtree;
1587 int c;
1588
1589 assert( scip != NULL );
1590 assert( orbireddata != NULL );
1591 assert( infeasible != NULL );
1592 assert( nred != NULL );
1593 assert( didrun != NULL );
1594
1595 *infeasible = FALSE;
1596 *nred = 0;
1597
1598 /* no components, no orbital reduction */
1599 assert( orbireddata->ncomponents >= 0 );
1600 if ( orbireddata->ncomponents == 0 )
1601 return SCIP_OKAY;
1602
1603 /* do nothing if we are in a probing node */
1604 if ( SCIPinProbing(scip) )
1605 return SCIP_OKAY;
1606
1607 /* do not run again in repropagation, since the path to the root might have changed */
1609 return SCIP_OKAY;
1610
1611 assert( orbireddata->shadowtreeeventhdlr != NULL );
1612 shadowtree = SCIPgetShadowTree(orbireddata->shadowtreeeventhdlr);
1613 assert( shadowtree != NULL );
1614
1615 for (c = 0; c < orbireddata->ncomponents; ++c)
1616 {
1617 orcdata = orbireddata->componentdatas[c];
1618 assert( orcdata != NULL );
1619 assert( orcdata->nperms > 0 );
1620 SCIP_CALL( orbitalReductionPropagateComponent(scip, orcdata, shadowtree, infeasible, nred) );
1621
1622 /* a symmetry propagator has ran, so set didrun to TRUE */
1623 *didrun = TRUE;
1624
1625 if ( *infeasible )
1626 break;
1627 }
1628
1629 orbireddata->nred += *nred;
1630 if ( *infeasible )
1631 ++orbireddata->ncutoff;
1632
1633 return SCIP_OKAY;
1634}
1635
1636
1637/** adds component for orbital reduction */
1639 SCIP* scip, /**< SCIP data structure */
1640 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */
1641 SCIP_VAR** permvars, /**< variable array of the permutation */
1642 int npermvars, /**< number of variables in that array */
1643 int** perms, /**< permutations in the component */
1644 int nperms, /**< number of permutations in the component */
1645 SCIP_Bool* success /**< to store whether the component is successfully added */
1646 )
1647{
1648 assert( scip != NULL );
1649 assert( orbireddata != NULL );
1650 assert( permvars != NULL );
1651 assert( npermvars > 0 );
1652 assert( perms != NULL );
1653 assert( nperms > 0 );
1654 assert( success != NULL );
1655
1656 /* dynamic symmetry reductions cannot be performed on original problem */
1658
1659 SCIP_CALL( addComponent(scip, orbireddata, permvars, npermvars, perms, nperms, success) );
1660
1661 return SCIP_OKAY;
1662}
1663
1664
1665/** resets orbital reduction data structure (clears all components) */
1667 SCIP* scip, /**< SCIP data structure */
1668 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */
1669 )
1670{
1671 assert( scip != NULL );
1672 assert( orbireddata != NULL );
1673 assert( orbireddata->ncomponents >= 0 );
1674 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) );
1675 assert( orbireddata->ncomponents <= orbireddata->maxncomponents );
1676 assert( orbireddata->shadowtreeeventhdlr != NULL );
1677
1678 while ( orbireddata->ncomponents > 0 )
1679 {
1680 SCIP_CALL( freeComponent(scip, orbireddata, &(orbireddata->componentdatas[--orbireddata->ncomponents])) );
1681 }
1682
1683 assert( orbireddata->ncomponents == 0 );
1684 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->componentdatas, orbireddata->maxncomponents);
1685 orbireddata->componentdatas = NULL;
1686 orbireddata->maxncomponents = 0;
1687
1688 return SCIP_OKAY;
1689}
1690
1691
1692/** frees orbital reduction data */
1694 SCIP* scip, /**< SCIP data structure */
1695 SCIP_ORBITALREDDATA** orbireddata /**< orbital reduction data structure */
1696 )
1697{
1698 assert( scip != NULL );
1699 assert( orbireddata != NULL );
1700 assert( *orbireddata != NULL );
1701
1703
1705 return SCIP_OKAY;
1706}
1707
1708
1709/** initializes structures needed for orbital reduction
1710 *
1711 * This is only done exactly once.
1712 */
1714 SCIP* scip, /**< SCIP data structure */
1715 SCIP_ORBITALREDDATA** orbireddata, /**< pointer to orbital reduction data structure to populate */
1716 SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */
1717 )
1718{
1719 assert( scip != NULL );
1720 assert( orbireddata != NULL );
1721 assert( shadowtreeeventhdlr != NULL );
1722
1723 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
1725
1727
1728 (*orbireddata)->componentdatas = NULL;
1729 (*orbireddata)->ncomponents = 0;
1730 (*orbireddata)->maxncomponents = 0;
1731 (*orbireddata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
1732 (*orbireddata)->nred = 0;
1733 (*orbireddata)->ncutoff = 0;
1734
1735 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(*orbireddata)->globalfixeventhdlr,
1738
1739 return SCIP_OKAY;
1740}
static SCIP_RETCODE freeComponent(COMPONENT *component)
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition debug.c:2208
methods for debugging
#define NULL
Definition def.h:267
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define 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)
SCIP_STAGE SCIPgetStage(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition misc.c:3192
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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:7724
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2264
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2192
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2302
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2340
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition symmetry.c:2226
SCIP_Bool 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:5205
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition var.c:17561
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5322
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
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:8717
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition misc.c:5538
return SCIP_OKAY
int c
int depth
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * var
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
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
#define EVENTHDLR_SYMMETRY_NAME
static SCIP_RETCODE identifyOrbitalSymmetriesBroken(SCIP *scip, ORCDATA *orcdata)
#define EVENTHDLR_SYMMETRY_DESC
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)
SCIP_RETCODE SCIPorbitalReductionAddComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
SCIP_RETCODE SCIPorbitalReductionReset(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
#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_DECL_EVENTEXEC(x)
Definition type_event.h:253
#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
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_FREE
Definition type_set.h:57
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
type definitions for problem variables