cuts.c
Go to the documentation of this file.
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58/* =========================================== general static functions =========================================== */
96 SCIPquadprecProdQD(coef, coef, (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]])));
102 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]])));
106 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]])));
112 SCIPdebugMsgPrint(scip, " <= %.6f (activity: %g)\n", QUAD_TO_DBL(cutrhs), QUAD_TO_DBL(activity));
130 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
175 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
218 * This is the quad precision version of varVecAddScaledRowCoefs() with a quad precision scaling factor.
222 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
274 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
332/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter */
336 SCIP_Real* vals, /**< array of the non-zero coefficients in the vector; this is a quad precision array! */
337 int* inds, /**< array of the problem indices of variables with a non-zero coefficient in the vector */
394/** calculates the cut efficacy for the given solution; the cut coefs are stored densely and in quad precision */
399 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
401 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
477 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
570 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
579 /* loop over non-zeros and remove values below minval; values above QUAD_EPSILON are cancelled with their bound
697/** change given coefficient to new given value, adjust right hand side using the variables bound;
742/** change given (quad) coefficient to new given value, adjust right hand side using the variables bound;
787/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
788 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse quad precision array;
798 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
820 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
832 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
850 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
899 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
900 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
920 if( chgQuadCoeffWithBound(scip, vars[cutinds[i]], QUAD(val), intval, cutislocal, QUAD(cutrhs)) )
960 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
970 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1040 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1046 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1061 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1064 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1070 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1084 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1108 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1111 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1117 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1131 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1155 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1164/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1165 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
1173 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1195 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1208 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1226 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1274 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
1275 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1334 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1343 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1400 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1406 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1424 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1430 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1444 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1470 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1476 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1490 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1513 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1522/** perform activity based coefficient tightening on the given cut; returns TRUE if the cut was detected
1532 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1566 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1584 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1611 /* terminate, because coefficient tightening cannot be performed; also excludes the case in which no integral variable is present */
1618 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1621 /* due to sorting, we can exit if we reached a continuous variable: all further integral variables have 0 coefficents anyway */
1630 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1643 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1671 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1684 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1709 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1719/* =========================================== aggregation row =========================================== */
1805 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", QUAD_TO_DBL(val), SCIPvarGetName(vars[aggrrow->inds[i]]));
1828 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->vals, source->vals, QUAD_ARRAY_SIZE(nvars)) );
1839 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowsinds, source->rowsinds, source->nrows) );
1840 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->slacksign, source->slacksign, source->nrows) );
1841 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowweights, source->rowweights, source->nrows) );
1885 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
1886 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
1887 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
1905 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
1933 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
1938/** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
1939 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
1941 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
1943 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
2003/** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
2154/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2156 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2166/** Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional
2177 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2190 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
2209 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
2214 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
2255 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2256 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2257 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2267 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
2287 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2313 SCIP_CALL( addOneRow(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2325 SCIP_CALL( addOneRow(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2350 SCIP_Bool* success /**< pointer to return whether post-processing was succesful or cut is redundant */
2378 SCIP_CALL( cutTightenCoefs(scip, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz, &redundant) );
2397 *success = ! removeZeros(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz);
2419 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
2435 if( removeZerosQuad(scip, SCIPfeastol(scip), cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz) )
2444 SCIP_CALL( cutTightenCoefsQuad(scip, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz, &redundant) );
2465 *success = ! removeZerosQuad(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz);
2481 *valid = ! removeZerosQuad(scip, SCIPsumepsilon(scip), useglbbounds ? FALSE : aggrrow->local, aggrrow->vals,
2540/** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
2590/* =========================================== c-MIR =========================================== */
2600 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2601 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2633 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
2637 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2638 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2661 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2662 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2694 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
2698 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2699 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2716/** determine the best bounds with respect to the given solution for complementing the given variable */
2722 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
2723 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2724 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2725 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
2727 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
2730 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
2736 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
2749 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || ( boundsfortrans[v] == -2 || boundsfortrans[v] == -1 ));
2780 *bestlb = vlbcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vlbvars[k]) : SCIPgetSolVal(scip, sol, vlbvars[k])) + vlbconsts[k];
2786 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2787 SCIP_CALL( findBestUb(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
2818 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2819 *bestub = vubcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vubvars[k]) : SCIPgetSolVal(scip, sol, vubvars[k])) + vubconsts[k];
2825 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2826 SCIP_CALL( findBestLb(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
2835 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2838 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2868 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
2915/** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index */
2926 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
2928 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
2995/** performs the bound substitution step with the simple bound for the variable with the given problem index */
3003 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
3005 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
3030 * x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation},\\
3031 * x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation},
3039 * x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\
3040 * x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.}
3043 * move the constant terms \f$ a_j\, dl_j \f$ or \f$ a_j\, du_j \f$ to the rhs, and update the coefficient of the VLB variable:
3055 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3057 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3058 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3060 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3063 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3074 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
3075 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
3105 /* start with continuous variables, because using variable bounds can affect the untransformed integral
3106 * variables, and these changes have to be incorporated in the transformation of the integral variables
3118 SCIP_CALL( determineBestBounds(scip, vars[cutinds[i]], sol, boundswitch, usevbds ? 2 : 0, allowlocal, fixintegralrhs,
3120 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3142 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestlbs[i], v, localbdsused);
3152 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestubs[i], v, localbdsused);
3156 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
3178 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
3181 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3190 /* now perform the bound substitution on the remaining integral variables which only uses standard bounds */
3205 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlbs[i], v, localbdsused);
3216 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestubs[i], v, localbdsused);
3298 /* prefer larger violations; for equal violations, prefer smaller f0 values since then the possibility that
3301 if( SCIPisGT(scip, violgain, bestviolgain) || (SCIPisGE(scip, violgain, bestviolgain) && newf0 < bestnewf0) )
3329 assert(bestubtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3336 assert(bestlbtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3357/** Calculate fractionalities \f$ f_0 := b - down(b), f_j := a^\prime_j - down(a^\prime_j) \f$, and derive MIR cut \f$ \tilde{a} \cdot x' \leq down(b) \f$
3372 * x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation}, \\
3373 * x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation},
3388 * x^\prime_j := x_j - (bl_j \cdot zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\
3389 * x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)}
3402 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
3412 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
3415 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
3437 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
3445 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
3513 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3548 /* now process the continuous variables; postpone deletion of zeros untill all continuous variables have been processed */
3596 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3703 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
3704 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r]. \f$
3706 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
3710 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f_0)/(1 - f_0),& \mbox{if}\qquad f_r > f_0 \\
3716 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
3862/** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
3865 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3877 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3879 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3880 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3881 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3884 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3890 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
3891 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
3892 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
3893 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
3895 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
3896 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
3897 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
3963 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, if vlb is used in transf.
3964 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, if vub is used in transf.
3965 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
3969 SCIP_CALL( cutsTransformMIR(scip, sol, boundswitch, usevbds, allowlocal, fixintegralrhs, FALSE,
3970 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
3991 * x'_j := x_j - lb_j, x_j == x'_j + lb_j, a'_j == a_j, a^_j := a~_j, if lb was used in transformation
3992 * x'_j := ub_j - x_j, x_j == ub_j - x'_j, a'_j == -a_j, a^_j := -a~_j, if ub was used in transformation
3999 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, a^_j := a~_j, (vlb)
4000 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, a^_j := -a~_j, (vub)
4028 SCIP_CALL( cutsRoundMIR(scip, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, QUAD(f0)) );
4036 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4040 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4056 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4059 SCIP_CALL( postprocessCutQuad(scip, tmpislocal, tmpinds, tmpcoefs, &tmpnnz, QUAD(&rhs), success) );
4063 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), tmpislocal, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz);
4071 SCIP_Real mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, tmpcoefs, QUAD_TO_DBL(rhs), tmpinds, tmpnnz);
4073 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
4198 * Given the aggregation, it is transformed to a mixed knapsack set via complementation (using bounds or variable bounds)
4201 * so one would prefer to have integer coefficients for integer variables which are far away from their bounds in the
4204 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
4216 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4218 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4220 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4223 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4230 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
4232 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
4235 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
4284 /* we only compute bound distance for integer variables; we allocate an array of length aggrrow->nnz to store this, since
4285 * this is the largest number of integer variables. (in contrast to the number of total variables which can be 2 *
4286 * aggrrow->nnz variables: if all are continuous and we use variable bounds to completement, we introduce aggrrow->nnz
4318 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, if vlb is used in transf.
4319 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, if vub is used in transf.
4320 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
4325 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, &freevariable, &localbdsused) );
4333 SCIPdebug( printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE) );
4371 SCIP_CALL( SCIPcalcIntegralScalar(deltacands, nbounddist, -SCIPepsilon(scip), SCIPsumepsilon(scip), (SCIP_Longint)10000, 10000.0, &intscale, &intscalesuccess) );
4441 * x'_j := x_j - lb_j, x_j == x'_j + lb_j, a'_j == a_j, a^_j := a~_j, if lb was used in transformation
4442 * x'_j := ub_j - x_j, x_j == ub_j - x'_j, a'_j == -a_j, a^_j := -a~_j, if ub was used in transformation
4449 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, a^_j := a~_j, (vlb)
4450 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, a^_j := -a~_j, (vub)
4642 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, deltacands[i], ntmpcoefs, minfrac, maxfrac);
4665 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, delta, ntmpcoefs, minfrac, maxfrac);
4675 /* try to improve efficacy by switching complementation of integral variables that are not at their bounds
4693 SCIP_CALL( findBestLb(scip, vars[mksetinds[k]], sol, 0, allowlocal, &bestlb, &simplebnd, &bestlbtype) );
4698 SCIP_CALL( findBestUb(scip, vars[mksetinds[k]], sol, 0, allowlocal, &bestub, &simplebnd, &bestubtype) );
4718 tmpvalues[k - intstart] = varsign[k] == +1 ? bestub - SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) : SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) - bestlb;
4721 newefficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(newrhs), contactivity, contsqrnorm, bestdelta, ntmpcoefs, minfrac, maxfrac);
4733 assert(bestubtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4740 assert(bestlbtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4780 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4784 SCIP_CALL( cutsRoundMIR(scip, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, QUAD(f0)) );
4787 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4791 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4795 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4807 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4821 SCIPdebugMsg(scip, "efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
4828 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4833 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, mksetinds, mksetcoefs, &mksetnnz, QUAD(&mksetrhs), success) );
4837 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz);
4841 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4845 mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, mksetcoefs, QUAD_TO_DBL(mksetrhs), mksetinds, mksetnnz);
4900/* =========================================== flow cover =========================================== */
4912#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
4929 SCIP_Real d1; /**< right hand side of single-node-flow set plus the sum of all \f$ u_j \f$ for \f$ j \in C^- \f$ */
4930 SCIP_Real d2; /**< right hand side of single-node-flow set plus the sum of all \f$ u_j \f$ for \f$ j \in N^- \f$ */
4932 SCIP_Real mp; /**< smallest variable bound coefficient of variable in \f$ C^{++} (min_{j \in C++} u_j) \f$ */
4936/** structure that contains all the data that defines the single-node-flow relaxation of an aggregation row */
4948 SCIP_Real* aggrcoefsbin; /**< aggregation coefficient of the original binary var used to define the
4950 SCIP_Real* aggrcoefscont; /**< aggregation coefficient of the original continuous var used to define the
4952 SCIP_Real* aggrconstants; /**< aggregation constant used to define the continuous variable in the relaxed set */
4955/** get solution value and index of variable lower bound (with binary variable) which is closest to the current LP
4956 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
4957 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
4971 SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
4972 int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
4980 assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
5025 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5033 /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
5037 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
5085/** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
5086 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
5087 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
5101 SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
5102 int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
5110 assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
5155 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5167 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
5215/** determines the bounds to use for constructing the single-node-flow relaxation of a variable in
5225 int varposinrow, /**< position of variable in the rowinds array for which the bounds should be determined */
5229 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5230 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5239 SCIP_BOUNDTYPE* selectedbounds, /**< pointer to store the preferred bound for the transformation */
5267 SCIP_CALL( findBestLb(scip, var, sol, 0, allowlocal, &bestslb[varposinrow], &simplebound, &bestslbtype[varposinrow]) );
5268 SCIP_CALL( findBestUb(scip, var, sol, 0, allowlocal, &bestsub[varposinrow], &simplebound, &bestsubtype[varposinrow]) );
5279 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef, SCIPvarGetName(var), probidx,
5280 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
5282 /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
5285 if( SCIPisInfinity(scip, -bestslb[varposinrow]) && SCIPisInfinity(scip, bestsub[varposinrow]) )
5291 /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
5304 SCIP_CALL( getClosestVlb(scip, var, sol, rowcoefs, binvarused, bestsub[varposinrow], rowcoef, &bestvlb, &bestvlbidx) );
5313 /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
5326 SCIP_CALL( getClosestVub(scip, var, sol, rowcoefs, binvarused, bestslb[varposinrow], rowcoef, &bestvub, &bestvubidx) );
5334 SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
5336 /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
5347 /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
5348 * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
5351 if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
5355 else if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
5360 else if( SCIPisLE(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
5366 assert(SCIPisGT(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
5396/** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
5403 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5404 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5411 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5434 SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
5452 /* array to store whether a binary variable is in the row (-1) or has been used (1) due to variable bound usage */
5466 SCIP_CALL( determineBoundForSNF(scip, sol, vars, rowcoefs, rowinds, i, binvarused, allowlocal, boundswitch,
5467 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
5536 /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
5566 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5594 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5595 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5596 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestsub), QUAD_TO_DBL(rowcoef), bestsub[i], QUAD_TO_DBL(transrhs));
5612 * y'_j = - ( a_j ( y_j - d_j ) + c_j x_j ) with 0 <= y'_j <= - ( a_j l~_j + c_j ) x_j if a_j > 0
5644 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5673 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5674 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5675 snf->ntransvars, SCIPvarGetName(vlbvars[bestlbtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvlbconst), QUAD_TO_DBL(rowcoef),
5718 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5746 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5747 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5748 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestslb), QUAD_TO_DBL(rowcoef), bestslb[i], QUAD_TO_DBL(transrhs));
5765 * y'_j = - ( a_j ( y_j - d_j ) + c_j x_j ) with 0 <= y'_j <= - ( a_j u~_j + c_j ) x_j if a_j < 0,
5794 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5823 /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
5825 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5826 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5827 snf->ntransvars, SCIPvarGetName(vubvars[bestubtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvubconst), QUAD_TO_DBL(rowcoef),
5870 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n", i, QUAD_TO_DBL(rowcoef), SCIPvarGetName(var), probidx, varsolval,
5883 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5910 assert(snf->transvarcoefs[snf->ntransvars] == 1 || snf->transvarcoefs[snf->ntransvars] == - 1 );
5916 SCIPdebugMsg(scip, " --> ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s))\n", snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars,
5990/** solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide
6030 /* allocate memory for temporary array used for sorting; array should contain profits divided by corresponding weights (p_1 / w_1 ... p_n / w_n )*/
6041 SCIPselectWeightedDownRealRealInt(tempsort, profits, items, weights, mediancapacity, nitems, &criticalitem);
6085/** build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished
6100 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6164/** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
6169 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
6170 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
6187/** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
6194 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
6195 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
6218 * i.e., get sets C1 subset N1 and C2 subset N2 with sum_{j in C1} u_j - sum_{j in C2} u_j = b + lambda and lambda > 0
6226 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6270 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
6310 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
6375 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6376 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
6384 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6385 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
6399 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
6411 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6412 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6417 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6418 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6423 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6426 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
6447 * solve KP^SNF_int exactly, if a suitable factor C is found and (nitems*capacity) <= MAXDYNPROGSPACE,
6461 SCIP_CALL( SCIPcalcIntegralScalar(transweightsreal, nitems, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE, &scalar,
6465 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
6500 SCIP_CALL(SCIPsolveKnapsackExactly(scip, nitems, transweightsint, transprofitsint, transcapacityint,
6517 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6525 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6533 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
6535 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6539 /* if the found structure is not a flow cover, because of scaling, solve KP^SNF_rat approximately */
6545 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6547#ifdef SCIP_DEBUG /* this time only for SCIP_DEBUG, because only then, the variable is used again */
6557 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6580 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
6600 * \f${(x,y) in {0,1}^n x R^n : sum_{j in N1} y_j - sum_{j in N2} y_j <= b, 0 <= y_j <= u_j x_j}\f$,
6610 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6645 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
6677 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
6744 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6745 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
6753 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6754 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
6768 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
6776 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6777 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6782 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6783 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6787 transcapacityreal = - snf->transrhs + QUAD_TO_DBL(flowcoverweight) + n1itemsweight; /*lint !e644*/
6788 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6791 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
6813 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
6819 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6825 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
6827 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6850 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
6868/** evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities
6996 int* transvarflowcoverstatus, /**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
7106 SCIP_UNUSED( SCIPsortedvecFindDownReal(liftingdata->m, liftingdata->mp, liftingdata->r, &liftingdata->t) );
7107 assert(liftingdata->m[liftingdata->t] == liftingdata->mp || SCIPisInfinity(scip, liftingdata->mp)); /*lint !e777*/
7113 while( liftingdata->t < liftingdata->r && liftingdata->m[liftingdata->t] == liftingdata->mp ) /*lint !e777*/
7140 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
7218 SCIP_Real liftedbincoef = evaluateLiftingFunction(scip, &liftingdata, snf->transvarvubcoefs[i]);
7401/** calculates a lifted simple generalized flow cover cut out of the weighted sum of LP rows given by an aggregation row; the
7402 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
7406 * Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs.
7409 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7421 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7422 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7426 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
7430 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
7452 SCIPdebug( printCutQuad(scip, sol, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, FALSE, aggrrow->local) );
7454 SCIP_CALL( constructSNFRelaxation(scip, sol, boundswitch, allowlocal, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, &snf, success, &localbdsused) );
7465 SCIP_CALL( getFlowCover(scip, &snf, &nflowcovervars, &nnonflowcovervars, transvarflowcoverstatus, &lambda, success) );
7474 SCIP_CALL( generateLiftedFlowCoverCut(scip, &snf, aggrrow, transvarflowcoverstatus, lambda, tmpcoefs, cutrhs, cutinds, cutnnz, success) );
7477 /* if success is FALSE generateLiftedFlowCoverCut wont have touched the tmpcoefs array so we dont need to clean it then */
7489 *success = ! removeZeros(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutinds, cutnnz);
7531/* =========================================== knapsack cover =========================================== */
7533/** Relax the row to a possibly fractional knapsack row containing no integer or continuous variables
7534 * and only having positive coefficients for binary variables. General integer and continuous variables
7535 * are complemented with variable or simple bounds such that their coefficient becomes positive and then
7537 * All remaining binary variables are complemented with simple upper or lower bounds such that their
7544 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7552 SCIP_Bool* localbdsused, /**< pointer to store whether local bounds were used in transformation */
7553 SCIP_Bool* success /**< stores whether the row could successfully be transformed into a knapsack constraint.
7574 /* start with continuous variables, because using variable bounds can affect the untransformed binary
7575 * variables, and these changes have to be incorporated in the transformation of the binary variables
7583 /* determine best bounds for the continuous and general integer variables such that they will have
7596 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable
7598 SCIP_CALL( findBestLb(scip, vars[v], sol, 1, allowlocal, bestbds + i, &simplebound, boundtype + i) );
7610 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable
7612 SCIP_CALL( findBestUb(scip, vars[v], sol, 1, allowlocal, bestbds + i, &simplebound, boundtype + i) );
7631 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], v, localbdsused);
7640 /* remove non-binary variables because their coefficients have been set to zero after bound substitution */
7648 /* after doing bound substitution of non-binary vars, some coefficients of binary vars might have changed, so here we
7649 * remove the ones that became 0 if any; also, we need that all remaining binary vars have positive coefficients,
7666 /* due to variable bound usage for bound substitution of continuous variables cancellation may have occurred */
7677 SCIP_CALL( findBestUb(scip, vars[v], sol, 0, allowlocal, &bestub, &simplebound, boundtype + i) );
7689 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
7696 SCIP_CALL( findBestLb(scip, vars[v], sol, 0, allowlocal, &bestlb, &simplebound, boundtype + i) );
7701 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
7714 /* increase i or remove zero coefficient (i.e. var with 0 coef) by shifting last nonzero to current position */
7744 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
7748 int* coverstatus, /**< array to return the coverstatus for each variable in the knapsack row */
7823 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(*coverweight), cutrhs);
7834 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
7902 /* now we partition C into C^+ and C^-, where C^+ are all the elements of C whose weight is strictly larger than
7903 * \bar{a} and C^- the rest. If a_i are the weights of the elements in C, let a_i^- = min(a_i, \bar{a}) We also
7904 * compute S^-(h) = sum of the h largest a_i^- and store S^-(h+1) in in covervals[h], for k = 0, ..., coversize - 1
7906 * we remember which elements of C^- in coverstatus, so that element in C^+ have coverstatus 1 and
7920 /* coefficient is in C^+ because it is greater than \bar{a} and contributes only \bar{a} to the sum */
7923 /* rather be on the safe side in numerical corner cases and relax the coefficient to exactly \bar{a}.
7924 * In that case the coefficient is not treated as in C^+ but as being <= \bar{a} and therefore in C^-.
7954 SCIP_Real* scale /**< pointer to update the scale to integrality when a fractional value is returned */
7963 /* the lifted value is at least the coeficient (a_k) divided by \bar{a} because the largest value
7972 /* if the coefficient is below \bar{a}, i.e. a / \bar{a} < 1 then g(a_k) = 0, otherwise g(a_k) > 0 */
7976 /* we perform h = MIN(h, coversize) in floating-point first because on some instances h was seen to exceed the range
7998 /* decrease by one to make sure rounding errors or coefficients that are larger than the right hand side by themselves
8004 * (todo: variables that have a coefficient above the right hand side can get an arbitrarily large coefficient but can
8005 * also be trivially fixed using the base row. Currently they get the coefficient |C| which is 1 above the right hand
8006 * side in the cover cut so that they can still be trivially fixed by propagating the cover cut.
8007 * We do not want to apply fixings here though because the LP should stay flushed during separation.
8008 * Possibly add a parameter to return additional fixings to the caller of the SCIPcalc*() functions in here
8014 /* compare with standard epsilon tolerance since computation involves abar, which is computed like an activity */
8025 SCIPdebugMsg(scip, "lifted coef %g < %g <= %g to %g\n", h == 0 ? 0 : covervals[h-1], QUAD_TO_DBL(x),
8031/** calculates a lifted knapsack cover cut out of the weighted sum of LP rows given by an aggregation row; the
8032 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
8036 * Letchford, A. N., & Souli, G. (2019). On lifted cover inequalities: A new lifting procedure with unusual properties.
8039 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8050 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8054 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8058 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
8135 /* Transform aggregated row into a (fractional, i.e. with possibly fractional weights) knapsack constraint.
8137 * so that only binary variables remain and complements those such that they have a positive coefficient.
8151 if( !computeInitialKnapsackCover(scip, sol, tmpcoefs, tmpinds, QUAD_TO_DBL(rhs), nnz, varsign, coverstatus,
8155 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(coverweight), QUAD_TO_DBL(rhs));
8201 * - h + 1/2 if z = k * \bar{a} for some integer k \in [1, |C^+| - 1] and S^-(h) < z <= S^-(h+1) for some h = 0, ..., coversize -1
8222 { /* variables is either in C^+ or not in the cover and its coefficient value is computed with the lifing function */
8228 SCIPdebugMsg(scip, "coef is QUAD_HI=%g, QUAD_LO=%g, QUAD_TO_DBL = %g\n",QUAD_HI(coef), QUAD_LO(coef), QUAD_TO_DBL(coef));
8231 cutcoef = evaluateLiftingFunctionKnapsack(scip, QUAD(coef), QUAD(abar), covervals, coversize, cplussize, &scale);
8249 /* variable was complemented so we have cutcoef * (1-x) = cutcoef - cutcoef * x.Thus we need to adjust the rhs
8262 /* calculate the efficacy of the computed cut and store the success flag if the efficacy exceeds the
8294 /* calculate efficacy again to make sure it matches the coefficients after they where rounded to double values
8339/* =========================================== strongcg =========================================== */
8344 * Differs from cutsTransformMIR for continuous variables for which the lower bound must be used
8346 * negative. This forces all continuous variable to have a positive coefficient in the transformed
8352 * x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation}\\
8353 * x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation}
8361 * x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\
8362 * x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.}
8365 * move the constant terms \f$ a_j\, dl_j \f$ or \f$ a_j\, du_j \f$ to the rhs, and update the coefficient of the VLB variable:
8377 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8379 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8387 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
8388 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
8409 /* start with continuous variables, because using variable bounds can affect the untransformed integral
8410 * variables, and these changes have to be incorporated in the transformation of the integral variables
8419 /* determine best bounds for the continuous variables such that they will have a positive coefficient in the transformation */
8431 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
8432 SCIP_CALL( findBestLb(scip, vars[v], sol, usevbds ? 2 : 0, allowlocal, bestbds + i, &simplebound, boundtype + i) );
8447 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
8448 SCIP_CALL( findBestUb(scip, vars[v], sol, usevbds ? 2 : 0, allowlocal, bestbds + i, &simplebound, boundtype + i) );
8467 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], cutinds[i], localbdsused);
8472 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
8473 * and perform the bound substitution for the integer variables that are left using simple bounds
8500 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
8501 SCIP_CALL( determineBestBounds(scip, vars[v], sol, boundswitch, 0, allowlocal, FALSE, FALSE, NULL, NULL,
8516 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
8524 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
8544/** Calculate fractionalities \f$ f_0 := b - down(b) \f$, \f$ f_j := a^\prime_j - down(a^\prime_j) \f$,
8545 * integer \f$ k \geq 1 \f$ with \f$ 1/(k + 1) \leq f_0 < 1/k \f$ \f$ (\Rightarrow k = up(1/f_0) - 1) \f$ and
8546 * integer \f$ 1 \leq p_j \leq k \f$ with \f$ f_0 + ((p_j - 1) \cdot (1 - f_0)/k) < f_j \leq f_0 + (p_j (1 - f_0)/k)\f$ \f$ (\Rightarrow p_j = up( k\,(f_j - f_0)/(1 - f_0) )) \f$
8562 * x^\prime_j := x_j - lb_j,& x_j == x^\prime_j + lb_j,& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation} \\
8563 * x^\prime_j := ub_j - x_j,& x_j == ub_j - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation}
8578 * x^\prime_j := x_j - (bl_j * zl_j + dl_j),& x_j == x^\prime_j + (bl_j * zl_j + dl_j),& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\
8579 * x^\prime_j := (bu_j * zu_j + du_j) - x_j,& x_j == (bu_j * zu_j + du_j) - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)}
8592 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\
8605 int* boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)*/
8627 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
8635 /* in debug mode check, that all continuous variables of the aggrrow come before the integral variables */
8688 assert(pj >= 0); /* should be >= 1, but due to rounding bias can be 0 if fj is almost equal to f0 */
8711 /* move the constant term -\tilde{a}_j * lb_j == -a_j * lb_j , or \tilde{a}_j * ub_j == -a_j * ub_j to the rhs */
8734 /* now process the continuous variables; postpone deletion of zeros until all continuous variables have been processed */
8738 /* in a strong CG cut, cut coefficients of continuous variables are always zero; check this in debug mode */
8775 /* fill empty positions of the continuous variables by integral variables; copy all indices to the front or only
8793 * The coefficient of the slack variable \f$s_r\f$ is equal to the row's weight times the slack's sign, because the slack
8794 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r] \f$.
8796 * Depending on the slack's type (integral or continuous), its coefficient in the cut calculates as follows:
8806 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
8885 assert(pr >= 0); /* should be >= 1, but due to rounding bias can be 0 if fr is almost equal to f0 */
8954/** calculates a strong CG cut out of the weighted sum of LP rows given by an aggregation row; the
8955 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
8958 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8970 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8972 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8979 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8983 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
9017 /* terminate if an integral slack fractionality is unreliable or a negative continuous slack variable is present */
9019 if( ( scip->lp->rows[aggrrow->rowsinds[i]]->integral && ABS(aggrrow->rowweights[i] * scale) > large )
9020 || ( !scip->lp->rows[aggrrow->rowsinds[i]]->integral && aggrrow->rowweights[i] * aggrrow->slacksign[i] < 0.0 ) )
9063 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, if vlb is used in transf.
9064 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, if vub is used in transf.
9065 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
9102 * - integer 1 <= p_j <= k with f_0 + ((p_j - 1) * (1 - f_0)/k) < f_j <= f_0 + (p_j * (1 - f_0)/k)
9114 * x'_j := x_j - lb_j, x_j == x'_j + lb_j, a'_j == a_j, a^_j := a~_j, if lb was used in transformation
9115 * x'_j := ub_j - x_j, x_j == ub_j - x'_j, a'_j == -a_j, a^_j := -a~_j, if ub was used in transformation
9122 * x'_j := x_j - (bl_j * zl_j + dl_j), x_j == x'_j + (bl_j * zl_j + dl_j), a'_j == a_j, a^_j := a~_j, (vlb)
9123 * x'_j := (bu_j * zu_j + du_j) - x_j, x_j == (bu_j * zu_j + du_j) - x'_j, a'_j == -a_j, a^_j := -a~_j, (vub)
9148 SCIP_CALL( cutsRoundStrongCG(scip, tmpcoefs, QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, QUAD(f0), k) );
9154 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
9158 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
9166 SCIP_CALL( cutsSubstituteStrongCG(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
9170 /* remove all nearly-zero coefficients from strong CG row and relax the right hand side correspondingly in order to
9175 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, cutinds, tmpcoefs, cutnnz, QUAD(&rhs), success) );
9179 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutinds, cutnnz);
static SCIP_Real computeMIREfficacy(SCIP *scip, SCIP_Real *RESTRICT coefs, SCIP_Real *RESTRICT solvals, SCIP_Real rhs, SCIP_Real contactivity, SCIP_Real contsqrnorm, SCIP_Real delta, int nvars, SCIP_Real minfrac, SCIP_Real maxfrac)
Definition: cuts.c:4130
static SCIP_RETCODE cutsTransformMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
Definition: cuts.c:3052
static void performBoundSubstitutionSimple(SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:2997
static void prepareLiftingData(SCIP *scip, SCIP_Real *cutcoefs, int *cutinds, QUAD(SCIP_Real cutrhs), int *coverpos, int coversize, QUAD(SCIP_Real coverweight), SCIP_Real *covervals, int *coverstatus, QUAD(SCIP_Real *abar), int *cplussize)
Definition: cuts.c:7831
static SCIP_RETCODE cutsTransformKnapsackCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *localbdsused, SCIP_Bool *success)
Definition: cuts.c:7541
static SCIP_RETCODE findBestLb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype)
Definition: cuts.c:2596
static SCIP_Real calcEfficacyDenseStorageQuad(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:396
static SCIP_Bool removeZerosQuad(SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
Definition: cuts.c:471
static SCIP_RETCODE cutsSubstituteStrongCG(SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, QUAD(SCIP_Real f0), SCIP_Real k)
Definition: cuts.c:8809
static SCIP_RETCODE computeLiftingData(SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
Definition: cuts.c:6993
static SCIP_RETCODE getClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestsub, SCIP_Real rowcoef, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: cuts.c:4961
static SCIP_RETCODE getFlowCover(SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
Definition: cuts.c:6605
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, int usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable)
Definition: cuts.c:2718
static SCIP_RETCODE getClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestslb, SCIP_Real rowcoef, SCIP_Real *closestvub, int *closestvubidx)
Definition: cuts.c:5091
static SCIP_RETCODE cutsTransformStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
Definition: cuts.c:8374
static SCIP_Real evaluateLiftingFunctionKnapsack(SCIP *scip, QUAD(SCIP_Real x), QUAD(SCIP_Real abar), SCIP_Real *covervals, int coversize, int cplussize, SCIP_Real *scale)
Definition: cuts.c:7947
static SCIP_Bool chgCoeffWithBound(SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal, QUAD(SCIP_Real *cutrhs))
Definition: cuts.c:701
static SCIP_Bool chgQuadCoeffWithBound(SCIP *scip, SCIP_VAR *var, QUAD(SCIP_Real oldcoeff), SCIP_Real newcoeff, SCIP_Bool cutislocal, QUAD(SCIP_Real *cutrhs))
Definition: cuts.c:746
static SCIP_RETCODE constructSNFRelaxation(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_Real *rowcoefs, QUAD(SCIP_Real rowrhs), int *rowinds, int nnz, SNF_RELAXATION *snf, SCIP_Bool *success, SCIP_Bool *localbdsused)
Definition: cuts.c:5400
static SCIP_RETCODE postprocessCutQuad(SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, QUAD(SCIP_Real *cutrhs), SCIP_Bool *success)
Definition: cuts.c:2412
static SCIP_RETCODE cutsRoundMIR(SCIP *scip, SCIP_Real *RESTRICT cutcoefs, QUAD(SCIP_Real *RESTRICT cutrhs), int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype, QUAD(SCIP_Real f0))
Definition: cuts.c:3408
static void performBoundSubstitution(SCIP *scip, int *cutinds, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *nnz, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:2917
static void destroyLiftingData(SCIP *scip, LIFTINGDATA *liftingdata)
Definition: cuts.c:7123
static SCIP_RETCODE varVecAddScaledRowCoefsQuad(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:174
static SCIP_Real calcEfficacyNormQuad(SCIP *scip, SCIP_Real *vals, int *inds, int nnz)
Definition: cuts.c:334
static SCIP_RETCODE cutTightenCoefs(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
Definition: cuts.c:1168
static SCIP_Bool removeZeros(SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
Definition: cuts.c:564
struct LiftingData LIFTINGDATA
static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT(SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
Definition: cuts.c:5994
static SCIP_RETCODE determineBoundForSNF(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *rowcoefs, int *rowinds, int varposinrow, int8_t *binvarused, SCIP_Bool allowlocal, SCIP_Real boundswitch, SCIP_Real *bestlb, SCIP_Real *bestub, SCIP_Real *bestslb, SCIP_Real *bestsub, int *bestlbtype, int *bestubtype, int *bestslbtype, int *bestsubtype, SCIP_BOUNDTYPE *selectedbounds, SCIP_Bool *freevariable)
Definition: cuts.c:5219
static SCIP_RETCODE postprocessCut(SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, SCIP_Real *cutrhs, SCIP_Bool *success)
Definition: cuts.c:2343
static void destroySNFRelaxation(SCIP *scip, SNF_RELAXATION *snf)
Definition: cuts.c:5974
static SCIP_RETCODE allocSNFRelaxation(SCIP *scip, SNF_RELAXATION *snf, int nvars)
Definition: cuts.c:5953
static SCIP_RETCODE cutsRoundStrongCG(SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k)
Definition: cuts.c:8598
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:269
static void buildFlowCover(SCIP *scip, int *coefs, SCIP_Real *vubcoefs, SCIP_Real rhs, int *solitems, int *nonsolitems, int nsolitems, int nnonsolitems, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, QUAD(SCIP_Real *flowcoverweight), SCIP_Real *lambda)
Definition: cuts.c:6089
static SCIP_RETCODE generateLiftedFlowCoverCut(SCIP *scip, SNF_RELAXATION *snf, SCIP_AGGRROW *aggrrow, int *flowcoverstatus, SCIP_Real lambda, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, SCIP_Bool *success)
Definition: cuts.c:7136
static void getAlphaAndBeta(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
Definition: cuts.c:6956
static SCIP_RETCODE cutsSubstituteMIR(SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, QUAD(SCIP_Real f0))
Definition: cuts.c:3719
static SCIP_RETCODE addOneRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *rowtoolong)
Definition: cuts.c:2170
static SCIP_RETCODE varVecAddScaledRowCoefsQuadScale(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, QUAD(SCIP_Real scale))
Definition: cuts.c:221
struct SNF_Relaxation SNF_RELAXATION
static SCIP_RETCODE cutTightenCoefsQuad(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
Definition: cuts.c:793
static SCIP_Real evaluateLiftingFunction(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
Definition: cuts.c:6872
static SCIP_RETCODE varVecAddScaledRowCoefs(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:129
static SCIP_RETCODE findBestUb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype)
Definition: cuts.c:2657
static SCIP_Bool computeInitialKnapsackCover(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real cutrhs, int cutnnz, int *varsign, int *coverstatus, int *coverpos, SCIP_Real *covervals, int *coversize, QUAD(SCIP_Real *coverweight))
Definition: cuts.c:7740
methods for the aggregation rows
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
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:1086
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
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:9560
void SCIPaggrRowCancelVarWithBound(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
Definition: cuts.c:1945
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
Definition: cuts.c:2518
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:4212
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:1527
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1723
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:8966
SCIP_RETCODE SCIPcalcKnapsackCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:8047
SCIP_RETCODE SCIPaggrRowCopy(SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
Definition: cuts.c:1813
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPaggrRowAddCustomCons(SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
Definition: cuts.c:2080
void SCIPaggrRowPrint(SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
Definition: cuts.c:1776
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition: cuts.c:2471
SCIP_Real * SCIPaggrRowGetRowWeights(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2507
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition: cuts.c:1859
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition: cuts.c:2279
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition: cuts.c:2004
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:7417
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2158
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:3873
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#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_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1939
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1956
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:705
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition: scip_var.c:6755
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: scip_var.c:6732
void SCIPselectWeightedDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, int len)
SCIP_Bool SCIPsortedvecFindDownReal(SCIP_Real *realarray, SCIP_Real val, int len, int *pos)
void SCIPsortDownReal(SCIP_Real *realarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortDownInt(int *intarray, int len)
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *intval)
Definition: lp.c:4900
internal methods for LP management
memory allocation routines
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
Definition: objbenders.h:44
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
methods for sorting joint arrays of various types
public methods for problem variables
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for SCIP variables
Definition: cuts.c:4919
Definition: struct_cuts.h:41
Definition: struct_message.h:46
Definition: struct_lp.h:202
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: cuts.c:4939
Definition: struct_scip.h:70
data structures for LP management
SCIP main data structure.
datastructures for global SCIP settings