Detailed Description
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 "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 |
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_Longint * | SCIPgetWeightsKnapsack (SCIP *scip, SCIP_CONS *cons) |
SCIP_Real | SCIPgetDualsolKnapsack (SCIP *scip, SCIP_CONS *cons) |
SCIP_Real | SCIPgetDualfarkasKnapsack (SCIP *scip, SCIP_CONS *cons) |
SCIP_ROW * | SCIPgetRowKnapsack (SCIP *scip, SCIP_CONS *cons) |
SCIP_RETCODE | SCIPcleanupConssKnapsack (SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible) |
Macro Definition Documentation
◆ CONSHDLR_NAME
#define CONSHDLR_NAME "knapsack" |
Definition at line 81 of file cons_knapsack.c.
◆ CONSHDLR_DESC
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 89 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 90 of file cons_knapsack.c.
◆ CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 91 of file cons_knapsack.c.
◆ CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 92 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 93 of file cons_knapsack.c.
◆ CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
Definition at line 95 of file cons_knapsack.c.
◆ CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 96 of file cons_knapsack.c.
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "knapsack" |
Definition at line 98 of file cons_knapsack.c.
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "bound change event handler for knapsack constraints" |
Definition at line 99 of file cons_knapsack.c.
◆ EVENTTYPE_KNAPSACK
#define EVENTTYPE_KNAPSACK |
variable events that should be caught by the event handler
Definition at line 104 of file cons_knapsack.c.
◆ LINCONSUPGD_PRIORITY
#define LINCONSUPGD_PRIORITY +100000 |
priority of the constraint handler for upgrading of linear constraints
Definition at line 106 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 108 of file cons_knapsack.c.
◆ MAX_ZEROITEMS_SIZE
#define MAX_ZEROITEMS_SIZE 10000 |
maximal number of items to store in the zero list in preprocessing
Definition at line 109 of file cons_knapsack.c.
◆ KNAPSACKRELAX_MAXDELTA
#define KNAPSACKRELAX_MAXDELTA 0.1 |
maximal allowed rounding distance for scaling in knapsack relaxation
Definition at line 111 of file cons_knapsack.c.
◆ KNAPSACKRELAX_MAXDNOM
#define KNAPSACKRELAX_MAXDNOM 1000LL |
maximal allowed denominator in knapsack rational relaxation
Definition at line 112 of file cons_knapsack.c.
◆ KNAPSACKRELAX_MAXSCALE
#define KNAPSACKRELAX_MAXSCALE 1000.0 |
maximal allowed scaling factor in knapsack rational relaxation
Definition at line 113 of file cons_knapsack.c.
◆ DEFAULT_SEPACARDFREQ
#define DEFAULT_SEPACARDFREQ 1 |
multiplier on separation frequency, how often knapsack cuts are separated
Definition at line 115 of file cons_knapsack.c.
◆ DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS 5 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 116 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 117 of file cons_knapsack.c.
◆ DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS 50 |
maximal number of cuts separated per separation round
Definition at line 118 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 119 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 122 of file cons_knapsack.c.
◆ DEFAULT_SIMPLIFYINEQUALITIES
#define DEFAULT_SIMPLIFYINEQUALITIES TRUE |
should presolving try to simplify knapsacks
Definition at line 123 of file cons_knapsack.c.
◆ DEFAULT_NEGATEDCLIQUE
#define DEFAULT_NEGATEDCLIQUE TRUE |
should negated clique information be used in solving process
Definition at line 124 of file cons_knapsack.c.
◆ MAXABSVBCOEF
#define MAXABSVBCOEF 1e+5 |
maximal absolute coefficient in variable bounds used for knapsack relaxation
Definition at line 126 of file cons_knapsack.c.
◆ USESUPADDLIFT
#define USESUPADDLIFT FALSE |
should lifted minimal cover inequalities using superadditive up-lifting be separated in addition
Definition at line 127 of file cons_knapsack.c.
◆ DEFAULT_PRESOLUSEHASHING
#define DEFAULT_PRESOLUSEHASHING TRUE |
should hash table be used for detecting redundant constraints in advance
Definition at line 129 of file cons_knapsack.c.
◆ HASHSIZE_KNAPSACKCONS
#define HASHSIZE_KNAPSACKCONS 500 |
minimal size of hash table in linear constraint tables
Definition at line 130 of file cons_knapsack.c.
◆ DEFAULT_PRESOLPAIRWISE
#define DEFAULT_PRESOLPAIRWISE TRUE |
should pairwise constraint comparison be performed in presolving?
Definition at line 132 of file cons_knapsack.c.
◆ NMINCOMPARISONS
#define NMINCOMPARISONS 200000 |
number for minimal pairwise presolving comparisons
Definition at line 133 of file cons_knapsack.c.
◆ MINGAINPERNMINCOMPARISONS
#define MINGAINPERNMINCOMPARISONS 1e-06 |
minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round
Definition at line 135 of file cons_knapsack.c.
◆ DEFAULT_DUALPRESOLVING
#define DEFAULT_DUALPRESOLVING TRUE |
should dual presolving steps be performed?
Definition at line 136 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 139 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 142 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 143 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 144 of file cons_knapsack.c.
◆ DEFAULT_USEGUBS
#define DEFAULT_USEGUBS FALSE |
should GUB information be used for separation?
Definition at line 146 of file cons_knapsack.c.
◆ GUBCONSGROWVALUE
#define GUBCONSGROWVALUE 6 |
memory growing value for GUB constraint array
Definition at line 147 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 148 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 150 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 151 of file cons_knapsack.c.
◆ MAXNCLIQUEVARSCOMP
#define MAXNCLIQUEVARSCOMP 1000000 |
limit on number of pairwise comparisons in clique partitioning algorithm
Definition at line 152 of file cons_knapsack.c.
◆ IDX
#define IDX | ( | j, | |
d | |||
) | ((j)*(intcap)+(d)) |
Definition at line 1065 of file cons_knapsack.c.
◆ MAX_CLIQUELENGTH
#define MAX_CLIQUELENGTH 50 |
Definition at line 9783 of file cons_knapsack.c.
Typedef Documentation
◆ SORTKEYPAIR
typedef struct sortkeypair SORTKEYPAIR |
Definition at line 269 of file cons_knapsack.c.
◆ GUBVARSTATUS
typedef enum GUBVarstatus GUBVARSTATUS |
Definition at line 281 of file cons_knapsack.c.
◆ GUBCONSSTATUS
typedef enum GUBConsstatus GUBCONSSTATUS |
Definition at line 293 of file cons_knapsack.c.
◆ SCIP_GUBCONS
typedef struct SCIP_GUBCons SCIP_GUBCONS |
Definition at line 303 of file cons_knapsack.c.
◆ SCIP_GUBSET
typedef struct SCIP_GUBSet SCIP_GUBSET |
Definition at line 315 of file cons_knapsack.c.
Enumeration Type Documentation
◆ GUBVarstatus
enum GUBVarstatus |
status of GUB constraint
Definition at line 272 of file cons_knapsack.c.
◆ GUBConsstatus
enum GUBConsstatus |
status of variable in GUB constraint
Definition at line 284 of file cons_knapsack.c.
Function Documentation
◆ SCIP_DECL_SORTPTRCOMP()
|
static |
comparison method for two sorting key pairs
Definition at line 323 of file cons_knapsack.c.
◆ eventdataCreate()
|
static |
creates event data
- Parameters
-
scip SCIP data structure eventdata pointer to store event data cons constraint weight weight of variable
Definition at line 342 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by addCoef(), and catchEvents().
◆ eventdataFree()
|
static |
frees event data
- Parameters
-
scip SCIP data structure eventdata pointer to event data
Definition at line 360 of file cons_knapsack.c.
References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.
Referenced by delCoefPos(), and dropEvents().
◆ sortItems()
|
static |
sorts items in knapsack with nonincreasing weights
- Parameters
-
consdata constraint data
Definition at line 374 of file cons_knapsack.c.
References FALSE, NULL, SCIPsortDownLongPtrPtrIntInt(), SCIPsortPtrPtrIntInt(), TRUE, and w.
Referenced by addCliques(), addNegatedCliques(), normalizeWeights(), prepareCons(), preprocessConstraintPairs(), propagateCons(), SCIP_DECL_HASHKEYVAL(), tightenWeights(), and tightenWeightsLift().
◆ calcCliquepartition()
|
static |
calculates a partition of the variables into cliques
- Parameters
-
scip SCIP data structure conshdlrdata knapsack constraint handler data consdata constraint data normalclique Should normal cliquepartition be created? negatedclique Should negated cliquepartition be created?
Definition at line 474 of file cons_knapsack.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcCliquePartition(), SCIPcalcNegatedCliquePartition(), SCIPgetNCliques(), and TRUE.
Referenced by addCliques(), addNegatedCliques(), detectRedundantVars(), propagateCons(), tightenWeights(), and tightenWeightsLift().
◆ lockRounding()
|
static |
installs rounding locks for the given variable in the given knapsack constraint
- Parameters
-
scip SCIP data structure cons knapsack constraint var variable of constraint entry
Definition at line 516 of file cons_knapsack.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPlockVarCons(), and TRUE.
Referenced by addCoef().
◆ unlockRounding()
|
static |
removes rounding locks for the given variable in the given knapsack constraint
- Parameters
-
scip SCIP data structure cons knapsack constraint var variable of constraint entry
Definition at line 529 of file cons_knapsack.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPunlockVarCons(), and TRUE.
Referenced by delCoefPos().
◆ catchEvents()
|
static |
catches bound change events for variables in knapsack
- Parameters
-
scip SCIP data structure cons constraint consdata constraint data eventhdlr event handler to call for the event processing
Definition at line 542 of file cons_knapsack.c.
References eventdataCreate(), EVENTTYPE_KNAPSACK, NULL, SCIP_CALL, SCIP_OKAY, and SCIPcatchVarEvent().
Referenced by SCIP_DECL_CONSTRANS(), and SCIPcreateConsKnapsack().
◆ dropEvents()
|
static |
drops bound change events for variables in knapsack
- Parameters
-
scip SCIP data structure consdata constraint data eventhdlr event handler to call for the event processing
Definition at line 569 of file cons_knapsack.c.
References eventdataFree(), EVENTTYPE_KNAPSACK, NULL, SCIP_CALL, SCIP_OKAY, and SCIPdropVarEvent().
Referenced by consdataFree().
◆ consdataEnsureVarsSize()
|
static |
ensures, that vars and vals arrays can store at least num entries
- Parameters
-
scip SCIP data structure consdata knapsack constraint data num minimum number of entries to store transformed is constraint from transformed problem?
Definition at line 594 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addCoef().
◆ updateWeightSums()
|
static |
updates all weight sums for fixed and unfixed variables
- Parameters
-
consdata knapsack constraint data var variable for this weight weightdelta difference between the old and the new weight of the variable
Definition at line 632 of file cons_knapsack.c.
References NULL, and SCIPvarGetLbLocal().
Referenced by addCoef(), consdataChgWeight(), consdataCreate(), and delCoefPos().
◆ consdataCreate()
|
static |
creates knapsack constraint data
- Parameters
-
scip SCIP data structure consdata pointer to store constraint data nvars number of variables in knapsack vars variables of knapsack weights weights of knapsack items capacity capacity of knapsack
Definition at line 652 of file cons_knapsack.c.
References 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 SCIP_DECL_CONSTRANS(), and SCIPcreateConsKnapsack().
◆ consdataFree()
|
static |
frees knapsack constraint data
- Parameters
-
scip SCIP data structure consdata pointer to the constraint data eventhdlr event handler to call for the event processing
Definition at line 778 of file cons_knapsack.c.
References dropEvents(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPreleaseNlRow(), SCIPreleaseRow(), and SCIPreleaseVar().
Referenced by SCIP_DECL_CONSDELETE().
◆ consdataChgWeight()
|
static |
changes a single weight in knapsack constraint data
- Parameters
-
consdata knapsack constraint data item item number newweight new weight of item
Definition at line 832 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Longint, and updateWeightSums().
Referenced by deleteRedundantVars(), dualWeightsTightening(), mergeMultiples(), normalizeWeights(), simplifyInequalities(), and tightenWeights().
◆ createRelaxation()
|
static |
creates LP row corresponding to knapsack constraint
- Parameters
-
scip SCIP data structure cons knapsack constraint
Definition at line 870 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), and SCIPinfinity().
Referenced by addRelaxation().
◆ addRelaxation()
|
static |
adds linear relaxation of knapsack constraint to the LP
- Parameters
-
scip SCIP data structure cons knapsack constraint cutoff whether a cutoff has been detected
Definition at line 898 of file cons_knapsack.c.
References createRelaxation(), FALSE, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPprintRow(), and SCIProwIsInLP().
Referenced by enforceConstraint(), SCIP_DECL_CONSINITLP(), and separateCons().
◆ addNlrow()
|
static |
adds knapsack constraint as row to the NLP, if not added yet
- Parameters
-
scip SCIP data structure cons knapsack constraint
Definition at line 932 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIP_Real, SCIPaddNlRow(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsLocal(), SCIPcreateNlRow(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisNLPConstructed(), and SCIPnlrowIsInNLP().
Referenced by SCIP_DECL_CONSACTIVE(), and SCIP_DECL_CONSINITSOL().
◆ checkCons()
|
static |
checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible
- Parameters
-
scip SCIP data structure cons constraint to check sol solution to check, NULL for current solution checklprows Do constraints represented by rows in the current LP have to be checked? printreason Should the reason for the violation be printed? violated pointer to store whether the constraint is violated
Definition at line 976 of file cons_knapsack.c.
References FALSE, NULL, SCIP_CALL, 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_CONSENFOPS(), and separateCons().
◆ GUBconsCreate()
|
static |
creates an empty GUB constraint
- Parameters
-
scip SCIP data structure gubcons pointer to store GUB constraint data
Definition at line 1728 of file cons_knapsack.c.
References GUBCONSGROWVALUE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by getLiftingSequenceGUB(), and GUBsetCreate().
◆ GUBconsFree()
|
static |
frees GUB constraint
- Parameters
-
scip SCIP data structure gubcons pointer to GUB constraint data structure
Definition at line 1749 of file cons_knapsack.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by GUBsetFree(), and GUBsetMoveVar().
◆ GUBconsAddVar()
|
static |
adds variable to given GUB constraint
- Parameters
-
scip SCIP data structure gubcons GUB constraint data var index of given variable in knapsack constraint
Definition at line 1767 of file cons_knapsack.c.
References GUBCONSGROWVALUE, SCIP_GUBCons::gubvars, SCIP_GUBCons::gubvarssize, SCIP_GUBCons::gubvarsstatus, GUBVARSTATUS_UNINITIAL, SCIP_GUBCons::ngubvars, NULL, SCIP_CALL, SCIP_OKAY, and SCIPreallocBufferArray.
Referenced by GUBsetCreate(), and GUBsetMoveVar().
◆ GUBconsDelVar()
|
static |
deletes variable from its current GUB constraint
- Parameters
-
scip SCIP data structure gubcons GUB constraint data var index of given variable in knapsack constraint gubvarsidx index of the variable in its current GUB constraint
Definition at line 1802 of file cons_knapsack.c.
References GUBCONSGROWVALUE, SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBCons::gubvarssize, SCIP_GUBCons::gubvarsstatus, SCIP_GUBCons::ngubvars, NULL, SCIP_CALL, SCIP_OKAY, and SCIPreallocBufferArray.
Referenced by GUBsetMoveVar().
◆ GUBsetMoveVar()
|
static |
moves variable from current GUB constraint to a different existing (nonempty) GUB constraint
- Parameters
-
scip SCIP data structure gubset GUB set data structure vars variables in knapsack constraint var index of given variable in knapsack constraint oldgubcons index of old GUB constraint of given variable newgubcons index of new GUB constraint of given variable
Definition at line 1839 of file cons_knapsack.c.
References GUBconsAddVar(), GUBconsDelVar(), GUBconsFree(), SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, SCIP_GUBSet::gubconsstatus, SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPvarGetName().
Referenced by getLiftingSequenceGUB(), and GUBsetGetCliquePartition().
◆ GUBsetSwapVars()
|
static |
swaps two variables in the same GUB constraint
- Parameters
-
scip SCIP data structure gubset GUB set data structure var1 first variable to be swapped var2 second variable to be swapped
Definition at line 1930 of file cons_knapsack.c.
References SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBCons::gubvarsstatus, and NULL.
Referenced by getLiftingSequenceGUB().
◆ GUBsetCreate()
|
static |
initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable)
- Parameters
-
scip SCIP data structure gubset pointer to store GUB set data structure nvars number of variables in the knapsack constraint weights weights of variables in knapsack constraint capacity capacity of knapsack
Definition at line 1970 of file cons_knapsack.c.
References GUBconsAddVar(), GUBconsCreate(), GUBCONSSTATUS_UNINITIAL, GUBVARSTATUS_CAPACITYEXCEEDED, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by SCIPseparateKnapsackCuts().
◆ GUBsetFree()
|
static |
frees GUB set data structure
- Parameters
-
scip SCIP data structure gubset pointer to GUB set data structure
Definition at line 2019 of file cons_knapsack.c.
References GUBconsFree(), NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by SCIPseparateKnapsackCuts().
◆ GUBsetCheck()
|
static |
checks whether GUB set data structure is consistent
- Parameters
-
scip SCIP data structure gubset GUB set data structure vars variables in the knapsack constraint
Definition at line 2051 of file cons_knapsack.c.
References FALSE, SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBSet::ngubconss, SCIP_GUBCons::ngubvars, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPvarGetName(), SCIPvarGetProbvarBinary(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by GUBsetGetCliquePartition().
◆ GUBsetCalcCliquePartition()
|
static |
calculates a partition of the given set of binary variables into cliques; afterwards the output array contains one value for each variable, such that two variables got the same value iff they were assigned to the same clique; the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of the preceding variables was assigned to clique i-1; note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one variable) and for the remaining variables, a partition with a small number of cliques is constructed
- Parameters
-
scip SCIP data structure vars binary variables in the clique from which at most one can be set to 1 nvars number of variables in the clique cliquepartition array of length nvars to store the clique partition ncliques pointer to store number of cliques actually contained in the partition solvals solution values of all given binary variables
Definition at line 2136 of file cons_knapsack.c.
References MAXNCLIQUEVARSCOMP, MIN, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPsortIntInt(), SCIPvarGetNCliques(), SCIPvarIsActive(), SCIPvarsGetProbvarBinary(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by GUBsetGetCliquePartition().
◆ GUBsetGetCliquePartition()
|
static |
constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs
- Parameters
-
scip SCIP data structure gubset GUB set data structure vars variables in the knapsack constraint solvals solution values of all knapsack variables
Definition at line 2294 of file cons_knapsack.c.
References SCIP_GUBSet::gubconss, SCIP_GUBSet::gubconssidx, GUBsetCalcCliquePartition(), GUBsetCheck(), GUBsetMoveVar(), SCIP_GUBCons::gubvars, SCIP_GUBSet::gubvarsidx, SCIP_GUBCons::ngubvars, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by SCIPseparateKnapsackCuts().
◆ getCover()
|
static |
gets a most violated cover C ( \(\sum_{j \in C} a_j > a_0\)) for a given knapsack constraint \(\sum_{j \in N} a_j x_j \leq a_0\) taking into consideration the following fixing: \(j \in C\), if \(j \in N_1 = \{j \in N : x^*_j = 1\}\) and \(j \in N \setminus C\), if \(j \in N_0 = \{j \in N : x^*_j = 0\}\), if one exists.
- Parameters
-
scip SCIP data structure vars variables in knapsack constraint nvars number of variables in knapsack constraint weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables covervars pointer to store cover variables noncovervars pointer to store noncover variables ncovervars pointer to store number of cover variables nnoncovervars pointer to store number of noncover variables coverweight pointer to store weight of cover found pointer to store whether a cover was found modtransused should modified transformed separation problem be used to find cover ntightened pointer to store number of variables with tightened upper bound fractional pointer to store whether the LP sol for knapsack vars is fractional
Definition at line 2391 of file cons_knapsack.c.
References 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 |
checks if minweightidx is set correctly
- Parameters
-
weights weights of variables in knapsack constraint capacity capacity of knapsack covervars pointer to store cover variables ncovervars pointer to store number of cover variables coverweight pointer to store weight of cover minweightidx index of variable in cover variables with minimum weight j current index in cover variables
Definition at line 2622 of file cons_knapsack.c.
References FALSE, NULL, SCIP_Longint, and TRUE.
Referenced by makeCoverMinimal().
◆ getPartitionCovervars()
|
static |
gets partition \((C_1,C_2)\) of minimal cover \(C\), i.e. \(C_1 \cup C_2 = C\) and \(C_1 \cap C_2 = \emptyset\), with \(C_1\) not empty; chooses partition as follows \(C_2 = \{ j \in C : x^*_j = 1 \}\) and \(C_1 = C \setminus C_2\)
- Parameters
-
scip SCIP data structure solvals solution values of all problem variables covervars cover variables ncovervars number of cover variables varsC1 pointer to store variables in C1 varsC2 pointer to store variables in C2 nvarsC1 pointer to store number of variables in C1 nvarsC2 pointer to store number of variables in C2
Definition at line 2665 of file cons_knapsack.c.
References NULL, SCIPisFeasGT(), SCIPisGE(), and SCIPisLT().
Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
◆ changePartitionCovervars()
|
static |
changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from C2 to C1 if |C1| = 1 and |C1| = 0, respectively.
- Parameters
-
scip SCIP data structure weights weights of variables in knapsack constraint varsC1 pointer to store variables in C1 varsC2 pointer to store variables in C2 nvarsC1 pointer to store number of variables in C1 nvarsC2 pointer to store number of variables in C2
Definition at line 2714 of file cons_knapsack.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().
Referenced by separateSequLiftedMinimalCoverInequality().
◆ changePartitionFeasiblesetvars()
|
static |
changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1
- Parameters
-
scip SCIP data structure weights weights of variables in knapsack constraint varsC1 pointer to store variables in C1 varsC2 pointer to store variables in C2 nvarsC1 pointer to store number of variables in C1 nvarsC2 pointer to store number of variables in C2
Definition at line 2754 of file cons_knapsack.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownRealInt().
Referenced by separateSequLiftedExtendedWeightInequality().
◆ getPartitionNoncovervars()
|
static |
gets partition \((F,R)\) of \(N \setminus C\) where \(C\) is a minimal cover, i.e. \(F \cup R = N \setminus C\) and \(F \cap R = \emptyset\); chooses partition as follows \(R = \{ j \in N \setminus C : x^*_j = 0 \}\) and \(F = (N \setminus C) \setminus F\)
- Parameters
-
scip SCIP data structure solvals solution values of all problem variables noncovervars noncover variables nnoncovervars number of noncover variables varsF pointer to store variables in F varsR pointer to store variables in R nvarsF pointer to store number of variables in F nvarsR pointer to store number of variables in R
Definition at line 2795 of file cons_knapsack.c.
References NULL, SCIPisFeasEQ(), and SCIPisFeasGT().
Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
◆ getLiftingSequence()
|
static |
sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential lifting procedure
- Parameters
-
scip SCIP data structure solvals solution values of all problem variables weights weights of variables in knapsack constraint varsF pointer to store variables in F varsC2 pointer to store variables in C2 varsR pointer to store variables in R nvarsF number of variables in F nvarsC2 number of variables in C2 nvarsR number of variables in R
Definition at line 2843 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownPtrInt(), and SCIPsortDownRealInt().
Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
◆ getLiftingSequenceGUB()
|
static |
categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs for the sequential GUB wise lifting procedure
- Parameters
-
scip SCIP data structure gubset GUB set data structure solvals solution values of variables in knapsack constraint weights weights of variables in knapsack constraint varsC1 variables in C1 varsC2 variables in C2 varsF variables in F varsR variables in R nvarsC1 number of variables in C1 nvarsC2 number of variables in C2 nvarsF number of variables in F nvarsR number of variables in R gubconsGC1 pointer to store GUBs in GC1(GNC1+GOC1) gubconsGC2 pointer to store GUBs in GC2 gubconsGFC1 pointer to store GUBs in GFC1(GNC1+GF) gubconsGR pointer to store GUBs in GR ngubconsGC1 pointer to store number of GUBs in GC1(GNC1+GOC1) ngubconsGC2 pointer to store number of GUBs in GC2 ngubconsGFC1 pointer to store number of GUBs in GFC1(GNC1+GF) ngubconsGR pointer to store number of GUBs in GR ngubconscapexceed pointer to store number of GUBs with only capacity exceeding variables maxgubvarssize pointer to store the maximal size of GUB constraints
Definition at line 2929 of file cons_knapsack.c.
References BMSclearMemoryArray, 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_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownPtrInt(), SCIPsortDownRealInt(), SCIPsortRealInt(), and TRUE.
Referenced by separateSequLiftedMinimalCoverInequality().
◆ enlargeMinweights()
|
static |
enlarges minweight table to at least the given length
- Parameters
-
scip SCIP data structure minweightsptr pointer to minweights table minweightslen pointer to store number of entries in minweights table (incl. z=0) minweightssize pointer to current size of minweights table newlen new length of minweights table
Definition at line 3432 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.
Referenced by sequentialUpAndDownLifting(), and sequentialUpAndDownLiftingGUB().
◆ sequentialUpAndDownLifting()
|
static |
lifts given inequality sum_{j in M_1} x_j <= alpha_0 valid for S^0 = { x in {0,1}^|M_1| : sum_{j in M_1} a_j x_j <= a_0 - sum_{j in M_2} a_j } to a valid inequality sum_{j in M_1} x_j + sum_{j in F} alpha_j x_j + sum_{j in M_2} alpha_j x_j + sum_{j in R} alpha_j x_j <= alpha_0 + sum_{j in M_2} alpha_j for S = { x in {0,1}^|N| : sum_{j in N} a_j x_j <= a_0 }; uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and extended weight inequalities.
- Parameters
-
scip SCIP data structure vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables varsM1 variables in M_1 varsM2 variables in M_2 varsF variables in F varsR variables in R nvarsM1 number of variables in M_1 nvarsM2 number of variables in M_2 nvarsF number of variables in F nvarsR number of variables in R alpha0 rights hand side of given valid inequality liftcoefs pointer to store lifting coefficient of vars in knapsack constraint cutact pointer to store activity of lifted valid inequality liftrhs pointer to store right hand side of the lifted valid inequality
Definition at line 3482 of file cons_knapsack.c.
References BMSclearMemoryArray, enlargeMinweights(), MIN, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), SCIPisFeasGT(), SCIPsortRealInt(), and w.
Referenced by separateSequLiftedExtendedWeightInequality(), and separateSequLiftedMinimalCoverInequality().
◆ safeAddMinweightsGUB()
|
static |
adds two minweight values in a safe way, i.e,, ensures no overflow
- Parameters
-
val1 first value to add val2 second value to add
Definition at line 3860 of file cons_knapsack.c.
References SCIP_LONGINT_MAX.
Referenced by computeMinweightsGUB(), and sequentialUpAndDownLiftingGUB().
◆ computeMinweightsGUB()
|
static |
computes minweights table for lifting with GUBs by combining unfished and fished tables
- Parameters
-
minweights minweight table to compute finished given finished table unfinished given unfinished table minweightslen length of minweight, finished, and unfinished tables
Definition at line 3879 of file cons_knapsack.c.
References safeAddMinweightsGUB(), SCIP_Longint, and SCIP_LONGINT_MAX.
Referenced by sequentialUpAndDownLiftingGUB().
◆ 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.
- Parameters
-
scip SCIP data structure gubset GUB set data structure vars variables in knapsack constraint ngubconscapexceed number of GUBs with only capacity exceeding variables weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all knapsack variables gubconsGC1 GUBs in GC1(GNC1+GOC1) gubconsGC2 GUBs in GC2 gubconsGFC1 GUBs in GFC1(GNC1+GF) gubconsGR GUBs in GR ngubconsGC1 number of GUBs in GC1(GNC1+GOC1) ngubconsGC2 number of GUBs in GC2 ngubconsGFC1 number of GUBs in GFC1(GNC1+GF) ngubconsGR number of GUBs in GR alpha0 rights hand side of given valid inequality liftcoefs pointer to store lifting coefficient of vars in knapsack constraint cutact pointer to store activity of lifted valid inequality liftrhs pointer to store right hand side of the lifted valid inequality maxgubvarssize maximal size of GUB constraints
Definition at line 3931 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, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasEQ(), and w.
Referenced by separateSequLiftedMinimalCoverInequality().
◆ superadditiveUpLifting()
|
static |
lifts given minimal cover inequality
\[ \sum_{j \in C} x_j \leq |C| - 1 \]
valid for
\[ S^0 = \{ x \in {0,1}^{|C|} : \sum_{j \in C} a_j x_j \leq a_0 \} \]
to a valid inequality
\[ \sum_{j \in C} x_j + \sum_{j \in N \setminus C} \alpha_j x_j \leq |C| - 1 \]
for
\[ S = \{ x \in {0,1}^{|N|} : \sum_{j \in N} a_j x_j \leq a_0 \}; \]
uses superadditive up-lifting for the variables in \(N \setminus C\).
- Parameters
-
scip SCIP data structure vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables covervars cover variables noncovervars noncover variables ncovervars number of cover variables nnoncovervars number of noncover variables coverweight weight of cover liftcoefs pointer to store lifting coefficient of vars in knapsack constraint cutact pointer to store activity of lifted valid inequality
Definition at line 4666 of file cons_knapsack.c.
References BMSclearMemoryArray, h, MAX, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), and SCIPsortRealInt().
Referenced by separateSupLiftedMinimalCoverInequality().
◆ separateSequLiftedMinimalCoverInequality()
|
static |
separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for given knapsack problem
- Parameters
-
scip SCIP data structure cons originating constraint of the knapsack problem, or NULL sepa originating separator of the knapsack problem, or NULL vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables mincovervars mincover variables nonmincovervars nonmincover variables nmincovervars number of mincover variables nnonmincovervars number of nonmincover variables sol primal SCIP solution to separate, NULL for current LP solution gubset GUB set data structure, NULL if no GUB information should be used cutoff pointer to store whether a cutoff has been detected ncuts pointer to add up the number of found cuts
Definition at line 4797 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_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(), sequentialUpAndDownLifting(), sequentialUpAndDownLiftingGUB(), and TRUE.
Referenced by SCIPseparateKnapsackCuts().
◆ separateSequLiftedExtendedWeightInequality()
|
static |
separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem
- Parameters
-
scip SCIP data structure cons constraint that originates the knapsack problem, or NULL sepa originating separator of the knapsack problem, or NULL vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables feassetvars variables in feasible set nonfeassetvars variables not in feasible set nfeassetvars number of variables in feasible set nnonfeassetvars number of variables not in feasible set sol primal SCIP solution to separate, NULL for current LP solution cutoff whether a cutoff has been detected ncuts pointer to add up the number of found cuts
Definition at line 5031 of file cons_knapsack.c.
References changePartitionFeasiblesetvars(), FALSE, getLiftingSequence(), getPartitionCovervars(), getPartitionNoncovervars(), MAX, NULL, SCIP_GUBSet::nvars, SCIP_CALL, 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(), sequentialUpAndDownLifting(), and TRUE.
Referenced by getFeasibleSet().
◆ separateSupLiftedMinimalCoverInequality()
|
static |
separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem
- Parameters
-
scip SCIP data structure cons constraint that originates the knapsack problem, or NULL sepa originating separator of the knapsack problem, or NULL vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables mincovervars mincover variables nonmincovervars nonmincover variables nmincovervars number of mincover variables nnonmincovervars number of nonmincover variables mincoverweight weight of minimal cover sol primal SCIP solution to separate, NULL for current LP solution cutoff whether a cutoff has been detected ncuts pointer to add up the number of found cuts
Definition at line 5198 of file cons_knapsack.c.
References FALSE, MAX, NULL, SCIP_GUBSet::nvars, SCIP_CALL, 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().
◆ makeCoverMinimal()
|
static |
converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen to be in C, i.e. in the order of non-increasing (1 - x*_j)/a_j, if the transformed separation problem was used to find C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C; note that all variables with x*_j = 1 will be removed last
- Parameters
-
scip SCIP data structure weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables covervars pointer to store cover variables noncovervars pointer to store noncover variables ncovervars pointer to store number of cover variables nnoncovervars pointer to store number of noncover variables coverweight pointer to store weight of cover modtransused TRUE if mod trans sepa prob was used to find cover
Definition at line 5312 of file cons_knapsack.c.
References checkMinweightidx(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPsortPtrInt().
Referenced by SCIPseparateKnapsackCuts().
◆ getFeasibleSet()
|
static |
converts given initial cover C_init to a feasible set by removing variables in the reverse order in which they were chosen to be in C_init: non-increasing (1 - x*_j)/a_j, if transformed separation problem was used to find C_init non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init. separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set and all subsequent feasible sets.
- Parameters
-
scip SCIP data structure cons constraint that originates the knapsack problem sepa originating separator of the knapsack problem, or NULL vars variables in knapsack constraint nvars number of variables in knapsack constraint ntightened number of variables with tightened upper bound weights weights of variables in knapsack constraint capacity capacity of knapsack solvals solution values of all problem variables covervars pointer to store cover variables noncovervars pointer to store noncover variables ncovervars pointer to store number of cover variables nnoncovervars pointer to store number of noncover variables coverweight pointer to store weight of cover modtransused TRUE if mod trans sepa prob was used to find cover sol primal SCIP solution to separate, NULL for current LP solution cutoff whether a cutoff has been detected ncuts pointer to add up the number of found cuts
Definition at line 5461 of file cons_knapsack.c.
References FALSE, MAXCOVERSIZEITERLEWI, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLE(), SCIPsortRealInt(), and separateSequLiftedExtendedWeightInequality().
Referenced by SCIPseparateKnapsackCuts().
◆ separateCons()
|
static |
separates given knapsack constraint
- Parameters
-
scip SCIP data structure cons knapsack constraint sol primal SCIP solution, NULL for current LP solution sepacuts should knapsack cuts be separated? usegubs should GUB information be used for separation? cutoff whether a cutoff has been detected ncuts pointer to add up the number of found cuts
Definition at line 6216 of file cons_knapsack.c.
References addRelaxation(), checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, and SCIPseparateKnapsackCuts().
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
◆ addCoef()
|
static |
adds coefficient to constraint data
- Parameters
-
scip SCIP data structure cons knapsack constraint var variable to add to knapsack weight weight of variable in knapsack
Definition at line 6258 of file cons_knapsack.c.
References consdataEnsureVarsSize(), eventdataCreate(), EVENTTYPE_KNAPSACK, FALSE, lockRounding(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddVarToRow(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPgetBinvarRepresentative(), SCIPmarkConsPropagate(), SCIPvarGetLbGlobal(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), TRUE, and updateWeightSums().
Referenced by applyFixings(), SCIPaddCoefKnapsack(), and tightenWeightsLift().
◆ delCoefPos()
|
static |
deletes coefficient at given position from constraint data
- Parameters
-
scip SCIP data structure cons knapsack constraint pos position of coefficient to delete
Definition at line 6338 of file cons_knapsack.c.
References eventdataFree(), EVENTTYPE_KNAPSACK, FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdropVarEvent(), SCIPmarkConsPropagate(), SCIPreleaseVar(), SCIPvarIsTransformed(), unlockRounding(), and updateWeightSums().
Referenced by applyFixings(), deleteRedundantVars(), dualWeightsTightening(), mergeMultiples(), performVarDeletions(), prepareCons(), removeZeroWeights(), and simplifyInequalities().
◆ removeZeroWeights()
|
static |
removes all items with weight zero from knapsack constraint
- Parameters
-
scip SCIP data structure cons knapsack constraint
Definition at line 6528 of file cons_knapsack.c.
References delCoefPos(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().
Referenced by tightenWeights().
◆ performVarDeletions()
|
static |
- Parameters
-
scip SCIP data structure conshdlr constraint handler conss array of constraints nconss number of constraints
Definition at line 6552 of file cons_knapsack.c.
References CONSHDLR_NAME, delCoefPos(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), and SCIPvarIsDeleted().
Referenced by SCIP_DECL_CONSDELVARS().
◆ mergeMultiples()
|
static |
replaces multiple occurrences of a variable or its negation by a single coefficient
- Parameters
-
scip SCIP data structure cons knapsack constraint cutoff pointer to store whether the node can be cut off
Definition at line 6594 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_NEGATED, SCIPconsGetData(), SCIPdebugMsg, SCIPsortPtrPtrLongIntInt(), SCIPvarGetNegatedVar(), SCIPvarGetStatus(), SCIPvarIsActive(), SCIPvarIsBinary(), and TRUE.
Referenced by addCliques(), addNegatedCliques(), applyFixings(), SCIP_DECL_CONSPRESOL(), simplifyInequalities(), tightenWeights(), and tightenWeightsLift().
◆ dualPresolving()
|
static |
in case the knapsack constraint is independent of every else, solve the knapsack problem (exactly) and apply the fixings (dual reductions)
- Parameters
-
scip SCIP data structure cons knapsack constraint nfixedvars pointer to count number of fixings ndelconss pointer to count number of deleted constraints deleted pointer to store if the constraint is deleted
Definition at line 6737 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPfreeBufferArray, SCIPsolveKnapsackExactly(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetProbvarBinary(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
◆ checkParallelObjective()
|
static |
check if the knapsack constraint is parallel to objective function; if so update the cutoff bound and avoid that the constraint enters the LP by setting the initial and separated flag to FALSE
- Parameters
-
scip SCIP data structure cons knapsack constraint conshdlrdata knapsack constraint handler data
Definition at line 6879 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsInitial(), SCIPconsIsSeparated(), SCIPcutoffbounddelta(), SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetNObjVars(), SCIPisEQ(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPsetConsEnforced(), SCIPsetConsInitial(), SCIPsetConsPropagated(), SCIPsetConsSeparated(), SCIPupdateCutoffbound(), SCIPupdateLocalLowerbound(), SCIPvarGetNegatedVar(), SCIPvarGetObj(), SCIPvarIsNegated(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
◆ stableSort()
|
static |
sort the variables and weights w.r.t. the clique partition; thereby ensure the current order of the variables when a weight of one variable is greater or equal another weight and both variables are in the same cliques
- Parameters
-
scip SCIP data structure consdata knapsack constraint data vars array for sorted variables weights array for sorted weights cliquestartposs starting position array for each clique usenegatedclique should negated or normal clique partition be used
Definition at line 7035 of file cons_knapsack.c.
References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by propagateCons().
◆ applyFixings()
|
static |
deletes all fixed variables from knapsack constraint, and replaces variables with binary representatives
- Parameters
-
scip SCIP data structure cons knapsack constraint cutoff pointer to store whether the node can be cut off, or NULL if this information is not needed; in this case, we apply all fixings instead of stopping after the first infeasible one
Definition at line 7159 of file cons_knapsack.c.
References addCoef(), delCoefPos(), FALSE, mergeMultiples(), NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPconsGetData(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPerrorMessage, SCIPflattenVarAggregationGraph(), SCIPfloor(), SCIPgetBinvarRepresentative(), SCIPgetNegatedVar(), SCIPisFeasEQ(), SCIPisIntegral(), SCIPisNegative(), SCIPvarGetLbGlobal(), SCIPvarGetMultaggrConstant(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPvarIsNegated(), and TRUE.
Referenced by SCIP_DECL_CONSEXITPRE(), SCIP_DECL_CONSPRESOL(), and SCIPcleanupConssKnapsack().
◆ propagateCons()
|
static |
propagation method for knapsack constraints
- Parameters
-
scip SCIP data structure cons knapsack constraint cutoff pointer to store whether the node can be cut off redundant pointer to store whether constraint is redundant nfixedvars pointer to count number of fixings usenegatedclique should negated clique information be used
Definition at line 7371 of file cons_knapsack.c.
References BMSclearMemoryArray, calcCliquepartition(), FALSE, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ 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
- Parameters
-
scip SCIP data structure cons knapsack constraint ndelconss pointer to store the amount of deleted constraints naddconss pointer to count number of added constraints
Definition at line 7835 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsLogicor(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdelCons(), SCIPfreeBufferArray, SCIPgetNegatedVars(), and SCIPreleaseCons().
Referenced by detectRedundantVars(), and dualWeightsTightening().
◆ deleteRedundantVars()
|
static |
delete redundant variables
i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them
i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique => x4, x5 always fits into the knapsack, so we can delete them
i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too => we create the set partitioning constraint x4 + x5 <= 1 and delete them in this knapsack
- Parameters
-
scip SCIP data structure cons knapsack constraint frontsum sum of front items which fit if we try to take from the first till the last splitpos split position till when all front items are fitting, splitpos is the first which did not fit nchgcoefs pointer to store the amount of changed coefficients nchgsides pointer to store the amount of changed sides naddconss pointer to count number of added constraints
Definition at line 7907 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), 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 |
- Parameters
-
scip SCIP data structure cons knapsack constraint ndelconss pointer to store the amount of deleted constraints nchgcoefs pointer to store the amount of changed coefficients nchgsides pointer to store the amount of changed sides naddconss pointer to count number of added constraints
Definition at line 8158 of file cons_knapsack.c.
References calcCliquepartition(), deleteRedundantVars(), FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpack(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), TRUE, upgradeCons(), and w.
Referenced by simplifyInequalities().
◆ normalizeWeights()
|
static |
divides weights by their greatest common divisor and divides capacity by the same value, rounding down the result
- Parameters
-
cons knapsack constraint nchgcoefs pointer to count total number of changed coefficients nchgsides pointer to count number of side changes
Definition at line 8346 of file cons_knapsack.c.
References consdataChgWeight(), NULL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIPcalcGreComDiv(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMessage, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sortItems(), and TRUE.
Referenced by dualWeightsTightening(), and SCIP_DECL_CONSPRESOL().
◆ dualWeightsTightening()
|
static |
dual weights tightening for knapsack constraints
- a) check if all two pairs exceed the capacity, then we can upgrade this constraint to a set-packing constraint b) check if all but the smallest weight fit into the knapsack, then we can upgrade this constraint to a logicor constraint
check if besides big coefficients, that fit only by itself, for a certain amount of variables all combination of these are a minimal cover, then might reduce the weights and the capacity, e.g.
+219y1 + 180y2 + 74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3
use the duality between a^Tx <= capacity <=> a^T~x >= weightsum - capacity to tighten weights, e.g.
11x1 + 10x2 + 7x3 + 7x4 + 5x5 <= 27 <=> 11~x1 + 10~x2 + 7~x3 + 7~x4 + 5~x5 >= 13
the above constraint can be changed to 8~x1 + 8~x2 + 6.5~x3 + 6.5~x4 + 5~x5 >= 13
16~x1 + 16~x2 + 13~x3 + 13~x4 + 10~x5 >= 26 <=> 16x1 + 16x2 + 13x3 + 13x4 + 10x5 <= 42
- Parameters
-
scip SCIP data structure cons knapsack constraint ndelconss pointer to store the amount of deleted constraints nchgcoefs pointer to store the amount of changed coefficients nchgsides pointer to store the amount of changed sides naddconss pointer to count number of added constraints
Definition at line 8420 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), FALSE, MIN, normalizeWeights(), NULL, SCIP_GUBSet::nvars, 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 |
fixes variables with weights bigger than the capacity and delete redundant constraints, also sort weights
- Parameters
-
scip SCIP data structure cons knapsack constraint nfixedvars pointer to store the amount of fixed variables ndelconss pointer to store the amount of deleted constraints nchgcoefs pointer to store the amount of changed coefficients
Definition at line 9280 of file cons_knapsack.c.
References delCoefPos(), NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPdelCons(), SCIPfixVar(), SCIPisHugeValue(), and sortItems().
Referenced by simplifyInequalities().
◆ 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
- Parameters
-
scip SCIP data structure cons knapsack constraint nfixedvars pointer to store the amount of fixed variables ndelconss pointer to store the amount of deleted constraints nchgcoefs pointer to store the amount of changed coefficients nchgsides pointer to store the amount of changed sides naddconss pointer to count number of added constraints cutoff pointer to store whether the node can be cut off
Definition at line 9397 of file cons_knapsack.c.
References consdataChgWeight(), delCoefPos(), detectRedundantVars(), dualWeightsTightening(), FALSE, 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().
Referenced by SCIP_DECL_CONSPRESOL().
◆ insertZerolist()
|
static |
inserts an element into the list of binary zero implications
- Parameters
-
scip SCIP data structure liftcands array of the lifting candidates nliftcands number of lifting candidates firstidxs array of first zeroitems indices zeroweightsums array of sums of weights of the implied-to-zero items zeroitems pointer to zero items array nextidxs pointer to array of next zeroitems indeces zeroitemssize pointer to size of zero items array nzeroitems pointer to length of zero items array probindex problem index of variable y in implication y == v -> x == 0 value value v of variable y in implication knapsackidx index of variable x in knapsack knapsackweight weight of variable x in knapsack memlimitreached pointer to store whether the memory limit was reached
Definition at line 9709 of file cons_knapsack.c.
References FALSE, MAX_ZEROITEMS_SIZE, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNContVars(), SCIPgetNVars(), SCIPreallocBufferArray, and TRUE.
Referenced by tightenWeightsLift().
◆ tightenWeightsLift()
|
static |
applies rule (3) of the weight tightening procedure, which can lift other variables into the knapsack: (3) for a clique C let C(xi == v) := C \ {j: xi == v -> xj == 0}), let cliqueweightsum(xi == v) := sum(W(C(xi == v))) if cliqueweightsum(xi == v) < capacity:
- fixing variable xi to v would make the knapsack constraint redundant
- the weight of the variable or its negation (depending on v) can be increased as long as it has the same redundancy effect: wi' := capacity - cliqueweightsum(xi == v) this rule can also be applied to binary variables not in the knapsack!
- Parameters
-
scip SCIP data structure cons knapsack constraint nchgcoefs pointer to count total number of changed coefficients cutoff pointer to store whether the node can be cut off
Definition at line 9795 of file cons_knapsack.c.
References addCoef(), BMSclearMemoryArray, calcCliquepartition(), FALSE, insertZerolist(), MAX_CLIQUELENGTH, MAX_USECLIQUES_SIZE, MAX_ZEROITEMS_SIZE, mergeMultiples(), MIN, NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNegatedVar(), SCIPgetNVars(), SCIPgetVars(), SCIPreallocBlockMemoryArray, SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetProbvarBinary(), sortItems(), and TRUE.
Referenced by tightenWeights().
◆ 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:
- not using item i would make the knapsack constraint redundant
- wi and capacity can be changed to have the same redundancy effect and the same results for fixing xi to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
- change coefficients: wi' := weightsum - capacity capacity' := capacity - (wi - wi') (2) increase weights from front to back(sortation is necessary) if there is no space left for another weight
- determine the four(can be adjusted) minimal weightsums of the knapsack, i.e. in increasing order weights[nvars - 1], weights[nvars - 2], MIN(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), MIN(MAX(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), weights[nvars - 4]), note that there can be multiple times the same weight, this can be improved
- check if summing up a minimal weightsum with a big weight exceeds the capacity, then we can increase the big weight, to capacity - lastmininmalweightsum, e.g. : 19x1 + 15x2 + 10x3 + 5x4 + 5x5 <= 19 -> minimal weightsums: 5, 5, 10, 10 -> 15 + 5 > 19 => increase 15 to 19 - 0 = 19 -> 10 + 10 > 19 => increase 10 to 19 - 5 = 14, resulting in 19x1 + 19x2 + 14x3 + 5x4 + 5x5 <= 19 (3) let W(C) be the maximal weight of clique C, cliqueweightsum := sum(W(C)) if cliqueweightsum - W(C) < capacity:
- not using any item of C would make the knapsack constraint redundant
- weights wi, i in C, and capacity can be changed to have the same redundancy effect and the same results for fixing xi, i in C, to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
- change coefficients: delta := capacity - (cliqueweightsum - W(C)) wi' := max(wi - delta, 0) capacity' := capacity - delta This rule has to add the used cliques in order to ensure they are enforced - otherwise, the reduction might introduce infeasible solutions. (4) for a clique C let C(xi == v) := C \ {j: xi == v -> xj == 0}), let cliqueweightsum(xi == v) := sum(W(C(xi == v))) if cliqueweightsum(xi == v) < capacity:
- fixing variable xi to v would make the knapsack constraint redundant
- the weight of the variable or its negation (depending on v) can be increased as long as it has the same redundancy effect: wi' := capacity - cliqueweightsum(xi == v) This rule can also be applied to binary variables not in the knapsack! (5) if min{w} + wi > capacity:
- using item i would force to fix other items to zero
- wi can be increased to the capacity
- Parameters
-
scip SCIP data structure cons knapsack constraint presoltiming current presolving timing nchgcoefs pointer to count total number of changed coefficients nchgsides pointer to count number of side changes naddconss pointer to count number of added constraints ndelconss pointer to count number of deleted constraints cutoff pointer to store whether the node can be cut off
Definition at line 10359 of file cons_knapsack.c.
References 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(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), sortItems(), tightenWeightsLift(), TRUE, and w.
Referenced by SCIP_DECL_CONSPRESOL().
◆ addNegatedCliques()
|
static |
adds negated cliques of the knapsack constraint to the global clique table
- Parameters
-
scip SCIP data structure cons knapsack constraint cutoff pointer to store whether the node can be cut off nbdchgs pointer to count the number of performed bound changes
Definition at line 10948 of file cons_knapsack.c.
References BMSclearMemoryArray, calcCliquepartition(), FALSE, mergeMultiples(), NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPaddClique(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebug, SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPsortDownLongPtrInt(), sortItems(), TRUE, and w.
Referenced by addCliques().
◆ greedyCliqueAlgorithm()
|
static |
greedy clique detection by considering weights and capacity
greedily detects cliques by first sorting the items by decreasing weights (optional) and then collecting greedily 1) neighboring items which exceed the capacity together => one clique 2) looping through the remaining items and finding the largest set of preceding items to build a clique => possibly many more cliques
- Parameters
-
scip SCIP data structure items array of variable items weights weights of the items nitems the number of items capacity maximum free capacity of the knapsack sorteditems are the items sorted by their weights nonincreasing? cliqueextractfactor lower clique size limit for greedy clique extraction algorithm (relative to largest clique) cutoff pointer to store whether the node can be cut off nbdchgs pointer to count the number of performed bound changes
Definition at line 11150 of file cons_knapsack.c.
References FALSE, MAX, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPaddClique(), SCIPdebug, SCIPduplicateBufferArray, SCIPfreeBufferArray, and SCIPsortDownLongPtr().
Referenced by addCliques().
◆ addCliques()
|
static |
adds cliques of the knapsack constraint to the global clique table
- Parameters
-
scip SCIP data structure cons knapsack constraint cliqueextractfactor lower clique size limit for greedy clique extraction algorithm (relative to largest clique) cutoff pointer to store whether the node can be cut off nbdchgs pointer to count the number of performed bound changes
Definition at line 11261 of file cons_knapsack.c.
References addNegatedCliques(), BMSclearMemoryArray, calcCliquepartition(), FALSE, greedyCliqueAlgorithm(), mergeMultiples(), NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, sortItems(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
◆ SCIP_DECL_HASHGETKEY()
|
static |
gets the key of the given element
Definition at line 11407 of file cons_knapsack.c.
◆ SCIP_DECL_HASHKEYEQ()
|
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 11417 of file cons_knapsack.c.
References FALSE, NULL, SCIPconsGetData(), SCIPvarCompare(), and TRUE.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 11460 of file cons_knapsack.c.
References NULL, SCIPconsGetData(), SCIPhashSix, SCIPvarGetIndex(), and sortItems().
◆ detectRedundantConstraints()
|
static |
compares each constraint with all other constraints for possible redundancy and removes or changes constraint accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
- Parameters
-
scip SCIP data structure blkmem block memory conss constraint set nconss number of constraints in constraint set cutoff pointer to store whether the problem is infeasible ndelconss pointer to count number of deleted constraints
Definition at line 11497 of file cons_knapsack.c.
References HASHSIZE_KNAPSACKCONS, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPupdateConsFlags(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
◆ preprocessConstraintPairs()
|
static |
compares constraint with all prior constraints for possible redundancy or aggregation, and removes or changes constraint accordingly
- Parameters
-
scip SCIP data structure conss constraint set firstchange first constraint that changed since last pair preprocessing round chkind index of constraint to check against all prior indices upto startind ndelconss pointer to count number of deleted constraints
Definition at line 11621 of file cons_knapsack.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPisGT(), SCIPisLT(), SCIPupdateConsFlags(), sortItems(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
◆ enforceConstraint()
|
static |
helper function to enforce constraints
- Parameters
-
scip SCIP data structure conshdlr constraint handler conss constraints to process nconss number of constraints nusefulconss number of useful (non-obsolete) constraints to process sol solution to enforce (NULL for the LP solution) result pointer to store the result of the enforcing call
Definition at line 11819 of file cons_knapsack.c.
References addRelaxation(), checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPdebugMsg, and SCIPgetDepth().
Referenced by SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFORELAX().
◆ createNormalizedKnapsack()
|
static |
creates and captures a knapsack constraint out of a linear inequality
- Parameters
-
scip SCIP data structure cons pointer to hold the created constraint name name of constraint nvars number of variables in the constraint vars array with variables of constraint entries vals array with inequality coefficients lhs left hand side of inequality rhs right hand side of inequality initial should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'. separate should the constraint be separated during LP processing? Usually set to TRUE. enforce should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints. check should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints. propagate should the constraint be propagated during node processing? Usually set to TRUE. local is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. modifiable is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint. dynamic is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints. removable should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. stickingatnode should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
Definition at line 11885 of file cons_knapsack.c.
References NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateConsKnapsack(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPisFeasIntegral(), and SCIPisInfinity().
Referenced by SCIP_DECL_LINCONSUPGD().
◆ SCIP_DECL_LINCONSUPGD()
|
static |
tries to upgrade a linear constraint into a knapsack constraint
Definition at line 11980 of file cons_knapsack.c.
References createNormalizedKnapsack(), NULL, SCIP_GUBSet::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, and SCIPisInfinity().
◆ addSymmetryInformation()
|
static |
adds symmetry information of constraint to a symmetry detection graph
- Parameters
-
scip SCIP pointer symtype type of symmetries that need to be added cons constraint graph symmetry detection graph success pointer to store whether symmetry information could be added
Definition at line 12015 of file cons_knapsack.c.
References NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPextendPermsymDetectionGraphLinear(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetNVars(), SCIPgetSymActiveVariables(), SCIPinfinity(), and SCIPisTransformed().
Referenced by SCIP_DECL_CONSGETPERMSYMGRAPH(), and SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins) ! [SnippetConsCopyKnapsack]
Definition at line 12073 of file cons_knapsack.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrKnapsack(), and TRUE.
◆ SCIP_DECL_CONSFREE()
|
static |
! [SnippetConsCopyKnapsack] destructor of constraint handler to free constraint handler data (called when SCIP is exiting) ! [SnippetConsFreeKnapsack]
Definition at line 12091 of file cons_knapsack.c.
References NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrSetData(), and SCIPfreeBlockMemory.
◆ SCIP_DECL_CONSINIT()
|
static |
! [SnippetConsFreeKnapsack] initialization method of constraint handler (called after problem was transformed)
Definition at line 12110 of file cons_knapsack.c.
References NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemoryArray, SCIPconshdlrGetData(), SCIPgetNContVars(), and SCIPgetNVars().
◆ SCIP_DECL_CONSEXIT()
|
static |
deinitialization method of constraint handler (called before transformed problem is freed)
Definition at line 12132 of file cons_knapsack.c.
References NULL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemoryArrayNull.
◆ SCIP_DECL_CONSINITPRE()
|
static |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 12151 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemoryArray, SCIPconshdlrGetData(), SCIPgetNContVars(), and SCIPgetNVars().
◆ SCIP_DECL_CONSEXITPRE()
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished)
Definition at line 12194 of file cons_knapsack.c.
References applyFixings(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconsIsDeleted(), and SCIPfreeBlockMemoryArrayNull.
◆ SCIP_DECL_CONSINITSOL()
|
static |
solving process initialization method of constraint handler
Definition at line 12237 of file cons_knapsack.c.
References addNlrow(), SCIP_CALL, SCIP_OKAY, and SCIPisNLPConstructed().
◆ SCIP_DECL_CONSEXITSOL()
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 12254 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPreleaseNlRow(), and SCIPreleaseRow().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 12283 of file cons_knapsack.c.
References consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem ! [SnippetConsTransKnapsack]
Definition at line 12304 of file cons_knapsack.c.
References catchEvents(), consdataCreate(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_TRANSFORMING, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), and SCIPgetStage().
◆ SCIP_DECL_CONSINITLP()
|
static |
! [SnippetConsTransKnapsack] LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 12345 of file cons_knapsack.c.
References addRelaxation(), FALSE, SCIP_CALL, SCIP_OKAY, and SCIPconsIsInitial().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 12362 of file cons_knapsack.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetSepaFreq(), SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLocalLowerbound(), SCIPgetLowerbound(), SCIPgetNLPBranchCands(), SCIPgetNSepaRounds(), SCIPisLE(), SCIPisStopped(), and separateCons().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 12436 of file cons_knapsack.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetSepaFreq(), SCIPdebugMsg, SCIPgetDepth(), SCIPgetNSepaRounds(), SCIPisStopped(), and separateCons().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 12496 of file cons_knapsack.c.
References enforceConstraint(), NULL, SCIP_CALL, and SCIP_OKAY.
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 12505 of file cons_knapsack.c.
References enforceConstraint(), SCIP_CALL, and SCIP_OKAY.
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 12514 of file cons_knapsack.c.
References checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and TRUE.
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 12535 of file cons_knapsack.c.
References checkCons(), SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, and SCIP_OKAY.
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 12554 of file cons_knapsack.c.
References FALSE, NULL, propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_INITSOLVE, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPgetStage(), SCIPinProbing(), and SCIPunmarkConsPropagate().
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 12604 of file cons_knapsack.c.
References addCliques(), applyFixings(), checkParallelObjective(), detectRedundantConstraints(), dualPresolving(), FALSE, mergeMultiples(), MINGAINPERNMINCOMPARISONS, NMINCOMPARISONS, normalizeWeights(), NULL, SCIP_GUBSet::nvars, preprocessConstraintPairs(), propagateCons(), SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_LOCKTYPE_MODEL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIP_Real, SCIP_SUCCESS, SCIPaddCons(), SCIPallocClearBufferArray, SCIPallowStrongDualReds(), SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsCardinality(), SCIPdebugMessage, SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPdelConsLocal(), SCIPfindOrigCons(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashmapSetImageInt(), SCIPinfoMessage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPisZero(), SCIPprintCons(), SCIPreleaseCons(), SCIPsetConsChecked(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetNImpls(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarIsActive(), SCIPvarIsBinary(), simplifyInequalities(), tightenWeights(), and TRUE.
◆ SCIP_DECL_CONSRESPROP()
|
static |
propagation conflict resolving method of constraint handler
Definition at line 13031 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictBinvar(), SCIPconsGetData(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPvarGetIndex(), and SCIPvarGetLbLocal().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler ! [SnippetConsLockKnapsack]
Definition at line 13115 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarLocksType(), and SCIPconsGetData().
◆ SCIP_DECL_CONSACTIVE()
|
static |
! [SnippetConsLockKnapsack] constraint activation notification method of constraint handler
Definition at line 13134 of file cons_knapsack.c.
References addNlrow(), SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPgetStage(), and SCIPisNLPConstructed().
◆ SCIP_DECL_CONSDEACTIVE()
|
static |
constraint deactivation notification method of constraint handler
Definition at line 13146 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPconsGetData(), SCIPdelNlRow(), and SCIPgetStage().
◆ SCIP_DECL_CONSDELVARS()
|
static |
variable deletion method of constraint handler
Definition at line 13168 of file cons_knapsack.c.
References NULL, performVarDeletions(), SCIP_CALL, and SCIP_OKAY.
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 13184 of file cons_knapsack.c.
References NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPconsGetData(), SCIPinfoMessage(), SCIPwriteVarName(), and TRUE.
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 13210 of file cons_knapsack.c.
References NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetName(), SCIPcopyConsLinear(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), SCIPgetWeightsKnapsack(), and SCIPinfinity().
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 13246 of file cons_knapsack.c.
References FALSE, NULL, SCIP_GUBSet::nvars, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateConsKnapsack(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPparseVarName(), SCIPreallocBufferArray, SCIPskipSpace(), and TRUE.
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 13354 of file cons_knapsack.c.
References BMScopyMemoryArray, FALSE, NULL, SCIP_GUBSet::nvars, SCIP_OKAY, SCIPconsGetData(), and TRUE.
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 13376 of file cons_knapsack.c.
References NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.
◆ SCIP_DECL_CONSGETPERMSYMGRAPH()
|
static |
constraint handler method which returns the permutation symmetry detection graph of a constraint
Definition at line 13391 of file cons_knapsack.c.
References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_PERM.
◆ SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH()
|
static |
constraint handler method which returns the signed permutation symmetry detection graph of a constraint
Definition at line 13400 of file cons_knapsack.c.
References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_SIGNPERM.
◆ SCIP_DECL_EVENTEXEC()
|
static |
execution method of bound change event handler
Definition at line 13413 of file cons_knapsack.c.
References FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_FORMAT, SCIP_EVENTTYPE_IMPLADDED, SCIP_EVENTTYPE_LBRELAXED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_EVENTTYPE_VARDELETED, SCIP_EVENTTYPE_VARFIXED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPconsGetData(), SCIPerrorMessage, SCIPeventGetType(), SCIPeventGetVar(), SCIPmarkConsPropagate(), SCIPvarGetNegatedVar(), SCIPvarGetStatus(), and TRUE.