cons_knapsack.c
Go to the documentation of this file.
27 * @brief Constraint handler for knapsack constraints of the form \f$a^T x \le b\f$, x binary and \f$a \ge 0\f$.
35/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
84#define CONSHDLR_ENFOPRIORITY -600000 /**< priority of the constraint handler for constraint enforcing */
85#define CONSHDLR_CHECKPRIORITY -600000 /**< priority of the constraint handler for checking feasibility */
86#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
87#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
88#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
90#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
91#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
92#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
93#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
106#define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */
108#define MAX_USECLIQUES_SIZE 1000 /**< maximal number of items in knapsack where clique information is used */
109#define MAX_ZEROITEMS_SIZE 10000 /**< maximal number of items to store in the zero list in preprocessing */
111#define KNAPSACKRELAX_MAXDELTA 0.1 /**< maximal allowed rounding distance for scaling in knapsack relaxation */
112#define KNAPSACKRELAX_MAXDNOM 1000LL /**< maximal allowed denominator in knapsack rational relaxation */
113#define KNAPSACKRELAX_MAXSCALE 1000.0 /**< maximal allowed scaling factor in knapsack rational relaxation */
115#define DEFAULT_SEPACARDFREQ 1 /**< multiplier on separation frequency, how often knapsack cuts are separated */
117#define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
119#define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in the root node */
120#define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
122#define DEFAULT_DISAGGREGATION TRUE /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
124#define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in solving process */
126#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for knapsack relaxation */
127#define USESUPADDLIFT FALSE /**< should lifted minimal cover inequalities using superadditive up-lifting be separated in addition */
129#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
132#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
134#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
137#define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
140#define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
143#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 /**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
144#define MAXCOVERSIZEITERLEWI 1000 /**< maximal size for which LEWI are iteratively separated by reducing the feasible set */
148#define GUBSPLITGNC1GUBS FALSE /**< should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss? */
149#define DEFAULT_CLQPARTUPDATEFAC 1.5 /**< factor on the growth of global cliques to decide when to update a previous
151#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE /**< should clique partition information be updated when old partition seems outdated? */
152#define MAXNCLIQUEVARSCOMP 1000000 /**< limit on number of pairwise comparisons in clique partitioning algorithm */
154#define DEFAULT_UPGDCARDINALITY FALSE /**< if TRUE then try to update knapsack constraints to cardinality constraints */
157/* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
170 SCIP_Longint* longints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
172 SCIP_Longint* longints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
174 SCIP_Bool* bools1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
176 SCIP_Bool* bools2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
178 SCIP_Bool* bools3; /**< cleared memory array, all entries are set to zero in initpre, if you use this
180 SCIP_Bool* bools4; /**< cleared memory array, all entries are set to zero in initpre, if you use this
182 SCIP_Real* reals1; /**< cleared memory array, all entries are set to zero in consinit, if you use this
194 SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
196 int sepacardfreq; /**< multiplier on separation frequency, how often knapsack cuts are separated */
200 int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
201 SCIP_Bool disaggregation; /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
202 SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
204 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
205 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
208 SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
211 SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
214 SCIP_Bool updatecliquepartitions; /**< should clique partition information be updated when old partition seems outdated? */
215 SCIP_Real cliqueextractfactor;/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
216 SCIP_Real clqpartupdatefac; /**< factor on the growth of global cliques to decide when to update a previous
219 SCIP_Bool upgdcardinality; /**< if TRUE then try to update knapsack constraints to cardinality constraints */
220 SCIP_Bool upgradedcard; /**< whether we have already upgraded knapsack constraints to cardinality constraints */
239 int ncliqueslastnegpart;/**< number of global cliques the last time a negated clique partition was computed */
240 int ncliqueslastpart; /**< number of global cliques the last time a clique partition was computed */
244 unsigned int presolvedtiming:5; /**< max level in which the knapsack constraint is already presolved */
249 unsigned int cliquesadded:1; /**< were the cliques of the knapsack already added to clique table? */
280};
288 GUBCONSSTATUS_BELONGSTOSET_GF = 1, /** all GUB variables are in noncovervars F (and noncovervars R) */
290 GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, /** some GUB variables are in covervars C1, others in noncovervars R or F */
292};
382 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
401 /* sort all items with same weight according to their variable index, used for hash value for fast pairwise comparison of all constraints */
411 /* sort all corresponding parts of arrays for which the weights are equal by using the variable index */
423 /* we need to make sure that our clique numbers of our normal clique will be in increasing order without gaps */
430 /* if the clique number in the normal clique at position pos is greater than the last found clique number the
441 /* we need to make sure that our clique numbers of our negated clique will be in increasing order without gaps */
448 /* if the clique number in the negated clique at position pos is greater than the last found clique number the
485 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
489 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
493 SCIP_CALL( SCIPcalcCliquePartition(scip, consdata->vars, consdata->nvars, consdata->cliquepartition, &consdata->ncliques) );
498 /* rerun eventually if number of global cliques increased considerably since last negated partition */
500 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
504 SCIP_CALL( SCIPcalcNegatedCliquePartition(scip, consdata->vars, consdata->nvars, consdata->negcliquepartition, &consdata->nnegcliques) );
610 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->varssize, newsize) );
613 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
614 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->cliquepartition, consdata->varssize, newsize) );
615 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->negcliquepartition, consdata->varssize, newsize) );
693 if( SCIPisConsCompressionEnabled(scip) && SCIPvarGetLbGlobal(vars[v]) > SCIPvarGetUbGlobal(vars[v]) - 0.5 )
749 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
755 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
760 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->nvars) );
761 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->nvars) );
889 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) );
921 SCIPdebugMsg(scip, "adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT "): ",
941 /* skip deactivated, redundant, or local linear constraints (the NLP does not allow for local rows at the moment) */
974/** checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
980 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
992 SCIPdebugMsg(scip, "checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1005 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1013 /* sum separately over normal and huge weight contributions in order to reduce numerical cancellation */
1070 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well
1077 * @todo If only the objective is relevant, it is easy to change the code to use only one slice with O(capacity) space.
1078 * There are recursive methods (see the book by Kellerer et al.) that require O(capacity) space, but it remains
1080 * Dembo and Hammer (see Kellerer et al. Section 5.1.3, page 126) found a method that relies on a fast probing method.
1388 /* If the greedy solution is optimal by comparing to the LP solution, we take this solution. This happens if:
1390 * - the greedy solution has an objective that is at least the LP value rounded down in case that all profits are integer, too. */
1391 greedyupperbound = greedysolvalue + myprofits[j] * (SCIP_Real) (capacity - greedysolweight)/((SCIP_Real) myweights[j]);
1437 assert(sizeof(size_t) >= sizeof(int)); /*lint !e506*/ /* no following conversion should be messed up */
1439 /* this condition checks whether we will try to allocate a correct number of bytes and do not have an overflow, while
1442 if( intcap < 0 || (intcap > 0 && (((size_t)nmyitems) > (SIZE_MAX / (size_t)intcap / sizeof(*optvalues)) || ((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues) > ((size_t)INT_MAX) )) ) /*lint !e571*/
1444 SCIPdebugMsg(scip, "Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/
1466 /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid;
1467 * each value entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is
1468 * invalid; a second possibility would be to clear the whole optvalues, which should be more expensive than storing
1496 /* if index d < current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should be 0 */
1538 /* collect solution items; the first condition means that no further item can fit anymore, but this does */
1586/** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's
1587 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not
1633 /* partially sort indices such that all elements that are larger than the break item appear first */
1634 SCIPselectWeightedDownRealLongRealInt(tempsort, weights, profits, items, realweights, (SCIP_Real)capacity, nitems, &criticalindex);
1816 /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */
1821 /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */
1837/** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */
1862 SCIPdebugMsg(scip, " moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons);
1866 /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */
1869 /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement;
1878 assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var);
1880 /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */
1895 /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */
1901 /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement;
1914 /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint
1968/** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */
2009 /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */
2011 (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED;
2070 /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */
2078 SCIPdebugMsg(scip, " var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2115 /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */
2127 * afterwards the output array contains one value for each variable, such that two variables got the same value iff they
2129 * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of
2131 * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one
2132 * variable) and for the remaining variables, a partition with a small number of cliques is constructed
2138 SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */
2141 int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */
2187 /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables
2202 /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */
2210 /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */
2271 /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */
2292/** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */
2321 SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) );
2344 /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB);
2345 * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar()
2358 /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the
2362 assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */
2386/** gets a most violated cover C (\f$\sum_{j \in C} a_j > a_0\f$) for a given knapsack constraint \f$\sum_{j \in N} a_j x_j \leq a_0\f$
2387 * taking into consideration the following fixing: \f$j \in C\f$, if \f$j \in N_1 = \{j \in N : x^*_j = 1\}\f$ and
2404 SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */
2406 SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */
2502 /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop
2571 /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified)
2577 SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items,
2579 /*assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused));*/
2649 /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */
2661/** gets partition \f$(C_1,C_2)\f$ of minimal cover \f$C\f$, i.e. \f$C_1 \cup C_2 = C\f$ and \f$C_1 \cap C_2 = \emptyset\f$,
2662 * with \f$C_1\f$ not empty; chooses partition as follows \f$C_2 = \{ j \in C : x^*_j = 1 \}\f$ and \f$C_1 = C \setminus C_2\f$
2710/** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from
2752/** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */
2790/** gets partition \f$(F,R)\f$ of \f$N \setminus C\f$ where \f$C\f$ is a minimal cover, i.e. \f$F \cup R = N \setminus C\f$
2791 * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and
2839/** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential
2878 * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e.
2925/** categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs
2950 int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */
3011 * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence.
3014 * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality
3033 * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j).
3134 /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs
3153 /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth;
3160 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3168 /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into
3194 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3240 assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED);
3272 /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over)
3303 /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering
3320 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3342 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3356 /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted
3372 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3394 /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */
3395 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3473 * 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
3477 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and
3478 * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and
3541 /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1|
3596 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
3604 * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} }
3612 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3639 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3652 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3694 * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
3728 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3741 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3789 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
3823 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3922 * 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
3925 * 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 };
4030 /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current
4060 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4063 /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|;
4077 /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables)
4079 * GUBs in the group GCI are sorted by non-decreasing min{ a_k : k in GC1_j } where min{ a_k : k in GC1_j } always
4115 * GUBs in the group GCI are sorted by non-decreasing min{ a_k : k in GC1_j } where min{ a_k : k in GC1_j } always
4151 * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time
4185 /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */
4208 /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and
4218 /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that
4226 /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight
4227 * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB
4249 /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and
4261 /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */
4287 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
4295 * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}}
4299 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4339 * and finished and minweight table can be updated easily as only C1 variables need to be considered;
4348 * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB
4349 * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB
4372 * w = |gubconsGC1| + sum_{k=1,2,..,i-1}sum_{j in Q_k} alpha_j+1,..,|C1| + sum_{k=1,2,..,i}sum_{j in Q_k} alpha_j
4380 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) );
4383 * note that instead of computing minweight table from updated finished and updated unfinished table again
4384 * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here
4385 * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight
4386 * not needed because only finished table changed at this point and the change was "adding" one weight)
4431 /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished;
4445 liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */
4453 * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
4469 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4487 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
4498 * w = |C1| + sum_{k=1,2,...,i-1}sum_{j in Q_k} alpha_j + 1 , ... , |C1| + sum_{k=1,2,...,i}sum_{j in Q_k} alpha_j
4500 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
4562 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
4602 /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */
4679 SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
4715 /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C|
4793/** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for
4839 /* gets partition (C_1,C_2) of C, i.e. C_1 & C_2 = C and C_1 cap C_2 = emptyset, with C_1 not empty; chooses partition
4844 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4847 assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */
4849 /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */
4857 /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows
4861 getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR);
4868 /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential
4871 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) );
4877 * to a valid inequality sum_{j in C_1} x_j + sum_{j in N\C_1} alpha_j x_j <= |C_1| - 1 + sum_{j in C_2} alpha_j for
4881 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential
4884 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2,
4918 /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of
4921 SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1,
4922 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4930 * to a valid inequality sum_{j in C_1} x_j + sum_{j in N\C_1} alpha_j x_j <= |C_1| - 1 + sum_{j in C_2} alpha_j for
4932 * 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 },
4938 SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1,
4960 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
4961 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
4967 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
4968 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4973 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4976 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5029/** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */
5073 /* gets partition (T_1,T_2) of T, i.e. T_1 & T_2 = T and T_1 cap T_2 = emptyset, with T_1 not empty; chooses partition
5078 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5081 /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */
5084 SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) );
5089 /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows
5093 getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR);
5097 /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential
5098 * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it
5101 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) );
5107 * to a valid inequality sum_{j in T_1} x_j + sum_{j in N\T_1} alpha_j x_j <= |T_1| + sum_{j in T_2} alpha_j for
5111 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential
5114 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5127 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5128 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5134 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5135 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5140 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5143 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5196/** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */
5239 SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars,
5254 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5255 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5261 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5262 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5267 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5270 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5282 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) );
5306/** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen
5307 * 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
5308 * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C;
5344 /* allocates temporary memory; we need two arrays for the keypairs in order to be able to free them in the correct
5351 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5352 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C