Detailed Description

Constraint handler for the set partitioning / packing / covering constraints $1^T x\ \{=, \le, \ge\}\ 1$ .

Author: Tobias Achterberg; Michael Winkler

This constraint handler handles three special classes of linear constraints, namely set partitioning, set packing, and set covering constraints. For a set of binary variables $x_i, i=1,\dots,n$ , a set partitioning constraint has the form

$\sum_{i=1}^n x_i = 1,$

a set packing constraint has the form

$\sum_{i=1}^n x_i \le 1,$

and a set covering constraint has the form

$\sum_{i=1}^n x_i \ge 1.$

Definition in file cons_setppc.h.

#include "scip/scip.h"

Go to the source code of this file.

Typedefs
typedef enum SCIP_SetppcType	SCIP_SETPPCTYPE

Enumerations
enum	SCIP_SetppcType { SCIP_SETPPCTYPE_PARTITIONING = 0, SCIP_SETPPCTYPE_PACKING = 1, SCIP_SETPPCTYPE_COVERING = 2 }

Functions
SCIP_RETCODE	SCIPincludeConshdlrSetppc (SCIP *scip)

SCIP_RETCODE	SCIPcreateConsSetpart (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars, 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	SCIPcreateConsBasicSetpart (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars)

SCIP_RETCODE	SCIPcreateConsSetpack (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars, 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	SCIPcreateConsBasicSetpack (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars)

SCIP_RETCODE	SCIPcreateConsSetcover (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars, 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	SCIPcreateConsBasicSetcover (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR **vars)

SCIP_RETCODE	SCIPaddCoefSetppc (SCIP scip, SCIP_CONS cons, SCIP_VAR *var)

int	SCIPgetNVarsSetppc (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetVarsSetppc (SCIP scip, SCIP_CONS cons)

SCIP_SETPPCTYPE	SCIPgetTypeSetppc (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPgetDualsolSetppc (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPgetDualfarkasSetppc (SCIP scip, SCIP_CONS cons)

SCIP_ROW *	SCIPgetRowSetppc (SCIP scip, SCIP_CONS cons)

int	SCIPgetNFixedonesSetppc (SCIP scip, SCIP_CONS cons)

int	SCIPgetNFixedzerosSetppc (SCIP scip, SCIP_CONS cons)

Typedef Documentation

typedef enum SCIP_SetppcType SCIP_SETPPCTYPE

Definition at line 57 of file cons_setppc.h.

Enumeration Type Documentation

enum SCIP_SetppcType

type of setppc constraint: set partitioning, set packing, or set covering

Enumerator:

SCIP_SETPPCTYPE_PARTITIONING	constraint is a set partitioning constraint: sum(x) == 1
SCIP_SETPPCTYPE_PACKING	constraint is a set packing constraint: sum(x) <= 1
SCIP_SETPPCTYPE_COVERING	constraint is a set covering constraint: sum(x) >= 1

Definition at line 51 of file cons_setppc.h.

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrSetppc ( SCIP * scip )

creates the handler for set partitioning / packing / covering constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 8767 of file cons_setppc.c.

References CONFLICTHDLR_DESC, CONFLICTHDLR_NAME, CONFLICTHDLR_PRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPRESOL, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, conshdlrdataCreate(), DEFAULT_ADDVARIABLESASCLIQUES, DEFAULT_CLIQUELIFTING, DEFAULT_CLIQUESHRINKING, DEFAULT_DUALPRESOLVING, DEFAULT_NPSEUDOBRANCHES, DEFAULT_PRESOLPAIRWISE, DEFAULT_PRESOLUSEHASHING, EVENTHDLR_DESC, EVENTHDLR_NAME, LINCONSUPGD_PRIORITY, NULL, QUADCONSUPGD_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPfindConshdlr(), SCIPincludeConflicthdlrBasic(), SCIPincludeConshdlrBasic(), SCIPincludeEventhdlrBasic(), SCIPincludeLinconsUpgrade(), SCIPincludeQuadconsUpgrade(), SCIPsetConshdlrActive(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDeactive(), SCIPsetConshdlrDelete(), SCIPsetConshdlrDelvars(), SCIPsetConshdlrExitpre(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrGetNVars(), SCIPsetConshdlrGetVars(), SCIPsetConshdlrInit(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrParse(), SCIPsetConshdlrPresol(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrResprop(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

Referenced by SCIP_DECL_CONSHDLRCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPcreateConsSetpart	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		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 set partitioning constraint

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
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.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
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.

Definition at line 8869 of file cons_setppc.c.

References createConsSetppc(), and SCIP_SETPPCTYPE_PARTITIONING.

Referenced by cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), extractGates(), processIntegerBoundChg(), SCIP_DECL_CONSPARSE(), SCIP_DECL_PRESOLEXEC(), and SCIPcreateConsBasicSetpart().

SCIP_RETCODE SCIPcreateConsBasicSetpart	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set partitioning constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See Also: SCIPcreateConsSetpart() for the default constraint flag configuration

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

creates and captures a set partitioning constraint with all constraint flags set to their default values

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 8909 of file cons_setppc.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSetpart(), and TRUE.

SCIP_RETCODE SCIPcreateConsSetpack	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		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 set packing constraint

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
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.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
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.

Definition at line 8927 of file cons_setppc.c.

References createConsSetppc(), and SCIP_SETPPCTYPE_PACKING.

Referenced by addCliques(), addExtraCliques(), cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), createCoveringProblem(), deleteRedundantVars(), detectRedundantVars(), dualWeightsTightening(), fixDeleteOrUpgradeCons(), presolRoundSOS1(), removeConstraintsDueToNegCliques(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONSPARSE(), SCIP_DECL_QUADCONSUPGD(), SCIPcreateConsBasicSetpack(), tightenWeights(), upgradeCons(), and upgradeConss().

SCIP_RETCODE SCIPcreateConsBasicSetpack	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set packing constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See Also: SCIPcreateConsSetpack() for the default constraint flag configuration

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

creates and captures a set packing constraint with all constraint flags set to their default values

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 8967 of file cons_setppc.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSetpack(), and TRUE.

SCIP_RETCODE SCIPcreateConsSetcover	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		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 set covering constraint

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
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.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
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.

Definition at line 8986 of file cons_setppc.c.

References createConsSetppc(), and SCIP_SETPPCTYPE_COVERING.

Referenced by createAndAddLinearCons(), CUTOFF_CONSTRAINT(), forbidCover(), forbidFixation(), processNlRow(), readCnf(), SCIP_DECL_CONFLICTEXEC(), SCIP_DECL_CONSPARSE(), and SCIPcreateConsBasicSetcover().

SCIP_RETCODE SCIPcreateConsBasicSetcover	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars
	)

creates and captures a set packing constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See Also: SCIPcreateConsSetpack() for the default constraint flag configuration

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

creates and captures a set covering constraint with all constraint flags set to their default values

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
nvars	number of variables in the constraint
vars	array with variables of constraint entries

Definition at line 9026 of file cons_setppc.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSetcover(), and TRUE.

SCIP_RETCODE SCIPaddCoefSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

adds coefficient in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data
var	variable to add to the constraint

Definition at line 9042 of file cons_setppc.c.

References addCoef(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by addCoefTerm(), cliquePresolve(), and SCIPaddCoefPseudoboolean().

int SCIPgetNVarsSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets number of variables in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9065 of file cons_setppc.c.

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

Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), getLinearConsNVars(), getLinearConsVarsData(), initMatrix(), SCIP_DECL_CONSCOPY(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERWRITE(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_VAR** SCIPgetVarsSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets array of variables in set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9086 of file cons_setppc.c.

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

Referenced by addSetppcConstraints(), correctPresoldata(), createPresoldata(), getLinearConsVarsData(), initMatrix(), SCIP_DECL_CONSCOPY(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERWRITE(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_SETPPCTYPE SCIPgetTypeSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets type of set partitioning / packing / covering constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9107 of file cons_setppc.c.

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

Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), findAggregation(), getLinearConsSides(), initMatrix(), SCIP_DECL_CONSCOPY(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERWRITE(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePip(), tryUpgradingSetppc(), writeFzn(), and writeOpbConstraints().

SCIP_Real SCIPgetDualsolSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the dual solution of the set partitioning / packing / covering constraint in the current LP

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9127 of file cons_setppc.c.

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

SCIP_Real SCIPgetDualfarkasSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9151 of file cons_setppc.c.

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

SCIP_ROW* SCIPgetRowSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no LP row was yet created; the user must not modify the row!

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9177 of file cons_setppc.c.

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

int SCIPgetNFixedonesSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns current number of variables fixed to one in the constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9198 of file cons_setppc.c.

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

int SCIPgetNFixedzerosSetppc	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns current number of variables fixed to zero in the constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 9220 of file cons_setppc.c.

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

SCIP

Detailed Description

Typedefs

Enumerations

Functions

Typedef Documentation

Enumeration Type Documentation

Function Documentation