138#define SEPA_NAME "lagromory"
139#define SEPA_DESC "separator for Lagromory cuts for MIP relaxations"
140#define SEPA_PRIORITY -8000
142#define SEPA_MAXBOUNDDIST 1.0
143#define SEPA_USESSUBSCIP FALSE
144#define SEPA_DELAY FALSE
147#define DEFAULT_AWAY 0.01
148#define DEFAULT_DELAYEDCUTS FALSE
149#define DEFAULT_SEPARATEROWS TRUE
150#define DEFAULT_SORTCUTOFFSOL TRUE
151#define DEFAULT_SIDETYPEBASIS TRUE
152#define DEFAULT_DYNAMICCUTS TRUE
153#define DEFAULT_MAKEINTEGRAL FALSE
154#define DEFAULT_FORCECUTS FALSE
155#define DEFAULT_ALLOWLOCAL FALSE
158#define DEFAULT_MAXROUNDSROOT 1
159#define DEFAULT_MAXROUNDS 1
160#define DEFAULT_DUALDEGENERACYRATETHRESHOLD 0.5
161#define DEFAULT_VARCONSRATIOTHRESHOLD 1.0
162#define DEFAULT_MINRESTART 1
164#define DEFAULT_PERLPMAXCUTSROOT 50
165#define DEFAULT_PERLPMAXCUTS 10
166#define DEFAULT_PERROUNDLPITERLIMITFACTOR -1.0
168#define DEFAULT_ROOTLPITERLIMITFACTOR -1.0
170#define DEFAULT_TOTALLPITERLIMITFACTOR -1.0
172#define DEFAULT_PERROUNDMAXLPITERS 50000
173#define DEFAULT_PERROUNDCUTSFACTORROOT 1.0
175#define DEFAULT_PERROUNDCUTSFACTOR 0.5
177#define DEFAULT_TOTALCUTSFACTOR 50.0
178#define DEFAULT_MAXMAINITERS 4
179#define DEFAULT_MAXSUBGRADIENTITERS 6
182#define DEFAULT_MUPARAMCONST TRUE
183#define DEFAULT_MUPARAMINIT 0.01
184#define DEFAULT_MUPARAMLB 0.0
185#define DEFAULT_MUPARAMUB 2.0
186#define DEFAULT_MUBACKTRACKFACTOR 0.5
188#define DEFAULT_MUSLAB1FACTOR 10.0
190#define DEFAULT_MUSLAB2FACTOR 2.0
192#define DEFAULT_MUSLAB3FACTOR 0.5
194#define DEFAULT_DELTASLAB1UB 0.001
196#define DEFAULT_DELTASLAB2UB 0.01
198#define DEFAULT_UBPARAMPOSFACTOR 2.0
200#define DEFAULT_UBPARAMNEGFACTOR 0.5
202#define DEFAULT_MAXLAGRANGIANVALSFORAVG 2
203#define DEFAULT_MAXCONSECITERSFORMUUPDATE 10
204#define DEFAULT_PERROOTLPITERFACTOR 0.2
206#define DEFAULT_PERLPITERFACTOR 0.1
208#define DEFAULT_CUTGENFREQ 1
209#define DEFAULT_CUTADDFREQ 1
210#define DEFAULT_CUTSFILTERFACTOR 1.0
211#define DEFAULT_OPTIMALFACEPRIORITY 2
213#define DEFAULT_AGGREGATECUTS TRUE
216#define DEFAULT_PROJECTIONTYPE 2
219#define DEFAULT_STABILITYCENTERTYPE 1
221#define DEFAULT_RADIUSINIT 0.5
222#define DEFAULT_RADIUSMAX 20.0
223#define DEFAULT_RADIUSMIN 1e-6
224#define DEFAULT_CONST 2.0
225#define DEFAULT_RADIUSUPDATEWEIGHT 0.98
229#define MAKECONTINTEGRAL FALSE
230#define POSTPROCESS TRUE
231#define BOUNDSWITCH 0.9999
233#define FIXINTEGRALRHS FALSE
234#define MAXAGGRLEN(ncols) (0.1*(ncols)+1000)
259 int nrowsinhardcutslp;
260 int nrunsinsoftcutslp;
270 int nmaxcutsperlproot;
278 int perroundnmaxlpiters;
285 int nmaxsubgradientiters;
286 int nmaxperroundlpiters;
289 int nmaxtotallpiters;
291 int nmaxperroundcutsroot;
292 int nmaxperroundcuts;
316 int nmaxlagrangianvalsforavg;
317 int nmaxconsecitersformuupdate;
325 int optimalfacepriority;
333 int stabilitycentertype;
361 unsigned int nintcols;
371 nruns =
sepadata->nrunsinsoftcutslp;
381 if( nruns != runnum )
388 sepadata->nmaxrootlpiters = (int)(
sepadata->rootlpiterlimitfactor * nrootlpiters);
394 sepadata->nmaxtotallpiters = (int)(
sepadata->totallpiterlimitfactor * nrootlpiters);
400 sepadata->nmaxperroundlpiters = (int)(
sepadata->perroundlpiterlimitfactor * nrootlpiters);
405 if(
sepadata->perroundnmaxlpiters > 0 )
410 for(
i = 0;
i < ncols; ++
i )
413 sepadata->nmaxperroundcutsroot = (int)(
sepadata->perroundcutsfactorroot * nintcols);
414 sepadata->nmaxperroundcuts = (int)(
sepadata->perroundcutsfactor * nintcols);
423 sepadata->nrunsinsoftcutslp = runnum;
508 for(
i = 0;
i < ncols; ++
i )
523 for(
i = 0;
i < nrows; ++
i )
538 for(
i = 0;
i < nrows; ++
i )
541 assert(nrownonz <= ncols);
545 rowbegs[
i + 1] = rowbegs[
i] + nrownonz;
550 for( j = 0; j < nrownonz; ++j )
554 assert(collppos <= ncols);
556 rowcolinds[rowbegs[
i] + j] = collppos;
557 rowvals[rowbegs[
i] + j] = rowval[j];
582 for(
i =
sepadata->nrowsinhardcutslp - nrows;
i < ncuts; ++
i )
597 for(
i =
sepadata->nrowsinhardcutslp - nrows;
i < ncuts; ++
i )
600 assert(nrownonz <= ncols);
604 rowbegs[
i -
sepadata->nrowsinhardcutslp + nrows + 1] = rowbegs[
i -
sepadata->nrowsinhardcutslp + nrows] +
612 for( j = 0; j < nrownonz; ++j )
616 assert(collppos <= ncols);
618 rowcolinds[rowbegs[
i -
sepadata->nrowsinhardcutslp + nrows] + j] = collppos;
619 rowvals[rowbegs[
i -
sepadata->nrowsinhardcutslp + nrows] + j] = rowval[j];
625 rowbegs[(ncuts -
sepadata->nrowsinhardcutslp + nrows)], rowbegs, rowcolinds, rowvals) );
632 sepadata->nrowsinhardcutslp = nrows + ncuts;
656 if( (*sepadata)->lpiwithhardcuts !=
NULL )
661 (*sepadata)->nrowsinhardcutslp = 0;
662 (*sepadata)->nrunsinsoftcutslp = 0;
663 (*sepadata)->ncalls = 0;
664 (*sepadata)->nmaxperroundlpiters = 0;
665 (*sepadata)->nmaxrootlpiters = 0;
666 (*sepadata)->nrootlpiters = 0;
667 (*sepadata)->nmaxtotallpiters = 0;
668 (*sepadata)->ntotallpiters = 0;
669 (*sepadata)->nmaxperroundcutsroot = 0;
670 (*sepadata)->nmaxperroundcuts = 0;
671 (*sepadata)->nmaxtotalcuts = 0;
672 (*sepadata)->ntotalcuts = 0;
686 int subgradientiternum,
711 delta = ubparam - bestlagrangianval;
720 muslab1factor =
sepadata->muslab1factor;
721 muslab2factor =
sepadata->muslab2factor;
722 muslab3factor =
sepadata->muslab3factor;
728 muslab1factor =
sepadata->muslab1factor;
729 muslab2factor =
sepadata->muslab3factor;
730 muslab3factor =
sepadata->muslab2factor;
734 muslab1factor =
sepadata->muslab3factor;
735 muslab2factor =
sepadata->muslab1factor;
736 muslab3factor =
sepadata->muslab2factor;
744 muslab1factor =
sepadata->muslab2factor;
745 muslab2factor =
sepadata->muslab1factor;
746 muslab3factor =
sepadata->muslab3factor;
752 muslab1factor =
sepadata->muslab2factor;
753 muslab2factor =
sepadata->muslab3factor;
754 muslab3factor =
sepadata->muslab1factor;
758 muslab1factor =
sepadata->muslab3factor;
759 muslab2factor =
sepadata->muslab2factor;
760 muslab3factor =
sepadata->muslab1factor;
769 if( subgradientiternum >= maxiters )
771 for(
i = subgradientiternum - maxiters;
i < subgradientiternum;
i++ )
773 if(
SCIPisGE(
scip, lagrangianvals[
i], bestlagrangianval - delta) )
777 if(
i == subgradientiternum )
779 *muparam *=
sepadata->mubacktrackfactor;
785 if( (subgradientiternum < maxiters) || (
i >= 0 &&
i < subgradientiternum) )
787 if( bestlagrangianval - avglagrangianval < deltaslab1ub * delta )
788 *muparam *= muslab1factor;
789 else if( bestlagrangianval - avglagrangianval < deltaslab2ub * delta )
790 *muparam *= muslab2factor;
792 *muparam *= muslab3factor;
817 int* nnzsubgradientdualprod,
823 int nzerosubgradient;
835 *nnzsubgradientdualprod = 0;
836 *maxnzsubgradientdualprod = 0.0;
837 nzerosubgradient = 0;
838 *subgradientzero =
FALSE;
841 for(
i = 0;
i < ncuts;
i++ )
849 subgradient[
i] = 0.0;
858 *maxcutviol =
MAX(*maxcutviol, subgradient[
i]);
864 (*nnzsubgradientdualprod)++;
865 term =
REALABS(subgradient[
i] * dualvector[
i]);
866 *maxnzsubgradientdualprod =
MAX(*maxnzsubgradientdualprod, term);
872 if( nzerosubgradient == ncuts )
873 *subgradientzero =
TRUE;
893 for(
i = 0;
i < ncuts;
i++ )
916 for(
i = 0;
i < ncuts;
i++ )
917 normsquared +=
SQR(subgradient[
i]);
920 *steplength = (muparam * (ubparam - lagrangianval))/(normsquared);
949 if( maxviolscoreimproved && nviolscoreimproved )
952 if(
sepadata->optimalfacepriority <= 1 )
955 *ballradius =
MIN(*ballradius,
sepadata->radiusmax);
960 *ballradius =
MIN(*ballradius,
sepadata->radiusmax/2.0);
963 else if( !maxviolscoreimproved && !nviolscoreimproved )
967 *ballradius =
MAX(*ballradius,
sepadata->radiusmin);
969 else if( nlpiters == 0 )
973 if(
sepadata->optimalfacepriority <= 1 )
976 *ballradius =
MIN(*ballradius,
sepadata->radiusmax);
981 *ballradius =
MIN(*ballradius,
sepadata->radiusmax/2.0);
1019 for(
i = 1;
i < dualvectorlen;
i++ )
1029 for(
i = 0;
i < dualvectorlen;
i++ )
1036 temp1vals[0] =
REALABS(dualvector[0]);
1039 pivotparam =
REALABS(dualvector[0]) - radius;
1041 for(
i = 1;
i < dualvectorlen;
i++ )
1045 pivotparam += ((
REALABS(dualvector[
i]) - pivotparam) / (temp1len + 1));
1048 temp1vals[temp1len] =
REALABS(dualvector[
i]);
1049 temp1inds[temp1len] =
i;
1054 for( j = 0; j < temp1len; j++ )
1056 temp2vals[temp2len + j] = temp1vals[j];
1057 temp2inds[temp2len + j] = temp1inds[j];
1059 temp2len += temp1len;
1060 temp1vals[0] =
REALABS(dualvector[
i]);
1063 pivotparam =
REALABS(dualvector[
i]) - radius;
1068 for(
i = 0;
i < temp2len;
i++ )
1072 temp1vals[temp1len] = temp2vals[
i];
1073 temp1inds[temp1len] = temp2inds[
i];
1075 pivotparam += ((temp2vals[
i] - pivotparam) / temp1len);
1079 temp1changed =
TRUE;
1081 while( temp1changed )
1083 temp1changed =
FALSE;
1085 for(
i = 0;
i < temp1len;
i++ )
1090 if( (temp1inds[
i] >= 0) &&
SCIPisLE(
scip, temp1vals[
i], pivotparam) )
1093 temp1changed =
TRUE;
1095 assert(temp1len - ntemp1removed > 0);
1097 pivotparam += ((pivotparam - temp1vals[
i]) / (temp1len - ntemp1removed));
1102 for(
i = 0;
i < dualvectorlen;
i++ )
1105 val =
MAX(term - pivotparam, 0.0);
1109 dualvector[
i] = val;
1113 dualvector[
i] = -val;
1118 for(
i = 0;
i < dualvectorlen;
i++ )
1150 for(
i = 0;
i < dualvectorlen;
i++ )
1151 l2norm +=
SQR(dualvector[
i]);
1152 l2norm = sqrt(l2norm);
1153 factor = radius/(1.0 + l2norm);
1158 for(
i = 0;
i < dualvectorlen;
i++ )
1159 dualvector[
i] *= factor;
1177 for(
i = 0;
i < dualvectorlen;
i++ )
1180 dualvector[
i] = -radius;
1182 dualvector[
i] = radius;
1196 int stabilitycenterlen,
1197 int nbestdualupdates,
1209 weight =
MIN(constant, (totaliternum + 1 + nbestdualupdates) / 2.0);
1210 alpha = 1.0 / weight;
1212 assert(dualvectorlen >= stabilitycenterlen);
1215 for(
i = 0;
i < stabilitycenterlen;
i++ )
1216 dualvector[
i] =
alpha * dualvector[
i] + (1 -
alpha) * stabilitycenter[
i];
1218 for(
i = stabilitycenterlen;
i < dualvectorlen;
i++ )
1219 dualvector[
i] =
alpha * dualvector[
i];
1230 int bestdualvectorlen,
1231 int nbestdualupdates,
1232 int subgradientiternum,
1249 if( subgradientiternum >= 1 )
1256 if(
sepadata->projectiontype == 1 )
1261 else if(
sepadata->projectiontype == 2 )
1266 else if(
sepadata->projectiontype == 3 )
1273 if(
sepadata->stabilitycentertype == 1 )
1290 int ndualvector2updates,
1291 int subgradientiternum,
1314 assert(dualvector2len <= ncuts);
1317 *dualvecsdiffer =
FALSE;
1322 for(
i = 0;
i < ncuts;
i++ )
1323 dualvector1copy[
i] = dualvector1[
i];
1330 assert((subgradient !=
NULL) || (ncuts == 0));
1331 assert(subgradientiternum >= 0);
1334 for(
i = 0;
i < ncuts;
i++ )
1337 dualvector1[
i] += steplength * subgradient[
i];
1341 for(
i = 0;
i < ncuts;
i++ )
1344 dualvector1[
i] =
MAX(dualvector1[
i], 0.0);
1349 ndualvector2updates, subgradientiternum, totaliternum, maxviolscore, maxviolscoreold, nviolscore,
1350 nviolscoreold, nlpiters, ballradius) );
1353 for(
i = 0;
i < ncuts;
i++ )
1354 dualvector1[
i] =
MAX(dualvector1[
i], 0.0);
1361 for(
i = 0;
i < dualvector2len;
i++ )
1362 dualvector1[
i] = dualvector2[
i];
1364 for(
i = dualvector2len;
i < ncuts;
i++ )
1365 dualvector1[
i] = 0.0;
1369 for(
i = 0;
i < ncuts;
i++ )
1373 *dualvecsdiffer =
TRUE;
1379 for(
i = 0;
i < ncuts;
i++ )
1380 dualvector1copy[
i] = 0.0;
1395 int nnewaddedsoftcuts,
1397 int nyettoaddsoftcuts,
1400 int ngeneratedcurrroundcuts,
1401 int nmaxgeneratedperroundcuts,
1402 int ncurrroundlpiters,
1412 if( (nnewaddedsoftcuts == 0) && (nyettoaddsoftcuts == 0) && !objvecsdiffer )
1416 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
1424 if( (
sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >=
sepadata->nmaxperroundlpiters) )
1449 int* ncurrroundlpiters
1485 if( timelimit <= 0.0 )
1503 else if( (
depth > 0) &&
1508 if(
sepadata->nmaxperroundlpiters >= 0 )
1510 if(
sepadata->nmaxperroundlpiters - *ncurrroundlpiters >= 0 )
1512 if( iterlimit >= 0 )
1513 iterlimit =
MIN(iterlimit,
sepadata->nmaxperroundlpiters - *ncurrroundlpiters);
1515 iterlimit =
sepadata->nmaxperroundlpiters - *ncurrroundlpiters;
1548 for(
i = 0;
i < ncols; ++
i )
1566 sepadata->nrootlpiters += (int)nlpiters;
1568 sepadata->ntotallpiters += (int)nlpiters;
1569 *ncurrroundlpiters += (int)nlpiters;
1604 if( timelimit <= 0.0 )
1624 for(
i = 0;
i < ncols; ++
i )
1646 int subgradientiternum,
1657 int ngeneratedcurrroundcuts,
1658 int* ngeneratednewcuts,
1669 assert(mainiternum >= 0);
1677 SCIPdebugMsg(
scip,
" -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
1691 if( subgradientiternum >= 0 )
1694 sepadata->ncalls, mainiternum, subgradientiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
1699 sepadata->ncalls, mainiternum, ngeneratedcurrroundcuts + *ngeneratednewcuts);
1715 for( v = 0; v < cutnnz; ++v )
1727 SCIPdebugMsg(
scip,
" -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", cutrhs);
1740 SCIPdebugMsg(
scip,
" -> %s cut <%s>: rhs=%f, eff=%f\n",
"lagromory", cutname, cutrhs, cutefficacy);
1755 SCIPdebugMsg(
scip,
"cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
1762 generatedcuts[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cut;
1763 generatedcutefficacies[ngeneratedcurrroundcuts + *ngeneratednewcuts] = cutefficacy;
1764 ++(*ngeneratednewcuts);
1779 int bestdualvectorlen,
1830 aggrindicator =
FALSE;
1843 for(
i = 0;
i < bestdualvectorlen;
i++ )
1845 multiplier = bestdualvector[
i];
1848 cut = generatedcuts[
i];
1858 for( j = 0; j < cutnnz; j++ )
1862 assert(collppos <= ncols);
1876 aggrcutrank =
MAX(aggrcutrank, cutrank);
1878 aggrindicator =
TRUE;
1882 aggrcutislocal = (nlocalcuts > 0 ?
TRUE :
FALSE);
1891 for(
i = 0;
i < ncols;
i++ )
1897 aggrcutcoefs[aggrcutnnz] = aggrcutvals[
i];
1898 aggrcutinds[aggrcutnnz] =
i;
1905 SCIPdebugMsg(
scip,
" -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
1916 aggrcutconst, aggrcutislocal,
FALSE,
sepadata->dynamiccuts) );
1925 for(
i = 0;
i < aggrcutnnz;
i++ )
1937 SCIPdebugMsg(
scip,
" -> Lagromory cut detected node infeasibility with cut 0 <= %g.\n", aggrcutrhs);
1950 SCIPdebugMsg(
scip,
" -> %s cut <%s>: rhs=%f\n",
"lagromory", aggrcutname, aggrcutrhs);
1965 SCIPdebugMsg(
scip,
"cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
1966 SCIProwGetName(aggrcut), cutlhs, cutrhs, minactivity, maxactivity);
1972 aggrcuts[*naggrcuts] = aggrcut;
1977 for(
i = 0;
i < ncols;
i++ )
1979 aggrcutvals[
i] = 0.0;
2001 int subgradientiternum,
2004 int nmaxgeneratedperroundcuts,
2009 int ngeneratedcurrroundcuts,
2010 int* ngeneratednewcuts,
2050 *ngeneratednewcuts = 0;
2066 for(
i = 0;
i < nrows; ++
i )
2102 if(
frac >= minfrac )
2123 if( (ngeneratedcurrroundcuts + *ngeneratednewcuts >= nmaxgeneratedperroundcuts) ||
2125 (*ngeneratednewcuts >= nmaxcutsperlp) )
2132 if( basisfrac[
i] == 0.0 )
2158 NULL, minfrac, maxfrac, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank,
2159 &cutislocal, &success) );
2163 assert(allowlocal || !cutislocal);
2166 cutefficacy, cutrhs, cutislocal, cutrank, generatedcurrroundcuts, generatedcutefficacies,
2167 ngeneratedcurrroundcuts, ngeneratednewcuts,
cutoff));
2217 *objvecsdiffer =
FALSE;
2220 for(
i = 0;
i < ncuts;
i++ )
2233 for( j = 0; j < cutnnz; ++j )
2237 assert(collppos <= ncols);
2239 prod[collppos] += dualvector[
i] * cutvals[j];
2245 for(
i = 0;
i < ncols;
i++ )
2249 objvals[
i] = origobjcoefs[
i] + prod[
i];
2254 if( !(*objvecsdiffer) && !
SCIPisEQ(
scip, oldobjvals[
i], objvals[
i]) )
2255 *objvecsdiffer =
TRUE;
2258 for(
i = 0;
i < ncols;
i++)
2276 int* nnewaddedsoftcuts
2281 assert(*naddedcuts <= ngeneratedcuts);
2284 for(
i = *naddedcuts;
i < ngeneratedcuts;
i++ )
2285 dualvector[
i] = 0.0;
2287 *nnewaddedsoftcuts = ngeneratedcuts - *naddedcuts;
2288 *naddedcuts = ngeneratedcuts;
2307 int nmaxgeneratedperroundcuts,
2315 int* ngeneratedcutsperiter,
2316 int* ngeneratedcurrroundcuts,
2317 int* ncurrroundlpiters,
2322 int* bestdualvectorlen,
2324 int* nbestdualupdates,
2350 int ncurrroundlpiterslast;
2352 int ngeneratednewcuts;
2353 int nnewaddedsoftcuts;
2355 int nnzsubgradientdualprod;
2365 avglagrangianval = 0.0;
2366 maxsoftcutviol = 0.0;
2367 maxnzsubgradientdualprod = 0.0;
2372 ngeneratednewcuts = 0;
2374 nnzsubgradientdualprod = 0;
2376 subgradientzero =
FALSE;
2377 objvecsdiffer =
FALSE;
2378 dualvecsdiffer =
FALSE;
2382 if( *nsoftcuts > 0 )
2389 nmaxgeneratedperroundcuts, *ncurrroundlpiters,
depth, &terminate) );
2395 subgradientzero =
FALSE;
2396 objvecsdiffer =
FALSE;
2397 dualvecsdiffer =
FALSE;
2398 nnewaddedsoftcuts = 0;
2399 scoreweight *=
sepadata->radiusupdateweight;
2401 ncurrroundlpiterslast = *ncurrroundlpiters;
2406 ncurrroundlpiters) );
2408 nlpiters = *ncurrroundlpiters - ncurrroundlpiterslast;
2414 if( (nlpiters >= 1) && (
i %
sepadata->cutgenfreq == 0) )
2416 ngeneratednewcuts = 0;
2418 nmaxgeneratedperroundcuts, allowlocal, generatedcurrroundcuts, generatedcutefficacies,
2419 *ngeneratedcurrroundcuts, &ngeneratednewcuts,
depth,
cutoff));
2420 sepadata->ntotalcuts += ngeneratednewcuts;
2421 *ngeneratedcurrroundcuts += ngeneratednewcuts;
2422 ngeneratedcutsperiter[mainiternum *
sepadata->nmaxsubgradientiters +
i + 1] = ngeneratednewcuts;
2427 &nsoftcutviols, &maxsoftcutviol, &nnzsubgradientdualprod, &maxnzsubgradientdualprod);
2433 *bestlagrangianval = lagrangianval;
2435 for( j = 0; j < *nsoftcuts; j++ )
2436 bestdualvector[j] = dualvector[j];
2438 *bestdualvectorlen = *nsoftcuts;
2439 (*nbestdualupdates)++;
2441 lagrangianvals[
i] = lagrangianval;
2443 avglagrangianval = (avglagrangianval *
i + lagrangianval)/(
i+1);
2446 avglagrangianval = (avglagrangianval *
sepadata->nmaxlagrangianvalsforavg -
2447 lagrangianvals[
i -
sepadata->nmaxlagrangianvalsforavg] +
2448 lagrangianval)/(
sepadata->nmaxlagrangianvalsforavg);
2452 if( !subgradientzero )
2456 &muparam, &backtrack) );
2462 maxviolscoreold = maxviolscore;
2463 nviolscoreold = nviolscore;
2464 maxviolscore = (1.0 - scoreweight) * maxsoftcutviol + scoreweight * maxnzsubgradientdualprod;
2465 nviolscore = (1.0 - scoreweight) * nsoftcutviols + scoreweight * nnzsubgradientdualprod;
2469 *nbestdualupdates,
i, *totaliternum, steplength, subgradient, *nsoftcuts, backtrack, maxviolscore,
2470 maxviolscoreold, nviolscore, nviolscoreold, nlpiters, &dualvecsdiffer, &ballradius) );
2473 if( dualvecsdiffer )
2482 dualvecsdiffer =
FALSE;
2483 objvecsdiffer =
FALSE;
2488 if( (
i %
sepadata->cutaddfreq == 0) || (!dualvecsdiffer && !objvecsdiffer &&
2489 (*ngeneratedcurrroundcuts - *nsoftcuts > 0)) )
2498 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
2508 objvecsdiffer, *ngeneratedcurrroundcuts, nmaxgeneratedperroundcuts, *ncurrroundlpiters,
depth,
2516 if( (*ngeneratedcurrroundcuts - *nsoftcuts) > 0 )
2522 for(
i = 0;
i < nmaxgeneratedperroundcuts;
i++)
2523 subgradient[
i] = 0.0;
2540 int nmaxgeneratedperroundcuts,
2545 int* ngeneratedcutsperiter,
2546 int* ngeneratedcurrroundcuts,
2551 int ngeneratednewcuts;
2553 ngeneratednewcuts = 0;
2557 allowlocal, generatedcurrroundcuts, generatedcutefficacies, *ngeneratedcurrroundcuts, &ngeneratednewcuts,
2561 sepadata->ntotalcuts += ngeneratednewcuts;
2562 *ngeneratedcurrroundcuts += ngeneratednewcuts;
2563 ngeneratedcutsperiter[
sepadata->nmaxsubgradientiters * mainiternum] = ngeneratednewcuts;
2591 madeintegral =
FALSE;
2593 for(
i = 0;
i < ncuts && !*
cutoff;
i++ )
2651 int ngeneratedcurrroundcuts,
2653 int nmaxgeneratedperroundcuts,
2654 int ncurrroundlpiters,
2667 if( !dualvecsdiffer && (ngeneratedcurrroundcuts == nsoftcuts) )
2671 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
2679 if( (
sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >=
sepadata->nmaxperroundlpiters) )
2706 SCIP_ROW** aggregatedcurrroundcuts;
2728 int* ngeneratedcutsperiter;
2729 int bestdualvectorlen;
2730 int nbestdualupdates;
2736 int ngeneratedcurrroundcuts;
2737 int nselectedcurrroundcuts;
2739 int naddedcurrroundcuts;
2740 int naggregatedcurrroundcuts;
2741 int nmaxgeneratedperroundcuts;
2742 int ncurrroundlpiters;
2754 bestdualvectorlen = 0;
2755 nbestdualupdates = 0;
2757 ngeneratedcurrroundcuts = 0;
2758 naddedcurrroundcuts = 0;
2759 naggregatedcurrroundcuts = 0;
2760 ncurrroundlpiters = 0;
2765 dualvecsdiffer =
FALSE;
2779 nmaxgeneratedperroundcuts = ((
depth == 0) ?
sepadata->nmaxperroundcutsroot :
sepadata->nmaxperroundcuts);
2787 (
sepadata->nmaxsubgradientiters + 1)) );
2798 for(
i = 0;
i < ncols;
i++ )
2805 &ncurrroundlpiters));
2809 generatedcurrroundcuts, generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts,
depth,
2814 nmaxgeneratedperroundcuts, ncurrroundlpiters,
depth, &terminate) );
2819 nsoftcutsold = nsoftcuts;
2820 nsoftcuts = ngeneratedcurrroundcuts;
2821 dualvecsdiffer =
FALSE;
2825 nmaxgeneratedperroundcuts, origobjcoefs, origobjoffset, dualvector, &nsoftcuts, generatedcurrroundcuts,
2826 generatedcutefficacies, ngeneratedcutsperiter, &ngeneratedcurrroundcuts, &ncurrroundlpiters, &
cutoff,
2827 &bestlagrangianval, bestdualvector, &bestdualvectorlen, &nbestdualupdates, &totaliternum) );
2832 if( !
cutoff && (ngeneratedcurrroundcuts - nsoftcutsold > 0) )
2854 ngeneratedcurrroundcuts, 0, -1, -1, 0.0,
NULL, ngeneratedcurrroundcuts,
TRUE, 0.0, 0.0, 0.0, 0.0, -1,
2855 &dualvecsdiffer,
NULL) );
2859 SCIP_CALL(
updateDualVector(
scip,
sepadata, dualvector, dualvector, nsoftcuts, 0, -1, -1, 0.0,
NULL,
2860 ngeneratedcurrroundcuts,
TRUE, 0.0, 0.0, 0.0, 0.0, -1, &dualvecsdiffer,
NULL) );
2866 nmaxgeneratedperroundcuts, ncurrroundlpiters,
depth, &terminate) );
2899 if( !
cutoff && (ngeneratedcurrroundcuts > 0) )
2903 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
2905 &naddedcurrroundcuts, &cutoff2) );
2913 if( ngeneratedcutsperiter[
i] != 0 )
2915 for( j = 0; j < ngeneratedcutsperiter[
i]; j++ )
2916 cutindsperm[j] = j + nprocessedcuts;
2919 SCIPsortDownRealInt(&generatedcutefficacies[nprocessedcuts], cutindsperm, ngeneratedcutsperiter[
i]);
2924 maxscale, &naddedcurrroundcuts, &cutoff2) );
2927 nprocessedcuts += ngeneratedcutsperiter[
i];
2932 else if( ngeneratedcurrroundcuts > 0 )
2934 nselectedcurrroundcuts = ngeneratedcurrroundcuts;
2936 &naddedcurrroundcuts, &cutoff2) );
2940 if(
sepadata->aggregatecuts && (ngeneratedcurrroundcuts > 0) && (bestdualvectorlen > 0) )
2942 assert(bestdualvectorlen <= ngeneratedcurrroundcuts);
2944 aggregatedcurrroundcuts, &naggregatedcurrroundcuts, &cutoff2) );
2946 if( naggregatedcurrroundcuts > 0 )
2949 &naddedcurrroundcuts, &cutoff2) );
2958 else if( naddedcurrroundcuts > 0 )
2971 for(
i = 0;
i < naggregatedcurrroundcuts; ++
i )
2977 for(
i = 0;
i < ngeneratedcurrroundcuts; ++
i )
2983 ngeneratedcutsperiter[
i] = 0;
2985 for(
i = 0;
i < nrows;
i++ )
2988 for(
i = 0;
i < nmaxgeneratedperroundcuts;
i++ )
2990 dualsol[nrows +
i] = 0.0;
2991 dualvector[
i] = 0.0;
2992 bestdualvector[
i] = 0.0;
3133 dualdegeneracyrate = 0.0;
3141 if( (
sepadata->minrestart >= 1) && (runnum < sepadata->minrestart + 1) )
3164 if( ncols == 0 || nrows == 0 )
3168 threshold1 =
sepadata->dualdegeneracyratethreshold;
3169 threshold2 =
sepadata->varconsratiothreshold;
3171 if( (dualdegeneracyrate < threshold1) && (varconsratio < threshold2) )
3178 if( bestsol !=
NULL )
3180 for(
i = 0;
i < ncols; ++
i )
3197 for(
i = 0;
i < ncols; ++
i )
3250 "iterations for maximal separating LP iterations in the root node (negative for no limit)",
3254 "iterations for maximal separating LP iterations in the tree (negative for no limit)",
3258 "iterations for maximal separating LP iterations per separation round (negative for no limit)",
3263 "columns for number of cuts separated per separation round in root node", &
sepadata->perroundcutsfactorroot,
3267 "columns for number of cuts separated per separation round at a non-root node",
3315 "iterations for iteration limit of each separating LP (negative for no limit)",
3319 "iterations for iteration limit of each separating LP (negative for no limit)", &
sepadata->perlpiterfactor,
TRUE,
3343 "violation score used for updating ball radius", &
sepadata->radiusupdateweight,
TRUE,
3347 "rate for separator execution", &
sepadata->dualdegeneracyratethreshold,
FALSE,
3351 "ratio on optimal face for separator execution", &
sepadata->varconsratiothreshold,
FALSE,
3392 "iterations per separation round (-1: unlimited)", &
sepadata->perroundnmaxlpiters,
FALSE,
3407 "iterations of the relax-and-cut algorithm", &
sepadata->nmaxsubgradientiters,
TRUE,
3417 "for rolling average of Lagrangian value", &
sepadata->nmaxlagrangianvalsforavg,
TRUE,
3421 "iterations used to determine if mu needs to be backtracked", &
sepadata->nmaxconsecitersformuupdate,
TRUE,
3425 "are projected for stabilization (0: no projection, 1: L1-norm ball projection, 2: L2-norm ball projection, 3: "
3429 "taking weighted average of Lagrangian multipliers for stabilization (0: no weighted stabilization, 1: best "
3434 "separator execution (0: low priority, 1: medium priority, 2: high priority)",
3438 "execution (0: from beginning of the instance solving, >= n with n >= 1: from restart round n)",
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDS
#define QUAD_ARRAY_STORE(a, idx, x)
#define SCIPquadprecProdDD(r, a, b)
#define QUAD_ARRAY_SIZE(size)
#define QUAD_ASSIGN(a, constant)
#define SCIPquadprecSumQQ(r, a, b)
#define QUAD_ARRAY_LOAD(r, a, idx)
#define SCIP_LONGINT_FORMAT
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
SCIP_RETCODE SCIPlpiSetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
SCIP_RETCODE SCIPlpiSetRealpar(SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
SCIP_Bool SCIPlpiIsPrimalFeasible(SCIP_LPI *lpi)
SCIP_Bool SCIPlpiIsDualFeasible(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
SCIP_RETCODE SCIPlpiFreeState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
SCIP_RETCODE SCIPlpiGetState(SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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 SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
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)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
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)
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
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_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_Real SCIPgetVarObjDive(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPgetLPDualDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
SCIP_RETCODE SCIPchgVarObjDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
int SCIPgetNLPRows(SCIP *scip)
SCIP_RETCODE SCIPgetLPI(SCIP *scip, SCIP_LPI **lpi)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetRowMinActivity(SCIP *scip, SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Real SCIPgetRowMaxActivity(SCIP *scip, SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
int SCIProwGetRank(SCIP_ROW *row)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
int SCIPgetMaxDepth(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasFrac(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 SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
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 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 SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
SCIP_RETCODE SCIPincludeSepaLagromory(SCIP *scip)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
primal heuristic that tries a given solution
#define BMSclearMemory(ptr)
struct BMS_BlkMem BMS_BLKMEM
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define DEFAULT_DYNAMICCUTS
#define SEPA_MAXBOUNDDIST
#define MAXAGGRLEN(nvars)
#define DEFAULT_MAKEINTEGRAL
#define DEFAULT_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
#define DEFAULT_FORCECUTS
#define DEFAULT_SEPARATEROWS
#define DEFAULT_MAXLAGRANGIANVALSFORAVG
#define DEFAULT_DELTASLAB1UB
#define DEFAULT_UBPARAMNEGFACTOR
#define DEFAULT_VARCONSRATIOTHRESHOLD
#define DEFAULT_DUALDEGENERACYRATETHRESHOLD
#define DEFAULT_MUPARAMINIT
static SCIP_RETCODE sepadataCreate(SCIP *scip, SCIP_SEPADATA **sepadata)
#define DEFAULT_MUPARAMUB
static SCIP_RETCODE updateMuSteplengthParam(SCIP *scip, SCIP_SEPADATA *sepadata, int subgradientiternum, SCIP_Real ubparam, SCIP_Real *lagrangianvals, SCIP_Real bestlagrangianval, SCIP_Real avglagrangianval, SCIP_Real *muparam, SCIP_Bool *backtrack)
#define DEFAULT_ALLOWLOCAL
static SCIP_RETCODE deleteLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
#define DEFAULT_UBPARAMPOSFACTOR
static void linfBallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
#define DEFAULT_MAXSUBGRADIENTITERS
static SCIP_RETCODE generateGMICuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, int depth, SCIP_Bool *cutoff)
static SCIP_RETCODE solveLagromoryLP(SCIP *scip, SCIP_SEPADATA *sepadata, int depth, SCIP_Real origobjoffset, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals, SCIP_Real *objval, int *ncurrroundlpiters)
static SCIP_RETCODE aggregateGeneratedCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_ROW **generatedcuts, SCIP_Real *bestdualvector, int bestdualvectorlen, SCIP_ROW **aggrcuts, int *naggrcuts, SCIP_Bool *cutoff)
#define DEFAULT_MUPARAMLB
#define DEFAULT_RADIUSMAX
static SCIP_RETCODE updateDualVector(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector1, SCIP_Real *dualvector2, int dualvector2len, int ndualvector2updates, int subgradientiternum, int totaliternum, SCIP_Real steplength, SCIP_Real *subgradient, int ncuts, SCIP_Bool backtrack, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Bool *dualvecsdiffer, SCIP_Real *ballradius)
#define DEFAULT_PERLPMAXCUTSROOT
#define DEFAULT_PROJECTIONTYPE
#define DEFAULT_CUTADDFREQ
static SCIP_RETCODE checkMainLoopTermination(SCIP_SEPADATA *sepadata, SCIP_Bool cutoff, SCIP_Bool dualvecsdiffer, int ngeneratedcurrroundcuts, int nsoftcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)
#define DEFAULT_MUSLAB2FACTOR
#define DEFAULT_RADIUSINIT
#define DEFAULT_TOTALCUTSFACTOR
static SCIP_RETCODE generateInitCutPool(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, SCIP_SOL *sol, SCIP_Real *solvals, int nmaxgeneratedperroundcuts, SCIP_Bool allowlocal, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int depth, SCIP_Bool *cutoff)
#define DEFAULT_PERROUNDMAXLPITERS
#define DEFAULT_PERROUNDCUTSFACTOR
#define DEFAULT_MAXMAINITERS
#define DEFAULT_PERROUNDCUTSFACTORROOT
static void updateSubgradient(SCIP *scip, SCIP_SOL *sol, SCIP_ROW **cuts, int ncuts, SCIP_Real *subgradient, SCIP_Real *dualvector, SCIP_Bool *subgradientzero, int *ncutviols, SCIP_Real *maxcutviol, int *nnzsubgradientdualprod, SCIP_Real *maxnzsubgradientdualprod)
static SCIP_RETCODE l1BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
#define DEFAULT_OPTIMALFACEPRIORITY
#define DEFAULT_SORTCUTOFFSOL
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, SCIP_RESULT *result)
#define DEFAULT_MUSLAB1FACTOR
#define DEFAULT_PERROUNDLPITERLIMITFACTOR
#define DEFAULT_CUTSFILTERFACTOR
static SCIP_RETCODE sepadataFree(SCIP *scip, SCIP_SEPADATA **sepadata)
static SCIP_RETCODE createLPWithSoftCuts(SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE updateObjectiveVector(SCIP *scip, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *origobjcoefs, SCIP_Bool *objvecsdiffer)
static SCIP_RETCODE addGMICutsAsSoftConss(SCIP_Real *dualvector, int ngeneratedcuts, int *naddedcuts, int *nnewaddedsoftcuts)
static SCIP_RETCODE addCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts, SCIP_Longint maxdnom, SCIP_Real maxscale, int *naddedcuts, SCIP_Bool *cutoff)
static SCIP_RETCODE solveLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Bool *solfound, SCIP_SOL *sol, SCIP_Real *solvals)
#define DEFAULT_PERLPITERFACTOR
static SCIP_RETCODE checkLagrangianDualTermination(SCIP_SEPADATA *sepadata, int nnewaddedsoftcuts, int nyettoaddsoftcuts, SCIP_Bool objvecsdiffer, int ngeneratedcurrroundcuts, int nmaxgeneratedperroundcuts, int ncurrroundlpiters, int depth, SCIP_Bool *terminate)
static SCIP_RETCODE createLPWithHardCuts(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_ROW **cuts, int ncuts)
#define DEFAULT_STABILITYCENTERTYPE
#define DEFAULT_RADIUSMIN
static SCIP_RETCODE solveLagrangianDual(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *solvals, int mainiternum, SCIP_Real ubparam, int depth, SCIP_Bool allowlocal, int nmaxgeneratedperroundcuts, SCIP_Real *origobjcoefs, SCIP_Real origobjoffset, SCIP_Real *dualvector, int *nsoftcuts, SCIP_ROW **generatedcurrroundcuts, SCIP_Real *generatedcutefficacies, int *ngeneratedcutsperiter, int *ngeneratedcurrroundcuts, int *ncurrroundlpiters, SCIP_Bool *cutoff, SCIP_Real *bestlagrangianval, SCIP_Real *bestdualvector, int *bestdualvectorlen, int *nbestdualupdates, int *totaliternum)
#define DEFAULT_PERROOTLPITERFACTOR
static SCIP_RETCODE constructCutRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int mainiternum, int subgradientiternum, int cutnnz, int *cutinds, SCIP_Real *cutcoefs, SCIP_Real cutefficacy, SCIP_Real cutrhs, SCIP_Bool cutislocal, int cutrank, SCIP_ROW **generatedcuts, SCIP_Real *generatedcutefficacies, int ngeneratedcurrroundcuts, int *ngeneratednewcuts, SCIP_Bool *cutoff)
#define DEFAULT_ROOTLPITERLIMITFACTOR
#define DEFAULT_AGGREGATECUTS
#define DEFAULT_MUBACKTRACKFACTOR
static void updateLagrangianValue(SCIP *scip, SCIP_Real objval, SCIP_Real *dualvector, SCIP_ROW **cuts, int ncuts, SCIP_Real *lagrangianval)
#define DEFAULT_MINRESTART
#define DEFAULT_CUTGENFREQ
static void updateStepLength(SCIP *scip, SCIP_Real muparam, SCIP_Real ubparam, SCIP_Real lagrangianval, SCIP_Real *subgradient, int ncuts, SCIP_Real *steplength)
#define DEFAULT_RADIUSUPDATEWEIGHT
static void updateBallRadius(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)
static void l2BallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
#define DEFAULT_DELTASLAB2UB
#define DEFAULT_MUPARAMCONST
static SCIP_RETCODE stabilizeDualVector(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *bestdualvector, int bestdualvectorlen, int nbestdualupdates, int subgradientiternum, int totaliternum, SCIP_Real maxviolscore, SCIP_Real maxviolscoreold, SCIP_Real nviolscore, SCIP_Real nviolscoreold, int nlpiters, SCIP_Real *ballradius)
#define DEFAULT_TOTALLPITERLIMITFACTOR
#define DEFAULT_PERLPMAXCUTS
static void weightedDualVector(SCIP_SEPADATA *sepadata, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real *stabilitycenter, int stabilitycenterlen, int nbestdualupdates, int totaliternum)
#define DEFAULT_MUSLAB3FACTOR
#define DEFAULT_MAXCONSECITERSFORMUUPDATE
struct SCIP_AggrRow SCIP_AGGRROW
struct SCIP_Heur SCIP_HEUR
enum SCIP_LPSolStat SCIP_LPSOLSTAT
struct SCIP_LPiState SCIP_LPISTATE
struct SCIP_RandNumGen SCIP_RANDNUMGEN
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXIT(x)
struct SCIP_Sepa SCIP_SEPA
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS