Scippy

SCIP

Solving Constraint Integer Programs

cons_linking.c File Reference

Detailed Description

constraint handler for linking constraints

Author
Stefan Heinz
Jens Schulz

The constraints handler stores linking constraints between an integer variable and an array of binary variables. Such a linking constraint has the form:

intvar = sum_{i=1}^n {vals[i] * binvars[i]}

with the additional side condition that exactly one binary variable has to be one (set partitioning condition).

This constraint can be created only with the integer variable. In this case the binary variables are only created on demand. That is, whenever someone asks for the binary variables. Therefore, such constraints can be used to get a "binary representation" of the domain of the integer variable which will be dynamically created.

Definition in file cons_linking.c.

#include <assert.h>
#include <string.h>
#include <ctype.h>
#include "scip/cons_linear.h"
#include "scip/cons_linking.h"
#include "scip/cons_setppc.h"

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "linking"
 
#define CONSHDLR_DESC   "linking constraint x = sum_{i=1}^{n} c_i*y_i, y1+...+yn = 1, x integer, y's binary"
 
#define EVENTHDLR_NAME   "linking"
 
#define EVENTHDLR_DESC   "event handler for linking constraints"
 
#define CONSHDLR_SEPAPRIORITY   750000
 
#define CONSHDLR_ENFOPRIORITY   -2050000
 
#define CONSHDLR_CHECKPRIORITY   -750000
 
#define CONSHDLR_SEPAFREQ   1
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM
 
#define HASHSIZE_BINVARSCONS   131101
 
#define DEFAULT_LINEARIZE   FALSE
 

Functions

static void * getHashmapKey (SCIP_VAR *var)
 
static void consdataSort (SCIP_CONSDATA *consdata)
 
static SCIP_RETCODE lockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR **binvars, int nbinvars)
 
static SCIP_RETCODE conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
 
static SCIP_RETCODE consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
 
static SCIP_RETCODE catchEvent (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE dropEvent (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE catchAllEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE dropAllEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE consdataLinearize (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata)
 
static SCIP_RETCODE consdataCreateBinvars (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool linearize)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSDATA **consdata, SCIP_VAR *intvar, SCIP_VAR **binvars, int *vals, int nbinvars)
 
static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE analyzeConflict (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *intvar, SCIP_VAR *binvar, SCIP_Bool lbintvar, SCIP_Bool ubintvar)
 
static SCIP_RETCODE consFixInteger (SCIP *scip, SCIP_CONS *cons, int pos, SCIP_Bool *cutoff)
 
static SCIP_RETCODE processIntegerBoundChg (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *mustcheck)
 
static SCIP_RETCODE delCoefPos (SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int pos)
 
static SCIP_RETCODE removeFixedBinvars (SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons)
 
static SCIP_RETCODE tightenedIntvar (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *nchgbds)
 
static SCIP_RETCODE processBinvarFixings (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *addcut, SCIP_Bool *mustcheck)
 
static SCIP_Bool checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
 
static SCIP_RETCODE createRows (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE addCuts (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff)
 
static SCIP_RETCODE separateCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff, SCIP_Bool *separated, int *nchgbds)
 
static SCIP_RETCODE enforcePseudo (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *infeasible, int *nchgbds, SCIP_Bool *solvelp)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyLinking)
 
static SCIP_DECL_CONSFREE (consFreeLinking)
 
static SCIP_DECL_CONSINITPRE (consInitpreLinking)
 
static SCIP_DECL_CONSEXITSOL (consExitsolLinking)
 
static SCIP_DECL_CONSDELETE (consDeleteLinking)
 
static SCIP_DECL_CONSTRANS (consTransLinking)
 
static SCIP_DECL_CONSINITLP (consInitlpLinking)
 
static SCIP_DECL_CONSSEPALP (consSepalpLinking)
 
static SCIP_DECL_CONSSEPASOL (consSepasolLinking)
 
static SCIP_DECL_CONSENFOLP (consEnfolpLinking)
 
static SCIP_DECL_CONSENFOPS (consEnfopsLinking)
 
static SCIP_DECL_CONSCHECK (consCheckLinking)
 
static SCIP_DECL_CONSPROP (consPropLinking)
 
static SCIP_DECL_CONSPRESOL (consPresolLinking)
 
static SCIP_DECL_CONSRESPROP (consRespropLinking)
 
static SCIP_DECL_CONSLOCK (consLockLinking)
 
static SCIP_DECL_CONSENABLE (consEnableLinking)
 
static SCIP_DECL_CONSPRINT (consPrintLinking)
 
static SCIP_DECL_CONSCOPY (consCopyLinking)
 
static SCIP_DECL_CONSPARSE (consParseLinking)
 
static SCIP_DECL_CONSGETVARS (consGetVarsLinking)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsLinking)
 
static SCIP_DECL_EVENTEXEC (eventExecBinvar)
 
SCIP_RETCODE SCIPincludeConshdlrLinking (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsLinking (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *intvar, SCIP_VAR **binvars, int *vals, int nbinvars, 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_RETCODE SCIPcreateConsBasicLinking (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *intvar, SCIP_VAR **binvars, int *vals, int nbinvars)
 
SCIP_Bool SCIPexistsConsLinking (SCIP *scip, SCIP_VAR *intvar)
 
SCIP_CONSSCIPgetConsLinking (SCIP *scip, SCIP_VAR *intvar)
 
SCIP_VARSCIPgetIntvarLinking (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPgetBinvarsLinking (SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
 
int SCIPgetNBinvarsLinking (SCIP *scip, SCIP_CONS *cons)
 
int * SCIPgetValsLinking (SCIP *scip, SCIP_CONS *cons)
 

Macro Definition Documentation

#define CONSHDLR_DESC   "linking constraint x = sum_{i=1}^{n} c_i*y_i, y1+...+yn = 1, x integer, y's binary"

Definition at line 50 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define EVENTHDLR_NAME   "linking"

Definition at line 52 of file cons_linking.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrLinking().

#define EVENTHDLR_DESC   "event handler for linking constraints"

Definition at line 53 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_SEPAPRIORITY   750000

priority of the constraint handler for separation

Definition at line 55 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_ENFOPRIORITY   -2050000

priority of the constraint handler for constraint enforcing

Definition at line 56 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_CHECKPRIORITY   -750000

priority of the constraint handler for checking feasibility

Definition at line 57 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_SEPAFREQ   1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 58 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 59 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 60 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_MAXPREROUNDS   -1

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

Definition at line 61 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 62 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 63 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 64 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask of the constraint handler

Definition at line 66 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

presolving timing of the constraint handler (fast, medium, or exhaustive)

Definition at line 67 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

#define HASHSIZE_BINVARSCONS   131101

minimal size of hash table in linking constraint handler

Definition at line 70 of file cons_linking.c.

Referenced by SCIPcreateConsLinking().

#define DEFAULT_LINEARIZE   FALSE

should the linking constraint be linearize after the binary variable are created

Definition at line 71 of file cons_linking.c.

Referenced by SCIPincludeConshdlrLinking().

Function Documentation

static void* getHashmapKey ( SCIP_VAR var)
static

returns for a given integer variable the corresponding hash map key

Parameters
varvariable to get the hash map key for

Definition at line 109 of file cons_linking.c.

References SCIPvarGetIndex().

Referenced by checkCons(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSTRANS(), SCIPcreateConsLinking(), SCIPexistsConsLinking(), and SCIPgetConsLinking().

static void consdataSort ( SCIP_CONSDATA consdata)
static
Parameters
consdatalinking constraint data

Definition at line 119 of file cons_linking.c.

References SCIPsortIntPtr(), and TRUE.

Referenced by processBinvarFixings(), and processIntegerBoundChg().

static SCIP_RETCODE lockRounding ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR **  binvars,
int  nbinvars 
)
static

installs rounding locks for the binary variables in the given linking constraint

Parameters
scipSCIP data structure
conslinking constraint
binvarsbinary variables
nbinvarsnumber of binary variables

Definition at line 135 of file cons_linking.c.

References SCIP_CALL, SCIP_OKAY, SCIPlockVarCons(), and TRUE.

Referenced by consdataCreateBinvars().

static SCIP_RETCODE conshdlrdataCreate ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata,
SCIP_EVENTHDLR eventhdlr 
)
static

creates constraint handler data for the linking constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to store the constraint handler data
eventhdlrevent handler

Definition at line 154 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by SCIPincludeConshdlrLinking().

static SCIP_RETCODE conshdlrdataFree ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata 
)
static

frees constraint handler data for linking constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to the constraint handler data

Definition at line 177 of file cons_linking.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, and SCIPhashmapFree().

Referenced by SCIP_DECL_CONSFREE().

static SCIP_RETCODE consdataPrint ( SCIP scip,
SCIP_CONSDATA consdata,
FILE *  file 
)
static

prints linking constraint to file stream

Parameters
scipSCIP data structure
consdatalinking constraint data
fileoutput file (or NULL for standard output)

Definition at line 197 of file cons_linking.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPwriteVarName(), and SCIPwriteVarsLinearsum().

Referenced by SCIP_DECL_CONSPRINT().

static SCIP_RETCODE catchEvent ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

catches events for variable at given position

Parameters
scipSCIP data structure
consdatalinking constraint data
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 251 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPisEQ(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by catchAllEvents().

static SCIP_RETCODE dropEvent ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

drops events for variable at given position

Parameters
scipSCIP data structure
consdatalinking constraint data
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 283 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPdropVarEvent(), SCIPisEQ(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by delCoefPos(), and dropAllEvents().

static SCIP_RETCODE catchAllEvents ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr 
)
static

catches bound change events for all variables in transformed linking constraint

Parameters
scipSCIP data structure
consdatalinking constraint data
eventhdlrevent handler to call for the event processing

Definition at line 314 of file cons_linking.c.

References catchEvent(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by consdataCreate(), and consdataCreateBinvars().

static SCIP_RETCODE dropAllEvents ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr 
)
static

drops bound change events for all variables in transformed linking constraint

Parameters
scipSCIP data structure
consdatalinking constraint data
eventhdlrevent handler to call for the event processing

Definition at line 338 of file cons_linking.c.

References dropEvent(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIP_DECL_CONSDELETE().

static SCIP_RETCODE consdataLinearize ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata 
)
static

linearize the given linking constraint into a set partitioning constraint for the binary variables and a linear constraint for the linking between the integer variable and the binary variables

Parameters
scipSCIP data structure
conslinking constraint
consdatalinking constraint data

Definition at line 363 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsLinear(), SCIPcreateConsSetpart(), SCIPdebugMessage, and SCIPreleaseCons().

Referenced by consdataCreateBinvars(), SCIP_DECL_CONSENABLE(), and SCIP_DECL_CONSINITPRE().

static SCIP_RETCODE consdataCreateBinvars ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr,
SCIP_Bool  linearize 
)
static

creates the binary variables

Parameters
scipSCIP data structure
conslinking constraint
consdatalinking constraint data
eventhdlrevent handler for bound change events on binary variables
linearizeshould the linking constraint be linearized

Definition at line 402 of file cons_linking.c.

References catchAllEvents(), consdataLinearize(), FALSE, lockRounding(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPconvertRealToInt(), SCIPcreateVar(), SCIPdebugMessage, SCIPenableCons(), SCIPisTransformed(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by SCIPgetBinvarsLinking().

static SCIP_RETCODE consdataCreate ( SCIP scip,
SCIP_EVENTHDLR eventhdlr,
SCIP_CONSDATA **  consdata,
SCIP_VAR intvar,
SCIP_VAR **  binvars,
int *  vals,
int  nbinvars 
)
static

creates consdata

Parameters
scipSCIP data structure
eventhdlrevent handler to call for the event processing
consdatapointer to constraint data
intvarinteger variable which is linked
binvarsbinary variables
valscoefficients of the binary variables
nbinvarsnumber of binary starting variables

Definition at line 497 of file cons_linking.c.

References catchAllEvents(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_CONTINUOUS, SCIPallocBlockMemory, SCIPcaptureVar(), SCIPduplicateBlockMemoryArray, SCIPgetTransformedVar(), SCIPgetTransformedVars(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), and SCIPvarGetType().

Referenced by SCIP_DECL_CONSTRANS(), and SCIPcreateConsLinking().

static SCIP_RETCODE consdataFree ( SCIP scip,
SCIP_CONSDATA **  consdata 
)
static

free consdata

Parameters
scipSCIP data structure
consdatapointer to consdata

Definition at line 577 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseRow(), and SCIPreleaseVar().

Referenced by SCIP_DECL_CONSDELETE().

static SCIP_RETCODE analyzeConflict ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR intvar,
SCIP_VAR binvar,
SCIP_Bool  lbintvar,
SCIP_Bool  ubintvar 
)
static

analyzes conflicting assignment on given constraint where reason comes from the integer variable lower or upper bound

Parameters
scipSCIP data structure
conslinking constraint to be processed
intvarinteger variable
binvarbinary variable is the reason
lbintvarlower bound of integer variable is the reason
ubintvarupper bound of integer variable is the reason

Definition at line 628 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPanalyzeConflictCons(), SCIPgetStage(), SCIPinitConflictAnalysis(), SCIPinProbing(), and SCIPisConflictAnalysisApplicable().

Referenced by consFixInteger(), and processIntegerBoundChg().

static SCIP_RETCODE consFixInteger ( SCIP scip,
SCIP_CONS cons,
int  pos,
SCIP_Bool cutoff 
)
static

fix integer variable to the value of the binary variable at pos

Parameters
scipSCIP data structure
conslinking constraint to be processed
posposition of binary variable
cutoffpointer to store TRUE, if the node can be cut off

Definition at line 671 of file cons_linking.c.

References analyzeConflict(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by processBinvarFixings().

static SCIP_RETCODE processIntegerBoundChg ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff,
int *  nchgbds,
SCIP_Bool mustcheck 
)
static

checks constraint for violation from the local bound of the integer variable, applies fixings to the binary variables if possible

Parameters
scipSCIP data structure
conslinking constraint to be processed
cutoffpointer to store TRUE, if the node can be cut off
nchgbdspointer to store the number of changes (foxed) variable bounds
mustcheckpointer to store whether this constraint must be checked for feasibility

Definition at line 728 of file cons_linking.c.

References analyzeConflict(), consdataSort(), CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPconvertRealToInt(), SCIPcreateConsSetpart(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPgetDepth(), SCIPinferBinvarCons(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by enforcePseudo(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPROP(), and separateCons().

static SCIP_RETCODE delCoefPos ( SCIP scip,
SCIP_EVENTHDLR eventhdlr,
SCIP_CONS cons,
int  pos 
)
static

deletes coefficient at given position from the binary variable array

Parameters
scipSCIP data structure
eventhdlrevent handler to call for the event processing
conslinking constraint
posposition of coefficient to delete

Definition at line 919 of file cons_linking.c.

References dropEvent(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPreleaseVar(), SCIPunlockVarCons(), SCIPvarIsTransformed(), and TRUE.

Referenced by removeFixedBinvars().

static SCIP_RETCODE removeFixedBinvars ( SCIP scip,
SCIP_EVENTHDLR eventhdlr,
SCIP_CONS cons 
)
static

remove the trailing and leeading binary variable which are fixed to zero

Parameters
scipSCIP data structure
eventhdlrevent handler to call for the event processing
conslinking constraint

Definition at line 977 of file cons_linking.c.

References delCoefPos(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIPconsGetData(), SCIPgetDepth(), SCIPgetStage(), SCIPinProbing(), SCIPinRepropagation(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_CONSPRESOL().

static SCIP_RETCODE tightenedIntvar ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_Bool cutoff,
int *  nchgbds 
)
static

tightened the integer variable due to binary variables which are fixed to zero

Parameters
scipSCIP data structure
conslinking constraint to be processed
consdatalinking constraint to be processed
cutoffpointer to store TRUE, if the node can be cut off
nchgbdspointer to store the number of changed variable bounds

Definition at line 1024 of file cons_linking.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPanalyzeConflictCons(), SCIPdebugMessage, SCIPgetStage(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by processBinvarFixings(), and SCIP_DECL_CONSPRESOL().

static SCIP_RETCODE processBinvarFixings ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff,
int *  nchgbds,
SCIP_Bool addcut,
SCIP_Bool mustcheck 
)
static

checks constraint for violation only looking at the fixed binary variables, applies further fixings if possible

Parameters
scipSCIP data structure
conslinking constraint to be processed
cutoffpointer to store TRUE, if the node can be cut off
nchgbdspointer to store the number of changed variable bounds
addcutpointer to store whether this constraint must be added as a cut
mustcheckpointer to store whether this constraint must be checked for feasibility

Definition at line 1160 of file cons_linking.c.

References consdataSort(), consFixInteger(), CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPaddConflictBinvar(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPgetStage(), SCIPinferBinvarCons(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPisConflictAnalysisApplicable(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisLT(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), tightenedIntvar(), and TRUE.

Referenced by enforcePseudo(), and SCIP_DECL_CONSPROP().

static SCIP_Bool checkCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol 
)
static

returns whether the given solution is feasible for the given linking constraint

Parameters
scipSCIP data structure
conslinking constraint to be checked
solprimal solution, or NULL for current LP/pseudo solution

Definition at line 1406 of file cons_linking.c.

References aggregateVariables(), getHashmapKey(), MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMessage, SCIPfeastol(), SCIPgetSolVal(), SCIPhashmapGetImage(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisIntegral(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetStatus(), SCIPvarIsBinary(), and TRUE.

Referenced by enforcePseudo(), SCIP_DECL_CONSCHECK(), and separateCons().

static SCIP_RETCODE createRows ( SCIP scip,
SCIP_CONS cons 
)
static

create two rows for the linking constraint

  • row1: {sum_{b=1}^n-1 vals[b] * binvars[b]} - intvar = 0
  • row2: {sum_{b=0}^n-1 binvars[b]} = 1.0
Parameters
scipSCIP data structure
conslinking constraint

Definition at line 1563 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRowSameCoef(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), and SCIPsnprintf().

Referenced by addCuts().

static SCIP_RETCODE addCuts ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool cutoff 
)
static

adds linking constraint as cut to the LP

Parameters
scipSCIP data structure
conslinking constraint
solprimal CIP solution, NULL for current LP solution
cutoffwhether a cutoff has been detected

Definition at line 1613 of file cons_linking.c.

References createRows(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIProwIsInLP(), and TRUE.

Referenced by SCIP_DECL_CONSINITLP(), and separateCons().

static SCIP_RETCODE separateCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool cutoff,
SCIP_Bool separated,
int *  nchgbds 
)
static

checks constraint for violation, and adds it as a cuts if possible

Parameters
scipSCIP data structure
conslinking constraint to be separated
solprimal CIP solution, NULL for current LP solution
cutoffpointer to store TRUE, if the node can be cut off
separatedpointer to store TRUE, if a cut was found
nchgbdspointer to store the number of changed variables bounds

Definition at line 1661 of file cons_linking.c.

References addCuts(), checkCons(), CONSHDLR_NAME, FALSE, MIN, NULL, processIntegerBoundChg(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPgetRowLPFeasibility(), SCIPincConsAge(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), and TRUE.

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

static SCIP_RETCODE enforcePseudo ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool cutoff,
SCIP_Bool infeasible,
int *  nchgbds,
SCIP_Bool solvelp 
)
static

enforces the pseudo solution on the given constraint

Parameters
scipSCIP data structure
conslinking constraint to be separated
cutoffpointer to store TRUE, if the node can be cut off
infeasiblepointer to store TRUE, if the constraint was infeasible
nchgbdspointer to store the number of changed variable bounds
solvelppointer to store TRUE, if the LP has to be solved

Definition at line 1755 of file cons_linking.c.

References checkCons(), CONSHDLR_NAME, FALSE, NULL, processBinvarFixings(), processIntegerBoundChg(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPhasCurrentNodeLP(), SCIPincConsAge(), SCIPresetConsAge(), and TRUE.

Referenced by SCIP_DECL_CONSENFOPS().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyLinking  )
static

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

Definition at line 1818 of file cons_linking.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrLinking(), and TRUE.

static SCIP_DECL_CONSFREE ( consFreeLinking  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 1834 of file cons_linking.c.

References CONSHDLR_NAME, conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().

static SCIP_DECL_CONSINITPRE ( consInitpreLinking  )
static

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

Definition at line 1854 of file cons_linking.c.

References consdataLinearize(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsAdded(), SCIPdelCons(), SCIPdisableCons(), and SCIPvarGetLbGlobal().

static SCIP_DECL_CONSEXITSOL ( consExitsolLinking  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 1891 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPreleaseRow().

static SCIP_DECL_CONSDELETE ( consDeleteLinking  )
static
static SCIP_DECL_CONSINITLP ( consInitlpLinking  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 1993 of file cons_linking.c.

References addCuts(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPconsIsInitial().

static SCIP_DECL_CONSSEPALP ( consSepalpLinking  )
static

separation method of constraint handler for LP solutions

Definition at line 2019 of file cons_linking.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetName(), SCIPdebugMessage, and separateCons().

static SCIP_DECL_CONSSEPASOL ( consSepasolLinking  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 2059 of file cons_linking.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetName(), SCIPdebugMessage, and separateCons().

static SCIP_DECL_CONSENFOLP ( consEnfolpLinking  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 2099 of file cons_linking.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetName(), SCIPdebugMessage, and separateCons().

static SCIP_DECL_CONSENFOPS ( consEnfopsLinking  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 2145 of file cons_linking.c.

References CONSHDLR_NAME, enforcePseudo(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SOLVELP, SCIPconshdlrGetName(), and SCIPdebugMessage.

static SCIP_DECL_CONSCHECK ( consCheckLinking  )
static
static SCIP_DECL_CONSPROP ( consPropLinking  )
static
static SCIP_DECL_CONSLOCK ( consLockLinking  )
static

variable rounding lock method of constraint handler

Definition at line 2827 of file cons_linking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarLocks(), and SCIPconsGetData().

static SCIP_DECL_CONSENABLE ( consEnableLinking  )
static

constraint enabling notification method of constraint handler

Definition at line 2849 of file cons_linking.c.

References consdataLinearize(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPdelCons(), SCIPdisableCons(), and SCIPvarGetLbGlobal().

static SCIP_DECL_CONSPRINT ( consPrintLinking  )
static

constraint display method of constraint handler

Definition at line 2877 of file cons_linking.c.

References consdataPrint(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().

static SCIP_DECL_CONSCOPY ( consCopyLinking  )
static
static SCIP_DECL_CONSPARSE ( consParseLinking  )
static
static SCIP_DECL_CONSGETVARS ( consGetVarsLinking  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 3068 of file cons_linking.c.

References BMScopyMemoryArray, FALSE, NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.

static SCIP_DECL_CONSGETNVARS ( consGetNVarsLinking  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 3091 of file cons_linking.c.

References NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.

static SCIP_DECL_EVENTEXEC ( eventExecBinvar  )
static
SCIP_RETCODE SCIPcreateConsLinking ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR intvar,
SCIP_VAR **  binvars,
int *  vals,
int  nbinvars,
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 
)

creates and captures a linking constraint

Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
intvarinteger variable which should be linked
binvarsbinary variables, or NULL
valscoefficients of the binary variables
nbinvarsnumber of binary variables
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 3219 of file cons_linking.c.

References consdataCreate(), CONSHDLR_NAME, getHashmapKey(), HASHSIZE_BINVARSCONS, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPblkmem(), SCIPconshdlrGetData(), SCIPcreateCons(), SCIPdebugMessage, SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapInsert(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by consdataCollectLinkingCons(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), and SCIPcreateConsBasicLinking().

SCIP_RETCODE SCIPcreateConsBasicLinking ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR intvar,
SCIP_VAR **  binvars,
int *  vals,
int  nbinvars 
)

creates and captures a linking constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsLinking(); all flags can be set via SCIPsetCons<Flagname>-methods in scip.h

See also
SCIPcreateConsLinking() for information about the basic constraint flag configuration
Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
intvarinteger variable which should be linked
binvarsbinary variables, or NULL
valscoefficients of the binary variables
nbinvarsnumber of binary variables

Definition at line 3305 of file cons_linking.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateConsLinking(), and TRUE.

SCIP_Bool SCIPexistsConsLinking ( SCIP scip,
SCIP_VAR intvar 
)

checks if for the given integer variable a linking constraint exists

Parameters
scipSCIP data structure
intvarinteger variable which should be linked

Definition at line 3324 of file cons_linking.c.

References CONSHDLR_NAME, getHashmapKey(), NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), and SCIPhashmapExists().

Referenced by collectBinaryVars(), and consdataCollectLinkingCons().

SCIP_CONS* SCIPgetConsLinking ( SCIP scip,
SCIP_VAR intvar 
)

returns the linking constraint belonging to the given integer variable or NULL if it does not exist yet

Parameters
scipSCIP data structure
intvarinteger variable which should be linked

Definition at line 3342 of file cons_linking.c.

References CONSHDLR_NAME, getHashmapKey(), NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), and SCIPhashmapGetImage().

Referenced by collectBinaryVars(), consdataCollectLinkingCons(), and consdataCreate().

SCIP_VAR* SCIPgetIntvarLinking ( SCIP scip,
SCIP_CONS cons 
)

returns the integer variable of the linking constraint

Parameters
scipSCIP data structure
conslinking constraint

Definition at line 3363 of file cons_linking.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

SCIP_RETCODE SCIPgetBinvarsLinking ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR ***  binvars,
int *  nbinvars 
)

returns the binary variables of the linking constraint

Parameters
scipSCIP data structure
conslinking constraint
binvarspointer to store the binary variables array pointer
nbinvarspointer to store the number of returned binary variables

Definition at line 3385 of file cons_linking.c.

References consdataCreateBinvars(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by collectBinaryVars(), and createCoverCutsTimepoint().

int SCIPgetNBinvarsLinking ( SCIP scip,
SCIP_CONS cons 
)

returns the number of binary variables of the linking constraint

Parameters
scipSCIP data structure
conslinking constraint

Definition at line 3429 of file cons_linking.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

int* SCIPgetValsLinking ( SCIP scip,
SCIP_CONS cons 
)

returns the coefficients of the binary variables

Parameters
scipSCIP data structure
conslinking constraint

Definition at line 3450 of file cons_linking.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by collectBinaryVars(), and createCoverCutsTimepoint().