73 #define SEPA_NAME "cgmip" 74 #define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator" 75 #define SEPA_PRIORITY -1000 77 #define SEPA_MAXBOUNDDIST 0.0 78 #define SEPA_USESSUBSCIP TRUE 79 #define SEPA_DELAY FALSE 81 #define DEFAULT_MAXROUNDS 5 82 #define DEFAULT_MAXROUNDSROOT 50 83 #define DEFAULT_MAXDEPTH -1 84 #define DEFAULT_DECISIONTREE FALSE 85 #define DEFAULT_TIMELIMIT 1e20 86 #define DEFAULT_MEMORYLIMIT 1e20 87 #define DEFAULT_CUTCOEFBND 1000.0 88 #define DEFAULT_MINNODELIMIT 500LL 89 #define DEFAULT_MAXNODELIMIT 5000LL 90 #define DEFAULT_ONLYACTIVEROWS FALSE 91 #define DEFAULT_MAXROWAGE -1 92 #define DEFAULT_ONLYRANKONE FALSE 93 #define DEFAULT_ONLYINTVARS FALSE 94 #define DEFAULT_CONTCONVERT FALSE 95 #define DEFAULT_CONTCONVFRAC 0.1 96 #define DEFAULT_CONTCONVMIN 100 97 #define DEFAULT_INTCONVERT FALSE 98 #define DEFAULT_INTCONVFRAC 0.1 99 #define DEFAULT_INTCONVMIN 100 100 #define DEFAULT_SKIPMULTBOUNDS TRUE 101 #define DEFAULT_OBJLONE FALSE 102 #define DEFAULT_OBJWEIGHT 1e-03 103 #define DEFAULT_OBJWEIGHTSIZE TRUE 104 #define DEFAULT_DYNAMICCUTS TRUE 105 #define DEFAULT_USECMIR TRUE 106 #define DEFAULT_USESTRONGCG FALSE 107 #define DEFAULT_CMIROWNBOUNDS FALSE 108 #define DEFAULT_USECUTPOOL TRUE 109 #define DEFAULT_PRIMALSEPARATION TRUE 110 #define DEFAULT_EARLYTERM TRUE 111 #define DEFAULT_ADDVIOLATIONCONS FALSE 112 #define DEFAULT_ADDVIOLCONSHDLR FALSE 113 #define DEFAULT_CONSHDLRUSENORM TRUE 114 #define DEFAULT_USEOBJUB FALSE 115 #define DEFAULT_USEOBJLB FALSE 116 #define DEFAULT_SUBSCIPFAST TRUE 117 #define DEFAULT_OUTPUT FALSE 118 #define DEFAULT_RANDSEED 101 120 #define NROWSTOOSMALL 5 121 #define NCOLSTOOSMALL 5 123 #define EPSILONVALUE 1e-03 124 #define BETAEPSILONVALUE 1e-02 125 #define STALLNODELIMIT 1000LL 126 #define CONSHDLRFULLNORM FALSE 127 #define MINEFFICACY 0.05 128 #define MAXNSOLS 1000 129 #define OBJWEIGHTRANGE 0.01 132 #define BOUNDSWITCH 0.9999 134 #define POSTPROCESS TRUE 135 #define MINFRAC 0.0009 136 #define MAXFRAC 0.9991 137 #define FIXINTEGRALRHS FALSE 138 #define MAKECONTINTEGRAL FALSE 139 #define MAXWEIGHTRANGE 1e+05 141 #define MAXAGGRLEN(nvars) nvars 208 unsigned int ntotalrows;
240 #define CONSHDLR_NAME "violatedCuts" 241 #define CONSHDLR_DESC "only allow solutions corresponding to violated cuts" 244 struct SCIP_ConshdlrData
284 assert( mipdata != NULL );
285 subscip = mipdata->subscip;
286 assert( subscip != NULL );
287 assert( violated != NULL );
295 if ( mipdata->conshdlrusenorm )
298 if ( mipdata->conshdlrfullnorm )
314 SCIP_CALL(
computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
316 #ifdef SCIP_MORE_DEBUG 317 for (j = 0; j < (
unsigned int) nvars; ++j)
331 for (j = 0; j < (
unsigned int) nvars; ++j)
336 cutsqrnorm += SQR(cutcoefs[j]);
339 norm = SQRT(cutsqrnorm);
345 switch ( mipdata->normtype )
349 for (j = 0; j < mipdata->ncols; ++j)
351 var = mipdata->alpha[j];
359 cutsqrnorm += SQR(val);
362 norm = SQRT(cutsqrnorm);
365 for (j = 0; j < mipdata->ncols; ++j)
367 var = mipdata->alpha[j];
381 for (j = 0; j < mipdata->ncols; ++j)
383 var = mipdata->alpha[j];
396 for (j = 0; j < mipdata->ncols; ++j)
398 var = mipdata->alpha[j];
413 SCIPerrorMessage(
"invalid efficacy norm parameter '%c'\n", mipdata->normtype);
426 for (j = 0; j < mipdata->ncols; ++j)
428 var = mipdata->alpha[j];
444 SCIPdebugMsg(scip,
"Violated cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
448 SCIPdebugMsg(scip,
"Rejected cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
464 assert( scip != NULL );
465 assert( conshdlr != NULL );
467 assert( conshdlrdata != NULL );
482 assert( scip != NULL );
483 assert( conshdlr != NULL );
484 assert( result != NULL );
489 assert( conshdlrdata != NULL );
506 assert( result != NULL );
523 assert( scip != NULL );
524 assert( conshdlr != NULL );
525 assert( sol != NULL );
526 assert( result != NULL );
529 assert( conshdlrdata != NULL );
562 conshdlrdata->mipdata = mipdata;
566 -1000000, -1000000, 100,
FALSE,
567 consEnfolpViolatedCuts, consEnfopsViolatedCuts, consCheckViolatedCuts, consLockViolatedCuts,
570 assert(conshdlr != NULL);
609 assert( nvars == 0 || cutcoefs != NULL );
610 assert( nvars == 0 || varsolvals != NULL );
611 assert( cutinds != NULL );
612 assert( cutvals != NULL );
613 assert( cutlen != NULL );
614 assert( cutact != NULL );
615 assert( cutnorm != NULL );
624 for (v = 0; v < nvars; ++v)
629 act += val * varsolvals[v];
630 cutsqrnorm += SQR(val);
632 cutvals[len++] = val;
635 norm = SQRT(cutsqrnorm);
638 for (v = 0; v < nvars; ++v)
643 act += val * varsolvals[v];
647 cutvals[len++] = val;
652 for (v = 0; v < nvars; ++v)
657 act += val * varsolvals[v];
660 cutvals[len++] = val;
665 for (v = 0; v < nvars; ++v)
670 act += val * varsolvals[v];
672 cutvals[len++] = val;
747 assert( scip != NULL );
748 assert( lhs != NULL );
749 assert( rhs != NULL );
750 assert( col != NULL );
764 assert( row != NULL );
771 assert( 0 <= pos && pos < (
int) mipdata->nrows );
775 lhs[pos] += sigma * colvals[i] * offset;
779 rhs[pos] += sigma * colvals[i] * offset;
783 if ( sepadata->useobjub || sepadata->useobjlb )
786 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
802 l = *ub/sigma + offset;
808 *ub = *lb/sigma + offset;
817 *lb = *lb/sigma + offset;
820 *ub = *ub/sigma + offset;
822 *primsol = *primsol/sigma + offset;
848 assert( maxrowsize > 0 );
849 assert( minrowsize < INT_MAX );
850 assert( minrowsize <= maxrowsize );
851 assert( minrowsize <= rowsize && rowsize <= maxrowsize );
853 if ( minrowsize == maxrowsize )
858 return 1.0 - a * ((
SCIP_Real) (maxrowsize - rowsize));
1017 unsigned int nshifted;
1018 unsigned int ncomplemented;
1019 unsigned int ncontconverted;
1020 unsigned int nintconverted;
1021 unsigned int nlbounds;
1022 unsigned int nubounds;
1034 int minrowsize = INT_MAX;
1037 assert( scip != NULL );
1038 assert( sepadata != NULL );
1040 assert( mipdata->subscip == NULL );
1044 assert( ncols > 0 && nrows > 0 );
1048 mipdata->nrows = (
unsigned int) nrows;
1049 mipdata->ncols = (
unsigned int) ncols;
1050 mipdata->ntotalrows = mipdata->nrows;
1052 if ( sepadata->useobjub || sepadata->useobjlb )
1053 mipdata->ntotalrows = mipdata->nrows + 1;
1055 assert(mipdata->ntotalrows <= INT_MAX);
1056 ntotalrows = (int) mipdata->ntotalrows;
1059 mipdata->conshdlrusenorm = sepadata->conshdlrusenorm;
1063 subscip = mipdata->subscip;
1067 if ( sepadata->addviolconshdlr )
1094 for (i = 0; i < nrows; ++i)
1100 assert( row != NULL );
1117 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 &&
SCIProwGetAge(row) > sepadata->maxrowage )
1121 if ( sepadata->onlyrankone )
1153 assert( maxrowsize > 0 );
1154 assert( minrowsize < INT_MAX );
1157 if ( sepadata->useobjub )
1159 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1168 if ( sepadata->useobjlb )
1170 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1190 for (j = 0; j < ncols; ++j)
1196 assert( col != NULL );
1198 assert( var != NULL );
1218 mipdata->iscomplemented[j] =
FALSE;
1219 mipdata->isshifted[j] =
FALSE;
1228 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1231 if (
SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac )
1242 if ( ub[j] - primsol[j] < primsol[j] - lb[j] )
1273 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1276 if (
SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac )
1295 SCIP_CALL(
transformColumn(scip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1296 mipdata->iscomplemented[j] =
TRUE;
1297 mipdata->coltype[j] =
colAtUb;
1307 SCIP_CALL(
transformColumn(scip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1309 mipdata->isshifted[j] =
TRUE;
1316 mipdata->coltype[j] =
colAtLb;
1326 SCIP_CALL(
transformColumn(scip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1328 mipdata->iscomplemented[j] =
TRUE;
1334 mipdata->coltype[j] =
colAtLb;
1346 if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1348 SCIPdebugMsg(scip,
"Converted %u fractional integral variables to have integral value.\n", nintconverted);
1350 if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1352 SCIPdebugMsg(scip,
"Converted %u integral variables to be continuous.\n", ncontconverted);
1355 SCIPdebugMsg(scip,
"original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n",
1357 nshifted, ncomplemented, nlbounds, nubounds);
1360 if ( sepadata->skipmultbounds )
1367 for (i = 0; i < nrows; ++i)
1372 assert( row != NULL );
1374 mipdata->ylhs[i] = NULL;
1375 mipdata->yrhs[i] = NULL;
1382 if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 &&
SCIProwGetAge(row) > sepadata->maxrowage )
1386 if ( sepadata->onlyrankone )
1393 if (
SCIPisEQ(scip, lhs[i], rhs[i]) )
1395 SCIP_Real weight = -sepadata->objweight;
1401 if ( sepadata->objweightsize )
1411 #ifdef SCIP_MORE_DEBUG 1421 #ifdef SCIP_MORE_DEBUG 1437 if ( sepadata->objweightsize )
1440 weight = -sepadata->objweight;
1443 if ( ! sepadata->onlyactiverows || isactive )
1452 #ifdef SCIP_MORE_DEBUG 1468 if ( sepadata->objweightsize )
1471 weight = -sepadata->objweight;
1474 if ( ! sepadata->onlyactiverows || isactive )
1482 #ifdef SCIP_MORE_DEBUG 1489 assert( (
int) cnt <= 2 * nrows );
1493 if ( sepadata->useobjub || sepadata->useobjlb )
1497 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1498 mipdata->ylhs[mipdata->nrows] = NULL;
1499 mipdata->yrhs[mipdata->nrows] = NULL;
1502 if ( sepadata->objweightsize )
1505 weight = -sepadata->objweight;
1508 if ( sepadata->useobjub && !
SCIPisInfinity(scip, rhs[mipdata->nrows]) )
1516 #ifdef SCIP_MORE_DEBUG 1517 SCIPdebugMsg(scip,
"Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight);
1522 if ( sepadata->useobjlb && !
SCIPisInfinity(scip, -lhs[mipdata->nrows]) )
1530 #ifdef SCIP_MORE_DEBUG 1531 SCIPdebugMsg(scip,
"Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight);
1535 assert( (
int) cnt <= 2 * ntotalrows );
1542 for (j = 0; j < ncols; ++j)
1544 mipdata->z[j] = NULL;
1545 mipdata->alpha[j] = NULL;
1546 mipdata->fracalpha[j] = NULL;
1552 if ( sepadata->objlone )
1559 SCIP_CALL(
SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj,
1592 assert( (
int) cnt <= 2 * ncols );
1593 assert( (
int) ucnt <= ncols );
1596 if ( sepadata->objlone )
1598 SCIP_CALL(
SCIPcreateVar(subscip, &(mipdata->beta),
"beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0,
1603 SCIP_CALL(
SCIPcreateVar(subscip, &(mipdata->beta),
"beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
1612 mipdata->n += cnt + ucnt + 2;
1620 for (j = 0; j < ncols; ++j)
1630 assert( cols[j] != NULL );
1635 if ( mipdata->iscomplemented[j] )
1647 assert( row != NULL );
1654 assert( 0 <= pos && pos < nrows );
1656 if ( mipdata->ylhs[pos] != NULL )
1658 consvars[nconsvars] = mipdata->ylhs[pos];
1659 consvals[nconsvars] = -sigma * colvals[i];
1662 if ( mipdata->yrhs[pos] != NULL )
1664 consvars[nconsvars] = mipdata->yrhs[pos];
1665 consvals[nconsvars] = sigma * colvals[i];
1668 assert( nconsvars <= (
int) mipdata->n );
1671 if ( mipdata->z[j] != NULL )
1674 consvars[nconsvars] = mipdata->z[j];
1675 consvals[nconsvars] = 1.0;
1678 assert( nconsvars <= (
int) mipdata->n );
1681 consvars[nconsvars] = mipdata->alpha[j];
1682 consvals[nconsvars] = -1.0;
1684 assert( nconsvars <= (
int) mipdata->n );
1687 consvars[nconsvars] = mipdata->fracalpha[j];
1688 consvals[nconsvars] = -1.0;
1690 assert( nconsvars <= (
int) mipdata->n );
1696 if ( mipdata->ylhs[mipdata->nrows] != NULL )
1698 assert( sepadata->useobjlb );
1699 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1705 if ( mipdata->yrhs[mipdata->nrows] != NULL )
1707 assert( sepadata->useobjub );
1708 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1728 assert( cols[j] != NULL );
1733 if ( mipdata->iscomplemented[j] )
1745 assert( row != NULL );
1752 assert( 0 <= pos && pos < nrows );
1754 if ( mipdata->ylhs[pos] != NULL )
1756 consvars[nconsvars] = mipdata->ylhs[pos];
1757 consvals[nconsvars] = -sigma * colvals[i];
1760 if ( mipdata->yrhs[pos] != NULL )
1762 consvars[nconsvars] = mipdata->yrhs[pos];
1763 consvals[nconsvars] = sigma * colvals[i];
1766 assert( nconsvars <= (
int) mipdata->n );
1773 if ( mipdata->ylhs[mipdata->nrows] )
1775 assert( sepadata->useobjlb );
1776 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1782 if ( mipdata->yrhs[mipdata->nrows] )
1784 assert( sepadata->useobjub );
1785 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1808 assert( (
int) cnt <= ncols );
1815 for (i = 0; i < nrows; ++i)
1817 assert( rows[i] != NULL );
1824 if ( mipdata->ylhs[i] != NULL && !
SCIPisZero(scip, lhs[i]) )
1827 consvars[nconsvars] = mipdata->ylhs[i];
1828 consvals[nconsvars] = -lhs[i];
1832 if ( mipdata->yrhs[i] != NULL && !
SCIPisZero(scip, rhs[i]) )
1835 consvars[nconsvars] = mipdata->yrhs[i];
1836 consvals[nconsvars] = rhs[i];
1839 assert( nconsvars <= (
int) mipdata->n );
1842 if ( sepadata->useobjub || sepadata->useobjlb )
1845 if ( mipdata->ylhs[mipdata->nrows] != NULL && !
SCIPisZero(scip, lhs[mipdata->nrows]) )
1847 assert( sepadata->useobjlb );
1849 consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1850 consvals[nconsvars] = -lhs[mipdata->nrows];
1855 if ( mipdata->yrhs[mipdata->nrows] != NULL && !
SCIPisZero(scip, rhs[mipdata->nrows]) )
1857 assert( sepadata->useobjub );
1859 consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1860 consvals[nconsvars] = rhs[mipdata->nrows];
1863 assert( nconsvars <= (
int) mipdata->n );
1867 for (j = 0; j < ncols; ++j)
1870 if ( mipdata->z[j] != NULL && !
SCIPisZero(scip, ub[j]) )
1874 consvars[nconsvars] = mipdata->z[j];
1875 consvals[nconsvars] = ub[j];
1877 assert( nconsvars <= (
int) mipdata->n );
1881 consvars[nconsvars] = mipdata->beta;
1882 consvals[nconsvars] = -1.0;
1886 consvars[nconsvars] = mipdata->fracbeta;
1887 consvals[nconsvars] = -1.0;
1889 assert( nconsvars <= (
int) mipdata->n );
1899 if ( sepadata->primalseparation )
1903 if ( bestsol != NULL )
1906 for (j = 0; j < ncols; ++j)
1908 if ( mipdata->alpha[j] != NULL )
1914 consvars[nconsvars] = mipdata->alpha[j];
1915 consvals[nconsvars] = val;
1917 assert( nconsvars <= (
int) mipdata->n );
1920 consvars[nconsvars] = mipdata->beta;
1921 consvals[nconsvars] = -1.0;
1934 if ( sepadata->addviolationcons )
1937 for (j = 0; j < ncols; ++j)
1939 if ( mipdata->alpha[j] != NULL )
1941 consvars[nconsvars] = mipdata->alpha[j];
1942 consvals[nconsvars] = primsol[j];
1944 assert( nconsvars <= (
int) mipdata->n );
1947 consvars[nconsvars] = mipdata->beta;
1948 consvals[nconsvars] = -1.0;
1959 SCIPdebugMsg(scip,
"Subscip has %u vars (%d integral, %d continuous), %u conss.\n",
1974 #ifdef SCIP_WRITEPROB 1977 sepadata->objlone ?
"_l1" :
"",
1978 sepadata->addviolationcons ?
"_vc" :
"",
1979 sepadata->skipmultbounds ?
"_ub" :
"",
1980 sepadata->primalseparation ?
"_ps" :
"",
2001 assert( sepadata != NULL );
2002 assert( mipdata != NULL );
2003 assert( success != NULL );
2007 subscip = mipdata->subscip;
2008 assert( subscip != NULL );
2011 if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr )
2033 if ( sepadata->output )
2045 if ( sepadata->subscipfast )
2063 #ifdef SCIP_DISABLED_CODE 2074 if ( sepadata->subscipfast )
2140 assert( scip != NULL );
2141 assert( sepadata != NULL );
2142 assert( mipdata != NULL );
2143 assert( success != NULL );
2147 subscip = mipdata->subscip;
2159 if ( sepadata->timelimit < timelimit )
2163 if ( sepadata->memorylimit < memorylimit )
2172 if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 )
2176 assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 );
2178 nodelimit =
MAX(sepadata->minnodelimit, nodelimit);
2179 nodelimit = MIN(sepadata->maxnodelimit, nodelimit);
2181 assert( nodelimit >= 0 );
2184 SCIPdebugMsg(scip,
"Solving sub-SCIP (time limit: %f mem limit: %f node limit: %" SCIP_LONGINT_FORMAT
") ...\n", timelimit, memorylimit, nodelimit);
2187 if( !sepadata->output )
2193 if ( ! sepadata->earlyterm )
2204 SCIPwarningMessage(scip,
"Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2214 if ( sepadata->output )
2230 SCIPerrorMessage(
"Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2250 SCIPwarningMessage(scip,
"Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2265 if ( sepadata->output )
2277 SCIPerrorMessage(
"Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2284 SCIPdebugMsg(scip,
"Continue solving separation problem ...\n");
2297 SCIPwarningMessage(scip,
"Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2308 if ( sepadata->output )
2324 SCIPerrorMessage(
"Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2389 assert( scip != NULL );
2390 assert( mipdata != NULL );
2391 assert( sepadata != NULL );
2392 assert( cutcoefs != NULL );
2393 assert( cutrhs != NULL );
2394 assert( localrowsused != NULL );
2395 assert( cutrank != NULL );
2396 assert( success != NULL );
2398 subscip = mipdata->subscip;
2399 assert( subscip != NULL );
2405 assert( nrows == (
int) mipdata->nrows );
2406 assert( ncols == (
int) mipdata->ncols );
2410 *localrowsused =
FALSE;
2412 *localboundsused =
FALSE;
2418 for (i = 0; i < nrows; ++i)
2424 assert( row != NULL );
2429 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2434 if ( mipdata->ylhs[i] != NULL )
2438 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2446 if ( mipdata->yrhs[i] != NULL )
2450 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2461 if ( absweight > maxabsweight )
2462 maxabsweight = absweight;
2466 if ( sepadata->useobjub || sepadata->useobjlb )
2470 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2472 if ( mipdata->ylhs[mipdata->nrows] != NULL )
2474 val =
SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
2480 if ( mipdata->yrhs[mipdata->nrows] != NULL )
2482 val =
SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
2490 if ( absweight > maxabsweight )
2491 maxabsweight = absweight;
2495 for (i = 0; i < nrows; ++i)
2503 assert( row != NULL );
2508 assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2515 if ( mipdata->ylhs[i] != NULL )
2520 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2529 if ( mipdata->yrhs[i] != NULL )
2534 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2558 assert( rowcols[j] != NULL );
2561 assert( var != NULL );
2566 assert( 0 <= idx && idx < nvars );
2568 cutcoefs[idx] += weight * rowvals[j];
2586 (*cutrhs) += weight * val;
2598 if ( sepadata->useobjub || sepadata->useobjlb )
2604 assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2606 if ( mipdata->ylhs[mipdata->nrows] != NULL )
2608 val =
SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
2610 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2619 if ( mipdata->yrhs[mipdata->nrows] != NULL )
2621 val =
SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
2623 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2638 for (j = 0; j < ncols; ++j)
2642 cutcoefs[j] += weight * obj;
2660 (*cutrhs) += weight * val;
2665 for (j = 0; j < ncols; ++j)
2667 assert( cols[j] != NULL );
2668 if ( mipdata->z[j] != NULL )
2675 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
2686 assert( var != NULL );
2692 assert( 0 <= idx && idx < nvars );
2695 if ( mipdata->iscomplemented[j] )
2711 *localboundsused =
TRUE;
2714 cutcoefs[idx] -= val;
2715 *cutrhs -= lbnd * val;
2730 *localboundsused =
TRUE;
2733 cutcoefs[idx] += val;
2734 *cutrhs += ubnd * val;
2741 for (j = 0; j < nvars; ++j)
2747 assert( var != NULL );
2753 assert( pos < ncols );
2758 if ( mipdata->iscomplemented[pos] )
2760 assert( ! mipdata->isshifted[pos] );
2783 *localboundsused =
TRUE;
2791 *cutrhs += ubnd * val;
2816 *localboundsused =
TRUE;
2824 *cutrhs -= lbnd * val;
2884 assert( scip != NULL );
2885 assert( sepadata != NULL );
2886 assert( mipdata != NULL );
2887 assert( sol != NULL );
2888 assert( cutcoefs != NULL );
2889 assert( cutinds != NULL );
2890 assert( cutvals != NULL );
2891 assert( varsolvals != NULL );
2892 assert( weights != NULL );
2893 assert( nprevrows != NULL );
2894 assert( prevrows != NULL );
2895 assert( cutoff != NULL );
2896 assert( ngen != NULL );
2902 localrowsused =
FALSE;
2903 localboundsused =
FALSE;
2908 SCIP_CALL(
computeCut(scip, sepa, mipdata, sepadata, sol, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
2909 cutislocal = localrowsused || localboundsused;
2920 for (k = 0; k < nvars; ++k)
2921 cutact += cutcoefs[k] * varsolvals[k];
2923 #ifdef SCIP_DISABLED_CODE 2935 subscip = mipdata->subscip;
2936 assert( subscip != NULL );
2941 for (j = 0; j < mipdata->ncols; ++j)
2946 assert( mipdata->alpha[j] != NULL );
2956 contVarShifted =
TRUE;
2959 assert( mipdata->beta != NULL );
2963 assert( contVarShifted ||
SCIPisFeasEQ(scip, obj, cutact - cutrhs) );
2975 cutinds, cutvals, &cutlen, &cutact, &cutnorm) );
2977 SCIPdebugMsg(scip,
"act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm);
2984 if ( violated || (sepadata->usecutpool && ! cutislocal ) )
2993 for( k = 0; k < cutlen; ++k )
3008 assert( violated || sepadata->usecutpool );
3016 for (k = 0; k < *nprevrows; ++k)
3020 assert( prevrows[k] != NULL );
3028 if ( k >= *nprevrows )
3030 prevrows[*nprevrows] = cut;
3033 SCIPdebugMsg(scip,
" -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
3041 if ( sepadata->output )
3083 int* boundsfortrans,
3107 assert( scip != NULL );
3108 assert( sepadata != NULL );
3109 assert( mipdata != NULL );
3110 assert( sol != NULL );
3111 assert( cutcoefs != NULL );
3112 assert( cutinds != NULL );
3113 assert( cutvals != NULL );
3114 assert( varsolvals != NULL );
3115 assert( weights != NULL );
3116 assert( nprevrows != NULL );
3117 assert( prevrows != NULL );
3118 assert( cutoff != NULL );
3119 assert( ngen != NULL );
3122 subscip = mipdata->subscip;
3123 assert( subscip != NULL );
3126 assert( nrows > 0 );
3127 assert( (
int) mipdata->nrows == nrows );
3137 for (k = 0; k < nrows; ++k)
3142 if ( mipdata->ylhs[k] != NULL )
3149 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
3155 if ( mipdata->yrhs[k] != NULL )
3162 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
3172 if ( sepadata->cmirownbounds )
3176 assert( boundsfortrans != NULL );
3177 assert( boundtypesfortrans != NULL );
3179 if ( sepadata->allowlocal )
3185 for (k = 0; k < nvars; ++k)
3191 assert( var != NULL );
3197 assert( pos < (
int) mipdata->ncols );
3200 boundsfortrans[k] = typefortrans;
3213 if ( ! mipdata->iscomplemented[pos] )
3220 if ( mipdata->iscomplemented[pos] )
3231 sepadata->allowlocal, 2, (
int)
MAXAGGRLEN(nvars), &success) );
3237 boundtypesfortrans,
MINFRAC,
MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy,
3238 &cutrank, &cutislocal, &success) );
3240 assert( sepadata->allowlocal || !cutislocal );
3241 SCIPdebugMsg(scip,
"CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3247 if( success && (
SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3257 for( k = 0; k < cutnnz; ++k )
3270 if ( sepadata->output )
3294 SCIPdebugMsg(scip,
" -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3304 for (k = 0; k < *nprevrows; ++k)
3308 assert( prevrows[k] != NULL );
3316 if ( k >= *nprevrows )
3318 prevrows[*nprevrows] = cut;
3321 SCIPdebugMsg(scip,
" -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3329 if ( sepadata->output )
3347 SCIPdebugMsg(scip,
" -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3348 name, cutefficacy, cutrhs);
3395 assert( scip != NULL );
3396 assert( sepadata != NULL );
3397 assert( mipdata != NULL );
3398 assert( sol != NULL );
3399 assert( cutcoefs != NULL );
3400 assert( cutinds != NULL );
3401 assert( cutvals != NULL );
3402 assert( varsolvals != NULL );
3403 assert( weights != NULL );
3404 assert( nprevrows != NULL );
3405 assert( prevrows != NULL );
3406 assert( cutoff != NULL );
3407 assert( ngen != NULL );
3410 subscip = mipdata->subscip;
3411 assert( subscip != NULL );
3414 assert( nrows > 0 );
3415 assert( (
int) mipdata->nrows == nrows );
3425 for (k = 0; k < nrows; ++k)
3430 if ( mipdata->ylhs[k] != NULL )
3437 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
3443 if ( mipdata->yrhs[k] != NULL )
3450 assert( sepadata->skipmultbounds ||
SCIPisFeasLT(subscip, val, 1.0) );
3463 sepadata->allowlocal, 1, (
int)
MAXAGGRLEN(nvars), &success) );
3469 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
3471 assert( sepadata->allowlocal || !cutislocal );
3472 SCIPdebugMsg(scip,
"Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3478 if( success && (
SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3488 for( k = 0; k < cutnnz; ++k )
3501 if ( sepadata->output )
3525 SCIPdebugMsg(scip,
" -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3535 for (k = 0; k < *nprevrows; ++k)
3539 assert( prevrows[k] != NULL );
3547 if ( k >= *nprevrows )
3549 prevrows[*nprevrows] = cut;
3552 SCIPdebugMsg(scip,
" -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3560 if ( sepadata->output )
3578 SCIPdebugMsg(scip,
" -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3579 name, cutefficacy, cutrhs);
3613 int* boundsfortrans;
3621 assert( scip != NULL );
3622 assert( sepadata != NULL );
3623 assert( mipdata != NULL );
3624 assert( cutoff != NULL );
3625 assert( ngen != NULL );
3627 subscip = mipdata->subscip;
3628 assert( subscip != NULL );
3644 SCIPdebugMsg(scip,
"Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg);
3652 assert(mipdata->ntotalrows <= INT_MAX);
3653 ntotalrows = (int)mipdata->ntotalrows;
3662 if ( sepadata->usecmir || sepadata->usestrongcg )
3668 if ( sepadata->usecmir && sepadata->cmirownbounds )
3675 boundsfortrans = NULL;
3676 boundtypesfortrans = NULL;
3680 for (k = 0; k < nvars; ++k)
3685 varsolvals[k] = 0.0;
3690 for (s = 0; s < nsols; ++s)
3696 if ( sepadata->usecmir )
3698 SCIP_CALL(
createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
3699 boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) );
3702 if ( sepadata->usestrongcg )
3704 SCIP_CALL(
createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
3705 &nprevrows, prevrows, cutoff, ngen) );
3708 if ( ! sepadata->usecmir && ! sepadata->usestrongcg )
3710 SCIP_CALL(
createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights,
3711 &nprevrows, prevrows, cutoff, ngen) );
3713 assert(! sepadata->usecmir && ! sepadata->usestrongcg);
3716 assert( nprevrows <= 2 * nsols );
3717 assert( sepadata->usecmir || nprevrows <= nsols );
3718 assert( sepadata->usestrongcg || nprevrows <= nsols );
3721 for (k = 0; k < nprevrows; ++k)
3726 if ( sepadata->usecmir || sepadata->usestrongcg )
3756 assert( scip != NULL );
3757 assert( sepa != NULL );
3758 assert( mipdata != NULL );
3762 assert( sepadata != NULL );
3766 subscip = mipdata->subscip;
3767 assert( subscip != NULL );
3769 for (j = 0; j < mipdata->ncols; ++j)
3773 assert( mipdata->alpha[j] != NULL );
3781 for (i = 0; i < mipdata->nrows; ++i)
3783 if ( mipdata->ylhs[i] != NULL )
3787 if ( mipdata->yrhs[i] != NULL )
3793 if ( sepadata->useobjub || sepadata->useobjlb )
3795 if ( mipdata->yrhs[mipdata->nrows] )
3799 if ( mipdata->ylhs[mipdata->nrows] )
3805 for (j = 0; j < mipdata->ncols; ++j)
3807 if ( mipdata->z[j] != NULL )
3840 assert(sepadata != NULL);
3855 assert(sepadata != NULL);
3866 assert( scip != NULL );
3867 assert( sepa != NULL );
3883 assert( scip != NULL );
3884 assert( sepa != NULL );
3889 assert( sepadata != NULL );
3914 assert( scip != NULL );
3915 assert( sepa != NULL );
3917 assert( result != NULL );
3923 assert(sepadata != NULL);
3932 if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
3937 if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3938 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3954 if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) )
3957 "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n");
3961 sepadata->allowlocal = allowlocal;
3970 if ( sepadata->decisiontree )
3978 if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 )
3980 else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 )
3982 else if ( 136 < nrows && nrows <= 332 && ncols <= 143 )
3984 else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 )
3986 else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 )
3988 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 )
3990 else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 )
3992 else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 )
3994 else if ( 875 < nrows && nrows <= 1676 && 0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 )
3996 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 )
3998 else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 )
4000 else if ( nrows > 8146 && firstlptime > 6.25 )
4012 SCIPdebugMsg(scip,
"separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows);
4016 mipdata->subscip = NULL;
4017 mipdata->alpha = NULL;
4018 mipdata->fracalpha = NULL;
4019 mipdata->beta = NULL;
4020 mipdata->fracbeta = NULL;
4021 mipdata->coltype = NULL;
4022 mipdata->iscomplemented = NULL;
4023 mipdata->isshifted = NULL;
4024 mipdata->ylhs = NULL;
4025 mipdata->yrhs = NULL;
4027 mipdata->normtype =
' ';
4030 mipdata->scip = scip;
4031 mipdata->sepa = sepa;
4062 else if ( ngen > 0 )
4092 assert(sepa != NULL);
4102 "maximal number of cgmip separation rounds per node (-1: unlimited)",
4106 "separating/" SEPA_NAME "/maxroundsroot",
4107 "maximal number of cgmip separation rounds in the root node (-1: unlimited)",
4112 "maximal depth at which the separator is applied (-1: unlimited)",
4116 "separating/" SEPA_NAME "/decisiontree",
4117 "Use decision tree to turn separation on/off?",
4122 "time limit for sub-MIP",
4127 "memory limit for sub-MIP",
4131 "separating/" SEPA_NAME "/minnodelimit",
4132 "minimum number of nodes considered for sub-MIP (-1: unlimited)",
4136 "separating/" SEPA_NAME "/maxnodelimit",
4137 "maximum number of nodes considered for sub-MIP (-1: unlimited)",
4142 "bounds on the values of the coefficients in the CG-cut",
4146 "separating/" SEPA_NAME "/onlyactiverows",
4147 "Use only active rows to generate cuts?",
4152 "maximal age of rows to consider if onlyactiverows is false",
4157 "Separate only rank 1 inequalities w.r.t. CG-MIP separator?",
4162 "Generate cuts for problems with only integer variables?",
4167 "Convert some integral variables to be continuous to reduce the size of the sub-MIP?",
4171 "separating/" SEPA_NAME "/contconvfrac",
4172 "fraction of integral variables converted to be continuous (if contconvert)",
4177 "minimum number of integral variables before some are converted to be continuous",
4182 "Convert some integral variables attaining fractional values to have integral value?",
4187 "fraction of frac. integral variables converted to have integral value (if intconvert)",
4192 "minimum number of integral variables before some are converted to have integral value",
4196 "separating/" SEPA_NAME "/skipmultbounds",
4197 "Skip the upper bounds on the multipliers in the sub-MIP?",
4202 "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?",
4207 "weight used for the row combination coefficient in the sub-MIP objective",
4211 "separating/" SEPA_NAME "/objweightsize",
4212 "Weight each row by its size?",
4217 "should generated cuts be removed from the LP if they are no longer tight?",
4222 "use CMIR-generator (otherwise add cut directly)?",
4227 "use strong CG-function to strengthen cut?",
4231 "separating/" SEPA_NAME "/cmirownbounds",
4232 "tell CMIR-generator which bounds to used in rounding?",
4237 "use cutpool to store CG-cuts even if the are not efficient?",
4241 "separating/" SEPA_NAME "/primalseparation",
4242 "only separate cuts that are tight for the best feasible solution?",
4247 "terminate separation if a violated (but possibly sub-optimal) cut has been found?",
4251 "separating/" SEPA_NAME "/addviolationcons",
4252 "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?",
4256 "separating/" SEPA_NAME "/addviolconshdlr",
4257 "add constraint handler to filter out violated cuts?",
4261 "separating/" SEPA_NAME "/conshdlrusenorm",
4262 "should the violation constraint handler use the norm of a cut to check for feasibility?",
4267 "Use upper bound on objective function (via primal solution)?",
4272 "Use lower bound on objective function (via primal solution)?",
4277 "Should the settings for the sub-MIP be optimized for speed?",
4282 "Should information about the sub-MIP and cuts be displayed?",
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum SCIP_BoundType SCIP_BOUNDTYPE
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
#define DEFAULT_INTCONVERT
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIProwGetAge(SCIP_ROW *row)
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
static SCIP_RETCODE createCGCutCMIR(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_CMIROWNBOUNDS
enum CGMIP_ColType CGMIP_COLTYPE
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSFREE(consFreeViolatedCuts)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
int SCIProwGetNLPNonz(SCIP_ROW *row)
static SCIP_DECL_SEPAINIT(sepaInitCGMIP)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
#define DEFAULT_INTCONVMIN
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
#define DEFAULT_CUTCOEFBND
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_Real SCIPcolGetObj(SCIP_COL *col)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
static SCIP_RETCODE solveSubscip(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
int SCIPvarGetProbindex(SCIP_VAR *var)
#define DEFAULT_CONTCONVMIN
#define SCIPfreeBlockMemory(scip, ptr)
static SCIP_RETCODE SCIPincludeConshdlrViolatedCut(SCIP *scip, CGMIP_MIPDATA *mipdata)
#define DEFAULT_EARLYTERM
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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_Bool SCIPisSumZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
int SCIPgetNContVars(SCIP *scip)
static SCIP_RETCODE solCutIsViolated(SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
#define MAXAGGRLEN(nvars)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
#define DEFAULT_TIMELIMIT
const char * SCIPgetProbName(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_RETCODE SCIPsolve(SCIP *scip)
#define DEFAULT_ADDVIOLATIONCONS
#define DEFAULT_DECISIONTREE
#define DEFAULT_ONLYINTVARS
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXROUNDSROOT
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
#define DEFAULT_MINNODELIMIT
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
#define DEFAULT_ONLYACTIVEROWS
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
struct CGMIP_MIPData CGMIP_MIPDATA
#define SCIPfreeBufferArrayNull(scip, ptr)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
static SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
static SCIP_DECL_CONSLOCK(consLockViolatedCuts)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
#define DEFAULT_OBJWEIGHTSIZE
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
static SCIP_RETCODE subscipSetParams(SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
#define DEFAULT_MAXROWAGE
static SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
#define DEFAULT_CONSHDLRUSENORM
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
int SCIPgetNLPRows(SCIP *scip)
#define DEFAULT_ONLYRANKONE
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define DEFAULT_SUBSCIPFAST
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
#define DEFAULT_PRIMALSEPARATION
static SCIP_Real computeObjWeightSize(int rowsize, int minrowsize, int maxrowsize)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
#define DEFAULT_SKIPMULTBOUNDS
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 SCIPincludeSepaCGMIP(SCIP *scip)
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)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
#define DEFAULT_USECUTPOOL
public data structures and miscellaneous methods
static SCIP_RETCODE createCGCutStrongCG(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
static SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
enum SCIP_Status SCIP_STATUS
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
public methods for LP management
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)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
int SCIPgetNSols(SCIP *scip)
static SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
#define DEFAULT_OBJWEIGHT
#define DEFAULT_DYNAMICCUTS
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
int SCIPgetNBinVars(SCIP *scip)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
int SCIProwGetRank(SCIP_ROW *row)
#define DEFAULT_USESTRONGCG
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
static SCIP_RETCODE freeSubscip(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata)
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, int *cutinds, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
#define DEFAULT_MAXROUNDS
#define DEFAULT_CONTCONVERT
#define DEFAULT_INTCONVFRAC
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Chvatal-Gomory cuts computed via a sub-MIP.
#define DEFAULT_ADDVIOLCONSHDLR
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIProwGetLPPos(SCIP_ROW *row)
enum SCIP_Stage SCIP_STAGE
static SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE createCGCutDirect(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen)
static SCIP_RETCODE transformColumn(SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
#define DEFAULT_MEMORYLIMIT
static SCIP_RETCODE createCGCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen)
#define DEFAULT_MAXNODELIMIT
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetNLPNonz(SCIP_COL *col)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
static SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
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_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
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_Real SCIPgetFirstLPTime(SCIP *scip)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
#define DEFAULT_CONTCONVFRAC
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
struct SCIP_SepaData SCIP_SEPADATA
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE computeCut(SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success)
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)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)