cons_knapsack.c
Go to the documentation of this file.
27 * @brief Constraint handler for knapsack constraints of the form \f$a^T x \le b\f$, x binary and \f$a \ge 0\f$.
35/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
83#define CONSHDLR_ENFOPRIORITY -600000 /**< priority of the constraint handler for constraint enforcing */
84#define CONSHDLR_CHECKPRIORITY -600000 /**< priority of the constraint handler for checking feasibility */
85#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
86#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
87#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
89#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
90#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
91#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
92#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
105#define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */
107#define MAX_USECLIQUES_SIZE 1000 /**< maximal number of items in knapsack where clique information is used */
108#define MAX_ZEROITEMS_SIZE 10000 /**< maximal number of items to store in the zero list in preprocessing */
110#define KNAPSACKRELAX_MAXDELTA 0.1 /**< maximal allowed rounding distance for scaling in knapsack relaxation */
111#define KNAPSACKRELAX_MAXDNOM 1000LL /**< maximal allowed denominator in knapsack rational relaxation */
112#define KNAPSACKRELAX_MAXSCALE 1000.0 /**< maximal allowed scaling factor in knapsack rational relaxation */
114#define DEFAULT_SEPACARDFREQ 1 /**< multiplier on separation frequency, how often knapsack cuts are separated */
116#define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of separation rounds in the root node (-1: unlimited) */
118#define DEFAULT_MAXSEPACUTSROOT 200 /**< maximal number of cuts separated per separation round in the root node */
119#define DEFAULT_MAXCARDBOUNDDIST 0.0 /**< maximal relative distance from current node's dual bound to primal bound compared
121#define DEFAULT_DISAGGREGATION TRUE /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
123#define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in solving process */
125#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for knapsack relaxation */
126#define USESUPADDLIFT FALSE /**< should lifted minimal cover inequalities using superadditive up-lifting be separated in addition */
128#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
131#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
133#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise
136#define DEFAULT_DETECTCUTOFFBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
139#define DEFAULT_DETECTLOWERBOUND TRUE /**< should presolving try to detect constraints parallel to the objective
142#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 /**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
143#define MAXCOVERSIZEITERLEWI 1000 /**< maximal size for which LEWI are iteratively separated by reducing the feasible set */
147#define GUBSPLITGNC1GUBS FALSE /**< should GNC1 GUB conss without F vars be split into GOC1 and GR GUB conss? */
148#define DEFAULT_CLQPARTUPDATEFAC 1.5 /**< factor on the growth of global cliques to decide when to update a previous
150#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE /**< should clique partition information be updated when old partition seems outdated? */
151#define MAXNCLIQUEVARSCOMP 1000000 /**< limit on number of pairwise comparisons in clique partitioning algorithm */
153#define DEFAULT_UPGDCARDINALITY FALSE /**< if TRUE then try to update knapsack constraints to cardinality constraints */
155#define DEFAULT_COPYTYPEDCONS FALSE /**< should knapsack constraints be copied as knapsack instead of linear? */
157/* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
170 SCIP_Longint* longints1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
172 SCIP_Longint* longints2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
174 SCIP_Bool* bools1; /**< cleared memory array, all entries are set to zero in initpre, if you use this
176 SCIP_Bool* bools2; /**< cleared memory array, all entries are set to zero in initpre, if you use this
178 SCIP_Bool* bools3; /**< cleared memory array, all entries are set to zero in initpre, if you use this
180 SCIP_Bool* bools4; /**< cleared memory array, all entries are set to zero in initpre, if you use this
182 SCIP_Real* reals1; /**< cleared memory array, all entries are set to zero in consinit, if you use this
193 int* probtoidxmap; /**< cleared memory array with default values -1; used for clique partitions */
196 SCIP_Real maxcardbounddist; /**< maximal relative distance from current node's dual bound to primal bound compared
198 int sepacardfreq; /**< multiplier on separation frequency, how often knapsack cuts are separated */
202 int maxsepacutsroot; /**< maximal number of cuts separated per separation round in the root node */
203 SCIP_Bool disaggregation; /**< should disaggregation of knapsack constraints be allowed in preprocessing? */
204 SCIP_Bool simplifyinequalities;/**< should presolving try to cancel down or delete coefficients in inequalities */
206 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
207 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
210 SCIP_Bool detectcutoffbound; /**< should presolving try to detect constraints parallel to the objective
213 SCIP_Bool detectlowerbound; /**< should presolving try to detect constraints parallel to the objective
216 SCIP_Bool updatecliquepartitions; /**< should clique partition information be updated when old partition seems outdated? */
217 SCIP_Real cliqueextractfactor;/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
218 SCIP_Real clqpartupdatefac; /**< factor on the growth of global cliques to decide when to update a previous
221 SCIP_Bool upgdcardinality; /**< if TRUE then try to update knapsack constraints to cardinality constraints */
222 SCIP_Bool upgradedcard; /**< whether we have already upgraded knapsack constraints to cardinality constraints */
224 SCIP_Bool copytypedcons; /**< should knapsack constraints be copied as knapsack instead of linear? */
242 int ncliqueslastnegpart;/**< number of global cliques the last time a negated clique partition was computed */
243 int ncliqueslastpart; /**< number of global cliques the last time a clique partition was computed */
247 unsigned int presolvedtiming:5; /**< max level in which the knapsack constraint is already presolved */
252 unsigned int cliquesadded:1; /**< were the cliques of the knapsack already added to clique table? */
283};
291 GUBCONSSTATUS_BELONGSTOSET_GF = 1, /** all GUB variables are in noncovervars F (and noncovervars R) */
293 GUBCONSSTATUS_BELONGSTOSET_GNC1 = 3, /** some GUB variables are in covervars C1, others in noncovervars R or F */
295};
385 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
404 /* sort all items with same weight according to their variable index, used for hash value for fast pairwise comparison of all constraints */
414 /* sort all corresponding parts of arrays for which the weights are equal by using the variable index */
426 /* we need to make sure that our clique numbers of our normal clique will be in increasing order without gaps */
433 /* if the clique number in the normal clique at position pos is greater than the last found clique number the
444 /* we need to make sure that our clique numbers of our negated clique will be in increasing order without gaps */
451 /* if the clique number in the negated clique at position pos is greater than the last found clique number the
488 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
492 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
496 SCIP_CALL( SCIPcalcCliquePartition(scip, consdata->vars, consdata->nvars, &conshdlrdata->probtoidxmap, &conshdlrdata->probtoidxmapsize,
502 /* rerun eventually if number of global cliques increased considerably since last negated partition */
504 && SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
508 SCIP_CALL( SCIPcalcNegatedCliquePartition(scip, consdata->vars, consdata->nvars, &conshdlrdata->probtoidxmap, &conshdlrdata->probtoidxmapsize,
615 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->varssize, newsize) );
618 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdata, consdata->varssize, newsize) );
619 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->cliquepartition, consdata->varssize, newsize) );
620 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->negcliquepartition, consdata->varssize, newsize) );
698 if( SCIPisConsCompressionEnabled(scip) && SCIPvarGetLbGlobal(vars[v]) > SCIPvarGetUbGlobal(vars[v]) - 0.5 )
754 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
760 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
765 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cliquepartition, (*consdata)->nvars) );
766 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->negcliquepartition, (*consdata)->nvars) );
894 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) );
926 SCIPdebugMsg(scip, "adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT "): ",
946 /* skip deactivated, redundant, or local linear constraints (the NLP does not allow for local rows at the moment) */
979/** checks knapsack constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
985 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
997 SCIPdebugMsg(scip, "checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1010 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1018 /* sum separately over normal and huge weight contributions in order to reduce numerical cancellation */
1075 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well
1082 * @todo If only the objective is relevant, it is easy to change the code to use only one slice with O(capacity) space.
1083 * There are recursive methods (see the book by Kellerer et al.) that require O(capacity) space, but it remains
1085 * Dembo and Hammer (see Kellerer et al. Section 5.1.3, page 126) found a method that relies on a fast probing method.
1394 /* If the greedy solution is optimal by comparing to the LP solution, we take this solution. This happens if:
1396 * - the greedy solution has an objective that is at least the LP value rounded down in case that all profits are integer, too. */
1397 greedyupperbound = greedysolvalue + myprofits[j] * (SCIP_Real) (capacity - greedysolweight)/((SCIP_Real) myweights[j]);
1443 assert(sizeof(size_t) >= sizeof(int)); /*lint !e506*/ /* no following conversion should be messed up */
1445 /* this condition checks whether we will try to allocate a correct number of bytes and do not have an overflow, while
1448 if( intcap < 0 || (intcap > 0 && (((size_t)nmyitems) > (SIZE_MAX / (size_t)intcap / sizeof(*optvalues)) || ((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues) > ((size_t)INT_MAX) )) ) /*lint !e571*/
1450 SCIPdebugMsg(scip, "Too much memory (%lu) would be consumed.\n", (unsigned long) (((size_t)nmyitems) * ((size_t)intcap) * sizeof(*optvalues))); /*lint !e571*/
1472 /* we memorize at each step the current minimal weight to later on know which value in our optvalues matrix is valid;
1473 * each value entries of the j-th row of optvalues is valid if the index is >= allcurrminweight[j], otherwise it is
1474 * invalid; a second possibility would be to clear the whole optvalues, which should be more expensive than storing
1505 /* if index d < current minweight then optvalues[IDX(j-1,d)] is not initialized, i.e. should be 0 */
1527 /* early termination: if current best value reaches the LP upper bound, we have found an optimal solution */
1543 /* items after lastitem were not processed due to early termination; they are not in the solution */
1558 /* collect solution items; the first condition means that no further item can fit anymore, but this does */
1606/** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's
1607 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not
1653 /* partially sort indices such that all elements that are larger than the break item appear first */
1654 SCIPselectWeightedDownRealLongRealInt(tempsort, weights, profits, items, realweights, (SCIP_Real)capacity, nitems, &criticalindex);
1836 /* delete variable from GUB by swapping it replacing in by the last variable in the GUB constraint */
1841 /* decrease space allocated for the GUB constraint, if the last GUBCONSGROWVALUE+1 array entries are now empty */
1857/** moves variable from current GUB constraint to a different existing (nonempty) GUB constraint */
1882 SCIPdebugMsg(scip, " moving variable<%s> from GUB<%d> to GUB<%d>\n", SCIPvarGetName(vars[var]), oldgubcons, newgubcons);
1886 /* delete variable from old GUB constraint by replacing it by the last variable of the GUB constraint */
1889 /* in GUB set, update stored index of variable in old GUB constraint for the variable used for replacement;
1898 assert(gubset->gubconss[newgubcons]->gubvars[gubset->gubconss[newgubcons]->ngubvars-1] == var);
1900 /* in GUB set, update stored index of GUB of moved variable and stored index of variable in this GUB constraint */
1915 /* if empty GUB was not the last one in GUB set data structure, replace it by last GUB constraint */
1921 /* in GUB set, update stored index of GUB constraint for all variable of the GUB constraint used for replacement;
1934 /* variable should be at given new position, unless new GUB constraint replaced empty old GUB constraint
1988/** initializes partition of knapsack variables into nonoverlapping trivial GUB constraints (GUB with one variable) */
2029 /* already updated status of variable in GUB constraint if it exceeds the capacity of the knapsack */
2031 (*gubset)->gubconss[(*gubset)->gubconssidx[i]]->gubvarsstatus[(*gubset)->gubvarsidx[i]] = GUBVARSTATUS_CAPACITYEXCEEDED;
2090 /* checks for all knapsack vars consistency of stored index of associated gubcons and corresponding index in gubvars */
2098 SCIPdebugMsg(scip, " var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2135 /* @todo: in case we used also negated cliques for the GUB partition, this assert has to be changed */
2147 * afterwards the output array contains one value for each variable, such that two variables got the same value iff they
2149 * the first variable is always assigned to clique 0, and a variable can only be assigned to clique i if at least one of
2151 * note: in contrast to SCIPcalcCliquePartition(), variables with LP value 1 are put into trivial cliques (with one
2152 * variable) and for the remaining variables, a partition with a small number of cliques is constructed
2158 SCIP_VAR**const vars, /**< binary variables in the clique from which at most one can be set to 1 */
2161 int*const ncliques, /**< pointer to store number of cliques actually contained in the partition */
2207 /* ignore variables with LP value 1 (will be assigned to trivial GUBs at the end) and sort remaining variables
2222 /* remaining variables are put to the front of varseq array and will be sorted by their number of cliques */
2230 /* sort variables with LP value less than 1 by nondecreasing order of the number of cliques they are in */
2291 /* if we had too many variables fill up the cliquepartition and put each variable in a separate clique */
2312/** constructs sophisticated partition of knapsack variables into non-overlapping GUBs; current partition uses trivial GUBs */
2341 SCIP_CALL( GUBsetCalcCliquePartition(scip, vars, nvars, cliquepartition, &ncliques, solvals) );
2364 /* corresponding GUB constraint in GUB set data structure was already constructed (as initial trivial GUB);
2365 * note: no assert for gubconssidx, because it can changed due to deleting empty GUBs in GUBsetMoveVar()
2378 /* move variable to GUB constraint defined by clique partition; index of this GUB constraint is given by the
2382 assert(newgubconsidx != currentgubconsidx); /* because initially every variable is in a different GUB */
2406/** 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$
2407 * 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
2424 SCIP_Bool modtransused, /**< should modified transformed separation problem be used to find cover */
2426 SCIP_Bool* fractional /**< pointer to store whether the LP sol for knapsack vars is fractional */
2522 /* sets whether the LP solution x* for the knapsack variables is fractional; if it is not fractional we stop
2591 /* solves (modified) transformed knapsack problem approximately by solving the LP-relaxation of the (modified)
2597 SCIP_CALL( SCIPsolveKnapsackApproximately(scip, nitems, transweights, transprofits, transcapacity, items,
2599 /*assert(checkSolveKnapsack(scip, nitems, transweights, transprofits, items, weights, solvals, modtransused));*/
2669 /* checks if all variables before index j cannot be removed, i.e. i cannot be the next minweightidx */
2681/** 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$,
2682 * 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$
2730/** changes given partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one and two (if possible) variables from
2772/** changes given partition (C_1,C_2) of feasible set C, if |C1| = 1, by moving one variable from C2 to C1 */
2810/** 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$
2811 * and \f$F \cap R = \emptyset\f$; chooses partition as follows \f$R = \{ j \in N \setminus C : x^*_j = 0 \}\f$ and
2859/** sorts variables in F, C_2, and R according to the second level lifting sequence that will be used in the sequential
2898 * sequence 1: non-increasing absolute difference between x*_j and the value the variable is fixed to, i.e.
2945/** categorizes GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of the GUBs
2970 int* ngubconscapexceed, /**< pointer to store number of GUBs with only capacity exceeding variables */
3031 * afterwards all GUBs (except GOC1 GUBs, which we do not need to lift) are sorted by a two level lifting sequence.
3034 * GFC1: non-increasing number of variables in F and non-increasing max{x*_k : k in GFC1_j} in case of equality
3053 * furthermore, sort C1 variables as needed for initializing the minweight table (non-increasing a_j).
3154 /* stores GUBs of group GC1 (GOC1+GNC1) and part of the GUBs of group GFC1 (GNC1 GUBs) and sorts variables in these GUBs
3173 /* current C1 variable is put to the front of its GUB where C1 part is stored by non-decreasing weigth;
3180 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3188 /* determine the status of the current GUB constraint, GOC1 or GNC1; GUBs involving R variables are split into
3214 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3260 assert(movevarstatus == GUBVARSTATUS_BELONGSTOSET_R || movevarstatus == GUBVARSTATUS_CAPACITYEXCEEDED);
3292 /* stores GUBs of group GC2 (only trivial GUBs); sorting is not required because the C2 variables (which we loop over)
3323 /* stores remaining part of the GUBs of group GFC1 (GF GUBs) and gets GUB sorting keys corresp. to following ordering
3340 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3362 if( solvals[gubset->gubconss[gubconsidx]->gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3376 /* stores GUBs of group GR; sorting is not required because the R variables (which we loop over) are already sorted
3392 /* the GUB was already handled (status set and stored in its group) by another variable of the GUB */
3414 /* update number of GUBs with only capacity exceeding variables (will not be used for lifting) */
3415 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3493 * 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
3497 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in M_2, and
3498 * sequential up-lifting for the variables in R; procedure can be used to strengthen minimal cover inequalities and
3561 /* sets lifting coefficient of variables in M1, sorts variables in M1 such that a_1 <= a_2 <= ... <= a_|M1|
3616 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
3624 * uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} }
3632 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3659 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3672 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3714 * z = max { w : 0 <= w <= |M_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
3748 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3761 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
3809 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
3843 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
3942 * 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
3945 * 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 };
4050 /* gets GOC1 and GNC1 GUBs, sets lifting coefficient of variables in C1 and calculates activity of the current
4080 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4083 /* initialize the minweight tables, defined as: for i = 1,...,m with m = |I| and w = 0,...,|gubconsGC1|;
4097 /* initialize finished table; note that variables in GOC1 GUBs (includes C1 and capacity exceeding variables)
4099 * 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
4135 * 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
4171 * we can directly initialize minweights instead of computing it from finished and unfinished (which would be more time
4205 /* gets sum of weights of variables fixed to one, i.e. sum of weights of C2 variables GC2 GUBs */
4228 /* GNC1 GUB: update unfinished table (remove current GUB, i.e., remove min weight of C1 vars in GUB) and
4238 /* get number of C1 variables of current GNC1 GUB and put them into array of variables in GUB that
4246 /* update unfinished table by removing current GNC1 GUB, i.e, remove C1 variable with minimal weight
4247 * unfinished[w] = MAX{unfinished[w], unfinished[w+1] - weight}, "weight" is the minimal weight of current GUB
4269 /* GF GUB: no update of unfinished table (and minweight table) required because GF GUBs have no C1 variables and
4281 /* compute lifting coefficient of F and R variables in GNC1 and GF GUBs (C1 vars have already liftcoef 1) */
4307 * sets z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i} } = liftrhs,
4315 * binary search to find z = max {w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - fixedonesweight - a_{j_i}}
4319 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4359 * and finished and minweight table can be updated easily as only C1 variables need to be considered;
4368 * finished[w] = MIN{finished[w], finished[w-1] + weight}, "weight" is the minimal weight of current GUB
4369 * minweights[w] = MIN{minweights[w], minweights[w-1] + weight}, "weight" is the minimal weight of current GUB
4392 * 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
4400 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + sumliftcoef) );
4403 * note that instead of computing minweight table from updated finished and updated unfinished table again
4404 * (for the lifting coefficient, we had to update unfinished table and compute minweight table), we here
4405 * only need to update the minweight table and the updated finished in the same way (i.e., computing for minweight
4406 * not needed because only finished table changed at this point and the change was "adding" one weight)
4451 /* note: now the unfinished table no longer exists, i.e., it is "0, MAX, MAX, ..." and minweight equals to finished;
4465 liftvar = gubset->gubconss[liftgubconsidx]->gubvars[0]; /* C2 GUBs contain only one variable */
4473 * z = max { w : 0 <= w <= |C_1| + sum_{k=1}^{i-1} alpha_{j_k}, minweights_[w] <= a_0 - fixedonesweight + a_{j_i}}
4489 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4507 /* minweight table and activity of current valid inequality will not change, if alpha_{j_i} = 0 */
4518 * 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
4520 SCIP_CALL( enlargeMinweights(scip, &minweights, &minweightslen, &minweightssize, minweightslen + liftcoef) );
4582 /* uses binary search to find z = max { w : 0 <= w <= liftrhs, minweights_i[w] <= a_0 - a_{j_i} }
4622 /* minweight table and activity of current valid inequality will not change if (sum of alpha_{j_i} in GUB) = 0 */
4699 SCIP_Real* liftcoefs, /**< pointer to store lifting coefficient of vars in knapsack constraint */
4735 /* sets lifting coefficient of variables in C, sorts variables in C such that a_1 >= a_2 >= ... >= a_|C|
4813/** separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information, if wanted, for
4859 /* 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
4864 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4867 assert(nvarsC1 >= 0); /* nvarsC1 > 0 does not always hold, because relaxed knapsack conss may already be violated */
4869 /* changes partition (C_1,C_2) of minimal cover C, if |C1| = 1, by moving one variable from C2 to C1 */
4877 /* gets partition (F,R) of N\C, i.e. F & R = N\C and F cap R = emptyset; chooses partition as follows
4881 getPartitionNoncovervars(scip, solvals, nonmincovervars, nnonmincovervars, varsF, varsR, &nvarsF, &nvarsR);
4888 /* sorts variables in F, C_2, R according to the second level lifting sequence that will be used in the sequential
4891 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsC2, varsR, nvarsF, nvarsC2, nvarsR) );
4897 * 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
4901 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in C_2 and sequential
4904 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsC1, varsC2,
4938 /* categorizies GUBs of knapsack GUB partion into GOC1, GNC1, GF, GC2, and GR and computes a lifting sequence of
4941 SCIP_CALL( getLiftingSequenceGUB(scip, gubset, solvals, weights, varsC1, varsC2, varsF, varsR, nvarsC1,
4942 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4950 * 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
4952 * 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 },
4958 SCIP_CALL( sequentialUpAndDownLiftingGUB(scip, gubset, vars, nconstightened, weights, capacity, solvals, gubconsGC1,
4980 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
4981 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
4987 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
4988 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4993 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
4996 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5049/** separates lifted extended weight inequalities using sequential up- and down-lifting for given knapsack problem */
5093 /* 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
5098 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5101 /* changes partition (T_1,T_2) of feasible set T, if |T1| = 0, by moving one variable from T2 to T1 */
5104 SCIP_CALL( changePartitionFeasiblesetvars(scip, weights, varsT1, varsT2, &nvarsT1, &nvarsT2) );
5109 /* gets partition (F,R) of N\T, i.e. F & R = N\T and F cap R = emptyset; chooses partition as follows
5113 getPartitionNoncovervars(scip, solvals, nonfeassetvars, nnonfeassetvars, varsF, varsR, &nvarsF, &nvarsR);
5117 /* sorts variables in F, T_2, and R according to the second level lifting sequence that will be used in the sequential
5118 * lifting procedure (the variable removed last from the initial cover does not have to be lifted first, therefore it
5121 SCIP_CALL( getLiftingSequence(scip, solvals, weights, varsF, varsT2, varsR, nvarsF, nvarsT2, nvarsR) );
5127 * 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
5131 * uses sequential up-lifting for the variables in F, sequential down-lifting for the variable in T_2 and sequential
5134 SCIP_CALL( sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5147 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5148 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5154 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_ewseq_%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5155 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5160 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5163 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5216/** separates lifted minimal cover inequalities using superadditive up-lifting for given knapsack problem */
5259 SCIP_CALL( superadditiveUpLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, mincovervars,
5274 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPconsGetName(cons), SCIPconshdlrGetNCutsFound(SCIPconsGetHdlr(cons)));
5275 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)liftrhs,
5281 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_mcsup%" SCIP_LONGINT_FORMAT "", SCIPsepaGetName(sepa), SCIPsepaGetNCutsFound(sepa));
5282 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &row, sepa, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5287 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, name, -SCIPinfinity(scip), (SCIP_Real)liftrhs, FALSE, FALSE, TRUE) );
5290 /* adds all variables in the knapsack constraint with calculated lifting coefficient to the cut */
5302 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[nonmincovervars[j]], realliftcoefs[nonmincovervars[j]]) );
5326/** converts given cover C to a minimal cover by removing variables in the reverse order in which the variables were chosen
5327 * 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
5328 * C and in the order of non-increasing (1 - x*_j), if the modified transformed separation problem was used to find C;
5364 /* allocates temporary memory; we need two arrays for the keypairs in order to be able to free them in the correct
5371 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5372 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5373 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5419 assert(checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5473/** converts given initial cover C_init to a feasible set by removing variables in the reverse order in which
5476 * non-increasing (1 - x*_j), if modified transformed separation problem was used to find C_init.
5477 * separates lifted extended weight inequalities using sequential up- and down-lifting for this feasible set
5525 * such that (1 - x*_1)/a_1 >= ... >= (1 - x*_|C|)/a_|C|, if trans separation problem was used to find C
5526 * such that (1 - x*_1) >= ... >= (1 - x*_|C|), if modified trans separation problem was used to find C
5527 * note that all variables with x*_j = 1 are in the end of the sorted C, so they will be removed last from C
5547 /* removes variables from C_init and separates lifted extended weight inequalities using sequential up- and down-lifting;
5564 SCIP_CALL( separateSequLiftedExtendedWeightInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals,
5641 SCIPdebugMsgPrint(scip, "%+" SCIP_LONGINT_FORMAT "<%s>(%g)", weights[i], SCIPvarGetName(vars[i]), solvals[i]);
5647 /* LMCI1 (lifted minimal cover inequalities using sequential up- and down-lifting) using GUB information
5669 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5688 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5689 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5691 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5694 /* only separate with GUB information if we have at least one nontrivial GUB (with more than one variable) */
5697 /* separates lifted minimal cover inequalities using sequential up- and down-lifting and GUB information */
5698 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5703 /* separates lifted minimal cover inequalities using sequential up- and down-lifting, but do not use trivial
5706 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5728 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5739 /* converts initial cover C_init to a minimal cover C by removing variables in the reverse order in which the
5740 * variables were chosen to be in C_init; note that variables with x*_j = 1 will be removed last
5742 SCIP_CALL( makeCoverMinimal(scip, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5746 SCIP_CALL( separateSequLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5753 SCIP_CALL( separateSupLiftedMinimalCoverInequality(scip, cons, sepa, vars, nvars, ntightened, weights, capacity,
5754 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5770 SCIP_CALL( getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5778 /* converts initial cover C_init to a feasible set by removing variables in the reverse order in which
5779 * they were chosen to be in C_init and separates lifted extended weight inequalities using sequential
5782 SCIP_CALL( getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5796/* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */
5803 SCIP_Real* knapvals, /**< coefficients of the variables in the continuous knapsack constraint */
5804 SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */
5836 SCIPdebugMsg(scip, "separate linear constraint <%s> relaxed to knapsack\n", cons != NULL ? SCIPconsGetName(cons) : "-");
5841 /* all variables which are of integral type can be potentially of binary type; this can be checked via the method SCIPvarIsBinary(var) */
5872 /* increase array size to avoid an endless loop in the next block; this might happen if continuous variables
5877 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, conshdlrdata->reals1size, 1) );
5884 /* next if condition should normally not be true, because it means that presolving has created more binary
5885 * variables than binary + integer variables existed at the constraint initialization method, but for example if you would
5893 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->reals1, oldsize, conshdlrdata->reals1size) );
5894 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize); /*lint !e866 */
5912 * - a_j < 0: x_j = lb or x_j = b*z + d with variable lower bound b*z + d with binary variable z
5913 * - a_j > 0: x_j = ub or x_j = b*z + d with variable upper bound b*z + d with binary variable z
5950 SCIPdebugMsg(scip, " -> binary variable %+.15g<%s>(%.15g)\n", valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var));
5978 if( (bvlb[j] >= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetLbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) ||
5979 (bvlb[j] <= 0.0 && SCIPisGT(scip, bvlb[j] * SCIPvarGetUbLocal(zvlb[j]) + dvlb[j], SCIPvarGetUbLocal(var))) )
5984 bvlb[j], SCIPvarGetName(zvlb[j]), SCIPvarGetLbLocal(zvlb[j]), SCIPvarGetUbLocal(zvlb[j]), dvlb[j]);
6005 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
6006 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetLbGlobal(var), rhs);
6010 assert(0 <= SCIPvarGetProbindex(zvlb[bestlbtype]) && SCIPvarGetProbindex(zvlb[bestlbtype]) < nbinvars);
6024 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6058 if( (bvub[j] >= 0.0 && SCIPisLT(scip, bvub[j] * SCIPvarGetUbLocal(zvub[j]) + dvub[j], SCIPvarGetLbLocal(var))) ||
6059 (bvub[j] <= 0.0 && SCIPisLT(scip, bvub[j] * SCIPvarGetLbLocal(zvub[j]) + dvub[j], SCIPvarGetLbLocal(var))) )
6064 bvub[j], SCIPvarGetName(zvub[j]), SCIPvarGetLbLocal(zvub[j]), SCIPvarGetUbLocal(zvub[j]), dvub[j]);
6085 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6086 valscale * knapvals[i], SCIPvarGetName(var), SCIPgetSolVal(scip, sol, var), SCIPvarGetUbGlobal(var), rhs);
6090 assert(0 <= SCIPvarGetProbindex(zvub[bestubtype]) && SCIPvarGetProbindex(zvub[bestubtype]) < nbinvars);
6104 SCIPdebugMsg(scip, " -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6118 /* calculate scalar which makes all coefficients integral in relative allowed difference in between
6121 SCIP_CALL( SCIPcalcIntegralScalar(binvals, nbinvars, -SCIPepsilon(scip), KNAPSACKRELAX_MAXDELTA,
6125 /* if coefficients cannot be made integral, we have to use a scalar of 1.0 and only round fractional coefficients down */
6150 SCIPdebugMsg(scip, " -> positive scaled binary variable %+" SCIP_LONGINT_FORMAT "<%s> (unscaled %.15g): not changed (rhs=%.15g)\n",
6160 SCIPdebugMsg(scip, " -> negative scaled binary variable %+" SCIP_LONGINT_FORMAT "<%s> (unscaled %.15g): substituted by (1 - <%s>) (rhs=%.15g)\n",
6185 SCIPdebugMsg(scip, " -> linear constraint <%s> relaxed to knapsack:", cons != NULL ? SCIPconsGetName(cons) : "-");
6189 SCIPdebugMsgPrint(scip, " %+" SCIP_LONGINT_FORMAT "<%s>(%.15g)", consvals[i], SCIPvarGetName(consvars[i]),
6193 SCIPdebugMsgPrint(scip, " <= %" SCIP_LONGINT_FORMAT " (%.15g) [act: %.15g, min: %" SCIP_LONGINT_FORMAT " max: %" SCIP_LONGINT_FORMAT "]\n",
6208 SCIP_CALL( SCIPseparateKnapsackCuts(scip, cons, sepa, consvars, nconsvars, consvals, capacity, sol, usegubs, cutoff, ncuts) );
6269 SCIP_CALL( SCIPseparateKnapsackCuts(scip, cons, NULL, consdata->vars, consdata->nvars, consdata->weights,
6312 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1, SCIPconsIsTransformed(cons)) );
6335 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
6416 /* if the clique number is equal to the number of variables we have only cliques with one element, so we don't
6427 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */
6433 /* if the old clique number was greater than the new one we have to check that before a bigger clique number
6442 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */
6445 /* if we reached the end in the for loop, it means we have deleted the last element of the clique with
6451 /* if the old clique number was smaller than the new one we have to check the front for an element with
6456 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/
6459 consdata->cliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */
6461 /* if we deleted the last element of the clique with biggest index, we have to decrease the clique number */
6465 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/
6480 /* if the clique number is equal to the number of variables we have only cliques with one element, so we don't
6491 consdata->negcliquepartitioned = FALSE; /* recalculate the clique partition after a coefficient was removed */
6497 /* if the old clique number was greater than the new one we have to check that, before a bigger clique number
6506 consdata->negcliquepartitioned = FALSE; /* recalculate the negated clique partition after a coefficient was removed */
6509 /* if we reached the end in the for loop, it means we have deleted the last element of the clique with
6515 /* if the old clique number was smaller than the new one we have to check the front for an element with
6520 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/
6523 consdata->negcliquepartitioned = FALSE; /* recalculate the negated clique partition after a coefficient was removed */
6525 /* if we deleted the last element of the clique with biggest index, we have to decrease the clique number */
6529 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i ); /*lint !e722*/
6534 /* otherwise if the old clique number is equal to the new one the cliquepartition should be ok */
6646 SCIPsortPtrPtrLongIntInt((void**)consdata->vars, (void**)consdata->eventdata, consdata->weights,
6647 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6694 /* variables var1 and var2 are opposite: subtract smaller weight from larger weight, reduce capacity,
6701 SCIP_CALL( delCoefPos(scip, cons, v) ); /* this does not affect var2, because var2 stands before var1 */
6711 SCIP_CALL( delCoefPos(scip, cons, v) ); /* this does not affect var2, because var2 stands before var1 */
6722 assert(prev == 0 || ((prev > 0) && (SCIPvarIsActive(consdata->vars[prev - 1]) || SCIPvarGetStatus(consdata->vars[prev - 1]) == SCIP_VARSTATUS_NEGATED)) );
6723 /* either that was the last pair or both, the negated and "normal" variable in front doesn't match var1, so the order is irrelevant */
6724 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 != SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6754/** in case the knapsack constraint is independent of every else, solve the knapsack problem (exactly) and apply the
6783 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
6784 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
6803 /* check if we can apply the dual reduction; this can be done if the knapsack has the only locks on this constraint;
6844 SCIPdebugMsg(scip, "the knapsack constraint <%s> is independent to rest of the problem\n", SCIPconsGetName(cons));
6848 SCIP_CALL( SCIPsolveKnapsackExactly(scip, consdata->nvars, consdata->weights, profits, consdata->capacity,
6861 SCIPdebugMsg(scip, "variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6874 SCIPdebugMsg(scip, "variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6896/** check if the knapsack constraint is parallel to objective function; if so update the cutoff bound and avoid that the
6928 /* check if the knapsack constraints has the same number of variables as the objective function and if the initial
6934 /* There are no variables in the ojective function and in the constraint. Thus, the constraint is redundant. Since we
6962 /* if a variable has a zero objective coefficient the knapsack constraint is not parallel to objective function */
7001 /* avoid that the knapsack constraint enters the LP since it is parallel to the objective function */
7007 SCIPdebugMsg(scip, "constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7010 /* increase the cutoff bound value by an epsilon to ensue that solution with the value of the cutoff bound are
7015 SCIPdebugMsg(scip, "constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7026 /* in case the cutoff bound is worse then currently known one we avoid additionaly enforcement and
7037 /* avoid that the knapsack constraint enters the LP since it is parallel to the objective function */
7043 SCIPdebugMsg(scip, "constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7053/** sort the variables and weights w.r.t. the clique partition; thereby ensure the current order of the variables when a
7054 * weight of one variable is greater or equal another weight and both variables are in the same cliques */
7137 /* to reach the goal that all variables of each clique will be standing next to each other we will initialize the
7138 * starting pointers for each clique by adding the number of each clique to the last clique starting pointer
7139 * e.g. clique1 has 4 elements and clique2 has 3 elements the the starting pointer for clique1 will be the pointer
7140 * to vars[0], the starting pointer to clique2 will be the pointer to vars[4] and to clique3 it will be
7178/** deletes all fixed variables from knapsack constraint, and replaces variables with binary representatives */
7265 /* @todo maybe resolve the problem that the eliminating of the multi-aggregation leads to a non-knapsack
7266 * constraint (converting into a linear constraint), for example the multi-aggregation consist of a non-binary
7267 * variable or due to resolving now their are non-integral coefficients or a non-integral capacity
7275 * 1b) If repvar is a negated variable of a multi-aggregated variable weight * repvar should be replaced by
7276 * weight - weight * (a_1*y_1 + ... + a_n*y_n + c), for better further use here we switch the sign of weight
7279 * 2a) weight * a_i < 0 than we add -weight * a_i * y_i_neg to the constraint and adjust the capacity through
7283 * 3b) If repvar was negated we need to subtract weight * (c - 1) from capacity(note we switched the sign of
7303 SCIPerrorMessage("try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7318 SCIPerrorMessage("try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7319 SCIPvarIsIntegral(aggrvars[i]) ? "integral " : "", SCIPvarGetName(aggrvars[i]), SCIPvarGetLbGlobal(aggrvars[i]), SCIPvarGetUbGlobal(aggrvars[i]));
7324 SCIPerrorMessage("try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[i]);
7327 /* if the new coefficient is smaller than zero, we need to add the negated variable instead and adjust the capacity */
7332 SCIP_CALL( addCoef(scip, cons, negvar, (SCIP_Longint)(SCIPfloor(scip, -weight * aggrscalars[i] + 0.5))) );
7337 SCIP_CALL( addCoef(scip, cons, aggrvars[i], (SCIP_Longint)(SCIPfloor(scip, weight * aggrscalars[i] + 0.5))) );
7343 /* adjust the capacity with the aggregation constant and if necessary the extra weight through the negation */
7376 /* if aggregated variables have been replaced, multiple entries of the same variable are possible and we have to
7434 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
7444 assert(SCIPvarIsActive(consdata->vars[i]) || SCIPvarIsNegated(consdata->vars[i]) || SCIPvarGetStatus(consdata->vars[i]) == SCIP_VARSTATUS_FIXED);
7466 * - minweightsum = sum_{negated cliques C} ( sum(wi : i \in C) - W_max(C) ), where W_max(C) is the maximal weight of C
7468 * if for i \in C (a negated clique) oneweightsum + minweightsum - wi + W_max(C) > capacity => xi = 1
7500 /* save the end positions of the cliques because start positions are moved in the following loop */
7525 /* for summing up the minimum active weights due to cliques we have to omit the biggest weights of each
7526 * clique, we can only skip this clique if this variables is not fixed to zero, otherwise we have to fix all
7571 /* we found a fixed variable to zero so all other variables in this negated clique have to be fixed to one */
7580 SCIPdebugMsg(scip, " -> fixing variable <%s> to 1, due to negated clique information\n", SCIPvarGetName(myvars[v]));
7581 SCIP_CALL( SCIPinferBinvarCons(scip, myvars[v], TRUE, cons, SCIPvarGetIndex(myvars[i]), &infeasible, &tightened) );
7612 /* reset local minweightsum for clique because all fixed to one variables are now counted in consdata->onesweightsum */
7626 SCIPdebugMsg(scip, "knapsack constraint <%s> has minimum weight sum of <%" SCIP_LONGINT_FORMAT ">\n",
7653 /* no need to process this negated clique because all variables are already fixed (which we detect from a fixed maxvar) */
7659 /* if the sum of all weights of fixed variables to one plus the minimalweightsum (minimal weight which is already
7660 * used in this knapsack due to negated cliques) plus any weight minus the second largest weight in this clique
7663 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[c]) > consdata->capacity )
7673 SCIP_CALL( SCIPinferBinvarCons(scip, maxvar, FALSE, cons, cliquestartposs[c], &infeasible, &tightened) );
7687 * the gain in any of the following negated cliques (the additional term if the maximum weight variable was set to 1, and the second
7690 * - the cliques are sorted by decreasing maximum weight -> for all c' >= c: maxweights[c'] <= maxcliqueweight
7693 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[nvars - 1]) <= consdata->capacity )
7699 /* there should be no variable fixed to 0 between startvarposclique + 1 and endvarposclique unless we
7715 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity )
7720 SCIPdebugMsg(scip, " -> fixing variable <%s> to 1, due to negated clique information\n", SCIPvarGetName(myvars[i]));
7743 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity;
7766 SCIPdebugMsg(scip, " -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT ", capacity: %" SCIP_LONGINT_FORMAT " \n",
7773 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) )
7775 /* start conflict analysis with the fixed-to-one variables, add only as many as needed to exceed the capacity */
7806 /* if all weights of fixed variables to one plus any weight exceeds the capacity the variables have to be fixed
7816 SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[i], FALSE, cons, i, &infeasible, &tightened) );
7830 /* sum up the weights of all unfixed variables, plus the weight sum of all variables fixed to one already */
7842 /* we summed up all (unfixed and fixed to one) weights and did not exceed the capacity, so the constraint is redundant */
7843 SCIPdebugMsg(scip, " -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT ", unfixedweightsum=%" SCIP_LONGINT_FORMAT ", capacity=%" SCIP_LONGINT_FORMAT "\n",
7852/** all but one variable fit into the knapsack constraint, so we can upgrade this constraint to an logicor constraint
7875 /* if the knapsack constraint consists only of two variables, we can upgrade it to a set-packing constraint */
7878 SCIPdebugMsg(scip, "upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons));
7880 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
7886 /* if the knapsack constraint consists of at least three variables, we can upgrade it to a logicor constraint
7893 SCIPdebugMsg(scip, "upgrading knapsack constraint <%s> to a logicor constraint", SCIPconsGetName(cons));
7898 SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consvars,
7920 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them
7922 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique
7925 * i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too
7932 SCIP_Longint frontsum, /**< sum of front items which fit if we try to take from the first till the last */
7968 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
7985 /* all rear items are redundant, because leaving one item in front and incl. of splitpos out the rear itmes always
8021 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8029 /* rear items can only be redundant, when the sum is smaller to the weight at splitpos and all rear items would
8030 * always fit into the knapsack, therefor the item directly after splitpos needs to be smaller than the one at
8044 SCIP_CALL( SCIPcalcCliquePartition(scip, &(consdata->vars[splitpos+1]), len, &conshdlrdata->probtoidxmap, &conshdlrdata->probtoidxmapsize, clqpart, &nclq) );
8066 /* all rear items are redundant due to clique information, if maxactduetoclq is smaller than the weight before,
8067 * so delete them and create for all clique the corresponding clique constraints and update the capacity
8077 SCIPdebugMsg(scip, "Found redundant variables in constraint <%s> due to clique information.\n", SCIPconsGetName(cons));
8094 /* we found a real clique so extract this constraint, because we do not know who this information generated so */
8100 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), capacity, c);
8154 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8173 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 13 => x4, x5 always fits into the knapsack, so we can delete them
8175 * i.e. 5x1 + 5x2 + 5x3 + 2x4 + 1x5 <= 8 and we have the cliqueinformation (x1,x2,x3) is a clique
8178 * i.e. 5x1 + 5x2 + 5x3 + 1x4 + 1x5 <= 6 and we have the cliqueinformation (x1,x2,x3) is a clique and (x4,x5) too
8225 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */
8240 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */
8292 /* if all items fit, then delete the whole constraint but create clique constraints which led to this
8304 SCIPdebugMsg(scip, "Found redundant constraint <%s> due to clique information.\n", SCIPconsGetName(cons));
8323 /* we found a real clique so extract this constraint, because we do not know who this information generated so */
8329 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), capacity, c);
8364/** divides weights by their greatest common divisor and divides capacity by the same value, rounding down the result */
8394 assert(SCIPvarGetUbLocal(consdata->vars[i]) > 0.5); /* all fixed variables should have been removed */
8401 SCIPdebugMessage("knapsack constraint <%s>: dividing weights by %" SCIP_LONGINT_FORMAT "\n", SCIPconsGetName(cons), gcd);
8422 * 1. a) check if all two pairs exceed the capacity, then we can upgrade this constraint to a set-packing constraint
8423 * b) check if all but the smallest weight fit into the knapsack, then we can upgrade this constraint to a logicor
8426 * 2. check if besides big coefficients, that fit only by itself, for a certain amount of variables all combination of
8429 * +219y1 + 180y2 + 74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3
8431 * 3. use the duality between a^Tx <= capacity <=> a^T~x >= weightsum - capacity to tighten weights, e.g.
8502 SCIPdebugMsg(scip, "upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons));
8504 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
8521 /* all but one variable fit into the knapsack, so we can upgrade this constraint to a logicor */
8530 /* early termination, if the pair with biggest coeffcients together does not exceed the dualcapacity */
8541 * the following is done without looking at the dualcapacity; it is enough to check whether for a certain amount of
8548 * +219y1 + 180y_2 +74x1 + 70x2 + 63x3 + 62x4 + 53x5 <= 219 <=> 3y1 + 3y2 + x1 + x2 + x3 + x4 + x5 <= 3
8600 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8610 /* a certain amount of small variables exceed the capacity, so check if this holds for all combinations of the
8626 /* if the same amount but with the smallest possible weights also exceed the capacity, it holds for all
8658 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8671 /* if the following assert fails we have either a redundant constraint or a set-packing constraint, this should
8680 * either choose x1, or all other variables (weightsum of x2 to x10 is 979 above), so we can tighten this
8721 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8757 /* any negated variable out of the first n - 1 items is enough to fulfill the constraint, so we can update it to a logicor
8781 /* we have a dual-knapsack constraint where we either need to choose one variable out of a subset (big
8788 * 3x1 + 3x2 + 2x3 + 2x4 + 2x5 + 2x6 + x7 <= 12 <=> 3~x1 + 3~x2 + 2~x3 + 2~x4 + 2~x5 + 2~x6 + ~x7 >= 3
8854 * e.g. 9x1 + 9x2 + 6x3 + 4x4 + 4x5 + 4x6 <= 27 <=> 9~x1 + 9~x2 + 6~x3 + 4~x4 + 4~x5 + 4~x6 >= 9
8881 /* we found redundant variables, which does not influence the feasibility of any integral solution, e.g.
8900 /* for performance reasons we do not update the capacity(, i.e. reduce it by reductionsum) and directly
8911 * e.g. 9x1 + 9x2 + 6x3 + 6x4 + 4x5 + 4x6 <= 29 <=> 9~x1 + 9~x2 + 6~x3 + 6~x4 + 4~x5 + 4~x6 >= 9
8916 if( weights[v] > 1 || (weights[startv] > (SCIP_Longint)nvars - v) || (startv > 0 && weights[0] == (SCIP_Longint)nvars - v + 1) )
8930 /* adjust middle sized coefficients, which when choosing also one small coefficients exceed the
8961 newcap = ((SCIP_Longint)startv - 1) * newweight + ((SCIP_Longint)v - startv) * (newweight - 1) + ((SCIP_Longint)nvars - v);
8970 assert(weights[v] == 1 && (weights[startv] == (SCIP_Longint)nvars - v) && (startv == 0 || weights[0] == (SCIP_Longint)nvars - v + 1));
8975 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
8985 /* check if all rear items have the same weight as the last one, so we cannot tighten the constraint further */
9032 /* dualcapacity is odd, we can set the middle weights to dualcapacity but therefor need to multiply all
9076 /* @todo loop for "k" can be extended, same coefficient when determine next sumcoef can be left out */
9106 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 5], weights[nvars - 2] + weights[nvars - 3]);
9110 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 4], weights[nvars - 1] + weights[nvars - 2] + weights[nvars - 3]);
9117 /* tighten next coefficients that, pair with the current small coefficient, exceed the dualcapacity */
9125 /* @todo check for further reductions, when two times the minweight exceeds the dualcapacity */
9157 /* now check if a combination of small coefficients allows us to tighten big coefficients further */
9220 /* dualcapacity is odd, we can set the middle weights to dualcapacity but therefor need to multiply all
9278 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal
9303/** fixes variables with weights bigger than the capacity and delete redundant constraints, also sort weights */
9402 * 1. use the duality between a^Tx <= capacity <=> -a^T~x <= capacity - weightsum to tighten weights, e.g.
9410 * 2. if variables in a constraint do not affect the (in-)feasibility of the constraint, we can delete them, e.g.
9414 * 3. Tries to use gcd information an all but one weight to change this not-included weight and normalize the
9417 * 9x1 + 6x2 + 6x3 + 5x4 <= 13 => 9x1 + 6x2 + 6x3 + 6x4 <= 12 => 3x1 + 2x2 + 2x3 + 2x4 <= 4 => 4x1 + 2x2 + 2x3 + 2x4 <= 4
9523 /* weight should still be sorted, because the reduction preserves this, but corresponding variables with equal weight
9546 /* determine coefficients as big as the capacity, these we do not need to take into account when calculating the
9565 /* calculate greatest common divisor over all integer and binary variables and determine the candidate where we might
9586 /* if the greatest commmon divisor has become 1, we might have found the possible coefficient to change or we
9597 /* if both first coefficients have a gcd of 1, both are candidates for the coefficient change */
9628 /* we should have found one coefficient, that led to a gcd of 1, otherwise we could normalize the constraint
9670 SCIPdebugMsg(scip, "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);
9672 /* must not change weights and capacity if one variable would be removed and we have a big coefficient,
9673 * e.g., 11x1 + 6x2 + 6x3 + 5x4 <= 11 => gcd = 6, offsetv = 1 => newweight = 0, but we would lose x1 = 1 => x4 = 0
9724 SCIPdebugMsg(scip, "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));
9773 /* we explicitly construct the complete implication graph where the knapsack variables are involved;
9778 SCIPdebugMsg(scip, "memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9809/** applies rule (3) of the weight tightening procedure, which can lift other variables into the knapsack:
9814 * - the weight of the variable or its negation (depending on v) can be increased as long as it has the same
9831 int* firstidxs[2]; /* first index in zeroitems for each binary variable/value pair, or zero for empty list */
9834 int* nextidxs; /* next index in zeroitems for the same binary variable, or zero for end of list */
9877 if( (!consdata->cliquepartitioned && nvars > MAX_USECLIQUES_SIZE) || consdata->ncliques > MAX_USECLIQUES_SIZE )
9886 /* we have to consider all integral variables since even integer and implicit integer variables can have binary bounds */
9907 /* next if conditions should normally not be true, because it means that presolving has created more binary variables
9908 * than binary + integer variables existed at the presolving initialization method, but for example if you would
9916 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->ints1, oldsize, conshdlrdata->ints1size) );
9917 BMSclearMemoryArray(&(conshdlrdata->ints1[oldsize]), conshdlrdata->ints1size - oldsize); /*lint !e866*/
9924 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->ints2, oldsize, conshdlrdata->ints2size) );
9925 BMSclearMemoryArray(&(conshdlrdata->ints2[oldsize]), conshdlrdata->ints2size - oldsize); /*lint !e866*/
9932 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->longints1, oldsize, conshdlrdata->longints1size) );
9933 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize); /*lint !e866*/
9940 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->longints2, oldsize, conshdlrdata->longints2size) );
9941 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize); /*lint !e866*/
9972 /* next if conditions should normally not be true, because it means that presolving has created more binary variables
9973 * than binary + integer variables existed at the presolving initialization method, but for example if you would
9981 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->bools1, oldsize, conshdlrdata->bools1size) );
9982 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize); /*lint !e866*/
9989 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->bools2, oldsize, conshdlrdata->bools2size) );
9990 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize); /*lint !e866*/
10134 /* calculate the clique partition and the maximal sum of weights using the clique information */
10140 /* next if condition should normally not be true, because it means that presolving has created more binary variables
10141 * in one constraint than binary + integer variables existed in the whole problem at the presolving initialization
10142 * method, but for example if you would transform all integers into their binary representation then it maybe happens
10149 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->bools3, oldsize, conshdlrdata->bools3size) );
10150 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize); /*lint !e866*/
10184 /* next if condition should normally not be true, because it means that presolving has created more binary variables
10185 * in one constraint than binary + integer variables existed in the whole problem at the presolving initialization
10186 * method, but for example if you would transform all integers into their binary representation then it maybe happens
10193 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->bools4, oldsize, conshdlrdata->bools4size) );
10194 BMSclearMemoryArray(&conshdlrdata->bools4[oldsize], conshdlrdata->bools4size - oldsize); /*lint !e866*/
10205 /* for each binary variable xi and each fixing v, calculate the cliqueweightsum and update the weight of the
10206 * variable in the knapsack (this is sequence-dependent because the new or modified weights have to be
10232 /* mark the items that are implied to zero by setting the current variable to the current value */
10280 SCIPdebugMsg(scip, "knapsack constraint <%s>: adding lifted item %" SCIP_LONGINT_FORMAT "<%s>\n",
10317 /* if new items were added, multiple entries of the same variable are possible and we have to clean up the constraint */
10342 * - wi and capacity can be changed to have the same redundancy effect and the same results for
10343 * fixing xi to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
10347 * (2) increase weights from front to back(sortation is necessary) if there is no space left for another weight
10348 * - determine the four(can be adjusted) minimal weightsums of the knapsack, i.e. in increasing order
10349 * weights[nvars - 1], weights[nvars - 2], MIN(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]),
10350 * MIN(MAX(weights[nvars - 3], weights[nvars - 1] + weights[nvars - 2]), weights[nvars - 4]), note that there
10352 * - check if summing up a minimal weightsum with a big weight exceeds the capacity, then we can increase the big
10363 * - weights wi, i in C, and capacity can be changed to have the same redundancy effect and the same results for
10364 * fixing xi, i in C, to zero or one, but with a reduced wi and tightened capacity to tighten the LP relaxation
10369 * This rule has to add the used cliques in order to ensure they are enforced - otherwise, the reduction might
10375 * - the weight of the variable or its negation (depending on v) can be increased as long as it has the same
10422 assert(consdata->weightsum > consdata->capacity); /* otherwise, the constraint is redundant */
10452 SCIPdebugMsg(scip, "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",
10483 /* @todo loop for "k" can be extended, same coefficient when determine next sumcoef can be left out */
10539 /* tighten next coefficients that, paired with the current small coefficient, exceed the capacity */
10546 SCIPdebugMsg(scip, "in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n",
10579 SCIPdebugMsg(scip, "in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n",
10592 /* apply rule (2) (don't apply, if the knapsack has too many items for applying this costly method) */
10615 SCIPdebugMsg(scip, "upgrading knapsack constraint <%s> to a set-packing constraint", SCIPconsGetName(cons));
10617 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, SCIPconsGetName(cons), pos, consdata->vars,
10641 SCIP_CALL( SCIPcalcCliquePartition(scip, &(consdata->vars[pos]), len, &conshdlrdata->probtoidxmap, &conshdlrdata->probtoidxmapsize, clqpart, &nclq) );
10650 SCIPdebugMsg(scip, "Disaggregating knapsack constraint <%s> due to clique information.\n", SCIPconsGetName(cons));
10676 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), consdata->capacity, c);
10700 else if( consdata->nvars <= MAX_USECLIQUES_SIZE || (consdata->cliquepartitioned && consdata->ncliques <= MAX_USECLIQUES_SIZE) )
10772 SCIPdebugMsg(scip, "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",
10802 /* check if our clique information results out of this knapsack constraint and if so check if we would loose the clique information */
10829 SCIPdebugMsg(scip, " -> change capacity from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT " (forceclique:%u)\n",
10841 SCIPdebugMsg(scip, " -> change weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n",
10848 /* if before the weight update at least one pair of weights did not fit into the knapsack and now fits,
10849 * we have to make sure, the clique is enforced - the clique might have been constructed partially from
10850 * this constraint, and by reducing the weights, this clique information is not contained anymore in the
10863 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%" SCIP_LONGINT_FORMAT "_%d", SCIPconsGetName(cons), consdata->capacity, i);
10927 SCIPdebugMsg(scip, "knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n",
10930 consdataChgWeight(consdata, i, consdata->capacity); /* this does not destroy the weight order! */
10950 SCIPdebugMsg(scip, "knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT " to %" SCIP_LONGINT_FORMAT "\n",
10951 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[consdata->nvars-1]), weight, consdata->capacity);
10953 consdataChgWeight(consdata, consdata->nvars-1, consdata->capacity); /* this does not destroy the weight order! */
11058 /* determine maximal weights for all negated cliques and calculate minimal weightsum due to negated cliques */
11061 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11078 /* free capacity is the rest of not used capacity if the smallest amount of weights due to negated cliques are used */
11082 SCIPdebugMsg(scip, "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",
11093 /* if we would take the biggest weight instead of another what would we gain, take weight[v] instead of
11099 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[w];
11111 SCIPsortDownLongPtrInt(gainweights,(void**) poscliquevars, gaincliquepartition, nposcliquevars);
11124 /* taking bigger weights make the knapsack redundant so we will create cliques, only take items which are not
11126 for( w = v + 1; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && gainweights[w] + lastweight > freecapacity; ++w )
11150 /* try to replace the last item in the clique by a different item to obtain a slightly different clique */
11151 for( ++w; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && beforelastweight + gainweights[w] > freecapacity; ++w )
11179 * greedily detects cliques by first sorting the items by decreasing weights (optional) and then collecting greedily
11181 * 2) looping through the remaining items and finding the largest set of preceding items to build a clique => possibly many more cliques
11191 SCIP_Real cliqueextractfactor,/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
11236 /* no more cliques to be found (don't know if this can actually happen, since the knapsack could be replaced by a set-packing constraint)*/
11243 /* try to replace the last item in the clique by a different item to obtain a slightly different clique */
11244 /* loop over remaining, smaller items and compare each item backwards against larger weights, starting with the second smallest weight */
11262 /* include this item together with all items that have a weight at least as large as the compare weight in a clique */
11281 /* choose a preceding, larger weight to compare small items against. Clique size is reduced by 1 simultaneously */
11298 SCIP_Real cliqueextractfactor,/**< lower clique size limit for greedy clique extraction algorithm (relative to largest clique) */
11359 /* calculate minimal activity due to negated cliques, and determine second maximal weight in each clique */
11388 /* free capacity is the rest of not used capacity if the smallest amount of weights due to negated cliques are used */
11392 SCIPdebugMsg(scip, "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",
11395 /* create negated cliques out of negated cliques, if we do not take the smallest weight of a cliques ... */
11418 SCIP_CALL( greedyCliqueAlgorithm(scip, poscliquevars, gainweights, nposcliquevars, freecapacity, FALSE, cliqueextractfactor, cutoff, nbdchgs) );
11426 SCIP_CALL( greedyCliqueAlgorithm(scip, consdata->vars, consdata->weights, nvars, consdata->capacity, TRUE, cliqueextractfactor, cutoff, nbdchgs) );
11447/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables and the
11527/** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
11596 /* constraint found: create a new constraint with same coefficients and best left and right hand side;
11627 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
11691 for( c = (consdata0->presolvedtiming == SCIP_PRESOLTIMING_EXHAUSTIVE ? firstchange : 0); c < chkind; ++c )
11711 if( consdata0->presolvedtiming >= SCIP_PRESOLTIMING_EXHAUSTIVE && consdata1->presolvedtiming >= SCIP_PRESOLTIMING_EXHAUSTIVE ) /*lint !e574*/
11745 SCIPdebugMsg(scip, "preprocess knapsack constraint pair <%s> and <%s>\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1));
11782 /* if cons1 is possible contained in cons0 (consdata0->weights[v0] / quotient) must be greater equals consdata1->weights[v1] */
11783 if( iscons1incons0contained && SCIPisLT(scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) )
11789 /* if cons0 is possible contained in cons1 (consdata0->weight[v0] / quotient) must be less equals consdata1->weight[v1] */
11790 else if( iscons0incons1contained && SCIPisGT(scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) )
11818 /* neither one constraint was contained in another or we checked all variables of one constraint against the
11828 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
11839 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
11872 SCIPdebugMsg(scip, "knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11878 maxncuts = (SCIPgetDepth(scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11946 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
11948 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
11968 /* if the right hand side is non-infinite, we have to negate all variables with negative coefficient;
11969 * otherwise, we have to negate all variables with positive coefficient and multiply the row with -1
12003 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
12033 SCIPdebugMsg(scip, "upgrading constraint <%s> to knapsack constraint\n", SCIPconsGetName(cons));
12035 /* create the knapsack constraint (an automatically upgraded constraint is always unmodifiable) */
12037 SCIP_CALL( createNormalizedKnapsack(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, lhs, rhs,
12088 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
12123/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
12134 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->probtoidxmap, conshdlrdata->probtoidxmapsize);
12157 /* all variables which are of integral type can be binary; this can be checked via the method SCIPvarIsBinary(var) */
12166/** deinitialization method of constraint handler (called before transformed problem is freed) */
12185/** presolving initialization method of constraint handler (called when presolving is about to begin) */
12199 /* all variables which are of integral type can be binary; this can be checked via the method SCIPvarIsBinary(var) */
12228/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
12242 /* since we are not allowed to detect infeasibility in the exitpre stage, we dont give an infeasible pointer */
12288/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
12368 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
12369 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
12372 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
12381/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
12431 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12459 SCIP_CALL( separateCons(scip, conss[i], NULL, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12500 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12520 SCIP_CALL( separateCons(scip, conss[i], sol, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12613 /* do not propagate constraints with multi-aggregated variables, which should only happen in probing mode,
12623 SCIP_CALL( propagateCons(scip, conss[i], &cutoff, &redundant, &nfixedvars, conshdlrdata->negatedclique) );
12670 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12722 SCIP_CALL( propagateCons(scip, cons, &cutoff, &redundant, nfixedvars, (presoltiming & SCIP_PRESOLTIMING_MEDIUM)) );
12745 /* check again for redundancy (applyFixings() might have decreased weightsum due to fixed-to-zero vars) */
12748 SCIPdebugMsg(scip, " -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT ", capacity=%" SCIP_LONGINT_FORMAT "\n",
12760 SCIP_CALL( simplifyInequalities(scip, cons, nfixedvars, ndelconss, nchgcoefs, nchgsides, naddconss, &cutoff) );
12777 SCIP_CALL( tightenWeights(scip, cons, presoltiming, nchgcoefs, nchgsides, naddconss, ndelconss, &cutoff) );
12783 if( conshdlrdata->dualpresolving && SCIPallowStrongDualReds(scip) && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12785 /* in case the knapsack constraints is independent of everything else, solve the knapsack and apply the
12803 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12805 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
12806 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &cutoff, ndelconss) );
12809 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12814 if( !cutoff && firstchange < nconss && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
12829 npaircomparisons += ((SCIPconsGetData(cons)->presolvedtiming < SCIP_PRESOLTIMING_EXHAUSTIVE) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
12835 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12837 if( ((SCIP_Real) (*ndelconss - oldndelconss) + ((SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12838 ((SCIP_Real) (*nchgcoefs - oldnchgcoefs))/10.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
12848 /* @todo upgrade to cardinality constraints: the code below relies on disabling the checking of the knapsack
12849 * constraint in the original problem, because the upgrade ensures that at most the given number of continuous
12850 * variables has a nonzero value, but not that the binary variables corresponding to the continuous variables with
12851 * value zero are set to zero as well. This can cause problems if the user accesses the values of the binary
12852 * variables (as the MIPLIB solution checker does), or the transformed problem is freed and the original problem
12853 * (possibly with some user modifications) is re-optimized. Until there is a way to force the binary variables to 0
12855 /* upgrade to cardinality constraints - only try to upgrade towards the end of presolving, since the process below is quite expensive */
12856 if ( ! cutoff && conshdlrdata->upgdcardinality && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 && SCIPisPresolveFinished(scip) && ! conshdlrdata->upgradedcard )
12874 * - First, determine for each binary variable the number of cardinality constraints that can be upgraded to a
12875 * knapsack constraint and contain this variable; this number has to coincide with the number of variable up
12876 * locks; otherwise it would be infeasible to delete the knapsack constraints after the constraint update.
12914 /* check whether all variables are of the form 0 <= x_v <= u_v y_v for y_v \in \{0,1\} and zero objective */
12996 /* for each variable: check whether the number of cardinality constraints that can be upgraded to a
13001 if ( SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL) != SCIPhashmapGetImageInt(varhash, vars[v]) )
13011 SCIPdebugMessage("Upgrading knapsack constraint <%s> to cardinality constraint ...\n", SCIPconsGetName(cons));
13015 SCIP_CALL( SCIPcreateConsCardinality(scip, &cardcons, SCIPconsGetName(cons), nvars, cardvars, (int) consdata->capacity, vars, cardweights,
13018 SCIPconsIsLocal(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
13033 /* We need to disable the original knapsack constraint, since it might happen that the binary variables
13034 * are 1 although the continuous variables are 0. Thus, the knapsack constraint might be violated,
13100 /* according to negated cliques the minweightsum and all variables which are fixed to one which led to a fixing of
13101 * another negated clique variable to one, the inferinfo was chosen to be the negative of the position in the
13108 /* locate the inference variable and calculate the capacity that has to be used up to conclude infervar == 0;
13109 * inferinfo stores the position of the inference variable (but maybe the variables were re-sorted)
13122 /* add fixed-to-one variables up to the point, that their weight plus the weight of the conflict variable exceeds
13140 /* NOTE: It might be the case that capsum < consdata->capacity. This is due the fact that the fixing of the variable
13141 * to zero can included negated clique information. A negated clique means, that at most one of the clique
13142 * variables can be zero. These information can be used to compute a minimum activity of the constraint and
13145 * Even if capsum < consdata->capacity we still reported a complete reason since the minimum activity is based
13146 * on global variable bounds. It might even be the case that we reported to many variables which are fixed to
13287 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
13301 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13322 -SCIPinfinity(scip), (SCIP_Real) SCIPgetCapacityKnapsack(sourcescip, sourcecons), varmap, consmap,
13323 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
13430 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13462/** constraint method of constraint handler which returns the number of variables (if possible) */
13477/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
13486/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
13525 case SCIP_EVENTTYPE_VARFIXED: /* the variable should be removed from the constraint in presolving */
13532 /* if the variable was aggregated or multiaggregated, we must signal to propagation that we are no longer merged */
13539 (SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(var)) == SCIP_VARSTATUS_AGGREGATED) )
13543 case SCIP_EVENTTYPE_IMPLADDED: /* further preprocessing might be possible due to additional implications */
13577 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr), EVENTHDLR_NAME, EVENTHDLR_DESC,
13614 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolKnapsack,CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
13616 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropKnapsack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
13619 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpKnapsack, consSepasolKnapsack, CONSHDLR_SEPAFREQ,
13624 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphKnapsack) );
13628 /* include the linear constraint to knapsack constraint upgrade in the linear constraint handler */
13629 SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdKnapsack, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );
13635 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13636 &conshdlrdata->sepacardfreq, TRUE, DEFAULT_SEPACARDFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
13639 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13643 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13644 &conshdlrdata->cliqueextractfactor, TRUE, DEFAULT_CLIQUEEXTRACTFACTOR, 0.0, 1.0, NULL, NULL) );
13691 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13695 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13722 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13751 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
13753 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
13791 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13805 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
13806 * method SCIPcreateConsKnapsack(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
13810 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13914/** gets the array of variables in the knapsack constraint; the user must not modify this array! */
13932/** gets the array of weights in the knapsack constraint; the user must not modify this array! */
13992/** returns the linear relaxation of the given knapsack constraint; may return NULL if no LP row was yet created;
14036 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, consdata->vars[i], (SCIP_Real)consdata->weights[i]) );
14047 SCIP_Bool* infeasible, /**< pointer to return whether the problem was detected to be infeasible */
14063 nconss = onlychecked ? SCIPconshdlrGetNCheckConss(conshdlr) : SCIPconshdlrGetNActiveConss(conshdlr);
constraint handler for cardinality constraints
static SCIP_Longint safeAddMinweightsGUB(SCIP_Longint val1, SCIP_Longint val2)
Definition: cons_knapsack.c:3880
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:6236
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
Definition: cons_knapsack.c:657
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyKnapsack)
Definition: cons_knapsack.c:12107
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:2949
static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss)
Definition: cons_knapsack.c:7929
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:9734
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
Definition: cons_knapsack.c:903
static SCIP_DECL_CONSENFOPS(consEnfopsKnapsack)
Definition: cons_knapsack.c:12552
static SCIP_RETCODE eventdataCreate(SCIP *scip, SCIP_EVENTDATA **eventdata, SCIP_CONS *cons, SCIP_Longint weight)
Definition: cons_knapsack.c:345
static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs)
Definition: cons_knapsack.c:9305
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphKnapsack)
Definition: cons_knapsack.c:13479
static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen)
Definition: cons_knapsack.c:3452
static SCIP_DECL_CONSGETVARS(consGetVarsKnapsack)
Definition: cons_knapsack.c:13442
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:5051
static SCIP_RETCODE GUBconsCreate(SCIP *scip, SCIP_GUBCONS **gubcons)
Definition: cons_knapsack.c:1748
static void normalizeWeights(SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
Definition: cons_knapsack.c:8366
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:5218
static SCIP_RETCODE addCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
Definition: cons_knapsack.c:11295
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
Definition: cons_knapsack.c:7856
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:875
static void updateWeightSums(SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Longint weightdelta)
Definition: cons_knapsack.c:637
static void GUBconsFree(SCIP *scip, SCIP_GUBCONS **gubcons)
Definition: cons_knapsack.c:1769
static SCIP_DECL_CONSSEPALP(consSepalpKnapsack)
Definition: cons_knapsack.c:12400
static void getPartitionCovervars(SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
Definition: cons_knapsack.c:2685
static void GUBsetSwapVars(SCIP *scip, SCIP_GUBSET *gubset, int var1, int var2)
Definition: cons_knapsack.c:1950
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_knapsack.c:534
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:2411
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool transformed)
Definition: cons_knapsack.c:599
static SCIP_DECL_CONSRESPROP(consRespropKnapsack)
Definition: cons_knapsack.c:13073
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:11919
static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)
Definition: cons_knapsack.c:477
static SCIP_DECL_CONSEXITPRE(consExitpreKnapsack)
Definition: cons_knapsack.c:12230
static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
Definition: cons_knapsack.c:6572
static SCIP_DECL_CONSINITSOL(consInitsolKnapsack)
Definition: cons_knapsack.c:12273
static SCIP_RETCODE changePartitionCovervars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
Definition: cons_knapsack.c:2734
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
Definition: cons_knapsack.c:6615
static SCIP_RETCODE GUBsetCheck(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars)
Definition: cons_knapsack.c:2071
static SCIP_RETCODE GUBsetMoveVar(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons)
Definition: cons_knapsack.c:1859
static SCIP_DECL_CONSGETNVARS(consGetNVarsKnapsack)
Definition: cons_knapsack.c:13464
static SCIP_RETCODE addNegatedCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs)
Definition: cons_knapsack.c:10982
static SCIP_RETCODE detectRedundantVars(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
Definition: cons_knapsack.c:8182
static SCIP_RETCODE GUBsetGetCliquePartition(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals)
Definition: cons_knapsack.c:2314
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition: cons_knapsack.c:12049
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
Definition: cons_knapsack.c:7180
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_knapsack.c:521
static void computeMinweightsGUB(SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen)
Definition: cons_knapsack.c:3899
static SCIP_DECL_CONSINITLP(consInitlpKnapsack)
Definition: cons_knapsack.c:12383
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:3951
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:2156
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:981
static SCIP_DECL_CONSEXITSOL(consExitsolKnapsack)
Definition: cons_knapsack.c:12290
static SCIP_RETCODE dualWeightsTightening(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
Definition: cons_knapsack.c:8440
static SCIP_DECL_CONSPRESOL(consPresolKnapsack)
Definition: cons_knapsack.c:12642
static SCIP_DECL_HASHGETKEY(hashGetKeyKnapsackcons)
Definition: cons_knapsack.c:11441
static SCIP_DECL_CONSDELVARS(consDelvarsKnapsack)
Definition: cons_knapsack.c:13210
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
Definition: cons_knapsack.c:6278
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_knapsack.c:574
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_knapsack.c:783
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:2642
static SCIP_DECL_CONSDEACTIVE(consDeactiveKnapsack)
Definition: cons_knapsack.c:13188
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:3502
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:4817
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:5332
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, int pos)
Definition: cons_knapsack.c:6358
static SCIP_RETCODE greedyCliqueAlgorithm(SCIP *const scip, SCIP_VAR **items, SCIP_Longint *weights, int nitems, SCIP_Longint capacity, SCIP_Bool sorteditems, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
Definition: cons_knapsack.c:11184
static SCIP_RETCODE eventdataFree(SCIP *scip, SCIP_EVENTDATA **eventdata)
Definition: cons_knapsack.c:363
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss)
Definition: cons_knapsack.c:11531
static SCIP_RETCODE GUBsetCreate(SCIP *scip, SCIP_GUBSET **gubset, int nvars, SCIP_Longint *weights, SCIP_Longint capacity)
Definition: cons_knapsack.c:1990
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:2863
static SCIP_RETCODE tightenWeightsLift(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff)
Definition: cons_knapsack.c:9820
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphKnapsack)
Definition: cons_knapsack.c:13488
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:5481
static SCIP_DECL_CONSACTIVE(consActiveKnapsack)
Definition: cons_knapsack.c:13176
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:9422
static SCIP_RETCODE removeZeroWeights(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:6548
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_knapsack.c:547
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_knapsack.c:11853
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:4686
static SCIP_DECL_CONSSEPASOL(consSepasolKnapsack)
Definition: cons_knapsack.c:12474
static void getPartitionNoncovervars(SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR)
Definition: cons_knapsack.c:2815
static SCIP_RETCODE stableSort(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique)
Definition: cons_knapsack.c:7056
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:10384
static void consdataChgWeight(SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight)
Definition: cons_knapsack.c:837
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique)
Definition: cons_knapsack.c:7392
static SCIP_DECL_CONSENFOLP(consEnfolpKnapsack)
Definition: cons_knapsack.c:12534
static SCIP_DECL_CONSINITPRE(consInitpreKnapsack)
Definition: cons_knapsack.c:12187
static SCIP_DECL_CONSDELETE(consDeleteKnapsack)
Definition: cons_knapsack.c:12319
static SCIP_DECL_LINCONSUPGD(linconsUpgdKnapsack)
Definition: cons_knapsack.c:12014
static SCIP_DECL_CONSENFORELAX(consEnforelaxKnapsack)
Definition: cons_knapsack.c:12543
static SCIP_RETCODE checkParallelObjective(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons_knapsack.c:6900
static SCIP_RETCODE GUBconsAddVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var)
Definition: cons_knapsack.c:1787
static SCIP_RETCODE changePartitionFeasiblesetvars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
Definition: cons_knapsack.c:2774
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss)
Definition: cons_knapsack.c:11655
static SCIP_RETCODE GUBconsDelVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var, int gubvarsidx)
Definition: cons_knapsack.c:1822
static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted)
Definition: cons_knapsack.c:6758
static SCIP_DECL_HASHKEYEQ(hashKeyEqKnapsackcons)
Definition: cons_knapsack.c:11451
static SCIP_DECL_HASHKEYVAL(hashKeyValKnapsackcons)
Definition: cons_knapsack.c:11494
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
Definition: cons_linear.c:17715
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13897
SCIP_RETCODE SCIPcreateRowKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:14013
SCIP_RETCODE SCIPcreateConsCardinality(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int cardval, SCIP_VAR **indvars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_cardinality.c:3685
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
Definition: cons_knapsack.c:13831
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:1610
SCIP_RETCODE SCIPcleanupConssKnapsack(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible, int *ndelconss)
Definition: cons_knapsack.c:14044
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:5580
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:9551
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:13812
SCIP_RETCODE SCIPchgCapacityKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity)
Definition: cons_knapsack.c:13870
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:5797
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:1091
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:13725
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:17944
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13933
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13849
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13915
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:5487
SCIP_Real SCIPgetDualfarkasKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13972
SCIP_ROW * SCIPgetRowKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13995
SCIP_Real SCIPgetDualsolKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13951
SCIP_RETCODE SCIPincludeConshdlrKnapsack(SCIP *scip)
Definition: cons_knapsack.c:13563
SCIP_Bool SCIPisConsCompressionEnabled(SCIP *scip)
Definition: scip_copy.c:662
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:713
SCIP_RETCODE SCIPaddConsUpgrade(SCIP *scip, SCIP_CONS *oldcons, SCIP_CONS **newcons)
Definition: scip_prob.c:3368
SCIP_CONS * SCIPfindOrigCons(SCIP *scip, const char *name)
Definition: scip_prob.c:3476
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3304
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3061
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3466
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3179
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3400
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:2298
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2596
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2665
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2535
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:4289
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:4067
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9197
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:9641
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_param.c:83
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_param.c:139
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_param.c:57
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:336
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:314
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:569
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip_conflict.c:728
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4802
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4350
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4759
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:396
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:492
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_cons.c:235
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
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_cons.c:181
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_Longint SCIPconshdlrGetNCutsFound(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:5046
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:420
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:516
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:940
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELVARS((*consdelvars)))
Definition: scip_cons.c:762
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4340
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4816
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4739
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2536
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
Definition: scip_cons.c:1296
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip_cons.c:1271
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
Definition: scip_cons.c:1321
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:2042
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_cons.c:997
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1812
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:2014
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1524
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1173
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
Definition: scip_cons.c:1371
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
Definition: scip_cons.c:1346
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:225
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:111
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:367
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:413
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition: scip_nlp.c:1058
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition: scip_nlp.c:954
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1398
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(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_lp.c:1367
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1646
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2176
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_lp.c:1429
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_lp.c:1458
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1844
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1763
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:467
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
Definition: scip_solvingstats.c:1845
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:823
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:488
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:771
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:462
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:784
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:797
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:872
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:475
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:810
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:436
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:449
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:848
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6401
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:5210
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:23875
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:8882
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:2119
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:4380
SCIP_RETCODE SCIPcalcNegatedCliquePartition(SCIP *scip, SCIP_VAR **vars, int nvars, int **probtoidxmap, int *probtoidxmapsize, int *cliquepartition, int *ncliques)
Definition: scip_var.c:9410
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6651
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:728
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:24617
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:5118
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:5296
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2872
SCIP_RETCODE SCIPcalcCliquePartition(SCIP *scip, SCIP_VAR **vars, int nvars, int **probtoidxmap, int *probtoidxmapsize, int *cliquepartition, int *ncliques)
Definition: scip_var.c:9330
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:24646
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2332
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:2166
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:24685
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:10318
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2736
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:17687
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:7412
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:361
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip_var.c:2236
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:16852
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:4322
SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars)
Definition: scip_var.c:2199
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:24632
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
Definition: var.c:17655
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:23850
void SCIPselectWeightedDownRealLongRealInt(SCIP_Real *realarray1, SCIP_Longint *longarray, SCIP_Real *realarray3, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortDownLongPtr(SCIP_Longint *longarray, void **ptrarray, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortPtrPtrLongIntInt(void **ptrarray1, void **ptrarray2, SCIP_Longint *longarray, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownLongPtrPtrIntInt(SCIP_Longint *longarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealIntLong(SCIP_Real *realarray, int *intarray, SCIP_Longint *longarray, int len)
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownLongPtrInt(SCIP_Longint *longarray, void **ptrarray, int *intarray, int len)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
Definition: symmetry_graph.c:1845
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
Definition: symmetry_graph.c:376
memory allocation routines
Definition: multiprecision.hpp:66
public methods for managing constraints
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for selecting k-medians
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
Definition: sepa_flower.c:1219
Definition: struct_implics.h:76
Definition: struct_cons.h:47
Definition: struct_cons.h:128
Definition: struct_event.h:218
Definition: cons_knapsack.c:300
Definition: cons_knapsack.c:310
Definition: struct_misc.h:139
Definition: struct_misc.h:90
Definition: struct_nlp.h:65
Definition: struct_lp.h:205
Definition: struct_sepa.h:47
Definition: struct_sol.h:74
Definition: struct_var.h:262
Definition: struct_symmetry.h:46
Definition: struct_scip.h:72
structs for symmetry computations
methods for dealing with symmetry detection graphs