cons_knapsack.c
Go to the documentation of this file.
17 * @brief Constraint handler for knapsack constraints of the form \f$a^T x \le b\f$, x binary and \f$a \ge 0\f$. 24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 42 #define CONSHDLR_ENFOPRIORITY -600000 /**< priority of the constraint handler for constraint enforcing */ 43 #define CONSHDLR_CHECKPRIORITY -600000 /**< priority of the constraint handler for checking feasibility */ 44 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */ 45 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 46 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 48 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 49 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 50 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 51 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 59 #define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */ 62 #define MAX_DYNPROG_CAPACITY 10000 /**< maximal capacity of knapsack to apply dynamic programming */ 65 #define MAX_USECLIQUES_SIZE 1000 /**< maximal number of items in knapsack where clique information is used */ 66 #define MAX_ZEROITEMS_SIZE 10000 /**< maximal number of items to store in the zero list in preprocessing */ 68 #define KNAPSACKRELAX_MAXDELTA 0.1 /**< maximal allowed rounding distance for scaling in knapsack relaxation */ 69 #define KNAPSACKRELAX_MAXDNOM 1000LL /**< maximal allowed denominator in knapsack rational relaxation */ 70 #define KNAPSACKRELAX_MAXSCALE 1000.0 /**< maximal allowed scaling factor in knapsack rational relaxation */ 72 #define DEFAULT_SEPACARDFREQ 1 /**< multiplier on separation frequency, how often knapsack cuts are separated */ 74 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */ 76 #define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in the root node */ 77 #define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared 79 #define DEFAULT_DISAGGREGATION TRUE /**< should disaggregation of knapsack constraints be allowed in preprocessing? */ 81 #define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in solving process */ 83 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for knapsack relaxation */ 84 #define USESUPADDLIFT FALSE /**< should lifted minimal cover inequalities using superadditive up-lifting be separated in addition */ 86 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */ 87 #define HASHSIZE_KNAPSACKCONS 131101 /**< minimal size of hash table in linear constraint tables */ 89 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */ 91 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise 94 #define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective 97 #define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective 101 #define MAXCOVERSIZEITERLEWI 1000 /**< maximal size for which LEWI are iteratively separated by reducing the feasible set */ 105 #define GUBSPLITGNC1GUBS FALSE /**< should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss? */ 108 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */ 121 SCIP_Longint* longints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this 123 SCIP_Longint* longints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this 125 SCIP_Bool* bools1; /**< cleared memory array, all entries are set to zero in initpre, if you use this 127 SCIP_Bool* bools2; /**< cleared memory array, all entries are set to zero in initpre, if you use this 129 SCIP_Bool* bools3; /**< cleared memory array, all entries are set to zero in initpre, if you use this 131 SCIP_Bool* bools4; /**< cleared memory array, all entries are set to zero in initpre, if you use this 133 SCIP_Real* reals1; /**< cleared memory array, all entries are set to zero in consinit, if you use this 145 SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared 147 int sepacardfreq; /**< multiplier on separation frequency, how often knapsack cuts are separated */ 151 int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */ 152 SCIP_Bool disaggregation; /**< should disaggregation of knapsack constraints be allowed in preprocessing? */ 153 SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */ 155 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */ 156 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */ 159 SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective 162 SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective 185 unsigned int presolvedtiming:5; /**< max level in which the knapsack constraint is already presolved */ 190 unsigned int cliquesadded:1; /**< were the cliques of the knapsack already added to clique table? */ 227 { 230 GUBCONSSTATUS_BELONGSTOSET_GF = 1, /** all GUB variables are in noncovervars F (and noncovervars R) */ 232 GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, /** some GUB variables are in covervars C1, others in noncovervars R or F */ 239 { 249 { 324 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL)); 343 /* sort all items with same weight according to their variable index, used for hash value for fast pairwise comparison of all constraints */ 353 /* sort all corresponding parts of arrays for which the weights are equal by using the variable index */ 365 /* we need to make sure that our clique numbers of our normal clique will be in increasing order without gaps */ 372 /* if the clique number in the normal clique at position pos is greater than the last found clique number the 383 /* we need to make sure that our clique numbers of our negated clique will be in increasing order without gaps */ 390 /* if the clique number in the negated clique at position pos is greater than the last found clique number the 424 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL)); 428 SCIP_CALL( SCIPcalcCliquePartition(scip, consdata->vars, consdata->nvars, consdata->cliquepartition, &consdata->ncliques) ); 434 SCIP_CALL( SCIPcalcNegatedCliquePartition(scip, consdata->vars, consdata->nvars, consdata->negcliquepartition, &consdata->nnegcliques) ); 544 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->varssize, newsize) ); 547 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) ); 548 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->cliquepartition, consdata->varssize, newsize) ); 549 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->negcliquepartition, consdata->varssize, newsize) ); 657 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) ); 663 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR); 668 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->nvars) ); 669 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->nvars) ); 791 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, SCIPconsGetHdlr(cons), SCIPconsGetName(cons), 798 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) ); 831 SCIPdebugMessage("adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT "): ", 840 /** checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible */ 846 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 849 ) 858 SCIPdebugMessage("checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n", 870 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in 906 if( (!ishuge && integralsum > consdata->capacity) || (ishuge && SCIPisFeasGT(scip, sum, (SCIP_Real)consdata->capacity)) ) 940 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part as well 1239 /* this condition checks if we will try to allocate a correct number of bytes and do not have an overflow, while 1242 if( intcap < 0 || (intcap > 0 && (((size_t)nmyitems) > (maxsize_t / (size_t)intcap / sizeof(*optvalues)) || ((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues) > ((size_t)INT_MAX) )) ) /*lint !e571*/ 1244 SCIPdebugMessage("Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/ 1251 /* @note we do allocate normal memory instead of buffer memory, because the buffer, will not be deleted directly and 1348 /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid; 1349 * all values entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is 1350 * invalid, a second possibility would be to clear the whole optvalues, which should be more expensive than storing 1377 /* if index d is smaller the the current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should 1413 /* if we cannot find any item anymore which is in our solution stop, if the following condition holds this 1422 /* collect solution items, first condition means that no next item can fit anymore, but this does */ 1481 /** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's 1482 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not 1578 assert(SCIPisFeasGE(scip, transprofits[j-1]/transweights[j-1], transprofits[j]/transweights[j])); 1761 /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */ 1766 /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */ 1782 /** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */ 1791 ) 1807 SCIPdebugMessage(" moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons); 1811 /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */ 1814 /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement; 1823 assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var); 1825 /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */ 1840 /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */ 1846 /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement; 1859 /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint 1913 /** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */ 1922 { 1954 /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */ 1956 (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED; 2018 /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */ 2026 SCIPdebugMessage(" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i, 2063 /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */ 2075 * afterwards the output array contains one value for each variable, such that two variables got the same value iff they 2077 * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of 2079 * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one 2080 * variable) and for the remaining variables, a partition with a small number of cliques is constructed 2086 SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */ 2089 int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */ 2091 ) 2136 /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables 2151 /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */ 2159 /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */ 2220 /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */ 2241 /** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */ 2270 SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) ); 2293 /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB); 2294 * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar() 2307 /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the 2311 assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */ 2335 /** 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$ 2336 * 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 2353 SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */ 2355 SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */ 2451 /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop 2520 /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified) 2526 SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items, 2528 assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused)); 2598 /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */ 2610 /** 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$, 2611 * 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$ 2659 /** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from 2670 ) 2701 /** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */ 2710 ) 2739 /** 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$ 2740 * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and 2788 /** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential 2827 * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e. 2874 /** categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs 2899 int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */ 2962 * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence. 2965 * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality 2988 * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j). 3108 /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs 3127 /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth; 3134 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */ 3142 /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into 3166 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 ) 3212 assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED); 3244 /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over) 3273 /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering 3288 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */ 3310 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 ) 3324 /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted 3338 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */ 3360 /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */ 3361 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR)); 3405 { 3439 * 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 3443 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and 3444 * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and 3507 /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1| 3562 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs, 3570 * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } 3578 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight); 3605 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */ 3618 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) ); 3660 * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}} 3694 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */ 3707 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) ); 3755 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} } 3789 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */ 3888 * 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 3891 * 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 }; 3993 /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current 4023 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed); 4026 /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|; 4040 /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables) 4042 * 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 4078 * 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 4114 * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time 4148 /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */ 4171 /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and 4181 /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that 4189 /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight 4190 * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB 4212 /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and 4224 /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */ 4250 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs, 4258 * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}} 4262 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight); 4302 * and finished and minweight table can be updated easily as only C1 variables need to be considered; 4311 * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB 4312 * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB 4335 * 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 4343 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) ); 4346 * note that instead of computing minweight table from updated finished and updated unfinished table again 4347 * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here 4348 * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight 4349 * not needed because only finished table changed at this point and the change was "adding" one weight) 4394 /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished; 4408 liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */ 4416 * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}} 4432 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight); 4450 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */ 4461 * 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 4463 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) ); 4525 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} } 4565 /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */ 4642 SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */ 4678 /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C| 4756 /** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for 4802 /* 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 4807 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2); 4810 assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */ 4812 /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */ 4820 /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows 4824 getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR); 4831 /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential 4834 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) ); 4840 * 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 4844 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential 4847 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2, 4881 /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of 4884 SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1, 4885 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2, 4893 * 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 4895 * 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 }, 4901 SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1, 4923 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons))); 4924 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, 4930 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa)); 4931 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 4936 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 4939 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */ 4992 /** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */ 5036 /* 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 5041 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2); 5044 /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */ 5047 SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) ); 5052 /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows 5056 getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR); 5060 /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential 5061 * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it 5064 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) ); 5070 * 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 5074 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential 5077 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR, 5090 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons))); 5091 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, 5097 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa)); 5098 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 5103 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 5106 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */ 5159 /** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */ 5202 SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars, 5217 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons))); 5218 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, 5224 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa)); 5225 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 5230 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) ); 5233 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */ 5245 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) ); 5269 /** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen 5270 * 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 5271 * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C; 5311 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C 5312 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C 5313 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C 5357 assert(checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j)); 5410 /** converts given initial cover C_init to a feasible set by removing variables in the reverse order in which 5413 * non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init. 5414 * separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set 5462 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C 5463 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C 5464 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C 5484 /* removes variables from C_init and separates lifted extended weight inequalities using sequential up- and down-lifting; 5501 SCIP_CALL( separateSequLiftedExtendedWeightInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, 5578 SCIPdebugPrintf("%+" SCIP_LONGINT_FORMAT "<%s>(%g)", weights[i], SCIPvarGetName(vars[i]), solvals[i]); 5584 /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting) using GUB information 5606 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars, 5625 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the 5626 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last 5628 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars, 5631 /* only separate with GUB information if we have at least one nontrivial GUB (with more than one variable) */ 5634 /* separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information */ 5635 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, 5640 /* separates lifted minimal cover inequalities using sequential up- and down-lifting, but do not use trivial 5643 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, 5665 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, 5683 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, 5690 SCIP_CALL( separateSupLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, 5691 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) ); 5707 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars, 5715 /* converts initial cover C_init to a feasible set by removing variables in the reverse order in which 5716 * they were chosen to be in C_init and separates lifted extended weight inequalities using sequential 5719 SCIP_CALL( getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars, 5733 /* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */ 5740 SCIP_Real* knapvals, /**< coefficient of the variables in the continuous knapsack constraint */ 5741 SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */ 5773 SCIPdebugMessage("separate linear constraint <%s> relaxed to knapsack\n", cons != NULL ? SCIPconsGetName(cons) : "-"); 5778 /* all variables which are of integral type can be potentially of binary type; this can be checked via the method SCIPvarIsBinary(var) */ 5809 /* increase array size to avoid an endless loop in the next block; this might happen if continuous variables 5821 /* next if condition should normally not be true, because it means that presolving has created more binary 5822 * variables than binary + integer variables existed at the constraint initialization method, but for example if you would 5833 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize); /*lint !e866 */ 5851 * - a_j < 0: x_j = lb or x_j = b*z + d with variable lower bound b*z + d with binary variable z 5852 * - a_j > 0: x_j = ub or x_j = b*z + d with variable upper bound b*z + d with binary variable z 5876 SCIPdebugMessage(" -> binary variable %+.15g<%s>(%.15g)\n", valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var)); 5904 if( (bvlb[j] >= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetLbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) || 5905 (bvlb[j] <= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetUbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) ) 5910 bvlb[j], SCIPvarGetName(zvlb[j]), SCIPvarGetLbLocal(zvlb[j]), SCIPvarGetUbLocal(zvlb[j]), dvlb[j]); 5931 SCIPdebugMessage(" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n", 5932 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbGlobal(var), rhs); 5936 assert(0 <= SCIPvarGetProbindex(zvlb[bestlbtype]) && SCIPvarGetProbindex(zvlb[bestlbtype]) < nbinvars); 5950 SCIPdebugMessage(" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n", 5984 if( (bvub[j] >= 0.0 && SCIPisLT(scip, bvub[j] * SCIPvarGetUbLocal(zvub[j]) + dvub[j], SCIPvarGetLbLocal(var))) || 5985 (bvub[j] <= 0.0 && SCIPisLT(scip, bvub[j] * SCIPvarGetLbLocal(zvub[j]) + dvub[j], SCIPvarGetLbLocal(var))) ) 5990 bvub[j], SCIPvarGetName(zvub[j]), SCIPvarGetLbLocal(zvub[j]), SCIPvarGetUbLocal(zvub[j]), dvub[j]); 6011 SCIPdebugMessage(" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n", 6012 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetUbGlobal(var), rhs); 6016 assert(0 <= SCIPvarGetProbindex(zvub[bestubtype]) && SCIPvarGetProbindex(zvub[bestubtype]) < nbinvars); 6030 SCIPdebugMessage(" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n", 6044 /* calculate scalar which makes all coefficients integral in relative allowed difference in between 6047 SCIP_CALL( SCIPcalcIntegralScalar(binvals, nbinvars, -SCIPepsilon(scip), KNAPSACKRELAX_MAXDELTA, 6051 /* if coefficients cannot be made integral, we have to use a scalar of 1.0 and only round fractional coefficients down */ 6076 SCIPdebugMessage(" -> positive scaled binary variable %+" SCIP_LONGINT_FORMAT "<%s> (unscaled %.15g): not changed (rhs=%.15g)\n", 6086 SCIPdebugMessage(" -> negative scaled binary variable %+" SCIP_LONGINT_FORMAT "<%s> (unscaled %.15g): substituted by (1 - <%s>) (rhs=%.15g)\n", 6111 SCIPdebugMessage(" -> linear constraint <%s> relaxed to knapsack:", cons != NULL ? SCIPconsGetName(cons) : "-"); 6115 SCIPdebugPrintf(" %+" SCIP_LONGINT_FORMAT "<%s>(%.15g)", consvals[i], SCIPvarGetName(consvars[i]), 6119 SCIPdebugPrintf(" <= %" SCIP_LONGINT_FORMAT " (%.15g) [act: %.15g, min: %" SCIP_LONGINT_FORMAT " max: %" SCIP_LONGINT_FORMAT "]\n", 6134 SCIP_CALL( SCIPseparateKnapsackCuts(scip, cons, sepa, consvars, nconsvars, consvals, capacity, sol, usegubs, cutoff, ncuts) ); 6195 SCIP_CALL( SCIPseparateKnapsackCuts(scip, cons, NULL, consdata->vars, consdata->nvars, consdata->weights, 6238 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1, SCIPconsIsTransformed(cons)) ); 6263 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR ) 6350 /* if the clique number is equal to the number of variables we have only cliques with one element, so we don't 6361 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */ 6367 /* if the old clique number was greater than the new one we have to check that before a bigger clique number 6376 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */ 6379 /* if we reached the end in the for loop, it means we have deleted the last element of the clique with 6385 /* if the old clique number was smaller than the new one we have to check the front for an element with 6390 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/ 6393 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */ 6395 /* if we deleted the last element of the clique with biggest index, we have to decrease the clique number */ 6399 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/ 6414 /* if the clique number is equal to the number of variables we have only cliques with one element, so we don't 6425 consdata->negcliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */ 6431 /* if the old clique number was greater than the new one we have to check that, before a bigger clique number 6440 consdata->negcliquepartitioned = FALSE; /* recalculate the negated clique partition after a coefficient was removed */ 6443 /* if we reached the end in the for loop, it means we have deleted the last element of the clique with 6449 /* if the old clique number was smaller than the new one we have to check the front for an element with 6454 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/ 6457 consdata->negcliquepartitioned = FALSE; /* recalculate the negated clique partition after a coefficient was removed */ 6459 /* if we deleted the last element of the clique with biggest index, we have to decrease the clique number */ 6463 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/ 6468 /* otherwise if the old clique number is equal to the new one the cliquepartition should be ok */ 6579 SCIPsortPtrPtrLongIntInt((void**)consdata->vars, (void**)consdata->eventdata, consdata->weights, 6580 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars); 6627 /* variables var1 and var2 are opposite: subtract smaller weight from larger weight, reduce capacity, 6634 SCIP_CALL( delCoefPos(scip, cons, v) ); /* this does not affect var2, because var2 stands before var1 */ 6644 SCIP_CALL( delCoefPos(scip, cons, v) ); /* this does not affect var2, because var2 stands before var1 */ 6655 assert(prev == 0 || ((prev > 0) && (SCIPvarIsActive(consdata->vars[prev - 1]) || SCIPvarGetStatus(consdata->vars[prev - 1]) == SCIP_VARSTATUS_NEGATED)) ); 6656 /* either that was the last pair or both, the negated and "normal" variable in front doesn't match var1, so the order is irrelevant */ 6657 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 != SCIPvarGetNegatedVar(consdata->vars[prev - 1])) ) 6687 /** in case the knapsack constraint is independent of every else, solve the knapsack problem (exactly) and apply the 6698 { 6716 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot 6717 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are 6736 /* check if we can apply the dual reduction; this can be done if the knapsack has the only locks on this constraint; 6776 SCIPdebugMessage("the knapsack constraint <%s> is independent to rest of the problem\n", SCIPconsGetName(cons)); 6780 SCIP_CALL( SCIPsolveKnapsackExactly(scip, consdata->nvars, consdata->weights, profits, consdata->capacity, 6793 SCIPdebugMessage("variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n", 6828 /** check if the knapsack constraint is parallel to objective function; if so update the cutoff bound and avoid that the 6860 /* check if the knapsack constraints has the same number of variables as the objective function and if the initial 6866 /* There are no variables in the ojective function and in the constraint. Thus, the constraint is redundant. Since we 6892 /* if a variable has a zero objective coefficient the knapsack constraint is not parallel to objective function */ 6931 /* avoid that the knapsack constraint enters the LP since it is parallel to the objective function */ 6937 /* increase the cutoff bound value by an epsilon to ensue that solution with the value of the cutoff bound are 6942 SCIPdebugMessage("constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n", 6953 /* in case the cutoff bound is worse then currently known one we avoid additionaly enforcement and 6964 /* avoid that the knapsack constraint enters the LP since it is parallel to the objective function */ 6970 SCIPdebugMessage("constraint <%s> is parallel to objective function and provids a lower bound <%g>\n", 6980 /** sort the variables and weights w.r.t. the clique partition; thereby ensure the current order of the variables when a 6981 * weight of one variable is greater or equal another weight and both variables are in the same cliques */ 6990 ) 7064 /* to reach the goal that all variables of each clique will be standing next to each other we will initialize the 7065 * starting pointers for each clique by adding the number of each clique to the last clique starting pointer 7066 * e.g. clique1 has 4 elements and clique2 has 3 elements the the starting pointer for clique1 will be the pointer 7067 * to vars[0], the starting pointer to clique2 will be the pointer to vars[4] and to clique3 it will be 7114 ) 7152 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */ 7158 /* we need a merged constraint cause without it the negated clique information could be invalid */ 7180 * - minweightsum = sum_{negated cliques C} ( sum(wi : i \in C) - W(C) ), where W(C) is the maximal weight of C 7223 /* for summing up the minimum active weights due to cliques we have to omit the biggest weights of each 7224 * clique, we can only skip this clique if this variables is not fixed to zero, otherwise we have to fix all 7269 /* we found a fixed variable to zero so all other variables in this negated clique have to be fixed to one */ 7278 SCIPdebugMessage(" -> fixing variable <%s> to 1, due to negated clique information\n", SCIPvarGetName(myvars[v])); 7279 SCIP_CALL( SCIPinferBinvarCons(scip, myvars[v], TRUE, cons, SCIPvarGetIndex(myvars[i]), &infeasible, &tightened) ); 7312 /* reset local minweightsum for clique because all fixed to one variables are now counted in consdata->onesweightsum */ 7323 SCIPdebugMessage("knapsack constraint <%s> has minimum weight sum of <%" SCIP_LONGINT_FORMAT ">\n", 7358 SCIPdebugMessage(" -> fixing variable <%s> to 1, due to negated clique information\n", SCIPvarGetName(myvars[i])); 7389 SCIPdebugMessage(" -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT ", capacity: %" SCIP_LONGINT_FORMAT ", minimum weight sum: %" SCIP_LONGINT_FORMAT " \n", 7396 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 7398 /* start conflict analysis with the fixed-to-one variables, add only as many as need to exceed the capacity */ 7428 /* if the sum of all weights of fixed variables to one plus the minimalweightsum (minimal weight which is already 7429 * used in this knapsack due to negated cliques) plus any weight minus the second largest weight in this cliques 7430 * exceeds the capacity the variables have to be fixed to zero (these variables should only be variables in the 7445 if( consdata->onesweightsum + minweightsum + myweights[cliquestartposs[c]] - secondmaxweights[c] > consdata->capacity ) 7454 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, cliquestartposs[c], &infeasible, &tightened) ); 7470 /* check, if weights of fixed variables already exceed knapsack capacity, this can only happen if 'usenegatedclique' 7471 * is FALSE, or 'nnegcliques == nvars', otherwise the stronger condition above should have led to a cutoff 7475 SCIPdebugMessage(" -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT ", capacity: %" SCIP_LONGINT_FORMAT " \n", 7482 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 7484 /* start conflict analysis with the fixed-to-one variables, add only as many as need to exceed the capacity */ 7508 /* if all weights of fixed variables to one plus any weight exceeds the capacity the variables have to be fixed 7519 SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[i], FALSE, cons, i, &infeasible, &tightened) ); 7533 /* if the remaining (potentially unfixed) variables would fit all into the knapsack, the knapsack is now redundant */ 7534 if( !SCIPconsIsModifiable(cons) && consdata->weightsum - zerosweightsum <= consdata->capacity ) 7536 SCIPdebugMessage(" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT ", zerosweightsum=%" SCIP_LONGINT_FORMAT ", capacity=%" SCIP_LONGINT_FORMAT "\n", 7547 /** all but one variable fit into the knapsack constraint, so we can upgrade this constraint to an logicor constraint 7570 /* if the knapsack constraint consists only of two variables, we can upgrade it to a set-packing constraint */ 7573 SCIPdebugMessage("upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons)); 7575 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars, 7581 /* if the knapsack constraint consists of at least three variables, we can upgrade it to a logicor constraint 7588 SCIPdebugMessage("upgrading knapsack constraint <%s> to a logicor constraint", SCIPconsGetName(cons)); 7593 SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consvars, 7614 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them 7616 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique 7619 * i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too 7626 SCIP_Longint frontsum, /**< sum of front items which fit if we try to take from the first till the last */ 7662 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 7679 /* all rear items are redundant, because leaving one item in front and incl. of splitpos out the rear itmes always 7715 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 7723 /* rear items can only be redundant, when the sum is smaller to the weight at splitpos and all rear items would 7724 * always fit into the knapsack, therefor the item directly after splitpos needs to be smaller than the one at 7738 SCIP_CALL( SCIPcalcCliquePartition(scip, &(consdata->vars[splitpos+1]), len, clqpart, &nclq) ); 7760 /* all rear items are redundant due to clique information, if maxactduetoclq is smaller than the weight before, 7761 * so delete them and create for all clique the corresponding clique constraints and update the capacity 7771 SCIPdebugMessage("Found redundant variables in constraint <%s> due to clique information.\n", SCIPconsGetName(cons)); 7788 /* we found a real clique so extract this constraint, because we do not know who this information generated so */ 7794 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), capacity, c); 7846 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 7865 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them 7867 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique 7870 * i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too 7881 ) 7918 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */ 7933 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */ 7991 /* if all items fit, then delete the whole constraint but create clique constraints which led to this 8003 SCIPdebugMessage("Found redundant constraint <%s> due to clique information.\n", SCIPconsGetName(cons)); 8022 /* we found a real clique so extract this constraint, because we do not know who this information generated so */ 8028 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), capacity, c); 8061 /** divides weights by their greatest common divisor and divides capacity by the same value, rounding down the result */ 8091 assert(SCIPvarGetUbLocal(consdata->vars[i]) > 0.5); /* all fixed variables should have been removed */ 8098 SCIPdebugMessage("knapsack constraint <%s>: dividing weights by %" SCIP_LONGINT_FORMAT "\n", SCIPconsGetName(cons), gcd); 8117 * 1. a) check if all two pairs exceed the capacity, then we can upgrade this constraint to a set-packing constraint 8118 * b) check if all but the smallest weight fit into the knapsack, then we can upgrade this constraint to a logicor 8121 * 2. check if besides big coefficients, that fit only by itself, for a certain amount of variables all combination of 8124 * +219y1 + 180y2 + 74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3 8126 * 3. use the duality between a^Tx <= capacity <=> a^T~x >= weightsum - capacity to tighten weights, e.g. 8142 ) 8190 SCIPdebugMessage("upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons)); 8192 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars, 8208 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */ 8217 /* early termination, if the pair with biggest coeffcients together does not exceed the dualcapacity */ 8228 * the following is done without looking at the dualcapacity; it is enough to check whether for a certain amount of 8235 * +219y1 + 180y_2 +74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3 8287 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 8297 /* a certain amount of small variables exceed the capacity, so check if this holds for all combinations of the 8313 /* if the same amount but with the smallest possible weights also exceed the capacity, it holds for all 8345 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 8358 /* if the follwoing assert fails we have either a redundant constraint or a set-packing constraint, this should 8367 * either choose x1, or all other variables (weightsum of x2 to x10 is 979 above), so we can tighten this 8408 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 8461 /* we have a dual-knapsack constraint were we either need to choose one variable out of a subset (big 8468 * 3x1 + 3x2 + 2x3 + 2x4 + 2x5 + 2x6 + x7 <= 12 <=> 3~x1 + 3~x2 + 2~x3 + 2~x4 + 2~x5 + 2~x6 + ~x7 >= 3 8534 * e.g. 9x1 + 9x2 + 6x3 + 4x4 + 4x5 + 4x6 <= 27 <=> 9~x1 + 9~x2 + 6~x3 + 4~x4 + 4~x5 + 4~x6 >= 9 8561 /* we found redundant variables, which does not influence the feasibility of any integral solution, e.g. 8580 /* for performance reasons we do not update the capacity(, i.e. reduce it by reductionsum) and directly 8591 * e.g. 9x1 + 9x2 + 6x3 + 6x4 + 4x5 + 4x6 <= 29 <=> 9~x1 + 9~x2 + 6~x3 + 6~x4 + 4~x5 + 4~x6 >= 9 8596 if( weights[v] > 1 || (weights[startv] > (SCIP_Longint)nvars - v) || (startv > 0 && weights[0] == (SCIP_Longint)nvars - v + 1) ) 8610 /* adjust middle sized coefficients, which when choosing also one small coefficients exceed the 8641 newcap = ((SCIP_Longint)startv - 1) * newweight + ((SCIP_Longint)v - startv) * (newweight - 1) + ((SCIP_Longint)nvars - v); 8650 assert(weights[v] == 1 && (weights[startv] == (SCIP_Longint)nvars - v) && (startv == 0 || weights[0] == (SCIP_Longint)nvars - v + 1)); 8655 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 8665 /* check if all rear items have the same weight as the last one, so we cannot tighten the constraint further */ 8713 /* dualcapacity is odd, we can set the middle weights to dualcapacity but therefor need to multiply all 8757 /* @todo loop for "k" can be extended, same coefficient when determine next sumcoef can be left out */ 8787 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 5], weights[nvars - 2] + weights[nvars - 3]); 8791 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 4], weights[nvars - 1] + weights[nvars - 2] + weights[nvars - 3]); 8798 /* tighten next coefficients that, pair with the current small coefficient, exceed the dualcapacity */ 8806 /* @todo check for further reductions, when two times the minweight exceeds the dualcapacity */ 8838 /* now check if a combination of small coefficients allows us to tighten big coefficients further */ 8902 /* dualcapacity is odd, we can set the middle weights to dualcapacity but therefor need to multiply all 8961 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal 8986 /** fixes variables with weights bigger than the capacity and delete redundant constraints, also sort weights */ 8995 { 9085 * 1. use the duality between a^Tx <= capacity <=> -a^T~x <= capacity - weightsum to tighten weights, e.g. 9093 * 2. if variables in a constraint do not affect the (in-)feasibility of the constraint, we can delte them, e.g. 9097 * 3. Tries to use gcd information an all but one weight to change this not-included weight and normalize the 9100 * 9x1 + 6x2 + 6x3 + 5x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => 3x1 + 2x2 + 2x3 + 2x4 <= 4 => 4x1 + 2x2 + 2x3 + 2x4 <= 4 9207 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal weight 9230 /* determine coefficients as big as the capacity, these we do not need to take into account when calculating the 9249 /* calculate greatest common divisor over all integer and binary variables and determine the candidate where we might 9270 /* if the greatest commmon divisor has become 1, we might have found the possible coefficient to change or we 9281 /* if both first coefficients have a gcd of 1, both are candidates for the coefficient change */ 9312 /* we should have found one coefficient, that led to a gcd of 1, otherwise we could normalize the constraint 9352 SCIPdebugMessage("gcd = %" SCIP_LONGINT_FORMAT ", rest = %" SCIP_LONGINT_FORMAT ", restweight = %" SCIP_LONGINT_FORMAT "; possible new weight of variable <%s> %" SCIP_LONGINT_FORMAT ", possible new capacity %" SCIP_LONGINT_FORMAT ", offset of coefficients as big as capacity %d\n", gcd, rest, restweight, SCIPvarGetName(vars[candpos]), newweight, consdata->capacity - rest, offsetv); 9354 /* must not change weights and capacity if one variable would be removed and we have a big coefficient, 9355 * e.g., 11x1 + 6x2 + 6x3 + 5x4 <= 11 => gcd = 6, offsetv = 1 => newweight = 0, but we would lose x1 = 1 => x4 = 0 9404 SCIPdebugMessage("we did %d coefficient changes and %d side changes on constraint %s when applying one round of the gcd algorithm\n", *nchgcoefs - oldnchgcoefs, *nchgsides - oldnchgsides, SCIPconsGetName(cons)); 9411 /** deletes all fixed variables from knapsack constraint, and replaces variables with binary representatives */ 9420 { 9498 /* @todo maybe resolve the problem that the eliminating of the multi-aggregation leads to a non-knapsack 9499 * constraint (converting into a linear constraint), for example the multi-aggregation consist of a non-binary 9500 * variable or due to resolving now their are non-integral coefficients or a non-integral capacity 9508 * 1b) If repvar is a negated variable of a multi-aggregated variable weight * repvar should be replaced by 9509 * weight - weight * (a_1*y_1 + ... + a_n*y_n + c), for better further use here we switch the sign of weight 9512 * 2a) weight * a_i < 0 than we add -weight * a_i * y_i_neg to the constraint and adjust the capacity through 9516 * 3b) If repvar was negated we need to subtract weight * (c - 1) from capacity(note we switched the sign of 9536 SCIPerrorMessage("try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst); 9551 SCIPerrorMessage("try to resolve a multi-aggregation with a non-binary variable <%s>\n", aggrvars[i]); 9556 SCIPerrorMessage("try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[i]); 9559 /* if the new coefficient is smaller than zero, we need to add the negated variable instead and adjust the capacity */ 9564 SCIP_CALL( addCoef(scip, cons, negvar, (SCIP_Longint)(SCIPfloor(scip, -weight * aggrscalars[i] + 0.5))) ); 9569 SCIP_CALL( addCoef(scip, cons, aggrvars[i], (SCIP_Longint)(SCIPfloor(scip, weight * aggrscalars[i] + 0.5))) ); 9575 /* adjust the capacity with the aggregation constant and if necessary the extra weight through the negation */ 9608 /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have to 9662 /* we explicitly construct the complete implication graph where the knapsack variables are involved; 9667 SCIPdebugMessage("memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n", 9698 /** applies rule (3) of the weight tightening procedure, which can lift other variables into the knapsack: 9703 * - the weight of the variable or its negation (depending on v) can be increased as long as it has the same 9720 int* firstidxs[2]; /* first index in zeroitems for each binary variable/value pair, or zero for empty list */ 9723 int* nextidxs; /* next index in zeroitems for the same binary variable, or zero for end of list */ 9766 if( (!consdata->cliquepartitioned && nvars > MAX_USECLIQUES_SIZE) || consdata->ncliques > MAX_USECLIQUES_SIZE ) 9775 /* we have to consider all integral variables since even integer and implicit integer variables can have binary bounds */ 9796 /* next if conditions should normally not be true, because it means that presolving has created more binary variables 9797 * than binary + integer variables existed at the presolving initialization method, but for example if you would 9808 BMSclearMemoryArray(&(conshdlrdata->ints1[oldsize]), conshdlrdata->ints1size - oldsize); /*lint !e866*/ 9818 BMSclearMemoryArray(&(conshdlrdata->ints2[oldsize]), conshdlrdata->ints2size - oldsize); /*lint !e866*/ 9827 SCIP_CALL( SCIPreallocMemoryArray(scip, &conshdlrdata->longints1, conshdlrdata->longints1size) ); 9828 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize); /*lint !e866*/ 9837 SCIP_CALL( SCIPreallocMemoryArray(scip, &conshdlrdata->longints2, conshdlrdata->longints2size) ); 9838 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize); /*lint !e866*/ 9869 /* next if conditions should normally not be true, because it means that presolving has created more binary variables 9870 * than binary + integer variables existed at the presolving initialization method, but for example if you would 9881 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize); /*lint !e866*/ 9891 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize); /*lint !e866*/ 10034 /* calculate the clique partition and the maximal sum of weights using the clique information */ 10040 /* next if condition should normally not be true, because it means that presolving has created more binary variables 10041 * in one constraint than binary + integer variables existed in the whole problem at the presolving initialization 10042 * method, but for example if you would transform all integers into their binary representation then it maybe happens 10052 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize); /*lint !e866*/ 10086 /* next if condition should normally not be true, because it means that presolving has created more binary variables 10087 * in one constraint than binary + integer variables existed in the whole problem at the presolving initialization 10088 * method, but for example if you would transform all integers into their binary representation then it maybe happens 10098 BMSclearMemoryArray(&conshdlrdata->bools4[oldsize], conshdlrdata->bools4size - oldsize); /*lint !e866*/ 10109 /* for each binary variable xi and each fixing v, calculate the cliqueweightsum and update the weight of the 10110 * variable in the knapsack (this is sequence-dependent because the new or modified weights have to be 10136 /* mark the items that are implied to zero by setting the current variable to the current value */ 10184 SCIPdebugMessage("knapsack constraint <%s>: adding lifted item %" SCIP_LONGINT_FORMAT "<%s>\n", 10227 /* if new items were added, multiple entries of the same variable are possible and we have to clean up the constraint */ 10247 * - wi and capacity can be changed to have the same redundancy effect and the same results for 10248 * fixing xi to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation 10252 * (2) increase weights from front to back(sortation is necessary) if there is no space left for another weight 10253 * - determine the four(can be adjusted) minimal weightsums of the knapsack, i.e. in increasing order 10254 * weights[nvars - 1], weights[nvars - 2], MIN(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), 10255 * MIN(MAX(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), weights[nvars - 4]), note that there 10257 * - check if summing up a minimal weightsum with a big weight exceeds the capacity, then we can increase the big 10268 * - weights wi, i in C, and capacity can be changed to have the same redundancy effect and the same results for 10269 * fixing xi, i in C, to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation 10274 * This rule has to add the used cliques in order to ensure they are enforced - otherwise, the reduction might 10280 * - the weight of the variable or its negation (depending on v) can be increased as long as it has the same 10327 assert(consdata->weightsum > consdata->capacity); /* otherwise, the constraint is redundant */ 10357 SCIPdebugMessage("knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT ", capacity from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10388 /* @todo loop for "k" can be extended, same coefficient when determine next sumcoef can be left out */ 10445 /* tighten next coefficients that, paired with the current small coefficient, exceed the capacity */ 10452 SCIPdebugMessage("in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10485 SCIPdebugMessage("in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10498 /* apply rule (2) (don't apply, if the knapsack has too many items for applying this costly method) */ 10501 if( conshdlrdata->disaggregation && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->nvars >= 2 && 10503 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) ) 10519 SCIPdebugMessage("upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons)); 10521 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, SCIPconsGetName(cons), pos, consdata->vars, 10553 SCIPdebugMessage("Disaggregating knapsack constraint <%s> due to clique information.\n", SCIPconsGetName(cons)); 10579 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), consdata->capacity, c); 10601 else if( consdata->nvars <= MAX_USECLIQUES_SIZE || (consdata->cliquepartitioned && consdata->ncliques <= MAX_USECLIQUES_SIZE) ) 10673 SCIPdebugMessage("knapsack constraint <%s>: weights of clique %d (maxweight: %" SCIP_LONGINT_FORMAT ") can be tightened: cliqueweightsum=%" SCIP_LONGINT_FORMAT ", capacity=%" SCIP_LONGINT_FORMAT " -> delta: %" SCIP_LONGINT_FORMAT "\n", 10703 /* check if our clique information results out of this knapsack constraint and if so check if we would loose the clique information */ 10730 SCIPdebugMessage(" -> change capacity from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT " (forceclique:%u)\n", 10742 SCIPdebugMessage(" -> change weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10749 /* if before the weight update at least one pair of weights did not fit into the knapsack and now fits, 10750 * we have to make sure, the clique is enforced - the clique might have been constructed partially from 10751 * this constraint, and by reducing the weights, this clique information is not contained anymore in the 10764 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), consdata->capacity, i); 10824 SCIPdebugMessage("knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10827 consdataChgWeight(consdata, i, consdata->capacity); /* this does not destroy the weight order! */ 10847 SCIPdebugMessage("knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n", 10848 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[consdata->nvars-1]), weight, consdata->capacity); 10850 consdataChgWeight(consdata, consdata->nvars-1, consdata->capacity); /* this does not destroy the weight order! */ 10937 /* determine maximal weights for all negated cliques and calculate minimal weightsum due to negated cliques */ 10940 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques); 10957 /* free capacity is the rest of not used capacity if the smallest amount of weights due to negated cliques are used */ 10961 SCIPdebugMessage("Try to add negated cliques in knapsack constraint handler for constraint %s; capacity = %" SCIP_LONGINT_FORMAT ", minactivity(due to neg. cliques) = %" SCIP_LONGINT_FORMAT ", freecapacity = %" SCIP_LONGINT_FORMAT ".\n", 10972 /* if we would take the biggest weight instead of another what would we gain, take weight[i] instead of 10978 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[w]; 10990 SCIPsortDownLongPtrInt(gainweights,(void**) poscliquevars, gaincliquepartition, nposcliquevars); 11003 /* taking bigger weights make the knapsack redundant so we will create cliques, only take items which are not 11005 for( w = v + 1; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && gainweights[w] + lastweight > freecapacity; ++w ) 11035 /* try to replace the last item in the clique by a different item to obtain a slightly different clique */ 11036 for( ++w; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && beforelastweight + gainweights[w] > freecapacity; ++w ) 11136 /* calculate minimal activity due to negated cliques, and determine second maximal weight in each clique */ 11165 /* free capacity is the rest of not used capacity if the smallest amount of weights due to negated cliques are used */ 11169 SCIPdebugMessage("Try to add cliques in knapsack constraint handler for constraint %s; capacity = %" SCIP_LONGINT_FORMAT ", minactivity(due to neg. cliques) = %" SCIP_LONGINT_FORMAT ", freecapacity = %" SCIP_LONGINT_FORMAT ".\n", 11172 /* create negated cliques out of negated cliques, if we do not take the smallest weight of a cliques ... */ 11225 /* try to replace the last item in the clique by a different item to obtain a slightly different clique */ 11248 for( i = 1; i < nvars && consdata->weights[i-1] + consdata->weights[i] > consdata->capacity; ++i ) 11270 /* try to replace the last item in the clique by a different item to obtain a slightly different clique */ 11272 for( i = ncliquevars; i < nvars && cliqueminweight + consdata->weights[i] > consdata->capacity; ++i ) 11310 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables and the 11392 hashval = (consdata->nvars << 29) + (minidx << 22) + (mididx << 11) + maxidx + maxabsval; /*lint !e701*/ 11397 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint 11408 ) 11466 /* constraint found: create a new constraint with same coefficients and best left and right hand side; 11497 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */ 11532 { 11557 for( c = (consdata0->presolvedtiming == SCIP_PRESOLTIMING_EXHAUSTIVE ? firstchange : 0); c < chkind; ++c ) 11577 if( consdata0->presolvedtiming >= SCIP_PRESOLTIMING_EXHAUSTIVE && consdata1->presolvedtiming >= SCIP_PRESOLTIMING_EXHAUSTIVE ) /*lint !e574*/ 11607 SCIPdebugMessage("preprocess knapsack constraint pair <%s> and <%s>\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1)); 11644 /* if cons1 is possible contained in cons0 (consdata0->weights[v0] / quotient) must be greater equals consdata1->weights[v1] */ 11645 if( iscons1incons0contained && SCIPisLT(scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) ) 11651 /* if cons0 is possible contained in cons1 (consdata0->weight[v0] / quotient) must be less equals consdata1->weight[v1] */ 11652 else if( iscons0incons1contained && SCIPisGT(scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) ) 11680 /* neither one constraint was contained in another or we checked all variables of one constraint against the 11690 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */ 11701 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */ 11746 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 11748 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 11768 /* if the right hand side is non-infinite, we have to negate all variables with negative coefficient; 11769 * otherwise, we have to negate all variables with positive coefficient and multiply the row with -1 11803 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 11831 SCIPdebugMessage("upgrading constraint <%s> to knapsack constraint\n", SCIPconsGetName(cons)); 11833 /* create the knapsack constraint (an automatically upgraded constraint is always unmodifiable) */ 11835 SCIP_CALL( createNormalizedKnapsack(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, lhs, rhs, 11866 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 11897 /* all variables which are of integral type can be binary; this can be checked via the method SCIPvarIsBinary(var) */ 11907 /** deinitialization method of constraint handler (called before transformed problem is freed) */ 11926 /** presolving initialization method of constraint handler (called when presolving is about to begin) */ 11940 /* all variables which are of integral type can be binary; this can be checked via the method SCIPvarIsBinary(var) */ 11974 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */ 11988 /* since we are not allowed to detect infeasibility in the exitpre stage, we dont give an infeasible pointer */ 12018 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 12090 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 12091 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 12094 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 12099 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 12149 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot) 12177 SCIP_CALL( separateCons(scip, conss[i], NULL, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) ); 12218 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot) 12238 SCIP_CALL( separateCons(scip, conss[i], sol, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) ); 12269 maxncuts = (SCIPgetDepth(scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts); 12368 /* do not propagate constraints with multi-aggregated variables, which should only happen in probing mode, 12378 SCIP_CALL( propagateCons(scip, conss[i], &cutoff, &redundant, &nfixedvars, conshdlrdata->negatedclique) ); 12422 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0); 12472 SCIP_CALL( propagateCons(scip, cons, &cutoff, &redundant, nfixedvars, (presoltiming & SCIP_PRESOLTIMING_MEDIUM)) ); 12493 /* check again for redundancy (applyFixings() might have decreased weightsum due to fixed-to-zero vars) */ 12496 SCIPdebugMessage(" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT ", capacity=%" SCIP_LONGINT_FORMAT "\n", 12508 SCIP_CALL( simplifyInequalities(scip, cons, nfixedvars, ndelconss, nchgcoefs, nchgsides, naddconss, &cutoff) ); 12525 SCIP_CALL( tightenWeights(scip, cons, presoltiming, nchgcoefs, nchgsides, naddconss, ndelconss, &cutoff) ); 12531 if( conshdlrdata->dualpresolving && SCIPallowDualReds(scip) && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 ) 12533 /* in case the knapsack constraints is independent of everything else, solve the knapsack and apply the 12551 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 ) 12553 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */ 12554 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &cutoff, ndelconss) ); 12557 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) ) 12562 if( !cutoff && firstchange < nconss && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 ) 12577 npaircomparisons += ((SCIPconsGetData(cons)->presolvedtiming < SCIP_PRESOLTIMING_EXHAUSTIVE) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange)); 12583 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) ) 12585 if( ((SCIP_Real) (*ndelconss - oldndelconss) + ((SCIP_Real) (*nchgsides - oldnchgsides))/2.0 + 12586 ((SCIP_Real) (*nchgcoefs - oldnchgcoefs))/10.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS ) 12635 /* according to negated cliques the minweightsum and all variables which are fixed to one which led to a fixing of 12636 * another negated clique variable to one, the inferinfo was chosen to be the negative of the position in the 12643 /* locate the inference variable and calculate the capacity that has to be used up to conclude infervar == 0; 12644 * inferinfo stores the position of the inference variable (but maybe the variables were resorted) 12657 /* add fixed-to-one variables up to the point, that their weight plus the weight of the conflict variable exceeds 12675 /* NOTE: It might be the case that capsum < consdata->capacity. This is due the fact that the fixing of the variable 12676 * to zero can included negated clique information. A negated clique means, that at most one of the clique 12677 * variables can be zero. These information can be used to compute a minimum activity of the constraint and 12680 * Even if capsum < consdata->capacity we still reported a complete reason since the minimum activity is based 12681 * on global variable bounds. It might even be the case that we reported to many variables which are fixed to 12717 { 12777 -SCIPinfinity(scip), (SCIP_Real) SCIPgetCapacityKnapsack(sourcescip, sourcecons), varmap, consmap, 12778 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) ); 12857 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "expected '<= ' at begin of '%s'\n", str); 12870 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "error parsing capacity from '%s'\n", str); 12876 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 12908 /** constraint method of constraint handler which returns the number of variables (if possible) */ 12917 (*nvars) = consdata->nvars; 12963 case SCIP_EVENTTYPE_VARFIXED: /* the variable should be removed from the constraint in presolving */ 12973 case SCIP_EVENTTYPE_IMPLADDED: /* further preprocessing might be possible due to additional implications */ 13007 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr), EVENTHDLR_NAME, EVENTHDLR_DESC, 13039 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolKnapsack,CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 13041 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropKnapsack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 13044 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpKnapsack, consSepasolKnapsack, CONSHDLR_SEPAFREQ, 13050 /* include the linear constraint to knapsack constraint upgrade in the linear constraint handler */ 13051 SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdKnapsack, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) ); 13057 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)", 13061 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts", 13109 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?", 13113 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?", 13121 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 13149 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 13151 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 13174 SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, weights, capacity) ); 13177 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 13184 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 13185 * method SCIPcreateConsKnapsack(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 13189 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 13304 /** gets the array of variables in the knapsack constraint; the user must not modify this array! */ 13325 /** gets the array of weights in the knapsack constraint; the user must not modify this array! */ 13394 /** returns the linear relaxation of the given knapsack constraint; may return NULL if no LP row was yet created;
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed) Definition: scip.c:22777 void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len) void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var) Definition: var.c:16861 SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type) Definition: scip.c:15853 Definition: cons_knapsack.c:226 static SCIP_RETCODE GUBsetFree(SCIP *scip, SCIP_GUBSET **gubset) Definition: cons_knapsack.c:1972 Definition: type_result.h:33 SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name) Definition: scip.c:5878 static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss) Definition: cons_knapsack.c:6513 Definition: type_result.h:37 static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff) Definition: cons_knapsack.c:6555 SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans))) Definition: scip.c:5588 static SCIP_RETCODE getCover(SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool *found, SCIP_Bool modtransused, int *ntightened, SCIP_Bool *fractional) Definition: cons_knapsack.c:2347 static SCIP_RETCODE GUBsetCalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques, SCIP_Real *solvals) Definition: cons_knapsack.c:2091 SCIP_Real SCIPgetDualfarkasKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13378 static SCIP_DECL_CONSRESPROP(consRespropKnapsack) Definition: cons_knapsack.c:12615 Definition: struct_scip.h:53 static SCIP_RETCODE GUBsetMoveVar(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons) Definition: cons_knapsack.c:1791 static SCIP_RETCODE addNegatedCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs) Definition: cons_knapsack.c:10870 SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element) Definition: misc.c:1567 static SCIP_DECL_HASHKEYVAL(hashKeyValKnapsackcons) Definition: cons_knapsack.c:11364 void SCIPsortDownLongPtrPtrIntInt(SCIP_Longint *longarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len) static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:6169 SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41920 SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing) Definition: var.c:17420 SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop))) Definition: scip.c:5634 SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy) Definition: scip.c:30877 SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa) Definition: scip.c:5246 Definition: type_result.h:49 static SCIP_RETCODE getLiftingSequenceGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_Real *solvals, SCIP_Longint *weights, int *varsC1, int *varsC2, int *varsF, int *varsR, int nvarsC1, int nvarsC2, int nvarsF, int nvarsR, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int *ngubconsGC1, int *ngubconsGC2, int *ngubconsGFC1, int *ngubconsGR, int *ngubconscapexceed, int *maxgubvarssize) Definition: cons_knapsack.c:2885 Definition: type_set.h:35 static SCIP_RETCODE separateSequLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_SOL *sol, SCIP_GUBSET *gubset, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:4767 SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy))) Definition: scip.c:5334 SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound) Definition: scip.c:38589 SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut) Definition: scip.c:30859 SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13238 static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) Definition: cons_knapsack.c:6211 static SCIP_DECL_CONSINITLP(consInitlpKnapsack) Definition: cons_knapsack.c:12108 SCIP_RETCODE SCIPseparateRelaxedKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:5741 Definition: struct_var.h:196 SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound) Definition: scip.c:12302 SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars) Definition: scip.c:17196 SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip) Definition: scip.c:24320 static SCIP_RETCODE checkParallelObjective(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata) Definition: cons_knapsack.c:6839 static SCIP_RETCODE separateSupLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_Longint mincoverweight, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:5168 static SCIP_RETCODE dualWeightsTightening(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss) Definition: cons_knapsack.c:8142 static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_knapsack.c:698 SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars))) Definition: scip.c:5818 static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique) Definition: cons_knapsack.c:7114 SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_setppc.c:8948 Definition: cons_knapsack.c:236 Definition: cons_knapsack.c:228 SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata) Definition: scip.c:7778 Definition: cons_knapsack.c:245 static SCIP_RETCODE insertZerolist(SCIP *scip, int **liftcands, int *nliftcands, int **firstidxs, SCIP_Longint **zeroweightsums, int **zeroitems, int **nextidxs, int *zeroitemssize, int *nzeroitems, int probindex, SCIP_Bool value, int knapsackidx, SCIP_Longint knapsackweight, SCIP_Bool *memlimitreached) Definition: cons_knapsack.c:9630 static SCIP_RETCODE separateSequLiftedExtendedWeightInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *feassetvars, int *nonfeassetvars, int nfeassetvars, int nnonfeassetvars, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:5001 SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse))) Definition: scip.c:5795 static void consdataChgWeight(SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight) Definition: cons_knapsack.c:748 SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13333 static void getPartitionNoncovervars(SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR) Definition: cons_knapsack.c:2751 SCIP_RETCODE SCIPseparateKnapsackCuts(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_SOL *sol, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:5524 SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15737 SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) Definition: scip.c:34983 Definition: type_result.h:40 SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity) Definition: cons_knapsack.c:13198 void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len) Definition: struct_sepa.h:36 SCIP_RETCODE SCIPincludeConshdlrKnapsack(SCIP *scip) Definition: cons_knapsack.c:13000 SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate) Definition: scip.c:25147 SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file) Definition: scip.c:26237 SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible) Definition: scip.c:30967 Constraint handler for the set partitioning / packing / covering constraints . SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13312 SCIP_Real SCIPgetDualsolKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13354 SCIP_RETCODE SCIPsolveKnapsackApproximately(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval) Definition: cons_knapsack.c:1492 static SCIP_RETCODE GUBsetGetCliquePartition(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals) Definition: cons_knapsack.c:2250 SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree))) Definition: scip.c:5359 SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr) Definition: misc.c:1480 Definition: cons_knapsack.c:235 SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success) Definition: scip.c:24720 static SCIP_DECL_CONSDELETE(consDeleteKnapsack) Definition: cons_knapsack.c:12051 Definition: struct_sol.h:50 SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit))) Definition: scip.c:5383 SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3547 SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27658 Definition: cons_knapsack.c:255 SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3573 SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr) Definition: scip.c:16156 static SCIP_RETCODE GUBconsFree(SCIP *scip, SCIP_GUBCONS **gubcons) Definition: cons_knapsack.c:1699 static SCIP_DECL_HASHGETKEY(hashGetKeyKnapsackcons) Definition: cons_knapsack.c:11311 static SCIP_RETCODE GUBconsDelVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var, int gubvarsidx) Definition: cons_knapsack.c:1754 SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr) Definition: cons.c:3917 static SCIP_RETCODE stableSort(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique) Definition: cons_knapsack.c:6990 SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos) Definition: scip.c:36622 static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated) Definition: cons_knapsack.c:849 SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated) Definition: scip.c:17233 static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff) Definition: cons_knapsack.c:9420 SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_knapsack.c:13130 Constraint handler for knapsack constraints of the form , x binary and . SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars) Definition: var.c:11541 void SCIPsortDownPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) static SCIP_DECL_HASHKEYEQ(hashKeyEqKnapsackcons) Definition: cons_knapsack.c:11321 static SCIP_DECL_CONSEXITSOL(consExitsolKnapsack) Definition: cons_knapsack.c:12027 static void getPartitionCovervars(SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) Definition: cons_knapsack.c:2621 Definition: type_result.h:35 static SCIP_RETCODE simplifyInequalities(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss, SCIP_Bool *cutoff) Definition: cons_knapsack.c:9112 Definition: struct_cons.h:36 SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19526 void SCIPsortIntInt(int *intarray1, int *intarray2, int len) SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1) Definition: scip.c:25300 Definition: struct_cons.h:116 static SCIP_DECL_CONSDELVARS(consDelvarsKnapsack) Definition: cons_knapsack.c:12717 static void GUBsetSwapVars(SCIP *scip, SCIP_GUBSET *gubset, int var1, int var2) Definition: cons_knapsack.c:1882 Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo... SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15859 static SCIP_RETCODE sequentialUpAndDownLiftingGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int ngubconscapexceed, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs, int maxgubvarssize) Definition: cons_knapsack.c:3904 static SCIP_DECL_CONSINITPRE(consInitpreKnapsack) Definition: cons_knapsack.c:11935 SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar) Definition: scip.c:17163 SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming) Definition: scip.c:5527 Definition: cons_knapsack.c:223 Definition: type_result.h:36 SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41907 SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20669 SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre))) Definition: scip.c:5503 #define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum) Definition: scip.h:20562 static SCIP_Longint safeAddMinweightsGUB(SCIP_Longint val1, SCIP_Longint val2) Definition: cons_knapsack.c:3833 SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated) Definition: var.c:11573 Definition: type_set.h:41 Definition: type_retcode.h:33 SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals) Definition: scip.c:35020 SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success) Definition: cons_knapsack.c:949 SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming) Definition: scip.c:5292 SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata) Definition: scip.c:5192 SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics) Definition: var.c:10742 static SCIP_DECL_CONSENFOPS(consEnfopsKnapsack) Definition: cons_knapsack.c:12313 SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element) Definition: misc.c:1719 Definition: type_result.h:42 static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff) Definition: cons_knapsack.c:814 SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27629 SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41946 void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) Definition: cons_knapsack.c:13217 static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:786 static SCIP_Bool checkSolveKnapsack(SCIP *scip, int nitems, SCIP_Longint *transweights, SCIP_Real *transprofits, int *items, SCIP_Longint *weights, SCIP_Real *solvals, SCIP_Bool modtransused) Definition: cons_knapsack.c:1563 static SCIP_RETCODE getLiftingSequence(SCIP *scip, SCIP_Real *solvals, SCIP_Longint *weights, int *varsF, int *varsC2, int *varsR, int nvarsF, int nvarsC2, int nvarsR) Definition: cons_knapsack.c:2799 Definition: type_retcode.h:34 void SCIPsortDownRealLongRealInt(SCIP_Real *realarray1, SCIP_Longint *longarray, SCIP_Real *realarray3, int *intarray, int len) SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars) Definition: scip.c:17116 static SCIP_DECL_CONSPRESOL(consPresolKnapsack) Definition: cons_knapsack.c:12401 static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool transformed) Definition: cons_knapsack.c:535 static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, int pos) Definition: cons_knapsack.c:6293 SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELVARS((*consdelvars))) Definition: scip.c:5749 SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20193 public data structures and miscellaneous methods SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre))) Definition: scip.c:5479 SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: scip.c:24772 static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen) Definition: cons_knapsack.c:3405 static SCIP_RETCODE addCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs) Definition: cons_knapsack.c:11078 SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs) Definition: scip.c:21810 SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce) Definition: scip.c:25097 static SCIP_RETCODE superadditiveUpLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Real *liftcoefs, SCIP_Real *cutact) Definition: cons_knapsack.c:4636 SCIP_RETCODE SCIPcalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques) Definition: scip.c:21859 Definition: type_message.h:43 Definition: type_var.h:46 SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27811 static SCIP_DECL_CONSEXITPRE(consExitpreKnapsack) Definition: cons_knapsack.c:11983 Definition: struct_lp.h:189 SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var) Definition: scip.c:17329 static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity) Definition: cons_knapsack.c:573 static SCIP_RETCODE GUBsetCreate(SCIP *scip, SCIP_GUBSET **gubset, int nvars, SCIP_Longint *weights, SCIP_Longint capacity) Definition: cons_knapsack.c:1922 static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_knapsack.c:481 Definition: type_var.h:45 SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp))) Definition: scip.c:5611 Definition: cons_knapsack.c:227 SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var) Definition: var.c:16849 static void normalizeWeights(SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) Definition: cons_knapsack.c:8070 Constraint handler for linear constraints in their most general form, . void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key) Definition: misc.c:1627 static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs) Definition: cons_knapsack.c:8995 static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss) Definition: cons_knapsack.c:7630 static SCIP_RETCODE changePartitionCovervars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) Definition: cons_knapsack.c:2670 void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...) Definition: scip.c:1298 static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_knapsack.c:508 static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted) Definition: cons_knapsack.c:6698 SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36668 SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete))) Definition: scip.c:5565 static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss) Definition: cons_knapsack.c:7558 static SCIP_DECL_CONSSEPALP(consSepalpKnapsack) Definition: cons_knapsack.c:12125 Definition: type_set.h:34 static SCIP_RETCODE sequentialUpAndDownLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *varsM1, int *varsM2, int *varsF, int *varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs) Definition: cons_knapsack.c:3455 static SCIP_RETCODE createNormalizedKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_knapsack.c:11726 static SCIP_DECL_LINCONSUPGD(linconsUpgdKnapsack) Definition: cons_knapsack.c:11821 Definition: struct_misc.h:80 static SCIP_RETCODE GUBconsCreate(SCIP *scip, SCIP_GUBCONS **gubcons) Definition: cons_knapsack.c:1678 static SCIP_RETCODE GUBsetCheck(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars) Definition: cons_knapsack.c:2006 SCIP_RETCODE SCIPchgCapacityKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity) Definition: cons_knapsack.c:13262 SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint))) Definition: scip.c:5772 static SCIP_DECL_CONSGETNVARS(consGetNVarsKnapsack) Definition: cons_knapsack.c:12917 SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27834 SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate) Definition: scip.c:25072 void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...) Definition: scip.c:1281 static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss) Definition: cons_knapsack.c:11408 SCIP_Longint SCIPconshdlrGetNCutsFound(SCIP_CONSHDLR *conshdlr) Definition: cons.c:4521 int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13291 static SCIP_Bool checkMinweightidx(SCIP_Longint *weights, SCIP_Longint capacity, int *covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j) Definition: cons_knapsack.c:2578 #define SCIPduplicateBufferArray(scip, ptr, source, num) Definition: scip.h:20593 SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol))) Definition: scip.c:5455 Definition: cons_knapsack.c:225 SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41933 SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19453 static SCIP_DECL_CONSGETVARS(consGetVarsKnapsack) Definition: cons_knapsack.c:12895 Definition: cons_knapsack.c:237 static SCIP_RETCODE GUBconsAddVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var) Definition: cons_knapsack.c:1719 SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial) Definition: scip.c:25047 static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_knapsack.c:467 SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20299 static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique) Definition: cons_knapsack.c:423 SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27600 Definition: struct_implics.h:64 SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file) Definition: scip.c:28334 static SCIP_DECL_CONSSEPASOL(consSepasolKnapsack) Definition: cons_knapsack.c:12199 SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41959 static SCIP_RETCODE tightenWeights(SCIP *scip, SCIP_CONS *cons, SCIP_PRESOLTIMING presoltiming, int *nchgcoefs, int *nchgsides, int *naddconss, int *ndelconss, SCIP_Bool *cutoff) Definition: cons_knapsack.c:10296 #define SCIPduplicateBlockMemoryArray(scip, ptr, source, num) Definition: scip.h:20568 SCIP_RETCODE SCIPcalcNegatedCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques) Definition: scip.c:22008 static SCIP_DECL_CONSENFOLP(consEnfolpKnapsack) Definition: cons_knapsack.c:12260 static SCIP_RETCODE removeZeroWeights(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:6489 Definition: cons_knapsack.c:224 Definition: type_retcode.h:45 SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success) Definition: misc.c:7375 Definition: type_set.h:42 static SCIP_RETCODE makeCoverMinimal(SCIP *scip, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused) Definition: cons_knapsack.c:5282 SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit))) Definition: scip.c:5407 SCIP_ROW * SCIPgetRowKnapsack(SCIP *scip, SCIP_CONS *cons) Definition: cons_knapsack.c:13404 SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup) Definition: scip.c:19399 SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname) Definition: cons_linear.c:16047 void SCIPsortPtrPtrLongIntInt(void **ptrarray1, void **ptrarray2, SCIP_Longint *longarray, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var) Definition: scip.c:24573 void SCIPsortDownRealIntLong(SCIP_Real *realarray, int *intarray, SCIP_Longint *longarray, int len) static SCIP_RETCODE getFeasibleSet(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts) Definition: cons_knapsack.c:5425 static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss) Definition: cons_knapsack.c:11532 static SCIP_RETCODE eventdataCreate(SCIP *scip, SCIP_EVENTDATA **eventdata, SCIP_CONSDATA *consdata, SCIP_Longint weight) Definition: cons_knapsack.c:291 static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_knapsack.c:453 Definition: type_retcode.h:35 static SCIP_RETCODE eventdataFree(SCIP *scip, SCIP_EVENTDATA **eventdata) Definition: cons_knapsack.c:309 static SCIP_RETCODE detectRedundantVars(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss) Definition: cons_knapsack.c:7881 Definition: type_retcode.h:43 Definition: objbranchrule.h:33 SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3629 SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars))) Definition: scip.c:5841 SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_logicor.c:5111 SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val) Definition: scip.c:27864 static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyKnapsack) Definition: cons_knapsack.c:11859 SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2) Definition: misc.c:7083 static SCIP_RETCODE changePartitionFeasiblesetvars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2) Definition: cons_knapsack.c:2710 static SCIP_RETCODE tightenWeightsLift(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff) Definition: cons_knapsack.c:9716 SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid) Definition: cons_linear.c:16311 void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata) Definition: cons.c:3927 void SCIPsortDownLongPtr(SCIP_Longint *longarray, void **ptrarray, int len) Definition: type_result.h:39 Definition: struct_event.h:185 static void computeMinweightsGUB(SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen) Definition: cons_knapsack.c:3852 void SCIPsortDownLongPtrInt(SCIP_Longint *longarray, void **ptrarray, int *intarray, int len) |