# International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

# 7615cnc02

A MASS BALANCING THEOREM FOR THE
ECONOMICAL NETWORK FLOW
MAXIMISATION

Ziauddin Ursani1,2, Ahsan A. Ursani3,4 and David W. Corne1,2
1Heriot Watt University UK
2Route Monkey Ltd.
3South Asian University New Delhi India
4Mehran University of Engineering and Technology Sindh Pakistan

ABSTRACT

A mass balancing theorem (MBT) was recently introduced, concerning the role of ‘unbalanced nodes’ in the optimization of network flow. The MBT discovers and proves a flow-balancing property, which can be exploited in the design of network flow algorithms. Subsequently a number of such applications of the MBT have been explored for various types of flow-networks. These have included, in particular, single and multiple commodity networks with additional equipment of separators, which are present in various real world scenarios including the oil and gas industry. In this paper, the mass balancing theorem is revisited,and further developed to consider new network examples with embedded cycles. In doing so, algorithms based on the mass balancing method are extended to remove any undesirably saturated edges in the network, consequently reducing economic costs for flow-maximization in such networks.

KEY WORDS

Mass Balancing Theorem, Graph Theory, Flow Networks, Optimisation

1.INTRODUCTION

Flow maximization through networks has been a major problem under study for last several decades . This is because many real world problems can be formulated as a network problem such as optical networks , wireless networks , reliability networks [4,5], biological networks , production assembly networks  and social networks  etc

A typical flow network is a directed graph with a number of nodes connected through a number of edges with a limited capacity. A flow network also has a source node and a sink node. It is assumed that source node can produce a flow of unlimited quantity. The problem is to push maximum flow through the network from the source node to the sink node such that capacity of any edge is not violated and all nodes must be balanced nodes i.e. incoming and outgoing flow at the node is equal.

In 1956 a remarkable theorem on this network was developed which is popularly known as max flow- min-cut theorem [9, 10]. According to this theorem maximum flow through the network is equal to minimum cut of the network. The minimum cut of the network is defined as a cut of minimum size through the network that disconnects completely the source from the sink such that no flow from the source could pass to the sink. Based on this theorem, a number of approaches have been discovered to solve this problem. These approaches can be divided into two main branches, i.e. augmentation paths algorithms, [9-16] and pre-flow push algorithms [17-25]. Some novel ideas have also been discovered such as pseudo flows , draining algorithm , postflow-pull method  and the mass balancing theorem (MBT) .

The MBT discovered an interesting network property that the fully saturated network is actually balance of certain easily computable flow load on the either side of the minimum cut. Utilizing this property, a flow dissipation algorithm was developed to maximize the flow through the network. An interesting aspect of this algorithm is that it visits only unbalanced nodes rather than the whole network to maximize the flow. Therefore this algorithm has very important role to play in dynamic networks where the network continues changing its state. A change is marked by removal of edges Eand/or addition of E+ edges. Due to these changes each time maximum of 2( E+ + E) number of nodes becomes unbalanced. This number is only a small fraction of total number of nodes in the network and by visiting only those unbalanced nodes flow can be re-maximized for the modified network.

The usefulness of this theorem has already been proved in various types of networks in different application areas [30, 31]. In this paper mass balancing theorem is revisited again with intent to study its applicability in new example networks with embedded cycles. These cycles sometimes have undesirably saturated edges which may incur economic costs without contributing to any flow maximisation. Therefore mass balancing method is extended to remove these undesirably saturated edges in those cycles to produce most economical solution of the flow maximisation problem. This paper is structured as follows. Section 2 revisits the theorem with explanation through network examples with cycles. Section 3 extends mass balancing method to produce most economical solution for the flow maximisation on networks with cycles and finally section 4 concludes the paper and discusses the future work.

2.MASS BALANCING THEOREM-A REVISIT

MBT states that minimum cut in the flow network is a balance of certain flow load on either side of the minimum cut. This flow balance can be represented through the following fundamental equation.

``` ```

Where

` Figure 1 provides an example network to understand equation 1.`
` Figure 1: An example network with a minimum s-t cut`

In Figure 1, edge e2,3represents the minimum cut. If this edge is blocked or removed then no flow can pass from the source to the sink. To describe equation 1, let us divide this network into two disjoint subnetworks i.e., source subnetwork (network A) and sink subnetwork (network B) according to the following procedure.

1. Disconnect the edges representing minimum s-t cut so that no flow can pass from the source to the sink.
2. Connect broken edges of minimum cut from the source side with the newly created sink.
3. Connect broken edges of the minimum cut on the sink side with the newly created source.
4. Remove any additional edges that are not on the any path of the flow from source to the sink of the same subnetwork.

Following above procedure, the set of two disjoint subnetworks shown in Figure 2 can be deduced from the network in Figure 1.

` Figure 2: Two networks and deduced from network in Figure 1`

By substituting parameters from the networks in Figure 2 in equation 1 we get

` `

Where

ci,j= capacity of edge ei,j

di= dissipative flow at node i

By substituting the values of above parameters from Figure 2 in equation 2 we get

( 10 + 30) – (-10 + 20 ) = 30 = ( 30 + 20 ) + ( – 30+ 10)

From the above substitution of values it can be seen that fundamental equation 1 of the theorem holds on this example. The theorem holds true on any complex network.

2.1. MASS BALANCING METHOD FOR SINGLE COMMODITY NETWORK

Based on MBT a flow dissipation algorithm was devised to maximize the flow through the network which is re-described here briefly. Readers are requested to refer mass balancing theorem  for details. It is necessary to reintroduce some of the terminology related to MBT  to explain the algorithm. These terms are dissipative flow of node, dissipative flow of edge, dissipative flow of path, and the act of flow dissipation on path.

The dissipative flow of node is the amount of unbalanced flow on the node. The dissipative flow of the source and the sink is considered +∞ and -∞ respectively. The dissipative flow of edge in forward direction is equal to the flow present in that edge, while in backward direction it is equal to residual capacity of that edge. The dissipative flow of path is equal to the minimum of dissipative flows of initial and final nodes of the path and dissipative flows of all edges present in that path. Furthermore the dissipative flow of the path is taken as negative if initial node is negative node else it is taken as positive. The act of flow dissipation on the path from initial to final node means adding dissipative flow of the path to each forward edge and deducting dissipative flow of the path from each backward edge of that path. The single commodity algorithm is shown in procedure 1.

` Procedure 1: MBT Method for Single Commodity Network `

If method in procedure 1 is applied on network in Figure 1 then algorithm will follow steps mentioned below.

-The algorithm starts with the fully saturated network (Figure 1) not observing the flow conservation law at nodes (Step 1)

-The algorithm computes the dissipative flow at each node except source and sink nodes as follows (Step 2)

` `

-The algorithm scans the node list to locate the node with negative dissipative flow. i.e., node N4 (Step 3)

-The algorithm finds path P4,5,2,3 from node N4 to node with positive dissipative flow i.e., node N3. (Steps 4-5)

-The algorithm dissipates the flow equal to -10 units along this path and updates the network as follows (Steps 4-5). Symbol q in the following equations represents the resulting flows in the respective edges.

` `

-The algorithm finds another path from node N4 to sink node N6 , i.e., the path comprising only one edge e4,6 and dissipates the flow equal to -20 units along this path and updates the network flows as follows (Steps 6-7)

` `

-The algorithm locates positive node N 3 and finds path from node N3 to source node N1 i.e., path comprising only one edge e3,1 , and dissipates the flow equal to +10 units along this path and updates the network flows as follows (Steps 8-10)

` `

At this point the algorithm terminates as all the nodes are balanced. Figure 3 shows resultant network, representing optimized flow through the network.

` Figure 3: An optimized flow for the network in Figure 1`

2.2. MASS BALANCING METHOD FOR MULTI-COMMODITY NETWORK

In mass balancing theorem , the method in section 2.1 was also extended to multi-commodity problem where network consists of more than one source with each source delivers mixture of number of commodities and each source has mixture of commodities in different proportions. The objective is to maximize output of one of those commodities, i.e., commodity of interest (COI). The proportion of this commodity in overall mixture in each source is called COI ratio. The algorithm can be summarized in the following steps.

` Procedure 2: MBT Method for Multi-Commodity Network `

To see the applicability of above procedure let us expand the network in Figure 1 from one source to two sources as shown in Figure 4.

` Figure 4: A multi-commodity network`

According to first step of algorithm, the ratio of commodity of interest in the overall mixture of each source is computed and the sources are sorted accordingly in the ascending order i.e. from lowest to highest COI ratio.

First 7 steps of procedure 1, as explained earlier, are applied to maximize the overall flow (Step 2). This ends up with only one node i.e., node N3 with positive dissipative flow equal to +10 units (Step 3). At this point decision needs to be made that to which source this excess flow should be dissipated. The natural choice would be the source s1 as this source contain the minimum COI ratio (Steps 4-5). Therefore the optimised network is shown in Figure 5.

` Figure 5: An optimised multi-commodity network`

2.3. MBT METHOD FOR MULTI-COMMODITY NETWORK WITH A SEPARATOR

An application of mass balancing theorem was further extended to multi-commodity network with a separator .

Let the multi-commodity network consists of n sources and m commodities, and each source j produces a unique mix of commodities in quantity Qj such that

` `

Equation 3 shows that total quantity of mixture is sum of all the quantities of individual commodities in the mixture, where quantity of each individual commodity can be determined from its proportion in the mixture. The value of proportion varies between 0 and 1 (expression 4).

Flow from all the sources ultimately terminates onto a separator that separates the commodity mixes. At the output of the separator, there are m commodity networks each corresponding to a single commodity, carrying ith commodity to the ith sink. The goal is to maximize the output of commodity of interest (COI) while obeying the capacity constraints of multi-commodity network and each of the m single commodity networks.

Figure 6 shows a multi-commodity network, namely,  connected to  sources S1,S2, …Sn , and a separator U. In addition, there are  commodity networks, namely N1,N2 , … Nm, which originate from the separator U and each of these networks has its own sink, i.e.T1  through Tm, respectively. For the problem formulation, following subsections define some notions.

` Figure 6. Multi-Commodity Network with Separator`

2.3.1 UNIFIED AND INDIVIDUAL SOURCE NETWORKS (USN AND ISNS)

Let us modify the network in Figure 6 by connecting its source nodes S1, S2, … Sn with the universal source node S0 of unlimited capacity through the edges e1, e2, … en of unlimited capacity respectively. Furthermore considering the separator as the ultimate sink, the network of Figure 6 can be reduced to the network shown in Figure 7. The network hereby referred to as Unified Source Network (USN). The USN in Figure 7 can be calibrated into the individual source networks. The individual source network corresponding to the source i, ISNi is the network with ci=∞ and cj=0 where j∈{1,…..,n/j≠i}. This means that in the individual network of source i all the other sources will be disconnected from the network except source i itself. Furthermore the capacity of source i is also considered unlimited.

` Figure 7. Unified Source Network and n Individual Source Networks`

2.3.2 INDIVIDUAL COMMODITY NETWORK (ICN)

Considering the separator U as the primary source for each commodity network, the network of Figure 6 can be reduced to the network shown in Figure 8. In Figure 8 since there are m commodities hence there are m ICNs, such that for ICNi, ci=∞ and cj=0 where j{1,…..,n/j≠i}. This means that in the individual commodity network of commodity i all the other commodities are disconnected from the network except commodity i itself. Furthermore the capacity of primary source of commodity i is also considered unlimited.

` Figure 8. m Individual Commodity Networks`

Let us consider

C0 = Minimum cut of the USN in Figure 7
C(si∈{1,….,n} )= Minimum cut of the 〖ISN〗(i∈{1,….,n} ) respectively in Figure 7
C(ci∈{1,….,m} ) = Minimum cut of the 〖ICN〗(i∈{1,….,m} ) respectively in Figure 8

Therefore the maximum flow Q0 in the multi-commodity network of Figure 1 is given by

` `

This means that maximum flow in the network can be only be minimum of the following three quantities.

1. Minimum cut of the unified source network
2. Sum of minimum cuts of individual source networks
3. Sum of minimum cuts of individual commodity networks

Since in any case

` `

Therefore expression 5 reduces to

` `

Expression 7 shows that maximum flow through the multi-commodity network of Figure 6 cannot be greater than lesser of the two quantities i.e., minimum cut of USN of Figure 7, and sum of minimum cuts of all the individual commodity networks ICNs of Figure 8. The ≤ sign in this expression indicates that there are other constraints too that may restrict the flow. Those constraints are shown in expressions 8 and 9. Suppose qij is flow of commodity i in source j then

` `

and

` `

Expression 8 shows that flow from any source j must not be greater than minimum cut of its individual source network and expression 9 shows that total flow of any commodity i must not be greater than the minimum cut Cci of its respective individual commodity network. The ≤ sign signifies the fact that if one of the commodities k exhausts the capacity of its individual network Cck, then flow cannot be further increased for other commodities i∈{1,…,m/i≠k} as increase in the overall mixture would also increase the flow of the commodity k. Therefore objective is to maximize the flow of COI, Qcoi i.e.,

` `

Substituting the values of qjcoi from expression 2 into expression 10 gives the following linear function

` `

The linear function in equation 11 is to be maximized under the constraints of expressions 7 through 9.

A method for maximization of flow of a commodity of interest through the network with a separator has been devised by keeping problem formulation presented above in mind. The method hybridizes mass balancing theorem with simplex method. Simplex method is used to maximize linear function shown in equation 11 under the constraints in expressions 7-9. However to determine the value of constraints mass balancing method of flow maximization (procedure 1) is used. This hybridized method is termed as simplex mass balancing (SMB) method.

The algorithm is explained in the following steps.

` Procedure 3: MBT Method for Multi-Commodity network with a separator `

From the above procedure it can be seen that in the second step procedure 1 is used to determine minimum cuts (maximum flows) of various conceptual networks introduced in Figures 7-8. The values of those minimum cuts are later used in design of linear programming formulation in step 3. The designed linear function is then optimized in step 4 using simplex method to determine optimal flows from all sources. In step 5, a flow through multi-commodity network is again maximized by restricting flow from sources to optimal flows obtained in previous step. In step 6, quantity of each commodity is computed in the resultant output mixture from all the sources. In step 7, flow in each commodity network is maximized by restricting quantity of each commodity equal to the commodity quantities obtained in previous step. In the final step, all the conceptual networks are joined together to form original network. The resultant network represents the optimal flow solution with respect to commodity of interest.

Readers are referred to simplex mass balancing method  to see proof of optimality, complexity analysis and solved example of multi-commodity network with a separator. In the next section, the MBT method for single commodity is extended to produce most economical maximised flow solution in the networks with embedded cycles.

3.MBT METHOD FOR THE ECONOMICAL FLOW MAXIMISATION

In the real world sometimes we may encounter with networks having embedded cycles, such as cyclic path P2,3,4,5,2 in the network of Figure 1. The MBT method shown in procedure 1 produced not only optimal but also most-economic solution of maximum flow on that network as shown in Figure 3. The solution is most economical because there is no extra-saturated edge not contributing to maximum flow through the network. However if edge capacities are reassigned in the same network as shown in Figure 9, then MBT method described in procedure 1 will definitely produce optimal solution on this network but the solution may not be most economical as it may contain extra saturated edge not contributing to the maximum flow.

` Figure 9: An example network with embedded cycle`

In the above example it can be seen that all the nodes are balanced nodes. Since MBT method mentioned in procedure 1 will not find any unbalanced nodes, it will return fully saturated network as a solution to the maximum flow problem. It is true that fully saturated network in the Figure 9 is a valid maximum flow solution of the network. However, it is not the most economical solution. This is because there are some saturated edges which do not contribute to the maximum flow such as edge e5,2. To address this, MBT method in procedure 1 is modified to produce most economical maximum flow solution for the networks with embedded cycles. The modified algorithm is shown in sequential steps in procedure 4 bellow.

` Procedure 4: MBT method for the economical maximum network flow`

Now let us apply procedure 4 on the network in Figure 9. The step 1 of procedure 4 i.e., application of procedure 1 returns the fully saturated network of Figure 9. In step 2, all the nodes are marked as unvisited. In step 3, counter of variable i starts (i=0). In step 4, counter i is incremented to (i=1). In step 5, it is checked that whether the whole network has already been scanned. In step 6, node N1 is found as not a candidate node because it is a source node therefore control of algorithm goes back to step 4. In step 4, counter i is incremented to (i=2). In step 5, again it is checked that whether the whole network has already been scanned. In step 6, node N2 is found as a candidate node i.e., it is unvisited and not a source or sink node. In step 7 a cyclic path from node N2 to node N2 i.e., Pc=P2,3,4,5,2 is found and all the nodes on this path i.e., N2,N3,N4,N5 are marked as visited. In step 8, ‘if’ condition fails as cyclic path is found in step 7. In step 9, edge ej=e5,2of minimum flow qmin=10 units, is found on cyclic path Pc. In step 10, the entire flow of 10 units from edge e5,2 is removed. The resultant network is shown in Figure 10.

` Figure 10: A network of Figure 9 after application of step 10 of procedure 4`

It can be seen that after application of step 10, two nodes of the network become unbalanced i.e. node (N2=-10) and node (N5=+10). In step 11, a path Pk=P2,3,4,5 from node N=N2 to node N+=N5 is established, which is subset of cyclic path Pc=P2,3,4,5,2. In step 12, a flow of -10 units is dissipated along path Pk. The resultant network is shown in Figure 11.

` Figure 11: A network of Figure 9 after application of step 12 of procedure 4`

In Figure 11, it can be seen that after application of step 12, the nodes N2 and N5 become balanced. In step 13, ‘if’ condition becomes true because i=2<n=6 . Therefore the control of algorithm goes back to step 4. The algorithm iterates between step 4 and step 6 as no other candidate node could be found as all the nodes except source and sink node have been marked visited. Finally step 5 sends control to step 13 when i=7. In step 13, ‘if’ condition fails to materialise because i>n. Finally the algorithm terminates at step 14. The network in Figure 11 represents the maximised flow with minimum costs. The solution in Figure 11 does not have any extra saturated edges.

4.CONCLUSIONS

In this paper mass balancing theorem on the flow networks has been revisited. The theorem is explained on new example networks with embedded cycles. The flow maximisation method based on this theorem is described again on single and multiple commodity network examples with embedded cycles. Simplex MBT method for the flow networks with a separator is also revisited with a view of how it is coupled with the earlier methods. Finally MBT single commodity flow maximisation method is extended to produce most economical solution of flow maximisation on the networks with embedded cycles. In future this method can be extended to multi-commodity networks with embedded cycles and multi-commodity networks with embedded cycles and a separator.

ACKNOWLEDGEMENTS

The authors are grateful for financial support from Innovate UK and Route Monkey Ltd via KTP Partnership number 9839.

REFERENCES

     R. K. Ahuja, T. L. Magnanti and J. B. Orlin, (1988) Network flows. Working paper: OR 185-88. Sloan School of Management, MIT, Cambridge, MA.

     D. Sheela and C. Chellamuthu, (2012) Protection in Optical Mesh Networks – A Cost Effective Strategy Based on Topological Constraints, Malaysian Journal of Computer Science (ISSN 0127-9084) 25(1), 38-55.

     H. Cho, M. Lee and G. Hwang, (2014) A cross-layer relay selection scheme of a wireless network with multiple relays under Rayleigh fading, Journal of Industrial and Management Optimization (JIMO) 10(1), 1-19.

     Y. K. Lin and C. F. Huang, (2013) Stochastic Flow Network Reliability with Tolerable Error Rate, Quality Technology and Quantitative Management. 10(1), 57-73.

     Z. Ursani, (2014) Computing availability for redundant flow systems. Optimization Letters, 8(2), 715-725.

     A. Bhan and E. Mjolsness, (2006) Static and Dynamic Models of Biological Networks. Complexity. Willey Inter Science © 2006 Wiley Periodicals, Inc., 11(6).

     M. Masin, M. O. Pasaogullari and S. Joshi, (2007) Dynamic scheduling of production-assembly networks in a distributed environment. IIE Transactions 39, 395–409.

     M. Lytras, L. Zhuhadar, J. X. Zhang and E. Kurilovas, (2014) Advances of Scientific Research on Technology Enhanced Learning in Social Networks and Mobile Contexts: Towards High Effective Educational Platforms for Next Generation Education, J.UCS 20(10), 1402–1406.

     L. R. Ford and D. R. Jr. Fulkerson, (1956) Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.

   P. Elias, A. Feinstein, C. E. Shannon, (1956) A Note on the Maximum Flow Through a Network. IRE Transactions on Information Theory, 117-119.

   E. A. Dinic, (1970) Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277-1280.

   J. Edmonds and R. M. Karp, (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19, 248-264.

   R. K. Ahuja and J. B. Orlin, (1989) A fast and simple algorithm for the maximum flow problem. Operations Research, 37(5), 748-759.

   R. K. Ahuja, and J. B. Orlin, (1991) Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics, 38, 413-430.

   H. N. Gabow, (1985) Scaling algorithms for network problems. Journal of Computer and System Sciences, 31, 148-168.

   J. B. Orlin, R. K. Ahuja, (1987) New distance-directed algorithms for maximum flow and parametric maximum flow problems. Working Paper 1908-87, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA.

   A. W. Boldyreff, (1955) Determination of the maximal Steady State Flow of Traffic through a Railroad Network. JORSA, 3(4), 443-465.

 A. V. Karzanov, (1974) Determining the maximal flow in a network by the method of pre-flows. Soviet Mathematics Doklady, 15, 434-437.

   R. V. Cherkasky, (1977) Algorithm for construction of maximum flow in networks with complexity of O(V2√E) operation. Mathematical Methods of Solution of Economical Problems, 7, 112-125 (in Russian).

   V. M. Malhotra, M. P. Kumar and S. N. Maheshwari, (1978) An O(V3) Algorithm for Finding Maximum Flows in Networks. Information Processing Letters, 7, 277-278.

   Z. Galil, (1980) O(V5/3E2/3) algorithm for the maximum flow problem. ActaInformatica, 14, 221-242.

   R. E. Tarjan, (1986) Algorithms for Maximum Network Flow. Mathematical Programming, 26, 1-11.

 A. V. Goldberg, (1985) A new max-flow algorithm. Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, MIT, Cambridge, Mass.

 A. V. Goldberg, R. E. Tarjan, (1988) A New Approach to the Maximum-Flow Problem. Journal of the Association for Computing Machinery, 35(4), 921-940.

 R. E. Tarjan, (1984) A simple version of Karzanov’s blocking flow algorithm. Operations Research Letters, 2, 265-268.

 D. S. Hochbaum, (2008) The Pseudo-flow Algorithm. A new algorithm for the maximum flow problem. Operations Research (Informs) 56(4), 992-1009.

 J. Dong, L. Wei, C. Cai and Z. Chen, (2009) Draining algorithm for the maximum flow problem. International Conference on Communications and Mobile Computing.

 Chien Tran Quoc, (2010). “Postflow-pull methods to find maximal flow”, Journal of science and technology – University of DaNang, 5(40)/2010, 31-38.

 Z. Ursani, (2012) Introducing Mass Balancing Theorem for Network Flow Maximization. International Journal of Industrial Engineering Computations 3, 843-858.

   Z. Ursani, (2014) Iterative Mass Balance Method for Multi-Commodity Maximization Problem. Production Planning & Control: The Management of Operations. 25(7), 592-602.

   Z. Ursani, A. A. Ursani, D. W. Corne (2015) Introducing Simplex Mass Balancing Method for the Multi-Commodity Flow Network with a Separator. Fourth International Conference on Advanced Information Technology and Applications (ICAITA 2015), Computer Science Conference Proceedings AIRCC, Jan Zizka et al. (Eds): ICAITA, SAI, CDKP, Signal, NCO-2015 pp. 43-57, 2015. © CS & IT-CSCP 2015.

AUTHORS Dr. Ziauddin Ursani graduated in Civil Engineering from Mehran University of Engineering and Technology Jamshoro, Sindh, Pakistan in 1989. He obtained Postgraduate Diploma in Environmental Engineering from the same university in 1999. Dr. Ursani did his masters in Information Technology from Hamdard University Karachi, Sindh, Pakistan in 2004 under the award of Science and Technology Scholarship. He received his PhD (Computer Science) in 2009 from Australian Defence Force Academy, University of New South Wales, Australia under the prestigious award of University College Postgraduate Research Scholarship (UCPRS).  He has worked in several postdoctoral projects in UK universities including Oxford Brookes University (Leverhulme Trust Project), University of Salford (Engineering and Physical Sciences Research Council ‘EPSRC’ Project) and University of Warwick (Department of Energy and Climate Change ‘DECC’ Project). Presently he is working as a Knowledge Transfer Partnership (KTP) Associate in the Innovate UK Technology Strategy Board Project awarded to Heriot Watt University and Route Monkey Limited. He is engaged in the development of route planning software for the company. Optimisation is his main research interest. Dr. Ahsan Ahmad Ursani was born in Pakistan in 1972. He received the B.Eng. degree in Electronics from Mehran University of Engineering and Technology (MUET), Jamshoro, Sindh, Pakistan, in 1995, and the Ph.D. degree in Signal and Image Processing from the National Institute for Applied Sciences (INSA), Rennes, France, in 2008. He has been working since 1996 as a faculty member at MUET and since 2011, as the Chairman of the Department of Bio-Medical Engineering at MUET. Currently, he is working as the Visiting Associate Professor in the Faculty of Mathematics and Computer Science at the South Asian University, New Delhi, India. His research interests include Remote Sensing, Speech Processing, Biomedical Engineering, Medical Imaging, Digital Signal and Image Processing, and Mathematical Optimization. He worked as a visiting research associate at the International Centre for Theoretical Physics (ITCP), Trieste, Italy, in 1998 and 2003.