cuts.c
Go to the documentation of this file.
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67/* =========================================== general static functions =========================================== */
106 SCIPquadprecProdQD(coef, coef, (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]])));
112 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]])));
116 SCIPquadprecProdQD(coef, coef, (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]])));
123 SCIPdebugMsgPrint(scip, " <= %.6f (activity: %g)\n", QUAD_TO_DBL(cutrhs), QUAD_TO_DBL(activity));
162 coef = coef * (sol == NULL ? SCIPvarGetLPSol(vars[cutinds[i]]) : SCIPgetSolVal(scip, sol, vars[cutinds[i]]));
168 coef = coef * (islocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]));
172 coef = coef * (islocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]));
196 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
241 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
284 * This is the quad precision version of varVecAddScaledRowCoefs() with a quad precision scaling factor.
288 int*RESTRICT inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
333/** add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
335 * In the safe variant, we need to transform all variables (implicitly) to nonnegative variables using their
336 * upper/lower bounds. When adding \f$\lambda * (c^Tx \le d)\f$ to \f$a^Tx \le b\f$, this results in:
344 * & \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
347 * This methods sums up the left hand side, and stores the change of the rhs due to the variable bounds in rhschange.
354 int* inds, /**< pointer to array with variable problem indices of non-zeros in variable vector */
403 SCIPintervalSetBounds(&valinterval, rowexact->valsinterval[i].inf, rowexact->valsinterval[i].sup);
407 if( SCIPisInfinity(scip, REALABS(valinterval.inf)) || SCIPisInfinity(scip, REALABS(valinterval.sup)) )
437 /* 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
457 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
515/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter */
519 SCIP_Real* vals, /**< array of the non-zero coefficients in the vector; this is a quad precision array! */
520 int* inds, /**< array of the problem indices of variables with a non-zero coefficient in the vector */
582 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
584 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
648/** calculates the cut efficacy for the given solution; the cut coefs are stored densely and in quad precision */
653 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut; this is a quad precision array! */
655 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
719/** safely (in the exact solving mode sense) remove all items with |a_i| or |u_i - l_i)| below the given value
732 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
761 /* for now we always use global bounds in exact solving mode (could be improved for local cuts in the future) */
828 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
921 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
930 /* loop over non-zeros and remove values below minval; values above QUAD_EPSILON are cancelled with their bound
1048/** change given coefficient to new given value, adjust right hand side using the variables bound;
1093/** change given (quad) coefficient to new given value, adjust right hand side using the variables bound;
1138/** change given coefficient to new given value, adjust right hand side using the variables bound;
1201/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1202 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse quad precision array;
1212 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1234 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1246 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1264 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1313 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
1314 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1334 if( chgQuadCoeffWithBound(scip, vars[cutinds[i]], QUAD(val), intval, cutislocal, QUAD(cutrhs)) )
1374 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1384 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1454 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1458 /* 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 */
1462 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1477 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1480 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1486 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1500 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1524 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1527 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1533 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
1547 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1571 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
1580/** multiplies a parameter for a variable in a row safely (using variable bounds and increasing the rhs)
1631 SCIPdebugMessage("Using lb %.17g corrected by %.17g. Change to rhs: %.17g \n", SCIPvarGetLbGlobal(var), -SCIPintervalGetSup(valinterval) + SCIPintervalGetInf(valinterval), *rhschange);
1638 SCIPdebugMessage("Using ub %.17g corrected by %.17g. Change to rhs: %.17g \n", SCIPvarGetUbGlobal(var), SCIPintervalGetSup(valinterval) - SCIPintervalGetInf(valinterval), *rhschange);
1652/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
1663 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1695 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
1707 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1726 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1777 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPepsilon(scip),
1778 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
1802 val = scaleValSafely(scip, val, intscalar, cutislocal, vars[cutinds[i]], &rhschange, &success);
1861 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
1871 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
1911 val = scaleValSafely(scip, val, equiscale, cutislocal, vars[cutinds[i]], &rhschange, &success);
1968 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
1979 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
1994 if( QUAD_TO_DBL(val) < 0.0 && SCIPisLE(scip, maxact + QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
1997 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2003 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2017 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2041 else if( QUAD_TO_DBL(val) > 0.0 && SCIPisLE(scip, maxact - QUAD_TO_DBL(val), QUAD_TO_DBL(*cutrhs)) )
2044 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2050 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2064 SCIPdebugPrintf("tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2088 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2099/** scales the cut and then tightens the coefficients of the given cut based on the maximal activity;
2100 * see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
2108 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
2132 /* compute maximal activity and maximal absolute coefficient values for all and for integral variables in the cut */
2145 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2163 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2211 SCIP_CALL( SCIPcalcIntegralScalar(intcoeffs, *cutnnz, -SCIPsumepsilon(scip), SCIPsumepsilon(scip),
2212 (SCIP_Longint)scip->set->sepa_maxcoefratio, scip->set->sepa_maxcoefratio, &intscalar, &success) );
2271 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2280 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2337 /* no coefficient tightening can be performed since the precondition doesn't hold for any of the variables */
2341 /* 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 */
2345 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
2363 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2369 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2383 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2409 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2415 /* if cut is integral, the true coefficient must also be integral; thus round it to exact integral value */
2429 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2452 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2461/** perform activity based coefficient tightening on the given cut; returns TRUE if the cut was detected
2471 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
2505 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2523 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2550 /* terminate, because coefficient tightening cannot be performed; also excludes the case in which no integral variable is present */
2557 /* loop over the integral variables and try to tighten the coefficients; see cons_linear for more details */
2560 /* due to sorting, we can exit if we reached a continuous variable: all further integral variables have 0 coefficents anyway */
2569 SCIP_Real lb = cutislocal ? SCIPvarGetLbLocal(vars[cutinds[i]]) : SCIPvarGetLbGlobal(vars[cutinds[i]]);
2582 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2610 SCIP_Real ub = cutislocal ? SCIPvarGetUbLocal(vars[cutinds[i]]) : SCIPvarGetUbGlobal(vars[cutinds[i]]);
2623 SCIPdebugMsg(scip, "tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
2648 else /* due to sorting we can stop completely if the precondition was not fulfilled for this variable */
2658/* =========================================== aggregation row =========================================== */
2663 * @note By default, this data structure uses quad precision via double-double arithmetic, i.e., it allocates a
2664 * SCIP_Real array of length two times SCIPgetNVars() for storing the coefficients. In exact solving mode, we
2665 * cannot use quad precision because we need to control the ronding mode, hence only the first SCIPgetNVars()
2750 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", QUAD_TO_DBL(val), SCIPvarGetName(vars[aggrrow->inds[i]]));
2773 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->vals, source->vals, QUAD_ARRAY_SIZE(nvars)) );
2784 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowsinds, source->rowsinds, source->nrows) );
2785 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->slacksign, source->slacksign, source->nrows) );
2786 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*aggrrow)->rowweights, source->rowweights, source->nrows) );
2830 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2831 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2832 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2850 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
2878 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
2885 * @note this method is the variant of SCIPaggrRowAddRow that is safe to use in exact solving mode
2918 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
2919 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
2920 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
2938 /* Automatically decide, whether we want to use the left or the right hand side of the row in the summation.
2966 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
2977 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
2991 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, aggrrow->inds, aggrrow->vals, &aggrrow->nnz, userow, weight, &sidevalchg, success) );
3001/** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
3002 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
3004 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
3006 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
3066/** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
3202 /* in exact solving mode, we do not use quad precision, because we need to control the rounding mode; hence, we only
3239/** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
3241 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
3253 * @note this method differs from SCIPaggrRowAddRow() by providing some additional parameters required for
3264 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3277 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
3296 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
3301 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
3342 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
3343 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
3344 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
3354 SCIP_CALL( varVecAddScaledRowCoefsQuad(aggrrow->inds, aggrrow->vals, &aggrrow->nnz, row, weight) );
3365 * @note this method differs from SCIPaggrRowAddRowSafely() by providing some additional parameters required for
3378 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3399 if( SCIPisFeasZero(scip, weight) || SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !allowlocal) )
3418 else if( SCIPisInfinity(scip, SCIProwGetRhs(row)) || (weight < 0.0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row))) )
3423 else if( (weight < 0.0 && !SCIPisInfinity(scip, -row->lhs)) || SCIPisInfinity(scip, row->rhs) )
3453 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
3471 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in cutsSubstituteMIRSafely() */
3493 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowsinds, aggrrow->rowssize, newsize) );
3494 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->slacksign, aggrrow->rowssize, newsize) );
3495 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggrrow->rowweights, aggrrow->rowssize, newsize) );
3505 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, aggrrow->inds, aggrrow->vals, &aggrrow->nnz, userow, weight, &sidevalchg, success) );
3519/** aggregate rows using the given weights; the current content of the aggregation row, \p aggrrow, is overwritten
3531 int negslack, /**< should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) */
3584 SCIP_CALL( addOneRow(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
3593 SCIP_CALL( addOneRowSafely(scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal,
3614 ((!lhsused && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant)) ||
3615 (lhsused && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) )
3624 SCIP_CALL( addOneRowSafely(scip, certificaterow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis,
3637 assert( (lhsused && weights[rowinds[k]] >= 0) || ((!lhsused) && weights[rowinds[k]] <= 0) || row->integral );
3657 SCIP_CALL( addOneRow(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
3666 SCIP_CALL( addOneRowSafely(scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack,
3687 ((!lhsused && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant)) ||
3688 (lhsused && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) )
3697 SCIP_CALL( addOneRowSafely(scip, certificaterow, rows[k], weights[k], sidetypebasis, allowlocal, 0,
3731 SCIP_CALL( SCIPaddCertificateAggrInfo(scip, certificaterow, usedrows, usedweights, certificaterow->nrows,
3760 SCIP_Bool* success /**< pointer to return whether post-processing was successful or cut is redundant */
3788 SCIP_CALL( cutTightenCoefs(scip, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz, &redundant) );
3807 *success = ! removeZeros(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(&rhs), cutinds, nnz);
3829 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
3845 if( removeZerosQuad(scip, SCIPfeastol(scip), cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz) )
3854 SCIP_CALL( cutTightenCoefsQuad(scip, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz, &redundant) );
3875 *success = ! removeZerosQuad(scip, minallowedcoef, cutislocal, cutcoefs, QUAD(cutrhs), cutinds, nnz);
3895 SCIP_Bool* success /**< pointer to return whether the cleanup was successful or if it is useless */
3922 SCIP_CALL( cutTightenCoefsSafely(scip, cutislocal, cutcoefs, cutrhs, cutinds, nnz, &redundant) );
3963 *valid = !removeZerosSafely(scip, SCIPsumepsilon(scip), aggrrow->vals, &rhs, aggrrow->inds, &aggrrow->nnz);
3968 *valid = ! removeZerosQuad(scip, SCIPsumepsilon(scip), useglbbounds ? FALSE : aggrrow->local, aggrrow->vals,
4027/** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
4077/* =========================================== c-MIR =========================================== */
4081/* In order to derive cuts, we partition the variable array up in (not necessarily contiguous) sections.
4082 * The only requirement we place on these sections is that section i can only have variable bounds variables whose section
4083 * is strictly greater than i. This way, we can process the variable array in a 'linear' manner. */
4085/* @todo maintain a DAG for used varbounds and use topological ordering instead, this would also allow
4160 * Currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences
4161 * in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code. */
4168 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4169 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4172 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4202 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
4207 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4208 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4229 * currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences
4230 * in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code. */
4237 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4238 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4241 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4270 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
4275 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4276 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4296/** determine the best bounds with respect to the given solution for complementing the given variable */
4303 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4304 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4305 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4306 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
4308 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4311 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4315 int* bestlbtype, /**< pointer to store type of the best lower bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4316 int* bestubtype, /**< pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4317 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
4361 *bestlb = vlbcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vlbvars[k]) : SCIPgetSolVal(scip, sol, vlbvars[k])) + vlbconsts[k];
4367 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4368 SCIP_CALL( findBestUbSafely(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
4399 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4400 *bestub = vubcoefs[k] * (sol == NULL ? SCIPvarGetLPSol(vubvars[k]) : SCIPgetSolVal(scip, sol, vubvars[k])) + vubconsts[k];
4406 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4407 SCIP_CALL( findBestLbSafely(scip, var, sol, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
4416 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4417 SCIP_CALL( findBestLbSafely(scip, var, sol, usevbds, allowlocal, bestlb, &simplelb, bestlbtype) );
4419 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4420 SCIP_CALL( findBestUbSafely(scip, var, sol, usevbds, allowlocal, bestub, &simpleub, bestubtype) );
4449 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
4502 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4503 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4505 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4533 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 && SCIPisGE(scip, bestvlb, *bestlb))) )
4538 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4539 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4565 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4566 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4568 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4596 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 && SCIPisLE(scip, bestvub, *bestub))) )
4601 /* we have to avoid cyclic variable bound usage, so we enforce to use only variable bounds variables of smaller index */
4602 /**@todo this check is not needed for continuous variables; but allowing all but binary variables
4624 * Differs from findBestLB() in that it allows more variable bound substitutions based on the variable sections. */
4631 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4632 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4635 int* bestlbtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4681 /* For now, we only allow variable bounds from sections that are strictly greater to prevent cyclic usage.*/
4682 /** @todo: We don't use the caching mechanism of SCIPvarGetClosestVLB() because the cached variable bound
4684 if( SCIPvarIsActive(vlbvars[i]) && boundedsection < varSection(data, SCIPvarGetProbindex(vlbvars[i])) &&
4713 * Differs from findBestUB() in that it allows more variable bound substitutions based on the variable sections. */
4720 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4721 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4724 int* bestubtype /**< pointer to store best bound type (-2: local bound, -1: global bound, >= 0 variable bound index) */
4770 /* For now, we only allow variable bounds from sections that are strictly greater to prevent cyclic usage.*/
4771 /** @todo: We don't use the caching mechanism of SCIPvarGetClosestVLB() because the cached variable bound
4773 if( SCIPvarIsActive(vubvars[i]) && boundedsection < varSection(data, SCIPvarGetProbindex(vubvars[i])) &&
4801/** determine the best bounds with respect to the given solution for complementing the given variable */
4808 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
4809 int usevbds, /**< should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) */
4810 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
4811 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
4813 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
4816 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
4820 int* bestlbtype, /**< pointer to store type of best lower bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4821 int* bestubtype, /**< pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) */
4822 SCIP_BOUNDTYPE* selectedbound, /**< pointer to store whether the lower bound or the upper bound should be preferred */
4877 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4878 SCIP_CALL( findMIRBestUb(scip, var, sol, data, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestub, &simpleub, bestubtype) );
4917 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4918 SCIP_CALL( findMIRBestLb(scip, var, sol, data, fixintegralrhs ? usevbds : 0, allowlocal && fixintegralrhs, bestlb, &simplelb, bestlbtype) );
4927 /* find closest lower bound in standard lower bound (and variable lower bounds for continuous variables) */
4928 SCIP_CALL( findMIRBestLb(scip, var, sol, data, usevbds, allowlocal, bestlb, &simplelb, bestlbtype) );
4930 /* find closest upper bound in standard upper bound (and variable upper bounds for continuous variables) */
4931 SCIP_CALL( findMIRBestUb(scip, var, sol, data, usevbds, allowlocal, bestub, &simpleub, bestubtype) );
4960 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !SCIPisEQ(scip, *bestlb - simplelb, simpleub - *bestub) )
5015 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5017 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5092/** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index
5106 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5108 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5139/** performs the bound substitution step with the simple bound for the variable with the given problem index
5152 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5154 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5178/** performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index */
5189 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5191 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5259/** performs the bound substitution step with the simple bound for the variable with the given problem index */
5267 SCIP_Real boundval, /**< array of best bound to be used for the substitution for each nonzero index */
5269 SCIP_Bool* localbdsused /**< pointer to updated whether a local bound was used for substitution */
5294 * 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},\\
5295 * 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},
5303 * 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.} \\
5304 * 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.}
5307 * 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:
5323 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5325 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5326 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
5328 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
5331 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
5340 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
5341 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5379 /* start with continuous variables, because using variable bounds can affect the untransformed integral
5380 * variables, and these changes have to be incorporated in the transformation of the integral variables
5392 SCIP_CALL( determineBestBoundsSafely(scip, vars[cutinds[i]], sol, boundswitch, usevbds ? 2 : 0, allowlocal, fixintegralrhs,
5394 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
5416 performBoundSubstitutionSafely(scip, cutcoefs, cutrhs, varsign[i], boundtype[i], bestlbs[i], v, localbdsused);
5426 performBoundSubstitutionSafely(scip, cutcoefs, cutrhs, varsign[i], boundtype[i], bestubs[i], v, localbdsused);
5441 /* remove integral variables that now have a zero coefficient due to variable bound usage of continuous variables
5449 /* determine the best bounds for the integral variable, usevbd can be set to 0 here as vbds are only used for continuous variables */
5450 SCIP_CALL( determineBestBoundsSafely(scip, vars[v], sol, boundswitch, 0, allowlocal, fixintegralrhs,
5452 bestlbs + i, bestubs + i, bestlbtypes + i, bestubtypes + i, selectedbounds + i, freevariable) );
5461 /* now perform the bound substitution on the remaining integral variables which only uses standard bounds */
5476 performBoundSubstitutionSimpleSafely(scip, cutcoefs, cutrhs, boundtype[i], bestlbs[i], v, localbdsused);
5487 performBoundSubstitutionSimpleSafely(scip, cutcoefs, cutrhs, boundtype[i], bestubs[i], v, localbdsused);
5521 * 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},\\
5522 * 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},
5530 * 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.} \\
5531 * 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.}
5534 * 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:
5547 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
5548 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
5549 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
5551 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
5554 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
5561 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
5562 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
5622 SCIP_CALL( determineBestBounds(scip, data->vars[v], sol, data, boundswitch, usevbds, allowlocal, fixintegralrhs,
5640 /* if we terminate early, we need to make sure all the zeros in the cut coefficient array are cancelled */
5729 newrhs = QUAD_TO_DBL(data->cutrhs) + varsign[i] * QUAD_TO_DBL(coef) * (bestlbs[i] - bestubs[i]);
5759 /* prefer larger violations; for equal violations, prefer smaller f0 values since then the possibility that
5762 if( SCIPisGT(scip, violgain, bestviolgain) || (SCIPisGE(scip, violgain, bestviolgain) && newf0 < bestnewf0) )
5791 assert(bestubtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
5798 assert(bestlbtypes[besti] < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
5819/** 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$
5834 * 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}, \\
5835 * 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},
5850 * 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)} \\
5851 * 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)}
5864 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
5876 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
5879 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
5903 /* 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 */
5915 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
5923 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
5981 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
5985 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6006 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6010 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6027 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6084 /* now process the continuous variables; postpone deletetion of zeros till all continuous variables have been processed */
6112 SCIPintervalMulScalar(SCIPinfinity(scip), &cutaj, onedivoneminusf0, aj); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
6139 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6209/** 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$
6224 * 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} \\
6225 * 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}
6240 * 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)} \\
6241 * 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)}
6254 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
6266 int*RESTRICT cutinds, /**< array of variables problem indices for non-zero coefficients in cut */
6269 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
6296 /* 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 */
6306 /* Loop backwards to process integral variables first and be able to delete coefficients of integral variables
6314 /*in debug mode check that all continuous variables of the aggrrow come before the integral variables */
6370 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6374 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6396 boundval = mirinfo->localbdused[v] ? SCIPvarGetUbLocalExact(var) : SCIPvarGetUbGlobalExact(var);
6400 boundval = mirinfo->localbdused[v] ? SCIPvarGetLbLocalExact(var) : SCIPvarGetLbGlobalExact(var);
6411 /* remove zero cut coefficients from cut, only remove positive coefficients in exact solving mode */
6431 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6437 assert(SCIPrationalRoundReal(SCIPvarGetLbGlobalExact(var), SCIP_R_ROUND_DOWNWARDS) == SCIPvarGetLbGlobal(var));
6440 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetLbGlobal(var) */
6446 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetLbLocal(var) */
6454 assert(SCIPrationalRoundReal(SCIPvarGetUbGlobalExact(var), SCIP_R_ROUND_UPWARDS) == SCIPvarGetUbGlobal(var));
6457 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetUbGlobal(var) */
6463 SCIPquadprecSumQD(*cutrhs, *cutrhs, SCIPrationalRoundReal(tmp, SCIP_R_ROUND_UPWARDS)); /* rhs += cutaj * SCIPvarGetUbLocal(var) */
6469 /* now process the continuous variables; postpone deletetion of zeros till all continuous variables have been processed */
6503 SCIPrationalMultReal(cutaj, cutaj, QUAD_TO_DBL(aj)); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
6537 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6543 assert(SCIPrationalRoundReal(SCIPvarGetLbGlobalExact(var), SCIP_R_ROUND_DOWNWARDS) == SCIPvarGetLbGlobal(var));
6560 assert(SCIPrationalRoundReal(SCIPvarGetUbGlobalExact(var), SCIP_R_ROUND_UPWARDS) == SCIPvarGetUbGlobal(var));
6659/** 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$
6674 * 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} \\
6675 * 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}
6690 * 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)} \\
6691 * 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)}
6704 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\
6714 int*RESTRICT boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) */
6732 /* Loop backwards through the sections, so that the reversing of varbound substitutions does not prematurely effect
6733 * the coefficients of variables in other sections, because the section index of a variable bound must always be
6744 /* iterate backwards over indices in section, so we can easily shrink the section if we find zeros */
6823 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
6914 /* Finally, store the relevant data in cutinds which is the array used by the other functions */
6931 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
6932 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r]. \f$
6934 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
6938 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f_0)/(1 - f_0),& \mbox{if}\qquad f_r > f_0 \\
6944 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7040 ((slacksign[i] == +1 && SCIPrealIsExactlyIntegral(row->rhs) && SCIPrealIsExactlyIntegral(row->constant))
7041 || (slacksign[i] == -1 && SCIPrealIsExactlyIntegral(row->lhs) && SCIPrealIsExactlyIntegral(row->constant))) ) /*lint !e613*/
7075 SCIPdebugMessage("fractionality %g, f0 %g -> round up! splitcoef %g sub-coefficient %g", fr.inf, f0.inf, splitcoef, cutar.inf);
7088 SCIPintervalMul(SCIPinfinity(scip), &cutar, onedivoneminusf0, ar); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
7089 SCIPdebugMessage("resubstituting negative continuous slack for row %s with coef %g\n", row->name, cutar.inf);
7110 /* save the value for the split disjunction for the integer slack and the continous part (for rounded up we
7149 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, cutinds, cutcoefs, nnz, userow, mult, &sidevalchg, &success) );
7168 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7188 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7212 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7215 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7219 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\
7225 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7316 || (slacksign[i] == -1 && SCIPisFeasIntegral(scip, row->lhs - row->constant))) ) /*lint !e613*/
7328 if( SCIPisLE(scip, QUAD_TO_DBL(fr), QUAD_TO_DBL(f0)) && (!SCIPisExact(scip) || QUAD_TO_DBL(fr) <= QUAD_TO_DBL(f0)) )
7350 SCIPrationalMult(cutar, ar, onedivoneminusf0); /* cutaj = varsign[i] * aj * onedivoneminusf0; // a^_j */
7387 SCIP_CALL( varVecAddScaledRowCoefsSafely(scip, cutinds, cutcoefs, nnz, userow, mult, &sidevalchg, &success) );
7405 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7427 /* this is disabled because we can't certify it yet in exact solving mode; if enabled change also in addOneRowSafely() */
7461 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7464 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7468 * & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\
7474 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
7621/** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
7624 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7641 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7643 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7644 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
7645 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
7648 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
7654 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
7655 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
7656 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
7657 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
7659 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
7660 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
7661 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
7740 * 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.
7741 * 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.
7742 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
7746 SCIP_CALL( cutsTransformMIRSafely(scip, sol, boundswitch, usevbds, allowlocal, fixintegralrhs, FALSE,
7747 boundsfortrans, boundtypesfortrans, tmpcoefs, &rhs, tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
7768 * 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
7769 * 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
7776 * 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)
7777 * 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)
7790 SCIP_MIRINFO* mirinfo = SCIPgetCertificate(scip)->mirinfo[SCIPgetCertificate(scip)->nmirinfos - 1];
7813 SCIP_CALL( cutsRoundMIRSafely(scip, tmpcoefs, &rhs, tmpinds, &tmpnnz, varsign, boundtype, f0interval) ); /*lint !e644*/
7821 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
7825 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
7834 SCIP_CALL( cutsSubstituteMIRSafely(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
7845 SCIP_CALL( postprocessCutSafely(scip, tmpislocal, tmpinds, tmpcoefs, &tmpnnz, &rhs, success) );
7859 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
7910/** calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because
7913 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
7927 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
7932 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
7933 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
7934 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
7937 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
7943 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy */
7944 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut if its efficacy improves cutefficacy */
7945 int* cutinds, /**< array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy */
7946 int* cutnnz, /**< pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy */
7948 int* cutrank, /**< pointer to return rank of generated cut or NULL if it improves cutefficacy */
7949 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally if it improves cutefficacy */
7950 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy */
7969 return calcMIRSafely(scip, sol, postprocess, boundswitch, vartypeusevbds > 0 ? TRUE : FALSE, allowlocal, fixintegralrhs,
7994 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
8001 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
8011 SCIP_CALL( SCIPallocCleanBufferArray(scip, &( data->cutcoefs ), QUAD_ARRAY_SIZE(data->nvars)) );
8046 SCIPdebug( printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, nnz, FALSE, FALSE) );
8064 * 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.
8065 * 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.
8066 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
8082 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8095 * 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
8096 * 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
8103 * 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)
8104 * 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)
8136 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8141 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
8145 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
8158 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
8162 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
8165 SCIP_CALL( postprocessCutQuad(scip, tmpislocal, data->cutinds, data->cutcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
8169 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), tmpislocal, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds);
8173 SCIPdebug( printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE) );
8177 SCIP_Real mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, data->cutcoefs, QUAD_TO_DBL(data->cutrhs), data->cutinds, data->ncutinds);
8179 if( SCIPisEfficacious(scip, mirefficacy) && (cutefficacy == NULL || mirefficacy > *cutefficacy) )
8325 * Given the aggregation, it is transformed to a mixed knapsack set via complementation (using bounds or variable bounds)
8328 * so one would prefer to have integer coefficients for integer variables which are far away from their bounds in the
8331 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
8343 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
8348 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
8350 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
8353 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
8360 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
8362 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
8365 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
8412 /* The +4 comes from a few rules that create extra delta candidates, see usages of ndeltacands. */
8415 /* we only compute bound distance for integer variables; by variable bound substitution, the number of integer variables
8438 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
8445 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
8502 * 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.
8503 * 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.
8504 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
8509 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, varsign, boundtype, &freevariable, &localbdsused) );
8512 /* Use aliases to stay more consistent with the old code. mksetrhs needs to synchronize its values data->cutrhs
8523 SCIPdebug( printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE) );
8556 /* Check that the continuous and implied integer variables and integer variables are partitioned */
8576 SCIP_CALL( SCIPcalcIntegralScalar(deltacands, nbounddist, -SCIPepsilon(scip), SCIPsumepsilon(scip), (SCIP_Longint)10000, 10000.0, &intscale, &intscalesuccess) );
8646 * 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
8647 * 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
8654 * 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)
8655 * 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)
8848 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, deltacands[i], ntmpcoefs, minfrac, maxfrac);
8871 efficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(mksetrhs), contactivity, contsqrnorm, delta, ntmpcoefs, minfrac, maxfrac);
8881 /* try to improve efficacy by switching complementation of integral variables that are not at their bounds
8923 tmpvalues[k - intstart] = varsign[k] == +1 ? bestub - SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) : SCIPgetSolVal(scip, sol, vars[mksetinds[k]]) - bestlb;
8926 newefficacy = computeMIREfficacy(scip, tmpcoefs, tmpvalues, QUAD_TO_DBL(newrhs), contactivity, contsqrnorm, bestdelta, ntmpcoefs, minfrac, maxfrac);
8938 assert(bestubtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
8945 assert(bestlbtype < 0); /* cannot switch to a variable bound (would lead to further coef updates) */
8986 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(mksetrhs), mksetinds, mksetnnz, FALSE, FALSE));
8995 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
8999 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
9003 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
9012 aggrrow->nrows, scale, mksetcoefs, QUAD(&data->cutrhs), mksetinds, &data->ncutinds, QUAD(f0)) );
9015 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
9029 SCIPdebugMsg(scip, "efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
9036 /* remove all nearly-zero coefficients from MIR row and relax the right hand side correspondingly in order to
9041 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, mksetinds, mksetcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
9045 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, mksetcoefs, QUAD(&data->cutrhs), mksetinds, &data->ncutinds);
9049 SCIPdebug(printCutQuad(scip, sol, mksetcoefs, QUAD(data->cutrhs), mksetinds, data->ncutinds, FALSE, FALSE));
9053 mirefficacy = calcEfficacyDenseStorageQuad(scip, sol, mksetcoefs, QUAD_TO_DBL(data->cutrhs), mksetinds, data->ncutinds);
9129/* =========================================== flow cover =========================================== */
9141#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds used for snf relaxation */
9158 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$ */
9159 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$ */
9161 SCIP_Real mp; /**< smallest variable bound coefficient of variable in \f$ C^{++} (min_{j \in C++} u_j) \f$ */
9165/** structure that contains all the data that defines the single-node-flow relaxation of an aggregation row */
9177 SCIP_Real* aggrcoefsbin; /**< aggregation coefficient of the original binary var used to define the
9179 SCIP_Real* aggrcoefscont; /**< aggregation coefficient of the original continuous var used to define the
9181 SCIP_Real* aggrconstants; /**< aggregation constant used to define the continuous variable in the relaxed set */
9184/** get solution value and index of variable lower bound (with binary variable) which is closest to the current LP
9185 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
9186 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
9199 SCIP_Real* closestvlb, /**< pointer to store the LP sol value of the closest variable lower bound */
9200 int* closestvlbidx /**< pointer to store the index of the closest vlb; -1 if no vlb was found */
9208 assert(bestsub == SCIPvarGetUbGlobal(var) || bestsub == SCIPvarGetUbLocal(var)); /*lint !e777*/
9253 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
9261 /* check if current variable lower bound l~_i * x_i + d_i imposed on y_j meets the following criteria:
9265 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k yet
9313/** get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP
9314 * solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity
9315 * of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the
9329 SCIP_Real* closestvub, /**< pointer to store the LP sol value of the closest variable upper bound */
9330 int* closestvubidx /**< pointer to store the index of the closest vub; -1 if no vub was found */
9338 assert(bestslb == SCIPvarGetLbGlobal(var) || bestslb == SCIPvarGetLbLocal(var)); /*lint !e777*/
9383 /* if the variable is not active the problem index is -1, so we cast to unsigned int before the comparison which
9395 * 0. no other non-binary variable y_k has used a variable bound with x_i to get transformed variable y'_k
9443/** determines the bounds to use for constructing the single-node-flow relaxation of a variable in
9453 int varposinrow, /**< position of variable in the rowinds array for which the bounds should be determined */
9457 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
9458 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
9463 int* bestlbtype, /**< pointer to store type of best lower bound (-2: local bound, -1: global bound, >= 0 variable bound index) */
9464 int* bestubtype, /**< pointer to store type of best upper bound (-2: local bound, -1: global bound, >= 0 variable bound index) */
9467 SCIP_BOUNDTYPE* selectedbounds, /**< pointer to store the preferred bound for the transformation */
9494 SCIP_CALL( findBestLb(scip, var, sol, 0, allowlocal, &bestslb[varposinrow], &bestslbtype[varposinrow]) );
9495 SCIP_CALL( findBestUb(scip, var, sol, 0, allowlocal, &bestsub[varposinrow], &bestsubtype[varposinrow]) );
9506 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef, SCIPvarGetName(var), probidx,
9507 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
9509 /* mixed integer set cannot be relaxed to 0-1 single node flow set because both simple bounds are -infinity
9512 if( SCIPisInfinity(scip, -bestslb[varposinrow]) && SCIPisInfinity(scip, bestsub[varposinrow]) )
9518 /* get closest lower bound that can be used to define the real variable y'_j in the 0-1 single node flow
9531 SCIP_CALL( getClosestVlb(scip, var, sol, rowcoefs, binvarused, bestsub[varposinrow], rowcoef, &bestvlb, &bestvlbidx) );
9540 /* get closest upper bound that can be used to define the real variable y'_j in the 0-1 single node flow
9553 SCIP_CALL( getClosestVub(scip, var, sol, rowcoefs, binvarused, bestslb[varposinrow], rowcoef, &bestvub, &bestvubidx) );
9561 SCIPdebugMsg(scip, " bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
9563 /* mixed integer set cannot be relaxed to 0-1 single node flow set because there are no suitable bounds
9574 /* select best upper bound if it is closer to the LP value of y_j and best lower bound otherwise and use this bound
9575 * to define the real variable y'_j with 0 <= y'_j <= u'_j x_j in the 0-1 single node flow relaxation;
9578 if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
9582 else if( SCIPisEQ(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
9587 else if( SCIPisLE(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
9593 assert(SCIPisGT(scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
9623/** construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set
9630 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
9631 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
9638 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
9661 SCIPdebugMsg(scip, "--------------------- construction of SNF relaxation ------------------------------------\n");
9679 /* array to store whether a binary variable is in the row (-1) or has been used (1) due to variable bound usage */
9693 SCIP_CALL( determineBoundForSNF(scip, sol, vars, rowcoefs, rowinds, i, binvarused, allowlocal, boundswitch,
9694 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
9763 /* store for y_j that bestlb is the bound used to define y'_j and that y'_j is the associated real variable
9793 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9821 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
9822 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9823 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestsub), QUAD_TO_DBL(rowcoef), bestsub[i], QUAD_TO_DBL(transrhs));
9839 * 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
9871 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9900 SCIPdebugMsg(scip, " --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
9901 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9902 snf->ntransvars, SCIPvarGetName(vlbvars[bestlbtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvlbconst), QUAD_TO_DBL(rowcoef),
9945 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
9973 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
9974 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
9975 snf->ntransvars, QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesbestslb), QUAD_TO_DBL(rowcoef), bestslb[i], QUAD_TO_DBL(transrhs));
9992 * 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,
10021 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
10050 /* store for x_j that y'_j is the associated real variable in the 0-1 single node flow relaxation */
10052 SCIPdebugMsg(scip, " --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
10053 snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars, snf->transvarvubcoefs[snf->ntransvars],
10054 snf->ntransvars, SCIPvarGetName(vubvars[bestubtype[i]]), QUAD_TO_DBL(transrhs) + QUAD_TO_DBL(rowcoeftimesvubconst), QUAD_TO_DBL(rowcoef),
10098 SCIPdebugMsg(scip, " %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n", i, QUAD_TO_DBL(rowcoef), SCIPvarGetName(var), probidx, varsolval,
10111 /* store aggregation information for y'_j for transforming cuts for the SNF relaxation back to the problem variables later */
10138 assert(snf->transvarcoefs[snf->ntransvars] == 1 || snf->transvarcoefs[snf->ntransvars] == - 1 );
10144 SCIPdebugMsg(scip, " --> ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s))\n", snf->transvarcoefs[snf->ntransvars] == 1 ? "+" : "-", snf->ntransvars, snf->ntransvars,
10218/** solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide
10258 /* allocate memory for temporary array used for sorting; array should contain profits divided by corresponding weights (p_1 / w_1 ... p_n / w_n )*/
10269 SCIPselectWeightedDownRealRealInt(tempsort, profits, items, weights, mediancapacity, nitems, &criticalitem);
10313/** build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished
10328 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10392/** checks whether the given scalar scales the given value to an integral number with error in the given bounds */
10397 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
10398 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
10415/** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
10422 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
10423 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
10446 * 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
10454 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10498 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
10538 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
10603 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10604 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
10612 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10613 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
10627 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
10639 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
10640 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
10645 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
10646 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
10651 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
10654 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
10675 * solve KP^SNF_int exactly, if a suitable factor C is found and (nitems*capacity) <= MAXDYNPROGSPACE,
10689 SCIP_CALL( SCIPcalcIntegralScalar(transweightsreal, nitems, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE, &scalar,
10693 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
10728 SCIP_CALL( SCIPsolveKnapsackExactly(scip, nitems, transweightsint, transprofitsint, transcapacityint,
10745 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10753 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10761 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
10763 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
10767 /* if the found structure is not a flow cover, because of scaling, solve KP^SNF_rat approximately */
10773 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
10775#ifdef SCIP_DEBUG /* this time only for SCIP_DEBUG, because only then, the variable is used again */
10785 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
10808 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
10828 * \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$,
10838 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
10873 SCIPdebugMsg(scip, "--------------------- get flow cover ----------------------------------------------------\n");
10905 assert(SCIPisFeasGE(scip, snf->transbinvarsolvals[j], 0.0) && SCIPisFeasLE(scip, snf->transbinvarsolvals[j], 1.0));
10972 * 1. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10973 * positive weights and the constraint is a "<" constraint, by complementing all variables in N1
10981 * 2. to a knapsack problem in maximization form, such that all variables in the knapsack constraint have
10982 * positive integer weights and the constraint is a "<=" constraint, by complementing all variables in N1
10996 /* get weight and profit of variables in KP^SNF_rat and check, whether all weights are already integral */
11004 SCIPdebugMsg(scip, " <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
11005 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
11010 SCIPdebugMsg(scip, " <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
11011 items[j], transprofitsreal[j], SCIPisIntegral(scip, transweightsreal[j]) ? "" : " ----> NOT integral");
11015 transcapacityreal = - snf->transrhs + QUAD_TO_DBL(flowcoverweight) + n1itemsweight; /*lint !e644*/
11016 SCIPdebugMsg(scip, " transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
11019 /* there exists no flow cover if the capacity of knapsack constraint in KP^SNF_rat after fixing
11041 /* initialize number of (non-)solution items, should be changed to a nonnegative number in all possible paths below */
11047 SCIP_CALL( SCIPsolveKnapsackApproximatelyLT(scip, nitems, transweightsreal, transprofitsreal, transcapacityreal,
11053 /* build the flow cover from the solution of KP^SNF_rat and KP^SNF_int, respectively and the fixing */
11055 buildFlowCover(scip, snf->transvarcoefs, snf->transvarvubcoefs, snf->transrhs, solitems, nonsolitems, nsolitems, nnonsolitems, nflowcovervars,
11078 SCIPdebugMsg(scip, " flowcoverweight(%g) = rhs(%g) + lambda(%g)\n", QUAD_TO_DBL(flowcoverweight), snf->transrhs, *lambda);
11096/** evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities
11224 int* transvarflowcoverstatus, /**< pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) */
11334 SCIP_UNUSED( SCIPsortedvecFindDownReal(liftingdata->m, liftingdata->mp, liftingdata->r, &liftingdata->t) );
11335 assert(liftingdata->m[liftingdata->t] == liftingdata->mp || SCIPisInfinity(scip, liftingdata->mp)); /*lint !e777*/
11341 while( liftingdata->t < liftingdata->r && liftingdata->m[liftingdata->t] == liftingdata->mp ) /*lint !e777*/
11368 int* flowcoverstatus, /**< pointer to store whether variable is in flow cover (+1) or not (-1) */
11446 SCIP_Real liftedbincoef = evaluateLiftingFunction(scip, &liftingdata, snf->transvarvubcoefs[i]);
11592 /* a*x + c + s == rhs => s == - a*x - c + rhs: move a^_r * (rhs - c) to the right hand side */
11629/** calculates a lifted simple generalized flow cover cut out of the weighted sum of LP rows given by an aggregation row; the
11630 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
11634 * Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs.
11637 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
11649 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
11650 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
11654 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
11658 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
11680 SCIPdebug( printCutQuad(scip, sol, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, FALSE, aggrrow->local) );
11682 SCIP_CALL( constructSNFRelaxation(scip, sol, boundswitch, allowlocal, aggrrow->vals, QUAD(aggrrow->rhs), aggrrow->inds, aggrrow->nnz, &snf, success, &localbdsused) );
11693 SCIP_CALL( getFlowCover(scip, &snf, &nflowcovervars, &nnonflowcovervars, transvarflowcoverstatus, &lambda, success) );
11702 SCIP_CALL( generateLiftedFlowCoverCut(scip, &snf, aggrrow, transvarflowcoverstatus, lambda, tmpcoefs, cutrhs, cutinds, cutnnz, success) );
11705 /* if success is FALSE generateLiftedFlowCoverCut wont have touched the tmpcoefs array so we dont need to clean it then */
11717 *success = ! removeZeros(scip, SCIPsumepsilon(scip), *cutislocal, tmpcoefs, QUAD(&rhs), cutinds, cutnnz);
11759/* =========================================== knapsack cover =========================================== */
11761/** Relax the row to a possibly fractional knapsack row containing no integer or continuous variables
11762 * and only having positive coefficients for binary variables. General integer and continuous variables
11763 * are complemented with variable or simple bounds such that their coefficient becomes positive and then
11765 * All remaining binary variables are complemented with simple upper or lower bounds such that their
11772 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
11780 SCIP_Bool* localbdsused, /**< pointer to store whether local bounds were used in transformation */
11781 SCIP_Bool* success /**< stores whether the row could successfully be transformed into a knapsack constraint.
11802 /* start with continuous variables, because using variable bounds can affect the untransformed binary
11803 * variables, and these changes have to be incorporated in the transformation of the binary variables
11811 /* determine best bounds for the continuous and general integer variables such that they will have
11822 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable
11824 SCIP_CALL( findBestLb(scip, vars[v], sol, SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS ? 1 : 0, allowlocal, bestbds + i, boundtype + i) );
11834 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable
11836 SCIP_CALL( findBestUb(scip, vars[v], sol, SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS ? 1 : 0, allowlocal, bestbds + i, boundtype + i) );
11855 performBoundSubstitution(scip, cutinds, cutcoefs, QUAD(cutrhs), nnz, varsign[i], boundtype[i], bestbds[i], v, localbdsused);
11864 /* remove non-binary variables because their coefficients have been set to zero after bound substitution */
11872 /* after doing bound substitution of non-binary vars, some coefficients of binary vars might have changed, so here we
11873 * remove the ones that became 0 if any; also, we need that all remaining binary vars have positive coefficients,
11889 /* due to variable bound usage for bound substitution of continuous variables cancellation may have occurred */
11912 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestub, v, localbdsused);
11924 performBoundSubstitutionSimple(scip, cutcoefs, QUAD(cutrhs), boundtype[i], bestlb, v, localbdsused);
11937 /* increase i or remove zero coefficient (i.e. var with 0 coef) by shifting last nonzero to current position */
11967 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
11971 int* coverstatus, /**< array to return the coverstatus for each variable in the knapsack row */
12023 SCIPsortDownRealInt(covervals + (*coversize), coverpos + (*coversize), cutnnz - (*coversize));
12046 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(*coverweight), cutrhs);
12057 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
12064 int* coverstatus, /**< coverstatus for each variable in the cover. After calling this function
12125 /* now we partition C into C^+ and C^-, where C^+ are all the elements of C whose weight is strictly larger than
12126 * \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
12127 * compute S^-(h) = sum of the h largest a_i^- and store S^-(h+1) in in covervals[h], for k = 0, ..., coversize - 1
12129 * we remember which elements of C^- in coverstatus, so that element in C^+ have coverstatus 1 and
12143 /* coefficient is in C^+ because it is greater than \bar{a} and contributes only \bar{a} to the sum */
12146 /* rather be on the safe side in numerical corner cases and relax the coefficient to exactly \bar{a}.
12147 * In that case the coefficient is not treated as in C^+ but as being <= \bar{a} and therefore in C^-.
12177 SCIP_Real* scale /**< pointer to update the scale to integrality when a fractional value is returned */
12186 /* the lifted value is at least the coeficient (a_k) divided by \bar{a} because the largest value
12195 /* if the coefficient is below \bar{a}, i.e. a / \bar{a} < 1 then g(a_k) = 0, otherwise g(a_k) > 0 */
12199 /* we perform h = MIN(h, coversize) in floating-point first because on some instances h was seen to exceed the range
12221 /* decrease by one to make sure rounding errors or coefficients that are larger than the right hand side by themselves
12227 * (todo: variables that have a coefficient above the right hand side can get an arbitrarily large coefficient but can
12228 * also be trivially fixed using the base row. Currently they get the coefficient |C| which is 1 above the right hand
12229 * side in the cover cut so that they can still be trivially fixed by propagating the cover cut.
12230 * We do not want to apply fixings here though because the LP should stay flushed during separation.
12231 * Possibly add a parameter to return additional fixings to the caller of the SCIPcalc*() functions in here
12237 /* compare with standard epsilon tolerance since computation involves abar, which is computed like an activity */
12248 SCIPdebugMsg(scip, "lifted coef %g < %g <= %g to %g\n", h == 0 ? 0 : covervals[h-1], QUAD_TO_DBL(x),
12254/** calculates a lifted knapsack cover cut out of the weighted sum of LP rows given by an aggregation row; the
12255 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
12259 * Letchford, A. N., & Souli, G. (2019). On lifted cover inequalities: A new lifting procedure with unusual properties.
12262 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
12273 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
12277 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
12281 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
12358 /* Transform aggregated row into a (fractional, i.e. with possibly fractional weights) knapsack constraint.
12360 * so that only binary variables remain and complements those such that they have a positive coefficient.
12374 if( !computeInitialKnapsackCover(scip, sol, tmpcoefs, tmpinds, QUAD_TO_DBL(rhs), nnz, varsign, coverstatus,
12378 SCIPdebugMsg(scip, "coverweight is %g and right hand side is %g\n", QUAD_TO_DBL(coverweight), QUAD_TO_DBL(rhs));
12424 * - 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
12445 { /* variables is either in C^+ or not in the cover and its coefficient value is computed with the lifing function */
12451 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));
12454 cutcoef = evaluateLiftingFunctionKnapsack(scip, QUAD(coef), QUAD(abar), covervals, coversize, cplussize, &scale);
12472 /* variable was complemented so we have cutcoef * (1-x) = cutcoef - cutcoef * x.Thus we need to adjust the rhs
12485 /* calculate the efficacy of the computed cut and store the success flag if the efficacy exceeds the
12517 /* calculate efficacy again to make sure it matches the coefficients after they where rounded to double values
12562/* =========================================== strongcg =========================================== */
12567 * Differs from cutsTransformMIR for continuous variables for which the lower bound must be used
12569 * negative. This forces all continuous variable to have a positive coefficient in the transformed
12575 * 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}\\
12576 * 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}
12584 * 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.} \\
12585 * 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.}
12588 * 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:
12601 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
12602 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
12606 SCIP_Bool* freevariable, /**< stores whether a free variable was found in MIR row -> invalid summation */
12607 SCIP_Bool* localbdsused /**< pointer to store whether local bounds were used in transformation */
12665 /* For continuous variables, we must choose the bound substitution so that they become positive in the cut */
12672 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
12692 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
12709 /* For implied integers, we still prefer to choose the bound substitution that makes them positive, but
12710 * if we cannot manage to do so it is not an error, because we can still treat them as integer variables */
12717 /* find closest lower bound in standard lower bound or variable lower bound for continuous variable so that it will have a positive coefficient */
12721 /* find closest upper bound in standard upper bound or variable upper bound for continuous variable so that it will have a positive coefficient */
12753 SCIP_CALL( determineBestBounds(scip, data->vars[v], sol, data, boundswitch, usevbds, allowlocal, FALSE, FALSE,
12802 /* If we terminate early, we need to make sure all the zeros in the cut coefficient array are cancelled */
12830/** Calculate fractionalities \f$ f_0 := b - down(b) \f$, \f$ f_j := a^\prime_j - down(a^\prime_j) \f$,
12831 * 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
12832 * 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$
12848 * 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} \\
12849 * 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}
12864 * 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)} \\
12865 * 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)}
12878 * \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\
12879 * \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j * bu_j == \hat{a}_{zu_j} - \hat{a}_j * bu_j &
12888 int* boundtype, /**< stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)*/
12907 /* Loop backwards through the sections, so that the reversing of varbound substitutions does not prematurely effect
12908 * the coefficients of variables in other sections, because the section index of a variable bound must always be
12918 /* iterate backwards over indices in section, so we can easily shrink the section if we find zeros */
12965 assert(pj >= 0); /* should be >= 1, but due to rounding bias can be 0 if fj is almost equal to f0 */
12975 /* Variable is continuous; must always be positive in strongcg cut. It will be automatically deleted. */
12999 /* move the constant term -a~_j * lb_j == -a^_j * lb_j , or a~_j * ub_j == -a^_j * ub_j to the rhs */
13090 /* Finally, store the relevant data in cutinds which is the array used by the other functions */
13108 * 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
13109 * variable only appears in its own row: \f$ a^\prime_r = scale \cdot weight[r] \cdot slacksign[r] \f$.
13111 * Depending on the slack's type (integral or continuous), its coefficient in the cut calculates as follows:
13121 * Substitute \f$ \hat{a}_r \cdot s_r \f$ by adding \f$ \hat{a}_r \f$ times the slack's definition to the cut.
13200 assert(pr >= 0); /* should be >= 1, but due to rounding bias can be 0 if fr is almost equal to f0 */
13269/** calculates a strong CG cut out of the weighted sum of LP rows given by an aggregation row; the
13270 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
13273 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
13285 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
13290 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
13297 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
13301 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
13334 /* terminate if an integral slack fractionality is unreliable or a negative continuous slack variable is present */
13337 if( ( scip->lp->rows[aggrrow->rowsinds[i]]->integral && ABS(aggrrow->rowweights[i] * scale) > large )
13338 || ( !scip->lp->rows[aggrrow->rowsinds[i]]->integral && aggrrow->rowweights[i] * aggrrow->slacksign[i] < 0.0 ) )
13364 assert(NSECTIONS == 6); /*lint !e506*/ /* If the section definition is changed, the below lines should also be adjusted to match */
13371 /* Problem data needs to be initialized before cut data as it is used to partition the variables into the sections */
13381 SCIP_CALL( SCIPallocCleanBufferArray(scip, &( data->cutcoefs ), QUAD_ARRAY_SIZE(data->nvars)) );
13431 * 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.
13432 * 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.
13433 * move the constant terms "a_j * dl_j" or "a_j * du_j" to the rhs, and update the coefficient of the VLB variable:
13437 SCIP_CALL( cutsTransformStrongCG(scip, data, sol, boundswitch, allowlocal, varsign, boundtype, &freevariable, &localbdsused) );
13458 SCIPdebug(printCutQuad(scip, NULL, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13469 * - 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)
13481 * 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
13482 * 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
13489 * 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)
13490 * 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)
13516 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13521 * The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack
13525 * Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
13533 SCIP_CALL( cutsSubstituteStrongCG(scip, aggrrow->rowweights, aggrrow->slacksign, aggrrow->rowsinds,
13534 aggrrow->nrows, scale, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds, QUAD(f0), k) );
13535 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
13537 /* remove all nearly-zero coefficients from strong CG row and relax the right hand side correspondingly in order to
13542 SCIP_CALL( postprocessCutQuad(scip, *cutislocal, data->cutinds, data->cutcoefs, &data->ncutinds, QUAD(&data->cutrhs), success) );
13546 *success = ! removeZerosQuad(scip, SCIPsumepsilon(scip), *cutislocal, data->cutcoefs, QUAD(&data->cutrhs), data->cutinds, &data->ncutinds);
13548 SCIPdebug(printCutQuad(scip, sol, data->cutcoefs, QUAD(data->cutrhs), data->cutinds, data->ncutinds, FALSE, FALSE));
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:8257
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:5872
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:4561
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:4164
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:352
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:5261
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:12054
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:3888
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:11769
static SCIP_Bool removeZerosSafely(SCIP *scip, SCIP_Real minval, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz)
Definition: cuts.c:727
static SCIP_Real calcEfficacyDenseStorageQuad(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:650
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:822
static SCIP_RETCODE cutsRoundStrongCG(SCIP *scip, MIR_DATA *data, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k)
Definition: cuts.c:12884
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:4233
static SCIP_RETCODE cutsRoundMIR(SCIP *scip, MIR_DATA *data, int *RESTRICT varsign, int *RESTRICT boundtype, QUAD(SCIP_Real f0))
Definition: cuts.c:6710
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:13124
static SCIP_RETCODE computeLiftingData(SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
Definition: cuts.c:11221
static void doMIRBoundSubstitution(SCIP *scip, MIR_DATA *data, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:5009
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:9190
static SCIP_RETCODE getFlowCover(SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
Definition: cuts.c:10833
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:9319
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:12170
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:1052
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:1097
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:1585
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:4498
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:5543
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:9627
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:3822
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:7637
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:5180
static void destroyLiftingData(SCIP *scip, LIFTINGDATA *liftingdata)
Definition: cuts.c:11351
static void performBoundSubstitutionSimpleSafely(SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
Definition: cuts.c:5146
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:4626
static SCIP_RETCODE varVecAddScaledRowCoefsQuad(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:240
static SCIP_Real calcEfficacyNormQuad(SCIP *scip, SCIP_Real *vals, int *inds, int nnz)
Definition: cuts.c:517
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:2103
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:4803
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:915
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:10222
static SCIP_Real calcEfficacyDenseStorage(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:579
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:9447
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:3753
static void destroySNFRelaxation(SCIP *scip, SNF_RELAXATION *snf)
Definition: cuts.c:10202
static SCIP_RETCODE allocSNFRelaxation(SCIP *scip, SNF_RELAXATION *snf, int nvars)
Definition: cuts.c:10181
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:3371
static SCIP_Bool chgCoeffWithBoundSafely(SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal, SCIP_Real *cutrhs)
Definition: cuts.c:1142
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:6953
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: cuts.c:452
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:10317
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:11364
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:12597
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:1658
static void getAlphaAndBeta(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
Definition: cuts.c:11184
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:7477
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:3257
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:4299
static SCIP_RETCODE varVecAddScaledRowCoefsQuadScale(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, QUAD(SCIP_Real scale))
Definition: cuts.c:287
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:5099
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:5320
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:1207
static SCIP_Real evaluateLiftingFunction(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
Definition: cuts.c:11100
static SCIP_RETCODE varVecAddScaledRowCoefs(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
Definition: cuts.c:195
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:4715
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:11963
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:1090
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:644
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:534
void SCIPaggrRowCancelVarWithBound(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
Definition: cuts.c:3008
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
Definition: cuts.c:4005
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:8339
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:7923
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:2466
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:2668
SCIP_RETCODE SCIPaggrRowAddRowSafely(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype, SCIP_Bool *success)
Definition: cuts.c:2887
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:12270
SCIP_RETCODE SCIPaggrRowCopy(SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
Definition: cuts.c:2758
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:3143
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:13281
void SCIPaggrRowPrint(SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
Definition: cuts.c:2721
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition: cuts.c:3949
SCIP_Real * SCIPaggrRowGetRowWeights(SCIP_AGGRROW *aggrrow)
Definition: cuts.c:3994
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition: cuts.c:2804
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:3523
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition: cuts.c:3067
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:11645
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
Definition: cuts.c:3243
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:1576
void SCIPrationalMult(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:1066
void SCIPrationalInvert(SCIP_RATIONAL *res, SCIP_RATIONAL *op)
Definition: rational.cpp:1323
SCIP_Real SCIPrationalGetReal(SCIP_RATIONAL *rational)
Definition: rational.cpp:2085
void SCIPrationalDiv(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:1132
void SCIPrationalSetReal(SCIP_RATIONAL *res, SCIP_Real real)
Definition: rational.cpp:603
void SCIPrationalFreeBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:473
void SCIPrationalDiff(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:983
SCIP_Bool SCIPrationalIsPositive(SCIP_RATIONAL *rational)
Definition: rational.cpp:1640
SCIP_RETCODE SCIPrationalCreateBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:123
SCIP_Bool SCIPrationalIsZero(SCIP_RATIONAL *rational)
Definition: rational.cpp:1624
void SCIPrationalSetRational(SCIP_RATIONAL *res, SCIP_RATIONAL *src)
Definition: rational.cpp:569
SCIP_Bool SCIPrationalIsGEReal(SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1606
SCIP_Bool SCIPrationalIsNegative(SCIP_RATIONAL *rational)
Definition: rational.cpp:1650
void SCIPrationalDiffReal(SCIP_RATIONAL *res, SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1009
SCIP_Real SCIPrationalRoundReal(SCIP_RATIONAL *rational, SCIP_ROUNDMODE_RAT roundmode)
Definition: rational.cpp:2110
SCIP_Bool SCIPrationalIsEQReal(SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:1437
void SCIPrationalMultReal(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_Real op2)
Definition: rational.cpp:1097
SCIP_Bool SCIPrationalIsLE(SCIP_RATIONAL *rat1, SCIP_RATIONAL *rat2)
Definition: rational.cpp:1521
void SCIPrationalAddReal(SCIP_RATIONAL *res, SCIP_RATIONAL *rat, SCIP_Real real)
Definition: rational.cpp:961
void SCIPrationalAddProdReal(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_Real op2)
Definition: rational.cpp:1210
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:1765
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:24130
SCIP_RATIONAL * SCIPvarGetUbGlobalExact(SCIP_VAR *var)
Definition: var.c:24152
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 (weighted) 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:9148
Definition: cuts.c:4091
SCIP_Real QUAD(cutrhs)
Definition: struct_cuts.h:41
Definition: struct_certificate.h:63
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:9168
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