The Out-of-Kilter Algorithm for Network Flows in IENG 516
undefined
PRESENTED TO: ASSIS.PROF.DR. SAHAND DANESHVAR
PRESENTED BY: YAHYA EL OSMAN EL DANDACHI 15500727
MOHAMMAD A. KH. HAMDAN 16500161
Out-of-Kilter Algorithm
Network Flows IENG 516
Introduction
9/30/2024
2
The out of kilter algorithm is an example of a primal-dual
algorithm.
It works on both the primal problem (edges of the network) and
the dual problem (nodes) in successive phases to find a feasible
solution, and then to optimize the problem.
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
What do we keep track of ?
We will have a variable for each node
w
i
, and the flows through each edge
of the original network.
As well as these variables, each edge will be given a kilter state and a
kilter number
k
ij
.
Edges are either “in kilter” or “out of kilter”.
We want all edges to be in kilter, so the algorithm keeps “in kilter” edges
in kilter, and brings “out of kilter” edges into kilter.
9/30/2024
3
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
THE OUT-OF-KILTER FORMULATION OF A MINIMAL-COST
NETWORK FLOW PROBLEM
We shall assume that
Cij, lij,
and
Uij
are integers
9/30/2024
4
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Algorithm explained
9/30/2024
5
We will have a variable for each node
w
i
, and the flows through
each edge of the original network.
As well as these variables, each edge will be given a kilter state
and a kilter number
k
ij
.
Edges are either “in kilter” or “out of kilter”.
We
want all edges to be in kilter
, so the algorithm keeps “in
kilter” edges in kilter, and
brings “out of kilter” edges into
kilter.
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Kilter Numbers Rules
9/30/2024
6
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
9/30/2024
7
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Starting the algorithm
When we start we have a set of upper and lower bounds for all edges in
the network and the cost of sending units of flow along each edge.
We may need to add an artificial edge from the sink to the source, or even
add an artificial node to handle some formulations.
All flows
x
ij
and the
w
i
values for the nodes can be set to zero in this initial
phase. This makes some working simple.
9/30/2024
8
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The primal phase
The primal phase of the algorithm finds the most out of kilter edge of the
network and tries to being it into kilter.
We find the reduced costs of the edges of our network, and determine the
kilter states and numbers for all edges.
The edge with the highest kilter number is chosen and we then look to
augment the flows of the network by finding a cycle through the
potential changes of our network flows.
The Primal Phase
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
10
The Dual Phase
9/30/2024
11
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The complementary Slackness Condition
9/30/2024
12
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
9/30/2024
13
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Kilter States and Kilter Numbers
9/30/2024
14
A kilter number can be thought of as the
change required to bring a flow into
feasibility and eventually optimality.
So we can add up all the kilter numbers
to find how far from optimality we are
at any given time.
An in kilter edge has a kilter number of
zero.
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Dual Phase and Variable Changes
9/30/2024
15
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Amount of Change
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
16
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
17
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
18
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
19
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
20
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
21
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
22
The Primal Phase
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
23
The First Dual Solution
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
24
The Second Dual Phase
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
25
The Optimal Solution
9/30/2024
Out of Kilter : Yahya Dandachi & Mohammad Hamdan
26
Delve into the Out-of-Kilter Algorithm, a primal-dual approach for optimizing network flows by balancing kilter states of edges and node variables. Learn about the formulation, tracking variables, algorithm explanation, kilter number rules, and initiating the process.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Network Flows IENG 516 Out-of-Kilter Algorithm PRESENTED TO: ASSIS.PROF.DR. SAHAND DANESHVAR PRESENTED BY: YAHYA EL OSMAN EL DANDACHI 15500727 MOHAMMAD A. KH. HAMDAN 16500161
Introduction 2 The out of kilter algorithm is an example of a primal-dual algorithm. It works on both the primal problem (edges of the network) and the dual problem (nodes) in successive phases to find a feasible solution, and then to optimize the problem. 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
What do we keep track of ? 3 We will have a variable for each node wi, and the flows through each edge of the original network. As well as these variables, each edge will be given a kilter state and a kilter number kij. Edges are either in kilter or out of kilter . We want all edges to be in kilter, so the algorithm keeps in kilter edges in kilter, and brings out of kilter edges into kilter. 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
THE OUT-OF-KILTER FORMULATION OF A MINIMAL-COST NETWORK FLOW PROBLEM 4 We shall assume that Cij, lij, and Uij are integers 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Algorithm explained 5 We will have a variable for each node wi, and the flows through each edge of the original network. As well as these variables, each edge will be given a kilter state and a kilter number kij. Edges are either in kilter or out of kilter . We want all edges to be in kilter, so the algorithm keeps in kilter edges in kilter, and brings out of kilter edges into kilter. 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Kilter Numbers Rules 6 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
7 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
Starting the algorithm 8 When we start we have a set of upper and lower bounds for all edges in the network and the cost of sending units of flow along each edge. We may need to add an artificial edge from the sink to the source, or even add an artificial node to handle some formulations. All flows xij and the wi values for the nodes can be set to zero in this initial phase. This makes some working simple. 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The primal phase The primal phase of the algorithm finds the most out of kilter edge of the network and tries to being it into kilter. We find the reduced costs of the edges of our network, and determine the kilter states and numbers for all edges. The edge with the highest kilter number is chosen and we then look to augment the flows of the network by finding a cycle through the potential changes of our network flows.
The Primal Phase 10 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Dual Phase 11 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The complementary Slackness Condition 12 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
13 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Kilter States and Kilter Numbers 14 A kilter number can be thought of as the change required to bring a flow into feasibility and eventually optimality. So we can add up all the kilter numbers to find how far from optimality we are at any given time. An in kilter edge has a kilter number of zero. 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Dual Phase and Variable Changes 15 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Amount of Change 16 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
17 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
18 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
19 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
20 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
21 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
22 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Primal Phase 23 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The First Dual Solution 24 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Second Dual Phase 25 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
The Optimal Solution 26 9/30/2024 Out of Kilter : Yahya Dandachi & Mohammad Hamdan
