114#define SYMHDLR_NAME "orbitopalreduction"
117#define EVENTHDLR_NAME "symmetry_orbitopal_eventhdlr"
118#define EVENTHDLR_DESC "event handler for maintaining the branch-and-bound tree"
119#define DEFAULT_COLUMNORDERING SCIP_COLUMNORDERING_MEDIAN
145struct SCIP_OrbitopalReductionData
154 SCIP_Bool conshdlr_nonlinear_checked;
235 return (
unsigned int)
nodeinfo->nodenumber;
371 for (
c = 0;
c < ncols; ++
c)
422#ifdef SCIP_MORE_DEBUG
425 for (
c = 0;
c < ncols; ++
c)
431#ifdef SCIP_MORE_DEBUG
444#ifdef SCIP_MORE_DEBUG
449#ifdef SCIP_MORE_DEBUG
509 SCIPdebugMessage(
"Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n",
620 for (
j = 0;
j < (*nselrows) - 1; ++
j)
633 for (
i = 0;
i < (*nselrows) / 2; ++
i)
637 (*roworder)[
i] = (*roworder)[(*nselrows) - 1 -
i];
638 (*roworder)[(*nselrows) - 1 -
i] =
j;
670 while ( node !=
NULL )
775 for (
c = 0;
c < nchildren; ++
c)
782 for (
i = 0;
i < nboundchgs; ++
i)
866 if (
rowid == roworder[
j] )
1051 assert( (*orbidata)->nrows > 0 );
1052 assert( (*orbidata)->ncols > 0 );
1053 assert( (*orbidata)->nrows * (*orbidata)->ncols > 0 );
1065 for (
i = 0;
i < nentries; ++
i)
1093 nelem = (*orbidata)->nrows * (*orbidata)->ncols;
1151 orbidata->rowordering = rowordering;
1170 if (
colid == ncols )
1329 for (
i = 0;
i < ncols; ++
i)
1333 for (
i = 0;
i < ncols; ++
i)
1447 unsigned int hash = 0;
1452 for (
i = 0;
i < len;
i++)
1462#ifdef SCIP_MORE_DEBUG
1478 for (row = 0; row <
nrows; ++row)
1481 for (col = 0; col < ncols; ++col)
1499 SCIP_Bool* infeasible,
1531 *infeasible =
FALSE;
1542#ifdef SCIP_MORE_DEBUG
1550 for (
k = 0;
k < ncols; ++
k)
1559 for (
k = 0;
k < ncols; ++
k)
1611 assert( (
i + 1) % ncols > 0 );
1910#ifdef SCIP_MORE_DEBUG
1947 SCIPdebugMessage(
"Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1965 SCIPdebugMessage(
"Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1990 SCIPdebugMessage(
"Detected infeasibility restricting variable LB %12s (%3d,%3d) to %5.2f\n",
2010 SCIPdebugMessage(
"Detected infeasibility restricting variable UB %12s (%3d,%3d) to %5.2f\n",
2034 SCIP_Bool* infeasible,
2050 *infeasible =
FALSE;
2108#ifdef SCIP_MORE_DEBUG
2158 " orbitopal reduction: %4d components: ",
orbireddata->norbitopes);
2176 SCIP_Bool* infeasible,
2192 *infeasible =
FALSE;
2222 SCIPdebugMessage(
"Detected infeasibility during orbitopal reduction for orbitope %d\n",
c);
2335 "The column ordering variant, respects enum SCIP_ColumnOrdering.",
2343 (*orbireddata)->eventhdlr = eventhdlr;
2346 (*orbireddata)->orbitopes =
NULL;
2347 (*orbireddata)->norbitopes = 0;
2348 (*orbireddata)->maxnorbitopes = 0;
2351 (*orbireddata)->conshdlr_nonlinear =
NULL;
2352 (*orbireddata)->conshdlr_nonlinear_checked =
FALSE;
2355 (*orbireddata)->nred = 0;
2356 (*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_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_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
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)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
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)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_NODE * SCIPeventGetNode(SCIP_EVENT *event)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(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 SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
void SCIPnodeGetNDomchg(SCIP_NODE *node, int *nbranchings, int *nconsprop, int *nprop)
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
int SCIPnodeGetDepth(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 SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
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_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
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_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
void SCIPsortInd(int *indarray, 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_HASHMAP * rowindexmap
SCIP_Longint lastnodenumber
SCIP_HASHTABLE * nodeinfos
SCIP_ROWORDERING rowordering
SCIP_HASHMAP * colindexmap
SCIP_COLUMNORDERING columnordering
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)
static SCIP_RETCODE getRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *node, int **roworder, int *nselrows)
static SCIP_RETCODE populateRootedPathColumnOrder(ORBITOPEDATA *orbidata, SCIP_NODE *node, SCIP_NODE **rootedpath, int *colorder, int *colorderinv)
static SCIP_RETCODE freeOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA **orbidata)
static int debugGetArrayHash(int *array, int len)
static void freeColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **colorder, int **colorderinv)
SCIP_RETCODE SCIPincludeOrbitopalReduction(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionFree(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionReset(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
static SCIP_RETCODE propagateOrbitope(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_Bool *infeasible, int *nfixedvars)
SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
static SCIP_Bool rowIsBranchRow(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA *orbidata, int rowid)
SCIP_RETCODE SCIPorbitopalReductionPropagate(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
static void freeRowOrder(SCIP *scip, ORBITOPEDATA *orbidata, int **roworder)
SCIP_RETCODE SCIPorbitopalReductionGetStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
static SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn(SCIP *scip, ORBITOPEDATA *orbidata, int *colorder, int *colorderinv, SCIP_VAR *var, COLSWAP *thiscolswap)
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)
SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
static SCIP_Bool testColumnsAreSymmetricallyEquivalent(SCIP *scip, ORBITOPEDATA *orbidata, int col1, int col2)
static SCIP_RETCODE getColumnOrder(SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *eventnode, int **colorder, int **colorderinv)
static SCIP_Bool vartypeIsBranchRowType(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_VARTYPE vartype)
SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(SCIP_ORBITOPALREDDATA *orbireddata)
static int getArrayEntryOrIndex(int *arr, int idx)
#define DEFAULT_COLUMNORDERING
static void assertIsOrbitopeMatrix(SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int *colorder, SCIP_Real *matrix, int nrows, int ncols, int *infinitesimal, SCIP_Bool addinfinitesimals)
@ SCIP_COLUMNORDERING_CENTRE
@ SCIP_COLUMNORDERING_FIRST
@ SCIP_COLUMNORDERING_NONE
@ SCIP_COLUMNORDERING_LAST
@ SCIP_COLUMNORDERING_MEDIAN
enum SCIP_ColumnOrdering SCIP_COLUMNORDERING
@ SCIP_ROWORDERING_BRANCHING
struct SCIP_OrbitopalReductionData SCIP_ORBITOPALREDDATA
enum SCIP_RowOrdering SCIP_ROWORDERING
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_NODEBRANCHED
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
enum SCIP_Retcode SCIP_RETCODE
type definitions for symmetry computations
type definitions for problem variables
@ SCIP_VARTYPE_CONTINUOUS
@ SCIP_BOUNDCHGTYPE_BRANCHING
enum SCIP_Vartype SCIP_VARTYPE