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;
911 for(
i = 0;
i < *cutnnz; )
940 cutinds[
i] = cutinds[*cutnnz];
950 for(
i = 0;
i < *cutnnz; ++
i )
1003 maxabsintval *= equiscale;
1005 for(
i = 0;
i < *cutnnz; ++
i )
1007 SCIP_Real
QUAD(val);
1019 SCIP_Real maxabsval;
1022 maxabsval =
MIN(maxabsval, maxabsintval);
1023 maxabsval =
MAX(maxabsval, maxabscontval);
1025 scale = 1.0 / maxabsval;
1032 maxabsintval *= scale;
1034 for(
i = 0;
i < *cutnnz; ++
i )
1036 SCIP_Real
QUAD(val);
1048 SCIPsortDownInd(cutinds, compareAbsCoefsQuad, (
void*) cutcoefs, *cutnnz);
1051 for(
i = 0;
i < *cutnnz; )
1053 SCIP_Real
QUAD(val);
1055 if( cutinds[
i] >= nintegralvars )
1067 SCIP_Real
QUAD(coef);
1081 SCIP_Real
QUAD(delta);
1082 SCIP_Real
QUAD(tmp);
1088 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1107 cutinds[
i] = cutinds[*cutnnz];
1114 SCIP_Real
QUAD(coef);
1128 SCIP_Real
QUAD(delta);
1129 SCIP_Real
QUAD(tmp);
1135 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1154 cutinds[
i] = cutinds[*cutnnz];
1174 SCIP_Bool cutislocal,
1175 SCIP_Real* cutcoefs,
1176 QUAD(SCIP_Real* cutrhs),
1179 SCIP_Bool* redundant
1184 SCIP_Bool isintegral =
TRUE;
1186 SCIP_Real
QUAD(maxacttmp);
1188 SCIP_Real maxabsintval = 0.0;
1189 SCIP_Real maxabscontval = 0.0;
1200 for(
i = 0;
i < *cutnnz; ++
i )
1203 SCIP_Real
QUAD(quadprod);
1208 val = cutcoefs[cutinds[
i]];
1217 if( cutinds[
i] < nintegralvars )
1218 maxabsintval =
MAX(maxabsintval, -val);
1221 maxabscontval =
MAX(maxabscontval, -val);
1235 if( cutinds[
i] < nintegralvars )
1236 maxabsintval =
MAX(maxabsintval, val);
1239 maxabscontval =
MAX(maxabscontval, val);
1260 SCIP_Real equiscale;
1261 SCIP_Real intscalar;
1263 SCIP_Real* intcoeffs;
1267 equiscale = 1.0 /
MIN((maxact -
QUAD_TO_DBL(*cutrhs)), maxabsintval);
1269 for(
i = 0;
i < *cutnnz; ++
i )
1273 val = equiscale * cutcoefs[cutinds[
i]];
1279 (SCIP_Longint)
scip->set->sepa_maxcoefratio,
scip->set->sepa_maxcoefratio, &intscalar, &success) );
1286 intscalar *= equiscale;
1290 for(
i = 0;
i < *cutnnz; )
1295 val = cutcoefs[cutinds[
i]];
1309 cutcoefs[cutinds[
i]] = intval;
1315 cutcoefs[cutinds[
i]] = 0.0;
1317 cutinds[
i] = cutinds[*cutnnz];
1327 for(
i = 0;
i < *cutnnz; ++
i )
1330 SCIP_Real
QUAD(quadprod);
1335 val = cutcoefs[cutinds[
i]];
1341 maxabsintval =
MAX(maxabsintval, -val);
1350 maxabsintval =
MAX(maxabsintval, val);
1379 maxabsintval *= equiscale;
1381 for(
i = 0;
i < *cutnnz; ++
i )
1382 cutcoefs[cutinds[
i]] *= equiscale;
1389 SCIP_Real maxabsval;
1392 maxabsval =
MIN(maxabsval, maxabsintval);
1393 maxabsval =
MAX(maxabsval, maxabscontval);
1395 scale = 1.0 / maxabsval;
1402 maxabsintval *= scale;
1404 for(
i = 0;
i < *cutnnz; ++
i )
1405 cutcoefs[cutinds[
i]] *= scale;
1415 for(
i = 0;
i < *cutnnz; )
1419 if( cutinds[
i] >= nintegralvars )
1425 val = cutcoefs[cutinds[
i]];
1431 SCIP_Real
QUAD(coef);
1445 SCIP_Real
QUAD(delta);
1446 SCIP_Real
QUAD(tmp);
1452 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1468 cutcoefs[cutinds[
i]] = 0.0;
1470 cutinds[
i] = cutinds[*cutnnz];
1477 SCIP_Real
QUAD(coef);
1491 SCIP_Real
QUAD(delta);
1492 SCIP_Real
QUAD(tmp);
1498 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1514 cutcoefs[cutinds[
i]] = 0.0;
1516 cutinds[
i] = cutinds[*cutnnz];
1537 SCIP_Bool cutislocal,
1538 SCIP_Real* cutcoefs,
1549 SCIP_Real
QUAD(maxacttmp);
1551 SCIP_Real maxabsval = 0.0;
1552 SCIP_Bool redundant =
FALSE;
1565 for(
i = 0;
i < *cutnnz; ++
i )
1567 SCIP_Real
QUAD(quadprod);
1572 if( cutcoefs[
i] < 0.0 )
1579 if( cutinds[
i] < nintegralvars )
1581 maxabsval =
MAX(maxabsval, -cutcoefs[
i]);
1582 absvals[
i] = -cutcoefs[
i];
1597 if( cutinds[
i] < nintegralvars )
1599 maxabsval =
MAX(maxabsval, cutcoefs[
i]);
1600 absvals[
i] = cutcoefs[
i];
1627 for(
i = 0;
i < *cutnnz; ++
i )
1630 if( cutinds[
i] >= nintegralvars )
1635 if( cutcoefs[
i] < 0.0 &&
SCIPisLE(
scip, maxact + cutcoefs[
i], *cutrhs) )
1637 SCIP_Real coef = (*cutrhs) - maxact;
1642 if( coef > cutcoefs[
i] )
1644 SCIP_Real
QUAD(delta);
1645 SCIP_Real
QUAD(tmp);
1651 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1670 cutinds[
i] = cutinds[*cutnnz];
1671 cutcoefs[
i] = cutcoefs[*cutnnz];
1676 else if( cutcoefs[
i] > 0.0 &&
SCIPisLE(
scip, maxact - cutcoefs[
i], *cutrhs) )
1678 SCIP_Real coef = maxact - (*cutrhs);
1683 if( coef < cutcoefs[
i] )
1685 SCIP_Real
QUAD(delta);
1686 SCIP_Real
QUAD(tmp);
1692 SCIPdebugMsg(
scip,
"tightened coefficient from %g to %g; rhs changed from %g to %g; the bounds are [%g,%g]\n",
1711 cutinds[
i] = cutinds[*cutnnz];
1712 cutcoefs[
i] = cutcoefs[*cutnnz];
1749 (*aggrrow)->local =
FALSE;
1750 (*aggrrow)->nnz = 0;
1751 (*aggrrow)->rank = 0;
1753 (*aggrrow)->rowsinds =
NULL;
1754 (*aggrrow)->slacksign =
NULL;
1755 (*aggrrow)->rowweights =
NULL;
1756 (*aggrrow)->nrows = 0;
1757 (*aggrrow)->rowssize = 0;
1804 if( aggrrow->
nnz == 0 )
1807 for(
i = 0;
i < aggrrow->
nnz; ++
i )
1809 SCIP_Real
QUAD(val);
1838 (*aggrrow)->nnz = source->
nnz;
1841 if( source->
nrows > 0 )
1853 (*aggrrow)->rowsinds =
NULL;
1854 (*aggrrow)->slacksign =
NULL;
1855 (*aggrrow)->rowweights =
NULL;
1858 (*aggrrow)->nrows = source->
nrows;
1859 (*aggrrow)->rowssize = source->
nrows;
1860 (*aggrrow)->rank = source->
rank;
1861 (*aggrrow)->local = source->
local;
1875 SCIP_Real
QUAD(quadprod);
1901 if( sidetype == -1 )
1906 else if( sidetype == 1 )
1961 SCIP_Real
QUAD(val);
1967 v = aggrrow->
inds[pos];
2020 SCIP_Real
QUAD(val);
2030 if( aggrrow->
nnz == 0 )
2052 SCIP_Real
QUAD(quadprod);
2100 SCIP_Real
QUAD(quadprod);
2117 for(
i = 0 ;
i < len; ++
i )
2119 SCIP_Real
QUAD(val);
2120 int probindex = inds[
i];
2125 aggrrow->
inds[aggrrow->
nnz++] = probindex;
2146 SCIP_Real
QUAD(tmp);
2150 for(
i = 0;
i < aggrrow->
nnz; ++
i )
2183 SCIP_Bool sidetypebasis,
2184 SCIP_Bool allowlocal,
2187 SCIP_Bool* rowtoolong
2190 SCIP_Real
QUAD(quadprod);
2196 *rowtoolong =
FALSE;
2231 if( weight > 0.0 && ((negslack == 0) || (negslack == 1 && !row->
integral)) )
2243 if( weight < 0.0 && ((negslack == 0) || (negslack == 1 && !row->
integral)) )
2278 if( aggrrow->
nnz > maxaggrlen )
2293 SCIP_Bool sidetypebasis,
2294 SCIP_Bool allowlocal,
2305 SCIP_Bool rowtoolong;
2317 if( rowinds !=
NULL && nrowinds > -1 )
2319 for( k = 0; k < nrowinds; ++k )
2321 SCIP_CALL(
addOneRow(
scip, aggrrow, rows[rowinds[k]], weights[rowinds[k]], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2329 for( k = 0; k < nrows; ++k )
2331 if( weights[k] != 0.0 )
2333 SCIP_CALL(
addOneRow(
scip, aggrrow, rows[k], weights[k], sidetypebasis, allowlocal, negslack, maxaggrlen, &rowtoolong) );
2353 SCIP_Bool cutislocal,
2355 SCIP_Real* cutcoefs,
2362 SCIP_Bool redundant;
2364 SCIP_Real minallowedcoef;
2365 SCIP_Real
QUAD(rhs);
2395 for(
i = 0;
i < *nnz; ++
i )
2397 SCIP_Real absval =
REALABS(cutcoefs[cutinds[
i]]);
2398 maxcoef =
MAX(absval, maxcoef);
2401 maxcoef /=
scip->set->sepa_maxcoefratio;
2403 minallowedcoef =
MAX(minallowedcoef, maxcoef);
2405 *success = !
removeZeros(
scip, minallowedcoef, cutislocal, cutcoefs,
QUAD(&rhs), cutinds, nnz);
2422 SCIP_Bool cutislocal,
2424 SCIP_Real* cutcoefs,
2426 QUAD(SCIP_Real* cutrhs),
2431 SCIP_Bool redundant;
2433 SCIP_Real minallowedcoef;
2460 for(
i = 0;
i < *nnz; ++
i )
2463 SCIP_Real
QUAD(coef);
2466 maxcoef =
MAX(abscoef, maxcoef);
2469 maxcoef /=
scip->set->sepa_maxcoefratio;
2471 minallowedcoef =
MAX(minallowedcoef, maxcoef);
2482 SCIP_Bool useglbbounds,
2490 QUAD(&aggrrow->rhs), aggrrow->
inds, &aggrrow->
nnz);
2500 return aggrrow->
nrows;
2539 for(
i = 0;
i < aggrrow->
nrows; ++
i )
2555 return aggrrow->
inds;
2565 return aggrrow->
nnz;
2575 return aggrrow->
rank;
2585 return aggrrow->
local;
2600#define MAXCMIRSCALE 1e+6
2609 SCIP_Bool allowlocal,
2611 SCIP_Real* simplebound,
2633 *simplebound = *bestlb;
2641 if( bestvlbidx >= 0 && (bestvlb > *bestlb || (*bestlbtype < 0 &&
SCIPisGE(
scip, bestvlb, *bestlb))) )
2655 *bestlbtype = bestvlbidx;
2670 SCIP_Bool allowlocal,
2672 SCIP_Real* simplebound,
2694 *simplebound = *bestub;
2702 if( bestvubidx >= 0 && (bestvub < *bestub || (*bestubtype < 0 &&
SCIPisLE(
scip, bestvub, *bestub))) )
2716 *bestubtype = bestvubidx;
2730 SCIP_Real boundswitch,
2732 SCIP_Bool allowlocal,
2733 SCIP_Bool fixintegralrhs,
2734 SCIP_Bool ignoresol,
2735 int* boundsfortrans,
2745 SCIP_Bool* freevariable
2755 if( boundsfortrans !=
NULL && boundsfortrans[v] > -3 )
2764 *bestlbtype = boundsfortrans[v];
2765 if( *bestlbtype == -1 )
2767 else if( *bestlbtype == -2 )
2772 SCIP_Real* vlbcoefs;
2773 SCIP_Real* vlbconsts;
2782 k = boundsfortrans[v];
2802 *bestubtype = boundsfortrans[v];
2803 if( *bestubtype == -1 )
2805 else if( *bestubtype == -2 )
2810 SCIP_Real* vubcoefs;
2811 SCIP_Real* vubconsts;
2820 k = boundsfortrans[v];
2855 *freevariable =
TRUE;
2868 else if(
SCIPisLT(
scip, varsol, (1.0 - boundswitch) * (*bestlb) + boundswitch * (*bestub)) )
2870 else if(
SCIPisGT(
scip, varsol, (1.0 - boundswitch) * (*bestlb) + boundswitch * (*bestub)) )
2872 else if( *bestlbtype == -1 )
2874 else if( *bestubtype == -1 )
2876 else if( ((*bestlbtype) >= 0 || (*bestubtype) >= 0) && !
SCIPisEQ(
scip, *bestlb - simplelb, simpleub - *bestub) )
2878 if( *bestlb - simplelb > simpleub - *bestub )
2883 else if( *bestlbtype >= 0 )
2885 else if( *bestubtype >= 0 )
2894 SCIP_Real distlb =
REALABS(glblb - *bestlb);
2895 SCIP_Real distub =
REALABS(glbub - *bestub);
2928 SCIP_Real* cutcoefs,
2929 QUAD(SCIP_Real* cutrhs),
2936 SCIP_Bool* localbdsused
2939 SCIP_Real
QUAD(coef);
2940 SCIP_Real
QUAD(tmp);
2951 *localbdsused = *localbdsused || (boundtype == -2);
2956 SCIP_Real* vbdcoefs;
2957 SCIP_Real* vbdconsts;
2958 SCIP_Real
QUAD(zcoef);
2991 cutinds[(*nnz)++] = zidx;
3007 SCIP_Real* cutcoefs,
3008 QUAD(SCIP_Real* cutrhs),
3013 SCIP_Bool* localbdsused
3016 SCIP_Real
QUAD(coef);
3017 SCIP_Real
QUAD(tmp);
3028 *localbdsused = *localbdsused || (boundtype == -2);
3063 SCIP_Real boundswitch,
3065 SCIP_Bool allowlocal,
3066 SCIP_Bool fixintegralrhs,
3067 SCIP_Bool ignoresol,
3068 int* boundsfortrans,
3075 SCIP_Real* cutcoefs,
3076 QUAD(SCIP_Real* cutrhs),
3082 SCIP_Bool* freevariable,
3083 SCIP_Bool* localbdsused
3086 SCIP_Real
QUAD(tmp);
3093 int aggrrowintstart;
3103 *freevariable =
FALSE;
3104 *localbdsused =
FALSE;
3127 ignoresol, boundsfortrans, boundtypesfortrans,
3128 bestlbs +
i, bestubs +
i, bestlbtypes +
i, bestubtypes +
i, selectedbounds +
i, freevariable) );
3135 aggrrowintstart =
i;
3138 for(
i = 0;
i < aggrrowintstart; ++
i )
3147 boundtype[
i] = bestlbtypes[
i];
3157 boundtype[
i] = bestubtypes[
i];
3169 SCIP_Real
QUAD(coef);
3171 assert(cutinds[
i] < firstcontvar);
3181 cutinds[
i] = cutinds[*nnz];
3188 ignoresol, boundsfortrans, boundtypesfortrans,
3189 bestlbs +
i, bestubs +
i, bestlbtypes +
i, bestubtypes +
i, selectedbounds +
i, freevariable) );
3199 for(
i = aggrrowintstart;
i < *nnz; ++
i )
3210 boundtype[
i] = bestlbtypes[
i];
3221 boundtype[
i] = bestubtypes[
i];
3228 if( fixintegralrhs )
3234 if( f0 < minfrac || f0 > maxfrac )
3236 SCIP_Real bestviolgain;
3237 SCIP_Real bestnewf0;
3242 bestviolgain = -1e+100;
3244 for(
i = 0;
i < *nnz;
i++ )
3247 SCIP_Real
QUAD(coef);
3255 if( boundtype[
i] < 0
3279 if( newf0 < minfrac || newf0 > maxfrac )
3281 if( v >= firstcontvar )
3295 viol = f0 - fj * (varsign[
i] == +1 ? solval - bestlbs[
i] : bestubs[
i] - solval);
3296 newviol = newf0 - newfj * (varsign[
i] == -1 ? solval - bestlbs[
i] : bestubs[
i] - solval);
3297 violgain = newviol - viol;
3302 SCIPerrorMessage(
"Cannot handle closest bounds with ignoring the LP solution.\n");
3312 bestviolgain = violgain;
3320 SCIP_Real
QUAD(coef);
3322 assert(boundtype[besti] < 0);
3334 if( varsign[besti] == +1 )
3337 assert(bestubtypes[besti] < 0);
3338 boundtype[besti] = bestubtypes[besti];
3339 varsign[besti] = -1;
3344 assert(bestlbtypes[besti] < 0);
3345 boundtype[besti] = bestlbtypes[besti];
3346 varsign[besti] = +1;
3348 *localbdsused = *localbdsused || (boundtype[besti] == -2);
3427 SCIP_Real
QUAD(tmp);
3428 SCIP_Real
QUAD(onedivoneminusf0);
3455 while(
i < *nnz && cutinds[
i] >= firstcontvar )
3460 assert(cutinds[
i] < firstcontvar);
3466 for(
i = *nnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
3469 SCIP_Real
QUAD(cutaj);
3478 assert(varsign[
i] == +1 || varsign[
i] == -1);
3483 SCIP_Real
QUAD(downaj);
3512 cutinds[
i] = cutinds[*nnz];
3522 if( varsign[
i] == +1 )
3525 if( boundtype[
i] == -1 )
3541 if( boundtype[
i] == -1 )
3558 while(
i >= ndelcontvars )
3561 SCIP_Real
QUAD(cutaj);
3571 assert(varsign[
i] == +1 || varsign[
i] == -1);
3572 assert( v >= firstcontvar );
3590 cutinds[
i] = cutinds[ndelcontvars];
3591 varsign[
i] = varsign[ndelcontvars];
3592 boundtype[
i] = boundtype[ndelcontvars];
3600 if( boundtype[
i] < 0 )
3605 if( varsign[
i] == +1 )
3608 if( boundtype[
i] == -1 )
3624 if( boundtype[
i] == -1 )
3643 SCIP_Real
QUAD(zcoef);
3648 vbidx = boundtype[
i];
3651 if( varsign[
i] == +1 )
3669 assert(0 <= zidx && zidx < firstcontvar);
3679 cutinds[(*nnz)++] = zidx;
3692 if( ndelcontvars > 0 )
3694 assert(ndelcontvars <= *nnz);
3695 *nnz -= ndelcontvars;
3696 if( *nnz < ndelcontvars )
3734 SCIP_Real* cutcoefs,
3735 QUAD(SCIP_Real* cutrhs),
3742 SCIP_Real
QUAD(onedivoneminusf0);
3760 for(
i = 0;
i < nrowinds;
i++ )
3764 SCIP_Real
QUAD(downar);
3765 SCIP_Real
QUAD(cutar);
3767 SCIP_Real
QUAD(tmp);
3768 SCIP_Real
QUAD(myprod);
3773 assert(slacksign[
i] == -1 || slacksign[
i] == +1);
3831 if( slacksign[
i] == +1 )
3833 SCIP_Real
QUAD(rowrhs);
3848 SCIP_Real
QUAD(rowlhs);
3884 SCIP_Bool postprocess,
3885 SCIP_Real boundswitch,
3887 SCIP_Bool allowlocal,
3888 SCIP_Bool fixintegralrhs,
3889 int* boundsfortrans,
3898 SCIP_Real* cutcoefs,
3902 SCIP_Real* cutefficacy,
3904 SCIP_Bool* cutislocal,
3914 SCIP_Real* tmpcoefs;
3916 SCIP_Real
QUAD(rhs);
3917 SCIP_Real
QUAD(downrhs);
3919 SCIP_Bool freevariable;
3920 SCIP_Bool localbdsused;
3921 SCIP_Bool tmpislocal;
3939 tmpnnz = aggrrow->
nnz;
3940 tmpislocal = aggrrow->
local;
3948 for(
i = 0;
i < tmpnnz; ++
i )
3950 SCIP_Real
QUAD(coef);
3951 int k = aggrrow->
inds[
i];
3978 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, tmpcoefs,
QUAD(&rhs), tmpinds, &tmpnnz, varsign, boundtype, &freevariable, &localbdsused) );
3979 assert(allowlocal || !localbdsused);
3980 tmpislocal = tmpislocal || localbdsused;
4057 aggrrow->
nrows, scale, tmpcoefs,
QUAD(&rhs), tmpinds, &tmpnnz,
QUAD(f0)) );
4086 *cutislocal = tmpislocal;
4089 for(
i = 0;
i < *cutnnz; ++
i )
4091 SCIP_Real
QUAD(coef);
4101 if( cutefficacy !=
NULL )
4102 *cutefficacy = mirefficacy;
4104 if( cutrank !=
NULL )
4105 *cutrank = aggrrow->
rank + 1;
4116 SCIP_Real
QUAD(tmp);
4119 for(
i = 0;
i < tmpnnz; ++
i )
4143 SCIP_Real contactivity,
4144 SCIP_Real contsqrnorm,
4152 SCIP_Real f0pluseps;
4154 SCIP_Real onedivoneminusf0;
4158 SCIP_Real contscale;
4160 scale = 1.0 / delta;
4165 if( f0 < minfrac || f0 > maxfrac )
4168 onedivoneminusf0 = 1.0 / (1.0 - f0);
4170 contscale = scale * onedivoneminusf0;
4179 rhs -= contscale * contactivity;
4180 norm =
SQR(contscale) * contsqrnorm;
4190 SCIP_Real fi = (scale * coefs[
i]) - floorai;
4192 if( fi > f0pluseps )
4193 floorai += (fi - f0) * onedivoneminusf0;
4195 rhs -= solvals[
i] * floorai;
4196 norm +=
SQR(floorai);
4201 return - rhs /
MAX(norm, 1e-6);
4223 SCIP_Bool postprocess,
4224 SCIP_Real boundswitch,
4226 SCIP_Bool allowlocal,
4228 int* boundsfortrans,
4236 SCIP_Real* cutcoefs,
4240 SCIP_Real* cutefficacy,
4243 SCIP_Bool* cutislocal,
4255 SCIP_Real* mksetcoefs;
4256 SCIP_Real
QUAD(mksetrhs);
4258 SCIP_Real* bounddist;
4261 SCIP_Real* tmpcoefs;
4262 SCIP_Real* tmpvalues;
4263 SCIP_Real* deltacands;
4265 SCIP_Real bestdelta;
4266 SCIP_Real bestefficacy;
4267 SCIP_Real maxabsmksetcoef;
4269 SCIP_Bool freevariable;
4270 SCIP_Bool localbdsused;
4271 SCIP_Real contactivity;
4272 SCIP_Real contsqrnorm;
4301 mksetnnz = aggrrow->
nnz;
4306 for(
i = 0;
i < mksetnnz; ++
i )
4308 int j = mksetinds[
i];
4309 SCIP_Real
QUAD(coef);
4315 *cutislocal = aggrrow->
local;
4333 boundsfortrans, boundtypesfortrans, minfrac, maxfrac, mksetcoefs,
QUAD(&mksetrhs), mksetinds, &mksetnnz, varsign, boundtype, &freevariable, &localbdsused) );
4335 assert(allowlocal || !localbdsused);
4344 maxabsmksetcoef = -1.0;
4347 for(
i = mksetnnz - 1;
i >= 0 && mksetinds[
i] < firstcontvar; --
i )
4353 SCIP_Real
QUAD(coef);
4361 bounddistpos[nbounddist] =
i;
4367 if( nbounddist == 0 )
4371 ndeltacands = nbounddist;
4377 SCIP_Bool intscalesuccess;
4381 if( intscalesuccess )
4384 SCIP_Real intscalerhs;
4388 delta = 1.0 / intscale;
4389 intf0 = intscalerhs - floor(intscalerhs);
4393 if( intf0 < minfrac || intf0 > maxfrac )
4395 intscale *=
SCIPceil(
scip,
MAX(minfrac, (1.0 - maxfrac)) /
MIN(intf0, (1.0 - intf0)));
4397 delta = 1.0 / intscale;
4398 intf0 = intscalerhs - floor(intscalerhs);
4401 if( intf0 >= minfrac && intf0 <= maxfrac )
4404 deltacands[ndeltacands++] = delta;
4406 if( intf0 < maxfrac )
4410 delta2 = 1.0 / (intscale *
SCIPfloor(
scip, maxfrac / intf0));
4413 deltacands[ndeltacands++] = delta2;
4420 for(
i = 0;
i < nbounddist; ++
i )
4422 SCIP_Real absmksetcoef;
4424 absmksetcoef =
REALABS(deltacands[
i]);
4425 maxabsmksetcoef =
MAX(absmksetcoef, maxabsmksetcoef);
4427 deltacands[
i] = absmksetcoef;
4431 if( maxabsmksetcoef != -1.0 )
4432 deltacands[ndeltacands++] = maxabsmksetcoef + 1.0;
4434 deltacands[ndeltacands++] = 1.0;
4436 maxtestdelta =
MIN(ndeltacands, maxtestdelta);
4468 for(
i = intstart;
i < mksetnnz; ++
i )
4472 SCIP_Real
QUAD(coef);
4480 if( boundtype[
i] == -1 )
4483 if( varsign[
i] == -1 )
4493 if( varsign[
i] == -1 )
4499 tmpvalues[ntmpcoefs] = solval;
4505 assert(ntmpcoefs == mksetnnz - intstart);
4509 for(
i = 0;
i < intstart; ++
i )
4512 SCIP_Real
QUAD(mksetcoef);
4523 switch( boundtype[
i] )
4527 if( varsign[
i] == -1 )
4534 if( varsign[
i] == -1 )
4541 if( varsign[
i] == -1 )
4545 SCIP_Real vbdsolval;
4551 solval = (coef * vbdsolval + constant) - solval;
4557 SCIP_Real vbdsolval;
4563 solval = solval - (coef * vbdsolval + constant);
4567 contactivity += solval * (
QUAD_TO_DBL(mksetcoef) * varsign[
i]);
4576 for(
i = 0;
i < aggrrow->
nrows; ++
i )
4594 slackval = row->
rhs - slackval;
4602 slackval = slackval - row->
lhs;
4608 tmpvalues[ntmpcoefs] = slackval;
4617 contactivity += slackval * slackcoeff;
4618 contsqrnorm +=
SQR(slackcoeff);
4627 for(
i = 0;
i < maxtestdelta; ++
i )
4633 SCIP_Bool deltaseenbefore =
FALSE;
4634 for( j = 0; j <
i; ++j )
4638 deltaseenbefore =
TRUE;
4644 if( deltaseenbefore )
4646 maxtestdelta =
MIN(maxtestdelta + 1, ndeltacands);
4652 if( efficacy > bestefficacy )
4654 bestefficacy = efficacy;
4655 bestdelta = deltacands[
i];
4665 SCIP_Real basedelta = bestdelta;
4666 for(
i = 2;
i <= 8 ;
i *= 2 )
4671 delta = basedelta /
i;
4675 if( efficacy > bestefficacy )
4677 bestefficacy = efficacy;
4686 for(
i = 0;
i < nbounddist; ++
i )
4689 SCIP_Real newefficacy;
4690 SCIP_Real
QUAD(newrhs);
4691 SCIP_Real
QUAD(quadprod);
4694 SCIP_Real oldsolval;
4695 SCIP_Real simplebnd;
4699 k = bounddistpos[
i];
4714 SCIP_Real
QUAD(coef);
4723 tmpcoefs[k - intstart] = -tmpcoefs[k - intstart];
4725 oldsolval = tmpvalues[k - intstart];
4732 if( newefficacy > bestefficacy )
4735 bestefficacy = newefficacy;
4738 if( varsign[k] == +1 )
4742 boundtype[k] = bestubtype;
4749 boundtype[k] = bestlbtype;
4753 localbdsused = localbdsused || (boundtype[k] == -2);
4758 tmpcoefs[k - intstart] = -tmpcoefs[k - intstart];
4759 tmpvalues[k - intstart] = oldsolval;
4763 if( bestefficacy > 0.0 )
4765 SCIP_Real mirefficacy;
4766 SCIP_Real
QUAD(downrhs);
4770 scale = 1.0 / bestdelta;
4779 for(
i = 0;
i < mksetnnz; ++
i )
4781 SCIP_Real
QUAD(coef);
4812 aggrrow->
nrows, scale, mksetcoefs,
QUAD(&mksetrhs), mksetinds, &mksetnnz,
QUAD(f0)) );
4820 for(
i = 0;
i < mksetnnz; ++
i )
4822 SCIP_Real
QUAD(coef);
4829 SCIPdebugMsg(
scip,
"efficacy of cmir cut is different than expected efficacy: %f != %f\n", efficacy, bestefficacy);
4834 *cutislocal = *cutislocal || localbdsused;
4848 SCIPdebugMsg(
scip,
"post-processed cut (success = %s):\n", *success ?
"TRUE" :
"FALSE");
4858 for(
i = 0;
i < mksetnnz; ++
i )
4860 SCIP_Real
QUAD(coef);
4871 *cutefficacy = mirefficacy;
4872 if( cutrank !=
NULL )
4873 *cutrank = aggrrow->
rank + 1;
4874 *cutislocal = *cutislocal || localbdsused;
4885 SCIP_Real
QUAD(tmp);
4888 for(
i = 0;
i < mksetnnz; ++
i )
4910#define NO_EXACT_KNAPSACK
4912#ifndef NO_EXACT_KNAPSACK
4913#define MAXDNOM 1000LL
4914#define MINDELTA 1e-03
4915#define MAXDELTA 1e-09
4916#define MAXSCALE 1000.0
4917#define MAXDYNPROGSPACE 1000000
4920#define MAXABSVBCOEF 1e+5
4921#define MAXBOUND 1e+10
4973 SCIP_Real* rowcoefs,
4979 SCIP_Real* closestvlb,
4999 *closestvlbidx = -1;
5004 SCIP_Real* vlbcoefs;
5005 SCIP_Real* vlbconsts;
5012 for(
i = 0;
i < nvlbs;
i++ )
5014 SCIP_Real rowcoefbinvar;
5018 SCIP_Real rowcoefsign;
5021 if( bestsub > vlbconsts[
i] )
5036 if( (
unsigned int)probidxbinvar >= (
unsigned int)
nbinvars )
5057 if( binvarused[probidxbinvar] == 1 )
5062 SCIP_Real
QUAD(tmp);
5066 rowcoefsign =
COPYSIGN(1.0, rowcoef);
5068 val2 = rowcoefsign * ((rowcoef * vlbcoefs[
i]) + rowcoefbinvar);
5074 val1 = rowcoefsign * ((rowcoef * (bestsub - vlbconsts[
i])) + rowcoefbinvar);
5081 if( vlbsol > *closestvlb )
5083 *closestvlb = vlbsol;
5086 assert(*closestvlbidx >= 0);
5103 SCIP_Real* rowcoefs,
5109 SCIP_Real* closestvub,
5129 *closestvubidx = -1;
5134 SCIP_Real* vubcoefs;
5135 SCIP_Real* vubconsts;
5142 for(
i = 0;
i < nvubs;
i++ )
5144 SCIP_Real rowcoefbinvar;
5148 SCIP_Real rowcoefsign;
5151 if( bestslb < vubconsts[
i] )
5166 if( (
unsigned int)probidxbinvar >= (
unsigned int)
nbinvars )
5187 if( binvarused[probidxbinvar] == 1 )
5192 SCIP_Real
QUAD(tmp);
5196 rowcoefsign =
COPYSIGN(1.0, rowcoef);
5198 val2 = rowcoefsign * ((rowcoef * vubcoefs[
i]) + rowcoefbinvar);
5204 val1 = rowcoefsign * ((rowcoef * (bestslb - vubconsts[
i])) + rowcoefbinvar);
5211 if( vubsol < *closestvub )
5213 *closestvub = vubsol;
5216 assert(*closestvubidx >= 0);
5231 SCIP_Real* rowcoefs,
5237 SCIP_Bool allowlocal,
5238 SCIP_Real boundswitch,
5248 SCIP_Bool* freevariable
5255 SCIP_Real simplebound;
5261 bestlbtype[varposinrow] = -3;
5262 bestubtype[varposinrow] = -3;
5264 probidx = rowinds[varposinrow];
5267 SCIP_Real
QUAD(tmp);
5279 if( bestslb[varposinrow] <= -
MAXBOUND )
5282 if( bestsub[varposinrow] >=
MAXBOUND )
5287 SCIPdebugMsg(
scip,
" %d: %g <%s, idx=%d, lp=%g, [%g(%d),%g(%d)]>:\n", varposinrow, rowcoef,
SCIPvarGetName(
var), probidx,
5288 solval, bestslb[varposinrow], bestslbtype[varposinrow], bestsub[varposinrow], bestsubtype[varposinrow]);
5295 *freevariable =
TRUE;
5304 bestlb[varposinrow] = bestslb[varposinrow];
5305 bestlbtype[varposinrow] = bestslbtype[varposinrow];
5315 bestlb[varposinrow] = bestvlb;
5316 bestlbtype[varposinrow] = bestvlbidx;
5326 bestub[varposinrow] = bestsub[varposinrow];
5327 bestubtype[varposinrow] = bestsubtype[varposinrow];
5337 bestub[varposinrow] = bestvub;
5338 bestubtype[varposinrow] = bestvubidx;
5342 SCIPdebugMsg(
scip,
" bestlb=%g(%d), bestub=%g(%d)\n", bestlb[varposinrow], bestlbtype[varposinrow], bestub[varposinrow], bestubtype[varposinrow]);
5349 *freevariable =
TRUE;
5353 *freevariable =
FALSE;
5359 if(
SCIPisEQ(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) && bestlbtype[varposinrow] >= 0 )
5363 else if(
SCIPisEQ(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow])
5364 && bestubtype[varposinrow] >= 0 )
5368 else if(
SCIPisLE(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]) )
5374 assert(
SCIPisGT(
scip, solval, (1.0 - boundswitch) * bestlb[varposinrow] + boundswitch * bestub[varposinrow]));
5387 binvarused[vlbvarprobidx] = 1;
5398 binvarused[vubvarprobidx] = 1;
5411 SCIP_Real boundswitch,
5412 SCIP_Bool allowlocal,
5413 SCIP_Real* rowcoefs,
5414 QUAD(SCIP_Real rowrhs),
5419 SCIP_Bool* localbdsused
5427 SCIP_Real
QUAD(transrhs);
5442 SCIPdebugMsg(
scip,
"--------------------- construction of SNF relaxation ------------------------------------\n");
5463 for(
i = nnz - 1;
i >= 0 && rowinds[
i] <
nbinvars; --
i )
5464 binvarused[rowinds[
i]] = -1;
5466 nnonbinvarsrow =
i + 1;
5468 for(
i = 0;
i < nnonbinvarsrow; ++
i )
5470 SCIP_Bool freevariable;
5475 bestlb, bestub, bestslb, bestsub, bestlbtype, bestubtype, bestslbtype, bestsubtype, selectedbounds, &freevariable) );
5482 for( j = nnz - 1; j >= nnonbinvarsrow; --j )
5483 binvarused[rowinds[j]] = 0;
5486 for( j = 0; j <
i; ++j )
5505 *localbdsused =
FALSE;
5520 for(
i = 0;
i < nnonbinvarsrow; ++
i )
5523 SCIP_Real
QUAD(rowcoef);
5527 probidx = rowinds[
i];
5541 assert(bestsubtype[
i] == -1 || bestsubtype[
i] == -2);
5549 if( bestlbtype[
i] < 0 )
5551 SCIP_Real
QUAD(val);
5552 SCIP_Real
QUAD(contsolval);
5553 SCIP_Real
QUAD(rowcoeftimesbestsub);
5569 if( bestlbtype[
i] == -2 || bestsubtype[
i] == -2 )
5570 *localbdsused =
TRUE;
5602 SCIPdebugMsg(
scip,
" --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5608 SCIP_Real
QUAD(rowcoefbinary);
5609 SCIP_Real varsolvalbinary;
5610 SCIP_Real
QUAD(val);
5611 SCIP_Real
QUAD(contsolval);
5612 SCIP_Real
QUAD(rowcoeftimesvlbconst);
5630 assert(binvarused[vlbvarprobidx] == 1);
5639 SCIP_Real
QUAD(tmp);
5650 binvarused[vlbvarprobidx] = 0;
5681 SCIPdebugMsg(
scip,
" --> bestlb used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5684 vlbconsts[bestlbtype[
i]], snf->
transrhs );
5693 assert(bestslbtype[
i] == -1 || bestslbtype[
i] == -2);
5701 if( bestubtype[
i] < 0 )
5703 SCIP_Real
QUAD(val);
5704 SCIP_Real
QUAD(contsolval);
5705 SCIP_Real
QUAD(rowcoeftimesbestslb);
5721 if( bestubtype[
i] == -2 || bestslbtype[
i] == -2 )
5722 *localbdsused =
TRUE;
5754 SCIPdebugMsg(
scip,
" --> bestub used for trans: ... %s y'_%d + ..., Y'_%d <= %g x_%d (=1), rhs=%g-(%g*%g)=%g\n",
5760 SCIP_Real
QUAD(rowcoefbinary);
5761 SCIP_Real varsolvalbinary;
5762 SCIP_Real
QUAD(val);
5763 SCIP_Real
QUAD(contsolval);
5764 SCIP_Real
QUAD(rowcoeftimesvubconst);
5782 assert(binvarused[vubvarprobidx] == 1);
5789 binvarused[vubvarprobidx] = 0;
5794 SCIP_Real
QUAD(tmp);
5833 SCIPdebugMsg(
scip,
" --> bestub used for trans: ... %s y'_%d + ..., y'_%d <= %g x_%d (=%s), rhs=%g-(%g*%g)=%g\n",
5850 for(
i = nnonbinvarsrow;
i < nnz; ++
i )
5853 SCIP_Real
QUAD(rowcoef);
5856 SCIP_Real contsolval;
5857 SCIP_Real varsolval;
5859 probidx = rowinds[
i];
5864 if( binvarused[probidx] == 0 )
5868 assert(binvarused[probidx] == -1);
5871 binvarused[probidx] = 0;
5878 SCIPdebugMsg(
scip,
" %d: %g <%s, idx=%d, lp=%g, [%g, %g]>:\n",
i,
QUAD_TO_DBL(rowcoef),
SCIPvarGetName(
var), probidx, varsolval,
5935 SCIPdebugMsg(
scip,
"constraint in constructed 0-1 single node flow relaxation: ");
6016 SCIP_Real* tempsort;
6017 SCIP_Real solitemsweight;
6018 SCIP_Real mediancapacity;
6030 if( solitems !=
NULL )
6035 if( solval !=
NULL )
6042 for(
i = nitems - 1;
i >= 0; --
i )
6043 tempsort[
i] = profits[
i] / weights[
i];
6055 solitemsweight = 0.0;
6056 for( j = 0; j < nitems &&
SCIPisFeasLT(
scip, solitemsweight + weights[j], capacity); j++ )
6058 if( solitems !=
NULL )
6060 solitems[*nsolitems] = items[j];
6063 if( solval !=
NULL )
6064 (*solval) += profits[j];
6065 solitemsweight += weights[j];
6069 for( ; j < nitems; j++ )
6073 if( solitems !=
NULL )
6075 solitems[*nsolitems] = items[j];
6078 if( solval !=
NULL )
6079 (*solval) += profits[j];
6080 solitemsweight += weights[j];
6082 else if( solitems !=
NULL )
6084 nonsolitems[*nnonsolitems] = items[j];
6100 SCIP_Real* vubcoefs,
6106 int* nflowcovervars,
6107 int* nnonflowcovervars,
6108 int* flowcoverstatus,
6109 QUAD(SCIP_Real* flowcoverweight),
6114 SCIP_Real
QUAD(tmp);
6122 assert(nnonsolitems >= 0);
6123 assert(nflowcovervars !=
NULL && *nflowcovervars >= 0);
6124 assert(nnonflowcovervars !=
NULL && *nnonflowcovervars >= 0);
6130 for( j = 0; j < nsolitems; j++ )
6133 if( coefs[solitems[j]] == 1 )
6135 flowcoverstatus[solitems[j]] = -1;
6136 (*nnonflowcovervars)++;
6141 assert(coefs[solitems[j]] == -1);
6142 flowcoverstatus[solitems[j]] = 1;
6143 (*nflowcovervars)++;
6147 for( j = 0; j < nnonsolitems; j++ )
6150 if( coefs[nonsolitems[j]] == 1 )
6152 flowcoverstatus[nonsolitems[j]] = 1;
6153 (*nflowcovervars)++;
6154 SCIPquadprecSumQD(*flowcoverweight, *flowcoverweight, vubcoefs[nonsolitems[j]]);
6159 assert(coefs[nonsolitems[j]] == -1);
6160 flowcoverstatus[nonsolitems[j]] = -1;
6161 (*nnonflowcovervars)++;
6170#ifndef NO_EXACT_KNAPSACK
6188 sval = val * scalar;
6189 downval = floor(sval);
6199SCIP_Longint getIntegralVal(
6208 SCIP_Longint intval;
6213 sval = val * scalar;
6232 int* nflowcovervars,
6233 int* nnonflowcovervars,
6234 int* flowcoverstatus,
6239 SCIP_Real* transprofitsint;
6240 SCIP_Real* transprofitsreal;
6241 SCIP_Real* transweightsreal;
6242 SCIP_Longint* transweightsint;
6247 SCIP_Real
QUAD(flowcoverweight);
6248 SCIP_Real
QUAD(flowcoverweightafterfix);
6249 SCIP_Real n1itemsweight;
6250 SCIP_Real n2itemsminweight;
6252 SCIP_Real transcapacityreal;
6253#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6256 SCIP_Bool scalesuccess;
6257 SCIP_Bool transweightsrealintegral;
6258 SCIP_Longint transcapacityint;
6259 int nflowcovervarsafterfix;
6262 int nnonflowcovervarsafterfix;
6278 SCIPdebugMsg(
scip,
"--------------------- get flow cover ----------------------------------------------------\n");
6292 *nflowcovervars = 0;
6293 *nnonflowcovervars = 0;
6296 nflowcovervarsafterfix = 0;
6297 nnonflowcovervarsafterfix = 0;
6299#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6313 n1itemsweight = 0.0;
6324 flowcoverstatus[j] = -1;
6325 (*nnonflowcovervars)++;
6345 flowcoverstatus[j] = -1;
6346 (*nnonflowcovervars)++;
6352 flowcoverstatus[j] = 1;
6353 (*nflowcovervars)++;
6360 flowcoverstatus[j] = 1;
6361 (*nflowcovervars)++;
6369 flowcoverstatus[j] = -1;
6370 (*nnonflowcovervars)++;
6374 assert((*nflowcovervars) + (*nnonflowcovervars) + nitems == snf->
ntransvars);
6408 transweightsrealintegral =
TRUE;
6409 for( j = 0; j < nitems; j++ )
6414 transweightsrealintegral =
FALSE;
6419 SCIPdebugMsg(
scip,
" <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6420 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6425 SCIPdebugMsg(
scip,
" <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6426 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6431 SCIPdebugMsg(
scip,
" transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6460 if( transweightsrealintegral )
6464 scalesuccess =
TRUE;
6468 scalesuccess =
FALSE;
6484 for( j = 0; j < nitems; ++j )
6486 transweightsint[j] = getIntegralVal(transweightsreal[j], scalar, -
MINDELTA,
MAXDELTA);
6487 transprofitsint[j] = transprofitsreal[j];
6488 itemsint[j] = items[j];
6492 transcapacityint = getIntegralVal(transcapacityreal, scalar, -
MINDELTA,
MAXDELTA);
6493 transcapacityint -= 1;
6496 transcapacityint = (
SCIP_Longint) (transcapacityreal * scalar);
6497 nflowcovervarsafterfix = *nflowcovervars;
6498 nnonflowcovervarsafterfix = *nnonflowcovervars;
6502 tmp2 = (
SCIP_Real) ((transcapacityint) + 1);
6503 if( transcapacityint * nitems <= MAXDYNPROGSPACE && tmp1 * tmp2 <= INT_MAX / 8.0)
6509 itemsint, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL, &success));
6515 transcapacityreal, items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6517#if !defined(NDEBUG) || defined(SCIP_DEBUG)
6526 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6534 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6539 assert(nnonsolitems != -1);
6542 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6544 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6554 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6560 *nflowcovervars = nflowcovervarsafterfix;
6561 *nnonflowcovervars = nnonflowcovervarsafterfix;
6564 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6566 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6576 SCIPdebugMsg(
scip,
"2. %s solution:\n", kpexact ?
"exact" :
"approximate");
6583 else if( snf->
transvarcoefs[j] == -1 && flowcoverstatus[j] == 1 )
6616 int* nflowcovervars,
6617 int* nnonflowcovervars,
6618 int* flowcoverstatus,
6623 SCIP_Real* transprofitsreal;
6624 SCIP_Real* transweightsreal;
6625 SCIP_Longint* transweightsint;
6630 SCIP_Real
QUAD(flowcoverweight);
6631 SCIP_Real n1itemsweight;
6632 SCIP_Real n2itemsminweight;
6633 SCIP_Real transcapacityreal;
6653 SCIPdebugMsg(
scip,
"--------------------- get flow cover ----------------------------------------------------\n");
6666 *nflowcovervars = 0;
6667 *nnonflowcovervars = 0;
6680 n1itemsweight = 0.0;
6691 flowcoverstatus[j] = -1;
6692 (*nnonflowcovervars)++;
6714 flowcoverstatus[j] = -1;
6715 (*nnonflowcovervars)++;
6721 flowcoverstatus[j] = 1;
6722 (*nflowcovervars)++;
6729 flowcoverstatus[j] = 1;
6730 (*nflowcovervars)++;
6738 flowcoverstatus[j] = -1;
6739 (*nnonflowcovervars)++;
6743 assert((*nflowcovervars) + (*nnonflowcovervars) + nitems == snf->
ntransvars);
6777 for( j = 0; j < nitems; j++ )
6784 SCIPdebugMsg(
scip,
" <%d>: j in N1: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6785 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6790 SCIPdebugMsg(
scip,
" <%d>: j in N2: w_%d = %g, p_%d = %g %s\n", items[j], items[j], transweightsreal[j],
6791 items[j], transprofitsreal[j],
SCIPisIntegral(
scip, transweightsreal[j]) ?
"" :
" ----> NOT integral");
6796 SCIPdebugMsg(
scip,
" transcapacity = -rhs(%g) + flowcoverweight(%g) + n1itemsweight(%g) = %g\n",
6828 items, solitems, nonsolitems, &nsolitems, &nnonsolitems,
NULL));
6831 assert(nnonsolitems != -1);
6834 assert(*nflowcovervars + *nnonflowcovervars + nsolitems + nnonsolitems == snf->
ntransvars);
6836 nnonflowcovervars, flowcoverstatus,
QUAD(&flowcoverweight), lambda);
6853 else if( snf->
transvarcoefs[j] == -1 && flowcoverstatus[j] == 1 )
6886 SCIP_Real
QUAD(tmp);
6887 SCIP_Real xpluslambda;
6892 xpluslambda =
x + liftingdata->
lambda;
6903 return i * liftingdata->
lambda;
6934 return i * liftingdata->
lambda;
6938 MAX(0.0, liftingdata->
m[
i] - (liftingdata->
mp - liftingdata->
lambda) - liftingdata->
ml)));
6972 SCIP_Real vubcoefpluslambda;
6975 vubcoefpluslambda = vubcoef + liftingdata->
lambda;
6983 SCIP_Real
QUAD(tmp);
6984 assert(liftingdata->
M[
i] < vubcoefpluslambda);
7004 int* transvarflowcoverstatus,
7011 SCIP_Real
QUAD(tmp);
7012 SCIP_Real
QUAD(sumN2mC2LE);
7013 SCIP_Real
QUAD(sumN2mC2GT);
7014 SCIP_Real
QUAD(sumC1LE);
7015 SCIP_Real
QUAD(sumC2);
7019 liftingdata->
m =
NULL;
7020 liftingdata->
M =
NULL;
7040 int s = (snf->
transvarcoefs[
i] + 1) + (transvarflowcoverstatus[
i] + 1)/2;
7106 for(
i = 0;
i < liftingdata->
r; ++
i)
7121 while( liftingdata->
t < liftingdata->
r && liftingdata->
m[liftingdata->
t] == liftingdata->
mp )
7124 liftingdata->
lambda = lambda;
7148 int* flowcoverstatus,
7150 SCIP_Real* cutcoefs,
7157 SCIP_Real
QUAD(rhs);
7228 if( liftedbincoef != 0.0 )
7250 SCIP_Real
QUAD(binvarcoef);
7293 SCIP_Real
QUAD(tmp);
7294 SCIP_Real
QUAD(tmp2);
7333 for(
i = 0;
i < aggrrow->
nrows; ++
i )
7339 SCIP_Real slackcoef;
7342 assert(slackcoef != 0.0);
7345 if( slackcoef > 0.0 )
7363 slackub = rowrhs - rowlhs;
7428 SCIP_Bool postprocess,
7429 SCIP_Real boundswitch,
7430 SCIP_Bool allowlocal,
7432 SCIP_Real* cutcoefs,
7436 SCIP_Real* cutefficacy,
7438 SCIP_Bool* cutislocal,
7444 SCIP_Bool localbdsused;
7447 SCIP_Real* tmpcoefs;
7448 int *transvarflowcoverstatus;
7450 int nnonflowcovervars;
7462 SCIP_CALL(
constructSNFRelaxation(
scip,
sol, boundswitch, allowlocal, aggrrow->
vals,
QUAD(aggrrow->rhs), aggrrow->
inds, aggrrow->
nnz, &snf, success, &localbdsused) );
7469 *cutislocal = aggrrow->
local || localbdsused;
7494 SCIP_Real
QUAD(rhs);
7504 for(
i = 0;
i < *cutnnz; ++
i )
7507 assert(tmpcoefs[j] != 0.0);
7508 cutcoefs[
i] = tmpcoefs[j];
7512 if( cutefficacy !=
NULL )
7515 if( cutrank !=
NULL )
7516 *cutrank = aggrrow->
rank + 1;
7521 for(
i = 0;
i < *cutnnz; ++
i )
7524 assert(tmpcoefs[j] != 0.0);
7552 SCIP_Bool allowlocal,
7553 SCIP_Real* cutcoefs,
7554 QUAD(SCIP_Real* cutrhs),
7560 SCIP_Bool* localbdsused,
7568 int aggrrowbinstart;
7595 SCIP_Real
QUAD(coef);
7602 SCIP_Real simplebound;
7616 SCIP_Real simplebound;
7631 aggrrowbinstart =
i;
7634 for(
i = 0;
i < aggrrowbinstart; ++
i )
7636 SCIP_Real
QUAD(coef);
7649 if( aggrrowbinstart != 0 )
7651 *nnz -= aggrrowbinstart;
7662 SCIP_Real
QUAD(coef);
7663 SCIP_Real simplebound;
7671 assert(v < firstnonbinvar);
7691 *localbdsused = *localbdsused || (boundtype[
i] == -2);
7719 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
7728 cutinds[
i] = cutinds[*nnz];
7751 SCIP_Real* cutcoefs,
7758 SCIP_Real* covervals,
7761 QUAD(SCIP_Real* coverweight)
7773 for( k = 0; k < cutnnz; ++k )
7777 SCIP_Real
QUAD(coef);
7781 if( varsign[k] == -1 )
7782 solval = 1 - solval;
7787 coverpos[*coversize] = k;
7808 SCIPsortDownRealInt(covervals + (*coversize), coverpos + (*coversize), cutnnz - (*coversize));
7813 while( *coversize < cutnnz &&
7817 SCIP_Real
QUAD(coef);
7818 k = coverpos[*coversize];
7841 SCIP_Real* cutcoefs,
7843 QUAD(SCIP_Real cutrhs),
7846 QUAD(SCIP_Real coverweight),
7847 SCIP_Real* covervals,
7852 QUAD(SCIP_Real* abar),
7857 SCIP_Real
QUAD(tmp);
7858 SCIP_Real
QUAD(sigma);
7873 for( k = 1; k < coversize; ++k )
7875 SCIP_Real
QUAD(lkplus1);
7876 SCIP_Real
QUAD(kdelta);
7896 SCIP_Real minusoneoverk = -1.0 / k;
7906 SCIP_Real oneoverc = 1.0 / coversize;
7919 for( k = 0; k < coversize; ++k )
7921 SCIP_Real
QUAD(coef);
7922 SCIP_Real
QUAD(coefminusabar);
7937 coverstatus[coverpos[k]] = -1;
7942 coverstatus[coverpos[k]] = -1;
7958 QUAD(SCIP_Real abar),
7959 SCIP_Real* covervals,
7965 SCIP_Real
QUAD(tmp);
7966 SCIP_Real
QUAD(hfrac);
7987 if( hreal > (SCIP_Real)coversize )
8019 while(
h < coversize )
8034 covervals[
h], cutcoef);
8058 SCIP_Bool allowlocal,
8060 SCIP_Real* cutcoefs,
8064 SCIP_Real* cutefficacy,
8066 SCIP_Bool* cutislocal,
8075 SCIP_Real* tmpcoefs;
8076 SCIP_Real* covervals;
8077 SCIP_Real
QUAD(rhs);
8078 SCIP_Real
QUAD(coverweight);
8079 SCIP_Real
QUAD(abar);
8080 SCIP_Bool transformed;
8102 if( aggrrow->
nnz == 0 )
8105 for( k = 0; k < aggrrow->
nrows; ++k )
8128 for( k = 0; k < nnz; ++k )
8130 SCIP_Real
QUAD(coef);
8147 local = aggrrow->
local;
8149 tmpcoefs,
QUAD(&rhs), tmpinds, &nnz, varsign, boundtype, &local, &transformed) );
8151 assert(allowlocal || !local);
8160 coverpos, covervals, &coversize,
QUAD(&coverweight)) )
8169 if( coversize == 1 )
8171 SCIP_Real
QUAD(tmp);
8174 for( k = 0; k < nnz; ++k )
8176 if( coverstatus[k] == 0 )
8182 tmpinds[0] = tmpinds[k];
8183 varsign[0] = varsign[k];
8188 if( varsign[0] == -1 )
8203 SCIP_Real
QUAD(tmp);
8218 QUAD(coverweight), covervals, coverstatus,
QUAD(&abar), &cplussize);
8222 for( k = 0; k < nnz; )
8225 if( coverstatus[k] == -1 )
8231 SCIP_Real
QUAD(coef);
8233 SCIPdebugMsg(
scip,
"load QUAD(coef) from tmpcoefs[tmpinds[k] = %d]\n",tmpinds[k]);
8242 if( cutcoef == 0.0 )
8247 coverstatus[k] = coverstatus[nnz];
8248 tmpinds[k] = tmpinds[nnz];
8249 varsign[k] = varsign[nnz];
8255 if( varsign[k] == -1 )
8274 *success = efficacy > *cutefficacy;
8282 *cutislocal = local;
8287 for( k = 0; k < nnz; ++k )
8289 SCIP_Real
QUAD(coef);
8306 if( cutrank !=
NULL )
8307 *cutrank = aggrrow->
rank + 1;
8315 SCIP_Real
QUAD(tmp);
8318 for( k = 0; k < nnz; ++k )
8326 if(tmpcoefs[k] != 0.0)
8385 SCIP_Real boundswitch,
8387 SCIP_Bool allowlocal,
8388 SCIP_Real* cutcoefs,
8389 QUAD(SCIP_Real* cutrhs),
8395 SCIP_Bool* freevariable,
8396 SCIP_Bool* localbdsused
8401 int aggrrowintstart;
8411 *freevariable =
FALSE;
8412 *localbdsused =
FALSE;
8430 SCIP_Real
QUAD(coef);
8437 SCIP_Real simplebound;
8445 *freevariable =
TRUE;
8453 SCIP_Real simplebound;
8461 *freevariable =
TRUE;
8470 aggrrowintstart =
i;
8473 for(
i = 0;
i < aggrrowintstart; ++
i )
8485 SCIP_Real
QUAD(coef);
8493 assert(v < firstcontvar);
8502 cutinds[
i] = cutinds[*nnz];
8509 SCIP_CALL(
determineBestBounds(
scip,
vars[v],
sol, boundswitch, 0, allowlocal,
FALSE,
FALSE,
NULL,
NULL,
8510 &bestlb, &bestub, &bestlbtype, &bestubtype, &selectedbound, freevariable) );
8521 boundtype[
i] = bestlbtype;
8529 boundtype[
i] = bestubtype;
8535 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
8608 SCIP_Real* cutcoefs,
8609 QUAD(SCIP_Real* cutrhs),
8618 SCIP_Real
QUAD(onedivoneminusf0);
8622 int aggrrowintstart;
8645 while(
i < *nnz && cutinds[
i] >= firstcontvar )
8652 assert(cutinds[
i] < firstcontvar);
8659 for(
i = *nnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
8663 SCIP_Real
QUAD(downaj);
8664 SCIP_Real
QUAD(cutaj);
8666 SCIP_Real
QUAD(tmp);
8676 assert(boundtype[
i] == -1 || boundtype[
i] == -2);
8677 assert(varsign[
i] == +1 || varsign[
i] == -1);
8710 cutinds[
i] = cutinds[*nnz];
8720 if( varsign[
i] == +1 )
8723 if( boundtype[
i] == -1 )
8732 if( boundtype[
i] == -1 )
8743 aggrrowintstart =
i + 1;
8747 for(
i = 0;
i < aggrrowintstart; ++
i )
8760 assert(varsign[
i] == +1 || varsign[
i] == -1);
8771 if( aggrrowintstart > 0 )
8773 SCIP_Real
QUAD(tmp);
8774 assert(aggrrowintstart <= *nnz);
8778 for(
i = 0;
i < aggrrowintstart; ++
i )
8785 *nnz -= aggrrowintstart;
8786 if( *nnz < aggrrowintstart )
8824 SCIP_Real* cutcoefs,
8825 QUAD(SCIP_Real* cutrhs),
8833 SCIP_Real
QUAD(onedivoneminusf0);
8851 for(
i = 0;
i < nrowinds;
i++ )
8855 SCIP_Real
QUAD(downar);
8856 SCIP_Real
QUAD(cutar);
8863 assert(slacksign[
i] == -1 || slacksign[
i] == +1);
8920 if( slacksign[
i] == +1 )
8977 SCIP_Bool postprocess,
8978 SCIP_Real boundswitch,
8980 SCIP_Bool allowlocal,
8985 SCIP_Real* cutcoefs,
8989 SCIP_Real* cutefficacy,
8991 SCIP_Bool* cutislocal,
8999 SCIP_Real* tmpcoefs;
9000 SCIP_Real
QUAD(downrhs);
9002 SCIP_Real
QUAD(tmp);
9003 SCIP_Real
QUAD(rhs);
9006 SCIP_Bool freevariable;
9007 SCIP_Bool localbdsused;
9026 for(
i = 0;
i < aggrrow->
nrows; ++
i )
9038 *cutnnz = aggrrow->
nnz;
9039 *cutislocal = aggrrow->
local;
9048 for(
i = 0;
i < *cutnnz; ++
i )
9050 SCIP_Real
QUAD(coef);
9078 tmpcoefs,
QUAD(&rhs), cutinds, cutnnz, varsign, boundtype, &freevariable, &localbdsused) );
9080 assert(allowlocal || !localbdsused);
9081 *cutislocal = *cutislocal || localbdsused;
9089 for(
i = *cutnnz - 1;
i >= 0 && cutinds[
i] < firstcontvar; --
i )
9091 SCIP_Real
QUAD(coef);
9175 aggrrow->
nrows, scale, tmpcoefs,
QUAD(&rhs), cutinds, cutnnz,
QUAD(f0), k) );
9196 for(
i = 0;
i < *cutnnz; ++
i )
9198 SCIP_Real
QUAD(coef);
9209 if( cutefficacy !=
NULL )
9212 if( cutrank !=
NULL )
9213 *cutrank = aggrrow->
rank + 1;
9223 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 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