36: and is described here. The analog of steady state flow in a network of nodes and arcs may describe a variety of processes. Examples include transportation systems & personnel assignment actions. Arcs generally have cost & capacity parameters. A recurring problem is trying to determine the minimum cost route between two points in a capacitated network. The idea of the algorithm is to identify out-of-kilter arcs and modify the flow network until all arcs are in-kilter and a minimum cost flow has been reached. The algorithm can be used to minimize the total cost of a constrained flow in an oriented network.
44:
To begin, the algorithm takes a single cycle and a set of node numbers. It then searches for out-of-kilter arcs. If none are found the algorithm is complete. If the flow needs to be increased or decreased to bring an arc into kilter, the algorithm will look for a path that increases or decreases the
542:
853:
667:
408:
45:
flow respectively. If no paths are found to improve the system then there is no feasible flow. This is done until all arcs are in-kilter, at which point the algorithm is complete.
833:
91:
714:
589:
326:
290:
761:
348:. The capacities may be either finite, or infinite on some or all arcs for either the lower or upper bounds. The problem that is at hand to solve is to minimize:
254:
158:
187:
719:
If a given flow x satisfies (1), then the flow is conserved at each node and we call the flow a circulation. If the flow x satisfies (2) we say it is feasible.
346:
227:
207:
131:
111:
941:
415:
967:
599:
925:
25:
889:
351:
772:
870:
51:
672:
547:
295:
259:
862:
734:
232:
136:
163:
33:
851:
D. R. Fulkerson (March 1961). "An Out-of-Kilter Method for
Minimal-Cost Flow Problems".
331:
212:
192:
116:
96:
961:
29:
919:
21:
874:
537:{\displaystyle \sum _{j:j~(i,i^{1})}x(j)-\sum _{j:j~(i^{1},i)}x(j)=0}
866:
48:
Suppose that the network has n nodes and m oriented arcs. We write
891:
The out-of-kilter algorithm: a primer — Memorandum RM-5472-PR
854:
Journal of the
Society for Industrial and Applied Mathematics
328:
to be the lower and upper capacity bounds on the flow in arc
897:. Santa Monica, California, USA: The Rand Corporation
775:
737:
675:
602:
550:
418:
354:
334:
298:
262:
235:
215:
195:
166:
139:
119:
99:
54:
827:
755:
708:
661:
583:
536:
402:
340:
320:
284:
248:
221:
201:
181:
152:
125:
105:
85:
766:Dominant computation is shortest path computation
662:{\displaystyle c^{-}(j)\leq x(j)\leq c^{+}(j)}
8:
888:Durbin, EP; Kroenke, DM (December 1967).
786:
774:
736:
674:
644:
607:
601:
549:
499:
479:
449:
423:
417:
370:
359:
353:
333:
303:
297:
267:
261:
240:
234:
214:
194:
165:
144:
138:
118:
98:
74:
53:
932:
843:
403:{\displaystyle \sum _{j=1}^{m}d(j)x(j)}
940:Cambridge, University of (July 2012).
7:
828:{\displaystyle O(m^{2}U+mUn\log(n))}
24:that computes the solution to the
14:
731:The algorithm terminates within
822:
819:
813:
779:
750:
741:
656:
650:
634:
628:
619:
613:
525:
519:
511:
492:
469:
463:
455:
436:
397:
391:
385:
379:
315:
309:
279:
273:
176:
170:
80:
61:
32:. It was published in 1961 by
1:
86:{\displaystyle j~(i,i^{1})}
984:
709:{\displaystyle j=1,....,n}
584:{\displaystyle i=1,....,n}
942:"Out of Kilter Algorithm"
26:minimum-cost flow problem
321:{\displaystyle c^{+}(j)}
285:{\displaystyle c^{-}(j)}
921:Algoritmo Out-of-Kilter
18:out-of-kilter algorithm
829:
757:
710:
663:
585:
538:
404:
375:
342:
322:
286:
250:
223:
203:
189:be the flow along arc
183:
154:
127:
107:
87:
830:
758:
756:{\displaystyle O(mU)}
711:
664:
586:
539:
405:
355:
343:
323:
287:
251:
249:{\displaystyle i^{1}}
224:
204:
184:
155:
153:{\displaystyle i^{1}}
128:
108:
88:
968:Network flow problem
773:
735:
673:
600:
548:
416:
352:
332:
296:
260:
233:
213:
193:
182:{\displaystyle x(j)}
164:
137:
117:
97:
52:
949:www.maths.cam.ac.uk
825:
769:Total runtime is:
753:
706:
659:
581:
534:
515:
459:
400:
338:
318:
282:
246:
219:
199:
179:
150:
133:and terminal node
123:
103:
83:
491:
475:
435:
419:
341:{\displaystyle j}
222:{\displaystyle i}
202:{\displaystyle j}
126:{\displaystyle i}
113:has initial node
106:{\displaystyle j}
60:
975:
953:
952:
946:
937:
922:
906:
905:
903:
902:
896:
885:
879:
878:
848:
834:
832:
831:
826:
791:
790:
762:
760:
759:
754:
715:
713:
712:
707:
668:
666:
665:
660:
649:
648:
612:
611:
590:
588:
587:
582:
543:
541:
540:
535:
514:
504:
503:
489:
458:
454:
453:
433:
409:
407:
406:
401:
374:
369:
347:
345:
344:
339:
327:
325:
324:
319:
308:
307:
291:
289:
288:
283:
272:
271:
255:
253:
252:
247:
245:
244:
228:
226:
225:
220:
208:
206:
205:
200:
188:
186:
185:
180:
159:
157:
156:
151:
149:
148:
132:
130:
129:
124:
112:
110:
109:
104:
92:
90:
89:
84:
79:
78:
58:
983:
982:
978:
977:
976:
974:
973:
972:
958:
957:
956:
944:
939:
938:
934:
920:
916:
909:
900:
898:
894:
887:
886:
882:
867:10.1137/0109002
850:
849:
845:
841:
782:
771:
770:
733:
732:
725:
671:
670:
640:
603:
598:
597:
546:
545:
495:
445:
414:
413:
350:
349:
330:
329:
299:
294:
293:
263:
258:
257:
236:
231:
230:
211:
210:
191:
190:
162:
161:
140:
135:
134:
115:
114:
95:
94:
70:
50:
49:
42:
34:D. R. Fulkerson
12:
11:
5:
981:
979:
971:
970:
960:
959:
955:
954:
931:
930:
929:
915:
914:External links
912:
908:
907:
880:
842:
840:
837:
836:
835:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
789:
785:
781:
778:
767:
764:
752:
749:
746:
743:
740:
724:
721:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
658:
655:
652:
647:
643:
639:
636:
633:
630:
627:
624:
621:
618:
615:
610:
606:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
533:
530:
527:
524:
521:
518:
513:
510:
507:
502:
498:
494:
488:
485:
482:
478:
474:
471:
468:
465:
462:
457:
452:
448:
444:
441:
438:
432:
429:
426:
422:
399:
396:
393:
390:
387:
384:
381:
378:
373:
368:
365:
362:
358:
337:
317:
314:
311:
306:
302:
281:
278:
275:
270:
266:
243:
239:
218:
198:
178:
175:
172:
169:
147:
143:
122:
102:
82:
77:
73:
69:
66:
63:
57:
41:
38:
13:
10:
9:
6:
4:
3:
2:
980:
969:
966:
965:
963:
950:
943:
936:
933:
927:
923:
918:
917:
913:
911:
893:
892:
884:
881:
876:
872:
868:
864:
860:
856:
855:
847:
844:
838:
816:
810:
807:
804:
801:
798:
795:
792:
787:
783:
776:
768:
765:
747:
744:
738:
730:
729:
728:
722:
720:
717:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
653:
645:
641:
637:
631:
625:
622:
616:
608:
604:
595:
592:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
531:
528:
522:
516:
508:
505:
500:
496:
486:
483:
480:
476:
472:
466:
460:
450:
446:
442:
439:
430:
427:
424:
420:
411:
394:
388:
382:
376:
371:
366:
363:
360:
356:
335:
312:
304:
300:
276:
268:
264:
241:
237:
216:
196:
173:
167:
145:
141:
120:
100:
75:
71:
67:
64:
55:
46:
39:
37:
35:
31:
27:
23:
19:
948:
935:
928:(in Spanish)
910:
899:. Retrieved
890:
883:
861:(1): 18–27.
858:
852:
846:
726:
718:
596:
593:
412:
410:subject to:
47:
43:
30:flow network
17:
15:
256:). Define
209:(from node
901:2018-01-16
839:References
763:iterations
723:Complexity
811:
727:Runtime:
669:for each
638:≤
623:≤
609:−
544:for each
477:∑
473:−
421:∑
357:∑
269:−
40:Algorithm
22:algorithm
962:Category
229:to node
926:YouTube
875:2099013
594:, and:
160:. Let
93:if arc
873:
490:
434:
59:
20:is an
945:(PDF)
895:(PDF)
871:JSTOR
28:in a
716:(2)
591:(1)
292:and
16:The
924:on
863:doi
808:log
964::
947:.
869:.
857:.
951:.
904:.
877:.
865::
859:9
823:)
820:)
817:n
814:(
805:n
802:U
799:m
796:+
793:U
788:2
784:m
780:(
777:O
751:)
748:U
745:m
742:(
739:O
704:n
701:,
698:.
695:.
692:.
689:.
686:,
683:1
680:=
677:j
657:)
654:j
651:(
646:+
642:c
635:)
632:j
629:(
626:x
620:)
617:j
614:(
605:c
579:n
576:,
573:.
570:.
567:.
564:.
561:,
558:1
555:=
552:i
532:0
529:=
526:)
523:j
520:(
517:x
512:)
509:i
506:,
501:1
497:i
493:(
487:j
484::
481:j
470:)
467:j
464:(
461:x
456:)
451:1
447:i
443:,
440:i
437:(
431:j
428::
425:j
398:)
395:j
392:(
389:x
386:)
383:j
380:(
377:d
372:m
367:1
364:=
361:j
336:j
316:)
313:j
310:(
305:+
301:c
280:)
277:j
274:(
265:c
242:1
238:i
217:i
197:j
177:)
174:j
171:(
168:x
146:1
142:i
121:i
101:j
81:)
76:1
72:i
68:,
65:i
62:(
56:j
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.