121#define EVENTHDLR_SYMMETRY_NAME "symmetry_orbital"
122#define EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction"
152struct SCIP_OrbitalReductionData
186 int* varorbitidssort;
190 int maxnsymbrokenvarids;
193 SCIP_Bool orbitsymbroken;
200 maxnsymbrokenvarids = 0;
204 for (p = 0; p < orcdata->
nperms; ++p)
206 perm = orcdata->
perms[p];
234 for (orbitbegin = 0; orbitbegin < orcdata->
npermvars; orbitbegin = orbitend)
237 orbitid = varorbitids[varorbitidssort[orbitbegin]];
240 orbitsymbroken =
FALSE;
241 j = varorbitidssort[orbitbegin];
246 j = varorbitidssort[
i];
249 if ( varorbitids[j] != orbitid )
252 if ( !orbitsymbroken )
256 orbitsymbroken =
TRUE;
261 assert( orbitsymbroken ||
i == orcdata->
npermvars || varorbitids[j] != orbitid );
264 if ( orbitsymbroken )
266 while (
i < orcdata->npermvars && varorbitids[j] == orbitid )
267 j = varorbitidssort[++
i];
272 if ( orbitsymbroken )
275 if ( orcdata->
nsymbrokenvarids + orbitend - orbitbegin > maxnsymbrokenvarids )
291 maxnsymbrokenvarids, newsize) );
294 maxnsymbrokenvarids = newsize;
298 for (
i = orbitbegin;
i < orbitend; ++
i)
300 j = varorbitidssort[
i];
301 assert( varorbitids[j] == orbitid );
324 "Orbital fixing symmetry for %p broken before symmetry. Requires fixing %d/%d affected variables.\n",
350 int* branchedvarindices,
351 SCIP_Bool* inbranchedvarindices,
353 int nbranchedvarindices
369 assert( nbranchedvarindices >= 0 );
375 for (p = 0; p < orcdata->
nperms; ++p)
377 perm = orcdata->
perms[p];
384 assert( varid < orcdata->npermvars );
386 varidimage = perm[varid];
387 assert( varidimage >= 0 );
388 assert( varidimage < orcdata->npermvars );
392 if ( varidimage == varid )
413 for (
i = 0;
i < nbranchedvarindices; ++
i)
415 varid = branchedvarindices[
i];
417 assert( varid < orcdata->npermvars );
419 varidimage = perm[varid];
420 assert( varidimage >= 0 );
421 assert( varidimage < orcdata->npermvars );
425 if ( varidimage == varid )
435 if (
i < nbranchedvarindices )
439 chosenperms[(*nchosenperms)++] = perm;
464 origframeleft = frameleft;
465 origframeright = frameright;
471 assert( frameright >= frameleft );
474 if ( frameright == frameleft )
477 while (frameright - frameleft >= 2)
480 center = frameleft + ((frameright - frameleft) / 2);
481 assert( center > frameleft );
482 assert( center < frameright );
483 id = idssort[center];
484 if ( ids[
id] < findid )
496 assert( frameright - frameleft == 1 );
497 id = idssort[frameleft];
498 if ( ids[
id] < findid )
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 );
518 SCIP_Bool* infeasible,
521 int* varorbitidssort,
552 for (orbitbegin = 0; orbitbegin < orcdata->
npermvars; orbitbegin = orbitend)
555 orbitid = varorbitids[varorbitidssort[orbitbegin]];
556 for (orbitend = orbitbegin + 1; orbitend < orcdata->
npermvars; ++orbitend)
558 if ( varorbitids[varorbitidssort[orbitend]] != orbitid )
563 if ( orbitend - orbitbegin <= 1 )
569 for (
i = orbitbegin;
i < orbitend; ++
i)
571 varid = varorbitidssort[
i];
573 assert( varid < orcdata->npermvars );
593 for (
i = orbitbegin;
i < orbitend; ++
i)
595 varid = varorbitidssort[
i];
597 assert( varid < orcdata->npermvars );
599 if ( varlbs !=
NULL )
602 varlbs[varid] = orbitlb;
617 if ( varubs !=
NULL )
620 varubs[varid] = orbitub;
647 SCIP_Bool* infeasible,
663 int* branchedvarindices;
664 SCIP_Bool* inbranchedvarindices;
665 int nbranchedvarindices;
668 int branchingdecisionvarid;
674 int* varorbitidssort;
679 int orbitsetcomponentid;
698 if ( orcdata->
lastnode == focusnode )
705 if ( parentnode ==
NULL )
711 if ( shadowfocusnode ==
NULL )
716 " (and suppressing future warnings for this component)\n");
725 tmpshadownode = shadowfocusnode;
728 tmpshadownode = tmpshadownode->
parent;
731 while ( tmpshadownode !=
NULL );
735 tmpshadownode = shadowfocusnode;
738 rootedshadowpath[--
i] = tmpshadownode;
740 tmpshadownode = tmpshadownode->
parent;
759 nbranchedvarindices = 0;
762 tmpshadownode = rootedshadowpath[
depth];
769 assert( varid < orcdata->npermvars || varid == INT_MAX );
771 if ( varid < orcdata->npermvars )
796 assert( varid < orcdata->npermvars || varid == INT_MAX );
798 if ( varid < orcdata->npermvars )
800 if ( inbranchedvarindices[varid] )
802 branchedvarindices[nbranchedvarindices++] = varid;
803 inbranchedvarindices[varid] =
TRUE;
819 assert( branchingdecisionvarid < orcdata->npermvars || branchingdecisionvarid == INT_MAX );
820 assert( branchingdecisionvarid >= 0 );
823 if ( branchingdecisionvarid >= orcdata->
npermvars )
825 assert( branchingdecisionvarid >= 0 && branchingdecisionvarid < orcdata->npermvars );
836 varlbs, varubs, branchedvarindices, inbranchedvarindices, nbranchedvarindices) );
843 for (p = 0; p < nchosenperms; ++p)
845 perm = chosenperms[p];
868 varorbitidssort, varlbs, varubs) );
889 varlbs[branchingdecisionvarid] = branchingdecision->
newbound;
900 varubs[branchingdecisionvarid] = branchingdecision->
newbound;
916 orbitsetcomponentid);
917 assert( orbitbegin >= 0 && orbitbegin < orcdata->npermvars );
918 assert( varorbitids[varorbitidssort[orbitbegin]] == orbitsetcomponentid );
919 assert( orbitbegin == 0 || varorbitids[varorbitidssort[orbitbegin - 1]] < orbitsetcomponentid );
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 );
928 for (idx = orbitbegin; idx < orbitend; ++idx)
930 varid = varorbitidssort[idx];
931 assert( varorbitids[varid] == orbitsetcomponentid );
934 if ( varid == branchingdecisionvarid )
946 ||
SCIPsymGE(
scip, varlbs[branchingdecisionvarid], varlbs[varid]) );
948 ||
SCIPsymLE(
scip, varubs[branchingdecisionvarid], varubs[varid]) );
956 varubs[varid] = varubs[branchingdecisionvarid];
961 infeasible, &tightened) );
984 if ( !inbranchedvarindices[branchingdecisionvarid] )
986 assert( nbranchedvarindices < orcdata->npermvars );
987 branchedvarindices[nbranchedvarindices++] = branchingdecisionvarid;
988 inbranchedvarindices[branchingdecisionvarid] =
TRUE;
994 for (
i = 0;
i < nbranchedvarindices; ++
i)
996 varid = branchedvarindices[
i];
998 assert( varid < orcdata->npermvars );
999 assert( inbranchedvarindices[varid] );
1000 inbranchedvarindices[varid] =
FALSE;
1025 SCIP_Bool* infeasible,
1034 int* branchedvarindices;
1035 SCIP_Bool* inbranchedvarindices;
1036 int nbranchedvarindices;
1044 int* varorbitidssort;
1071 nbranchedvarindices = 0;
1072 tmpshadownode = shadowfocusnode;
1073 while ( tmpshadownode !=
NULL )
1080 assert( varid < orcdata->npermvars || varid == INT_MAX );
1082 if ( varid < orcdata->npermvars )
1084 if ( inbranchedvarindices[varid] )
1086 branchedvarindices[nbranchedvarindices++] = varid;
1087 inbranchedvarindices[varid] =
TRUE;
1090 tmpshadownode = tmpshadownode->
parent;
1097 NULL,
NULL, branchedvarindices, inbranchedvarindices, nbranchedvarindices) );
1098 assert( nchosenperms >= 0 );
1101 if ( nchosenperms == 0 )
1110 for (p = 0; p < nchosenperms; ++p)
1112 perm = chosenperms[p];
1137 for (
i = 0;
i < nbranchedvarindices; ++
i)
1139 varid = branchedvarindices[
i];
1141 assert( varid < orcdata->npermvars );
1142 assert( inbranchedvarindices[varid] );
1143 inbranchedvarindices[varid] =
FALSE;
1186 SCIP_Bool* infeasible,
1267 for (
i = 0;
i < npermvars; ++
i)
1270 for (p = 0; p < nperms; ++p)
1272 if ( perms[p][
i] !=
i )
1296 for (
i = 0;
i < npermvars; ++
i)
1302 for (p = 0; p < nperms; ++p)
1304 if ( perms[p][
i] !=
i )
1319 orcdata->
nperms = nperms;
1321 for (p = 0; p < nperms; ++p)
1324 origperm = perms[p];
1325 newperm = orcdata->
perms[p];
1327 for (
i = 0;
i < npermvars; ++
i)
1333 assert( newidx < orcdata->npermvars );
1336 assert( newpermidx >= 0 );
1337 assert( newidx < orcdata->npermvars );
1340 newperm[newidx] = newpermidx;
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 )
1379 if ( orbireddata->ncomponents == 0 )
1386 orbireddata->ncomponents, newsize) );
1389 orbireddata->maxncomponents = newsize;
1396 assert( orbireddata->ncomponents < orbireddata->maxncomponents );
1397 orbireddata->componentdatas[orbireddata->ncomponents++] = orcdata;
1420 assert( (*orcdata)->nperms > 0 );
1421 assert( (*orcdata)->npermvars > 0 );
1425 assert( (*orcdata)->npermvars > 0 );
1430 if ( (*orcdata)->symmetrybrokencomputed )
1432 assert( ((*orcdata)->nsymbrokenvarids == 0) == ((*orcdata)->symbrokenvarids ==
NULL) );
1440 for (
i = (*orcdata)->npermvars - 1;
i >= 0; --
i)
1444 orbireddata->globalfixeventhdlr, (
SCIP_EVENTDATA*) (*orcdata), -1) );
1451 for (p = (*orcdata)->nperms -1; p >= 0; --p)
1458 for (
i = 0;
i < (*orcdata)->npermvars; ++
i)
1490 orcdata = (
ORCDATA*) eventdata;
1544 *nred = orbireddata->nred;
1545 *ncutoff = orbireddata->ncutoff;
1561 if ( orbireddata->ncomponents == 0 )
1568 " orbital reduction: %4d components of sizes ", orbireddata->ncomponents);
1569 for (
i = 0;
i < orbireddata->ncomponents; ++
i)
1585 SCIP_Bool* infeasible,
1601 *infeasible =
FALSE;
1605 assert( orbireddata->ncomponents >= 0 );
1606 if ( orbireddata->ncomponents == 0 )
1617 assert( orbireddata->shadowtreeeventhdlr !=
NULL );
1621 for (
c = 0;
c < orbireddata->ncomponents; ++
c)
1623 orcdata = orbireddata->componentdatas[
c];
1635 orbireddata->nred += *nred;
1637 ++orbireddata->ncutoff;
1679 assert( orbireddata->ncomponents >= 0 );
1680 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas ==
NULL) );
1681 assert( orbireddata->ncomponents <= orbireddata->maxncomponents );
1682 assert( orbireddata->shadowtreeeventhdlr !=
NULL );
1684 while ( orbireddata->ncomponents > 0 )
1689 assert( orbireddata->ncomponents == 0 );
1691 orbireddata->componentdatas =
NULL;
1692 orbireddata->maxncomponents = 0;
1734 (*orbireddata)->componentdatas =
NULL;
1735 (*orbireddata)->ncomponents = 0;
1736 (*orbireddata)->maxncomponents = 0;
1737 (*orbireddata)->shadowtreeeventhdlr = shadowtreeeventhdlr;
1738 (*orbireddata)->nred = 0;
1739 (*orbireddata)->ncutoff = 0;
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)
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)
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
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)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
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)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for message output
public methods for problem variables
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
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for SCIP variables
SCIP_Bool symmetrybrokencomputed
SCIP_HASHMAP * permvarmap
SCIP_Bool treewarninggiven
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)
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
struct SCIP_EventData SCIP_EVENTDATA
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_GLBCHANGED
enum SCIP_Retcode SCIP_RETCODE
type definitions for problem variables