Scippy

SCIP

Solving Constraint Integer Programs

cons_setppc.h File Reference

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_ROWSCIPgetRowSetppc (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNFixedonesSetppc (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNFixedzerosSetppc (SCIP *scip, SCIP_CONS *cons)
 

Typedef Documentation

Definition at line 57 of file cons_setppc.h.

Enumeration Type Documentation

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
scipSCIP data structure

Definition at line 8788 of file cons_setppc.c.

Referenced by 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
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 8890 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_PARTITIONING, and SCIPcreateConsBasicSetpart().

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

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries

Definition at line 8930 of file cons_setppc.c.

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPcreateConsSetpart().

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
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 8948 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_PACKING, and SCIPcreateConsBasicSetpack().

Referenced by addCliques(), addExtraCliques(), cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), createCoveringProblem(), deleteRedundantVars(), detectRedundantVars(), dualWeightsTightening(), fixDeleteOrUpgradeCons(), presolRoundConsSOS1(), removeConstraintsDueToNegCliques(), 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries

Definition at line 8988 of file cons_setppc.c.

Referenced by SCIPcreateConsSetpack().

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
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 9007 of file cons_setppc.c.

References createConsSetppc(), SCIP_SETPPCTYPE_COVERING, and SCIPcreateConsBasicSetcover().

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

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries

Definition at line 9047 of file cons_setppc.c.

Referenced by SCIPcreateConsSetcover().

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

adds coefficient in set partitioning / packing / covering constraint

Parameters
scipSCIP data structure
consconstraint data
varvariable to add to the constraint

Definition at line 9063 of file cons_setppc.c.

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

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

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

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

Parameters
scipSCIP data structure
consconstraint data

Definition at line 9148 of file cons_setppc.c.

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

Referenced by SCIPgetTypeSetppc().

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
scipSCIP data structure
consconstraint data

Definition at line 9172 of file cons_setppc.c.

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

Referenced by SCIPgetDualsolSetppc().

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
scipSCIP data structure
consconstraint data

Definition at line 9198 of file cons_setppc.c.

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

Referenced by SCIPgetDualfarkasSetppc().

int SCIPgetNFixedonesSetppc ( SCIP scip,
SCIP_CONS cons 
)

returns current number of variables fixed to one in the constraint

Parameters
scipSCIP data structure
consconstraint data

Definition at line 9219 of file cons_setppc.c.

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

Referenced by SCIPgetRowSetppc().

int SCIPgetNFixedzerosSetppc ( SCIP scip,
SCIP_CONS cons 
)

returns current number of variables fixed to zero in the constraint

Parameters
scipSCIP data structure
consconstraint data

Definition at line 9241 of file cons_setppc.c.

References NULL, SCIPABORT, SCIPconsGetData(), and SCIPerrorMessage.

Referenced by SCIPgetNFixedonesSetppc().