Scippy

SCIP

Solving Constraint Integer Programs

cons_knapsack.h File Reference

Detailed Description

Constraint handler for knapsack constraints of the form $a^T x \le b$, x binary and $a \ge 0$.

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

\[ \sum_{i=1}^n a_i x_i \leq b \]

with non-negative integer coefficients $a_i$, integer right-hand side $b$, and binary variables $x_i$.

Definition in file cons_knapsack.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions

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_LongintSCIPgetWeightsKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualsolKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualfarkasKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_ROWSCIPgetRowKnapsack (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)
 

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrKnapsack ( SCIP scip)

creates the handler for knapsack constraints and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 13000 of file cons_knapsack.c.

Referenced by SCIPincludeDefaultPlugins().

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of items in the knapsack
varsarray with item variables
weightsarray with item weights
capacitycapacity of knapsack
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 13130 of file cons_knapsack.c.

References consdataCreate(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPconshdlrGetData(), SCIPcreateCons(), SCIPcreateConsBasicKnapsack(), SCIPerrorMessage, and SCIPfindConshdlr().

Referenced by createAndAddLinearCons(), createCapacityRestriction(), createNormalizedKnapsack(), and SCIPcreateConsBasicKnapsack().

SCIP_RETCODE SCIPcreateConsBasicKnapsack ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_Longint weights,
SCIP_Longint  capacity 
)

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of items in the knapsack
varsarray with item variables
weightsarray with item weights
capacitycapacity of knapsack

Definition at line 13198 of file cons_knapsack.c.

References FALSE, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPaddCoefKnapsack(), SCIPcreateConsKnapsack(), and TRUE.

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPcreateConsKnapsack().

SCIP_RETCODE SCIPaddCoefKnapsack ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Longint  weight 
)

adds new item to knapsack constraint

Parameters
scipSCIP data structure
consconstraint data
varitem variable
weightitem weight

Definition at line 13217 of file cons_knapsack.c.

Referenced by addCoefTerm(), createCapacityRestriction(), SCIP_DECL_SOLVECUMULATIVE(), SCIPaddCoefPseudoboolean(), and SCIPcreateConsBasicKnapsack().

SCIP_Longint SCIPgetCapacityKnapsack ( SCIP scip,
SCIP_CONS cons 
)

gets the capacity of the knapsack constraint

Parameters
scipSCIP data structure
consconstraint data

Definition at line 13238 of file cons_knapsack.c.

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

Referenced by addKnapsackConstraints(), checkKnapsack(), getLinearConsSides(), SCIP_DECL_READERWRITE(), SCIPmatrixCreate(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePip(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_RETCODE SCIPchgCapacityKnapsack ( SCIP scip,
SCIP_CONS cons,
SCIP_Longint  capacity 
)

changes capacity of the knapsack constraint

Note
This method can only be called during problem creation stage (SCIP_STAGE_PROBLEM)
Parameters
scipSCIP data structure
consconstraint data
capacitynew capacity of knapsack

Definition at line 13262 of file cons_knapsack.c.

References NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIPconsGetData(), SCIPerrorMessage, SCIPgetNVarsKnapsack(), and SCIPgetStage().

Referenced by SCIPgetCapacityKnapsack().

int SCIPgetNVarsKnapsack ( SCIP scip,
SCIP_CONS cons 
)
SCIP_VAR** SCIPgetVarsKnapsack ( SCIP scip,
SCIP_CONS cons 
)

gets the array of variables in the knapsack constraint; the user must not modify this array!

Parameters
scipSCIP data structure
consconstraint data

Definition at line 13312 of file cons_knapsack.c.

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

Referenced by addKnapsackConstraints(), checkKnapsack(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPgetNVarsKnapsack(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), writeOpbConstraints(), and writeOpbObjective().

SCIP_Longint* SCIPgetWeightsKnapsack ( SCIP scip,
SCIP_CONS cons 
)

gets the array of weights in the knapsack constraint; the user must not modify this array!

Parameters
scipSCIP data structure
consconstraint data

Definition at line 13333 of file cons_knapsack.c.

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

Referenced by addKnapsackConstraints(), checkKnapsack(), getLinearConsVarsData(), SCIP_DECL_READERWRITE(), SCIPgetVarsKnapsack(), SCIPmatrixCreate(), SCIPwriteCcg(), SCIPwriteGms(), SCIPwriteLp(), SCIPwritePbm(), SCIPwritePip(), SCIPwritePpm(), writeFzn(), and writeOpbConstraints().

SCIP_Real SCIPgetDualsolKnapsack ( SCIP scip,
SCIP_CONS cons 
)

gets the dual solution of the knapsack constraint in the current LP

Parameters
scipSCIP data structure
consconstraint data

Definition at line 13354 of file cons_knapsack.c.

References NULL, SCIP_INVALID, SCIP_Real, SCIPABORT, SCIPconsGetData(), SCIPerrorMessage, SCIPgetDualfarkasKnapsack(), and SCIProwGetDualsol().

Referenced by SCIPgetWeightsKnapsack().

SCIP_Real SCIPgetDualfarkasKnapsack ( SCIP scip,
SCIP_CONS cons 
)

gets the dual Farkas value of the knapsack constraint in the current infeasible LP

Parameters
scipSCIP data structure
consconstraint data

Definition at line 13378 of file cons_knapsack.c.

References NULL, SCIP_INVALID, SCIPABORT, SCIPconsGetData(), SCIPerrorMessage, SCIPgetRowKnapsack(), and SCIProwGetDualfarkas().

Referenced by SCIPgetDualsolKnapsack().

SCIP_ROW* SCIPgetRowKnapsack ( SCIP scip,
SCIP_CONS cons 
)

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

Definition at line 13404 of file cons_knapsack.c.

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

Referenced by SCIPgetDualfarkasKnapsack().

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

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

Note
in case you provide the solitems or nonsolitems array you also have to provide the counter part as well
Parameters
scipSCIP data structure
nitemsnumber of available items
weightsitem weights
profitsitem profits
capacitycapacity of knapsack
itemsitem numbers
solitemsarray to store items in solution, or NULL
nonsolitemsarray to store items not in solution, or NULL
nsolitemspointer to store number of items in solution, or NULL
nnonsolitemspointer to store number of items not in solution, or NULL
solvalpointer to store optimal solution value, or NULL
successpointer to store if an error occured during solving(normally a memory problem)

Definition at line 949 of file cons_knapsack.c.

References FALSE, IDX, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_NOMEMORY, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcalcGreComDiv(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPsolveKnapsackApproximately(), SCIPsortDownRealIntLong(), SCIPsortDownRealLongRealInt(), and TRUE.

Referenced by dualPresolving(), getFlowCover(), and getHighestCapacityUsage().

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
scipSCIP data structure
nitemsnumber of available items
weightsitem weights
profitsitem profits
capacitycapacity of knapsack
itemsitem numbers
solitemsarray to store items in solution, or NULL
nonsolitemsarray to store items not in solution, or NULL
nsolitemspointer to store number of items in solution, or NULL
nnonsolitemspointer to store number of items not in solution, or NULL
solvalpointer to store optimal solution value, or NULL

Definition at line 1492 of file cons_knapsack.c.

References checkSolveKnapsack(), NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealLongRealInt().

Referenced by getCover(), and SCIPsolveKnapsackExactly().

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

separates different classes of valid inequalities for the 0-1 knapsack problem

Parameters
scipSCIP data structure
consoriginating constraint of the knapsack problem, or NULL
sepaoriginating separator of the knapsack problem, or NULL
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solprimal SCIP solution to separate, NULL for current LP solution
usegubsshould GUB information be used for separation?
cutoffwhether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 5524 of file cons_knapsack.c.

References FALSE, getCover(), getFeasibleSet(), GUBsetCreate(), GUBsetFree(), GUBsetGetCliquePartition(), makeCoverMinimal(), SCIP_GUBSet::ngubconss, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPdebugMessage, SCIPdebugPrintf, SCIPfreeBufferArray, SCIPgetSolVals(), SCIPincConsAge(), SCIPseparateRelaxedKnapsack(), SCIPvarGetName(), separateSequLiftedMinimalCoverInequality(), separateSupLiftedMinimalCoverInequality(), TRUE, and USESUPADDLIFT.

Referenced by getFeasibleSet(), SCIPseparateRelaxedKnapsack(), and separateCons().

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
scipSCIP data structure
consoriginating constraint of the knapsack problem, or NULL
sepaoriginating separator of the knapsack problem, or NULL
nknapvarsnumber of variables in the continuous knapsack constraint
knapvarsvariables in the continuous knapsack constraint
knapvalscoefficients 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
rhsright hand side of the continuous knapsack constraint
solprimal CIP solution, NULL for current LP solution
cutoffpointer to store whether a cutoff was found
ncutspointer to add up the number of found cuts

Definition at line 5741 of file cons_knapsack.c.

References BMSclearMemoryArray, CONSHDLR_NAME, DEFAULT_USEGUBS, FALSE, KNAPSACKRELAX_MAXDELTA, KNAPSACKRELAX_MAXDNOM, KNAPSACKRELAX_MAXSCALE, MAXABSVBCOEF, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintCons, SCIPdebugPrintf, SCIPepsilon(), SCIPfeasFloor(), SCIPfindConshdlr(), SCIPfloor(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNegatedVar(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPreallocMemoryArray, SCIPseparateKnapsackCuts(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsBinary(), separateCons(), and TRUE.

Referenced by addCut(), and SCIPseparateKnapsackCuts().