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_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)

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrKnapsack ( SCIP * scip )

creates the handler for knapsack constraints and includes it in SCIP

Parameters

scip	SCIP 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

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
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 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

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

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

scip	SCIP data structure
cons	constraint data
var	item variable
weight	item 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

scip	SCIP data structure
cons	constraint 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

scip	SCIP data structure
cons	constraint data
capacity	new 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
	)

gets the number of items in the knapsack constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13291 of file cons_knapsack.c.

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

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

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

scip	SCIP data structure
cons	constraint 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

scip	SCIP data structure
cons	constraint 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

scip	SCIP data structure
cons	constraint 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

scip	SCIP data structure
cons	constraint 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

scip	SCIP data structure
cons	constraint 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

Note: in case you provide the solitems or nonsolitems array you also have to provide the counter part as well

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)

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

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

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

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 SCIP solution to separate, NULL for current LP solution
usegubs	should GUB information be used for separation?
cutoff	whether a cutoff has been detected
ncuts	pointer 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

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

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().

SCIP

Detailed Description

Functions

Function Documentation