presol_gateextraction.c File Reference

Detailed Description

gateextraction presolver

Author

Michael Winkler

Definition in file presol_gateextraction.c.

#include <assert.h>
#include <string.h>
#include "scip/presol_gateextraction.h"
#include "scip/cons_setppc.h"
#include "scip/cons_logicor.h"
#include "scip/cons_and.h"

Go to the source code of this file.

Macros
#define	PRESOL_NAME   "gateextraction"
#define	PRESOL_DESC   "presolver extracting gate(and)-constraints"
#define	PRESOL_PRIORITY   1000000
#define	PRESOL_MAXROUNDS   -1
#define	PRESOL_DELAY   TRUE
#define	HASHSIZE_LOGICORCONS   131101
#define	HASHSIZE_SETPPCCONS   131101
#define	DEFAULT_ONLYSETPART   FALSE
#define	DEFAULT_SEARCHEQUATIONS   TRUE
#define	DEFAULT_SORTING   1
#define	HASHTABLESIZE_FACTOR   5

Typedefs
typedef struct HashData	HASHDATA

Functions
static	SCIP_DECL_HASHKEYEQ (hashdataKeyEqCons)
static	SCIP_DECL_HASHKEYVAL (hashdataKeyValCons)
static	SCIP_DECL_HASHKEYEQ (setppcHashdataKeyEqCons)
static	SCIP_DECL_HASHKEYVAL (setppcHashdataKeyValCons)
static void	presoldataInit (SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE	presoldataInitHashtables (SCIP *scip, SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE	createPresoldata (SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_CONS **setppcs, int nsetppcs, SCIP_CONS **logicors, int nlogicors)
static SCIP_RETCODE	cleanupHashDatas (SCIP *scip, SCIP_PRESOLDATA *presoldata)
static SCIP_RETCODE	correctPresoldata (SCIP *scip, SCIP_PRESOLDATA *presoldata, SCIP_CONS **setppcs, int nsetppcs, SCIP_CONS **logicors, int nlogicors)
static SCIP_RETCODE	extractGates (SCIP *scip, SCIP_PRESOLDATA *presoldata, int pos, SCIP_HASHMAP *varmap, SCIP_CONS **gateconss, SCIP_VAR **activevars, SCIP_VAR **posresultants, HASHDATA *hashdata, int *ndelconss, int *naddconss)
static	SCIP_DECL_PRESOLCOPY (presolCopyGateextraction)
static	SCIP_DECL_PRESOLFREE (presolFreeGateextraction)
static	SCIP_DECL_PRESOLEXIT (presolExitGateextraction)
static	SCIP_DECL_PRESOLINITPRE (presolInitpreGateextraction)
static	SCIP_DECL_PRESOLEXITPRE (presolExitpreGateextraction)
static	SCIP_DECL_PRESOLEXEC (presolExecGateextraction)
SCIP_RETCODE	SCIPincludePresolGateextraction (SCIP *scip)

Macro Definition Documentation

#define PRESOL_NAME   "gateextraction"

Definition at line 32 of file presol_gateextraction.c.

Referenced by SCIP_DECL_PRESOLCOPY(), SCIP_DECL_PRESOLEXEC(), and SCIPincludePresolGateextraction().

#define PRESOL_DESC   "presolver extracting gate(and)-constraints"

Definition at line 33 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define PRESOL_PRIORITY   1000000

priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators

Definition at line 34 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 35 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define PRESOL_DELAY   TRUE

should presolver be delayed, if other presolvers found reductions?

Definition at line 36 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define HASHSIZE_LOGICORCONS   131101

minimal size of hash table in logicor constraint tables

Definition at line 38 of file presol_gateextraction.c.

Referenced by presoldataInitHashtables().

#define HASHSIZE_SETPPCCONS   131101

minimal size of hash table in setppc constraint tables

Definition at line 39 of file presol_gateextraction.c.

Referenced by presoldataInitHashtables().

#define DEFAULT_ONLYSETPART   FALSE

should only set-partitioning constraints be extracted and no and-constraints

Definition at line 41 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define DEFAULT_SEARCHEQUATIONS   TRUE

should we try to extract set-partitioning constraint out of one logicor and one corresponding set-packing constraint

Definition at line 42 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define DEFAULT_SORTING   1

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)

Definition at line 45 of file presol_gateextraction.c.

Referenced by SCIPincludePresolGateextraction().

#define HASHTABLESIZE_FACTOR   5

Definition at line 1262 of file presol_gateextraction.c.

Referenced by SCIP_DECL_PRESOLEXEC().

Typedef Documentation

typedef struct HashData HASHDATA

Definition at line 89 of file presol_gateextraction.c.

Function Documentation

static SCIP_DECL_HASHKEYEQ ( hashdataKeyEqCons  )

static

returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer

Definition at line 133 of file presol_gateextraction.c.

References HashData::cons, FALSE, NULL, HashData::nvars, SCIPvarCompare(), TRUE, and HashData::vars.

static SCIP_DECL_HASHKEYVAL ( hashdataKeyValCons  )

static

returns the hash value of the key

Definition at line 175 of file presol_gateextraction.c.

References NULL, HashData::nvars, SCIPvarGetIndex(), and HashData::vars.

static SCIP_DECL_HASHKEYEQ ( setppcHashdataKeyEqCons  )

static

returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer

Definition at line 194 of file presol_gateextraction.c.

References HashData::cons, FALSE, NULL, HashData::nvars, SCIPvarCompare(), TRUE, and HashData::vars.

static SCIP_DECL_HASHKEYVAL ( setppcHashdataKeyValCons  )

static

returns the hash value of the key

Definition at line 239 of file presol_gateextraction.c.

References NULL, HashData::nvars, SCIPvarGetIndex(), and HashData::vars.

static void presoldataInit ( SCIP_PRESOLDATA *  presoldata )

static

initialize gateextraction presolver data

Parameters

presoldata

data object of presolver

Definition at line 263 of file presol_gateextraction.c.

References FALSE, and NULL.

Referenced by SCIPincludePresolGateextraction().

static SCIP_RETCODE presoldataInitHashtables ( SCIP *  scip, SCIP_PRESOLDATA *  presoldata  )

static

initialize gateextraction hashtables

Parameters

scip	SCIP data structure
presoldata	data object of presolver

Definition at line 289 of file presol_gateextraction.c.

References FALSE, HASHSIZE_LOGICORCONS, HASHSIZE_SETPPCCONS, NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), and SCIPhashtableCreate().

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE createPresoldata ( SCIP *  scip, SCIP_PRESOLDATA *  presoldata, SCIP_CONS **  setppcs, int  nsetppcs, SCIP_CONS **  logicors, int  nlogicors  )

static

create useful set-packing information by adding new set-packing constraints with two variables

Parameters

scip	SCIP data structure
presoldata	data object of presolver
setppcs	active setppc constraints
nsetppcs	number of active setppc constraints
logicors	active logicor constraints
nlogicors	number of active logicor constraints

Definition at line 323 of file presol_gateextraction.c.

References MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureCons(), SCIPcaptureVar(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetBinvarRepresentative(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashtableInsert(), SCIPvarGetIndex(), SCIPvarGetStatus(), and TRUE.

Referenced by correctPresoldata(), and SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE cleanupHashDatas ( SCIP *  scip, SCIP_PRESOLDATA *  presoldata  )

static

remove old setppchashdatas objects, so that the allocated memory will stay low

Parameters

scip	SCIP data structure
presoldata	data object of presolver

Definition at line 473 of file presol_gateextraction.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPfreeBlockMemoryArray, SCIPgetBinvarRepresentative(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPvarGetStatus(), and TRUE.

Referenced by correctPresoldata(), and SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE correctPresoldata ( SCIP *  scip, SCIP_PRESOLDATA *  presoldata, SCIP_CONS **  setppcs, int  nsetppcs, SCIP_CONS **  logicors, int  nlogicors  )

static

refresh useful set-packing information, delete redundant constraints and add new constraints

Parameters

scip	SCIP data structure
presoldata	data object of presolver
setppcs	active setppc constraints
nsetppcs	number of active setppc constraints
logicors	active setppc constraints
nlogicors	number of active setppc constraints

Definition at line 575 of file presol_gateextraction.c.

References cleanupHashDatas(), createPresoldata(), NULL, SCIP_Bool, SCIP_CALL, SCIP_NOMEMORY, SCIP_OKAY, SCIP_SETPPCTYPE_PACKING, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPcalcMemGrowSize(), SCIPcaptureCons(), SCIPcaptureVar(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPgetBinvarRepresentative(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRemoveAll(), SCIPreallocBlockMemoryArray, SCIPreleaseCons(), SCIPvarGetIndex(), SCIPvarGetStatus(), and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_RETCODE extractGates ( SCIP *  scip, SCIP_PRESOLDATA *  presoldata, int  pos, SCIP_HASHMAP *  varmap, SCIP_CONS **  gateconss, SCIP_VAR **  activevars, SCIP_VAR **  posresultants, HASHDATA *  hashdata, int *  ndelconss, int *  naddconss  )

static

extract and-constraints and set-partitioning constraints

Parameters

scip	SCIP data structure
presoldata	data object of presolver
pos	position of logicor in usefullogicor array to presolve
varmap	variable map mapping inactive variables to their active representation
gateconss	allocated memory for all gate-constraints
activevars	allocated memory for active variables
posresultants	allocated memory for all possible resultant variables
hashdata	allocated memory for a hashdata object
ndelconss	pointer to store number of deleted constraints
naddconss	pointer to store number of added constraints

Definition at line 792 of file presol_gateextraction.c.

References HashData::cons, NULL, HashData::nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsAnd(), SCIPcreateConsSetpart(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetBinvarRepresentative(), SCIPgetNegatedVar(), SCIPgetNVarsLogicor(), SCIPgetVarsLogicor(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPreleaseCons(), SCIPsnprintf(), SCIPsortPtr(), SCIPvarCompare(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetNegatedVar(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), and HashData::vars.

Referenced by SCIP_DECL_PRESOLEXEC().

static SCIP_DECL_PRESOLCOPY ( presolCopyGateextraction  )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 1127 of file presol_gateextraction.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePresolGateextraction(), and SCIPpresolGetName().

static SCIP_DECL_PRESOLFREE ( presolFreeGateextraction  )

static

destructor of presolver to free user data (called when SCIP is exiting)

Definition at line 1142 of file presol_gateextraction.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPhashtableFree(), SCIPpresolGetData(), and SCIPpresolSetData().

static SCIP_DECL_PRESOLEXIT ( presolExitGateextraction  )

static

deinitialization method of presolver (called before transformed problem is freed)

Definition at line 1169 of file presol_gateextraction.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashtableExists(), SCIPhashtableRemove(), SCIPhashtableRemoveAll(), SCIPpresolGetData(), SCIPreleaseCons(), and SCIPreleaseVar().

static SCIP_DECL_PRESOLINITPRE ( presolInitpreGateextraction  )

static

presolving initialization method of presolver (called when presolving is about to begin)

Definition at line 1248 of file presol_gateextraction.c.

References SCIP_OKAY.

static SCIP_DECL_PRESOLEXITPRE ( presolExitpreGateextraction  )

static

presolving deinitialization method of presolver (called after presolving has been finished)

Definition at line 1256 of file presol_gateextraction.c.

References SCIP_OKAY.

static SCIP_DECL_PRESOLEXEC ( presolExecGateextraction  )

static

execution method of presolver

Definition at line 1266 of file presol_gateextraction.c.

References cleanupHashDatas(), HashData::cons, correctPresoldata(), createPresoldata(), extractGates(), FALSE, HASHTABLESIZE_FACTOR, MAX, NULL, HashData::nvars, PRESOL_NAME, presoldataInitHashtables(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcaptureCons(), SCIPconsGetHdlr(), SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpart(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPdelCons(), SCIPduplicateBlockMemoryArray, SCIPduplicateBufferArray, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPgetBinvarRepresentative(), SCIPgetBoolParam(), SCIPgetCapacityKnapsack(), SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsKnapsack(), SCIPgetVarsLogicor(), SCIPgetVarsSetppc(), SCIPgetWeightsKnapsack(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisParamFixed(), SCIPisStopped(), SCIPpresolGetData(), SCIPpresolGetName(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsetConsChecked(), SCIPsetConsDynamic(), SCIPsetConsEnforced(), SCIPsetConsInitial(), SCIPsetConsLocal(), SCIPsetConsModifiable(), SCIPsetConsPropagated(), SCIPsetConsRemovable(), SCIPsetConsSeparated(), SCIPsetConsStickingAtNode(), SCIPsnprintf(), SCIPsortDownIntPtr(), SCIPsortIntPtr(), SCIPsortPtr(), SCIPunfixParam(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPwarningMessage(), TRUE, and HashData::vars.

SCIP_RETCODE SCIPincludePresolGateextraction

(

SCIP *

scip

)

creates the gateextraction presolver and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1786 of file presol_gateextraction.c.

References DEFAULT_ONLYSETPART, DEFAULT_SEARCHEQUATIONS, DEFAULT_SORTING, NULL, PRESOL_DELAY, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, presoldataInit(), SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludePresolBasic(), SCIPsetPresolCopy(), SCIPsetPresolExit(), SCIPsetPresolExitpre(), SCIPsetPresolFree(), SCIPsetPresolInitpre(), and TRUE.

Referenced by SCIP_DECL_PRESOLCOPY(), and SCIPincludeDefaultPlugins().