47 #define BETTERWEIGHTFORDEMANDNODES 75 #define SEPA_NAME "mcf" 76 #define SEPA_DESC "multi-commodity-flow network cut separator" 77 #define SEPA_PRIORITY -10000 79 #define SEPA_MAXBOUNDDIST 0.0 80 #define SEPA_USESSUBSCIP FALSE 81 #define SEPA_DELAY FALSE 84 #define DEFAULT_NCLUSTERS 5 85 #define DEFAULT_MAXWEIGHTRANGE 1e+06 86 #define DEFAULT_MAXTESTDELTA 20 87 #define DEFAULT_TRYNEGSCALING FALSE 88 #define DEFAULT_FIXINTEGRALRHS TRUE 89 #define DEFAULT_DYNAMICCUTS TRUE 90 #define DEFAULT_MODELTYPE 0 91 #define DEFAULT_MAXSEPACUTS 100 92 #define DEFAULT_MAXSEPACUTSROOT 200 93 #define DEFAULT_MAXINCONSISTENCYRATIO 0.02 94 #define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5 95 #define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE 96 #define DEFAULT_SEPARATESINGLENODECUTS TRUE 97 #define DEFAULT_SEPARATEFLOWCUTSET TRUE 98 #define DEFAULT_SEPARATEKNAPSACK TRUE 101 #define BOUNDSWITCH 0.5 102 #define POSTPROCESS TRUE 105 #define MAXFRAC 0.999 107 #define MAXCOLS 2000000 108 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 109 #define MINCOLROWRATIO 0.01 110 #define MAXCOLROWRATIO 100.0 111 #define MAXFLOWVARFLOWROWRATIO 100.0 112 #define MAXARCNODERATIO 100.0 113 #define MAXNETWORKS 4 114 #define MAXFLOWCANDDENSITY 0.1 115 #define MINCOMNODESFRACTION 0.5 118 #define MAXCAPACITYSLACK 0.1 119 #define UNCAPACITATEDARCSTRESHOLD 0.8 120 #define HASHSIZE_NODEPAIRS 500 132 #define MCFdebugMessage printf 136 #define MCFdebugMessage while(FALSE) printf 210 unsigned char* flowrowsigns;
213 unsigned char* capacityrowsigns;
222 int nemptycommodities;
224 int commoditysignssize;
245 int capacityrowssize;
272 int* representatives;
284 #define LHSPOSSIBLE 1u 285 #define RHSPOSSIBLE 2u 286 #define LHSASSIGNED 4u 287 #define RHSASSIGNED 8u 289 #define DISCARDED 32u 290 #define UNDIRECTED 64u 300 assert(mcfnetwork !=
NULL);
303 (*mcfnetwork)->nodeflowrows =
NULL;
304 (*mcfnetwork)->nodeflowscales =
NULL;
305 (*mcfnetwork)->nodeflowinverted =
NULL;
306 (*mcfnetwork)->arccapacityrows =
NULL;
307 (*mcfnetwork)->arccapacityscales =
NULL;
308 (*mcfnetwork)->arcsources =
NULL;
309 (*mcfnetwork)->arctargets =
NULL;
310 (*mcfnetwork)->colcommodity =
NULL;
311 (*mcfnetwork)->nnodes = 0;
312 (*mcfnetwork)->nuncapacitatedarcs = 0;
313 (*mcfnetwork)->narcs = 0;
314 (*mcfnetwork)->ncommodities = 0;
326 assert(mcfnetwork !=
NULL);
328 if( *mcfnetwork !=
NULL )
333 for( v = 0; v < (*mcfnetwork)->nnodes; v++ )
337 for( k = 0; k < (*mcfnetwork)->ncommodities; k++ )
339 if( (*mcfnetwork)->nodeflowrows[v][k] !=
NULL )
348 for( a = 0; a < (*mcfnetwork)->narcs; a++ )
350 if( (*mcfnetwork)->arccapacityrows[a] !=
NULL )
383 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
384 SCIP_Real* flowrowscalars = mcfdata->flowrowscalars;
385 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
386 int* flowcands = mcfdata->flowcands;
387 int nflowcands = mcfdata->nflowcands;
389 int* commoditysigns = mcfdata->commoditysigns;
391 int* rowcommodity = mcfdata->rowcommodity;
392 int* rownodeid = mcfdata->rownodeid;
393 SCIP_ROW** capacityrows = mcfdata->capacityrows;
402 int ncompcommodities;
409 assert(mcfnetwork !=
NULL);
411 assert(2 <= ncompnodes && ncompnodes <= mcfdata->
nnodes);
412 assert(1 <= ncomparcs && ncomparcs <= mcfdata->
narcs);
413 assert(ncommodities > 0);
417 for( v = 0; v < mcfdata->nnodes; v++ )
418 assert(compnodeid[v] == -1);
430 compcommodity[k] = -1;
437 for( i = 0; i < ncompnodes; i++ )
440 assert(0 <= v && v < mcfdata->nnodes);
445 ncompcommodities = 0;
446 for( i = 0; i < nflowcands; i++ )
452 assert(0 <= r && r < nrows);
455 if( rv >= 0 && compnodeid[rv] >= 0 )
458 assert(0 <= k && k < ncommodities);
459 if( compcommodity[k] == -1 )
461 compcommodity[k] = ncompcommodities;
472 mcfnetwork->
nnodes = ncompnodes;
473 mcfnetwork->
narcs = ncomparcs;
481 for( v = 0; v < mcfnetwork->
nnodes; v++ )
499 for( a = 0; a < mcfnetwork->
narcs; a++ )
509 for( i = 0; i < nflowcands; i++ )
515 assert(0 <= r && r < nrows);
518 if( rv >= 0 && compnodeid[rv] >= 0 )
524 rk = rowcommodity[
r];
525 assert(v < mcfnetwork->nnodes);
526 assert(0 <= rk && rk < ncommodities);
529 k = compcommodity[rk];
530 assert(0 <= k && k < mcfnetwork->ncommodities);
535 scale = flowrowscalars[
r];
538 if( commoditysigns[rk] == -1 )
546 for( a = 0; a < mcfnetwork->
narcs; a++ )
556 globala = comparcs[
a];
557 capacityrow = capacityrows[globala];
562 if( capacityrow !=
NULL)
565 assert(0 <= r && r < nrows);
567 assert((capacityrowsigns[r] &
INVERTED) == 0);
568 assert(mcfdata->rowarcid[r] == globala);
586 for( j = 0; j < rowlen; j++ )
593 if( comdemands[k] != 0.0 )
608 for( j = 0; j < rowlen; j++ )
613 if( k >= 0 && comdemands[k] == 0.0 )
625 if( mcfdata->arcsources[globala] >= 0 )
627 assert(mcfdata->arcsources[globala] < mcfdata->nnodes);
628 assert(0 <= compnodeid[mcfdata->arcsources[globala]] && compnodeid[mcfdata->arcsources[globala]] < mcfnetwork->
nnodes);
629 mcfnetwork->
arcsources[
a] = compnodeid[mcfdata->arcsources[globala]];
631 if( mcfdata->arctargets[globala] >= 0 )
633 assert(mcfdata->arctargets[globala] < mcfdata->nnodes);
634 assert(0 <= compnodeid[mcfdata->arctargets[globala]] && compnodeid[mcfdata->arctargets[globala]] < mcfnetwork->
nnodes);
635 mcfnetwork->
arctargets[
a] = compnodeid[mcfdata->arctargets[globala]];
640 for( c = 0; c < ncols; c++ )
650 for( i = 0; i < ncompnodes; i++ )
652 assert(0 <= compnodes[i] && compnodes[i] < mcfdata->nnodes);
653 assert(compnodeid[compnodes[i]] == i);
654 compnodeid[compnodes[i]] = -1;
667 void mcfnetworkPrint(
671 if( mcfnetwork ==
NULL )
678 for( v = 0; v < mcfnetwork->
nnodes; v++ )
697 for( a = 0; a < mcfnetwork->
narcs; a++ )
713 void printCommodities(
718 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
719 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
721 int* commoditysigns = mcfdata->commoditysigns;
723 int* rowcommodity = mcfdata->rowcommodity;
724 int* colarcid = mcfdata->colarcid;
725 int* rownodeid = mcfdata->rownodeid;
726 int nnodes = mcfdata->nnodes;
727 SCIP_ROW** capacityrows = mcfdata->capacityrows;
747 for( c = 0; c < ncols; c++ )
749 if( colcommodity[c] == k )
752 for( r = 0; r < nrows; r++ )
754 if( rowcommodity[r] == k )
757 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
762 if( rownodeid !=
NULL )
766 for( v = 0; v <
nnodes; v++ )
769 for( r = 0; r < nrows; r++ )
771 if( rownodeid[r] == v )
774 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
780 assert(capacityrows !=
NULL || mcfdata->narcs == 0);
783 for( a = 0; a < mcfdata->narcs; a++ )
786 if( capacityrows[a] !=
NULL )
789 assert(0 <= r && r < nrows);
792 else if( (capacityrowsigns[r] &
RHSASSIGNED) != 0 )
800 assert(colcommodity !=
NULL || ncols == 0);
803 for( c = 0; c < ncols; c++ )
805 if( colcommodity[c] == -1 )
814 for( r = 0; r < nrows; r++ )
816 assert(rowcommodity !=
NULL);
834 if( rowscores[ind2] < rowscores[ind1] )
836 else if( rowscores[ind2] > rowscores[ind1] )
849 unsigned char* flowrowsigns;
869 flowrowsigns = mcfdata->flowrowsigns;
870 flowrowscalars = mcfdata->flowrowscalars;
871 flowrowscores = mcfdata->flowrowscores;
872 flowcands = mcfdata->flowcands;
874 assert(mcfdata->nflowcands == 0);
877 for( r = 0; r < nrows; r++ )
902 absdualsol = ABS(absdualsol);
905 flowrowscalars[
r] = 0.0;
906 flowrowscores[
r] = 0.0;
927 coef = ABS(rowvals[0]);
934 for( i = 0; i < rowlen; i++ )
940 hasposcoef = hasposcoef || (rowvals[i] > 0.0);
941 hasnegcoef = hasnegcoef || (rowvals[i] < 0.0);
971 flowrowscalars[
r] = 1.0/coef;
972 flowcands[mcfdata->nflowcands] =
r;
973 mcfdata->nflowcands++;
980 if(
SCIPisEQ(scip, flowrowscalars[r], 1.0) )
981 flowrowscores[
r] += 1000.0;
984 if( hasposcoef && hasnegcoef )
985 flowrowscores[
r] += 500.0;
992 if( ncontvars == rowlen )
993 flowrowscores[
r] += 1000.0;
994 else if( nintvars + nimplintvars == rowlen )
995 flowrowscores[
r] += 500.0;
996 else if( nbinvars == rowlen )
997 flowrowscores[
r] += 100.0;
1001 flowrowscores[
r] += 10.0*rowlen/(rowlen+10.0);
1005 flowrowscores[
r] += 50.0;
1007 assert(flowrowscores[r] > 0.0);
1010 maxdualflow =
MAX(maxdualflow, absdualsol);
1023 for( i = 0; i < mcfdata->nflowcands; i++ )
1028 assert(0 <= r && r < nrows);
1033 dualsol = ABS(dualsol);
1036 assert(maxdualflow > 0.0);
1037 flowrowscores[
r] += dualsol/maxdualflow + 1.0;
1038 assert(flowrowscores[r] > 0.0);
1043 SCIPsortInd(mcfdata->flowcands, compCands, (
void*)flowrowscores, mcfdata->nflowcands);
1045 MCFdebugMessage(
"flow conservation candidates [%d]\n", mcfdata->nflowcands);
1047 for( r = 0; r < mcfdata->nflowcands; r++ )
1050 SCIPdebugMsg(scip,
"%4d [score: %2g]: %s\n", mcfdata->flowcands[r], flowrowscores[mcfdata->flowcands[r]],
1065 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1068 int nactivecommodities = mcfdata->ncommodities - mcfdata->nemptycommodities;
1071 unsigned char* capacityrowsigns;
1080 int maxcolspercommoditylimit;
1081 int *ncolspercommodity;
1082 int *maxcolspercommodity;
1092 capacityrowsigns = mcfdata->capacityrowsigns;
1093 capacityrowscores = mcfdata->capacityrowscores;
1094 capacitycands = mcfdata->capacitycands;
1096 assert(mcfdata->ncapacitycands == 0);
1106 maxcolspercommoditylimit = 2;
1109 maxcolspercommoditylimit = 1;
1112 maxcolspercommoditylimit = 2;
1115 SCIPerrorMessage(
"invalid parameter value %d for model type\n", modeltype);
1119 maxdualcapacity = 0.0;
1120 directedcandsscore = 0.0;
1121 undirectedcandsscore = 0.0;
1122 for( r = 0; r < nrows; r++ )
1132 int nposcapacitycoefs;
1133 int nnegcapacitycoefs;
1135 int ncoveredcommodities;
1140 unsigned char rowsign;
1146 capacityrowsigns[
r] = 0;
1147 capacityrowscores[
r] = 0.0;
1166 absdualsol = ABS(absdualsol);
1175 maxcolspercommodity[
r] = 0;
1180 nposcapacitycoefs = 0;
1181 nnegcapacitycoefs = 0;
1183 ncoveredcommodities = 0;
1185 sameabsflowcoef = 0.0;
1186 maxabscapacitycoef = 0.0;
1193 for( i = 0; i < rowlen; i++ )
1200 assert(colcommodity !=
NULL);
1203 k = colcommodity[c];
1204 assert(-1 <= k && k < ncommodities);
1209 abscoef = ABS(rowvals[i]);
1210 if( sameflowcoef == 0.0 )
1211 sameflowcoef = rowvals[i];
1212 else if( !
SCIPisEQ(scip, sameflowcoef, rowvals[i]) )
1214 if( sameabsflowcoef == 0.0 )
1215 sameabsflowcoef = abscoef;
1216 else if( !
SCIPisEQ(scip, sameabsflowcoef, abscoef) )
1219 if( rowvals[i] > 0.0 )
1225 if( ncolspercommodity[k] == 0 )
1226 ncoveredcommodities++;
1227 ncolspercommodity[k]++;
1228 maxcolspercommodity[
r] =
MAX(maxcolspercommodity[r], ncolspercommodity[k]);
1230 if( ncolspercommodity[k] >= 2 )
1239 abscoef = ABS(rowvals[i]);
1240 if( abscoef > maxabscapacitycoef )
1241 maxabscapacitycoef = abscoef;
1244 if( rowvals[i] > 0.0 )
1245 nposcapacitycoefs++;
1247 nnegcapacitycoefs++;
1257 if( rowsign != 0 && nposflowcoefs + nnegflowcoefs > 0 )
1261 capacityrowsigns[
r] |= rowsign;
1262 capacitycands[mcfdata->ncapacitycands] =
r;
1263 mcfdata->ncapacitycands++;
1266 capacityrowscores[
r] = 1.0;
1270 assert(ncoveredcommodities > 0);
1271 commodityexcessratio =
1272 ABS((nposflowcoefs + nnegflowcoefs)/(
SCIP_Real)ncoveredcommodities - maxcolspercommoditylimit);
1274 capacityrowscores[
r] += 1000.0 *
MAX(0.0, 2.0 - commodityexcessratio);
1281 if( (capacityrowsigns[r] &
RHSPOSSIBLE) != 0 && nnegflowcoefs == 0 && nposcapacitycoefs == 0 && nnegcapacitycoefs > 0 )
1282 capacityrowscores[
r] += 1000.0;
1283 if( (capacityrowsigns[r] &
LHSPOSSIBLE) != 0 && nposflowcoefs == 0 && nposcapacitycoefs > 0 && nnegcapacitycoefs == 0 )
1284 capacityrowscores[
r] += 1000.0;
1293 assert(nactivecommodities + 3 > 0);
1294 capacityrowscores[
r] += 2000.0 * ncoveredcommodities/(
SCIP_Real)(nactivecommodities + 3);
1297 if(
SCIPisEQ(scip, ABS(sameflowcoef), 1.0) )
1298 capacityrowscores[r] += 500.0;
1302 capacityrowscores[
r] += 250.0;
1305 if(
SCIPisEQ(scip, sameabsflowcoef, 1.0) )
1306 capacityrowscores[r] += 100.0;
1309 if( maxabscapacitycoef > 0.0 && !
SCIPisEQ(scip, maxabscapacitycoef, 1.0) )
1310 capacityrowscores[r] += 100.0;
1313 capacityrowscores[
r] += 20.0 *
MAX(nposflowcoefs, nnegflowcoefs)/
MAX(1.0,(
SCIP_Real)(nposflowcoefs + nnegflowcoefs));
1316 capacityrowscores[
r] += 10.0 *
MAX(nposcapacitycoefs, nnegcapacitycoefs)/(
SCIP_Real)(nposcapacitycoefs+nnegcapacitycoefs+1.0);
1319 if( (capacityrowsigns[r] & RHSPOSSIBLE) != 0 && !
SCIPisNegative(scip, rowrhs) )
1320 capacityrowscores[r] += 10.0;
1324 capacityrowscores[r] += 10.0;
1326 assert(capacityrowscores[r] > 0.0);
1327 SCIPdebugMsg(scip,
"row <%s>: maxcolspercommodity=%d capacityrowsign=%d nposflowcoefs=%d nnegflowcoefs=%d nposcapacitycoefs=%d nnegcapacitycoefs=%d nbadcoefs=%d nactivecommodities=%d sameflowcoef=%g -> score=%g\n",
1328 SCIProwGetName(row), maxcolspercommodity[r], capacityrowsigns[r], nposflowcoefs, nnegflowcoefs, nposcapacitycoefs, nnegcapacitycoefs, nbadcoefs, nactivecommodities, sameflowcoef, capacityrowscores[r]);
1331 maxdualcapacity =
MAX(maxdualcapacity, absdualsol);
1336 assert(maxcolspercommoditylimit == 2);
1337 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1338 undirectedcandsscore += capacityrowscores[
r];
1340 directedcandsscore += capacityrowscores[
r];
1345 SCIPdebugMsg(scip,
"row <%s>: rowsign = %d nposflowcoefs = %d nnegflowcoefs = %d -> discard\n",
1353 if( directedcandsscore > undirectedcandsscore )
1358 MCFdebugMessage(
"detected model type: %s (%g directed score, %g undirected score)\n",
1366 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1368 r = capacitycands[i];
1369 assert(0 <= r && r < nrows);
1370 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1373 if( maxcolspercommodity[r] <= maxcolspercommoditylimit )
1374 capacityrowscores[
r] -= 1000.0;
1388 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1392 r = capacitycands[i];
1393 assert(0 <= r && r < nrows);
1398 dualsol = ABS(dualsol);
1401 assert(maxdualcapacity > 0.0);
1402 capacityrowscores[
r] +=
MAX(dualsol, 0.0)/maxdualcapacity;
1403 assert(capacityrowscores[r] > 0.0);
1408 SCIPsortInd(mcfdata->capacitycands, compCands, (
void*)capacityrowscores, mcfdata->ncapacitycands);
1410 MCFdebugMessage(
"capacity candidates [%d]\n", mcfdata->ncapacitycands);
1412 for( r = 0; r < mcfdata->ncapacitycands; r++ )
1414 SCIPdebugMsg(scip,
"row %4d [score: %2g]: %s\n", mcfdata->capacitycands[r],
1415 capacityrowscores[mcfdata->capacitycands[r]],
SCIProwGetName(rows[mcfdata->capacitycands[r]]));
1435 assert(mcfdata->ncommodities <= mcfdata->commoditysignssize);
1436 if( mcfdata->ncommodities == mcfdata->commoditysignssize )
1438 mcfdata->commoditysignssize =
MAX(2*mcfdata->commoditysignssize, mcfdata->ncommodities+1);
1441 assert(mcfdata->ncommodities < mcfdata->commoditysignssize);
1444 SCIPdebugMsg(scip,
"**** creating new commodity %d ****\n", mcfdata->ncommodities);
1445 mcfdata->commoditysigns[mcfdata->ncommodities] = 0;
1446 mcfdata->ncommodities++;
1461 assert(source != target );
1462 assert(0 <= source && source < mcfdata->
nnodes);
1463 assert(0 <= target && target < mcfdata->nnodes);
1464 assert(newarcid !=
NULL);
1466 *newarcid = mcfdata->narcs;
1469 assert(mcfdata->narcs <= mcfdata->arcarraysize);
1470 if( mcfdata->narcs == mcfdata->arcarraysize )
1472 mcfdata->arcarraysize =
MAX(2*mcfdata->arcarraysize, mcfdata->narcs+1);
1478 assert(mcfdata->narcs < mcfdata->arcarraysize);
1481 if( mcfdata->capacityrowssize < mcfdata->arcarraysize )
1483 mcfdata->capacityrowssize = mcfdata->arcarraysize;
1486 assert(mcfdata->narcs < mcfdata->capacityrowssize);
1489 SCIPdebugMsg(scip,
"**** creating new arc %d: %d -> %d ****\n", mcfdata->narcs, source, target);
1491 mcfdata->arcsources[*newarcid] = source;
1492 mcfdata->arctargets[*newarcid] = target;
1493 mcfdata->nextoutarcs[*newarcid] = mcfdata->firstoutarcs[source];
1494 mcfdata->firstoutarcs[source] = *newarcid;
1495 mcfdata->nextinarcs[*newarcid] = mcfdata->firstinarcs[target];
1496 mcfdata->firstinarcs[target] = *newarcid;
1497 mcfdata->capacityrows[*newarcid] =
NULL;
1510 unsigned char rowsign,
1515 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1516 SCIP_Bool* plusflow = mcfdata->plusflow;
1517 SCIP_Bool* minusflow = mcfdata->minusflow;
1519 int* commoditysigns = mcfdata->commoditysigns;
1521 int* rowcommodity = mcfdata->rowcommodity;
1522 int* newcols = mcfdata->newcols;
1533 assert(comcolids !=
NULL);
1534 assert(ncomcolids !=
NULL);
1543 invertrow = ((rowsign &
INVERTED) != 0);
1546 assert(rowcommodity[r] == -1);
1547 assert((flowrowsigns[r] | rowsign) == flowrowsigns[r]);
1549 assert(rowsign != 0);
1555 commoditysigns[k] = +1;
1584 else if( rowlhs > 0.0 )
1601 flowrowsigns[
r] |= rowsign;
1603 SCIPdebugMsg(scip,
"adding flow row %d <%s> with sign %+d%s to commodity %d [score:%g]\n",
1605 k, mcfdata->flowrowscores[r]);
1609 rowcommodity[
r] = k;
1613 for( i = 0; i < rowlen; i++ )
1622 if( colcommodity[c] == -1 )
1624 assert(!plusflow[c]);
1625 assert(!minusflow[c]);
1627 colcommodity[c] = k;
1628 newcols[mcfdata->nnewcols] = c;
1629 mcfdata->nnewcols++;
1630 comcolids[*ncomcolids] = c;
1633 assert(colcommodity[c] == k);
1636 val = rowscale * rowvals[i];
1639 assert(!plusflow[c]);
1644 assert(!minusflow[c]);
1645 minusflow[c] =
TRUE;
1662 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1663 SCIP_Bool* plusflow = mcfdata->plusflow;
1664 SCIP_Bool* minusflow = mcfdata->minusflow;
1668 assert(mcfdata->commoditysigns[k] == 0);
1669 assert(comrows !=
NULL || ncomrows == 0);
1670 assert(comcolids !=
NULL);
1673 for( i = 0; i < ncomrows; i++ )
1677 unsigned char rowsign;
1679 assert(comrows !=
NULL);
1681 assert( row !=
NULL );
1684 assert(mcfdata->rowcommodity[r] == k);
1688 rowsign = flowrowsigns[
r];
1700 for( i = 0; i < ncomcolids; i++ )
1707 assert(mcfdata->colcommodity[c] == k);
1710 plusflow[c] = minusflow[c];
1727 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1728 SCIP_Bool* plusflow = mcfdata->plusflow;
1729 SCIP_Bool* minusflow = mcfdata->minusflow;
1732 int* rowcommodity = mcfdata->rowcommodity;
1736 assert(0 <= k && k < ncommodities);
1738 assert( ndelflowrows !=
NULL );
1739 assert( ndelflowvars !=
NULL );
1741 SCIPdebugMsg(scip,
"deleting commodity %d (%d total commodities) with %d flow rows\n", k, ncommodities, nrows);
1746 for( n = 0; n < nrows; n++ )
1757 assert(rowcommodity[r] == k);
1766 rowcommodity[
r] = -1;
1769 for( i = 0; i < rowlen; i++ )
1777 assert(colcommodity[c] == k || colcommodity[c] == -1);
1778 if(colcommodity[c] == k)
1780 colcommodity[c] = -1;
1783 plusflow[c] =
FALSE;
1784 minusflow[c] =
FALSE;
1793 if( k == ncommodities-1 )
1794 mcfdata->ncommodities--;
1796 mcfdata->nemptycommodities++;
1806 unsigned char* rowsign,
1810 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1811 SCIP_Bool* plusflow = mcfdata->plusflow;
1812 SCIP_Bool* minusflow = mcfdata->minusflow;
1814 int* rowcommodity = mcfdata->rowcommodity;
1815 int* commoditysigns = mcfdata->commoditysigns;
1820 unsigned char flowrowsign;
1821 unsigned char invflowrowsign;
1825 assert(invertcommodity !=
NULL);
1828 *invertcommodity =
FALSE;
1834 if( rowcommodity[r] != -1 )
1838 flowrowsign = flowrowsigns[
r];
1844 invflowrowsign = flowrowsign;
1850 for( j = 0; j < rowlen && (flowrowsign != 0 || invflowrowsign != 0); j++ )
1858 if( colcommodity[rowc] == k )
1861 if( plusflow[rowc] )
1864 if( rowvals[j] > 0.0 )
1875 if( minusflow[rowc] )
1878 if( rowvals[j] > 0.0 )
1890 else if( colcommodity[rowc] != -1 )
1898 if( flowrowsign != 0 )
1901 *rowsign = flowrowsign;
1902 *invertcommodity =
FALSE;
1904 else if( invflowrowsign != 0 )
1910 if( commoditysigns ==
NULL || commoditysigns[k] == 0 )
1913 *rowsign = invflowrowsign;
1914 *invertcommodity =
TRUE;
1919 *rowsign = (invflowrowsign |
INVERTED);
1920 *invertcommodity =
FALSE;
1937 unsigned char* nextrowsign,
1941 SCIP_Real* flowrowscores = mcfdata->flowrowscores;
1942 SCIP_Bool* plusflow = mcfdata->plusflow;
1943 SCIP_Bool* minusflow = mcfdata->minusflow;
1944 int* newcols = mcfdata->newcols;
1950 assert(nextrow !=
NULL);
1951 assert(nextrowsign !=
NULL);
1955 *nextinvertcommodity =
FALSE;
1960 assert(cols !=
NULL);
1963 while( mcfdata->nnewcols > 0 )
1969 unsigned char bestrowsign;
1976 c = newcols[mcfdata->nnewcols-1];
1977 mcfdata->nnewcols--;
1981 assert(plusflow[c] || minusflow[c]);
1982 if( plusflow[c] && minusflow[c] )
1988 bestinvertcommodity =
FALSE;
1993 for( i = 0; i < collen; i++ )
1996 unsigned char flowrowsign;
2002 getFlowrowFit(scip, mcfdata, row, k, &flowrowsign, &invertcommodity);
2005 if( flowrowsign != 0 )
2012 score = flowrowscores[
r];
2013 assert(score > 0.0);
2019 if( (flowrowsign &
INVERTED) != 0 )
2022 if( score > bestscore )
2025 bestrowsign = flowrowsign;
2026 bestinvertcommodity = invertcommodity;
2036 if( bestrow !=
NULL )
2038 assert(bestscore > 0.0);
2039 assert(bestrowsign != 0);
2041 *nextrowsign = bestrowsign;
2042 *nextinvertcommodity = bestinvertcommodity;
2057 int* flowcands = mcfdata->flowcands;
2084 assert(failed !=
NULL);
2093 plusflow = mcfdata->plusflow;
2094 minusflow = mcfdata->minusflow;
2095 colcommodity = mcfdata->colcommodity;
2096 rowcommodity = mcfdata->rowcommodity;
2108 for( c = 0; c < ncols; c++ )
2109 colcommodity[c] = -1;
2110 for( r = 0; r < nrows; r++ )
2111 rowcommodity[r] = -1;
2113 assert(flowcands !=
NULL || mcfdata->nflowcands == 0);
2124 for( i = 0; i < mcfdata->nflowcands; i++ )
2127 unsigned char newrowsign;
2131 assert(flowcands !=
NULL);
2133 assert(0 <= r && r < nrows);
2137 getFlowrowFit(scip, mcfdata, newrow, mcfdata->ncommodities, &newrowsign, &newinvertcommodity);
2138 if( newrowsign == 0 )
2140 assert(!newinvertcommodity);
2141 assert((newrowsign &
INVERTED) == 0);
2144 SCIPdebugMsg(scip,
" -------------------start new commodity %d--------------------- \n", mcfdata->ncommodities );
2153 if( newinvertcommodity )
2154 invertCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, comcolids, ncomcolids);
2159 comrows[
nnodes] = newrow;
2164 getNextFlowrow(scip, mcfdata, &newrow, &newrowsign, &newinvertcommodity);
2166 while( newrow !=
NULL );
2168 ncomnodes[mcfdata->ncommodities-1] =
nnodes;
2169 maxnnodes =
MAX(maxnnodes, nnodes);
2170 nflowvars += ncomcolids;
2171 SCIPdebugMsg(scip,
" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n", mcfdata->ncommodities-1, nnodes, maxnnodes);
2179 deleteCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2180 nflowrows -= ndelflowrows;
2181 nflowvars -= ndelflowvars;
2182 assert(nflowvars >= 0);
2183 assert(nflowrows >= 0);
2187 for( k = 0; k < mcfdata->ncommodities; k++ )
2199 for( i = 0; i < mcfdata->nflowcands; i++ )
2201 assert(flowcands !=
NULL);
2203 if( rowcommodity[r] == k )
2208 if( nnodes == ncomnodes[k] )
2213 assert(nnodes == ncomnodes[k]);
2214 deleteCommodity(scip, mcfdata, k, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2215 nflowrows -= ndelflowrows;
2216 nflowvars -= ndelflowvars;
2217 assert(nflowvars >= 0);
2218 assert(nflowrows >= 0);
2227 MCFdebugMessage(
"identified %d commodities (%d empty) with a maximum of %d nodes and %d flowrows, %d flowvars \n",
2228 mcfdata->ncommodities, mcfdata->nemptycommodities, maxnnodes, nflowrows, nflowvars);
2230 assert(nflowvars >= 0);
2231 assert(nflowrows >= 0);
2249 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
2252 unsigned char* flowrowsigns = mcfdata->capacityrowsigns;
2253 int* rowcommodity = mcfdata->rowcommodity;
2269 SCIP_Real* capacityrowscores = mcfdata->capacityrowscores;
2271 int *capacitycands = mcfdata->capacitycands;
2272 int ncapacitycands = mcfdata->ncapacitycands;
2274 assert(mcfdata->narcs == 0);
2275 assert(capacitycands !=
NULL || ncapacitycands == 0);
2284 colarcid = mcfdata->colarcid;
2285 rowarcid = mcfdata->rowarcid;
2288 for( c = 0; c < ncols; c++ )
2290 for( r = 0; r < nrows; r++ )
2294 for( i = 0; i < ncapacitycands; i++ )
2299 int nassignedflowvars;
2300 int nunassignedflowvars;
2303 assert(capacitycands !=
NULL);
2304 r = capacitycands[i];
2305 assert(0 <= r && r < nrows );
2306 capacityrow = rows[
r];
2308 assert(capacityrowsigns !=
NULL);
2309 assert(capacityrowscores !=
NULL);
2310 assert(rowcommodity !=
NULL);
2311 assert(flowrowsigns !=
NULL);
2315 assert((capacityrowsigns[r] &
DISCARDED) == 0);
2316 assert(capacityrowscores[r] > 0.0);
2320 assert(rowarcid[r] == -1);
2323 assert( rowcommodity[r] == -1 );
2329 nassignedflowvars = 0;
2330 nunassignedflowvars = 0;
2331 for( k = 0; k < rowlen; k++ )
2334 assert(0 <= c && c < ncols);
2335 assert(colcommodity !=
NULL);
2337 assert(-1 <= colcommodity[c] && colcommodity[c] < mcfdata->ncommodities);
2338 assert(-1 <= colarcid[c] && colarcid[c] < mcfdata->narcs);
2341 if( colcommodity[c] == -1 )
2345 if( colarcid[c] >= 0 )
2346 nassignedflowvars++;
2348 nunassignedflowvars++;
2355 if( nunassignedflowvars == 0 || nassignedflowvars >= nunassignedflowvars * 2 )
2357 SCIPdebugMsg(scip,
"discarding capacity candidate row %d <%s> [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2358 r,
SCIProwGetName(capacityrow), mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2364 assert(mcfdata->narcs <= mcfdata->capacityrowssize);
2365 if( mcfdata->narcs == mcfdata->capacityrowssize )
2367 mcfdata->capacityrowssize =
MAX(2*mcfdata->capacityrowssize, mcfdata->narcs+1);
2370 assert(mcfdata->narcs < mcfdata->capacityrowssize);
2371 assert(mcfdata->narcs < nrows);
2373 mcfdata->capacityrows[mcfdata->narcs] = capacityrow;
2376 assert(0 <= r && r < nrows);
2377 rowarcid[
r] = mcfdata->narcs;
2388 SCIPdebugMsg(scip,
"assigning capacity row %d <%s> with sign %+d to arc %d [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2390 mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2393 for( k = 0; k < rowlen; k++ )
2396 assert(0 <= rowc && rowc < ncols);
2397 assert(colcommodity !=
NULL);
2402 if( colcommodity[rowc] >= 0 && colarcid[rowc] == -1 )
2403 colarcid[rowc] = mcfdata->narcs;
2423 int* colarcid = mcfdata->colarcid;
2424 int* newcols = mcfdata->newcols;
2425 SCIP_ROW** capacityrows = mcfdata->capacityrows;
2426 SCIP_Bool* colisincident = mcfdata->colisincident;
2435 assert(!colisincident[i]);
2441 mcfdata->nnewcols = 0;
2443 for( i = 0; i < rowlen; i++ )
2455 arcid = colarcid[c];
2458 assert(arcid < mcfdata->
narcs);
2461 assert(capacityrows[arcid] !=
NULL);
2465 for( j = 0; j < capacityrowlen; j++ )
2473 if( colcommodity[caprowc] == -1 )
2475 assert(colarcid[caprowc] == -1);
2478 assert(colarcid[caprowc] <= arcid);
2481 if( colcommodity[caprowc] == basecommodity )
2485 if( !colisincident[caprowc] )
2487 assert(mcfdata->nnewcols < SCIPgetNLPCols(scip));
2488 colisincident[caprowc] =
TRUE;
2489 newcols[mcfdata->nnewcols] = caprowc;
2490 mcfdata->nnewcols++;
2504 int* basearcpattern,
2513 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2514 int* commoditysigns = mcfdata->commoditysigns;
2515 int narcs = mcfdata->narcs;
2516 int* rowcommodity = mcfdata->rowcommodity;
2517 int* colarcid = mcfdata->colarcid;
2518 int* arcpattern = mcfdata->zeroarcarray;
2531 int* overlappingarcs;
2532 int noverlappingarcs;
2537 *invertcommodity =
FALSE;
2540 for( i = 0; i <
narcs; i++ )
2541 assert(arcpattern[i] == 0);
2550 rowcom = rowcommodity[
r];
2552 rowcomsign = commoditysigns[rowcom];
2553 assert(-1 <= rowcomsign && rowcomsign <= +1);
2558 incompatible =
FALSE;
2559 noverlappingarcs = 0;
2563 for( i = 0; i < rowlen; i++ )
2573 valsign = (rowvals[i] > 0.0 ? +1 : -1);
2576 if( (flowrowsigns[r] &
INVERTED) != 0 )
2579 arcid = colarcid[c];
2588 assert(arcid < narcs);
2591 if( basearcpattern[arcid] != 0 )
2598 if( ( valsign * basearcpattern[arcid] ) > 0 )
2603 if( rowcomsign == 0 )
2606 rowcomsign = validcomsign;
2608 else if( rowcomsign != validcomsign )
2611 incompatible =
TRUE;
2622 if( arcpattern[arcid] == 0 )
2624 overlappingarcs[noverlappingarcs] = arcid;
2627 arcpattern[arcid] += valsign;
2633 for( i = 0; i < noverlappingarcs; i++ )
2639 arcid = overlappingarcs[i];
2640 assert(0 <= arcid && arcid < narcs);
2643 basenum = ABS(basearcpattern[arcid]);
2644 arcnum = ABS(arcpattern[arcid]);
2645 assert(basenum != 0.0);
2646 assert(arcnum != 0.0);
2648 if( basenum > arcnum )
2649 overlap += arcnum/basenum;
2651 overlap += basenum/arcnum;
2653 arcpattern[arcid] = 0;
2657 if( !incompatible && overlap > 0.0 )
2660 int rowarcs = rowlen - nposuncap - nneguncap;
2661 int baserowarcs = baserowlen - basenposuncap - basenneguncap;
2664 assert(overlap <= (
SCIP_Real) baserowlen);
2665 assert(noverlappingarcs >= 1);
2667 *invertcommodity = (rowcomsign == -1);
2671 if( noverlappingarcs >= 2 )
2674 assert(rowarcs >= 0 && baserowarcs >= 0 );
2677 *score = overlap - (rowarcs + baserowarcs - 2.0 * overlap)/(2.0 * ncols + 1.0);
2679 *score = overlap - (rowarcs + baserowarcs - 4.0 * overlap)/(2.0 * ncols + 1.0);
2682 if(*invertcommodity)
2683 *score += 1.0 - (ABS(nneguncap - basenposuncap) + ABS(nposuncap - basenneguncap))/(2.0 * ncols + 1.0);
2685 *score += 1.0 - (ABS(nposuncap - basenposuncap) + ABS(nneguncap - basenneguncap))/(2.0 * ncols + 1.0);
2687 *score =
MAX(*score, 1e-6);
2690 SCIPdebugMsg(scip,
" -> node similarity: row <%s>: incompatible=%u overlap=%g rowlen=%d baserowlen=%d score=%g\n",
2691 SCIProwGetName(row), incompatible, overlap, rowlen, baserowlen, *score);
2706 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2708 int* commoditysigns = mcfdata->commoditysigns;
2709 int narcs = mcfdata->narcs;
2710 int* flowcands = mcfdata->flowcands;
2711 int nflowcands = mcfdata->nflowcands;
2712 int* rowcommodity = mcfdata->rowcommodity;
2713 int* colarcid = mcfdata->colarcid;
2714 int* newcols = mcfdata->newcols;
2735 assert(mcfdata->nnodes == 0);
2747 rownodeid = mcfdata->rownodeid;
2748 colisincident = mcfdata->colisincident;
2758 for( r = 0; r < nrows; r++ )
2760 for( c = 0; c < ncols; c++ )
2761 colisincident[c] =
FALSE;
2763 assert(flowcands !=
NULL || nflowcands == 0);
2766 for( n = 0; n < nflowcands; n++ )
2775 assert(flowcands !=
NULL);
2777 assert(0 <= r && r < nrows);
2778 assert(rowcommodity !=
NULL);
2781 basecommodity = rowcommodity[
r];
2782 if( basecommodity == -1 )
2785 assert(mcfdata->rowarcid[r] == -1);
2788 if( rownodeid[r] >= 0 )
2792 SCIPdebugMsg(scip,
"assigning row %d <%s> of commodity %d to node %d [score: %g]\n",
2793 r,
SCIProwGetName(rows[r]), basecommodity, mcfdata->nnodes, mcfdata->flowrowscores[r]);
2794 rownodeid[
r] = mcfdata->nnodes;
2802 if(ncommodities == 1)
2814 assert(commoditysigns !=
NULL);
2820 if( (flowrowsigns[r] &
INVERTED) != 0 )
2822 if( commoditysigns[basecommodity] == -1 )
2825 for( i = 0; i < rowlen; i++ )
2830 assert(0 <= c && c < ncols);
2831 arcid = colarcid[c];
2836 arcpattern[arcid]++;
2838 arcpattern[arcid]--;
2853 bestflowrows[i] =
NULL;
2854 bestscores[i] = 0.0;
2855 bestinverted[i] =
FALSE;
2867 for( i = 0; i < mcfdata->nnewcols; i++ )
2873 assert(newcols !=
NULL);
2875 assert(0 <= c && c < ncols);
2876 assert(mcfdata->colcommodity[c] >= 0);
2877 assert(mcfdata->colcommodity[c] != basecommodity);
2880 assert(colisincident[c]);
2881 colisincident[c] =
FALSE;
2887 for( j = 0; j < collen; j++ )
2895 assert(0 <= colr && colr < nrows);
2898 if( rowprocessed[colr] )
2900 rowprocessed[colr] =
TRUE;
2903 rowcom = rowcommodity[colr];
2904 assert(rowcom != basecommodity);
2908 assert(rowcom == mcfdata->colcommodity[c]);
2909 assert((flowrowsigns[colr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2910 assert(mcfdata->rowarcid[colr] == -1);
2913 if( rownodeid[colr] >= 0 )
2918 nposuncap, nneguncap, colrows[j], &score, &invertcommodity) );
2921 if( score > bestscores[rowcom] )
2923 bestflowrows[rowcom] = colrows[j];
2924 bestscores[rowcom] = score;
2925 bestinverted[rowcom] = invertcommodity;
2929 assert(bestflowrows[basecommodity] ==
NULL);
2936 if( bestflowrows[i] ==
NULL )
2940 assert(0 <= comr && comr < nrows);
2941 assert(rowcommodity[comr] == i);
2942 assert((flowrowsigns[comr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2943 assert(rownodeid[comr] == -1);
2944 assert(mcfdata->nnodes >= 1);
2946 SCIPdebugMsg(scip,
" -> assigning row %d <%s> of commodity %d to node %d [invert:%u]\n",
2947 comr,
SCIProwGetName(rows[comr]), i, mcfdata->nnodes-1, bestinverted[i]);
2948 rownodeid[comr] = mcfdata->nnodes-1;
2951 if( bestinverted[i] )
2953 assert(commoditysigns[i] != +1);
2954 commoditysigns[i] = -1;
2958 assert(commoditysigns[i] != -1);
2959 commoditysigns[i] = +1;
2981 int* commoditysigns = mcfdata->commoditysigns;
2984 for( k = 0; k < mcfdata->ncommodities; k++ )
2986 if( commoditysigns[k] == 0 )
2987 commoditysigns[k] = +1;
3002 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3003 int* commoditysigns = mcfdata->commoditysigns;
3004 int* rowcommodity = mcfdata->rowcommodity;
3005 int* rownodeid = mcfdata->rownodeid;
3006 int* colsources = mcfdata->colsources;
3007 int* coltargets = mcfdata->coltargets;
3015 assert(sourcenode !=
NULL);
3016 assert(targetnode !=
NULL);
3017 assert(colsources !=
NULL);
3018 assert(coltargets !=
NULL);
3024 if( colsources[c] >= -1 )
3026 assert(coltargets[c] >= -1);
3027 *sourcenode = colsources[c];
3028 *targetnode = coltargets[c];
3039 for( i = 0; i < collen; i++ )
3046 if( rownodeid[r] >= 0 )
3053 k = rowcommodity[
r];
3054 assert(0 <= v && v < mcfdata->
nnodes);
3062 if( (flowrowsigns[r] &
INVERTED) != 0 )
3064 if( commoditysigns[k] == -1 )
3068 if( ( scale * colvals[i] ) > 0.0 )
3070 assert(*sourcenode == -1);
3072 if( *targetnode >= 0 )
3077 assert(*targetnode == -1);
3079 if( *sourcenode >= 0 )
3086 colsources[c] = *sourcenode;
3087 coltargets[c] = *targetnode;
3098 int* flowcands = mcfdata->flowcands;
3099 int nflowcands = mcfdata->nflowcands;
3101 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3103 int* rowcommodity = mcfdata->rowcommodity;
3105 int* rownodeid = mcfdata->rownodeid;
3106 int* colarcid = mcfdata->colarcid;
3107 int nnodes = mcfdata->nnodes;
3115 int* sortedflowcands;
3116 int* sortedflowcandnodeid;
3129 assert(mcfdata->nemptycommodities == 0);
3130 assert(ncommodities >= 0);
3134 if( ncommodities == 0 || nflowcands == 0 || nnodes == 0 )
3143 assert(rows !=
NULL);
3144 assert(cols !=
NULL || ncols == 0);
3155 for( n = 0; n < nflowcands; n++ )
3157 sortedflowcands[n] = flowcands[n];
3158 sortedflowcandnodeid[n] = rownodeid[flowcands[n]];
3162 SCIPsortIntInt(sortedflowcandnodeid, sortedflowcands, nflowcands);
3163 assert(sortedflowcandnodeid[0] <= 0);
3164 assert(sortedflowcandnodeid[nflowcands-1] == nnodes-1);
3167 for( v = 0; v <
nnodes; v++ )
3183 for( n = 0; n < nflowcands; n++ )
3185 if( sortedflowcandnodeid[n] >= 0 )
3187 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3188 assert(rowcommodity[sortedflowcands[n]] == -1);
3190 assert(n < nflowcands);
3191 assert(sortedflowcandnodeid[n] == 0);
3196 for( v = 0; n < nflowcands; v++ )
3201 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3202 assert(rowcommodity[sortedflowcands[n]] >= 0);
3203 assert(rownodeid[sortedflowcands[n]] == sortedflowcandnodeid[n]);
3204 assert(sortedflowcandnodeid[n] == v);
3205 assert(nadjnodes == 0);
3206 assert(ninccols == 0);
3211 for( ; n < nflowcands && sortedflowcandnodeid[n] == v; n++ )
3218 r = sortedflowcands[n];
3220 assert(mcfdata->rowarcid[r] == -1);
3225 for( i = 0; i < rowlen; i++ )
3236 arcid = colarcid[c];
3237 assert(-2 <= arcid && arcid < mcfdata->
narcs);
3238 assert(rowcommodity[r] == colcommodity[c]);
3248 else if( arcid == -1 )
3258 assert(-1 <= s && s < nnodes);
3259 assert(-1 <= t && t < nnodes);
3260 assert(s == v || t == v);
3271 if( s < 0 || t < 0 )
3279 assert(ninccols < ncols);
3280 inccols[ninccols] = c;
3296 if( sourcecount[u] + targetcount[u] == 1 )
3298 assert(nadjnodes < nnodes);
3299 adjnodes[nadjnodes] = u;
3307 for( l = 0; l < nadjnodes; l++ )
3312 assert(0 <= u && u < nnodes);
3313 assert(sourcecount[u] > 0 || targetcount[u] > 0);
3315 assert(ninccols >= 0);
3318 if( sourcecount[u] >= arcsthreshold )
3325 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, u, v);
3328 for( m = 0; m < ninccols; m++ )
3335 assert(0 <= c && c < ncols);
3337 assert(cols !=
NULL);
3339 assert(s == v || t == v);
3344 colarcid[c] = arcid;
3347 inccols[m] = inccols[ninccols-1];
3355 if( targetcount[u] >= arcsthreshold )
3362 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, v, u);
3365 for( m = 0; m < ninccols; m++ )
3372 assert(0 <= c && c < ncols);
3374 assert(cols !=
NULL);
3376 assert(s == v || t == v);
3381 colarcid[c] = arcid;
3384 inccols[m] = inccols[ninccols-1];
3393 for( l = 0; l < nadjnodes; l++ )
3401 for( l = 0; l < ninccols; l++ )
3403 assert(colarcid[inccols[l]] == -1);
3404 colarcid[inccols[l]] = -2;
3408 assert(n == nflowcands);
3409 assert(v == nnodes);
3413 for( n = 0; n < ncols; n++ )
3414 assert(colarcid[n] >= -1);
3425 MCFdebugMessage(
"network after finding uncapacitated arcs has %d nodes, %d arcs, and %d commodities\n",
3426 mcfdata->nnodes, mcfdata->narcs, mcfdata->ncommodities);
3438 int* flowcands = mcfdata->flowcands;
3439 int nflowcands = mcfdata->nflowcands;
3441 int* rowcommodity = mcfdata->rowcommodity;
3442 int* colarcid = mcfdata->colarcid;
3443 int* rowarcid = mcfdata->rowarcid;
3444 int* rownodeid = mcfdata->rownodeid;
3446 int* commoditysigns = mcfdata->commoditysigns;
3447 int narcs = mcfdata->narcs;
3448 int nnodes = mcfdata->nnodes;
3449 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3461 int nnodesthreshold;
3462 int newncommodities;
3468 MCFdebugMessage(
"network before cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3476 permsize =
MAX(permsize, narcs);
3477 permsize =
MAX(permsize, nnodes);
3487 assert(flowcands !=
NULL || nflowcands == 0);
3490 for( i = 0; i < nflowcands; i++ )
3494 assert(flowcands !=
NULL);
3496 assert(0 <= r && r < nrows);
3497 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3498 if( rowcommodity[r] >= 0 )
3500 assert(rowcommodity[r] < ncommodities);
3501 nnodespercom[rowcommodity[
r]]++;
3505 assert(capacityrows !=
NULL || narcs == 0);
3508 for( a = 0; a <
narcs; a++ )
3515 assert(capacityrows !=
NULL);
3517 assert(0 <= r && r < nrows);
3518 assert(rowarcid[r] == a);
3524 for( j = 0; j < rowlen; j++ )
3529 assert(0 <= c && c < ncols);
3530 if( colcommodity[c] >= 0 && colarcid[c] == a )
3532 assert(colcommodity[c] < ncommodities);
3533 arcisincom[colcommodity[c]] =
TRUE;
3548 maxnnodes =
MAX(maxnnodes, nnodespercom[k]);
3556 SCIPdebugMsg(scip,
" -> node threshold: %d\n", nnodesthreshold);
3559 newncommodities = 0;
3562 SCIPdebugMsg(scip,
" -> commodity %d: %d nodes, %d arcs\n", k, nnodespercom[k], narcspercom[k]);
3565 if( nnodespercom[k] >= nnodesthreshold && narcspercom[k] >= 1 )
3567 assert(newncommodities <= k);
3568 perm[k] = newncommodities;
3569 commoditysigns[newncommodities] = commoditysigns[k];
3576 if( newncommodities < ncommodities )
3585 SCIPdebugMsg(scip,
" -> discarding %d of %d commodities\n", ncommodities - newncommodities, ncommodities);
3593 for( c = 0; c < ncols; c++ )
3595 if( colcommodity[c] >= 0 )
3597 assert(-1 <= colarcid[c] && colarcid[c] < narcs);
3598 assert(colcommodity[c] < mcfdata->ncommodities);
3599 colcommodity[c] = perm[colcommodity[c]];
3600 assert(colcommodity[c] < newncommodities);
3601 if( colcommodity[c] == -1 )
3606 else if( colarcid[c] >= 0 )
3607 arcisused[colarcid[c]] =
TRUE;
3610 for( i = 0; i < nflowcands; i++ )
3614 assert(flowcands !=
NULL);
3616 assert(0 <= r && r < nrows);
3617 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3618 if( rowcommodity[r] >= 0 )
3620 assert(0 <= rownodeid[r] && rownodeid[r] < nnodes);
3621 assert(rowcommodity[r] < mcfdata->ncommodities);
3622 rowcommodity[
r] = perm[rowcommodity[
r]];
3623 assert(rowcommodity[r] < newncommodities);
3624 if( rowcommodity[r] == -1 )
3630 nodeisused[rownodeid[
r]] =
TRUE;
3634 mcfdata->ncommodities = newncommodities;
3635 ncommodities = newncommodities;
3639 for( a = 0; a <
narcs; a++ )
3643 assert(capacityrows !=
NULL);
3647 assert(newnarcs <= a);
3649 capacityrows[newnarcs] = capacityrows[
a];
3658 assert(0 <= r && r < nrows);
3659 assert(rowarcid[r] == a);
3660 rowarcid[
r] = perm[
a];
3664 if( newnarcs < narcs )
3666 SCIPdebugMsg(scip,
" -> discarding %d of %d arcs\n", narcs - newnarcs, narcs);
3668 for( c = 0; c < ncols; c++ )
3670 if( colarcid[c] >= 0 )
3672 colarcid[c] = perm[colarcid[c]];
3673 assert(colarcid[c] >= 0);
3676 mcfdata->narcs = newnarcs;
3680 for( a = 0; a <
narcs; a++ )
3683 assert(capacityrows !=
NULL);
3685 assert(0 <= r && r < nrows);
3686 assert(rowarcid[r] == a);
3692 for( v = 0; v <
nnodes; v++ )
3696 assert(newnnodes <= v);
3697 perm[v] = newnnodes;
3705 if( newnnodes < nnodes )
3707 SCIPdebugMsg(scip,
" -> discarding %d of %d nodes\n", nnodes - newnnodes, nnodes);
3709 for( i = 0; i < nflowcands; i++ )
3713 assert(flowcands !=
NULL);
3715 assert(0 <= r && r < nrows);
3716 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3717 if( rowcommodity[r] >= 0 )
3719 assert(rowcommodity[r] < ncommodities);
3720 rownodeid[
r] = perm[rownodeid[
r]];
3721 assert(rownodeid[r] >= 0);
3724 mcfdata->nnodes = newnnodes;
3736 mcfdata->nemptycommodities = 0;
3744 MCFdebugMessage(
"network after cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3758 int* colarcid = mcfdata->colarcid;
3760 int narcs = mcfdata->narcs;
3761 int nnodes = mcfdata->nnodes;
3763 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3765 SCIP_Real maxinconsistencyratio = sepadata->maxinconsistencyratio;
3766 SCIP_Real maxarcinconsistencyratio = sepadata->maxarcinconsistencyratio;
3778 int *flowvarspercom;
3791 assert(effortlevel !=
NULL);
3805 arcsources = mcfdata->arcsources;
3806 arctargets = mcfdata->arctargets;
3807 colsources = mcfdata->colsources;
3808 coltargets = mcfdata->coltargets;
3809 firstoutarcs = mcfdata->firstoutarcs;
3810 firstinarcs = mcfdata->firstinarcs;
3811 nextoutarcs = mcfdata->nextoutarcs;
3812 nextinarcs = mcfdata->nextinarcs;
3814 mcfdata->arcarraysize =
narcs;
3817 for( c = 0; c < ncols; c++ )
3824 for( v = 0; v <
nnodes; v++ )
3826 firstoutarcs[v] = -1;
3827 firstinarcs[v] = -1;
3829 for( a = 0; a <
narcs; a++ )
3831 nextoutarcs[
a] = -1;
3845 mcfdata->ninconsistencies = 0.0;
3846 maxninconsistencies = maxinconsistencyratio * (
SCIP_Real)narcs;
3849 for( a = 0; a <
narcs; a++ )
3871 assert(mcfdata->rowarcid[r] == a);
3874 for( i = 0; i <
nnodes; i++ )
3876 assert(sourcenodecnt[i] == 0);
3877 assert(targetnodecnt[i] == 0);
3888 for( i = 0; i < rowlen; i++ )
3892 if( colarcid[c] >= 0 )
3894 int k = colcommodity[c];
3895 assert (0 <= k && k < ncommodities);
3896 flowvarspercom[k]++;
3897 if( !comtouched[k] )
3900 comtouched[k] =
TRUE;
3906 if( ntouchedcoms == 0 )
3908 capacityrows[
a] =
NULL;
3916 totalsourcecnt = 0.0;
3917 totaltargetcnt = 0.0;
3919 for( i = 0; i < rowlen; i++ )
3923 if( colarcid[c] >= 0 )
3925 int k = colcommodity[c];
3930 assert (0 <= k && k < ncommodities);
3931 assert (comtouched[k]);
3932 assert (flowvarspercom[k] >= 1);
3938 weight = 1.0/flowvarspercom[k];
3941 if( sourcenodecnt[sourcev] == 0.0 && targetnodecnt[sourcev] == 0.0 )
3943 touchednodes[ntouchednodes] = sourcev;
3946 sourcenodecnt[sourcev] += weight;
3947 totalsourcecnt += weight;
3951 if( sourcenodecnt[targetv] == 0.0 && targetnodecnt[targetv] == 0.0 )
3953 touchednodes[ntouchednodes] = targetv;
3956 targetnodecnt[targetv] += weight;
3957 totaltargetcnt += weight;
3959 if( sourcev >= 0 || targetv >= 0 )
3960 totalnodecnt += weight;
3967 bestsourcecnt = 0.0;
3968 besttargetcnt = 0.0;
3969 for( i = 0; i < ntouchednodes; i++ )
3971 v = touchednodes[i];
3972 assert(0 <= v && v < nnodes);
3977 if( sourcenodecnt[v] >= targetnodecnt[v] )
3979 if( sourcenodecnt[v] > bestsourcecnt )
3982 bestsourcecnt = sourcenodecnt[v];
3987 if( targetnodecnt[v] > besttargetcnt )
3990 besttargetcnt = targetnodecnt[v];
3996 SCIP_Real nodecnt = sourcenodecnt[v] + targetnodecnt[v];
4000 if( nodecnt > bestsourcecnt )
4002 besttargetv = bestsourcev;
4003 besttargetcnt = bestsourcecnt;
4005 bestsourcecnt = nodecnt;
4007 else if( nodecnt > besttargetcnt )
4010 besttargetcnt = nodecnt;
4015 sourcenodecnt[v] = 0;
4016 targetnodecnt[v] = 0;
4022 totalsourcecnt = totalnodecnt;
4023 totaltargetcnt = totalnodecnt;
4025 assert(
SCIPisGE(scip,totalsourcecnt,bestsourcecnt));
4026 assert(
SCIPisGE(scip,totaltargetcnt,besttargetcnt));
4027 nsourceinconsistencies = (totalsourcecnt - bestsourcecnt)/ntouchedcoms;
4028 ntargetinconsistencies = (totaltargetcnt - besttargetcnt)/ntouchedcoms;
4031 if( nsourceinconsistencies > maxarcinconsistencyratio )
4037 if( ntargetinconsistencies > maxarcinconsistencyratio )
4044 assert(bestsourcev == -1 || bestsourcev != besttargetv);
4045 arcsources[
a] = bestsourcev;
4046 arctargets[
a] = besttargetv;
4047 SCIPdebugMsg(scip,
"arc %d: %d -> %d (len=%d, sourcecnt=%g/%g, targetcnt=%g/%g, %g/%g inconsistencies)\n",
4048 a, bestsourcev, besttargetv, rowlen,
4049 bestsourcecnt, totalsourcecnt, besttargetcnt, totaltargetcnt,
4050 nsourceinconsistencies, ntargetinconsistencies);
4053 if( bestsourcev != -1 )
4055 nextoutarcs[
a] = firstoutarcs[bestsourcev];
4056 firstoutarcs[bestsourcev] =
a;
4058 if( besttargetv != -1 )
4060 nextinarcs[
a] = firstinarcs[besttargetv];
4061 firstinarcs[besttargetv] =
a;
4065 mcfdata->ninconsistencies += 0.5*(nsourceinconsistencies + ntargetinconsistencies);
4067 if( mcfdata->ninconsistencies > maxninconsistencies )
4069 MCFdebugMessage(
" -> reached maximal number of inconsistencies: %g > %g\n",
4070 mcfdata->ninconsistencies, maxninconsistencies);
4076 if( mcfdata->ninconsistencies <= maxninconsistencies && narcs > 0 && ncommodities > 0 )
4081 MCFdebugMessage(
"extracted network has %g inconsistencies (ratio %g) -> separating with effort %d\n",
4082 mcfdata->ninconsistencies, mcfdata->ninconsistencies/(
SCIP_Real)narcs, *effortlevel);
4113 int* firstoutarcs = mcfdata->firstoutarcs;
4114 int* firstinarcs = mcfdata->firstinarcs;
4115 int* nextoutarcs = mcfdata->nextoutarcs;
4116 int* nextinarcs = mcfdata->nextinarcs;
4117 int nnodes = mcfdata->nnodes;
4122 assert(nodevisited !=
NULL);
4123 assert(0 <= startv && startv < nnodes);
4124 assert(nodevisited[startv] ==
UNKNOWN);
4125 assert(compnodes !=
NULL);
4126 assert(ncompnodes !=
NULL);
4127 assert(comparcs !=
NULL);
4128 assert(ncomparcs !=
NULL);
4137 stacknodes[0] = startv;
4139 nodevisited[startv] =
ONSTACK;
4142 while( nstacknodes > 0 )
4147 assert(firstoutarcs !=
NULL);
4148 assert(firstinarcs !=
NULL);
4149 assert(nextoutarcs !=
NULL);
4150 assert(nextinarcs !=
NULL);
4153 v = stacknodes[nstacknodes-1];
4155 assert(0 <= v && v < nnodes);
4156 assert(nodevisited[v] ==
ONSTACK);
4160 assert(*ncompnodes < nnodes);
4161 compnodes[*ncompnodes] = v;
4165 for( a = firstoutarcs[v]; a != -1; a = nextoutarcs[
a] )
4169 assert(0 <= a && a < mcfdata->
narcs);
4170 assert(arctargets !=
NULL);
4172 targetv = arctargets[
a];
4175 if( targetv != -1 && nodevisited[targetv] ==
VISITED )
4179 assert(*ncomparcs < mcfdata->narcs);
4180 comparcs[*ncomparcs] =
a;
4184 if( targetv != -1 && nodevisited[targetv] ==
UNKNOWN )
4186 assert(nstacknodes < nnodes);
4187 stacknodes[nstacknodes] = targetv;
4189 nodevisited[targetv] =
ONSTACK;
4194 for( a = firstinarcs[v]; a != -1; a = nextinarcs[
a] )
4198 assert(0 <= a && a < mcfdata->
narcs);
4199 assert(arcsources !=
NULL);
4201 sourcev = arcsources[
a];
4204 if( sourcev != -1 && nodevisited[sourcev] ==
VISITED )
4208 assert(*ncomparcs < mcfdata->narcs);
4209 comparcs[*ncomparcs] =
a;
4213 if( sourcev != -1 && nodevisited[sourcev] ==
UNKNOWN )
4215 assert(nstacknodes < nnodes);
4216 stacknodes[nstacknodes] = sourcev;
4218 nodevisited[sourcev] =
ONSTACK;
4249 int mcfnetworkssize;
4251 assert(mcfnetworks !=
NULL);
4252 assert(nmcfnetworks !=
NULL);
4253 assert(effortlevel !=
NULL);
4257 *mcfnetworks =
NULL;
4259 mcfnetworkssize = 0;
4290 mcfdata.flowrowsigns =
NULL;
4291 mcfdata.flowrowscalars =
NULL;
4292 mcfdata.flowrowscores =
NULL;
4293 mcfdata.capacityrowsigns =
NULL;
4294 mcfdata.capacityrowscores =
NULL;
4295 mcfdata.flowcands =
NULL;
4296 mcfdata.nflowcands = 0;
4297 mcfdata.capacitycands =
NULL;
4298 mcfdata.ncapacitycands = 0;
4299 mcfdata.plusflow =
NULL;
4300 mcfdata.minusflow =
NULL;
4301 mcfdata.ncommodities = 0;
4302 mcfdata.nemptycommodities = 0;
4303 mcfdata.commoditysigns =
NULL;
4304 mcfdata.commoditysignssize = 0;
4305 mcfdata.colcommodity =
NULL;
4306 mcfdata.rowcommodity =
NULL;
4307 mcfdata.colarcid =
NULL;
4308 mcfdata.rowarcid =
NULL;
4309 mcfdata.rownodeid =
NULL;
4310 mcfdata.arcarraysize = 0;
4311 mcfdata.arcsources =
NULL;
4312 mcfdata.arctargets =
NULL;
4313 mcfdata.colsources =
NULL;
4314 mcfdata.coltargets =
NULL;
4315 mcfdata.firstoutarcs =
NULL;
4316 mcfdata.firstinarcs =
NULL;
4317 mcfdata.nextoutarcs =
NULL;
4318 mcfdata.nextinarcs =
NULL;
4319 mcfdata.newcols =
NULL;
4320 mcfdata.nnewcols = 0;
4323 mcfdata.ninconsistencies = 0.0;
4324 mcfdata.capacityrows =
NULL;
4325 mcfdata.capacityrowssize = 0;
4326 mcfdata.colisincident =
NULL;
4327 mcfdata.zeroarcarray =
NULL;
4334 assert(mcfdata.flowrowsigns !=
NULL);
4335 assert(mcfdata.flowrowscalars !=
NULL);
4336 assert(mcfdata.flowrowscores !=
NULL);
4337 assert(mcfdata.flowcands !=
NULL);
4339 if( mcfdata.nflowcands == 0 )
4347 assert(mcfdata.plusflow !=
NULL);
4348 assert(mcfdata.minusflow !=
NULL);
4349 assert(mcfdata.colcommodity !=
NULL);
4350 assert(mcfdata.rowcommodity !=
NULL);
4351 assert(mcfdata.newcols !=
NULL);
4357 printCommodities(scip, &mcfdata);
4364 assert(mcfdata.capacityrowsigns !=
NULL);
4365 assert(mcfdata.capacityrowscores !=
NULL);
4366 assert(mcfdata.capacitycands !=
NULL);
4368 if( mcfdata.ncapacitycands == 0 )
4376 assert(mcfdata.colarcid !=
NULL);
4377 assert(mcfdata.rowarcid !=
NULL);
4381 assert(mcfdata.rownodeid !=
NULL);
4382 assert(mcfdata.colisincident !=
NULL);
4383 assert(mcfdata.zeroarcarray !=
NULL);
4394 assert(mcfdata.arcsources !=
NULL);
4395 assert(mcfdata.arctargets !=
NULL);
4396 assert(mcfdata.colsources !=
NULL);
4397 assert(mcfdata.coltargets !=
NULL);
4398 assert(mcfdata.firstoutarcs !=
NULL);
4399 assert(mcfdata.firstinarcs !=
NULL);
4400 assert(mcfdata.nextoutarcs !=
NULL);
4401 assert(mcfdata.nextinarcs !=
NULL);
4417 printCommodities(scip, &mcfdata);
4430 for( v = 0; v < mcfdata.nnodes; v++ )
4434 for( v = 0; v < mcfdata.nnodes; v++ )
4441 if( nodevisited[v] ==
VISITED )
4446 assert(ncompnodes >= 1);
4447 assert(compnodes[0] == v);
4448 assert(nodevisited[v] ==
VISITED);
4451 if( ncompnodes >= minnodes && ncomparcs >=
MINARCS )
4458 assert(*nmcfnetworks <= mcfnetworkssize);
4459 if( *nmcfnetworks == mcfnetworkssize )
4461 mcfnetworkssize =
MAX(2*mcfnetworkssize, *nmcfnetworks+1);
4464 assert(*nmcfnetworks < mcfnetworkssize);
4470 SCIP_CALL(
mcfnetworkFill(scip, mcfnetwork, &mcfdata, compnodeid, compnodes, ncompnodes, comparcs, ncomparcs) );
4473 assert(*mcfnetworks !=
NULL);
4474 for( i = *nmcfnetworks; i > 0 && mcfnetwork->
nnodes > (*mcfnetworks)[i-1]->nnodes; i-- )
4475 (*mcfnetworks)[i] = (*mcfnetworks)[i-1];
4476 (*mcfnetworks)[i] = mcfnetwork;
4481 minnodes =
MAX(minnodes, (*mcfnetworks)[*nmcfnetworks-1]->
nnodes);
4486 SCIPdebugMsg(scip,
" -> discarded network with %d nodes and %d arcs due to maxnetworks (minnodes=%d)\n",
4487 (*mcfnetworks)[*nmcfnetworks-1]->
nnodes, (*mcfnetworks)[*nmcfnetworks-1]->
narcs, minnodes);
4495 SCIPdebugMsg(scip,
" -> discarded component with %d nodes and %d arcs\n", ncompnodes, ncomparcs);
4537 #ifdef COUNTNETWORKVARIABLETYPES 4559 int nintflowvars = 0;
4560 int nbinflowvars = 0;
4561 int ncontflowvars = 0;
4563 int nintcapvars = 0;
4564 int nbincapvars = 0;
4565 int ncontcapvars = 0;
4573 for(c=0; c < ncols; c++)
4574 colvisited[c]=
FALSE;
4578 for(m=0; m < nmcfnetworks; m++)
4590 for(c=0; c < ncols; c++)
4594 if(colcommodity[c] >= 0 && ! colvisited[c])
4599 colvisited[c] =
TRUE;
4622 for( a = 0; a <
narcs; a++ )
4625 row = arccapacityrows[
a];
4637 for( i = 0; i < rowlen; i++ )
4642 if(colcommodity[c] == -1 && ! colvisited[c] )
4645 colvisited[c] =
TRUE;
4672 for( v = 0; v <
nnodes; v++ )
4675 row = nodeflowrows[v][k];
4685 MCFdebugMessage(
" nof flowvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4686 nflowvars, ncontflowvars, nintflowvars, nbinflowvars);
4687 MCFdebugMessage(
" nof capvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4688 ncapvars, ncontcapvars, nintcapvars, nbincapvars);
4707 int* representatives,
4714 for( v = 0; v < nelems; v++ )
4715 representatives[v] = v;
4721 int* representatives,
4725 assert(representatives !=
NULL);
4727 while( v != representatives[v] )
4729 representatives[v] = representatives[representatives[v]];
4730 v = representatives[v];
4739 int* representatives,
4744 assert(rep1 != rep2);
4745 assert(representatives[rep1] == rep1);
4746 assert(representatives[rep2] == rep2);
4752 representatives[rep2] = rep1;
4754 representatives[rep1] = rep2;
4770 if( nodepair1->weight > nodepair2->weight )
4772 else if( nodepair1->weight < nodepair2->weight )
4807 assert(mcfnetwork !=
NULL);
4813 assert(nodepair1 !=
NULL);
4814 assert(nodepair2 !=
NULL);
4816 source1 = nodepair1->node1;
4817 source2 = nodepair2->node1;
4818 target1 = nodepair1->node2;
4819 target2 = nodepair2->node2;
4821 assert(source1 >=0 && source1 < mcfnetwork->
nnodes);
4822 assert(source2 >=0 && source2 < mcfnetwork->nnodes);
4823 assert(target1 >=0 && target1 < mcfnetwork->nnodes);
4824 assert(target2 >=0 && target2 < mcfnetwork->nnodes);
4825 assert(source1 <= target1);
4826 assert(source2 <= target2);
4828 return (source1 == source2 && target1 == target2);
4842 unsigned int hashval;
4846 assert(mcfnetwork !=
NULL);
4850 assert( nodepair !=
NULL);
4852 source = nodepair->node1;
4853 target = nodepair->node2;
4855 assert(source >=0 && source < mcfnetwork->
nnodes);
4856 assert(target >=0 && target < mcfnetwork->nnodes);
4857 assert(source <= target);
4859 hashval = (unsigned)((source << 16) + target);
4882 #ifdef BETTERWEIGHTFORDEMANDNODES 4902 assert(mcfnetwork !=
NULL);
4904 #ifdef BETTERWEIGHTFORDEMANDNODES 4914 assert(nodepairqueue !=
NULL);
4921 hashtablesize = mcfnetwork->
narcs;
4924 hashGetKeyNodepairs, hashKeyEqNodepairs, hashKeyValNodepairs, (
void*) mcfnetwork) );
4931 for( a = 0; a < mcfnetwork->narcs; a++ )
4937 capacityrow = mcfnetwork->arccapacityrows[
a];
4939 SCIPdebugMsg(scip,
"arc %i = (%i %i)\n", a, mcfnetwork->arcsources[a], mcfnetwork->arctargets[a]);
4942 if( mcfnetwork->arcsources[a] <= mcfnetwork->arctargets[a] )
4944 nodepair.node1 = mcfnetwork->arcsources[
a];
4945 nodepair.node2 = mcfnetwork->arctargets[
a];
4949 nodepair.node2 = mcfnetwork->arcsources[
a];
4950 nodepair.node1 = mcfnetwork->arctargets[
a];
4953 assert(nodepair.node1 < mcfnetwork->nnodes);
4954 assert(nodepair.node2 < mcfnetwork->nnodes);
4955 if( nodepair.node1 == -1 || nodepair.node2 == -1 )
4959 if( capacityrow !=
NULL )
4975 slack =
MAX(slack, 0.0);
4978 scale = ABS(mcfnetwork->arccapacityscales[a])/maxval;
4979 assert(scale > 0.0);
4989 for( i = 0; i < rowlen; i++ )
4996 if(colcommodity[c] >= 0)
5008 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g -- flow:%g -- cap:%g \n", scale * slack, dualsol/scale, totalflow * scale, totalcap * scale);
5010 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g1\n", scale * slack, dualsol/scale);
5014 nodepair.weight = scale * slack - ABS(dualsol)/scale;
5015 #ifdef USEFLOWFORTIEBREAKING 5018 nodepair.weight += totalflow * scale;
5019 nodepair.weight = MIN( nodepair.weight, -0.0001);
5022 #ifdef USECAPACITYFORTIEBREAKING 5025 nodepair.weight += totalcap * scale;
5026 nodepair.weight = MIN( nodepair.weight, -0.0001);
5041 if( nodepairptr !=
NULL )
5044 SCIPdebugMsg(scip,
"nodepair known [%d,%d] -- old weight:%g -- new weight:%g\n", nodepair.node1,nodepair.node2,nodepairptr->weight,
5045 MIN(nodepair.weight, nodepairptr->weight));
5046 nodepairptr->weight = MIN(nodepair.weight, nodepairptr->weight);
5051 nodepairs = (*nodepairqueue)->nodepairs;
5053 assert(nnodepairs < mcfnetwork->
narcs);
5054 nodepairs[nnodepairs] = nodepair;
5057 SCIPdebugMsg(scip,
"new nodepair [%d,%d]-- weight:%g\n", nodepair.node1, nodepair.node2, nodepair.weight);
5068 #ifdef BETTERWEIGHTFORDEMANDNODES 5076 nodepairs = (*nodepairqueue)->nodepairs;
5077 for( n = 0; n < nnodepairs; n++ )
5081 maxweight =
MAX(maxweight, nodepairs[n].weight);
5083 minweight = MIN(minweight, nodepairs[n].weight);
5086 SCIPdebugMsg(scip,
"min/max weight:%g / %g\n", minweight, maxweight);
5093 for( n = 0; n < nnodepairs; n++ )
5095 int node1 = nodepairs[n].node1;
5096 int node2 = nodepairs[n].node2;
5098 #ifdef BETTERWEIGHTFORDEMANDNODES 5105 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5113 if( nodeflowrows[node1][k] ==
NULL )
5116 if( nodeflowscales[node1][k] > 0.0 )
5133 if( nodeflowrows[node2][k] ==
NULL )
5136 if( nodeflowscales[node2][k] > 0.0 )
5158 if( !hasdemand1 || !hasdemand2 )
5159 nodepairs[n].weight += maxweight;
5165 if( hasdemand1 && hasdemand2)
5166 nodepairs[n].weight += minweight;
5169 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5186 assert(nodepairqueue !=
NULL);
5187 assert(*nodepairqueue !=
NULL);
5201 assert(nodepairqueue !=
NULL);
5213 assert(nodepairqueue !=
NULL);
5261 assert(mcfnetwork !=
NULL);
5262 assert(nodepartition !=
NULL);
5263 assert(mcfnetwork->
nnodes >= 1);
5271 (*nodepartition)->nclusters = 0;
5280 nclustersleft = mcfnetwork->
nnodes;
5291 assert(nodepair !=
NULL);
5292 node1 = nodepair->node1;
5293 node2 = nodepair->node2;
5295 assert(node1 >= 0 && node1 < mcfnetwork->
nnodes);
5296 assert(node2 >= 0 && node2 < mcfnetwork->nnodes);
5301 assert(0 <= node1rep && node1rep < mcfnetwork->nnodes);
5302 assert(0 <= node2rep && node2rep < mcfnetwork->nnodes);
5305 if( node1rep == node2rep )
5309 SCIPdebugMsg(scip,
"shrinking nodepair (%d,%d) with weight %g: join representatives %d and %d\n",
5310 node1, node2, nodepair->weight, node1rep, node2rep);
5316 assert((*nodepartition)->representatives[0] == 0);
5321 if( nclustersleft > nclusters )
5323 for( v = 1; v < mcfnetwork->
nnodes && nclustersleft > nclusters; v++ )
5335 assert(nclustersleft <= nclusters);
5340 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5350 c = (*nodepartition)->nclusters;
5351 (*nodepartition)->nclusters++;
5354 c = (*nodepartition)->nodeclusters[rep];
5355 assert(0 <= c && c < nclusters);
5358 (*nodepartition)->nodeclusters[v] = c;
5364 for( c = 0; c < (*nodepartition)->nclusters; c++ )
5366 (*nodepartition)->clusterbegin[c] = pos;
5367 pos += clustersize[c];
5369 assert(pos == mcfnetwork->
nnodes);
5370 (*nodepartition)->clusterbegin[(*nodepartition)->nclusters] = mcfnetwork->
nnodes;
5374 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5376 c = (*nodepartition)->nodeclusters[v];
5377 assert(0 <= c && c < (*nodepartition)->nclusters);
5378 pos = (*nodepartition)->clusterbegin[c] + clustersize[c];
5379 assert(pos < (*nodepartition)->clusterbegin[c+1]);
5380 (*nodepartition)->clusternodes[pos] = v;
5400 assert(nodepartition !=
NULL);
5401 assert(*nodepartition !=
NULL);
5414 unsigned int partition,
5425 if( nodepartition ==
NULL )
5426 return ((v == (
int)partition) == !inverted);
5430 unsigned int clusterbit;
5432 cluster = nodepartition->nodeclusters[v];
5433 assert(0 <= cluster && cluster < nodepartition->nclusters);
5434 clusterbit = (1 << cluster);
5436 return (((partition & clusterbit) != 0) == !inverted);
5446 unsigned int partition
5449 const int* nodeclusters = nodepartition->nodeclusters;
5459 assert(nodepartition->nodeclusters !=
NULL);
5460 nclusters = nodepartition->nclusters;
5467 ncomponents = nclusters;
5468 assert(ncomponents >= 2);
5471 for( a = 0; a <
narcs; a++ )
5473 int s = arcsources[
a];
5474 int t = arctargets[
a];
5477 if( s == -1 || t == -1 )
5488 assert(0 <= s && s < mcfnetwork->
nnodes);
5489 assert(0 <= t && t < mcfnetwork->nnodes);
5492 cs = nodeclusters[s];
5493 ct = nodeclusters[t];
5494 assert(0 <= cs && cs < nclusters);
5495 assert(0 <= ct && ct < nclusters);
5504 if( repcs == repct )
5511 if( ncomponents <= 2 )
5521 assert(ncomponents >= 2);
5523 return (ncomponents == 2);
5528 void nodepartitionPrint(
5534 for( c = 0; c < nodepartition->nclusters; c++ )
5539 for( i = nodepartition->clusterbegin[c]; i < nodepartition->clusterbegin[c+1]; i++ )
5554 unsigned int partition
5563 if( nodepartition ==
NULL )
5568 file = fopen(filename,
"w");
5576 fprintf(file,
"graph\n");
5577 fprintf(file,
"[\n");
5578 fprintf(file,
" hierarchic 1\n");
5579 fprintf(file,
" label \"\"\n");
5580 fprintf(file,
" directed 1\n");
5583 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5594 fprintf(file,
" node\n");
5595 fprintf(file,
" [\n");
5596 fprintf(file,
" id %d\n", v);
5597 fprintf(file,
" label \"%s\"\n", label);
5598 fprintf(file,
" graphics\n");
5599 fprintf(file,
" [\n");
5600 fprintf(file,
" w 30.0\n");
5601 fprintf(file,
" h 30.0\n");
5602 fprintf(file,
" type \"ellipse\"\n");
5604 fprintf(file,
" fill \"#FF0000\"\n");
5606 fprintf(file,
" fill \"#00FF00\"\n");
5607 fprintf(file,
" outline \"#000000\"\n");
5608 fprintf(file,
" ]\n");
5609 fprintf(file,
" LabelGraphics\n");
5610 fprintf(file,
" [\n");
5611 fprintf(file,
" text \"%s\"\n", label);
5612 fprintf(file,
" fontSize 13\n");
5613 fprintf(file,
" fontName \"Dialog\"\n");
5614 fprintf(file,
" anchor \"c\"\n");
5615 fprintf(file,
" ]\n");
5617 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+1);
5619 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+2);
5620 fprintf(file,
" ]\n");
5624 fprintf(file,
" node\n");
5625 fprintf(file,
" [\n");
5626 fprintf(file,
" id %d\n", mcfnetwork->
nnodes);
5627 fprintf(file,
" label \"?\"\n");
5628 fprintf(file,
" graphics\n");
5629 fprintf(file,
" [\n");
5630 fprintf(file,
" w 30.0\n");
5631 fprintf(file,
" h 30.0\n");
5632 fprintf(file,
" type \"ellipse\"\n");
5633 fprintf(file,
" fill \"#FFFFFF\"\n");
5634 fprintf(file,
" outline \"#000000\"\n");
5635 fprintf(file,
" ]\n");
5636 fprintf(file,
" LabelGraphics\n");
5637 fprintf(file,
" [\n");
5638 fprintf(file,
" text \"?\"\n");
5639 fprintf(file,
" fontSize 13\n");
5640 fprintf(file,
" fontName \"Dialog\"\n");
5641 fprintf(file,
" anchor \"c\"\n");
5642 fprintf(file,
" ]\n");
5643 fprintf(file,
" ]\n");
5646 fprintf(file,
" node\n");
5647 fprintf(file,
" [\n");
5648 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+1);
5649 fprintf(file,
" label \"Partition S\"\n");
5650 fprintf(file,
" graphics\n");
5651 fprintf(file,
" [\n");
5652 fprintf(file,
" type \"roundrectangle\"\n");
5653 fprintf(file,
" fill \"#CAECFF84\"\n");
5654 fprintf(file,
" outline \"#666699\"\n");
5655 fprintf(file,
" outlineStyle \"dotted\"\n");
5656 fprintf(file,
" topBorderInset 0\n");
5657 fprintf(file,
" bottomBorderInset 0\n");
5658 fprintf(file,
" leftBorderInset 0\n");
5659 fprintf(file,
" rightBorderInset 0\n");
5660 fprintf(file,
" ]\n");
5661 fprintf(file,
" LabelGraphics\n");
5662 fprintf(file,
" [\n");
5663 fprintf(file,
" text \"Partition S\"\n");
5664 fprintf(file,
" fill \"#99CCFF\"\n");
5665 fprintf(file,
" fontSize 15\n");
5666 fprintf(file,
" fontName \"Dialog\"\n");
5667 fprintf(file,
" alignment \"right\"\n");
5668 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5669 fprintf(file,
" anchor \"t\"\n");
5670 fprintf(file,
" borderDistance 0.0\n");
5671 fprintf(file,
" ]\n");
5672 fprintf(file,
" isGroup 1\n");
5673 fprintf(file,
" ]\n");
5676 fprintf(file,
" node\n");
5677 fprintf(file,
" [\n");
5678 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+2);
5679 fprintf(file,
" label \"Partition T\"\n");
5680 fprintf(file,
" graphics\n");
5681 fprintf(file,
" [\n");
5682 fprintf(file,
" type \"roundrectangle\"\n");
5683 fprintf(file,
" fill \"#CAECFF84\"\n");
5684 fprintf(file,
" outline \"#666699\"\n");
5685 fprintf(file,
" outlineStyle \"dotted\"\n");
5686 fprintf(file,
" topBorderInset 0\n");
5687 fprintf(file,
" bottomBorderInset 0\n");
5688 fprintf(file,
" leftBorderInset 0\n");
5689 fprintf(file,
" rightBorderInset 0\n");
5690 fprintf(file,
" ]\n");
5691 fprintf(file,
" LabelGraphics\n");
5692 fprintf(file,
" [\n");
5693 fprintf(file,
" text \"Partition T\"\n");
5694 fprintf(file,
" fill \"#99CCFF\"\n");
5695 fprintf(file,
" fontSize 15\n");
5696 fprintf(file,
" fontName \"Dialog\"\n");
5697 fprintf(file,
" alignment \"right\"\n");
5698 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5699 fprintf(file,
" anchor \"t\"\n");
5700 fprintf(file,
" borderDistance 0.0\n");
5701 fprintf(file,
" ]\n");
5702 fprintf(file,
" isGroup 1\n");
5703 fprintf(file,
" ]\n");
5706 for( a = 0; a < mcfnetwork->
narcs; a++ )
5718 hasfractional =
FALSE;
5729 for( i = 0; i < rowlen; i++ )
5736 hasfractional =
TRUE;
5744 fprintf(file,
" edge\n");
5745 fprintf(file,
" [\n");
5748 fprintf(file,
" label \"%s\"\n", label);
5749 fprintf(file,
" graphics\n");
5750 fprintf(file,
" [\n");
5752 fprintf(file,
" fill \"#000000\"\n");
5754 fprintf(file,
" fill \"#FF0000\"\n");
5756 fprintf(file,
" style \"dashed\"\n");
5757 fprintf(file,
" width 1\n");
5758 fprintf(file,
" targetArrow \"standard\"\n");
5759 fprintf(file,
" ]\n");
5760 fprintf(file,
" LabelGraphics\n");
5761 fprintf(file,
" [\n");
5762 fprintf(file,
" text \"%s\"\n", label);
5763 fprintf(file,
" ]\n");
5764 fprintf(file,
" ]\n");
5768 fprintf(file,
"]\n");
5803 assert(scip !=
NULL);
5804 assert(sepadata !=
NULL);
5805 assert(cutcoefs !=
NULL);
5806 assert(ncuts !=
NULL);
5807 assert(cutoff !=
NULL);
5811 assert(nvars == 0 || vars !=
NULL);
5817 for( i = 0; i < cutnnz; ++i )
5819 cutvars[i] = vars[cutinds[i]];
5825 sepadata->dynamiccuts) );
5835 SCIPdebugMsg(scip,
" -> found MCF cut <%s>: rhs=%f, act=%f eff=%f rank=%d\n",
5852 if( !(*cutoff) && sepadata->separateknapsack)
5855 SCIP_CALL(
SCIPseparateRelaxedKnapsack(scip,
NULL, sepa, cutnnz, cutvars, cutcoefs, +1.0, cutrhs, sol, cutoff, ncuts) );
5905 unsigned int partition;
5906 unsigned int allpartitions;
5907 unsigned int startpartition;
5921 maxsepacuts = sepadata->maxsepacutsroot;
5923 maxsepacuts = sepadata->maxsepacuts;
5924 if( maxsepacuts < 0 )
5925 maxsepacuts = INT_MAX;
5930 maxtestdelta = sepadata->maxtestdelta;
5931 if( maxtestdelta <= 0 )
5932 maxtestdelta = INT_MAX;
5968 if( nodepartition ==
NULL )
5972 allpartitions = (
unsigned int) nnodes;
5973 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nnodes: %d \n", maxtestdelta, maxsepacuts, nnodes);
5980 int nclusters = nodepartition->nclusters;
5982 assert((
unsigned int)nclusters <= 8*
sizeof(
unsigned int));
5983 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nclusters: %d \n", maxtestdelta, maxsepacuts, nclusters);
5990 allpartitions = (1 << (nclusters-1));
5994 for( partition = startpartition; partition <= allpartitions-1 && !
SCIPisStopped(scip) && *ncuts < maxsepacuts && !*cutoff; partition++ )
6008 if( sepadata->checkcutshoreconnectivity )
6015 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x \n", partition );
6016 SCIPdebugMsg(scip,
" -> either shore S or shore T is not connected - skip partition.\n");
6021 for( inverted =
FALSE; inverted <= useinverted && !*cutoff; inverted++ )
6023 if( nodepartition ==
NULL )
6025 SCIPdebugMsg(scip,
"generating single-node cuts for node %u (inverted: %u)\n", partition, inverted);
6029 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x (inverted: %u)\n", partition, inverted);
6033 SCIP_CALL( outputGraph(scip, mcfnetwork, nodepartition, inverted, partition) );
6051 for( v = 0; v <
nnodes; v++ )
6065 if( nodeflowrows[v][k] ==
NULL )
6068 if( nodeflowscales[v][k] > 0.0 )
6072 if( nodeflowinverted[v][k] )
6075 comcutdemands[k] += rhs * nodeflowscales[v][k];
6078 assert (1 <= nnodesinS && nnodesinS <= nnodes-1);
6083 if( sepadata->separatesinglenodecuts && nodepartition !=
NULL && (nnodesinS == 1 || nnodesinS == nnodes-1) )
6085 SCIPdebugMsg(scip,
" -> shore S or T has only one node - skip partition.\n");
6095 SCIPdebugMsg(scip,
" -> commodity %d: directed cutdemand=%g\n", k, comcutdemands[k]);
6105 SCIPdebugMsg(scip,
" -> commodity %d: undirected cutdemand=%g\n", k, comcutdemands[k]);
6110 if( k == ncommodities )
6114 for( a = 0; a <
narcs; a++ )
6123 assert(arcsources[a] < nnodes);
6124 assert(arctargets[a] < nnodes);
6130 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) ||
6140 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6146 if( !
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6155 if( arccapacityrows[a] ==
NULL )
6163 assert(rowweights[r] == 0.0);
6169 if( arcsources[a] == -1 || arctargets[a] == -1 )
6179 assert(maxcoef > 0.0);
6184 rowweights[
r] = arccapacityscales[
a];
6185 SCIPdebugMsg(scip,
" -> arc %d, r=%d, capacity row <%s>: weight=%g slack=%g dual=%g\n", a, r,
SCIProwGetName(arccapacityrows[a]), rowweights[r],
6189 if( sepadata->separateflowcutset )
6191 if( rowweights[r] > 0.0 )
6201 for( j = 0; j < rowlen; j++ )
6206 coef = rowvals[j] * arccapacityscales[
a];
6212 k = colcommodity[c];
6214 comdemands[k] = coef;
6228 while( left <= right )
6230 int mid = (left+right)/2;
6232 if(
REALABS( deltas[mid] / coef - 1.0 ) < 1e-03 )
6237 else if( coef < deltas[mid] )
6246 assert(right == left-1);
6247 assert(ndeltas <= deltassize);
6248 if( ndeltas == deltassize )
6253 if( left < ndeltas )
6255 for( d = ndeltas; d > left; d-- )
6256 deltas[d] = deltas[d-1];
6258 deltas[left] = coef;
6260 SCIPdebugMsg(scip,
" -> new capacity %g considered as delta\n", coef);
6267 for( v = 0; v <
nnodes; v++ )
6276 if( comdemands[k] == 0.0 )
6279 scale = comdemands[k];
6302 if( comcutdemands[k] > 0.0 )
6321 if( nodeflowrows[v][k] ==
NULL )
6330 assert(rowweights[r] == 0.0);
6336 rowweights[
r] = scale * nodeflowscales[v][k];
6337 if( nodeflowinverted[v][k] )
6338 rowweights[
r] *= -1.0;
6339 SCIPdebugMsg(scip,
" -> node %d, commodity %d, r=%d, flow row <%s>: scale=%g weight=%g slack=%g dual=%g\n",
6340 v, k, r,
SCIProwGetName(nodeflowrows[v][k]), scale, rowweights[r],
6343 if( sepadata->separateflowcutset )
6345 if( nodeflowscales[v][k] > 0.0 )
6361 if( sepadata->separateflowcutset )
6364 bestdelta = deltas[ndeltas-1];
6374 SCIPdebugMsg(scip,
" -> found %d different deltas to try\n", ndeltas);
6375 for( d = ndeltas-1; d >= 0 && d >= ndeltas-maxtestdelta; d-- )
6389 SCIPdebugMsg(scip,
"applying MIR with delta = %g\n", deltas[d]);
6390 SCIP_CALL(
SCIPcalcMIR(scip, sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal, sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6391 1.0/deltas[d], aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6392 assert(allowlocal || !cutislocal);
6400 if( sepadata->separateflowcutset )
6402 if( cutefficacy > bestefficacy )
6404 bestdelta = deltas[d];
6405 bestefficacy = cutefficacy;
6411 SCIPdebugMsg(scip,
"success -> delta = %g -> rhs: %g, efficacy: %g\n", deltas[d], cutrhs, cutefficacy);
6412 SCIP_CALL(
addCut(scip, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );
6417 for( a = 0; a <
narcs; a++ )
6419 if( arccapacityrows[a] !=
NULL )
6425 if( r >= 0 && rowweights[r] != 0.0 )
6427 MCFdebugMessage(
" -> arc %d, capacity row <%s>: weight=%g slack=%g prod=%g dual=%g\n", a,
6440 if( sepadata->separateflowcutset && oldncuts == *ncuts && !*cutoff )
6443 f0 =
SCIPfrac(scip, baserhs/bestdelta);
6448 totalviolationdelta = 0.0;
6449 onedivoneminsf0 = 1.0/(1.0 - f0);
6450 for( a = 0; a <
narcs; a++ )
6464 if( arccapacityrows[a] ==
NULL )
6475 if( rowweights[r] == 0.0 )
6490 rowweight = rowweights[
r]/bestdelta;
6495 violationdelta = rowweight * (rowlhs - rowconstant);
6497 violationdelta = rowweight * (rowrhs - rowconstant);
6499 for( j = 0; j < rowlen; j++ )
6507 coef = rowvals[j] * rowweight;
6518 if( colcommodity[c] >= 0 )
6529 mircoef =
SCIPfloor(scip, coef) + (fj - f0)*onedivoneminsf0;
6536 mircoef = coef * onedivoneminsf0;
6541 if( colcommodity[c] >= 0 )
6542 violationdelta += mircoef * solval;
6544 violationdelta -= mircoef * solval;
6549 SCIPdebugMsg(scip,
" -> discarding capacity row <%s> of weight %g and slack %g: increases MIR violation by %g\n",
6552 rowweights[
r] = 0.0;
6553 totalviolationdelta += violationdelta;
6558 if( totalviolationdelta > 0.0 )
6571 SCIPdebugMsg(scip,
"applying MIR with delta = %g to flowcut inequality (violation improvement: %g)\n", bestdelta, totalviolationdelta);
6578 SCIP_CALL(
SCIPcalcMIR(scip, sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal, sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6579 1.0/bestdelta, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6581 assert(allowlocal || !cutislocal);
6585 SCIPdebugMsg(scip,
" -> delta = %g -> rhs: %g, efficacy: %g\n", bestdelta, cutrhs, cutefficacy);
6586 SCIP_CALL(
addCut(scip, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );
6629 assert(result !=
NULL);
6642 if( ncols != nvars )
6644 MCFdebugMessage(
"%d variables but %d columns -> exit\n", nvars, ncols );
6657 colrowratio = (
SCIP_Real)ncols/(nrows+1e-9);
6661 assert(sepadata !=
NULL);
6670 if( colrowratio < MINCOLROWRATIO || colrowratio >
MAXCOLROWRATIO )
6679 if( sepadata->nmcfnetworks == -1 )
6687 for( i = 0; i < sepadata->nmcfnetworks; i++ )
6689 MCFdebugMessage(
" -> extracted network %d has %d nodes, %d (%d) arcs (uncapacitated), and %d commodities (modeltype: %s)\n",
6690 i, sepadata->mcfnetworks[i]->nnodes, sepadata->mcfnetworks[i]->narcs, sepadata->mcfnetworks[i]->nuncapacitatedarcs,
6691 sepadata->mcfnetworks[i]->ncommodities,
6693 SCIPdebug( mcfnetworkPrint(sepadata->mcfnetworks[i]) );
6696 #ifdef COUNTNETWORKVARIABLETYPES 6697 SCIP_CALL( printFlowSystemInfo(scip,sepadata->mcfnetworks,sepadata->nmcfnetworks));
6701 assert(sepadata->nmcfnetworks >= 0);
6702 assert(sepadata->mcfnetworks !=
NULL || sepadata->nmcfnetworks == 0);
6703 mcfnetworks = sepadata->mcfnetworks;
6704 nmcfnetworks = sepadata->nmcfnetworks;
6711 sepadata->lastroundsuccess =
FALSE;
6713 for( i = 0; i < nmcfnetworks && !cutoff; i++ )
6719 mcfnetwork = mcfnetworks[i];
6722 assert(mcfnetwork->
nnodes >= 2);
6723 assert(mcfnetwork->
narcs >= 1);
6730 MCFdebugMessage(
"MCF network has %d nodes and %d arcs. arc node ratio %.2f exceed --> exit\n",
6736 if( sepadata->separatesinglenodecuts )
6747 nodepartitionPrint(nodepartition);
6757 MCFdebugMessage(
"MCF network has %d nodes, %d arcs, %d commodities. Found %d MCF network cuts, cutoff = %u.\n",
6764 sepadata->lastroundsuccess =
TRUE;
6766 else if( ncuts > 0 )
6769 sepadata->lastroundsuccess =
TRUE;
6786 assert(scip !=
NULL);
6787 assert(sepa !=
NULL);
6805 assert(sepadata !=
NULL);
6806 assert(sepadata->mcfnetworks ==
NULL);
6807 assert(sepadata->nmcfnetworks == -1);
6825 assert(sepadata !=
NULL);
6827 sepadata->lastroundsuccess =
TRUE;
6844 assert(sepadata !=
NULL);
6847 for( i = 0; i < sepadata->nmcfnetworks; i++ )
6852 sepadata->nmcfnetworks = -1;
6914 sepadata->mcfnetworks =
NULL;
6915 sepadata->nmcfnetworks = -1;
6917 sepadata->lastroundsuccess =
TRUE;
6923 sepaExeclpMcf, sepaExecsolMcf,
6926 assert(sepa !=
NULL);
6937 "separating/mcf/nclusters",
6938 "number of clusters to generate in the shrunken network -- default separation",
6941 "separating/mcf/maxweightrange",
6942 "maximal valid range max(|weights|)/min(|weights|) of row weights",
6945 "separating/mcf/maxtestdelta",
6946 "maximal number of different deltas to try (-1: unlimited) -- default separation",
6949 "separating/mcf/trynegscaling",
6950 "should negative values also be tested in scaling?",
6953 "separating/mcf/fixintegralrhs",
6954 "should an additional variable be complemented if f0 = 0?",
6957 "separating/mcf/dynamiccuts",
6958 "should generated cuts be removed from the LP if they are no longer tight?",
6961 "separating/mcf/modeltype",
6962 "model type of network (0: auto, 1:directed, 2:undirected)",
6965 "separating/mcf/maxsepacuts",
6966 "maximal number of mcf cuts separated per separation round",
6969 "separating/mcf/maxsepacutsroot",
6970 "maximal number of mcf cuts separated per separation round in the root node -- default separation",
6973 "separating/mcf/maxinconsistencyratio",
6974 "maximum inconsistency ratio for separation at all",
6977 "separating/mcf/maxarcinconsistencyratio",
6978 "maximum inconsistency ratio of arcs not to be deleted",
6981 "separating/mcf/checkcutshoreconnectivity",
6982 "should we separate only if the cuts shores are connected?",
6985 "separating/mcf/separatesinglenodecuts",
6986 "should we separate inequalities based on single-node cuts?",
6989 "separating/mcf/separateflowcutset",
6990 "should we separate flowcutset inequalities on the network cuts?",
6993 "separating/mcf/separateknapsack",
6994 "should we separate knapsack cover inequalities on the network cuts?",
enum SCIP_Result SCIP_RESULT
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
static SCIP_RETCODE mcfnetworkCreate(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
#define DEFAULT_TRYNEGSCALING
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_RETCODE extractFlowRows(SCIP *scip, MCFDATA *mcfdata)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
public methods for SCIP parameter handling
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_Bool ** nodeflowinverted
SCIP_RETCODE SCIPcaptureRow(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNLPRows(SCIP *scip)
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
#define SCIPfreeMemoryArrayNull(scip, ptr)
public methods for memory management
static SCIP_RETCODE nodepairqueueCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPAIRQUEUE **nodepairqueue)
static SCIP_RETCODE identifySourcesTargets(SCIP *scip, MCFDATA *mcfdata, SCIP_SEPADATA *sepadata, MCFEFFORTLEVEL *effortlevel)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
#define SCIPallocMemoryArray(scip, ptr, num)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_RETCODE extractFlow(SCIP *scip, MCFDATA *mcfdata, SCIP_Real maxflowvarflowrowratio, SCIP_Bool *failed)
int SCIPgetNLPCols(SCIP *scip)
static SCIP_RETCODE extractCapacities(SCIP *scip, MCFDATA *mcfdata)
int SCIPgetNLPBranchCands(SCIP *scip)
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE identifyComponent(SCIP *scip, MCFDATA *mcfdata, int *nodevisited, int startv, int *compnodes, int *ncompnodes, int *comparcs, int *ncomparcs)
#define DEFAULT_MODELTYPE
struct nodepairqueue NODEPAIRQUEUE
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
int SCIPgetNVars(SCIP *scip)
#define DEFAULT_MAXINCONSISTENCYRATIO
static SCIP_RETCODE nodepartitionCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION **nodepartition, int nclusters)
static void nodepairqueueFree(SCIP *scip, NODEPAIRQUEUE **nodepairqueue)
SCIP_RETCODE SCIPseparateRelaxedKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPincludeSepaMcf(SCIP *scip)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
methods for the aggregation rows
int SCIProwGetRank(SCIP_ROW *row)
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_DECL_SORTINDCOMP(compCands)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
static SCIP_DECL_HASHKEYVAL(hashKeyValNodepairs)
public methods for problem variables
#define DEFAULT_FIXINTEGRALRHS
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
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)
static SCIP_DECL_SORTPTRCOMP(compNodepairs)
static SCIP_RETCODE getNodeSimilarityScore(SCIP *scip, MCFDATA *mcfdata, int baserowlen, int *basearcpattern, int basenposuncap, int basenneguncap, SCIP_ROW *row, SCIP_Real *score, SCIP_Bool *invertcommodity)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
#define DEFAULT_CHECKCUTSHORECONNECTIVITY
static NODEPAIRENTRY * nodepairqueueRemove(NODEPAIRQUEUE *nodepairqueue)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_MCFMODELTYPE modeltype
#define SCIPfreeBufferArray(scip, ptr)
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_RESULT *result)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
public methods for separator plugins
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE mcfnetworkExtract(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_MCFNETWORK ***mcfnetworks, int *nmcfnetworks, MCFEFFORTLEVEL *effortlevel)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define MAXFLOWCANDDENSITY
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for querying solving statistics
static SCIP_RETCODE findUncapacitatedArcs(SCIP *scip, MCFDATA *mcfdata)
public methods for the branch-and-bound tree
#define MAXFLOWVARFLOWROWRATIO
#define DEFAULT_MAXTESTDELTA
#define DEFAULT_SEPARATEFLOWCUTSET
static void getIncidentNodes(SCIP *scip, MCFDATA *mcfdata, SCIP_COL *col, int *sourcenode, int *targetnode)
Constraint handler for knapsack constraints of the form , x binary and .
static SCIP_DECL_SEPACOPY(sepaCopyMcf)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
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)
#define MAXAGGRLEN(nvars)
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
static void unionfindJoinSets(int *representatives, int rep1, int rep2)
#define DEFAULT_MAXSEPACUTSROOT
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
static SCIP_Bool nodeInPartition(NODEPARTITION *nodepartition, unsigned int partition, SCIP_Bool inverted, int v)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
static void nodepartitionJoin(NODEPARTITION *nodepartition, int rep1, int rep2)
static SCIP_RETCODE createNewArc(SCIP *scip, MCFDATA *mcfdata, int source, int target, int *newarcid)
#define SCIPallocBuffer(scip, ptr)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static int nodepartitionIsConnected(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, unsigned int partition)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPcolGetNLPNonz(SCIP_COL *col)
#define DEFAULT_MAXSEPACUTS
static SCIP_RETCODE cleanupNetwork(SCIP *scip, MCFDATA *mcfdata)
enum McfEffortLevel MCFEFFORTLEVEL
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_EXPORT SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
SCIP_EXPORT const char * SCIPsepaGetName(SCIP_SEPA *sepa)
#define DEFAULT_MAXWEIGHTRANGE
static SCIP_RETCODE mcfnetworkFill(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, MCFDATA *mcfdata, int *compnodeid, int *compnodes, int ncompnodes, int *comparcs, int ncomparcs)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
static void collectIncidentFlowCols(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *flowrow, int basecommodity)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
struct nodepair NODEPAIRENTRY
multi-commodity-flow network cut separator
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
int SCIPgetDepth(SCIP *scip)
#define DEFAULT_NCLUSTERS
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
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_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
enum SCIP_McfModeltype SCIP_MCFMODELTYPE
static SCIP_DECL_HASHKEYEQ(hashKeyEqNodepairs)
static SCIP_DECL_SEPAEXITSOL(sepaExitsolMcf)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_ROW ** arccapacityrows
public methods for LP management
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
public methods for cuts and aggregation rows
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
void SCIProwChgRank(SCIP_ROW *row, int rank)
static void deleteCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int nrows, int *ndelflowrows, int *ndelflowvars)
#define UNCAPACITATEDARCSTRESHOLD
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_VAR * SCIPcolGetVar(SCIP_COL *col)
public methods for the LP relaxation, rows and columns
static void getNextFlowrow(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW **nextrow, unsigned char *nextrowsign, SCIP_Bool *nextinvertcommodity)
#define HASHSIZE_NODEPAIRS
#define SCIPfreeMemory(scip, ptr)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE mcfnetworkFree(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
methods for sorting joint arrays of various types
public methods for branching rule plugins and branching
SCIP_EXPORT SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
#define DEFAULT_MAXARCINCONSISTENCYRATIO
#define SCIPfreeBuffer(scip, ptr)
#define DEFAULT_SEPARATEKNAPSACK
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
static void fixCommoditySigns(MCFDATA *mcfdata)
static int nodepartitionGetRepresentative(NODEPARTITION *nodepartition, int v)
#define DEFAULT_SEPARATESINGLENODECUTS
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_EXPORT void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz, SCIP_Bool cutislocal, int cutrank, int *ncuts, SCIP_Bool *cutoff)
public methods for message output
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPsnprintf(char *t, int len, const char *s,...)
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_Real ** nodeflowscales
static SCIP_RETCODE extractCapacityRows(SCIP *scip, MCFDATA *mcfdata)
const char * SCIProwGetName(SCIP_ROW *row)
#define MINCOMNODESFRACTION
public methods for message handling
static SCIP_DECL_SEPAEXECSOL(sepaExecsolMcf)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
static void getFlowrowFit(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, int k, unsigned char *rowsign, SCIP_Bool *invertcommodity)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
static SCIP_DECL_SEPAINITSOL(sepaInitsolMcf)
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
#define SCIPallocMemory(scip, ptr)
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
static SCIP_DECL_SEPAEXECLP(sepaExeclpMcf)
SCIP_ROW *** nodeflowrows
SCIP_Real * arccapacityscales
SCIP_EXPORT void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
static SCIP_Bool nodepairqueueIsEmpty(NODEPAIRQUEUE *nodepairqueue)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
public methods for separators
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
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)
static void unionfindInitSets(int *representatives, int nelems)
static void invertCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int ncomrows, int *comcolids, int ncomcolids)
#define DEFAULT_DYNAMICCUTS
static SCIP_RETCODE generateClusterCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, int *ncuts, SCIP_Bool *cutoff)
static int unionfindGetRepresentative(int *representatives, int v)
static void addFlowrowToCommodity(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, unsigned char rowsign, int *comcolids, int *ncomcolids)
public methods for global and local (sub)problems
static SCIP_DECL_HASHGETKEY(hashGetKeyNodepairs)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
static SCIP_RETCODE extractNodes(SCIP *scip, MCFDATA *mcfdata)
struct nodepartition NODEPARTITION
static SCIP_DECL_SEPAFREE(sepaFreeMcf)
struct SCIP_SepaData SCIP_SEPADATA
int SCIPcolGetLPPos(SCIP_COL *col)
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)
static void nodepartitionFree(SCIP *scip, NODEPARTITION **nodepartition)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE createNewCommodity(SCIP *scip, MCFDATA *mcfdata)
#define SCIPreallocBufferArray(scip, ptr, num)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
memory allocation routines