Scippy

SCIP

Solving Constraint Integer Programs

presol_gateextraction.c File Reference

Detailed Description

gateextraction presolver

Author
Michael Winkler

Definition in file presol_gateextraction.c.

#include "blockmemshell/memory.h"
#include "scip/cons_and.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/presol_gateextraction.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_prob.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  HashData
 

Macros

#define PRESOL_NAME   "gateextraction"
 
#define PRESOL_DESC   "presolver extracting gate(and)-constraints"
 
#define PRESOL_PRIORITY   1000000
 
#define PRESOL_MAXROUNDS   -1
 
#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
 
#define HASHSIZE_LOGICORCONS   500
 
#define HASHSIZE_SETPPCCONS   500
 
#define DEFAULT_ONLYSETPART   FALSE
 
#define DEFAULT_SEARCHEQUATIONS   TRUE
 
#define DEFAULT_SORTING   1
 

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

◆ PRESOL_NAME

#define PRESOL_NAME   "gateextraction"

Definition at line 44 of file presol_gateextraction.c.

◆ PRESOL_DESC

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

Definition at line 45 of file presol_gateextraction.c.

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   1000000

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

Definition at line 46 of file presol_gateextraction.c.

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   -1

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

Definition at line 47 of file presol_gateextraction.c.

◆ PRESOL_TIMING

#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */

Definition at line 48 of file presol_gateextraction.c.

◆ HASHSIZE_LOGICORCONS

#define HASHSIZE_LOGICORCONS   500

minimal size of hash table in logicor constraint tables

Definition at line 50 of file presol_gateextraction.c.

Referenced by presoldataInitHashtables().

◆ HASHSIZE_SETPPCCONS

#define HASHSIZE_SETPPCCONS   500

minimal size of hash table in setppc constraint tables

Definition at line 51 of file presol_gateextraction.c.

Referenced by presoldataInitHashtables().

◆ DEFAULT_ONLYSETPART

#define DEFAULT_ONLYSETPART   FALSE

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

Definition at line 53 of file presol_gateextraction.c.

◆ DEFAULT_SEARCHEQUATIONS

#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 54 of file presol_gateextraction.c.

◆ DEFAULT_SORTING

#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 59 of file presol_gateextraction.c.

Typedef Documentation

◆ HASHDATA

typedef struct HashData HASHDATA

Definition at line 105 of file presol_gateextraction.c.

Function Documentation

◆ SCIP_DECL_HASHKEYEQ() [1/2]

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 146 of file presol_gateextraction.c.

◆ SCIP_DECL_HASHKEYVAL() [1/2]

static SCIP_DECL_HASHKEYVAL ( hashdataKeyValCons  )
static

returns the hash value of the key

Definition at line 190 of file presol_gateextraction.c.

◆ SCIP_DECL_HASHKEYEQ() [2/2]

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 209 of file presol_gateextraction.c.

◆ SCIP_DECL_HASHKEYVAL() [2/2]

static SCIP_DECL_HASHKEYVAL ( setppcHashdataKeyValCons  )
static

returns the hash value of the key

Definition at line 254 of file presol_gateextraction.c.

◆ presoldataInit()

static void presoldataInit ( SCIP_PRESOLDATA presoldata)
static

initialize gateextraction presolver data

Parameters
presoldatadata object of presolver

Definition at line 270 of file presol_gateextraction.c.

◆ presoldataInitHashtables()

static SCIP_RETCODE presoldataInitHashtables ( SCIP scip,
SCIP_PRESOLDATA presoldata 
)
static

initialize gateextraction hashtables

Parameters
scipSCIP data structure
presoldatadata object of presolver

Definition at line 296 of file presol_gateextraction.c.

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

◆ createPresoldata()

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
scipSCIP data structure
presoldatadata object of presolver
setppcsactive setppc constraints
nsetppcsnumber of active setppc constraints
logicorsactive logicor constraints
nlogicorsnumber of active logicor constraints

Definition at line 333 of file presol_gateextraction.c.

References cleanupHashDatas(), h, 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 presoldataInitHashtables().

◆ cleanupHashDatas()

◆ correctPresoldata()

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
scipSCIP data structure
presoldatadata object of presolver
setppcsactive setppc constraints
nsetppcsnumber of active setppc constraints
logicorsactive setppc constraints
nlogicorsnumber of active setppc constraints

Definition at line 582 of file presol_gateextraction.c.

References cleanupHashDatas(), createPresoldata(), extractGates(), 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 cleanupHashDatas().

◆ extractGates()

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
scipSCIP data structure
presoldatadata object of presolver
posposition of logicor in usefullogicor array to presolve
varmapvariable map mapping inactive variables to their active representation
gateconssallocated memory for all gate-constraints
activevarsallocated memory for active variables
posresultantsallocated memory for all possible resultant variables
hashdataallocated memory for a hashdata object
ndelconsspointer to store number of deleted constraints
naddconsspointer to store number of added constraints

Definition at line 796 of file presol_gateextraction.c.

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

Referenced by correctPresoldata().

◆ SCIP_DECL_PRESOLCOPY()

static SCIP_DECL_PRESOLCOPY ( presolCopyGateextraction  )
static

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

Definition at line 1129 of file presol_gateextraction.c.

Referenced by extractGates().

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeGateextraction  )
static

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

Definition at line 1144 of file presol_gateextraction.c.

◆ SCIP_DECL_PRESOLEXIT()

static SCIP_DECL_PRESOLEXIT ( presolExitGateextraction  )
static

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

Definition at line 1171 of file presol_gateextraction.c.

◆ SCIP_DECL_PRESOLINITPRE()

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.

◆ SCIP_DECL_PRESOLEXITPRE()

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.

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecGateextraction  )
static

execution method of presolver

Definition at line 1264 of file presol_gateextraction.c.