54#define PRESOL_NAME "gateextraction"
55#define PRESOL_DESC "presolver extracting gate(and)-constraints"
56#define PRESOL_PRIORITY 1000000
57#define PRESOL_MAXROUNDS -1
58#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE
60#define HASHSIZE_LOGICORCONS 500
61#define HASHSIZE_SETPPCCONS 500
63#define DEFAULT_ONLYSETPART FALSE
64#define DEFAULT_SEARCHEQUATIONS TRUE
67#define DEFAULT_SORTING 1
115struct SCIP_PresolData
124 int nsetppchashdatas;
125 int ssetppchashdatas;
127 int firstchangedlogicor;
132 SCIP_Bool usefulsetppcexist;
133 SCIP_Bool usefullogicorexist;
134 SCIP_Bool newsetppchashdatas;
137 SCIP_Bool initialized;
138 SCIP_Bool onlysetpart;
139 SCIP_Bool searchequations;
176 for( v = 1; v >= 0; --v )
240 for( v =
hashdata1->nvars - 1; v >= 0; --v )
282 presoldata->usefullogicor =
NULL;
283 presoldata->nusefullogicor = 0;
284 presoldata->susefullogicor = 0;
285 presoldata->firstchangedlogicor = -1;
286 presoldata->maxnvarslogicor = 0;;
287 presoldata->nsetppchashdatas = 0;
288 presoldata->ssetppchashdatas = 0;
289 presoldata->ngates = 0;
290 presoldata->usefulsetppcexist =
FALSE;
291 presoldata->usefullogicorexist =
FALSE;
292 presoldata->newsetppchashdatas =
FALSE;
293 presoldata->initialized =
FALSE;
295 presoldata->hashdatatable =
NULL;
296 presoldata->setppchashtable =
NULL;
297 presoldata->logicorhashtable =
NULL;
310 assert(presoldata->nusefullogicor == 0);
311 assert(presoldata->susefullogicor == 0);
312 assert(presoldata->nsetppchashdatas == 0);
313 assert(presoldata->ssetppchashdatas == 0);
314 assert(presoldata->firstchangedlogicor == -1);
315 assert(presoldata->ngates == 0);
362 presoldata->initialized =
TRUE;
369 if( !presoldata->usefulsetppcexist )
392 presoldata->usefulsetppcexist =
TRUE;
416 presoldata->setppchashdatas[
h].nvars = 2;
426 presoldata->setppchashdatas[
h].vars[0] = presoldata->setppchashdatas[
h].vars[1];
427 presoldata->setppchashdatas[
h].vars[1] =
tmp;
437 presoldata->nsetppchashdatas =
h;
439 if( presoldata->nsetppchashdatas > 0 )
440 presoldata->newsetppchashdatas =
TRUE;
446 if( !presoldata->usefullogicorexist )
471 presoldata->firstchangedlogicor = 0;
472 presoldata->usefullogicorexist =
TRUE;
496 if( presoldata->usefulsetppcexist )
500 assert(presoldata->setppchashdatas !=
NULL || presoldata->nsetppchashdatas == 0);
502 for(
c = presoldata->nsetppchashdatas - 1;
c >= 0; --
c )
506 assert(presoldata->setppchashdatas[
c].cons !=
NULL);
523 || presoldata->setppchashdatas[
c].vars[0] !=
vars[0] || presoldata->setppchashdatas[
c].vars[1] !=
vars[1] )
555 presoldata->setppchashdatas[
c].cons = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].cons;
556 presoldata->setppchashdatas[
c].vars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].vars;
557 presoldata->setppchashdatas[
c].nvars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].nvars;
564 --(presoldata->nsetppchashdatas);
569 for(
c = presoldata->nsetppchashdatas - 1;
c >= 0; --
c )
571 assert(presoldata->setppchashdatas[
c].nvars == 2);
572 assert(presoldata->setppchashdatas[
c].vars !=
NULL);
573 assert(presoldata->setppchashdatas[
c].vars[0] !=
NULL);
574 assert(presoldata->setppchashdatas[
c].vars[1] !=
NULL);
575 assert(presoldata->setppchashdatas[
c].cons !=
NULL);
606 assert(presoldata->initialized);
611 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
634 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
658 if( presoldata->nsetppchashdatas == presoldata->ssetppchashdatas )
673 presoldata->ssetppchashdatas =
newsize;
676 for(
d = presoldata->nsetppchashdatas - 1;
d >= 0; --
d )
699 presoldata->setppchashdatas[presoldata->nsetppchashdatas].nvars = 2;
706 if(
SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) >
SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) )
708 SCIP_VAR*
tmp = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0];
709 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0] = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1];
710 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1] =
tmp;
713 presoldata->setppchashdatas[presoldata->nsetppchashdatas].cons =
setppcs[
c];
718 ++(presoldata->nsetppchashdatas);
725 presoldata->newsetppchashdatas =
TRUE;
729 while( presoldata->nusefullogicor > 0 && !
SCIPconsIsActive(presoldata->usefullogicor[presoldata->nusefullogicor - 1]) )
734 --(presoldata->nusefullogicor);
738 for(
c = presoldata->nusefullogicor - 1;
c >= 0; --
c )
749 presoldata->usefullogicor[
c] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
750 --(presoldata->nusefullogicor);
754 presoldata->firstchangedlogicor = presoldata->nusefullogicor;
755 assert(presoldata->firstchangedlogicor >= 0);
768 if( presoldata->nusefullogicor == presoldata->susefullogicor )
779 presoldata->susefullogicor =
newsize;
786 presoldata->usefullogicor[presoldata->nusefullogicor] =
logicors[
c];
787 ++(presoldata->nusefullogicor);
839 logicor = presoldata->usefullogicor[pos];
915 presoldata->usefullogicor[pos] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
916 --(presoldata->nusefullogicor);
1006 SCIP_Bool modifiable;
1008 SCIP_Bool removable;
1009 SCIP_Bool stickingatnode;
1029 SCIPdebugMsg(
scip,
"Following constraints form a set-partitioning constraint.\n");
1064 assert(!presoldata->onlysetpart);
1083 initial, separate, enforce, check,
propagate,
1084 local, modifiable, dynamic, removable, stickingatnode) );
1091 ++(presoldata->ngates);
1107 initial, separate, enforce, check,
propagate,
1108 local, modifiable, dynamic, removable, stickingatnode) );
1115 ++(presoldata->ngates);
1158 if( presoldata->hashdatatable !=
NULL )
1161 assert(presoldata->logicorhashtable !=
NULL);
1187 for(
c = presoldata->nusefullogicor - 1;
c >= 0; --
c )
1192 if( presoldata->usefullogicorexist )
1197 if( presoldata->usefulsetppcexist )
1199 assert(presoldata->setppchashdatas !=
NULL || presoldata->nsetppchashdatas == 0);
1200 for(
c = presoldata->nsetppchashdatas - 1;
c >= 0; --
c )
1202 assert(presoldata->setppchashdatas[
c].cons !=
NULL);
1203 assert(presoldata->setppchashdatas[
c].vars !=
NULL);
1226 if( presoldata->hashdatatable !=
NULL )
1229 assert(presoldata->logicorhashtable !=
NULL);
1237 presoldata->nusefullogicor = 0;
1238 presoldata->susefullogicor = 0;
1239 presoldata->nsetppchashdatas = 0;
1240 presoldata->ssetppchashdatas = 0;
1241 presoldata->firstchangedlogicor = -1;
1242 presoldata->ngates = 0;
1243 presoldata->usefullogicorexist =
FALSE;
1244 presoldata->usefulsetppcexist =
FALSE;
1245 presoldata->newsetppchashdatas =
FALSE;
1246 presoldata->initialized =
FALSE;
1311 SCIP_Longint capacity;
1332 if(
nvars > 1 && capacity ==
nvars - 1 && vals[0] == capacity && vals[1] == 1 )
1334 printf(
"possible knapsack for gate extraction\n");
1366 if( !presoldata->searchequations )
1377 assert(presoldata->onlysetpart);
1386 SCIPwarningMessage(
scip,
"Gate-presolving is the 'counterpart' of linearizing all and-constraints, so enabling both presolving steps simultaneously does not make sense.\n");
1399 if( presoldata->hashdatatable ==
NULL )
1405 assert(presoldata->logicorhashtable !=
NULL);
1407 presoldata->newsetppchashdatas =
FALSE;
1409 if( !presoldata->initialized )
1421 assert(presoldata->initialized);
1423 if( presoldata->nusefullogicor == 0 )
1428 if( presoldata->sorting != 0 )
1434 for(
c = presoldata->nusefullogicor - 1;
c >= 0; --
c )
1439 if( presoldata->sorting == -1 )
1467 int nsetppchashdatas;
1479 size = presoldata->maxnvarslogicor;
1490 nsetppchashdatas = 0;
1551 setppchashdatas[nsetppchashdatas]->
cons =
setppc;
1615 SCIP_Bool modifiable;
1617 SCIP_Bool removable;
1618 SCIP_Bool stickingatnode;
1648 SCIPdebugMsg(
scip,
"Following logicor is redundant to the set-partitioning constraint.\n");
1659 SCIPdebugMsg(
scip,
"Following logicor and set-packing constraints form a set-partitioning constraint.\n");
1666 initial, separate, enforce, check,
propagate,
1667 local, modifiable, dynamic, removable, stickingatnode) );
1674 ++(presoldata->ngates);
1691 for(
d = nsetppchashdatas - 1;
d >= 0; --
d )
1710 if( presoldata->nsetppchashdatas == 0 || (presoldata->firstchangedlogicor == presoldata->nusefullogicor && !presoldata->newsetppchashdatas) )
1717 assert(presoldata->nusefullogicor > 0);
1718 assert(presoldata->firstchangedlogicor >= 0);
1719 assert(presoldata->nsetppchashdatas > 0);
1730 if( presoldata->newsetppchashdatas )
1733 endloop =
MAX(presoldata->firstchangedlogicor, 0);
1735 assert(presoldata->maxnvarslogicor >= 3);
1813 "should we only try to extract set-partitioning constraints and no and-constraints",
1819 "should we try to extract set-partitioning constraint out of one logicor and one corresponding set-packing constraint",
1825 "order logicor contraints to extract big-gates before smaller ones (-1), do not order them (0) or order them to extract smaller gates at first (1)",
Constraint handler for AND constraints, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
@ SCIP_SETPPCTYPE_COVERING
@ SCIP_SETPPCTYPE_PACKING
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
#define SCIPhashFour(a, b, c, d)
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 SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
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_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConsStickingAtNode(SCIP *scip, SCIP_CONS *cons, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConsModifiable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool modifiable)
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
SCIP_RETCODE SCIPsetConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_Bool local)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool propagate
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHKEYVAL(x)
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
#define SCIP_DECL_PRESOLINITPRE(x)
#define SCIP_DECL_PRESOLEXITPRE(x)
#define SCIP_DECL_PRESOLEXIT(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_MULTAGGR