symmetry_orbitopal.c
Go to the documentation of this file.
30 * This implements orbitopal reducion, which generalizes full orbitope propagation to work for non-binary variable
31 * domains, and is dynamified. See cons_orbitope.c for the variant for binary variables, both the static and partially
33 * Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables
41 * If the variables can be arranged in a matrix and the symmetries correspond to all column permutations of this matrix,
44 * If a reduction on a variable is applied, and if this variable is high up in the variable matrix, then this has a
45 * relatively large impact on the lexicographic ordering. Moreover, the ordering of the columns also matter.
46 * Dynamification allows for choosing a custom ordering of a subset of rows and a permutation of the columns.
49 * If towards a new node it is branched on a variable, that appears in a row which is not included in the subset of
50 * rows for the current node, then the row set of the new children is the ordered row set of the current node, appended
52 * For the column order, if at the current node columns are symmetrically equivalent, then these can be permuted for
53 * the sake of symmetry handling. In the implementation, we only swap the column containing the branching variable
57 * - First: Permute such that the column containing the branching variable is in the symmetrically equivalent column
60 * - Centre: The same, but to the symmetrically equivalent column closest to to the middlemost column among all columns.
61 * - Median: The same, but to the median of all symmetrically equivalent columns. (This is the default)
63 * Since the dynamic row and column ordering rule for a branch-and-bound tree node depends on the decisions made up to
64 * that branch-and-bound tree node, we compute and store the row and column order for the branch-and-bound tree children
66 * Instead of storing those, we could have chosen to reconstruct this row and column ordering to save memory.
68 * because the row and column ordering depends on symmetrical equivalence of columns in the orbitope matrix,
69 * and because SCIP can change the tree structure during solving that may re-write historic variable bound changes
70 * (for instance when global variable bound changes are found, or when the root node is moved down the tree to become
72 * We are not concerned about storing the row and column ordering, since we only store the mutations with its parent.
79/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
135 SCIP_Longint lastnodenumber; /**< the last node number where the row and column order is computed */
142typedef struct OrbitopeData ORBITOPEDATA; /**< orbitopal symmetry handling data for a single orbitope */
242 * If all symmetry-compatible reductions are applied, then it suffices to check only as many rows as are selected
243 * for orbitopal reduction. However, to be resilient to reductions that are not symmetry-compatible,
286 * When it is branched on a variable in a column, update the column order for the children of the focusnode.
287 * Symmetrically equivalent columns, that is the columns where the variables have elementwise the same domain,
289 * In this function, we select such a permutation, based on the column containing the branching variable(s).
290 * In all cases, we swap the column containing the branching variable with a symmetrically equivalent column,
291 * and the columnordering specifies if we prefer it to be the leftmost, rightmost, centermost symmetrically
359 /* @todo other policies: If the variable is in a ppc-row, then select the minimal/second to minimal to branch on */
365 /* CENTRE uses the same code as FIRST and LAST, but requires that middlecolumn = ncols / 2 is set */
370 /* for each column, test column ordering condition, then if the column is identical to the var-column */
414 /* collect columns identical to the var-column, then select column satisfying ordering condition */
457 /* @todo computing the median is O(n) by repeated median-of-medians (CLRS, Ch9), but let's just sort things */
506 SCIPdebugMessage("Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n",
507 (void*) orbidata, origcolid, positionorigcolidincolorder, swaporigcolid, positionswaporigcolidincolorder);
607 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
647 SCIP_NODE** rootedpath, /**< array to populate with the rooted path, must be sufficiently long */
683 ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
766 maxnbranchvars = 1; /* it's a good guess that there's one branching variable, because that's likely the number */
853 assert( SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ); /* otherwise was not added to branchvars */
870 /* if we end up here, the row index does not appear for any ancestor or the present row order */
883 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
937 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps + 1) );
941 /* reallocate with linear increments, because we expect 1 branching variable most of the time */
1022 vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(orbidata->vars[rowid * orbidata->ncols + c])) );
1054 if ( (*orbidata)->columnordering != SCIP_COLUMNORDERING_NONE || (*orbidata)->rowordering != SCIP_ROWORDERING_NONE )
1096 SCIPfreeBlockMemoryArray(scip, &((*orbidata)->vars), (*orbidata)->nrows * (*orbidata)->ncols); /*lint !e647*/
1162 SCIPdebugMessage("Orbitope variables for (%dx%d) orbitope with orbidata %p\n", nrows, ncols, (void*) orbidata);
1198 /* @todo at getRowData: If nselrows == nbranchrows, append the non-branch rows (like before) */
1209 if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE || orbidata->rowordering != SCIP_ROWORDERING_NONE )
1217 * Assuming at most one branching on every variable implying a column swap, initial hashtable size nelem.
1220 SCIP_CALL( SCIPhashtableCreate(&orbidata->nodeinfos, scip->mem->probmem, MIN(16 * ncols + 64, nelem),
1241 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->orbitopes, orbireddata->norbitopes, newsize) );
1290 * The column order is (deterministically) dynamically decided based on the policy for column ordering.
1342 SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, *colorder, *colorderinv) );
1351/** checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering */
1362 SCIP_Bool addinfinitesimals /**< whether infinitesimals are added (TRUE) or subtracted (FALSE) */
1572 /* array to store for each column at which row we add an infinitesimal value, initially at none (-1) */
1594 /* "rowid" of the last unfixed entry whose domain allows for larger values than the current chosen.
1619 * Option 1: The upper bound is smaller. Then we're in an infeasible situation. Resolve as described below.
1630 * Try to repair: Go back to the last row with "room" left, and make the value minimally larger.
1648 assert( SCIPsymLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1652 assert( SCIPsymLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1669 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), min\n", colid, origcolid);
1687 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1726 /* there had been a row before which breaks the equality-condition, choose minimally possible value */
1734 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexminface, nselrows, ncols, lexminepsrow, TRUE);
1740 /* array to store for each column at which row we subtract an infinitesimal value, initially at none (-1) */
1762 /* "rowid" of the last unfixed entry whose domain allows for smaller values than the current chosen.
1775 /* the entry one to the left is not the last column, i.e., this column cannot be the first column */
1787 * Option 1: The lower bound is larger. Then we're in an infeasible situation. Resolve as described below.
1798 * Try to repair: Go back to the last row with "room" left, and make the value minimally smaller.
1816 assert( SCIPsymGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1817 assert( SCIPsymLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1821 assert( SCIPsymGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1822 assert( SCIPsymLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1839 SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), max\n", colid, origcolid);
1857 assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1883 /* continuous type: if we can subtract an infinitesimal value to the current lexmaxface[i] value,
1896 /* there had been a row before which breaks the equality-condition, choose maximally possible value */
1904 assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexmaxface, nselrows, ncols, lexmaxepsrow, FALSE);
1934 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1939 SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1952 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1957 SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1969 /* This is the row index where the min- and max-face have a different value for this column entry.
2066 /* DEBUG: if propagation is repeated in the same node, the same column order and row order is needed */
2083 SCIPdebugPrintf(" node %lld: (%d, %d, %d) \n", tmpnode->number, nbranchings, nconsprop, nprop);
2099 SCIP_CALL( propagateStaticOrbitope(scip, orbidata, roworder, nselrows, colorder, infeasible, nfixedvars) );
2210 SCIPdebugMessage("Found %d reductions during orbitopal reduction for orbitope %d\n", thisfixedvars, c);
2260 SCIP_CALL( addOrbitope(scip, orbireddata, rowordering, colordering, vars, nrows, ncols, success) );
2269 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
2282 SCIP_CALL( freeOrbitope(scip, orbireddata, &(orbireddata->orbitopes[--orbireddata->norbitopes])) );
2296 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2316 SCIP_ORBITOPALREDDATA** orbireddata /**< pointer to orbitopal reduction structure to populate */
2324 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitopalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2338 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExec, NULL) );
2361 SCIP_ORBITOPALREDDATA* orbireddata /**< pointer to orbitopal reduction structure to populate */
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
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2579
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2785
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4670
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
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:234
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
Definition: tree.c:7598
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:164
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_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17374
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17336
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_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
memory allocation routines
Definition: objbenders.h:44
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
Definition: symmetry_orbitopal.c:205
Definition: symmetry_orbitopal.c:197
Definition: symmetry_orbitopal.c:127
Definition: struct_var.h:92
Definition: struct_cons.h:127
Definition: struct_event.h:205
Definition: struct_misc.h:138
Definition: struct_misc.h:90
Definition: struct_tree.h:142
Definition: struct_var.h:208
Definition: struct_scip.h:70
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 propagateStaticOrbitope(SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int nselrows, int *colorder, SCIP_Bool *infeasible, int *nfixedvars)
Definition: symmetry_orbitopal.c:1490
static SCIP_RETCODE getRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *node, int **roworder, int *nselrows)
Definition: symmetry_orbitopal.c:567
static SCIP_DECL_EVENTEXEC(eventExecNodeBranched)
Definition: symmetry_orbitopal.c:727
static SCIP_RETCODE populateRootedPathColumnOrder(ORBITOPEDATA *orbidata, SCIP_NODE *node, SCIP_NODE **rootedpath, int *colorder, int *colorderinv)
Definition: symmetry_orbitopal.c:644
static SCIP_RETCODE freeOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA **orbidata)
Definition: symmetry_orbitopal.c:1032
static int debugGetArrayHash(int *array, int len)
Definition: symmetry_orbitopal.c:1438
static void freeColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **colorder, int **colorderinv)
Definition: symmetry_orbitopal.c:1261
SCIP_RETCODE SCIPincludeOrbitopalReduction(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
Definition: symmetry_orbitopal.c:2314
static SCIP_DECL_HASHGETKEY(hashGetKeyBnbnodeinfo)
Definition: symmetry_orbitopal.c:216
SCIP_RETCODE SCIPorbitopalReductionFree(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
Definition: symmetry_orbitopal.c:2294
SCIP_RETCODE SCIPorbitopalReductionReset(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2267
static SCIP_RETCODE propagateOrbitope(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_Bool *infeasible, int *nfixedvars)
Definition: symmetry_orbitopal.c:2028
SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
Definition: symmetry_orbitopal.c:2232
static SCIP_Bool rowIsBranchRow(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA *orbidata, int rowid)
Definition: symmetry_orbitopal.c:989
SCIP_RETCODE SCIPorbitopalReductionPropagate(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_orbitopal.c:2170
static void freeRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **roworder)
Definition: symmetry_orbitopal.c:534
SCIP_RETCODE SCIPorbitopalReductionGetStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
Definition: symmetry_orbitopal.c:2119
static SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn(SCIP *scip, ORBITOPEDATA *orbidata, int *colorder, int *colorderinv, SCIP_VAR *var, COLSWAP *thiscolswap)
Definition: symmetry_orbitopal.c:297
static SCIP_DECL_HASHKEYVAL(hashKeyValBnbnodeinfo)
Definition: symmetry_orbitopal.c:232
static SCIP_RETCODE addOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
Definition: symmetry_orbitopal.c:1106
SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2138
static SCIP_Bool testColumnsAreSymmetricallyEquivalent(SCIP *scip, ORBITOPEDATA *orbidata, int col1, int col2)
Definition: symmetry_orbitopal.c:247
static SCIP_RETCODE getColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *eventnode, int **colorder, int **colorderinv)
Definition: symmetry_orbitopal.c:1293
static SCIP_Bool vartypeIsBranchRowType(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_VARTYPE vartype)
Definition: symmetry_orbitopal.c:165
static SCIP_DECL_HASHKEYEQ(hashKeyEqBnbnodeinfo)
Definition: symmetry_orbitopal.c:223
SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2360
static int getArrayEntryOrIndex(int *arr, int idx)
Definition: symmetry_orbitopal.c:521
static void assertIsOrbitopeMatrix(SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int *colorder, SCIP_Real *matrix, int nrows, int ncols, int *infinitesimal, SCIP_Bool addinfinitesimals)
Definition: symmetry_orbitopal.c:1353
struct SCIP_OrbitopalReductionData SCIP_ORBITOPALREDDATA
Definition: symmetry_orbitopal.h:69
type definitions for symmetry computations
type definitions for problem variables
Definition: struct_var.h:161