{"id":3910,"date":"2016-08-24T09:21:40","date_gmt":"2016-08-24T08:21:40","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3910"},"modified":"2022-12-03T22:59:07","modified_gmt":"2022-12-03T21:59:07","slug":"algorithme-out-of-kilter","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/out-of-kilter-algorithm\/","title":{"rendered":"Out-of-Kilter algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3910\" class=\"elementor elementor-3910\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-efb2af4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"efb2af4\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-862500c\" data-id=\"862500c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2411965 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2411965\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Maximum flow problem<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1090814\" data-id=\"1090814\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8ecd9f4 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8ecd9f4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-f7f1f43\" data-id=\"f7f1f43\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bdd8712 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"bdd8712\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/www.rand.org\/content\/dam\/rand\/pubs\/research_memoranda\/2008\/RM5472.pdf\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-284489a1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"284489a1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-58e9a757\" data-id=\"58e9a757\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5667251a elementor-widget elementor-widget-text-editor\" data-id=\"5667251a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/out-of-kilter-algorithm\/#Algorithme-out-of-kilter\" >Out-of-kilter algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-out-of-kilter\"><\/span>Out-of-kilter algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Also called <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> of Fulkerson-Ford (not to be confused with the algorithm of <a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">maximum flow<\/a>), the out-of-kilter algorithm calculates a maximum flow at minimum cost with min and max bounds on the edges.<\/p>\n\n<p>We will say that an edge is In-Kilter if it satisfies the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/complementary-deviations\/\">additional deviations<\/a>, otherwise we&#039;ll say it&#039;s Out-of-Kilter (kilter means &quot;in good condition&quot;).<\/p>\n\n<p>The following explanations will not be translated for the sake of understanding the underlying logic in the sense of &quot;kilter&quot;.<\/p>\n\n<p><b>Theorem: <\/b>A feasible solution x * is an optimal solution of the MCF problem if and only if for some set of node potentials \u03c0, the reduced costs and flow values satisfy the following complementary slackness conditions for every edge (u, v) in the <b>network<\/b><b>:<\/b><\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4437\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1.png\" alt=\"out-of-kilter algorithm\" width=\"417\" height=\"166\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1.png 417w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1-300x119.png 300w\" sizes=\"(max-width: 417px) 100vw, 417px\" \/><\/figure>\n<\/div>\n\n<p>Which gives the following efficiency diagram:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4446 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2.png\" alt=\"out-of-kilter algorithm\" width=\"869\" height=\"356\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2.png 869w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2-300x123.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2-768x315.png 768w\" sizes=\"(max-width: 869px) 100vw, 869px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4452 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4.png\" alt=\"out-of-kilter algorithm\" width=\"897\" height=\"386\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4.png 897w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4-300x129.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4-768x330.png 768w\" sizes=\"(max-width: 897px) 100vw, 897px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4455 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5.png\" alt=\"out-of-kilter algorithm\" width=\"867\" height=\"397\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5.png 867w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5-300x137.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5-768x352.png 768w\" sizes=\"(max-width: 867px) 100vw, 867px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4458 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6.png\" alt=\"out-of-kilter algorithm\" width=\"840\" height=\"427\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6.png 840w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6-300x153.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6-768x390.png 768w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><\/figure>\n<\/div>\n\n<p>Correctness:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>Kilter numbers of the edges are non-increasing\n<ul>\n<li>Two operations in the algorithm affect the kilter numbers of arcs:\n<ul>\n<li>updating node potentials<\/li>\n<li>augmenting flow along the cycle <i>W<\/i><\/li>\n<\/ul>\n<\/li>\n<li>At each iteration the algorithm selects and edge (p, q)\n<ul>\n<li>Makes it in-kilter during potential update<\/li>\n<li>decrease it by at least 1 by the flow increase<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n<p>The algorithm terminate within O (mU) iterations, total runtime is: O (m ^ 2 U + mUn log n)<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Maximum flow problem Home page Wiki Out-of-kilter algorithm Also called the Fulkerson-Ford algorithm (not to be confused with the maximum flow algorithm), the out-of-kilter algorithm \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":3587,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3910","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3910","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=3910"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3910\/revisions"}],"predecessor-version":[{"id":18459,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3910\/revisions\/18459"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3587"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=3910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}