56#define NLHDLR_NAME "soc"
57#define NLHDLR_DESC "nonlinear handler for second-order cone structures"
58#define NLHDLR_DETECTPRIORITY 100
59#define NLHDLR_ENFOPRIORITY 100
60#define DEFAULT_MINCUTEFFICACY 1e-5
61#define DEFAULT_COMPEIGENVALUES TRUE
108struct SCIP_NlhdlrExprData
112 SCIP_Real* transcoefs;
124 SCIP_Real* disvarvals;
127struct SCIP_NlhdlrData
129 SCIP_Real mincutefficacy;
130 SCIP_Bool compeigenvalues;
140void printNlhdlrExprData(
149 nterms = nlhdlrexprdata->nterms;
157 startidx = nlhdlrexprdata->termbegins[
i];
160 if( startidx == nlhdlrexprdata->termbegins[
i + 1] )
162 assert(nlhdlrexprdata->offsets[
i] != 0.0);
171 for( j = startidx; j < nlhdlrexprdata->termbegins[
i + 1]; ++j )
173 if( nlhdlrexprdata->transcoefs[j] != 1.0 )
185 if( nlhdlrexprdata->offsets[
i] != 0.0 )
196 for( j = nlhdlrexprdata->termbegins[
nterms-1]; j < nlhdlrexprdata->termbegins[
nterms]; ++j )
198 if( nlhdlrexprdata->transcoefs[j] != 1.0 )
207 if( nlhdlrexprdata->offsets[
nterms-1] != 0.0 )
228 ndisvars = nlhdlrexprdata->nterms - 1;
235 for(
i = 0;
i < ndisvars; ++
i )
261 if( nlhdlrexprdata->disvars ==
NULL )
264 ndisvars = nlhdlrexprdata->nterms - 1;
267 for(
i = 0;
i < ndisvars; ++
i )
300 nterms = nlhdlrexprdata->nterms;
301 beta = nlhdlrexprdata->offsets[
nterms - 1];
311 for(
i = 0;
i < ndisvars; ++
i )
317 for(
i = nlhdlrexprdata->termbegins[
nterms - 1];
i < nlhdlrexprdata->termbegins[
nterms]; ++
i )
325 coef = -nlhdlrexprdata->transcoefs[
i];
339 SCIP_Real* transcoefs,
356 ntranscoefs = termbegins[
nterms];
364 (*nlhdlrexprdata)->nvars =
nvars;
365 (*nlhdlrexprdata)->nterms =
nterms;
367 (*nlhdlrexprdata)->disrow =
NULL;
368 (*nlhdlrexprdata)->disvars =
NULL;
370 (*nlhdlrexprdata)->varvals =
NULL;
371 (*nlhdlrexprdata)->disvarvals =
NULL;
374 SCIPdebugMsg(
scip,
"created nlhdlr data for the following soc expression:\n");
375 printNlhdlrExprData(
scip, *nlhdlrexprdata);
397 ntranscoefs = (*nlhdlrexprdata)->termbegins[(*nlhdlrexprdata)->nterms];
416 SCIP_Bool roundtinyfrac
425 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
429 nlhdlrexprdata->varvals[
i] =
SCIPround(
scip, nlhdlrexprdata->varvals[
i]);
433 if( nlhdlrexprdata->disvarvals !=
NULL )
434 for(
i = 0;
i < nlhdlrexprdata->nterms - 1; ++
i )
438 nlhdlrexprdata->disvarvals[
i] =
SCIPround(
scip, nlhdlrexprdata->disvarvals[
i]);
457 result = nlhdlrexprdata->offsets[k];
459 for(
i = nlhdlrexprdata->termbegins[k];
i < nlhdlrexprdata->termbegins[k + 1]; ++
i )
460 result += nlhdlrexprdata->transcoefs[
i] * nlhdlrexprdata->varvals[nlhdlrexprdata->transcoefsidx[
i]];
500 SCIP_Real mincutviolation,
504 SCIP_Real* transcoefs;
507 SCIP_Real valterms[2] = {0.0, 0.0};
511 SCIP_Bool offsetzero;
523 vars = nlhdlrexprdata->vars;
524 transcoefs = nlhdlrexprdata->transcoefs;
525 transcoefsidx = nlhdlrexprdata->transcoefsidx;
526 termbegins = nlhdlrexprdata->termbegins;
527 nterms = nlhdlrexprdata->nterms;
537 fvalue +=
SQR( valterms[
i] );
538 if( nlhdlrexprdata->offsets[
i] != 0.0 )
541 fvalue = sqrt(fvalue);
546 if( fvalue - rhsval <= mincutviolation )
548 SCIPdebugMsg(
scip,
"do not generate cut: rhsval %g, fvalue %g violation is %g\n", rhsval, fvalue, fvalue - rhsval);
555 SCIPdebugMsg(
scip,
"do not generate cut for lhs=%g, cannot linearize at top of cone\n", fvalue);
568 cutrhs = nlhdlrexprdata->offsets[
nterms - 1];
573 for( j = 0; j <
nterms - 1; ++j )
575 for(
i = termbegins[j];
i < termbegins[j + 1]; ++
i )
580 cutcoef = transcoefs[
i] * valterms[j] / fvalue;
585 cutrhs += cutcoef * nlhdlrexprdata->varvals[transcoefsidx[
i]];
634 SCIP_Real mincutviolation,
640 SCIP_Real* transcoefs;
649 SCIP_Real denominator;
650 SCIP_Bool offsetzero;
661 vars = nlhdlrexprdata->vars;
662 disvars = nlhdlrexprdata->disvars;
663 transcoefs = nlhdlrexprdata->transcoefs;
664 transcoefsidx = nlhdlrexprdata->transcoefsidx;
665 termbegins = nlhdlrexprdata->termbegins;
666 nterms = nlhdlrexprdata->nterms;
672 disvarval = nlhdlrexprdata->disvarvals[disaggidx];
676 denominator = sqrt(4.0 *
SQR(lhsval) +
SQR(rhsval - disvarval));
679 fvalue = denominator - rhsval - disvarval;
682 if( fvalue <= mincutviolation )
684 SCIPdebugMsg(
scip,
"skip cut on disaggregation index %d as violation=%g below minviolation %g\n", disaggidx,
685 fvalue, mincutviolation);
692 SCIPdebugMsg(
scip,
"skip cut on disaggregation index %d as we are on top of cone (denom=%g)\n", disaggidx, denominator);
697 ncutvars = (termbegins[
nterms] - termbegins[
nterms-1]) + (termbegins[disaggidx + 1] - termbegins[disaggidx]) + 1;
704 offsetzero = nlhdlrexprdata->offsets[disaggidx] == 0.0 && nlhdlrexprdata->offsets[
nterms-1] == 0.0;
712 for(
i = termbegins[disaggidx];
i < termbegins[disaggidx + 1]; ++
i )
718 cutcoef = 4.0 * lhsval * transcoefs[
i] / denominator;
723 constant += cutcoef * nlhdlrexprdata->varvals[transcoefsidx[
i]];
733 cutcoef = (rhsval - disvarval) * transcoefs[
i] / denominator - transcoefs[
i];
738 constant += cutcoef * nlhdlrexprdata->varvals[transcoefsidx[
i]];
742 cutcoef = (disvarval - rhsval) / denominator - 1.0;
743 cutvar = disvars[disaggidx];
749 constant += cutcoef * nlhdlrexprdata->disvarvals[disaggidx];
769 SCIP_Bool allowweakcuts,
774 SCIP_Real cutefficacy;
801 SCIPdebugMsg(
scip,
"generated row for SOC, efficacy=%g, minefficacy=%g, allowweakcuts=%u\n",
802 cutefficacy, nlhdlrdata->mincutefficacy, allowweakcuts);
807 SCIP_Bool infeasible;
811#ifdef SCIP_CONSNONLINEAR_ROWNOTREMOVABLE
813 if( addbranchscores )
901 for(
i = nchildren - 1;
i >= 0; --
i )
920 assert(*nexprs < 2 * nchildren);
921 occurringexprs[*nexprs] = childarg;
933 assert(*nexprs < 2 * nchildren);
934 occurringexprs[*nexprs] = child;
955 assert(*nexprs < 2 * nchildren);
956 occurringexprs[*nexprs] = childarg1;
966 assert(*nexprs < 2 * nchildren);
967 occurringexprs[*nexprs] = childarg2;
995 SCIP_Real* quadmatrix,
1000 SCIP_Real* childcoefs;
1015 for(
i = 0;
i < nchildren; ++
i )
1025 assert(0 <= varpos && varpos < nexprs);
1027 quadmatrix[varpos * nexprs + varpos] = childcoefs[
i];
1034 assert(0 <= varpos && varpos < nexprs);
1036 quadmatrix[varpos * nexprs + varpos] = childcoefs[
i];
1047 assert(0 <= varpos && varpos < nexprs);
1050 assert(0 <= varpos2 && varpos2 < nexprs);
1051 assert(varpos != varpos2);
1054 quadmatrix[
MIN(varpos, varpos2) * nexprs +
MAX(varpos, varpos2)] = childcoefs[
i] / 2.0;
1059 assert(0 <= varpos && varpos < nexprs);
1061 linvector[varpos] = childcoefs[
i];
1074 SCIP_Real* eigvecmatrix,
1079 SCIP_Real* transcoefs,
1082 SCIP_Real* lhsconstant,
1087 SCIP_Real sqrteigval;
1089 int nexttranscoef = 0;
1112 specialtermidx = -1;
1118 if( eigvals[
i] < 0.0 )
1120 assert(specialtermidx == -1);
1124 *lhsconstant -= bp[
i] * bp[
i] / (4.0 * eigvals[
i]);
1130 sqrteigval = sqrt(eigvals[
i]);
1132 termbegins[nextterm] = nexttranscoef;
1133 offsets[nextterm] = bp[
i] / (2.0 * sqrteigval);
1134 *lhsconstant -= bp[
i] * bp[
i] / (4.0 * eigvals[
i]);
1137 for( j = 0; j <
nvars; ++j )
1141 transcoefs[nexttranscoef] = sqrteigval * eigvecmatrix[
i *
nvars + j];
1142 transcoefsidx[nexttranscoef] = j;
1149 assert(specialtermidx > -1);
1156 if( *lhsconstant < 0.0 )
1160 if( *lhsconstant > 0.0 )
1162 termbegins[nextterm] = nexttranscoef;
1163 offsets[nextterm] = sqrt(*lhsconstant);
1169 SCIP_Real rhstermlb;
1170 SCIP_Real rhstermub;
1171 SCIP_Real signfactor;
1173 assert(-eigvals[specialtermidx] > 0.0);
1174 sqrteigval = sqrt(-eigvals[specialtermidx]);
1176 termbegins[nextterm] = nexttranscoef;
1177 offsets[nextterm] = -bp[specialtermidx] / (2.0 * sqrteigval);
1182 rhstermlb = offsets[nextterm];
1183 for( j = 0; j <
nvars; ++j )
1194 if( eigvecmatrix[specialtermidx *
nvars + j] > 0.0 )
1211 rhstermlb += sqrteigval * eigvecmatrix[specialtermidx *
nvars + j] * aux;
1214 rhstermub = offsets[nextterm];
1215 for( j = 0; j <
nvars; ++j )
1226 if( eigvecmatrix[specialtermidx *
nvars + j] > 0.0 )
1243 rhstermub += sqrteigval * eigvecmatrix[specialtermidx *
nvars + j] * aux;
1250 if( rhstermub < rhstermlb )
1260 signfactor =
SCIPisLE(
scip, rhstermub, 0.0) ? -1.0 : 1.0;
1262 offsets[nextterm] *= signfactor;
1265 for( j = 0; j <
nvars; ++j )
1270 transcoefs[nexttranscoef] = signfactor * sqrteigval * eigvecmatrix[specialtermidx *
nvars + j];
1271 transcoefsidx[nexttranscoef] = j;
1277 assert(nexttranscoef > termbegins[nextterm]);
1286 termbegins[nextterm] = nexttranscoef;
1310 SCIP_Real* childcoefs;
1312 SCIP_Real* transcoefs;
1373 for(
i = 0;
i < nchildren; ++
i )
1385 if( childcoefs[
i] < 0.0 )
1390 transcoefs[
nterms] = sqrt(childcoefs[
i]);
1403 if( childcoefs[
i] < 0.0 )
1408 transcoefs[
nterms] = sqrt(childcoefs[
i]);
1436 for(
i = 0;
i < nchildren; ++
i )
1445 constant -=
SQR(0.5 * childcoefs[
i] / transcoefs[auxvarpos]);
1467 if( constant > 0.0 )
1479 transcoefsidx[
i] =
i;
1486 if( constant > 0.0 )
1490 offsets[
nterms - 2] = sqrt(constant);
1494 offsets[
nterms - 1] = 0.0;
1496 transcoefs[
nterms - 2] = 1.0;
1505 offsets[
nterms - 1] = 0.0;
1507 transcoefs[
nterms - 1] = 1.0;
1515 for(
i = 0;
i < nchildren; ++
i )
1526 vars[nextentry] = squarearg;
1533 vars[nextentry] = children[
i];
1545 offsets[auxvarpos] = 0.5 * childcoefs[
i] / transcoefs[auxvarpos];
1551 SCIPdebugMsg(
scip,
"found SOC structure for expression %p\n", (
void*)expr);
1588 SCIP_Bool* enforcebelow,
1594 SCIP_Real* childcoefs;
1595 SCIP_Real* offsets =
NULL;
1596 SCIP_Real* transcoefs =
NULL;
1597 int* transcoefsidx =
NULL;
1598 int* termbegins =
NULL;
1600 SCIP_Real lhsconstant;
1619 SCIP_Bool ishyperbolic;
1647 for(
i = 0;
i < nchildren; ++
i )
1651 if( childcoefs[
i] > 0.0 )
1664 if( childcoefs[
i] > 0.0 )
1677 if( childcoefs[
i] > 0.0 )
1694 if( nposquadterms > 1 && nnegquadterms > 1 )
1698 if( nposbilinterms + nnegbilinterms > 1 )
1702 if( nposbilinterms > 0 && nposquadterms > 0 )
1706 if( nnegbilinterms > 0 && nnegquadterms > 0 )
1710 if( nposquadterms == nchildren || nnegquadterms == nchildren )
1713 assert(nposquadterms <= 1 || nnegquadterms <= 1);
1714 assert(nposbilinterms + nnegbilinterms <= 1);
1715 assert(nposbilinterms == 0 || nposquadterms == 0);
1716 assert(nnegbilinterms == 0 || nnegquadterms == 0);
1719 ishyperbolic = (nposbilinterms + nnegbilinterms > 0);
1736 if( (ishyperbolic && nnegbilinterms > 0) || (!ishyperbolic && nnegquadterms < 2) )
1742 assert(nnegbilinterms == 1 || nnegquadterms == 1);
1752 specialtermidx = rhsidx;
1753 lhsconstant = constant - rhs;
1754 *enforcebelow =
TRUE;
1764 specialtermidx = lhsidx;
1765 lhsconstant = lhs - constant;
1768 for(
i = 0;
i < nchildren; ++
i )
1769 childcoefs[
i] = -childcoefs[
i];
1770 *enforcebelow =
FALSE;
1772 assert(childcoefs[specialtermidx] != 0.0);
1798 lhsconstant *= 4.0 / -childcoefs[specialtermidx];
1813 if( rhsactivity.
inf < 0.0 )
1816 if( rhsactivity.
sup > 0.0 )
1845 ntranscoefs = ishyperbolic ? nchildren + 3 : nchildren;
1846 nvars = ishyperbolic ? nchildren + 1 : nchildren;
1850 if( lhsconstant > 0.0 )
1865 for(
i = 0;
i < nchildren; ++
i )
1868 if(
i == specialtermidx )
1874 vars[nextentry] = children[
i];
1889 termbegins[nextentry] = nnzinterms;
1890 offsets[nextentry] = 0.0;
1892 transcoefsidx[nnzinterms] = nextentry;
1896 assert(4.0 * childcoefs[
i] / -childcoefs[specialtermidx] > 0.0);
1897 transcoefs[nnzinterms] = sqrt(4.0 * childcoefs[
i] / -childcoefs[specialtermidx]);
1902 transcoefs[nnzinterms] = sqrt(childcoefs[
i]);
1911 assert(nextentry == nchildren - 1);
1914 if( lhsconstant > 0.0 )
1916 termbegins[nextentry] = nnzinterms;
1917 offsets[nextentry] = sqrt(lhsconstant);
1930 vars[
nvars - 1] = children[specialtermidx];
1940 assert(childcoefs[specialtermidx] < 0.0);
1942 termbegins[nextentry] = nnzinterms;
1943 offsets[nextentry] = 0.0;
1944 transcoefs[nnzinterms] = rhssign * sqrt(-childcoefs[specialtermidx]);
1945 transcoefsidx[nnzinterms] =
nvars - 1;
1965 termbegins[nextentry] = nnzinterms;
1966 offsets[nextentry] = 0.0;
1969 transcoefsidx[nnzinterms] =
nvars - 2;
1970 transcoefs[nnzinterms] = 1.0;
1974 transcoefsidx[nnzinterms] =
nvars - 1;
1975 transcoefs[nnzinterms] = -1.0;
1982 termbegins[nextentry] = nnzinterms;
1983 offsets[nextentry] = 0.0;
1986 transcoefsidx[nnzinterms] =
nvars - 2;
1987 transcoefs[nnzinterms] = rhssign;
1991 transcoefsidx[nnzinterms] =
nvars - 1;
1992 transcoefs[nnzinterms] = rhssign;
1999 assert(nnzinterms == ntranscoefs);
2002 termbegins[nextentry] = nnzinterms;
2005 SCIPdebugMsg(
scip,
"found SOC structure for expression %p\n %g <= ", (
void*)expr, lhs);
2056 SCIP_Bool* enforcebelow,
2064 SCIP_Real* transcoefs;
2065 SCIP_Real* eigvecmatrix;
2067 SCIP_Real* lincoefs;
2072 SCIP_Real lhsconstant;
2086 SCIP_Bool isquadratic;
2110 transcoefsidx =
NULL;
2152 SCIPdebugMsg(
scip,
"Failed to compute eigenvalues and eigenvectors for expression:\n");
2170 for( j = 0; j <
nvars; ++j )
2172 bp[
i] += lincoefs[j] * eigvecmatrix[
i *
nvars + j];
2188 else if( eigvals[
i] > 0.0 )
2195 if( npos + nneg < 2 )
2202 if( rhsissoc || lhsissoc )
2229 lhsconstant = lhs - constant;
2233 eigvals[
i] = -eigvals[
i];
2236 *enforcebelow =
FALSE;
2240 lhsconstant = constant - rhs;
2241 *enforcebelow =
TRUE;
2252 transcoefsidx, offsets, &lhsconstant, &
nterms, success) );
2271 SCIPdebugMsg(
scip,
"found SOC structure for expression %p\n%f <= ", (
void*)expr, lhs);
2331 SCIP_Bool* enforcebelow,
2350 *enforcebelow = *success;
2359 if( !(*success) && nlhdlrdata->compeigenvalues )
2419#define nlhdlrInitSoc NULL
2434#define nlhdlrExitSoc NULL
2444 SCIP_Bool enforcebelow;
2464 SCIP_CALL(
detectSOC(
scip, nlhdlrdata, expr, conslhs, consrhs, nlhdlrexprdata, &enforcebelow, &success) );
2477 *enforcing |= *participating;
2494 assert(nlhdlrexprdata->transcoefsidx !=
NULL);
2495 assert(nlhdlrexprdata->nterms > 1);
2506 for(
i = 0;
i < nlhdlrexprdata->nterms - 1; ++
i )
2511 *auxvalue +=
SQR(termval);
2514 assert(*auxvalue >= 0.0);
2517 *auxvalue = sqrt(*auxvalue);
2523 SCIP_Real* childcoefs;
2534 for(
i = 0;
i < nchildren; ++
i )
2547 *auxvalue += childcoefs[
i] *
SQR( solval );
2593 if( nlhdlrexprdata->nterms > 3 )
2598#ifdef WITH_DEBUG_SOLUTION
2599 if( SCIPdebugIsMainscip(
scip) )
2603 SCIP_Real disvarval;
2608 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
2619 nterms = nlhdlrexprdata->nterms;
2625 ndisvars = nlhdlrexprdata->nterms - 1;
2629 for(
i = 0;
i < ndisvars; ++
i )
2637 for(
i = 0;
i < ndisvars; ++
i )
2641 disvarval =
SQR(lhsval) / rhsval;
2655 printNlhdlrExprData(
scip, nlhdlrexprdata);
2659 if( nlhdlrexprdata->nterms == 2 )
2667 SCIP_Real plusminus1;
2673 for(
i = nlhdlrexprdata->termbegins[0];
i < nlhdlrexprdata->termbegins[1]; ++
i )
2674 norm +=
SQR(nlhdlrexprdata->transcoefs[
i]);
2679 for( plusminus1 = -1.0; plusminus1 <= 1.0; plusminus1 += 2.0 )
2682 for(
i = nlhdlrexprdata->termbegins[0];
i < nlhdlrexprdata->termbegins[1]; ++
i )
2683 nlhdlrexprdata->varvals[nlhdlrexprdata->transcoefsidx[
i]] = nlhdlrexprdata->transcoefs[
i] / norm * (plusminus1 - nlhdlrexprdata->offsets[0]);
2689 if( rowprep !=
NULL )
2691 SCIP_Bool success =
FALSE;
2709 else if( nlhdlrexprdata->nterms == 3 && nlhdlrexprdata->termbegins[0] != nlhdlrexprdata->termbegins[1] )
2736 static const SCIP_Real refpoints[3][2] = { {-1.0, 0.0}, {1.0, 1.0}, {1.0, -1.0} };
2737 SCIP_Real v1i, v1j = 0.0;
2738 SCIP_Real v2i, v2j = 0.0;
2745 i = nlhdlrexprdata->transcoefsidx[nlhdlrexprdata->termbegins[0]];
2746 v1i = nlhdlrexprdata->transcoefs[nlhdlrexprdata->termbegins[0]];
2749 v2zero = nlhdlrexprdata->termbegins[1] == nlhdlrexprdata->termbegins[2];
2753 if( !v2zero &&
SCIPsortedvecFindInt(nlhdlrexprdata->transcoefsidx + nlhdlrexprdata->termbegins[1],
i, nlhdlrexprdata->termbegins[2] - nlhdlrexprdata->termbegins[1], &pos) )
2755 assert(nlhdlrexprdata->transcoefsidx[nlhdlrexprdata->termbegins[1] + pos] ==
i);
2756 v2i = nlhdlrexprdata->transcoefs[nlhdlrexprdata->termbegins[1] + pos];
2760 for( k = nlhdlrexprdata->termbegins[1]; k < nlhdlrexprdata->termbegins[2]; ++k )
2764 if( nlhdlrexprdata->transcoefsidx[k] ==
i )
2769 if(
SCIPsortedvecFindInt(nlhdlrexprdata->transcoefsidx + nlhdlrexprdata->termbegins[0], nlhdlrexprdata->transcoefsidx[k], nlhdlrexprdata->termbegins[1] - nlhdlrexprdata->termbegins[0], &pos) )
2771 assert(nlhdlrexprdata->transcoefsidx[nlhdlrexprdata->termbegins[0] + pos] == nlhdlrexprdata->transcoefsidx[k]);
2772 v1j = nlhdlrexprdata->transcoefs[nlhdlrexprdata->termbegins[0] + pos];
2775 v2j = nlhdlrexprdata->transcoefs[k];
2780 j = nlhdlrexprdata->transcoefsidx[k];
2798 for( point = 0; point < (v2zero ? 2 : 3); ++point )
2800 c = refpoints[point][0] - nlhdlrexprdata->offsets[0];
2805 d = refpoints[point][1] - nlhdlrexprdata->offsets[1];
2806 nlhdlrexprdata->varvals[j] = (d - v2i/v1i*
c) / (v2j - v2i * v1j / v1i);
2807 nlhdlrexprdata->varvals[
i] = (
c - v1j * nlhdlrexprdata->varvals[j]) / v1i;
2816 nlhdlrexprdata->varvals[
i] =
c / v1i;
2828 if( rowprep !=
NULL )
2830 SCIP_Bool success =
FALSE;
2849 else if( nlhdlrexprdata->nterms == 3 )
2858 SCIP_Real plusminus1;
2864 for(
i = nlhdlrexprdata->termbegins[1];
i < nlhdlrexprdata->termbegins[2]; ++
i )
2865 norm +=
SQR(nlhdlrexprdata->transcoefs[
i]);
2870 for( plusminus1 = -1.0; plusminus1 <= 1.0; plusminus1 += 2.0 )
2873 for(
i = nlhdlrexprdata->termbegins[1];
i < nlhdlrexprdata->termbegins[2]; ++
i )
2874 nlhdlrexprdata->varvals[nlhdlrexprdata->transcoefsidx[
i]] = nlhdlrexprdata->transcoefs[
i] / norm * (plusminus1 - nlhdlrexprdata->offsets[1]);
2880 if( rowprep !=
NULL )
2882 SCIP_Bool success =
FALSE;
2914 static const SCIP_Real refpoints[3][2] = { {-0.5, 0.0}, {0.5, 1.0}, {0.5, -1.0} };
2928 for( k = 0; k < nlhdlrexprdata->nterms - 1; ++k )
2930 vkzero = nlhdlrexprdata->termbegins[k+1] == nlhdlrexprdata->termbegins[k];
2931 assert(!vkzero || nlhdlrexprdata->offsets[k] != 0.0);
2935 for(
i = nlhdlrexprdata->termbegins[k];
i < nlhdlrexprdata->termbegins[k+1]; ++
i )
2936 norm +=
SQR(nlhdlrexprdata->transcoefs[
i]);
2937 assert(vkzero || norm > 0.0);
2941 for( point = vkzero ? 1 : 0; point < 3; ++point )
2944 for(
i = nlhdlrexprdata->termbegins[k];
i < nlhdlrexprdata->termbegins[k+1]; ++
i )
2945 nlhdlrexprdata->varvals[nlhdlrexprdata->transcoefsidx[
i]] = nlhdlrexprdata->transcoefs[
i] / norm * (refpoints[point][0] - nlhdlrexprdata->offsets[k]);
2950 nlhdlrexprdata->disvarvals[k] = rhsval + refpoints[point][1];
2955 if( rowprep !=
NULL )
2957 SCIP_Bool success =
FALSE;
2988 if( nlhdlrexprdata->disrow !=
NULL )
3007 SCIP_Bool infeasible;
3010 assert(nlhdlrexprdata->nterms < 4 || nlhdlrexprdata->disrow !=
NULL);
3011 assert(nlhdlrexprdata->nterms > 1);
3015 if( branchcandonly )
3032 if( nlhdlrexprdata->nterms < 4 )
3039 if( rowprep !=
NULL )
3053 ndisaggrs = nlhdlrexprdata->nterms - 1;
3059 SCIPdebugMsg(
scip,
"added disaggregation row to LP, cutoff=%u\n", infeasible);
3077 if( rowprep !=
NULL )
3097 assert(nlhdlrexprdata->nterms < 4 || nlhdlrexprdata->disrow !=
NULL);
3098 assert(nlhdlrexprdata->nterms > 1);
3109 if( nlhdlrexprdata->nterms < 4 )
3116 if( rowprep !=
NULL )
3126 for( k = 0; k < nlhdlrexprdata->nterms - 1; ++k )
3133 if( rowprep !=
NULL )
3174 "Minimum efficacy which a cut needs in order to be added.",
3178 "Should Eigenvalue computations be done to detect complex cases in quadratic constraints?",
3210 SCIP_Bool compeigenvalues,
3215 SCIP_Real** offsets,
3216 SCIP_Real** transcoefs,
3217 int** transcoefsidx,
3228 SCIP_Bool enforcebelow;
3236 nlhdlrdata.mincutefficacy = 0.0;
3237 nlhdlrdata.compeigenvalues = compeigenvalues;
3242 SCIP_CALL(
detectSOC(
scip, &nlhdlrdata, expr, conslhs, consrhs, &nlhdlrexprdata, &enforcebelow, success) );
3249 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
3264 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
3270 *offsets = nlhdlrexprdata->offsets;
3271 *transcoefs = nlhdlrexprdata->transcoefs;
3272 *transcoefsidx = nlhdlrexprdata->transcoefsidx;
3273 *termbegins = nlhdlrexprdata->termbegins;
3274 *
nvars = nlhdlrexprdata->nvars;
3275 *
nterms = nlhdlrexprdata->nterms;
3280 if( nlhdlrexprdata !=
NULL )
3287 *transcoefsidx =
NULL;
3300 SCIP_Real** offsets,
3301 SCIP_Real** transcoefs,
3302 int** transcoefsidx,
3319 ntranscoefs = (*termbegins)[
nterms];
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIPdebugGetSolVal(scip, var, val)
#define SCIPdebugAddSolVal(scip, var, val)
#define SCIP_LONGINT_FORMAT
power and signed power expression handlers
variable expression handler
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
int SCIPgetExprNLocksNegNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
int SCIPhashmapGetNElements(SCIP_HASHMAP *hashmap)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
int SCIPhashsetGetNElements(SCIP_HASHSET *hashset)
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
SCIP_RETCODE SCIPhashsetRemove(SCIP_HASHSET *hashset, void *element)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPfreeSOCArraysNonlinear(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **offsets, SCIP_Real **transcoefs, int **transcoefsidx, int **termbegins, int nvars, int nterms)
SCIP_RETCODE SCIPisSOCNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Bool compeigenvalues, SCIP_Bool *success, SCIP_SIDETYPE *sidetype, SCIP_VAR ***vars, SCIP_Real **offsets, SCIP_Real **transcoefs, int **transcoefsidx, int **termbegins, int *nvars, int *nterms)
SCIP_RETCODE SCIPincludeNlhdlrSoc(SCIP *scip)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Bool SCIPisCutApplicable(SCIP *scip, SCIP_ROW *cut)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
SCIP_RETCODE SCIPdismantleExpr(SCIP *scip, FILE *file, SCIP_EXPR *expr)
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
SCIP_Real SCIPgetLPFeastol(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemory(scip, ptr)
BMS_BUFMEM * SCIPbuffer(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
void SCIPnlhdlrSetInitExit(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINIT((*init)),)
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr,)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetSollinearize(SCIP_NLHDLR *nlhdlr,)
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)),)
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr,)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr,)
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
void SCIPmarkRowNotRemovableLocal(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(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_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
void SCIPvarMarkRelaxationOnly(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static volatile int nterms
SCIP_Bool SCIPlapackIsAvailable(void)
SCIP_RETCODE SCIPlapackComputeEigenvalues(BMS_BUFMEM *bufmem, SCIP_Bool geteigenvectors, int N, SCIP_Real *a, SCIP_Real *w)
interface methods for lapack functions
#define BMSclearMemoryArray(ptr, num)
#define NLHDLR_DETECTPRIORITY
static SCIP_RETCODE addCutPool(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_CONS *cons)
static SCIP_RETCODE tryFillNlhdlrExprDataQuad(SCIP *scip, SCIP_EXPR **occurringexprs, SCIP_Real *eigvecmatrix, SCIP_Real *eigvals, SCIP_Real *bp, int nvars, int *termbegins, SCIP_Real *transcoefs, int *transcoefsidx, SCIP_Real *offsets, SCIP_Real *lhsconstant, int *nterms, SCIP_Bool *success)
#define NLHDLR_ENFOPRIORITY
static SCIP_RETCODE freeNlhdlrExprData(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata)
static void updateVarVals(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Bool roundtinyfrac)
static SCIP_RETCODE generateCutSolSOC(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_EXPR *expr, SCIP_CONS *cons, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Real mincutviolation, SCIP_Real rhsval)
static SCIP_RETCODE createDisaggrRow(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static SCIP_RETCODE detectSocNorm(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *success)
static SCIP_RETCODE detectSOC(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_EXPR *expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *enforcebelow, SCIP_Bool *success)
static SCIP_RETCODE checkAndCollectQuadratic(SCIP *scip, SCIP_EXPR *quadexpr, SCIP_HASHMAP *expr2idx, SCIP_EXPR **occurringexprs, int *nexprs, SCIP_Bool *success)
#define DEFAULT_MINCUTEFFICACY
#define DEFAULT_COMPEIGENVALUES
static SCIP_RETCODE createDisaggrVars(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static SCIP_RETCODE detectSocQuadraticComplex(SCIP *scip, SCIP_EXPR *expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *enforcebelow, SCIP_Bool *success)
static SCIP_RETCODE createNlhdlrExprData(SCIP *scip, SCIP_EXPR **vars, SCIP_Real *offsets, SCIP_Real *transcoefs, int *transcoefsidx, int *termbegins, int nvars, int nterms, SCIP_NLHDLREXPRDATA **nlhdlrexprdata)
static void buildQuadExprMatrix(SCIP *scip, SCIP_EXPR *quadexpr, SCIP_HASHMAP *expr2idx, int nexprs, SCIP_Real *quadmatrix, SCIP_Real *linvector)
static SCIP_RETCODE addCut(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_Bool allowweakcuts, SCIP_RESULT *result)
static SCIP_RETCODE freeDisaggrVars(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static SCIP_RETCODE generateCutSolDisagg(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_EXPR *expr, SCIP_CONS *cons, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int disaggidx, SCIP_Real mincutviolation, SCIP_Real rhsval)
static SCIP_Real evalSingleTerm(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, int k)
static SCIP_RETCODE detectSocQuadraticSimple(SCIP *scip, SCIP_EXPR *expr, SCIP_Real conslhs, SCIP_Real consrhs, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool *enforcebelow, SCIP_Bool *success)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public functions of nonlinear handlers of nonlinear constraints
enum SCIP_SideType SCIP_SIDETYPE
#define SCIP_NLHDLR_METHOD_SEPAABOVE
#define SCIP_DECL_NLHDLREVALAUX(x)
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
#define SCIP_NLHDLR_METHOD_SEPABOTH
#define SCIP_DECL_NLHDLRCOPYHDLR(x)
#define SCIP_DECL_NLHDLRINIT(x)
#define SCIP_DECL_NLHDLRSOLLINEARIZE(x)
#define SCIP_DECL_NLHDLREXIT(x)
#define SCIP_DECL_NLHDLRFREEEXPRDATA(x)
#define SCIP_DECL_NLHDLRDETECT(x)
#define SCIP_DECL_NLHDLREXITSEPA(x)
#define SCIP_DECL_NLHDLRINITSEPA(x)
#define SCIP_DECL_NLHDLRFREEHDLRDATA(x)
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
#define SCIP_DECL_NLHDLRENFO(x)
#define SCIP_NLHDLR_METHOD_SEPABELOW
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS