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
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
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
198 SCIP_Real maxweightrange;
200 SCIP_Bool trynegscaling;
201 SCIP_Bool fixintegralrhs;
202 SCIP_Bool dynamiccuts;
206 SCIP_Real maxinconsistencyratio;
207 SCIP_Real maxarcinconsistencyratio;
208 SCIP_Bool checkcutshoreconnectivity;
209 SCIP_Bool separatesinglenodecuts;
210 SCIP_Bool separateflowcutset;
211 SCIP_Bool separateknapsack;
212 SCIP_Bool lastroundsuccess;
219 unsigned char* flowrowsigns;
220 SCIP_Real* flowrowscalars;
221 SCIP_Real* flowrowscores;
222 unsigned char* capacityrowsigns;
223 SCIP_Real* capacityrowscores;
229 SCIP_Bool* minusflow;
231 int nemptycommodities;
233 int commoditysignssize;
252 SCIP_Real ninconsistencies;
254 int capacityrowssize;
255 SCIP_Bool* colisincident;
281 int* representatives;
293#define LHSPOSSIBLE 1u
294#define RHSPOSSIBLE 2u
295#define LHSASSIGNED 4u
296#define RHSASSIGNED 8u
299#define UNDIRECTED 64u
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;
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;
397 int ncommodities = mcfdata->ncommodities;
398 int* commoditysigns = mcfdata->commoditysigns;
399 int* colcommodity = mcfdata->colcommodity;
400 int* rowcommodity = mcfdata->rowcommodity;
401 int* rownodeid = mcfdata->rownodeid;
402 SCIP_ROW** capacityrows = mcfdata->capacityrows;
405 SCIP_Real* comdemands;
411 int ncompcommodities;
420 assert(2 <= ncompnodes && ncompnodes <= mcfdata->
nnodes);
421 assert(1 <= ncomparcs && ncomparcs <= mcfdata->
narcs);
426 for( v = 0; v < mcfdata->nnodes; v++ )
427 assert(compnodeid[v] == -1);
438 for( k = 0; k < ncommodities; k++ )
439 compcommodity[k] = -1;
446 for(
i = 0;
i < ncompnodes;
i++ )
454 ncompcommodities = 0;
455 for(
i = 0;
i < nflowcands;
i++ )
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++ )
527 if( rv >= 0 && compnodeid[rv] >= 0 )
533 rk = rowcommodity[
r];
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)
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;
680 if( mcfnetwork ==
NULL )
687 for( v = 0; v < mcfnetwork->
nnodes; v++ )
706 for(
a = 0;
a < mcfnetwork->
narcs;
a++ )
722void printCommodities(
727 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
728 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
729 int ncommodities = mcfdata->ncommodities;
730 int* commoditysigns = mcfdata->commoditysigns;
731 int* colcommodity = mcfdata->colcommodity;
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;
752 for( k = 0; k < ncommodities; k++ )
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 )
812 for(
c = 0;
c < ncols;
c++ )
814 if( colcommodity[
c] == -1 )
823 for(
r = 0;
r < nrows;
r++ )
841 SCIP_Real* rowscores = (SCIP_Real*)dataptr;
843 if( rowscores[ind2] < rowscores[ind1] )
845 else if( rowscores[ind2] > rowscores[ind1] )
858 unsigned char* flowrowsigns;
859 SCIP_Real* flowrowscalars;
860 SCIP_Real* flowrowscores;
868 SCIP_Real maxdualflow;
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++ )
899 SCIP_Bool hasposcoef;
900 SCIP_Bool hasnegcoef;
901 SCIP_Real absdualsol;
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++ )
945 SCIP_Real absval =
ABS(rowvals[
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++;
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;
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++ )
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;
1075 int* colcommodity = mcfdata->colcommodity;
1076 int ncommodities = mcfdata->ncommodities;
1077 int nactivecommodities = mcfdata->ncommodities - mcfdata->nemptycommodities;
1080 unsigned char* capacityrowsigns;
1081 SCIP_Real* capacityrowscores;
1088 SCIP_Real maxdualcapacity;
1089 int maxcolspercommoditylimit;
1090 int *ncolspercommodity;
1091 int *maxcolspercommodity;
1092 SCIP_Real directedcandsscore;
1093 SCIP_Real undirectedcandsscore;
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;
1145 SCIP_Real sameflowcoef;
1146 SCIP_Real sameabsflowcoef;
1147 SCIP_Real maxabscapacitycoef;
1148 SCIP_Real absdualsol;
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++ )
1212 k = colcommodity[
c];
1213 assert(-1 <= k && k < ncommodities);
1218 abscoef =
ABS(rowvals[
i]);
1219 if( sameflowcoef == 0.0 )
1220 sameflowcoef = rowvals[
i];
1223 if( sameabsflowcoef == 0.0 )
1224 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 )
1268 SCIP_Real commodityexcessratio;
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);
1308 capacityrowscores[
r] += 500.0;
1312 capacityrowscores[
r] += 250.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);
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);
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];
1383 if( maxcolspercommodity[
r] <= maxcolspercommoditylimit )
1384 capacityrowscores[
r] -= 1000.0;
1390 mcfdata->modeltype = modeltype;
1398 for(
i = 0;
i < mcfdata->ncapacitycands;
i++ )
1402 r = capacitycands[
i];
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++ )
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 );
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;
1528 int ncommodities = mcfdata->ncommodities;
1529 int* commoditysigns = mcfdata->commoditysigns;
1530 int* colcommodity = mcfdata->colcommodity;
1531 int* rowcommodity = mcfdata->rowcommodity;
1532 int* newcols = mcfdata->newcols;
1538 SCIP_Bool invertrow;
1553 invertrow = ((rowsign &
INVERTED) != 0);
1554 rowsign &= ~INVERTED;
1556 assert(rowcommodity[
r] == -1);
1557 assert((flowrowsigns[
r] | rowsign) == flowrowsigns[
r]);
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 )
1637 colcommodity[
c] = k;
1638 newcols[mcfdata->nnewcols] =
c;
1639 mcfdata->nnewcols++;
1640 comcolids[*ncomcolids] =
c;
1646 val = rowscale * rowvals[
i];
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);
1683 for(
i = 0;
i < ncomrows;
i++ )
1687 unsigned char rowsign;
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;
1740 int ncommodities = mcfdata->ncommodities;
1741 int* colcommodity = mcfdata->colcommodity;
1742 int* rowcommodity = mcfdata->rowcommodity;
1746 assert(0 <= k && k < ncommodities);
1751 SCIPdebugMsg(
scip,
"deleting commodity %d (%d total commodities) with %d flow rows\n", k, ncommodities, nrows);
1756 for( n = 0; n < nrows; n++ )
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;
1803 if( k == ncommodities-1 )
1804 mcfdata->ncommodities--;
1806 mcfdata->nemptycommodities++;
1816 unsigned char* rowsign,
1817 SCIP_Bool* invertcommodity
1820 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1821 SCIP_Bool* plusflow = mcfdata->plusflow;
1822 SCIP_Bool* minusflow = mcfdata->minusflow;
1823 int* colcommodity = mcfdata->colcommodity;
1824 int* rowcommodity = mcfdata->rowcommodity;
1825 int* commoditysigns = mcfdata->commoditysigns;
1830 unsigned char flowrowsign;
1831 unsigned char invflowrowsign;
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 )
1876 flowrowsign &= ~RHSPOSSIBLE;
1877 invflowrowsign &= ~LHSPOSSIBLE;
1881 flowrowsign &= ~LHSPOSSIBLE;
1882 invflowrowsign &= ~RHSPOSSIBLE;
1885 if( minusflow[rowc] )
1888 if( rowvals[j] > 0.0 )
1890 flowrowsign &= ~LHSPOSSIBLE;
1891 invflowrowsign &= ~RHSPOSSIBLE;
1895 flowrowsign &= ~RHSPOSSIBLE;
1896 invflowrowsign &= ~LHSPOSSIBLE;
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,
1948 SCIP_Bool* nextinvertcommodity
1951 SCIP_Real* flowrowscores = mcfdata->flowrowscores;
1952 SCIP_Bool* plusflow = mcfdata->plusflow;
1953 SCIP_Bool* minusflow = mcfdata->minusflow;
1954 int* newcols = mcfdata->newcols;
1955 int ncommodities = mcfdata->ncommodities;
1965 *nextinvertcommodity =
FALSE;
1973 while( mcfdata->nnewcols > 0 )
1979 unsigned char bestrowsign;
1980 SCIP_Bool bestinvertcommodity;
1981 SCIP_Real bestscore;
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;
2007 SCIP_Bool invertcommodity;
2015 if( flowrowsign != 0 )
2022 score = flowrowscores[
r];
2029 if( (flowrowsign &
INVERTED) != 0 )
2032 if( score > bestscore )
2035 bestrowsign = flowrowsign;
2036 bestinvertcommodity = invertcommodity;
2046 if( bestrow !=
NULL )
2049 assert(bestrowsign != 0);
2051 *nextrowsign = bestrowsign;
2052 *nextinvertcommodity = bestinvertcommodity;
2063 SCIP_Real maxflowvarflowrowratio,
2067 int* flowcands = mcfdata->flowcands;
2069 SCIP_Bool* plusflow;
2070 SCIP_Bool* minusflow;
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;
2138 SCIP_Bool newinvertcommodity;
2147 getFlowrowFit(
scip, mcfdata, newrow, mcfdata->ncommodities, &newrowsign, &newinvertcommodity);
2148 if( newrowsign == 0 )
2150 assert(!newinvertcommodity);
2154 SCIPdebugMsg(
scip,
" -------------------start new commodity %d--------------------- \n", mcfdata->ncommodities );
2163 if( newinvertcommodity )
2169 comrows[
nnodes] = newrow;
2176 while( newrow !=
NULL );
2178 ncomnodes[mcfdata->ncommodities-1] =
nnodes;
2180 nflowvars += ncomcolids;
2181 SCIPdebugMsg(
scip,
" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n", mcfdata->ncommodities-1,
nnodes, maxnnodes);
2190 nflowrows -= ndelflowrows;
2191 nflowvars -= ndelflowvars;
2197 for( k = 0; k < mcfdata->ncommodities; k++ )
2209 for(
i = 0;
i < mcfdata->nflowcands;
i++ )
2213 if( rowcommodity[
r] == k )
2218 if(
nnodes == ncomnodes[k] )
2225 nflowrows -= ndelflowrows;
2226 nflowvars -= ndelflowvars;
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);
2246 else if( (SCIP_Real)nflowvars / (SCIP_Real)nflowrows > maxflowvarflowrowratio )
2259 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
2260 int* colcommodity = mcfdata->colcommodity;
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;
2314 r = capacitycands[
i];
2316 capacityrow = rows[
r];
2326 assert(capacityrowscores[
r] > 0.0);
2333 assert( rowcommodity[
r] == -1 );
2339 nassignedflowvars = 0;
2340 nunassignedflowvars = 0;
2341 for( k = 0; k < rowlen; k++ )
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;
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);
2412 if( colcommodity[rowc] >= 0 && colarcid[rowc] == -1 )
2413 colarcid[rowc] = mcfdata->narcs;
2432 int* colcommodity = mcfdata->colcommodity;
2433 int* colarcid = mcfdata->colarcid;
2434 int* newcols = mcfdata->newcols;
2435 SCIP_ROW** capacityrows = mcfdata->capacityrows;
2436 SCIP_Bool* colisincident = mcfdata->colisincident;
2451 mcfdata->nnewcols = 0;
2453 for(
i = 0;
i < rowlen;
i++ )
2465 arcid = colarcid[
c];
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] )
2498 colisincident[caprowc] =
TRUE;
2499 newcols[mcfdata->nnewcols] = caprowc;
2500 mcfdata->nnewcols++;
2514 int* basearcpattern,
2519 SCIP_Bool* invertcommodity
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;
2539 SCIP_Bool incompatible;
2541 int* overlappingarcs;
2542 int noverlappingarcs;
2547 *invertcommodity =
FALSE;
2560 rowcom = rowcommodity[
r];
2561 assert(0 <= rowcom && rowcom < mcfdata->ncommodities);
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);
2589 arcid = colarcid[
c];
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];
2653 basenum =
ABS(basearcpattern[arcid]);
2654 arcnum =
ABS(arcpattern[arcid]);
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;
2673 assert(overlap <= (SCIP_Real) rowlen);
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;
2717 int ncommodities = mcfdata->ncommodities;
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;
2727 SCIP_Bool* colisincident;
2728 SCIP_Bool* rowprocessed;
2739 SCIP_Real* bestscores;
2740 SCIP_Bool* bestinverted;
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++ )
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)
2832 if( commoditysigns[basecommodity] == -1 )
2835 for(
i = 0;
i < rowlen;
i++ )
2841 arcid = colarcid[
c];
2846 arcpattern[arcid]++;
2848 arcpattern[arcid]--;
2861 for(
i = 0;
i < ncommodities;
i++ )
2863 bestflowrows[
i] =
NULL;
2864 bestscores[
i] = 0.0;
2877 for(
i = 0;
i < mcfdata->nnewcols;
i++ )
2886 assert(mcfdata->colcommodity[
c] >= 0);
2887 assert(mcfdata->colcommodity[
c] != basecommodity);
2891 colisincident[
c] =
FALSE;
2897 for( j = 0; j < collen; j++ )
2902 SCIP_Bool invertcommodity;
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]);
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;
2942 for(
i = 0;
i < ncommodities;
i++ )
2946 if( bestflowrows[
i] ==
NULL )
2950 assert(0 <= comr && comr < nrows);
2951 assert(rowcommodity[comr] ==
i);
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",
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;
3034 if( colsources[
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];
3065 assert(0 <= k && k < mcfdata->ncommodities);
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;
3112 int* colcommodity = mcfdata->colcommodity;
3113 int* rowcommodity = mcfdata->rowcommodity;
3115 int* rownodeid = mcfdata->rownodeid;
3116 int* colarcid = mcfdata->colarcid;
3117 int nnodes = mcfdata->nnodes;
3118 int ncommodities = mcfdata->ncommodities;
3125 int* sortedflowcands;
3126 int* sortedflowcandnodeid;
3139 assert(mcfdata->nemptycommodities == 0);
3140 assert(ncommodities >= 0);
3144 if( ncommodities == 0 || nflowcands == 0 ||
nnodes == 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 )
3198 assert(rowcommodity[sortedflowcands[n]] == -1);
3201 assert(sortedflowcandnodeid[n] == 0);
3206 for( v = 0; n < nflowcands; v++ )
3212 assert(rowcommodity[sortedflowcands[n]] >= 0);
3213 assert(rownodeid[sortedflowcands[n]] == sortedflowcandnodeid[n]);
3214 assert(sortedflowcandnodeid[n] == v);
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];
3248 assert(rowcommodity[
r] == colcommodity[
c]);
3258 else if( arcid == -1 )
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 )
3309 adjnodes[nadjnodes] = u;
3317 for( l = 0; l < nadjnodes; l++ )
3323 assert(sourcecount[u] > 0 || targetcount[u] > 0);
3328 if( sourcecount[u] >= arcsthreshold )
3338 for( m = 0; m < ninccols; m++ )
3349 assert(s == v || t == v);
3354 colarcid[
c] = arcid;
3357 inccols[m] = inccols[ninccols-1];
3365 if( targetcount[u] >= arcsthreshold )
3375 for( m = 0; m < ninccols; m++ )
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;
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;
3450 int* colcommodity = mcfdata->colcommodity;
3451 int* rowcommodity = mcfdata->rowcommodity;
3452 int* colarcid = mcfdata->colarcid;
3453 int* rowarcid = mcfdata->rowarcid;
3454 int* rownodeid = mcfdata->rownodeid;
3455 int ncommodities = mcfdata->ncommodities;
3456 int* commoditysigns = mcfdata->commoditysigns;
3457 int narcs = mcfdata->narcs;
3458 int nnodes = mcfdata->nnodes;
3459 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3467 SCIP_Bool* arcisincom;
3471 int nnodesthreshold;
3472 int newncommodities;
3485 permsize = ncommodities;
3497 assert(flowcands !=
NULL || nflowcands == 0);
3500 for(
i = 0;
i < nflowcands;
i++ )
3507 assert((rownodeid[
r] >= 0) == (rowcommodity[
r] >= 0));
3508 if( rowcommodity[
r] >= 0 )
3510 assert(rowcommodity[
r] < ncommodities);
3511 nnodespercom[rowcommodity[
r]]++;
3534 for( j = 0; j < rowlen; j++ )
3540 if( colcommodity[
c] >= 0 && colarcid[
c] ==
a )
3542 assert(colcommodity[
c] < ncommodities);
3543 arcisincom[colcommodity[
c]] =
TRUE;
3548 for( k = 0; k < ncommodities; k++ )
3557 for( k = 0; k < ncommodities; k++ )
3558 maxnnodes =
MAX(maxnnodes, nnodespercom[k]);
3569 newncommodities = 0;
3570 for( k = 0; k < ncommodities; k++ )
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 )
3588 SCIP_Bool* arcisused;
3589 SCIP_Bool* nodeisused;
3595 SCIPdebugMsg(
scip,
" -> discarding %d of %d commodities\n", ncommodities - newncommodities, ncommodities);
3603 for(
c = 0;
c < ncols;
c++ )
3605 if( colcommodity[
c] >= 0 )
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++ )
3627 assert((rownodeid[
r] >= 0) == (rowcommodity[
r] >= 0));
3628 if( rowcommodity[
r] >= 0 )
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;
3659 capacityrows[newnarcs] = capacityrows[
a];
3670 rowarcid[
r] = perm[
a];
3674 if( newnarcs <
narcs )
3678 for(
c = 0;
c < ncols;
c++ )
3680 if( colarcid[
c] >= 0 )
3682 colarcid[
c] = perm[colarcid[
c]];
3686 mcfdata->narcs = newnarcs;
3702 for( v = 0; v <
nnodes; v++ )
3707 perm[v] = newnnodes;
3719 for(
i = 0;
i < nflowcands;
i++ )
3726 assert((rownodeid[
r] >= 0) == (rowcommodity[
r] >= 0));
3727 if( rowcommodity[
r] >= 0 )
3729 assert(rowcommodity[
r] < ncommodities);
3730 rownodeid[
r] = perm[rownodeid[
r]];
3734 mcfdata->nnodes = newnnodes;
3746 mcfdata->nemptycommodities = 0;
3768 int* colarcid = mcfdata->colarcid;
3769 int* colcommodity = mcfdata->colcommodity;
3770 int narcs = mcfdata->narcs;
3771 int nnodes = mcfdata->nnodes;
3772 int ncommodities = mcfdata->ncommodities;
3773 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3775 SCIP_Real maxinconsistencyratio =
sepadata->maxinconsistencyratio;
3776 SCIP_Real maxarcinconsistencyratio =
sepadata->maxarcinconsistencyratio;
3786 SCIP_Real *sourcenodecnt;
3787 SCIP_Real *targetnodecnt;
3788 int *flowvarspercom;
3794 SCIP_Real maxninconsistencies;
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;
3841 nextoutarcs[
a] = -1;
3855 mcfdata->ninconsistencies = 0.0;
3865 SCIP_Real bestsourcecnt;
3866 SCIP_Real besttargetcnt;
3867 SCIP_Real totalsourcecnt;
3868 SCIP_Real totaltargetcnt;
3869 SCIP_Real totalnodecnt;
3870 SCIP_Real nsourceinconsistencies;
3871 SCIP_Real ntargetinconsistencies;
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);
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];
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;
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);
4121 int* arcsources = mcfdata->arcsources;
4122 int* arctargets = mcfdata->arctargets;
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;
4147 stacknodes[0] = startv;
4149 nodevisited[startv] =
ONSTACK;
4152 while( nstacknodes > 0 )
4163 v = stacknodes[nstacknodes-1];
4171 compnodes[*ncompnodes] = v;
4175 for(
a = firstoutarcs[v];
a != -1;
a = nextoutarcs[
a] )
4182 targetv = arctargets[
a];
4185 if( targetv != -1 && nodevisited[targetv] ==
VISITED )
4190 comparcs[*ncomparcs] =
a;
4194 if( targetv != -1 && nodevisited[targetv] ==
UNKNOWN )
4197 stacknodes[nstacknodes] = targetv;
4199 nodevisited[targetv] =
ONSTACK;
4204 for(
a = firstinarcs[v];
a != -1;
a = nextinarcs[
a] )
4211 sourcev = arcsources[
a];
4214 if( sourcev != -1 && nodevisited[sourcev] ==
VISITED )
4219 comparcs[*ncomparcs] =
a;
4223 if( sourcev != -1 && nodevisited[sourcev] ==
UNKNOWN )
4226 stacknodes[nstacknodes] = sourcev;
4228 nodevisited[sourcev] =
ONSTACK;
4259 int mcfnetworkssize;
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;
4338 mcfdata.modeltype = modeltype;
4349 if( mcfdata.nflowcands == 0 )
4367 printCommodities(
scip, &mcfdata);
4378 if( mcfdata.ncapacitycands == 0 )
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 )
4457 assert(compnodes[0] == v);
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);
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
4558 SCIP_Bool* colvisited;
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++)
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;
4635 row = arccapacityrows[
a];
4647 for(
i = 0;
i < rowlen;
i++ )
4652 if(colcommodity[
c] == -1 && ! colvisited[
c] )
4655 colvisited[
c] =
TRUE;
4680 for( k = 0; k < ncommodities; k++ )
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,
4737 while( v != representatives[v] )
4739 representatives[v] = representatives[representatives[v]];
4740 v = representatives[v];
4749 int* representatives,
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 )
4826 source1 = nodepair1->node1;
4827 source2 = nodepair2->node1;
4828 target1 = nodepair1->node2;
4829 target2 = nodepair2->node2;
4835 assert(source1 <= target1);
4836 assert(source2 <= target2);
4838 return (source1 == source2 && target1 == target2);
4852 unsigned int hashval;
4862 source = nodepair->node1;
4863 target = nodepair->node2;
4867 assert(source <= target);
4869 hashval = (unsigned)((source << 16) + target);
4892#ifdef BETTERWEIGHTFORDEMANDNODES
4895 SCIP_Real** nodeflowscales;
4896 SCIP_Real maxweight;
4897 SCIP_Real minweight;
4914#ifdef BETTERWEIGHTFORDEMANDNODES
4931 hashtablesize = mcfnetwork->
narcs;
4934 hashGetKeyNodepairs, hashKeyEqNodepairs, hashKeyValNodepairs, (
void*) mcfnetwork) );
4941 for(
a = 0;
a < mcfnetwork->
narcs;
a++ )
4965 if( nodepair.node1 == -1 || nodepair.node2 == -1 )
4969 if( capacityrow !=
NULL )
4976 SCIP_Real totalflow;
4985 slack =
MAX(slack, 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;
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);
5103 for( n = 0; n < nnodepairs; n++ )
5105 int node1 = nodepairs[n].node1;
5106 int node2 = nodepairs[n].node2;
5108#ifdef BETTERWEIGHTFORDEMANDNODES
5110 SCIP_Bool hasdemand1 =
FALSE;
5111 SCIP_Bool hasdemand2 =
FALSE;
5115 SCIPdebugMsg(
scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5121 for( k = 0; k < ncommodities; k++ )
5123 if( nodeflowrows[node1][k] ==
NULL )
5126 if( nodeflowscales[node1][k] > 0.0 )
5141 for( k = 0; k < ncommodities; k++ )
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);
5281 (*nodepartition)->nclusters = 0;
5290 nclustersleft = mcfnetwork->
nnodes;
5302 node1 = nodepair->node1;
5303 node2 = nodepair->node2;
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];
5368 (*nodepartition)->nodeclusters[v] =
c;
5374 for(
c = 0;
c < (*nodepartition)->nclusters;
c++ )
5376 (*nodepartition)->clusterbegin[
c] = pos;
5377 pos += clustersize[
c];
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;
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;
5460 const int* arcsources = mcfnetwork->
arcsources;
5461 const int* arctargets = mcfnetwork->
arctargets;
5470 nclusters = nodepartition->nclusters;
5477 ncomponents = nclusters;
5478 assert(ncomponents >= 2);
5483 int s = arcsources[
a];
5484 int t = arctargets[
a];
5487 if( s == -1 || t == -1 )
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);
5538void nodepartitionPrint(
5544 for(
c = 0;
c < nodepartition->nclusters;
c++ )
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++ )
5596 SCIP_Bool inpartition;
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++ )
5720 SCIP_Bool hasfractional;
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");
5794 SCIP_Real* cutcoefs,
5798 SCIP_Bool cutislocal,
5827 for(
i = 0;
i < cutnnz; ++
i )
5829 cutvars[
i] =
vars[cutinds[
i]];
5845 SCIPdebugMsg(
scip,
" -> found MCF cut <%s>: rhs=%f, act=%f eff=%f rank=%d\n",
5865 SCIP_CALL(
SCIPseparateRelaxedKnapsack(
scip,
NULL, sepa, cutnnz, cutvars, cutcoefs, +1.0, cutrhs,
sol,
cutoff, ncuts) );
5881 SCIP_Bool allowlocal,
5908 SCIP_Real* cutcoefs;
5913 SCIP_Real* rowweights;
5914 SCIP_Real* comcutdemands;
5915 SCIP_Real* comdemands;
5916 unsigned int partition;
5917 unsigned int allpartitions;
5918 unsigned int startpartition;
5919 SCIP_Bool useinverted;
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++ )
6015 SCIP_Real bestdelta = 1.0;
6016 SCIP_Real bestefficacy;
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++ )
6072 for( k = 0; k < ncommodities; k++ )
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];
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");
6103 for( k = 0; k < ncommodities; k++ )
6106 SCIPdebugMsg(
scip,
" -> commodity %d: directed cutdemand=%g\n", k, comcutdemands[k]);
6113 for( k = 0; k < ncommodities; k++ )
6116 SCIPdebugMsg(
scip,
" -> commodity %d: undirected cutdemand=%g\n", k, comcutdemands[k]);
6121 if( k == ncommodities )
6129 SCIP_Real feasibility;
6166 if( arccapacityrows[
a] ==
NULL )
6180 if( arcsources[
a] == -1 || arctargets[
a] == -1 )
6195 rowweights[
r] = arccapacityscales[
a];
6202 if( rowweights[
r] > 0.0 )
6212 for( j = 0; j < rowlen; j++ )
6217 coef = rowvals[j] * arccapacityscales[
a];
6223 k = colcommodity[
c];
6225 comdemands[k] = coef;
6239 while( left <= right )
6241 int mid = (left+right)/2;
6243 if(
REALABS( deltas[mid] / coef - 1.0 ) < 1e-03 )
6248 else if( coef < deltas[mid] )
6258 assert(ndeltas <= deltassize);
6259 if( ndeltas == deltassize )
6264 if( left < ndeltas )
6266 for( d = ndeltas; d > left; d-- )
6267 deltas[d] = deltas[d-1];
6269 deltas[left] = coef;
6278 for( v = 0; v <
nnodes; v++ )
6281 for( k = 0; k < ncommodities; k++ )
6287 if( comdemands[k] == 0.0 )
6290 scale = comdemands[k];
6313 if( comcutdemands[k] > 0.0 )
6332 if( nodeflowrows[v][k] ==
NULL )
6339 SCIP_Real feasibility;
6347 rowweights[
r] = scale * nodeflowscales[v][k];
6348 if( nodeflowinverted[v][k] )
6349 rowweights[
r] *= -1.0;
6350 SCIPdebugMsg(
scip,
" -> node %d, commodity %d, r=%d, flow row <%s>: scale=%g weight=%g slack=%g dual=%g\n",
6356 if( nodeflowscales[v][k] > 0.0 )
6375 bestdelta = deltas[ndeltas-1];
6386 for( d = ndeltas-1; d >= 0 && d >= ndeltas-maxtestdelta; d-- )
6388 SCIP_Real cutrhs = 0.0;
6389 SCIP_Real cutefficacy = 0.0;
6390 SCIP_Bool cutislocal =
FALSE;
6401 SCIP_CALL(
SCIPcalcMIR(
scip,
sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal,
sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6402 1.0/deltas[d], aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6403 assert(allowlocal || !cutislocal);
6413 if( cutefficacy > bestefficacy )
6415 bestdelta = deltas[d];
6416 bestefficacy = cutefficacy;
6422 SCIPdebugMsg(
scip,
"success -> delta = %g -> rhs: %g, efficacy: %g\n", deltas[d], cutrhs, cutefficacy);
6423 SCIP_CALL(
addCut(
scip, sepa,
sepadata,
sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts,
cutoff) );
6430 if( arccapacityrows[
a] !=
NULL )
6436 if(
r >= 0 && rowweights[
r] != 0.0 )
6438 MCFdebugMessage(
" -> arc %d, capacity row <%s>: weight=%g slack=%g prod=%g dual=%g\n",
a,
6451 if(
sepadata->separateflowcutset && oldncuts == *ncuts && !*
cutoff )
6457 SCIP_Real onedivoneminsf0;
6458 SCIP_Real totalviolationdelta;
6459 totalviolationdelta = 0.0;
6460 onedivoneminsf0 = 1.0/(1.0 - f0);
6466 SCIP_Real rowweight;
6469 SCIP_Real rowconstant;
6470 SCIP_Real violationdelta;
6475 if( arccapacityrows[
a] ==
NULL )
6486 if( rowweights[
r] == 0.0 )
6501 rowweight = rowweights[
r]/bestdelta;
6506 violationdelta = rowweight * (rowlhs - rowconstant);
6508 violationdelta = rowweight * (rowrhs - rowconstant);
6510 for( j = 0; j < rowlen; j++ )
6518 coef = rowvals[j] * rowweight;
6529 if( colcommodity[
c] >= 0 )
6540 mircoef =
SCIPfloor(
scip, coef) + (fj - f0)*onedivoneminsf0;
6547 mircoef = coef * onedivoneminsf0;
6552 if( colcommodity[
c] >= 0 )
6553 violationdelta += mircoef * solval;
6555 violationdelta -= mircoef * solval;
6560 SCIPdebugMsg(
scip,
" -> discarding capacity row <%s> of weight %g and slack %g: increases MIR violation by %g\n",
6563 rowweights[
r] = 0.0;
6564 totalviolationdelta += violationdelta;
6569 if( totalviolationdelta > 0.0 )
6572 SCIP_Real cutefficacy = 0.0;
6573 SCIP_Bool cutislocal;
6582 SCIPdebugMsg(
scip,
"applying MIR with delta = %g to flowcut inequality (violation improvement: %g)\n", bestdelta, totalviolationdelta);
6589 SCIP_CALL(
SCIPcalcMIR(
scip,
sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal,
sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6590 1.0/bestdelta, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6592 assert(allowlocal || !cutislocal);
6596 SCIPdebugMsg(
scip,
" -> delta = %g -> rhs: %g, efficacy: %g\n", bestdelta, cutrhs, cutefficacy);
6597 SCIP_CALL(
addCut(
scip, sepa,
sepadata,
sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts,
cutoff) );
6624 SCIP_Bool allowlocal,
6637 SCIP_Real colrowratio;
6654 if( ncols !=
nvars )
6669 colrowratio = (
SCIP_Real)ncols/(nrows+1e-9);
6682 if( colrowratio < MINCOLROWRATIO || colrowratio >
MAXCOLROWRATIO )
6701 MCFdebugMessage(
" -> extracted network %d has %d nodes, %d (%d) arcs (uncapacitated), and %d commodities (modeltype: %s)\n",
6708#ifdef COUNTNETWORKVARIABLETYPES
6715 mcfnetworks =
sepadata->mcfnetworks;
6716 nmcfnetworks =
sepadata->nmcfnetworks;
6725 for(
i = 0;
i < nmcfnetworks && !
cutoff;
i++ )
6729 SCIP_Real arcnoderatio;
6731 mcfnetwork = mcfnetworks[
i];
6742 MCFdebugMessage(
"MCF network has %d nodes and %d arcs. arc node ratio %.2f exceed --> exit\n",
6748 if(
sepadata->separatesinglenodecuts )
6759 nodepartitionPrint(nodepartition);
6769 MCFdebugMessage(
"MCF network has %d nodes, %d arcs, %d commodities. Found %d MCF network cuts, cutoff = %u.\n",
6778 else if( ncuts > 0 )
6935 sepaExeclpMcf, sepaExecsolMcf,
6949 "separating/mcf/nclusters",
6950 "number of clusters to generate in the shrunken network -- default separation",
6953 "separating/mcf/maxweightrange",
6954 "maximal valid range max(|weights|)/min(|weights|) of row weights",
6957 "separating/mcf/maxtestdelta",
6958 "maximal number of different deltas to try (-1: unlimited) -- default separation",
6961 "separating/mcf/trynegscaling",
6962 "should negative values also be tested in scaling?",
6965 "separating/mcf/fixintegralrhs",
6966 "should an additional variable be complemented if f0 = 0?",
6969 "separating/mcf/dynamiccuts",
6970 "should generated cuts be removed from the LP if they are no longer tight?",
6973 "separating/mcf/modeltype",
6974 "model type of network (0: auto, 1:directed, 2:undirected)",
6977 "separating/mcf/maxsepacuts",
6978 "maximal number of mcf cuts separated per separation round",
6981 "separating/mcf/maxsepacutsroot",
6982 "maximal number of mcf cuts separated per separation round in the root node -- default separation",
6985 "separating/mcf/maxinconsistencyratio",
6986 "maximum inconsistency ratio for separation at all",
6989 "separating/mcf/maxarcinconsistencyratio",
6990 "maximum inconsistency ratio of arcs not to be deleted",
6993 "separating/mcf/checkcutshoreconnectivity",
6994 "should we separate only if the cuts shores are connected?",
6997 "separating/mcf/separatesinglenodecuts",
6998 "should we separate inequalities based on single-node cuts?",
7001 "separating/mcf/separateflowcutset",
7002 "should we separate flowcutset inequalities on the network cuts?",
7005 "separating/mcf/separateknapsack",
7006 "should we separate knapsack cover inequalities on the network cuts?",
Constraint handler for knapsack constraints of the form , x binary and .
methods for the aggregation rows
#define SCIP_LONGINT_FORMAT
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_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
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)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)),)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
int SCIPgetNLPBranchCands(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPfreeMemoryArrayNull(scip, ptr)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPallocMemory(scip, ptr)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemory(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPallocBuffer(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetNLPNonz(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPcaptureRow(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
int SCIProwGetRank(SCIP_ROW *row)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeSepaMcf(SCIP *scip)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
static void addFlowrowToCommodity(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, unsigned char rowsign, int *comcolids, int *ncomcolids)
static SCIP_RETCODE extractFlow(SCIP *scip, MCFDATA *mcfdata, SCIP_Real maxflowvarflowrowratio, SCIP_Bool *failed)
static SCIP_RETCODE nodepartitionCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION **nodepartition, int nclusters)
static SCIP_RETCODE mcfnetworkFree(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
static SCIP_RETCODE mcfnetworkFill(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, MCFDATA *mcfdata, int *compnodeid, int *compnodes, int ncompnodes, int *comparcs, int ncomparcs)
struct nodepair NODEPAIRENTRY
#define DEFAULT_MODELTYPE
#define DEFAULT_MAXWEIGHTRANGE
#define DEFAULT_MAXARCINCONSISTENCYRATIO
struct nodepartition NODEPARTITION
#define DEFAULT_DYNAMICCUTS
enum McfEffortLevel MCFEFFORTLEVEL
static void getNextFlowrow(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW **nextrow, unsigned char *nextrowsign, SCIP_Bool *nextinvertcommodity)
static SCIP_RETCODE findUncapacitatedArcs(SCIP *scip, MCFDATA *mcfdata)
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)
static void nodepartitionJoin(NODEPARTITION *nodepartition, int rep1, int rep2)
static SCIP_RETCODE identifySourcesTargets(SCIP *scip, MCFDATA *mcfdata, SCIP_SEPADATA *sepadata, MCFEFFORTLEVEL *effortlevel)
#define DEFAULT_SEPARATEFLOWCUTSET
#define HASHSIZE_NODEPAIRS
static SCIP_RETCODE mcfnetworkCreate(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
static void nodepairqueueFree(SCIP *scip, NODEPAIRQUEUE **nodepairqueue)
static SCIP_RETCODE mcfnetworkExtract(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_MCFNETWORK ***mcfnetworks, int *nmcfnetworks, MCFEFFORTLEVEL *effortlevel)
#define UNCAPACITATEDARCSTRESHOLD
static SCIP_RETCODE extractNodes(SCIP *scip, MCFDATA *mcfdata)
static void unionfindJoinSets(int *representatives, int rep1, int rep2)
static void deleteCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int nrows, int *ndelflowrows, int *ndelflowvars)
@ MCFEFFORTLEVEL_AGGRESSIVE
static SCIP_RETCODE nodepairqueueCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPAIRQUEUE **nodepairqueue)
static int nodepartitionIsConnected(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, unsigned int partition)
#define DEFAULT_CHECKCUTSHORECONNECTIVITY
#define DEFAULT_TRYNEGSCALING
static SCIP_RETCODE extractFlowRows(SCIP *scip, MCFDATA *mcfdata)
enum SCIP_McfModeltype SCIP_MCFMODELTYPE
struct nodepairqueue NODEPAIRQUEUE
#define DEFAULT_SEPARATESINGLENODECUTS
#define DEFAULT_MAXSEPACUTSROOT
static void getFlowrowFit(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, int k, unsigned char *rowsign, SCIP_Bool *invertcommodity)
#define MAXFLOWVARFLOWROWRATIO
#define DEFAULT_FIXINTEGRALRHS
static void getIncidentNodes(SCIP *scip, MCFDATA *mcfdata, SCIP_COL *col, int *sourcenode, int *targetnode)
static SCIP_Bool nodeInPartition(NODEPARTITION *nodepartition, unsigned int partition, SCIP_Bool inverted, int v)
static SCIP_RETCODE extractCapacities(SCIP *scip, MCFDATA *mcfdata)
static SCIP_RETCODE createNewArc(SCIP *scip, MCFDATA *mcfdata, int source, int target, int *newarcid)
static SCIP_RETCODE identifyComponent(SCIP *scip, MCFDATA *mcfdata, int *nodevisited, int startv, int *compnodes, int *ncompnodes, int *comparcs, int *ncomparcs)
static SCIP_RETCODE generateClusterCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, int *ncuts, SCIP_Bool *cutoff)
#define DEFAULT_MAXTESTDELTA
static SCIP_RETCODE cleanupNetwork(SCIP *scip, MCFDATA *mcfdata)
#define DEFAULT_NCLUSTERS
#define SEPA_MAXBOUNDDIST
static void nodepartitionFree(SCIP *scip, NODEPARTITION **nodepartition)
static SCIP_RETCODE extractCapacityRows(SCIP *scip, MCFDATA *mcfdata)
static SCIP_Bool nodepairqueueIsEmpty(NODEPAIRQUEUE *nodepairqueue)
static int nodepartitionGetRepresentative(NODEPARTITION *nodepartition, int v)
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)
static void unionfindInitSets(int *representatives, int nelems)
#define MAXAGGRLEN(nvars)
#define DEFAULT_MAXSEPACUTS
static void collectIncidentFlowCols(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *flowrow, int basecommodity)
#define MINCOMNODESFRACTION
static void invertCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int ncomrows, int *comcolids, int ncomcolids)
@ SCIP_MCFMODELTYPE_UNDIRECTED
@ SCIP_MCFMODELTYPE_DIRECTED
static NODEPAIRENTRY * nodepairqueueRemove(NODEPAIRQUEUE *nodepairqueue)
static void fixCommoditySigns(MCFDATA *mcfdata)
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_RESULT *result)
static SCIP_RETCODE createNewCommodity(SCIP *scip, MCFDATA *mcfdata)
#define DEFAULT_SEPARATEKNAPSACK
#define DEFAULT_MAXINCONSISTENCYRATIO
#define MAXFLOWCANDDENSITY
static int unionfindGetRepresentative(int *representatives, int v)
multi-commodity-flow network cut separator
SCIP_ROW *** nodeflowrows
SCIP_MCFMODELTYPE modeltype
SCIP_Real * arccapacityscales
SCIP_Real ** nodeflowscales
SCIP_Bool ** nodeflowinverted
SCIP_ROW ** arccapacityrows
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_SORTINDCOMP(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAINITSOL(x)
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXITSOL(x)
#define SCIP_DECL_SEPACOPY(x)
@ SCIP_VARTYPE_CONTINUOUS