Detailed Description

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

Author: Tobias Achterberg; Xin Liu; Kati Wolter; Michael Winkler; Tobias Fischer

#include "blockmemshell/memory.h"
#include "scip/cons_knapsack.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_setppc.h"
#include "scip/pub_cons.h"
#include "scip/pub_event.h"
#include "scip/pub_implics.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <ctype.h>
#include <string.h>

Go to the source code of this file.

Data Structures
struct	SCIP_GUBCons

struct	SCIP_GUBSet

Macros
#define	CONSHDLR_NAME "knapsack"

#define	CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"

#define	CONSHDLR_SEPAPRIORITY +600000

#define	CONSHDLR_ENFOPRIORITY -600000

#define	CONSHDLR_CHECKPRIORITY -600000

#define	CONSHDLR_SEPAFREQ 0

#define	CONSHDLR_PROPFREQ 1

#define	CONSHDLR_EAGERFREQ 100

#define	CONSHDLR_MAXPREROUNDS -1

#define	CONSHDLR_DELAYSEPA FALSE

#define	CONSHDLR_DELAYPROP FALSE

#define	CONSHDLR_NEEDSCONS TRUE

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	EVENTHDLR_NAME "knapsack"

#define	EVENTHDLR_DESC "bound change event handler for knapsack constraints"

#define	EVENTTYPE_KNAPSACK

#define	LINCONSUPGD_PRIORITY +100000

#define	MAX_USECLIQUES_SIZE 1000

#define	MAX_ZEROITEMS_SIZE 10000

#define	KNAPSACKRELAX_MAXDELTA 0.1

#define	KNAPSACKRELAX_MAXDNOM 1000LL

#define	KNAPSACKRELAX_MAXSCALE 1000.0

#define	DEFAULT_SEPACARDFREQ 1

#define	DEFAULT_MAXROUNDS 5

#define	DEFAULT_MAXROUNDSROOT -1

#define	DEFAULT_MAXSEPACUTS 50

#define	DEFAULT_MAXSEPACUTSROOT 200

#define	DEFAULT_MAXCARDBOUNDDIST 0.0

#define	DEFAULT_DISAGGREGATION TRUE

#define	DEFAULT_SIMPLIFYINEQUALITIES TRUE

#define	DEFAULT_NEGATEDCLIQUE TRUE

#define	MAXABSVBCOEF 1e+5

#define	USESUPADDLIFT FALSE

#define	DEFAULT_PRESOLUSEHASHING TRUE

#define	HASHSIZE_KNAPSACKCONS 500

#define	DEFAULT_PRESOLPAIRWISE TRUE

#define	NMINCOMPARISONS 200000

#define	MINGAINPERNMINCOMPARISONS 1e-06

#define	DEFAULT_DUALPRESOLVING TRUE

#define	DEFAULT_DETECTCUTOFFBOUND TRUE

#define	DEFAULT_DETECTLOWERBOUND TRUE

#define	DEFAULT_CLIQUEEXTRACTFACTOR 0.5

#define	MAXCOVERSIZEITERLEWI 1000

#define	DEFAULT_USEGUBS FALSE

#define	GUBCONSGROWVALUE 6

#define	GUBSPLITGNC1GUBS FALSE

#define	DEFAULT_CLQPARTUPDATEFAC 1.5

#define	DEFAULT_UPDATECLIQUEPARTITIONS FALSE

#define	MAXNCLIQUEVARSCOMP 1000000

#define	IDX(j, d) ((j)*(intcap)+(d))

#define	MAX_CLIQUELENGTH 50

Typedefs
typedef struct sortkeypair	SORTKEYPAIR

typedef enum GUBVarstatus	GUBVARSTATUS

typedef enum GUBConsstatus	GUBCONSSTATUS

typedef struct SCIP_GUBCons	SCIP_GUBCONS

typedef struct SCIP_GUBSet	SCIP_GUBSET

Enumerations
enum	GUBVarstatus { GUBVARSTATUS_UNINITIAL = -1, GUBVARSTATUS_CAPACITYEXCEEDED = 0, GUBVARSTATUS_BELONGSTOSET_R = 1, GUBVARSTATUS_BELONGSTOSET_F = 2, GUBVARSTATUS_BELONGSTOSET_C2 = 3, GUBVARSTATUS_BELONGSTOSET_C1 = 4 }

enum	GUBConsstatus { GUBCONSSTATUS_UNINITIAL = -1, GUBCONSSTATUS_BELONGSTOSET_GR = 0, GUBCONSSTATUS_BELONGSTOSET_GF = 1, GUBCONSSTATUS_BELONGSTOSET_GC2 = 2, GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, GUBCONSSTATUS_BELONGSTOSET_GOC1 = 4 }

Functions
static	SCIP_DECL_SORTPTRCOMP (compSortkeypairs)

static SCIP_RETCODE	eventdataCreate (SCIP scip, SCIP_EVENTDATA eventdata, SCIP_CONS cons, SCIP_Longint weight)

static SCIP_RETCODE	eventdataFree (SCIP scip, SCIP_EVENTDATA *eventdata)

static void	sortItems (SCIP_CONSDATA *consdata)

static SCIP_RETCODE	calcCliquepartition (SCIP scip, SCIP_CONSHDLRDATA conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)

static SCIP_RETCODE	lockRounding (SCIP scip, SCIP_CONS cons, SCIP_VAR *var)

static SCIP_RETCODE	unlockRounding (SCIP scip, SCIP_CONS cons, SCIP_VAR *var)

static SCIP_RETCODE	catchEvents (SCIP scip, SCIP_CONS cons, SCIP_CONSDATA consdata, SCIP_EVENTHDLR eventhdlr)

static SCIP_RETCODE	dropEvents (SCIP scip, SCIP_CONSDATA consdata, SCIP_EVENTHDLR *eventhdlr)

static SCIP_RETCODE	consdataEnsureVarsSize (SCIP scip, SCIP_CONSDATA consdata, int num, SCIP_Bool transformed)

static void	updateWeightSums (SCIP_CONSDATA consdata, SCIP_VAR var, SCIP_Longint weightdelta)

static SCIP_RETCODE	consdataCreate (SCIP scip, SCIP_CONSDATA consdata, int nvars, SCIP_VAR vars, SCIP_Longint weights, SCIP_Longint capacity)

static SCIP_RETCODE	consdataFree (SCIP scip, SCIP_CONSDATA consdata, SCIP_EVENTHDLR eventhdlr)

static void	consdataChgWeight (SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight)

static SCIP_RETCODE	createRelaxation (SCIP scip, SCIP_CONS cons)

static SCIP_RETCODE	addRelaxation (SCIP scip, SCIP_CONS cons, SCIP_Bool *cutoff)

static SCIP_RETCODE	addNlrow (SCIP scip, SCIP_CONS cons)

static SCIP_RETCODE	checkCons (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool violated)

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)

static SCIP_RETCODE	GUBconsCreate (SCIP scip, SCIP_GUBCONS *gubcons)

static void	GUBconsFree (SCIP scip, SCIP_GUBCONS *gubcons)

static SCIP_RETCODE	GUBconsAddVar (SCIP scip, SCIP_GUBCONS gubcons, int var)

static SCIP_RETCODE	GUBconsDelVar (SCIP scip, SCIP_GUBCONS gubcons, int var, int gubvarsidx)

static SCIP_RETCODE	GUBsetMoveVar (SCIP scip, SCIP_GUBSET gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons)

static void	GUBsetSwapVars (SCIP scip, SCIP_GUBSET gubset, int var1, int var2)

static SCIP_RETCODE	GUBsetCreate (SCIP scip, SCIP_GUBSET gubset, int nvars, SCIP_Longint weights, SCIP_Longint capacity)

static void	GUBsetFree (SCIP scip, SCIP_GUBSET *gubset)

static SCIP_RETCODE	GUBsetCheck (SCIP scip, SCIP_GUBSET gubset, SCIP_VAR **vars)

static SCIP_RETCODE	GUBsetCalcCliquePartition (SCIP const scip, SCIP_VAR const vars, int const nvars, int const cliquepartition, int const ncliques, SCIP_Real solvals)

static SCIP_RETCODE	GUBsetGetCliquePartition (SCIP scip, SCIP_GUBSET gubset, SCIP_VAR *vars, SCIP_Real solvals)

static SCIP_RETCODE	getCover (SCIP scip, SCIP_VAR vars, int nvars, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int covervars, int noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Bool found, SCIP_Bool modtransused, int ntightened, SCIP_Bool *fractional)

static SCIP_Bool	checkMinweightidx (SCIP_Longint weights, SCIP_Longint capacity, int covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j)

static void	getPartitionCovervars (SCIP scip, SCIP_Real solvals, int covervars, int ncovervars, int varsC1, int varsC2, int nvarsC1, int *nvarsC2)

static SCIP_RETCODE	changePartitionCovervars (SCIP scip, SCIP_Longint weights, int varsC1, int varsC2, int nvarsC1, int nvarsC2)

static SCIP_RETCODE	changePartitionFeasiblesetvars (SCIP scip, SCIP_Longint weights, int varsC1, int varsC2, int nvarsC1, int nvarsC2)

static void	getPartitionNoncovervars (SCIP scip, SCIP_Real solvals, int noncovervars, int nnoncovervars, int varsF, int varsR, int nvarsF, int *nvarsR)

static SCIP_RETCODE	getLiftingSequence (SCIP scip, SCIP_Real solvals, SCIP_Longint weights, int varsF, int varsC2, int varsR, int nvarsF, int nvarsC2, int nvarsR)

static SCIP_RETCODE	getLiftingSequenceGUB (SCIP scip, SCIP_GUBSET gubset, SCIP_Real solvals, SCIP_Longint weights, int varsC1, int varsC2, int varsF, int varsR, int nvarsC1, int nvarsC2, int nvarsF, int nvarsR, int gubconsGC1, int gubconsGC2, int gubconsGFC1, int gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int ngubconscapexceed, int maxgubvarssize)

static SCIP_RETCODE	enlargeMinweights (SCIP scip, SCIP_Longint minweightsptr, int minweightslen, int *minweightssize, int newlen)

static SCIP_RETCODE	sequentialUpAndDownLifting (SCIP scip, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int varsM1, int varsM2, int varsF, int varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int liftcoefs, SCIP_Real cutact, int liftrhs)

static SCIP_Longint	safeAddMinweightsGUB (SCIP_Longint val1, SCIP_Longint val2)

static void	computeMinweightsGUB (SCIP_Longint minweights, SCIP_Longint finished, SCIP_Longint *unfinished, int minweightslen)

static SCIP_RETCODE	sequentialUpAndDownLiftingGUB (SCIP scip, SCIP_GUBSET gubset, SCIP_VAR *vars, int ngubconscapexceed, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int gubconsGC1, int gubconsGC2, int gubconsGFC1, int gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int alpha0, int liftcoefs, SCIP_Real cutact, int liftrhs, int maxgubvarssize)

static SCIP_RETCODE	superadditiveUpLifting (SCIP scip, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int covervars, int noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Real liftcoefs, SCIP_Real *cutact)

static SCIP_RETCODE	separateSequLiftedMinimalCoverInequality (SCIP scip, SCIP_CONS cons, SCIP_SEPA sepa, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int mincovervars, int nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_SOL sol, SCIP_GUBSET gubset, SCIP_Bool cutoff, int *ncuts)

static SCIP_RETCODE	separateSequLiftedExtendedWeightInequality (SCIP scip, SCIP_CONS cons, SCIP_SEPA sepa, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int feassetvars, int nonfeassetvars, int nfeassetvars, int nnonfeassetvars, SCIP_SOL sol, SCIP_Bool cutoff, int ncuts)

static SCIP_RETCODE	separateSupLiftedMinimalCoverInequality (SCIP scip, SCIP_CONS cons, SCIP_SEPA sepa, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int mincovervars, int nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_Longint mincoverweight, SCIP_SOL sol, SCIP_Bool cutoff, int ncuts)

static SCIP_RETCODE	makeCoverMinimal (SCIP scip, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int covervars, int noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Bool modtransused)

static SCIP_RETCODE	getFeasibleSet (SCIP scip, SCIP_CONS cons, SCIP_SEPA sepa, SCIP_VAR vars, int nvars, int ntightened, SCIP_Longint weights, SCIP_Longint capacity, SCIP_Real solvals, int covervars, int noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Bool modtransused, SCIP_SOL sol, SCIP_Bool cutoff, int *ncuts)

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)

static SCIP_RETCODE	separateCons (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool cutoff, int *ncuts)

static SCIP_RETCODE	addCoef (SCIP scip, SCIP_CONS cons, SCIP_VAR *var, SCIP_Longint weight)

static SCIP_RETCODE	delCoefPos (SCIP scip, SCIP_CONS cons, int pos)

static SCIP_RETCODE	removeZeroWeights (SCIP scip, SCIP_CONS cons)

static SCIP_RETCODE	performVarDeletions (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONS **conss, int nconss)

static SCIP_RETCODE	mergeMultiples (SCIP scip, SCIP_CONS cons, SCIP_Bool *cutoff)

static SCIP_RETCODE	dualPresolving (SCIP scip, SCIP_CONS cons, int nfixedvars, int ndelconss, SCIP_Bool *deleted)

static SCIP_RETCODE	checkParallelObjective (SCIP scip, SCIP_CONS cons, SCIP_CONSHDLRDATA *conshdlrdata)

static SCIP_RETCODE	stableSort (SCIP scip, SCIP_CONSDATA consdata, SCIP_VAR *vars, SCIP_Longint weights, int *cliquestartposs, SCIP_Bool usenegatedclique)

static SCIP_RETCODE	applyFixings (SCIP scip, SCIP_CONS cons, SCIP_Bool *cutoff)

static SCIP_RETCODE	propagateCons (SCIP scip, SCIP_CONS cons, SCIP_Bool cutoff, SCIP_Bool redundant, int *nfixedvars, SCIP_Bool usenegatedclique)

static SCIP_RETCODE	upgradeCons (SCIP scip, SCIP_CONS cons, int ndelconss, int naddconss)

static SCIP_RETCODE	deleteRedundantVars (SCIP scip, SCIP_CONS cons, SCIP_Longint frontsum, int splitpos, int nchgcoefs, int nchgsides, int *naddconss)

static SCIP_RETCODE	detectRedundantVars (SCIP scip, SCIP_CONS cons, int ndelconss, int nchgcoefs, int nchgsides, int naddconss)

static void	normalizeWeights (SCIP_CONS cons, int nchgcoefs, int *nchgsides)

static SCIP_RETCODE	dualWeightsTightening (SCIP scip, SCIP_CONS cons, int ndelconss, int nchgcoefs, int nchgsides, int naddconss)

static SCIP_RETCODE	prepareCons (SCIP scip, SCIP_CONS cons, int nfixedvars, int ndelconss, int *nchgcoefs)

static SCIP_RETCODE	simplifyInequalities (SCIP scip, SCIP_CONS cons, int nfixedvars, int ndelconss, int nchgcoefs, int nchgsides, int naddconss, SCIP_Bool cutoff)

static SCIP_RETCODE	insertZerolist (SCIP scip, int liftcands, int nliftcands, int firstidxs, SCIP_Longint zeroweightsums, int zeroitems, int nextidxs, int zeroitemssize, int nzeroitems, int probindex, SCIP_Bool value, int knapsackidx, SCIP_Longint knapsackweight, SCIP_Bool *memlimitreached)

static SCIP_RETCODE	tightenWeightsLift (SCIP scip, SCIP_CONS cons, int nchgcoefs, SCIP_Bool cutoff)

static SCIP_RETCODE	tightenWeights (SCIP scip, SCIP_CONS cons, SCIP_PRESOLTIMING presoltiming, int nchgcoefs, int nchgsides, int naddconss, int ndelconss, SCIP_Bool *cutoff)

static SCIP_RETCODE	addNegatedCliques (SCIP const scip, SCIP_CONS const cons, SCIP_Bool const cutoff, int const nbdchgs)

static SCIP_RETCODE	greedyCliqueAlgorithm (SCIP const scip, SCIP_VAR items, SCIP_Longint weights, int nitems, SCIP_Longint capacity, SCIP_Bool sorteditems, SCIP_Real cliqueextractfactor, SCIP_Bool const cutoff, int const nbdchgs)

static SCIP_RETCODE	addCliques (SCIP const scip, SCIP_CONS const cons, SCIP_Real cliqueextractfactor, SCIP_Bool const cutoff, int const nbdchgs)

static	SCIP_DECL_HASHGETKEY (hashGetKeyKnapsackcons)

static	SCIP_DECL_HASHKEYEQ (hashKeyEqKnapsackcons)

static	SCIP_DECL_HASHKEYVAL (hashKeyValKnapsackcons)

static SCIP_RETCODE	detectRedundantConstraints (SCIP scip, BMS_BLKMEM blkmem, SCIP_CONS *conss, int nconss, SCIP_Bool cutoff, int *ndelconss)

static SCIP_RETCODE	preprocessConstraintPairs (SCIP scip, SCIP_CONS conss, int firstchange, int chkind, int ndelconss)

static SCIP_RETCODE	enforceConstraint (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONS *conss, int nconss, int nusefulconss, SCIP_SOL sol, SCIP_RESULT *result)

static SCIP_RETCODE	createNormalizedKnapsack (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, 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)

static	SCIP_DECL_LINCONSUPGD (linconsUpgdKnapsack)

static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyKnapsack)

static	SCIP_DECL_CONSFREE (consFreeKnapsack)

static	SCIP_DECL_CONSINIT (consInitKnapsack)

static	SCIP_DECL_CONSEXIT (consExitKnapsack)

static	SCIP_DECL_CONSINITPRE (consInitpreKnapsack)

static	SCIP_DECL_CONSEXITPRE (consExitpreKnapsack)

static	SCIP_DECL_CONSINITSOL (consInitsolKnapsack)

static	SCIP_DECL_CONSEXITSOL (consExitsolKnapsack)

static	SCIP_DECL_CONSDELETE (consDeleteKnapsack)

static	SCIP_DECL_CONSTRANS (consTransKnapsack)

static	SCIP_DECL_CONSINITLP (consInitlpKnapsack)

static	SCIP_DECL_CONSSEPALP (consSepalpKnapsack)

static	SCIP_DECL_CONSSEPASOL (consSepasolKnapsack)

static	SCIP_DECL_CONSENFOLP (consEnfolpKnapsack)

static	SCIP_DECL_CONSENFORELAX (consEnforelaxKnapsack)

static	SCIP_DECL_CONSENFOPS (consEnfopsKnapsack)

static	SCIP_DECL_CONSCHECK (consCheckKnapsack)

static	SCIP_DECL_CONSPROP (consPropKnapsack)

static	SCIP_DECL_CONSPRESOL (consPresolKnapsack)

static	SCIP_DECL_CONSRESPROP (consRespropKnapsack)

static	SCIP_DECL_CONSLOCK (consLockKnapsack)

static	SCIP_DECL_CONSACTIVE (consActiveKnapsack)

static	SCIP_DECL_CONSDEACTIVE (consDeactiveKnapsack)

static	SCIP_DECL_CONSDELVARS (consDelvarsKnapsack)

static	SCIP_DECL_CONSPRINT (consPrintKnapsack)

static	SCIP_DECL_CONSCOPY (consCopyKnapsack)

static	SCIP_DECL_CONSPARSE (consParseKnapsack)

static	SCIP_DECL_CONSGETVARS (consGetVarsKnapsack)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsKnapsack)

static	SCIP_DECL_EVENTEXEC (eventExecKnapsack)

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	SCIPcleanupConssKnapsack (SCIP scip, SCIP_Bool onlychecked, SCIP_Bool infeasible)

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "knapsack"

Definition at line 79 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSEXITSOL(), SCIP_DECL_LINCONSUPGD(), SCIPcreateConsKnapsack(), and SCIPseparateRelaxedKnapsack().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"

Definition at line 80 of file cons_knapsack.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY +600000

priority of the constraint handler for separation

Definition at line 81 of file cons_knapsack.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY -600000

priority of the constraint handler for constraint enforcing

Definition at line 82 of file cons_knapsack.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -600000

priority of the constraint handler for checking feasibility

Definition at line 83 of file cons_knapsack.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 0

frequency for separating cuts; zero means to separate only in the root node

Definition at line 84 of file cons_knapsack.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 85 of file cons_knapsack.c.

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ 100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 86 of file cons_knapsack.c.

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 89 of file cons_knapsack.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 90 of file cons_knapsack.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 91 of file cons_knapsack.c.

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 92 of file cons_knapsack.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

Definition at line 94 of file cons_knapsack.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 95 of file cons_knapsack.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "knapsack"

Definition at line 97 of file cons_knapsack.c.

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"

Definition at line 98 of file cons_knapsack.c.

◆ EVENTTYPE_KNAPSACK

#define EVENTTYPE_KNAPSACK

Value:

SCIP_EVENTTYPE_LBCHANGED \
                         | SCIP_EVENTTYPE_UBTIGHTENED \
                         | SCIP_EVENTTYPE_VARFIXED \
                         | SCIP_EVENTTYPE_VARDELETED \
                         | SCIP_EVENTTYPE_IMPLADDED

variable events that should be caught by the event handler

Definition at line 99 of file cons_knapsack.c.

◆ LINCONSUPGD_PRIORITY

#define LINCONSUPGD_PRIORITY +100000

priority of the constraint handler for upgrading of linear constraints

Definition at line 105 of file cons_knapsack.c.

◆ MAX_USECLIQUES_SIZE

#define MAX_USECLIQUES_SIZE 1000

maximal number of items in knapsack where clique information is used

Definition at line 107 of file cons_knapsack.c.

Referenced by tightenWeights().

◆ MAX_ZEROITEMS_SIZE

#define MAX_ZEROITEMS_SIZE 10000

maximal number of items to store in the zero list in preprocessing

Definition at line 108 of file cons_knapsack.c.

Referenced by insertZerolist().

◆ KNAPSACKRELAX_MAXDELTA

#define KNAPSACKRELAX_MAXDELTA 0.1

maximal allowed rounding distance for scaling in knapsack relaxation

Definition at line 110 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ KNAPSACKRELAX_MAXDNOM

#define KNAPSACKRELAX_MAXDNOM 1000LL

maximal allowed denominator in knapsack rational relaxation

Definition at line 111 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ KNAPSACKRELAX_MAXSCALE

#define KNAPSACKRELAX_MAXSCALE 1000.0

maximal allowed scaling factor in knapsack rational relaxation

Definition at line 112 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ DEFAULT_SEPACARDFREQ

#define DEFAULT_SEPACARDFREQ 1

multiplier on separation frequency, how often knapsack cuts are separated

Definition at line 114 of file cons_knapsack.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 5

maximal number of separation rounds per node (-1: unlimited)

Definition at line 115 of file cons_knapsack.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 116 of file cons_knapsack.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 50

maximal number of cuts separated per separation round

Definition at line 117 of file cons_knapsack.c.

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT 200

maximal number of cuts separated per separation round in the root node

Definition at line 118 of file cons_knapsack.c.

◆ DEFAULT_MAXCARDBOUNDDIST

#define DEFAULT_MAXCARDBOUNDDIST 0.0

maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts

Definition at line 119 of file cons_knapsack.c.

◆ DEFAULT_DISAGGREGATION

#define DEFAULT_DISAGGREGATION TRUE

should disaggregation of knapsack constraints be allowed in preprocessing?

Definition at line 122 of file cons_knapsack.c.

◆ DEFAULT_SIMPLIFYINEQUALITIES

#define DEFAULT_SIMPLIFYINEQUALITIES TRUE

should presolving try to simplify knapsacks

Definition at line 123 of file cons_knapsack.c.

◆ DEFAULT_NEGATEDCLIQUE

#define DEFAULT_NEGATEDCLIQUE TRUE

should negated clique information be used in solving process

Definition at line 124 of file cons_knapsack.c.

◆ MAXABSVBCOEF

#define MAXABSVBCOEF 1e+5

maximal absolute coefficient in variable bounds used for knapsack relaxation

Definition at line 126 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ USESUPADDLIFT

#define USESUPADDLIFT FALSE

should lifted minimal cover inequalities using superadditive up-lifting be separated in addition

Definition at line 127 of file cons_knapsack.c.

Referenced by SCIPseparateKnapsackCuts().

◆ DEFAULT_PRESOLUSEHASHING

#define DEFAULT_PRESOLUSEHASHING TRUE

should hash table be used for detecting redundant constraints in advance

Definition at line 129 of file cons_knapsack.c.

◆ HASHSIZE_KNAPSACKCONS

#define HASHSIZE_KNAPSACKCONS 500

minimal size of hash table in linear constraint tables

Definition at line 130 of file cons_knapsack.c.

Referenced by detectRedundantConstraints().

◆ DEFAULT_PRESOLPAIRWISE

#define DEFAULT_PRESOLPAIRWISE TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 132 of file cons_knapsack.c.

◆ NMINCOMPARISONS

#define NMINCOMPARISONS 200000

number for minimal pairwise presolving comparisons

Definition at line 133 of file cons_knapsack.c.

◆ MINGAINPERNMINCOMPARISONS

#define MINGAINPERNMINCOMPARISONS 1e-06

minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round

Definition at line 134 of file cons_knapsack.c.

◆ DEFAULT_DUALPRESOLVING

#define DEFAULT_DUALPRESOLVING TRUE

should dual presolving steps be performed?

Definition at line 137 of file cons_knapsack.c.

◆ DEFAULT_DETECTCUTOFFBOUND

#define DEFAULT_DETECTCUTOFFBOUND TRUE

should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP

Definition at line 138 of file cons_knapsack.c.

◆ DEFAULT_DETECTLOWERBOUND

#define DEFAULT_DETECTLOWERBOUND TRUE

should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP

Definition at line 143 of file cons_knapsack.c.

◆ DEFAULT_CLIQUEEXTRACTFACTOR

#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5

lower clique size limit for greedy clique extraction algorithm (relative to largest clique)

Definition at line 148 of file cons_knapsack.c.

◆ MAXCOVERSIZEITERLEWI

#define MAXCOVERSIZEITERLEWI 1000

maximal size for which LEWI are iteratively separated by reducing the feasible set

Definition at line 149 of file cons_knapsack.c.

Referenced by getFeasibleSet().

◆ DEFAULT_USEGUBS

#define DEFAULT_USEGUBS FALSE

should GUB information be used for separation?

Definition at line 151 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ GUBCONSGROWVALUE

#define GUBCONSGROWVALUE 6

memory growing value for GUB constraint array

Definition at line 152 of file cons_knapsack.c.

◆ GUBSPLITGNC1GUBS

#define GUBSPLITGNC1GUBS FALSE

should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss?

Definition at line 153 of file cons_knapsack.c.

◆ DEFAULT_CLQPARTUPDATEFAC

#define DEFAULT_CLQPARTUPDATEFAC 1.5

factor on the growth of global cliques to decide when to update a previous (negated) clique partition (used only if updatecliquepartitions is set to TRUE)

Definition at line 154 of file cons_knapsack.c.

◆ DEFAULT_UPDATECLIQUEPARTITIONS

#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE

should clique partition information be updated when old partition seems outdated?

Definition at line 157 of file cons_knapsack.c.

◆ MAXNCLIQUEVARSCOMP

#define MAXNCLIQUEVARSCOMP 1000000

limit on number of pairwise comparisons in clique partitioning algorithm

Definition at line 158 of file cons_knapsack.c.

Referenced by GUBsetCalcCliquePartition().

◆ IDX

#define IDX	(	j,
		d
	)	((j)*(intcap)+(d))

Definition at line 1079 of file cons_knapsack.c.

Referenced by SCIPsolveKnapsackExactly().

◆ MAX_CLIQUELENGTH

#define MAX_CLIQUELENGTH 50

Definition at line 9788 of file cons_knapsack.c.

Typedef Documentation

◆ SORTKEYPAIR

typedef struct sortkeypair SORTKEYPAIR

Definition at line 275 of file cons_knapsack.c.

◆ GUBVARSTATUS

typedef enum GUBVarstatus GUBVARSTATUS

Definition at line 287 of file cons_knapsack.c.

◆ GUBCONSSTATUS

typedef enum GUBConsstatus GUBCONSSTATUS

Definition at line 299 of file cons_knapsack.c.

◆ SCIP_GUBCONS

typedef struct SCIP_GUBCons SCIP_GUBCONS

Definition at line 309 of file cons_knapsack.c.

◆ SCIP_GUBSET

typedef struct SCIP_GUBSet SCIP_GUBSET

Definition at line 321 of file cons_knapsack.c.

Enumeration Type Documentation

◆ GUBVarstatus

enum GUBVarstatus

status of GUB constraint

Enumerator
GUBVARSTATUS_UNINITIAL
GUBVARSTATUS_CAPACITYEXCEEDED	unintitialized variable status
GUBVARSTATUS_BELONGSTOSET_R	variable with weight exceeding the knapsack capacity
GUBVARSTATUS_BELONGSTOSET_F	variable in noncovervars R
GUBVARSTATUS_BELONGSTOSET_C2	variable in noncovervars F
GUBVARSTATUS_BELONGSTOSET_C1	variable in covervars C2

Definition at line 278 of file cons_knapsack.c.

◆ GUBConsstatus

enum GUBConsstatus

status of variable in GUB constraint

Enumerator
GUBCONSSTATUS_UNINITIAL
GUBCONSSTATUS_BELONGSTOSET_GR	unintitialized GUB constraint status
GUBCONSSTATUS_BELONGSTOSET_GF	all GUB variables are in noncovervars R
GUBCONSSTATUS_BELONGSTOSET_GC2	all GUB variables are in noncovervars F (and noncovervars R)
GUBCONSSTATUS_BELONGSTOSET_GNC1	all GUB variables are in covervars C2
GUBCONSSTATUS_BELONGSTOSET_GOC1	some GUB variables are in covervars C1, others in noncovervars R or F

Definition at line 290 of file cons_knapsack.c.

Function Documentation

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compSortkeypairs )

static

comparison method for two sorting key pairs

Definition at line 329 of file cons_knapsack.c.

References NULL.

◆ eventdataCreate()

static SCIP_RETCODE eventdataCreate	(	SCIP *	scip,
		SCIP_EVENTDATA **	eventdata,
		SCIP_CONS *	cons,
		SCIP_Longint	weight
	)

static

creates event data

Parameters

scip	SCIP data structure
eventdata	pointer to store event data
cons	constraint
weight	weight of variable

Definition at line 348 of file cons_knapsack.c.

◆ eventdataFree()

static SCIP_RETCODE eventdataFree	(	SCIP *	scip,
		SCIP_EVENTDATA **	eventdata
	)

static

frees event data

Parameters

scip	SCIP data structure
eventdata	pointer to event data

Definition at line 366 of file cons_knapsack.c.

References NULL.

◆ sortItems()

static void sortItems ( SCIP_CONSDATA * consdata )

static

sorts items in knapsack with nonincreasing weights

Parameters

consdata constraint data

Definition at line 380 of file cons_knapsack.c.

Referenced by propagateCons(), and tightenWeights().

◆ calcCliquepartition()

static SCIP_RETCODE calcCliquepartition	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_CONSDATA *	consdata,
		SCIP_Bool	normalclique,
		SCIP_Bool	negatedclique
	)

static

calculates a partition of the variables into cliques

Parameters

scip	SCIP data structure
conshdlrdata	knapsack constraint handler data
consdata	constraint data
normalclique	Should normal cliquepartition be created?
negatedclique	Should negated cliquepartition be created?

Definition at line 480 of file cons_knapsack.c.

Referenced by detectRedundantVars(), propagateCons(), and tightenWeights().

◆ lockRounding()

static SCIP_RETCODE lockRounding	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

static

installs rounding locks for the given variable in the given knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint
var	variable of constraint entry

Definition at line 522 of file cons_knapsack.c.

References FALSE, SCIP_CALL, SCIPunlockVarCons(), and TRUE.

◆ unlockRounding()

static SCIP_RETCODE unlockRounding	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

static

removes rounding locks for the given variable in the given knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint
var	variable of constraint entry

Definition at line 535 of file cons_knapsack.c.

◆ catchEvents()

static SCIP_RETCODE catchEvents	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

catches bound change events for variables in knapsack

Parameters

scip	SCIP data structure
cons	constraint
consdata	constraint data
eventhdlr	event handler to call for the event processing

Definition at line 548 of file cons_knapsack.c.

Referenced by SCIPcreateConsKnapsack().

◆ dropEvents()

static SCIP_RETCODE dropEvents	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

drops bound change events for variables in knapsack

Parameters

scip	SCIP data structure
consdata	constraint data
eventhdlr	event handler to call for the event processing

Definition at line 575 of file cons_knapsack.c.

Referenced by consdataFree().

◆ consdataEnsureVarsSize()

static SCIP_RETCODE consdataEnsureVarsSize	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		int	num,
		SCIP_Bool	transformed
	)

static

ensures, that vars and vals arrays can store at least num entries

Parameters

scip	SCIP data structure
consdata	knapsack constraint data
num	minimum number of entries to store
transformed	is constraint from transformed problem?

Definition at line 600 of file cons_knapsack.c.

◆ updateWeightSums()

static void updateWeightSums	(	SCIP_CONSDATA *	consdata,
		SCIP_VAR *	var,
		SCIP_Longint	weightdelta
	)

static

updates all weight sums for fixed and unfixed variables

Parameters

consdata	knapsack constraint data
var	variable for this weight
weightdelta	difference between the old and the new weight of the variable

Definition at line 638 of file cons_knapsack.c.

Referenced by consdataCreate().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity
	)

static

creates knapsack constraint data

Parameters

scip	SCIP data structure
consdata	pointer to store constraint data
nvars	number of variables in knapsack
vars	variables of knapsack
weights	weights of knapsack items
capacity	capacity of knapsack

Definition at line 658 of file cons_knapsack.c.

References consdataFree(), FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureVar(), SCIPduplicateBlockMemoryArray, SCIPfreeBufferArray, SCIPgetTransformedVars(), SCIPisConsCompressionEnabled(), SCIPisTransformed(), SCIPvarGetLbGlobal(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and updateWeightSums().

Referenced by SCIPcreateConsKnapsack().

◆ consdataFree()

static SCIP_RETCODE consdataFree	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

frees knapsack constraint data

Parameters

scip	SCIP data structure
consdata	pointer to the constraint data
eventhdlr	event handler to call for the event processing

Definition at line 784 of file cons_knapsack.c.

References consdataChgWeight(), dropEvents(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseNlRow(), SCIPreleaseRow(), and SCIPreleaseVar().

Referenced by consdataCreate().

◆ consdataChgWeight()

static void consdataChgWeight	(	SCIP_CONSDATA *	consdata,
		int	item,
		SCIP_Longint	newweight
	)

static

changes a single weight in knapsack constraint data

Parameters

consdata	knapsack constraint data
item	item number
newweight	new weight of item

Definition at line 838 of file cons_knapsack.c.

Referenced by consdataFree(), deleteRedundantVars(), dualWeightsTightening(), simplifyInequalities(), and tightenWeights().

◆ createRelaxation()

static SCIP_RETCODE createRelaxation	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

creates LP row corresponding to knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint

Definition at line 876 of file cons_knapsack.c.

◆ addRelaxation()

static SCIP_RETCODE addRelaxation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	cutoff
	)

static

adds linear relaxation of knapsack constraint to the LP

Parameters

scip	SCIP data structure
cons	knapsack constraint
cutoff	whether a cutoff has been detected

Definition at line 904 of file cons_knapsack.c.

Referenced by enforceConstraint(), and separateCons().

◆ addNlrow()

static SCIP_RETCODE addNlrow	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

adds knapsack constraint as row to the NLP, if not added yet

Parameters

scip	SCIP data structure
cons	knapsack constraint

Definition at line 938 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSINITSOL(), and SCIP_DECL_CONSLOCK().

◆ checkCons()

static SCIP_RETCODE checkCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool	checklprows,
		SCIP_Bool	printreason,
		SCIP_Bool *	violated
	)

static

checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible

Parameters

scip	SCIP data structure
cons	constraint to check
sol	solution to check, NULL for current solution
checklprows	Do constraints represented by rows in the current LP have to be checked?
printreason	Should the reason for the violation be printed?
violated	pointer to store whether the constraint is violated

Definition at line 982 of file cons_knapsack.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPincConsAge(), SCIPinfoMessage(), SCIPisFeasPositive(), SCIPisHugeValue(), SCIPprintCons(), SCIPrelDiff(), SCIPresetConsAge(), SCIProwIsInLP(), SCIPupdateSolLPConsViolation(), SCIPvarIsBinary(), and TRUE.

Referenced by enforceConstraint(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFORELAX(), and separateCons().

◆ GUBconsCreate()

static SCIP_RETCODE GUBconsCreate	(	SCIP *	scip,
		SCIP_GUBCONS **	gubcons
	)

static

creates an empty GUB constraint

Parameters

scip	SCIP data structure
gubcons	pointer to store GUB constraint data

Definition at line 1742 of file cons_knapsack.c.

Referenced by getLiftingSequenceGUB(), and SCIPsolveKnapsackApproximately().

◆ GUBconsFree()

static void GUBconsFree	(	SCIP *	scip,
		SCIP_GUBCONS **	gubcons
	)

static

frees GUB constraint

Parameters

scip	SCIP data structure
gubcons	pointer to GUB constraint data structure

Definition at line 1763 of file cons_knapsack.c.

Referenced by GUBsetMoveVar().

◆ GUBconsAddVar()

static SCIP_RETCODE GUBconsAddVar	(	SCIP *	scip,
		SCIP_GUBCONS *	gubcons,
		int	var
	)

static

adds variable to given GUB constraint

Parameters

scip	SCIP data structure
gubcons	GUB constraint data
var	index of given variable in knapsack constraint

Definition at line 1781 of file cons_knapsack.c.

Referenced by GUBsetMoveVar().

◆ GUBconsDelVar()

static SCIP_RETCODE GUBconsDelVar	(	SCIP *	scip,
		SCIP_GUBCONS *	gubcons,
		int	var,
		int	gubvarsidx
	)

static

deletes variable from its current GUB constraint

Parameters

scip	SCIP data structure
gubcons	GUB constraint data
var	index of given variable in knapsack constraint
gubvarsidx	index of the variable in its current GUB constraint

Definition at line 1816 of file cons_knapsack.c.

Referenced by GUBsetMoveVar().

◆ GUBsetMoveVar()

static SCIP_RETCODE GUBsetMoveVar	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		SCIP_VAR **	vars,
		int	var,
		int	oldgubcons,
		int	newgubcons
	)

static

moves variable from current GUB constraint to a different existing (nonempty) GUB constraint

Parameters

scip	SCIP data structure
gubset	GUB set data structure
vars	variables in knapsack constraint
var	index of given variable in knapsack constraint
oldgubcons	index of old GUB constraint of given variable
newgubcons	index of new GUB constraint of given variable

Definition at line 1853 of file cons_knapsack.c.

References GUBconsAddVar(), GUBconsDelVar(), GUBconsFree(), SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, SCIP_GUBSet::gubconsstatus, GUBsetSwapVars(), SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPvarGetName().

Referenced by getLiftingSequenceGUB().

◆ GUBsetSwapVars()

static void GUBsetSwapVars	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		int	var1,
		int	var2
	)

static

swaps two variables in the same GUB constraint

Parameters

scip	SCIP data structure
gubset	GUB set data structure
var1	first variable to be swapped
var2	second variable to be swapped

Definition at line 1944 of file cons_knapsack.c.

Referenced by getLiftingSequenceGUB(), and GUBsetMoveVar().

◆ GUBsetCreate()

static SCIP_RETCODE GUBsetCreate	(	SCIP *	scip,
		SCIP_GUBSET **	gubset,
		int	nvars,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity
	)

static

initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable)

Parameters

scip	SCIP data structure
gubset	pointer to store GUB set data structure
nvars	number of variables in the knapsack constraint
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack

Definition at line 1984 of file cons_knapsack.c.

Referenced by SCIPseparateKnapsackCuts().

◆ GUBsetFree()

static void GUBsetFree	(	SCIP *	scip,
		SCIP_GUBSET **	gubset
	)

static

frees GUB set data structure

Parameters

scip	SCIP data structure
gubset	pointer to GUB set data structure

Definition at line 2033 of file cons_knapsack.c.

Referenced by SCIPseparateKnapsackCuts().

◆ GUBsetCheck()

static SCIP_RETCODE GUBsetCheck	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		SCIP_VAR **	vars
	)

static

checks whether GUB set data structure is consistent

Parameters

scip	SCIP data structure
gubset	GUB set data structure
vars	variables in the knapsack constraint

Definition at line 2065 of file cons_knapsack.c.

◆ GUBsetCalcCliquePartition()

static SCIP_RETCODE GUBsetCalcCliquePartition	(	SCIP *const	scip,
		SCIP_VAR **const	vars,
		int const	nvars,
		int *const	cliquepartition,
		int *const	ncliques,
		SCIP_Real *	solvals
	)

static

calculates a partition of the given set of binary variables into cliques; afterwards the output array contains one value for each variable, such that two variables got the same value iff they were assigned to the same clique; the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of the preceding variables was assigned to clique i-1; note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one variable) and for the remaining variables, a partition with a small number of cliques is constructed

Parameters

scip	SCIP data structure
vars	binary variables in the clique from which at most one can be set to 1
nvars	number of variables in the clique
cliquepartition	array of length nvars to store the clique partition
ncliques	pointer to store number of cliques actually contained in the partition
solvals	solution values of all given binary variables

Definition at line 2150 of file cons_knapsack.c.

References GUBsetGetCliquePartition(), MAXNCLIQUEVARSCOMP, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPsortIntInt(), SCIPvarGetNCliques(), SCIPvarIsActive(), SCIPvarsGetProbvarBinary(), SCIPvarsHaveCommonClique(), and TRUE.

◆ GUBsetGetCliquePartition()

static SCIP_RETCODE GUBsetGetCliquePartition	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		SCIP_VAR **	vars,
		SCIP_Real *	solvals
	)

static

constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs

Parameters

scip	SCIP data structure
gubset	GUB set data structure
vars	variables in the knapsack constraint
solvals	solution values of all knapsack variables

Definition at line 2308 of file cons_knapsack.c.

Referenced by GUBsetCalcCliquePartition(), and SCIPseparateKnapsackCuts().

◆ getCover()

static SCIP_RETCODE getCover	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	covervars,
		int *	noncovervars,
		int *	ncovervars,
		int *	nnoncovervars,
		SCIP_Longint *	coverweight,
		SCIP_Bool *	found,
		SCIP_Bool	modtransused,
		int *	ntightened,
		SCIP_Bool *	fractional
	)

static

gets a most violated cover C ( \(\sum_{j \in C} a_j > a_0\)) for a given knapsack constraint \(\sum_{j \in N} a_j x_j \leq a_0\) taking into consideration the following fixing: \(j \in C\), if \(j \in N_1 = \{j \in N : x^*_j = 1\}\) and \(j \in N \setminus C\), if \(j \in N_0 = \{j \in N : x^*_j = 0\}\), if one exists.

Parameters

scip	SCIP data structure
vars	variables in knapsack constraint
nvars	number of variables in knapsack constraint
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
covervars	pointer to store cover variables
noncovervars	pointer to store noncover variables
ncovervars	pointer to store number of cover variables
nnoncovervars	pointer to store number of noncover variables
coverweight	pointer to store weight of cover
found	pointer to store whether a cover was found
modtransused	should modified transformed separation problem be used to find cover
ntightened	pointer to store number of variables with tightened upper bound
fractional	pointer to store whether the LP sol for knapsack vars is fractional

Definition at line 2405 of file cons_knapsack.c.

References checkMinweightidx(), FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasPositive(), SCIPsolveKnapsackApproximately(), SCIPtightenVarUb(), SCIPvarIsBinary(), and TRUE.

Referenced by SCIPseparateKnapsackCuts().

◆ checkMinweightidx()

static SCIP_Bool checkMinweightidx	(	SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		int *	covervars,
		int	ncovervars,
		SCIP_Longint	coverweight,
		int	minweightidx,
		int	j
	)

static

checks if minweightidx is set correctly

Parameters

weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
covervars	pointer to store cover variables
ncovervars	pointer to store number of cover variables
coverweight	pointer to store weight of cover
minweightidx	index of variable in cover variables with minimum weight
j	current index in cover variables

Definition at line 2636 of file cons_knapsack.c.

References FALSE, getPartitionCovervars(), NULL, SCIP_Longint, SCIP_Real, and TRUE.

Referenced by getCover(), and makeCoverMinimal().

◆ getPartitionCovervars()

static void getPartitionCovervars	(	SCIP *	scip,
		SCIP_Real *	solvals,
		int *	covervars,
		int	ncovervars,
		int *	varsC1,
		int *	varsC2,
		int *	nvarsC1,
		int *	nvarsC2
	)

static

gets partition \((C_1,C_2)\) of minimal cover \(C\), i.e. \(C_1 \cup C_2 = C\) and \(C_1 \cap C_2 = \emptyset\), with \(C_1\) not empty; chooses partition as follows \(C_2 = \{ j \in C : x^*_j = 1 \}\) and \(C_1 = C \setminus C_2\)

Parameters

scip	SCIP data structure
solvals	solution values of all problem variables
covervars	cover variables
ncovervars	number of cover variables
varsC1	pointer to store variables in C1
varsC2	pointer to store variables in C2
nvarsC1	pointer to store number of variables in C1
nvarsC2	pointer to store number of variables in C2

Definition at line 2679 of file cons_knapsack.c.

References changePartitionCovervars(), NULL, SCIP_Longint, SCIPisFeasGT(), SCIPisGE(), and SCIPisLT().

Referenced by checkMinweightidx(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().

◆ changePartitionCovervars()

static SCIP_RETCODE changePartitionCovervars	(	SCIP *	scip,
		SCIP_Longint *	weights,
		int *	varsC1,
		int *	varsC2,
		int *	nvarsC1,
		int *	nvarsC2
	)

static

changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from C2 to C1 if |C1| = 1 and |C1| = 0, respectively.

Parameters

scip	SCIP data structure
weights	weights of variables in knapsack constraint
varsC1	pointer to store variables in C1
varsC2	pointer to store variables in C2
nvarsC1	pointer to store number of variables in C1
nvarsC2	pointer to store number of variables in C2

Definition at line 2728 of file cons_knapsack.c.

References changePartitionFeasiblesetvars(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().

Referenced by getPartitionCovervars(), and separateSequLiftedMinimalCoverInequality().

◆ changePartitionFeasiblesetvars()

static SCIP_RETCODE changePartitionFeasiblesetvars	(	SCIP *	scip,
		SCIP_Longint *	weights,
		int *	varsC1,
		int *	varsC2,
		int *	nvarsC1,
		int *	nvarsC2
	)

static

changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1

Parameters

scip	SCIP data structure
weights	weights of variables in knapsack constraint
varsC1	pointer to store variables in C1
varsC2	pointer to store variables in C2
nvarsC1	pointer to store number of variables in C1
nvarsC2	pointer to store number of variables in C2

Definition at line 2768 of file cons_knapsack.c.

References getPartitionNoncovervars(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().

Referenced by changePartitionCovervars(), and separateSequLiftedExtendedWeightInequality().

◆ getPartitionNoncovervars()

static void getPartitionNoncovervars	(	SCIP *	scip,
		SCIP_Real *	solvals,
		int *	noncovervars,
		int	nnoncovervars,
		int *	varsF,
		int *	varsR,
		int *	nvarsF,
		int *	nvarsR
	)

static

gets partition \((F,R)\) of \(N \setminus C\) where \(C\) is a minimal cover, i.e. \(F \cup R = N \setminus C\) and \(F \cap R = \emptyset\); chooses partition as follows \(R = \{ j \in N \setminus C : x^*_j = 0 \}\) and \(F = (N \setminus C) \setminus F\)

Parameters

scip	SCIP data structure
solvals	solution values of all problem variables
noncovervars	noncover variables
nnoncovervars	number of noncover variables
varsF	pointer to store variables in F
varsR	pointer to store variables in R
nvarsF	pointer to store number of variables in F
nvarsR	pointer to store number of variables in R

Definition at line 2809 of file cons_knapsack.c.

References getLiftingSequence(), NULL, SCIP_Longint, SCIP_Real, SCIPisFeasEQ(), and SCIPisFeasGT().

Referenced by changePartitionFeasiblesetvars(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().

◆ getLiftingSequence()

static SCIP_RETCODE getLiftingSequence	(	SCIP *	scip,
		SCIP_Real *	solvals,
		SCIP_Longint *	weights,
		int *	varsF,
		int *	varsC2,
		int *	varsR,
		int	nvarsF,
		int	nvarsC2,
		int	nvarsR
	)

static

sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential lifting procedure

Parameters

scip	SCIP data structure
solvals	solution values of all problem variables
weights	weights of variables in knapsack constraint
varsF	pointer to store variables in F
varsC2	pointer to store variables in C2
varsR	pointer to store variables in R
nvarsF	number of variables in F
nvarsC2	number of variables in C2
nvarsR	number of variables in R

Definition at line 2857 of file cons_knapsack.c.

References getLiftingSequenceGUB(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownPtrInt(), and SCIPsortDownRealInt().

Referenced by getPartitionNoncovervars(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().

◆ getLiftingSequenceGUB()

static SCIP_RETCODE getLiftingSequenceGUB	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		SCIP_Real *	solvals,
		SCIP_Longint *	weights,
		int *	varsC1,
		int *	varsC2,
		int *	varsF,
		int *	varsR,
		int	nvarsC1,
		int	nvarsC2,
		int	nvarsF,
		int	nvarsR,
		int *	gubconsGC1,
		int *	gubconsGC2,
		int *	gubconsGFC1,
		int *	gubconsGR,
		int *	ngubconsGC1,
		int *	ngubconsGC2,
		int *	ngubconsGFC1,
		int *	ngubconsGR,
		int *	ngubconscapexceed,
		int *	maxgubvarssize
	)

static

categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs for the sequential GUB wise lifting procedure

Parameters

scip	SCIP data structure
gubset	GUB set data structure
solvals	solution values of variables in knapsack constraint
weights	weights of variables in knapsack constraint
varsC1	variables in C1
varsC2	variables in C2
varsF	variables in F
varsR	variables in R
nvarsC1	number of variables in C1
nvarsC2	number of variables in C2
nvarsF	number of variables in F
nvarsR	number of variables in R
gubconsGC1	pointer to store GUBs in GC1(GNC1+GOC1)
gubconsGC2	pointer to store GUBs in GC2
gubconsGFC1	pointer to store GUBs in GFC1(GNC1+GF)
gubconsGR	pointer to store GUBs in GR
ngubconsGC1	pointer to store number of GUBs in GC1(GNC1+GOC1)
ngubconsGC2	pointer to store number of GUBs in GC2
ngubconsGFC1	pointer to store number of GUBs in GFC1(GNC1+GF)
ngubconsGR	pointer to store number of GUBs in GR
ngubconscapexceed	pointer to store number of GUBs with only capacity exceeding variables
maxgubvarssize	pointer to store the maximal size of GUB constraints

Definition at line 2943 of file cons_knapsack.c.

References BMSclearMemoryArray, enlargeMinweights(), FALSE, GUBconsCreate(), SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, SCIP_GUBSet::gubconsstatus, GUBCONSSTATUS_BELONGSTOSET_GC2, GUBCONSSTATUS_BELONGSTOSET_GF, GUBCONSSTATUS_BELONGSTOSET_GNC1, GUBCONSSTATUS_BELONGSTOSET_GOC1, GUBCONSSTATUS_BELONGSTOSET_GR, GUBCONSSTATUS_UNINITIAL, GUBsetMoveVar(), GUBsetSwapVars(), SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBCons::gubvarssize, SCIP_GUBCons::gubvarsstatus, GUBVARSTATUS_BELONGSTOSET_C1, GUBVARSTATUS_BELONGSTOSET_C2, GUBVARSTATUS_BELONGSTOSET_F, GUBVARSTATUS_BELONGSTOSET_R, GUBVARSTATUS_CAPACITYEXCEEDED, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownPtrInt(), SCIPsortDownRealInt(), SCIPsortRealInt(), and TRUE.

Referenced by getLiftingSequence(), and separateSequLiftedMinimalCoverInequality().

◆ enlargeMinweights()

static SCIP_RETCODE enlargeMinweights	(	SCIP *	scip,
		SCIP_Longint **	minweightsptr,
		int *	minweightslen,
		int *	minweightssize,
		int	newlen
	)

static

enlarges minweight table to at least the given length

Parameters

scip	SCIP data structure
minweightsptr	pointer to minweights table
minweightslen	pointer to store number of entries in minweights table (incl. z=0)
minweightssize	pointer to current size of minweights table
newlen	new length of minweights table

Definition at line 3437 of file cons_knapsack.c.

Referenced by getLiftingSequenceGUB(), sequentialUpAndDownLifting(), and sequentialUpAndDownLiftingGUB().

◆ sequentialUpAndDownLifting()

static SCIP_RETCODE sequentialUpAndDownLifting	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	varsM1,
		int *	varsM2,
		int *	varsF,
		int *	varsR,
		int	nvarsM1,
		int	nvarsM2,
		int	nvarsF,
		int	nvarsR,
		int	alpha0,
		int *	liftcoefs,
		SCIP_Real *	cutact,
		int *	liftrhs
	)

static

lifts given inequality sum_{j in M_1} x_j <= alpha_0 valid for S^0 = { x in {0,1}^|M_1| : sum_{j in M_1} a_j x_j <= a_0 - sum_{j in M_2} a_j } to a valid inequality sum_{j in M_1} x_j + sum_{j in F} alpha_j x_j + sum_{j in M_2} alpha_j x_j + sum_{j in R} alpha_j x_j <= alpha_0 + sum_{j in M_2} alpha_j for S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 }; uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and extended weight inequalities.

Parameters

scip	SCIP data structure
vars	variables in knapsack constraint
nvars	number of variables in knapsack constraint
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
varsM1	variables in M_1
varsM2	variables in M_2
varsF	variables in F
varsR	variables in R
nvarsM1	number of variables in M_1
nvarsM2	number of variables in M_2
nvarsF	number of variables in F
nvarsR	number of variables in R
alpha0	rights hand side of given valid inequality
liftcoefs	pointer to store lifting coefficient of vars in knapsack constraint
cutact	pointer to store activity of lifted valid inequality
liftrhs	pointer to store right hand side of the lifted valid inequality

Definition at line 3487 of file cons_knapsack.c.

References BMSclearMemoryArray, enlargeMinweights(), NULL, safeAddMinweightsGUB(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPisFeasGT(), SCIPsortRealInt(), and w.

Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().

◆ safeAddMinweightsGUB()

static SCIP_Longint safeAddMinweightsGUB	(	SCIP_Longint	val1,
		SCIP_Longint	val2
	)

static

adds two minweight values in a safe way, i.e,, ensures no overflow

Parameters

val1	first value to add
val2	second value to add

Definition at line 3865 of file cons_knapsack.c.

References computeMinweightsGUB(), SCIP_Longint, and SCIP_LONGINT_MAX.

Referenced by sequentialUpAndDownLifting(), and sequentialUpAndDownLiftingGUB().

◆ computeMinweightsGUB()

static void computeMinweightsGUB	(	SCIP_Longint *	minweights,
		SCIP_Longint *	finished,
		SCIP_Longint *	unfinished,
		int	minweightslen
	)

static

computes minweights table for lifting with GUBs by combining unfished and fished tables

Parameters

minweights	minweight table to compute
finished	given finished table
unfinished	given unfinished table
minweightslen	length of minweight, finished, and unfinished tables

Definition at line 3884 of file cons_knapsack.c.

Referenced by safeAddMinweightsGUB(), and sequentialUpAndDownLiftingGUB().

◆ sequentialUpAndDownLiftingGUB()

static SCIP_RETCODE sequentialUpAndDownLiftingGUB	(	SCIP *	scip,
		SCIP_GUBSET *	gubset,
		SCIP_VAR **	vars,
		int	ngubconscapexceed,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	gubconsGC1,
		int *	gubconsGC2,
		int *	gubconsGFC1,
		int *	gubconsGR,
		int	ngubconsGC1,
		int	ngubconsGC2,
		int	ngubconsGFC1,
		int	ngubconsGR,
		int	alpha0,
		int *	liftcoefs,
		SCIP_Real *	cutact,
		int *	liftrhs,
		int	maxgubvarssize
	)

static

lifts given inequality sum_{j in C_1} x_j <= alpha_0 valid for S^0 = { x in {0,1}^|C_1| : sum_{j in C_1} a_j x_j <= a_0 - sum_{j in C_2} a_j; sum_{j in Q_i} x_j <= 1, forall i in I } to a valid inequality sum_{j in C_1} x_j + sum_{j in F} alpha_j x_j + sum_{j in C_2} alpha_j x_j + sum_{j in R} alpha_j x_j <= alpha_0 + sum_{j in C_2} alpha_j for S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0; sum_{j in Q_i} x_j <= 1, forall i in I }; uses sequential up-lifting for the variables in GUB constraints in gubconsGFC1, sequential down-lifting for the variables in GUB constraints in gubconsGC2, and sequential up-lifting for the variabels in GUB constraints in gubconsGR.

Parameters

scip	SCIP data structure
gubset	GUB set data structure
vars	variables in knapsack constraint
ngubconscapexceed	number of GUBs with only capacity exceeding variables
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all knapsack variables
gubconsGC1	GUBs in GC1(GNC1+GOC1)
gubconsGC2	GUBs in GC2
gubconsGFC1	GUBs in GFC1(GNC1+GF)
gubconsGR	GUBs in GR
ngubconsGC1	number of GUBs in GC1(GNC1+GOC1)
ngubconsGC2	number of GUBs in GC2
ngubconsGFC1	number of GUBs in GFC1(GNC1+GF)
ngubconsGR	number of GUBs in GR
alpha0	rights hand side of given valid inequality
liftcoefs	pointer to store lifting coefficient of vars in knapsack constraint
cutact	pointer to store activity of lifted valid inequality
liftrhs	pointer to store right hand side of the lifted valid inequality
maxgubvarssize	maximal size of GUB constraints

Definition at line 3936 of file cons_knapsack.c.

References BMSclearMemoryArray, computeMinweightsGUB(), enlargeMinweights(), SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconsstatus, GUBCONSSTATUS_BELONGSTOSET_GC2, GUBCONSSTATUS_BELONGSTOSET_GF, GUBCONSSTATUS_BELONGSTOSET_GNC1, GUBCONSSTATUS_BELONGSTOSET_GOC1, GUBCONSSTATUS_BELONGSTOSET_GR, SCIP_GUBCons::gubvars, SCIP_GUBCons::gubvarsstatus, GUBVARSTATUS_BELONGSTOSET_C1, GUBVARSTATUS_BELONGSTOSET_C2, GUBVARSTATUS_BELONGSTOSET_F, GUBVARSTATUS_BELONGSTOSET_R, GUBVARSTATUS_CAPACITYEXCEEDED, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, NULL, SCIP_GUBSet::nvars, safeAddMinweightsGUB(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), superadditiveUpLifting(), and w.

Referenced by separateSequLiftedMinimalCoverInequality().

◆ superadditiveUpLifting()

static SCIP_RETCODE superadditiveUpLifting	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	covervars,
		int *	noncovervars,
		int	ncovervars,
		int	nnoncovervars,
		SCIP_Longint	coverweight,
		SCIP_Real *	liftcoefs,
		SCIP_Real *	cutact
	)

static

lifts given minimal cover inequality

\[ \sum_{j \in C} x_j \leq |C| - 1 \]

valid for

\[ S^0 = \{ x \in {0,1}^{|C|} : \sum_{j \in C} a_j x_j \leq a_0 \} \]

to a valid inequality

\[ \sum_{j \in C} x_j + \sum_{j \in N \setminus C} \alpha_j x_j \leq |C| - 1 \]

for

\[ S = \{ x \in {0,1}^{|N|} : \sum_{j \in N} a_j x_j \leq a_0 \}; \]

uses superadditive up-lifting for the variables in \(N \setminus C\).

Parameters

scip	SCIP data structure
vars	variables in knapsack constraint
nvars	number of variables in knapsack constraint
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
covervars	cover variables
noncovervars	noncover variables
ncovervars	number of cover variables
nnoncovervars	number of noncover variables
coverweight	weight of cover
liftcoefs	pointer to store lifting coefficient of vars in knapsack constraint
cutact	pointer to store activity of lifted valid inequality

Definition at line 4671 of file cons_knapsack.c.

References BMSclearMemoryArray, h, MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), and separateSequLiftedMinimalCoverInequality().

Referenced by separateSupLiftedMinimalCoverInequality(), and sequentialUpAndDownLiftingGUB().

◆ separateSequLiftedMinimalCoverInequality()

static SCIP_RETCODE separateSequLiftedMinimalCoverInequality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SEPA *	sepa,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	mincovervars,
		int *	nonmincovervars,
		int	nmincovervars,
		int	nnonmincovervars,
		SCIP_SOL *	sol,
		SCIP_GUBSET *	gubset,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, 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
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
mincovervars	mincover variables
nonmincovervars	nonmincover variables
nmincovervars	number of mincover variables
nnonmincovervars	number of nonmincover variables
sol	primal SCIP solution to separate, NULL for current LP solution
gubset	GUB set data structure, NULL if no GUB information should be used
cutoff	pointer to store whether a cutoff has been detected
ncuts	pointer to add up the number of found cuts

Definition at line 4802 of file cons_knapsack.c.

References changePartitionCovervars(), FALSE, getLiftingSequence(), getLiftingSequenceGUB(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, SCIP_GUBSet::ngubconss, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), separateSequLiftedExtendedWeightInequality(), sequentialUpAndDownLifting(), sequentialUpAndDownLiftingGUB(), and TRUE.

Referenced by SCIPseparateKnapsackCuts(), and superadditiveUpLifting().

◆ separateSequLiftedExtendedWeightInequality()

static SCIP_RETCODE separateSequLiftedExtendedWeightInequality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SEPA *	sepa,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	feassetvars,
		int *	nonfeassetvars,
		int	nfeassetvars,
		int	nnonfeassetvars,
		SCIP_SOL *	sol,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem

Parameters

scip	SCIP data structure
cons	constraint that originates 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
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
feassetvars	variables in feasible set
nonfeassetvars	variables not in feasible set
nfeassetvars	number of variables in feasible set
nnonfeassetvars	number of variables not in feasible set
sol	primal SCIP solution to separate, NULL for current LP solution
cutoff	whether a cutoff has been detected
ncuts	pointer to add up the number of found cuts

Definition at line 5036 of file cons_knapsack.c.

References changePartitionFeasiblesetvars(), FALSE, getLiftingSequence(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowConshdlr(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), separateSupLiftedMinimalCoverInequality(), sequentialUpAndDownLifting(), and TRUE.

Referenced by getFeasibleSet(), and separateSequLiftedMinimalCoverInequality().

◆ separateSupLiftedMinimalCoverInequality()

static SCIP_RETCODE separateSupLiftedMinimalCoverInequality	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SEPA *	sepa,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	mincovervars,
		int *	nonmincovervars,
		int	nmincovervars,
		int	nnonmincovervars,
		SCIP_Longint	mincoverweight,
		SCIP_SOL *	sol,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem

Parameters

scip	SCIP data structure
cons	constraint that originates 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
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
mincovervars	mincover variables
nonmincovervars	nonmincover variables
nmincovervars	number of mincover variables
nnonmincovervars	number of nonmincover variables
mincoverweight	weight of minimal cover
sol	primal SCIP solution to separate, NULL for current LP solution
cutoff	whether a cutoff has been detected
ncuts	pointer to add up the number of found cuts

Definition at line 5203 of file cons_knapsack.c.

References FALSE, makeCoverMinimal(), MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowConshdlr(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), superadditiveUpLifting(), and TRUE.

Referenced by SCIPseparateKnapsackCuts(), and separateSequLiftedExtendedWeightInequality().

◆ makeCoverMinimal()

static SCIP_RETCODE makeCoverMinimal	(	SCIP *	scip,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	covervars,
		int *	noncovervars,
		int *	ncovervars,
		int *	nnoncovervars,
		SCIP_Longint *	coverweight,
		SCIP_Bool	modtransused
	)

static

converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen to be in C, i.e. in the order of non-increasing (1 - x*_j)/a_j, if the transformed separation problem was used to find C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C; note that all variables with x*_j = 1 will be removed last

Parameters

scip	SCIP data structure
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
covervars	pointer to store cover variables
noncovervars	pointer to store noncover variables
ncovervars	pointer to store number of cover variables
nnoncovervars	pointer to store number of noncover variables
coverweight	pointer to store weight of cover
modtransused	TRUE if mod trans sepa prob was used to find cover

Definition at line 5317 of file cons_knapsack.c.

References checkMinweightidx(), getFeasibleSet(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPsortPtrInt().

Referenced by SCIPseparateKnapsackCuts(), and separateSupLiftedMinimalCoverInequality().

◆ getFeasibleSet()

static SCIP_RETCODE getFeasibleSet	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SEPA *	sepa,
		SCIP_VAR **	vars,
		int	nvars,
		int	ntightened,
		SCIP_Longint *	weights,
		SCIP_Longint	capacity,
		SCIP_Real *	solvals,
		int *	covervars,
		int *	noncovervars,
		int *	ncovervars,
		int *	nnoncovervars,
		SCIP_Longint *	coverweight,
		SCIP_Bool	modtransused,
		SCIP_SOL *	sol,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

converts given initial cover C_init to a feasible set by removing variables in the reverse order in which they were chosen to be in C_init: non-increasing (1 - x*_j)/a_j, if transformed separation problem was used to find C_init non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init. separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set and all subsequent feasible sets.

Parameters

scip	SCIP data structure
cons	constraint that originates the knapsack problem
sepa	originating separator of the knapsack problem, or NULL
vars	variables in knapsack constraint
nvars	number of variables in knapsack constraint
ntightened	number of variables with tightened upper bound
weights	weights of variables in knapsack constraint
capacity	capacity of knapsack
solvals	solution values of all problem variables
covervars	pointer to store cover variables
noncovervars	pointer to store noncover variables
ncovervars	pointer to store number of cover variables
nnoncovervars	pointer to store number of noncover variables
coverweight	pointer to store weight of cover
modtransused	TRUE if mod trans sepa prob was used to find cover
sol	primal SCIP solution to separate, NULL for current LP solution
cutoff	whether a cutoff has been detected
ncuts	pointer to add up the number of found cuts

Definition at line 5466 of file cons_knapsack.c.

References FALSE, MAXCOVERSIZEITERLEWI, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLE(), SCIPseparateKnapsackCuts(), SCIPsortRealInt(), and separateSequLiftedExtendedWeightInequality().

Referenced by makeCoverMinimal(), and SCIPseparateKnapsackCuts().

◆ separateCons()

static SCIP_RETCODE separateCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool	sepacuts,
		SCIP_Bool	usegubs,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

separates given knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint
sol	primal SCIP solution, NULL for current LP solution
sepacuts	should knapsack cuts be separated?
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 6221 of file cons_knapsack.c.

References addCoef(), addRelaxation(), checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, and SCIPseparateKnapsackCuts().

Referenced by SCIPseparateRelaxedKnapsack().

◆ addCoef()

static SCIP_RETCODE addCoef	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var,
		SCIP_Longint	weight
	)

static

adds coefficient to constraint data

Parameters

scip	SCIP data structure
cons	knapsack constraint
var	variable to add to knapsack
weight	weight of variable in knapsack

Definition at line 6263 of file cons_knapsack.c.

Referenced by separateCons().

◆ delCoefPos()

static SCIP_RETCODE delCoefPos	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	pos
	)

static

deletes coefficient at given position from constraint data

Parameters

scip	SCIP data structure
cons	knapsack constraint
pos	position of coefficient to delete

Definition at line 6343 of file cons_knapsack.c.

Referenced by deleteRedundantVars(), dualWeightsTightening(), and simplifyInequalities().

◆ removeZeroWeights()

static SCIP_RETCODE removeZeroWeights	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

removes all items with weight zero from knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint

Definition at line 6533 of file cons_knapsack.c.

Referenced by tightenWeights().

◆ performVarDeletions()

static SCIP_RETCODE performVarDeletions	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss
	)

static

Parameters

scip	SCIP data structure
conshdlr	constraint handler
conss	array of constraints
nconss	number of constraints

Definition at line 6557 of file cons_knapsack.c.

◆ mergeMultiples()

static SCIP_RETCODE mergeMultiples	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	cutoff
	)

static

replaces multiple occurrences of a variable or its negation by a single coefficient

Parameters

scip	SCIP data structure
cons	knapsack constraint
cutoff	pointer to store whether the node can be cut off

Definition at line 6599 of file cons_knapsack.c.

Referenced by simplifyInequalities(), and tightenWeights().

◆ dualPresolving()

static SCIP_RETCODE dualPresolving	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nfixedvars,
		int *	ndelconss,
		SCIP_Bool *	deleted
	)

static

in case the knapsack constraint is independent of every else, solve the knapsack problem (exactly) and apply the fixings (dual reductions)

Parameters

scip	SCIP data structure
cons	knapsack constraint
nfixedvars	pointer to count number of fixings
ndelconss	pointer to count number of deleted constraints
deleted	pointer to store if the constraint is deleted

Definition at line 6742 of file cons_knapsack.c.

◆ checkParallelObjective()

static SCIP_RETCODE checkParallelObjective	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSHDLRDATA *	conshdlrdata
	)

static

check if the knapsack constraint is parallel to objective function; if so update the cutoff bound and avoid that the constraint enters the LP by setting the initial and separated flag to FALSE

Parameters

scip	SCIP data structure
cons	knapsack constraint
conshdlrdata	knapsack constraint handler data

Definition at line 6884 of file cons_knapsack.c.

◆ stableSort()

static SCIP_RETCODE stableSort	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_VAR **	vars,
		SCIP_Longint *	weights,
		int *	cliquestartposs,
		SCIP_Bool	usenegatedclique
	)

static

sort the variables and weights w.r.t. the clique partition; thereby ensure the current order of the variables when a weight of one variable is greater or equal another weight and both variables are in the same cliques

Parameters

scip	SCIP data structure
consdata	knapsack constraint data
vars	array for sorted variables
weights	array for sorted weights
cliquestartposs	starting position array for each clique
usenegatedclique	should negated or normal clique partition be used

Definition at line 7040 of file cons_knapsack.c.

References applyFixings(), BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by propagateCons().

◆ applyFixings()

static SCIP_RETCODE applyFixings	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	cutoff
	)

static

deletes all fixed variables from knapsack constraint, and replaces variables with binary representatives

Parameters

scip	SCIP data structure
cons	knapsack constraint
cutoff	pointer to store whether the node can be cut off, or NULL if this information is not needed; in this case, we apply all fixings instead of stopping after the first infeasible one

Definition at line 7164 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSEXITPRE(), and stableSort().

◆ propagateCons()

static SCIP_RETCODE propagateCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	cutoff,
		SCIP_Bool *	redundant,
		int *	nfixedvars,
		SCIP_Bool	usenegatedclique
	)

static

propagation method for knapsack constraints

Parameters

scip	SCIP data structure
cons	knapsack constraint
cutoff	pointer to store whether the node can be cut off
redundant	pointer to store whether constraint is redundant
nfixedvars	pointer to count number of fixings
usenegatedclique	should negated clique information be used

Definition at line 7376 of file cons_knapsack.c.

References BMSclearMemoryArray, calcCliquepartition(), FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_VARSTATUS_FIXED, SCIPaddConflictBinvar(), SCIPallocBufferArray, SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetStage(), SCIPincConsAge(), SCIPinferBinvarCons(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPinRepropagation(), SCIPisConflictAnalysisApplicable(), SCIPresetConsAge(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), sortItems(), stableSort(), TRUE, and upgradeCons().

◆ upgradeCons()

static SCIP_RETCODE upgradeCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	ndelconss,
		int *	naddconss
	)

static

all but one variable fit into the knapsack constraint, so we can upgrade this constraint to an logicor constraint containing all negated variables of this knapsack constraint

Parameters

scip	SCIP data structure
cons	knapsack constraint
ndelconss	pointer to store the amount of deleted constraints
naddconss	pointer to count number of added constraints

Definition at line 7840 of file cons_knapsack.c.

Referenced by detectRedundantVars(), dualWeightsTightening(), and propagateCons().

◆ deleteRedundantVars()

static SCIP_RETCODE deleteRedundantVars	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Longint	frontsum,
		int	splitpos,
		int *	nchgcoefs,
		int *	nchgsides,
		int *	naddconss
	)

static

delete redundant variables

i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them

i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique => x4, x5 always fits into the knapsack, so we can delete them

i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too => we create the set partitioning constraint x4 + x5 <= 1 and delete them in this knapsack

Parameters

scip	SCIP data structure
cons	knapsack constraint
frontsum	sum of front items which fit if we try to take from the first till the last
splitpos	split position till when all front items are fitting, splitpos is the first which did not fit
nchgcoefs	pointer to store the amount of changed coefficients
nchgsides	pointer to store the amount of changed sides
naddconss	pointer to count number of added constraints

Definition at line 7912 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), detectRedundantVars(), NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcalcCliquePartition(), SCIPcalcGreComDiv(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), and w.

Referenced by detectRedundantVars().

◆ detectRedundantVars()

static SCIP_RETCODE detectRedundantVars	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	ndelconss,
		int *	nchgcoefs,
		int *	nchgsides,
		int *	naddconss
	)

static

Parameters

scip	SCIP data structure
cons	knapsack constraint
ndelconss	pointer to store the amount of deleted constraints
nchgcoefs	pointer to store the amount of changed coefficients
nchgsides	pointer to store the amount of changed sides
naddconss	pointer to count number of added constraints

Definition at line 8163 of file cons_knapsack.c.

References calcCliquepartition(), deleteRedundantVars(), FALSE, normalizeWeights(), NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), TRUE, upgradeCons(), and w.

Referenced by deleteRedundantVars(), and simplifyInequalities().

◆ normalizeWeights()

static void normalizeWeights	(	SCIP_CONS *	cons,
		int *	nchgcoefs,
		int *	nchgsides
	)

static

divides weights by their greatest common divisor and divides capacity by the same value, rounding down the result

Parameters

cons	knapsack constraint
nchgcoefs	pointer to count total number of changed coefficients
nchgsides	pointer to count number of side changes

Definition at line 8351 of file cons_knapsack.c.

Referenced by detectRedundantVars(), and dualWeightsTightening().

◆ dualWeightsTightening()

static SCIP_RETCODE dualWeightsTightening	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	ndelconss,
		int *	nchgcoefs,
		int *	nchgsides,
		int *	naddconss
	)

static

dual weights tightening for knapsack constraints

a) check if all two pairs exceed the capacity, then we can upgrade this constraint to a set-packing constraint b) check if all but the smallest weight fit into the knapsack, then we can upgrade this constraint to a logicor constraint
check if besides big coefficients, that fit only by itself, for a certain amount of variables all combination of these are a minimal cover, then might reduce the weights and the capacity, e.g.

+219y1 + 180y2 + 74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3
use the duality between a^Tx <= capacity <=> a^T~x >= weightsum - capacity to tighten weights, e.g.

11x1 + 10x2 + 7x3 + 7x4 + 5x5 <= 27 <=> 11~x1 + 10~x2 + 7~x3 + 7~x4 + 5~x5 >= 13

the above constraint can be changed to 8~x1 + 8~x2 + 6.5~x3 + 6.5~x4 + 5~x5 >= 13

16~x1 + 16~x2 + 13~x3 + 13~x4 + 10~x5 >= 26 <=> 16x1 + 16x2 + 13x3 + 13x4 + 10x5 <= 42

Parameters

scip	SCIP data structure
cons	knapsack constraint
ndelconss	pointer to store the amount of deleted constraints
nchgcoefs	pointer to store the amount of changed coefficients
nchgsides	pointer to store the amount of changed sides
naddconss	pointer to count number of added constraints

Definition at line 8425 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), FALSE, normalizeWeights(), NULL, SCIP_GUBSet::nvars, prepareCons(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIPaddCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdelCons(), SCIPreleaseCons(), TRUE, upgradeCons(), and w.

Referenced by simplifyInequalities().

◆ prepareCons()

static SCIP_RETCODE prepareCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nfixedvars,
		int *	ndelconss,
		int *	nchgcoefs
	)

static

fixes variables with weights bigger than the capacity and delete redundant constraints, also sort weights

Parameters

scip	SCIP data structure
cons	knapsack constraint
nfixedvars	pointer to store the amount of fixed variables
ndelconss	pointer to store the amount of deleted constraints
nchgcoefs	pointer to store the amount of changed coefficients

Definition at line 9285 of file cons_knapsack.c.

Referenced by dualWeightsTightening(), and simplifyInequalities().

◆ simplifyInequalities()

static SCIP_RETCODE simplifyInequalities	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nfixedvars,
		int *	ndelconss,
		int *	nchgcoefs,
		int *	nchgsides,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

static

tries to simplify weights and delete redundant variables in knapsack a^Tx <= capacity

use the duality between a^Tx <= capacity <=> -a^T~x <= capacity - weightsum to tighten weights, e.g.

11x1 + 10x2 + 7x3 + 5x4 + 5x5 <= 25 <=> -10~x1 - 10~x2 - 7~x3 - 5~x4 - 5~x5 <= -13

the above constraint can be changed to

-8~x1 - 8~x2 - 7~x3 - 5~x4 - 5~x5 <= -12 <=> 8x1 + 8x2 + 7x3 + 5x4 + 5x5 <= 20
if variables in a constraint do not affect the (in-)feasibility of the constraint, we can delete them, e.g.

7x1 + 6x2 + 5x3 + 5x4 + x5 + x6 <= 20 => x5 and x6 are redundant and can be removed
Tries to use gcd information an all but one weight to change this not-included weight and normalize the constraint further, e.g.

9x1 + 6x2 + 6x3 + 5x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => 3x1 + 2x2 + 2x3 + 2x4 <= 4 => 4x1 + 2x2 + 2x3 + 2x4 <= 4 => 2x1 + x2 + x3 + x4 <= 2 9x1 + 6x2 + 6x3 + 7x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => see above

Parameters

scip	SCIP data structure
cons	knapsack constraint
nfixedvars	pointer to store the amount of fixed variables
ndelconss	pointer to store the amount of deleted constraints
nchgcoefs	pointer to store the amount of changed coefficients
nchgsides	pointer to store the amount of changed sides
naddconss	pointer to count number of added constraints
cutoff	pointer to store whether the node can be cut off

Definition at line 9402 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), detectRedundantVars(), dualWeightsTightening(), FALSE, insertZerolist(), mergeMultiples(), NULL, SCIP_GUBSet::nvars, prepareCons(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPcalcGreComDiv(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPdebug, SCIPdebugMsg, SCIPdebugPrintCons, SCIPisHugeValue(), and SCIPvarGetName().

◆ insertZerolist()

static SCIP_RETCODE insertZerolist	(	SCIP *	scip,
		int **	liftcands,
		int *	nliftcands,
		int **	firstidxs,
		SCIP_Longint **	zeroweightsums,
		int **	zeroitems,
		int **	nextidxs,
		int *	zeroitemssize,
		int *	nzeroitems,
		int	probindex,
		SCIP_Bool	value,
		int	knapsackidx,
		SCIP_Longint	knapsackweight,
		SCIP_Bool *	memlimitreached
	)

static

inserts an element into the list of binary zero implications

Parameters

scip	SCIP data structure
liftcands	array of the lifting candidates
nliftcands	number of lifting candidates
firstidxs	array of first zeroitems indices
zeroweightsums	array of sums of weights of the implied-to-zero items
zeroitems	pointer to zero items array
nextidxs	pointer to array of next zeroitems indeces
zeroitemssize	pointer to size of zero items array
nzeroitems	pointer to length of zero items array
probindex	problem index of variable y in implication y == v -> x == 0
value	value v of variable y in implication
knapsackidx	index of variable x in knapsack
knapsackweight	weight of variable x in knapsack
memlimitreached	pointer to store whether the memory limit was reached

Definition at line 9714 of file cons_knapsack.c.

References FALSE, MAX_ZEROITEMS_SIZE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNContVars(), SCIPgetNVars(), SCIPreallocBufferArray, and TRUE.

Referenced by simplifyInequalities().

◆ tightenWeightsLift()

static SCIP_RETCODE tightenWeightsLift	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nchgcoefs,
		SCIP_Bool *	cutoff
	)

static

applies rule (3) of the weight tightening procedure, which can lift other variables into the knapsack: (3) for a clique C let C(xi == v) := C \ {j: xi == v -> xj == 0}), let cliqueweightsum(xi == v) := sum(W(C(xi == v))) if cliqueweightsum(xi == v) < capacity:

fixing variable xi to v would make the knapsack constraint redundant
the weight of the variable or its negation (depending on v) can be increased as long as it has the same redundancy effect: wi' := capacity - cliqueweightsum(xi == v) this rule can also be applied to binary variables not in the knapsack!

Parameters

scip	SCIP data structure
cons	knapsack constraint
nchgcoefs	pointer to count total number of changed coefficients
cutoff	pointer to store whether the node can be cut off

Definition at line 9800 of file cons_knapsack.c.

Referenced by tightenWeights().

◆ tightenWeights()

static SCIP_RETCODE tightenWeights	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_PRESOLTIMING	presoltiming,
		int *	nchgcoefs,
		int *	nchgsides,
		int *	naddconss,
		int *	ndelconss,
		SCIP_Bool *	cutoff
	)

static

tightens item weights and capacity in presolving: given a knapsack sum(wi*xi) <= capacity (1) let weightsum := sum(wi) if weightsum - wi < capacity:

not using item i would make the knapsack constraint redundant
wi and capacity can be changed to have the same redundancy effect and the same results for fixing xi to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
change coefficients: wi' := weightsum - capacity capacity' := capacity - (wi - wi') (2) increase weights from front to back(sortation is necessary) if there is no space left for another weight
determine the four(can be adjusted) minimal weightsums of the knapsack, i.e. in increasing order weights[nvars - 1], weights[nvars - 2], MIN(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), MIN(MAX(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), weights[nvars - 4]), note that there can be multiple times the same weight, this can be improved
check if summing up a minimal weightsum with a big weight exceeds the capacity, then we can increase the big weight, to capacity - lastmininmalweightsum, e.g. : 19x1 + 15x2 + 10x3 + 5x4 + 5x5 <= 19 -> minimal weightsums: 5, 5, 10, 10 -> 15 + 5 > 19 => increase 15 to 19 - 0 = 19 -> 10 + 10 > 19 => increase 10 to 19 - 5 = 14, resulting in 19x1 + 19x2 + 14x3 + 5x4 + 5x5 <= 19 (3) let W(C) be the maximal weight of clique C, cliqueweightsum := sum(W(C)) if cliqueweightsum - W(C) < capacity:
not using any item of C would make the knapsack constraint redundant
weights wi, i in C, and capacity can be changed to have the same redundancy effect and the same results for fixing xi, i in C, to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
change coefficients: delta := capacity - (cliqueweightsum - W(C)) wi' := max(wi - delta, 0) capacity' := capacity - delta This rule has to add the used cliques in order to ensure they are enforced - otherwise, the reduction might introduce infeasible solutions. (4) for a clique C let C(xi == v) := C \ {j: xi == v -> xj == 0}), let cliqueweightsum(xi == v) := sum(W(C(xi == v))) if cliqueweightsum(xi == v) < capacity:
fixing variable xi to v would make the knapsack constraint redundant
the weight of the variable or its negation (depending on v) can be increased as long as it has the same redundancy effect: wi' := capacity - cliqueweightsum(xi == v) This rule can also be applied to binary variables not in the knapsack! (5) if min{w} + wi > capacity:
using item i would force to fix other items to zero
wi can be increased to the capacity

Parameters

scip	SCIP data structure
cons	knapsack constraint
presoltiming	current presolving timing
nchgcoefs	pointer to count total number of changed coefficients
nchgsides	pointer to count number of side changes
naddconss	pointer to count number of added constraints
ndelconss	pointer to count number of deleted constraints
cutoff	pointer to store whether the node can be cut off

Definition at line 10364 of file cons_knapsack.c.

References addNegatedCliques(), b, calcCliquepartition(), consdataChgWeight(), FALSE, MAX, MAX_USECLIQUES_SIZE, mergeMultiples(), NULL, SCIP_GUBSet::nvars, removeZeroWeights(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIPaddCons(), SCIPallocBufferArray, SCIPcalcCliquePartition(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdebugPrintf, SCIPdelCons(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), sortItems(), tightenWeightsLift(), TRUE, and w.

◆ addNegatedCliques()

static SCIP_RETCODE addNegatedCliques	(	SCIP *const	scip,
		SCIP_CONS *const	cons,
		SCIP_Bool *const	cutoff,
		int *const	nbdchgs
	)

static

adds negated cliques of the knapsack constraint to the global clique table

Parameters

scip	SCIP data structure
cons	knapsack constraint
cutoff	pointer to store whether the node can be cut off
nbdchgs	pointer to count the number of performed bound changes

Definition at line 10953 of file cons_knapsack.c.

Referenced by tightenWeights().

◆ greedyCliqueAlgorithm()

static SCIP_RETCODE greedyCliqueAlgorithm	(	SCIP *const	scip,
		SCIP_VAR **	items,
		SCIP_Longint *	weights,
		int	nitems,
		SCIP_Longint	capacity,
		SCIP_Bool	sorteditems,
		SCIP_Real	cliqueextractfactor,
		SCIP_Bool *const	cutoff,
		int *const	nbdchgs
	)

static

greedy clique detection by considering weights and capacity

greedily detects cliques by first sorting the items by decreasing weights (optional) and then collecting greedily 1) neighboring items which exceed the capacity together => one clique 2) looping through the remaining items and finding the largest set of preceding items to build a clique => possibly many more cliques

Parameters

scip	SCIP data structure
items	array of variable items
weights	weights of the items
nitems	the number of items
capacity	maximum free capacity of the knapsack
sorteditems	are the items sorted by their weights nonincreasing?
cliqueextractfactor	lower clique size limit for greedy clique extraction algorithm (relative to largest clique)
cutoff	pointer to store whether the node can be cut off
nbdchgs	pointer to count the number of performed bound changes

Definition at line 11155 of file cons_knapsack.c.

References addCliques(), FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddClique(), SCIPdebug, SCIPduplicateBufferArray, SCIPfreeBufferArray, and SCIPsortDownLongPtr().

◆ addCliques()

static SCIP_RETCODE addCliques	(	SCIP *const	scip,
		SCIP_CONS *const	cons,
		SCIP_Real	cliqueextractfactor,
		SCIP_Bool *const	cutoff,
		int *const	nbdchgs
	)

static

adds cliques of the knapsack constraint to the global clique table

Parameters

scip	SCIP data structure
cons	knapsack constraint
cliqueextractfactor	lower clique size limit for greedy clique extraction algorithm (relative to largest clique)
cutoff	pointer to store whether the node can be cut off
nbdchgs	pointer to count the number of performed bound changes

Definition at line 11266 of file cons_knapsack.c.

Referenced by greedyCliqueAlgorithm().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyKnapsackcons )

static

gets the key of the given element

Definition at line 11412 of file cons_knapsack.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqKnapsackcons )

static

returns TRUE iff both keys are equal; two constraints are equal if they have the same variables and the same coefficients

Definition at line 11422 of file cons_knapsack.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValKnapsackcons )

static

returns the hash value of the key

Definition at line 11465 of file cons_knapsack.c.

◆ detectRedundantConstraints()

static SCIP_RETCODE detectRedundantConstraints	(	SCIP *	scip,
		BMS_BLKMEM *	blkmem,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_Bool *	cutoff,
		int *	ndelconss
	)

static

compares each constraint with all other constraints for possible redundancy and removes or changes constraint accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table

Parameters

scip	SCIP data structure
blkmem	block memory
conss	constraint set
nconss	number of constraints in constraint set
cutoff	pointer to store whether the problem is infeasible
ndelconss	pointer to count number of deleted constraints

Definition at line 11502 of file cons_knapsack.c.

References HASHSIZE_KNAPSACKCONS, MAX, NULL, preprocessConstraintPairs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPupdateConsFlags(), and TRUE.

◆ preprocessConstraintPairs()

static SCIP_RETCODE preprocessConstraintPairs	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	firstchange,
		int	chkind,
		int *	ndelconss
	)

static

compares constraint with all prior constraints for possible redundancy or aggregation, and removes or changes constraint accordingly

Parameters

scip	SCIP data structure
conss	constraint set
firstchange	first constraint that changed since last pair preprocessing round
chkind	index of constraint to check against all prior indices upto startind
ndelconss	pointer to count number of deleted constraints

Definition at line 11626 of file cons_knapsack.c.

Referenced by detectRedundantConstraints().

◆ enforceConstraint()

static SCIP_RETCODE enforceConstraint	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss,
		int	nusefulconss,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

helper function to enforce constraints

Parameters

scip	SCIP data structure
conshdlr	constraint handler
conss	constraints to process
nconss	number of constraints
nusefulconss	number of useful (non-obsolete) constraints to process
sol	solution to enforce (NULL for the LP solution)
result	pointer to store the result of the enforcing call

Definition at line 11824 of file cons_knapsack.c.

References addRelaxation(), checkCons(), createNormalizedKnapsack(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMsg, and SCIPgetDepth().

Referenced by SCIP_DECL_CONSENFOLP().

◆ createNormalizedKnapsack()

static SCIP_RETCODE createNormalizedKnapsack	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		SCIP_Real	lhs,
		SCIP_Real	rhs,
		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
	)

static

creates and captures a knapsack constraint out of a linear inequality

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
vals	array with inequality coefficients
lhs	left hand side of inequality
rhs	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.

Definition at line 11890 of file cons_knapsack.c.

References NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_DECL_LINCONSUPGD(), SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateConsKnapsack(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPisFeasIntegral(), and SCIPisInfinity().

Referenced by enforceConstraint(), and SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_LINCONSUPGD()

static SCIP_DECL_LINCONSUPGD ( linconsUpgdKnapsack )

static

tries to upgrade a linear constraint into a knapsack constraint

Definition at line 11985 of file cons_knapsack.c.

References CONSHDLR_NAME, createNormalizedKnapsack(), NULL, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, and SCIPincludeConshdlrKnapsack().

Referenced by createNormalizedKnapsack().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyKnapsack )

static

copy method for constraint handler plugins (called when SCIP copies plugins) ! [SnippetConsCopyKnapsack]

Definition at line 12026 of file cons_knapsack.c.

References NULL, and SCIPconshdlrGetData().

Referenced by SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeKnapsack )

static

! [SnippetConsCopyKnapsack] destructor of constraint handler to free constraint handler data (called when SCIP is exiting) ! [SnippetConsFreeKnapsack]

Definition at line 12044 of file cons_knapsack.c.

◆ SCIP_DECL_CONSINIT()

static SCIP_DECL_CONSINIT ( consInitKnapsack )

static

! [SnippetConsFreeKnapsack] initialization method of constraint handler (called after problem was transformed)

Definition at line 12063 of file cons_knapsack.c.

◆ SCIP_DECL_CONSEXIT()

static SCIP_DECL_CONSEXIT ( consExitKnapsack )

static

deinitialization method of constraint handler (called before transformed problem is freed)

Definition at line 12085 of file cons_knapsack.c.

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreKnapsack )

static

presolving initialization method of constraint handler (called when presolving is about to begin)

Definition at line 12104 of file cons_knapsack.c.

◆ SCIP_DECL_CONSEXITPRE()

static SCIP_DECL_CONSEXITPRE ( consExitpreKnapsack )

static

presolving deinitialization method of constraint handler (called after presolving has been finished)

Definition at line 12147 of file cons_knapsack.c.

References applyFixings(), NULL, SCIP_CALL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconsIsDeleted(), SCIPfreeBlockMemoryArrayNull, and SCIPisNLPConstructed().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolKnapsack )

static

solving process initialization method of constraint handler

Definition at line 12190 of file cons_knapsack.c.

References addNlrow(), NULL, SCIP_CALL, SCIP_DECL_CONSEXITSOL(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSEXITPRE().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolKnapsack )

static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 12208 of file cons_knapsack.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPreleaseNlRow(), and SCIPreleaseRow().

Referenced by SCIP_DECL_CONSINITSOL().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteKnapsack )

static

frees specific constraint data

Definition at line 12237 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSEXITSOL().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransKnapsack )

static

transforms constraint data into data belonging to the transformed problem ! [SnippetConsTransKnapsack]

Definition at line 12258 of file cons_knapsack.c.

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpKnapsack )

static

! [SnippetConsTransKnapsack] LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 12299 of file cons_knapsack.c.

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpKnapsack )

static

separation method of constraint handler for LP solutions

Definition at line 12316 of file cons_knapsack.c.

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolKnapsack )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 12390 of file cons_knapsack.c.

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpKnapsack )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 12450 of file cons_knapsack.c.

References enforceConstraint(), SCIP_CALL, and SCIP_OKAY.

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxKnapsack )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 12459 of file cons_knapsack.c.

References checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, and TRUE.

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsKnapsack )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 12468 of file cons_knapsack.c.

References SCIP_Bool, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, and SCIP_OKAY.

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckKnapsack )

static

feasibility check method of constraint handler for integral solutions

Definition at line 12489 of file cons_knapsack.c.

References checkCons(), SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_INFEASIBLE, and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropKnapsack )

static

domain propagation method of constraint handler

Definition at line 12508 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolKnapsack )

static

presolving method of constraint handler

Definition at line 12558 of file cons_knapsack.c.

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropKnapsack )

static

propagation conflict resolving method of constraint handler

Definition at line 12985 of file cons_knapsack.c.

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockKnapsack )

static

variable rounding lock method of constraint handler ! [SnippetConsLockKnapsack]

Definition at line 13069 of file cons_knapsack.c.

References addNlrow(), SCIP_CALL, SCIP_DECL_CONSACTIVE(), SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPaddVarLocksType(), SCIPgetStage(), and SCIPisNLPConstructed().

◆ SCIP_DECL_CONSACTIVE()

static SCIP_DECL_CONSACTIVE ( consActiveKnapsack )

static

! [SnippetConsLockKnapsack] constraint activation notification method of constraint handler

Definition at line 13088 of file cons_knapsack.c.

References NULL, and SCIPconsGetData().

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSDEACTIVE()

static SCIP_DECL_CONSDEACTIVE ( consDeactiveKnapsack )

static

constraint deactivation notification method of constraint handler

Definition at line 13101 of file cons_knapsack.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSDELVARS(), SCIP_OKAY, and SCIPdelNlRow().

◆ SCIP_DECL_CONSDELVARS()

static SCIP_DECL_CONSDELVARS ( consDelvarsKnapsack )

static

variable deletion method of constraint handler

Definition at line 13123 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSDEACTIVE().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintKnapsack )

static

constraint display method of constraint handler

Definition at line 13139 of file cons_knapsack.c.

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyKnapsack )

static

constraint copying method of constraint handler

Definition at line 13165 of file cons_knapsack.c.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseKnapsack )

static

constraint parsing method of constraint handler

Definition at line 13201 of file cons_knapsack.c.

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsKnapsack )

static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 13302 of file cons_knapsack.c.

References BMScopyMemoryArray, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsKnapsack )

static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 13324 of file cons_knapsack.c.

References NULL, and SCIPconsGetData().

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecKnapsack )

static

execution method of bound change event handler

Definition at line 13343 of file cons_knapsack.c.

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PRESOLTIMING

◆ CONSHDLR_PROP_TIMING

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ EVENTTYPE_KNAPSACK

◆ LINCONSUPGD_PRIORITY

◆ MAX_USECLIQUES_SIZE

◆ MAX_ZEROITEMS_SIZE

◆ KNAPSACKRELAX_MAXDELTA

◆ KNAPSACKRELAX_MAXDNOM

◆ KNAPSACKRELAX_MAXSCALE

◆ DEFAULT_SEPACARDFREQ

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_MAXCARDBOUNDDIST

◆ DEFAULT_DISAGGREGATION

◆ DEFAULT_SIMPLIFYINEQUALITIES

◆ DEFAULT_NEGATEDCLIQUE

◆ MAXABSVBCOEF

◆ USESUPADDLIFT

◆ DEFAULT_PRESOLUSEHASHING

◆ HASHSIZE_KNAPSACKCONS

◆ DEFAULT_PRESOLPAIRWISE

◆ NMINCOMPARISONS

◆ MINGAINPERNMINCOMPARISONS

◆ DEFAULT_DUALPRESOLVING

◆ DEFAULT_DETECTCUTOFFBOUND

◆ DEFAULT_DETECTLOWERBOUND

◆ DEFAULT_CLIQUEEXTRACTFACTOR

◆ MAXCOVERSIZEITERLEWI

◆ DEFAULT_USEGUBS

◆ GUBCONSGROWVALUE

◆ GUBSPLITGNC1GUBS

◆ DEFAULT_CLQPARTUPDATEFAC

◆ DEFAULT_UPDATECLIQUEPARTITIONS

◆ MAXNCLIQUEVARSCOMP

◆ IDX

◆ MAX_CLIQUELENGTH

Typedef Documentation

◆ SORTKEYPAIR

◆ GUBVARSTATUS

◆ GUBCONSSTATUS

◆ SCIP_GUBCONS

◆ SCIP_GUBSET

Enumeration Type Documentation

◆ GUBVarstatus

◆ GUBConsstatus

Function Documentation

◆ SCIP_DECL_SORTPTRCOMP()

◆ eventdataCreate()

◆ eventdataFree()

◆ sortItems()

◆ calcCliquepartition()

◆ lockRounding()

◆ unlockRounding()

◆ catchEvents()

◆ dropEvents()

◆ consdataEnsureVarsSize()