Scippy

SCIP

Solving Constraint Integer Programs

cons_indicator.h File Reference

Detailed Description

constraint handler for indicator constraints

Author
Marc Pfetsch

An indicator constraint is given by a binary variable $z$ and an inequality $ax \leq b$. It states that if $z = 1$ then $ax \leq b$ holds.

This constraint is handled by adding a slack variable $s:\; ax - s \leq b$ with $s \geq 0$. The constraint is enforced by fixing $s$ to 0 if $z = 1$.

Note
The constraint only implements an implication not an equivalence, i.e., it does not ensure that $z = 1$ if $ax \leq b$ or equivalently if $s = 0$ holds.

This constraint is equivalent to a linear constraint $ax - s \leq b$ and an SOS1 constraint on $z$ and $s$ (at most one should be nonzero). In the indicator context we can, however, separate more inequalities.

The name indicator apparently comes from CPLEX.

Definition in file cons_indicator.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeConshdlrIndicator (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsIndicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhs, 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 SCIPcreateConsBasicIndicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhs)
 
SCIP_RETCODE SCIPcreateConsIndicatorLinCons (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *lincons, SCIP_VAR *slackvar, 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 SCIPcreateConsBasicIndicatorLinCons (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *lincons, SCIP_VAR *slackvar)
 
SCIP_RETCODE SCIPaddVarIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
 
SCIP_CONSSCIPgetLinearConsIndicator (SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetLinearConsIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_CONS *lincons)
 
SCIP_RETCODE SCIPsetBinaryVarIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *binvar)
 
SCIP_VARSCIPgetBinaryVarIndicator (SCIP_CONS *cons)
 
SCIP_VARSCIPgetSlackVarIndicator (SCIP_CONS *cons)
 
SCIP_Bool SCIPisViolatedIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
 
SCIP_RETCODE SCIPmakeIndicatorFeasible (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *changed)
 
SCIP_RETCODE SCIPmakeIndicatorsFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed)
 
SCIP_RETCODE SCIPaddLinearConsIndicator (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *lincons)
 
SCIP_RETCODE SCIPaddRowIndicator (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_ROW *row)
 

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrIndicator ( SCIP scip)

creates the handler for indicator constraints and includes it in SCIP

Parameters
scipSCIP data structure
SCIP_RETCODE SCIPcreateConsIndicator ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR binvar,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  rhs,
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 
)

creates and captures an indicator constraint

Note
binvar is checked to be binary only later. This enables a change of the type in procedures reading an instance.
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 (indicator or quadratic)
namename of constraint
binvarbinary indicator variable (or NULL)
nvarsnumber of variables in the inequality
varsarray with variables of inequality (or NULL)
valsvalues of variables in inequality (or NULL)
rhsrhs of the inequality
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE.
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.
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.
SCIP_RETCODE SCIPcreateConsBasicIndicator ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR binvar,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  rhs 
)

creates and captures an indicator constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsIndicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h

See Also
SCIPcreateConsIndicator() 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 (indicator or quadratic)
namename of constraint
binvarbinary indicator variable (or NULL)
nvarsnumber of variables in the inequality
varsarray with variables of inequality (or NULL)
valsvalues of variables in inequality (or NULL)
rhsrhs of the inequality
SCIP_RETCODE SCIPcreateConsIndicatorLinCons ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR binvar,
SCIP_CONS lincons,
SCIP_VAR slackvar,
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 
)

creates and captures an indicator constraint with given linear constraint and slack variable

Note
binvar is checked to be binary only later. This enables a change of the type in procedures reading an instance.
we assume that slackvar actually appears in lincons and we also assume that it takes the role of a slack variable!
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
binvarbinary indicator variable (or NULL)
linconslinear constraint
slackvarslack variable
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE.
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.
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.
SCIP_RETCODE SCIPcreateConsBasicIndicatorLinCons ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR binvar,
SCIP_CONS lincons,
SCIP_VAR slackvar 
)

creates and captures an indicator constraint with given linear constraint and slack variable in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsIndicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h

Note
binvar is checked to be binary only later. This enables a change of the type in procedures reading an instance.
we assume that slackvar actually appears in lincons and we also assume that it takes the role of a slack variable!
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
See Also
SCIPcreateConsIndicatorLinCons() 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
binvarbinary indicator variable (or NULL)
linconslinear constraint
slackvarslack variable
SCIP_RETCODE SCIPaddVarIndicator ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  val 
)

adds variable to the inequality of the indicator constraint

Parameters
scipSCIP data structure
consindicator constraint
varvariable to add to the inequality
valvalue of variable
SCIP_CONS* SCIPgetLinearConsIndicator ( SCIP_CONS cons)

gets the linear constraint corresponding to the indicator constraint (may be NULL)

Parameters
consindicator constraint
SCIP_RETCODE SCIPsetLinearConsIndicator ( SCIP scip,
SCIP_CONS cons,
SCIP_CONS lincons 
)

sets the linear constraint corresponding to the indicator constraint (may be NULL)

Parameters
scipSCIP data structure
consindicator constraint
linconslinear constraint
SCIP_RETCODE SCIPsetBinaryVarIndicator ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR binvar 
)

sets binary indicator variable for indicator constraint

Parameters
scipSCIP data structure
consindicator constraint
binvarbinary variable to add to the inequality
SCIP_VAR* SCIPgetBinaryVarIndicator ( SCIP_CONS cons)

gets binary variable corresponding to indicator constraint

Parameters
consindicator constraint
SCIP_VAR* SCIPgetSlackVarIndicator ( SCIP_CONS cons)

gets slack variable corresponding to indicator constraint

Parameters
consindicator constraint
SCIP_Bool SCIPisViolatedIndicator ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol 
)

checks whether indicator constraint is violated w.r.t. sol

Parameters
scipSCIP data structure
consindicator constraint
solsolution, or NULL to use current node's solution
SCIP_RETCODE SCIPmakeIndicatorFeasible ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool changed 
)

Based on values of other variables, computes slack and binary variable to turn constraint feasible

Parameters
scipSCIP data structure
consindicator constraint
solsolution
changedpointer to store whether the solution has been changed
SCIP_RETCODE SCIPmakeIndicatorsFeasible ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
SCIP_Bool changed 
)

Based on values of other variables, computes slack and binary variable to turn all constraints feasible

Parameters
scipSCIP data structure
conshdlrindicator constraint handler
solsolution
changedpointer to store whether the solution has been changed
SCIP_RETCODE SCIPaddLinearConsIndicator ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS lincons 
)

adds additional linear constraint that is not connected by an indicator constraint, but can be used for separation

Parameters
scipSCIP data structure
conshdlrindicator constraint handler
linconslinear constraint
SCIP_RETCODE SCIPaddRowIndicator ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_ROW row 
)

adds additional globally valid row that is not connected by an indicator constraint, but can be used for separation

Parameters
scipSCIP data structure
conshdlrindicator constraint handler
rowrow to add