47 #define BETTERWEIGHTFORDEMANDNODES 75 #define SEPA_NAME "mcf" 76 #define SEPA_DESC "multi-commodity-flow network cut separator" 77 #define SEPA_PRIORITY -10000 79 #define SEPA_MAXBOUNDDIST 0.0 80 #define SEPA_USESSUBSCIP FALSE 81 #define SEPA_DELAY FALSE 84 #define DEFAULT_NCLUSTERS 5 85 #define DEFAULT_MAXWEIGHTRANGE 1e+06 86 #define DEFAULT_MAXTESTDELTA 20 87 #define DEFAULT_TRYNEGSCALING FALSE 88 #define DEFAULT_FIXINTEGRALRHS TRUE 89 #define DEFAULT_DYNAMICCUTS TRUE 90 #define DEFAULT_MODELTYPE 0 91 #define DEFAULT_MAXSEPACUTS 100 92 #define DEFAULT_MAXSEPACUTSROOT 200 93 #define DEFAULT_MAXINCONSISTENCYRATIO 0.02 94 #define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5 95 #define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE 96 #define DEFAULT_SEPARATESINGLENODECUTS TRUE 97 #define DEFAULT_SEPARATEFLOWCUTSET TRUE 98 #define DEFAULT_SEPARATEKNAPSACK TRUE 101 #define BOUNDSWITCH 0.5 102 #define POSTPROCESS TRUE 105 #define MAXFRAC 0.999 107 #define MAXCOLS 2000000 108 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) 109 #define MINCOLROWRATIO 0.01 110 #define MAXCOLROWRATIO 100.0 111 #define MAXFLOWVARFLOWROWRATIO 100.0 112 #define MAXARCNODERATIO 100.0 113 #define MAXNETWORKS 4 114 #define MAXFLOWCANDDENSITY 0.1 115 #define MINCOMNODESFRACTION 0.5 118 #define MAXCAPACITYSLACK 0.1 119 #define UNCAPACITATEDARCSTRESHOLD 0.8 120 #define HASHSIZE_NODEPAIRS 500 132 #define MCFdebugMessage printf 136 #define MCFdebugMessage while(FALSE) printf 210 unsigned char* flowrowsigns;
213 unsigned char* capacityrowsigns;
222 int nemptycommodities;
224 int commoditysignssize;
245 int capacityrowssize;
272 int* representatives;
284 #define LHSPOSSIBLE 1u 285 #define RHSPOSSIBLE 2u 286 #define LHSASSIGNED 4u 287 #define RHSASSIGNED 8u 289 #define DISCARDED 32u 290 #define UNDIRECTED 64u 300 assert(mcfnetwork !=
NULL);
303 (*mcfnetwork)->nodeflowrows =
NULL;
304 (*mcfnetwork)->nodeflowscales =
NULL;
305 (*mcfnetwork)->nodeflowinverted =
NULL;
306 (*mcfnetwork)->arccapacityrows =
NULL;
307 (*mcfnetwork)->arccapacityscales =
NULL;
308 (*mcfnetwork)->arcsources =
NULL;
309 (*mcfnetwork)->arctargets =
NULL;
310 (*mcfnetwork)->colcommodity =
NULL;
311 (*mcfnetwork)->nnodes = 0;
312 (*mcfnetwork)->nuncapacitatedarcs = 0;
313 (*mcfnetwork)->narcs = 0;
314 (*mcfnetwork)->ncommodities = 0;
326 assert(mcfnetwork !=
NULL);
328 if( *mcfnetwork !=
NULL )
333 for( v = 0; v < (*mcfnetwork)->nnodes; v++ )
337 for( k = 0; k < (*mcfnetwork)->ncommodities; k++ )
339 if( (*mcfnetwork)->nodeflowrows[v][k] !=
NULL )
348 for( a = 0; a < (*mcfnetwork)->narcs; a++ )
350 if( (*mcfnetwork)->arccapacityrows[a] !=
NULL )
383 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
384 SCIP_Real* flowrowscalars = mcfdata->flowrowscalars;
385 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
386 int* flowcands = mcfdata->flowcands;
387 int nflowcands = mcfdata->nflowcands;
389 int* commoditysigns = mcfdata->commoditysigns;
391 int* rowcommodity = mcfdata->rowcommodity;
392 int* rownodeid = mcfdata->rownodeid;
393 SCIP_ROW** capacityrows = mcfdata->capacityrows;
402 int ncompcommodities;
409 assert(mcfnetwork !=
NULL);
411 assert(2 <= ncompnodes && ncompnodes <= mcfdata->
nnodes);
412 assert(1 <= ncomparcs && ncomparcs <= mcfdata->
narcs);
413 assert(ncommodities > 0);
417 for( v = 0; v < mcfdata->nnodes; v++ )
418 assert(compnodeid[v] == -1);
430 compcommodity[k] = -1;
437 for( i = 0; i < ncompnodes; i++ )
440 assert(0 <= v && v < mcfdata->nnodes);
445 ncompcommodities = 0;
446 for( i = 0; i < nflowcands; i++ )
452 assert(0 <= r && r < nrows);
455 if( rv >= 0 && compnodeid[rv] >= 0 )
458 assert(0 <= k && k < ncommodities);
459 if( compcommodity[k] == -1 )
461 compcommodity[k] = ncompcommodities;
472 mcfnetwork->
nnodes = ncompnodes;
473 mcfnetwork->
narcs = ncomparcs;
481 for( v = 0; v < mcfnetwork->
nnodes; v++ )
499 for( a = 0; a < mcfnetwork->
narcs; a++ )
509 for( i = 0; i < nflowcands; i++ )
515 assert(0 <= r && r < nrows);
518 if( rv >= 0 && compnodeid[rv] >= 0 )
524 rk = rowcommodity[
r];
525 assert(v < mcfnetwork->nnodes);
526 assert(0 <= rk && rk < ncommodities);
529 k = compcommodity[rk];
530 assert(0 <= k && k < mcfnetwork->ncommodities);
535 scale = flowrowscalars[
r];
538 if( commoditysigns[rk] == -1 )
546 for( a = 0; a < mcfnetwork->
narcs; a++ )
556 globala = comparcs[
a];
557 capacityrow = capacityrows[globala];
562 if( capacityrow !=
NULL)
565 assert(0 <= r && r < nrows);
567 assert((capacityrowsigns[r] &
INVERTED) == 0);
568 assert(mcfdata->rowarcid[r] == globala);
586 for( j = 0; j < rowlen; j++ )
593 if( comdemands[k] != 0.0 )
608 for( j = 0; j < rowlen; j++ )
613 if( k >= 0 && comdemands[k] == 0.0 )
625 if( mcfdata->arcsources[globala] >= 0 )
627 assert(mcfdata->arcsources[globala] < mcfdata->nnodes);
628 assert(0 <= compnodeid[mcfdata->arcsources[globala]] && compnodeid[mcfdata->arcsources[globala]] < mcfnetwork->
nnodes);
629 mcfnetwork->
arcsources[
a] = compnodeid[mcfdata->arcsources[globala]];
631 if( mcfdata->arctargets[globala] >= 0 )
633 assert(mcfdata->arctargets[globala] < mcfdata->nnodes);
634 assert(0 <= compnodeid[mcfdata->arctargets[globala]] && compnodeid[mcfdata->arctargets[globala]] < mcfnetwork->
nnodes);
635 mcfnetwork->
arctargets[
a] = compnodeid[mcfdata->arctargets[globala]];
640 for( c = 0; c < ncols; c++ )
650 for( i = 0; i < ncompnodes; i++ )
652 assert(0 <= compnodes[i] && compnodes[i] < mcfdata->nnodes);
653 assert(compnodeid[compnodes[i]] == i);
654 compnodeid[compnodes[i]] = -1;
667 void mcfnetworkPrint(
671 if( mcfnetwork ==
NULL )
678 for( v = 0; v < mcfnetwork->
nnodes; v++ )
697 for( a = 0; a < mcfnetwork->
narcs; a++ )
713 void printCommodities(
718 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
719 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
721 int* commoditysigns = mcfdata->commoditysigns;
723 int* rowcommodity = mcfdata->rowcommodity;
724 int* colarcid = mcfdata->colarcid;
725 int* rownodeid = mcfdata->rownodeid;
726 int nnodes = mcfdata->nnodes;
727 SCIP_ROW** capacityrows = mcfdata->capacityrows;
747 for( c = 0; c < ncols; c++ )
749 if( colcommodity[c] == k )
752 for( r = 0; r < nrows; r++ )
754 if( rowcommodity[r] == k )
757 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
762 if( rownodeid !=
NULL )
766 for( v = 0; v <
nnodes; v++ )
769 for( r = 0; r < nrows; r++ )
771 if( rownodeid[r] == v )
774 (flowrowsigns[r] &
INVERTED) != 0 ? -1 : +1);
780 assert(capacityrows !=
NULL || mcfdata->narcs == 0);
783 for( a = 0; a < mcfdata->narcs; a++ )
786 if( capacityrows[a] !=
NULL )
789 assert(0 <= r && r < nrows);
792 else if( (capacityrowsigns[r] &
RHSASSIGNED) != 0 )
800 assert(colcommodity !=
NULL || ncols == 0);
803 for( c = 0; c < ncols; c++ )
805 if( colcommodity[c] == -1 )
814 for( r = 0; r < nrows; r++ )
816 assert(rowcommodity !=
NULL);
834 if( rowscores[ind2] < rowscores[ind1] )
836 else if( rowscores[ind2] > rowscores[ind1] )
849 unsigned char* flowrowsigns;
869 flowrowsigns = mcfdata->flowrowsigns;
870 flowrowscalars = mcfdata->flowrowscalars;
871 flowrowscores = mcfdata->flowrowscores;
872 flowcands = mcfdata->flowcands;
874 assert(mcfdata->nflowcands == 0);
877 for( r = 0; r < nrows; r++ )
902 absdualsol = ABS(absdualsol);
905 flowrowscalars[
r] = 0.0;
906 flowrowscores[
r] = 0.0;
927 coef = ABS(rowvals[0]);
934 for( i = 0; i < rowlen; i++ )
940 hasposcoef = hasposcoef || (rowvals[i] > 0.0);
941 hasnegcoef = hasnegcoef || (rowvals[i] < 0.0);
971 flowrowscalars[
r] = 1.0/coef;
972 flowcands[mcfdata->nflowcands] =
r;
973 mcfdata->nflowcands++;
980 if(
SCIPisEQ(scip, flowrowscalars[r], 1.0) )
981 flowrowscores[
r] += 1000.0;
984 if( hasposcoef && hasnegcoef )
985 flowrowscores[
r] += 500.0;
992 if( ncontvars == rowlen )
993 flowrowscores[
r] += 1000.0;
994 else if( nintvars + nimplintvars == rowlen )
995 flowrowscores[
r] += 500.0;
996 else if( nbinvars == rowlen )
997 flowrowscores[
r] += 100.0;
1001 flowrowscores[
r] += 10.0*rowlen/(rowlen+10.0);
1005 flowrowscores[
r] += 50.0;
1007 assert(flowrowscores[r] > 0.0);
1010 maxdualflow =
MAX(maxdualflow, absdualsol);
1023 for( i = 0; i < mcfdata->nflowcands; i++ )
1028 assert(0 <= r && r < nrows);
1033 dualsol = ABS(dualsol);
1036 assert(maxdualflow > 0.0);
1037 flowrowscores[
r] += dualsol/maxdualflow + 1.0;
1038 assert(flowrowscores[r] > 0.0);
1043 SCIPsortInd(mcfdata->flowcands, compCands, (
void*)flowrowscores, mcfdata->nflowcands);
1045 MCFdebugMessage(
"flow conservation candidates [%d]\n", mcfdata->nflowcands);
1047 for( r = 0; r < mcfdata->nflowcands; r++ )
1050 SCIPdebugMsg(scip,
"%4d [score: %2g]: %s\n", mcfdata->flowcands[r], flowrowscores[mcfdata->flowcands[r]],
1065 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1068 int nactivecommodities = mcfdata->ncommodities - mcfdata->nemptycommodities;
1071 unsigned char* capacityrowsigns;
1080 int maxcolspercommoditylimit;
1081 int *ncolspercommodity;
1082 int *maxcolspercommodity;
1092 capacityrowsigns = mcfdata->capacityrowsigns;
1093 capacityrowscores = mcfdata->capacityrowscores;
1094 capacitycands = mcfdata->capacitycands;
1096 assert(mcfdata->ncapacitycands == 0);
1106 maxcolspercommoditylimit = 2;
1109 maxcolspercommoditylimit = 1;
1112 maxcolspercommoditylimit = 2;
1115 SCIPerrorMessage(
"invalid parameter value %d for model type\n", modeltype);
1119 maxdualcapacity = 0.0;
1120 directedcandsscore = 0.0;
1121 undirectedcandsscore = 0.0;
1122 for( r = 0; r < nrows; r++ )
1132 int nposcapacitycoefs;
1133 int nnegcapacitycoefs;
1135 int ncoveredcommodities;
1140 unsigned char rowsign;
1146 capacityrowsigns[
r] = 0;
1147 capacityrowscores[
r] = 0.0;
1166 absdualsol = ABS(absdualsol);
1175 maxcolspercommodity[
r] = 0;
1180 nposcapacitycoefs = 0;
1181 nnegcapacitycoefs = 0;
1183 ncoveredcommodities = 0;
1185 sameabsflowcoef = 0.0;
1186 maxabscapacitycoef = 0.0;
1193 for( i = 0; i < rowlen; i++ )
1200 assert(colcommodity !=
NULL);
1203 k = colcommodity[c];
1204 assert(-1 <= k && k < ncommodities);
1209 abscoef = ABS(rowvals[i]);
1210 if( sameflowcoef == 0.0 )
1211 sameflowcoef = rowvals[i];
1212 else if( !
SCIPisEQ(scip, sameflowcoef, rowvals[i]) )
1214 if( sameabsflowcoef == 0.0 )
1215 sameabsflowcoef = abscoef;
1216 else if( !
SCIPisEQ(scip, sameabsflowcoef, abscoef) )
1219 if( rowvals[i] > 0.0 )
1225 if( ncolspercommodity[k] == 0 )
1226 ncoveredcommodities++;
1227 ncolspercommodity[k]++;
1228 maxcolspercommodity[
r] =
MAX(maxcolspercommodity[r], ncolspercommodity[k]);
1230 if( ncolspercommodity[k] >= 2 )
1239 abscoef = ABS(rowvals[i]);
1240 if( abscoef > maxabscapacitycoef )
1241 maxabscapacitycoef = abscoef;
1244 if( rowvals[i] > 0.0 )
1245 nposcapacitycoefs++;
1247 nnegcapacitycoefs++;
1257 if( rowsign != 0 && nposflowcoefs + nnegflowcoefs > 0 )
1261 capacityrowsigns[
r] |= rowsign;
1262 capacitycands[mcfdata->ncapacitycands] =
r;
1263 mcfdata->ncapacitycands++;
1266 capacityrowscores[
r] = 1.0;
1270 assert(ncoveredcommodities > 0);
1272 commodityexcessratio =
1273 ABS((nposflowcoefs + nnegflowcoefs)/(
SCIP_Real)ncoveredcommodities - maxcolspercommoditylimit);
1275 capacityrowscores[
r] += 1000.0 *
MAX(0.0, 2.0 - commodityexcessratio);
1282 if( (capacityrowsigns[r] &
RHSPOSSIBLE) != 0 && nnegflowcoefs == 0 && nposcapacitycoefs == 0 && nnegcapacitycoefs > 0 )
1283 capacityrowscores[
r] += 1000.0;
1284 if( (capacityrowsigns[r] &
LHSPOSSIBLE) != 0 && nposflowcoefs == 0 && nposcapacitycoefs > 0 && nnegcapacitycoefs == 0 )
1285 capacityrowscores[
r] += 1000.0;
1294 assert(nactivecommodities + 3 > 0);
1295 capacityrowscores[
r] += 2000.0 * ncoveredcommodities/(
SCIP_Real)(nactivecommodities + 3);
1298 if(
SCIPisEQ(scip, ABS(sameflowcoef), 1.0) )
1299 capacityrowscores[r] += 500.0;
1303 capacityrowscores[
r] += 250.0;
1306 if(
SCIPisEQ(scip, sameabsflowcoef, 1.0) )
1307 capacityrowscores[r] += 100.0;
1310 if( maxabscapacitycoef > 0.0 && !
SCIPisEQ(scip, maxabscapacitycoef, 1.0) )
1311 capacityrowscores[r] += 100.0;
1314 capacityrowscores[
r] += 20.0 *
MAX(nposflowcoefs, nnegflowcoefs)/
MAX(1.0,(
SCIP_Real)(nposflowcoefs + nnegflowcoefs));
1317 capacityrowscores[
r] += 10.0 *
MAX(nposcapacitycoefs, nnegcapacitycoefs)/(
SCIP_Real)(nposcapacitycoefs+nnegcapacitycoefs+1.0);
1320 if( (capacityrowsigns[r] & RHSPOSSIBLE) != 0 && !
SCIPisNegative(scip, rowrhs) )
1321 capacityrowscores[r] += 10.0;
1325 capacityrowscores[r] += 10.0;
1327 assert(capacityrowscores[r] > 0.0);
1328 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",
1329 SCIProwGetName(row), maxcolspercommodity[r], capacityrowsigns[r], nposflowcoefs, nnegflowcoefs, nposcapacitycoefs, nnegcapacitycoefs, nbadcoefs, nactivecommodities, sameflowcoef, capacityrowscores[r]);
1332 maxdualcapacity =
MAX(maxdualcapacity, absdualsol);
1337 assert(maxcolspercommoditylimit == 2);
1338 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1339 undirectedcandsscore += capacityrowscores[
r];
1341 directedcandsscore += capacityrowscores[
r];
1346 SCIPdebugMsg(scip,
"row <%s>: rowsign = %d nposflowcoefs = %d nnegflowcoefs = %d -> discard\n",
1354 if( directedcandsscore > undirectedcandsscore )
1359 MCFdebugMessage(
"detected model type: %s (%g directed score, %g undirected score)\n",
1367 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1369 r = capacitycands[i];
1370 assert(0 <= r && r < nrows);
1371 if( (capacityrowsigns[r] &
UNDIRECTED) != 0 )
1374 if( maxcolspercommodity[r] <= maxcolspercommoditylimit )
1375 capacityrowscores[
r] -= 1000.0;
1389 for( i = 0; i < mcfdata->ncapacitycands; i++ )
1393 r = capacitycands[i];
1394 assert(0 <= r && r < nrows);
1399 dualsol = ABS(dualsol);
1402 assert(maxdualcapacity > 0.0);
1403 capacityrowscores[
r] +=
MAX(dualsol, 0.0)/maxdualcapacity;
1404 assert(capacityrowscores[r] > 0.0);
1409 SCIPsortInd(mcfdata->capacitycands, compCands, (
void*)capacityrowscores, mcfdata->ncapacitycands);
1411 MCFdebugMessage(
"capacity candidates [%d]\n", mcfdata->ncapacitycands);
1413 for( r = 0; r < mcfdata->ncapacitycands; r++ )
1415 SCIPdebugMsg(scip,
"row %4d [score: %2g]: %s\n", mcfdata->capacitycands[r],
1416 capacityrowscores[mcfdata->capacitycands[r]],
SCIProwGetName(rows[mcfdata->capacitycands[r]]));
1436 assert(mcfdata->ncommodities <= mcfdata->commoditysignssize);
1437 if( mcfdata->ncommodities == mcfdata->commoditysignssize )
1439 mcfdata->commoditysignssize =
MAX(2*mcfdata->commoditysignssize, mcfdata->ncommodities+1);
1442 assert(mcfdata->ncommodities < mcfdata->commoditysignssize);
1445 SCIPdebugMsg(scip,
"**** creating new commodity %d ****\n", mcfdata->ncommodities);
1446 mcfdata->commoditysigns[mcfdata->ncommodities] = 0;
1447 mcfdata->ncommodities++;
1462 assert(source != target );
1463 assert(0 <= source && source < mcfdata->
nnodes);
1464 assert(0 <= target && target < mcfdata->nnodes);
1465 assert(newarcid !=
NULL);
1467 *newarcid = mcfdata->narcs;
1470 assert(mcfdata->narcs <= mcfdata->arcarraysize);
1471 if( mcfdata->narcs == mcfdata->arcarraysize )
1473 mcfdata->arcarraysize =
MAX(2*mcfdata->arcarraysize, mcfdata->narcs+1);
1479 assert(mcfdata->narcs < mcfdata->arcarraysize);
1482 if( mcfdata->capacityrowssize < mcfdata->arcarraysize )
1484 mcfdata->capacityrowssize = mcfdata->arcarraysize;
1487 assert(mcfdata->narcs < mcfdata->capacityrowssize);
1490 SCIPdebugMsg(scip,
"**** creating new arc %d: %d -> %d ****\n", mcfdata->narcs, source, target);
1492 mcfdata->arcsources[*newarcid] = source;
1493 mcfdata->arctargets[*newarcid] = target;
1494 mcfdata->nextoutarcs[*newarcid] = mcfdata->firstoutarcs[source];
1495 mcfdata->firstoutarcs[source] = *newarcid;
1496 mcfdata->nextinarcs[*newarcid] = mcfdata->firstinarcs[target];
1497 mcfdata->firstinarcs[target] = *newarcid;
1498 mcfdata->capacityrows[*newarcid] =
NULL;
1511 unsigned char rowsign,
1516 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1517 SCIP_Bool* plusflow = mcfdata->plusflow;
1518 SCIP_Bool* minusflow = mcfdata->minusflow;
1520 int* commoditysigns = mcfdata->commoditysigns;
1522 int* rowcommodity = mcfdata->rowcommodity;
1523 int* newcols = mcfdata->newcols;
1534 assert(comcolids !=
NULL);
1535 assert(ncomcolids !=
NULL);
1544 invertrow = ((rowsign &
INVERTED) != 0);
1547 assert(rowcommodity[r] == -1);
1548 assert((flowrowsigns[r] | rowsign) == flowrowsigns[r]);
1550 assert(rowsign != 0);
1556 commoditysigns[k] = +1;
1585 else if( rowlhs > 0.0 )
1602 flowrowsigns[
r] |= rowsign;
1604 SCIPdebugMsg(scip,
"adding flow row %d <%s> with sign %+d%s to commodity %d [score:%g]\n",
1606 k, mcfdata->flowrowscores[r]);
1610 rowcommodity[
r] = k;
1614 for( i = 0; i < rowlen; i++ )
1623 if( colcommodity[c] == -1 )
1625 assert(!plusflow[c]);
1626 assert(!minusflow[c]);
1628 colcommodity[c] = k;
1629 newcols[mcfdata->nnewcols] = c;
1630 mcfdata->nnewcols++;
1631 comcolids[*ncomcolids] = c;
1634 assert(colcommodity[c] == k);
1637 val = rowscale * rowvals[i];
1640 assert(!plusflow[c]);
1645 assert(!minusflow[c]);
1646 minusflow[c] =
TRUE;
1663 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1664 SCIP_Bool* plusflow = mcfdata->plusflow;
1665 SCIP_Bool* minusflow = mcfdata->minusflow;
1669 assert(mcfdata->commoditysigns[k] == 0);
1670 assert(comrows !=
NULL || ncomrows == 0);
1671 assert(comcolids !=
NULL);
1674 for( i = 0; i < ncomrows; i++ )
1678 unsigned char rowsign;
1680 assert(comrows !=
NULL);
1682 assert( row !=
NULL );
1685 assert(mcfdata->rowcommodity[r] == k);
1689 rowsign = flowrowsigns[
r];
1701 for( i = 0; i < ncomcolids; i++ )
1708 assert(mcfdata->colcommodity[c] == k);
1711 plusflow[c] = minusflow[c];
1728 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1729 SCIP_Bool* plusflow = mcfdata->plusflow;
1730 SCIP_Bool* minusflow = mcfdata->minusflow;
1733 int* rowcommodity = mcfdata->rowcommodity;
1737 assert(0 <= k && k < ncommodities);
1739 assert( ndelflowrows !=
NULL );
1740 assert( ndelflowvars !=
NULL );
1742 SCIPdebugMsg(scip,
"deleting commodity %d (%d total commodities) with %d flow rows\n", k, ncommodities, nrows);
1747 for( n = 0; n < nrows; n++ )
1758 assert(rowcommodity[r] == k);
1767 rowcommodity[
r] = -1;
1770 for( i = 0; i < rowlen; i++ )
1778 assert(colcommodity[c] == k || colcommodity[c] == -1);
1779 if(colcommodity[c] == k)
1781 colcommodity[c] = -1;
1784 plusflow[c] =
FALSE;
1785 minusflow[c] =
FALSE;
1794 if( k == ncommodities-1 )
1795 mcfdata->ncommodities--;
1797 mcfdata->nemptycommodities++;
1807 unsigned char* rowsign,
1811 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
1812 SCIP_Bool* plusflow = mcfdata->plusflow;
1813 SCIP_Bool* minusflow = mcfdata->minusflow;
1815 int* rowcommodity = mcfdata->rowcommodity;
1816 int* commoditysigns = mcfdata->commoditysigns;
1821 unsigned char flowrowsign;
1822 unsigned char invflowrowsign;
1826 assert(invertcommodity !=
NULL);
1829 *invertcommodity =
FALSE;
1835 if( rowcommodity[r] != -1 )
1839 flowrowsign = flowrowsigns[
r];
1845 invflowrowsign = flowrowsign;
1851 for( j = 0; j < rowlen && (flowrowsign != 0 || invflowrowsign != 0); j++ )
1859 if( colcommodity[rowc] == k )
1862 if( plusflow[rowc] )
1865 if( rowvals[j] > 0.0 )
1876 if( minusflow[rowc] )
1879 if( rowvals[j] > 0.0 )
1891 else if( colcommodity[rowc] != -1 )
1899 if( flowrowsign != 0 )
1902 *rowsign = flowrowsign;
1903 *invertcommodity =
FALSE;
1905 else if( invflowrowsign != 0 )
1911 if( commoditysigns ==
NULL || commoditysigns[k] == 0 )
1914 *rowsign = invflowrowsign;
1915 *invertcommodity =
TRUE;
1920 *rowsign = (invflowrowsign |
INVERTED);
1921 *invertcommodity =
FALSE;
1938 unsigned char* nextrowsign,
1942 SCIP_Real* flowrowscores = mcfdata->flowrowscores;
1943 SCIP_Bool* plusflow = mcfdata->plusflow;
1944 SCIP_Bool* minusflow = mcfdata->minusflow;
1945 int* newcols = mcfdata->newcols;
1951 assert(nextrow !=
NULL);
1952 assert(nextrowsign !=
NULL);
1956 *nextinvertcommodity =
FALSE;
1961 assert(cols !=
NULL);
1964 while( mcfdata->nnewcols > 0 )
1970 unsigned char bestrowsign;
1977 c = newcols[mcfdata->nnewcols-1];
1978 mcfdata->nnewcols--;
1982 assert(plusflow[c] || minusflow[c]);
1983 if( plusflow[c] && minusflow[c] )
1989 bestinvertcommodity =
FALSE;
1994 for( i = 0; i < collen; i++ )
1997 unsigned char flowrowsign;
2003 getFlowrowFit(scip, mcfdata, row, k, &flowrowsign, &invertcommodity);
2006 if( flowrowsign != 0 )
2013 score = flowrowscores[
r];
2014 assert(score > 0.0);
2020 if( (flowrowsign &
INVERTED) != 0 )
2023 if( score > bestscore )
2026 bestrowsign = flowrowsign;
2027 bestinvertcommodity = invertcommodity;
2037 if( bestrow !=
NULL )
2039 assert(bestscore > 0.0);
2040 assert(bestrowsign != 0);
2042 *nextrowsign = bestrowsign;
2043 *nextinvertcommodity = bestinvertcommodity;
2058 int* flowcands = mcfdata->flowcands;
2085 assert(failed !=
NULL);
2094 plusflow = mcfdata->plusflow;
2095 minusflow = mcfdata->minusflow;
2096 colcommodity = mcfdata->colcommodity;
2097 rowcommodity = mcfdata->rowcommodity;
2109 for( c = 0; c < ncols; c++ )
2110 colcommodity[c] = -1;
2111 for( r = 0; r < nrows; r++ )
2112 rowcommodity[r] = -1;
2114 assert(flowcands !=
NULL || mcfdata->nflowcands == 0);
2125 for( i = 0; i < mcfdata->nflowcands; i++ )
2128 unsigned char newrowsign;
2132 assert(flowcands !=
NULL);
2134 assert(0 <= r && r < nrows);
2138 getFlowrowFit(scip, mcfdata, newrow, mcfdata->ncommodities, &newrowsign, &newinvertcommodity);
2139 if( newrowsign == 0 )
2141 assert(!newinvertcommodity);
2142 assert((newrowsign &
INVERTED) == 0);
2145 SCIPdebugMsg(scip,
" -------------------start new commodity %d--------------------- \n", mcfdata->ncommodities );
2154 if( newinvertcommodity )
2155 invertCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, comcolids, ncomcolids);
2160 comrows[
nnodes] = newrow;
2165 getNextFlowrow(scip, mcfdata, &newrow, &newrowsign, &newinvertcommodity);
2167 while( newrow !=
NULL );
2169 ncomnodes[mcfdata->ncommodities-1] =
nnodes;
2170 maxnnodes =
MAX(maxnnodes, nnodes);
2171 nflowvars += ncomcolids;
2172 SCIPdebugMsg(scip,
" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n", mcfdata->ncommodities-1, nnodes, maxnnodes);
2180 deleteCommodity(scip, mcfdata, mcfdata->ncommodities-1, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2181 nflowrows -= ndelflowrows;
2182 nflowvars -= ndelflowvars;
2183 assert(nflowvars >= 0);
2184 assert(nflowrows >= 0);
2188 for( k = 0; k < mcfdata->ncommodities; k++ )
2200 for( i = 0; i < mcfdata->nflowcands; i++ )
2202 assert(flowcands !=
NULL);
2204 if( rowcommodity[r] == k )
2209 if( nnodes == ncomnodes[k] )
2214 assert(nnodes == ncomnodes[k]);
2215 deleteCommodity(scip, mcfdata, k, comrows, nnodes, &ndelflowrows, &ndelflowvars);
2216 nflowrows -= ndelflowrows;
2217 nflowvars -= ndelflowvars;
2218 assert(nflowvars >= 0);
2219 assert(nflowrows >= 0);
2228 MCFdebugMessage(
"identified %d commodities (%d empty) with a maximum of %d nodes and %d flowrows, %d flowvars \n",
2229 mcfdata->ncommodities, mcfdata->nemptycommodities, maxnnodes, nflowrows, nflowvars);
2231 assert(nflowvars >= 0);
2232 assert(nflowrows >= 0);
2250 unsigned char* capacityrowsigns = mcfdata->capacityrowsigns;
2253 unsigned char* flowrowsigns = mcfdata->capacityrowsigns;
2254 int* rowcommodity = mcfdata->rowcommodity;
2270 SCIP_Real* capacityrowscores = mcfdata->capacityrowscores;
2272 int *capacitycands = mcfdata->capacitycands;
2273 int ncapacitycands = mcfdata->ncapacitycands;
2275 assert(mcfdata->narcs == 0);
2276 assert(capacitycands !=
NULL || ncapacitycands == 0);
2285 colarcid = mcfdata->colarcid;
2286 rowarcid = mcfdata->rowarcid;
2289 for( c = 0; c < ncols; c++ )
2291 for( r = 0; r < nrows; r++ )
2295 for( i = 0; i < ncapacitycands; i++ )
2300 int nassignedflowvars;
2301 int nunassignedflowvars;
2304 assert(capacitycands !=
NULL);
2305 r = capacitycands[i];
2306 assert(0 <= r && r < nrows );
2307 capacityrow = rows[
r];
2309 assert(capacityrowsigns !=
NULL);
2310 assert(capacityrowscores !=
NULL);
2311 assert(rowcommodity !=
NULL);
2312 assert(flowrowsigns !=
NULL);
2316 assert((capacityrowsigns[r] &
DISCARDED) == 0);
2317 assert(capacityrowscores[r] > 0.0);
2321 assert(rowarcid[r] == -1);
2324 assert( rowcommodity[r] == -1 );
2330 nassignedflowvars = 0;
2331 nunassignedflowvars = 0;
2332 for( k = 0; k < rowlen; k++ )
2335 assert(0 <= c && c < ncols);
2336 assert(colcommodity !=
NULL);
2338 assert(-1 <= colcommodity[c] && colcommodity[c] < mcfdata->ncommodities);
2339 assert(-1 <= colarcid[c] && colarcid[c] < mcfdata->narcs);
2342 if( colcommodity[c] == -1 )
2346 if( colarcid[c] >= 0 )
2347 nassignedflowvars++;
2349 nunassignedflowvars++;
2356 if( nunassignedflowvars == 0 || nassignedflowvars >= nunassignedflowvars * 2 )
2358 SCIPdebugMsg(scip,
"discarding capacity candidate row %d <%s> [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2359 r,
SCIProwGetName(capacityrow), mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2365 assert(mcfdata->narcs <= mcfdata->capacityrowssize);
2366 if( mcfdata->narcs == mcfdata->capacityrowssize )
2368 mcfdata->capacityrowssize =
MAX(2*mcfdata->capacityrowssize, mcfdata->narcs+1);
2371 assert(mcfdata->narcs < mcfdata->capacityrowssize);
2372 assert(mcfdata->narcs < nrows);
2374 mcfdata->capacityrows[mcfdata->narcs] = capacityrow;
2377 assert(0 <= r && r < nrows);
2378 rowarcid[
r] = mcfdata->narcs;
2389 SCIPdebugMsg(scip,
"assigning capacity row %d <%s> with sign %+d to arc %d [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
2391 mcfdata->capacityrowscores[r], nassignedflowvars, nunassignedflowvars);
2394 for( k = 0; k < rowlen; k++ )
2397 assert(0 <= rowc && rowc < ncols);
2398 assert(colcommodity !=
NULL);
2403 if( colcommodity[rowc] >= 0 && colarcid[rowc] == -1 )
2404 colarcid[rowc] = mcfdata->narcs;
2424 int* colarcid = mcfdata->colarcid;
2425 int* newcols = mcfdata->newcols;
2426 SCIP_ROW** capacityrows = mcfdata->capacityrows;
2427 SCIP_Bool* colisincident = mcfdata->colisincident;
2436 assert(!colisincident[i]);
2442 mcfdata->nnewcols = 0;
2444 for( i = 0; i < rowlen; i++ )
2456 arcid = colarcid[c];
2459 assert(arcid < mcfdata->
narcs);
2462 assert(capacityrows[arcid] !=
NULL);
2466 for( j = 0; j < capacityrowlen; j++ )
2474 if( colcommodity[caprowc] == -1 )
2476 assert(colarcid[caprowc] == -1);
2479 assert(colarcid[caprowc] <= arcid);
2482 if( colcommodity[caprowc] == basecommodity )
2486 if( !colisincident[caprowc] )
2488 assert(mcfdata->nnewcols < SCIPgetNLPCols(scip));
2489 colisincident[caprowc] =
TRUE;
2490 newcols[mcfdata->nnewcols] = caprowc;
2491 mcfdata->nnewcols++;
2505 int* basearcpattern,
2514 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2515 int* commoditysigns = mcfdata->commoditysigns;
2516 int narcs = mcfdata->narcs;
2517 int* rowcommodity = mcfdata->rowcommodity;
2518 int* colarcid = mcfdata->colarcid;
2519 int* arcpattern = mcfdata->zeroarcarray;
2532 int* overlappingarcs;
2533 int noverlappingarcs;
2538 *invertcommodity =
FALSE;
2541 for( i = 0; i <
narcs; i++ )
2542 assert(arcpattern[i] == 0);
2551 rowcom = rowcommodity[
r];
2553 rowcomsign = commoditysigns[rowcom];
2554 assert(-1 <= rowcomsign && rowcomsign <= +1);
2559 incompatible =
FALSE;
2560 noverlappingarcs = 0;
2564 for( i = 0; i < rowlen; i++ )
2574 valsign = (rowvals[i] > 0.0 ? +1 : -1);
2577 if( (flowrowsigns[r] &
INVERTED) != 0 )
2580 arcid = colarcid[c];
2589 assert(arcid < narcs);
2592 if( basearcpattern[arcid] != 0 )
2599 if( ( valsign * basearcpattern[arcid] ) > 0 )
2604 if( rowcomsign == 0 )
2607 rowcomsign = validcomsign;
2609 else if( rowcomsign != validcomsign )
2612 incompatible =
TRUE;
2623 if( arcpattern[arcid] == 0 )
2625 overlappingarcs[noverlappingarcs] = arcid;
2628 arcpattern[arcid] += valsign;
2634 for( i = 0; i < noverlappingarcs; i++ )
2640 arcid = overlappingarcs[i];
2641 assert(0 <= arcid && arcid < narcs);
2644 basenum = ABS(basearcpattern[arcid]);
2645 arcnum = ABS(arcpattern[arcid]);
2646 assert(basenum != 0.0);
2647 assert(arcnum != 0.0);
2649 if( basenum > arcnum )
2650 overlap += arcnum/basenum;
2652 overlap += basenum/arcnum;
2654 arcpattern[arcid] = 0;
2658 if( !incompatible && overlap > 0.0 )
2661 int rowarcs = rowlen - nposuncap - nneguncap;
2662 int baserowarcs = baserowlen - basenposuncap - basenneguncap;
2665 assert(overlap <= (
SCIP_Real) baserowlen);
2666 assert(noverlappingarcs >= 1);
2668 *invertcommodity = (rowcomsign == -1);
2672 if( noverlappingarcs >= 2 )
2675 assert(rowarcs >= 0 && baserowarcs >= 0 );
2678 *score = overlap - (rowarcs + baserowarcs - 2.0 * overlap)/(2.0 * ncols + 1.0);
2680 *score = overlap - (rowarcs + baserowarcs - 4.0 * overlap)/(2.0 * ncols + 1.0);
2683 if(*invertcommodity)
2684 *score += 1.0 - (ABS(nneguncap - basenposuncap) + ABS(nposuncap - basenneguncap))/(2.0 * ncols + 1.0);
2686 *score += 1.0 - (ABS(nposuncap - basenposuncap) + ABS(nneguncap - basenneguncap))/(2.0 * ncols + 1.0);
2688 *score =
MAX(*score, 1e-6);
2691 SCIPdebugMsg(scip,
" -> node similarity: row <%s>: incompatible=%u overlap=%g rowlen=%d baserowlen=%d score=%g\n",
2692 SCIProwGetName(row), incompatible, overlap, rowlen, baserowlen, *score);
2707 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
2709 int* commoditysigns = mcfdata->commoditysigns;
2710 int narcs = mcfdata->narcs;
2711 int* flowcands = mcfdata->flowcands;
2712 int nflowcands = mcfdata->nflowcands;
2713 int* rowcommodity = mcfdata->rowcommodity;
2714 int* colarcid = mcfdata->colarcid;
2715 int* newcols = mcfdata->newcols;
2736 assert(mcfdata->nnodes == 0);
2748 rownodeid = mcfdata->rownodeid;
2749 colisincident = mcfdata->colisincident;
2759 for( r = 0; r < nrows; r++ )
2761 for( c = 0; c < ncols; c++ )
2762 colisincident[c] =
FALSE;
2764 assert(flowcands !=
NULL || nflowcands == 0);
2767 for( n = 0; n < nflowcands; n++ )
2776 assert(flowcands !=
NULL);
2778 assert(0 <= r && r < nrows);
2779 assert(rowcommodity !=
NULL);
2782 basecommodity = rowcommodity[
r];
2783 if( basecommodity == -1 )
2786 assert(mcfdata->rowarcid[r] == -1);
2789 if( rownodeid[r] >= 0 )
2793 SCIPdebugMsg(scip,
"assigning row %d <%s> of commodity %d to node %d [score: %g]\n",
2794 r,
SCIProwGetName(rows[r]), basecommodity, mcfdata->nnodes, mcfdata->flowrowscores[r]);
2795 rownodeid[
r] = mcfdata->nnodes;
2803 if(ncommodities == 1)
2815 assert(commoditysigns !=
NULL);
2821 if( (flowrowsigns[r] &
INVERTED) != 0 )
2823 if( commoditysigns[basecommodity] == -1 )
2826 for( i = 0; i < rowlen; i++ )
2831 assert(0 <= c && c < ncols);
2832 arcid = colarcid[c];
2837 arcpattern[arcid]++;
2839 arcpattern[arcid]--;
2854 bestflowrows[i] =
NULL;
2855 bestscores[i] = 0.0;
2856 bestinverted[i] =
FALSE;
2868 for( i = 0; i < mcfdata->nnewcols; i++ )
2874 assert(newcols !=
NULL);
2876 assert(0 <= c && c < ncols);
2877 assert(mcfdata->colcommodity[c] >= 0);
2878 assert(mcfdata->colcommodity[c] != basecommodity);
2881 assert(colisincident[c]);
2882 colisincident[c] =
FALSE;
2888 for( j = 0; j < collen; j++ )
2896 assert(0 <= colr && colr < nrows);
2899 if( rowprocessed[colr] )
2901 rowprocessed[colr] =
TRUE;
2904 rowcom = rowcommodity[colr];
2905 assert(rowcom != basecommodity);
2909 assert(rowcom == mcfdata->colcommodity[c]);
2910 assert((flowrowsigns[colr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2911 assert(mcfdata->rowarcid[colr] == -1);
2914 if( rownodeid[colr] >= 0 )
2919 nposuncap, nneguncap, colrows[j], &score, &invertcommodity) );
2922 if( score > bestscores[rowcom] )
2924 bestflowrows[rowcom] = colrows[j];
2925 bestscores[rowcom] = score;
2926 bestinverted[rowcom] = invertcommodity;
2930 assert(bestflowrows[basecommodity] ==
NULL);
2937 if( bestflowrows[i] ==
NULL )
2941 assert(0 <= comr && comr < nrows);
2942 assert(rowcommodity[comr] == i);
2943 assert((flowrowsigns[comr] & (
LHSASSIGNED | RHSASSIGNED)) != 0);
2944 assert(rownodeid[comr] == -1);
2945 assert(mcfdata->nnodes >= 1);
2947 SCIPdebugMsg(scip,
" -> assigning row %d <%s> of commodity %d to node %d [invert:%u]\n",
2948 comr,
SCIProwGetName(rows[comr]), i, mcfdata->nnodes-1, bestinverted[i]);
2949 rownodeid[comr] = mcfdata->nnodes-1;
2952 if( bestinverted[i] )
2954 assert(commoditysigns[i] != +1);
2955 commoditysigns[i] = -1;
2959 assert(commoditysigns[i] != -1);
2960 commoditysigns[i] = +1;
2982 int* commoditysigns = mcfdata->commoditysigns;
2985 for( k = 0; k < mcfdata->ncommodities; k++ )
2987 if( commoditysigns[k] == 0 )
2988 commoditysigns[k] = +1;
3003 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3004 int* commoditysigns = mcfdata->commoditysigns;
3005 int* rowcommodity = mcfdata->rowcommodity;
3006 int* rownodeid = mcfdata->rownodeid;
3007 int* colsources = mcfdata->colsources;
3008 int* coltargets = mcfdata->coltargets;
3016 assert(sourcenode !=
NULL);
3017 assert(targetnode !=
NULL);
3018 assert(colsources !=
NULL);
3019 assert(coltargets !=
NULL);
3025 if( colsources[c] >= -1 )
3027 assert(coltargets[c] >= -1);
3028 *sourcenode = colsources[c];
3029 *targetnode = coltargets[c];
3040 for( i = 0; i < collen; i++ )
3047 if( rownodeid[r] >= 0 )
3054 k = rowcommodity[
r];
3055 assert(0 <= v && v < mcfdata->
nnodes);
3063 if( (flowrowsigns[r] &
INVERTED) != 0 )
3065 if( commoditysigns[k] == -1 )
3069 if( ( scale * colvals[i] ) > 0.0 )
3071 assert(*sourcenode == -1);
3073 if( *targetnode >= 0 )
3078 assert(*targetnode == -1);
3080 if( *sourcenode >= 0 )
3087 colsources[c] = *sourcenode;
3088 coltargets[c] = *targetnode;
3099 int* flowcands = mcfdata->flowcands;
3100 int nflowcands = mcfdata->nflowcands;
3102 unsigned char* flowrowsigns = mcfdata->flowrowsigns;
3104 int* rowcommodity = mcfdata->rowcommodity;
3106 int* rownodeid = mcfdata->rownodeid;
3107 int* colarcid = mcfdata->colarcid;
3108 int nnodes = mcfdata->nnodes;
3116 int* sortedflowcands;
3117 int* sortedflowcandnodeid;
3130 assert(mcfdata->nemptycommodities == 0);
3131 assert(ncommodities >= 0);
3135 if( ncommodities == 0 || nflowcands == 0 || nnodes == 0 )
3144 assert(rows !=
NULL);
3145 assert(cols !=
NULL || ncols == 0);
3156 for( n = 0; n < nflowcands; n++ )
3158 sortedflowcands[n] = flowcands[n];
3159 sortedflowcandnodeid[n] = rownodeid[flowcands[n]];
3163 SCIPsortIntInt(sortedflowcandnodeid, sortedflowcands, nflowcands);
3164 assert(sortedflowcandnodeid[0] <= 0);
3165 assert(sortedflowcandnodeid[nflowcands-1] == nnodes-1);
3168 for( v = 0; v <
nnodes; v++ )
3184 for( n = 0; n < nflowcands; n++ )
3186 if( sortedflowcandnodeid[n] >= 0 )
3188 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3189 assert(rowcommodity[sortedflowcands[n]] == -1);
3191 assert(n < nflowcands);
3192 assert(sortedflowcandnodeid[n] == 0);
3197 for( v = 0; n < nflowcands; v++ )
3202 assert(0 <= sortedflowcands[n] && sortedflowcands[n] <
SCIPgetNLPRows(scip));
3203 assert(rowcommodity[sortedflowcands[n]] >= 0);
3204 assert(rownodeid[sortedflowcands[n]] == sortedflowcandnodeid[n]);
3205 assert(sortedflowcandnodeid[n] == v);
3206 assert(nadjnodes == 0);
3207 assert(ninccols == 0);
3212 for( ; n < nflowcands && sortedflowcandnodeid[n] == v; n++ )
3219 r = sortedflowcands[n];
3221 assert(mcfdata->rowarcid[r] == -1);
3226 for( i = 0; i < rowlen; i++ )
3237 arcid = colarcid[c];
3238 assert(-2 <= arcid && arcid < mcfdata->
narcs);
3239 assert(rowcommodity[r] == colcommodity[c]);
3249 else if( arcid == -1 )
3259 assert(-1 <= s && s < nnodes);
3260 assert(-1 <= t && t < nnodes);
3261 assert(s == v || t == v);
3272 if( s < 0 || t < 0 )
3280 assert(ninccols < ncols);
3281 inccols[ninccols] = c;
3297 if( sourcecount[u] + targetcount[u] == 1 )
3299 assert(nadjnodes < nnodes);
3300 adjnodes[nadjnodes] = u;
3308 for( l = 0; l < nadjnodes; l++ )
3313 assert(0 <= u && u < nnodes);
3314 assert(sourcecount[u] > 0 || targetcount[u] > 0);
3316 assert(ninccols >= 0);
3319 if( sourcecount[u] >= arcsthreshold )
3326 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, u, v);
3329 for( m = 0; m < ninccols; m++ )
3336 assert(0 <= c && c < ncols);
3338 assert(cols !=
NULL);
3340 assert(s == v || t == v);
3345 colarcid[c] = arcid;
3348 inccols[m] = inccols[ninccols-1];
3356 if( targetcount[u] >= arcsthreshold )
3363 SCIPdebugMsg(scip,
" -> new arc: <%i> = (%i,%i)\n", arcid, v, u);
3366 for( m = 0; m < ninccols; m++ )
3373 assert(0 <= c && c < ncols);
3375 assert(cols !=
NULL);
3377 assert(s == v || t == v);
3382 colarcid[c] = arcid;
3385 inccols[m] = inccols[ninccols-1];
3394 for( l = 0; l < nadjnodes; l++ )
3402 for( l = 0; l < ninccols; l++ )
3404 assert(colarcid[inccols[l]] == -1);
3405 colarcid[inccols[l]] = -2;
3409 assert(n == nflowcands);
3410 assert(v == nnodes);
3414 for( n = 0; n < ncols; n++ )
3415 assert(colarcid[n] >= -1);
3426 MCFdebugMessage(
"network after finding uncapacitated arcs has %d nodes, %d arcs, and %d commodities\n",
3427 mcfdata->nnodes, mcfdata->narcs, mcfdata->ncommodities);
3439 int* flowcands = mcfdata->flowcands;
3440 int nflowcands = mcfdata->nflowcands;
3442 int* rowcommodity = mcfdata->rowcommodity;
3443 int* colarcid = mcfdata->colarcid;
3444 int* rowarcid = mcfdata->rowarcid;
3445 int* rownodeid = mcfdata->rownodeid;
3447 int* commoditysigns = mcfdata->commoditysigns;
3448 int narcs = mcfdata->narcs;
3449 int nnodes = mcfdata->nnodes;
3450 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3462 int nnodesthreshold;
3463 int newncommodities;
3469 MCFdebugMessage(
"network before cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3477 permsize =
MAX(permsize, narcs);
3478 permsize =
MAX(permsize, nnodes);
3488 assert(flowcands !=
NULL || nflowcands == 0);
3491 for( i = 0; i < nflowcands; i++ )
3495 assert(flowcands !=
NULL);
3497 assert(0 <= r && r < nrows);
3498 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3499 if( rowcommodity[r] >= 0 )
3501 assert(rowcommodity[r] < ncommodities);
3502 nnodespercom[rowcommodity[
r]]++;
3506 assert(capacityrows !=
NULL || narcs == 0);
3509 for( a = 0; a <
narcs; a++ )
3516 assert(capacityrows !=
NULL);
3518 assert(0 <= r && r < nrows);
3519 assert(rowarcid[r] == a);
3525 for( j = 0; j < rowlen; j++ )
3530 assert(0 <= c && c < ncols);
3531 if( colcommodity[c] >= 0 && colarcid[c] == a )
3533 assert(colcommodity[c] < ncommodities);
3534 arcisincom[colcommodity[c]] =
TRUE;
3549 maxnnodes =
MAX(maxnnodes, nnodespercom[k]);
3557 SCIPdebugMsg(scip,
" -> node threshold: %d\n", nnodesthreshold);
3560 newncommodities = 0;
3563 SCIPdebugMsg(scip,
" -> commodity %d: %d nodes, %d arcs\n", k, nnodespercom[k], narcspercom[k]);
3566 if( nnodespercom[k] >= nnodesthreshold && narcspercom[k] >= 1 )
3568 assert(newncommodities <= k);
3569 perm[k] = newncommodities;
3570 commoditysigns[newncommodities] = commoditysigns[k];
3577 if( newncommodities < ncommodities )
3586 SCIPdebugMsg(scip,
" -> discarding %d of %d commodities\n", ncommodities - newncommodities, ncommodities);
3594 for( c = 0; c < ncols; c++ )
3596 if( colcommodity[c] >= 0 )
3598 assert(-1 <= colarcid[c] && colarcid[c] < narcs);
3599 assert(colcommodity[c] < mcfdata->ncommodities);
3600 colcommodity[c] = perm[colcommodity[c]];
3601 assert(colcommodity[c] < newncommodities);
3602 if( colcommodity[c] == -1 )
3607 else if( colarcid[c] >= 0 )
3608 arcisused[colarcid[c]] =
TRUE;
3611 for( i = 0; i < nflowcands; i++ )
3615 assert(flowcands !=
NULL);
3617 assert(0 <= r && r < nrows);
3618 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3619 if( rowcommodity[r] >= 0 )
3621 assert(0 <= rownodeid[r] && rownodeid[r] < nnodes);
3622 assert(rowcommodity[r] < mcfdata->ncommodities);
3623 rowcommodity[
r] = perm[rowcommodity[
r]];
3624 assert(rowcommodity[r] < newncommodities);
3625 if( rowcommodity[r] == -1 )
3631 nodeisused[rownodeid[
r]] =
TRUE;
3635 mcfdata->ncommodities = newncommodities;
3636 ncommodities = newncommodities;
3640 for( a = 0; a <
narcs; a++ )
3644 assert(capacityrows !=
NULL);
3648 assert(newnarcs <= a);
3650 capacityrows[newnarcs] = capacityrows[
a];
3659 assert(0 <= r && r < nrows);
3660 assert(rowarcid[r] == a);
3661 rowarcid[
r] = perm[
a];
3665 if( newnarcs < narcs )
3667 SCIPdebugMsg(scip,
" -> discarding %d of %d arcs\n", narcs - newnarcs, narcs);
3669 for( c = 0; c < ncols; c++ )
3671 if( colarcid[c] >= 0 )
3673 colarcid[c] = perm[colarcid[c]];
3674 assert(colarcid[c] >= 0);
3677 mcfdata->narcs = newnarcs;
3681 for( a = 0; a <
narcs; a++ )
3684 assert(capacityrows !=
NULL);
3686 assert(0 <= r && r < nrows);
3687 assert(rowarcid[r] == a);
3693 for( v = 0; v <
nnodes; v++ )
3697 assert(newnnodes <= v);
3698 perm[v] = newnnodes;
3706 if( newnnodes < nnodes )
3708 SCIPdebugMsg(scip,
" -> discarding %d of %d nodes\n", nnodes - newnnodes, nnodes);
3710 for( i = 0; i < nflowcands; i++ )
3714 assert(flowcands !=
NULL);
3716 assert(0 <= r && r < nrows);
3717 assert((rownodeid[r] >= 0) == (rowcommodity[r] >= 0));
3718 if( rowcommodity[r] >= 0 )
3720 assert(rowcommodity[r] < ncommodities);
3721 rownodeid[
r] = perm[rownodeid[
r]];
3722 assert(rownodeid[r] >= 0);
3725 mcfdata->nnodes = newnnodes;
3737 mcfdata->nemptycommodities = 0;
3745 MCFdebugMessage(
"network after cleanup has %d nodes, %d arcs, and %d commodities\n", nnodes, narcs, ncommodities);
3759 int* colarcid = mcfdata->colarcid;
3761 int narcs = mcfdata->narcs;
3762 int nnodes = mcfdata->nnodes;
3764 SCIP_ROW** capacityrows = mcfdata->capacityrows;
3766 SCIP_Real maxinconsistencyratio = sepadata->maxinconsistencyratio;
3767 SCIP_Real maxarcinconsistencyratio = sepadata->maxarcinconsistencyratio;
3779 int *flowvarspercom;
3792 assert(effortlevel !=
NULL);
3806 arcsources = mcfdata->arcsources;
3807 arctargets = mcfdata->arctargets;
3808 colsources = mcfdata->colsources;
3809 coltargets = mcfdata->coltargets;
3810 firstoutarcs = mcfdata->firstoutarcs;
3811 firstinarcs = mcfdata->firstinarcs;
3812 nextoutarcs = mcfdata->nextoutarcs;
3813 nextinarcs = mcfdata->nextinarcs;
3815 mcfdata->arcarraysize =
narcs;
3818 for( c = 0; c < ncols; c++ )
3825 for( v = 0; v <
nnodes; v++ )
3827 firstoutarcs[v] = -1;
3828 firstinarcs[v] = -1;
3830 for( a = 0; a <
narcs; a++ )
3832 nextoutarcs[
a] = -1;
3846 mcfdata->ninconsistencies = 0.0;
3847 maxninconsistencies = maxinconsistencyratio * (
SCIP_Real)narcs;
3850 for( a = 0; a <
narcs; a++ )
3872 assert(mcfdata->rowarcid[r] == a);
3875 for( i = 0; i <
nnodes; i++ )
3877 assert(sourcenodecnt[i] == 0);
3878 assert(targetnodecnt[i] == 0);
3889 for( i = 0; i < rowlen; i++ )
3893 if( colarcid[c] >= 0 )
3895 int k = colcommodity[c];
3896 assert (0 <= k && k < ncommodities);
3897 flowvarspercom[k]++;
3898 if( !comtouched[k] )
3901 comtouched[k] =
TRUE;
3907 if( ntouchedcoms == 0 )
3909 capacityrows[
a] =
NULL;
3917 totalsourcecnt = 0.0;
3918 totaltargetcnt = 0.0;
3920 for( i = 0; i < rowlen; i++ )
3924 if( colarcid[c] >= 0 )
3926 int k = colcommodity[c];
3931 assert (0 <= k && k < ncommodities);
3932 assert (comtouched[k]);
3933 assert (flowvarspercom[k] >= 1);
3939 weight = 1.0/flowvarspercom[k];
3942 if( sourcenodecnt[sourcev] == 0.0 && targetnodecnt[sourcev] == 0.0 )
3944 touchednodes[ntouchednodes] = sourcev;
3947 sourcenodecnt[sourcev] += weight;
3948 totalsourcecnt += weight;
3952 if( sourcenodecnt[targetv] == 0.0 && targetnodecnt[targetv] == 0.0 )
3954 touchednodes[ntouchednodes] = targetv;
3957 targetnodecnt[targetv] += weight;
3958 totaltargetcnt += weight;
3960 if( sourcev >= 0 || targetv >= 0 )
3961 totalnodecnt += weight;
3968 bestsourcecnt = 0.0;
3969 besttargetcnt = 0.0;
3970 for( i = 0; i < ntouchednodes; i++ )
3972 v = touchednodes[i];
3973 assert(0 <= v && v < nnodes);
3978 if( sourcenodecnt[v] >= targetnodecnt[v] )
3980 if( sourcenodecnt[v] > bestsourcecnt )
3983 bestsourcecnt = sourcenodecnt[v];
3988 if( targetnodecnt[v] > besttargetcnt )
3991 besttargetcnt = targetnodecnt[v];
3997 SCIP_Real nodecnt = sourcenodecnt[v] + targetnodecnt[v];
4001 if( nodecnt > bestsourcecnt )
4003 besttargetv = bestsourcev;
4004 besttargetcnt = bestsourcecnt;
4006 bestsourcecnt = nodecnt;
4008 else if( nodecnt > besttargetcnt )
4011 besttargetcnt = nodecnt;
4016 sourcenodecnt[v] = 0;
4017 targetnodecnt[v] = 0;
4023 totalsourcecnt = totalnodecnt;
4024 totaltargetcnt = totalnodecnt;
4026 assert(
SCIPisGE(scip,totalsourcecnt,bestsourcecnt));
4027 assert(
SCIPisGE(scip,totaltargetcnt,besttargetcnt));
4028 nsourceinconsistencies = (totalsourcecnt - bestsourcecnt)/ntouchedcoms;
4029 ntargetinconsistencies = (totaltargetcnt - besttargetcnt)/ntouchedcoms;
4032 if( nsourceinconsistencies > maxarcinconsistencyratio )
4038 if( ntargetinconsistencies > maxarcinconsistencyratio )
4045 assert(bestsourcev == -1 || bestsourcev != besttargetv);
4046 arcsources[
a] = bestsourcev;
4047 arctargets[
a] = besttargetv;
4048 SCIPdebugMsg(scip,
"arc %d: %d -> %d (len=%d, sourcecnt=%g/%g, targetcnt=%g/%g, %g/%g inconsistencies)\n",
4049 a, bestsourcev, besttargetv, rowlen,
4050 bestsourcecnt, totalsourcecnt, besttargetcnt, totaltargetcnt,
4051 nsourceinconsistencies, ntargetinconsistencies);
4054 if( bestsourcev != -1 )
4056 nextoutarcs[
a] = firstoutarcs[bestsourcev];
4057 firstoutarcs[bestsourcev] =
a;
4059 if( besttargetv != -1 )
4061 nextinarcs[
a] = firstinarcs[besttargetv];
4062 firstinarcs[besttargetv] =
a;
4066 mcfdata->ninconsistencies += 0.5*(nsourceinconsistencies + ntargetinconsistencies);
4068 if( mcfdata->ninconsistencies > maxninconsistencies )
4070 MCFdebugMessage(
" -> reached maximal number of inconsistencies: %g > %g\n",
4071 mcfdata->ninconsistencies, maxninconsistencies);
4077 if( mcfdata->ninconsistencies <= maxninconsistencies && narcs > 0 && ncommodities > 0 )
4082 MCFdebugMessage(
"extracted network has %g inconsistencies (ratio %g) -> separating with effort %d\n",
4083 mcfdata->ninconsistencies, mcfdata->ninconsistencies/(
SCIP_Real)narcs, *effortlevel);
4114 int* firstoutarcs = mcfdata->firstoutarcs;
4115 int* firstinarcs = mcfdata->firstinarcs;
4116 int* nextoutarcs = mcfdata->nextoutarcs;
4117 int* nextinarcs = mcfdata->nextinarcs;
4118 int nnodes = mcfdata->nnodes;
4123 assert(nodevisited !=
NULL);
4124 assert(0 <= startv && startv < nnodes);
4125 assert(nodevisited[startv] ==
UNKNOWN);
4126 assert(compnodes !=
NULL);
4127 assert(ncompnodes !=
NULL);
4128 assert(comparcs !=
NULL);
4129 assert(ncomparcs !=
NULL);
4138 stacknodes[0] = startv;
4140 nodevisited[startv] =
ONSTACK;
4143 while( nstacknodes > 0 )
4148 assert(firstoutarcs !=
NULL);
4149 assert(firstinarcs !=
NULL);
4150 assert(nextoutarcs !=
NULL);
4151 assert(nextinarcs !=
NULL);
4154 v = stacknodes[nstacknodes-1];
4156 assert(0 <= v && v < nnodes);
4157 assert(nodevisited[v] ==
ONSTACK);
4161 assert(*ncompnodes < nnodes);
4162 compnodes[*ncompnodes] = v;
4166 for( a = firstoutarcs[v]; a != -1; a = nextoutarcs[
a] )
4170 assert(0 <= a && a < mcfdata->
narcs);
4171 assert(arctargets !=
NULL);
4173 targetv = arctargets[
a];
4176 if( targetv != -1 && nodevisited[targetv] ==
VISITED )
4180 assert(*ncomparcs < mcfdata->narcs);
4181 comparcs[*ncomparcs] =
a;
4185 if( targetv != -1 && nodevisited[targetv] ==
UNKNOWN )
4187 assert(nstacknodes < nnodes);
4188 stacknodes[nstacknodes] = targetv;
4190 nodevisited[targetv] =
ONSTACK;
4195 for( a = firstinarcs[v]; a != -1; a = nextinarcs[
a] )
4199 assert(0 <= a && a < mcfdata->
narcs);
4200 assert(arcsources !=
NULL);
4202 sourcev = arcsources[
a];
4205 if( sourcev != -1 && nodevisited[sourcev] ==
VISITED )
4209 assert(*ncomparcs < mcfdata->narcs);
4210 comparcs[*ncomparcs] =
a;
4214 if( sourcev != -1 && nodevisited[sourcev] ==
UNKNOWN )
4216 assert(nstacknodes < nnodes);
4217 stacknodes[nstacknodes] = sourcev;
4219 nodevisited[sourcev] =
ONSTACK;
4250 int mcfnetworkssize;
4252 assert(mcfnetworks !=
NULL);
4253 assert(nmcfnetworks !=
NULL);
4254 assert(effortlevel !=
NULL);
4258 *mcfnetworks =
NULL;
4260 mcfnetworkssize = 0;
4291 mcfdata.flowrowsigns =
NULL;
4292 mcfdata.flowrowscalars =
NULL;
4293 mcfdata.flowrowscores =
NULL;
4294 mcfdata.capacityrowsigns =
NULL;
4295 mcfdata.capacityrowscores =
NULL;
4296 mcfdata.flowcands =
NULL;
4297 mcfdata.nflowcands = 0;
4298 mcfdata.capacitycands =
NULL;
4299 mcfdata.ncapacitycands = 0;
4300 mcfdata.plusflow =
NULL;
4301 mcfdata.minusflow =
NULL;
4302 mcfdata.ncommodities = 0;
4303 mcfdata.nemptycommodities = 0;
4304 mcfdata.commoditysigns =
NULL;
4305 mcfdata.commoditysignssize = 0;
4306 mcfdata.colcommodity =
NULL;
4307 mcfdata.rowcommodity =
NULL;
4308 mcfdata.colarcid =
NULL;
4309 mcfdata.rowarcid =
NULL;
4310 mcfdata.rownodeid =
NULL;
4311 mcfdata.arcarraysize = 0;
4312 mcfdata.arcsources =
NULL;
4313 mcfdata.arctargets =
NULL;
4314 mcfdata.colsources =
NULL;
4315 mcfdata.coltargets =
NULL;
4316 mcfdata.firstoutarcs =
NULL;
4317 mcfdata.firstinarcs =
NULL;
4318 mcfdata.nextoutarcs =
NULL;
4319 mcfdata.nextinarcs =
NULL;
4320 mcfdata.newcols =
NULL;
4321 mcfdata.nnewcols = 0;
4324 mcfdata.ninconsistencies = 0.0;
4325 mcfdata.capacityrows =
NULL;
4326 mcfdata.capacityrowssize = 0;
4327 mcfdata.colisincident =
NULL;
4328 mcfdata.zeroarcarray =
NULL;
4335 assert(mcfdata.flowrowsigns !=
NULL);
4336 assert(mcfdata.flowrowscalars !=
NULL);
4337 assert(mcfdata.flowrowscores !=
NULL);
4338 assert(mcfdata.flowcands !=
NULL);
4340 if( mcfdata.nflowcands == 0 )
4348 assert(mcfdata.plusflow !=
NULL);
4349 assert(mcfdata.minusflow !=
NULL);
4350 assert(mcfdata.colcommodity !=
NULL);
4351 assert(mcfdata.rowcommodity !=
NULL);
4352 assert(mcfdata.newcols !=
NULL);
4358 printCommodities(scip, &mcfdata);
4365 assert(mcfdata.capacityrowsigns !=
NULL);
4366 assert(mcfdata.capacityrowscores !=
NULL);
4367 assert(mcfdata.capacitycands !=
NULL);
4369 if( mcfdata.ncapacitycands == 0 )
4377 assert(mcfdata.colarcid !=
NULL);
4378 assert(mcfdata.rowarcid !=
NULL);
4382 assert(mcfdata.rownodeid !=
NULL);
4383 assert(mcfdata.colisincident !=
NULL);
4384 assert(mcfdata.zeroarcarray !=
NULL);
4395 assert(mcfdata.arcsources !=
NULL);
4396 assert(mcfdata.arctargets !=
NULL);
4397 assert(mcfdata.colsources !=
NULL);
4398 assert(mcfdata.coltargets !=
NULL);
4399 assert(mcfdata.firstoutarcs !=
NULL);
4400 assert(mcfdata.firstinarcs !=
NULL);
4401 assert(mcfdata.nextoutarcs !=
NULL);
4402 assert(mcfdata.nextinarcs !=
NULL);
4418 printCommodities(scip, &mcfdata);
4431 for( v = 0; v < mcfdata.nnodes; v++ )
4435 for( v = 0; v < mcfdata.nnodes; v++ )
4442 if( nodevisited[v] ==
VISITED )
4447 assert(ncompnodes >= 1);
4448 assert(compnodes[0] == v);
4449 assert(nodevisited[v] ==
VISITED);
4452 if( ncompnodes >= minnodes && ncomparcs >=
MINARCS )
4459 assert(*nmcfnetworks <= mcfnetworkssize);
4460 if( *nmcfnetworks == mcfnetworkssize )
4462 mcfnetworkssize =
MAX(2*mcfnetworkssize, *nmcfnetworks+1);
4465 assert(*nmcfnetworks < mcfnetworkssize);
4471 SCIP_CALL(
mcfnetworkFill(scip, mcfnetwork, &mcfdata, compnodeid, compnodes, ncompnodes, comparcs, ncomparcs) );
4474 assert(*mcfnetworks !=
NULL);
4475 for( i = *nmcfnetworks; i > 0 && mcfnetwork->
nnodes > (*mcfnetworks)[i-1]->nnodes; i-- )
4476 (*mcfnetworks)[i] = (*mcfnetworks)[i-1];
4477 (*mcfnetworks)[i] = mcfnetwork;
4482 minnodes =
MAX(minnodes, (*mcfnetworks)[*nmcfnetworks-1]->
nnodes);
4487 SCIPdebugMsg(scip,
" -> discarded network with %d nodes and %d arcs due to maxnetworks (minnodes=%d)\n",
4488 (*mcfnetworks)[*nmcfnetworks-1]->
nnodes, (*mcfnetworks)[*nmcfnetworks-1]->
narcs, minnodes);
4496 SCIPdebugMsg(scip,
" -> discarded component with %d nodes and %d arcs\n", ncompnodes, ncomparcs);
4538 #ifdef COUNTNETWORKVARIABLETYPES 4560 int nintflowvars = 0;
4561 int nbinflowvars = 0;
4562 int ncontflowvars = 0;
4564 int nintcapvars = 0;
4565 int nbincapvars = 0;
4566 int ncontcapvars = 0;
4574 for(c=0; c < ncols; c++)
4575 colvisited[c]=
FALSE;
4579 for(m=0; m < nmcfnetworks; m++)
4591 for(c=0; c < ncols; c++)
4595 if(colcommodity[c] >= 0 && ! colvisited[c])
4600 colvisited[c] =
TRUE;
4623 for( a = 0; a <
narcs; a++ )
4626 row = arccapacityrows[
a];
4638 for( i = 0; i < rowlen; i++ )
4643 if(colcommodity[c] == -1 && ! colvisited[c] )
4646 colvisited[c] =
TRUE;
4673 for( v = 0; v <
nnodes; v++ )
4676 row = nodeflowrows[v][k];
4686 MCFdebugMessage(
" nof flowvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4687 nflowvars, ncontflowvars, nintflowvars, nbinflowvars);
4688 MCFdebugMessage(
" nof capvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
4689 ncapvars, ncontcapvars, nintcapvars, nbincapvars);
4708 int* representatives,
4715 for( v = 0; v < nelems; v++ )
4716 representatives[v] = v;
4722 int* representatives,
4726 assert(representatives !=
NULL);
4728 while( v != representatives[v] )
4730 representatives[v] = representatives[representatives[v]];
4731 v = representatives[v];
4740 int* representatives,
4745 assert(rep1 != rep2);
4746 assert(representatives[rep1] == rep1);
4747 assert(representatives[rep2] == rep2);
4753 representatives[rep2] = rep1;
4755 representatives[rep1] = rep2;
4771 if( nodepair1->weight > nodepair2->weight )
4773 else if( nodepair1->weight < nodepair2->weight )
4808 assert(mcfnetwork !=
NULL);
4814 assert(nodepair1 !=
NULL);
4815 assert(nodepair2 !=
NULL);
4817 source1 = nodepair1->node1;
4818 source2 = nodepair2->node1;
4819 target1 = nodepair1->node2;
4820 target2 = nodepair2->node2;
4822 assert(source1 >=0 && source1 < mcfnetwork->
nnodes);
4823 assert(source2 >=0 && source2 < mcfnetwork->nnodes);
4824 assert(target1 >=0 && target1 < mcfnetwork->nnodes);
4825 assert(target2 >=0 && target2 < mcfnetwork->nnodes);
4826 assert(source1 <= target1);
4827 assert(source2 <= target2);
4829 return (source1 == source2 && target1 == target2);
4843 unsigned int hashval;
4847 assert(mcfnetwork !=
NULL);
4851 assert( nodepair !=
NULL);
4853 source = nodepair->node1;
4854 target = nodepair->node2;
4856 assert(source >=0 && source < mcfnetwork->
nnodes);
4857 assert(target >=0 && target < mcfnetwork->nnodes);
4858 assert(source <= target);
4860 hashval = (unsigned)((source << 16) + target);
4883 #ifdef BETTERWEIGHTFORDEMANDNODES 4903 assert(mcfnetwork !=
NULL);
4905 #ifdef BETTERWEIGHTFORDEMANDNODES 4915 assert(nodepairqueue !=
NULL);
4922 hashtablesize = mcfnetwork->
narcs;
4925 hashGetKeyNodepairs, hashKeyEqNodepairs, hashKeyValNodepairs, (
void*) mcfnetwork) );
4932 for( a = 0; a < mcfnetwork->narcs; a++ )
4938 capacityrow = mcfnetwork->arccapacityrows[
a];
4940 SCIPdebugMsg(scip,
"arc %i = (%i %i)\n", a, mcfnetwork->arcsources[a], mcfnetwork->arctargets[a]);
4943 if( mcfnetwork->arcsources[a] <= mcfnetwork->arctargets[a] )
4945 nodepair.node1 = mcfnetwork->arcsources[
a];
4946 nodepair.node2 = mcfnetwork->arctargets[
a];
4950 nodepair.node2 = mcfnetwork->arcsources[
a];
4951 nodepair.node1 = mcfnetwork->arctargets[
a];
4954 assert(nodepair.node1 < mcfnetwork->nnodes);
4955 assert(nodepair.node2 < mcfnetwork->nnodes);
4956 if( nodepair.node1 == -1 || nodepair.node2 == -1 )
4960 if( capacityrow !=
NULL )
4976 slack =
MAX(slack, 0.0);
4979 scale = ABS(mcfnetwork->arccapacityscales[a])/maxval;
4980 assert(scale > 0.0);
4990 for( i = 0; i < rowlen; i++ )
4997 if(colcommodity[c] >= 0)
5009 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g -- flow:%g -- cap:%g \n", scale * slack, dualsol/scale, totalflow * scale, totalcap * scale);
5011 SCIPdebugMsg(scip,
"cap arc -- slack:%g -- dual:%g1\n", scale * slack, dualsol/scale);
5015 nodepair.weight = scale * slack - ABS(dualsol)/scale;
5016 #ifdef USEFLOWFORTIEBREAKING 5019 nodepair.weight += totalflow * scale;
5020 nodepair.weight = MIN( nodepair.weight, -0.0001);
5023 #ifdef USECAPACITYFORTIEBREAKING 5026 nodepair.weight += totalcap * scale;
5027 nodepair.weight = MIN( nodepair.weight, -0.0001);
5042 if( nodepairptr !=
NULL )
5045 SCIPdebugMsg(scip,
"nodepair known [%d,%d] -- old weight:%g -- new weight:%g\n", nodepair.node1,nodepair.node2,nodepairptr->weight,
5046 MIN(nodepair.weight, nodepairptr->weight));
5047 nodepairptr->weight = MIN(nodepair.weight, nodepairptr->weight);
5052 nodepairs = (*nodepairqueue)->nodepairs;
5054 assert(nnodepairs < mcfnetwork->
narcs);
5055 nodepairs[nnodepairs] = nodepair;
5058 SCIPdebugMsg(scip,
"new nodepair [%d,%d]-- weight:%g\n", nodepair.node1, nodepair.node2, nodepair.weight);
5069 #ifdef BETTERWEIGHTFORDEMANDNODES 5077 nodepairs = (*nodepairqueue)->nodepairs;
5078 for( n = 0; n < nnodepairs; n++ )
5082 maxweight =
MAX(maxweight, nodepairs[n].weight);
5084 minweight = MIN(minweight, nodepairs[n].weight);
5087 SCIPdebugMsg(scip,
"min/max weight:%g / %g\n", minweight, maxweight);
5094 for( n = 0; n < nnodepairs; n++ )
5096 int node1 = nodepairs[n].node1;
5097 int node2 = nodepairs[n].node2;
5099 #ifdef BETTERWEIGHTFORDEMANDNODES 5106 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5114 if( nodeflowrows[node1][k] ==
NULL )
5117 if( nodeflowscales[node1][k] > 0.0 )
5134 if( nodeflowrows[node2][k] ==
NULL )
5137 if( nodeflowscales[node2][k] > 0.0 )
5159 if( !hasdemand1 || !hasdemand2 )
5160 nodepairs[n].weight += maxweight;
5166 if( hasdemand1 && hasdemand2)
5167 nodepairs[n].weight += minweight;
5170 SCIPdebugMsg(scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5187 assert(nodepairqueue !=
NULL);
5188 assert(*nodepairqueue !=
NULL);
5202 assert(nodepairqueue !=
NULL);
5214 assert(nodepairqueue !=
NULL);
5262 assert(mcfnetwork !=
NULL);
5263 assert(nodepartition !=
NULL);
5264 assert(mcfnetwork->
nnodes >= 1);
5272 (*nodepartition)->nclusters = 0;
5281 nclustersleft = mcfnetwork->
nnodes;
5292 assert(nodepair !=
NULL);
5293 node1 = nodepair->node1;
5294 node2 = nodepair->node2;
5296 assert(node1 >= 0 && node1 < mcfnetwork->
nnodes);
5297 assert(node2 >= 0 && node2 < mcfnetwork->nnodes);
5302 assert(0 <= node1rep && node1rep < mcfnetwork->nnodes);
5303 assert(0 <= node2rep && node2rep < mcfnetwork->nnodes);
5306 if( node1rep == node2rep )
5310 SCIPdebugMsg(scip,
"shrinking nodepair (%d,%d) with weight %g: join representatives %d and %d\n",
5311 node1, node2, nodepair->weight, node1rep, node2rep);
5317 assert((*nodepartition)->representatives[0] == 0);
5322 if( nclustersleft > nclusters )
5324 for( v = 1; v < mcfnetwork->
nnodes && nclustersleft > nclusters; v++ )
5336 assert(nclustersleft <= nclusters);
5341 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5351 c = (*nodepartition)->nclusters;
5352 (*nodepartition)->nclusters++;
5355 c = (*nodepartition)->nodeclusters[rep];
5356 assert(0 <= c && c < nclusters);
5359 (*nodepartition)->nodeclusters[v] = c;
5365 for( c = 0; c < (*nodepartition)->nclusters; c++ )
5367 (*nodepartition)->clusterbegin[c] = pos;
5368 pos += clustersize[c];
5370 assert(pos == mcfnetwork->
nnodes);
5371 (*nodepartition)->clusterbegin[(*nodepartition)->nclusters] = mcfnetwork->
nnodes;
5375 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5377 c = (*nodepartition)->nodeclusters[v];
5378 assert(0 <= c && c < (*nodepartition)->nclusters);
5379 pos = (*nodepartition)->clusterbegin[c] + clustersize[c];
5380 assert(pos < (*nodepartition)->clusterbegin[c+1]);
5381 (*nodepartition)->clusternodes[pos] = v;
5401 assert(nodepartition !=
NULL);
5402 assert(*nodepartition !=
NULL);
5415 unsigned int partition,
5426 if( nodepartition ==
NULL )
5427 return ((v == (
int)partition) == !inverted);
5431 unsigned int clusterbit;
5433 cluster = nodepartition->nodeclusters[v];
5434 assert(0 <= cluster && cluster < nodepartition->nclusters);
5435 clusterbit = (1 << cluster);
5437 return (((partition & clusterbit) != 0) == !inverted);
5447 unsigned int partition
5450 const int* nodeclusters = nodepartition->nodeclusters;
5460 assert(nodepartition->nodeclusters !=
NULL);
5461 nclusters = nodepartition->nclusters;
5468 ncomponents = nclusters;
5469 assert(ncomponents >= 2);
5472 for( a = 0; a <
narcs; a++ )
5474 int s = arcsources[
a];
5475 int t = arctargets[
a];
5478 if( s == -1 || t == -1 )
5489 assert(0 <= s && s < mcfnetwork->
nnodes);
5490 assert(0 <= t && t < mcfnetwork->nnodes);
5493 cs = nodeclusters[s];
5494 ct = nodeclusters[t];
5495 assert(0 <= cs && cs < nclusters);
5496 assert(0 <= ct && ct < nclusters);
5505 if( repcs == repct )
5512 if( ncomponents <= 2 )
5522 assert(ncomponents >= 2);
5524 return (ncomponents == 2);
5529 void nodepartitionPrint(
5535 for( c = 0; c < nodepartition->nclusters; c++ )
5540 for( i = nodepartition->clusterbegin[c]; i < nodepartition->clusterbegin[c+1]; i++ )
5555 unsigned int partition
5564 if( nodepartition ==
NULL )
5569 file = fopen(filename,
"w");
5577 fprintf(file,
"graph\n");
5578 fprintf(file,
"[\n");
5579 fprintf(file,
" hierarchic 1\n");
5580 fprintf(file,
" label \"\"\n");
5581 fprintf(file,
" directed 1\n");
5584 for( v = 0; v < mcfnetwork->
nnodes; v++ )
5595 fprintf(file,
" node\n");
5596 fprintf(file,
" [\n");
5597 fprintf(file,
" id %d\n", v);
5598 fprintf(file,
" label \"%s\"\n", label);
5599 fprintf(file,
" graphics\n");
5600 fprintf(file,
" [\n");
5601 fprintf(file,
" w 30.0\n");
5602 fprintf(file,
" h 30.0\n");
5603 fprintf(file,
" type \"ellipse\"\n");
5605 fprintf(file,
" fill \"#FF0000\"\n");
5607 fprintf(file,
" fill \"#00FF00\"\n");
5608 fprintf(file,
" outline \"#000000\"\n");
5609 fprintf(file,
" ]\n");
5610 fprintf(file,
" LabelGraphics\n");
5611 fprintf(file,
" [\n");
5612 fprintf(file,
" text \"%s\"\n", label);
5613 fprintf(file,
" fontSize 13\n");
5614 fprintf(file,
" fontName \"Dialog\"\n");
5615 fprintf(file,
" anchor \"c\"\n");
5616 fprintf(file,
" ]\n");
5618 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+1);
5620 fprintf(file,
" gid %d\n", mcfnetwork->
nnodes+2);
5621 fprintf(file,
" ]\n");
5625 fprintf(file,
" node\n");
5626 fprintf(file,
" [\n");
5627 fprintf(file,
" id %d\n", mcfnetwork->
nnodes);
5628 fprintf(file,
" label \"?\"\n");
5629 fprintf(file,
" graphics\n");
5630 fprintf(file,
" [\n");
5631 fprintf(file,
" w 30.0\n");
5632 fprintf(file,
" h 30.0\n");
5633 fprintf(file,
" type \"ellipse\"\n");
5634 fprintf(file,
" fill \"#FFFFFF\"\n");
5635 fprintf(file,
" outline \"#000000\"\n");
5636 fprintf(file,
" ]\n");
5637 fprintf(file,
" LabelGraphics\n");
5638 fprintf(file,
" [\n");
5639 fprintf(file,
" text \"?\"\n");
5640 fprintf(file,
" fontSize 13\n");
5641 fprintf(file,
" fontName \"Dialog\"\n");
5642 fprintf(file,
" anchor \"c\"\n");
5643 fprintf(file,
" ]\n");
5644 fprintf(file,
" ]\n");
5647 fprintf(file,
" node\n");
5648 fprintf(file,
" [\n");
5649 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+1);
5650 fprintf(file,
" label \"Partition S\"\n");
5651 fprintf(file,
" graphics\n");
5652 fprintf(file,
" [\n");
5653 fprintf(file,
" type \"roundrectangle\"\n");
5654 fprintf(file,
" fill \"#CAECFF84\"\n");
5655 fprintf(file,
" outline \"#666699\"\n");
5656 fprintf(file,
" outlineStyle \"dotted\"\n");
5657 fprintf(file,
" topBorderInset 0\n");
5658 fprintf(file,
" bottomBorderInset 0\n");
5659 fprintf(file,
" leftBorderInset 0\n");
5660 fprintf(file,
" rightBorderInset 0\n");
5661 fprintf(file,
" ]\n");
5662 fprintf(file,
" LabelGraphics\n");
5663 fprintf(file,
" [\n");
5664 fprintf(file,
" text \"Partition S\"\n");
5665 fprintf(file,
" fill \"#99CCFF\"\n");
5666 fprintf(file,
" fontSize 15\n");
5667 fprintf(file,
" fontName \"Dialog\"\n");
5668 fprintf(file,
" alignment \"right\"\n");
5669 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5670 fprintf(file,
" anchor \"t\"\n");
5671 fprintf(file,
" borderDistance 0.0\n");
5672 fprintf(file,
" ]\n");
5673 fprintf(file,
" isGroup 1\n");
5674 fprintf(file,
" ]\n");
5677 fprintf(file,
" node\n");
5678 fprintf(file,
" [\n");
5679 fprintf(file,
" id %d\n", mcfnetwork->
nnodes+2);
5680 fprintf(file,
" label \"Partition T\"\n");
5681 fprintf(file,
" graphics\n");
5682 fprintf(file,
" [\n");
5683 fprintf(file,
" type \"roundrectangle\"\n");
5684 fprintf(file,
" fill \"#CAECFF84\"\n");
5685 fprintf(file,
" outline \"#666699\"\n");
5686 fprintf(file,
" outlineStyle \"dotted\"\n");
5687 fprintf(file,
" topBorderInset 0\n");
5688 fprintf(file,
" bottomBorderInset 0\n");
5689 fprintf(file,
" leftBorderInset 0\n");
5690 fprintf(file,
" rightBorderInset 0\n");
5691 fprintf(file,
" ]\n");
5692 fprintf(file,
" LabelGraphics\n");
5693 fprintf(file,
" [\n");
5694 fprintf(file,
" text \"Partition T\"\n");
5695 fprintf(file,
" fill \"#99CCFF\"\n");
5696 fprintf(file,
" fontSize 15\n");
5697 fprintf(file,
" fontName \"Dialog\"\n");
5698 fprintf(file,
" alignment \"right\"\n");
5699 fprintf(file,
" autoSizePolicy \"node_width\"\n");
5700 fprintf(file,
" anchor \"t\"\n");
5701 fprintf(file,
" borderDistance 0.0\n");
5702 fprintf(file,
" ]\n");
5703 fprintf(file,
" isGroup 1\n");
5704 fprintf(file,
" ]\n");
5707 for( a = 0; a < mcfnetwork->
narcs; a++ )
5719 hasfractional =
FALSE;
5730 for( i = 0; i < rowlen; i++ )
5737 hasfractional =
TRUE;
5745 fprintf(file,
" edge\n");
5746 fprintf(file,
" [\n");
5749 fprintf(file,
" label \"%s\"\n", label);
5750 fprintf(file,
" graphics\n");
5751 fprintf(file,
" [\n");
5753 fprintf(file,
" fill \"#000000\"\n");
5755 fprintf(file,
" fill \"#FF0000\"\n");
5757 fprintf(file,
" style \"dashed\"\n");
5758 fprintf(file,
" width 1\n");
5759 fprintf(file,
" targetArrow \"standard\"\n");
5760 fprintf(file,
" ]\n");
5761 fprintf(file,
" LabelGraphics\n");
5762 fprintf(file,
" [\n");
5763 fprintf(file,
" text \"%s\"\n", label);
5764 fprintf(file,
" ]\n");
5765 fprintf(file,
" ]\n");
5769 fprintf(file,
"]\n");
5804 assert(scip !=
NULL);
5805 assert(sepadata !=
NULL);
5806 assert(cutcoefs !=
NULL);
5807 assert(ncuts !=
NULL);
5808 assert(cutoff !=
NULL);
5812 assert(nvars == 0 || vars !=
NULL);
5818 for( i = 0; i < cutnnz; ++i )
5820 cutvars[i] = vars[cutinds[i]];
5826 sepadata->dynamiccuts) );
5836 SCIPdebugMsg(scip,
" -> found MCF cut <%s>: rhs=%f, act=%f eff=%f rank=%d\n",
5853 if( !(*cutoff) && sepadata->separateknapsack)
5856 SCIP_CALL(
SCIPseparateRelaxedKnapsack(scip,
NULL, sepa, cutnnz, cutvars, cutcoefs, +1.0, cutrhs, sol, cutoff, ncuts) );
5907 unsigned int partition;
5908 unsigned int allpartitions;
5909 unsigned int startpartition;
5923 maxsepacuts = sepadata->maxsepacutsroot;
5925 maxsepacuts = sepadata->maxsepacuts;
5926 if( maxsepacuts < 0 )
5927 maxsepacuts = INT_MAX;
5932 maxtestdelta = sepadata->maxtestdelta;
5933 if( maxtestdelta <= 0 )
5934 maxtestdelta = INT_MAX;
5970 if( nodepartition ==
NULL )
5974 allpartitions = (
unsigned int) nnodes;
5975 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nnodes: %d \n", maxtestdelta, maxsepacuts, nnodes);
5982 int nclusters = nodepartition->nclusters;
5984 assert((
unsigned int)nclusters <= 8*
sizeof(
unsigned int));
5985 SCIPdebugMsg(scip,
"maxtestdelta: %d, maxsepacuts: %d, nclusters: %d \n", maxtestdelta, maxsepacuts, nclusters);
5992 allpartitions = (1 << (nclusters-1));
5996 for( partition = startpartition; partition <= allpartitions-1 && !
SCIPisStopped(scip) && *ncuts < maxsepacuts && !*cutoff; partition++ )
6010 if( sepadata->checkcutshoreconnectivity )
6017 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x \n", partition );
6018 SCIPdebugMsg(scip,
" -> either shore S or shore T is not connected - skip partition.\n");
6023 for( inverted =
FALSE; inverted <= useinverted && !*cutoff; inverted++ )
6025 if( nodepartition ==
NULL )
6027 SCIPdebugMsg(scip,
"generating single-node cuts for node %u (inverted: %u)\n", partition, inverted);
6031 SCIPdebugMsg(scip,
"generating cluster cuts for partition 0x%x (inverted: %u)\n", partition, inverted);
6035 SCIP_CALL( outputGraph(scip, mcfnetwork, nodepartition, inverted, partition) );
6053 for( v = 0; v <
nnodes; v++ )
6067 if( nodeflowrows[v][k] ==
NULL )
6070 if( nodeflowscales[v][k] > 0.0 )
6074 if( nodeflowinverted[v][k] )
6077 comcutdemands[k] += rhs * nodeflowscales[v][k];
6080 assert (1 <= nnodesinS && nnodesinS <= nnodes-1);
6085 if( sepadata->separatesinglenodecuts && nodepartition !=
NULL && (nnodesinS == 1 || nnodesinS == nnodes-1) )
6087 SCIPdebugMsg(scip,
" -> shore S or T has only one node - skip partition.\n");
6097 SCIPdebugMsg(scip,
" -> commodity %d: directed cutdemand=%g\n", k, comcutdemands[k]);
6107 SCIPdebugMsg(scip,
" -> commodity %d: undirected cutdemand=%g\n", k, comcutdemands[k]);
6112 if( k == ncommodities )
6116 for( a = 0; a <
narcs; a++ )
6125 assert(arcsources[a] < nnodes);
6126 assert(arctargets[a] < nnodes);
6132 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) ||
6142 if(
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6148 if( !
nodeInPartition(nodepartition, partition, inverted, arcsources[a]) &&
6157 if( arccapacityrows[a] ==
NULL )
6165 assert(rowweights[r] == 0.0);
6171 if( arcsources[a] == -1 || arctargets[a] == -1 )
6181 assert(maxcoef > 0.0);
6186 rowweights[
r] = arccapacityscales[
a];
6187 SCIPdebugMsg(scip,
" -> arc %d, r=%d, capacity row <%s>: weight=%g slack=%g dual=%g\n", a, r,
SCIProwGetName(arccapacityrows[a]), rowweights[r],
6191 if( sepadata->separateflowcutset )
6193 if( rowweights[r] > 0.0 )
6203 for( j = 0; j < rowlen; j++ )
6208 coef = rowvals[j] * arccapacityscales[
a];
6214 k = colcommodity[c];
6216 comdemands[k] = coef;
6230 while( left <= right )
6232 int mid = (left+right)/2;
6234 if(
REALABS( deltas[mid] / coef - 1.0 ) < 1e-03 )
6239 else if( coef < deltas[mid] )
6248 assert(right == left-1);
6249 assert(ndeltas <= deltassize);
6250 if( ndeltas == deltassize )
6255 if( left < ndeltas )
6257 for( d = ndeltas; d > left; d-- )
6258 deltas[d] = deltas[d-1];
6260 deltas[left] = coef;
6262 SCIPdebugMsg(scip,
" -> new capacity %g considered as delta\n", coef);
6269 for( v = 0; v <
nnodes; v++ )
6278 if( comdemands[k] == 0.0 )
6281 scale = comdemands[k];
6304 if( comcutdemands[k] > 0.0 )
6323 if( nodeflowrows[v][k] ==
NULL )
6332 assert(rowweights[r] == 0.0);
6338 rowweights[
r] = scale * nodeflowscales[v][k];
6339 if( nodeflowinverted[v][k] )
6340 rowweights[
r] *= -1.0;
6341 SCIPdebugMsg(scip,
" -> node %d, commodity %d, r=%d, flow row <%s>: scale=%g weight=%g slack=%g dual=%g\n",
6342 v, k, r,
SCIProwGetName(nodeflowrows[v][k]), scale, rowweights[r],
6345 if( sepadata->separateflowcutset )
6347 if( nodeflowscales[v][k] > 0.0 )
6363 if( sepadata->separateflowcutset )
6366 bestdelta = deltas[ndeltas-1];
6376 SCIPdebugMsg(scip,
" -> found %d different deltas to try\n", ndeltas);
6377 for( d = ndeltas-1; d >= 0 && d >= ndeltas-maxtestdelta; d-- )
6391 SCIPdebugMsg(scip,
"applying MIR with delta = %g\n", deltas[d]);
6392 SCIP_CALL(
SCIPcalcMIR(scip, sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal, sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6393 1.0/deltas[d], aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6394 assert(allowlocal || !cutislocal);
6402 if( sepadata->separateflowcutset )
6404 if( cutefficacy > bestefficacy )
6406 bestdelta = deltas[d];
6407 bestefficacy = cutefficacy;
6413 SCIPdebugMsg(scip,
"success -> delta = %g -> rhs: %g, efficacy: %g\n", deltas[d], cutrhs, cutefficacy);
6414 SCIP_CALL(
addCut(scip, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );
6419 for( a = 0; a <
narcs; a++ )
6421 if( arccapacityrows[a] !=
NULL )
6427 if( r >= 0 && rowweights[r] != 0.0 )
6429 MCFdebugMessage(
" -> arc %d, capacity row <%s>: weight=%g slack=%g prod=%g dual=%g\n", a,
6442 if( sepadata->separateflowcutset && oldncuts == *ncuts && !*cutoff )
6445 f0 =
SCIPfrac(scip, baserhs/bestdelta);
6450 totalviolationdelta = 0.0;
6451 onedivoneminsf0 = 1.0/(1.0 - f0);
6452 for( a = 0; a <
narcs; a++ )
6466 if( arccapacityrows[a] ==
NULL )
6477 if( rowweights[r] == 0.0 )
6492 rowweight = rowweights[
r]/bestdelta;
6497 violationdelta = rowweight * (rowlhs - rowconstant);
6499 violationdelta = rowweight * (rowrhs - rowconstant);
6501 for( j = 0; j < rowlen; j++ )
6509 coef = rowvals[j] * rowweight;
6520 if( colcommodity[c] >= 0 )
6531 mircoef =
SCIPfloor(scip, coef) + (fj - f0)*onedivoneminsf0;
6538 mircoef = coef * onedivoneminsf0;
6543 if( colcommodity[c] >= 0 )
6544 violationdelta += mircoef * solval;
6546 violationdelta -= mircoef * solval;
6551 SCIPdebugMsg(scip,
" -> discarding capacity row <%s> of weight %g and slack %g: increases MIR violation by %g\n",
6554 rowweights[
r] = 0.0;
6555 totalviolationdelta += violationdelta;
6560 if( totalviolationdelta > 0.0 )
6573 SCIPdebugMsg(scip,
"applying MIR with delta = %g to flowcut inequality (violation improvement: %g)\n", bestdelta, totalviolationdelta);
6580 SCIP_CALL(
SCIPcalcMIR(scip, sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal, sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6581 1.0/bestdelta, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
6583 assert(allowlocal || !cutislocal);
6587 SCIPdebugMsg(scip,
" -> delta = %g -> rhs: %g, efficacy: %g\n", bestdelta, cutrhs, cutefficacy);
6588 SCIP_CALL(
addCut(scip, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );
6632 assert(result !=
NULL);
6645 if( ncols != nvars )
6647 MCFdebugMessage(
"%d variables but %d columns -> exit\n", nvars, ncols );
6660 colrowratio = (
SCIP_Real)ncols/(nrows+1e-9);
6664 assert(sepadata !=
NULL);
6673 if( colrowratio < MINCOLROWRATIO || colrowratio >
MAXCOLROWRATIO )
6682 if( sepadata->nmcfnetworks == -1 )
6690 for( i = 0; i < sepadata->nmcfnetworks; i++ )
6692 MCFdebugMessage(
" -> extracted network %d has %d nodes, %d (%d) arcs (uncapacitated), and %d commodities (modeltype: %s)\n",
6693 i, sepadata->mcfnetworks[i]->nnodes, sepadata->mcfnetworks[i]->narcs, sepadata->mcfnetworks[i]->nuncapacitatedarcs,
6694 sepadata->mcfnetworks[i]->ncommodities,
6696 SCIPdebug( mcfnetworkPrint(sepadata->mcfnetworks[i]) );
6699 #ifdef COUNTNETWORKVARIABLETYPES 6700 SCIP_CALL( printFlowSystemInfo(scip,sepadata->mcfnetworks,sepadata->nmcfnetworks));
6704 assert(sepadata->nmcfnetworks >= 0);
6705 assert(sepadata->mcfnetworks !=
NULL || sepadata->nmcfnetworks == 0);
6706 mcfnetworks = sepadata->mcfnetworks;
6707 nmcfnetworks = sepadata->nmcfnetworks;
6714 sepadata->lastroundsuccess =
FALSE;
6716 for( i = 0; i < nmcfnetworks && !cutoff; i++ )
6722 mcfnetwork = mcfnetworks[i];
6725 assert(mcfnetwork->
nnodes >= 2);
6726 assert(mcfnetwork->
narcs >= 1);
6733 MCFdebugMessage(
"MCF network has %d nodes and %d arcs. arc node ratio %.2f exceed --> exit\n",
6739 if( sepadata->separatesinglenodecuts )
6750 nodepartitionPrint(nodepartition);
6760 MCFdebugMessage(
"MCF network has %d nodes, %d arcs, %d commodities. Found %d MCF network cuts, cutoff = %u.\n",
6767 sepadata->lastroundsuccess =
TRUE;
6769 else if( ncuts > 0 )
6772 sepadata->lastroundsuccess =
TRUE;
6789 assert(scip !=
NULL);
6790 assert(sepa !=
NULL);
6808 assert(sepadata !=
NULL);
6809 assert(sepadata->mcfnetworks ==
NULL);
6810 assert(sepadata->nmcfnetworks == -1);
6828 assert(sepadata !=
NULL);
6830 sepadata->lastroundsuccess =
TRUE;
6847 assert(sepadata !=
NULL);
6850 for( i = 0; i < sepadata->nmcfnetworks; i++ )
6855 sepadata->nmcfnetworks = -1;
6917 sepadata->mcfnetworks =
NULL;
6918 sepadata->nmcfnetworks = -1;
6920 sepadata->lastroundsuccess =
TRUE;
6926 sepaExeclpMcf, sepaExecsolMcf,
6929 assert(sepa !=
NULL);
6940 "separating/mcf/nclusters",
6941 "number of clusters to generate in the shrunken network -- default separation",
6944 "separating/mcf/maxweightrange",
6945 "maximal valid range max(|weights|)/min(|weights|) of row weights",
6948 "separating/mcf/maxtestdelta",
6949 "maximal number of different deltas to try (-1: unlimited) -- default separation",
6952 "separating/mcf/trynegscaling",
6953 "should negative values also be tested in scaling?",
6956 "separating/mcf/fixintegralrhs",
6957 "should an additional variable be complemented if f0 = 0?",
6960 "separating/mcf/dynamiccuts",
6961 "should generated cuts be removed from the LP if they are no longer tight?",
6964 "separating/mcf/modeltype",
6965 "model type of network (0: auto, 1:directed, 2:undirected)",
6968 "separating/mcf/maxsepacuts",
6969 "maximal number of mcf cuts separated per separation round",
6972 "separating/mcf/maxsepacutsroot",
6973 "maximal number of mcf cuts separated per separation round in the root node -- default separation",
6976 "separating/mcf/maxinconsistencyratio",
6977 "maximum inconsistency ratio for separation at all",
6980 "separating/mcf/maxarcinconsistencyratio",
6981 "maximum inconsistency ratio of arcs not to be deleted",
6984 "separating/mcf/checkcutshoreconnectivity",
6985 "should we separate only if the cuts shores are connected?",
6988 "separating/mcf/separatesinglenodecuts",
6989 "should we separate inequalities based on single-node cuts?",
6992 "separating/mcf/separateflowcutset",
6993 "should we separate flowcutset inequalities on the network cuts?",
6996 "separating/mcf/separateknapsack",
6997 "should we separate knapsack cover inequalities on the network cuts?",
enum SCIP_Result SCIP_RESULT
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE mcfnetworkCreate(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
#define DEFAULT_TRYNEGSCALING
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
static SCIP_RETCODE extractFlowRows(SCIP *scip, MCFDATA *mcfdata)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
public methods for SCIP parameter handling
SCIP_Bool ** nodeflowinverted
#define SCIPfreeMemoryArrayNull(scip, ptr)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
public methods for memory management
static SCIP_RETCODE nodepairqueueCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPAIRQUEUE **nodepairqueue)
static SCIP_RETCODE identifySourcesTargets(SCIP *scip, MCFDATA *mcfdata, SCIP_SEPADATA *sepadata, MCFEFFORTLEVEL *effortlevel)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
#define SCIPallocMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE extractFlow(SCIP *scip, MCFDATA *mcfdata, SCIP_Real maxflowvarflowrowratio, SCIP_Bool *failed)
const char * SCIProwGetName(SCIP_ROW *row)
static SCIP_RETCODE extractCapacities(SCIP *scip, MCFDATA *mcfdata)
#define SEPA_MAXBOUNDDIST
static SCIP_RETCODE identifyComponent(SCIP *scip, MCFDATA *mcfdata, int *nodevisited, int startv, int *compnodes, int *ncompnodes, int *comparcs, int *ncomparcs)
#define DEFAULT_MODELTYPE
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_RESULT *result)
struct nodepairqueue NODEPAIRQUEUE
int SCIProwGetNLPNonz(SCIP_ROW *row)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
#define DEFAULT_MAXINCONSISTENCYRATIO
static SCIP_RETCODE nodepartitionCreate(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION **nodepartition, int nclusters)
static void nodepairqueueFree(SCIP *scip, NODEPAIRQUEUE **nodepairqueue)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
methods for the aggregation rows
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_DECL_SORTINDCOMP(compCands)
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
static SCIP_DECL_HASHKEYVAL(hashKeyValNodepairs)
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)
public methods for problem variables
#define DEFAULT_FIXINTEGRALRHS
static SCIP_DECL_SORTPTRCOMP(compNodepairs)
static SCIP_RETCODE getNodeSimilarityScore(SCIP *scip, MCFDATA *mcfdata, int baserowlen, int *basearcpattern, int basenposuncap, int basenneguncap, SCIP_ROW *row, SCIP_Real *score, SCIP_Bool *invertcommodity)
#define SCIPfreeBlockMemory(scip, ptr)
#define DEFAULT_CHECKCUTSHORECONNECTIVITY
static NODEPAIRENTRY * nodepairqueueRemove(NODEPAIRQUEUE *nodepairqueue)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
SCIP_MCFMODELTYPE modeltype
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
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)
public methods for separator plugins
static SCIP_RETCODE mcfnetworkExtract(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_MCFNETWORK ***mcfnetworks, int *nmcfnetworks, MCFEFFORTLEVEL *effortlevel)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
#define MAXFLOWCANDDENSITY
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
public methods for numerical tolerances
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
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)
public methods for querying solving statistics
static SCIP_RETCODE findUncapacitatedArcs(SCIP *scip, MCFDATA *mcfdata)
public methods for the branch-and-bound tree
#define MAXFLOWVARFLOWROWRATIO
#define DEFAULT_MAXTESTDELTA
#define DEFAULT_SEPARATEFLOWCUTSET
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
static void getIncidentNodes(SCIP *scip, MCFDATA *mcfdata, SCIP_COL *col, int *sourcenode, int *targetnode)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
static SCIP_DECL_SEPACOPY(sepaCopyMcf)
#define MAXAGGRLEN(nvars)
static void unionfindJoinSets(int *representatives, int rep1, int rep2)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
#define DEFAULT_MAXSEPACUTSROOT
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
static SCIP_Bool nodeInPartition(NODEPARTITION *nodepartition, unsigned int partition, SCIP_Bool inverted, int v)
static void nodepartitionJoin(NODEPARTITION *nodepartition, int rep1, int rep2)
static SCIP_RETCODE createNewArc(SCIP *scip, MCFDATA *mcfdata, int source, int target, int *newarcid)
#define SCIPallocBuffer(scip, ptr)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static int nodepartitionIsConnected(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, unsigned int partition)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define DEFAULT_MAXSEPACUTS
const char * SCIPvarGetName(SCIP_VAR *var)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
int SCIPgetNLPRows(SCIP *scip)
static SCIP_RETCODE cleanupNetwork(SCIP *scip, MCFDATA *mcfdata)
enum McfEffortLevel MCFEFFORTLEVEL
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeSepaMcf(SCIP *scip)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
#define DEFAULT_MAXWEIGHTRANGE
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
static SCIP_RETCODE mcfnetworkFill(SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, MCFDATA *mcfdata, int *compnodeid, int *compnodes, int ncompnodes, int *comparcs, int ncomparcs)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
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)
static void collectIncidentFlowCols(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *flowrow, int basecommodity)
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
public data structures and miscellaneous methods
struct nodepair NODEPAIRENTRY
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
multi-commodity-flow network cut separator
#define DEFAULT_NCLUSTERS
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
enum SCIP_McfModeltype SCIP_MCFMODELTYPE
SCIP_RETCODE SCIPcaptureRow(SCIP *scip, SCIP_ROW *row)
static SCIP_DECL_HASHKEYEQ(hashKeyEqNodepairs)
static SCIP_DECL_SEPAEXITSOL(sepaExitsolMcf)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_ROW ** arccapacityrows
public methods for LP management
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
public methods for cuts and aggregation rows
static void deleteCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int nrows, int *ndelflowrows, int *ndelflowvars)
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define UNCAPACITATEDARCSTRESHOLD
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
public methods for the LP relaxation, rows and columns
int SCIProwGetRank(SCIP_ROW *row)
static void getNextFlowrow(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW **nextrow, unsigned char *nextrowsign, SCIP_Bool *nextinvertcommodity)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
int SCIPgetNVars(SCIP *scip)
#define HASHSIZE_NODEPAIRS
#define SCIPfreeMemory(scip, ptr)
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
static SCIP_RETCODE mcfnetworkFree(SCIP *scip, SCIP_MCFNETWORK **mcfnetwork)
methods for sorting joint arrays of various types
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
#define DEFAULT_MAXARCINCONSISTENCYRATIO
#define SCIPfreeBuffer(scip, ptr)
#define DEFAULT_SEPARATEKNAPSACK
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
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_VAR * SCIPcolGetVar(SCIP_COL *col)
public methods for solutions
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
static void fixCommoditySigns(MCFDATA *mcfdata)
static int nodepartitionGetRepresentative(NODEPARTITION *nodepartition, int v)
void SCIProwChgRank(SCIP_ROW *row, int rank)
#define DEFAULT_SEPARATESINGLENODECUTS
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz, SCIP_Bool cutislocal, int cutrank, int *ncuts, SCIP_Bool *cutoff)
public methods for message output
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_Real ** nodeflowscales
static SCIP_RETCODE extractCapacityRows(SCIP *scip, MCFDATA *mcfdata)
#define MINCOMNODESFRACTION
public methods for message handling
static SCIP_DECL_SEPAEXECSOL(sepaExecsolMcf)
static void getFlowrowFit(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, int k, unsigned char *rowsign, SCIP_Bool *invertcommodity)
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
static SCIP_DECL_SEPAINITSOL(sepaInitsolMcf)
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
#define SCIPallocMemory(scip, ptr)
static SCIP_DECL_SEPAEXECLP(sepaExeclpMcf)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_ROW *** nodeflowrows
SCIP_Real * arccapacityscales
int SCIPgetNLPCols(SCIP *scip)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
static SCIP_Bool nodepairqueueIsEmpty(NODEPAIRQUEUE *nodepairqueue)
public methods for separators
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIPallocBlockMemory(scip, subsol))
static void unionfindInitSets(int *representatives, int nelems)
static void invertCommodity(SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int ncomrows, int *comcolids, int ncomcolids)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define DEFAULT_DYNAMICCUTS
static int unionfindGetRepresentative(int *representatives, int v)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
static void addFlowrowToCommodity(SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, unsigned char rowsign, int *comcolids, int *ncomcolids)
public methods for global and local (sub)problems
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
int SCIPcolGetLPPos(SCIP_COL *col)
static SCIP_DECL_HASHGETKEY(hashGetKeyNodepairs)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
static SCIP_RETCODE extractNodes(SCIP *scip, MCFDATA *mcfdata)
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)
struct nodepartition NODEPARTITION
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_SEPAFREE(sepaFreeMcf)
struct SCIP_SepaData SCIP_SEPADATA
SCIP_RETCODE SCIPseparateRelaxedKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
static void nodepartitionFree(SCIP *scip, NODEPARTITION **nodepartition)
static SCIP_RETCODE createNewCommodity(SCIP *scip, MCFDATA *mcfdata)
#define SCIPreallocBufferArray(scip, ptr, num)
memory allocation routines