SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
Constraint handler for knapsack constraints of the form \(a^T x \le b\), x binary and \(a \ge 0\).
Definition in file cons_knapsack.c.
#include <assert.h>#include <string.h>#include <limits.h>#include <stdio.h>#include <ctype.h>#include "scip/cons_knapsack.h"#include "scip/cons_linear.h"#include "scip/cons_logicor.h"#include "scip/cons_setppc.h"#include "scip/pub_misc.h"Go to the source code of this file.
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 | 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 SCIP_RETCODE | 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 SCIP_RETCODE | GUBsetFree (SCIP *scip, SCIP_GUBSET **gubset) |
| static SCIP_RETCODE | GUBsetCheck (SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars) |
| static SCIP_RETCODE | GUBsetCalcCliquePartition (SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques, SCIP_Real *solvals) |
| static SCIP_RETCODE | GUBsetGetCliquePartition (SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals) |
| static SCIP_RETCODE | getCover (SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool *found, SCIP_Bool modtransused, int *ntightened, SCIP_Bool *fractional) |
| static SCIP_Bool | checkMinweightidx (SCIP_Longint *weights, SCIP_Longint capacity, int *covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j) |
| static void | getPartitionCovervars (SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) |
| static SCIP_RETCODE | changePartitionCovervars (SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) |
| static SCIP_RETCODE | changePartitionFeasiblesetvars (SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) |
| static void | getPartitionNoncovervars (SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR) |
| static SCIP_RETCODE | getLiftingSequence (SCIP *scip, SCIP_Real *solvals, SCIP_Longint *weights, int *varsF, int *varsC2, int *varsR, int nvarsF, int nvarsC2, int nvarsR) |
| static SCIP_RETCODE | getLiftingSequenceGUB (SCIP *scip, SCIP_GUBSET *gubset, SCIP_Real *solvals, SCIP_Longint *weights, int *varsC1, int *varsC2, int *varsF, int *varsR, int nvarsC1, int nvarsC2, int nvarsF, int nvarsR, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int *ngubconsGC1, int *ngubconsGC2, int *ngubconsGFC1, int *ngubconsGR, int *ngubconscapexceed, int *maxgubvarssize) |
| static SCIP_RETCODE | enlargeMinweights (SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen) |
| static SCIP_RETCODE | sequentialUpAndDownLifting (SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *varsM1, int *varsM2, int *varsF, int *varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs) |
| static SCIP_Longint | safeAddMinweightsGUB (SCIP_Longint val1, SCIP_Longint val2) |
| static void | computeMinweightsGUB (SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen) |
| static SCIP_RETCODE | sequentialUpAndDownLiftingGUB (SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int ngubconscapexceed, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs, int maxgubvarssize) |
| static SCIP_RETCODE | superadditiveUpLifting (SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Real *liftcoefs, SCIP_Real *cutact) |
| static SCIP_RETCODE | separateSequLiftedMinimalCoverInequality (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_SOL *sol, SCIP_GUBSET *gubset, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | separateSequLiftedExtendedWeightInequality (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *feassetvars, int *nonfeassetvars, int nfeassetvars, int nnonfeassetvars, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | separateSupLiftedMinimalCoverInequality (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_Longint mincoverweight, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | makeCoverMinimal (SCIP *scip, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused) |
| static SCIP_RETCODE | getFeasibleSet (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) |
| SCIP_RETCODE | SCIPseparateKnapsackCuts (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_SOL *sol, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts) |
| SCIP_RETCODE | SCIPseparateRelaxedKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | separateCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts) |
| static SCIP_RETCODE | addCoef (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) |
| static SCIP_RETCODE | delCoefPos (SCIP *scip, SCIP_CONS *cons, int pos) |
| static SCIP_RETCODE | removeZeroWeights (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | performVarDeletions (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | mergeMultiples (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | dualPresolving (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted) |
| static SCIP_RETCODE | checkParallelObjective (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata) |
| static SCIP_RETCODE | stableSort (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique) |
| static SCIP_RETCODE | applyFixings (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique) |
| static SCIP_RETCODE | upgradeCons (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss) |
| static SCIP_RETCODE | deleteRedundantVars (SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss) |
| static SCIP_RETCODE | detectRedundantVars (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss) |
| static void | normalizeWeights (SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) |
| static SCIP_RETCODE | dualWeightsTightening (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss) |
| static SCIP_RETCODE | prepareCons (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs) |
| static SCIP_RETCODE | simplifyInequalities (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | insertZerolist (SCIP *scip, int **liftcands, int *nliftcands, int **firstidxs, SCIP_Longint **zeroweightsums, int **zeroitems, int **nextidxs, int *zeroitemssize, int *nzeroitems, int probindex, SCIP_Bool value, int knapsackidx, SCIP_Longint knapsackweight, SCIP_Bool *memlimitreached) |
| static SCIP_RETCODE | tightenWeightsLift (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | tightenWeights (SCIP *scip, SCIP_CONS *cons, SCIP_PRESOLTIMING presoltiming, int *nchgcoefs, int *nchgsides, int *naddconss, int *ndelconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | addNegatedCliques (SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs) |
| static SCIP_RETCODE | greedyCliqueAlgorithm (SCIP *const scip, SCIP_VAR **items, SCIP_Longint *weights, int nitems, SCIP_Longint capacity, SCIP_Bool sorteditems, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs) |
| static SCIP_RETCODE | addCliques (SCIP *const scip, SCIP_CONS *const cons, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs) |
| static | SCIP_DECL_HASHGETKEY (hashGetKeyKnapsackcons) |
| static | SCIP_DECL_HASHKEYEQ (hashKeyEqKnapsackcons) |
| static | SCIP_DECL_HASHKEYVAL (hashKeyValKnapsackcons) |
| static SCIP_RETCODE | detectRedundantConstraints (SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss) |
| static SCIP_RETCODE | preprocessConstraintPairs (SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss) |
| static SCIP_RETCODE | enforceConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result) |
| static SCIP_RETCODE | createNormalizedKnapsack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
| static | SCIP_DECL_LINCONSUPGD (linconsUpgdKnapsack) |
| static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyKnapsack) |
| static | SCIP_DECL_CONSFREE (consFreeKnapsack) |
| static | SCIP_DECL_CONSINIT (consInitKnapsack) |
| static | SCIP_DECL_CONSEXIT (consExitKnapsack) |
| static | SCIP_DECL_CONSINITPRE (consInitpreKnapsack) |
| static | SCIP_DECL_CONSEXITPRE (consExitpreKnapsack) |
| static | SCIP_DECL_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_CONSDELVARS (consDelvarsKnapsack) |
| static | SCIP_DECL_CONSPRINT (consPrintKnapsack) |
| static | SCIP_DECL_CONSCOPY (consCopyKnapsack) |
| static | SCIP_DECL_CONSPARSE (consParseKnapsack) |
| static | SCIP_DECL_CONSGETVARS (consGetVarsKnapsack) |
| static | SCIP_DECL_CONSGETNVARS (consGetNVarsKnapsack) |
| static | SCIP_DECL_EVENTEXEC (eventExecKnapsack) |
| SCIP_RETCODE | SCIPincludeConshdlrKnapsack (SCIP *scip) |
| SCIP_RETCODE | SCIPcreateConsKnapsack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
| SCIP_RETCODE | SCIPcreateConsBasicKnapsack (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity) |
| SCIP_RETCODE | SCIPaddCoefKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) |
| SCIP_Longint | SCIPgetCapacityKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_RETCODE | SCIPchgCapacityKnapsack (SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity) |
| int | SCIPgetNVarsKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_VAR ** | SCIPgetVarsKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_Longint * | SCIPgetWeightsKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_Real | SCIPgetDualsolKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_Real | SCIPgetDualfarkasKnapsack (SCIP *scip, SCIP_CONS *cons) |
| SCIP_ROW * | SCIPgetRowKnapsack (SCIP *scip, SCIP_CONS *cons) |
| #define CONSHDLR_NAME "knapsack" |
Definition at line 44 of file cons_knapsack.c.
Referenced by SCIP_DECL_CONSEXITSOL(), SCIP_DECL_LINCONSUPGD(), SCIPaddCoefKnapsack(), SCIPchgCapacityKnapsack(), SCIPcreateConsKnapsack(), SCIPgetDualfarkasKnapsack(), SCIPgetDualsolKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), and SCIPseparateRelaxedKnapsack().
| #define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0" |
Definition at line 45 of file cons_knapsack.c.
| #define CONSHDLR_SEPAPRIORITY +600000 |
priority of the constraint handler for separation
Definition at line 46 of file cons_knapsack.c.
| #define CONSHDLR_ENFOPRIORITY -600000 |
priority of the constraint handler for constraint enforcing
Definition at line 47 of file cons_knapsack.c.
| #define CONSHDLR_CHECKPRIORITY -600000 |
priority of the constraint handler for checking feasibility
Definition at line 48 of file cons_knapsack.c.
| #define CONSHDLR_SEPAFREQ 0 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 49 of file cons_knapsack.c.
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 50 of file cons_knapsack.c.
| #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 51 of file cons_knapsack.c.
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 54 of file cons_knapsack.c.
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 55 of file cons_knapsack.c.
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 56 of file cons_knapsack.c.
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 57 of file cons_knapsack.c.
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
Definition at line 59 of file cons_knapsack.c.
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 60 of file cons_knapsack.c.
| #define EVENTHDLR_NAME "knapsack" |
Definition at line 62 of file cons_knapsack.c.
| #define EVENTHDLR_DESC "bound change event handler for knapsack constraints" |
Definition at line 63 of file cons_knapsack.c.
| #define EVENTTYPE_KNAPSACK |
variable events that should be caught by the event handler
Definition at line 64 of file cons_knapsack.c.
| #define LINCONSUPGD_PRIORITY +100000 |
priority of the constraint handler for upgrading of linear constraints
Definition at line 70 of file cons_knapsack.c.
| #define MAX_USECLIQUES_SIZE 1000 |
maximal number of items in knapsack where clique information is used
Definition at line 72 of file cons_knapsack.c.
Referenced by tightenWeights().
| #define MAX_ZEROITEMS_SIZE 10000 |
maximal number of items to store in the zero list in preprocessing
Definition at line 73 of file cons_knapsack.c.
Referenced by insertZerolist().
| #define KNAPSACKRELAX_MAXDELTA 0.1 |
maximal allowed rounding distance for scaling in knapsack relaxation
Definition at line 75 of file cons_knapsack.c.
Referenced by SCIPseparateRelaxedKnapsack().
| #define KNAPSACKRELAX_MAXDNOM 1000LL |
maximal allowed denominator in knapsack rational relaxation
Definition at line 76 of file cons_knapsack.c.
Referenced by SCIPseparateRelaxedKnapsack().
| #define KNAPSACKRELAX_MAXSCALE 1000.0 |
maximal allowed scaling factor in knapsack rational relaxation
Definition at line 77 of file cons_knapsack.c.
Referenced by SCIPseparateRelaxedKnapsack().
| #define DEFAULT_SEPACARDFREQ 1 |
multiplier on separation frequency, how often knapsack cuts are separated
Definition at line 79 of file cons_knapsack.c.
| #define DEFAULT_MAXROUNDS 5 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 80 of file cons_knapsack.c.
| #define DEFAULT_MAXROUNDSROOT -1 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 81 of file cons_knapsack.c.
| #define DEFAULT_MAXSEPACUTS 50 |
maximal number of cuts separated per separation round
Definition at line 82 of file cons_knapsack.c.
| #define DEFAULT_MAXSEPACUTSROOT 200 |
maximal number of cuts separated per separation round in the root node
Definition at line 83 of file cons_knapsack.c.
| #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 84 of file cons_knapsack.c.
| #define DEFAULT_DISAGGREGATION TRUE |
should disaggregation of knapsack constraints be allowed in preprocessing?
Definition at line 87 of file cons_knapsack.c.
| #define DEFAULT_SIMPLIFYINEQUALITIES TRUE |
should presolving try to simplify knapsacks
Definition at line 88 of file cons_knapsack.c.
| #define DEFAULT_NEGATEDCLIQUE TRUE |
should negated clique information be used in solving process
Definition at line 89 of file cons_knapsack.c.
| #define MAXABSVBCOEF 1e+5 |
maximal absolute coefficient in variable bounds used for knapsack relaxation
Definition at line 91 of file cons_knapsack.c.
Referenced by SCIPseparateRelaxedKnapsack().
| #define USESUPADDLIFT FALSE |
should lifted minimal cover inequalities using superadditive up-lifting be separated in addition
Definition at line 92 of file cons_knapsack.c.
Referenced by SCIPseparateKnapsackCuts().
| #define DEFAULT_PRESOLUSEHASHING TRUE |
should hash table be used for detecting redundant constraints in advance
Definition at line 94 of file cons_knapsack.c.
| #define HASHSIZE_KNAPSACKCONS 500 |
minimal size of hash table in linear constraint tables
Definition at line 95 of file cons_knapsack.c.
Referenced by detectRedundantConstraints().
| #define DEFAULT_PRESOLPAIRWISE TRUE |
should pairwise constraint comparison be performed in presolving?
Definition at line 97 of file cons_knapsack.c.
| #define NMINCOMPARISONS 200000 |
number for minimal pairwise presolving comparisons
Definition at line 98 of file cons_knapsack.c.
| #define MINGAINPERNMINCOMPARISONS 1e-06 |
minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round
Definition at line 99 of file cons_knapsack.c.
| #define DEFAULT_DUALPRESOLVING TRUE |
should dual presolving steps be performed?
Definition at line 102 of file cons_knapsack.c.
| #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 103 of file cons_knapsack.c.
| #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 108 of file cons_knapsack.c.
| #define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 |
lower clique size limit for greedy clique extraction algorithm (relative to largest clique)
Definition at line 113 of file cons_knapsack.c.
| #define MAXCOVERSIZEITERLEWI 1000 |
maximal size for which LEWI are iteratively separated by reducing the feasible set
Definition at line 114 of file cons_knapsack.c.
Referenced by getFeasibleSet().
| #define DEFAULT_USEGUBS FALSE |
should GUB information be used for separation?
Definition at line 116 of file cons_knapsack.c.
Referenced by SCIPseparateRelaxedKnapsack().
| #define GUBCONSGROWVALUE 6 |
memory growing value for GUB constraint array
Definition at line 117 of file cons_knapsack.c.
| #define GUBSPLITGNC1GUBS FALSE |
should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss?
Definition at line 118 of file cons_knapsack.c.
| #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 119 of file cons_knapsack.c.
| #define DEFAULT_UPDATECLIQUEPARTITIONS FALSE |
should clique partition information be updated when old partition seems outdated?
Definition at line 122 of file cons_knapsack.c.
| #define MAXNCLIQUEVARSCOMP 1000000 |
limit on number of pairwise comparisons in clique partitioning algorithm
Definition at line 123 of file cons_knapsack.c.
Referenced by GUBsetCalcCliquePartition().
| #define IDX | ( | j, | |
| d | |||
| ) | ((j)*(intcap)+(d)) |
Definition at line 1001 of file cons_knapsack.c.
Referenced by SCIPsolveKnapsackExactly().
| #define MAX_CLIQUELENGTH 50 |
Definition at line 9755 of file cons_knapsack.c.
| typedef struct sortkeypair SORTKEYPAIR |
Definition at line 239 of file cons_knapsack.c.
| typedef enum GUBVarstatus GUBVARSTATUS |
Definition at line 251 of file cons_knapsack.c.
| typedef enum GUBConsstatus GUBCONSSTATUS |
Definition at line 263 of file cons_knapsack.c.
| typedef struct SCIP_GUBCons SCIP_GUBCONS |
Definition at line 273 of file cons_knapsack.c.
| typedef struct SCIP_GUBSet SCIP_GUBSET |
Definition at line 285 of file cons_knapsack.c.
| enum GUBVarstatus |
status of GUB constraint
Definition at line 242 of file cons_knapsack.c.
| enum GUBConsstatus |
status of variable in GUB constraint
Definition at line 254 of file cons_knapsack.c.
|
static |
comparison method for two sorting key pairs
Definition at line 293 of file cons_knapsack.c.
|
static |
creates event data
| scip | SCIP data structure |
| eventdata | pointer to store event data |
| cons | constraint |
| weight | weight of variable |
Definition at line 312 of file cons_knapsack.c.
|
static |
frees event data
| scip | SCIP data structure |
| eventdata | pointer to event data |
Definition at line 330 of file cons_knapsack.c.
|
static |
sorts items in knapsack with nonincreasing weights
| consdata | constraint data |
Definition at line 344 of file cons_knapsack.c.
Referenced by propagateCons(), and tightenWeights().
|
static |
calculates a partition of the variables into cliques
| scip | SCIP data structure |
| conshdlrdata | knapsack constraint handler data |
| consdata | constraint data |
| normalclique | Should normal cliquepartition be created? |
| negatedclique | Should negated cliquepartition be created? |
Definition at line 444 of file cons_knapsack.c.
Referenced by detectRedundantVars(), propagateCons(), and tightenWeights().
|
static |
installs rounding locks for the given variable in the given knapsack constraint
| scip | SCIP data structure |
| cons | knapsack constraint |
| var | variable of constraint entry |
Definition at line 486 of file cons_knapsack.c.
References FALSE, SCIP_CALL, SCIPunlockVarCons(), and TRUE.
|
static |
removes rounding locks for the given variable in the given knapsack constraint
| scip | SCIP data structure |
| cons | knapsack constraint |
| var | variable of constraint entry |
Definition at line 500 of file cons_knapsack.c.
|
static |
catches bound change events for variables in knapsack
| scip | SCIP data structure |
| cons | constraint |
| consdata | constraint data |
| eventhdlr | event handler to call for the event processing |
Definition at line 514 of file cons_knapsack.c.
Referenced by SCIPcreateConsKnapsack().
|
static |
drops bound change events for variables in knapsack
| scip | SCIP data structure |
| consdata | constraint data |
| eventhdlr | event handler to call for the event processing |
Definition at line 541 of file cons_knapsack.c.
Referenced by consdataFree().
|
static |
ensures, that vars and vals arrays can store at least num entries
| scip | SCIP data structure |
| consdata | knapsack constraint data |
| num | minimum number of entries to store |
| transformed | is constraint from transformed problem? |
Definition at line 566 of file cons_knapsack.c.
|
static |
updates all weight sums for fixed and unfixed variables
| consdata | knapsack constraint data |
| var | variable for this weight |
| weightdelta | difference between the old and the new weight of the variable |
Definition at line 604 of file cons_knapsack.c.
Referenced by consdataCreate().
|
static |
creates knapsack constraint data
| scip | SCIP data structure |
| consdata | pointer to store constraint data |
| nvars | number of variables in knapsack |
| vars | variables of knapsack |
| weights | weights of knapsack items |
| capacity | capacity of knapsack |
Definition at line 624 of file cons_knapsack.c.
References consdataFree(), FALSE, 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().
|
static |
frees knapsack constraint data
| scip | SCIP data structure |
| consdata | pointer to the constraint data |
| eventhdlr | event handler to call for the event processing |
Definition at line 752 of file cons_knapsack.c.
References consdataChgWeight(), dropEvents(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseRow(), and SCIPreleaseVar().
Referenced by consdataCreate().
|
static |
changes a single weight in knapsack constraint data
| consdata | knapsack constraint data |
| item | item number |
| newweight | new weight of item |
Definition at line 802 of file cons_knapsack.c.
Referenced by consdataFree(), deleteRedundantVars(), dualWeightsTightening(), simplifyInequalities(), and tightenWeights().
|
static |
creates LP row corresponding to knapsack constraint
| scip | SCIP data structure |
| cons | knapsack constraint |
Definition at line 841 of file cons_knapsack.c.
|
static |
adds linear relaxation of knapsack constraint to the LP
| scip | SCIP data structure |
| cons | knapsack constraint |
| cutoff | whether a cutoff has been detected |
Definition at line 869 of file cons_knapsack.c.
Referenced by enforceConstraint(), and separateCons().
|
static |
checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible
| scip | SCIP data structure |
| cons | constraint to check |
| sol | solution to check, NULL for current solution |
| checklprows | Do constraints represented by rows in the current LP have to be checked? |
| printreason | Should the reason for the violation be printed? |
| violated | pointer to store whether the constraint is violated |
Definition at line 903 of file cons_knapsack.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPincConsAge(), SCIPinfoMessage(), SCIPisFeasPositive(), SCIPisHugeValue(), SCIPprintCons(), SCIPrelDiff(), SCIPresetConsAge(), SCIProwIsInLP(), SCIPsolveKnapsackExactly(), SCIPupdateSolLPConsViolation(), SCIPvarIsBinary(), and TRUE.
Referenced by enforceConstraint(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFORELAX(), and separateCons().
|
static |
creates an empty GUB constraint
| scip | SCIP data structure |
| gubcons | pointer to store GUB constraint data |
Definition at line 1688 of file cons_knapsack.c.
Referenced by getLiftingSequenceGUB(), and SCIPsolveKnapsackApproximately().
|
static |
frees GUB constraint
| scip | SCIP data structure |
| gubcons | pointer to GUB constraint data structure |
Definition at line 1709 of file cons_knapsack.c.
Referenced by GUBsetMoveVar().
|
static |
adds variable to given GUB constraint
| scip | SCIP data structure |
| gubcons | GUB constraint data |
| var | index of given variable in knapsack constraint |
Definition at line 1729 of file cons_knapsack.c.
Referenced by GUBsetMoveVar().
|
static |
deletes variable from its current GUB constraint
| scip | SCIP data structure |
| gubcons | GUB constraint data |
| var | index of given variable in knapsack constraint |
| gubvarsidx | index of the variable in its current GUB constraint |
Definition at line 1764 of file cons_knapsack.c.
Referenced by GUBsetMoveVar().
|
static |
moves variable from current GUB constraint to a different existing (nonempty) GUB constraint
| scip | SCIP data structure |
| gubset | GUB set data structure |
| vars | variables in knapsack constraint |
| var | index of given variable in knapsack constraint |
| oldgubcons | index of old GUB constraint of given variable |
| newgubcons | index of new GUB constraint of given variable |
Definition at line 1801 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, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPvarGetName().
Referenced by getLiftingSequenceGUB().
|
static |
swaps two variables in the same GUB constraint
| scip | SCIP data structure |
| gubset | GUB set data structure |
| var1 | first variable to be swapped |
| var2 | second variable to be swapped |
Definition at line 1892 of file cons_knapsack.c.
Referenced by getLiftingSequenceGUB(), and GUBsetMoveVar().
|
static |
initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable)
| scip | SCIP data structure |
| gubset | pointer to store GUB set data structure |
| nvars | number of variables in the knapsack constraint |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
Definition at line 1932 of file cons_knapsack.c.
Referenced by SCIPseparateKnapsackCuts().
|
static |
frees GUB set data structure
| scip | SCIP data structure |
| gubset | pointer to GUB set data structure |
Definition at line 1982 of file cons_knapsack.c.
Referenced by SCIPseparateKnapsackCuts().
|
static |
checks whether GUB set data structure is consistent
| scip | SCIP data structure |
| gubset | GUB set data structure |
| vars | variables in the knapsack constraint |
Definition at line 2016 of file cons_knapsack.c.
|
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
| scip | SCIP data structure |
| vars | binary variables in the clique from which at most one can be set to 1 |
| nvars | number of variables in the clique |
| cliquepartition | array of length nvars to store the clique partition |
| ncliques | pointer to store number of cliques actually contained in the partition |
| solvals | solution values of all given binary variables |
Definition at line 2101 of file cons_knapsack.c.
References GUBsetGetCliquePartition(), MAXNCLIQUEVARSCOMP, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPsortIntInt(), SCIPvarGetNCliques(), SCIPvarIsActive(), SCIPvarsGetProbvarBinary(), SCIPvarsHaveCommonClique(), and TRUE.
|
static |
constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs
| scip | SCIP data structure |
| gubset | GUB set data structure |
| vars | variables in the knapsack constraint |
| solvals | solution values of all knapsack variables |
Definition at line 2259 of file cons_knapsack.c.
Referenced by GUBsetCalcCliquePartition(), and SCIPseparateKnapsackCuts().
|
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.
| scip | SCIP data structure |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| covervars | pointer to store cover variables |
| noncovervars | pointer to store noncover variables |
| ncovervars | pointer to store number of cover variables |
| nnoncovervars | pointer to store number of noncover variables |
| coverweight | pointer to store weight of cover |
| found | pointer to store whether a cover was found |
| modtransused | should modified transformed separation problem be used to find cover |
| ntightened | pointer to store number of variables with tightened upper bound |
| fractional | pointer to store whether the LP sol for knapsack vars is fractional |
Definition at line 2356 of file cons_knapsack.c.
References checkMinweightidx(), FALSE, 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().
|
static |
checks if minweightidx is set correctly
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| covervars | pointer to store cover variables |
| ncovervars | pointer to store number of cover variables |
| coverweight | pointer to store weight of cover |
| minweightidx | index of variable in cover variables with minimum weight |
| j | current index in cover variables |
Definition at line 2587 of file cons_knapsack.c.
References FALSE, getPartitionCovervars(), SCIP_Longint, SCIP_Real, and TRUE.
Referenced by getCover(), and makeCoverMinimal().
|
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\)
| scip | SCIP data structure |
| solvals | solution values of all problem variables |
| covervars | cover variables |
| ncovervars | number of cover variables |
| varsC1 | pointer to store variables in C1 |
| varsC2 | pointer to store variables in C2 |
| nvarsC1 | pointer to store number of variables in C1 |
| nvarsC2 | pointer to store number of variables in C2 |
Definition at line 2630 of file cons_knapsack.c.
References changePartitionCovervars(), SCIP_Longint, SCIPisFeasGT(), SCIPisGE(), and SCIPisLT().
Referenced by checkMinweightidx(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
|
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.
| scip | SCIP data structure |
| weights | weights of variables in knapsack constraint |
| varsC1 | pointer to store variables in C1 |
| varsC2 | pointer to store variables in C2 |
| nvarsC1 | pointer to store number of variables in C1 |
| nvarsC2 | pointer to store number of variables in C2 |
Definition at line 2679 of file cons_knapsack.c.
References changePartitionFeasiblesetvars(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().
Referenced by getPartitionCovervars(), and separateSequLiftedMinimalCoverInequality().
|
static |
changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1
| scip | SCIP data structure |
| weights | weights of variables in knapsack constraint |
| varsC1 | pointer to store variables in C1 |
| varsC2 | pointer to store variables in C2 |
| nvarsC1 | pointer to store number of variables in C1 |
| nvarsC2 | pointer to store number of variables in C2 |
Definition at line 2719 of file cons_knapsack.c.
References getPartitionNoncovervars(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().
Referenced by changePartitionCovervars(), and separateSequLiftedExtendedWeightInequality().
|
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\)
| scip | SCIP data structure |
| solvals | solution values of all problem variables |
| noncovervars | noncover variables |
| nnoncovervars | number of noncover variables |
| varsF | pointer to store variables in F |
| varsR | pointer to store variables in R |
| nvarsF | pointer to store number of variables in F |
| nvarsR | pointer to store number of variables in R |
Definition at line 2760 of file cons_knapsack.c.
References getLiftingSequence(), SCIP_Longint, SCIP_Real, SCIPisFeasEQ(), and SCIPisFeasGT().
Referenced by changePartitionFeasiblesetvars(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
|
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
| scip | SCIP data structure |
| solvals | solution values of all problem variables |
| weights | weights of variables in knapsack constraint |
| varsF | pointer to store variables in F |
| varsC2 | pointer to store variables in C2 |
| varsR | pointer to store variables in R |
| nvarsF | number of variables in F |
| nvarsC2 | number of variables in C2 |
| nvarsR | number of variables in R |
Definition at line 2808 of file cons_knapsack.c.
References getLiftingSequenceGUB(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownPtrInt(), and SCIPsortDownRealInt().
Referenced by getPartitionNoncovervars(), separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
|
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
| scip | SCIP data structure |
| gubset | GUB set data structure |
| solvals | solution values of variables in knapsack constraint |
| weights | weights of variables in knapsack constraint |
| varsC1 | variables in C1 |
| varsC2 | variables in C2 |
| varsF | variables in F |
| varsR | variables in R |
| nvarsC1 | number of variables in C1 |
| nvarsC2 | number of variables in C2 |
| nvarsF | number of variables in F |
| nvarsR | number of variables in R |
| gubconsGC1 | pointer to store GUBs in GC1(GNC1+GOC1) |
| gubconsGC2 | pointer to store GUBs in GC2 |
| gubconsGFC1 | pointer to store GUBs in GFC1(GNC1+GF) |
| gubconsGR | pointer to store GUBs in GR |
| ngubconsGC1 | pointer to store number of GUBs in GC1(GNC1+GOC1) |
| ngubconsGC2 | pointer to store number of GUBs in GC2 |
| ngubconsGFC1 | pointer to store number of GUBs in GFC1(GNC1+GF) |
| ngubconsGR | pointer to store number of GUBs in GR |
| ngubconscapexceed | pointer to store number of GUBs with only capacity exceeding variables |
| maxgubvarssize | pointer to store the maximal size of GUB constraints |
Definition at line 2894 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, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPsortDownPtrInt(), SCIPsortDownRealInt(), SCIPsortRealInt(), and TRUE.
Referenced by getLiftingSequence(), and separateSequLiftedMinimalCoverInequality().
|
static |
enlarges minweight table to at least the given length
| scip | SCIP data structure |
| minweightsptr | pointer to minweights table |
| minweightslen | pointer to store number of entries in minweights table (incl. z=0) |
| minweightssize | pointer to current size of minweights table |
| newlen | new length of minweights table |
Definition at line 3414 of file cons_knapsack.c.
Referenced by getLiftingSequenceGUB(), sequentialUpAndDownLifting(), and sequentialUpAndDownLiftingGUB().
|
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.
| scip | SCIP data structure |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| varsM1 | variables in M_1 |
| varsM2 | variables in M_2 |
| varsF | variables in F |
| varsR | variables in R |
| nvarsM1 | number of variables in M_1 |
| nvarsM2 | number of variables in M_2 |
| nvarsF | number of variables in F |
| nvarsR | number of variables in R |
| alpha0 | rights hand side of given valid inequality |
| liftcoefs | pointer to store lifting coefficient of vars in knapsack constraint |
| cutact | pointer to store activity of lifted valid inequality |
| liftrhs | pointer to store right hand side of the lifted valid inequality |
Definition at line 3464 of file cons_knapsack.c.
References BMSclearMemoryArray, enlargeMinweights(), safeAddMinweightsGUB(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPisFeasGT(), and SCIPsortRealInt().
Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
|
static |
adds two minweight values in a safe way, i.e,, ensures no overflow
| val1 | first value to add |
| val2 | second value to add |
Definition at line 3842 of file cons_knapsack.c.
References computeMinweightsGUB(), SCIP_Longint, and SCIP_LONGINT_MAX.
Referenced by sequentialUpAndDownLifting(), and sequentialUpAndDownLiftingGUB().
|
static |
computes minweights table for lifting with GUBs by combining unfished and fished tables
| minweights | minweight table to compute |
| finished | given finished table |
| unfinished | given unfinished table |
| minweightslen | length of minweight, finished, and unfinished tables |
Definition at line 3861 of file cons_knapsack.c.
Referenced by safeAddMinweightsGUB(), and sequentialUpAndDownLiftingGUB().
|
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.
| scip | SCIP data structure |
| gubset | GUB set data structure |
| vars | variables in knapsack constraint |
| ngubconscapexceed | number of GUBs with only capacity exceeding variables |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all knapsack variables |
| gubconsGC1 | GUBs in GC1(GNC1+GOC1) |
| gubconsGC2 | GUBs in GC2 |
| gubconsGFC1 | GUBs in GFC1(GNC1+GF) |
| gubconsGR | GUBs in GR |
| ngubconsGC1 | number of GUBs in GC1(GNC1+GOC1) |
| ngubconsGC2 | number of GUBs in GC2 |
| ngubconsGFC1 | number of GUBs in GFC1(GNC1+GF) |
| ngubconsGR | number of GUBs in GR |
| alpha0 | rights hand side of given valid inequality |
| liftcoefs | pointer to store lifting coefficient of vars in knapsack constraint |
| cutact | pointer to store activity of lifted valid inequality |
| liftrhs | pointer to store right hand side of the lifted valid inequality |
| maxgubvarssize | maximal size of GUB constraints |
Definition at line 3913 of file cons_knapsack.c.
References BMSclearMemoryArray, computeMinweightsGUB(), enlargeMinweights(), SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconsstatus, GUBCONSSTATUS_BELONGSTOSET_GC2, GUBCONSSTATUS_BELONGSTOSET_GF, GUBCONSSTATUS_BELONGSTOSET_GNC1, GUBCONSSTATUS_BELONGSTOSET_GOC1, GUBCONSSTATUS_BELONGSTOSET_GR, SCIP_GUBCons::gubvars, SCIP_GUBCons::gubvarsstatus, GUBVARSTATUS_BELONGSTOSET_C1, GUBVARSTATUS_BELONGSTOSET_C2, GUBVARSTATUS_BELONGSTOSET_F, GUBVARSTATUS_BELONGSTOSET_R, GUBVARSTATUS_CAPACITYEXCEEDED, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, SCIP_GUBSet::nvars, safeAddMinweightsGUB(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), and superadditiveUpLifting().
Referenced by separateSequLiftedMinimalCoverInequality().
|
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\).
| scip | SCIP data structure |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| covervars | cover variables |
| noncovervars | noncover variables |
| ncovervars | number of cover variables |
| nnoncovervars | number of noncover variables |
| coverweight | weight of cover |
| liftcoefs | pointer to store lifting coefficient of vars in knapsack constraint |
| cutact | pointer to store activity of lifted valid inequality |
Definition at line 4648 of file cons_knapsack.c.
References BMSclearMemoryArray, MAX, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), SCIPsortRealInt(), and separateSequLiftedMinimalCoverInequality().
Referenced by separateSupLiftedMinimalCoverInequality(), and sequentialUpAndDownLiftingGUB().
|
static |
separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for given knapsack problem
| scip | SCIP data structure |
| cons | originating constraint of the knapsack problem, or NULL |
| sepa | originating separator of the knapsack problem, or NULL |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| mincovervars | mincover variables |
| nonmincovervars | nonmincover variables |
| nmincovervars | number of mincover variables |
| nnonmincovervars | number of nonmincover variables |
| sol | primal SCIP solution to separate, NULL for current LP solution |
| gubset | GUB set data structure, NULL if no GUB information should be used |
| cutoff | pointer to store whether a cutoff has been detected |
| ncuts | pointer to add up the number of found cuts |
Definition at line 4779 of file cons_knapsack.c.
References changePartitionCovervars(), FALSE, getLiftingSequence(), getLiftingSequenceGUB(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, SCIP_GUBSet::ngubconss, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), separateSequLiftedExtendedWeightInequality(), sequentialUpAndDownLifting(), sequentialUpAndDownLiftingGUB(), sqrt(), and TRUE.
Referenced by SCIPseparateKnapsackCuts(), and superadditiveUpLifting().
|
static |
separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem
| scip | SCIP data structure |
| cons | constraint that originates the knapsack problem, or NULL |
| sepa | originating separator of the knapsack problem, or NULL |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| feassetvars | variables in feasible set |
| nonfeassetvars | variables not in feasible set |
| nfeassetvars | number of variables in feasible set |
| nnonfeassetvars | number of variables not in feasible set |
| sol | primal SCIP solution to separate, NULL for current LP solution |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to add up the number of found cuts |
Definition at line 5013 of file cons_knapsack.c.
References changePartitionFeasiblesetvars(), FALSE, getLiftingSequence(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), separateSupLiftedMinimalCoverInequality(), sequentialUpAndDownLifting(), sqrt(), and TRUE.
Referenced by getFeasibleSet(), and separateSequLiftedMinimalCoverInequality().
|
static |
separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem
| scip | SCIP data structure |
| cons | constraint that originates the knapsack problem, or NULL |
| sepa | originating separator of the knapsack problem, or NULL |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| mincovervars | mincover variables |
| nonmincovervars | nonmincover variables |
| nmincovervars | number of mincover variables |
| nnonmincovervars | number of nonmincover variables |
| mincoverweight | weight of minimal cover |
| sol | primal SCIP solution to separate, NULL for current LP solution |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to add up the number of found cuts |
Definition at line 5180 of file cons_knapsack.c.
References FALSE, makeCoverMinimal(), MAX, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNCutsFound(), SCIPconsIsLocal(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateEmptyRowUnspec(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsepaGetName(), SCIPsepaGetNCutsFound(), SCIPsnprintf(), sqrt(), superadditiveUpLifting(), and TRUE.
Referenced by SCIPseparateKnapsackCuts(), and separateSequLiftedExtendedWeightInequality().
|
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
| scip | SCIP data structure |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| covervars | pointer to store cover variables |
| noncovervars | pointer to store noncover variables |
| ncovervars | pointer to store number of cover variables |
| nnoncovervars | pointer to store number of noncover variables |
| coverweight | pointer to store weight of cover |
| modtransused | TRUE if mod trans sepa prob was used to find cover |
Definition at line 5294 of file cons_knapsack.c.
References checkMinweightidx(), getFeasibleSet(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPsortPtrInt().
Referenced by SCIPseparateKnapsackCuts(), and separateSupLiftedMinimalCoverInequality().
|
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.
| scip | SCIP data structure |
| cons | constraint that originates the knapsack problem |
| sepa | originating separator of the knapsack problem, or NULL |
| vars | variables in knapsack constraint |
| nvars | number of variables in knapsack constraint |
| ntightened | number of variables with tightened upper bound |
| weights | weights of variables in knapsack constraint |
| capacity | capacity of knapsack |
| solvals | solution values of all problem variables |
| covervars | pointer to store cover variables |
| noncovervars | pointer to store noncover variables |
| ncovervars | pointer to store number of cover variables |
| nnoncovervars | pointer to store number of noncover variables |
| coverweight | pointer to store weight of cover |
| modtransused | TRUE if mod trans sepa prob was used to find cover |
| sol | primal SCIP solution to separate, NULL for current LP solution |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to add up the number of found cuts |
Definition at line 5437 of file cons_knapsack.c.
References FALSE, MAXCOVERSIZEITERLEWI, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLE(), SCIPseparateKnapsackCuts(), SCIPsortRealInt(), and separateSequLiftedExtendedWeightInequality().
Referenced by makeCoverMinimal(), and SCIPseparateKnapsackCuts().
|
static |
separates given knapsack constraint
| scip | SCIP data structure |
| cons | knapsack constraint |
| sol | primal SCIP solution, NULL for current LP solution |
| sepacuts | should knapsack cuts be separated? |
| usegubs | should GUB information be used for separation? |
| cutoff | whether a cutoff has been detected |
| ncuts | pointer to add up the number of found cuts |
Definition at line 6192 of file cons_knapsack.c.
References addCoef(), addRelaxation(), checkCons(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, and SCIPseparateKnapsackCuts().
Referenced by SCIPseparateRelaxedKnapsack().
|
static |
adds coefficient to constraint data
| scip | SCIP data structure |
| cons | knapsack constraint |
| var | variable to add to knapsack |
| weight | weight of variable in knapsack |
Definition at line 6234 of file cons_knapsack.c.
Referenced by SCIPaddCoefKnapsack(), and separateCons().
|
static |
deletes coefficient at given position from constraint data
| scip | SCIP data structure |
| cons | knapsack constraint |
| pos | position of coefficient to delete |
Definition at line 6314 of file cons_knapsack.c.
Referenced by deleteRedundantVars(), dualWeightsTightening(), and simplifyInequalities().
|
static |
removes all items with weight zero from knapsack constraint
| scip | SCIP data structure |
| cons | knapsack constraint |
Definition at line 6504 of file cons_knapsack.c.
Referenced by tightenWeights().
|
static |
| scip | SCIP data structure |
| conshdlr | constraint handler |
| conss | array of constraints |
| nconss | number of constraints |
Definition at line 6528 of file cons_knapsack.c.
|
static |
replaces multiple occurrences of a variable or its negation by a single coefficient
| scip | SCIP data structure |
| cons | knapsack constraint |
| cutoff | pointer to store whether the node can be cut off |
Definition at line 6570 of file cons_knapsack.c.
Referenced by simplifyInequalities(), and tightenWeights().
|
static |
in case the knapsack constraint is independent of every else, solve the knapsack problem (exactly) and apply the fixings (dual reductions)
| scip | SCIP data structure |
| cons | knapsack constraint |
| nfixedvars | pointer to count number of fixings |
| ndelconss | pointer to count number of deleted constraints |
| deleted | pointer to store if the constraint is deleted |
Definition at line 6713 of file cons_knapsack.c.
|
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
| scip | SCIP data structure |
| cons | knapsack constraint |
| conshdlrdata | knapsack constraint handler data |
Definition at line 6854 of file cons_knapsack.c.
|
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
| scip | SCIP data structure |
| consdata | knapsack constraint data |
| vars | array for sorted variables |
| weights | array for sorted weights |
| cliquestartposs | starting position array for each clique |
| usenegatedclique | should negated or normal clique partition be used |
Definition at line 7007 of file cons_knapsack.c.
References applyFixings(), BMSclearMemoryArray, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by propagateCons().
|
static |
deletes all fixed variables from knapsack constraint, and replaces variables with binary representatives
| scip | SCIP data structure |
| cons | knapsack constraint |
| cutoff | pointer to store whether the node can be cut off, or NULL if this information is not needed; in this case, we apply all fixings instead of stopping after the first infeasible one |
Definition at line 7131 of file cons_knapsack.c.
Referenced by SCIP_DECL_CONSEXITPRE(), and stableSort().
|
static |
propagation method for knapsack constraints
| scip | SCIP data structure |
| cons | knapsack constraint |
| cutoff | pointer to store whether the node can be cut off |
| redundant | pointer to store whether constraint is redundant |
| nfixedvars | pointer to count number of fixings |
| usenegatedclique | should negated clique information be used |
Definition at line 7342 of file cons_knapsack.c.
References BMSclearMemoryArray, calcCliquepartition(), FALSE, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_VARSTATUS_FIXED, SCIPaddConflictBinvar(), SCIPallocBufferArray, SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetStage(), SCIPincConsAge(), SCIPinferBinvarCons(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPinRepropagation(), SCIPisConflictAnalysisApplicable(), SCIPresetConsAge(), SCIPvarGetIndex(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsNegated(), sortItems(), stableSort(), TRUE, and upgradeCons().
|
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
| scip | SCIP data structure |
| cons | knapsack constraint |
| ndelconss | pointer to store the amount of deleted constraints |
| naddconss | pointer to count number of added constraints |
Definition at line 7805 of file cons_knapsack.c.
Referenced by detectRedundantVars(), dualWeightsTightening(), and propagateCons().
|
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
| scip | SCIP data structure |
| cons | knapsack constraint |
| frontsum | sum of front items which fit if we try to take from the first till the last |
| splitpos | split position till when all front items are fitting, splitpos is the first which did not fit |
| nchgcoefs | pointer to store the amount of changed coefficients |
| nchgsides | pointer to store the amount of changed sides |
| naddconss | pointer to count number of added constraints |
Definition at line 7877 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), detectRedundantVars(), SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcalcCliquePartition(), SCIPcalcGreComDiv(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, SCIPreleaseCons(), and SCIPsnprintf().
Referenced by detectRedundantVars().
|
static |
| scip | SCIP data structure |
| cons | knapsack constraint |
| ndelconss | pointer to store the amount of deleted constraints |
| nchgcoefs | pointer to store the amount of changed coefficients |
| nchgsides | pointer to store the amount of changed sides |
| naddconss | pointer to count number of added constraints |
Definition at line 8128 of file cons_knapsack.c.
References calcCliquepartition(), deleteRedundantVars(), FALSE, normalizeWeights(), SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), TRUE, and upgradeCons().
Referenced by deleteRedundantVars(), and simplifyInequalities().
|
static |
divides weights by their greatest common divisor and divides capacity by the same value, rounding down the result
| cons | knapsack constraint |
| nchgcoefs | pointer to count total number of changed coefficients |
| nchgsides | pointer to count number of side changes |
Definition at line 8317 of file cons_knapsack.c.
Referenced by detectRedundantVars(), and dualWeightsTightening().
|
static |
dual weights tightening for knapsack constraints
check if besides big coefficients, that fit only by itself, for a certain amount of variables all combination of these are a minimal cover, then might reduce the weights and the capacity, e.g.
+219y1 + 180y2 + 74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3
use the duality between a^Tx <= capacity <=> a^T~x >= weightsum - capacity to tighten weights, e.g.
11x1 + 10x2 + 7x3 + 7x4 + 5x5 <= 27 <=> 11~x1 + 10~x2 + 7~x3 + 7~x4 + 5~x5 >= 13
the above constraint can be changed to 8~x1 + 8~x2 + 6.5~x3 + 6.5~x4 + 5~x5 >= 13
16~x1 + 16~x2 + 13~x3 + 13~x4 + 10~x5 >= 26 <=> 16x1 + 16x2 + 13x3 + 13x4 + 10x5 <= 42
| scip | SCIP data structure |
| cons | knapsack constraint |
| ndelconss | pointer to store the amount of deleted constraints |
| nchgcoefs | pointer to store the amount of changed coefficients |
| nchgsides | pointer to store the amount of changed sides |
| naddconss | pointer to count number of added constraints |
Definition at line 8391 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), FALSE, normalizeWeights(), 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, and upgradeCons().
Referenced by simplifyInequalities().
|
static |
fixes variables with weights bigger than the capacity and delete redundant constraints, also sort weights
| scip | SCIP data structure |
| cons | knapsack constraint |
| nfixedvars | pointer to store the amount of fixed variables |
| ndelconss | pointer to store the amount of deleted constraints |
| nchgcoefs | pointer to store the amount of changed coefficients |
Definition at line 9252 of file cons_knapsack.c.
Referenced by dualWeightsTightening(), and simplifyInequalities().
|
static |
tries to simplify weights and delete redundant variables in knapsack a^Tx <= capacity
use the duality between a^Tx <= capacity <=> -a^T~x <= capacity - weightsum to tighten weights, e.g.
11x1 + 10x2 + 7x3 + 5x4 + 5x5 <= 25 <=> -10~x1 - 10~x2 - 7~x3 - 5~x4 - 5~x5 <= -13
the above constraint can be changed to
-8~x1 - 8~x2 - 7~x3 - 5~x4 - 5~x5 <= -12 <=> 8x1 + 8x2 + 7x3 + 5x4 + 5x5 <= 20
if variables in a constraint do not affect the (in-)feasibility of the constraint, we can delete them, e.g.
7x1 + 6x2 + 5x3 + 5x4 + x5 + x6 <= 20 => x5 and x6 are redundant and can be removed
Tries to use gcd information an all but one weight to change this not-included weight and normalize the constraint further, e.g.
9x1 + 6x2 + 6x3 + 5x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => 3x1 + 2x2 + 2x3 + 2x4 <= 4 => 4x1 + 2x2 + 2x3 + 2x4 <= 4 => 2x1 + x2 + x3 + x4 <= 2 9x1 + 6x2 + 6x3 + 7x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => see above
| scip | SCIP data structure |
| cons | knapsack constraint |
| nfixedvars | pointer to store the amount of fixed variables |
| ndelconss | pointer to store the amount of deleted constraints |
| nchgcoefs | pointer to store the amount of changed coefficients |
| nchgsides | pointer to store the amount of changed sides |
| naddconss | pointer to count number of added constraints |
| cutoff | pointer to store whether the node can be cut off |
Definition at line 9369 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), detectRedundantVars(), dualWeightsTightening(), FALSE, insertZerolist(), mergeMultiples(), SCIP_GUBSet::nvars, prepareCons(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPcalcGreComDiv(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPdebug, SCIPdebugMsg, SCIPdebugPrintCons, SCIPisHugeValue(), and SCIPvarGetName().
|
static |
inserts an element into the list of binary zero implications
| scip | SCIP data structure |
| liftcands | array of the lifting candidates |
| nliftcands | number of lifting candidates |
| firstidxs | array of first zeroitems indices |
| zeroweightsums | array of sums of weights of the implied-to-zero items |
| zeroitems | pointer to zero items array |
| nextidxs | pointer to array of next zeroitems indeces |
| zeroitemssize | pointer to size of zero items array |
| nzeroitems | pointer to length of zero items array |
| probindex | problem index of variable y in implication y == v -> x == 0 |
| value | value v of variable y in implication |
| knapsackidx | index of variable x in knapsack |
| knapsackweight | weight of variable x in knapsack |
| memlimitreached | pointer to store whether the memory limit was reached |
Definition at line 9681 of file cons_knapsack.c.
References FALSE, MAX_ZEROITEMS_SIZE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNContVars(), SCIPgetNVars(), SCIPreallocBufferArray, and TRUE.
Referenced by simplifyInequalities().
|
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:
| scip | SCIP data structure |
| cons | knapsack constraint |
| nchgcoefs | pointer to count total number of changed coefficients |
| cutoff | pointer to store whether the node can be cut off |
Definition at line 9767 of file cons_knapsack.c.
Referenced by tightenWeights().
|
static |
tightens item weights and capacity in presolving: given a knapsack sum(wi*xi) <= capacity (1) let weightsum := sum(wi) if weightsum - wi < capacity:
| scip | SCIP data structure |
| cons | knapsack constraint |
| presoltiming | current presolving timing |
| nchgcoefs | pointer to count total number of changed coefficients |
| nchgsides | pointer to count number of side changes |
| naddconss | pointer to count number of added constraints |
| ndelconss | pointer to count number of deleted constraints |
| cutoff | pointer to store whether the node can be cut off |
Definition at line 10331 of file cons_knapsack.c.
References addNegatedCliques(), calcCliquepartition(), consdataChgWeight(), FALSE, MAX, MAX_USECLIQUES_SIZE, mergeMultiples(), SCIP_GUBSet::nvars, removeZeroWeights(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIPaddCons(), SCIPallocBufferArray, SCIPcalcCliquePartition(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdebugPrintf, SCIPdelCons(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), sortItems(), tightenWeightsLift(), and TRUE.
|
static |
adds negated cliques of the knapsack constraint to the global clique table
| scip | SCIP data structure |
| cons | knapsack constraint |
| cutoff | pointer to store whether the node can be cut off |
| nbdchgs | pointer to count the number of performed bound changes |
Definition at line 10920 of file cons_knapsack.c.
Referenced by tightenWeights().
|
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
| scip | SCIP data structure |
| items | array of variable items |
| weights | weights of the items |
| nitems | the number of items |
| capacity | maximum free capacity of the knapsack |
| sorteditems | are the items sorted by their weights nonincreasing? |
| cliqueextractfactor | lower clique size limit for greedy clique extraction algorithm (relative to largest clique) |
| cutoff | pointer to store whether the node can be cut off |
| nbdchgs | pointer to count the number of performed bound changes |
Definition at line 11124 of file cons_knapsack.c.
References addCliques(), FALSE, MAX, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddClique(), SCIPdebug, SCIPduplicateBufferArray, SCIPfreeBufferArray, and SCIPsortDownLongPtr().
|
static |
adds cliques of the knapsack constraint to the global clique table
| scip | SCIP data structure |
| cons | knapsack constraint |
| cliqueextractfactor | lower clique size limit for greedy clique extraction algorithm (relative to largest clique) |
| cutoff | pointer to store whether the node can be cut off |
| nbdchgs | pointer to count the number of performed bound changes |
Definition at line 11236 of file cons_knapsack.c.
Referenced by greedyCliqueAlgorithm().
|
static |
gets the key of the given element
Definition at line 11382 of file cons_knapsack.c.
|
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 11392 of file cons_knapsack.c.
|
static |
returns the hash value of the key
Definition at line 11435 of file cons_knapsack.c.
|
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
| scip | SCIP data structure |
| blkmem | block memory |
| conss | constraint set |
| nconss | number of constraints in constraint set |
| cutoff | pointer to store whether the problem is infeasible |
| ndelconss | pointer to count number of deleted constraints |
Definition at line 11471 of file cons_knapsack.c.
References HASHSIZE_KNAPSACKCONS, MAX, preprocessConstraintPairs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPupdateConsFlags(), and TRUE.
|
static |
compares constraint with all prior constraints for possible redundancy or aggregation, and removes or changes constraint accordingly
| scip | SCIP data structure |
| conss | constraint set |
| firstchange | first constraint that changed since last pair preprocessing round |
| chkind | index of constraint to check against all prior indices upto startind |
| ndelconss | pointer to count number of deleted constraints |
Definition at line 11595 of file cons_knapsack.c.
Referenced by detectRedundantConstraints().
|
static |
helper function to enforce constraints
| scip | SCIP data structure |
| conshdlr | constraint handler |
| conss | constraints to process |
| nconss | number of constraints |
| nusefulconss | number of useful (non-obsolete) constraints to process |
| sol | solution to enforce (NULL for the LP solution) |
| result | pointer to store the result of the enforcing call |
Definition at line 11785 of file cons_knapsack.c.
References addRelaxation(), checkCons(), createNormalizedKnapsack(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMsg, and SCIPgetDepth().
Referenced by SCIP_DECL_CONSENFOLP().
|
static |
creates and captures a knapsack constraint out of a linear inequality
| scip | SCIP data structure |
| cons | pointer to hold the created constraint |
| name | name of constraint |
| nvars | number of variables in the constraint |
| vars | array with variables of constraint entries |
| vals | array with inequality coefficients |
| lhs | left hand side of inequality |
| rhs | right hand side of inequality |
| initial | should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'. |
| separate | should the constraint be separated during LP processing? Usually set to TRUE. |
| enforce | should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints. |
| check | should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints. |
| propagate | should the constraint be propagated during node processing? Usually set to TRUE. |
| local | is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. |
| modifiable | is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint. |
| dynamic | is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints. |
| removable | should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. |
| stickingatnode | should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data. |
Definition at line 11851 of file cons_knapsack.c.
References 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().
|
static |
tries to upgrade a linear constraint into a knapsack constraint
Definition at line 11946 of file cons_knapsack.c.
References CONSHDLR_NAME, createNormalizedKnapsack(), SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, and SCIPincludeConshdlrKnapsack().
Referenced by createNormalizedKnapsack().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins) ! [SnippetConsCopyKnapsack]
Definition at line 11985 of file cons_knapsack.c.
References SCIPconshdlrGetData().
Referenced by SCIP_DECL_LINCONSUPGD().
|
static |
! [SnippetConsCopyKnapsack] destructor of constraint handler to free constraint handler data (called when SCIP is exiting) ! [SnippetConsFreeKnapsack]
Definition at line 12003 of file cons_knapsack.c.
|
static |
! [SnippetConsFreeKnapsack] initialization method of constraint handler (called after problem was transformed)
Definition at line 12022 of file cons_knapsack.c.
|
static |
deinitialization method of constraint handler (called before transformed problem is freed)
Definition at line 12044 of file cons_knapsack.c.
|
static |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 12063 of file cons_knapsack.c.
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished)
Definition at line 12106 of file cons_knapsack.c.
References applyFixings(), SCIP_CALL, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconsIsDeleted(), and SCIPfreeBlockMemoryArrayNull.
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 12150 of file cons_knapsack.c.
References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPreleaseRow().
Referenced by SCIP_DECL_CONSEXITPRE().
|
static |
frees specific constraint data
Definition at line 12174 of file cons_knapsack.c.
Referenced by SCIP_DECL_CONSEXITSOL().
|
static |
transforms constraint data into data belonging to the transformed problem ! [SnippetConsTransKnapsack]
Definition at line 12195 of file cons_knapsack.c.
|
static |
! [SnippetConsTransKnapsack] LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 12236 of file cons_knapsack.c.
|
static |
separation method of constraint handler for LP solutions
Definition at line 12253 of file cons_knapsack.c.
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 12327 of file cons_knapsack.c.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 12387 of file cons_knapsack.c.
References enforceConstraint(), SCIP_CALL, and SCIP_OKAY.
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 12396 of file cons_knapsack.c.
References checkCons(), FALSE, SCIP_Bool, SCIP_CALL, and TRUE.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 12405 of file cons_knapsack.c.
References SCIP_Bool, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, and SCIP_OKAY.
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 12426 of file cons_knapsack.c.
References checkCons(), SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_INFEASIBLE, and SCIP_OKAY.
Referenced by SCIP_DECL_CONSENFOPS().
|
static |
domain propagation method of constraint handler
Definition at line 12445 of file cons_knapsack.c.
Referenced by SCIP_DECL_CONSCHECK().
|
static |
presolving method of constraint handler
Definition at line 12496 of file cons_knapsack.c.
|
static |
propagation conflict resolving method of constraint handler
Definition at line 12923 of file cons_knapsack.c.
|
static |
variable rounding lock method of constraint handler ! [SnippetConsLockKnapsack]
Definition at line 13007 of file cons_knapsack.c.
References SCIP_CALL, SCIP_DECL_CONSDELVARS(), SCIP_OKAY, and SCIPaddVarLocks().
|
static |
! [SnippetConsLockKnapsack] variable deletion method of constraint handler
Definition at line 13027 of file cons_knapsack.c.
Referenced by SCIP_DECL_CONSLOCK().
|
static |
constraint display method of constraint handler
Definition at line 13043 of file cons_knapsack.c.
|
static |
constraint copying method of constraint handler
Definition at line 13069 of file cons_knapsack.c.
|
static |
constraint parsing method of constraint handler
Definition at line 13105 of file cons_knapsack.c.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 13205 of file cons_knapsack.c.
References BMScopyMemoryArray, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 13227 of file cons_knapsack.c.
References SCIPconsGetData().
Referenced by SCIP_DECL_CONSGETVARS().
|
static |
execution method of bound change event handler
Definition at line 13246 of file cons_knapsack.c.