|
|
Constraint handler for the set partitioning / packing / covering constraints  .
- 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  , a set partitioning constraint has the form
![\[ \sum_{i=1}^n x_i = 1, \]](form_246.png)
a set packing constraint has the form
![\[ \sum_{i=1}^n x_i \le 1, \]](form_247.png)
and a set covering constraint has the form
![\[ \sum_{i=1}^n x_i \ge 1. \]](form_207.png)
Definition in file cons_setppc.h.
Go to the source code of this file.
|
| 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) |
| |
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.
| 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 8890 of file cons_setppc.c.
References createConsSetppc(), SCIP_SETPPCTYPE_PARTITIONING, and SCIPcreateConsBasicSetpart().
Referenced by cliquePresolve(), consdataLinearize(), createAndAddLinearCons(), extractGates(), and processIntegerBoundChg().
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 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
-
| 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 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().
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 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
-
| 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 9007 of file cons_setppc.c.
References createConsSetppc(), SCIP_SETPPCTYPE_COVERING, and SCIPcreateConsBasicSetcover().
Referenced by createAndAddLinearCons(), CUTOFF_CONSTRAINT(), forbidCover(), forbidFixation(), processNlRow(), and readCnf().
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 9047 of file cons_setppc.c.
Referenced by SCIPcreateConsSetcover().
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 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().
gets number 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(), SCIPerrorMessage, and SCIPgetVarsSetppc().
Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), getLinearConsNVars(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPaddCoefSetppc(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().
gets array of variables in 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(), SCIPerrorMessage, and SCIPgetTypeSetppc().
Referenced by addSetppcConstraints(), correctPresoldata(), createPresoldata(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPgetNVarsSetppc(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().
gets type of set partitioning / packing / covering constraint
- Parameters
-
| scip | SCIP data structure |
| cons | constraint data |
Definition at line 9128 of file cons_setppc.c.
References CONSHDLR_NAME, NULL, SCIP_Real, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetDualsolSetppc().
Referenced by addSetppcConstraints(), cleanupHashDatas(), correctPresoldata(), createPresoldata(), findAggregation(), getLinearConsSides(), SCIP_DECL_READERWRITE(), SCIPgetVarsSetppc(), SCIPmatrixCreate(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePip(), tryUpgradingSetppc(), writeFzn(), and writeOpbConstraints().
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 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().
|
