56 #define BETTERWEIGHTFORDEMANDNODES 84 #define SEPA_NAME "mcf" 85 #define SEPA_DESC "multi-commodity-flow network cut separator" 86 #define SEPA_PRIORITY -10000 88 #define SEPA_MAXBOUNDDIST 0.0 89 #define SEPA_USESSUBSCIP FALSE 90 #define SEPA_DELAY FALSE 93 #define DEFAULT_NCLUSTERS 5 94 #define DEFAULT_MAXWEIGHTRANGE 1e+06 95 #define DEFAULT_MAXTESTDELTA 20 96 #define DEFAULT_TRYNEGSCALING FALSE 97 #define DEFAULT_FIXINTEGRALRHS TRUE 98 #define DEFAULT_DYNAMICCUTS TRUE 99 #define DEFAULT_MODELTYPE 0 100 #define DEFAULT_MAXSEPACUTS 100 101 #define DEFAULT_MAXSEPACUTSROOT 200 102 #define DEFAULT_MAXINCONSISTENCYRATIO 0.02 103 #define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5 104 #define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE 105 #define DEFAULT_SEPARATESINGLENODECUTS TRUE 106 #define DEFAULT_SEPARATEFLOWCUTSET TRUE 107 #define DEFAULT_SEPARATEKNAPSACK TRUE 110 #define BOUNDSWITCH 0.5 111 #define POSTPROCESS TRUE 114 #define MAXFRAC 0.999 116 #define MAXCOLS 2000000 117 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 118 #define MINCOLROWRATIO 0.01 119 #define MAXCOLROWRATIO 100.0 120 #define MAXFLOWVARFLOWROWRATIO 100.0 121 #define MAXARCNODERATIO 100.0 122 #define MAXNETWORKS 4 123 #define MAXFLOWCANDDENSITY 0.1 124 #define MINCOMNODESFRACTION 0.5 127 #define MAXCAPACITYSLACK 0.1 128 #define UNCAPACITATEDARCSTRESHOLD 0.8 129 #define HASHSIZE_NODEPAIRS 500 141 #define MCFdebugMessage printf 145 #define MCFdebugMessage while(FALSE) printf 219 unsigned char* flowrowsigns;
222 unsigned char* capacityrowsigns;
231 int nemptycommodities;
233 int commoditysignssize;
254 int capacityrowssize;
281 int* representatives;
293 #define LHSPOSSIBLE 1u 294 #define RHSPOSSIBLE 2u 295 #define LHSASSIGNED 4u 296 #define RHSASSIGNED 8u 298 #define DISCARDED 32u 299 #define UNDIRECTED 64u 309 assert(mcfnetwork !=
NULL);
312 (*mcfnetwork)->nodeflowrows =
NULL;
313 (*mcfnetwork)->nodeflowscales =
NULL;
314 (*mcfnetwork)->nodeflowinverted =
NULL;
315 (*mcfnetwork)->arccapacityrows =
NULL;
316 (*mcfnetwork)->arccapacityscales =
NULL;
317 (*mcfnetwork)->arcsources =
NULL;
318 (*mcfnetwork)->arctargets =
NULL;
319 (*mcfnetwork)->colcommodity =
NULL;
320 (*mcfnetwork)->nnodes = 0;
321 (*mcfnetwork)->nuncapacitatedarcs = 0;
322 (*mcfnetwork)->narcs = 0;
323 (*mcfnetwork)->ncommodities = 0;
335 assert(mcfnetwork !=
NULL);
337 if( *mcfnetwork !=
NULL )
342 for( v = 0; v < (*mcfnetwork)->nnodes; v++ )
346 for( k = 0; k < (*mcfnetwork)->ncommodities; k++ )
348 if( (*mcfnetwork)->nodeflowrows[v][k] !=
NULL )
357 for( a = 0; a < (*mcfnetwork)->narcs; a++ )
359 if( (*mcfnetwork)->arccapacityrows[a] !=
NULL )
392 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
393 SCIP_Real* flowrowscalars = mcfdata->flowrowscalars;
394 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
395 int* flowcands = mcfdata->flowcands;
396 int nflowcands = mcfdata->nflowcands;
398 int* commoditysigns = mcfdata->commoditysigns;
400 int* rowcommodity = mcfdata->rowcommodity;
401 int* rownodeid = mcfdata->rownodeid;
402 SCIP_ROW** capacityrows = mcfdata->capacityrows;
411 int ncompcommodities;
418 assert(mcfnetwork !=
NULL);
420 assert(2 <= ncompnodes && ncompnodes <= mcfdata->
nnodes);
421 assert(1 <= ncomparcs && ncomparcs <= mcfdata->
narcs);
422 assert(ncommodities > 0);
426 for( v = 0; v < mcfdata->nnodes; v++ )
427 assert(compnodeid[v] == -1);
439 compcommodity[k] = -1;
446 for( i = 0; i < ncompnodes; i++ )
449 assert(0 <= v && v < mcfdata->nnodes);
454 ncompcommodities = 0;
455 for( i = 0; i < nflowcands; i++ )
461 assert(0 <= r && r < nrows);
464 if( rv >= 0 && compnodeid[rv] >= 0 )
467 assert(0 <= k && k < ncommodities);
468 if( compcommodity[k] == -1 )
470 compcommodity[k] = ncompcommodities;
481 mcfnetwork->
nnodes = ncompnodes;
482 mcfnetwork->
narcs = ncomparcs;
490 for( v = 0; v < mcfnetwork->
nnodes; v++ )
508 for( a = 0; a < mcfnetwork->
narcs; a++ )
518 for( i = 0; i < nflowcands; i++ )
524 assert(0 <= r && r < nrows);
527 if( rv >= 0 && compnodeid[rv] >= 0 )
533 rk = rowcommodity[
r];
534 assert(v < mcfnetwork->nnodes);
535 assert(0 <= rk && rk < ncommodities);
538 k = compcommodity[rk];
539 assert(0 <= k && k < mcfnetwork->ncommodities);
544 scale = flowrowscalars[
r];
547 if( commoditysigns[rk] == -1 )
555 for( a = 0; a < mcfnetwork->
narcs; a++ )
565 globala = comparcs[
a];
566 capacityrow = capacityrows[globala];
571 if( capacityrow !=
NULL)
574 assert(0 <= r && r < nrows);
576 assert((capacityrowsigns[r] &
INVERTED) == 0);
577 assert(mcfdata->rowarcid[r] == globala);
595 for( j = 0; j < rowlen; j++ )
602 if( comdemands[k] != 0.0 )
617 for( j = 0; j < rowlen; j++ )
622 if( k >= 0 && comdemands[k] == 0.0 )
634 if( mcfdata->arcsources[globala] >= 0 )
636 assert(mcfdata->arcsources[globala] < mcfdata->nnodes);
637 assert(0 <= compnodeid[mcfdata->arcsources[globala]] && compnodeid[mcfdata->arcsources[globala]] < mcfnetwork->
nnodes);
638 mcfnetwork->
arcsources[
a] = compnodeid[mcfdata->arcsources[globala]];
640 if( mcfdata->arctargets[globala] >= 0 )
642 assert(mcfdata->arctargets[globala] < mcfdata->nnodes);
643 assert(0 <= compnodeid[mcfdata->arctargets[globala]] && compnodeid[mcfdata->arctargets[globala]] < mcfnetwork->
nnodes);
644 mcfnetwork->
arctargets[
a] = compnodeid[mcfdata->arctargets[globala]];
649 for( c = 0; c < ncols; c++ )
659 for( i = 0; i < ncompnodes; i++ )
661 assert(0 <= compnodes[i] && compnodes[i] < mcfdata->nnodes);
662 assert(compnodeid[compnodes[i]] == i);
663 compnodeid[compnodes[i]] = -1;
676 void mcfnetworkPrint(
680 if( mcfnetwork ==
NULL )
687 for( v = 0; v < mcfnetwork->
nnodes; v++ )
706 for( a = 0; a < mcfnetwork->
narcs; a++ )
722 void printCommodities(
727 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
728 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
730 int* commoditysigns = mcfdata->commoditysigns;
732 int* rowcommodity = mcfdata->rowcommodity;
733 int* colarcid = mcfdata->colarcid;
734 int* rownodeid = mcfdata->rownodeid;
735 int nnodes = mcfdata->nnodes;
736 SCIP_ROW** capacityrows = mcfdata->capacityrows;
756 for( c = 0; c < ncols; c++ )
758 if( colcommodity[c] == k )
761 for( r = 0; r < nrows; r++ )
763 if( rowcommodity[r] == k )
766 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
771 if( rownodeid !=
NULL )
775 for( v = 0; v <
nnodes; v++ )
778 for( r = 0; r < nrows; r++ )
780 if( rownodeid[r] == v )
783 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
789 assert(capacityrows !=
NULL || mcfdata->narcs == 0);
792 for( a = 0; a < mcfdata->narcs; a++ )
795 if( capacityrows[a] !=
NULL )
798 assert(0 <= r && r < nrows);
801 else if( (capacityrowsigns[r] &
RHSASSIGNED) != 0 )
809 assert(colcommodity !=
NULL || ncols == 0);
812 for( c = 0; c < ncols; c++ )
814 if( colcommodity[c] == -1 )
823 for( r = 0; r < nrows; r++ )
825 assert(rowcommodity !=
NULL);
843 if( rowscores[ind2] < rowscores[ind1] )
845 else if( rowscores[ind2] > rowscores[ind1] )
858 unsigned char* flowrowsigns;
878 flowrowsigns = mcfdata->flowrowsigns;
879 flowrowscalars = mcfdata->flowrowscalars;
880 flowrowscores = mcfdata->flowrowscores;
881 flowcands = mcfdata->flowcands;
883 assert(mcfdata->nflowcands == 0);
886 for( r = 0; r < nrows; r++ )
911 absdualsol = ABS(absdualsol);
914 flowrowscalars[
r] = 0.0;
915 flowrowscores[
r] = 0.0;
936 coef = ABS(rowvals[0]);
943 for( i = 0; i < rowlen; i++ )
949 hasposcoef = hasposcoef || (rowvals[i] > 0.0);
950 hasnegcoef = hasnegcoef || (rowvals[i] < 0.0);
980 flowrowscalars[
r] = 1.0/coef;
981 flowcands[mcfdata->nflowcands] =
r;
982 mcfdata->nflowcands++;
989 if(
SCIPisEQ(scip, flowrowscalars[r], 1.0) )
990 flowrowscores[
r] += 1000.0;
993 if( hasposcoef && hasnegcoef )
994 flowrowscores[
r] += 500.0;
1001 if( ncontvars == rowlen )
1002 flowrowscores[
r] += 1000.0;
1003 else if( nintvars + nimplintvars == rowlen )
1004 flowrowscores[
r] += 500.0;
1005 else if( nbinvars == rowlen )
1006 flowrowscores[
r] += 100.0;
1010 flowrowscores[
r] += 10.0*rowlen/(rowlen+10.0);
1014 flowrowscores[
r] += 50.0;
1016 assert(flowrowscores[r] > 0.0);
1019 maxdualflow =
MAX(maxdualflow, absdualsol);
1032 for( i = 0; i < mcfdata->nflowcands; i++ )
1037 assert(0 <= r && r < nrows);
1042 dualsol = ABS(dualsol);
1045 assert(maxdualflow > 0.0);
1046 flowrowscores[
r] += dualsol/maxdualflow + 1.0;
1047 assert(flowrowscores[r] > 0.0);
1052 SCIPsortInd(mcfdata->flowcands, compCands, (
void*)flowrowscores, mcfdata->nflowcands);
1054 MCFdebugMessage(
"flow conservation candidates [%d]\n", mcfdata->nflowcands);
1056 for( r = 0; r < mcfdata->nflowcands; r++ )
1059 SCIPdebugMsg(scip,
"%4d [score: %2g]: %s\n", mcfdata->flowcands[r], flowrowscores[mcfdata->flowcands[r]],
1074 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1077 int nactivecommodities = mcfdata->ncommodities - mcfdata->nemptycommodities;
1080 unsigned char* capacityrowsigns;
1089 int maxcolspercommoditylimit;
1090 int *ncolspercommodity;
1091 int *maxcolspercommodity;
1101 capacityrowsigns = mcfdata->capacityrowsigns;
1102 capacityrowscores = mcfdata->capacityrowscores;
1103 capacitycands = mcfdata->capacitycands;
1105 assert(mcfdata->ncapacitycands == 0);
1115 maxcolspercommoditylimit = 2;
1118 maxcolspercommoditylimit = 1;
1121 maxcolspercommoditylimit = 2;
1124 SCIPerrorMessage(
"invalid parameter value %d for model type\n", modeltype);
1128 maxdualcapacity = 0.0;
1129 directedcandsscore = 0.0;
1130 undirectedcandsscore = 0.0;
1131 for( r = 0; r < nrows; r++ )
1141 int nposcapacitycoefs;
1142 int nnegcapacitycoefs;
1144 int ncoveredcommodities;
1149 unsigned char rowsign;
1155 capacityrowsigns[
r] = 0;
1156 capacityrowscores[
r] = 0.0;
1175 absdualsol = ABS(absdualsol);
1184 maxcolspercommodity[
r] = 0;
1189 nposcapacitycoefs = 0;
1190 nnegcapacitycoefs = 0;
1192 ncoveredcommodities = 0;
1194 sameabsflowcoef = 0.0;
1195 maxabscapacitycoef = 0.0;
1202 for( i = 0; i < rowlen; i++ )
1209 assert(colcommodity !=
NULL);
1212 k = colcommodity[c];
1213 assert(-1 <= k && k < ncommodities);
1218 abscoef = ABS(rowvals[i]);
1219 if( sameflowcoef == 0.0 )
1220 sameflowcoef = rowvals[i];
1221 else if( !
SCIPisEQ(scip, sameflowcoef, rowvals[i]) )
1223 if( sameabsflowcoef == 0.0 )
1224 sameabsflowcoef = abscoef;
1225 else if( !
SCIPisEQ(scip, sameabsflowcoef, abscoef) )
1228 if( rowvals[i] > 0.0 )
1234 if( ncolspercommodity[k] == 0 )
1235 ncoveredcommodities++;
1236 ncolspercommodity[k]++;
1237 maxcolspercommodity[
r] =
MAX(maxcolspercommodity[r], ncolspercommodity[k]);
1239 if( ncolspercommodity[k] >= 2 )
1248 abscoef = ABS(rowvals[i]);
1249 if( abscoef > maxabscapacitycoef )
1250 maxabscapacitycoef = abscoef;
1253 if( rowvals[i] > 0.0 )
1254 nposcapacitycoefs++;
1256 nnegcapacitycoefs++;
1266 if( rowsign != 0 && nposflowcoefs + nnegflowcoefs > 0 )
1270 capacityrowsigns[
r] |= rowsign;
1271 capacitycands[mcfdata->ncapacitycands] =
r;
1272 mcfdata->ncapacitycands++;
1275 capacityrowscores[
r] = 1.0;
1279 assert(ncoveredcommodities > 0);
1281 commodityexcessratio =
1282 ABS((nposflowcoefs + nnegflowcoefs)/(
SCIP_Real)ncoveredcommodities - maxcolspercommoditylimit);
1284 capacityrowscores[
r] += 1000.0 *
MAX(0.0, 2.0 - commodityexcessratio);
1291 if( (capacityrowsigns[r] &
RHSPOSSIBLE) != 0 && nnegflowcoefs == 0 && nposcapacitycoefs == 0 && nnegcapacitycoefs > 0 )
1292 capacityrowscores[
r] += 1000.0;
1293 if( (capacityrowsigns[r] &
LHSPOSSIBLE) != 0 && nposflowcoefs == 0 && nposcapacitycoefs > 0 && nnegcapacitycoefs == 0 )
1294 capacityrowscores[
r] += 1000.0;
1303 assert(nactivecommodities + 3 > 0);
1304 capacityrowscores[
r] += 2000.0 * ncoveredcommodities/(
SCIP_Real)(nactivecommodities + 3);
1307 if(
SCIPisEQ(scip, ABS(sameflowcoef), 1.0) )
1308 capacityrowscores[r] += 500.0;
1312 capacityrowscores[
r] += 250.0;
1315 if(
SCIPisEQ(scip, sameabsflowcoef, 1.0) )
1316 capacityrowscores[r] += 100.0;
1319 if( maxabscapacitycoef > 0.0 && !
SCIPisEQ(scip, maxabscapacitycoef, 1.0) )
1320 capacityrowscores[r] += 100.0;
1323 capacityrowscores[
r] += 20.0 *
MAX(nposflowcoefs, nnegflowcoefs)/
MAX(1.0,(
SCIP_Real)(nposflowcoefs + nnegflowcoefs));
1326 capacityrowscores[
r] += 10.0 *
MAX(nposcapacitycoefs, nnegcapacitycoefs)/(
SCIP_Real)(nposcapacitycoefs+nnegcapacitycoefs+1.0);
1329 if( (capacityrowsigns[r] & RHSPOSSIBLE) != 0 && !
SCIPisNegative(scip, rowrhs) )
1330 capacityrowscores[r] += 10.0;
1334 capacityrowscores[r] += 10.0;
1336 assert(capacityrowscores[r] > 0.0);
1337 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",
1338 SCIProwGetName(row), maxcolspercommodity[r], capacityrowsigns[r], nposflowcoefs, nnegflowcoefs, nposcapacitycoefs, nnegcapacitycoefs, nbadcoefs, nactivecommodities, sameflowcoef, capacityrowscores[r]);
1341 maxdualcapacity =
MAX(maxdualcapacity, absdualsol);
1346 assert(maxcolspercommoditylimit == 2);
1347 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1348 undirectedcandsscore += capacityrowscores[
r];
1350 directedcandsscore += capacityrowscores[
r];
1355 SCIPdebugMsg(scip,
"row <%s>: rowsign = %d nposflowcoefs = %d nnegflowcoefs = %d -> discard\n",
1363 if( directedcandsscore > undirectedcandsscore )
1368 MCFdebugMessage(
"detected model type: %s (%g directed score, %g undirected score)\n",
1376 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1378 r = capacitycands[i];
1379 assert(0 <= r && r < nrows);
1380 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1383 if( maxcolspercommodity[r] <= maxcolspercommoditylimit )
1384 capacityrowscores[
r] -= 1000.0;
1398 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1402 r = capacitycands[i];
1403 assert(0 <= r && r < nrows);
1408 dualsol = ABS(dualsol);
1411 assert(maxdualcapacity > 0.0);
1412 capacityrowscores[
r] +=
MAX(dualsol, 0.0)/maxdualcapacity;
1413 assert(capacityrowscores[r] > 0.0);
1418 SCIPsortInd(mcfdata->capacitycands, compCands, (
void*)capacityrowscores, mcfdata->ncapacitycands);
1420 MCFdebugMessage(
"capacity candidates [%d]\n", mcfdata->ncapacitycands);
1422 for( r = 0; r < mcfdata->ncapacitycands; r++ )
1424 SCIPdebugMsg(scip,
"row %4d [score: %2g]: %s\n", mcfdata->capacitycands[r],
1425 capacityrowscores[mcfdata->capacitycands[r]],
SCIProwGetName(rows[mcfdata->capacitycands[r]]));
1445 assert(mcfdata->ncommodities <= mcfdata->commoditysignssize);
1446 if( mcfdata->ncommodities == mcfdata->commoditysignssize )
1448 mcfdata->commoditysignssize =
MAX(2*mcfdata->commoditysignssize, mcfdata->ncommodities+1);
1451 assert(mcfdata->ncommodities < mcfdata->commoditysignssize);
1454 SCIPdebugMsg(scip,
"**** creating new commodity %d ****\n", mcfdata->ncommodities);
1455 mcfdata->commoditysigns[mcfdata->ncommodities] = 0;
1456 mcfdata->ncommodities++;
1471 assert(source != target );
1472 assert(0 <= source && source < mcfdata->
nnodes);
1473 assert(0 <= target && target < mcfdata->nnodes);
1474 assert(newarcid !=
NULL);
1476 *newarcid = mcfdata->narcs;
1479 assert(mcfdata->narcs <= mcfdata->arcarraysize);
1480 if( mcfdata->narcs == mcfdata->arcarraysize )
1482 mcfdata->arcarraysize =
MAX(2*mcfdata->arcarraysize, mcfdata->narcs+1);
1488 assert(mcfdata->narcs < mcfdata->arcarraysize);
1491 if( mcfdata->capacityrowssize < mcfdata->arcarraysize )
1493 mcfdata->capacityrowssize = mcfdata->arcarraysize;
1496 assert(mcfdata->narcs < mcfdata->capacityrowssize);
1499 SCIPdebugMsg(scip,
"**** creating new arc %d: %d -> %d ****\n", mcfdata->narcs, source, target);
1501 mcfdata->arcsources[*newarcid] = source;
1502 mcfdata->arctargets[*newarcid] = target;
1503 mcfdata->nextoutarcs[*newarcid] = mcfdata->firstoutarcs[source];
1504 mcfdata->firstoutarcs[source] = *newarcid;
1505 mcfdata->nextinarcs[*newarcid] = mcfdata->firstinarcs[target];
1506 mcfdata->firstinarcs[target] = *newarcid;
1507 mcfdata->capacityrows[*newarcid] =
NULL;
1520 unsigned char rowsign,
1525 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1526 SCIP_Bool* plusflow = mcfdata->plusflow;
1527 SCIP_Bool* minusflow = mcfdata->minusflow;
1529 int* commoditysigns = mcfdata->commoditysigns;
1531 int* rowcommodity = mcfdata->rowcommodity;
1532 int* newcols = mcfdata->newcols;
1543 assert(comcolids !=
NULL);
1544 assert(ncomcolids !=
NULL);
1553 invertrow = ((rowsign &
INVERTED) != 0);
1556 assert(rowcommodity[r] == -1);
1557 assert((flowrowsigns[r] | rowsign) == flowrowsigns[r]);
1559 assert(rowsign != 0);
1565 commoditysigns[k] = +1;
1594 else if( rowlhs > 0.0 )
1611 flowrowsigns[
r] |= rowsign;
1613 SCIPdebugMsg(scip,
"adding flow row %d <%s> with sign %+d%s to commodity %d [score:%g]\n",
1615 k, mcfdata->flowrowscores[r]);
1619 rowcommodity[
r] = k;
1623 for( i = 0; i < rowlen; i++ )
1632 if( colcommodity[c] == -1 )
1634 assert(!plusflow[c]);
1635 assert(!minusflow[c]);
1637 colcommodity[c] = k;
1638 newcols[mcfdata->nnewcols] = c;
1639 mcfdata->nnewcols++;
1640 comcolids[*ncomcolids] = c;
1643 assert(colcommodity[c] == k);
1646 val = rowscale * rowvals[i];
1649 assert(!plusflow[c]);
1654 assert(!minusflow[c]);
1655 minusflow[c] =
TRUE;
1672 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1673 SCIP_Bool* plusflow = mcfdata->plusflow;
1674 SCIP_Bool* minusflow = mcfdata->minusflow;
1678 assert(mcfdata->commoditysigns[k] == 0);
1679 assert(comrows !=
NULL || ncomrows == 0);
1680 assert(comcolids !=
NULL);
1683 for( i = 0; i < ncomrows; i++ )
1687 unsigned char rowsign;
1689 assert(comrows !=
NULL);
1691 assert( row !=
NULL );
1694 assert(mcfdata->rowcommodity[r] == k);
1698 rowsign = flowrowsigns[
r];
1710 for( i = 0; i < ncomcolids; i++ )
1717 assert(mcfdata->colcommodity[c] == k);
1720 plusflow[c] = minusflow[c];
1737 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1738 SCIP_Bool* plusflow = mcfdata->plusflow;
1739 SCIP_Bool* minusflow = mcfdata->minusflow;
1742 int* rowcommodity = mcfdata->rowcommodity;
1746 assert(0 <= k && k < ncommodities);
1748 assert( ndelflowrows !=
NULL );
1749 assert( ndelflowvars !=
NULL );
1751 SCIPdebugMsg(scip,
"deleting commodity %d (%d total commodities) with %d flow rows\n", k, ncommodities, nrows);
1756 for( n = 0; n < nrows; n++ )
1767 assert(rowcommodity[r] == k);
1776 rowcommodity[
r] = -1;
1779 for( i = 0; i < rowlen; i++ )
1787 assert(colcommodity[c] == k || colcommodity[c] == -1);
1788 if(colcommodity[c] == k)
1790 colcommodity[c] = -1;
1793 plusflow[c] =
FALSE;
1794 minusflow[c] =
FALSE;
1803 if( k == ncommodities-1 )
1804 mcfdata->ncommodities--;
1806 mcfdata->nemptycommodities++;
1816 unsigned char* rowsign,
1820 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1821 SCIP_Bool* plusflow = mcfdata->plusflow;
1822 SCIP_Bool* minusflow = mcfdata->minusflow;
1824 int* rowcommodity = mcfdata->rowcommodity;
1825 int* commoditysigns = mcfdata->commoditysigns;
1830 unsigned char flowrowsign;
1831 unsigned char invflowrowsign;
1835 assert(invertcommodity !=
NULL);
1838 *invertcommodity =
FALSE;
1844 if( rowcommodity[r] != -1 )
1848 flowrowsign = flowrowsigns[
r];
1854 invflowrowsign = flowrowsign;
1860 for( j = 0; j < rowlen && (flowrowsign != 0 || invflowrowsign != 0); j++ )
1868 if( colcommodity[rowc] == k )
1871 if( plusflow[rowc] )
1874 if( rowvals[j] > 0.0 )
1885 if( minusflow[rowc] )
1888 if( rowvals[j] > 0.0 )
1900 else if( colcommodity[rowc] != -1 )
1908 if( flowrowsign != 0 )
1911 *rowsign = flowrowsign;
1912 *invertcommodity =
FALSE;
1914 else if( invflowrowsign != 0 )
1920 if( commoditysigns ==
NULL || commoditysigns[k] == 0 )
1923 *rowsign = invflowrowsign;
1924 *invertcommodity =
TRUE;
1929 *rowsign = (invflowrowsign |
INVERTED);
1930 *invertcommodity =
FALSE;
1947 unsigned char* nextrowsign,
1951 SCIP_Real* flowrowscores = mcfdata->flowrowscores;
1952 SCIP_Bool* plusflow = mcfdata->plusflow;
1953 SCIP_Bool* minusflow = mcfdata->minusflow;
1954 int* newcols = mcfdata->newcols;
1960 assert(nextrow !=
NULL);
1961 assert(nextrowsign !=
NULL);
1965 *nextinvertcommodity =
FALSE;
1970 assert(cols !=
NULL);
1973 while( mcfdata->nnewcols > 0 )
1979 unsigned char bestrowsign;
1986 c = newcols[mcfdata->nnewcols-1];
1987 mcfdata->nnewcols--;
1991 assert(plusflow[c] || minusflow[c]);
1992 if( plusflow[c] && minusflow[c] )
1998 bestinvertcommodity =
FALSE;
2003 for( i = 0; i < collen; i++ )
2006 unsigned char flowrowsign;
2012 getFlowrowFit(scip, mcfdata, row, k, &flowrowsign, &invertcommodity);
2015 if( flowrowsign != 0 )
2022 score = flowrowscores[
r];
2023 assert(score > 0.0);
2029 if( (flowrowsign &
INVERTED) != 0 )
2032 if( score > bestscore )
2035 bestrowsign = flowrowsign;
2036 bestinvertcommodity = invertcommodity;
2046 if( bestrow !=
NULL )
2048 assert(bestscore > 0.0);
2049 assert(bestrowsign != 0);
2051 *nextrowsign = bestrowsign;
2052 *nextinvertcommodity = bestinvertcommodity;
2067 int* flowcands = mcfdata->flowcands;
2094 assert(failed !=
NULL);
2103 plusflow = mcfdata->plusflow;
2104 minusflow = mcfdata->minusflow;
2105 colcommodity = mcfdata->colcommodity;
2106 rowcommodity = mcfdata->rowcommodity;
2118 for( c = 0; c < ncols; c++ )
2119 colcommodity[c] = -1;
2120 for( r = 0; r < nrows; r++ )
2121 rowcommodity[r] = -1;
2123 assert(flowcands !=
NULL || mcfdata->nflowcands == 0);
2134 for( i = 0; i < mcfdata->nflowcands; i++ )
2137 unsigned char newrowsign;
2141 assert(flowcands !=
NULL);
2143 assert(0 <= r && r < nrows);
2147 getFlowrowFit(scip, mcfdata, newrow, mcfdata->ncommodities, &newrowsign, &newinvertcommodity);
2148 if( newrowsign == 0 )
2150 assert(!newinvertcommodity);
2151 assert((newrowsign &
INVERTED) == 0);
2154 SCIPdebugMsg(scip,
" -------------------start new commodity %d--------------------- \n", mcfdata->ncommodities );
2163 if( newinvertcommodity )
2164 invertCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, comcolids, ncomcolids);
2169 comrows[
nnodes] = newrow;
2174 getNextFlowrow(scip, mcfdata, &newrow, &newrowsign, &newinvertcommodity);
2176 while( newrow !=
NULL );
2178 ncomnodes[mcfdata->ncommodities-1] =
nnodes;
2179 maxnnodes =
MAX(maxnnodes, nnodes);
2180 nflowvars += ncomcolids;
2181 SCIPdebugMsg(scip,
" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n", mcfdata->ncommodities-1, nnodes, maxnnodes);
2189 deleteCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2190 nflowrows -= ndelflowrows;
2191 nflowvars -= ndelflowvars;
2192 assert(nflowvars >= 0);
2193 assert(nflowrows >= 0);
2197 for( k = 0; k < mcfdata->ncommodities; k++ )
2209 for( i = 0; i < mcfdata->nflowcands; i++ )
2211 assert(flowcands !=
NULL);
2213 if( rowcommodity[r] == k )
2218 if( nnodes == ncomnodes[k] )
2223 assert(nnodes == ncomnodes[k]);
2224 deleteCommodity(scip, mcfdata, k, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2225 nflowrows -= ndelflowrows;
2226 nflowvars -= ndelflowvars;
2227 assert(nflowvars >= 0);
2228 assert(nflowrows >= 0);
2237 MCFdebugMessage(
"identified %d commodities (%d empty) with a maximum of %d nodes and %d flowrows, %d flowvars \n",
2238 mcfdata->ncommodities, mcfdata->nemptycommodities, maxnnodes, nflowrows, nflowvars);
2240 assert(nflowvars >= 0);
2241 assert(nflowrows >= 0);
2259 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
2262 unsigned char* flowrowsigns = mcfdata->capacityrowsigns;
2263 int* rowcommodity = mcfdata->rowcommodity;
2279 SCIP_Real* capacityrowscores = mcfdata->capacityrowscores;
2281 int *capacitycands = mcfdata->capacitycands;
2282 int ncapacitycands = mcfdata->ncapacitycands;
2284 assert(mcfdata->narcs == 0);
2285 assert(capacitycands !=
NULL || ncapacitycands == 0);
2294 colarcid = mcfdata->colarcid;
2295 rowarcid = mcfdata->rowarcid;
2298 for( c = 0; c < ncols; c++ )
2300 for( r = 0; r < nrows; r++ )
2304 for( i = 0; i < ncapacitycands; i++ )
2309 int nassignedflowvars;
2310 int nunassignedflowvars;
2313 assert(capacitycands !=
NULL);
2314 r = capacitycands[i];
2315 assert(0 <= r && r < nrows );
2316 capacityrow = rows[
r];
2318 assert(capacityrowsigns !=
NULL);
2319 assert(capacityrowscores !=
NULL);
2320 assert(rowcommodity !=
NULL);
2321 assert(flowrowsigns !=
NULL);
2325 assert((capacityrowsigns[r] &
DISCARDED) == 0);
2326 assert(capacityrowscores[r] > 0.0);
2330 assert(rowarcid[r] == -1);
2333 assert( rowcommodity[r] == -1 );
2339 nassignedflowvars = 0;
2340 nunassignedflowvars = 0;
2341 for( k = 0; k < rowlen; k++ )
2344 assert(0 <= c && c < ncols);
2345 assert(colcommodity !=
NULL);
2347 assert(-1 <= colcommodity[c] && colcommodity[c] < mcfdata->ncommodities);
2348 assert(-1 <= colarcid[c] && colarcid[c] < mcfdata->narcs);
2351 if( colcommodity[c] == -1 )
2355 if( colarcid[c] >= 0 )
2356 nassignedflowvars++;
2358 nunassignedflowvars++;
2365 if( nunassignedflowvars == 0 || nassignedflowvars >= nunassignedflowvars * 2 )
2367 SCIPdebugMsg(scip,
"discarding capacity candidate row %d <%s> [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2368 r,
SCIProwGetName(capacityrow), mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2374 assert(mcfdata->narcs <= mcfdata->capacityrowssize);
2375 if( mcfdata->narcs == mcfdata->capacityrowssize )
2377 mcfdata->capacityrowssize =
MAX(2*mcfdata->capacityrowssize, mcfdata->narcs+1);
2380 assert(mcfdata->narcs < mcfdata->capacityrowssize);
2381 assert(mcfdata->narcs < nrows);
2383 mcfdata->capacityrows[mcfdata->narcs] = capacityrow;
2386 assert(0 <= r && r < nrows);
2387 rowarcid[
r] = mcfdata->narcs;
2398 SCIPdebugMsg(scip,
"assigning capacity row %d <%s> with sign %+d to arc %d [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2400 mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2403 for( k = 0; k < rowlen; k++ )
2406 assert(0 <= rowc && rowc < ncols);
2407 assert(colcommodity !=
NULL);
2412 if( colcommodity[rowc] >= 0 && colarcid[rowc] == -1 )
2413 colarcid[rowc] = mcfdata->narcs;
2433 int* colarcid = mcfdata->colarcid;
2434 int* newcols = mcfdata->newcols;
2435 SCIP_ROW** capacityrows = mcfdata->capacityrows;
2436 SCIP_Bool* colisincident = mcfdata->colisincident;
2445 assert(!colisincident[i]);
2451 mcfdata->nnewcols = 0;
2453 for( i = 0; i < rowlen; i++ )
2465 arcid = colarcid[c];
2468 assert(arcid < mcfdata->
narcs);
2471 assert(capacityrows[arcid] !=
NULL);
2475 for( j = 0; j < capacityrowlen; j++ )
2483 if( colcommodity[caprowc] == -1 )
2485 assert(colarcid[caprowc] == -1);
2488 assert(colarcid[caprowc] <= arcid);
2491 if( colcommodity[caprowc] == basecommodity )
2495 if( !colisincident[caprowc] )
2497 assert(mcfdata->nnewcols < SCIPgetNLPCols(scip));
2498 colisincident[caprowc] =
TRUE;
2499 newcols[mcfdata->nnewcols] = caprowc;
2500 mcfdata->nnewcols++;
2514 int* basearcpattern,
2523 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2524 int* commoditysigns = mcfdata->commoditysigns;
2525 int narcs = mcfdata->narcs;
2526 int* rowcommodity = mcfdata->rowcommodity;
2527 int* colarcid = mcfdata->colarcid;
2528 int* arcpattern = mcfdata->zeroarcarray;
2541 int* overlappingarcs;
2542 int noverlappingarcs;
2547 *invertcommodity =
FALSE;
2550 for( i = 0; i <
narcs; i++ )
2551 assert(arcpattern[i] == 0);
2560 rowcom = rowcommodity[
r];
2562 rowcomsign = commoditysigns[rowcom];
2563 assert(-1 <= rowcomsign && rowcomsign <= +1);
2568 incompatible =
FALSE;
2569 noverlappingarcs = 0;
2573 for( i = 0; i < rowlen; i++ )
2583 valsign = (rowvals[i] > 0.0 ? +1 : -1);
2586 if( (flowrowsigns[r] &
INVERTED) != 0 )
2589 arcid = colarcid[c];
2598 assert(arcid < narcs);
2601 if( basearcpattern[arcid] != 0 )
2608 if( ( valsign * basearcpattern[arcid] ) > 0 )
2613 if( rowcomsign == 0 )
2616 rowcomsign = validcomsign;
2618 else if( rowcomsign != validcomsign )
2621 incompatible =
TRUE;
2632 if( arcpattern[arcid] == 0 )
2634 overlappingarcs[noverlappingarcs] = arcid;
2637 arcpattern[arcid] += valsign;
2643 for( i = 0; i < noverlappingarcs; i++ )
2649 arcid = overlappingarcs[i];
2650 assert(0 <= arcid && arcid < narcs);
2653 basenum = ABS(basearcpattern[arcid]);
2654 arcnum = ABS(arcpattern[arcid]);
2655 assert(basenum != 0.0);
2656 assert(arcnum != 0.0);
2658 if( basenum > arcnum )
2659 overlap += arcnum/basenum;
2661 overlap += basenum/arcnum;
2663 arcpattern[arcid] = 0;
2667 if( !incompatible && overlap > 0.0 )
2670 int rowarcs = rowlen - nposuncap - nneguncap;
2671 int baserowarcs = baserowlen - basenposuncap - basenneguncap;
2674 assert(overlap <= (
SCIP_Real) baserowlen);
2675 assert(noverlappingarcs >= 1);
2677 *invertcommodity = (rowcomsign == -1);
2681 if( noverlappingarcs >= 2 )
2684 assert(rowarcs >= 0 && baserowarcs >= 0 );
2687 *score = overlap - (rowarcs + baserowarcs - 2.0 * overlap)/(2.0 * ncols + 1.0);
2689 *score = overlap - (rowarcs + baserowarcs - 4.0 * overlap)/(2.0 * ncols + 1.0);
2692 if(*invertcommodity)
2693 *score += 1.0 - (ABS(nneguncap - basenposuncap) + ABS(nposuncap - basenneguncap))/(2.0 * ncols + 1.0);
2695 *score += 1.0 - (ABS(nposuncap - basenposuncap) + ABS(nneguncap - basenneguncap))/(2.0 * ncols + 1.0);
2697 *score =
MAX(*score, 1e-6);
2700 SCIPdebugMsg(scip,
" -> node similarity: row <%s>: incompatible=%u overlap=%g rowlen=%d baserowlen=%d score=%g\n",
2701 SCIProwGetName(row), incompatible, overlap, rowlen, baserowlen, *score);
2716 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2718 int* commoditysigns = mcfdata->commoditysigns;
2719 int narcs = mcfdata->narcs;
2720 int* flowcands = mcfdata->flowcands;
2721 int nflowcands = mcfdata->nflowcands;
2722 int* rowcommodity = mcfdata->rowcommodity;
2723 int* colarcid = mcfdata->colarcid;
2724 int* newcols = mcfdata->newcols;
2745 assert(mcfdata->nnodes == 0);
2757 rownodeid = mcfdata->rownodeid;
2758 colisincident = mcfdata->colisincident;
2768 for( r = 0; r < nrows; r++ )
2770 for( c = 0; c < ncols; c++ )
2771 colisincident[c] =
FALSE;
2773 assert(flowcands !=
NULL || nflowcands == 0);
2776 for( n = 0; n < nflowcands; n++ )
2785 assert(flowcands !=
NULL);
2787 assert(0 <= r && r < nrows);
2788 assert(rowcommodity !=
NULL);
2791 basecommodity = rowcommodity[
r];
2792 if( basecommodity == -1 )
2795 assert(mcfdata->rowarcid[r] == -1);
2798 if( rownodeid[r] >= 0 )
2802 SCIPdebugMsg(scip,
"assigning row %d <%s> of commodity %d to node %d [score: %g]\n",
2803 r,
SCIProwGetName(rows[r]), basecommodity, mcfdata->nnodes, mcfdata->flowrowscores[r]);
2804 rownodeid[
r] = mcfdata->nnodes;
2812 if(ncommodities == 1)
2824 assert(commoditysigns !=
NULL);
2830 if( (flowrowsigns[r] &
INVERTED) != 0 )
2832 if( commoditysigns[basecommodity] == -1 )
2835 for( i = 0; i < rowlen; i++ )
2840 assert(0 <= c && c < ncols);
2841 arcid = colarcid[c];
2846 arcpattern[arcid]++;
2848 arcpattern[arcid]--;
2863 bestflowrows[i] =
NULL;
2864 bestscores[i] = 0.0;
2865 bestinverted[i] =
FALSE;
2877 for( i = 0; i < mcfdata->nnewcols; i++ )
2883 assert(newcols !=
NULL);
2885 assert(0 <= c && c < ncols);
2886 assert(mcfdata->colcommodity[c] >= 0);
2887 assert(mcfdata->colcommodity[c] != basecommodity);
2890 assert(colisincident[c]);
2891 colisincident[c] =
FALSE;
2897 for( j = 0; j < collen; j++ )
2905 assert(0 <= colr && colr < nrows);
2908 if( rowprocessed[colr] )
2910 rowprocessed[colr] =
TRUE;
2913 rowcom = rowcommodity[colr];
2914 assert(rowcom != basecommodity);
2918 assert(rowcom == mcfdata->colcommodity[c]);
2919 assert((flowrowsigns[colr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2920 assert(mcfdata->rowarcid[colr] == -1);
2923 if( rownodeid[colr] >= 0 )
2928 nposuncap, nneguncap, colrows[j], &score, &invertcommodity) );
2931 if( score > bestscores[rowcom] )
2933 bestflowrows[rowcom] = colrows[j];
2934 bestscores[rowcom] = score;
2935 bestinverted[rowcom] = invertcommodity;
2939 assert(bestflowrows[basecommodity] ==
NULL);
2946 if( bestflowrows[i] ==
NULL )
2950 assert(0 <= comr && comr < nrows);
2951 assert(rowcommodity[comr] == i);
2952 assert((flowrowsigns[comr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2953 assert(rownodeid[comr] == -1);
2954 assert(mcfdata->nnodes >= 1);
2956 SCIPdebugMsg(scip,
" -> assigning row %d <%s> of commodity %d to node %d [invert:%u]\n",
2957 comr,
SCIProwGetName(rows[comr]), i, mcfdata->nnodes-1, bestinverted[i]);
2958 rownodeid[comr] = mcfdata->nnodes-1;
2961 if( bestinverted[i] )
2963 assert(commoditysigns[i] != +1);
2964 commoditysigns[i] = -1;
2968 assert(commoditysigns[i] != -1);
2969 commoditysigns[i] = +1;
2991 int* commoditysigns = mcfdata->commoditysigns;
2994 for( k = 0; k < mcfdata->ncommodities; k++ )
2996 if( commoditysigns[k] == 0 )
2997 commoditysigns[k] = +1;
3012 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3013 int* commoditysigns = mcfdata->commoditysigns;
3014 int* rowcommodity = mcfdata->rowcommodity;
3015 int* rownodeid = mcfdata->rownodeid;
3016 int* colsources = mcfdata->colsources;
3017 int* coltargets = mcfdata->coltargets;
3025 assert(sourcenode !=
NULL);
3026 assert(targetnode !=
NULL);
3027 assert(colsources !=
NULL);
3028 assert(coltargets !=
NULL);
3034 if( colsources[c] >= -1 )
3036 assert(coltargets[c] >= -1);
3037 *sourcenode = colsources[c];
3038 *targetnode = coltargets[c];
3049 for( i = 0; i < collen; i++ )
3056 if( rownodeid[r] >= 0 )
3063 k = rowcommodity[
r];
3064 assert(0 <= v && v < mcfdata->
nnodes);
3072 if( (flowrowsigns[r] &
INVERTED) != 0 )
3074 if( commoditysigns[k] == -1 )
3078 if( ( scale * colvals[i] ) > 0.0 )
3080 assert(*sourcenode == -1);
3082 if( *targetnode >= 0 )
3087 assert(*targetnode == -1);
3089 if( *sourcenode >= 0 )
3096 colsources[c] = *sourcenode;
3097 coltargets[c] = *targetnode;
3108 int* flowcands = mcfdata->flowcands;
3109 int nflowcands = mcfdata->nflowcands;
3111 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3113 int* rowcommodity = mcfdata->rowcommodity;
3115 int* rownodeid = mcfdata->rownodeid;
3116 int* colarcid = mcfdata->colarcid;
3117 int nnodes = mcfdata->nnodes;
3125 int* sortedflowcands;
3126 int* sortedflowcandnodeid;
3139 assert(mcfdata->nemptycommodities == 0);
3140 assert(ncommodities >= 0);
3144 if( ncommodities == 0 || nflowcands == 0 || nnodes == 0 )
3153 assert(rows !=
NULL);
3154 assert(cols !=
NULL || ncols == 0);
3165 for( n = 0; n < nflowcands; n++ )
3167 sortedflowcands[n] = flowcands[n];
3168 sortedflowcandnodeid[n] = rownodeid[flowcands[n]];
3172 SCIPsortIntInt(sortedflowcandnodeid, sortedflowcands, nflowcands);
3173 assert(sortedflowcandnodeid[0] <= 0);
3174 assert(sortedflowcandnodeid[nflowcands-1] == nnodes-1);
3177 for( v = 0; v <
nnodes; v++ )
3193 for( n = 0; n < nflowcands; n++ )
3195 if( sortedflowcandnodeid[n] >= 0 )
3197 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3198 assert(rowcommodity[sortedflowcands[n]] == -1);
3200 assert(n < nflowcands);
3201 assert(sortedflowcandnodeid[n] == 0);
3206 for( v = 0; n < nflowcands; v++ )
3211 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3212 assert(rowcommodity[sortedflowcands[n]] >= 0);
3213 assert(rownodeid[sortedflowcands[n]] == sortedflowcandnodeid[n]);
3214 assert(sortedflowcandnodeid[n] == v);
3215 assert(nadjnodes == 0);
3216 assert(ninccols == 0);
3221 for( ; n < nflowcands && sortedflowcandnodeid[n] == v; n++ )
3228 r = sortedflowcands[n];
3230 assert(mcfdata->rowarcid[r] == -1);
3235 for( i = 0; i < rowlen; i++ )
3246 arcid = colarcid[c];
3247 assert(-2 <= arcid && arcid < mcfdata->
narcs);
3248 assert(rowcommodity[r] == colcommodity[c]);
3258 else if( arcid == -1 )
3268 assert(-1 <= s && s < nnodes);
3269 assert(-1 <= t && t < nnodes);
3270 assert(s == v || t == v);
3281 if( s < 0 || t < 0 )
3289 assert(ninccols < ncols);
3290 inccols[ninccols] = c;
3306 if( sourcecount[u] + targetcount[u] == 1 )
3308 assert(nadjnodes < nnodes);
3309 adjnodes[nadjnodes] = u;
3317 for( l = 0; l < nadjnodes; l++ )
3322 assert(0 <= u && u < nnodes);
3323 assert(sourcecount[u] > 0 || targetcount[u] > 0);
3325 assert(ninccols >= 0);
3328 if( sourcecount[u] >= arcsthreshold )
3335 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, u, v);
3338 for( m = 0; m < ninccols; m++ )
3345 assert(0 <= c && c < ncols);
3347 assert(cols !=
NULL);
3349 assert(s == v || t == v);
3354 colarcid[c] = arcid;
3357 inccols[m] = inccols[ninccols-1];
3365 if( targetcount[u] >= arcsthreshold )
3372 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, v, u);
3375 for( m = 0; m < ninccols; m++ )
3382 assert(0 <= c && c < ncols);
3384 assert(cols !=
NULL);
3386 assert(s == v || t == v);
3391 colarcid[c] = arcid;
3394 inccols[m] = inccols[ninccols-1];
3403 for( l = 0; l < nadjnodes; l++ )
3411 for( l = 0; l < ninccols; l++ )
3413 assert(colarcid[inccols[l]] == -1);
3414 colarcid[inccols[l]] = -2;
3418 assert(n == nflowcands);
3419 assert(v == nnodes);
3423 for( n = 0; n < ncols; n++ )
3424 assert(colarcid[n] >= -1);
3435 MCFdebugMessage(
"network after finding uncapacitated arcs has %d nodes, %d arcs, and %d commodities\n",
3436 mcfdata->nnodes, mcfdata->narcs, mcfdata->ncommodities);
3448 int* flowcands = mcfdata->flowcands;
3449 int nflowcands = mcfdata->nflowcands;
3451 int* rowcommodity = mcfdata->rowcommodity;
3452 int* colarcid = mcfdata->colarcid;
3453 int* rowarcid = mcfdata->rowarcid;
3454 int* rownodeid = mcfdata->rownodeid;
3456 int* commoditysigns = mcfdata->commoditysigns;
3457 int narcs = mcfdata->narcs;
3458 int nnodes = mcfdata->nnodes;
3459 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3471 int nnodesthreshold;
3472 int newncommodities;
3478 MCFdebugMessage(
"network before cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3486 permsize =
MAX(permsize, narcs);
3487 permsize =
MAX(permsize, nnodes);
3497 assert(flowcands !=
NULL || nflowcands == 0);
3500 for( i = 0; i < nflowcands; i++ )
3504 assert(flowcands !=
NULL);
3506 assert(0 <= r && r < nrows);
3507 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3508 if( rowcommodity[r] >= 0 )
3510 assert(rowcommodity[r] < ncommodities);
3511 nnodespercom[rowcommodity[
r]]++;
3515 assert(capacityrows !=
NULL || narcs == 0);
3518 for( a = 0; a <
narcs; a++ )
3525 assert(capacityrows !=
NULL);
3527 assert(0 <= r && r < nrows);
3528 assert(rowarcid[r] == a);
3534 for( j = 0; j < rowlen; j++ )
3539 assert(0 <= c && c < ncols);
3540 if( colcommodity[c] >= 0 && colarcid[c] == a )
3542 assert(colcommodity[c] < ncommodities);
3543 arcisincom[colcommodity[c]] =
TRUE;
3558 maxnnodes =
MAX(maxnnodes, nnodespercom[k]);
3566 SCIPdebugMsg(scip,
" -> node threshold: %d\n", nnodesthreshold);
3569 newncommodities = 0;
3572 SCIPdebugMsg(scip,
" -> commodity %d: %d nodes, %d arcs\n", k, nnodespercom[k], narcspercom[k]);
3575 if( nnodespercom[k] >= nnodesthreshold && narcspercom[k] >= 1 )
3577 assert(newncommodities <= k);
3578 perm[k] = newncommodities;
3579 commoditysigns[newncommodities] = commoditysigns[k];
3586 if( newncommodities < ncommodities )
3595 SCIPdebugMsg(scip,
" -> discarding %d of %d commodities\n", ncommodities - newncommodities, ncommodities);
3603 for( c = 0; c < ncols; c++ )
3605 if( colcommodity[c] >= 0 )
3607 assert(-1 <= colarcid[c] && colarcid[c] < narcs);
3608 assert(colcommodity[c] < mcfdata->ncommodities);
3609 colcommodity[c] = perm[colcommodity[c]];
3610 assert(colcommodity[c] < newncommodities);
3611 if( colcommodity[c] == -1 )
3616 else if( colarcid[c] >= 0 )
3617 arcisused[colarcid[c]] =
TRUE;
3620 for( i = 0; i < nflowcands; i++ )
3624 assert(flowcands !=
NULL);
3626 assert(0 <= r && r < nrows);
3627 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3628 if( rowcommodity[r] >= 0 )
3630 assert(0 <= rownodeid[r] && rownodeid[r] < nnodes);
3631 assert(rowcommodity[r] < mcfdata->ncommodities);
3632 rowcommodity[
r] = perm[rowcommodity[
r]];
3633 assert(rowcommodity[r] < newncommodities);
3634 if( rowcommodity[r] == -1 )
3640 nodeisused[rownodeid[
r]] =
TRUE;
3644 mcfdata->ncommodities = newncommodities;
3645 ncommodities = newncommodities;
3649 for( a = 0; a <
narcs; a++ )
3653 assert(capacityrows !=
NULL);
3657 assert(newnarcs <= a);
3659 capacityrows[newnarcs] = capacityrows[
a];
3668 assert(0 <= r && r < nrows);
3669 assert(rowarcid[r] == a);
3670 rowarcid[
r] = perm[
a];
3674 if( newnarcs < narcs )
3676 SCIPdebugMsg(scip,
" -> discarding %d of %d arcs\n", narcs - newnarcs, narcs);
3678 for( c = 0; c < ncols; c++ )
3680 if( colarcid[c] >= 0 )
3682 colarcid[c] = perm[colarcid[c]];
3683 assert(colarcid[c] >= 0);
3686 mcfdata->narcs = newnarcs;
3690 for( a = 0; a <
narcs; a++ )
3693 assert(capacityrows !=
NULL);
3695 assert(0 <= r && r < nrows);
3696 assert(rowarcid[r] == a);
3702 for( v = 0; v <
nnodes; v++ )
3706 assert(newnnodes <= v);
3707 perm[v] = newnnodes;
3715 if( newnnodes < nnodes )
3717 SCIPdebugMsg(scip,
" -> discarding %d of %d nodes\n", nnodes - newnnodes, nnodes);
3719 for( i = 0; i < nflowcands; i++ )
3723 assert(flowcands !=
NULL);
3725 assert(0 <= r && r < nrows);
3726 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3727 if( rowcommodity[r] >= 0 )
3729 assert(rowcommodity[r] < ncommodities);
3730 rownodeid[
r] = perm[rownodeid[
r]];
3731 assert(rownodeid[r] >= 0);
3734 mcfdata->nnodes = newnnodes;
3746 mcfdata->nemptycommodities = 0;
3754 MCFdebugMessage(
"network after cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3768 int* colarcid = mcfdata->colarcid;
3770 int narcs = mcfdata->narcs;
3771 int nnodes = mcfdata->nnodes;
3773 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3775 SCIP_Real maxinconsistencyratio = sepadata->maxinconsistencyratio;
3776 SCIP_Real maxarcinconsistencyratio = sepadata->maxarcinconsistencyratio;
3788 int *flowvarspercom;
3801 assert(effortlevel !=
NULL);
3815 arcsources = mcfdata->arcsources;
3816 arctargets = mcfdata->arctargets;
3817 colsources = mcfdata->colsources;
3818 coltargets = mcfdata->coltargets;
3819 firstoutarcs = mcfdata->firstoutarcs;
3820 firstinarcs = mcfdata->firstinarcs;
3821 nextoutarcs = mcfdata->nextoutarcs;
3822 nextinarcs = mcfdata->nextinarcs;
3824 mcfdata->arcarraysize =
narcs;
3827 for( c = 0; c < ncols; c++ )
3834 for( v = 0; v <
nnodes; v++ )
3836 firstoutarcs[v] = -1;
3837 firstinarcs[v] = -1;
3839 for( a = 0; a <
narcs; a++ )
3841 nextoutarcs[
a] = -1;
3855 mcfdata->ninconsistencies = 0.0;
3856 maxninconsistencies = maxinconsistencyratio * (
SCIP_Real)narcs;
3859 for( a = 0; a <
narcs; a++ )
3881 assert(mcfdata->rowarcid[r] == a);
3884 for( i = 0; i <
nnodes; i++ )
3886 assert(sourcenodecnt[i] == 0);
3887 assert(targetnodecnt[i] == 0);
3898 for( i = 0; i < rowlen; i++ )
3902 if( colarcid[c] >= 0 )
3904 int k = colcommodity[c];
3905 assert (0 <= k && k < ncommodities);
3906 flowvarspercom[k]++;
3907 if( !comtouched[k] )
3910 comtouched[k] =
TRUE;
3916 if( ntouchedcoms == 0 )
3918 capacityrows[
a] =
NULL;
3926 totalsourcecnt = 0.0;
3927 totaltargetcnt = 0.0;
3929 for( i = 0; i < rowlen; i++ )
3933 if( colarcid[c] >= 0 )
3935 int k = colcommodity[c];
3940 assert (0 <= k && k < ncommodities);
3941 assert (comtouched[k]);
3942 assert (flowvarspercom[k] >= 1);
3948 weight = 1.0/flowvarspercom[k];
3951 if( sourcenodecnt[sourcev] == 0.0 && targetnodecnt[sourcev] == 0.0 )
3953 touchednodes[ntouchednodes] = sourcev;
3956 sourcenodecnt[sourcev] += weight;
3957 totalsourcecnt += weight;
3961 if( sourcenodecnt[targetv] == 0.0 && targetnodecnt[targetv] == 0.0 )
3963 touchednodes[ntouchednodes] = targetv;
3966 targetnodecnt[targetv] += weight;
3967 totaltargetcnt += weight;
3969 if( sourcev >= 0 || targetv >= 0 )
3970 totalnodecnt += weight;
3977 bestsourcecnt = 0.0;
3978 besttargetcnt = 0.0;
3979 for( i = 0; i < ntouchednodes; i++ )
3981 v = touchednodes[i];
3982 assert(0 <= v && v < nnodes);
3987 if( sourcenodecnt[v] >= targetnodecnt[v] )
3989 if( sourcenodecnt[v] > bestsourcecnt )
3992 bestsourcecnt = sourcenodecnt[v];
3997 if( targetnodecnt[v] > besttargetcnt )
4000 besttargetcnt = targetnodecnt[v];
4006 SCIP_Real nodecnt = sourcenodecnt[v] + targetnodecnt[v];
4010 if( nodecnt > bestsourcecnt )
4012 besttargetv = bestsourcev;
4013 besttargetcnt = bestsourcecnt;
4015 bestsourcecnt = nodecnt;
4017 else if( nodecnt > besttargetcnt )
4020 besttargetcnt = nodecnt;
4025 sourcenodecnt[v] = 0;
4026 targetnodecnt[v] = 0;
4032 totalsourcecnt = totalnodecnt;
4033 totaltargetcnt = totalnodecnt;
4035 assert(
SCIPisGE(scip,totalsourcecnt,bestsourcecnt));
4036 assert(
SCIPisGE(scip,totaltargetcnt,besttargetcnt));
4037 nsourceinconsistencies = (totalsourcecnt - bestsourcecnt)/ntouchedcoms;
4038 ntargetinconsistencies = (totaltargetcnt - besttargetcnt)/ntouchedcoms;
4041 if( nsourceinconsistencies > maxarcinconsistencyratio )
4047 if( ntargetinconsistencies > maxarcinconsistencyratio )
4054 assert(bestsourcev == -1 || bestsourcev != besttargetv);
4055 arcsources[
a] = bestsourcev;
4056 arctargets[
a] = besttargetv;
4057 SCIPdebugMsg(scip,
"arc %d: %d -> %d (len=%d, sourcecnt=%g/%g, targetcnt=%g/%g, %g/%g inconsistencies)\n",
4058 a, bestsourcev, besttargetv, rowlen,
4059 bestsourcecnt, totalsourcecnt, besttargetcnt, totaltargetcnt,
4060 nsourceinconsistencies, ntargetinconsistencies);
4063 if( bestsourcev != -1 )
4065 nextoutarcs[
a] = firstoutarcs[bestsourcev];
4066 firstoutarcs[bestsourcev] =
a;
4068 if( besttargetv != -1 )
4070 nextinarcs[
a] = firstinarcs[besttargetv];
4071 firstinarcs[besttargetv] =
a;
4075 mcfdata->ninconsistencies += 0.5*(nsourceinconsistencies + ntargetinconsistencies);
4077 if( mcfdata->ninconsistencies > maxninconsistencies )
4079 MCFdebugMessage(
" -> reached maximal number of inconsistencies: %g > %g\n",
4080 mcfdata->ninconsistencies, maxninconsistencies);
4086 if( mcfdata->ninconsistencies <= maxninconsistencies && narcs > 0 && ncommodities > 0 )
4091 MCFdebugMessage(
"extracted network has %g inconsistencies (ratio %g) -> separating with effort %d\n",
4092 mcfdata->ninconsistencies, mcfdata->ninconsistencies/(
SCIP_Real)narcs, *effortlevel);
4123 int* firstoutarcs = mcfdata->firstoutarcs;
4124 int* firstinarcs = mcfdata->firstinarcs;
4125 int* nextoutarcs = mcfdata->nextoutarcs;
4126 int* nextinarcs = mcfdata->nextinarcs;
4127 int nnodes = mcfdata->nnodes;
4132 assert(nodevisited !=
NULL);
4133 assert(0 <= startv && startv < nnodes);
4134 assert(nodevisited[startv] ==
UNKNOWN);
4135 assert(compnodes !=
NULL);
4136 assert(ncompnodes !=
NULL);
4137 assert(comparcs !=
NULL);
4138 assert(ncomparcs !=
NULL);
4147 stacknodes[0] = startv;
4149 nodevisited[startv] =
ONSTACK;
4152 while( nstacknodes > 0 )
4157 assert(firstoutarcs !=
NULL);
4158 assert(firstinarcs !=
NULL);
4159 assert(nextoutarcs !=
NULL);
4160 assert(nextinarcs !=
NULL);
4163 v = stacknodes[nstacknodes-1];
4165 assert(0 <= v && v < nnodes);
4166 assert(nodevisited[v] ==
ONSTACK);
4170 assert(*ncompnodes < nnodes);
4171 compnodes[*ncompnodes] = v;
4175 for( a = firstoutarcs[v]; a != -1; a = nextoutarcs[
a] )
4179 assert(0 <= a && a < mcfdata->
narcs);
4180 assert(arctargets !=
NULL);
4182 targetv = arctargets[
a];
4185 if( targetv != -1 && nodevisited[targetv] ==
VISITED )
4189 assert(*ncomparcs < mcfdata->narcs);
4190 comparcs[*ncomparcs] =
a;
4194 if( targetv != -1 && nodevisited[targetv] ==
UNKNOWN )
4196 assert(nstacknodes < nnodes);
4197 stacknodes[nstacknodes] = targetv;
4199 nodevisited[targetv] =
ONSTACK;
4204 for( a = firstinarcs[v]; a != -1; a = nextinarcs[
a] )
4208 assert(0 <= a && a < mcfdata->
narcs);
4209 assert(arcsources !=
NULL);
4211 sourcev = arcsources[
a];
4214 if( sourcev != -1 && nodevisited[sourcev] ==
VISITED )
4218 assert(*ncomparcs < mcfdata->narcs);
4219 comparcs[*ncomparcs] =
a;
4223 if( sourcev != -1 && nodevisited[sourcev] ==
UNKNOWN )
4225 assert(nstacknodes < nnodes);
4226 stacknodes[nstacknodes] = sourcev;
4228 nodevisited[sourcev] =
ONSTACK;
4259 int mcfnetworkssize;
4261 assert(mcfnetworks !=
NULL);
4262 assert(nmcfnetworks !=
NULL);
4263 assert(effortlevel !=
NULL);
4267 *mcfnetworks =
NULL;
4269 mcfnetworkssize = 0;
4300 mcfdata.flowrowsigns =
NULL;
4301 mcfdata.flowrowscalars =
NULL;
4302 mcfdata.flowrowscores =
NULL;
4303 mcfdata.capacityrowsigns =
NULL;
4304 mcfdata.capacityrowscores =
NULL;
4305 mcfdata.flowcands =
NULL;
4306 mcfdata.nflowcands = 0;
4307 mcfdata.capacitycands =
NULL;
4308 mcfdata.ncapacitycands = 0;
4309 mcfdata.plusflow =
NULL;
4310 mcfdata.minusflow =
NULL;
4311 mcfdata.ncommodities = 0;
4312 mcfdata.nemptycommodities = 0;
4313 mcfdata.commoditysigns =
NULL;
4314 mcfdata.commoditysignssize = 0;
4315 mcfdata.colcommodity =
NULL;
4316 mcfdata.rowcommodity =
NULL;
4317 mcfdata.colarcid =
NULL;
4318 mcfdata.rowarcid =
NULL;
4319 mcfdata.rownodeid =
NULL;
4320 mcfdata.arcarraysize = 0;
4321 mcfdata.arcsources =
NULL;
4322 mcfdata.arctargets =
NULL;
4323 mcfdata.colsources =
NULL;
4324 mcfdata.coltargets =
NULL;
4325 mcfdata.firstoutarcs =
NULL;
4326 mcfdata.firstinarcs =
NULL;
4327 mcfdata.nextoutarcs =
NULL;
4328 mcfdata.nextinarcs =
NULL;
4329 mcfdata.newcols =
NULL;
4330 mcfdata.nnewcols = 0;
4333 mcfdata.ninconsistencies = 0.0;
4334 mcfdata.capacityrows =
NULL;
4335 mcfdata.capacityrowssize = 0;
4336 mcfdata.colisincident =
NULL;
4337 mcfdata.zeroarcarray =
NULL;
4344 assert(mcfdata.flowrowsigns !=
NULL);
4345 assert(mcfdata.flowrowscalars !=
NULL);
4346 assert(mcfdata.flowrowscores !=
NULL);
4347 assert(mcfdata.flowcands !=
NULL);
4349 if( mcfdata.nflowcands == 0 )
4357 assert(mcfdata.plusflow !=
NULL);
4358 assert(mcfdata.minusflow !=
NULL);
4359 assert(mcfdata.colcommodity !=
NULL);
4360 assert(mcfdata.rowcommodity !=
NULL);
4361 assert(mcfdata.newcols !=
NULL);
4367 printCommodities(scip, &mcfdata);
4374 assert(mcfdata.capacityrowsigns !=
NULL);
4375 assert(mcfdata.capacityrowscores !=
NULL);
4376 assert(mcfdata.capacitycands !=
NULL);
4378 if( mcfdata.ncapacitycands == 0 )
4386 assert(mcfdata.colarcid !=
NULL);
4387 assert(mcfdata.rowarcid !=
NULL);
4391 assert(mcfdata.rownodeid !=
NULL);
4392 assert(mcfdata.colisincident !=
NULL);
4393 assert(mcfdata.zeroarcarray !=
NULL);
4404 assert(mcfdata.arcsources !=
NULL);
4405 assert(mcfdata.arctargets !=
NULL);
4406 assert(mcfdata.colsources !=
NULL);
4407 assert(mcfdata.coltargets !=
NULL);
4408 assert(mcfdata.firstoutarcs !=
NULL);
4409 assert(mcfdata.firstinarcs !=
NULL);
4410 assert(mcfdata.nextoutarcs !=
NULL);
4411 assert(mcfdata.nextinarcs !=
NULL);
4427 printCommodities(scip, &mcfdata);
4440 for( v = 0; v < mcfdata.nnodes; v++ )
4444 for( v = 0; v < mcfdata.nnodes; v++ )
4451 if( nodevisited[v] ==
VISITED )
4456 assert(ncompnodes >= 1);
4457 assert(compnodes[0] == v);
4458 assert(nodevisited[v] ==
VISITED);
4461 if( ncompnodes >= minnodes && ncomparcs >=
MINARCS )
4468 assert(*nmcfnetworks <= mcfnetworkssize);
4469 if( *nmcfnetworks == mcfnetworkssize )
4471 mcfnetworkssize =
MAX(2*mcfnetworkssize, *nmcfnetworks+1);
4474 assert(*nmcfnetworks < mcfnetworkssize);
4480 SCIP_CALL(
mcfnetworkFill(scip, mcfnetwork, &mcfdata, compnodeid, compnodes, ncompnodes, comparcs, ncomparcs) );
4483 assert(*mcfnetworks !=
NULL);
4484 for( i = *nmcfnetworks; i > 0 && mcfnetwork->
nnodes > (*mcfnetworks)[i-1]->nnodes; i-- )
4485 (*mcfnetworks)[i] = (*mcfnetworks)[i-1];
4486 (*mcfnetworks)[i] = mcfnetwork;
4491 minnodes =
MAX(minnodes, (*mcfnetworks)[*nmcfnetworks-1]->
nnodes);
4496 SCIPdebugMsg(scip,
" -> discarded network with %d nodes and %d arcs due to maxnetworks (minnodes=%d)\n",
4497 (*mcfnetworks)[*nmcfnetworks-1]->
nnodes, (*mcfnetworks)[*nmcfnetworks-1]->
narcs, minnodes);
4505 SCIPdebugMsg(scip,
" -> discarded component with %d nodes and %d arcs\n", ncompnodes, ncomparcs);
4547 #ifdef COUNTNETWORKVARIABLETYPES 4569 int nintflowvars = 0;
4570 int nbinflowvars = 0;
4571 int ncontflowvars = 0;
4573 int nintcapvars = 0;
4574 int nbincapvars = 0;
4575 int ncontcapvars = 0;
4583 for(c=0; c < ncols; c++)
4584 colvisited[c]=
FALSE;
4588 for(m=0; m < nmcfnetworks; m++)
4600 for(c=0; c < ncols; c++)
4604 if(colcommodity[c] >= 0 && ! colvisited[c])
4609 colvisited[c] =
TRUE;
4632 for( a = 0; a <
narcs; a++ )
4635 row = arccapacityrows[
a];
4647 for( i = 0; i < rowlen; i++ )
4652 if(colcommodity[c] == -1 && ! colvisited[c] )
4655 colvisited[c] =
TRUE;
4682 for( v = 0; v <
nnodes; v++ )
4685 row = nodeflowrows[v][k];
4695 MCFdebugMessage(
" nof flowvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4696 nflowvars, ncontflowvars, nintflowvars, nbinflowvars);
4697 MCFdebugMessage(
" nof capvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4698 ncapvars, ncontcapvars, nintcapvars, nbincapvars);
4717 int* representatives,
4724 for( v = 0; v < nelems; v++ )
4725 representatives[v] = v;
4731 int* representatives,
4735 assert(representatives !=
NULL);
4737 while( v != representatives[v] )
4739 representatives[v] = representatives[representatives[v]];
4740 v = representatives[v];
4749 int* representatives,
4754 assert(rep1 != rep2);
4755 assert(representatives[rep1] == rep1);
4756 assert(representatives[rep2] == rep2);
4762 representatives[rep2] = rep1;
4764 representatives[rep1] = rep2;
4780 if( nodepair1->weight > nodepair2->weight )
4782 else if( nodepair1->weight < nodepair2->weight )
4817 assert(mcfnetwork !=
NULL);
4823 assert(nodepair1 !=
NULL);
4824 assert(nodepair2 !=
NULL);
4826 source1 = nodepair1->node1;
4827 source2 = nodepair2->node1;
4828 target1 = nodepair1->node2;
4829 target2 = nodepair2->node2;
4831 assert(source1 >=0 && source1 < mcfnetwork->
nnodes);
4832 assert(source2 >=0 && source2 < mcfnetwork->nnodes);
4833 assert(target1 >=0 && target1 < mcfnetwork->nnodes);
4834 assert(target2 >=0 && target2 < mcfnetwork->nnodes);
4835 assert(source1 <= target1);
4836 assert(source2 <= target2);
4838 return (source1 == source2 && target1 == target2);
4852 unsigned int hashval;
4856 assert(mcfnetwork !=
NULL);
4860 assert( nodepair !=
NULL);
4862 source = nodepair->node1;
4863 target = nodepair->node2;
4865 assert(source >=0 && source < mcfnetwork->
nnodes);
4866 assert(target >=0 && target < mcfnetwork->nnodes);
4867 assert(source <= target);
4869 hashval = (unsigned)((source << 16) + target);
4892 #ifdef BETTERWEIGHTFORDEMANDNODES 4912 assert(mcfnetwork !=
NULL);
4914 #ifdef BETTERWEIGHTFORDEMANDNODES 4924 assert(nodepairqueue !=
NULL);
4931 hashtablesize = mcfnetwork->
narcs;
4934 hashGetKeyNodepairs, hashKeyEqNodepairs, hashKeyValNodepairs, (
void*) mcfnetwork) );
4941 for( a = 0; a < mcfnetwork->narcs; a++ )
4947 capacityrow = mcfnetwork->arccapacityrows[
a];
4949 SCIPdebugMsg(scip,
"arc %i = (%i %i)\n", a, mcfnetwork->arcsources[a], mcfnetwork->arctargets[a]);
4952 if( mcfnetwork->arcsources[a] <= mcfnetwork->arctargets[a] )
4954 nodepair.node1 = mcfnetwork->arcsources[
a];
4955 nodepair.node2 = mcfnetwork->arctargets[
a];
4959 nodepair.node2 = mcfnetwork->arcsources[
a];
4960 nodepair.node1 = mcfnetwork->arctargets[
a];
4963 assert(nodepair.node1 < mcfnetwork->nnodes);
4964 assert(nodepair.node2 < mcfnetwork->nnodes);
4965 if( nodepair.node1 == -1 || nodepair.node2 == -1 )
4969 if( capacityrow !=
NULL )
4985 slack =
MAX(slack, 0.0);
4988 scale = ABS(mcfnetwork->arccapacityscales[a])/maxval;
4989 assert(scale > 0.0);
4999 for( i = 0; i < rowlen; i++ )
5006 if(colcommodity[c] >= 0)
5018 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g -- flow:%g -- cap:%g \n", scale * slack, dualsol/scale, totalflow * scale, totalcap * scale);
5020 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g1\n", scale * slack, dualsol/scale);
5024 nodepair.weight = scale * slack - ABS(dualsol)/scale;
5025 #ifdef USEFLOWFORTIEBREAKING 5028 nodepair.weight += totalflow * scale;
5029 nodepair.weight = MIN( nodepair.weight, -0.0001);
5032 #ifdef USECAPACITYFORTIEBREAKING 5035 nodepair.weight += totalcap * scale;
5036 nodepair.weight = MIN( nodepair.weight, -0.0001);
5051 if( nodepairptr !=
NULL )
5054 SCIPdebugMsg(scip,
"nodepair known [%d,%d] -- old weight:%g -- new weight:%g\n", nodepair.node1,nodepair.node2,nodepairptr->weight,
5055 MIN(nodepair.weight, nodepairptr->weight));
5056 nodepairptr->weight = MIN(nodepair.weight, nodepairptr->weight);
5061 nodepairs = (*nodepairqueue)->nodepairs;
5063 assert(nnodepairs < mcfnetwork->
narcs);
5064 nodepairs[nnodepairs] = nodepair;
5067 SCIPdebugMsg(scip,
"new nodepair [%d,%d]-- weight:%g\n", nodepair.node1, nodepair.node2, nodepair.weight);
5078 #ifdef BETTERWEIGHTFORDEMANDNODES 5086 nodepairs = (*nodepairqueue)->nodepairs;
5087 for( n = 0; n < nnodepairs; n++ )
5091 maxweight =
MAX(maxweight, nodepairs[n].weight);
5093 minweight = MIN(minweight, nodepairs[n].weight);
5096 SCIPdebugMsg(scip,
"min/max weight:%g / %g\n", minweight, maxweight);
5103 for( n = 0; n < nnodepairs; n++ )
5105 int node1 = nodepairs[n].node1;
5106 int node2 = nodepairs[n].node2;
5108 #ifdef BETTERWEIGHTFORDEMANDNODES 5115 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5123 if( nodeflowrows[node1][k] ==
NULL )
5126 if( nodeflowscales[node1][k] > 0.0 )
5143 if( nodeflowrows[node2][k] ==
NULL )
5146 if( nodeflowscales[node2][k] > 0.0 )
5168 if( !hasdemand1 || !hasdemand2 )
5169 nodepairs[n].weight += maxweight;
5175 if( hasdemand1 && hasdemand2)
5176 nodepairs[n].weight += minweight;
5179 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5196 assert(nodepairqueue !=
NULL);
5197 assert(*nodepairqueue !=
NULL);
5211 assert(nodepairqueue !=
NULL);
5223 assert(nodepairqueue !=
NULL);
5271 assert(mcfnetwork !=
NULL);
5272 assert(nodepartition !=
NULL);
5273 assert(mcfnetwork->
nnodes >= 1);
5281 (*nodepartition)->nclusters = 0;
5290 nclustersleft = mcfnetwork->
nnodes;
5301 assert(nodepair !=
NULL);
5302 node1 = nodepair->node1;
5303 node2 = nodepair->node2;
5305 assert(node1 >= 0 && node1 < mcfnetwork->
nnodes);
5306 assert(node2 >= 0 && node2 < mcfnetwork->nnodes);
5311 assert(0 <= node1rep && node1rep < mcfnetwork->nnodes);
5312 assert(0 <= node2rep && node2rep < mcfnetwork->nnodes);
5315 if( node1rep == node2rep )
5319 SCIPdebugMsg(scip,
"shrinking nodepair (%d,%d) with weight %g: join representatives %d and %d\n",
5320 node1, node2, nodepair->weight, node1rep, node2rep);
5326 assert((*nodepartition)->representatives[0] == 0);
5331 if( nclustersleft > nclusters )
5333 for( v = 1; v < mcfnetwork->
nnodes && nclustersleft > nclusters; v++ )
5345 assert(nclustersleft <= nclusters);
5350 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5360 c = (*nodepartition)->nclusters;
5361 (*nodepartition)->nclusters++;
5364 c = (*nodepartition)->nodeclusters[rep];
5365 assert(0 <= c && c < nclusters);
5368 (*nodepartition)->nodeclusters[v] = c;
5374 for( c = 0; c < (*nodepartition)->nclusters; c++ )
5376 (*nodepartition)->clusterbegin[c] = pos;
5377 pos += clustersize[c];
5379 assert(pos == mcfnetwork->
nnodes);
5380 (*nodepartition)->clusterbegin[(*nodepartition)->nclusters] = mcfnetwork->
nnodes;
5384 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5386 c = (*nodepartition)->nodeclusters[v];
5387 assert(0 <= c && c < (*nodepartition)->nclusters);
5388 pos = (*nodepartition)->clusterbegin[c] + clustersize[c];
5389 assert(pos < (*nodepartition)->clusterbegin[c+1]);
5390 (*nodepartition)->clusternodes[pos] = v;
5410 assert(nodepartition !=
NULL);
5411 assert(*nodepartition !=
NULL);
5424 unsigned int partition,
5435 if( nodepartition ==
NULL )
5436 return ((v == (
int)partition) == !inverted);
5440 unsigned int clusterbit;
5442 cluster = nodepartition->nodeclusters[v];
5443 assert(0 <= cluster && cluster < nodepartition->nclusters);
5444 clusterbit = (1 << cluster);
5446 return (((partition & clusterbit) != 0) == !inverted);
5456 unsigned int partition
5459 const int* nodeclusters = nodepartition->nodeclusters;
5469 assert(nodepartition->nodeclusters !=
NULL);
5470 nclusters = nodepartition->nclusters;
5477 ncomponents = nclusters;
5478 assert(ncomponents >= 2);
5481 for( a = 0; a <
narcs; a++ )
5483 int s = arcsources[
a];
5484 int t = arctargets[
a];
5487 if( s == -1 || t == -1 )
5498 assert(0 <= s && s < mcfnetwork->
nnodes);
5499 assert(0 <= t && t < mcfnetwork->nnodes);
5502 cs = nodeclusters[s];
5503 ct = nodeclusters[t];
5504 assert(0 <= cs && cs < nclusters);
5505 assert(0 <= ct && ct < nclusters);
5514 if( repcs == repct )
5521 if( ncomponents <= 2 )
5531 assert(ncomponents >= 2);
5533 return (ncomponents == 2);
5538 void nodepartitionPrint(
5544 for( c = 0; c < nodepartition->nclusters; c++ )
5549 for( i = nodepartition->clusterbegin[c]; i < nodepartition->clusterbegin[c+1]; i++ )
5564 unsigned int partition
5573 if( nodepartition ==
NULL )
5578 file = fopen(filename,
"w");
5586 fprintf(file,
"graph\n");
5587 fprintf(file,
"[\n");
5588 fprintf(file,
" hierarchic 1\n");
5589 fprintf(file,
" label \"\"\n");
5590 fprintf(file,
" directed 1\n");
5593 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5604 fprintf(file,
" node\n");
5605 fprintf(file,
" [\n");
5606 fprintf(file,
" id %d\n", v);
5607 fprintf(file,
" label \"%s\"\n", label);
5608 fprintf(file,
" graphics\n");
5609 fprintf(file,
" [\n");
5610 fprintf(file,
" w 30.0\n");
5611 fprintf(file,
" h 30.0\n");
5612 fprintf(file,
" type \"ellipse\"\n");
5614 fprintf(file,
" fill \"#FF0000\"\n");
5616 fprintf(file,
" fill \"#00FF00\"\n");
5617 fprintf(file,
" outline \"#000000\"\n");
5618 fprintf(file,
" ]\n");
5619 fprintf(file,
" LabelGraphics\n");
5620 fprintf(file,
" [\n");
5621 fprintf(file,
" text \"%s\"\n", label);
5622 fprintf(file,
" fontSize 13\n");
5623 fprintf(file,
" fontName \"Dialog\"\n");
5624 fprintf(file,
" anchor \"c\"\n");
5625 fprintf(file,
" ]\n");
5627 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+1);
5629 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+2);
5630 fprintf(file,
" ]\n");
5634 fprintf(file,
" node\n");
5635 fprintf(file,
" [\n");
5636 fprintf(file,
" id %d\n", mcfnetwork->
nnodes);
5637 fprintf(file,
" label \"?\"\n");
5638 fprintf(file,
" graphics\n");
5639 fprintf(file,
" [\n");
5640 fprintf(file,
" w 30.0\n");
5641 fprintf(file,
" h 30.0\n");
5642 fprintf(file,
" type \"ellipse\"\n");
5643 fprintf(file,
" fill \"#FFFFFF\"\n");
5644 fprintf(file,
" outline \"#000000\"\n");
5645 fprintf(file,
" ]\n");
5646 fprintf(file,
" LabelGraphics\n");
5647 fprintf(file,
" [\n");
5648 fprintf(file,
" text \"?\"\n");
5649 fprintf(file,
" fontSize 13\n");
5650 fprintf(file,
" fontName \"Dialog\"\n");
5651 fprintf(file,
" anchor \"c\"\n");
5652 fprintf(file,
" ]\n");
5653 fprintf(file,
" ]\n");
5656 fprintf(file,
" node\n");
5657 fprintf(file,
" [\n");
5658 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+1);
5659 fprintf(file,
" label \"Partition S\"\n");
5660 fprintf(file,
" graphics\n");
5661 fprintf(file,
" [\n");
5662 fprintf(file,
" type \"roundrectangle\"\n");
5663 fprintf(file,
" fill \"#CAECFF84\"\n");
5664 fprintf(file,
" outline \"#666699\"\n");
5665 fprintf(file,
" outlineStyle \"dotted\"\n");
5666 fprintf(file,
" topBorderInset 0\n");
5667 fprintf(file,
" bottomBorderInset 0\n");
5668 fprintf(file,
" leftBorderInset 0\n");
5669 fprintf(file,
" rightBorderInset 0\n");
5670 fprintf(file,
" ]\n");
5671 fprintf(file,
" LabelGraphics\n");
5672 fprintf(file,
" [\n");
5673 fprintf(file,
" text \"Partition S\"\n");
5674 fprintf(file,
" fill \"#99CCFF\"\n");
5675 fprintf(file,
" fontSize 15\n");
5676 fprintf(file,
" fontName \"Dialog\"\n");
5677 fprintf(file,
" alignment \"right\"\n");
5678 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5679 fprintf(file,
" anchor \"t\"\n");
5680 fprintf(file,
" borderDistance 0.0\n");
5681 fprintf(file,
" ]\n");
5682 fprintf(file,
" isGroup 1\n");
5683 fprintf(file,
" ]\n");
5686 fprintf(file,
" node\n");
5687 fprintf(file,
" [\n");
5688 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+2);
5689 fprintf(file,
" label \"Partition T\"\n");
5690 fprintf(file,
" graphics\n");
5691 fprintf(file,
" [\n");
5692 fprintf(file,
" type \"roundrectangle\"\n");
5693 fprintf(file,
" fill \"#CAECFF84\"\n");
5694 fprintf(file,
" outline \"#666699\"\n");
5695 fprintf(file,
" outlineStyle \"dotted\"\n");
5696 fprintf(file,
" topBorderInset 0\n");
5697 fprintf(file,
" bottomBorderInset 0\n");
5698 fprintf(file,
" leftBorderInset 0\n");
5699 fprintf(file,
" rightBorderInset 0\n");
5700 fprintf(file,
" ]\n");
5701 fprintf(file,
" LabelGraphics\n");
5702 fprintf(file,
" [\n");
5703 fprintf(file,
" text \"Partition T\"\n");
5704 fprintf(file,
" fill \"#99CCFF\"\n");
5705 fprintf(file,
" fontSize 15\n");
5706 fprintf(file,
" fontName \"Dialog\"\n");
5707 fprintf(file,
" alignment \"right\"\n");
5708 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5709 fprintf(file,
" anchor \"t\"\n");
5710 fprintf(file,
" borderDistance 0.0\n");
5711 fprintf(file,
" ]\n");
5712 fprintf(file,
" isGroup 1\n");
5713 fprintf(file,
" ]\n");
5716 for( a = 0; a < mcfnetwork->
narcs; a++ )
5728 hasfractional =
FALSE;
5739 for( i = 0; i < rowlen; i++ )
5746 hasfractional =
TRUE;
5754 fprintf(file,
" edge\n");
5755 fprintf(file,
" [\n");
5758 fprintf(file,
" label \"%s\"\n", label);
5759 fprintf(file,
" graphics\n");
5760 fprintf(file,
" [\n");
5762 fprintf(file,
" fill \"#000000\"\n");
5764 fprintf(file,
" fill \"#FF0000\"\n");
5766 fprintf(file,
" style \"dashed\"\n");
5767 fprintf(file,
" width 1\n");
5768 fprintf(file,
" targetArrow \"standard\"\n");
5769 fprintf(file,
" ]\n");
5770 fprintf(file,
" LabelGraphics\n");
5771 fprintf(file,
" [\n");
5772 fprintf(file,
" text \"%s\"\n", label);
5773 fprintf(file,
" ]\n");
5774 fprintf(file,
" ]\n");
5778 fprintf(file,
"]\n");
5813 assert(scip !=
NULL);
5814 assert(sepadata !=
NULL);
5815 assert(cutcoefs !=
NULL);
5816 assert(ncuts !=
NULL);
5817 assert(cutoff !=
NULL);
5821 assert(nvars == 0 || vars !=
NULL);
5827 for( i = 0; i < cutnnz; ++i )
5829 cutvars[i] = vars[cutinds[i]];
5835 sepadata->dynamiccuts) );
5845 SCIPdebugMsg(scip,
" -> found MCF cut <%s>: rhs=%f, act=%f eff=%f rank=%d\n",
5862 if( !(*cutoff) && sepadata->separateknapsack)
5865 SCIP_CALL(
SCIPseparateRelaxedKnapsack(scip,
NULL, sepa, cutnnz, cutvars, cutcoefs, +1.0, cutrhs, sol, cutoff, ncuts) );
5916 unsigned int partition;
5917 unsigned int allpartitions;
5918 unsigned int startpartition;
5932 maxsepacuts = sepadata->maxsepacutsroot;
5934 maxsepacuts = sepadata->maxsepacuts;
5935 if( maxsepacuts < 0 )
5936 maxsepacuts = INT_MAX;
5941 maxtestdelta = sepadata->maxtestdelta;
5942 if( maxtestdelta <= 0 )
5943 maxtestdelta = INT_MAX;
5979 if( nodepartition ==
NULL )
5983 allpartitions = (
unsigned int) nnodes;
5984 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nnodes: %d \n", maxtestdelta, maxsepacuts, nnodes);
5991 int nclusters = nodepartition->nclusters;
5993 assert((
unsigned int)nclusters <= 8*
sizeof(
unsigned int));
5994 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nclusters: %d \n", maxtestdelta, maxsepacuts, nclusters);
6001 allpartitions = (1 << (nclusters-1));
6005 for( partition = startpartition; partition <= allpartitions-1 && !
SCIPisStopped(scip) && *ncuts < maxsepacuts && !*cutoff; partition++ )
6019 if( sepadata->checkcutshoreconnectivity )
6026 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x \n", partition );
6027 SCIPdebugMsg(scip,
" -> either shore S or shore T is not connected - skip partition.\n");
6032 for( inverted =
FALSE; inverted <= useinverted && !*cutoff; inverted++ )
6034 if( nodepartition ==
NULL )
6036 SCIPdebugMsg(scip,
"generating single-node cuts for node %u (inverted: %u)\n", partition, inverted);
6040 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x (inverted: %u)\n", partition, inverted);
6044 SCIP_CALL( outputGraph(scip, mcfnetwork, nodepartition, inverted, partition) );
6062 for( v = 0; v <
nnodes; v++ )
6076 if( nodeflowrows[v][k] ==
NULL )
6079 if( nodeflowscales[v][k] > 0.0 )
6083 if( nodeflowinverted[v][k] )
6086 comcutdemands[k] += rhs * nodeflowscales[v][k];
6089 assert (1 <= nnodesinS && nnodesinS <= nnodes-1);
6094 if( sepadata->separatesinglenodecuts && nodepartition !=
NULL && (nnodesinS == 1 || nnodesinS == nnodes-1) )
6096 SCIPdebugMsg(scip,
" -> shore S or T has only one node - skip partition.\n");
6106 SCIPdebugMsg(scip,
" -> commodity %d: directed cutdemand=%g\n", k, comcutdemands[k]);
6116 SCIPdebugMsg(scip,
" -> commodity %d: undirected cutdemand=%g\n", k, comcutdemands[k]);
6121 if( k == ncommodities )
6125 for( a = 0; a <
narcs; a++ )
6134 assert(arcsources[a] < nnodes);
6135 assert(arctargets[a] < nnodes);
6141 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) ||
6151 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6157 if( !
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6166 if( arccapacityrows[a] ==
NULL )
6174 assert(rowweights[r] == 0.0);