Scippy

SCIP

Solving Constraint Integer Programs

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

Definition in file cons_knapsack.c.

#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 "scip/symmetry_graph.h"
#include "symmetry/struct_symmetry.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_RETCODE addSymmetryInformation (SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
 
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_CONSGETPERMSYMGRAPH (consGetPermsymGraphKnapsack)
 
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH (consGetSignedPermsymGraphKnapsack)
 
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_LongintSCIPgetWeightsKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualsolKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetDualfarkasKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_ROWSCIPgetRowKnapsack (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPcleanupConssKnapsack (SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME   "knapsack"

◆ CONSHDLR_DESC

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

Definition at line 82 of file cons_knapsack.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   +600000

priority of the constraint handler for separation

Definition at line 83 of file cons_knapsack.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -600000

priority of the constraint handler for constraint enforcing

Definition at line 84 of file cons_knapsack.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -600000

priority of the constraint handler for checking feasibility

Definition at line 85 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 86 of file cons_knapsack.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 87 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 88 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 91 of file cons_knapsack.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 92 of file cons_knapsack.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 93 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 94 of file cons_knapsack.c.

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS

Definition at line 96 of file cons_knapsack.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 97 of file cons_knapsack.c.

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "knapsack"

Definition at line 99 of file cons_knapsack.c.

◆ EVENTHDLR_DESC

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

Definition at line 100 of file cons_knapsack.c.

◆ EVENTTYPE_KNAPSACK

#define EVENTTYPE_KNAPSACK
Value:
#define SCIP_EVENTTYPE_VARFIXED
Definition: type_event.h:72
#define SCIP_EVENTTYPE_LBCHANGED
Definition: type_event.h:121
#define SCIP_EVENTTYPE_IMPLADDED
Definition: type_event.h:85
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
#define SCIP_EVENTTYPE_VARDELETED
Definition: type_event.h:71

variable events that should be caught by the event handler

Definition at line 101 of file cons_knapsack.c.

◆ LINCONSUPGD_PRIORITY

#define LINCONSUPGD_PRIORITY   +100000

priority of the constraint handler for upgrading of linear constraints

Definition at line 107 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 109 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 110 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 112 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ KNAPSACKRELAX_MAXDNOM

#define KNAPSACKRELAX_MAXDNOM   1000LL

maximal allowed denominator in knapsack rational relaxation

Definition at line 113 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 114 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 116 of file cons_knapsack.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   5

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

Definition at line 117 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 118 of file cons_knapsack.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   50

maximal number of cuts separated per separation round

Definition at line 119 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 120 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 121 of file cons_knapsack.c.

◆ DEFAULT_DISAGGREGATION

#define DEFAULT_DISAGGREGATION   TRUE

should disaggregation of knapsack constraints be allowed in preprocessing?

Definition at line 124 of file cons_knapsack.c.

◆ DEFAULT_SIMPLIFYINEQUALITIES

#define DEFAULT_SIMPLIFYINEQUALITIES   TRUE

should presolving try to simplify knapsacks

Definition at line 125 of file cons_knapsack.c.

◆ DEFAULT_NEGATEDCLIQUE

#define DEFAULT_NEGATEDCLIQUE   TRUE

should negated clique information be used in solving process

Definition at line 126 of file cons_knapsack.c.

◆ MAXABSVBCOEF

#define MAXABSVBCOEF   1e+5

maximal absolute coefficient in variable bounds used for knapsack relaxation

Definition at line 128 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 129 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 131 of file cons_knapsack.c.

◆ HASHSIZE_KNAPSACKCONS

#define HASHSIZE_KNAPSACKCONS   500

minimal size of hash table in linear constraint tables

Definition at line 132 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 134 of file cons_knapsack.c.

◆ NMINCOMPARISONS

#define NMINCOMPARISONS   200000

number for minimal pairwise presolving comparisons

Definition at line 135 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 136 of file cons_knapsack.c.

◆ DEFAULT_DUALPRESOLVING

#define DEFAULT_DUALPRESOLVING   TRUE

should dual presolving steps be performed?

Definition at line 139 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 140 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 145 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 150 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 151 of file cons_knapsack.c.

Referenced by getFeasibleSet().

◆ DEFAULT_USEGUBS

#define DEFAULT_USEGUBS   FALSE

should GUB information be used for separation?

Definition at line 153 of file cons_knapsack.c.

Referenced by SCIPseparateRelaxedKnapsack().

◆ GUBCONSGROWVALUE

#define GUBCONSGROWVALUE   6

memory growing value for GUB constraint array

Definition at line 154 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 155 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 156 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 159 of file cons_knapsack.c.

◆ MAXNCLIQUEVARSCOMP

#define MAXNCLIQUEVARSCOMP   1000000

limit on number of pairwise comparisons in clique partitioning algorithm

Definition at line 160 of file cons_knapsack.c.

Referenced by GUBsetCalcCliquePartition().

◆ IDX

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

Definition at line 1081 of file cons_knapsack.c.

Referenced by SCIPsolveKnapsackExactly().

◆ MAX_CLIQUELENGTH

#define MAX_CLIQUELENGTH   50

Definition at line 9799 of file cons_knapsack.c.

Typedef Documentation

◆ SORTKEYPAIR

typedef struct sortkeypair SORTKEYPAIR

Definition at line 277 of file cons_knapsack.c.

◆ GUBVARSTATUS

typedef enum GUBVarstatus GUBVARSTATUS

Definition at line 289 of file cons_knapsack.c.

◆ GUBCONSSTATUS

Definition at line 301 of file cons_knapsack.c.

◆ SCIP_GUBCONS

typedef struct SCIP_GUBCons SCIP_GUBCONS

Definition at line 311 of file cons_knapsack.c.

◆ SCIP_GUBSET

typedef struct SCIP_GUBSet SCIP_GUBSET

Definition at line 323 of file cons_knapsack.c.

Enumeration Type Documentation

◆ 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 280 of file cons_knapsack.c.

◆ 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 292 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 331 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
scipSCIP data structure
eventdatapointer to store event data
consconstraint
weightweight of variable

Definition at line 350 of file cons_knapsack.c.

◆ eventdataFree()

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

frees event data

Parameters
scipSCIP data structure
eventdatapointer to event data

Definition at line 368 of file cons_knapsack.c.

References NULL.

◆ sortItems()

static void sortItems ( SCIP_CONSDATA consdata)
static

sorts items in knapsack with nonincreasing weights

Parameters
consdataconstraint data

Definition at line 382 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
scipSCIP data structure
conshdlrdataknapsack constraint handler data
consdataconstraint data
normalcliqueShould normal cliquepartition be created?
negatedcliqueShould negated cliquepartition be created?

Definition at line 482 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
scipSCIP data structure
consknapsack constraint
varvariable of constraint entry

Definition at line 524 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
scipSCIP data structure
consknapsack constraint
varvariable of constraint entry

Definition at line 537 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
scipSCIP data structure
consconstraint
consdataconstraint data
eventhdlrevent handler to call for the event processing

Definition at line 550 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
scipSCIP data structure
consdataconstraint data
eventhdlrevent handler to call for the event processing

Definition at line 577 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
scipSCIP data structure
consdataknapsack constraint data
numminimum number of entries to store
transformedis constraint from transformed problem?

Definition at line 602 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
consdataknapsack constraint data
varvariable for this weight
weightdeltadifference between the old and the new weight of the variable

Definition at line 640 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
scipSCIP data structure
consdatapointer to store constraint data
nvarsnumber of variables in knapsack
varsvariables of knapsack
weightsweights of knapsack items
capacitycapacity of knapsack

Definition at line 660 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
scipSCIP data structure
consdatapointer to the constraint data
eventhdlrevent handler to call for the event processing

Definition at line 786 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
consdataknapsack constraint data
itemitem number
newweightnew weight of item

Definition at line 840 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
scipSCIP data structure
consknapsack constraint

Definition at line 878 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
scipSCIP data structure
consknapsack constraint
cutoffwhether a cutoff has been detected

Definition at line 906 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
scipSCIP data structure
consknapsack constraint

Definition at line 940 of file cons_knapsack.c.

Referenced by 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
scipSCIP data structure
consconstraint to check
solsolution to check, NULL for current solution
checklprowsDo constraints represented by rows in the current LP have to be checked?
printreasonShould the reason for the violation be printed?
violatedpointer to store whether the constraint is violated

Definition at line 984 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
scipSCIP data structure
gubconspointer to store GUB constraint data

Definition at line 1744 of file cons_knapsack.c.

Referenced by getLiftingSequenceGUB(), and SCIPsolveKnapsackApproximately().

◆ GUBconsFree()

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

frees GUB constraint

Parameters
scipSCIP data structure
gubconspointer to GUB constraint data structure

Definition at line 1765 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
scipSCIP data structure
gubconsGUB constraint data
varindex of given variable in knapsack constraint

Definition at line 1783 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
scipSCIP data structure
gubconsGUB constraint data
varindex of given variable in knapsack constraint
gubvarsidxindex of the variable in its current GUB constraint

Definition at line 1818 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
scipSCIP data structure
gubsetGUB set data structure
varsvariables in knapsack constraint
varindex of given variable in knapsack constraint
oldgubconsindex of old GUB constraint of given variable
newgubconsindex of new GUB constraint of given variable

Definition at line 1855 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
scipSCIP data structure
gubsetGUB set data structure
var1first variable to be swapped
var2second variable to be swapped

Definition at line 1946 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
scipSCIP data structure
gubsetpointer to store GUB set data structure
nvarsnumber of variables in the knapsack constraint
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack

Definition at line 1986 of file cons_knapsack.c.

Referenced by SCIPseparateKnapsackCuts().

◆ GUBsetFree()

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

frees GUB set data structure

Parameters
scipSCIP data structure
gubsetpointer to GUB set data structure

Definition at line 2035 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
scipSCIP data structure
gubsetGUB set data structure
varsvariables in the knapsack constraint

Definition at line 2067 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
scipSCIP data structure
varsbinary variables in the clique from which at most one can be set to 1
nvarsnumber of variables in the clique
cliquepartitionarray of length nvars to store the clique partition
ncliquespointer to store number of cliques actually contained in the partition
solvalssolution values of all given binary variables

Definition at line 2152 of file cons_knapsack.c.

References GUBsetGetCliquePartition(), MAXNCLIQUEVARSCOMP, MIN, 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
scipSCIP data structure
gubsetGUB set data structure
varsvariables in the knapsack constraint
solvalssolution values of all knapsack variables

Definition at line 2310 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
scipSCIP data structure
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
covervarspointer to store cover variables
noncovervarspointer to store noncover variables
ncovervarspointer to store number of cover variables
nnoncovervarspointer to store number of noncover variables
coverweightpointer to store weight of cover
foundpointer to store whether a cover was found
modtransusedshould modified transformed separation problem be used to find cover
ntightenedpointer to store number of variables with tightened upper bound
fractionalpointer to store whether the LP sol for knapsack vars is fractional

Definition at line 2407 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
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
covervarspointer to store cover variables
ncovervarspointer to store number of cover variables
coverweightpointer to store weight of cover
minweightidxindex of variable in cover variables with minimum weight
jcurrent index in cover variables

Definition at line 2638 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
scipSCIP data structure
solvalssolution values of all problem variables
covervarscover variables
ncovervarsnumber of cover variables
varsC1pointer to store variables in C1
varsC2pointer to store variables in C2
nvarsC1pointer to store number of variables in C1
nvarsC2pointer to store number of variables in C2

Definition at line 2681 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
scipSCIP data structure
weightsweights of variables in knapsack constraint
varsC1pointer to store variables in C1
varsC2pointer to store variables in C2
nvarsC1pointer to store number of variables in C1
nvarsC2pointer to store number of variables in C2

Definition at line 2730 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
scipSCIP data structure
weightsweights of variables in knapsack constraint
varsC1pointer to store variables in C1
varsC2pointer to store variables in C2
nvarsC1pointer to store number of variables in C1
nvarsC2pointer to store number of variables in C2

Definition at line 2770 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
scipSCIP data structure
solvalssolution values of all problem variables
noncovervarsnoncover variables
nnoncovervarsnumber of noncover variables
varsFpointer to store variables in F
varsRpointer to store variables in R
nvarsFpointer to store number of variables in F
nvarsRpointer to store number of variables in R

Definition at line 2811 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
scipSCIP data structure
solvalssolution values of all problem variables
weightsweights of variables in knapsack constraint
varsFpointer to store variables in F
varsC2pointer to store variables in C2
varsRpointer to store variables in R
nvarsFnumber of variables in F
nvarsC2number of variables in C2
nvarsRnumber of variables in R

Definition at line 2859 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
scipSCIP data structure
gubsetGUB set data structure
solvalssolution values of variables in knapsack constraint
weightsweights of variables in knapsack constraint
varsC1variables in C1
varsC2variables in C2
varsFvariables in F
varsRvariables in R
nvarsC1number of variables in C1
nvarsC2number of variables in C2
nvarsFnumber of variables in F
nvarsRnumber of variables in R
gubconsGC1pointer to store GUBs in GC1(GNC1+GOC1)
gubconsGC2pointer to store GUBs in GC2
gubconsGFC1pointer to store GUBs in GFC1(GNC1+GF)
gubconsGRpointer to store GUBs in GR
ngubconsGC1pointer to store number of GUBs in GC1(GNC1+GOC1)
ngubconsGC2pointer to store number of GUBs in GC2
ngubconsGFC1pointer to store number of GUBs in GFC1(GNC1+GF)
ngubconsGRpointer to store number of GUBs in GR
ngubconscapexceedpointer to store number of GUBs with only capacity exceeding variables
maxgubvarssizepointer to store the maximal size of GUB constraints

Definition at line 2945 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
scipSCIP data structure
minweightsptrpointer to minweights table
minweightslenpointer to store number of entries in minweights table (incl. z=0)
minweightssizepointer to current size of minweights table
newlennew length of minweights table

Definition at line 3448 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
scipSCIP data structure
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
varsM1variables in M_1
varsM2variables in M_2
varsFvariables in F
varsRvariables in R
nvarsM1number of variables in M_1
nvarsM2number of variables in M_2
nvarsFnumber of variables in F
nvarsRnumber of variables in R
alpha0rights hand side of given valid inequality
liftcoefspointer to store lifting coefficient of vars in knapsack constraint
cutactpointer to store activity of lifted valid inequality
liftrhspointer to store right hand side of the lifted valid inequality

Definition at line 3498 of file cons_knapsack.c.

References BMSclearMemoryArray, enlargeMinweights(), MIN, 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
val1first value to add
val2second value to add

Definition at line 3876 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
minweightsminweight table to compute
finishedgiven finished table
unfinishedgiven unfinished table
minweightslenlength of minweight, finished, and unfinished tables

Definition at line 3895 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
scipSCIP data structure
gubsetGUB set data structure
varsvariables in knapsack constraint
ngubconscapexceednumber of GUBs with only capacity exceeding variables
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all knapsack variables
gubconsGC1GUBs in GC1(GNC1+GOC1)
gubconsGC2GUBs in GC2
gubconsGFC1GUBs in GFC1(GNC1+GF)
gubconsGRGUBs in GR
ngubconsGC1number of GUBs in GC1(GNC1+GOC1)
ngubconsGC2number of GUBs in GC2
ngubconsGFC1number of GUBs in GFC1(GNC1+GF)
ngubconsGRnumber of GUBs in GR
alpha0rights hand side of given valid inequality
liftcoefspointer to store lifting coefficient of vars in knapsack constraint
cutactpointer to store activity of lifted valid inequality
liftrhspointer to store right hand side of the lifted valid inequality
maxgubvarssizemaximal size of GUB constraints

Definition at line 3947 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, MIN, 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
scipSCIP data structure
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
covervarscover variables
noncovervarsnoncover variables
ncovervarsnumber of cover variables
nnoncovervarsnumber of noncover variables
coverweightweight of cover
liftcoefspointer to store lifting coefficient of vars in knapsack constraint
cutactpointer to store activity of lifted valid inequality

Definition at line 4682 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
scipSCIP data structure
consoriginating constraint of the knapsack problem, or NULL
sepaoriginating separator of the knapsack problem, or NULL
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
mincovervarsmincover variables
nonmincovervarsnonmincover variables
nmincovervarsnumber of mincover variables
nnonmincovervarsnumber of nonmincover variables
solprimal SCIP solution to separate, NULL for current LP solution
gubsetGUB set data structure, NULL if no GUB information should be used
cutoffpointer to store whether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 4813 of file cons_knapsack.c.

References changePartitionCovervars(), FALSE, getLiftingSequence(), getLiftingSequenceGUB(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, MIN, SCIP_GUBSet::ngubconss, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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
scipSCIP data structure
consconstraint that originates the knapsack problem, or NULL
sepaoriginating separator of the knapsack problem, or NULL
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
feassetvarsvariables in feasible set
nonfeassetvarsvariables not in feasible set
nfeassetvarsnumber of variables in feasible set
nnonfeassetvarsnumber of variables not in feasible set
solprimal SCIP solution to separate, NULL for current LP solution
cutoffwhether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 5047 of file cons_knapsack.c.

References changePartitionFeasiblesetvars(), FALSE, getLiftingSequence(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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
scipSCIP data structure
consconstraint that originates the knapsack problem, or NULL
sepaoriginating separator of the knapsack problem, or NULL
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
mincovervarsmincover variables
nonmincovervarsnonmincover variables
nmincovervarsnumber of mincover variables
nnonmincovervarsnumber of nonmincover variables
mincoverweightweight of minimal cover
solprimal SCIP solution to separate, NULL for current LP solution
cutoffwhether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 5214 of file cons_knapsack.c.

References FALSE, makeCoverMinimal(), MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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
scipSCIP data structure
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
covervarspointer to store cover variables
noncovervarspointer to store noncover variables
ncovervarspointer to store number of cover variables
nnoncovervarspointer to store number of noncover variables
coverweightpointer to store weight of cover
modtransusedTRUE if mod trans sepa prob was used to find cover

Definition at line 5328 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
scipSCIP data structure
consconstraint that originates the knapsack problem
sepaoriginating separator of the knapsack problem, or NULL
varsvariables in knapsack constraint
nvarsnumber of variables in knapsack constraint
ntightenednumber of variables with tightened upper bound
weightsweights of variables in knapsack constraint
capacitycapacity of knapsack
solvalssolution values of all problem variables
covervarspointer to store cover variables
noncovervarspointer to store noncover variables
ncovervarspointer to store number of cover variables
nnoncovervarspointer to store number of noncover variables
coverweightpointer to store weight of cover
modtransusedTRUE if mod trans sepa prob was used to find cover
solprimal SCIP solution to separate, NULL for current LP solution
cutoffwhether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 5477 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
scipSCIP data structure
consknapsack constraint
solprimal SCIP solution, NULL for current LP solution
sepacutsshould knapsack cuts be separated?
usegubsshould GUB information be used for separation?
cutoffwhether a cutoff has been detected
ncutspointer to add up the number of found cuts

Definition at line 6232 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
scipSCIP data structure
consknapsack constraint
varvariable to add to knapsack
weightweight of variable in knapsack

Definition at line 6274 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
scipSCIP data structure
consknapsack constraint
posposition of coefficient to delete

Definition at line 6354 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
scipSCIP data structure
consknapsack constraint

Definition at line 6544 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
scipSCIP data structure
conshdlrconstraint handler
conssarray of constraints
nconssnumber of constraints

Definition at line 6568 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
scipSCIP data structure
consknapsack constraint
cutoffpointer to store whether the node can be cut off

Definition at line 6610 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
scipSCIP data structure
consknapsack constraint
nfixedvarspointer to count number of fixings
ndelconsspointer to count number of deleted constraints
deletedpointer to store if the constraint is deleted

Definition at line 6753 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
scipSCIP data structure
consknapsack constraint
conshdlrdataknapsack constraint handler data

Definition at line 6895 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
scipSCIP data structure
consdataknapsack constraint data
varsarray for sorted variables
weightsarray for sorted weights
cliquestartpossstarting position array for each clique
usenegatedcliqueshould negated or normal clique partition be used

Definition at line 7051 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
scipSCIP data structure
consknapsack constraint
cutoffpointer 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 7175 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

◆ 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
scipSCIP data structure
consknapsack constraint
ndelconsspointer to store the amount of deleted constraints
naddconsspointer to count number of added constraints

Definition at line 7851 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
scipSCIP data structure
consknapsack constraint
frontsumsum of front items which fit if we try to take from the first till the last
splitpossplit position till when all front items are fitting, splitpos is the first which did not fit
nchgcoefspointer to store the amount of changed coefficients
nchgsidespointer to store the amount of changed sides
naddconsspointer to count number of added constraints

Definition at line 7923 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), detectRedundantVars(), NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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

◆ 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
consknapsack constraint
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to count number of side changes

Definition at line 8362 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

  1. 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
  2. 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

  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
scipSCIP data structure
consknapsack constraint
ndelconsspointer to store the amount of deleted constraints
nchgcoefspointer to store the amount of changed coefficients
nchgsidespointer to store the amount of changed sides
naddconsspointer to count number of added constraints

Definition at line 8436 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), FALSE, MIN, 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
scipSCIP data structure
consknapsack constraint
nfixedvarspointer to store the amount of fixed variables
ndelconsspointer to store the amount of deleted constraints
nchgcoefspointer to store the amount of changed coefficients

Definition at line 9296 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

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

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

  3. 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
scipSCIP data structure
consknapsack constraint
nfixedvarspointer to store the amount of fixed variables
ndelconsspointer to store the amount of deleted constraints
nchgcoefspointer to store the amount of changed coefficients
nchgsidespointer to store the amount of changed sides
naddconsspointer to count number of added constraints
cutoffpointer to store whether the node can be cut off

Definition at line 9413 of file cons_knapsack.c.

References consdataChgWeight(), delCoefPos(), detectRedundantVars(), dualWeightsTightening(), FALSE, insertZerolist(), mergeMultiples(), NULL, SCIP_GUBSet::nvars, prepareCons(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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
scipSCIP data structure
liftcandsarray of the lifting candidates
nliftcandsnumber of lifting candidates
firstidxsarray of first zeroitems indices
zeroweightsumsarray of sums of weights of the implied-to-zero items
zeroitemspointer to zero items array
nextidxspointer to array of next zeroitems indeces
zeroitemssizepointer to size of zero items array
nzeroitemspointer to length of zero items array
probindexproblem index of variable y in implication y == v -> x == 0
valuevalue v of variable y in implication
knapsackidxindex of variable x in knapsack
knapsackweightweight of variable x in knapsack
memlimitreachedpointer to store whether the memory limit was reached

Definition at line 9725 of file cons_knapsack.c.

References FALSE, MAX_ZEROITEMS_SIZE, MIN, 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
scipSCIP data structure
consknapsack constraint
nchgcoefspointer to count total number of changed coefficients
cutoffpointer to store whether the node can be cut off

Definition at line 9811 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
scipSCIP data structure
consknapsack constraint
presoltimingcurrent presolving timing
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to count number of side changes
naddconsspointer to count number of added constraints
ndelconsspointer to count number of deleted constraints
cutoffpointer to store whether the node can be cut off

Definition at line 10375 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_LONGINT_FORMAT, 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
scipSCIP data structure
consknapsack constraint
cutoffpointer to store whether the node can be cut off
nbdchgspointer to count the number of performed bound changes

Definition at line 10964 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
scipSCIP data structure
itemsarray of variable items
weightsweights of the items
nitemsthe number of items
capacitymaximum free capacity of the knapsack
sorteditemsare the items sorted by their weights nonincreasing?
cliqueextractfactorlower clique size limit for greedy clique extraction algorithm (relative to largest clique)
cutoffpointer to store whether the node can be cut off
nbdchgspointer to count the number of performed bound changes

Definition at line 11166 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
scipSCIP data structure
consknapsack constraint
cliqueextractfactorlower clique size limit for greedy clique extraction algorithm (relative to largest clique)
cutoffpointer to store whether the node can be cut off
nbdchgspointer to count the number of performed bound changes

Definition at line 11277 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 11423 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 11433 of file cons_knapsack.c.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValKnapsackcons  )
static

returns the hash value of the key

Definition at line 11476 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
scipSCIP data structure
blkmemblock memory
conssconstraint set
nconssnumber of constraints in constraint set
cutoffpointer to store whether the problem is infeasible
ndelconsspointer to count number of deleted constraints

Definition at line 11513 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
scipSCIP data structure
conssconstraint set
firstchangefirst constraint that changed since last pair preprocessing round
chkindindex of constraint to check against all prior indices upto startind
ndelconsspointer to count number of deleted constraints

Definition at line 11637 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
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
nusefulconssnumber of useful (non-obsolete) constraints to process
solsolution to enforce (NULL for the LP solution)
resultpointer to store the result of the enforcing call

Definition at line 11835 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables in the constraint
varsarray with variables of constraint entries
valsarray with inequality coefficients
lhsleft hand side of inequality
rhsright hand side of inequality
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 11901 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()

◆ addSymmetryInformation()

static SCIP_RETCODE addSymmetryInformation ( SCIP scip,
SYM_SYMTYPE  symtype,
SCIP_CONS cons,
SYM_GRAPH graph,
SCIP_Bool success 
)
static

adds symmetry information of constraint to a symmetry detection graph

Parameters
scipSCIP pointer
symtypetype of symmetries that need to be added
consconstraint
graphsymmetry detection graph
successpointer to store whether symmetry information could be added

Definition at line 12031 of file cons_knapsack.c.

Referenced by SCIP_DECL_CONSGETNVARS(), SCIP_DECL_CONSGETPERMSYMGRAPH(), and SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyKnapsack  )
static

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

Definition at line 12089 of file cons_knapsack.c.

References NULL, and SCIPconshdlrGetData().

◆ 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 12107 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 12126 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 12148 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 12167 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 12210 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 12253 of file cons_knapsack.c.

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 12270 of file cons_knapsack.c.

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

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteKnapsack  )
static

frees specific constraint data

Definition at line 12299 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 12320 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 12361 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 12378 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 12452 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 12512 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 12521 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 12530 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 12551 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 12570 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 12620 of file cons_knapsack.c.

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropKnapsack  )
static

propagation conflict resolving method of constraint handler

Definition at line 13047 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 13131 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 13150 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 13162 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 13184 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 13200 of file cons_knapsack.c.

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyKnapsack  )
static

constraint copying method of constraint handler

Definition at line 13226 of file cons_knapsack.c.

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseKnapsack  )
static

constraint parsing method of constraint handler

Definition at line 13262 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 13370 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 13392 of file cons_knapsack.c.

References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_PERM.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_CONSGETPERMSYMGRAPH()

static SCIP_DECL_CONSGETPERMSYMGRAPH ( consGetPermsymGraphKnapsack  )
static

constraint handler method which returns the permutation symmetry detection graph of a constraint

Definition at line 13407 of file cons_knapsack.c.

References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_SIGNPERM.

◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()

static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH ( consGetSignedPermsymGraphKnapsack  )
static

constraint handler method which returns the signed permutation symmetry detection graph of a constraint

Definition at line 13416 of file cons_knapsack.c.

References NULL, and SCIPconsGetData().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecKnapsack  )
static

execution method of bound change event handler

Definition at line 13429 of file cons_knapsack.c.