cuts.c
Go to the documentation of this file.
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
76#define DEFAULT_CUTGEN_MAXTESTDELTA (-1) /**< default maximum number of deltas to test (-1 = unlimited) */
78/* =========================================== general static functions =========================================== */
117 SCIPquadprecProdQD(coef, coef, (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]])));
123 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]])));
127 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]])));
134 SCIPdebugMsgPrint(scip, " <= %.6f (activity: %g)\n", QUAD_TO_DBL(cutrhs), QUAD_TO_DBL(activity));
173 coef = coef * (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]]));
179 coef = coef * (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]));
183 coef = coef * (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]));
207 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
252 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
295 * This is the quad precision version of varVecAddScaledRowCoefs() with a quad precision scaling factor.
299 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
344/** add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
346 * In the safe variant, we need to transform all variables (implicitly) to nonnegative variables using their
347 * upper/lower bounds. When adding \f$\lambda * (c^Tx \le d)\f$ to \f$a^Tx \le b\f$, this results in:
355 * & \le b+ \lambda d + \sum_{i \in U, u_i > 0}(\overline{m_i}-\underline{m_i})u_i + \sum_{i \in L, l_i < 0}(\underline{m_i}-\overline{m_i})l_i
358 * This methods sums up the left hand side, and stores the change of the rhs due to the variable bounds in rhschange.
365 int* inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
414 SCIPintervalSetBounds(&valinterval, rowexact->valsinterval[i].inf, rowexact->valsinterval[i].sup);
418 if( SCIPisInfinity(scip, REALABS(valinterval.inf)) || SCIPisInfinity(scip, REALABS(valinterval.sup)) )
448 /* we can't set the value to 0 or the sparsity pattern does not work. We can't perturb it slightly because we are solving
468 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
526/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter */
530 SCIP_Real* vals, /**< array of the non-zero coefficients in the vector; this is a quad precision array! */
531 int* inds, /**< array of the problem indices of variables with a non-zero coefficient in the vector */
593 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
595 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
659/** calculates the cut efficacy for the given solution; the cut coefs are stored densely and in quad precision */
664 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
666 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
730/** safely (in the exact solving mode sense) remove all items with |a_i| or |u_i - l_i)| below the given value
743 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
772 /* for now we always use global bounds in exact solving mode (could be improved for local cuts in the future) */
839 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
932 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
941 /* loop over non-zeros and remove values below minval; values above QUAD_EPSILON are cancelled with their bound
1059/** change given coefficient to new given value, adjust right hand side using the variables bound;
1104/** change given (quad) coefficient to new given value, adjust right hand side using the variables bound;
1149/** change given coefficient to new given value, adjust right hand side using the variables bound;
1212/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1213 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse quad precision array;
1223 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1245 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1257 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1275 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1324 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
1325 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1345 if( chgQuadCoeffWithBound(scip, vars[cutinds[i]], QUAD(val), intval, cutislocal, QUAD(cutrhs)) )
1385 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1395 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1465 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1469 /* first sort indices, so that in the following sort, the order for coefficients with same absolute value does not depend on how cutinds was initially ordered */
1473 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1488 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1491 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1497 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1511 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1535 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1538 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1544 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1558 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1582 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1591/** multiplies a parameter for a variable in a row safely (using variable bounds and increasing the rhs)
1642 SCIPdebugMessage("Using lb %.17g corrected by %.17g. Change to rhs: %.17g \n", SCIPvarGetLbGlobal(var), -SCIPintervalGetSup(valinterval) + SCIPintervalGetInf(valinterval), *rhschange);
1649 SCIPdebugMessage("Using ub %.17g corrected by %.17g. Change to rhs: %.17g \n", SCIPvarGetUbGlobal(var), SCIPintervalGetSup(valinterval) - SCIPintervalGetInf(valinterval), *rhschange);
1663/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1674 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1706 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1718 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1737 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1788 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPepsilon(scip),
1789 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1813 val = scaleValSafely(scip, val, intscalar, cutislocal, vars[cutinds[i]], &rhschange, &success);
1872 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1882 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1922 val = scaleValSafely(scip, val, equiscale, cutislocal, vars[cutinds[i]], &rhschange, &success);
1979 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1990 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
2005 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
2008 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2014 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2028 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2052 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
2055 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2061 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2075 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2099 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2110/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
2111 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
2119 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
2143 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
2156 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2174 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2222 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
2223 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
2282 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2291 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2348 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
2352 /* first sort indices, so that in the following sort, the order for coefficients with same absolute value does not depend on how cutinds was initially ordered */
2356 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
2374 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2380 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2394 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2420 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2426 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2440 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2463 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2472/** perform activity based coefficient tightening on the given cut; returns TRUE if the cut was detected
2482 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
2516 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2534 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2561 /* terminate, because coefficient tightening cannot be performed; also excludes the case in which no integral variable is present */
2568 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
2571 /* due to sorting, we can exit if we reached a continuous variable: all further integral variables have 0 coefficents anyway */
2580 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2593 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2621 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2634 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2659 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2669/* =========================================== aggregation row =========================================== */
2674 * @note By default, this data structure uses quad precision via double-double arithmetic, i.e., it allocates a
2675 * SCIP_Real array of length two times SCIPgetNVars() for storing the coefficients. In exact solving mode, we
2676 * cannot use quad precision because we need to control the ronding mode, hence only the first SCIPgetNVars()
2761 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", QUAD_TO_DBL(val), SCIPvarGetName(vars[aggrrow->inds[i]]));
2784 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->vals, source->vals, QUAD_ARRAY_SIZE(nvars)) );
2795 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowsinds, source->rowsinds, source->nrows) );
2796 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->slacksign, source->slacksign, source->nrows) );
2797 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowweights, source->rowweights, source->nrows) );
2841 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2842 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2843 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2861 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
2889 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
2896 * @note this method is the variant of SCIPaggrRowAddRow that is safe to use in exact solving mode
2929 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2930 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2931 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2949 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
2977 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
2988 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
3002 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, aggrrow->inds, aggrrow->vals, &aggrrow->nnz, userow, weight, &sidevalchg, success) );
3012/** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
3013 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
3015 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
3017 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
3077/** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
3213 /* in exact solving mode, we do not use quad precision, because we need to control the rounding mode; hence, we only
3250/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
3252 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
3264 * @note this method differs from SCIPaggrRowAddRow() by providing some additional parameters required for
3275 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3288 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
3307 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
3312 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
3353 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
3354 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
3355 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
3365 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
3376 * @note this method differs from SCIPaggrRowAddRowSafely() by providing some additional parameters required for
3389 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3410 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
3429 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
3434 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
3464 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
3482 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
3504 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
3505 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
3506 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
3516 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, aggrrow->inds, aggrrow->vals, &aggrrow->nnz, userow, weight, &sidevalchg, success) );
3530/** aggregate rows using the given weights; the current content of the aggregation row, \p aggrrow, is overwritten
3542 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3595 SCIP_CALL( addOneRow(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
3604 SCIP_CALL( addOneRowSafely(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal,
3625 ((!lhsused && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant)) ||
3626 (lhsused && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) )
3635 SCIP_CALL( addOneRowSafely(scip, certificaterow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis,
3648 assert( (lhsused && weights[rowinds[k]] >= 0) || ((!lhsused) && weights[rowinds[k]] <= 0) || row->integral );
3668 SCIP_CALL( addOneRow(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
3677 SCIP_CALL( addOneRowSafely(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack,
3698 ((!lhsused && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant)) ||
3699 (lhsused && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) )
3708 SCIP_CALL( addOneRowSafely(scip, certificaterow, rows[k], weights[k], sidetypebasis, allowlocal, 0,
3742 SCIP_CALL( SCIPaddCertificateAggrInfo(scip, certificaterow, usedrows, usedweights, certificaterow->nrows,
3771 SCIP_Bool* success /**< pointer to return whether post-processing was successful or cut is redundant */
3799 SCIP_CALL( cutTightenCoefs(scip, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz, &redundant) );
3818 *success = ! removeZeros(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz);
3840 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
3856 if( removeZerosQuad(scip, SCIPfeastol(scip), cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz) )
3865 SCIP_CALL( cutTightenCoefsQuad(scip, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz, &redundant) );
3886 *success = ! removeZerosQuad(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz);
3906 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
3933 SCIP_CALL( cutTightenCoefsSafely(scip, cutislocal, cutcoefs, cutrhs, cutinds, nnz, &redundant) );
3974 *valid = !removeZerosSafely(scip, SCIPsumepsilon(scip), aggrrow->vals, &rhs, aggrrow->inds, &aggrrow->nnz);
3979 *valid = ! removeZerosQuad(scip, SCIPsumepsilon(scip), useglbbounds ? FALSE : aggrrow->local, aggrrow->vals,
4038/** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
4088/* =========================================== c-MIR =========================================== */
4092/* In order to derive cuts, we partition the variable array up in (not necessarily contiguous) sections.
4093 * The only requirement we place on these sections is that section i can only have variable bounds variables whose section
4094 * is strictly greater than i. This way, we can process the variable array in a 'linear' manner. */
4096/* @todo maintain a DAG for used varbounds and use topological ordering instead, this would also allow
4171 * Currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences
4172 * in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code. */
4179 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4180 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4183 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4213 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
4218 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4219 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4240 * currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences
4241 * in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code. */
4248 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4249 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4252 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4281 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
4286 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4287 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4307/** determine the best bounds with respect to the given solution for complementing the given variable */
4314 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4315 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4316 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4317 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
4319 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4322 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4326 int* bestlbtype, /**< pointer to store type of the best lower bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4327 int* bestubtype, /**< pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4328 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
4372 *bestlb = vlbcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vlbvars[k]) : SCIPgetSolVal(scip, sol, vlbvars[k])) + vlbconsts[k];
4378 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4379 SCIP_CALL( findBestUbSafely(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
4410 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4411 *bestub = vubcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vubvars[k]) : SCIPgetSolVal(scip, sol, vubvars[k])) + vubconsts[k];
4417 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4418 SCIP_CALL( findBestLbSafely(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
4427 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4428 SCIP_CALL( findBestLbSafely(scip, var, sol, usevbds, allowlocal, bestlb, &simplelb, bestlbtype) );
4430 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4431 SCIP_CALL( findBestUbSafely(scip, var, sol, usevbds, allowlocal, bestub, &simpleub, bestubtype) );
4460 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
4513 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4514 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4516 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4544 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
4549 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4550 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4576 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4577 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4579 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4607 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
4612 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4613 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4635 * Differs from findBestLB() in that it allows more variable bound substitutions based on the variable sections. */
4642 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4643 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4646 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4692 /* For now, we only allow variable bounds from sections that are strictly greater to prevent cyclic usage.*/
4693 /** @todo: We don't use the caching mechanism of SCIPvarGetClosestVLB() because the cached variable bound
4695 if( SCIPvarIsActive(vlbvars[i]) && boundedsection < varSection(data, SCIPvarGetProbindex(vlbvars[i])) &&
4724 * Differs from findBestUB() in that it allows more variable bound substitutions based on the variable sections. */
4731 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4732 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4735 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4781 /* For now, we only allow variable bounds from sections that are strictly greater to prevent cyclic usage.*/
4782 /** @todo: We don't use the caching mechanism of SCIPvarGetClosestVLB() because the cached variable bound
4784 if( SCIPvarIsActive(vubvars[i]) && boundedsection < varSection(data, SCIPvarGetProbindex(vubvars[i])) &&
4812/** determine the best bounds with respect to the given solution for complementing the given variable */
4819 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4820 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4821 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4822 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
4824 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4827 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4831 int* bestlbtype, /**< pointer to store type of best lower bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4832 int* bestubtype, /**< pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4833 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
4888 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4889 SCIP_CALL( findMIRBestUb(scip, var, sol, data, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
4928 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4929 SCIP_CALL( findMIRBestLb(scip, var, sol, data, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
4938 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4939 SCIP_CALL( findMIRBestLb(scip, var, sol, data, usevbds, allowlocal, bestlb, &simplelb, bestlbtype) );
4941 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4942 SCIP_CALL( findMIRBestUb(scip, var, sol, data, usevbds, allowlocal, bestub, &simpleub, bestubtype) );
4971 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
5026 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5028 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5103/** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index
5117 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5119 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5150/** performs the bound substitution step with the simple bound for the variable with the given problem index
5163 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5165 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5189/** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index */
5200 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5202 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5270/** performs the bound substitution step with the simple bound for the variable with the given problem index */
5278 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5280 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5305 * 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},\\
5306 * 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},
5314 * 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.} \\
5315 * 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.}
5318 * 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:
5334 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5336 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5337 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
5339 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
5342 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
5351 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
5352 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5390 /* start with continuous variables, because using variable bounds can affect the untransformed integral
5391 * variables, and these changes have to be incorporated in the transformation of the integral variables
5403 SCIP_CALL( determineBestBoundsSafely(scip, vars[cutinds[i]], sol, boundswitch, usevbds ? 2 : 0, allowlocal, fixintegralrhs,
5405 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
5427 performBoundSubstitutionSafely(scip, cutcoefs, cutrhs, varsign[i], boundtype[i], bestlbs[i], v, localbdsused);
5437 performBoundSubstitutionSafely(scip, cutcoefs, cutrhs, varsign[i], boundtype[i], bestubs[i], v, localbdsused);
5452 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
5460 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
5461 SCIP_CALL( determineBestBoundsSafely(scip, vars[v], sol, boundswitch, 0, allowlocal, fixintegralrhs,
5463 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
5472 /* now perform the bound substitution on the remaining integral variables which only uses standard bounds */
5487 performBoundSubstitutionSimpleSafely(scip, cutcoefs, cutrhs, boundtype[i], bestlbs[i], v, localbdsused);
5498 performBoundSubstitutionSimpleSafely(scip, cutcoefs, cutrhs, boundtype[i], bestubs[i], v, localbdsused);
5532 * 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},\\
5533 * 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},
5541 * 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.} \\
5542 * 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.}
5545 * 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:
5558 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5559 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5560 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
5562 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
5565 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
5572 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
5573 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5633 SCIP_CALL( determineBestBounds(scip, data->vars[v], sol, data, boundswitch, usevbds, allowlocal, fixintegralrhs,
5651 /* if we terminate early, we need to make sure all the zeros in the cut coefficient array are cancelled */
5740 newrhs = QUAD_TO_DBL(data->cutrhs) + varsign[i] * QUAD_TO_DBL(coef) * (bestlbs[i] - bestubs[i]);
5770 /* prefer larger violations; for equal violations, prefer smaller f0 values since then the possibility that
5773 if( SCIPisGT(scip, violgain, bestviolgain) || (SCIPisGE(scip, violgain, bestviolgain) && newf0 < bestnewf0) )
5802 assert(bestubtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
5809 assert(bestlbtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
5830/** 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$
5845 * 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}, \\
5846 * 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},
5861 * 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)} \\
5862 * 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)}
5875 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
5887 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
5890 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
5914 /* we need to careate the split-data for certification here, since part of the f_j > f_0 variables goes into the continuous part of the split */
5926 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
5934 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
5992 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
5996 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6017 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6021 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6038 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6095 /* now process the continuous variables; postpone deletetion of zeros till all continuous variables have been processed */
6123 SCIPintervalMulScalar(SCIPinfinity(scip), &cutaj, onedivoneminusf0, aj); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
6150 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6220/** 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$
6235 * 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} \\
6236 * 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}
6251 * 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)} \\
6252 * 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)}
6265 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
6277 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
6280 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
6307 /* we need to careate the split-data for certification here, since part of the f_j > f_0 variables goes into the continuous part of the split */
6317 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
6325 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
6381 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6385 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6407 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6411 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6422 /* remove zero cut coefficients from cut, only remove positive coefficients in exact solving mode */
6442 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6448 assert(SCIPrationalRoundReal(SCIPvarGetLbGlobalExact(var), SCIP_R_ROUND_DOWNWARDS) == SCIPvarGetLbGlobal(var));
6451 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetLbGlobal(var) */
6457 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetLbLocal(var) */
6465 assert(SCIPrationalRoundReal(SCIPvarGetUbGlobalExact(var), SCIP_R_ROUND_UPWARDS) == SCIPvarGetUbGlobal(var));
6468 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetUbGlobal(var) */
6474 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetUbLocal(var) */
6480 /* now process the continuous variables; postpone deletetion of zeros till all continuous variables have been processed */
6514 SCIPrationalMultReal(cutaj, cutaj, QUAD_TO_DBL(aj)); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
6548 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6554 assert(SCIPrationalRoundReal(SCIPvarGetLbGlobalExact(var), SCIP_R_ROUND_DOWNWARDS) == SCIPvarGetLbGlobal(var));
6571 assert(SCIPrationalRoundReal(SCIPvarGetUbGlobalExact(var), SCIP_R_ROUND_UPWARDS) == SCIPvarGetUbGlobal(var));
6670/** 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$
6685 * 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} \\
6686 * 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}
6701 * 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)} \\
6702 * 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)}
6715 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
6725 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
6743 /* Loop backwards through the sections, so that the reversing of varbound substitutions does not prematurely effect
6744 * the coefficients of variables in other sections, because the section index of a variable bound must always be
6755 /* iterate backwards over indices in section, so we can easily shrink the section if we find zeros */
6834 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6925 /* Finally, store the relevant data in cutinds which is the array used by the other functions */
6942 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
6943 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r]. \f$
6945 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
6949 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f_0)/(1 - f_0),& \mbox{if}\qquad f_r > f_0 \\
6955 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7051 ((slacksign[i] == +1 && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant))
7052 || (slacksign[i] == -1 && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) ) /*lint !e613*/
7086 SCIPdebugMessage("fractionality %g, f0 %g -> round up! splitcoef %g sub-coefficient %g", fr.inf, f0.inf, splitcoef, cutar.inf);
7099 SCIPintervalMul(SCIPinfinity(scip), &cutar, onedivoneminusf0, ar); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
7100 SCIPdebugMessage("resubstituting negative continuous slack for row %s with coef %g\n", row->name, cutar.inf);
7121 /* save the value for the split disjunction for the integer slack and the continous part (for rounded up we
7160 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, cutinds, cutcoefs, nnz, userow, mult, &sidevalchg, &success) );
7179 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7199 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7223 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7226 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7230 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\
7236 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7327 || (slacksign[i] == -1 && SCIPisFeasIntegral(scip, row->lhs - row->constant))) ) /*lint !e613*/
7339 if( SCIPisLE(scip, QUAD_TO_DBL(fr), QUAD_TO_DBL(f0)) && (!SCIPisExact(scip) || QUAD_TO_DBL(fr) <= QUAD_TO_DBL(f0)) )
7361 SCIPrationalMult(cutar, ar, onedivoneminusf0); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
7398 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, cutinds, cutcoefs, nnz, userow, mult, &sidevalchg, &success) );
7416 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7438 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7472 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7475 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7479 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\
7485 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7632/** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
7635 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7652 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7654 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7655 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
7656 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
7659 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
7665 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
7666 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
7667 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
7668 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
7670 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
7671 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
7672 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
7751 * 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.
7752 * 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.
7753 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
7757 SCIP_CALL( cutsTransformMIRSafely(scip, sol, boundswitch, usevbds, allowlocal, fixintegralrhs, FALSE,
7758 boundsfortrans, boundtypesfortrans, tmpcoefs, &rhs, tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
7779 * 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
7780 * 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
7787 * 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)
7788 * 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)
7801 SCIP_MIRINFO* mirinfo = SCIPgetCertificate(scip)->mirinfo[SCIPgetCertificate(scip)->nmirinfos - 1];
7824 SCIP_CALL( cutsRoundMIRSafely(scip, tmpcoefs, &rhs, tmpinds, &tmpnnz, varsign, boundtype, f0interval) ); /*lint !e644*/
7832 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7836 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7845 SCIP_CALL( cutsSubstituteMIRSafely(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
7856 SCIP_CALL( postprocessCutSafely(scip, tmpislocal, tmpinds, tmpcoefs, &tmpnnz, &rhs, success) );
7870 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
7921/** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
7924 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7938 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7943 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7944 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
7945 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
7948 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
7954 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
7955 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
7956 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
7957 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
7959 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
7960 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
7961 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
7980 return calcMIRSafely(scip, sol, postprocess, boundswitch, vartypeusevbds > 0 ? TRUE : FALSE, allowlocal, fixintegralrhs,
8005 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
8012 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
8022 SCIP_CALL( SCIPallocCleanBufferArray(scip, &( data->cutcoefs ), QUAD_ARRAY_SIZE(data->nvars)) );
8057 SCIPdebug( printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, nnz, FALSE, FALSE) );
8075 * 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.
8076 * 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.
8077 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
8093 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8106 * 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
8107 * 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
8114 * 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)
8115 * 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)
8147 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8152 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
8156 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
8169 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8173 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
8176 SCIP_CALL( postprocessCutQuad(scip, tmpislocal, data->cutinds, data->cutcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
8180 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), tmpislocal, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds);
8184 SCIPdebug( printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE) );
8188 SCIP_Real mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, data->cutcoefs, QUAD_TO_DBL(data->cutrhs), data->cutinds, data->ncutinds);
8190 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
8336 * Given the aggregation, it is transformed to a mixed knapsack set via complementation (using bounds or variable bounds)
8339 * so one would prefer to have integer coefficients for integer variables which are far away from their bounds in the
8342 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8354 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8359 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8361 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
8364 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
8371 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8373 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
8376 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
8423 /* The +4 comes from a few rules that create extra delta candidates, see usages of ndeltacands. */
8426 /* we only compute bound distance for integer variables; by variable bound substitution, the number of integer variables
8449 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
8456 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
8513 * 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.
8514 * 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.
8515 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
8520 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, varsign, boundtype, &freevariable, &localbdsused) );
8523 /* Use aliases to stay more consistent with the old code. mksetrhs needs to synchronize its values data->cutrhs
8534 SCIPdebug( printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE) );
8567 /* Check that the continuous and implied integer variables and integer variables are partitioned */
8587 SCIP_CALL( SCIPcalcIntegralScalar(deltacands, nbounddist, -SCIPepsilon(scip), SCIPsumepsilon(scip), (SCIP_Longint)10000, 10000.0, &intscale, &intscalesuccess) );
8657 * 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
8658 * 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
8665 * 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)
8666 * 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)
8859 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, deltacands[i], ntmpcoefs, minfrac, maxfrac);
8882 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, delta, ntmpcoefs, minfrac, maxfrac);
8892 /* try to improve efficacy by switching complementation of integral variables that are not at their bounds
8934 tmpvalues[k - intstart] = varsign[k] == +1 ? bestub - SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) : SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) - bestlb;
8937 newefficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(newrhs), contactivity, contsqrnorm, bestdelta, ntmpcoefs, minfrac, maxfrac);
8949 assert(bestubtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
8956 assert(bestlbtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
8997 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
9006 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
9010 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
9014 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
9023 aggrrow->nrows, scale, mksetcoefs, QUAD(&data->cutrhs), mksetinds, &data->ncutinds, QUAD(f0)) );
9026 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
9040 SCIPdebugMsg(scip, "efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
9047 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
9052 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, mksetinds, mksetcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
9056 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, mksetcoefs, QUAD(&data->cutrhs), mksetinds, &data->ncutinds);
9060 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
9064 mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, mksetcoefs, QUAD_TO_DBL(data->cutrhs), mksetinds, data->ncutinds);
9140/* =========================================== flow cover =========================================== */
9152#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
9169 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$ */
9170 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$ */
9172 SCIP_Real mp; /**< smallest variable bound coefficient of variable in \f$ C^{++} (min_{j \in C++} u_j) \f$ */
9176/** structure that contains all the data that defines the single-node-flow relaxation of an aggregation row */
9188 SCIP_Real* aggrcoefsbin; /**< aggregation coefficient of the original binary var used to define the
9190 SCIP_Real* aggrcoefscont; /**< aggregation coefficient of the original continuous var used to define the
9192 SCIP_Real* aggrconstants; /**< aggregation constant used to define the continuous variable in the relaxed set */
9195/** get solution value and index of variable lower bound (with binary variable) which is closest to the current LP
9196 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
9197 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
9210 SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
9211 int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
9219 assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
9264 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
9272 /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
9276 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
9324/** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
9325 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
9326 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
9340 SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
9341 int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
9349 assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
9394 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
9406 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
9454/** determines the bounds to use for constructing the single-node-flow relaxation of a variable in
9464 int varposinrow, /**< position of variable in the rowinds array for which the bounds should be determined */
9468 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
9469 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
9474 int* bestlbtype, /**< pointer to store type of best lower bound (-2: local bound, -1: global bound, >= 0 variable bound index) */
9475 int* bestubtype, /**< pointer to store type of best upper bound (-2: local bound, -1: global bound, >= 0 variable bound index) */
9478 SCIP_BOUNDTYPE* selectedbounds, /**< pointer to store the preferred bound for the transformation */
9505 SCIP_CALL( findBestLb(scip, var, sol, 0, allowlocal, &bestslb[varposinrow], &bestslbtype[varposinrow]) );
9506 SCIP_CALL( findBestUb(scip, var, sol, 0, allowlocal, &bestsub[varposinrow], &bestsubtype[varposinrow]) );
9517 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef, SCIPvarGetName(var), probidx,
9518 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
9520 /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
9523 if( SCIPisInfinity(scip, -bestslb[varposinrow]) && SCIPisInfinity(scip, bestsub[varposinrow]) )
9529 /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
9542 SCIP_CALL( getClosestVlb(scip, var, sol, rowcoefs, binvarused, bestsub[varposinrow], rowcoef, &bestvlb, &bestvlbidx) );
9551 /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
9564 SCIP_CALL( getClosestVub(scip, var, sol, rowcoefs, binvarused, bestslb[varposinrow], rowcoef, &bestvub, &bestvubidx) );
9572 SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
9574 /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
9585 /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
9586 * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
9589 if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
9593 else if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
9598 else if( SCIPisLE(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
9604 assert(SCIPisGT(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
9634/** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
9641 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
9642 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
9649 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
9672 SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
9690 /* array to store whether a binary variable is in the row (-1) or has been used (1) due to variable bound usage */
9704 SCIP_CALL( determineBoundForSNF(scip, sol, vars, rowcoefs, rowinds, i, binvarused, allowlocal, boundswitch,
9705 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
9774 /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
9804 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9832 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
9833 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9834 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestsub), QUAD_TO_DBL(rowcoef), bestsub[i], QUAD_TO_DBL(transrhs));
9850 * 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
9882 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9911 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
9912 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9913 snf->ntransvars, SCIPvarGetName(vlbvars[bestlbtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvlbconst), QUAD_TO_DBL(rowcoef),
9956 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9984 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
9985 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9986 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestslb), QUAD_TO_DBL(rowcoef), bestslb[i], QUAD_TO_DBL(transrhs));
10003 * 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,
10032 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
10061 /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
10063 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
10064 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
10065 snf->ntransvars, SCIPvarGetName(vubvars[bestubtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvubconst), QUAD_TO_DBL(rowcoef),
10109 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n", i, QUAD_TO_DBL(rowcoef), SCIPvarGetName(var), probidx, varsolval,
10122 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
10149 assert(snf->transvarcoefs[snf->ntransvars] == 1 || snf->transvarcoefs[snf->ntransvars] == - 1 );
10155 SCIPdebugMsg(scip, " --> ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s))\n", snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars,
10229/** solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide
10269 /* allocate memory for temporary array used for sorting; array should contain profits divided by corresponding weights (p_1 / w_1 ... p_n / w_n )*/
10280 SCIPselectWeightedDownRealRealInt(tempsort, profits, items, weights, mediancapacity, nitems, &criticalitem);
10324/** build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished
10339 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10403/** checks whether the given scalar scales the given value to an integral number with error in the given bounds */
10408 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
10409 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
10426/** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
10433 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
10434 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
10457 * 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
10465 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10509 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
10549 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
10614 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10615 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
10623 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10624 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
10638 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
10650 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
10651 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
10656 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
10657 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
10662 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
10665 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
10686 * solve KP^SNF_int exactly, if a suitable factor C is found and (nitems*capacity) <= MAXDYNPROGSPACE,
10700 SCIP_CALL( SCIPcalcIntegralScalar(transweightsreal, nitems, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE, &scalar,
10704 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
10739 SCIP_CALL( SCIPsolveKnapsackExactly(scip, nitems, transweightsint, transprofitsint, transcapacityint,
10756 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10764 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10772 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
10774 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
10778 /* if the found structure is not a flow cover, because of scaling, solve KP^SNF_rat approximately */
10784 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10786#ifdef SCIP_DEBUG /* this time only for SCIP_DEBUG, because only then, the variable is used again */
10796 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
10819 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
10839 * \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$,
10849 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10884 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
10916 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
10983 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10984 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
10992 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10993 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
11007 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
11015 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
11016 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
11021 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
11022 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
11026 transcapacityreal = - snf->transrhs + QUAD_TO_DBL(flowcoverweight) + n1itemsweight; /*lint !e644*/
11027 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
11030 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
11052 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
11058 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
11064 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
11066 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
11089 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
11107/** evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities
11235 int* transvarflowcoverstatus, /**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
11345 SCIP_UNUSED( SCIPsortedvecFindDownReal(liftingdata->m, liftingdata->mp, liftingdata->r, &liftingdata->t) );
11346 assert(liftingdata->m[liftingdata->t] == liftingdata->mp || SCIPisInfinity(scip, liftingdata->mp)); /*lint !e777*/
11352 while( liftingdata->t < liftingdata->r && liftingdata->m[liftingdata->t] == liftingdata->mp ) /*lint !e777*/
11379 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
11457 SCIP_Real liftedbincoef = evaluateLiftingFunction(scip, &liftingdata, snf->transvarvubcoefs[i]);
11603 /* a*x + c + s == rhs => s == - a*x - c + rhs: move a^_r * (rhs - c) to the right hand side */
11640/** calculates a lifted simple generalized flow cover cut out of the weighted sum of LP rows given by an aggregation row; the
11641 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
11645 * Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs.
11648 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
11660 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
11661 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
11665 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
11669 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
11695 SCIPdebug( printCutQuad(scip, sol, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, FALSE, aggrrow->local) );
11697 SCIP_CALL( constructSNFRelaxation(scip, sol, boundswitch, allowlocal, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, &snf, success, &localbdsused) );
11708 SCIP_CALL( getFlowCover(scip, &snf, &nflowcovervars, &nnonflowcovervars, transvarflowcoverstatus, &lambda, success) );
11718 SCIP_CALL( generateLiftedFlowCoverCut(scip, &snf, aggrrow, transvarflowcoverstatus, lambda, tmpcoefs, &tmprhs, tmpinds, &tmpnnz, success) );
11721 /* if success is FALSE generateLiftedFlowCoverCut wont have touched the tmpcoefs array so we dont need to clean it then */
11733 *success = ! removeZeros(scip, SCIPsumepsilon(scip), tmpislocal, tmpcoefs, QUAD(&rhs), tmpinds, &tmpnnz);
11791/* =========================================== knapsack cover =========================================== */
11793/** Relax the row to a possibly fractional knapsack row containing no integer or continuous variables
11794 * and only having positive coefficients for binary variables. General integer and continuous variables
11795 * are complemented with variable or simple bounds such that their coefficient becomes positive and then
11797 * All remaining binary variables are complemented with simple upper or lower bounds such that their
11804 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
11812 SCIP_Bool* localbdsused, /**< pointer to store whether local bounds were used in transformation */
11813 SCIP_Bool* success /**< stores whether the row could successfully be transformed into a knapsack constraint.
11834 /* start with continuous variables, because using variable bounds can affect the untransformed binary
11835 * variables, and these changes have to be incorporated in the transformation of the binary variables
11843 /* determine best bounds for the continuous and general integer variables such that they will have
11854 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable
11856 SCIP_CALL( findBestLb(scip, vars[v], sol, SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS ? 1 : 0, allowlocal, bestbds + i, boundtype + i) );
11866 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable
11868 SCIP_CALL( findBestUb(scip, vars[v], sol, SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS ? 1 : 0, allowlocal, bestbds + i, boundtype + i) );
11887 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], v, localbdsused);
11896 /* remove non-binary variables because their coefficients have been set to zero after bound substitution */
11904 /* after doing bound substitution of non-binary vars, some coefficients of binary vars might have changed, so here we
11905 * remove the ones that became 0 if any; also, we need that all remaining binary vars have positive coefficients,
11921 /* due to variable bound usage for bound substitution of continuous variables cancellation may have occurred */
11944 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
11956 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
11969 /* increase i or remove zero coefficient (i.e. var with 0 coef) by shifting last nonzero to current position */
11999 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
12003 int* coverstatus, /**< array to return the coverstatus for each variable in the knapsack row */
12055 SCIPsortDownRealInt(covervals + (*coversize), coverpos + (*coversize), cutnnz - (*coversize));
12078 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(*coverweight), cutrhs);
12089 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
12096 int* coverstatus, /**< coverstatus for each variable in the cover. After calling this function
12157 /* now we partition C into C^+ and C^-, where C^+ are all the elements of C whose weight is strictly larger than
12158 * \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
12159 * compute S^-(h) = sum of the h largest a_i^- and store S^-(h+1) in in covervals[h], for k = 0, ..., coversize - 1
12161 * we remember which elements of C^- in coverstatus, so that element in C^+ have coverstatus 1 and
12175 /* coefficient is in C^+ because it is greater than \bar{a} and contributes only \bar{a} to the sum */
12178 /* rather be on the safe side in numerical corner cases and relax the coefficient to exactly \bar{a}.
12179 * In that case the coefficient is not treated as in C^+ but as being <= \bar{a} and therefore in C^-.
12209 SCIP_Real* scale /**< pointer to update the scale to integrality when a fractional value is returned */
12218 /* the lifted value is at least the coeficient (a_k) divided by \bar{a} because the largest value
12227 /* if the coefficient is below \bar{a}, i.e. a / \bar{a} < 1 then g(a_k) = 0, otherwise g(a_k) > 0 */
12231 /* we perform h = MIN(h, coversize) in floating-point first because on some instances h was seen to exceed the range
12253 /* decrease by one to make sure rounding errors or coefficients that are larger than the right hand side by themselves
12259 * (todo: variables that have a coefficient above the right hand side can get an arbitrarily large coefficient but can
12260 * also be trivially fixed using the base row. Currently they get the coefficient |C| which is 1 above the right hand
12261 * side in the cover cut so that they can still be trivially fixed by propagating the cover cut.
12262 * We do not want to apply fixings here though because the LP should stay flushed during separation.
12263 * Possibly add a parameter to return additional fixings to the caller of the SCIPcalc*() functions in here
12269 /* compare with standard epsilon tolerance since computation involves abar, which is computed like an activity */
12280 SCIPdebugMsg(scip, "lifted coef %g < %g <= %g to %g\n", h == 0 ? 0 : covervals[h-1], QUAD_TO_DBL(x),
12286/** calculates a lifted knapsack cover cut out of the weighted sum of LP rows given by an aggregation row; the
12287 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
12291 * Letchford, A. N., & Souli, G. (2019). On lifted cover inequalities: A new lifting procedure with unusual properties.
12294 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
12305 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
12309 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
12313 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
12390 /* Transform aggregated row into a (fractional, i.e. with possibly fractional weights) knapsack constraint.
12392 * so that only binary variables remain and complements those such that they have a positive coefficient.
12406 if( !computeInitialKnapsackCover(scip, sol, tmpcoefs, tmpinds, QUAD_TO_DBL(rhs), nnz, varsign, coverstatus,
12410 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(coverweight), QUAD_TO_DBL(rhs));
12456 * - 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
12477 { /* variables is either in C^+ or not in the cover and its coefficient value is computed with the lifing function */
12483 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));
12486 cutcoef = evaluateLiftingFunctionKnapsack(scip, QUAD(coef), QUAD(abar), covervals, coversize, cplussize, &scale);
12504 /* variable was complemented so we have cutcoef * (1-x) = cutcoef - cutcoef * x.Thus we need to adjust the rhs
12517 /* calculate the efficacy of the computed cut and store the success flag if the efficacy exceeds the
12549 /* calculate efficacy again to make sure it matches the coefficients after they where rounded to double values
12594/* =========================================== strongcg =========================================== */
12599 * Differs from cutsTransformMIR for continuous variables for which the lower bound must be used
12601 * negative. This forces all continuous variable to have a positive coefficient in the transformed
12607 * 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}\\
12608 * 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}
12616 * 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.} \\
12617 * 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.}
12620 * 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:
12633 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
12634 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
12638 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
12639 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
12697 /* For continuous variables, we must choose the bound substitution so that they become positive in the cut */
12704 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
12724 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
12741 /* For implied integers, we still prefer to choose the bound substitution that makes them positive, but
12742 * if we cannot manage to do so it is not an error, because we can still treat them as integer variables */
12749 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
12753 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
12785 SCIP_CALL( determineBestBounds(scip, data->vars[v], sol, data, boundswitch, usevbds, allowlocal, FALSE, FALSE,
12834 /* If we terminate early, we need to make sure all the zeros in the cut coefficient array are cancelled */
12862/** Calculate fractionalities \f$ f_0 := b - down(b) \f$, \f$ f_j := a^\prime_j - down(a^\prime_j) \f$,
12863 * 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
12864 * 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$
12880 * 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} \\
12881 * 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}
12896 * 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)} \\
12897 * 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)}
12910 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\
12911 * \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j * bu_j == \hat{a}_{zu_j} - \hat{a}_j * bu_j &
12920 int* boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)*/
12939 /* Loop backwards through the sections, so that the reversing of varbound substitutions does not prematurely effect
12940 * the coefficients of variables in other sections, because the section index of a variable bound must always be
12950 /* iterate backwards over indices in section, so we can easily shrink the section if we find zeros */
12997 assert(pj >= 0); /* should be >= 1, but due to rounding bias can be 0 if fj is almost equal to f0 */
13007 /* Variable is continuous; must always be positive in strongcg cut. It will be automatically deleted. */
13031 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
13122 /* Finally, store the relevant data in cutinds which is the array used by the other functions */
13140 * 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
13141 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r] \f$.
13143 * Depending on the slack's type (integral or continuous), its coefficient in the cut calculates as follows:
13153 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
13232 assert(pr >= 0); /* should be >= 1, but due to rounding bias can be 0 if fr is almost equal to f0 */
13301/** calculates a strong CG cut out of the weighted sum of LP rows given by an aggregation row; the
13302 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
13305 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
13317 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
13322 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
13329 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
13333 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
13366 /* terminate if an integral slack fractionality is unreliable or a negative continuous slack variable is present */
13369 if( ( scip->lp->rows[aggrrow->rowsinds[i]]->integral && ABS(aggrrow->rowweights[i] * scale) > large )
13370 || ( !scip->lp->rows[aggrrow->rowsinds[i]]->integral && aggrrow->rowweights[i] * aggrrow->slacksign[i] < 0.0 ) )
13396 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
13403 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
13413 SCIP_CALL( SCIPallocCleanBufferArray(scip, &( data->cutcoefs ), QUAD_ARRAY_SIZE(data->nvars)) );
13463 * 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.
13464 * 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.
13465 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
13469 SCIP_CALL( cutsTransformStrongCG(scip, data, sol, boundswitch, allowlocal, varsign, boundtype, &freevariable, &localbdsused) );
13490 SCIPdebug(printCutQuad(scip, NULL, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13501 * - 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)
13513 * 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
13514 * 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
13521 * 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)
13522 * 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)
13548 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13553 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
13557 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
13565 SCIP_CALL( cutsSubstituteStrongCG(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
13566 aggrrow->nrows, scale, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds, QUAD(f0), k) );
13567 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13569 /* remove all nearly-zero coefficients from strong CG row and relax the right hand side correspondingly in order to
13574 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, data->cutinds, data->cutcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
13578 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds);
13580 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13660/** creates a cut generation result structure and allocates arrays for cut coefficients and indices
13662 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
13699/** tries multiple cut generation methods on an aggregation row and returns the best cut by efficacy
13706 * Use SCIPcreateCutGenResult() to create the result structure, or manually set result->cutcoefs and result->cutinds
13710 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
13720 SCIP_CUTGENMETHOD methods, /**< bit field indicating which methods to try (SCIP_CUTGENMETHOD_*) */
13722 SCIP_CUTGENRESULT* result /**< pointer to result structure (cutcoefs and cutinds pre-allocated) */
13754 /* Each cut generation method writes to local variables and only succeeds if the generated cut has efficacy strictly
13762 SCIP_CALL( SCIPcalcFlowCover(scip, sol, params->postprocess, params->boundswitch, params->allowlocal, aggrrow,
13763 result->cutcoefs, &cutrhs, result->cutinds, &cutnnz, &efficacy, &cutrank, &cutislocal, &success) );
13782 result->cutcoefs, &cutrhs, result->cutinds, &cutnnz, &efficacy, &cutrank, &cutislocal, &success) );
13800 SCIP_CALL( SCIPcutGenerationHeuristicCMIR(scip, sol, params->postprocess, params->boundswitch,
13803 result->cutcoefs, &cutrhs, result->cutinds, &cutnnz, &efficacy, &cutrank, &cutislocal, &success) );
methods for certificate output
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:8268
static SCIP_RETCODE cutsRoundMIRSafely(SCIP *scip, SCIP_Real *RESTRICT cutcoefs, SCIP_Real *RESTRICT cutrhs, int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype, SCIP_INTERVAL f0)
Definition: cuts.c:5883
struct MIR_Data MIR_DATA
static SCIP_RETCODE findBestUb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, int *bestubtype)
Definition: cuts.c:4572
static SCIP_RETCODE findBestLbSafely(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype)
Definition: cuts.c:4175
static SCIP_RETCODE varVecAddScaledRowCoefsSafely(SCIP *scip, int *inds, SCIP_Real *vals, int *nnz, SCIP_ROW *row, SCIP_Real scale, SCIP_Real *rhschange, SCIP_Bool *success)
Definition: cuts.c:363
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:5272
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:12086
static SCIP_RETCODE postprocessCutSafely(SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, SCIP_Real *cutrhs, SCIP_Bool *success)
Definition: cuts.c:3899
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:11801
static SCIP_Bool removeZerosSafely(SCIP *scip, SCIP_Real minval, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz)
Definition: cuts.c:738
static SCIP_Real calcEfficacyDenseStorageQuad(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:661
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:833
static SCIP_RETCODE cutsRoundStrongCG(SCIP *scip, MIR_DATA *data, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k)
Definition: cuts.c:12916
static SCIP_RETCODE findBestUbSafely(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype)
Definition: cuts.c:4244
static SCIP_RETCODE cutsRoundMIR(SCIP *scip, MIR_DATA *data, int *RESTRICT varsign, int *RESTRICT boundtype, QUAD(SCIP_Real f0))
Definition: cuts.c:6721
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:13156
static SCIP_RETCODE computeLiftingData(SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
Definition: cuts.c:11232
static void doMIRBoundSubstitution(SCIP *scip, MIR_DATA *data, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:5020
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:9201
static SCIP_RETCODE getFlowCover(SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
Definition: cuts.c:10844
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:9330
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:12202
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:1063
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:1108
static SCIP_Real scaleValSafely(SCIP *scip, SCIP_Real val, SCIP_Real scale, SCIP_Bool cutislocal, SCIP_VAR *var, SCIP_Real *rhschange, SCIP_Bool *success)
Definition: cuts.c:1596
static SCIP_RETCODE findBestLb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, int *bestlbtype)
Definition: cuts.c:4509
static SCIP_RETCODE cutsTransformMIR(SCIP *scip, MIR_DATA *data, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
Definition: cuts.c:5554
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:9638
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:3833
static SCIP_RETCODE calcMIRSafely(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:7648
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:5191
static void destroyLiftingData(SCIP *scip, LIFTINGDATA *liftingdata)
Definition: cuts.c:11362
static void performBoundSubstitutionSimpleSafely(SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:5157
static SCIP_RETCODE findMIRBestLb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype)
Definition: cuts.c:4637
static SCIP_RETCODE varVecAddScaledRowCoefsQuad(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:251
static SCIP_Real calcEfficacyNormQuad(SCIP *scip, SCIP_Real *vals, int *inds, int nnz)
Definition: cuts.c:528
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:2114
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, 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:4814
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:926
struct LiftingData LIFTINGDATA
static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT(SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
Definition: cuts.c:10233
static SCIP_Real calcEfficacyDenseStorage(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:590
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:9458
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:3764
static void destroySNFRelaxation(SCIP *scip, SNF_RELAXATION *snf)
Definition: cuts.c:10213
static SCIP_RETCODE allocSNFRelaxation(SCIP *scip, SNF_RELAXATION *snf, int nvars)
Definition: cuts.c:10192
static SCIP_RETCODE addOneRowSafely(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *rowtoolong, SCIP_Bool *rowused, SCIP_Bool *success, SCIP_Bool *lhsused)
Definition: cuts.c:3382
static SCIP_Bool chgCoeffWithBoundSafely(SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal, SCIP_Real *cutrhs)
Definition: cuts.c:1153
static SCIP_RETCODE cutsSubstituteMIRSafely(SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, SCIP_INTERVAL f0)
Definition: cuts.c:6964
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:463
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:10328
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:11375
static SCIP_RETCODE cutsTransformStrongCG(SCIP *scip, MIR_DATA *data, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
Definition: cuts.c:12629
static SCIP_RETCODE cutTightenCoefsSafely(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Bool *redundant)
Definition: cuts.c:1669
static void getAlphaAndBeta(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
Definition: cuts.c:11195
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:7488
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:3268
static SCIP_RETCODE determineBestBoundsSafely(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:4310
static SCIP_RETCODE varVecAddScaledRowCoefsQuadScale(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, QUAD(SCIP_Real scale))
Definition: cuts.c:298
static void performBoundSubstitutionSafely(SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:5110
static SCIP_RETCODE cutsTransformMIRSafely(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 *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
Definition: cuts.c:5331
struct SNF_Relaxation SNF_RELAXATION
static SCIP_RETCODE cutTightenCoefsQuad(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
Definition: cuts.c:1218
static SCIP_Real evaluateLiftingFunction(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
Definition: cuts.c:11111
static SCIP_RETCODE varVecAddScaledRowCoefs(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:206
static SCIP_RETCODE findMIRBestUb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype)
Definition: cuts.c:4726
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:11995
methods for the aggregation rows
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success)
Definition: cons_knapsack.c:1091
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2115
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
Definition: misc.c:9641
SCIP_RETCODE SCIPaddCertificateMirInfo(SCIP *scip)
Definition: scip_certificate.c:643
SCIP_RETCODE SCIPaddCertificateAggrInfo(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW **aggrrows, SCIP_Real *weights, int naggrrows, SCIP_ROW **negslackrows, SCIP_Real *negslackweights, int nnegslackrows)
Definition: scip_certificate.c:533
void SCIPaggrRowCancelVarWithBound(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
Definition: cuts.c:3019
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
Definition: cuts.c:4016
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, 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:8350
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, 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:7934
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:2477
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:2679
SCIP_RETCODE SCIPaggrRowAddRowSafely(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype, SCIP_Bool *success)
Definition: cuts.c:2898
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:12302
SCIP_RETCODE SCIPcreateCutGenResult(SCIP *scip, SCIP_CUTGENRESULT **result)
Definition: cuts.c:13665
SCIP_RETCODE SCIPaggrRowCopy(SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
Definition: cuts.c:2769
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPaggrRowAddCustomCons(SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
Definition: cuts.c:3154
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, 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:13313
void SCIPfreeCutGenResult(SCIP *scip, SCIP_CUTGENRESULT **result)
Definition: cuts.c:13685
SCIP_RETCODE SCIPcalcBestCut(SCIP *scip, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_CUTGENMETHOD methods, SCIP_CUTGENPARAMS *params, SCIP_CUTGENRESULT *result)
Definition: cuts.c:13716
void SCIPaggrRowPrint(SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
Definition: cuts.c:2732
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition: cuts.c:3960
SCIP_Real * SCIPaggrRowGetRowWeights(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:4005
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition: cuts.c:2815
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:3534
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition: cuts.c:3078
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:11656
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition: cuts.c:3254
void SCIPintervalSetRoundingModeUpwards(void)
Definition: intervalarith.c:353
void SCIPintervalSetRoundingModeDownwards(void)
Definition: intervalarith.c:345
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
Definition: intervalarith.c:406
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:810
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
Definition: intervalarith.c:277
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
Definition: intervalarith.c:269
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:858
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
Definition: intervalarith.c:422
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:446
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:1128
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:989
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:1167
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
Definition: intervalarith.c:730
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
Definition: intervalarith.c:414
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
Definition: intervalarith.c:703
void SCIPintervalSetRational(SCIP_INTERVAL *resultant, SCIP_RATIONAL *value)
Definition: intervalarith.c:434
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:576
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_Bool SCIPrationalIsLTReal(SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1577
void SCIPrationalMult(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:1067
void SCIPrationalInvert(SCIP_RATIONAL *res, SCIP_RATIONAL *op)
Definition: rational.cpp:1324
SCIP_Real SCIPrationalGetReal(SCIP_RATIONAL *rational)
Definition: rational.cpp:2084
void SCIPrationalDiv(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:1133
void SCIPrationalSetReal(SCIP_RATIONAL *res, SCIP_Real real)
Definition: rational.cpp:604
void SCIPrationalFreeBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:474
void SCIPrationalDiff(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:984
SCIP_Bool SCIPrationalIsPositive(SCIP_RATIONAL *rational)
Definition: rational.cpp:1641
SCIP_RETCODE SCIPrationalCreateBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:124
SCIP_Bool SCIPrationalIsZero(SCIP_RATIONAL *rational)
Definition: rational.cpp:1625
void SCIPrationalSetRational(SCIP_RATIONAL *res, SCIP_RATIONAL *src)
Definition: rational.cpp:570
SCIP_Bool SCIPrationalIsGEReal(SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1607
SCIP_Bool SCIPrationalIsNegative(SCIP_RATIONAL *rational)
Definition: rational.cpp:1651
void SCIPrationalDiffReal(SCIP_RATIONAL *res, SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1010
SCIP_Real SCIPrationalRoundReal(SCIP_RATIONAL *rational, SCIP_ROUNDMODE_RAT roundmode)
Definition: rational.cpp:2109
SCIP_Bool SCIPrationalIsEQReal(SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1438
void SCIPrationalMultReal(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_Real op2)
Definition: rational.cpp:1098
SCIP_Bool SCIPrationalIsLE(SCIP_RATIONAL *rat1, SCIP_RATIONAL *rat2)
Definition: rational.cpp:1522
void SCIPrationalAddReal(SCIP_RATIONAL *res, SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:962
void SCIPrationalAddProdReal(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_Real op2)
Definition: rational.cpp:1211
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1903
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1920
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2176
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2108
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1763
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:823
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:488
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:771
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:462
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:784
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:797
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:872
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:475
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:810
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:436
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:449
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:696
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition: scip_var.c:8592
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: scip_var.c:8569
SCIP_RATIONAL * SCIPvarGetLbGlobalExact(SCIP_VAR *var)
Definition: var.c:24162
SCIP_RATIONAL * SCIPvarGetUbGlobalExact(SCIP_VAR *var)
Definition: var.c:24184
void SCIPselectWeightedDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortDownRealRealInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray, int len)
SCIP_Bool SCIPsortedvecFindDownReal(SCIP_Real *realarray, SCIP_Real val, int len, int *pos)
void SCIPsortDownReal(SCIP_Real *realarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortDownInt(int *intarray, int len)
void SCIPsortInt(int *intarray, int len)
interval arithmetics for provable bounds
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *intval)
Definition: lp.c:5099
internal methods for LP management
SCIP_Bool SCIProwExactHasFpRelax(SCIP_ROWEXACT *row)
Definition: lpexact.c:5089
memory allocation routines
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
internal miscellaneous methods
Definition: multiprecision.hpp:66
public methods for LP management
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for selecting k-medians
methods for sorting joint arrays of various types
public methods for problem variables
wrapper for rational number arithmetic
public methods for certified solving
public methods for cuts and aggregation rows
public methods for exact solving
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for SCIP variables
Definition: cuts.c:9159
Definition: cuts.c:4102
SCIP_Real QUAD(cutrhs)
Definition: struct_cuts.h:43
Definition: struct_certificate.h:63
Definition: struct_cuts.h:60
SCIP_BOUNDTYPE * boundtypesfortrans
Definition: struct_cuts.h:67
Definition: struct_cuts.h:74
Definition: intervalarith.h:55
Definition: struct_message.h:46
Definition: struct_certificate.h:78
Definition: struct_rational.h:47
Definition: struct_lpexact.h:187
Definition: struct_lp.h:205
Definition: struct_sol.h:74
Definition: struct_var.h:262
Definition: cuts.c:9179
Definition: struct_scip.h:72
data structures for certificate output
data structures for LP management
data structures for exact LP management
SCIP main data structure.
datastructures for global SCIP settings
type definitions for certificate output