Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

constraint handler for indicator constraints over arbitrary constraint types

Author
Ambros Gleixner
Frederic Pythoud

Definition in file cons_superindicator.c.

#include "blockmemshell/memory.h"
#include "scip/cons_indicator.h"
#include "scip/cons_linear.h"
#include "scip/cons_superindicator.h"
#include "scip/dialog_default.h"
#include "scip/pub_cons.h"
#include "scip/pub_dialog.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_dialog.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "superindicator"
 
#define CONSHDLR_DESC   "constraint handler for indicator constraints over arbitrary constraint types"
 
#define CONSHDLR_SEPAPRIORITY   0
 
#define CONSHDLR_ENFOPRIORITY   -5000000
 
#define CONSHDLR_CHECKPRIORITY   -5000000
 
#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 DEFAULT_CHECKSLACKTYPE   TRUE
 
#define DEFAULT_UPGDPRIOINDICATOR   1
 
#define DEFAULT_UPGDPRIOLINEAR   2
 
#define DEFAULT_MAXUPGDCOEFLINEAR   1e4
 

Functions

static SCIP_RETCODE consdataCreateSuperindicator (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *binvar, SCIP_CONS *slackcons)
 
static SCIP_RETCODE consdataCheckSuperindicator (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_RESULT *result)
 
static void extractLinearValues (SCIP *scip, SCIP_CONS *cons, SCIP_Real *minactivity, SCIP_Real *maxactivity, SCIP_Real *minabscoef)
 
static SCIP_RETCODE upgradeIndicatorSuperindicator (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success, SCIP_Bool *deleted)
 
static SCIP_RETCODE upgradeLinearSuperindicator (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success, SCIP_Bool *deleted)
 
static SCIP_RETCODE upgradeSuperindicator (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success, SCIP_Bool *deleted)
 
static SCIP_RETCODE enforceConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool solinfeasible, SCIP_RESULT *result)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopySuperindicator)
 
static SCIP_DECL_CONSFREE (consFreeSuperindicator)
 
static SCIP_DECL_CONSINITPRE (consInitpreSuperindicator)
 
static SCIP_DECL_CONSDELETE (consDeleteSuperindicator)
 
static SCIP_DECL_CONSTRANS (consTransSuperindicator)
 
static SCIP_DECL_CONSINITLP (consInitlpSuperindicator)
 
static SCIP_DECL_CONSSEPALP (consSepalpSuperindicator)
 
static SCIP_DECL_CONSSEPASOL (consSepasolSuperindicator)
 
static SCIP_DECL_CONSENFOLP (consEnfolpSuperindicator)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxSuperindicator)
 
static SCIP_DECL_CONSENFOPS (consEnfopsSuperindicator)
 
static SCIP_DECL_CONSCHECK (consCheckSuperindicator)
 
static SCIP_DECL_CONSPROP (consPropSuperindicator)
 
static SCIP_DECL_CONSPRESOL (consPresolSuperindicator)
 
static SCIP_DECL_CONSRESPROP (consRespropSuperindicator)
 
static SCIP_DECL_CONSLOCK (consLockSuperindicator)
 
static SCIP_DECL_CONSPRINT (consPrintSuperindicator)
 
static SCIP_DECL_CONSCOPY (consCopySuperindicator)
 
static SCIP_DECL_CONSPARSE (consParseSuperindicator)
 
static SCIP_DECL_CONSGETVARS (consGetVarsSuperindicator)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsSuperindicator)
 
SCIP_RETCODE SCIPincludeConshdlrSuperindicator (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsSuperindicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *slackcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicSuperindicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *slackcons)
 
SCIP_VARSCIPgetBinaryVarSuperindicator (SCIP_CONS *cons)
 
SCIP_CONSSCIPgetSlackConsSuperindicator (SCIP_CONS *cons)
 
SCIP_RETCODE SCIPtransformMinUC (SCIP *scip, SCIP_Bool *success)
 
 SCIP_DECL_DIALOGEXEC (SCIPdialogExecChangeMinUC)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "constraint handler for indicator constraints over arbitrary constraint types"

Definition at line 63 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   0

priority of the constraint handler for separation

Definition at line 64 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -5000000

priority of the constraint handler for constraint enforcing

Definition at line 65 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -5000000

priority of the constraint handler for checking feasibility

Definition at line 66 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   -1

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

Definition at line 67 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 68 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_EAGERFREQ

#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 69 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

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

Definition at line 72 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 75 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 76 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

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

Definition at line 77 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask of the constraint handler

Definition at line 79 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

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

Definition at line 80 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ DEFAULT_CHECKSLACKTYPE

#define DEFAULT_CHECKSLACKTYPE   TRUE

should type of slack constraint be checked when creating superindicator constraint?

Definition at line 82 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ DEFAULT_UPGDPRIOINDICATOR

#define DEFAULT_UPGDPRIOINDICATOR   1

priority for upgrading to an indicator constraint (-1: never)

Definition at line 83 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ DEFAULT_UPGDPRIOLINEAR

#define DEFAULT_UPGDPRIOLINEAR   2

priority for upgrading to a linear constraint (-1: never)

Definition at line 84 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

◆ DEFAULT_MAXUPGDCOEFLINEAR

#define DEFAULT_MAXUPGDCOEFLINEAR   1e4

maximum big-M coefficient of binary variable in upgrade to a linear constraint (relative to smallest coefficient)

Definition at line 85 of file cons_superindicator.c.

Referenced by SCIPincludeConshdlrSuperindicator().

Function Documentation

◆ consdataCreateSuperindicator()

static SCIP_RETCODE consdataCreateSuperindicator ( SCIP scip,
SCIP_CONSDATA **  consdata,
SCIP_VAR binvar,
SCIP_CONS slackcons 
)
static

creates superindicator constraint data

Parameters
scipSCIP data structure
consdatapointer to constraint data
binvarbinary variable
slackconsslack constraint

Definition at line 118 of file cons_superindicator.c.

References consdataCheckSuperindicator(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), SCIPcaptureCons(), SCIPdebugMsg, SCIPgetTransformedVar(), SCIPisTransformed(), and SCIPtransformCons().

Referenced by SCIPcreateConsSuperindicator().

◆ consdataCheckSuperindicator()

static SCIP_RETCODE consdataCheckSuperindicator ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol,
SCIP_Bool  checkintegrality,
SCIP_Bool  checklprows,
SCIP_Bool  printreason,
SCIP_RESULT result 
)
static

checks the feasibility of a superindicator constraint

Parameters
scipSCIP data structure
consdatapointer to superindicator constraint data
solpointer to the solution to be checked
checkintegralityHas integrality to be checked?
checklprowsDo constraints represented by rows in the current LP have to be checked?
printreasonShould the reason for the violation be printed?
resultpointer to store the result of the test

Definition at line 157 of file cons_superindicator.c.

References extractLinearValues(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPcheckCons(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasEQ(), SCIPisIntegral(), SCIPvarGetName(), and TRUE.

Referenced by consdataCreateSuperindicator(), and enforceConstraint().

◆ extractLinearValues()

static void extractLinearValues ( SCIP scip,
SCIP_CONS cons,
SCIP_Real minactivity,
SCIP_Real maxactivity,
SCIP_Real minabscoef 
)
static

computes the minactivity, maxactivity, and minimal absolute value of nonzero coefficients of a linear constraint with respect to its global bounds

Parameters
scipSCIP data structure
conspointer to linear constraint
minactivitypointer to return the minimal activity
maxactivitypointer to return the maximal activity
minabscoefpointer to return the minimal absolute value of the coefficients

Definition at line 228 of file cons_superindicator.c.

References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPgetNVarsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPinfinity(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and upgradeIndicatorSuperindicator().

Referenced by consdataCheckSuperindicator(), and upgradeLinearSuperindicator().

◆ upgradeIndicatorSuperindicator()

static SCIP_RETCODE upgradeIndicatorSuperindicator ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool success,
SCIP_Bool deleted 
)
static

◆ upgradeLinearSuperindicator()

◆ upgradeSuperindicator()

static SCIP_RETCODE upgradeSuperindicator ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool success,
SCIP_Bool deleted 
)
static

tries to upgrade a superindicator constraint in order of the upgrade priority parameters

Parameters
scipSCIP data structure
conssuperindicator constraint to be updated
successpointer to store if the constraint was upgraded
deletedpointer to store if the constraint was deleted

Definition at line 624 of file cons_superindicator.c.

References enforceConstraint(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetData(), upgradeIndicatorSuperindicator(), and upgradeLinearSuperindicator().

Referenced by upgradeLinearSuperindicator().

◆ enforceConstraint()

static SCIP_RETCODE enforceConstraint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
int  nusefulconss,
SCIP_SOL sol,
SCIP_Bool  solinfeasible,
SCIP_RESULT result 
)
static

helper function to enforce constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
nusefulconssnumber of useful (non-obsolete) constraints to process
solsolution to enforce (NULL for the LP solution)
solinfeasiblewas the solution already declared infeasible by a constraint handler?
resultpointer to store the result of the enforcing call

Definition at line 671 of file cons_superindicator.c.

References consdataCheckSuperindicator(), FALSE, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DECL_CONSHDLRCOPY(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_INVALIDRESULT, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPdebugPrintf, SCIPenfolpCons(), SCIPenforelaxCons(), SCIPerrorMessage, SCIPisFeasEQ(), SCIPprintSol(), SCIPvarGetLbLocal(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSENFOLP(), and upgradeSuperindicator().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySuperindicator  )
static

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

Definition at line 805 of file cons_superindicator.c.

Referenced by enforceConstraint().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeSuperindicator  )
static

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

Definition at line 821 of file cons_superindicator.c.

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreSuperindicator  )
static

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

Definition at line 844 of file cons_superindicator.c.

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteSuperindicator  )
static

frees specific constraint data

Definition at line 865 of file cons_superindicator.c.

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransSuperindicator  )
static

transforms constraint data into data belonging to the transformed problem

Definition at line 888 of file cons_superindicator.c.

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpSuperindicator  )
static

LP initialization method of constraint handler

Definition at line 915 of file cons_superindicator.c.

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpSuperindicator  )
static

separation method of constraint handler for LP solutions

Definition at line 952 of file cons_superindicator.c.

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolSuperindicator  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 1061 of file cons_superindicator.c.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpSuperindicator  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 1170 of file cons_superindicator.c.

References enforceConstraint(), and SCIP_CALL.

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSuperindicator  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 1179 of file cons_superindicator.c.

References SCIP_Bool.

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsSuperindicator  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 1188 of file cons_superindicator.c.

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckSuperindicator  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 1321 of file cons_superindicator.c.

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropSuperindicator  )
static

domain propagation method of constraint handler

Definition at line 1349 of file cons_superindicator.c.

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolSuperindicator  )
static

presolving method of constraint handler

Definition at line 1442 of file cons_superindicator.c.

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropSuperindicator  )
static

propagation conflict resolving method of constraint handler

Definition at line 1531 of file cons_superindicator.c.

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockSuperindicator  )
static

variable rounding lock method of constraint handler

Definition at line 1564 of file cons_superindicator.c.

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintSuperindicator  )
static

constraint display method of constraint handler

Definition at line 1588 of file cons_superindicator.c.

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopySuperindicator  )
static

constraint copying method of constraint handler

Definition at line 1630 of file cons_superindicator.c.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseSuperindicator  )
static

constraint parsing method of constraint handler

Definition at line 1749 of file cons_superindicator.c.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsSuperindicator  )
static

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

Definition at line 1841 of file cons_superindicator.c.

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSuperindicator  )
static

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

Definition at line 1865 of file cons_superindicator.c.