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 */
116 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
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 */
130 #define HASHSIZE_KNAPSACKCONS 500 /**< minimal size of hash table in linear constraint tables */
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 };
285 {
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 };
297 {
307 {
314 };
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) );
602 assert(consdata->nvars <= consdata->varssize);
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) );
660 {
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? */
984 {
992 SCIPdebugMsg(scip, "checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1006 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1078 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well
1085 * @todo If only the objective is relevant, it is easy to change the code to use only one slice with O(capacity) space.
1086 * There are recursive methods (see the book by Kellerer et al.) that require O(capacity) space, but it remains
1088 * Dembo and Hammer (see Kellerer et al. Section 5.1.3, page 126) found a method that relies on a fast probing method.
1396 /* If the greedy solution is optimal by comparing to the LP solution, we take this solution. This happens if:
1398 * - the greedy solution has an objective that is at least the LP value rounded down in case that all profits are integer, too. */
1399 greedyupperbound = greedysolvalue + myprofits[j] * (SCIP_Real) (capacity - greedysolweight)/((SCIP_Real) myweights[j]);
1445 assert(sizeof(size_t) >= sizeof(int)); /*lint !e506*/ /* no following conversion should be messed up */
1447 /* this condition checks whether we will try to allocate a correct number of bytes and do not have an overflow, while
1450 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*/
1452 SCIPdebugMsg(scip, "Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/
1474 /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid;
1475 * each value entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is
1476 * invalid; a second possibility would be to clear the whole optvalues, which should be more expensive than storing
1504 /* if index d < current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should be 0 */
1546 /* collect solution items; the first condition means that no further item can fit anymore, but this does */
1594 /** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's
1595 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not
1641 /* partially sort indices such that all elements that are larger than the break item appear first */
1642 SCIPselectWeightedDownRealLongRealInt(tempsort, weights, profits, items, realweights, (SCIP_Real)capacity, nitems, &criticalindex);
1824 /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */
1829 /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */
1845 /** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */
1855 {
1870 SCIPdebugMsg(scip, " moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons);
1874 /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */
1877 /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement;
1886 assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var);
1888 /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */
1903 /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */
1909 /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement;
1922 /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint
1976 /** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */
2017 /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */
2019 (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED;
2078 /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */
2086 SCIPdebugMsg(scip, " var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2123 /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */
2135 * afterwards the output array contains one value for each variable, such that two variables got the same value iff they
2137 * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of
2139 * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one
2140 * variable) and for the remaining variables, a partition with a small number of cliques is constructed
2146 SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */
2149 int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */
2152 {
2195 /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables
2210 /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */
2218 /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */
2279 /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */
2300 /** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */
2329 SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) );
2352 /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB);
2353 * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar()
2366 /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the
2370 assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */
2394 /** 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$
2395 * 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
2412 SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */
2414 SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */
2510 /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop
2579 /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified)
2585 SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items,
2587 /*assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused));*/
2638 )
2657 /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */
2669 /** 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$,
2670 * 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$
2718 /** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from
2730 {
2760 /** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */
2770 {
2798 /** 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$
2799 * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and
2847 /** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential
2886 * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e.
2933 /** categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs
2958 int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */
3019 * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence.
3022 * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality
3041 * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j).
3142 /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs
3161 /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth;
3168 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3176 /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into
3202 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3248 assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED);
3280 /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over)
3311 /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering
3328 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3350 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3364 /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted
3380 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3402 /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */
3403 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3481 * 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
3485 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and
3486 * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and
3549 /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1|
3604 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
3612 * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} }
3620 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3647 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3660 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3702 * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
3736 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3749 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3797 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
3831 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3930 * 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
3933 * 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 };
4038 /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current
4068 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4071 /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|;
4085 /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables)
4087 * 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
4123 * 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
4159 * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time
4193 /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */
4216 /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and
4226 /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that
4234 /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight
4235 * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB
4257 /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and
4269 /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */
4295 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
4303 * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}}
4307 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4347 * and finished and minweight table can be updated easily as only C1 variables need to be considered;
4356 * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB
4357 * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB
4380 * 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
4388 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) );
4391 * note that instead of computing minweight table from updated finished and updated unfinished table again
4392 * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here
4393 * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight
4394 * not needed because only finished table changed at this point and the change was "adding" one weight)
4439 /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished;
4453 liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */
4461 * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
4477 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4495 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
4506 * 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
4508 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
4570 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
4610 /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */
4687 SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
4723 /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C|
4801 /** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for
4847 /* 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
4852 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4855 assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */
4857 /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */
4865 /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows
4869 getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR);
4876 /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential
4879 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) );
4885 * 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
4889 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential
4892 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2,
4926 /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of
4929 SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1,
4930 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4938 * 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
4940 * 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 },
4946 SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1,
4968 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
4969 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
4975 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
4976 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4981 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4984 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5037 /** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */
5081 /* 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
5086 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5089 /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */
5092 SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) );
5097 /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows
5101 getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR);
5105 /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential
5106 * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it
5109 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) );
5115 * 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
5119 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential
5122 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5135 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5136 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5142 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5143 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5148 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5151 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5204 /** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */
5247 SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars,
5262 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5263 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5269 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5270 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5275 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5278 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5290 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) );
5314 /** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen
5315 * 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
5316 * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C;
5352 /* allocates temporary memory; we need two arrays for the keypairs in order to be able to free them in the correct
5359 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5360 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5361 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5407 assert(checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5461 /** converts given initial cover C_init to a feasible set by removing variables in the reverse order in which
5464 * non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init.
5465 * separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set
5513 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5514 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5515 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5535 /* removes variables from C_init and separates lifted extended weight inequalities using sequential up- and down-lifting;
5552 SCIP_CALL( separateSequLiftedExtendedWeightInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals,
5629 SCIPdebugMsgPrint(scip, "%+" SCIP_LONGINT_FORMAT "<%s>(%g)", weights[i], SCIPvarGetName(vars[i]), solvals[i]);
5635 /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting) using GUB information
5657 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5676 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5677 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5679 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5682 /* only separate with GUB information if we have at least one nontrivial GUB (with more than one variable) */
5685 /* separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information */
5686 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5691 /* separates lifted minimal cover inequalities using sequential up- and down-lifting, but do not use trivial
5694 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5716 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5727 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5728 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5730 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5734 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5741 SCIP_CALL( separateSupLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5742 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5758 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5766 /* converts initial cover C_init to a feasible set by removing variables in the reverse order in which
5767 * they were chosen to be in C_init and separates lifted extended weight inequalities using sequential
5770 SCIP_CALL( getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5784 /* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */
5791 SCIP_Real* knapvals, /**< coefficients of the variables in the continuous knapsack constraint */
5792 SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */
5824 SCIPdebugMsg(scip, "separate linear constraint <%s> relaxed to knapsack\n", cons != NULL ? SCIPconsGetName(cons) : "-");
5829 /* all variables which are of integral type can be potentially of binary type; this can be checked via the method SCIPvarIsBinary(var) */
5860 /* increase array size to avoid an endless loop in the next block; this might happen if continuous variables
5865 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, conshdlrdata->reals1size, 1) );
5872 /* next if condition should normally not be true, because it means that presolving has created more binary
5873 * variables than binary + integer variables existed at the constraint initialization method, but for example if you would
5881 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, oldsize, conshdlrdata->reals1size) );
5882 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize); /*lint !e866 */
5900 * - a_j < 0: x_j = lb or x_j = b*z + d with variable lower bound b*z + d with binary variable z
5901 * - a_j > 0: x_j = ub or x_j = b*z + d with variable upper bound b*z + d with binary variable z
5938 SCIPdebugMsg(scip, " -> binary variable %+.15g<%s>(%.15g)\n", valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
5966 if( (bvlb[j] >= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetLbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) ||
5967 (bvlb[j] <= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetUbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) )
5972 bvlb[j], SCIPvarGetName(zvlb[j]), SCIPvarGetLbLocal(zvlb[j]), SCIPvarGetUbLocal(zvlb[j]), dvlb[j]);
5993 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5994 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbGlobal(var), rhs);
5998 assert(0 <= SCIPvarGetProbindex(zvlb[bestlbtype]) && SCIPvarGetProbindex(zvlb[bestlbtype]) < nbinvars);