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;
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;
426 for( v = 0; v < mcfdata->nnodes; v++ )
438 for(
k = 0;
k < ncommodities;
k++ )
455 for(
i = 0;
i < nflowcands;
i++ )
518 for(
i = 0;
i < nflowcands;
i++ )
533 rk = rowcommodity[
r];
544 scale = flowrowscalars[
r];
547 if( commoditysigns[
rk] == -1 )
634 if( mcfdata->arcsources[
globala] >= 0 )
640 if( mcfdata->arctargets[
globala] >= 0 )
649 for(
c = 0;
c < ncols;
c++ )
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;
858 unsigned char* flowrowsigns;
859 SCIP_Real* flowrowscalars;
860 SCIP_Real* flowrowscores;
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++ )
914 flowrowscalars[
r] = 0.0;
915 flowrowscores[
r] = 0.0;
980 flowrowscalars[
r] = 1.0/coef;
981 flowcands[mcfdata->nflowcands] =
r;
982 mcfdata->nflowcands++;
990 flowrowscores[
r] += 1000.0;
994 flowrowscores[
r] += 500.0;
1001 if( ncontvars ==
rowlen )
1002 flowrowscores[
r] += 1000.0;
1004 flowrowscores[
r] += 500.0;
1006 flowrowscores[
r] += 100.0;
1014 flowrowscores[
r] += 50.0;
1016 assert(flowrowscores[
r] > 0.0);
1032 for(
i = 0;
i < mcfdata->nflowcands;
i++ )
1042 dualsol =
ABS(dualsol);
1047 assert(flowrowscores[
r] > 0.0);
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;
1080 unsigned char* capacityrowsigns;
1081 SCIP_Real* capacityrowscores;
1101 capacityrowsigns = mcfdata->capacityrowsigns;
1102 capacityrowscores = mcfdata->capacityrowscores;
1103 capacitycands = mcfdata->capacitycands;
1105 assert(mcfdata->ncapacitycands == 0);
1124 SCIPerrorMessage(
"invalid parameter value %d for model type\n", modeltype);
1131 for(
r = 0;
r < nrows;
r++ )
1155 capacityrowsigns[
r] = 0;
1156 capacityrowscores[
r] = 0.0;
1212 k = colcommodity[
c];
1213 assert(-1 <=
k &&
k < ncommodities);
1271 capacitycands[mcfdata->ncapacitycands] =
r;
1272 mcfdata->ncapacitycands++;
1275 capacityrowscores[
r] = 1.0;
1292 capacityrowscores[
r] += 1000.0;
1294 capacityrowscores[
r] += 1000.0;
1308 capacityrowscores[
r] += 500.0;
1312 capacityrowscores[
r] += 250.0;
1316 capacityrowscores[
r] += 100.0;
1320 capacityrowscores[
r] += 100.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]);
1355 SCIPdebugMsg(
scip,
"row <%s>: rowsign = %d nposflowcoefs = %d nnegflowcoefs = %d -> discard\n",
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];
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);
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++;
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);
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;
1556 assert(rowcommodity[
r] == -1);
1565 commoditysigns[
k] = +1;
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;
1632 if( colcommodity[
c] == -1 )
1637 colcommodity[
c] =
k;
1638 newcols[mcfdata->nnewcols] =
c;
1639 mcfdata->nnewcols++;
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);
1694 assert(mcfdata->rowcommodity[
r] ==
k);
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;
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++;
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;
1844 if( rowcommodity[
r] != -1 )
1868 if( colcommodity[
rowc] ==
k )
1871 if( plusflow[
rowc] )
1885 if( minusflow[
rowc] )
1900 else if( colcommodity[
rowc] != -1 )
1920 if( commoditysigns ==
NULL || commoditysigns[
k] == 0 )
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;
1973 while( mcfdata->nnewcols > 0 )
1986 c = newcols[mcfdata->nnewcols-1];
1987 mcfdata->nnewcols--;
1991 assert(plusflow[
c] || minusflow[
c]);
1992 if( plusflow[
c] && minusflow[
c] )
2022 score = flowrowscores[
r];
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++ )
2154 SCIPdebugMsg(
scip,
" -------------------start new commodity %d--------------------- \n", mcfdata->ncommodities );
2181 SCIPdebugMsg(
scip,
" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n", mcfdata->ncommodities-1,
nnodes, maxnnodes);
2197 for(
k = 0;
k < mcfdata->ncommodities;
k++ )
2209 for(
i = 0;
i < mcfdata->nflowcands;
i++ )
2213 if( rowcommodity[
r] ==
k )
2237 MCFdebugMessage(
"identified %d commodities (%d empty) with a maximum of %d nodes and %d flowrows, %d flowvars \n",
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++ )
2314 r = capacitycands[
i];
2326 assert(capacityrowscores[
r] > 0.0);
2333 assert( rowcommodity[
r] == -1 );
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 )
2367 SCIPdebugMsg(
scip,
"discarding capacity candidate row %d <%s> [score:%g]: %d assigned flowvars, %d unassigned flowvars\n",
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",
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;
2483 if( colcommodity[
caprowc] == -1 )
2499 newcols[mcfdata->nnewcols] =
caprowc;
2500 mcfdata->nnewcols++;
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;
2697 *score =
MAX(*score, 1
e-6);
2700 SCIPdebugMsg(
scip,
" -> node similarity: row <%s>: incompatible=%u overlap=%g rowlen=%d baserowlen=%d score=%g\n",
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;
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++ )
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",
2804 rownodeid[
r] = mcfdata->nnodes;
2812 if(ncommodities == 1)
2861 for(
i = 0;
i < ncommodities;
i++ )
2877 for(
i = 0;
i < mcfdata->nnewcols;
i++ )
2886 assert(mcfdata->colcommodity[
c] >= 0);
2891 colisincident[
c] =
FALSE;
2923 if( rownodeid[
colr] >= 0 )
2942 for(
i = 0;
i < ncommodities;
i++ )
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;
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 )
3056 if( rownodeid[
r] >= 0 )
3063 k = rowcommodity[
r];
3074 if( commoditysigns[
k] == -1 )
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;
3139 assert(mcfdata->nemptycommodities == 0);
3140 assert(ncommodities >= 0);
3144 if( ncommodities == 0 || nflowcands == 0 ||
nnodes == 0 )
3165 for( n = 0; n < nflowcands; n++ )
3177 for( v = 0; v <
nnodes; v++ )
3193 for( n = 0; n < nflowcands; n++ )
3206 for( v = 0; n < nflowcands; v++ )
3230 assert(mcfdata->rowarcid[
r] == -1);
3248 assert(rowcommodity[
r] == colcommodity[
c]);
3258 else if(
arcid == -1 )
3270 assert(s == v || t == v);
3281 if( s < 0 || t < 0 )
3349 assert(s == v || t == v);
3386 assert(s == v || t == v);
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;
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);
3540 if( colcommodity[
c] >= 0 && colarcid[
c] ==
a )
3542 assert(colcommodity[
c] < ncommodities);
3548 for(
k = 0;
k < ncommodities;
k++ )
3557 for(
k = 0;
k < ncommodities;
k++ )
3570 for(
k = 0;
k < ncommodities;
k++ )
3603 for(
c = 0;
c < ncols;
c++ )
3605 if( colcommodity[
c] >= 0 )
3608 assert(colcommodity[
c] < mcfdata->ncommodities);
3609 colcommodity[
c] = perm[colcommodity[
c]];
3611 if( colcommodity[
c] == -1 )
3616 else if( colarcid[
c] >= 0 )
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]];
3634 if( rowcommodity[
r] == -1 )
3659 capacityrows[
newnarcs] = capacityrows[
a];
3670 rowarcid[
r] = perm[
a];
3678 for(
c = 0;
c < ncols;
c++ )
3680 if( colarcid[
c] >= 0 )
3682 colarcid[
c] = perm[colarcid[
c]];
3702 for( v = 0; v <
nnodes; v++ )
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]];
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;
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;
3902 if( colarcid[
c] >= 0 )
3904 int k = colcommodity[
c];
3905 assert (0 <=
k &&
k < ncommodities);
3918 capacityrows[
a] =
NULL;
3933 if( colarcid[
c] >= 0 )
3935 int k = colcommodity[
c];
3940 assert (0 <=
k &&
k < ncommodities);
4057 SCIPdebugMsg(
scip,
"arc %d: %d -> %d (len=%d, sourcecnt=%g/%g, targetcnt=%g/%g, %g/%g inconsistencies)\n",
4079 MCFdebugMessage(
" -> reached maximal number of inconsistencies: %g > %g\n",
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;
4175 for(
a = firstoutarcs[v];
a != -1;
a = nextoutarcs[
a] )
4204 for(
a = firstinarcs[v];
a != -1;
a = nextinarcs[
a] )
4267 *mcfnetworks =
NULL;
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 )
4378 if( mcfdata.ncapacitycands == 0 )
4440 for( v = 0; v < mcfdata.nnodes; v++ )
4444 for( v = 0; v < mcfdata.nnodes; v++ )
4484 for(
i = *nmcfnetworks;
i > 0 &&
mcfnetwork->nnodes > (*mcfnetworks)[
i-1]->nnodes;
i-- )
4485 (*mcfnetworks)[
i] = (*mcfnetworks)[
i-1];
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);
4547#ifdef COUNTNETWORKVARIABLETYPES
4583 for(
c=0;
c < ncols;
c++)
4588 for(m=0; m < nmcfnetworks; m++)
4597 int* colcommodity =
mcfnetwork->colcommodity;
4600 for(
c=0;
c < ncols;
c++)
4635 row = arccapacityrows[
a];
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",
4697 MCFdebugMessage(
" nof capvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n",
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,
4862 source = nodepair->node1;
4863 target = nodepair->node2;
4892#ifdef BETTERWEIGHTFORDEMANDNODES
4895 SCIP_Real** nodeflowscales;
4896 SCIP_Real maxweight;
4897 SCIP_Real minweight;
4914#ifdef BETTERWEIGHTFORDEMANDNODES
4965 if( nodepair.node1 == -1 || nodepair.node2 == -1 )
4985 slack =
MAX(slack, 0.0);
5006 if(colcommodity[
c] >= 0)
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
5029 nodepair.weight =
MIN( nodepair.weight, -0.0001);
5032#ifdef USECAPACITYFORTIEBREAKING
5035 nodepair.weight +=
totalcap * scale;
5036 nodepair.weight =
MIN( nodepair.weight, -0.0001);
5054 SCIPdebugMsg(
scip,
"nodepair known [%d,%d] -- old weight:%g -- new weight:%g\n", nodepair.node1,nodepair.node2,
nodepairptr->weight,
5061 nodepairs = (*nodepairqueue)->nodepairs;
5067 SCIPdebugMsg(
scip,
"new nodepair [%d,%d]-- weight:%g\n", nodepair.node1, nodepair.node2, nodepair.weight);
5078#ifdef BETTERWEIGHTFORDEMANDNODES
5086 nodepairs = (*nodepairqueue)->nodepairs;
5091 maxweight =
MAX(maxweight, nodepairs[n].weight);
5093 minweight =
MIN(minweight, nodepairs[n].weight);
5105 int node1 = nodepairs[n].node1;
5106 int node2 = nodepairs[n].node2;
5108#ifdef BETTERWEIGHTFORDEMANDNODES
5115 SCIPdebugMsg(
scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
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 )
5169 nodepairs[n].weight += maxweight;
5176 nodepairs[n].weight += minweight;
5179 SCIPdebugMsg(
scip,
"nodepair [%d,%d] weight %g\n", node1,node2,nodepairs[n].weight);
5281 (*nodepartition)->nclusters = 0;
5302 node1 = nodepair->node1;
5303 node2 = nodepair->node2;
5319 SCIPdebugMsg(
scip,
"shrinking nodepair (%d,%d) with weight %g: join representatives %d and %d\n",
5326 assert((*nodepartition)->representatives[0] == 0);
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;
5380 (*nodepartition)->clusterbegin[(*nodepartition)->nclusters] =
mcfnetwork->nnodes;
5386 c = (*nodepartition)->nodeclusters[v];
5387 assert(0 <=
c &&
c < (*nodepartition)->nclusters);
5389 assert(pos < (*nodepartition)->clusterbegin[
c+1]);
5390 (*nodepartition)->clusternodes[pos] = v;
5435 if( nodepartition ==
NULL )
5442 cluster = nodepartition->nodeclusters[v];
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];
5521 if( ncomponents <= 2 )
5531 assert(ncomponents >= 2);
5533 return (ncomponents == 2);
5544 for(
c = 0;
c < nodepartition->nclusters;
c++ )
5549 for(
i = nodepartition->clusterbegin[
c];
i < nodepartition->clusterbegin[
c+1];
i++ )
5573 if( nodepartition ==
NULL )
5578 file =
fopen(filename,
"w");
5588 fprintf(file,
" hierarchic 1\n");
5589 fprintf(file,
" label \"\"\n");
5590 fprintf(file,
" directed 1\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");
5619 fprintf(file,
" LabelGraphics\n");
5622 fprintf(file,
" fontSize 13\n");
5623 fprintf(file,
" fontName \"Dialog\"\n");
5624 fprintf(file,
" anchor \"c\"\n");
5637 fprintf(file,
" label \"?\"\n");
5642 fprintf(file,
" type \"ellipse\"\n");
5643 fprintf(file,
" fill \"#FFFFFF\"\n");
5644 fprintf(file,
" outline \"#000000\"\n");
5646 fprintf(file,
" LabelGraphics\n");
5648 fprintf(file,
" text \"?\"\n");
5649 fprintf(file,
" fontSize 13\n");
5650 fprintf(file,
" fontName \"Dialog\"\n");
5651 fprintf(file,
" anchor \"c\"\n");
5659 fprintf(file,
" label \"Partition S\"\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");
5671 fprintf(file,
" LabelGraphics\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");
5682 fprintf(file,
" isGroup 1\n");
5689 fprintf(file,
" label \"Partition T\"\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");
5701 fprintf(file,
" LabelGraphics\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");
5712 fprintf(file,
" isGroup 1\n");
5762 fprintf(file,
" fill \"#000000\"\n");
5764 fprintf(file,
" fill \"#FF0000\"\n");
5766 fprintf(file,
" style \"dashed\"\n");
5768 fprintf(file,
" targetArrow \"standard\"\n");
5770 fprintf(file,
" LabelGraphics\n");
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,
5890 SCIP_Real** nodeflowscales =
mcfnetwork->nodeflowscales;
5891 SCIP_Bool** nodeflowinverted =
mcfnetwork->nodeflowinverted;
5893 SCIP_Real* arccapacityscales =
mcfnetwork->arccapacityscales;
5894 int* colcommodity =
mcfnetwork->colcommodity;
5913 SCIP_Real* rowweights;
5932 maxsepacuts =
sepadata->maxsepacutsroot;
5934 maxsepacuts =
sepadata->maxsepacuts;
5935 if( maxsepacuts < 0 )
5941 maxtestdelta =
sepadata->maxtestdelta;
5942 if( maxtestdelta <= 0 )
5979 if( nodepartition ==
NULL )
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);
6016 SCIP_Real bestefficacy;
6019 if(
sepadata->checkcutshoreconnectivity )
6027 SCIPdebugMsg(
scip,
" -> either shore S or shore T is not connected - skip partition.\n");
6034 if( nodepartition ==
NULL )
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] )
6096 SCIPdebugMsg(
scip,
" -> shore S or T has only one node - skip partition.\n");
6103 for(
k = 0;
k < ncommodities;
k++ )
6113 for(
k = 0;
k < ncommodities;
k++ )
6121 if(
k == ncommodities )
6166 if( arccapacityrows[
a] ==
NULL )
6180 if( arcsources[
a] == -1 || arctargets[
a] == -1 )
6195 rowweights[
r] = arccapacityscales[
a];
6202 if( rowweights[
r] > 0.0 )
6217 coef =
rowvals[
j] * arccapacityscales[
a];
6223 k = colcommodity[
c];
6239 while( left <= right )
6241 int mid = (left+right)/2;
6278 for( v = 0; v <
nnodes; v++ )
6281 for(
k = 0;
k < ncommodities;
k++ )
6332 if( nodeflowrows[v][
k] ==
NULL )
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 )
6401 SCIP_CALL(
SCIPcalcMIR(
scip,
sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal,
sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
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 )
6475 if( arccapacityrows[
a] ==
NULL )
6486 if( rowweights[
r] == 0.0 )
6529 if( colcommodity[
c] >= 0 )
6552 if( colcommodity[
c] >= 0 )
6560 SCIPdebugMsg(
scip,
" -> discarding capacity row <%s> of weight %g and slack %g: increases MIR violation by %g\n",
6563 rowweights[
r] = 0.0;
6589 SCIP_CALL(
SCIPcalcMIR(
scip,
sol,
POSTPROCESS,
BOUNDSWITCH,
USEVBDS, allowlocal,
sepadata->fixintegralrhs,
NULL,
NULL,
MINFRAC,
MAXFRAC,
6597 SCIP_CALL(
addCut(
scip, sepa,
sepadata,
sol,
cutcoefs,
cutrhs,
cutinds,
cutnnz,
cutislocal,
cutrank, ncuts,
cutoff) );
6624 SCIP_Bool allowlocal,
6654 if( ncols !=
nvars )
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++ )
6742 MCFdebugMessage(
"MCF network has %d nodes and %d arcs. arc node ratio %.2f exceed --> exit\n",
6748 if(
sepadata->separatesinglenodecuts )
6769 MCFdebugMessage(
"MCF network has %d nodes, %d arcs, %d commodities. Found %d MCF network cuts, cutoff = %u.\n",
6778 else if( ncuts > 0 )
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
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