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)
245 SCIP_Bool delayedcuts;
246 SCIP_Bool separaterows;
247 SCIP_Bool sortcutoffsol;
248 SCIP_Bool sidetypebasis;
249 SCIP_Bool dynamiccuts;
250 SCIP_Bool makeintegral;
252 SCIP_Bool allowlocal;
259 int nrowsinhardcutslp;
260 int nrunsinsoftcutslp;
266 SCIP_Real dualdegeneracyratethreshold;
267 SCIP_Real varconsratiothreshold;
270 int nmaxcutsperlproot;
272 SCIP_Real perroundlpiterlimitfactor;
274 SCIP_Real rootlpiterlimitfactor;
276 SCIP_Real totallpiterlimitfactor;
278 int perroundnmaxlpiters;
279 SCIP_Real perroundcutsfactorroot;
281 SCIP_Real perroundcutsfactor;
283 SCIP_Real totalcutsfactor;
285 int nmaxsubgradientiters;
286 int nmaxperroundlpiters;
289 int nmaxtotallpiters;
291 int nmaxperroundcutsroot;
292 int nmaxperroundcuts;
297 SCIP_Bool muparamconst;
298 SCIP_Real muparaminit;
301 SCIP_Real mubacktrackfactor;
303 SCIP_Real muslab1factor;
305 SCIP_Real muslab2factor;
307 SCIP_Real muslab3factor;
308 SCIP_Real deltaslab1ub;
310 SCIP_Real deltaslab2ub;
312 SCIP_Real ubparamposfactor;
314 SCIP_Real ubparamnegfactor;
316 int nmaxlagrangianvalsforavg;
317 int nmaxconsecitersformuupdate;
318 SCIP_Real perrootlpiterfactor;
320 SCIP_Real perlpiterfactor;
324 SCIP_Real cutsfilterfactor;
325 int optimalfacepriority;
327 SCIP_Bool aggregatecuts;
333 int stabilitycentertype;
335 SCIP_Real radiusinit;
339 SCIP_Real radiusupdateweight;
361 unsigned int nintcols;
362 SCIP_Longint nrootlpiters;
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,
688 SCIP_Real* lagrangianvals,
689 SCIP_Real bestlagrangianval,
690 SCIP_Real avglagrangianval,
696 SCIP_Real deltaslab1ub;
697 SCIP_Real deltaslab2ub;
698 SCIP_Real muslab1factor;
699 SCIP_Real muslab2factor;
700 SCIP_Real muslab3factor;
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;
812 SCIP_Real* subgradient,
813 SCIP_Real* dualvector,
814 SCIP_Bool* subgradientzero,
816 SCIP_Real* maxcutviol,
817 int* nnzsubgradientdualprod,
819 SCIP_Real* maxnzsubgradientdualprod
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;
881 SCIP_Real* dualvector,
884 SCIP_Real* lagrangianval
893 for(
i = 0;
i < ncuts;
i++ )
907 SCIP_Real lagrangianval,
908 SCIP_Real* subgradient,
910 SCIP_Real* steplength
913 SCIP_Real normsquared = 0.0;
916 for(
i = 0;
i < ncuts;
i++ )
917 normsquared +=
SQR(subgradient[
i]);
920 *steplength = (muparam * (ubparam - lagrangianval))/(normsquared);
928 SCIP_Real maxviolscore,
930 SCIP_Real maxviolscoreold,
932 SCIP_Real nviolscore,
934 SCIP_Real nviolscoreold,
938 SCIP_Real* ballradius
941 SCIP_Bool maxviolscoreimproved;
942 SCIP_Bool nviolscoreimproved;
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);
996 SCIP_Real* dualvector,
1001 SCIP_Real* temp1vals;
1002 SCIP_Real* temp2vals;
1003 SCIP_Real pivotparam;
1006 SCIP_Bool temp1changed;
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++ )
1136 SCIP_Real* dualvector,
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;
1167 SCIP_Real* dualvector,
1177 for(
i = 0;
i < dualvectorlen;
i++ )
1180 dualvector[
i] = -radius;
1182 dualvector[
i] = radius;
1193 SCIP_Real* dualvector,
1195 SCIP_Real* stabilitycenter,
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];
1227 SCIP_Real* dualvector,
1229 SCIP_Real* bestdualvector,
1230 int bestdualvectorlen,
1231 int nbestdualupdates,
1232 int subgradientiternum,
1234 SCIP_Real maxviolscore,
1236 SCIP_Real maxviolscoreold,
1238 SCIP_Real nviolscore,
1240 SCIP_Real nviolscoreold,
1244 SCIP_Real* ballradius
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 )
1287 SCIP_Real* dualvector1,
1288 SCIP_Real* dualvector2,
1290 int ndualvector2updates,
1291 int subgradientiternum,
1293 SCIP_Real steplength,
1294 SCIP_Real* subgradient,
1296 SCIP_Bool backtrack,
1297 SCIP_Real maxviolscore,
1299 SCIP_Real maxviolscoreold,
1301 SCIP_Real nviolscore,
1303 SCIP_Real nviolscoreold,
1307 SCIP_Bool* dualvecsdiffer,
1308 SCIP_Real* ballradius
1311 SCIP_Real* dualvector1copy;
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,
1399 SCIP_Bool objvecsdiffer,
1400 int ngeneratedcurrroundcuts,
1401 int nmaxgeneratedperroundcuts,
1402 int ncurrroundlpiters,
1404 SCIP_Bool* terminate
1412 if( (nnewaddedsoftcuts == 0) && (nyettoaddsoftcuts == 0) && !objvecsdiffer )
1416 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
1424 if( (
sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >=
sepadata->nmaxperroundlpiters) )
1444 SCIP_Real origobjoffset,
1445 SCIP_Bool* solfound,
1449 int* ncurrroundlpiters
1453 SCIP_Real timelimit;
1461 SCIP_Longint ntotallpiters;
1462 SCIP_Longint nlpiters;
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;
1580 SCIP_Bool* solfound,
1585 SCIP_Real timelimit;
1604 if( timelimit <= 0.0 )
1624 for(
i = 0;
i < ncols; ++
i )
1646 int subgradientiternum,
1649 SCIP_Real* cutcoefs,
1650 SCIP_Real cutefficacy,
1652 SCIP_Bool cutislocal,
1655 SCIP_Real* generatedcutefficacies,
1657 int ngeneratedcurrroundcuts,
1658 int* ngeneratednewcuts,
1663 SCIP_Real minactivity;
1664 SCIP_Real maxactivity;
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);
1778 SCIP_Real* bestdualvector,
1779 int bestdualvectorlen,
1791 SCIP_Real minactivity;
1792 SCIP_Real maxactivity;
1796 SCIP_Real aggrcutlhs;
1797 SCIP_Real aggrcutrhs;
1798 SCIP_Real aggrcutconst;
1799 SCIP_Real* aggrcutvals;
1800 SCIP_Real* aggrcutcoefs;
1801 SCIP_Real multiplier;
1802 SCIP_Bool aggrcutislocal;
1803 SCIP_Bool aggrindicator;
1804 SCIP_Real* tmpcutvals;
1805 SCIP_Real
QUAD(quadterm);
1806 SCIP_Real
QUAD(tmpcutconst);
1807 SCIP_Real
QUAD(tmpcutrhs);
1808 SCIP_Real
QUAD(quadprod);
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,
2005 SCIP_Bool allowlocal,
2007 SCIP_Real* generatedcutefficacies,
2009 int ngeneratedcurrroundcuts,
2010 int* ngeneratednewcuts,
2018 SCIP_Real* basisfrac;
2022 SCIP_Real* cutcoefs;
2024 SCIP_Real cutefficacy;
2025 SCIP_Bool cutislocal;
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));
2188 SCIP_Real* dualvector,
2191 SCIP_Real* origobjcoefs,
2192 SCIP_Bool* objvecsdiffer
2197 SCIP_Real* oldobjvals;
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++)
2272 SCIP_Real* dualvector,
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;
2306 SCIP_Bool allowlocal,
2307 int nmaxgeneratedperroundcuts,
2308 SCIP_Real* origobjcoefs,
2309 SCIP_Real origobjoffset,
2310 SCIP_Real* dualvector,
2313 SCIP_Real* generatedcutefficacies,
2315 int* ngeneratedcutsperiter,
2316 int* ngeneratedcurrroundcuts,
2317 int* ncurrroundlpiters,
2320 SCIP_Real* bestlagrangianval,
2321 SCIP_Real* bestdualvector,
2322 int* bestdualvectorlen,
2324 int* nbestdualupdates,
2328 SCIP_Real* subgradient;
2330 SCIP_Real steplength;
2332 SCIP_Real lagrangianval;
2333 SCIP_Real* lagrangianvals;
2334 SCIP_Real avglagrangianval;
2335 SCIP_Real maxsoftcutviol;
2336 SCIP_Real maxnzsubgradientdualprod;
2337 SCIP_Real maxviolscore;
2338 SCIP_Real maxviolscoreold;
2339 SCIP_Real nviolscore;
2340 SCIP_Real nviolscoreold;
2341 SCIP_Real scoreweight;
2342 SCIP_Real ballradius;
2344 SCIP_Bool backtrack;
2345 SCIP_Bool terminate;
2346 SCIP_Bool subgradientzero;
2347 SCIP_Bool objvecsdiffer;
2348 SCIP_Bool dualvecsdiffer;
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,
2541 SCIP_Bool allowlocal,
2543 SCIP_Real* generatedcutefficacies,
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;
2575 SCIP_Longint maxdnom,
2582 SCIP_Bool madeintegral;
2591 madeintegral =
FALSE;
2593 for(
i = 0;
i < ncuts && !*
cutoff;
i++ )
2650 SCIP_Bool dualvecsdiffer,
2651 int ngeneratedcurrroundcuts,
2653 int nmaxgeneratedperroundcuts,
2654 int ncurrroundlpiters,
2657 SCIP_Bool* terminate
2667 if( !dualvecsdiffer && (ngeneratedcurrroundcuts == nsoftcuts) )
2671 if( ngeneratedcurrroundcuts >= nmaxgeneratedperroundcuts )
2679 if( (
sepadata->nmaxperroundlpiters >= 0) && (ncurrroundlpiters >=
sepadata->nmaxperroundlpiters) )
2701 SCIP_Bool allowlocal,
2706 SCIP_ROW** aggregatedcurrroundcuts;
2707 SCIP_Real* generatedcutefficacies;
2710 SCIP_Real* softcutslpsolvals;
2712 SCIP_Real* hardcutslpsolvals;
2714 SCIP_Real* dualvector;
2715 SCIP_Real* bestdualvector;
2716 SCIP_Real bestlagrangianval;
2717 SCIP_Real* origobjcoefs;
2718 SCIP_Real origobjoffset;
2721 SCIP_Longint maxdnom;
2724 SCIP_Bool dualvecsdiffer;
2725 SCIP_Bool terminate;
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;
3111 SCIP_Real dualdegeneracyrate;
3112 SCIP_Real varconsratio;
3113 SCIP_Real threshold1;
3114 SCIP_Real threshold2;
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 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_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_DYNAMICCUTS
#define DEFAULT_UBPARAMPOSFACTOR
static void linfBallProjection(SCIP *scip, SCIP_Real *dualvector, int dualvectorlen, SCIP_Real radius)
#define DEFAULT_MAKEINTEGRAL
#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_MAXROUNDSROOT
#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_DELAYEDCUTS
#define DEFAULT_SIDETYPEBASIS
#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
#define MAXAGGRLEN(ncols)
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)
#define SEPA_MAXBOUNDDIST
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_FORCECUTS
#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_MAXROUNDS
#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)
#define DEFAULT_SEPARATEROWS
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
enum SCIP_LPSolStat SCIP_LPSOLSTAT
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)
#define SCIP_DECL_SEPACOPY(x)
#define SCIP_DECL_SEPAINIT(x)
@ SCIP_VARTYPE_CONTINUOUS