RetroSearch Browse

);

312

(*mcfnetwork)->nodeflowrows =

;

313

(*mcfnetwork)->nodeflowscales =

;

314

(*mcfnetwork)->nodeflowinverted =

;

315

(*mcfnetwork)->arccapacityrows =

;

316

(*mcfnetwork)->arccapacityscales =

;

317

(*mcfnetwork)->arcsources =

;

318

(*mcfnetwork)->arctargets =

;

319

(*mcfnetwork)->colcommodity =

;

320

(*mcfnetwork)->nnodes = 0;

321

(*mcfnetwork)->nuncapacitatedarcs = 0;

322

(*mcfnetwork)->narcs = 0;

323

(*mcfnetwork)->ncommodities = 0;

335

assert(mcfnetwork !=

);

337 if

( *mcfnetwork !=

)

342 for

( v = 0; v < (*mcfnetwork)->nnodes; v++ )

346 for

( k = 0; k < (*mcfnetwork)->ncommodities; k++ )

348 if

( (*mcfnetwork)->nodeflowrows[v][k] !=

)

357 for

(

= 0;

< (*mcfnetwork)->narcs;

++ )

359 if

( (*mcfnetwork)->arccapacityrows[

] !=

)

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;

411 int

ncompcommodities;

418

assert(mcfnetwork !=

);

420

assert(2 <= ncompnodes && ncompnodes <= mcfdata->

);

421

assert(1 <= ncomparcs && ncomparcs <= mcfdata->

);

422

assert(ncommodities > 0);

426 for

( v = 0; v < mcfdata->nnodes; v++ )

427

assert(compnodeid[v] == -1);

438 for

( k = 0; k < ncommodities; k++ )

439

compcommodity[k] = -1;

446 for

( i = 0; i < ncompnodes; i++ )

449

assert(0 <= v && v < mcfdata->

);

454

ncompcommodities = 0;

455 for

( i = 0; i < nflowcands; i++ )

461

assert(0 <=

< nrows);

464 if

( rv >= 0 && compnodeid[rv] >= 0 )

466

k = rowcommodity[

];

467

assert(0 <= k && k < ncommodities);

468 if

( compcommodity[k] == -1 )

470

compcommodity[k] = ncompcommodities;

481

mcfnetwork->

= ncompnodes;

482

mcfnetwork->

= ncomparcs;

490 for

( v = 0; v < mcfnetwork->

; v++ )

508 for

(

= 0;

< mcfnetwork->

;

++ )

518 for

( i = 0; i < nflowcands; i++ )

524

assert(0 <=

< nrows);

527 if

( rv >= 0 && compnodeid[rv] >= 0 )

533

rk = rowcommodity[

];

534

assert(v < mcfnetwork->

);

535

assert(0 <= rk && rk < ncommodities);

538

k = compcommodity[rk];

539

assert(0 <= k && k < mcfnetwork->ncommodities);

544

scale = flowrowscalars[

];

547 if

( commoditysigns[rk] == -1 )

555 for

(

= 0;

< mcfnetwork->

;

++ )

565

globala = comparcs[

];

566

capacityrow = capacityrows[globala];

571 if

( capacityrow !=

)

574

assert(0 <=

< nrows);

576

assert((capacityrowsigns[

] &

) == 0);

577

assert(mcfdata->rowarcid[

] == globala);

595 for

( j = 0; j < rowlen; j++ )

602 if

( comdemands[k] != 0.0 )

617 for

( j = 0; j < rowlen; j++ )

622 if

( k >= 0 && comdemands[k] == 0.0 )

634 if

( mcfdata->arcsources[globala] >= 0 )

636

assert(mcfdata->arcsources[globala] < mcfdata->nnodes);

637

assert(0 <= compnodeid[mcfdata->arcsources[globala]] && compnodeid[mcfdata->arcsources[globala]] < mcfnetwork->

);

638

mcfnetwork->

arcsources

[

] = compnodeid[mcfdata->arcsources[globala]];

640 if

( mcfdata->arctargets[globala] >= 0 )

642

assert(mcfdata->arctargets[globala] < mcfdata->nnodes);

643

assert(0 <= compnodeid[mcfdata->arctargets[globala]] && compnodeid[mcfdata->arctargets[globala]] < mcfnetwork->

);

644

mcfnetwork->

arctargets

[

] = compnodeid[mcfdata->arctargets[globala]];

649 for

( c = 0; c < ncols; c++ )

659 for

( i = 0; i < ncompnodes; i++ )

661

assert(0 <= compnodes[i] && compnodes[i] < mcfdata->nnodes);

662

assert(compnodeid[compnodes[i]] == i);

663

compnodeid[compnodes[i]] = -1;

680 if

( mcfnetwork ==

)

687 for

( v = 0; v < mcfnetwork->

; v++ )

706 for

(

= 0;

< mcfnetwork->

;

++ )

722void

printCommodities(

727 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

728 unsigned char

* capacityrowsigns = mcfdata->capacityrowsigns;

729 int

ncommodities = mcfdata->ncommodities;

730 int

* commoditysigns = mcfdata->commoditysigns;

731 int

* colcommodity = mcfdata->colcommodity;

732 int

* rowcommodity = mcfdata->rowcommodity;

733 int

* colarcid = mcfdata->colarcid;

734 int

* rownodeid = mcfdata->rownodeid;

735 int nnodes

= mcfdata->nnodes;

736 SCIP_ROW

** capacityrows = mcfdata->capacityrows;

752 for

( k = 0; k < ncommodities; k++ )

754 MCFdebugMessage

(

"commodity %d (sign: %+d):\n"

, k, commoditysigns[k]);

756 for

( c = 0; c < ncols; c++ )

758 if

( colcommodity[c] == k )

761 for

(

= 0;

< nrows;

++ )

763 if

( rowcommodity[

] == k )

766

(flowrowsigns[

] &

) != 0 ? -1 : +1);

771 if

( rownodeid !=

)

775 for

( v = 0; v <

; v++ )

778 for

(

= 0;

< nrows;

++ )

780 if

( rownodeid[

] == v )

783

(flowrowsigns[

] &

) != 0 ? -1 : +1);

789

assert(capacityrows !=

|| mcfdata->narcs == 0);

792 for

(

= 0;

< mcfdata->narcs;

++ )

795 if

( capacityrows[

] !=

)

798

assert(0 <=

< nrows);

809

assert(colcommodity !=

|| ncols == 0);

812 for

( c = 0; c < ncols; c++ )

814 if

( colcommodity[c] == -1 )

823 for

(

= 0;

< nrows;

++ )

825

assert(rowcommodity !=

);

843 if

( rowscores[ind2] < rowscores[ind1] )

845 else if

( rowscores[ind2] > rowscores[ind1] )

858 unsigned char

* flowrowsigns;

878

flowrowsigns = mcfdata->flowrowsigns;

879

flowrowscalars = mcfdata->flowrowscalars;

880

flowrowscores = mcfdata->flowrowscores;

881

flowcands = mcfdata->flowcands;

883

assert(mcfdata->nflowcands == 0);

886 for

(

= 0;

< nrows;

++ )

911

absdualsol =

(absdualsol);

913

flowrowsigns[

] = 0;

914

flowrowscalars[

] = 0.0;

915

flowrowscores[

] = 0.0;

936

coef =

(rowvals[0]);

943 for

( i = 0; i < rowlen; i++ )

949

hasposcoef = hasposcoef || (rowvals[i] > 0.0);

950

hasnegcoef = hasnegcoef || (rowvals[i] < 0.0);

980

flowrowscalars[

] = 1.0/coef;

981

flowcands[mcfdata->nflowcands] =

;

982

mcfdata->nflowcands++;

990

flowrowscores[

] += 1000.0;

993 if

( hasposcoef && hasnegcoef )

994

flowrowscores[

] += 500.0;

1001 if

( ncontvars == rowlen )

1002

flowrowscores[

] += 1000.0;

1003 else if

( nintvars + nimplintvars == rowlen )

1004

flowrowscores[

] += 500.0;

1005 else if

( nbinvars == rowlen )

1006

flowrowscores[

] += 100.0;

1010

flowrowscores[

] += 10.0*rowlen/(rowlen+10.0);

1014

flowrowscores[

] += 50.0;

1016

assert(flowrowscores[

] > 0.0);

1019

maxdualflow =

(maxdualflow, absdualsol);

1032 for

( i = 0; i < mcfdata->nflowcands; i++ )

1037

assert(0 <=

< nrows);

1042

dualsol =

(dualsol);

1045

assert(maxdualflow > 0.0);

1046

flowrowscores[

] += dualsol/maxdualflow + 1.0;

1047

assert(flowrowscores[

] > 0.0);

1052 SCIPsortInd

(mcfdata->flowcands, compCands, (

void

*)flowrowscores, mcfdata->nflowcands);

1054 MCFdebugMessage

(

"flow conservation candidates [%d]\n"

, mcfdata->nflowcands);

1056 for

(

= 0;

< mcfdata->nflowcands;

++ )

1059 SCIPdebugMsg

(

"%4d [score: %2g]: %s\n"

, mcfdata->flowcands[

], flowrowscores[mcfdata->flowcands[

]],

1074 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

1075 int

* colcommodity = mcfdata->colcommodity;

1076 int

ncommodities = mcfdata->ncommodities;

1077 int

nactivecommodities = mcfdata->ncommodities - mcfdata->nemptycommodities;

1080 unsigned char

* capacityrowsigns;

1082 int

* capacitycands;

1089 int

maxcolspercommoditylimit;

1090 int

*ncolspercommodity;

1091 int

*maxcolspercommodity;

1101

capacityrowsigns = mcfdata->capacityrowsigns;

1102

capacityrowscores = mcfdata->capacityrowscores;

1103

capacitycands = mcfdata->capacitycands;

1105

assert(mcfdata->ncapacitycands == 0);

1112 switch

( modeltype )

1115

maxcolspercommoditylimit = 2;

1118

maxcolspercommoditylimit = 1;

1121

maxcolspercommoditylimit = 2;

1124 SCIPerrorMessage

(

"invalid parameter value %d for model type\n"

, modeltype);

1128

maxdualcapacity = 0.0;

1129

directedcandsscore = 0.0;

1130

undirectedcandsscore = 0.0;

1131 for

(

= 0;

< nrows;

++ )

1141 int

nposcapacitycoefs;

1142 int

nnegcapacitycoefs;

1144 int

ncoveredcommodities;

1149 unsigned char

rowsign;

1155

capacityrowsigns[

] = 0;

1156

capacityrowscores[

] = 0.0;

1175

absdualsol =

(absdualsol);

1184

maxcolspercommodity[

] = 0;

1189

nposcapacitycoefs = 0;

1190

nnegcapacitycoefs = 0;

1192

ncoveredcommodities = 0;

1194

sameabsflowcoef = 0.0;

1195

maxabscapacitycoef = 0.0;

1202 for

( i = 0; i < rowlen; i++ )

1209

assert(colcommodity !=

);

1212

k = colcommodity[c];

1213

assert(-1 <= k && k < ncommodities);

1218

abscoef =

(rowvals[i]);

1219 if

( sameflowcoef == 0.0 )

1220

sameflowcoef = rowvals[i];

1221 else if

( !

SCIPisEQ

(

, sameflowcoef, rowvals[i]) )

1223 if

( sameabsflowcoef == 0.0 )

1224

sameabsflowcoef = abscoef;

1225 else if

( !

SCIPisEQ

(

, sameabsflowcoef, abscoef) )

1228 if

( rowvals[i] > 0.0 )

1234 if

( ncolspercommodity[k] == 0 )

1235

ncoveredcommodities++;

1236

ncolspercommodity[k]++;

1237

maxcolspercommodity[

] =

(maxcolspercommodity[

], ncolspercommodity[k]);

1239 if

( ncolspercommodity[k] >= 2 )

1248

abscoef =

(rowvals[i]);

1249 if

( abscoef > maxabscapacitycoef )

1250

maxabscapacitycoef = abscoef;

1253 if

( rowvals[i] > 0.0 )

1254

nposcapacitycoefs++;

1256

nnegcapacitycoefs++;

1266 if

( rowsign != 0 && nposflowcoefs + nnegflowcoefs > 0 )

1270

capacityrowsigns[

] |= rowsign;

1271

capacitycands[mcfdata->ncapacitycands] =

;

1272

mcfdata->ncapacitycands++;

1275

capacityrowscores[

] = 1.0;

1279

assert(ncoveredcommodities > 0);

1281

commodityexcessratio =

1282 ABS

((nposflowcoefs + nnegflowcoefs)/(

)ncoveredcommodities - maxcolspercommoditylimit);

1284

capacityrowscores[

] += 1000.0 *

(0.0, 2.0 - commodityexcessratio);

1291 if

( (capacityrowsigns[

] &

RHSPOSSIBLE

) != 0 && nnegflowcoefs == 0 && nposcapacitycoefs == 0 && nnegcapacitycoefs > 0 )

1292

capacityrowscores[

] += 1000.0;

1293 if

( (capacityrowsigns[

] &

LHSPOSSIBLE

) != 0 && nposflowcoefs == 0 && nposcapacitycoefs > 0 && nnegcapacitycoefs == 0 )

1294

capacityrowscores[

] += 1000.0;

1303

assert(nactivecommodities + 3 > 0);

1304

capacityrowscores[

] += 2000.0 * ncoveredcommodities/(

)(nactivecommodities + 3);

1308

capacityrowscores[

] += 500.0;

1312

capacityrowscores[

] += 250.0;

1316

capacityrowscores[

] += 100.0;

1319 if

( maxabscapacitycoef > 0.0 && !

SCIPisEQ

(

, maxabscapacitycoef, 1.0) )

1320

capacityrowscores[

] += 100.0;

1323

capacityrowscores[

] += 20.0 *

(nposflowcoefs, nnegflowcoefs)/

(1.0,(

)(nposflowcoefs + nnegflowcoefs));

1326

capacityrowscores[

] += 10.0 *

(nposcapacitycoefs, nnegcapacitycoefs)/(

)(nposcapacitycoefs+nnegcapacitycoefs+1.0);

1330

capacityrowscores[

] += 10.0;

1334

capacityrowscores[

] += 10.0;

1336

assert(capacityrowscores[

] > 0.0);

1337 SCIPdebugMsg

(

"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[

], capacityrowsigns[

], nposflowcoefs, nnegflowcoefs, nposcapacitycoefs, nnegcapacitycoefs, nbadcoefs, nactivecommodities, sameflowcoef, capacityrowscores[

]);

1341

maxdualcapacity =

(maxdualcapacity, absdualsol);

1346

assert(maxcolspercommoditylimit == 2);

1348

undirectedcandsscore += capacityrowscores[

];

1350

directedcandsscore += capacityrowscores[

];

1355 SCIPdebugMsg

(

"row <%s>: rowsign = %d nposflowcoefs = %d nnegflowcoefs = %d -> discard\n"

1363 if

( directedcandsscore > undirectedcandsscore )

1368 MCFdebugMessage

(

"detected model type: %s (%g directed score, %g undirected score)\n"

1376 for

( i = 0; i < mcfdata->ncapacitycands; i++ )

1378 r

= capacitycands[i];

1379

assert(0 <=

< nrows);

1383 if

( maxcolspercommodity[

] <= maxcolspercommoditylimit )

1384

capacityrowscores[

] -= 1000.0;

1390

mcfdata->modeltype = modeltype;

1398 for

( i = 0; i < mcfdata->ncapacitycands; i++ )

1402 r

= capacitycands[i];

1403

assert(0 <=

< nrows);

1408

dualsol =

(dualsol);

1411

assert(maxdualcapacity > 0.0);

1412

capacityrowscores[

] +=

(dualsol, 0.0)/maxdualcapacity;

1413

assert(capacityrowscores[

] > 0.0);

1418 SCIPsortInd

(mcfdata->capacitycands, compCands, (

void

*)capacityrowscores, mcfdata->ncapacitycands);

1420 MCFdebugMessage

(

"capacity candidates [%d]\n"

, mcfdata->ncapacitycands);

1422 for

(

= 0;

< mcfdata->ncapacitycands;

++ )

1424 SCIPdebugMsg

(

"row %4d [score: %2g]: %s\n"

, mcfdata->capacitycands[

1425

capacityrowscores[mcfdata->capacitycands[

]],

(rows[mcfdata->capacitycands[

]]));

1445

assert(mcfdata->ncommodities <= mcfdata->commoditysignssize);

1446 if

( mcfdata->ncommodities == mcfdata->commoditysignssize )

1448

mcfdata->commoditysignssize =

(2*mcfdata->commoditysignssize, mcfdata->ncommodities+1);

1451

assert(mcfdata->ncommodities < mcfdata->commoditysignssize);

1454 SCIPdebugMsg

(

"**** creating new commodity %d ****\n"

, mcfdata->ncommodities);

1455

mcfdata->commoditysigns[mcfdata->ncommodities] = 0;

1456

mcfdata->ncommodities++;

1471

assert(source != target );

1472

assert(0 <= source && source < mcfdata->

);

1473

assert(0 <= target && target < mcfdata->

);

1474

assert(newarcid !=

);

1476

*newarcid = mcfdata->narcs;

1479

assert(mcfdata->narcs <= mcfdata->arcarraysize);

1480 if

( mcfdata->narcs == mcfdata->arcarraysize )

1482

mcfdata->arcarraysize =

(2*mcfdata->arcarraysize, mcfdata->narcs+1);

1488

assert(mcfdata->narcs < mcfdata->arcarraysize);

1491 if

( mcfdata->capacityrowssize < mcfdata->arcarraysize )

1493

mcfdata->capacityrowssize = mcfdata->arcarraysize;

1496

assert(mcfdata->narcs < mcfdata->capacityrowssize);

1499 SCIPdebugMsg

(

"**** creating new arc %d: %d -> %d ****\n"

, mcfdata->narcs, source, target);

1501

mcfdata->arcsources[*newarcid] = source;

1502

mcfdata->arctargets[*newarcid] = target;

1503

mcfdata->nextoutarcs[*newarcid] = mcfdata->firstoutarcs[source];

1504

mcfdata->firstoutarcs[source] = *newarcid;

1505

mcfdata->nextinarcs[*newarcid] = mcfdata->firstinarcs[target];

1506

mcfdata->firstinarcs[target] = *newarcid;

1507

mcfdata->capacityrows[*newarcid] =

;

1520 unsigned char

rowsign,

1525 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

1526 SCIP_Bool

* plusflow = mcfdata->plusflow;

1527 SCIP_Bool

* minusflow = mcfdata->minusflow;

1528 int

ncommodities = mcfdata->ncommodities;

1529 int

* commoditysigns = mcfdata->commoditysigns;

1530 int

* colcommodity = mcfdata->colcommodity;

1531 int

* rowcommodity = mcfdata->rowcommodity;

1532 int

* newcols = mcfdata->newcols;

1543

assert(comcolids !=

);

1544

assert(ncomcolids !=

);

1553

invertrow = ((rowsign &

) != 0);

1554

rowsign &= ~INVERTED;

1556

assert(rowcommodity[

] == -1);

1557

assert((flowrowsigns[

] | rowsign) == flowrowsigns[

]);

1559

assert(rowsign != 0);

1565

commoditysigns[k] = +1;

1581 if

( dualsol > 0.0 )

1594 else if

( rowlhs > 0.0 )

1611

flowrowsigns[

] |= rowsign;

1613 SCIPdebugMsg

(

"adding flow row %d <%s> with sign %+d%s to commodity %d [score:%g]\n"

1615

k, mcfdata->flowrowscores[

]);

1619

rowcommodity[

] = k;

1623 for

( i = 0; i < rowlen; i++ )

1632 if

( colcommodity[c] == -1 )

1634

assert(!plusflow[c]);

1635

assert(!minusflow[c]);

1637

colcommodity[c] = k;

1638

newcols[mcfdata->nnewcols] = c;

1639

mcfdata->nnewcols++;

1640

comcolids[*ncomcolids] = c;

1643

assert(colcommodity[c] == k);

1646

val = rowscale * rowvals[i];

1649

assert(!plusflow[c]);

1650

plusflow[c] =

;

1654

assert(!minusflow[c]);

1655

minusflow[c] =

;

1672 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

1673 SCIP_Bool

* plusflow = mcfdata->plusflow;

1674 SCIP_Bool

* minusflow = mcfdata->minusflow;

1678

assert(mcfdata->commoditysigns[k] == 0);

1679

assert(comrows !=

|| ncomrows == 0);

1680

assert(comcolids !=

);

1683 for

( i = 0; i < ncomrows; i++ )

1687 unsigned char

rowsign;

1689

assert(comrows !=

);

1691

assert( row !=

);

1694

assert(mcfdata->rowcommodity[

] == k);

1698

rowsign = flowrowsigns[

];

1700

assert((rowsign &

) == 0);

1710 for

( i = 0; i < ncomcolids; i++ )

1717

assert(mcfdata->colcommodity[c] == k);

1720

plusflow[c] = minusflow[c];

1737 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

1738 SCIP_Bool

* plusflow = mcfdata->plusflow;

1739 SCIP_Bool

* minusflow = mcfdata->minusflow;

1740 int

ncommodities = mcfdata->ncommodities;

1741 int

* colcommodity = mcfdata->colcommodity;

1742 int

* rowcommodity = mcfdata->rowcommodity;

1746

assert(0 <= k && k < ncommodities);

1748

assert( ndelflowrows !=

);

1749

assert( ndelflowvars !=

);

1751 SCIPdebugMsg

(

"deleting commodity %d (%d total commodities) with %d flow rows\n"

, k, ncommodities, nrows);

1756 for

( n = 0; n < nrows; n++ )

1767

assert(rowcommodity[

] == k);

1776

rowcommodity[

] = -1;

1779 for

( i = 0; i < rowlen; i++ )

1787

assert(colcommodity[c] == k || colcommodity[c] == -1);

1788 if

(colcommodity[c] == k)

1790

colcommodity[c] = -1;

1793

plusflow[c] =

;

1794

minusflow[c] =

;

1803 if

( k == ncommodities-1 )

1804

mcfdata->ncommodities--;

1806

mcfdata->nemptycommodities++;

1816 unsigned char

* rowsign,

1820 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

1821 SCIP_Bool

* plusflow = mcfdata->plusflow;

1822 SCIP_Bool

* minusflow = mcfdata->minusflow;

1823 int

* colcommodity = mcfdata->colcommodity;

1824 int

* rowcommodity = mcfdata->rowcommodity;

1825 int

* commoditysigns = mcfdata->commoditysigns;

1830 unsigned char

flowrowsign;

1831 unsigned char

invflowrowsign;

1835

assert(invertcommodity !=

);

1838

*invertcommodity =

;

1844 if

( rowcommodity[

] != -1 )

1848

flowrowsign = flowrowsigns[

];

1854

invflowrowsign = flowrowsign;

1860 for

( j = 0; j < rowlen && (flowrowsign != 0 || invflowrowsign != 0); j++ )

1868 if

( colcommodity[rowc] == k )

1871 if

( plusflow[rowc] )

1874 if

( rowvals[j] > 0.0 )

1876

flowrowsign &= ~RHSPOSSIBLE;

1877

invflowrowsign &= ~LHSPOSSIBLE;

1881

flowrowsign &= ~LHSPOSSIBLE;

1882

invflowrowsign &= ~RHSPOSSIBLE;

1885 if

( minusflow[rowc] )

1888 if

( rowvals[j] > 0.0 )

1890

flowrowsign &= ~LHSPOSSIBLE;

1891

invflowrowsign &= ~RHSPOSSIBLE;

1895

flowrowsign &= ~RHSPOSSIBLE;

1896

invflowrowsign &= ~LHSPOSSIBLE;

1900 else if

( colcommodity[rowc] != -1 )

1908 if

( flowrowsign != 0 )

1911

*rowsign = flowrowsign;

1912

*invertcommodity =

;

1914 else if

( invflowrowsign != 0 )

1920 if

( commoditysigns ==

|| commoditysigns[k] == 0 )

1923

*rowsign = invflowrowsign;

1924

*invertcommodity =

;

1929

*rowsign = (invflowrowsign |

);

1930

*invertcommodity =

;

1947 unsigned char

* nextrowsign,

1951 SCIP_Real

* flowrowscores = mcfdata->flowrowscores;

1952 SCIP_Bool

* plusflow = mcfdata->plusflow;

1953 SCIP_Bool

* minusflow = mcfdata->minusflow;

1954 int

* newcols = mcfdata->newcols;

1955 int

ncommodities = mcfdata->ncommodities;

1960

assert(nextrow !=

);

1961

assert(nextrowsign !=

);

1965

*nextinvertcommodity =

;

1970

assert(cols !=

);

1973 while

( mcfdata->nnewcols > 0 )

1979 unsigned char

bestrowsign;

1986

c = newcols[mcfdata->nnewcols-1];

1987

mcfdata->nnewcols--;

1991

assert(plusflow[c] || minusflow[c]);

1992 if

( plusflow[c] && minusflow[c] )

1998

bestinvertcommodity =

;

2003 for

( i = 0; i < collen; i++ )

2006 unsigned char

flowrowsign;

2015 if

( flowrowsign != 0 )

2022

score = flowrowscores[

];

2023

assert(score > 0.0);

2029 if

( (flowrowsign &

) != 0 )

2032 if

( score > bestscore )

2035

bestrowsign = flowrowsign;

2036

bestinvertcommodity = invertcommodity;

2046 if

( bestrow !=

)

2048

assert(bestscore > 0.0);

2049

assert(bestrowsign != 0);

2051

*nextrowsign = bestrowsign;

2052

*nextinvertcommodity = bestinvertcommodity;

2067 int

* flowcands = mcfdata->flowcands;

2094

assert(failed !=

);

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

(

= 0;

< nrows;

++ )

2121

rowcommodity[

] = -1;

2123

assert(flowcands !=

|| mcfdata->nflowcands == 0);

2134 for

( i = 0; i < mcfdata->nflowcands; i++ )

2137 unsigned char

newrowsign;

2141

assert(flowcands !=

);

2143

assert(0 <=

< nrows);

2147 getFlowrowFit

(

, mcfdata, newrow, mcfdata->ncommodities, &newrowsign, &newinvertcommodity);

2148 if

( newrowsign == 0 )

2150

assert(!newinvertcommodity);

2151

assert((newrowsign &

) == 0);

2154 SCIPdebugMsg

(

" -------------------start new commodity %d--------------------- \n"

, mcfdata->ncommodities );

2163 if

( newinvertcommodity )

2169

comrows[

] = newrow;

2176 while

( newrow !=

);

2178

ncomnodes[mcfdata->ncommodities-1] =

;

2180

nflowvars += ncomcolids;

2181 SCIPdebugMsg

(

" -> finished commodity %d: identified %d nodes, maxnnodes=%d\n"

, mcfdata->ncommodities-1,

, maxnnodes);

2190

nflowrows -= ndelflowrows;

2191

nflowvars -= ndelflowvars;

2192

assert(nflowvars >= 0);

2193

assert(nflowrows >= 0);

2197 for

( k = 0; k < mcfdata->ncommodities; k++ )

2209 for

( i = 0; i < mcfdata->nflowcands; i++ )

2211

assert(flowcands !=

);

2213 if

( rowcommodity[

] == k )

2215

comrows[

] = rows[

];

2218 if

(

== ncomnodes[k] )

2223

assert(

== ncomnodes[k]);

2225

nflowrows -= ndelflowrows;

2226

nflowvars -= ndelflowvars;

2227

assert(nflowvars >= 0);

2228

assert(nflowrows >= 0);

2237 MCFdebugMessage

(

"identified %d commodities (%d empty) with a maximum of %d nodes and %d flowrows, %d flowvars \n"

2238

mcfdata->ncommodities, mcfdata->nemptycommodities, maxnnodes, nflowrows, nflowvars);

2240

assert(nflowvars >= 0);

2241

assert(nflowrows >= 0);

2244 if

( nflowrows == 0)

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 !=

|| ncapacitycands == 0);

2294

colarcid = mcfdata->colarcid;

2295

rowarcid = mcfdata->rowarcid;

2298 for

( c = 0; c < ncols; c++ )

2300 for

(

= 0;

< nrows;

++ )

2304 for

( i = 0; i < ncapacitycands; i++ )

2309 int

nassignedflowvars;

2310 int

nunassignedflowvars;

2313

assert(capacitycands !=

);

2314 r

= capacitycands[i];

2315

assert(0 <=

< nrows );

2316

capacityrow = rows[

];

2318

assert(capacityrowsigns !=

);

2319

assert(capacityrowscores !=

);

2320

assert(rowcommodity !=

);

2321

assert(flowrowsigns !=

);

2325

assert((capacityrowsigns[

] &

DISCARDED

) == 0);

2326

assert(capacityrowscores[

] > 0.0);

2330

assert(rowarcid[

] == -1);

2333

assert( rowcommodity[

] == -1 );

2339

nassignedflowvars = 0;

2340

nunassignedflowvars = 0;

2341 for

( k = 0; k < rowlen; k++ )

2344

assert(0 <= c && c < ncols);

2345

assert(colcommodity !=

);

2347

assert(-1 <= colcommodity[c] && colcommodity[c] < mcfdata->ncommodities);

2348

assert(-1 <= colarcid[c] && colarcid[c] < mcfdata->narcs);

2351 if

( colcommodity[c] == -1 )

2355 if

( colarcid[c] >= 0 )

2356

nassignedflowvars++;

2358

nunassignedflowvars++;

2365 if

( nunassignedflowvars == 0 || nassignedflowvars >= nunassignedflowvars * 2 )

2367 SCIPdebugMsg

(

"discarding capacity candidate row %d <%s> [score:%g]: %d assigned flowvars, %d unassigned flowvars\n"

2368 r

(capacityrow), mcfdata->capacityrowscores[

], nassignedflowvars, nunassignedflowvars);

2374

assert(mcfdata->narcs <= mcfdata->capacityrowssize);

2375 if

( mcfdata->narcs == mcfdata->capacityrowssize )

2377

mcfdata->capacityrowssize =

(2*mcfdata->capacityrowssize, mcfdata->narcs+1);

2380

assert(mcfdata->narcs < mcfdata->capacityrowssize);

2381

assert(mcfdata->narcs < nrows);

2383

mcfdata->capacityrows[mcfdata->narcs] = capacityrow;

2386

assert(0 <=

< nrows);

2387

rowarcid[

] = mcfdata->narcs;

2398 SCIPdebugMsg

(

"assigning capacity row %d <%s> with sign %+d to arc %d [score:%g]: %d assigned flowvars, %d unassigned flowvars\n"

2400

mcfdata->capacityrowscores[

], nassignedflowvars, nunassignedflowvars);

2403 for

( k = 0; k < rowlen; k++ )

2406

assert(0 <= rowc && rowc < ncols);

2407

assert(colcommodity !=

);

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;

2445

assert(!colisincident[i]);

2451

mcfdata->nnewcols = 0;

2453 for

( i = 0; i < rowlen; i++ )

2465

arcid = colarcid[c];

2468

assert(arcid < mcfdata->

);

2471

assert(capacityrows[arcid] !=

);

2475 for

( j = 0; j < capacityrowlen; j++ )

2483 if

( colcommodity[caprowc] == -1 )

2485

assert(colarcid[caprowc] == -1);

2488

assert(colarcid[caprowc] <= arcid);

2491 if

( colcommodity[caprowc] == basecommodity )

2495 if

( !colisincident[caprowc] )

2498

colisincident[caprowc] =

;

2499

newcols[mcfdata->nnewcols] = caprowc;

2500

mcfdata->nnewcols++;

2514 int

* basearcpattern,

2523 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

2524 int

* commoditysigns = mcfdata->commoditysigns;

2525 int narcs

= mcfdata->narcs;

2526 int

* rowcommodity = mcfdata->rowcommodity;

2527 int

* colarcid = mcfdata->colarcid;

2528 int

* arcpattern = mcfdata->zeroarcarray;

2541 int

* overlappingarcs;

2542 int

noverlappingarcs;

2547

*invertcommodity =

;

2550 for

( i = 0; i <

; i++ )

2551

assert(arcpattern[i] == 0);

2560

rowcom = rowcommodity[

];

2561

assert(0 <= rowcom && rowcom < mcfdata->ncommodities);

2562

rowcomsign = commoditysigns[rowcom];

2563

assert(-1 <= rowcomsign && rowcomsign <= +1);

2568

incompatible =

;

2569

noverlappingarcs = 0;

2573 for

( i = 0; i < rowlen; i++ )

2583

valsign = (rowvals[i] > 0.0 ? +1 : -1);

2586 if

( (flowrowsigns[

] &

) != 0 )

2589

arcid = colarcid[c];

2598

assert(arcid <

);

2601 if

( basearcpattern[arcid] != 0 )

2608 if

( ( valsign * basearcpattern[arcid] ) > 0 )

2613 if

( rowcomsign == 0 )

2616

rowcomsign = validcomsign;

2618 else if

( rowcomsign != validcomsign )

2621

incompatible =

;

2632 if

( arcpattern[arcid] == 0 )

2634

overlappingarcs[noverlappingarcs] = arcid;

2637

arcpattern[arcid] += valsign;

2643 for

( i = 0; i < noverlappingarcs; i++ )

2649

arcid = overlappingarcs[i];

2650

assert(0 <= arcid && arcid <

);

2653

basenum =

(basearcpattern[arcid]);

2654

arcnum =

(arcpattern[arcid]);

2655

assert(basenum != 0.0);

2656

assert(arcnum != 0.0);

2658 if

( basenum > arcnum )

2659

overlap += arcnum/basenum;

2661

overlap += basenum/arcnum;

2663

arcpattern[arcid] = 0;

2667 if

( !incompatible && overlap > 0.0 )

2670 int

rowarcs = rowlen - nposuncap - nneguncap;

2671 int

baserowarcs = baserowlen - basenposuncap - basenneguncap;

2673

assert(overlap <= (

) rowlen);

2674

assert(overlap <= (

) baserowlen);

2675

assert(noverlappingarcs >= 1);

2677

*invertcommodity = (rowcomsign == -1);

2681 if

( noverlappingarcs >= 2 )

2684

assert(rowarcs >= 0 && baserowarcs >= 0 );

2687

*score = overlap - (rowarcs + baserowarcs - 2.0 * overlap)/(2.0 * ncols + 1.0);

2689

*score = overlap - (rowarcs + baserowarcs - 4.0 * overlap)/(2.0 * ncols + 1.0);

2692 if

(*invertcommodity)

2693

*score += 1.0 - (

(nneguncap - basenposuncap) +

(nposuncap - basenneguncap))/(2.0 * ncols + 1.0);

2695

*score += 1.0 - (

(nposuncap - basenposuncap) +

(nneguncap - basenneguncap))/(2.0 * ncols + 1.0);

2697

*score =

(*score, 1e-6);

2700 SCIPdebugMsg

(

" -> node similarity: row <%s>: incompatible=%u overlap=%g rowlen=%d baserowlen=%d score=%g\n"

2701 SCIProwGetName

(row), incompatible, overlap, rowlen, baserowlen, *score);

2716 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

2717 int

ncommodities = mcfdata->ncommodities;

2718 int

* commoditysigns = mcfdata->commoditysigns;

2719 int narcs

= mcfdata->narcs;

2720 int

* flowcands = mcfdata->flowcands;

2721 int

nflowcands = mcfdata->nflowcands;

2722 int

* rowcommodity = mcfdata->rowcommodity;

2723 int

* colarcid = mcfdata->colarcid;

2724 int

* newcols = mcfdata->newcols;

2745

assert(mcfdata->nnodes == 0);

2757

rownodeid = mcfdata->rownodeid;

2758

colisincident = mcfdata->colisincident;

2768 for

(

= 0;

< nrows;

++ )

2769

rownodeid[

] = -1;

2770 for

( c = 0; c < ncols; c++ )

2771

colisincident[c] =

;

2773

assert(flowcands !=

|| nflowcands == 0);

2776 for

( n = 0; n < nflowcands; n++ )

2785

assert(flowcands !=

);

2787

assert(0 <=

< nrows);

2788

assert(rowcommodity !=

);

2791

basecommodity = rowcommodity[

];

2792 if

( basecommodity == -1 )

2795

assert(mcfdata->rowarcid[

] == -1);

2798 if

( rownodeid[

] >= 0 )

2802 SCIPdebugMsg

(

"assigning row %d <%s> of commodity %d to node %d [score: %g]\n"

2803 r

(rows[

]), basecommodity, mcfdata->nnodes, mcfdata->flowrowscores[

]);

2804

rownodeid[

] = mcfdata->nnodes;

2812 if

(ncommodities == 1)

2824

assert(commoditysigns !=

);

2830 if

( (flowrowsigns[

] &

) != 0 )

2832 if

( commoditysigns[basecommodity] == -1 )

2835 for

( i = 0; i < rowlen; i++ )

2840

assert(0 <= c && c < ncols);

2841

arcid = colarcid[c];

2846

arcpattern[arcid]++;

2848

arcpattern[arcid]--;

2861 for

( i = 0; i < ncommodities; i++ )

2863

bestflowrows[i] =

;

2864

bestscores[i] = 0.0;

2865

bestinverted[i] =

;

2877 for

( i = 0; i < mcfdata->nnewcols; i++ )

2883

assert(newcols !=

);

2885

assert(0 <= c && c < ncols);

2886

assert(mcfdata->colcommodity[c] >= 0);

2887

assert(mcfdata->colcommodity[c] != basecommodity);

2890

assert(colisincident[c]);

2891

colisincident[c] =

;

2897 for

( j = 0; j < collen; j++ )

2905

assert(0 <= colr && colr < nrows);

2908 if

( rowprocessed[colr] )

2910

rowprocessed[colr] =

;

2913

rowcom = rowcommodity[colr];

2914

assert(rowcom != basecommodity);

2918

assert(rowcom == mcfdata->colcommodity[c]);

2920

assert(mcfdata->rowarcid[colr] == -1);

2923 if

( rownodeid[colr] >= 0 )

2928

nposuncap, nneguncap, colrows[j], &score, &invertcommodity) );

2931 if

( score > bestscores[rowcom] )

2933

bestflowrows[rowcom] = colrows[j];

2934

bestscores[rowcom] = score;

2935

bestinverted[rowcom] = invertcommodity;

2939

assert(bestflowrows[basecommodity] ==

);

2942 for

( i = 0; i < ncommodities; i++ )

2946 if

( bestflowrows[i] ==

)

2950

assert(0 <= comr && comr < nrows);

2951

assert(rowcommodity[comr] == i);

2953

assert(rownodeid[comr] == -1);

2954

assert(mcfdata->nnodes >= 1);

2956 SCIPdebugMsg

(

" -> assigning row %d <%s> of commodity %d to node %d [invert:%u]\n"

2957

comr,

(rows[comr]), i, mcfdata->nnodes-1, bestinverted[i]);

2958

rownodeid[comr] = mcfdata->nnodes-1;

2961 if

( bestinverted[i] )

2963

assert(commoditysigns[i] != +1);

2964

commoditysigns[i] = -1;

2968

assert(commoditysigns[i] != -1);

2969

commoditysigns[i] = +1;

2991 int

* commoditysigns = mcfdata->commoditysigns;

2994 for

( k = 0; k < mcfdata->ncommodities; k++ )

2996 if

( commoditysigns[k] == 0 )

2997

commoditysigns[k] = +1;

3012 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

3013 int

* commoditysigns = mcfdata->commoditysigns;

3014 int

* rowcommodity = mcfdata->rowcommodity;

3015 int

* rownodeid = mcfdata->rownodeid;

3016 int

* colsources = mcfdata->colsources;

3017 int

* coltargets = mcfdata->coltargets;

3025

assert(sourcenode !=

);

3026

assert(targetnode !=

);

3027

assert(colsources !=

);

3028

assert(coltargets !=

);

3034 if

( colsources[c] >= -1 )

3036

assert(coltargets[c] >= -1);

3037

*sourcenode = colsources[c];

3038

*targetnode = coltargets[c];

3049 for

( i = 0; i < collen; i++ )

3056 if

( rownodeid[

] >= 0 )

3063

k = rowcommodity[

];

3064

assert(0 <= v && v < mcfdata->

);

3065

assert(0 <= k && k < mcfdata->ncommodities);

3072 if

( (flowrowsigns[

] &

) != 0 )

3074 if

( commoditysigns[k] == -1 )

3078 if

( ( scale * colvals[i] ) > 0.0 )

3080

assert(*sourcenode == -1);

3082 if

( *targetnode >= 0 )

3087

assert(*targetnode == -1);

3089 if

( *sourcenode >= 0 )

3096

colsources[c] = *sourcenode;

3097

coltargets[c] = *targetnode;

3108 int

* flowcands = mcfdata->flowcands;

3109 int

nflowcands = mcfdata->nflowcands;

3111 unsigned char

* flowrowsigns = mcfdata->flowrowsigns;

3112 int

* colcommodity = mcfdata->colcommodity;

3113 int

* rowcommodity = mcfdata->rowcommodity;

3115 int

* rownodeid = mcfdata->rownodeid;

3116 int

* colarcid = mcfdata->colarcid;

3117 int nnodes

= mcfdata->nnodes;

3118 int

ncommodities = mcfdata->ncommodities;

3125 int

* sortedflowcands;

3126 int

* sortedflowcandnodeid;

3139

assert(mcfdata->nemptycommodities == 0);

3140

assert(ncommodities >= 0);

3144 if

( ncommodities == 0 || nflowcands == 0 ||

== 0 )

3153

assert(rows !=

);

3154

assert(cols !=

|| ncols == 0);

3165 for

( n = 0; n < nflowcands; n++ )

3167

sortedflowcands[n] = flowcands[n];

3168

sortedflowcandnodeid[n] = rownodeid[flowcands[n]];

3172 SCIPsortIntInt

(sortedflowcandnodeid, sortedflowcands, nflowcands);

3173

assert(sortedflowcandnodeid[0] <= 0);

3174

assert(sortedflowcandnodeid[nflowcands-1] ==

-1);

3177 for

( v = 0; v <

; v++ )

3193 for

( n = 0; n < nflowcands; n++ )

3195 if

( sortedflowcandnodeid[n] >= 0 )

3198

assert(rowcommodity[sortedflowcands[n]] == -1);

3200

assert(n < nflowcands);

3201

assert(sortedflowcandnodeid[n] == 0);

3206 for

( v = 0; n < nflowcands; v++ )

3212

assert(rowcommodity[sortedflowcands[n]] >= 0);

3213

assert(rownodeid[sortedflowcands[n]] == sortedflowcandnodeid[n]);

3214

assert(sortedflowcandnodeid[n] == v);

3215

assert(nadjnodes == 0);

3216

assert(ninccols == 0);

3221 for

( ; n < nflowcands && sortedflowcandnodeid[n] == v; n++ )

3228 r

= sortedflowcands[n];

3230

assert(mcfdata->rowarcid[

] == -1);

3235 for

( i = 0; i < rowlen; i++ )

3246

arcid = colarcid[c];

3247

assert(-2 <= arcid && arcid < mcfdata->

);

3248

assert(rowcommodity[

] == colcommodity[c]);

3258 else if

( arcid == -1 )

3268

assert(-1 <= s && s <

);

3269

assert(-1 <= t && t <

);

3270

assert(s == v || t == v);

3281 if

( s < 0 || t < 0 )

3289

assert(ninccols < ncols);

3290

inccols[ninccols] = c;

3306 if

( sourcecount[u] + targetcount[u] == 1 )

3308

assert(nadjnodes <

);

3309

adjnodes[nadjnodes] = u;

3317 for

( l = 0; l < nadjnodes; l++ )

3322

assert(0 <= u && u <

);

3323

assert(sourcecount[u] > 0 || targetcount[u] > 0);

3325

assert(ninccols >= 0);

3328 if

( sourcecount[u] >= arcsthreshold )

3338 for

( m = 0; m < ninccols; m++ )

3345

assert(0 <= c && c < ncols);

3347

assert(cols !=

);

3349

assert(s == v || t == v);

3354

colarcid[c] = arcid;

3357

inccols[m] = inccols[ninccols-1];

3365 if

( targetcount[u] >= arcsthreshold )

3375 for

( m = 0; m < ninccols; m++ )

3382

assert(0 <= c && c < ncols);

3384

assert(cols !=

);

3386

assert(s == v || t == v);

3391

colarcid[c] = arcid;

3394

inccols[m] = inccols[ninccols-1];

3403 for

( l = 0; l < nadjnodes; l++ )

3411 for

( l = 0; l < ninccols; l++ )

3413

assert(colarcid[inccols[l]] == -1);

3414

colarcid[inccols[l]] = -2;

3418

assert(n == nflowcands);

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;

3471 int

nnodesthreshold;

3472 int

newncommodities;

3485

permsize = ncommodities;

3497

assert(flowcands !=

|| nflowcands == 0);

3500 for

( i = 0; i < nflowcands; i++ )

3504

assert(flowcands !=

);

3506

assert(0 <=

< nrows);

3507

assert((rownodeid[

] >= 0) == (rowcommodity[

] >= 0));

3508 if

( rowcommodity[

] >= 0 )

3510

assert(rowcommodity[

] < ncommodities);

3511

nnodespercom[rowcommodity[

]]++;

3515

assert(capacityrows !=

== 0);

3525

assert(capacityrows !=

);

3527

assert(0 <=

< nrows);

3528

assert(rowarcid[

] ==

);

3534 for

( j = 0; j < rowlen; j++ )

3539

assert(0 <= c && c < ncols);

3540 if

( colcommodity[c] >= 0 && colarcid[c] ==

)

3542

assert(colcommodity[c] < ncommodities);

3543

arcisincom[colcommodity[c]] =

;

3548 for

( k = 0; k < ncommodities; k++ )

3550 if

( arcisincom[k] )

3557 for

( k = 0; k < ncommodities; k++ )

3558

maxnnodes =

(maxnnodes, nnodespercom[k]);

3565

nnodesthreshold =

(nnodesthreshold,

MINNODES

);

3569

newncommodities = 0;

3570 for

( k = 0; k < ncommodities; k++ )

3572 SCIPdebugMsg

(

" -> commodity %d: %d nodes, %d arcs\n"

, k, nnodespercom[k], narcspercom[k]);

3575 if

( nnodespercom[k] >= nnodesthreshold && narcspercom[k] >= 1 )

3577

assert(newncommodities <= k);

3578

perm[k] = newncommodities;

3579

commoditysigns[newncommodities] = commoditysigns[k];

3586 if

( newncommodities < ncommodities )

3595 SCIPdebugMsg

(

" -> discarding %d of %d commodities\n"

, ncommodities - newncommodities, ncommodities);

3603 for

( c = 0; c < ncols; c++ )

3605 if

( colcommodity[c] >= 0 )

3607

assert(-1 <= colarcid[c] && colarcid[c] <

);

3608

assert(colcommodity[c] < mcfdata->ncommodities);

3609

colcommodity[c] = perm[colcommodity[c]];

3610

assert(colcommodity[c] < newncommodities);

3611 if

( colcommodity[c] == -1 )

3616 else if

( colarcid[c] >= 0 )

3617

arcisused[colarcid[c]] =

;

3620 for

( i = 0; i < nflowcands; i++ )

3624

assert(flowcands !=

);

3626

assert(0 <=

< nrows);

3627

assert((rownodeid[

] >= 0) == (rowcommodity[

] >= 0));

3628 if

( rowcommodity[

] >= 0 )

3630

assert(0 <= rownodeid[

] && rownodeid[

] <

);

3631

assert(rowcommodity[

] < mcfdata->ncommodities);

3632

rowcommodity[

] = perm[rowcommodity[

]];

3633

assert(rowcommodity[

] < newncommodities);

3634 if

( rowcommodity[

] == -1 )

3637

rownodeid[

] = -1;

3640

nodeisused[rownodeid[

]] =

;

3644

mcfdata->ncommodities = newncommodities;

3645

ncommodities = newncommodities;

3653

assert(capacityrows !=

);

3655 if

( arcisused[

] )

3657

assert(newnarcs <=

);

3658

perm[

] = newnarcs;

3659

capacityrows[newnarcs] = capacityrows[

];

3668

assert(0 <=

< nrows);

3669

assert(rowarcid[

] ==

);

3670

rowarcid[

] = perm[

];

3674 if

( newnarcs <

)

3678 for

( c = 0; c < ncols; c++ )

3680 if

( colarcid[c] >= 0 )

3682

colarcid[c] = perm[colarcid[c]];

3683

assert(colarcid[c] >= 0);

3686

mcfdata->narcs = newnarcs;

3693

assert(capacityrows !=

);

3695

assert(0 <=

< nrows);

3696

assert(rowarcid[

] ==

);

3702 for

( v = 0; v <

; v++ )

3704 if

( nodeisused[v] )

3706

assert(newnnodes <= v);

3707

perm[v] = newnnodes;

3715 if

( newnnodes <

)

3719 for

( i = 0; i < nflowcands; i++ )

3723

assert(flowcands !=

);

3725

assert(0 <=

< nrows);

3726

assert((rownodeid[

] >= 0) == (rowcommodity[

] >= 0));

3727 if

( rowcommodity[

] >= 0 )

3729

assert(rowcommodity[

] < ncommodities);

3730

rownodeid[

] = perm[rownodeid[

]];

3731

assert(rownodeid[

] >= 0);

3734

mcfdata->nnodes = newnnodes;

3746

mcfdata->nemptycommodities = 0;

3768 int

* colarcid = mcfdata->colarcid;

3769 int

* colcommodity = mcfdata->colcommodity;

3770 int narcs

= mcfdata->narcs;

3771 int nnodes

= mcfdata->nnodes;

3772 int

ncommodities = mcfdata->ncommodities;

3773 SCIP_ROW

** capacityrows = mcfdata->capacityrows;

3775 SCIP_Real

maxinconsistencyratio = sepadata->maxinconsistencyratio;

3776 SCIP_Real

maxarcinconsistencyratio = sepadata->maxarcinconsistencyratio;

3788 int

*flowvarspercom;

3801

assert(effortlevel !=

);

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 =

;

3827 for

( c = 0; c < ncols; c++ )

3834 for

( v = 0; v <

; v++ )

3836

firstoutarcs[v] = -1;

3837

firstinarcs[v] = -1;

3841

nextoutarcs[

] = -1;

3842

nextinarcs[

] = -1;

3855

mcfdata->ninconsistencies = 0.0;

3856

maxninconsistencies = maxinconsistencyratio * (

)

;

3881

assert(mcfdata->rowarcid[

] ==

);

3884 for

( i = 0; i <

; i++ )

3886

assert(sourcenodecnt[i] == 0);

3887

assert(targetnodecnt[i] == 0);

3898 for

( i = 0; i < rowlen; i++ )

3902 if

( colarcid[c] >= 0 )

3904 int

k = colcommodity[c];

3905

assert (0 <= k && k < ncommodities);

3906

flowvarspercom[k]++;

3907 if

( !comtouched[k] )

3910

comtouched[k] =

;

3916 if

( ntouchedcoms == 0 )

3918

capacityrows[

] =

;

3919

arcsources[

] = -1;

3920

arctargets[

] = -1;

3926

totalsourcecnt = 0.0;

3927

totaltargetcnt = 0.0;

3929 for

( i = 0; i < rowlen; i++ )

3933 if

( colarcid[c] >= 0 )

3935 int

k = colcommodity[c];

3940

assert (0 <= k && k < ncommodities);

3941

assert (comtouched[k]);

3942

assert (flowvarspercom[k] >= 1);

3948

weight = 1.0/flowvarspercom[k];

3951 if

( sourcenodecnt[sourcev] == 0.0 && targetnodecnt[sourcev] == 0.0 )

3953

touchednodes[ntouchednodes] = sourcev;

3956

sourcenodecnt[sourcev] += weight;

3957

totalsourcecnt += weight;

3961 if

( sourcenodecnt[targetv] == 0.0 && targetnodecnt[targetv] == 0.0 )

3963

touchednodes[ntouchednodes] = targetv;

3966

targetnodecnt[targetv] += weight;

3967

totaltargetcnt += weight;

3969 if

( sourcev >= 0 || targetv >= 0 )

3970

totalnodecnt += weight;

3977

bestsourcecnt = 0.0;

3978

besttargetcnt = 0.0;

3979 for

( i = 0; i < ntouchednodes; i++ )

3981

v = touchednodes[i];

3982

assert(0 <= v && v <

);

3987 if

( sourcenodecnt[v] >= targetnodecnt[v] )

3989 if

( sourcenodecnt[v] > bestsourcecnt )

3992

bestsourcecnt = sourcenodecnt[v];

3997 if

( targetnodecnt[v] > besttargetcnt )

4000

besttargetcnt = targetnodecnt[v];

4006 SCIP_Real

nodecnt = sourcenodecnt[v] + targetnodecnt[v];

4010 if

( nodecnt > bestsourcecnt )

4012

besttargetv = bestsourcev;

4013

besttargetcnt = bestsourcecnt;

4015

bestsourcecnt = nodecnt;

4017 else if

( nodecnt > besttargetcnt )

4020

besttargetcnt = nodecnt;

4025

sourcenodecnt[v] = 0;

4026

targetnodecnt[v] = 0;

4032

totalsourcecnt = totalnodecnt;

4033

totaltargetcnt = totalnodecnt;

4035

assert(

SCIPisGE

(

,totalsourcecnt,bestsourcecnt));

4036

assert(

SCIPisGE

(

,totaltargetcnt,besttargetcnt));

4037

nsourceinconsistencies = (totalsourcecnt - bestsourcecnt)/ntouchedcoms;

4038

ntargetinconsistencies = (totaltargetcnt - besttargetcnt)/ntouchedcoms;

4041 if

( nsourceinconsistencies > maxarcinconsistencyratio )

4047 if

( ntargetinconsistencies > maxarcinconsistencyratio )

4054

assert(bestsourcev == -1 || bestsourcev != besttargetv);

4055

arcsources[

] = bestsourcev;

4056

arctargets[

] = besttargetv;

4057 SCIPdebugMsg

(

"arc %d: %d -> %d (len=%d, sourcecnt=%g/%g, targetcnt=%g/%g, %g/%g inconsistencies)\n"

4058 a

, bestsourcev, besttargetv, rowlen,

4059

bestsourcecnt, totalsourcecnt, besttargetcnt, totaltargetcnt,

4060

nsourceinconsistencies, ntargetinconsistencies);

4063 if

( bestsourcev != -1 )

4065

nextoutarcs[

] = firstoutarcs[bestsourcev];

4066

firstoutarcs[bestsourcev] =

;

4068 if

( besttargetv != -1 )

4070

nextinarcs[

] = firstinarcs[besttargetv];

4071

firstinarcs[besttargetv] =

;

4075

mcfdata->ninconsistencies += 0.5*(nsourceinconsistencies + ntargetinconsistencies);

4077 if

( mcfdata->ninconsistencies > maxninconsistencies )

4079 MCFdebugMessage

(

" -> reached maximal number of inconsistencies: %g > %g\n"

4080

mcfdata->ninconsistencies, maxninconsistencies);

4086 if

( mcfdata->ninconsistencies <= maxninconsistencies &&

> 0 && ncommodities > 0 )

4091 MCFdebugMessage

(

"extracted network has %g inconsistencies (ratio %g) -> separating with effort %d\n"

4092

mcfdata->ninconsistencies, mcfdata->ninconsistencies/(

)

, *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;

4132

assert(nodevisited !=

);

4133

assert(0 <= startv && startv <

);

4134

assert(nodevisited[startv] ==

UNKNOWN

);

4135

assert(compnodes !=

);

4136

assert(ncompnodes !=

);

4137

assert(comparcs !=

);

4138

assert(ncomparcs !=

);

4147

stacknodes[0] = startv;

4149

nodevisited[startv] =

;

4152 while

( nstacknodes > 0 )

4157

assert(firstoutarcs !=

);

4158

assert(firstinarcs !=

);

4159

assert(nextoutarcs !=

);

4160

assert(nextinarcs !=

);

4163

v = stacknodes[nstacknodes-1];

4165

assert(0 <= v && v <

);

4166

assert(nodevisited[v] ==

);

4170

assert(*ncompnodes <

);

4171

compnodes[*ncompnodes] = v;

4175 for

(

= firstoutarcs[v];

!= -1;

= nextoutarcs[

] )

4179

assert(0 <=

&& a < mcfdata->

);

4180

assert(arctargets !=

);

4182

targetv = arctargets[

];

4185 if

( targetv != -1 && nodevisited[targetv] ==

)

4189

assert(*ncomparcs < mcfdata->

);

4190

comparcs[*ncomparcs] =

;

4194 if

( targetv != -1 && nodevisited[targetv] ==

UNKNOWN

)

4196

assert(nstacknodes <

);

4197

stacknodes[nstacknodes] = targetv;

4199

nodevisited[targetv] =

;

4204 for

(

= firstinarcs[v];

!= -1;

= nextinarcs[

] )

4208

assert(0 <=

&& a < mcfdata->

);

4209

assert(arcsources !=

);

4211

sourcev = arcsources[

];

4214 if

( sourcev != -1 && nodevisited[sourcev] ==

)

4218

assert(*ncomparcs < mcfdata->

);

4219

comparcs[*ncomparcs] =

;

4223 if

( sourcev != -1 && nodevisited[sourcev] ==

UNKNOWN

)

4225

assert(nstacknodes <

);

4226

stacknodes[nstacknodes] = sourcev;

4228

nodevisited[sourcev] =

;

4259 int

mcfnetworkssize;

4261

assert(mcfnetworks !=

);

4262

assert(nmcfnetworks !=

);

4263

assert(effortlevel !=

);

4267

*mcfnetworks =

;

4269

mcfnetworkssize = 0;

4300

mcfdata.flowrowsigns =

;

4301

mcfdata.flowrowscalars =

;

4302

mcfdata.flowrowscores =

;

4303

mcfdata.capacityrowsigns =

;

4304

mcfdata.capacityrowscores =

;

4305

mcfdata.flowcands =

;

4306

mcfdata.nflowcands = 0;

4307

mcfdata.capacitycands =

;

4308

mcfdata.ncapacitycands = 0;

4309

mcfdata.plusflow =

;

4310

mcfdata.minusflow =

;

4311

mcfdata.ncommodities = 0;

4312

mcfdata.nemptycommodities = 0;

4313

mcfdata.commoditysigns =

;

4314

mcfdata.commoditysignssize = 0;

4315

mcfdata.colcommodity =

;

4316

mcfdata.rowcommodity =

;

4317

mcfdata.colarcid =

;

4318

mcfdata.rowarcid =

;

4319

mcfdata.rownodeid =

;

4320

mcfdata.arcarraysize = 0;

4321

mcfdata.arcsources =

;

4322

mcfdata.arctargets =

;

4323

mcfdata.colsources =

;

4324

mcfdata.coltargets =

;

4325

mcfdata.firstoutarcs =

;

4326

mcfdata.firstinarcs =

;

4327

mcfdata.nextoutarcs =

;

4328

mcfdata.nextinarcs =

;

4329

mcfdata.newcols =

;

4330

mcfdata.nnewcols = 0;

4333

mcfdata.ninconsistencies = 0.0;

4334

mcfdata.capacityrows =

;

4335

mcfdata.capacityrowssize = 0;

4336

mcfdata.colisincident =

;

4337

mcfdata.zeroarcarray =

;

4338

mcfdata.modeltype = modeltype;

4344

assert(mcfdata.flowrowsigns !=

);

4345

assert(mcfdata.flowrowscalars !=

);

4346

assert(mcfdata.flowrowscores !=

);

4347

assert(mcfdata.flowcands !=

);

4349 if

( mcfdata.nflowcands == 0 )

4357

assert(mcfdata.plusflow !=

);

4358

assert(mcfdata.minusflow !=

);

4359

assert(mcfdata.colcommodity !=

);

4360

assert(mcfdata.rowcommodity !=

);

4361

assert(mcfdata.newcols !=

);

4367

printCommodities(

, &mcfdata);

4374

assert(mcfdata.capacityrowsigns !=

);

4375

assert(mcfdata.capacityrowscores !=

);

4376

assert(mcfdata.capacitycands !=

);

4378 if

( mcfdata.ncapacitycands == 0 )

4386

assert(mcfdata.colarcid !=

);

4387

assert(mcfdata.rowarcid !=

);

4391

assert(mcfdata.rownodeid !=

);

4392

assert(mcfdata.colisincident !=

);

4393

assert(mcfdata.zeroarcarray !=

);

4404

assert(mcfdata.arcsources !=

);

4405

assert(mcfdata.arctargets !=

);

4406

assert(mcfdata.colsources !=

);

4407

assert(mcfdata.coltargets !=

);

4408

assert(mcfdata.firstoutarcs !=

);

4409

assert(mcfdata.firstinarcs !=

);

4410

assert(mcfdata.nextoutarcs !=

);

4411

assert(mcfdata.nextinarcs !=

);

4427

printCommodities(

, &mcfdata);

4440 for

( v = 0; v < mcfdata.nnodes; v++ )

4444 for

( v = 0; v < mcfdata.nnodes; v++ )

4451 if

( nodevisited[v] ==

)

4456

assert(ncompnodes >= 1);

4457

assert(compnodes[0] == v);

4458

assert(nodevisited[v] ==

);

4461 if

( ncompnodes >= minnodes && ncomparcs >=

MINARCS

)

4468

assert(*nmcfnetworks <= mcfnetworkssize);

4469 if

( *nmcfnetworks == mcfnetworkssize )

4471

mcfnetworkssize =

(2*mcfnetworkssize, *nmcfnetworks+1);

4474

assert(*nmcfnetworks < mcfnetworkssize);

4483

assert(*mcfnetworks !=

);

4484 for

( i = *nmcfnetworks; i > 0 && mcfnetwork->

> (*mcfnetworks)[i-1]->nnodes; i-- )

4485

(*mcfnetworks)[i] = (*mcfnetworks)[i-1];

4486

(*mcfnetworks)[i] = mcfnetwork;

4491

minnodes =

(minnodes, (*mcfnetworks)[*nmcfnetworks-1]->

);

4496 SCIPdebugMsg

(

" -> discarded network with %d nodes and %d arcs due to maxnetworks (minnodes=%d)\n"

4497

(*mcfnetworks)[*nmcfnetworks-1]->

, (*mcfnetworks)[*nmcfnetworks-1]->

, minnodes);

4505 SCIPdebugMsg

(

" -> discarded component with %d nodes and %d arcs\n"

, ncompnodes, ncomparcs);

4547#ifdef COUNTNETWORKVARIABLETYPES 4569 int

nintflowvars = 0;

4570 int

nbinflowvars = 0;

4571 int

ncontflowvars = 0;

4573 int

nintcapvars = 0;

4574 int

nbincapvars = 0;

4575 int

ncontcapvars = 0;

4583 for

(c=0; c < ncols; c++)

4584

colvisited[c]=

;

4588 for

(m=0; m < nmcfnetworks; m++)

4600 for

(c=0; c < ncols; c++)

4604 if

(colcommodity[c] >= 0 && ! colvisited[c])

4609

colvisited[c] =

;

4635

row = arccapacityrows[

];

4647 for

( i = 0; i < rowlen; i++ )

4652 if

(colcommodity[c] == -1 && ! colvisited[c] )

4655

colvisited[c] =

;

4680 for

( k = 0; k < ncommodities; k++ )

4682 for

( v = 0; v <

; v++ )

4685

row = nodeflowrows[v][k];

4695 MCFdebugMessage

(

" nof flowvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n"

4696

nflowvars, ncontflowvars, nintflowvars, nbinflowvars);

4697 MCFdebugMessage

(

" nof capvars: %5d of which [ %d , %d , %d ] are continuous, integer, binary\n"

4698

ncapvars, ncontcapvars, nintcapvars, nbincapvars);

4717 int

* representatives,

4724 for

( v = 0; v < nelems; v++ )

4725

representatives[v] = v;

4731 int

* representatives,

4735

assert(representatives !=

);

4737 while

( v != representatives[v] )

4739

representatives[v] = representatives[representatives[v]];

4740

v = representatives[v];

4749 int

* representatives,

4754

assert(rep1 != rep2);

4755

assert(representatives[rep1] == rep1);

4756

assert(representatives[rep2] == rep2);

4762

representatives[rep2] = rep1;

4764

representatives[rep1] = rep2;

4780 if

( nodepair1->weight > nodepair2->weight )

4782 else if

( nodepair1->weight < nodepair2->weight )

4817

assert(mcfnetwork !=

);

4823

assert(nodepair1 !=

);

4824

assert(nodepair2 !=

);

4826

source1 = nodepair1->node1;

4827

source2 = nodepair2->node1;

4828

target1 = nodepair1->node2;

4829

target2 = nodepair2->node2;

4831

assert(source1 >=0 && source1 < mcfnetwork->

);

4832

assert(source2 >=0 && source2 < mcfnetwork->

);

4833

assert(target1 >=0 && target1 < mcfnetwork->

);

4834

assert(target2 >=0 && target2 < mcfnetwork->

);

4835

assert(source1 <= target1);

4836

assert(source2 <= target2);

4838 return

(source1 == source2 && target1 == target2);

4852 unsigned int

hashval;

4856

assert(mcfnetwork !=

);

4860

assert( nodepair !=

);

4862

source = nodepair->node1;

4863

target = nodepair->node2;

4865

assert(source >=0 && source < mcfnetwork->

);

4866

assert(target >=0 && target < mcfnetwork->

);

4867

assert(source <= target);

4869

hashval = (unsigned)((source << 16) + target);

4892#ifdef BETTERWEIGHTFORDEMANDNODES 4912

assert(mcfnetwork !=

);

4914#ifdef BETTERWEIGHTFORDEMANDNODES 4924

assert(nodepairqueue !=

);

4931

hashtablesize = mcfnetwork->

;

4934

hashGetKeyNodepairs, hashKeyEqNodepairs, hashKeyValNodepairs, (

void

*) mcfnetwork) );

4941 for

(

= 0;

< mcfnetwork->

;

++ )

4963

assert(nodepair.node1 < mcfnetwork->

);

4964

assert(nodepair.node2 < mcfnetwork->

);

4965 if

( nodepair.node1 == -1 || nodepair.node2 == -1 )

4969 if

( capacityrow !=

)

4985

slack =

(slack, 0.0);

4989

assert(scale > 0.0);

4999 for

( i = 0; i < rowlen; i++ )

5006 if

(colcommodity[c] >= 0)

5018 SCIPdebugMsg

(

"cap arc -- slack:%g -- dual:%g -- flow:%g -- cap:%g \n"

, scale * slack, dualsol/scale, totalflow * scale, totalcap * scale);

5020 SCIPdebugMsg

(

"cap arc -- slack:%g -- dual:%g1\n"

, scale * slack, dualsol/scale);

5024

nodepair.weight = scale * slack -

(dualsol)/scale;

5025#ifdef USEFLOWFORTIEBREAKING 5028

nodepair.weight += totalflow * scale;

5029

nodepair.weight =

( nodepair.weight, -0.0001);

5032#ifdef USECAPACITYFORTIEBREAKING 5035

nodepair.weight += totalcap * scale;

5036

nodepair.weight =

( nodepair.weight, -0.0001);

5051 if

( nodepairptr !=

)

5054 SCIPdebugMsg

(

"nodepair known [%d,%d] -- old weight:%g -- new weight:%g\n"

, nodepair.node1,nodepair.node2,nodepairptr->weight,

5055 MIN

(nodepair.weight, nodepairptr->weight));

5056

nodepairptr->weight =

(nodepair.weight, nodepairptr->weight);

5061

nodepairs = (*nodepairqueue)->nodepairs;

5063

assert(nnodepairs < mcfnetwork->

);

5064

nodepairs[nnodepairs] = nodepair;

5067 SCIPdebugMsg

(

"new nodepair [%d,%d]-- weight:%g\n"

, nodepair.node1, nodepair.node2, nodepair.weight);

5078#ifdef BETTERWEIGHTFORDEMANDNODES 5086

nodepairs = (*nodepairqueue)->nodepairs;

5087 for

( n = 0; n < nnodepairs; n++ )

5091

maxweight =

(maxweight, nodepairs[n].weight);

5093

minweight =

(minweight, nodepairs[n].weight);

5103 for

( n = 0; n < nnodepairs; n++ )

5105 int

node1 = nodepairs[n].node1;

5106 int

node2 = nodepairs[n].node2;

5108#ifdef BETTERWEIGHTFORDEMANDNODES 5115 SCIPdebugMsg

(

"nodepair [%d,%d] weight %g\n"

, node1,node2,nodepairs[n].weight);

5121 for

( k = 0; k < ncommodities; k++ )

5123 if

( nodeflowrows[node1][k] ==

)

5126 if

( nodeflowscales[node1][k] > 0.0 )

5141 for

( k = 0; k < ncommodities; k++ )

5143 if

( nodeflowrows[node2][k] ==

)

5146 if

( nodeflowscales[node2][k] > 0.0 )

5168 if

( !hasdemand1 || !hasdemand2 )

5169

nodepairs[n].weight += maxweight;

5175 if

( hasdemand1 && hasdemand2)

5176

nodepairs[n].weight += minweight;

5179 SCIPdebugMsg

(

"nodepair [%d,%d] weight %g\n"

, node1,node2,nodepairs[n].weight);

5196

assert(nodepairqueue !=

);

5197

assert(*nodepairqueue !=

);

5211

assert(nodepairqueue !=

);

5223

assert(nodepairqueue !=

);

5271

assert(mcfnetwork !=

);

5272

assert(nodepartition !=

);

5273

assert(mcfnetwork->

>= 1);

5281

(*nodepartition)->nclusters = 0;

5290

nclustersleft = mcfnetwork->

;

5301

assert(nodepair !=

);

5302

node1 = nodepair->node1;

5303

node2 = nodepair->node2;

5305

assert(node1 >= 0 && node1 < mcfnetwork->

);

5306

assert(node2 >= 0 && node2 < mcfnetwork->

);

5311

assert(0 <= node1rep && node1rep < mcfnetwork->

);

5312

assert(0 <= node2rep && node2rep < mcfnetwork->

);

5315 if

( node1rep == node2rep )

5319 SCIPdebugMsg

(

"shrinking nodepair (%d,%d) with weight %g: join representatives %d and %d\n"

5320

node1, node2, nodepair->weight, node1rep, node2rep);

5326

assert((*nodepartition)->representatives[0] == 0);

5331 if

( nclustersleft > nclusters )

5333 for

( v = 1; v < mcfnetwork->

&& nclustersleft > nclusters; v++ )

5345

assert(nclustersleft <= nclusters);

5350 for

( v = 0; v < mcfnetwork->

; v++ )

5360

c = (*nodepartition)->nclusters;

5361

(*nodepartition)->nclusters++;

5364

c = (*nodepartition)->nodeclusters[rep];

5365

assert(0 <= c && c < nclusters);

5368

(*nodepartition)->nodeclusters[v] = c;

5374 for

( c = 0; c < (*nodepartition)->nclusters; c++ )

5376

(*nodepartition)->clusterbegin[c] = pos;

5377

pos += clustersize[c];

5379

assert(pos == mcfnetwork->

);

5380

(*nodepartition)->clusterbegin[(*nodepartition)->nclusters] = mcfnetwork->

;

5384 for

( v = 0; v < mcfnetwork->

; v++ )

5386

c = (*nodepartition)->nodeclusters[v];

5387

assert(0 <= c && c < (*nodepartition)->nclusters);

5388

pos = (*nodepartition)->clusterbegin[c] + clustersize[c];

5389

assert(pos < (*nodepartition)->clusterbegin[c+1]);

5390

(*nodepartition)->clusternodes[pos] = v;

5410

assert(nodepartition !=

);

5411

assert(*nodepartition !=

);

5424 unsigned int

partition,

5435 if

( nodepartition ==

)

5436 return

((v == (

int

)partition) == !inverted);

5440 unsigned int

clusterbit;

5442

cluster = nodepartition->nodeclusters[v];

5443

assert(0 <= cluster && cluster < nodepartition->nclusters);

5444

clusterbit = (1 << cluster);

5446 return

(((partition & clusterbit) != 0) == !inverted);

5456 unsigned int

partition

5459 const int

* nodeclusters = nodepartition->nodeclusters;

5460 const int

* arcsources = mcfnetwork->

arcsources

;

5461 const int

* arctargets = mcfnetwork->

arctargets

;

5469

assert(nodepartition->nodeclusters !=

);

5470

nclusters = nodepartition->nclusters;

5477

ncomponents = nclusters;

5478

assert(ncomponents >= 2);

5483 int

s = arcsources[

];

5484 int

t = arctargets[

];

5487 if

( s == -1 || t == -1 )

5498

assert(0 <= s && s < mcfnetwork->

);

5499

assert(0 <= t && t < mcfnetwork->

);

5502

cs = nodeclusters[s];

5503

ct = nodeclusters[t];

5504

assert(0 <= cs && cs < nclusters);

5505

assert(0 <= ct && ct < nclusters);

5514 if

( repcs == repct )

5521 if

( ncomponents <= 2 )

5531

assert(ncomponents >= 2);

5533 return

(ncomponents == 2);

5538void

nodepartitionPrint(

5544 for

( c = 0; c < nodepartition->nclusters; c++ )

5549 for

( i = nodepartition->clusterbegin[c]; i < nodepartition->clusterbegin[c+1]; i++ )

5564 unsigned int

partition

5573 if

( nodepartition ==

)

5578

file = fopen(filename,

"w"

);

5586

fprintf(file,

"graph\n"

);

5587

fprintf(file,

"[\n"

);

5588

fprintf(file,

" hierarchic 1\n"

);

5589

fprintf(file,

" label \"\"\n"

);

5590

fprintf(file,

" directed 1\n"

);

5593 for

( v = 0; v < mcfnetwork->

; v++ )

5602

inpartition =

(nodepartition, partition, inverted, v);

5604

fprintf(file,

" node\n"

);

5605

fprintf(file,

" [\n"

);

5606

fprintf(file,

" id %d\n"

, v);

5607

fprintf(file,

" label \"%s\"\n"

, label);

5608

fprintf(file,

" graphics\n"

);

5609

fprintf(file,

" [\n"

);

5610

fprintf(file,

" w 30.0\n"

);

5611

fprintf(file,

" h 30.0\n"

);

5612

fprintf(file,

" type \"ellipse\"\n"

);

5614

fprintf(file,

" fill \"#FF0000\"\n"

);

5616

fprintf(file,

" fill \"#00FF00\"\n"

);

5617

fprintf(file,

" outline \"#000000\"\n"

);

5618

fprintf(file,

" ]\n"

);

5619

fprintf(file,

" LabelGraphics\n"

);

5620

fprintf(file,

" [\n"

);

5621

fprintf(file,

" text \"%s\"\n"

, label);

5622

fprintf(file,

" fontSize 13\n"

);

5623

fprintf(file,

" fontName \"Dialog\"\n"

);

5624

fprintf(file,

" anchor \"c\"\n"

);

5625

fprintf(file,

" ]\n"

);

5627

fprintf(file,

" gid %d\n"

, mcfnetwork->

+1);

5629

fprintf(file,

" gid %d\n"

, mcfnetwork->

+2);

5630

fprintf(file,

" ]\n"

);

5634

fprintf(file,

" node\n"

);

5635

fprintf(file,

" [\n"

);

5636

fprintf(file,

" id %d\n"

, mcfnetwork->

);

5637

fprintf(file,

" label \"?\"\n"

);

5638

fprintf(file,

" graphics\n"

);

5639

fprintf(file,

" [\n"

);

5640

fprintf(file,

" w 30.0\n"

);

5641

fprintf(file,

" h 30.0\n"

);

5642

fprintf(file,

" type \"ellipse\"\n"

);

5643

fprintf(file,

" fill \"#FFFFFF\"\n"

);

5644

fprintf(file,

" outline \"#000000\"\n"

);

5645

fprintf(file,

" ]\n"

);

5646

fprintf(file,

" LabelGraphics\n"

);

5647

fprintf(file,

" [\n"

);

5648

fprintf(file,

" text \"?\"\n"

);

5649

fprintf(file,

" fontSize 13\n"

);

5650

fprintf(file,

" fontName \"Dialog\"\n"

);

5651

fprintf(file,

" anchor \"c\"\n"

);

5652

fprintf(file,

" ]\n"

);

5653

fprintf(file,

" ]\n"

);

5656

fprintf(file,

" node\n"

);

5657

fprintf(file,

" [\n"

);

5658

fprintf(file,

" id %d\n"

, mcfnetwork->

+1);

5659

fprintf(file,

" label \"Partition S\"\n"

);

5660

fprintf(file,

" graphics\n"

);

5661

fprintf(file,

" [\n"

);

5662

fprintf(file,

" type \"roundrectangle\"\n"

);

5663

fprintf(file,

" fill \"#CAECFF84\"\n"

);

5664

fprintf(file,

" outline \"#666699\"\n"

);

5665

fprintf(file,

" outlineStyle \"dotted\"\n"

);

5666

fprintf(file,

" topBorderInset 0\n"

);

5667

fprintf(file,

" bottomBorderInset 0\n"

);

5668

fprintf(file,

" leftBorderInset 0\n"

);

5669

fprintf(file,

" rightBorderInset 0\n"

);

5670

fprintf(file,

" ]\n"

);

5671

fprintf(file,

" LabelGraphics\n"

);

5672

fprintf(file,

" [\n"

);

5673

fprintf(file,

" text \"Partition S\"\n"

);

5674

fprintf(file,

" fill \"#99CCFF\"\n"

);

5675

fprintf(file,

" fontSize 15\n"

);

5676

fprintf(file,

" fontName \"Dialog\"\n"

);

5677

fprintf(file,

" alignment \"right\"\n"

);

5678

fprintf(file,

" autoSizePolicy \"node_width\"\n"

);

5679

fprintf(file,

" anchor \"t\"\n"

);

5680

fprintf(file,

" borderDistance 0.0\n"

);

5681

fprintf(file,

" ]\n"

);

5682

fprintf(file,

" isGroup 1\n"

);

5683

fprintf(file,

" ]\n"

);

5686

fprintf(file,

" node\n"

);

5687

fprintf(file,

" [\n"

);

5688

fprintf(file,

" id %d\n"

, mcfnetwork->

+2);

5689

fprintf(file,

" label \"Partition T\"\n"

);

5690

fprintf(file,

" graphics\n"

);

5691

fprintf(file,

" [\n"

);

5692

fprintf(file,

" type \"roundrectangle\"\n"

);

5693

fprintf(file,

" fill \"#CAECFF84\"\n"

);

5694

fprintf(file,

" outline \"#666699\"\n"

);

5695

fprintf(file,

" outlineStyle \"dotted\"\n"

);

5696

fprintf(file,

" topBorderInset 0\n"

);

5697

fprintf(file,

" bottomBorderInset 0\n"

);

5698

fprintf(file,

" leftBorderInset 0\n"

);

5699

fprintf(file,

" rightBorderInset 0\n"

);

5700

fprintf(file,

" ]\n"

);

5701

fprintf(file,

" LabelGraphics\n"

);

5702

fprintf(file,

" [\n"

);

5703

fprintf(file,

" text \"Partition T\"\n"

);

5704

fprintf(file,

" fill \"#99CCFF\"\n"

);

5705

fprintf(file,

" fontSize 15\n"

);

5706

fprintf(file,

" fontName \"Dialog\"\n"

);

5707

fprintf(file,

" alignment \"right\"\n"

);

5708

fprintf(file,

" autoSizePolicy \"node_width\"\n"

);

5709

fprintf(file,

" anchor \"t\"\n"

);

5710

fprintf(file,

" borderDistance 0.0\n"

);

5711

fprintf(file,

" ]\n"

);

5712

fprintf(file,

" isGroup 1\n"

);

5713

fprintf(file,

" ]\n"

);

5716 for

(

= 0;

< mcfnetwork->

;

++ )

5728

hasfractional =

;

5739 for

( i = 0; i < rowlen; i++ )

5746

hasfractional =

;

5754

fprintf(file,

" edge\n"

);

5755

fprintf(file,

" [\n"

);

5758

fprintf(file,

" label \"%s\"\n"

, label);

5759

fprintf(file,

" graphics\n"

);

5760

fprintf(file,

" [\n"

);

5762

fprintf(file,

" fill \"#000000\"\n"

);

5764

fprintf(file,

" fill \"#FF0000\"\n"

);

5765 if

( hasfractional )

5766

fprintf(file,

" style \"dashed\"\n"

);

5767

fprintf(file,

" width 1\n"

);

5768

fprintf(file,

" targetArrow \"standard\"\n"

);

5769

fprintf(file,

" ]\n"

);

5770

fprintf(file,

" LabelGraphics\n"

);

5771

fprintf(file,

" [\n"

);

5772

fprintf(file,

" text \"%s\"\n"

, label);

5773

fprintf(file,

" ]\n"

);

5774

fprintf(file,

" ]\n"

);

5778

fprintf(file,

"]\n"

);

5814

assert(sepadata !=

);

5815

assert(cutcoefs !=

);

5816

assert(ncuts !=

);

5817

assert(cutoff !=

);

5821

assert(nvars == 0 || vars !=

);

5827 for

( i = 0; i < cutnnz; ++i )

5829

cutvars[i] = vars[cutinds[i]];

5835

sepadata->dynamiccuts) );

5845 SCIPdebugMsg

(

SCIPseparateRelaxedKnapsack

" -> found MCF cut <%s>: rhs=%f, act=%f eff=%f rank=%d\n"

5862 if

( !(*cutoff) && sepadata->separateknapsack)

5865 SCIP_CALL

(

(

, sepa, cutnnz, cutvars, cutcoefs, +1.0, cutrhs, sol, cutoff, ncuts) );

5916 unsigned int

partition;

5917 unsigned int

allpartitions;

5918 unsigned int

startpartition;

5932

maxsepacuts = sepadata->maxsepacutsroot;

5934

maxsepacuts = sepadata->maxsepacuts;

5935 if

( maxsepacuts < 0 )

5936

maxsepacuts = INT_MAX;

5941

maxtestdelta = sepadata->maxtestdelta;

5942 if

( maxtestdelta <= 0 )

5943

maxtestdelta = INT_MAX;

5979 if

( nodepartition ==

)

5983

allpartitions = (

unsigned

int)

;

5984 SCIPdebugMsg

(

"maxtestdelta: %d, maxsepacuts: %d, nnodes: %d \n"

, maxtestdelta, maxsepacuts,

);

5991 int

nclusters = nodepartition->nclusters;

5993

assert((

unsigned int

)nclusters <= 8*

sizeof

(

unsigned int

));

5994 SCIPdebugMsg

(

"maxtestdelta: %d, maxsepacuts: %d, nclusters: %d \n"

, maxtestdelta, maxsepacuts, nclusters);

6001

allpartitions = (1 << (nclusters-1));

6005 for

( partition = startpartition; partition <= allpartitions-1 && !

SCIPisStopped

(

) && *ncuts < maxsepacuts && !*cutoff; partition++ )

6019 if

( sepadata->checkcutshoreconnectivity )

6026 SCIPdebugMsg

(

"generating cluster cuts for partition 0x%x \n"

, partition );

6027 SCIPdebugMsg

(

" -> either shore S or shore T is not connected - skip partition.\n"

);

6032 for

( inverted =

; inverted <= useinverted && !*cutoff; inverted++ )

6034 if

( nodepartition ==

)

6036 SCIPdebugMsg

(

"generating single-node cuts for node %u (inverted: %u)\n"

, partition, inverted);

6040 SCIPdebugMsg

(

"generating cluster cuts for partition 0x%x (inverted: %u)\n"

, partition, inverted);

6044 SCIP_CALL

( outputGraph(

, mcfnetwork, nodepartition, inverted, partition) );

6062 for

( v = 0; v <

; v++ )

6072 for

( k = 0; k < ncommodities; k++ )

6076 if

( nodeflowrows[v][k] ==

)

6079 if

( nodeflowscales[v][k] > 0.0 )

6083 if

( nodeflowinverted[v][k] )

6086

comcutdemands[k] += rhs * nodeflowscales[v][k];

6089

assert (1 <= nnodesinS && nnodesinS <=

-1);

6094 if

( sepadata->separatesinglenodecuts && nodepartition !=

&& (nnodesinS == 1 || nnodesinS ==

-1) )

6096 SCIPdebugMsg

(

" -> shore S or T has only one node - skip partition.\n"

);

6103 for

( k = 0; k < ncommodities; k++ )

6106 SCIPdebugMsg

(

" -> commodity %d: directed cutdemand=%g\n"

, k, comcutdemands[k]);

6113 for

( k = 0; k < ncommodities; k++ )

6116 SCIPdebugMsg

(

" -> commodity %d: undirected cutdemand=%g\n"

, k, comcutdemands[k]);

6121 if

( k == ncommodities )

6134

assert(arcsources[

] <

);

6135

assert(arctargets[

] <

);

6141 if

(

(nodepartition, partition, inverted, arcsources[

]) ||

6151 if

(

(nodepartition, partition, inverted, arcsources[

]) &&

6157 if

( !

(nodepartition, partition, inverted, arcsources[

]) &&

6166 if

( arccapacityrows[

] ==

)

6174

assert(rowweights[

] == 0.0);

6180 if

( arcsources[

] == -1 || arctargets[

] == -1 )

6190

assert(maxcoef > 0.0);

6195

rowweights[

] = arccapacityscales[

];

6200 if

( sepadata->separateflowcutset )

6202 if

( rowweights[

] > 0.0 )

6212 for

( j = 0; j < rowlen; j++ )

6217

coef = rowvals[j] * arccapacityscales[

];

6223

k = colcommodity[c];

6225

comdemands[k] = coef;

6239 while

( left <= right )

6241 int

mid = (left+right)/2;

6243 if

(

REALABS

( deltas[mid] / coef - 1.0 ) < 1e-03 )

6248 else if

( coef < deltas[mid] )

6257

assert(right == left-1);

6258

assert(ndeltas <= deltassize);

6259 if

( ndeltas == deltassize )

6264 if

( left < ndeltas )

6266 for

( d = ndeltas; d > left; d-- )

6267

deltas[d] = deltas[d-1];

6269

deltas[left] = coef;

6278 for

( v = 0; v <

; v++ )

6281 for

( k = 0; k < ncommodities; k++ )

6287 if

( comdemands[k] == 0.0 )

6290

scale = comdemands[k];

6313 if

( comcutdemands[k] > 0.0 )

6332 if

( nodeflowrows[v][k] ==

)

6341

assert(rowweights[

] == 0.0);

6347

rowweights[

] = scale * nodeflowscales[v][k];

6348 if

( nodeflowinverted[v][k] )

6349

rowweights[

] *= -1.0;

6350 SCIPdebugMsg

(

" -> node %d, commodity %d, r=%d, flow row <%s>: scale=%g weight=%g slack=%g dual=%g\n"

6354 if

( sepadata->separateflowcutset )

6356 if

( nodeflowscales[v][k] > 0.0 )

6372 if

( sepadata->separateflowcutset )

6375

bestdelta = deltas[ndeltas-1];

6386 for

( d = ndeltas-1; d >= 0 && d >= ndeltas-maxtestdelta; d-- )

6401 SCIP_CALL

(

(

, sol,

, allowlocal, sepadata->fixintegralrhs,

MINFRAC

MAXFRAC

6402

1.0/deltas[d], aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );

6403

assert(allowlocal || !cutislocal);

6411 if

( sepadata->separateflowcutset )

6413 if

( cutefficacy > bestefficacy )

6415

bestdelta = deltas[d];

6416

bestefficacy = cutefficacy;

6422 SCIPdebugMsg

(

"success -> delta = %g -> rhs: %g, efficacy: %g\n"

, deltas[d], cutrhs, cutefficacy);

6423 SCIP_CALL

(

addCut

(

, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );

6430 if

( arccapacityrows[

] !=

)

6436 if

(

>= 0 && rowweights[

] != 0.0 )

6438 MCFdebugMessage

(

" -> arc %d, capacity row <%s>: weight=%g slack=%g prod=%g dual=%g\n"

6451 if

( sepadata->separateflowcutset && oldncuts == *ncuts && !*cutoff )

6459

totalviolationdelta = 0.0;

6460

onedivoneminsf0 = 1.0/(1.0 - f0);

6475 if

( arccapacityrows[

] ==

)

6486 if

( rowweights[

] == 0.0 )

6501

rowweight = rowweights[

]/bestdelta;

6506

violationdelta = rowweight * (rowlhs - rowconstant);

6508

violationdelta = rowweight * (rowrhs - rowconstant);

6510 for

( j = 0; j < rowlen; j++ )

6518

coef = rowvals[j] * rowweight;

6529 if

( colcommodity[c] >= 0 )

6540

mircoef =

SCIPfloor

(

, coef) + (fj - f0)*onedivoneminsf0;

6547

mircoef = coef * onedivoneminsf0;

6552 if

( colcommodity[c] >= 0 )

6553

violationdelta += mircoef * solval;

6555

violationdelta -= mircoef * solval;

6560 SCIPdebugMsg

(

" -> discarding capacity row <%s> of weight %g and slack %g: increases MIR violation by %g\n"

6563

rowweights[

] = 0.0;

6564

totalviolationdelta += violationdelta;

6569 if

( totalviolationdelta > 0.0 )

6582 SCIPdebugMsg

(

"applying MIR with delta = %g to flowcut inequality (violation improvement: %g)\n"

, bestdelta, totalviolationdelta);

6589 SCIP_CALL

(

(

, sol,

, allowlocal, sepadata->fixintegralrhs,

MINFRAC

MAXFRAC

6590

1.0/bestdelta, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );

6592

assert(allowlocal || !cutislocal);

6596 SCIPdebugMsg

(

" -> delta = %g -> rhs: %g, efficacy: %g\n"

, bestdelta, cutrhs, cutefficacy);

6597 SCIP_CALL

(

addCut

(

, sepa, sepadata, sol, cutcoefs, cutrhs, cutinds, cutnnz, cutislocal, cutrank, ncuts, cutoff) );

6641

assert(result !=

);

6654 if

( ncols != nvars )

6656 MCFdebugMessage

(

"%d variables but %d columns -> exit\n"

, nvars, ncols );

6669

colrowratio = (

)ncols/(nrows+1e-9);

6673

assert(sepadata !=

);

6682 if

( colrowratio < MINCOLROWRATIO || colrowratio >

MAXCOLROWRATIO

)

6691 if

( sepadata->nmcfnetworks == -1 )

6697 MCFdebugMessage

(

"extracted %d networks\n"

, sepadata->nmcfnetworks);

6699 for

( i = 0; i < sepadata->nmcfnetworks; i++ )

6701 MCFdebugMessage

(

" -> extracted network %d has %d nodes, %d (%d) arcs (uncapacitated), and %d commodities (modeltype: %s)\n"

6702

i, sepadata->mcfnetworks[i]->nnodes, sepadata->mcfnetworks[i]->narcs, sepadata->mcfnetworks[i]->nuncapacitatedarcs,

6703

sepadata->mcfnetworks[i]->ncommodities,

6705 SCIPdebug

( mcfnetworkPrint(sepadata->mcfnetworks[i]) );

6708#ifdef COUNTNETWORKVARIABLETYPES 6709 SCIP_CALL

( printFlowSystemInfo(

,sepadata->mcfnetworks,sepadata->nmcfnetworks));

6713

assert(sepadata->nmcfnetworks >= 0);

6714

assert(sepadata->mcfnetworks !=

|| sepadata->nmcfnetworks == 0);

6715

mcfnetworks = sepadata->mcfnetworks;

6716

nmcfnetworks = sepadata->nmcfnetworks;

6723

sepadata->lastroundsuccess =

;

6725 for

( i = 0; i < nmcfnetworks && !cutoff; i++ )

6731

mcfnetwork = mcfnetworks[i];

6734

assert(mcfnetwork->

>= 2);

6735

assert(mcfnetwork->

>= 1);

6742 MCFdebugMessage

(

"MCF network has %d nodes and %d arcs. arc node ratio %.2f exceed --> exit\n"

6748 if

( sepadata->separatesinglenodecuts )

6759

nodepartitionPrint(nodepartition);

6769 MCFdebugMessage

(

"MCF network has %d nodes, %d arcs, %d commodities. Found %d MCF network cuts, cutoff = %u.\n"

6776

sepadata->lastroundsuccess =

;

6778 else if

( ncuts > 0 )

6781

sepadata->lastroundsuccess =

;

6799

assert(sepa !=

);

6817

assert(sepadata !=

);

6818

assert(sepadata->mcfnetworks ==

);

6819

assert(sepadata->nmcfnetworks == -1);

6837

assert(sepadata !=

);

6839

sepadata->lastroundsuccess =

;

6856

assert(sepadata !=

);

6859 for

( i = 0; i < sepadata->nmcfnetworks; i++ )

6864

sepadata->nmcfnetworks = -1;

6926

sepadata->mcfnetworks =

;

6927

sepadata->nmcfnetworks = -1;

6929

sepadata->lastroundsuccess =

;

6935

sepaExeclpMcf, sepaExecsolMcf,

6938

assert(sepa !=