|
Constraint handler for knapsack constraints of the form , x binary and .
- Author
- Tobias Achterberg
-
Kati Wolter
-
Michael Winkler
This constraint handler handles a special type of linear constraints, namely knapsack constraints. A knapsack constraint has the form
with non-negative integer coefficients , integer right-hand side , and binary variables .
Definition in file cons_knapsack.h.
Go to the source code of this file.
|
SCIP_RETCODE | SCIPincludeConshdlrKnapsack (SCIP *scip) |
|
SCIP_RETCODE | SCIPcreateConsKnapsack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, 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 | SCIPcreateConsBasicKnapsack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity) |
|
SCIP_RETCODE | SCIPaddCoefKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) |
|
SCIP_Longint | SCIPgetCapacityKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_RETCODE | SCIPchgCapacityKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity) |
|
int | SCIPgetNVarsKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_VAR ** | SCIPgetVarsKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Longint * | SCIPgetWeightsKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real | SCIPgetDualsolKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real | SCIPgetDualfarkasKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_ROW * | SCIPgetRowKnapsack (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_RETCODE | SCIPsolveKnapsackExactly (SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success) |
|
SCIP_RETCODE | SCIPsolveKnapsackApproximately (SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval) |
|
SCIP_RETCODE | SCIPseparateKnapsackCuts (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_SOL *sol, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts) |
|
SCIP_RETCODE | SCIPseparateRelaxedKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) |
|
creates the handler for knapsack constraints and includes it in SCIP
- Parameters
-
SCIP_RETCODE SCIPcreateConsKnapsack |
( |
SCIP * |
scip, |
|
|
SCIP_CONS ** |
cons, |
|
|
const char * |
name, |
|
|
int |
nvars, |
|
|
SCIP_VAR ** |
vars, |
|
|
SCIP_Longint * |
weights, |
|
|
SCIP_Longint |
capacity, |
|
|
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 knapsack 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 items in the knapsack |
vars | array with item variables |
weights | array with item weights |
capacity | capacity of knapsack (right hand side of inequality) |
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. |
creates and captures a knapsack constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsKnapsack(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
- See Also
- SCIPcreateConsKnapsack() 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 |
nvars | number of items in the knapsack |
vars | array with item variables |
weights | array with item weights |
capacity | capacity of knapsack |
adds new item to knapsack constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
var | item variable |
weight | item weight |
gets the capacity of the knapsack constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
changes capacity of the knapsack constraint
- Note
- This method can only be called during problem creation stage (SCIP_STAGE_PROBLEM)
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
capacity | new capacity of knapsack |
gets the number of items in the knapsack constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
gets the array of variables in the knapsack constraint; the user must not modify this array!
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
gets the array of weights in the knapsack constraint; the user must not modify this array!
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
gets the dual solution of the knapsack constraint in the current LP
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
gets the dual Farkas value of the knapsack constraint in the current infeasible LP
- Parameters
-
scip | SCIP data structure |
cons | constraint data |
returns the linear relaxation of the given knapsack 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 |
SCIP_RETCODE SCIPsolveKnapsackExactly |
( |
SCIP * |
scip, |
|
|
int |
nitems, |
|
|
SCIP_Longint * |
weights, |
|
|
SCIP_Real * |
profits, |
|
|
SCIP_Longint |
capacity, |
|
|
int * |
items, |
|
|
int * |
solitems, |
|
|
int * |
nonsolitems, |
|
|
int * |
nsolitems, |
|
|
int * |
nnonsolitems, |
|
|
SCIP_Real * |
solval, |
|
|
SCIP_Bool * |
success |
|
) |
| |
solves knapsack problem in maximization form exactly using dynamic programming; if needed, one can provide arrays to store all selected items and all not selected items
- Parameters
-
scip | SCIP data structure |
nitems | number of available items |
weights | item weights |
profits | item profits |
capacity | capacity of knapsack |
items | item numbers |
solitems | array to store items in solution, or NULL |
nonsolitems | array to store items not in solution, or NULL |
nsolitems | pointer to store number of items in solution, or NULL |
nnonsolitems | pointer to store number of items not in solution, or NULL |
solval | pointer to store optimal solution value, or NULL |
success | pointer to store if an error occured during solving (normally a memory problem) |
SCIP_RETCODE SCIPsolveKnapsackApproximately |
( |
SCIP * |
scip, |
|
|
int |
nitems, |
|
|
SCIP_Longint * |
weights, |
|
|
SCIP_Real * |
profits, |
|
|
SCIP_Longint |
capacity, |
|
|
int * |
items, |
|
|
int * |
solitems, |
|
|
int * |
nonsolitems, |
|
|
int * |
nsolitems, |
|
|
int * |
nnonsolitems, |
|
|
SCIP_Real * |
solval |
|
) |
| |
solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not selected items
- Parameters
-
scip | SCIP data structure |
nitems | number of available items |
weights | item weights |
profits | item profits |
capacity | capacity of knapsack |
items | item numbers |
solitems | array to store items in solution, or NULL |
nonsolitems | array to store items not in solution, or NULL |
nsolitems | pointer to store number of items in solution, or NULL |
nnonsolitems | pointer to store number of items not in solution, or NULL |
solval | pointer to store optimal solution value, or NULL |
SCIP_RETCODE SCIPseparateKnapsackCuts |
( |
SCIP * |
scip, |
|
|
SCIP_CONS * |
cons, |
|
|
SCIP_SEPA * |
sepa, |
|
|
SCIP_VAR ** |
vars, |
|
|
int |
nvars, |
|
|
SCIP_Longint * |
weights, |
|
|
SCIP_Longint |
capacity, |
|
|
SCIP_SOL * |
sol, |
|
|
SCIP_Bool |
usegubs, |
|
|
SCIP_Bool * |
cutoff, |
|
|
int * |
ncuts |
|
) |
| |
separates lifted valid inequalities for given knapsack problem
- Parameters
-
scip | SCIP data structure |
cons | originating constraint of the knapsack problem, or NULL |
sepa | originating separator of the knapsack problem, or NULL |
vars | variables in knapsack constraint |
nvars | number of variables in knapsack constraint |
weights | weights of variables in knapsack constraint |
capacity | capacity of knapsack |
sol | primal CIP solution to separate, NULL for current LP solution |
usegubs | should GUB information be used for separation? |
cutoff | pointer to store whether a cutoff has been detected |
ncuts | pointer to add up the number of found cuts |
SCIP_RETCODE SCIPseparateRelaxedKnapsack |
( |
SCIP * |
scip, |
|
|
SCIP_CONS * |
cons, |
|
|
SCIP_SEPA * |
sepa, |
|
|
int |
nknapvars, |
|
|
SCIP_VAR ** |
knapvars, |
|
|
SCIP_Real * |
knapvals, |
|
|
SCIP_Real |
valscale, |
|
|
SCIP_Real |
rhs, |
|
|
SCIP_SOL * |
sol, |
|
|
SCIP_Bool * |
cutoff, |
|
|
int * |
ncuts |
|
) |
| |
- Parameters
-
scip | SCIP data structure |
cons | originating constraint of the knapsack problem, or NULL |
sepa | originating separator of the knapsack problem, or NULL |
nknapvars | number of variables in the continuous knapsack constraint |
knapvars | variables in the continuous knapsack constraint |
knapvals | coefficients of the variables in the continuous knapsack constraint |
valscale | -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise |
rhs | right hand side of the continuous knapsack constraint |
sol | primal CIP solution, NULL for current LP solution |
cutoff | pointer to store whether a cutoff was found |
ncuts | pointer to add up the number of found cuts |
|