1493:
938:, which can be used for solving minimum cost flow. The minimum cost circulation problem has no source and sink; instead it has costs and lower and upper bounds on each edge, and seeks flow amounts within the given bounds that balance the flow at each vertex and minimize the sum over edges of cost times flow. Any minimum-cost flow instance can be converted into a minimum cost circulation instance by setting the lower bound on all edges to zero, and then making an extra edge from the sink
50:. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the
1196:(large enough to exceed the maximum flow; for instance, the sum of capacities out of the source vertex) Set the costs of all edges in the maximum flow instance to zero, and introduce a new edge from source to sink with unit cost and capacity
899:
A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximum flow solutions. This could be called a minimum-cost maximum-flow problem and is useful for finding minimum cost maximum
885:
773:
544:
617:
390:
686:
232:
191:
1058:
1017:
101:
1352:
1298:
302:
267:
153:
127:
1272:
334:
1380:
1326:
1240:
1214:
1194:
1168:
1148:
1118:
1098:
1078:
976:
956:
929:
450:
430:
410:
1602:
to this vertex. The capacity of all the new edges is 1 and their costs is 0. It is proved that there is minimum weight perfect bipartite matching in
787:
1674:
1123:
The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn):
907:
With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, one can find the maximum flow by performing a
700:
1870:
1727:
Refael Hassin (1983). "The minimum cost flow problem: A unifying approach to existing algorithms and a new tree search algorithm".
1130:(single-source). Require that a feasible solution to the minimum cost flow problem sends one unit of flow from a designated source
935:
1690:
Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems".
1965:
304:, with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge
1960:
465:
1439:
1624:
1456:
51:
1471:
901:
1699:
1449:
565:
1619:
1127:
339:
1492:
631:
1629:
1542:. The minimum weight bipartite matching problem or assignment problem is to find a perfect matching
1173:
1704:
1425:
1861:
1787:
1658:
1461:
1392:
1219:
196:
158:
1552:
whose total weight is minimized. The idea is to reduce this problem to a network flow problem.
1670:
1654:
1022:
981:
68:
1917:
1909:
1879:
1841:
1803:
1791:
1767:
1736:
1709:
1331:
1277:
272:
237:
132:
106:
43:
1245:
307:
1825:
1501:
1476:
1398:
Apart from that, many combinatorial algorithms exist. Some of them are generalizations of
1946:
The MCFClass C++ project library with some minimum cost flow and shortest path algorithms
1357:
1303:
1897:
1662:
1464:
1225:
1199:
1179:
1153:
1133:
1103:
1083:
1063:
961:
941:
914:
435:
415:
395:
63:
1954:
1900:(1997). "A polynomial time primal network simplex algorithm for minimum cost flows".
1865:
1772:
1755:
908:
1945:
1941:
LEMON C++ library with several maximum flow and minimum cost circulation algorithms
1821:
1399:
47:
39:
1756:"Two strongly polynomial cut cancelling algorithms for minimum cost network flow"
17:
46:
to find the cheapest possible way of sending a certain amount of flow through a
1830:"Theoretical improvements in algorithmic efficiency for network flow problems"
880:{\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}
1496:
Reducing
Minimum weight bipartite matching to minimum cost max flow problem
1448:: a primal-dual approach, which can be viewed as the generalization of the
1883:
1846:
1829:
1794:(1989). "Finding minimum-cost circulations by canceling negative cycles".
1713:
1868:(1990). "Finding minimum-cost circulations by successive approximation".
1807:
1922:
1913:
1740:
1395:, since we optimize a linear function, and all constraints are linear.
768:{\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t}
1491:
1438:: dual methods, which can be viewed as the generalization of the
1405:
Well-known fundamental algorithms (they have many variations):
1940:
1522:, the goal is to find the maximum cardinality matching in
1222:. Suppose that each partite set in the bipartition has
1754:
Thomas R. Ervolina & S. Thomas McCormick (1993).
1360:
1334:
1306:
1280:
1248:
1228:
1202:
1182:
1156:
1136:
1106:
1086:
1066:
1025:
984:
964:
944:
917:
790:
703:
634:
568:
468:
438:
418:
398:
342:
310:
275:
240:
199:
161:
135:
109:
71:
539:{\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}
1667:
1374:
1346:
1320:
1292:
1266:
1234:
1208:
1188:
1162:
1142:
1112:
1092:
1072:
1052:
1011:
970:
950:
923:
879:
767:
680:
611:
538:
444:
424:
404:
384:
328:
296:
261:
226:
185:
147:
121:
95:
455:The definition of the problem is to minimize the
1391:The minimum cost flow problem can be solved by
8:
1606:if and only if there a minimum cost flow in
1402:, others use entirely different approaches.
1582:. Assign the capacity of all the edges in
1921:
1845:
1771:
1703:
1364:
1359:
1333:
1310:
1305:
1279:
1247:
1227:
1201:
1181:
1155:
1135:
1105:
1085:
1065:
1024:
983:
963:
943:
916:
841:
832:
796:
791:
789:
745:
709:
704:
702:
635:
633:
569:
567:
473:
467:
437:
417:
397:
392:. The problem requires an amount of flow
341:
309:
274:
239:
198:
160:
134:
108:
70:
1242:vertices, and denote the bipartition by
1649:
1647:
1645:
1641:
1598:and connect all vertices inside group
1590:and connect it to all the vertices in
1538:be a weight function on the edges of
1382:. Each edge is to have unit capacity.
7:
1170:. Give all edges infinite capacity.
612:{\displaystyle \,f(u,v)\leq c(u,v)}
1871:Mathematics of Operations Research
385:{\displaystyle f(u,v)\cdot a(u,v)}
25:
1488:Minimum weight bipartite matching
27:Mathematical optimization problem
936:minimum cost circulation problem
681:{\displaystyle \,f(u,v)=-f(v,u)}
1460:: a specialized version of the
1261:
1249:
1060:, forcing the total flow from
1041:
1029:
1000:
988:
868:
856:
823:
811:
736:
724:
675:
663:
651:
639:
606:
594:
585:
573:
533:
521:
512:
500:
486:
474:
379:
367:
358:
346:
323:
311:
291:
279:
256:
244:
215:
203:
174:
162:
90:
78:
1:
1773:10.1016/0166-218x(93)90025-j
1760:Discrete Applied Mathematics
1422:Minimum mean cycle canceling
459:of the flow over all edges:
1526:that has minimum cost. Let
227:{\displaystyle c(u,v)>0}
1982:
1625:GNU Linear Programming Kit
1586:to 1. Add a source vertex
1412:: a general primal method.
895:Relation to other problems
186:{\displaystyle (u,v)\in E}
1457:Network simplex algorithm
934:A related problem is the
52:network simplex algorithm
32:minimum-cost flow problem
1902:Mathematical Programming
1729:Mathematical Programming
1440:Ford–Fulkerson algorithm
1432:Successive shortest path
1418:: a general dual method.
1176:. Choose a large demand
1053:{\displaystyle l(t,s)=d}
1012:{\displaystyle c(t,s)=d}
1594:and add a sink vertex
1472:Out-of-kilter algorithm
1400:maximum flow algorithms
412:to be sent from source
96:{\displaystyle G=(V,E)}
1669:. Prentice-Hall, Inc.
1497:
1450:push-relabel algorithm
1376:
1348:
1347:{\displaystyle y\in Y}
1322:
1294:
1293:{\displaystyle x\in X}
1268:
1236:
1210:
1190:
1164:
1144:
1114:
1094:
1074:
1054:
1013:
972:
952:
925:
881:
769:
682:
613:
540:
446:
426:
406:
386:
330:
298:
297:{\displaystyle a(u,v)}
263:
262:{\displaystyle f(u,v)}
228:
187:
149:
148:{\displaystyle t\in V}
123:
122:{\displaystyle s\in V}
97:
1966:Mathematical problems
1884:10.1287/moor.15.3.430
1847:10.1145/321694.321699
1714:10.1287/mnsc.14.3.205
1495:
1377:
1349:
1323:
1295:
1269:
1267:{\displaystyle (X,Y)}
1237:
1211:
1191:
1165:
1150:to a designated sink
1145:
1128:Shortest path problem
1115:
1095:
1075:
1055:
1014:
973:
953:
926:
882:
770:
683:
614:
549:with the constraints
541:
447:
427:
407:
387:
331:
329:{\displaystyle (u,v)}
299:
264:
229:
188:
150:
124:
103:with a source vertex
98:
1961:Network flow problem
1630:Network flow problem
1358:
1332:
1304:
1278:
1246:
1226:
1200:
1180:
1174:Maximum flow problem
1154:
1134:
1104:
1084:
1064:
1023:
982:
962:
942:
915:
788:
701:
632:
566:
558:Capacity constraints
466:
436:
416:
396:
340:
308:
273:
238:
197:
159:
133:
107:
69:
62:A flow network is a
1862:Goldberg, Andrew V.
1808:10.1145/76359.76368
1620:LEMON (C++ library)
1426:strongly polynomial
1375:{\displaystyle 1/n}
1321:{\displaystyle 1/n}
747: for all
1914:10.1007/bf02614365
1834:Journal of the ACM
1796:Journal of the ACM
1788:Andrew V. Goldberg
1741:10.1007/bf02591772
1692:Management Science
1659:Thomas L. Magnanti
1498:
1462:linear programming
1393:linear programming
1372:
1344:
1318:
1290:
1264:
1232:
1220:Assignment problem
1206:
1186:
1160:
1140:
1110:
1090:
1070:
1050:
1009:
968:
948:
921:
877:
852:
807:
765:
720:
678:
609:
536:
496:
442:
422:
402:
382:
326:
294:
259:
224:
183:
155:, where each edge
145:
129:and a sink vertex
119:
93:
1866:Tarjan, Robert E.
1676:978-0-13-617549-0
1655:Ravindra K. Ahuja
1235:{\displaystyle n}
1209:{\displaystyle d}
1189:{\displaystyle d}
1163:{\displaystyle t}
1143:{\displaystyle s}
1113:{\displaystyle d}
1093:{\displaystyle t}
1073:{\displaystyle s}
971:{\displaystyle s}
951:{\displaystyle t}
924:{\displaystyle d}
890:
889:
837:
835:
792:
748:
705:
693:Flow conservation
469:
445:{\displaystyle t}
425:{\displaystyle s}
405:{\displaystyle d}
18:Minimum cost flow
16:(Redirected from
1973:
1928:
1927:
1925:
1894:
1888:
1887:
1858:
1852:
1851:
1849:
1818:
1812:
1811:
1792:Robert E. Tarjan
1784:
1778:
1777:
1775:
1751:
1745:
1744:
1724:
1718:
1717:
1707:
1687:
1681:
1680:
1651:
1581:
1551:
1521:
1436:capacity scaling
1381:
1379:
1378:
1373:
1368:
1353:
1351:
1350:
1345:
1327:
1325:
1324:
1319:
1314:
1299:
1297:
1296:
1291:
1273:
1271:
1270:
1265:
1241:
1239:
1238:
1233:
1215:
1213:
1212:
1207:
1195:
1193:
1192:
1187:
1169:
1167:
1166:
1161:
1149:
1147:
1146:
1141:
1119:
1117:
1116:
1111:
1099:
1097:
1096:
1091:
1079:
1077:
1076:
1071:
1059:
1057:
1056:
1051:
1019:and lower bound
1018:
1016:
1015:
1010:
978:, with capacity
977:
975:
974:
969:
957:
955:
954:
949:
930:
928:
927:
922:
886:
884:
883:
878:
851:
836:
833:
806:
774:
772:
771:
766:
749:
746:
719:
687:
685:
684:
679:
618:
616:
615:
610:
554:
553:
545:
543:
542:
537:
495:
451:
449:
448:
443:
431:
429:
428:
423:
411:
409:
408:
403:
391:
389:
388:
383:
335:
333:
332:
327:
303:
301:
300:
295:
268:
266:
265:
260:
233:
231:
230:
225:
192:
190:
189:
184:
154:
152:
151:
146:
128:
126:
125:
120:
102:
100:
99:
94:
44:decision problem
21:
1981:
1980:
1976:
1975:
1974:
1972:
1971:
1970:
1951:
1950:
1937:
1932:
1931:
1896:
1895:
1891:
1860:
1859:
1855:
1826:Richard M. Karp
1820:
1819:
1815:
1786:
1785:
1781:
1753:
1752:
1748:
1726:
1725:
1721:
1705:10.1.1.228.7696
1689:
1688:
1684:
1677:
1653:
1652:
1643:
1638:
1616:
1556:
1543:
1504:
1502:bipartite graph
1490:
1485:
1477:D. R. Fulkerson
1410:Cycle canceling
1389:
1356:
1355:
1330:
1329:
1302:
1301:
1276:
1275:
1244:
1243:
1224:
1223:
1198:
1197:
1178:
1177:
1152:
1151:
1132:
1131:
1102:
1101:
1082:
1081:
1062:
1061:
1021:
1020:
980:
979:
960:
959:
940:
939:
913:
912:
897:
834: and
786:
785:
699:
698:
630:
629:
564:
563:
464:
463:
434:
433:
414:
413:
394:
393:
338:
337:
306:
305:
271:
270:
236:
235:
195:
194:
157:
156:
131:
130:
105:
104:
67:
66:
60:
28:
23:
22:
15:
12:
11:
5:
1979:
1977:
1969:
1968:
1963:
1953:
1952:
1949:
1948:
1943:
1936:
1935:External links
1933:
1930:
1929:
1908:(2): 109–129.
1898:James B. Orlin
1889:
1878:(3): 430–466.
1853:
1840:(2): 248–264.
1813:
1802:(4): 873–886.
1779:
1766:(2): 133–165.
1746:
1719:
1698:(3): 205–220.
1682:
1675:
1663:James B. Orlin
1640:
1639:
1637:
1634:
1633:
1632:
1627:
1622:
1615:
1612:
1489:
1486:
1484:
1481:
1480:
1479:
1468:
1465:simplex method
1453:
1443:
1429:
1419:
1413:
1388:
1385:
1384:
1383:
1371:
1367:
1363:
1343:
1340:
1337:
1328:and give each
1317:
1313:
1309:
1289:
1286:
1283:
1263:
1260:
1257:
1254:
1251:
1231:
1217:
1205:
1185:
1171:
1159:
1139:
1109:
1089:
1069:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1008:
1005:
1002:
999:
996:
993:
990:
987:
967:
958:to the source
947:
920:
896:
893:
892:
891:
888:
887:
876:
873:
870:
867:
864:
861:
858:
855:
850:
847:
844:
840:
831:
828:
825:
822:
819:
816:
813:
810:
805:
802:
799:
795:
783:
776:
775:
764:
761:
758:
755:
752:
744:
741:
738:
735:
732:
729:
726:
723:
718:
715:
712:
708:
696:
689:
688:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
627:
620:
619:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
561:
547:
546:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
494:
491:
488:
485:
482:
479:
476:
472:
441:
421:
401:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
325:
322:
319:
316:
313:
293:
290:
287:
284:
281:
278:
258:
255:
252:
249:
246:
243:
223:
220:
217:
214:
211:
208:
205:
202:
182:
179:
176:
173:
170:
167:
164:
144:
141:
138:
118:
115:
112:
92:
89:
86:
83:
80:
77:
74:
64:directed graph
59:
56:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1978:
1967:
1964:
1962:
1959:
1958:
1956:
1947:
1944:
1942:
1939:
1938:
1934:
1924:
1919:
1915:
1911:
1907:
1903:
1899:
1893:
1890:
1885:
1881:
1877:
1873:
1872:
1867:
1863:
1857:
1854:
1848:
1843:
1839:
1835:
1831:
1827:
1823:
1817:
1814:
1809:
1805:
1801:
1797:
1793:
1789:
1783:
1780:
1774:
1769:
1765:
1761:
1757:
1750:
1747:
1742:
1738:
1734:
1730:
1723:
1720:
1715:
1711:
1706:
1701:
1697:
1693:
1686:
1683:
1678:
1672:
1668:
1664:
1660:
1656:
1650:
1648:
1646:
1642:
1635:
1631:
1628:
1626:
1623:
1621:
1618:
1617:
1613:
1611:
1609:
1605:
1601:
1597:
1593:
1589:
1585:
1579:
1575:
1571:
1567:
1563:
1559:
1553:
1550:
1546:
1541:
1537:
1533:
1529:
1525:
1519:
1515:
1511:
1507:
1503:
1494:
1487:
1482:
1478:
1474:
1473:
1469:
1466:
1463:
1459:
1458:
1454:
1451:
1447:
1444:
1441:
1437:
1433:
1430:
1427:
1423:
1420:
1417:
1416:Cut canceling
1414:
1411:
1408:
1407:
1406:
1403:
1401:
1396:
1394:
1386:
1369:
1365:
1361:
1341:
1338:
1335:
1315:
1311:
1307:
1287:
1284:
1281:
1258:
1255:
1252:
1229:
1221:
1218:
1203:
1183:
1175:
1172:
1157:
1137:
1129:
1126:
1125:
1124:
1121:
1107:
1087:
1067:
1047:
1044:
1038:
1035:
1032:
1026:
1006:
1003:
997:
994:
991:
985:
965:
945:
937:
932:
918:
910:
909:binary search
905:
903:
894:
874:
871:
865:
862:
859:
853:
848:
845:
842:
838:
829:
826:
820:
817:
814:
808:
803:
800:
797:
793:
784:
781:
780:Required flow
778:
777:
762:
759:
756:
753:
750:
742:
739:
733:
730:
727:
721:
716:
713:
710:
706:
697:
694:
691:
690:
672:
669:
666:
660:
657:
654:
648:
645:
642:
636:
628:
625:
624:Skew symmetry
622:
621:
603:
600:
597:
591:
588:
582:
579:
576:
570:
562:
559:
556:
555:
552:
551:
550:
530:
527:
524:
518:
515:
509:
506:
503:
497:
492:
489:
483:
480:
477:
470:
462:
461:
460:
458:
453:
439:
419:
399:
376:
373:
370:
364:
361:
355:
352:
349:
343:
320:
317:
314:
288:
285:
282:
276:
253:
250:
247:
241:
221:
218:
212:
209:
206:
200:
193:has capacity
180:
177:
171:
168:
165:
142:
139:
136:
116:
113:
110:
87:
84:
81:
75:
72:
65:
57:
55:
53:
49:
45:
41:
37:
33:
19:
1905:
1901:
1892:
1875:
1869:
1856:
1837:
1833:
1822:Jack Edmonds
1816:
1799:
1795:
1782:
1763:
1759:
1749:
1732:
1728:
1722:
1695:
1691:
1685:
1666:
1607:
1603:
1599:
1595:
1591:
1587:
1583:
1577:
1573:
1569:
1565:
1561:
1557:
1554:
1548:
1544:
1539:
1535:
1531:
1527:
1523:
1517:
1513:
1509:
1505:
1499:
1470:
1455:
1446:Cost scaling
1445:
1435:
1431:
1421:
1415:
1409:
1404:
1397:
1390:
1274:. Give each
1122:
933:
906:
898:
779:
692:
623:
557:
548:
456:
454:
61:
48:flow network
40:optimization
35:
31:
29:
1923:1721.1/2584
1735:: 228–239.
1483:Application
1424:: a simple
1100:to also be
1955:Categories
1636:References
1428:algorithm.
457:total cost
58:Definition
1700:CiteSeerX
1387:Solutions
1339:∈
1285:∈
902:matchings
846:∈
839:∑
801:∈
794:∑
754:≠
714:∈
707:∑
658:−
589:≤
516:⋅
490:∈
471:∑
362:⋅
269:and cost
178:∈
140:∈
114:∈
1828:(1972).
1665:(1993).
1614:See also
1608:G′
1600:B′
1592:A′
1584:E′
1574:E′
1562:V′
1558:G′
1500:Given a
432:to sink
38:) is an
1354:demand
1300:supply
234:, flow
1864:&
1824:&
1790:&
1702:
1673:
1661:&
1671:ISBN
1555:Let
1434:and
219:>
42:and
36:MCFP
30:The
1918:hdl
1910:doi
1880:doi
1842:doi
1804:doi
1768:doi
1737:doi
1710:doi
1610:.
1560:= (
1508:= (
1475:by
1080:to
911:on
336:is
1957::
1916:.
1906:78
1904:.
1876:15
1874:.
1838:19
1836:.
1832:.
1800:36
1798:.
1762:.
1758:.
1733:25
1731:.
1708:.
1696:14
1694:.
1657:;
1644:^
1576:=
1572:,
1568:∪
1564:=
1547:⊆
1534:→
1530::
1516:,
1512:∪
1120:.
931:.
904:.
452:.
54:.
1926:.
1920::
1912::
1886:.
1882::
1850:.
1844::
1810:.
1806::
1776:.
1770::
1764:4
1743:.
1739::
1716:.
1712::
1679:.
1604:G
1596:t
1588:s
1580:)
1578:E
1570:B
1566:A
1549:E
1545:M
1540:E
1536:R
1532:E
1528:w
1524:G
1520:)
1518:E
1514:B
1510:A
1506:G
1467:.
1452:.
1442:.
1370:n
1366:/
1362:1
1342:Y
1336:y
1316:n
1312:/
1308:1
1288:X
1282:x
1262:)
1259:Y
1256:,
1253:X
1250:(
1230:n
1216:.
1204:d
1184:d
1158:t
1138:s
1108:d
1088:t
1068:s
1048:d
1045:=
1042:)
1039:s
1036:,
1033:t
1030:(
1027:l
1007:d
1004:=
1001:)
998:s
995:,
992:t
989:(
986:c
966:s
946:t
919:d
875:d
872:=
869:)
866:t
863:,
860:w
857:(
854:f
849:V
843:w
830:d
827:=
824:)
821:w
818:,
815:s
812:(
809:f
804:V
798:w
782::
763:t
760:,
757:s
751:u
743:0
740:=
737:)
734:w
731:,
728:u
725:(
722:f
717:V
711:w
695::
676:)
673:u
670:,
667:v
664:(
661:f
655:=
652:)
649:v
646:,
643:u
640:(
637:f
626::
607:)
604:v
601:,
598:u
595:(
592:c
586:)
583:v
580:,
577:u
574:(
571:f
560::
534:)
531:v
528:,
525:u
522:(
519:f
513:)
510:v
507:,
504:u
501:(
498:a
493:E
487:)
484:v
481:,
478:u
475:(
440:t
420:s
400:d
380:)
377:v
374:,
371:u
368:(
365:a
359:)
356:v
353:,
350:u
347:(
344:f
324:)
321:v
318:,
315:u
312:(
292:)
289:v
286:,
283:u
280:(
277:a
257:)
254:v
251:,
248:u
245:(
242:f
222:0
216:)
213:v
210:,
207:u
204:(
201:c
181:E
175:)
172:v
169:,
166:u
163:(
143:V
137:t
117:V
111:s
91:)
88:E
85:,
82:V
79:(
76:=
73:G
34:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
