65 QUAD(SCIP_Real cutrhs),
72 SCIP_Real
QUAD(activity);
81 for(
i = 0;
i < cutnnz; ++
i )
100 if( cutcoefs[
i] > 0.0 )
123#define NONZERO(x) (COPYSIGN(1e-100, (x)) + (x))
145 for(
i = 0 ;
i < row->
len; ++
i )
151 val = vals[probindex];
154 inds[(*nnz)++] = probindex;
156 val += row->
vals[
i] * scale;
162 vals[probindex] = val;
190 for(
i = 0 ;
i < row->
len; ++
i )
192 SCIP_Real
QUAD(scaledrowval);
200 inds[(*nnz)++] = probindex;
226 QUAD(SCIP_Real scale)
237 for(
i = 0 ;
i < row->
len; ++
i )
240 SCIP_Real
QUAD(rowval);
248 inds[(*nnz)++] = probindex;
279 SCIP_Real norm = 0.0;
280 SCIP_Real activity = 0.0;
289 switch(
scip->set->sepa_efficacynorm )
292 for(
i = 0;
i < cutnnz; ++
i )
295 norm +=
SQR(cutcoefs[
i]);
300 for(
i = 0;
i < cutnnz; ++
i )
306 norm =
MAX(norm, absval);
310 for(
i = 0;
i < cutnnz; ++
i )
317 for(
i = 0;
i < cutnnz; ++
i )
329 return (activity - cutrhs) /
MAX(1e-6, norm);
341 SCIP_Real norm = 0.0;
342 SCIP_Real
QUAD(coef);
348 switch(
scip->set->sepa_efficacynorm )
351 for(
i = 0;
i < nnz; ++
i )
359 for(
i = 0;
i < nnz; ++
i )
365 norm =
MAX(norm, absval);
369 for(
i = 0;
i < nnz; ++
i )
376 for(
i = 0;
i < nnz; ++
i )
406 SCIP_Real norm = 0.0;
407 SCIP_Real activity = 0.0;
408 SCIP_Real
QUAD(coef);
418 switch(
scip->set->sepa_efficacynorm )
421 for(
i = 0;
i < cutnnz; ++
i )
430 for(
i = 0;
i < cutnnz; ++
i )
437 norm =
MAX(norm, absval);
441 for(
i = 0;
i < cutnnz; ++
i )
449 for(
i = 0;
i < cutnnz; ++
i )
462 return (activity - cutrhs) /
MAX(1e-6, norm);
474 SCIP_Bool cutislocal,
476 QUAD(SCIP_Real* cutrhs),
486 for(
i = 0;
i < *cutnnz; )
545 cutinds[
i] = cutinds[*cutnnz];
567 SCIP_Bool cutislocal,
569 QUAD(SCIP_Real* cutrhs),
582 for(
i = 0;
i < *cutnnz; )
589 SCIP_Real
QUAD(quadprod);
610 if(
EPSZ(val, minval) || isfixed )
641 cutinds[
i] = cutinds[*cutnnz];
660 SCIP_Real
QUAD(coef1);
661 SCIP_Real
QUAD(coef2);
662 SCIP_Real* coefs = (SCIP_Real*) dataptr;
670 if( abscoef1 < abscoef2 )
672 if( abscoef2 < abscoef1 )
684 SCIP_Real* coefs = (SCIP_Real*) dataptr;
686 abscoef1 =
REALABS(coefs[ind1]);
687 abscoef2 =
REALABS(coefs[ind2]);
689 if( abscoef1 < abscoef2 )
691 if( abscoef2 < abscoef1 )
706 SCIP_Bool cutislocal,
707 QUAD(SCIP_Real* cutrhs)
710 SCIP_Real
QUAD(delta);
749 QUAD(SCIP_Real oldcoeff),
751 SCIP_Bool cutislocal,
752 QUAD(SCIP_Real* cutrhs)
755 SCIP_Real
QUAD(delta);
795 SCIP_Bool cutislocal,
797 QUAD(SCIP_Real* cutrhs),
805 SCIP_Bool isintegral =
TRUE;
807 SCIP_Real
QUAD(maxacttmp);
809 SCIP_Real maxabsintval = 0.0;
810 SCIP_Real maxabscontval = 0.0;
821 for(
i = 0;
i < *cutnnz; ++
i )
837 if( cutinds[
i] < nintegralvars )
855 if( cutinds[
i] < nintegralvars )
883 SCIP_Real* intcoeffs;
887 equiscale = 1.0 /
MIN((maxact -
QUAD_TO_DBL(*cutrhs)), maxabsintval);
889 for(
i = 0;
i < *cutnnz; ++
i )
900 (SCIP_Longint)
scip->set->sepa_maxcoefratio,
scip->set->sepa_maxcoefratio, &intscalar, &success) );
907 intscalar *= equiscale;
910 for(
i = 0;
i < *cutnnz; )
939 cutinds[
i] = cutinds[*cutnnz];
949 for(
i = 0;
i < *cutnnz; ++
i )
992 maxabsintval *= equiscale;
994 for(
i = 0;
i < *cutnnz; ++
i )
1008 SCIP_Real maxabsval;
1011 maxabsval =
MIN(maxabsval, maxabsintval);
1012 maxabsval =
MAX(maxabsval, maxabscontval);
1014 scale = 1.0 / maxabsval;
1019 maxabsintval *= scale;
1021 for(
i = 0;
i < *cutnnz; ++
i )
1023 SCIP_Real
QUAD(val);
1044 SCIPsortDownInd(cutinds, compareAbsCoefsQuad, (
void*) cutcoefs, *cutnnz);
1047 for(
i = 0;
i < *cutnnz; )
1049 SCIP_Real
QUAD(val);
1051 if( cutinds[
i] >= nintegralvars )
1063 SCIP_Real
QUAD(coef);
1077 SCIP_Real
QUAD(delta);
1078 SCIP_Real
QUAD(tmp);
1084 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1103 cutinds[
i] = cutinds[*cutnnz];
1110 SCIP_Real
QUAD(coef);
1124 SCIP_Real
QUAD(delta);
1125 SCIP_Real
QUAD(tmp);
1131 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1150 cutinds[
i] = cutinds[*cutnnz];
1170 SCIP_Bool cutislocal,
1171 SCIP_Real* cutcoefs,
1172 QUAD(SCIP_Real* cutrhs),
1175 SCIP_Bool* redundant
1180 SCIP_Bool isintegral =
TRUE;
1182 SCIP_Real
QUAD(maxacttmp);
1184 SCIP_Real maxabsintval = 0.0;
1185 SCIP_Real maxabscontval = 0.0;
1196 for(
i = 0;
i < *cutnnz; ++
i )
1199 SCIP_Real
QUAD(quadprod);
1204 val = cutcoefs[cutinds[
i]];
1213 if( cutinds[
i] < nintegralvars )
1214 maxabsintval =
MAX(maxabsintval, -val);
1217 maxabscontval =
MAX(maxabscontval, -val);
1231 if( cutinds[
i] < nintegralvars )
1232 maxabsintval =
MAX(maxabsintval, val);
1235 maxabscontval =
MAX(maxabscontval, val);
1256 SCIP_Real equiscale;
1257 SCIP_Real intscalar;
1259 SCIP_Real* intcoeffs;
1263 equiscale = 1.0 /
MIN((maxact -
QUAD_TO_DBL(*cutrhs)), maxabsintval);
1265 for(
i = 0;
i < *cutnnz; ++
i )
1269 val = equiscale * cutcoefs[cutinds[
i]];
1275 (SCIP_Longint)
scip->set->sepa_maxcoefratio,
scip->set->sepa_maxcoefratio, &intscalar, &success) );
1282 intscalar *= equiscale;
1285 for(
i = 0;
i < *cutnnz; )
1290 val = cutcoefs[cutinds[
i]];
1304 cutcoefs[cutinds[
i]] = intval;
1310 cutcoefs[cutinds[
i]] = 0.0;
1312 cutinds[
i] = cutinds[*cutnnz];
1322 for(
i = 0;
i < *cutnnz; ++
i )
1325 SCIP_Real
QUAD(quadprod);
1330 val = cutcoefs[cutinds[
i]];
1336 maxabsintval =
MAX(maxabsintval, -val);
1345 maxabsintval =
MAX(maxabsintval, val);
1364 maxabsintval *= equiscale;
1366 for(
i = 0;
i < *cutnnz; ++
i )
1367 cutcoefs[cutinds[
i]] *= equiscale;
1374 SCIP_Real maxabsval;
1377 maxabsval =
MIN(maxabsval, maxabsintval);
1378 maxabsval =
MAX(maxabsval, maxabscontval);
1380 scale = 1.0 / maxabsval;
1385 maxabsintval *= scale;
1387 for(
i = 0;
i < *cutnnz; ++
i )
1388 cutcoefs[cutinds[
i]] *= scale;
1407 for(
i = 0;
i < *cutnnz; )
1411 if( cutinds[
i] >= nintegralvars )
1417 val = cutcoefs[cutinds[
i]];
1423 SCIP_Real
QUAD(coef);
1437 SCIP_Real
QUAD(delta);
1438 SCIP_Real
QUAD(tmp);
1444 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1460 cutcoefs[cutinds[
i]] = 0.0;
1462 cutinds[
i] = cutinds[*cutnnz];
1469 SCIP_Real
QUAD(coef);
1483 SCIP_Real
QUAD(delta);
1484 SCIP_Real
QUAD(tmp);
1490 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1506 cutcoefs[cutinds[
i]] = 0.0;
1508 cutinds[
i] = cutinds[*cutnnz];
1529 SCIP_Bool cutislocal,
1530 SCIP_Real* cutcoefs,
1541 SCIP_Real
QUAD(maxacttmp);
1543 SCIP_Real maxabsval = 0.0;
1544 SCIP_Bool redundant =
FALSE;
1557 for(
i = 0;
i < *cutnnz; ++
i )
1559 SCIP_Real
QUAD(quadprod);
1564 if( cutcoefs[
i] < 0.0 )
1571 if( cutinds[
i] < nintegralvars )
1573 maxabsval =
MAX(maxabsval, -cutcoefs[
i]);
1574 absvals[
i] = -cutcoefs[
i];
1589 if( cutinds[
i] < nintegralvars )
1591 maxabsval =
MAX(maxabsval, cutcoefs[
i]);
1592 absvals[
i] = cutcoefs[
i];
1619 for(
i = 0;
i < *cutnnz; ++
i )
1622 if( cutinds[
i] >= nintegralvars )
1627 if( cutcoefs[
i] < 0.0 &&
SCIPisLE(
scip, maxact + cutcoefs[
i], *cutrhs) )
1629 SCIP_Real coef = (*cutrhs) - maxact;
1634 if( coef > cutcoefs[
i] )
1636 SCIP_Real
QUAD(delta);
1637 SCIP_Real
QUAD(tmp);
1643 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1662 cutinds[
i] = cutinds[*cutnnz];
1663 cutcoefs[
i] = cutcoefs[*cutnnz];
1668 else if( cutcoefs[
i] > 0.0 &&
SCIPisLE(
scip, maxact - cutcoefs[
i], *cutrhs) )
1670 SCIP_Real coef = maxact - (*cutrhs);
1675 if( coef < cutcoefs[
i] )
1677 SCIP_Real
QUAD(delta);
1678 SCIP_Real
QUAD(tmp);
1684 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1703 cutinds[
i] = cutinds[*cutnnz];
1704 cutcoefs[
i] = cutcoefs[*cutnnz];
1741 (*aggrrow)->local =
FALSE;
1742 (*aggrrow)->nnz = 0;
1743 (*aggrrow)->rank = 0;
1745 (*aggrrow)->rowsinds =
NULL;
1746 (*aggrrow)->slacksign =
NULL;
1747 (*aggrrow)->rowweights =
NULL;
1748 (*aggrrow)->nrows = 0;
1749 (*aggrrow)->rowssize = 0;
1796 if( aggrrow->
nnz == 0 )
1799 for(
i = 0;
i < aggrrow->
nnz; ++
i )
1801 SCIP_Real
QUAD(val);
1830 (*aggrrow)->nnz = source->
nnz;
1833 if( source->
nrows > 0 )
1845 (*aggrrow)->rowsinds =
NULL;
1846 (*aggrrow)->slacksign =
NULL;
1847 (*aggrrow)->rowweights =
NULL;
1850 (*aggrrow)->nrows = source->
nrows;
1851 (*aggrrow)->rowssize = source->
nrows;
1852 (*aggrrow)->rank = source->
rank;
1853 (*aggrrow)->local = source->
local;
1867 SCIP_Real
QUAD(quadprod);
1893 if( sidetype == -1 )
1898 else if( sidetype == 1 )
1953 SCIP_Real
QUAD(val);
1959 v = aggrrow->
inds[pos];
2012 SCIP_Real
QUAD(val);
2022 if( aggrrow->
nnz == 0 )
2044 SCIP_Real
QUAD(quadprod);
2092 SCIP_Real
QUAD(quadprod);
2109 for(
i = 0 ;
i < len; ++
i )
2111 SCIP_Real
QUAD(val);
2112 int probindex = inds[
i];
2117 aggrrow->
inds[aggrrow->
nnz++] = probindex;
2138 SCIP_Real
QUAD(tmp);
2142 for(
i = 0;
i < aggrrow->
nnz; ++
i )
2175 SCIP_Bool sidetypebasis,
2176 SCIP_Bool allowlocal,
2179 SCIP_Bool* rowtoolong
2182 SCIP_Real
QUAD(quadprod);
2188 *rowtoolong =
FALSE;
2223 if( weight > 0.0 && ((negslack == 0) || (negslack == 1 && !row->
integral)) )
2235 if( weight < 0.0 && ((negslack == 0) || (negslack == 1 && !row->
integral)) )
2270 if( aggrrow->
nnz > maxaggrlen )
2285 SCIP_Bool sidetypebasis,
2286 SCIP_Bool allowlocal,
2297 SCIP_Bool rowtoolong;
2309 if( rowinds !=
NULL && nrowinds > -1 )
2311 for( k = 0; k < nrowinds; ++k )
2313 SCIP_CALL(
addOneRow(
scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2321 for( k = 0; k < nrows; ++k )
2323 if( weights[k] != 0.0 )
2325 SCIP_CALL(
addOneRow(
scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2345 SCIP_Bool cutislocal,
2347 SCIP_Real* cutcoefs,
2354 SCIP_Bool redundant;
2356 SCIP_Real minallowedcoef;
2357 SCIP_Real
QUAD(rhs);
2387 for(
i = 0;
i < *nnz; ++
i )
2389 SCIP_Real absval =
REALABS(cutcoefs[cutinds[
i]]);
2390 maxcoef =
MAX(absval, maxcoef);
2393 maxcoef /=
scip->set->sepa_maxcoefratio;
2395 minallowedcoef =
MAX(minallowedcoef, maxcoef);
2397 *success = !
removeZeros(
scip, minallowedcoef, cutislocal, cutcoefs,
QUAD(&rhs), cutinds, nnz);
2414 SCIP_Bool cutislocal,
2416 SCIP_Real* cutcoefs,
2418 QUAD(SCIP_Real* cutrhs),
2423 SCIP_Bool redundant;
2425 SCIP_Real minallowedcoef;
2452 for(
i = 0;
i < *nnz; ++
i )
2455 SCIP_Real
QUAD(coef);
2458 maxcoef =
MAX(abscoef, maxcoef);
2461 maxcoef /=
scip->set->sepa_maxcoefratio;
2463 minallowedcoef =
MAX(minallowedcoef, maxcoef);
2474 SCIP_Bool useglbbounds,
2482 QUAD(&aggrrow->rhs), aggrrow->
inds, &aggrrow->
nnz);
2492 return aggrrow->
nrows;
2531 for(
i = 0;
i < aggrrow->
nrows; ++
i )
2547 return aggrrow->
inds;
2557 return aggrrow->
nnz;
2567 return aggrrow->
rank;
2577 return aggrrow->
local;
2592#define MAXCMIRSCALE 1e+6
2601 SCIP_Bool allowlocal,
2603 SCIP_Real* simplebound,
2625 *simplebound = *bestlb;
2633 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 &&
SCIPisGE(
scip, bestvlb, *bestlb))) )
2647 *bestlbtype = bestvlbidx;
2662 SCIP_Bool allowlocal,
2664 SCIP_Real* simplebound,
2686 *simplebound = *bestub;
2694 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 &&
SCIPisLE(
scip, bestvub, *bestub))) )
2708 *bestubtype = bestvubidx;
2722 SCIP_Real boundswitch,
2724 SCIP_Bool allowlocal,
2725 SCIP_Bool fixintegralrhs,
2726 SCIP_Bool ignoresol,
2727 int* boundsfortrans,
2737 SCIP_Bool* freevariable
2747 if( boundsfortrans !=
NULL && boundsfortrans[v] > -3 )
2756 *bestlbtype = boundsfortrans[v];
2757 if( *bestlbtype == -1 )
2759 else if( *bestlbtype == -2 )
2764 SCIP_Real* vlbcoefs;
2765 SCIP_Real* vlbconsts;
2774 k = boundsfortrans[v];
2794 *bestubtype = boundsfortrans[v];
2795 if( *bestubtype == -1 )
2797 else if( *bestubtype == -2 )
2802 SCIP_Real* vubcoefs;
2803 SCIP_Real* vubconsts;
2812 k = boundsfortrans[v];
2847 *freevariable =
TRUE;
2860 else if(
SCIPisLT(
scip, varsol, (1.0 - boundswitch) * (*bestlb) + boundswitch * (*bestub)) )
2862 else if(
SCIPisGT(
scip, varsol, (1.0 - boundswitch) * (*bestlb) + boundswitch * (*bestub)) )
2864 else if( *bestlbtype == -1 )
2866 else if( *bestubtype == -1 )
2868 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !
SCIPisEQ(
scip, *bestlb - simplelb, simpleub - *bestub) )
2870 if( *bestlb - simplelb > simpleub - *bestub )
2875 else if( *bestlbtype >= 0 )
2877 else if( *bestubtype >= 0 )
2886 SCIP_Real distlb =
REALABS(glblb - *bestlb);
2887 SCIP_Real distub =
REALABS(glbub - *bestub);
2920 SCIP_Real* cutcoefs,
2921 QUAD(SCIP_Real* cutrhs),
2928 SCIP_Bool* localbdsused
2931 SCIP_Real
QUAD(coef);
2932 SCIP_Real
QUAD(tmp);
2943 *localbdsused = *localbdsused || (boundtype == -2);
2948 SCIP_Real* vbdcoefs;
2949 SCIP_Real* vbdconsts;
2950 SCIP_Real
QUAD(zcoef);
2983 cutinds[(*nnz)++] = zidx;
2999 SCIP_Real* cutcoefs,
3000 QUAD(SCIP_Real* cutrhs),
3005 SCIP_Bool* localbdsused
3008 SCIP_Real
QUAD(coef);
3009 SCIP_Real
QUAD(tmp);
3020 *localbdsused = *localbdsused || (boundtype == -2);
3055 SCIP_Real boundswitch,
3057 SCIP_Bool allowlocal,
3058 SCIP_Bool fixintegralrhs,
3059 SCIP_Bool ignoresol,
3060 int* boundsfortrans,
3067 SCIP_Real* cutcoefs,
3068 QUAD(SCIP_Real* cutrhs),
3074 SCIP_Bool* freevariable,
3075 SCIP_Bool* localbdsused
3078 SCIP_Real
QUAD(tmp);
3085 int aggrrowintstart;
3095 *freevariable =
FALSE;
3096 *localbdsused =
FALSE;
3119 ignoresol, boundsfortrans, boundtypesfortrans,
3120 bestlbs +
i, bestubs +
i, bestlbtypes +
i, bestubtypes +
i, selectedbounds +
i, freevariable) );
3127 aggrrowintstart =
i;
3130 for(
i = 0;
i < aggrrowintstart; ++
i )
3139 boundtype[
i] = bestlbtypes[
i];
3149 boundtype[
i] = bestubtypes[
i];
3161 SCIP_Real
QUAD(coef);
3163 assert(cutinds[
i] < firstcontvar);
3173 cutinds[
i] = cutinds[*nnz];
3180 ignoresol, boundsfortrans, boundtypesfortrans,
3181 bestlbs +
i, bestubs +
i, bestlbtypes +
i, bestubtypes +
i, selectedbounds +
i, freevariable) );
3191 for(
i = aggrrowintstart;
i < *nnz; ++
i )
3202 boundtype[
i] = bestlbtypes[
i];
3213 boundtype[
i] = bestubtypes[
i];
3220 if( fixintegralrhs )
3226 if( f0 < minfrac || f0 > maxfrac )
3228 SCIP_Real bestviolgain;
3229 SCIP_Real bestnewf0;
3234 bestviolgain = -1e+100;
3236 for(
i = 0;
i < *nnz;
i++ )
3239 SCIP_Real
QUAD(coef);
3247 if( boundtype[
i] < 0
3271 if( newf0 < minfrac || newf0 > maxfrac )
3273 if( v >= firstcontvar )
3287 viol = f0 - fj * (varsign[
i] == +1 ? solval - bestlbs[
i] : bestubs[
i] - solval);
3288 newviol = newf0 - newfj * (varsign[
i] == -1 ? solval - bestlbs[
i] : bestubs[
i] - solval);
3289 violgain = newviol - viol;
3294 SCIPerrorMessage(
"Cannot handle closest bounds with ignoring the LP solution.\n");
3304 bestviolgain = violgain;
3312 SCIP_Real
QUAD(coef);
3314 assert(boundtype[besti] < 0);
3326 if( varsign[besti] == +1 )
3329 assert(bestubtypes[besti] < 0);
3330 boundtype[besti] = bestubtypes[besti];
3331 varsign[besti] = -1;
3336 assert(bestlbtypes[besti] < 0);
3337 boundtype[besti] = bestlbtypes[besti];
3338 varsign[besti] = +1;
3340 *localbdsused = *localbdsused || (boundtype[besti] == -2);
3419 SCIP_Real
QUAD(tmp);
3420 SCIP_Real
QUAD(onedivoneminusf0);
3447 while(
i < *nnz && cutinds[
i] >= firstcontvar )
3452 assert(cutinds[
i] < firstcontvar);
3458 for(
i = *nnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
3461 SCIP_Real
QUAD(cutaj);
3470 assert(varsign[
i] == +1 || varsign[
i] == -1);
3475 SCIP_Real
QUAD(downaj);
3504 cutinds[
i] = cutinds[*nnz];
3514 if( varsign[
i] == +1 )
3517 if( boundtype[
i] == -1 )
3533 if( boundtype[
i] == -1 )
3550 while(
i >= ndelcontvars )
3553 SCIP_Real
QUAD(cutaj);
3563 assert(varsign[
i] == +1 || varsign[
i] == -1);
3564 assert( v >= firstcontvar );
3582 cutinds[
i] = cutinds[ndelcontvars];
3583 varsign[
i] = varsign[ndelcontvars];
3584 boundtype[
i] = boundtype[ndelcontvars];
3592 if( boundtype[
i] < 0 )
3597 if( varsign[
i] == +1 )
3600 if( boundtype[
i] == -1 )
3616 if( boundtype[
i] == -1 )
3635 SCIP_Real
QUAD(zcoef);
3640 vbidx = boundtype[
i];
3643 if( varsign[
i] == +1 )
3661 assert(0 <= zidx && zidx < firstcontvar);
3671 cutinds[(*nnz)++] = zidx;
3684 if( ndelcontvars > 0 )
3686 assert(ndelcontvars <= *nnz);
3687 *nnz -= ndelcontvars;
3688 if( *nnz < ndelcontvars )
3726 SCIP_Real* cutcoefs,
3727 QUAD(SCIP_Real* cutrhs),
3734 SCIP_Real
QUAD(onedivoneminusf0);
3752 for(
i = 0;
i < nrowinds;
i++ )
3756 SCIP_Real
QUAD(downar);
3757 SCIP_Real
QUAD(cutar);
3759 SCIP_Real
QUAD(tmp);
3760 SCIP_Real
QUAD(myprod);
3765 assert(slacksign[
i] == -1 || slacksign[
i] == +1);
3823 if( slacksign[
i] == +1 )
3825 SCIP_Real
QUAD(rowrhs);
3840 SCIP_Real
QUAD(rowlhs);
3876 SCIP_Bool postprocess,
3877 SCIP_Real boundswitch,
3879 SCIP_Bool allowlocal,
3880 SCIP_Bool fixintegralrhs,
3881 int* boundsfortrans,
3890 SCIP_Real* cutcoefs,
3894 SCIP_Real* cutefficacy,
3896 SCIP_Bool* cutislocal,
3906 SCIP_Real* tmpcoefs;
3908 SCIP_Real
QUAD(rhs);
3909 SCIP_Real
QUAD(downrhs);
3911 SCIP_Bool freevariable;
3912 SCIP_Bool localbdsused;
3913 SCIP_Bool tmpislocal;
3931 tmpnnz = aggrrow->
nnz;
3932 tmpislocal = aggrrow->
local;
3940 for(
i = 0;
i < tmpnnz; ++
i )
3942 SCIP_Real
QUAD(coef);
3943 int k = aggrrow->
inds[
i];
3970 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, tmpcoefs,
QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
3971 assert(allowlocal || !localbdsused);
3972 tmpislocal = tmpislocal || localbdsused;
4049 aggrrow->
nrows, scale, tmpcoefs,
QUAD(&rhs), tmpinds, &tmpnnz,
QUAD(f0)) );
4078 *cutislocal = tmpislocal;
4081 for(
i = 0;
i < *cutnnz; ++
i )
4083 SCIP_Real
QUAD(coef);
4093 if( cutefficacy !=
NULL )
4094 *cutefficacy = mirefficacy;
4096 if( cutrank !=
NULL )
4097 *cutrank = aggrrow->
rank + 1;
4108 SCIP_Real
QUAD(tmp);
4111 for(
i = 0;
i < tmpnnz; ++
i )
4135 SCIP_Real contactivity,
4136 SCIP_Real contsqrnorm,
4144 SCIP_Real f0pluseps;
4146 SCIP_Real onedivoneminusf0;
4150 SCIP_Real contscale;
4152 scale = 1.0 / delta;
4157 if( f0 < minfrac || f0 > maxfrac )
4160 onedivoneminusf0 = 1.0 / (1.0 - f0);
4162 contscale = scale * onedivoneminusf0;
4171 rhs -= contscale * contactivity;
4172 norm =
SQR(contscale) * contsqrnorm;
4182 SCIP_Real fi = (scale * coefs[
i]) - floorai;
4184 if( fi > f0pluseps )
4185 floorai += (fi - f0) * onedivoneminusf0;
4187 rhs -= solvals[
i] * floorai;
4188 norm +=
SQR(floorai);
4193 return - rhs /
MAX(norm, 1e-6);
4215 SCIP_Bool postprocess,
4216 SCIP_Real boundswitch,
4218 SCIP_Bool allowlocal,
4220 int* boundsfortrans,
4228 SCIP_Real* cutcoefs,
4232 SCIP_Real* cutefficacy,
4235 SCIP_Bool* cutislocal,
4247 SCIP_Real* mksetcoefs;
4248 SCIP_Real
QUAD(mksetrhs);
4250 SCIP_Real* bounddist;
4253 SCIP_Real* tmpcoefs;
4254 SCIP_Real* tmpvalues;
4255 SCIP_Real* deltacands;
4257 SCIP_Real bestdelta;
4258 SCIP_Real bestefficacy;
4259 SCIP_Real maxabsmksetcoef;
4261 SCIP_Bool freevariable;
4262 SCIP_Bool localbdsused;
4263 SCIP_Real contactivity;
4264 SCIP_Real contsqrnorm;
4293 mksetnnz = aggrrow->
nnz;
4298 for(
i = 0;
i < mksetnnz; ++
i )
4300 int j = mksetinds[
i];
4301 SCIP_Real
QUAD(coef);
4307 *cutislocal = aggrrow->
local;
4325 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, mksetcoefs,
QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, &freevariable, &localbdsused) );
4327 assert(allowlocal || !localbdsused);
4336 maxabsmksetcoef = -1.0;
4339 for(
i = mksetnnz - 1;
i >= 0 && mksetinds[
i] < firstcontvar; --
i )
4345 SCIP_Real
QUAD(coef);
4353 bounddistpos[nbounddist] =
i;
4359 if( nbounddist == 0 )
4363 ndeltacands = nbounddist;
4369 SCIP_Bool intscalesuccess;
4373 if( intscalesuccess )
4376 SCIP_Real intscalerhs;
4380 delta = 1.0 / intscale;
4381 intf0 = intscalerhs - floor(intscalerhs);
4385 if( intf0 < minfrac || intf0 > maxfrac )
4387 intscale *=
SCIPceil(
scip,
MAX(minfrac, (1.0 - maxfrac)) /
MIN(intf0, (1.0 - intf0)));
4389 delta = 1.0 / intscale;
4390 intf0 = intscalerhs - floor(intscalerhs);
4393 if( intf0 >= minfrac && intf0 <= maxfrac )
4396 deltacands[ndeltacands++] = delta;
4398 if( intf0 < maxfrac )
4402 delta2 = 1.0 / (intscale *
SCIPfloor(
scip, maxfrac / intf0));
4405 deltacands[ndeltacands++] = delta2;
4412 for(
i = 0;
i < nbounddist; ++
i )
4414 SCIP_Real absmksetcoef;
4416 absmksetcoef =
REALABS(deltacands[
i]);
4417 maxabsmksetcoef =
MAX(absmksetcoef, maxabsmksetcoef);
4419 deltacands[
i] = absmksetcoef;
4423 if( maxabsmksetcoef != -1.0 )
4424 deltacands[ndeltacands++] = maxabsmksetcoef + 1.0;
4426 deltacands[ndeltacands++] = 1.0;
4428 maxtestdelta =
MIN(ndeltacands, maxtestdelta);
4460 for(
i = intstart;
i < mksetnnz; ++
i )
4464 SCIP_Real
QUAD(coef);
4472 if( boundtype[
i] == -1 )
4475 if( varsign[
i] == -1 )
4485 if( varsign[
i] == -1 )
4491 tmpvalues[ntmpcoefs] = solval;
4497 assert(ntmpcoefs == mksetnnz - intstart);
4501 for(
i = 0;
i < intstart; ++
i )
4504 SCIP_Real
QUAD(mksetcoef);
4515 switch( boundtype[
i] )
4519 if( varsign[
i] == -1 )
4526 if( varsign[
i] == -1 )
4533 if( varsign[
i] == -1 )
4537 SCIP_Real vbdsolval;
4543 solval = (coef * vbdsolval + constant) - solval;
4549 SCIP_Real vbdsolval;
4555 solval = solval - (coef * vbdsolval + constant);
4559 contactivity += solval * (
QUAD_TO_DBL(mksetcoef) * varsign[
i]);
4568 for(
i = 0;
i < aggrrow->
nrows; ++
i )
4586 slackval = row->
rhs - slackval;
4594 slackval = slackval - row->
lhs;
4600 tmpvalues[ntmpcoefs] = slackval;
4609 contactivity += slackval * slackcoeff;
4610 contsqrnorm +=
SQR(slackcoeff);
4619 for(
i = 0;
i < maxtestdelta; ++
i )
4625 SCIP_Bool deltaseenbefore =
FALSE;
4626 for( j = 0; j <
i; ++j )
4630 deltaseenbefore =
TRUE;
4636 if( deltaseenbefore )
4638 maxtestdelta =
MIN(maxtestdelta + 1, ndeltacands);
4644 if( efficacy > bestefficacy )
4646 bestefficacy = efficacy;
4647 bestdelta = deltacands[
i];
4657 SCIP_Real basedelta = bestdelta;
4658 for(
i = 2;
i <= 8 ;
i *= 2 )
4663 delta = basedelta /
i;
4667 if( efficacy > bestefficacy )
4669 bestefficacy = efficacy;
4678 for(
i = 0;
i < nbounddist; ++
i )
4681 SCIP_Real newefficacy;
4682 SCIP_Real
QUAD(newrhs);
4683 SCIP_Real
QUAD(quadprod);
4686 SCIP_Real oldsolval;
4687 SCIP_Real simplebnd;
4691 k = bounddistpos[
i];
4706 SCIP_Real
QUAD(coef);
4715 tmpcoefs[k - intstart] = -tmpcoefs[k - intstart];
4717 oldsolval = tmpvalues[k - intstart];
4724 if( newefficacy > bestefficacy )
4727 bestefficacy = newefficacy;
4730 if( varsign[k] == +1 )
4734 boundtype[k] = bestubtype;
4741 boundtype[k] = bestlbtype;
4745 localbdsused = localbdsused || (boundtype[k] == -2);
4750 tmpcoefs[k - intstart] = -tmpcoefs[k - intstart];
4751 tmpvalues[k - intstart] = oldsolval;
4755 if( bestefficacy > 0.0 )
4757 SCIP_Real mirefficacy;
4758 SCIP_Real
QUAD(downrhs);
4762 scale = 1.0 / bestdelta;
4771 for(
i = 0;
i < mksetnnz; ++
i )
4773 SCIP_Real
QUAD(coef);
4804 aggrrow->
nrows, scale, mksetcoefs,
QUAD(&mksetrhs), mksetinds, &mksetnnz,
QUAD(f0)) );
4812 for(
i = 0;
i < mksetnnz; ++
i )
4814 SCIP_Real
QUAD(coef);
4821 SCIPdebugMsg(
scip,
"efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
4826 *cutislocal = *cutislocal || localbdsused;
4840 SCIPdebugMsg(
scip,
"post-processed cut (success = %s):\n", *success ?
"TRUE" :
"FALSE");
4850 for(
i = 0;
i < mksetnnz; ++
i )
4852 SCIP_Real
QUAD(coef);
4863 *cutefficacy = mirefficacy;
4864 if( cutrank !=
NULL )
4865 *cutrank = aggrrow->
rank + 1;
4866 *cutislocal = *cutislocal || localbdsused;
4877 SCIP_Real
QUAD(tmp);
4880 for(
i = 0;
i < mksetnnz; ++
i )
4902#define NO_EXACT_KNAPSACK
4904#ifndef NO_EXACT_KNAPSACK
4905#define MAXDNOM 1000LL
4906#define MINDELTA 1e-03
4907#define MAXDELTA 1e-09
4908#define MAXSCALE 1000.0
4909#define MAXDYNPROGSPACE 1000000
4912#define MAXABSVBCOEF 1e+5
4913#define MAXBOUND 1e+10
4965 SCIP_Real* rowcoefs,
4971 SCIP_Real* closestvlb,
4991 *closestvlbidx = -1;
4996 SCIP_Real* vlbcoefs;
4997 SCIP_Real* vlbconsts;
5004 for(
i = 0;
i < nvlbs;
i++ )
5006 SCIP_Real rowcoefbinvar;
5010 SCIP_Real rowcoefsign;
5013 if( bestsub > vlbconsts[
i] )
5028 if( (
unsigned int)probidxbinvar >= (
unsigned int)
nbinvars )
5049 if( binvarused[probidxbinvar] == 1 )
5054 SCIP_Real
QUAD(tmp);
5058 rowcoefsign =
COPYSIGN(1.0, rowcoef);
5060 val2 = rowcoefsign * ((rowcoef * vlbcoefs[
i]) + rowcoefbinvar);
5066 val1 = rowcoefsign * ((rowcoef * (bestsub - vlbconsts[
i])) + rowcoefbinvar);
5073 if( vlbsol > *closestvlb )
5075 *closestvlb = vlbsol;
5078 assert(*closestvlbidx >= 0);
5095 SCIP_Real* rowcoefs,
5101 SCIP_Real* closestvub,
5121 *closestvubidx = -1;
5126 SCIP_Real* vubcoefs;
5127 SCIP_Real* vubconsts;
5134 for(
i = 0;
i < nvubs;
i++ )
5136 SCIP_Real rowcoefbinvar;
5140 SCIP_Real rowcoefsign;
5143 if( bestslb < vubconsts[
i] )
5158 if( (
unsigned int)probidxbinvar >= (
unsigned int)
nbinvars )
5179 if( binvarused[probidxbinvar] == 1 )
5184 SCIP_Real
QUAD(tmp);
5188 rowcoefsign =
COPYSIGN(1.0, rowcoef);
5190 val2 = rowcoefsign * ((rowcoef * vubcoefs[
i]) + rowcoefbinvar);
5196 val1 = rowcoefsign * ((rowcoef * (bestslb - vubconsts[
i])) + rowcoefbinvar);
5203 if( vubsol < *closestvub )
5205 *closestvub = vubsol;
5208 assert(*closestvubidx >= 0);
5223 SCIP_Real* rowcoefs,
5229 SCIP_Bool allowlocal,
5230 SCIP_Real boundswitch,
5240 SCIP_Bool* freevariable
5247 SCIP_Real simplebound;
5253 bestlbtype[varposinrow] = -3;
5254 bestubtype[varposinrow] = -3;
5256 probidx = rowinds[varposinrow];
5259 SCIP_Real
QUAD(tmp);
5271 if( bestslb[varposinrow] <= -
MAXBOUND )
5274 if( bestsub[varposinrow] >=
MAXBOUND )
5279 SCIPdebugMsg(
scip,
" %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef,
SCIPvarGetName(
var), probidx,
5280 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
5287 *freevariable =
TRUE;
5296 bestlb[varposinrow] = bestslb[varposinrow];
5297 bestlbtype[varposinrow] = bestslbtype[varposinrow];
5307 bestlb[varposinrow] = bestvlb;
5308 bestlbtype[varposinrow] = bestvlbidx;
5318 bestub[varposinrow] = bestsub[varposinrow];
5319 bestubtype[varposinrow] = bestsubtype[varposinrow];
5329 bestub[varposinrow] = bestvub;
5330 bestubtype[varposinrow] = bestvubidx;
5334 SCIPdebugMsg(
scip,
" bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
5341 *freevariable =
TRUE;
5345 *freevariable =
FALSE;
5351 if(
SCIPisEQ(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
5355 else if(
SCIPisEQ(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
5356 && bestubtype[varposinrow] >= 0 )
5360 else if(
SCIPisLE(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
5366 assert(
SCIPisGT(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
5379 binvarused[vlbvarprobidx] = 1;
5390 binvarused[vubvarprobidx] = 1;
5403 SCIP_Real boundswitch,
5404 SCIP_Bool allowlocal,
5405 SCIP_Real* rowcoefs,
5406 QUAD(SCIP_Real rowrhs),
5411 SCIP_Bool* localbdsused
5419 SCIP_Real
QUAD(transrhs);
5434 SCIPdebugMsg(
scip,
"--------------------- construction of SNF relaxation ------------------------------------\n");
5455 for(
i = nnz - 1;
i >= 0 && rowinds[
i] <
nbinvars; --
i )
5456 binvarused[rowinds[
i]] = -1;
5458 nnonbinvarsrow =
i + 1;
5460 for(
i = 0;
i < nnonbinvarsrow; ++
i )
5462 SCIP_Bool freevariable;
5467 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
5474 for( j = nnz - 1; j >= nnonbinvarsrow; --j )
5475 binvarused[rowinds[j]] = 0;
5478 for( j = 0; j <
i; ++j )
5497 *localbdsused =
FALSE;
5512 for(
i = 0;
i < nnonbinvarsrow; ++
i )
5515 SCIP_Real
QUAD(rowcoef);
5519 probidx = rowinds[
i];
5533 assert(bestsubtype[
i] == -1 || bestsubtype[
i] == -2);
5541 if( bestlbtype[
i] < 0 )
5543 SCIP_Real
QUAD(val);
5544 SCIP_Real
QUAD(contsolval);
5545 SCIP_Real
QUAD(rowcoeftimesbestsub);
5561 if( bestlbtype[
i] == -2 || bestsubtype[
i] == -2 )
5562 *localbdsused =
TRUE;
5594 SCIPdebugMsg(
scip,
" --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5600 SCIP_Real
QUAD(rowcoefbinary);
5601 SCIP_Real varsolvalbinary;
5602 SCIP_Real
QUAD(val);
5603 SCIP_Real
QUAD(contsolval);
5604 SCIP_Real
QUAD(rowcoeftimesvlbconst);
5622 assert(binvarused[vlbvarprobidx] == 1);
5631 SCIP_Real
QUAD(tmp);
5642 binvarused[vlbvarprobidx] = 0;
5673 SCIPdebugMsg(
scip,
" --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5676 vlbconsts[bestlbtype[
i]], snf->
transrhs );
5685 assert(bestslbtype[
i] == -1 || bestslbtype[
i] == -2);
5693 if( bestubtype[
i] < 0 )
5695 SCIP_Real
QUAD(val);
5696 SCIP_Real
QUAD(contsolval);
5697 SCIP_Real
QUAD(rowcoeftimesbestslb);
5713 if( bestubtype[
i] == -2 || bestslbtype[
i] == -2 )
5714 *localbdsused =
TRUE;
5746 SCIPdebugMsg(
scip,
" --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5752 SCIP_Real
QUAD(rowcoefbinary);
5753 SCIP_Real varsolvalbinary;
5754 SCIP_Real
QUAD(val);
5755 SCIP_Real
QUAD(contsolval);
5756 SCIP_Real
QUAD(rowcoeftimesvubconst);
5774 assert(binvarused[vubvarprobidx] == 1);
5781 binvarused[vubvarprobidx] = 0;
5786 SCIP_Real
QUAD(tmp);
5825 SCIPdebugMsg(
scip,
" --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5842 for(
i = nnonbinvarsrow;
i < nnz; ++
i )
5845 SCIP_Real
QUAD(rowcoef);
5848 SCIP_Real contsolval;
5849 SCIP_Real varsolval;
5851 probidx = rowinds[
i];
5856 if( binvarused[probidx] == 0 )
5860 assert(binvarused[probidx] == -1);
5863 binvarused[probidx] = 0;
5870 SCIPdebugMsg(
scip,
" %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n",
i,
QUAD_TO_DBL(rowcoef),
SCIPvarGetName(
var), probidx, varsolval,
5927 SCIPdebugMsg(
scip,
"constraint in constructed 0-1 single node flow relaxation: ");
6008 SCIP_Real* tempsort;
6009 SCIP_Real solitemsweight;
6010 SCIP_Real mediancapacity;
6022 if( solitems !=
NULL )
6027 if( solval !=
NULL )
6034 for(
i = nitems - 1;
i >= 0; --
i )
6035 tempsort[
i] = profits[
i] / weights[
i];
6047 solitemsweight = 0.0;
6048 for( j = 0; j < nitems &&
SCIPisFeasLT(
scip, solitemsweight + weights[j], capacity); j++ )
6050 if( solitems !=
NULL )
6052 solitems[*nsolitems] = items[j];
6055 if( solval !=
NULL )
6056 (*solval) += profits[j];
6057 solitemsweight += weights[j];
6061 for( ; j < nitems; j++ )
6065 if( solitems !=
NULL )
6067 solitems[*nsolitems] = items[j];
6070 if( solval !=
NULL )
6071 (*solval) += profits[j];
6072 solitemsweight += weights[j];
6074 else if( solitems !=
NULL )
6076 nonsolitems[*nnonsolitems] = items[j];
6092 SCIP_Real* vubcoefs,
6098 int* nflowcovervars,
6099 int* nnonflowcovervars,
6100 int* flowcoverstatus,
6101 QUAD(SCIP_Real* flowcoverweight),
6106 SCIP_Real
QUAD(tmp);
6114 assert(nnonsolitems >= 0);
6115 assert(nflowcovervars !=
NULL && *nflowcovervars >= 0);
6116 assert(nnonflowcovervars !=
NULL && *nnonflowcovervars >= 0);
6122 for( j = 0; j < nsolitems; j++ )
6125 if( coefs[solitems[j]] == 1 )
6127 flowcoverstatus[solitems[j]] = -1;
6128 (*nnonflowcovervars)++;
6133 assert(coefs[solitems[j]] == -1);
6134 flowcoverstatus[solitems[j]] = 1;
6135 (*nflowcovervars)++;
6139 for( j = 0; j < nnonsolitems; j++ )
6142 if( coefs[nonsolitems[j]] == 1 )
6144 flowcoverstatus[nonsolitems[j]] = 1;
6145 (*nflowcovervars)++;
6146 SCIPquadprecSumQD(*flowcoverweight, *flowcoverweight, vubcoefs[nonsolitems[j]]);
6151 assert(coefs[nonsolitems[j]] == -1);
6152 flowcoverstatus[nonsolitems[j]] = -1;
6153 (*nnonflowcovervars)++;
6162#ifndef NO_EXACT_KNAPSACK
6180 sval = val * scalar;
6181 downval = floor(sval);
6191SCIP_Longint getIntegralVal(
6200 SCIP_Longint intval;
6205 sval = val * scalar;
6224 int* nflowcovervars,
6225 int* nnonflowcovervars,
6226 int* flowcoverstatus,
6231 SCIP_Real* transprofitsint;
6232 SCIP_Real* transprofitsreal;
6233 SCIP_Real* transweightsreal;
6234 SCIP_Longint* transweightsint;
6239 SCIP_Real
QUAD(flowcoverweight);
6240 SCIP_Real
QUAD(flowcoverweightafterfix);
6241 SCIP_Real n1itemsweight;
6242 SCIP_Real n2itemsminweight;
6244 SCIP_Real transcapacityreal;
6245#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6248 SCIP_Bool scalesuccess;
6249 SCIP_Bool transweightsrealintegral;
6250 SCIP_Longint transcapacityint;
6251 int nflowcovervarsafterfix;
6254 int nnonflowcovervarsafterfix;
6270 SCIPdebugMsg(
scip,
"--------------------- get flow cover ----------------------------------------------------\n");
6284 *nflowcovervars = 0;
6285 *nnonflowcovervars = 0;
6288 nflowcovervarsafterfix = 0;
6289 nnonflowcovervarsafterfix = 0;
6291#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6305 n1itemsweight = 0.0;
6316 flowcoverstatus[j] = -1;
6317 (*nnonflowcovervars)++;
6337 flowcoverstatus[j] = -1;
6338 (*nnonflowcovervars)++;
6344 flowcoverstatus[j] = 1;
6345 (*nflowcovervars)++;
6352 flowcoverstatus[j] = 1;
6353 (*nflowcovervars)++;
6361 flowcoverstatus[j] = -1;
6362 (*nnonflowcovervars)++;
6366 assert((*nflowcovervars) + (*nnonflowcovervars) + nitems == snf->
ntransvars);
6400 transweightsrealintegral =
TRUE;
6401 for( j = 0; j < nitems; j++ )
6406 transweightsrealintegral =
FALSE;
6411 SCIPdebugMsg(
scip,
" <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6412 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6417 SCIPdebugMsg(
scip,
" <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6418 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6423 SCIPdebugMsg(
scip,
" transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6452 if( transweightsrealintegral )
6456 scalesuccess =
TRUE;
6460 scalesuccess =
FALSE;
6476 for( j = 0; j < nitems; ++j )
6478 transweightsint[j] = getIntegralVal(transweightsreal[j], scalar, -
MINDELTA,
MAXDELTA);
6479 transprofitsint[j] = transprofitsreal[j];
6480 itemsint[j] = items[j];
6484 transcapacityint = getIntegralVal(transcapacityreal, scalar, -
MINDELTA,
MAXDELTA);
6485 transcapacityint -= 1;
6488 transcapacityint = (
SCIP_Longint) (transcapacityreal * scalar);
6489 nflowcovervarsafterfix = *nflowcovervars;
6490 nnonflowcovervarsafterfix = *nnonflowcovervars;
6494 tmp2 = (
SCIP_Real) ((transcapacityint) + 1);
6495 if( transcapacityint * nitems <= MAXDYNPROGSPACE && tmp1 * tmp2 <= INT_MAX / 8.0)
6501 itemsint, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL, &success));
6507 transcapacityreal, items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6509#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6518 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6526 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6531 assert(nnonsolitems != -1);
6534 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6536 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6546 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6552 *nflowcovervars = nflowcovervarsafterfix;
6553 *nnonflowcovervars = nnonflowcovervarsafterfix;
6556 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6558 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6568 SCIPdebugMsg(
scip,
"2. %s solution:\n", kpexact ?
"exact" :
"approximate");
6575 else if( snf->
transvarcoefs[j] == -1 && flowcoverstatus[j] == 1 )
6608 int* nflowcovervars,
6609 int* nnonflowcovervars,
6610 int* flowcoverstatus,
6615 SCIP_Real* transprofitsreal;
6616 SCIP_Real* transweightsreal;
6617 SCIP_Longint* transweightsint;
6622 SCIP_Real
QUAD(flowcoverweight);
6623 SCIP_Real n1itemsweight;
6624 SCIP_Real n2itemsminweight;
6625 SCIP_Real transcapacityreal;
6645 SCIPdebugMsg(
scip,
"--------------------- get flow cover ----------------------------------------------------\n");
6658 *nflowcovervars = 0;
6659 *nnonflowcovervars = 0;
6672 n1itemsweight = 0.0;
6683 flowcoverstatus[j] = -1;
6684 (*nnonflowcovervars)++;
6706 flowcoverstatus[j] = -1;
6707 (*nnonflowcovervars)++;
6713 flowcoverstatus[j] = 1;
6714 (*nflowcovervars)++;
6721 flowcoverstatus[j] = 1;
6722 (*nflowcovervars)++;
6730 flowcoverstatus[j] = -1;
6731 (*nnonflowcovervars)++;
6735 assert((*nflowcovervars) + (*nnonflowcovervars) + nitems == snf->
ntransvars);
6769 for( j = 0; j < nitems; j++ )
6776 SCIPdebugMsg(
scip,
" <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6777 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6782 SCIPdebugMsg(
scip,
" <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6783 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6788 SCIPdebugMsg(
scip,
" transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6820 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6823 assert(nnonsolitems != -1);
6826 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6828 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6845 else if( snf->
transvarcoefs[j] == -1 && flowcoverstatus[j] == 1 )
6878 SCIP_Real
QUAD(tmp);
6879 SCIP_Real xpluslambda;
6884 xpluslambda =
x + liftingdata->
lambda;
6895 return i * liftingdata->
lambda;
6926 return i * liftingdata->
lambda;
6930 MAX(0.0, liftingdata->
m[
i] - (liftingdata->
mp - liftingdata->
lambda) - liftingdata->
ml)));
6964 SCIP_Real vubcoefpluslambda;
6967 vubcoefpluslambda = vubcoef + liftingdata->
lambda;
6975 SCIP_Real
QUAD(tmp);
6976 assert(liftingdata->
M[
i] < vubcoefpluslambda);
6996 int* transvarflowcoverstatus,
7003 SCIP_Real
QUAD(tmp);
7004 SCIP_Real
QUAD(sumN2mC2LE);
7005 SCIP_Real
QUAD(sumN2mC2GT);
7006 SCIP_Real
QUAD(sumC1LE);
7007 SCIP_Real
QUAD(sumC2);
7011 liftingdata->
m =
NULL;
7012 liftingdata->
M =
NULL;
7032 int s = (snf->
transvarcoefs[
i] + 1) + (transvarflowcoverstatus[
i] + 1)/2;
7098 for(
i = 0;
i < liftingdata->
r; ++
i)
7113 while( liftingdata->
t < liftingdata->
r && liftingdata->
m[liftingdata->
t] == liftingdata->
mp )
7116 liftingdata->
lambda = lambda;
7140 int* flowcoverstatus,
7142 SCIP_Real* cutcoefs,
7149 SCIP_Real
QUAD(rhs);
7220 if( liftedbincoef != 0.0 )
7242 SCIP_Real
QUAD(binvarcoef);
7285 SCIP_Real
QUAD(tmp);
7286 SCIP_Real
QUAD(tmp2);
7325 for(
i = 0;
i < aggrrow->
nrows; ++
i )
7331 SCIP_Real slackcoef;
7334 assert(slackcoef != 0.0);
7337 if( slackcoef > 0.0 )
7355 slackub = rowrhs - rowlhs;
7420 SCIP_Bool postprocess,
7421 SCIP_Real boundswitch,
7422 SCIP_Bool allowlocal,
7424 SCIP_Real* cutcoefs,
7428 SCIP_Real* cutefficacy,
7430 SCIP_Bool* cutislocal,
7436 SCIP_Bool localbdsused;
7439 SCIP_Real* tmpcoefs;
7440 int *transvarflowcoverstatus;
7442 int nnonflowcovervars;
7454 SCIP_CALL(
constructSNFRelaxation(
scip,
sol, boundswitch, allowlocal, aggrrow->
vals,
QUAD(aggrrow->rhs), aggrrow->
inds, aggrrow->
nnz, &snf, success, &localbdsused) );
7461 *cutislocal = aggrrow->
local || localbdsused;
7486 SCIP_Real
QUAD(rhs);
7496 for(
i = 0;
i < *cutnnz; ++
i )
7499 assert(tmpcoefs[j] != 0.0);
7500 cutcoefs[
i] = tmpcoefs[j];
7504 if( cutefficacy !=
NULL )
7507 if( cutrank !=
NULL )
7508 *cutrank = aggrrow->
rank + 1;
7513 for(
i = 0;
i < *cutnnz; ++
i )
7516 assert(tmpcoefs[j] != 0.0);
7544 SCIP_Bool allowlocal,
7545 SCIP_Real* cutcoefs,
7546 QUAD(SCIP_Real* cutrhs),
7552 SCIP_Bool* localbdsused,
7560 int aggrrowbinstart;
7587 SCIP_Real
QUAD(coef);
7594 SCIP_Real simplebound;
7608 SCIP_Real simplebound;
7623 aggrrowbinstart =
i;
7626 for(
i = 0;
i < aggrrowbinstart; ++
i )
7628 SCIP_Real
QUAD(coef);
7641 if( aggrrowbinstart != 0 )
7643 *nnz -= aggrrowbinstart;
7654 SCIP_Real
QUAD(coef);
7655 SCIP_Real simplebound;
7663 assert(v < firstnonbinvar);
7683 *localbdsused = *localbdsused || (boundtype[
i] == -2);
7711 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
7720 cutinds[
i] = cutinds[*nnz];
7743 SCIP_Real* cutcoefs,
7750 SCIP_Real* covervals,
7753 QUAD(SCIP_Real* coverweight)
7765 for( k = 0; k < cutnnz; ++k )
7769 SCIP_Real
QUAD(coef);
7773 if( varsign[k] == -1 )
7774 solval = 1 - solval;
7779 coverpos[*coversize] = k;
7800 SCIPsortDownRealInt(covervals + (*coversize), coverpos + (*coversize), cutnnz - (*coversize));
7805 while( *coversize < cutnnz &&
7809 SCIP_Real
QUAD(coef);
7810 k = coverpos[*coversize];
7833 SCIP_Real* cutcoefs,
7835 QUAD(SCIP_Real cutrhs),
7838 QUAD(SCIP_Real coverweight),
7839 SCIP_Real* covervals,
7844 QUAD(SCIP_Real* abar),
7849 SCIP_Real
QUAD(tmp);
7850 SCIP_Real
QUAD(sigma);
7865 for( k = 1; k < coversize; ++k )
7867 SCIP_Real
QUAD(lkplus1);
7868 SCIP_Real
QUAD(kdelta);
7888 SCIP_Real minusoneoverk = -1.0 / k;
7898 SCIP_Real oneoverc = 1.0 / coversize;
7911 for( k = 0; k < coversize; ++k )
7913 SCIP_Real
QUAD(coef);
7914 SCIP_Real
QUAD(coefminusabar);
7929 coverstatus[coverpos[k]] = -1;
7934 coverstatus[coverpos[k]] = -1;
7950 QUAD(SCIP_Real abar),
7951 SCIP_Real* covervals,
7957 SCIP_Real
QUAD(tmp);
7958 SCIP_Real
QUAD(hfrac);
7979 if( hreal > (SCIP_Real)coversize )
8011 while(
h < coversize )
8026 covervals[
h], cutcoef);
8050 SCIP_Bool allowlocal,
8052 SCIP_Real* cutcoefs,
8056 SCIP_Real* cutefficacy,
8058 SCIP_Bool* cutislocal,
8067 SCIP_Real* tmpcoefs;
8068 SCIP_Real* covervals;
8069 SCIP_Real
QUAD(rhs);
8070 SCIP_Real
QUAD(coverweight);
8071 SCIP_Real
QUAD(abar);
8072 SCIP_Bool transformed;
8094 if( aggrrow->
nnz == 0 )
8097 for( k = 0; k < aggrrow->
nrows; ++k )
8120 for( k = 0; k < nnz; ++k )
8122 SCIP_Real
QUAD(coef);
8139 local = aggrrow->
local;
8141 tmpcoefs,
QUAD(&rhs), tmpinds, &nnz, varsign, boundtype, &local, &transformed) );
8143 assert(allowlocal || !local);
8152 coverpos, covervals, &coversize,
QUAD(&coverweight)) )
8161 if( coversize == 1 )
8163 SCIP_Real
QUAD(tmp);
8166 for( k = 0; k < nnz; ++k )
8168 if( coverstatus[k] == 0 )
8174 tmpinds[0] = tmpinds[k];
8175 varsign[0] = varsign[k];
8180 if( varsign[0] == -1 )
8195 SCIP_Real
QUAD(tmp);
8210 QUAD(coverweight), covervals, coverstatus,
QUAD(&abar), &cplussize);
8214 for( k = 0; k < nnz; )
8217 if( coverstatus[k] == -1 )
8223 SCIP_Real
QUAD(coef);
8225 SCIPdebugMsg(
scip,
"load QUAD(coef) from tmpcoefs[tmpinds[k] = %d]\n",tmpinds[k]);
8234 if( cutcoef == 0.0 )
8239 coverstatus[k] = coverstatus[nnz];
8240 tmpinds[k] = tmpinds[nnz];
8241 varsign[k] = varsign[nnz];
8247 if( varsign[k] == -1 )
8266 *success = efficacy > *cutefficacy;
8274 *cutislocal = local;
8279 for( k = 0; k < nnz; ++k )
8281 SCIP_Real
QUAD(coef);
8298 if( cutrank !=
NULL )
8299 *cutrank = aggrrow->
rank + 1;
8307 SCIP_Real
QUAD(tmp);
8310 for( k = 0; k < nnz; ++k )
8318 if(tmpcoefs[k] != 0.0)
8377 SCIP_Real boundswitch,
8379 SCIP_Bool allowlocal,
8380 SCIP_Real* cutcoefs,
8381 QUAD(SCIP_Real* cutrhs),
8387 SCIP_Bool* freevariable,
8388 SCIP_Bool* localbdsused
8393 int aggrrowintstart;
8403 *freevariable =
FALSE;
8404 *localbdsused =
FALSE;
8422 SCIP_Real
QUAD(coef);
8429 SCIP_Real simplebound;
8437 *freevariable =
TRUE;
8445 SCIP_Real simplebound;
8453 *freevariable =
TRUE;
8462 aggrrowintstart =
i;
8465 for(
i = 0;
i < aggrrowintstart; ++
i )
8477 SCIP_Real
QUAD(coef);
8485 assert(v < firstcontvar);
8494 cutinds[
i] = cutinds[*nnz];
8501 SCIP_CALL(
determineBestBounds(
scip,
vars[v],
sol, boundswitch, 0, allowlocal,
FALSE,
FALSE,
NULL,
NULL,
8502 &bestlb, &bestub, &bestlbtype, &bestubtype, &selectedbound, freevariable) );
8513 boundtype[
i] = bestlbtype;
8521 boundtype[
i] = bestubtype;
8527 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
8600 SCIP_Real* cutcoefs,
8601 QUAD(SCIP_Real* cutrhs),
8610 SCIP_Real
QUAD(onedivoneminusf0);
8614 int aggrrowintstart;
8637 while(
i < *nnz && cutinds[
i] >= firstcontvar )
8644 assert(cutinds[
i] < firstcontvar);
8651 for(
i = *nnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
8655 SCIP_Real
QUAD(downaj);
8656 SCIP_Real
QUAD(cutaj);
8658 SCIP_Real
QUAD(tmp);
8668 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
8669 assert(varsign[
i] == +1 || varsign[
i] == -1);
8702 cutinds[
i] = cutinds[*nnz];
8712 if( varsign[
i] == +1 )
8715 if( boundtype[
i] == -1 )
8724 if( boundtype[
i] == -1 )
8735 aggrrowintstart =
i + 1;
8739 for(
i = 0;
i < aggrrowintstart; ++
i )
8752 assert(varsign[
i] == +1 || varsign[
i] == -1);
8763 if( aggrrowintstart > 0 )
8765 SCIP_Real
QUAD(tmp);
8766 assert(aggrrowintstart <= *nnz);
8770 for(
i = 0;
i < aggrrowintstart; ++
i )
8777 *nnz -= aggrrowintstart;
8778 if( *nnz < aggrrowintstart )
8816 SCIP_Real* cutcoefs,
8817 QUAD(SCIP_Real* cutrhs),
8825 SCIP_Real
QUAD(onedivoneminusf0);
8843 for(
i = 0;
i < nrowinds;
i++ )
8847 SCIP_Real
QUAD(downar);
8848 SCIP_Real
QUAD(cutar);
8855 assert(slacksign[
i] == -1 || slacksign[
i] == +1);
8912 if( slacksign[
i] == +1 )
8969 SCIP_Bool postprocess,
8970 SCIP_Real boundswitch,
8972 SCIP_Bool allowlocal,
8977 SCIP_Real* cutcoefs,
8981 SCIP_Real* cutefficacy,
8983 SCIP_Bool* cutislocal,
8991 SCIP_Real* tmpcoefs;
8992 SCIP_Real
QUAD(downrhs);
8994 SCIP_Real
QUAD(tmp);
8995 SCIP_Real
QUAD(rhs);
8998 SCIP_Bool freevariable;
8999 SCIP_Bool localbdsused;
9018 for(
i = 0;
i < aggrrow->
nrows; ++
i )
9030 *cutnnz = aggrrow->
nnz;
9031 *cutislocal = aggrrow->
local;
9040 for(
i = 0;
i < *cutnnz; ++
i )
9042 SCIP_Real
QUAD(coef);
9070 tmpcoefs,
QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, &freevariable, &localbdsused) );
9072 assert(allowlocal || !localbdsused);
9073 *cutislocal = *cutislocal || localbdsused;
9081 for(
i = *cutnnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
9083 SCIP_Real
QUAD(coef);
9167 aggrrow->
nrows, scale, tmpcoefs,
QUAD(&rhs), cutinds, cutnnz,
QUAD(f0), k) );
9188 for(
i = 0;
i < *cutnnz; ++
i )
9190 SCIP_Real
QUAD(coef);
9201 if( cutefficacy !=
NULL )
9204 if( cutrank !=
NULL )
9205 *cutrank = aggrrow->
rank + 1;
9215 for(
i = 0;
i < *cutnnz; ++
i )
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)
static SCIP_RETCODE cutsTransformMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
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,)
static SCIP_Bool chgQuadCoeffWithBound(SCIP *scip, SCIP_VAR *var, QUAD(SCIP_Real oldcoeff), SCIP_Real newcoeff, SCIP_Bool cutislocal,)
static void performBoundSubstitutionSimple(SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused)
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)
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)
static SCIP_RETCODE findBestLb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype)
static SCIP_Real calcEfficacyDenseStorageQuad(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
static SCIP_Bool removeZerosQuad(SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
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)
static SCIP_RETCODE computeLiftingData(SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
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)
static SCIP_RETCODE getFlowCover(SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, int usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable)
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)
static SCIP_RETCODE varVecAddScaledRowCoefsQuadScale(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row,)
static SCIP_RETCODE cutsTransformStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
static SCIP_Real evaluateLiftingFunctionKnapsack(SCIP *scip, QUAD(SCIP_Real x), QUAD(SCIP_Real abar), SCIP_Real *covervals, int coversize, int cplussize, SCIP_Real *scale)
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)
static SCIP_RETCODE postprocessCutQuad(SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, QUAD(SCIP_Real *cutrhs), SCIP_Bool *success)
static SCIP_Bool chgCoeffWithBound(SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal,)
static SCIP_RETCODE cutsRoundMIR(SCIP *scip, SCIP_Real *RESTRICT cutcoefs, QUAD(SCIP_Real *RESTRICT cutrhs), int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype,)
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)
static void destroyLiftingData(SCIP *scip, LIFTINGDATA *liftingdata)
static SCIP_RETCODE varVecAddScaledRowCoefsQuad(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
static SCIP_Real calcEfficacyNormQuad(SCIP *scip, SCIP_Real *vals, int *inds, int nnz)
static SCIP_RETCODE cutTightenCoefs(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
static SCIP_Bool removeZeros(SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
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)
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)
static SCIP_RETCODE postprocessCut(SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, SCIP_Real *cutrhs, SCIP_Bool *success)
static void destroySNFRelaxation(SCIP *scip, SNF_RELAXATION *snf)
static SCIP_RETCODE allocSNFRelaxation(SCIP *scip, SNF_RELAXATION *snf, int nvars)
static SCIP_RETCODE cutsRoundStrongCG(SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k)
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
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)
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)
static void getAlphaAndBeta(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
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,)
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)
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)
static SCIP_Real evaluateLiftingFunction(SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
static SCIP_RETCODE varVecAddScaledRowCoefs(int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale)
static SCIP_RETCODE findBestUb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype)
methods for the aggregation rows
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
#define QUAD_ARRAY_STORE(a, idx, x)
#define SCIPquadprecProdDD(r, a, b)
#define SCIPquadprecProdQD(r, a, b)
#define SCIPquadprecProdQQ(r, a, b)
#define SCIPquadprecSumQD(r, a, b)
#define QUAD_ARRAY_SIZE(size)
#define SCIPquadprecEpsFloorQ(r, a, eps)
#define QUAD_ASSIGN(a, constant)
#define SCIPquadprecFloorQ(r, a)
#define SCIPquadprecEpsCeilQ(r, a, eps)
#define SCIPquadprecSumDD(r, a, b)
#define SCIPquadprecSumQQ(r, a, b)
#define SCIPquadprecDivDQ(r, a, b)
#define QUAD_ASSIGN_Q(a, b)
#define QUAD_ARRAY_LOAD(r, a, idx)
#define SCIPquadprecDivDD(r, a, b)
#define SCIP_CALL_ABORT(x)
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)
int SCIPgetNContVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
#define SCIPdebugMsgPrint
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
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)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
void SCIPaggrRowCancelVarWithBound(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
int SCIPaggrRowGetRank(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
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)
void SCIPaggrRowClear(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPaggrRowCopy(SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
SCIP_Bool SCIPaggrRowIsLocal(SCIP_AGGRROW *aggrrow)
SCIP_Real SCIPaggrRowGetRhs(SCIP_AGGRROW *aggrrow)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
int SCIPaggrRowGetNRows(SCIP_AGGRROW *aggrrow)
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)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
void SCIPaggrRowPrint(SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
SCIP_Real * SCIPaggrRowGetRowWeights(SCIP_AGGRROW *aggrrow)
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
int * SCIPaggrRowGetRowInds(SCIP_AGGRROW *aggrrow)
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)
int SCIPgetNCuts(SCIP *scip)
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
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)
SCIP_Real SCIPaggrRowCalcEfficacyNorm(SCIP *scip, SCIP_AGGRROW *aggrrow)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
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)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *intval)
internal methods for LP management
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSmoveMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
methods for sorting joint arrays of various types
public methods for problem variables
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for SCIP variables
SCIP_Real * transbinvarsolvals
SCIP_Real * transcontvarsolvals
SCIP_Real * aggrconstants
SCIP_Real * aggrcoefscont
SCIP_Real * transvarvubcoefs
data structures for LP management
SCIP main data structure.
datastructures for global SCIP settings
enum SCIP_BoundType SCIP_BOUNDTYPE
enum SCIP_BaseStat SCIP_BASESTAT
#define SCIP_DECL_SORTINDCOMP(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS