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 if $ax \leq b$ or equivalently if 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_CONS *	SCIPgetLinearConsIndicator (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_VAR *	SCIPgetBinaryVarIndicator (SCIP_CONS *cons)

SCIP_VAR *	SCIPgetSlackVarIndicator (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

scip	SCIP 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

scip	SCIP data structure
cons	pointer to hold the created constraint (indicator or quadratic)
name	name of constraint
binvar	binary indicator variable (or NULL)
nvars	number of variables in the inequality
vars	array with variables of inequality (or NULL)
vals	values of variables in inequality (or NULL)
rhs	rhs of the inequality
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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

scip	SCIP data structure
cons	pointer to hold the created constraint (indicator or quadratic)
name	name of constraint
binvar	binary indicator variable (or NULL)
nvars	number of variables in the inequality
vars	array with variables of inequality (or NULL)
vals	values of variables in inequality (or NULL)
rhs	rhs 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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
binvar	binary indicator variable (or NULL)
lincons	linear constraint
slackvar	slack variable
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should 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'.
stickingatnode	should 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

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
binvar	binary indicator variable (or NULL)
lincons	linear constraint
slackvar	slack 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

scip	SCIP data structure
cons	indicator constraint
var	variable to add to the inequality
val	value of variable

SCIP_CONS* SCIPgetLinearConsIndicator ( SCIP_CONS * cons )

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

Parameters

cons	indicator 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

scip	SCIP data structure
cons	indicator constraint
lincons	linear constraint

SCIP_RETCODE SCIPsetBinaryVarIndicator	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	binvar
	)

sets binary indicator variable for indicator constraint

Parameters

scip	SCIP data structure
cons	indicator constraint
binvar	binary variable to add to the inequality

SCIP_VAR* SCIPgetBinaryVarIndicator ( SCIP_CONS * cons )

gets binary variable corresponding to indicator constraint

Parameters

cons	indicator constraint

SCIP_VAR* SCIPgetSlackVarIndicator ( SCIP_CONS * cons )

gets slack variable corresponding to indicator constraint

Parameters

cons	indicator constraint

SCIP_Bool SCIPisViolatedIndicator	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol
	)

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

Parameters

scip	SCIP data structure
cons	indicator constraint
sol	solution, 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

scip	SCIP data structure
cons	indicator constraint
sol	solution
changed	pointer 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

scip	SCIP data structure
conshdlr	indicator constraint handler
sol	solution
changed	pointer 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

scip	SCIP data structure
conshdlr	indicator constraint handler
lincons	linear 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

scip	SCIP data structure
conshdlr	indicator constraint handler
row	row to add

SCIP

Detailed Description

Functions

Function Documentation