cuts.c
Go to the documentation of this file.
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 /* =========================================== general static functions =========================================== */
81 SCIPquadprecProdQD(coef, coef, (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]])));
87 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]])));
91 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]])));
115 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
158 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
203 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
226 /** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter */
230 SCIP_Real* vals, /**< array of the non-zero coefficients in the vector; this is a quad precision array! */
231 int* inds, /**< array of the problem indices of variables with a non-zero coefficient in the vector */
288 /** calculates the cuts efficacy for the given solution; the cut coefs are stored densely and in quad precision */
293 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
295 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
323 /** safely remove all items with |a_i| or |u_i - l_i)| below the given value; returns TRUE if the cut became redundant
333 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
411 /** safely remove all items with |a_i| or |u_i - l_i)| below the given value; returns TRUE if the cut became redundant
421 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
430 /* loop over non-zeros and remove values below minval; values above QUAD_EPSILON are cancelled with their bound
540 /** change given coefficient to new given value, adjust right hand side using the variables bound;
582 /** change given (quad) coefficient to new given value, adjust right hand side using the variables bound;
625 /** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
626 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse quad precision array;
634 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
658 /* compute the maximum activity and maximum absolute coefficient values for all and for integral variables in the cut */
670 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
689 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
740 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
761 if( chgQuadCoeffWithBound(scip, vars[cutinds[i]], QUAD(val), intval, cutislocal, QUAD(cutrhs)) )
801 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
811 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
884 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
890 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
908 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
931 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
955 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
958 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
981 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1004 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1013 /** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1014 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
1022 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1056 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1073 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1123 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPepsilon(scip),
1124 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1183 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1193 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1254 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1260 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1278 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1300 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1326 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1348 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1371 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1380 /** perform activity based coefficient tightening on the given cut; returns TRUE if the cut was detected
1388 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1421 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1440 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1468 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1475 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1489 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1502 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1530 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1543 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1568 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1580 /* =========================================== aggregation row =========================================== */
1665 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", QUAD_TO_DBL(val), SCIPvarGetName(vars[aggrrow->inds[i]]));
1688 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->vals, source->vals, QUAD_ARRAY_SIZE(nvars)) );
1699 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowsinds, source->rowsinds, source->nrows) );
1700 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->slacksign, source->slacksign, source->nrows) );
1701 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowweights, source->rowweights, source->nrows) );
1746 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
1747 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
1748 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
1766 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
1794 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
1799 /** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
1800 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
1802 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
1804 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
1862 /** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
2005 /** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2007 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
2017 /** Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional
2028 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2040 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
2059 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
2064 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
2104 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2105 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2106 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2116 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
2136 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
2162 SCIP_CALL( addOneRow(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2174 SCIP_CALL( addOneRow(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2199 SCIP_Bool* success /**< pointer to return whether post-processing was succesful or cut is redundant */
2227 SCIP_CALL( cutTightenCoefs(scip, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz, &redundant) );
2246 *success = ! removeZeros(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz);
2268 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
2284 if( removeZerosQuad(scip, SCIPfeastol(scip), cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz) )
2293 SCIP_CALL( cutTightenCoefsQuad(scip, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz, &redundant) );
2314 *success = ! removeZerosQuad(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz);
2330 *valid = ! removeZerosQuad(scip, SCIPsumepsilon(scip), useglbbounds ? FALSE : aggrrow->local, aggrrow->vals,
2389 /** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
2440 * for the given cut; moves filtered cuts to the end of the array and returns number of selected cuts */
2477 /** move the cut with the highest score to the first position in the array; there must be at least one cut */
2523 SCIP_Real efficacyweight, /**< weight of efficacy (shortest cutoff distance) in score calculation */
2557 /* if there is an incumbent and the factor is not 0.0, compute directed cutoff distances for the incumbent */
2567 intsupportweight * SCIProwGetNumIntCols(cuts[i], scip->set) / (SCIP_Real) SCIProwGetNNonz(cuts[i]) :
2570 objparallelism = objparalweight != 0.0 ? objparalweight * SCIProwGetObjParallelism(cuts[i], scip->set, scip->lp) : 0.0;
2611 intsupportweight * SCIProwGetNumIntCols(cuts[i], scip->set) / (SCIP_Real) SCIProwGetNNonz(cuts[i]) :
2614 objparallelism = objparalweight > 0.0 ? objparalweight * SCIProwGetObjParallelism(cuts[i], scip->set, scip->lp) : 0.0;
2653 nnonforcedcuts = filterWithParallelism(cuts[i], nonforcedcuts, nonforcedscores, nnonforcedcuts, goodscore, goodmaxparall, maxparall);
2656 /* if the maximal number of cuts was exceeded after selecting the forced cuts, we can stop here */
2668 /* if the best cut of the remaining cuts is considered bad, we discard it and all remaining cuts */
2678 /* move the pointers to the next position and filter the remaining cuts to enforce the maximum parallelism constraint */
2683 nnonforcedcuts = filterWithParallelism(selectedcut, nonforcedcuts, nonforcedscores, nnonforcedcuts, goodscore, goodmaxparall, maxparall);
2693 /* =========================================== c-MIR =========================================== */
2704 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2741 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2742 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2765 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2802 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2803 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
2819 /** determine the best bounds with respect to the given solution for complementing the given variable */
2825 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
2827 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
2828 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
2830 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
2833 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
2839 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
2852 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || ( boundsfortrans[v] == -2 || boundsfortrans[v] == -1 ));
2883 *bestlb = vlbcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vlbvars[k]) : SCIPgetSolVal(scip, sol, vlbvars[k])) + vlbconsts[k];
2889 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2890 SCIP_CALL( findBestUb(scip, var, sol, usevbds && fixintegralrhs, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
2921 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
2922 *bestub = vubcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vubvars[k]) : SCIPgetSolVal(scip, sol, vubvars[k])) + vubconsts[k];
2928 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2929 SCIP_CALL( findBestLb(scip, var, sol, usevbds && fixintegralrhs, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
2938 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
2941 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
2971 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
3024 * 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}\\
3025 * 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}
3033 * 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.} \\
3034 * 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.}
3037 * 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:
3049 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3051 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3052 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3054 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3057 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3068 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
3069 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
3099 /* start with continuous variables, because using variable bounds can affect the untransformed integral
3100 * variables, and these changes have to be incorporated in the transformation of the integral variables
3112 SCIP_CALL( determineBestBounds(scip, vars[cutinds[i]], sol, boundswitch, usevbds, allowlocal, fixintegralrhs,
3114 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3234 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
3256 /* determine the best bounds for the integral variable, usevbd can be set to FALSE here as vbds are only used for continous variables */
3257 SCIP_CALL( determineBestBounds(scip, vars[v], sol, boundswitch, FALSE, allowlocal, fixintegralrhs,
3259 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
3268 /* now perform the bound substitution on the remaining integral variables which only uses standard bounds */
3384 /* prefer larger violations; for equal violations, prefer smaller f0 values since then the possibility that
3416 assert(bestubtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3423 assert(bestlbtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
3444 /** 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$
3459 * 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} \\
3460 * 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}
3475 * 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)} \\
3476 * 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)}
3489 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
3499 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
3502 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
3524 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
3532 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
3600 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3635 /* now process the continuous variables; postpone deletetion of zeros till all continuous variables have been processed */
3661 SCIPquadprecProdQQ(cutaj, onedivoneminusf0, aj); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
3686 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
3793 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
3796 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
3800 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\
3806 * 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 || (slacksign[i] == -1 && SCIPisFeasIntegral(scip, row->lhs - row->constant))) ) /*lint !e613*/
3952 /** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
3955 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
3967 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
3969 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
3970 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
3971 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
3974 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
3982 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
3986 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
3987 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut */
4049 * 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.
4050 * 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.
4051 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
4055 SCIP_CALL( cutsTransformMIR(scip, sol, boundswitch, usevbds, allowlocal, fixintegralrhs, FALSE,
4056 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, tmpcoefs, QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, &freevariable, &localbdsused) );
4075 * 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
4076 * 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
4083 * 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)
4084 * 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)
4112 SCIP_CALL( cutsRoundMIR(scip, tmpcoefs, QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, QUAD(f0)) );
4118 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4122 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4136 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4139 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, cutinds, tmpcoefs, cutnnz, QUAD(&rhs), success) );
4143 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutnnz, cutinds);
4267 * Given the aggregation, it is transformed to a mixed knapsack set via complementation (using bounds or variable bounds)
4270 * so one would prefer to have integer coefficients for integer variables which are far away from their bounds in the
4273 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
4285 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4287 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4289 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4292 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4299 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
4301 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
4304 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
4353 /* we only compute bound distance for integer variables; we allocate an array of length aggrrow->nnz to store this, since
4354 * this is the largest number of integer variables. (in contrast to the number of total variables which can be 2 *
4355 * aggrrow->nnz variables: if all are continuous and we use variable bounds to completement, we introduce aggrrow->nnz
4387 * 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.
4388 * 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.
4389 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
4394 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, &freevariable, &localbdsused) );
4402 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4440 SCIP_CALL( SCIPcalcIntegralScalar(deltacands, nbounddist, -QUAD_EPSILON, SCIPsumepsilon(scip), (SCIP_Longint)10000, 10000.0, &intscale, &intscalesuccess) );
4516 * 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
4517 * 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
4524 * 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)
4525 * 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)
4717 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, deltacands[i], ntmpcoefs, minfrac, maxfrac);
4740 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, delta, ntmpcoefs, minfrac, maxfrac);
4750 /* try to improve efficacy by switching complementation of integral variables that are not at their bounds
4767 SCIP_CALL( findBestLb(scip, vars[mksetinds[k]], sol, FALSE, allowlocal, &bestlb, &simplebnd, &bestlbtype) );
4772 SCIP_CALL( findBestUb(scip, vars[mksetinds[k]], sol, FALSE, allowlocal, &bestub, &simplebnd, &bestubtype) );
4791 tmpvalues[k - intstart] = varsign[k] == +1 ? bestub - SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) : SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) - bestlb;
4794 newefficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(newrhs), contactivity, contsqrnorm, bestdelta, ntmpcoefs, minfrac, maxfrac);
4806 assert(bestubtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4813 assert(bestlbtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
4853 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4857 SCIP_CALL( cutsRoundMIR(scip, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, QUAD(f0)) );
4860 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4864 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
4868 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
4880 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4894 SCIPdebugMessage("efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
4901 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
4906 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, mksetinds, mksetcoefs, &mksetnnz, QUAD(&mksetrhs), success) );
4910 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, mksetcoefs, QUAD(&mksetrhs), mksetinds, &mksetnnz);
4914 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
4918 mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, mksetcoefs, QUAD_TO_DBL(mksetrhs), mksetinds, mksetnnz);
4975 /* =========================================== flow cover =========================================== */
4987 #define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
5004 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$ */
5005 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$ */
5007 SCIP_Real mp; /**< smallest variable bound coefficient of variable in \f$ C^{++} (min_{j \in C++} u_j) \f$ */
5011 /** structure that contains all the data that defines the single-node-flow relaxation of an aggregation row */
5023 SCIP_Real* aggrcoefsbin; /**< aggregation coefficient of the original binary var used to define the
5025 SCIP_Real* aggrcoefscont; /**< aggregation coefficient of the original continous var used to define the
5027 SCIP_Real* aggrconstants; /**< aggregation constant used to define the continuous variable in the relaxed set */
5030 /** get solution value and index of variable lower bound (with binary variable) which is closest to the current LP
5031 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
5032 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
5046 SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
5047 int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
5055 assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
5100 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5108 /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
5112 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
5160 /** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
5161 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
5162 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
5176 SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
5177 int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
5185 assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
5230 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
5242 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
5290 /** determines the bounds to use for constructing the single-node-flow relaxation of a variable in
5300 int varposinrow, /**< position of variable in the rowinds array for which the bounds should be determined */
5304 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5305 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5314 SCIP_BOUNDTYPE* selectedbounds, /**< pointer to store the preferred bound for the transformation */
5342 SCIP_CALL( findBestLb(scip, var, sol, FALSE, allowlocal, &bestslb[varposinrow], &simplebound, &bestslbtype[varposinrow]) );
5343 SCIP_CALL( findBestUb(scip, var, sol, FALSE, allowlocal, &bestsub[varposinrow], &simplebound, &bestsubtype[varposinrow]) );
5354 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef, SCIPvarGetName(var), probidx,
5355 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
5357 /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
5360 if( SCIPisInfinity(scip, -bestslb[varposinrow]) && SCIPisInfinity(scip, bestsub[varposinrow]) )
5366 /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
5379 SCIP_CALL( getClosestVlb(scip, var, sol, rowcoefs, binvarused, bestsub[varposinrow], rowcoef, &bestvlb, &bestvlbidx) );
5388 /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
5401 SCIP_CALL( getClosestVub(scip, var, sol, rowcoefs, binvarused, bestslb[varposinrow], rowcoef, &bestvub, &bestvubidx) );
5409 SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
5411 /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
5422 /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
5423 * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
5426 if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
5430 else if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
5435 else if( SCIPisLE(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
5441 assert(SCIPisGT(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
5456 else if ( selectedbounds[varposinrow] == SCIP_BOUNDTYPE_UPPER && bestubtype[varposinrow] >= 0 )
5471 /** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
5478 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5479 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5486 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5509 SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
5527 /* array to store whether a binary variable is in the row (-1) or has been used (1) due to variable bound usage */
5544 SCIP_CALL( determineBoundForSNF(scip, sol, vars, rowcoefs, rowinds, i, binvarused, allowlocal, boundswitch,
5545 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
5613 /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
5643 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5672 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5673 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5674 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestsub), QUAD_TO_DBL(rowcoef), bestsub, QUAD_TO_DBL(transrhs));
5690 * 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
5722 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5752 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5753 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5754 snf->ntransvars, SCIPvarGetName(vlbvars[bestlbtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvlbconst), QUAD_TO_DBL(rowcoef),
5797 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
5826 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5827 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
5828 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestslb), QUAD_TO_DBL(rowcoef), bestslb[i], QUAD_TO_DBL(transrhs));