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*/
79 #define CONSHDLR_ENFOPRIORITY -600000 /**< priority of the constraint handler for constraint enforcing */
80 #define CONSHDLR_CHECKPRIORITY -600000 /**< priority of the constraint handler for checking feasibility */
81 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
82 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
83 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
85 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
86 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
87 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
88 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
101 #define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */
103 #define MAX_USECLIQUES_SIZE 1000 /**< maximal number of items in knapsack where clique information is used */
104 #define MAX_ZEROITEMS_SIZE 10000 /**< maximal number of items to store in the zero list in preprocessing */
106 #define KNAPSACKRELAX_MAXDELTA 0.1 /**< maximal allowed rounding distance for scaling in knapsack relaxation */
107 #define KNAPSACKRELAX_MAXDNOM 1000LL /**< maximal allowed denominator in knapsack rational relaxation */
108 #define KNAPSACKRELAX_MAXSCALE 1000.0 /**< maximal allowed scaling factor in knapsack rational relaxation */
110 #define DEFAULT_SEPACARDFREQ 1 /**< multiplier on separation frequency, how often knapsack cuts are separated */
111 #define DEFAULT_MAXROUNDS 5 /**< maximal number of separation rounds per node (-1: unlimited) */
112 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
114 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in the root node */
115 #define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
117 #define DEFAULT_DISAGGREGATION TRUE /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
119 #define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in solving process */
121 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for knapsack relaxation */
122 #define USESUPADDLIFT FALSE /**< should lifted minimal cover inequalities using superadditive up-lifting be separated in addition */
124 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
125 #define HASHSIZE_KNAPSACKCONS 500 /**< minimal size of hash table in linear constraint tables */
127 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
129 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
132 #define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
135 #define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
138 #define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 /**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
139 #define MAXCOVERSIZEITERLEWI 1000 /**< maximal size for which LEWI are iteratively separated by reducing the feasible set */
143 #define GUBSPLITGNC1GUBS FALSE /**< should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss? */
144 #define DEFAULT_CLQPARTUPDATEFAC 1.5 /**< factor on the growth of global cliques to decide when to update a previous
146 #define DEFAULT_UPDATECLIQUEPARTITIONS FALSE /**< should clique partition information be updated when old partition seems outdated? */
147 #define MAXNCLIQUEVARSCOMP 1000000 /**< limit on number of pairwise comparisons in clique partitioning algorithm */
149 #define DEFAULT_UPGDCARDINALITY FALSE /**< if TRUE then try to update knapsack constraints to cardinality constraints */
152 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
165 SCIP_Longint* longints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
167 SCIP_Longint* longints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
169 SCIP_Bool* bools1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
171 SCIP_Bool* bools2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
173 SCIP_Bool* bools3; /**< cleared memory array, all entries are set to zero in initpre, if you use this
175 SCIP_Bool* bools4; /**< cleared memory array, all entries are set to zero in initpre, if you use this
177 SCIP_Real* reals1; /**< cleared memory array, all entries are set to zero in consinit, if you use this
189 SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
191 int sepacardfreq; /**< multiplier on separation frequency, how often knapsack cuts are separated */
195 int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
196 SCIP_Bool disaggregation; /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
197 SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
199 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
200 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
203 SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
206 SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
209 SCIP_Bool updatecliquepartitions; /**< should clique partition information be updated when old partition seems outdated? */
210 SCIP_Real cliqueextractfactor;/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
211 SCIP_Real clqpartupdatefac; /**< factor on the growth of global cliques to decide when to update a previous
214 SCIP_Bool upgdcardinality; /**< if TRUE then try to update knapsack constraints to cardinality constraints */
215 SCIP_Bool upgradedcard; /**< whether we have already upgraded knapsack constraints to cardinality constraints */
234 int ncliqueslastnegpart;/**< number of global cliques the last time a negated clique partition was computed */
235 int ncliqueslastpart; /**< number of global cliques the last time a clique partition was computed */
239 unsigned int presolvedtiming:5; /**< max level in which the knapsack constraint is already presolved */
244 unsigned int cliquesadded:1; /**< were the cliques of the knapsack already added to clique table? */
275 };
280 {
283 GUBCONSSTATUS_BELONGSTOSET_GF = 1, /** all GUB variables are in noncovervars F (and noncovervars R) */
285 GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, /** some GUB variables are in covervars C1, others in noncovervars R or F */
287 };
292 {
302 {
309 };
377 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
396 /* sort all items with same weight according to their variable index, used for hash value for fast pairwise comparison of all constraints */
406 /* sort all corresponding parts of arrays for which the weights are equal by using the variable index */
418 /* we need to make sure that our clique numbers of our normal clique will be in increasing order without gaps */
425 /* if the clique number in the normal clique at position pos is greater than the last found clique number the
436 /* we need to make sure that our clique numbers of our negated clique will be in increasing order without gaps */
443 /* if the clique number in the negated clique at position pos is greater than the last found clique number the
480 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
484 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
488 SCIP_CALL( SCIPcalcCliquePartition(scip, consdata->vars, consdata->nvars, consdata->cliquepartition, &consdata->ncliques) );
493 /* rerun eventually if number of global cliques increased considerably since last negated partition */
495 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
499 SCIP_CALL( SCIPcalcNegatedCliquePartition(scip, consdata->vars, consdata->nvars, consdata->negcliquepartition, &consdata->nnegcliques) );
597 assert(consdata->nvars <= consdata->varssize);
605 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->varssize, newsize) );
608 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
609 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->cliquepartition, consdata->varssize, newsize) );
610 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->negcliquepartition, consdata->varssize, newsize) );
655 {
688 if( SCIPisConsCompressionEnabled(scip) && SCIPvarGetLbGlobal(vars[v]) > SCIPvarGetUbGlobal(vars[v]) - 0.5 )
744 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
750 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
755 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->nvars) );
756 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->nvars) );
884 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) );
916 SCIPdebugMsg(scip, "adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT "): ",
936 /* skip deactivated, redundant, or local linear constraints (the NLP does not allow for local rows at the moment) */
969 /** checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
975 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
979 {
987 SCIPdebugMsg(scip, "checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1001 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1073 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well
1080 * @todo If only the objective is relevant, it is easy to change the code to use only one slice with O(capacity) space.
1081 * There are recursive methods (see the book by Kellerer et al.) that require O(capacity) space, but it remains
1083 * Dembo and Hammer (see Kellerer et al. Section 5.1.3, page 126) found a method that relies on a fast probing method.
1391 /* If the greedy solution is optimal by comparing to the LP solution, we take this solution. This happens if:
1393 * - the greedy solution has an objective that is at least the LP value rounded down in case that all profits are integer, too. */
1394 greedyupperbound = greedysolvalue + myprofits[j] * (SCIP_Real) (capacity - greedysolweight)/((SCIP_Real) myweights[j]);
1440 assert(sizeof(size_t) >= sizeof(int)); /*lint !e506*/ /* no following conversion should be messed up */
1442 /* this condition checks whether we will try to allocate a correct number of bytes and do not have an overflow, while
1445 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*/
1447 SCIPdebugMsg(scip, "Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/
1469 /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid;
1470 * each value entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is
1471 * invalid; a second possibility would be to clear the whole optvalues, which should be more expensive than storing
1499 /* if index d < current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should be 0 */
1541 /* collect solution items; the first condition means that no further item can fit anymore, but this does */
1589 /** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's
1590 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not
1636 /* partially sort indices such that all elements that are larger than the break item appear first */
1637 SCIPselectWeightedDownRealLongRealInt(tempsort, weights, profits, items, realweights, (SCIP_Real)capacity, nitems, &criticalindex);
1819 /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */
1824 /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */
1840 /** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */
1850 {
1865 SCIPdebugMsg(scip, " moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons);
1869 /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */
1872 /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement;
1881 assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var);
1883 /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */
1898 /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */
1904 /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement;
1917 /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint
1971 /** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */
2012 /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */
2014 (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED;
2073 /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */
2081 SCIPdebugMsg(scip, " var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2118 /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */
2130 * afterwards the output array contains one value for each variable, such that two variables got the same value iff they
2132 * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of
2134 * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one
2135 * variable) and for the remaining variables, a partition with a small number of cliques is constructed
2141 SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */
2144 int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */
2147 {
2190 /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables
2205 /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */
2213 /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */
2274 /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */
2295 /** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */
2324 SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) );
2347 /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB);
2348 * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar()
2361 /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the
2365 assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */
2389 /** 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$
2390 * 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
2407 SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */
2409 SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */
2505 /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop
2574 /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified)
2580 SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items,
2582 /*assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused));*/
2633 )
2652 /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */
2664 /** 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$,
2665 * 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$
2713 /** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from
2725 {
2755 /** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */
2765 {
2793 /** 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$
2794 * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and
2842 /** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential
2881 * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e.
2928 /** categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs
2953 int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */
3014 * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence.
3017 * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality
3036 * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j).
3137 /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs
3156 /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth;
3163 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3171 /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into
3197 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3243 assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED);
3275 /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over)
3306 /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering
3323 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3345 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3359 /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted
3375 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3397 /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */
3398 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3476 * 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
3480 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and
3481 * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and
3544 /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1|
3599 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
3607 * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} }
3615 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3642 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3655 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3697 * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
3731 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3744 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3792 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
3826 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3925 * 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
3928 * 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 };
4033 /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current
4063 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4066 /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|;
4080 /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables)
4082 * 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
4118 * 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
4154 * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time
4188 /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */
4211 /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and
4221 /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that
4229 /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight
4230 * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB
4252 /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and
4264 /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */
4290 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
4298 * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}}
4302 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4342 * and finished and minweight table can be updated easily as only C1 variables need to be considered;
4351 * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB
4352 * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB
4375 * 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
4383 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) );
4386 * note that instead of computing minweight table from updated finished and updated unfinished table again
4387 * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here
4388 * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight
4389 * not needed because only finished table changed at this point and the change was "adding" one weight)
4434 /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished;
4448 liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */
4456 * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
4472 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4490 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
4501 * 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
4503 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
4565 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
4605 /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */
4682 SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
4718 /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C|
4796 /** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for
4842 /* 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
4847 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4850 assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */
4852 /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */
4860 /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows
4864 getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR);
4871 /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential
4874 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) );
4880 * 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
4884 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential
4887 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2,
4921 /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of
4924 SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1,
4925 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4933 * 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
4935 * 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 },
4941 SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1,
4963 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
4964 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
4970 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
4971 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4976 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4979 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5032 /** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */
5076 /* 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
5081 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5084 /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */
5087 SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) );
5092 /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows
5096 getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR);
5100 /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential
5101 * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it
5104 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) );
5110 * 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
5114 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential
5117 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5130 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5131 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5137 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5138 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5143 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5146 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5199 /** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */
5242 SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars,
5257 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5258 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5264 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5265 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5270 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5273 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5285 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) );
5309 /** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen
5310 * 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
5311 * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C;
5347 /* allocates temporary memory; we need two arrays for the keypairs in order to be able to free them in the correct
5354 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5355 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5356 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5402 assert(checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5456 /** converts given initial cover C_init to a feasible set by removing variables in the reverse order in which
5459 * non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init.
5460 * separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set
5508 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5509 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5510 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5530 /* removes variables from C_init and separates lifted extended weight inequalities using sequential up- and down-lifting;
5547 SCIP_CALL( separateSequLiftedExtendedWeightInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals,
5624 SCIPdebugMsgPrint(scip, "%+" SCIP_LONGINT_FORMAT "<%s>(%g)", weights[i], SCIPvarGetName(vars[i]), solvals[i]);
5630 /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting) using GUB information
5652 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5671 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5672 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5674 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5677 /* only separate with GUB information if we have at least one nontrivial GUB (with more than one variable) */
5680 /* separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information */
5681 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5686 /* separates lifted minimal cover inequalities using sequential up- and down-lifting, but do not use trivial
5689 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5711 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5722 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5723 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5725 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5729 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5736 SCIP_CALL( separateSupLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5737 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5753 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5761 /* converts initial cover C_init to a feasible set by removing variables in the reverse order in which
5762 * they were chosen to be in C_init and separates lifted extended weight inequalities using sequential
5765 SCIP_CALL( getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5779 /* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */
5786 SCIP_Real* knapvals, /**< coefficients of the variables in the continuous knapsack constraint */
5787 SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */
5819 SCIPdebugMsg(scip, "separate linear constraint <%s> relaxed to knapsack\n", cons != NULL ? SCIPconsGetName(cons) : "-");
5824 /* all variables which are of integral type can be potentially of binary type; this can be checked via the method SCIPvarIsBinary(var) */
5855 /* increase array size to avoid an endless loop in the next block; this might happen if continuous variables
5860 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, conshdlrdata->reals1size, 1) );
5867 /* next if condition should normally not be true, because it means that presolving has created more binary
5868 * variables than binary + integer variables existed at the constraint initialization method, but for example if you would
5876 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, oldsize, conshdlrdata->reals1size) );
5877 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize); /*lint !e866 */
5895 * - a_j < 0: x_j = lb or x_j = b*z + d with variable lower bound b*z + d with binary variable z
5896 * - a_j > 0: x_j = ub or x_j = b*z + d with variable upper bound b*z + d with binary variable z
5933 SCIPdebugMsg(scip, " -> binary variable %+.15g<%s>(%.15g)\n", valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
5961 if( (bvlb[j] >= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetLbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) ||
5962 (bvlb[j] <= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetUbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) )
5967 bvlb[j], SCIPvarGetName(zvlb[j]), SCIPvarGetLbLocal(zvlb[j]), SCIPvarGetUbLocal(zvlb[j]), dvlb[j]);
5988 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5989 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbGlobal(var), rhs);
5993 assert(0 <= SCIPvarGetProbindex(zvlb[bestlbtype]) && SCIPvarGetProbindex(zvlb[bestlbtype]) < nbinvars);
6007 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",