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) );
921 if( chgQuadCoeffWithBound(scip, vars[cutinds[i]], QUAD(val), intval, cutislocal, QUAD(cutrhs)) )
961 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
971 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1044 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1050 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1065 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1068 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1074 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1088 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1112 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1115 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1121 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1135 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1159 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1168 /** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1169 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
1177 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1199 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1212 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1230 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1278 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
1279 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1339 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1348 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1408 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1414 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1432 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1438 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1452 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1478 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1484 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1498 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1521 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1530 /** perform activity based coefficient tightening on the given cut; returns TRUE if the cut was detected
1540 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1574 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1592 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1619 /* terminate, because coefficient tightening cannot be performed; also excludes the case in which no integral variable is present */
1626 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1629 /* due to sorting, we can exit if we reached a continuous variable: all further integral variables have 0 coefficents anyway */
1638 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1651 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1679 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1692 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1717 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1727 /* =========================================== aggregation row =========================================== */
1813 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", QUAD_TO_DBL(val), SCIPvarGetName(vars[aggrrow->inds[i]]));
1836 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->vals, source->vals, QUAD_ARRAY_SIZE(nvars)) );
1847 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowsinds, source->rowsinds, source->nrows) );
1848 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->slacksign, source->slacksign, source->nrows) );
1849 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowweights, source->rowweights, source->nrows) );
1893 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
1894 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
1895 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
1913 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
1941 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
1946 /** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
1947 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
1949 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
1951 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
2011 /** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
2162 /** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2164 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2174 /** Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional
2185 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2198 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
2217 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
2222 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
2263 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2264 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2265 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2275 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
2295 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2321 SCIP_CALL( addOneRow(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2333 SCIP_CALL( addOneRow(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2358 SCIP_Bool* success /**< pointer to return whether post-processing was succesful or cut is redundant */
2386 SCIP_CALL( cutTightenCoefs(scip, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz, &redundant) );
2405 *success = ! removeZeros(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz);
2427 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
2443 if( removeZerosQuad(scip, SCIPfeastol(scip), cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz) )
2452 SCIP_CALL( cutTightenCoefsQuad(scip, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz, &redundant) );
2473 *success = ! removeZerosQuad(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz);
2489 *valid = ! removeZerosQuad(scip, SCIPsumepsilon(scip), useglbbounds ? FALSE : aggrrow->local, aggrrow->vals,
2548 /** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
2598 /* =========================================== c-MIR =========================================== */
2608 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2609 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2641 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
2645 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2646 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2669 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2670 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2702 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
2706 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2707 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2724 /** determine the best bounds with respect to the given solution for complementing the given variable */
2730 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
2731 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
2732 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2733 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
2735 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
2738 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
2744 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
2757 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || ( boundsfortrans[v] == -2 || boundsfortrans[v] == -1 ));
2788 *bestlb = vlbcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vlbvars[k]) : SCIPgetSolVal(scip, sol, vlbvars[k])) + vlbconsts[k];
2794 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2795 SCIP_CALL( findBestUb(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
2826 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2827 *bestub = vubcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vubvars[k]) : SCIPgetSolVal(scip, sol, vubvars[k])) + vubconsts[k];
2833 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2834 SCIP_CALL( findBestLb(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
2843 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2846 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2876 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
2923 /** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index */
2934 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
2936 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
3003 /** performs the bound substitution step with the simple bound for the variable with the given problem index */
3011 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
3013 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
3038 * 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},\\
3039 * 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},
3047 * 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.} \\
3048 * 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.}
3051 * 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:
3063 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3065 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3066 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3068 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3071 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3082 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
3083 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
3113 /* start with continuous variables, because using variable bounds can affect the untransformed integral
3114 * variables, and these changes have to be incorporated in the transformation of the integral variables
3126 SCIP_CALL( determineBestBounds(scip, vars[cutinds[i]], sol, boundswitch, usevbds ? 2 : 0, allowlocal, fixintegralrhs,
3128 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3150 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestlbs[i], v, localbdsused);
3160 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestubs[i], v, localbdsused);
3164 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
3186 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
3189 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3198 /* now perform the bound substitution on the remaining integral variables which only uses standard bounds */
3213 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlbs[i], v, localbdsused);
3224 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestubs[i], v, localbdsused);
3306 /* prefer larger violations; for equal violations, prefer smaller f0 values since then the possibility that
3309 if( SCIPisGT(scip, violgain, bestviolgain) || (SCIPisGE(scip, violgain, bestviolgain) && newf0 < bestnewf0) )
3337 assert(bestubtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3344 assert(bestlbtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3365 /** 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$
3380 * 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}, \\
3381 * 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},
3396 * 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)} \\
3397 * 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)}
3410 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
3420 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
3423 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
3445 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
3453 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
3521 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3556 /* now process the continuous variables; postpone deletion of zeros untill all continuous variables have been processed */
3604 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3711 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
3712 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r]. \f$
3714 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
3718 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f_0)/(1 - f_0),& \mbox{if}\qquad f_r > f_0 \\
3724 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
3870 /** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
3873 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3885 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3887 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3888 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3889 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3892 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3898 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
3899 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
3900 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
3901 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
3903 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
3904 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
3905 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
3971 * 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.
3972 * 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.
3973 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
3977 SCIP_CALL( cutsTransformMIR(scip, sol, boundswitch, usevbds, allowlocal, fixintegralrhs, FALSE,
3978 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
3999 * 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
4000 * 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
4007 * 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)
4008 * 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)
4036 SCIP_CALL( cutsRoundMIR(scip, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, QUAD(f0)) );
4044 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4048 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4064 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4067 SCIP_CALL( postprocessCutQuad(scip, tmpislocal, tmpinds, tmpcoefs, &tmpnnz, QUAD(&rhs), success) );
4071 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), tmpislocal, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz);
4079 SCIP_Real mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, tmpcoefs, QUAD_TO_DBL(rhs), tmpinds, tmpnnz);
4081 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
4206 * Given the aggregation, it is transformed to a mixed knapsack set via complementation (using bounds or variable bounds)
4209 * so one would prefer to have integer coefficients for integer variables which are far away from their bounds in the
4212 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
4224 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4226 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4228 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4231 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4238 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
4240 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
4243 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
4292 /* we only compute bound distance for integer variables; we allocate an array of length aggrrow->nnz to store this, since
4293 * this is the largest number of integer variables. (in contrast to the number of total variables which can be 2 *
4294 * aggrrow->nnz variables: if all are continuous and we use variable bounds to completement, we introduce aggrrow->nnz
4326 * 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.
4327 * 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.
4328 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
4333 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, &freevariable, &localbdsused) );
4341 SCIPdebug( printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE) );
4379 SCIP_CALL( SCIPcalcIntegralScalar(deltacands, nbounddist, -SCIPepsilon(scip), SCIPsumepsilon(scip), (SCIP_Longint)10000, 10000.0, &intscale, &intscalesuccess) );
4449 * 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
4450 * 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
4457 * 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)
4458 * 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)
4650 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, deltacands[i], ntmpcoefs, minfrac, maxfrac);
4673 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, delta, ntmpcoefs, minfrac, maxfrac);
4683 /* try to improve efficacy by switching complementation of integral variables that are not at their bounds
4701 SCIP_CALL( findBestLb(scip, vars[mksetinds[k]], sol, 0, allowlocal, &bestlb, &simplebnd, &bestlbtype) );
4706 SCIP_CALL( findBestUb(scip, vars[mksetinds[k]], sol, 0, allowlocal, &bestub, &simplebnd, &bestubtype) );
4726 tmpvalues[k - intstart] = varsign[k] == +1 ? bestub - SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) : SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) - bestlb;
4729 newefficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(newrhs), contactivity, contsqrnorm, bestdelta, ntmpcoefs, minfrac, maxfrac);
4741 assert(bestubtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4748 assert(bestlbtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4788 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4792 SCIP_CALL( cutsRoundMIR(scip, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, QUAD(f0)) );
4795 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4799 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4803 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4815 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4829 SCIPdebugMsg(scip, "efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
4836 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4841 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, mksetinds, mksetcoefs, &mksetnnz, QUAD(&mksetrhs), success) );
4845 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz);
4849 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4853 mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, mksetcoefs, QUAD_TO_DBL(mksetrhs), mksetinds, mksetnnz);
4908 /* =========================================== flow cover =========================================== */
4920 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
4937 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$ */
4938 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$ */
4940 SCIP_Real mp; /**< smallest variable bound coefficient of variable in \f$ C^{++} (min_{j \in C++} u_j) \f$ */
4944 /** structure that contains all the data that defines the single-node-flow relaxation of an aggregation row */
4956 SCIP_Real* aggrcoefsbin; /**< aggregation coefficient of the original binary var used to define the
4958 SCIP_Real* aggrcoefscont; /**< aggregation coefficient of the original continuous var used to define the
4960 SCIP_Real* aggrconstants; /**< aggregation constant used to define the continuous variable in the relaxed set */
4963 /** get solution value and index of variable lower bound (with binary variable) which is closest to the current LP
4964 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
4965 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
4979 SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
4980 int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
4988 assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
5033 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5041 /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
5045 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
5093 /** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
5094 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
5095 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
5109 SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
5110 int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
5118 assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
5163 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5175 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
5223 /** determines the bounds to use for constructing the single-node-flow relaxation of a variable in
5233 int varposinrow, /**< position of variable in the rowinds array for which the bounds should be determined */
5237 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5238 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5247 SCIP_BOUNDTYPE* selectedbounds, /**< pointer to store the preferred bound for the transformation */
5275 SCIP_CALL( findBestLb(scip, var, sol, 0, allowlocal, &bestslb[varposinrow], &simplebound, &bestslbtype[varposinrow]) );
5276 SCIP_CALL( findBestUb(scip, var, sol, 0, allowlocal, &bestsub[varposinrow], &simplebound, &bestsubtype[varposinrow]) );
5287 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef, SCIPvarGetName(var), probidx,
5288 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
5290 /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
5293 if( SCIPisInfinity(scip, -bestslb[varposinrow]) && SCIPisInfinity(scip, bestsub[varposinrow]) )
5299 /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
5312 SCIP_CALL( getClosestVlb(scip, var, sol, rowcoefs, binvarused, bestsub[varposinrow], rowcoef, &bestvlb, &bestvlbidx) );
5321 /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
5334 SCIP_CALL( getClosestVub(scip, var, sol, rowcoefs, binvarused, bestslb[varposinrow], rowcoef, &bestvub, &bestvubidx) );
5342 SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
5344 /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
5355 /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
5356 * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
5359 if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
5363 else if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
5368 else if( SCIPisLE(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
5374 assert(SCIPisGT(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
5404 /** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
5411 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5412 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5419 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5442 SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
5460 /* array to store whether a binary variable is in the row (-1) or has been used (1) due to variable bound usage */
5474 SCIP_CALL( determineBoundForSNF(scip, sol, vars, rowcoefs, rowinds, i, binvarused, allowlocal, boundswitch,
5475 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
5544 /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
5574 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5602 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5603 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5604 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestsub), QUAD_TO_DBL(rowcoef), bestsub[i], QUAD_TO_DBL(transrhs));
5620 * 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
5652 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5681 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5682 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5683 snf->ntransvars, SCIPvarGetName(vlbvars[bestlbtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvlbconst), QUAD_TO_DBL(rowcoef),
5726 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5754 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5755 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5756 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestslb), QUAD_TO_DBL(rowcoef), bestslb[i], QUAD_TO_DBL(transrhs));
5773 * 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,
5802 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5831 /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
5833 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5834 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5835 snf->ntransvars, SCIPvarGetName(vubvars[bestubtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvubconst), QUAD_TO_DBL(rowcoef),
5878 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n", i, QUAD_TO_DBL(rowcoef), SCIPvarGetName(var), probidx, varsolval,
5891 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5918 assert(snf->transvarcoefs[snf->ntransvars] == 1 || snf->transvarcoefs[snf->ntransvars] == - 1 );
5924 SCIPdebugMsg(scip, " --> ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s))\n", snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars,
5998 /** solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide
6038 /* allocate memory for temporary array used for sorting; array should contain profits divided by corresponding weights (p_1 / w_1 ... p_n / w_n )*/
6049 SCIPselectWeightedDownRealRealInt(tempsort, profits, items, weights, mediancapacity, nitems, &criticalitem);
6093 /** build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished
6108 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6172 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
6177 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
6178 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
6195 /** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
6202 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
6203 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
6226 * 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
6234 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6278 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
6318 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
6383 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6384 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
6392 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6393 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
6407 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
6419 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6420 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6425 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6426 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6431 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6434 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
6455 * solve KP^SNF_int exactly, if a suitable factor C is found and (nitems*capacity) <= MAXDYNPROGSPACE,
6469 SCIP_CALL( SCIPcalcIntegralScalar(transweightsreal, nitems, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE, &scalar,
6473 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
6508 SCIP_CALL(SCIPsolveKnapsackExactly(scip, nitems, transweightsint, transprofitsint, transcapacityint,
6525 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6533 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6541 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
6543 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6547 /* if the found structure is not a flow cover, because of scaling, solve KP^SNF_rat approximately */
6553 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6555 #ifdef SCIP_DEBUG /* this time only for SCIP_DEBUG, because only then, the variable is used again */
6565 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6588 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
6608 * \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$,
6618 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
6653 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
6685 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
6752 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6753 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
6761 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
6762 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
6776 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
6784 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6785 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6790 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6791 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
6795 transcapacityreal = - snf->transrhs + QUAD_TO_DBL(flowcoverweight) + n1itemsweight; /*lint !e644*/
6796 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6799 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
6821 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
6827 SCIP_CALL(SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
6833 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
6835 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
6858 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
6876 /** evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities
7004 int* transvarflowcoverstatus, /**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
7114 SCIP_UNUSED( SCIPsortedvecFindDownReal(liftingdata->m, liftingdata->mp, liftingdata->r, &liftingdata->t) );
7115 assert(liftingdata->m[liftingdata->t] == liftingdata->mp || SCIPisInfinity(scip, liftingdata->mp)); /*lint !e777*/
7121 while( liftingdata->t < liftingdata->r && liftingdata->m[liftingdata->t] == liftingdata->mp ) /*lint !e777*/
7148 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
7226 SCIP_Real liftedbincoef = evaluateLiftingFunction(scip, &liftingdata, snf->transvarvubcoefs[i]);
7409 /** calculates a lifted simple generalized flow cover cut out of the weighted sum of LP rows given by an aggregation row; the
7410 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
7414 * Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs.
7417 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7429 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7430 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7434 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
7438 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
7460 SCIPdebug( printCutQuad(scip, sol, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, FALSE, aggrrow->local) );
7462 SCIP_CALL( constructSNFRelaxation(scip, sol, boundswitch, allowlocal, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, &snf, success, &localbdsused) );
7473 SCIP_CALL( getFlowCover(scip, &snf, &nflowcovervars, &nnonflowcovervars, transvarflowcoverstatus, &lambda, success) );
7482 SCIP_CALL( generateLiftedFlowCoverCut(scip, &snf, aggrrow, transvarflowcoverstatus, lambda, tmpcoefs, cutrhs, cutinds, cutnnz, success) );
7485 /* if success is FALSE generateLiftedFlowCoverCut wont have touched the tmpcoefs array so we dont need to clean it then */
7497 *success = ! removeZeros(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutinds, cutnnz);
7539 /* =========================================== knapsack cover =========================================== */
7541 /** Relax the row to a possibly fractional knapsack row containing no integer or continuous variables
7542 * and only having positive coefficients for binary variables. General integer and continuous variables
7543 * are complemented with variable or simple bounds such that their coefficient becomes positive and then
7545 * All remaining binary variables are complemented with simple upper or lower bounds such that their
7552 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7560 SCIP_Bool* localbdsused, /**< pointer to store whether local bounds were used in transformation */
7561 SCIP_Bool* success /**< stores whether the row could successfully be transformed into a knapsack constraint.
7582 /* start with continuous variables, because using variable bounds can affect the untransformed binary
7583 * variables, and these changes have to be incorporated in the transformation of the binary variables
7591 /* determine best bounds for the continuous and general integer variables such that they will have
7604 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable
7606 SCIP_CALL( findBestLb(scip, vars[v], sol, 1, allowlocal, bestbds + i, &simplebound, boundtype + i) );
7618 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable
7620 SCIP_CALL( findBestUb(scip, vars[v], sol, 1, allowlocal, bestbds + i, &simplebound, boundtype + i) );
7639 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], v, localbdsused);
7648 /* remove non-binary variables because their coefficients have been set to zero after bound substitution */
7656 /* after doing bound substitution of non-binary vars, some coefficients of binary vars might have changed, so here we
7657 * remove the ones that became 0 if any; also, we need that all remaining binary vars have positive coefficients,
7674 /* due to variable bound usage for bound substitution of continuous variables cancellation may have occurred */
7685 SCIP_CALL( findBestUb(scip, vars[v], sol, 0, allowlocal, &bestub, &simplebound, boundtype + i) );
7697 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
7704 SCIP_CALL( findBestLb(scip, vars[v], sol, 0, allowlocal, &bestlb, &simplebound, boundtype + i) );
7709 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
7722 /* increase i or remove zero coefficient (i.e. var with 0 coef) by shifting last nonzero to current position */
7752 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
7756 int* coverstatus, /**< array to return the coverstatus for each variable in the knapsack row */
7831 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(*coverweight), cutrhs);
7842 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
7910 /* now we partition C into C^+ and C^-, where C^+ are all the elements of C whose weight is strictly larger than
7911 * \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
7912 * compute S^-(h) = sum of the h largest a_i^- and store S^-(h+1) in in covervals[h], for k = 0, ..., coversize - 1
7914 * we remember which elements of C^- in coverstatus, so that element in C^+ have coverstatus 1 and
7928 /* coefficient is in C^+ because it is greater than \bar{a} and contributes only \bar{a} to the sum */
7931 /* rather be on the safe side in numerical corner cases and relax the coefficient to exactly \bar{a}.
7932 * In that case the coefficient is not treated as in C^+ but as being <= \bar{a} and therefore in C^-.
7962 SCIP_Real* scale /**< pointer to update the scale to integrality when a fractional value is returned */
7971 /* the lifted value is at least the coeficient (a_k) divided by \bar{a} because the largest value
7980 /* if the coefficient is below \bar{a}, i.e. a / \bar{a} < 1 then g(a_k) = 0, otherwise g(a_k) > 0 */
7984 /* we perform h = MIN(h, coversize) in floating-point first because on some instances h was seen to exceed the range
8006 /* decrease by one to make sure rounding errors or coefficients that are larger than the right hand side by themselves
8012 * (todo: variables that have a coefficient above the right hand side can get an arbitrarily large coefficient but can
8013 * also be trivially fixed using the base row. Currently they get the coefficient |C| which is 1 above the right hand
8014 * side in the cover cut so that they can still be trivially fixed by propagating the cover cut.
8015 * We do not want to apply fixings here though because the LP should stay flushed during separation.
8016 * Possibly add a parameter to return additional fixings to the caller of the SCIPcalc*() functions in here
8022 /* compare with standard epsilon tolerance since computation involves abar, which is computed like an activity */
8033 SCIPdebugMsg(scip, "lifted coef %g < %g <= %g to %g\n", h == 0 ? 0 : covervals[h-1], QUAD_TO_DBL(x),
8039 /** calculates a lifted knapsack cover cut out of the weighted sum of LP rows given by an aggregation row; the
8040 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
8044 * Letchford, A. N., & Souli, G. (2019). On lifted cover inequalities: A new lifting procedure with unusual properties.
8047 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8058 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8062 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8066 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
8143 /* Transform aggregated row into a (fractional, i.e. with possibly fractional weights) knapsack constraint.
8145 * so that only binary variables remain and complements those such that they have a positive coefficient.
8159 if( !computeInitialKnapsackCover(scip, sol, tmpcoefs, tmpinds, QUAD_TO_DBL(rhs), nnz, varsign, coverstatus,
8163 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(coverweight), QUAD_TO_DBL(rhs));
8209 * - 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
8230 { /* variables is either in C^+ or not in the cover and its coefficient value is computed with the lifing function */
8236 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));
8239 cutcoef = evaluateLiftingFunctionKnapsack(scip, QUAD(coef), QUAD(abar), covervals, coversize, cplussize, &scale);
8257 /* variable was complemented so we have cutcoef * (1-x) = cutcoef - cutcoef * x.Thus we need to adjust the rhs
8270 /* calculate the efficacy of the computed cut and store the success flag if the efficacy exceeds the
8302 /* calculate efficacy again to make sure it matches the coefficients after they where rounded to double values
8347 /* =========================================== strongcg =========================================== */
8352 * Differs from cutsTransformMIR for continuous variables for which the lower bound must be used
8354 * negative. This forces all continuous variable to have a positive coefficient in the transformed
8360 * 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}\\
8361 * 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}
8369 * 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.} \\
8370 * 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.}
8373 * 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:
8385 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8387 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8395 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
8396 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
8417 /* start with continuous variables, because using variable bounds can affect the untransformed integral
8418 * variables, and these changes have to be incorporated in the transformation of the integral variables
8427 /* determine best bounds for the continuous variables such that they will have a positive coefficient in the transformation */
8439 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
8440 SCIP_CALL( findBestLb(scip, vars[v], sol, usevbds ? 2 : 0, allowlocal, bestbds + i, &simplebound, boundtype + i) );
8455 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
8456 SCIP_CALL( findBestUb(scip, vars[v], sol, usevbds ? 2 : 0, allowlocal, bestbds + i, &simplebound, boundtype + i) );
8475 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], cutinds[i], localbdsused);
8480 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
8481 * and perform the bound substitution for the integer variables that are left using simple bounds
8508 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
8509 SCIP_CALL( determineBestBounds(scip, vars[v], sol, boundswitch, 0, allowlocal, FALSE, FALSE, NULL, NULL,
8524 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
8532 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
8552 /** Calculate fractionalities \f$ f_0 := b - down(b) \f$, \f$ f_j := a^\prime_j - down(a^\prime_j) \f$,
8553 * 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
8554 * 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$
8570 * 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} \\
8571 * 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}
8586 * 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)} \\
8587 * 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)}
8600 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\
8613 int* boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)*/
8635 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
8643 /* in debug mode check, that all continuous variables of the aggrrow come before the integral variables */
8696 assert(pj >= 0); /* should be >= 1, but due to rounding bias can be 0 if fj is almost equal to f0 */
8719 /* 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 */
8742 /* now process the continuous variables; postpone deletion of zeros until all continuous variables have been processed */
8746 /* in a strong CG cut, cut coefficients of continuous variables are always zero; check this in debug mode */
8783 /* fill empty positions of the continuous variables by integral variables; copy all indices to the front or only
8801 * 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
8802 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r] \f$.
8804 * Depending on the slack's type (integral or continuous), its coefficient in the cut calculates as follows:
8814 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
8893 assert(pr >= 0); /* should be >= 1, but due to rounding bias can be 0 if fr is almost equal to f0 */
8962 /** calculates a strong CG cut out of the weighted sum of LP rows given by an aggregation row; the
8963 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
8966 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8978 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8980 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8987 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8991 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
9025 /* terminate if an integral slack fractionality is unreliable or a negative continuous slack variable is present */
9027 if( ( scip->lp->rows[aggrrow->rowsinds[i]]->integral && ABS(aggrrow->rowweights[i] * scale) > large )
9028 || ( !scip->lp->rows[aggrrow->rowsinds[i]]->integral && aggrrow->rowweights[i] * aggrrow->slacksign[i] < 0.0 ) )
9071 * 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.
9072 * 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.
9073 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
9110 * - 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)
9122 * 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
9123 * 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
9130 * 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)
9131 * 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)
9156 SCIP_CALL( cutsRoundStrongCG(scip, tmpcoefs, QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, QUAD(f0), k) );
9162 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
9166 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
9174 SCIP_CALL( cutsSubstituteStrongCG(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
9178 /* remove all nearly-zero coefficients from strong CG row and relax the right hand side correspondingly in order to
9183 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, cutinds, tmpcoefs, cutnnz, QUAD(&rhs), success) );
9187 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutinds, cutnnz);
void SCIPsortDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, int len)
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:2420
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
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:8974
static SCIP_RETCODE computeLiftingData(SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
Definition: cuts.c:7001
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:1094
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:69
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:7955
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition: cuts.c:1867
static SCIP_RETCODE varVecAddScaledRowCoefsQuad(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:174
public methods for memory management
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
Definition: struct_cuts.h:40
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:2925
void SCIPaggrRowCancelVarWithBound(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
Definition: cuts.c:1953
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
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:6002
Definition: struct_var.h:207
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:4138
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
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:7144
struct LiftingData LIFTINGDATA
methods for the aggregation rows
Definition: struct_message.h:45
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:8382
Definition: type_var.h:62
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:4220
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:3727
static SCIP_Real evaluateLiftingFunction(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
Definition: cuts.c:6880
public methods for problem variables
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:2665
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:8055
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPaggrRowPrint(SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
Definition: cuts.c:1784
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
public methods for SCIP variables
Definition: cuts.c:4945
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:7839
internal methods for LP management
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: scip_var.c:6608
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1956
static void getAlphaAndBeta(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
Definition: cuts.c:6964
public methods for numerical tolerances
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
Definition: cuts.c:2526
static void destroyLiftingData(SCIP *scip, LIFTINGDATA *liftingdata)
Definition: cuts.c:7131
public methods for querying solving statistics
Definition: cuts.c:4925
Definition: struct_sol.h:73
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition: cuts.c:2012
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:1172
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
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
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
static SCIP_RETCODE varVecAddScaledRowCoefs(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:129
SCIP_Bool SCIPsortedvecFindDownReal(SCIP_Real *realarray, SCIP_Real val, int len, int *pos)
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *intval)
Definition: lp.c:4900
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
Definition: type_retcode.h:51
Definition: type_lp.h:56
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
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_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:3060
Definition: type_retcode.h:42
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition: cuts.c:2479
SCIP main data structure.
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition: scip_var.c:6631
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
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:2088
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:4969
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 allocSNFRelaxation(SCIP *scip, SNF_RELAXATION *snf, int nvars)
Definition: cuts.c:5961
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:3881
public data structures and miscellaneous methods
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:8817
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2166
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:1535
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:705
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:7425
Definition: type_var.h:63
Definition: struct_lp.h:201
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:5227
public methods for LP management
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
public methods for cuts and aggregation rows
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:5408
SCIP_Real * SCIPaggrRowGetRowWeights(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:2515
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:8606
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:2178
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:5099
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
struct SNF_Relaxation SNF_RELAXATION
public methods for the LP relaxation, rows and columns
methods for sorting joint arrays of various types
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:3416
SCIP_RETCODE SCIPaggrRowCopy(SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
Definition: cuts.c:1821
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
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:2726
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:2287
void SCIPselectWeightedDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
public methods for solutions
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
Definition: type_lp.h:57
static void destroySNFRelaxation(SCIP *scip, SNF_RELAXATION *snf)
Definition: cuts.c:5982
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:6097
public methods for message output
data structures for LP management
Definition: type_lpi.h:91
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
void SCIPsortDownInt(int *intarray, int len)
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:2351
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1939
public methods for message handling
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:2604
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1731
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:9557
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
static SCIP_RETCODE getFlowCover(SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
Definition: cuts.c:6613
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:7549
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:7748
Definition: objbenders.h:43
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
datastructures for global SCIP settings
static SCIP_Real calcEfficacyDenseStorageQuad(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:396
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:3005
void SCIPsortDownReal(SCIP_Real *realarray, int len)
Definition: type_lpi.h:93
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:269
methods for selecting (weighted) k-medians
memory allocation routines
Definition: type_var.h:71