Distributed optimization in transportation and logistics networks

Many important problems in communication networks, transportation networks, and logistics networks are solved by the minimization of cost functions. In general, these can be complex optimization problems involving many variables. However, physicists noted that in a network, a node variable (such as the amount of resources of the nodes) is connected to a set of link variables (such as the flow connecting the node), and similarly each link variable is connected to a number of (usually two) node variables. This enables one to break the problem into local components, often arriving at distributive algorithms to solve the problems. Compared with centralized algorithms, distributed algorithms have the advantages of lower computational complexity, and lower communication overhead. Since they have a faster response to local changes of the environment, they are especially useful for networks with evolving conditions. This review will cover message-passing algorithms in applications such as resource allocation, transportation networks, facility location, traffic routing, and stability of power grids.

Foreign direct investment and corruption

In the last few decades, the world has witnessed an enormous growth in the volume of foreign direct investment (FDI). The global stock of FDI reached US$ 7.5 trillion in 2003 and accounted for 11% of world Gross Domestic Product, up from 7% in 1990. The sales of multinational enterprises at around US$ 19 trillion were more than double the level of world exports. Substantial FDI inflows went into transition countries. Inflows into one of the region's largest recipient, the Russian Federation, almost doubled, enabling Russia to become one of the five top FDI destinations in 2005-2006. FDI inflows in Russia have increased almost threefold from 13.6% in 2003 to 35% in 2007. In 2003, these flows were twice greater than those into China; whilst in 2007 they were six times larger. Russia's FDI inflows were also about 2.5 times greater than those of Brazil. Efficient government institutions are argued by many economists to foster FDI and growth as a result. However, the magnitude of this effect has yet to be measured. This thesis takes a Political Economy approach to explore, empirically, the potential impact of malfunctioning governmental institutions, proxied by three indices of perceived corruption, on FDI stocks accumulation/distribution within Russia over the period of 2002-2004. Using a regional data-set it concentrates on three areas relating to FDI. Firstly, it considers the significance, the size and the sign of the impact of perceived corruption on accumulation of FDI stocks within Russia. Secondly, it quantifies the impact of perceived corruption on the volume of FDI stocks simultaneously estimating the impact of the investment in public capital such as telecommunications and transportation networks on FDI in the presence of corruption. In particular, it addresses the question whether more corrupt regions in Russia are also those that could have accumulated more of FDI stocks, and investigates whether those 'more corrupt' regions would have had lower level of public capital investment. Finally, it examines whether decentralisation increases or decreases corruption and whether a larger extent of decentralisation has a positive or negative impact on FDI (stocks). The results of three studies are as follows. Firstly, along with market potential, corruption is found to be one of the key factors in explaining FDI distribution within Russia between 2002 and 2004. Secondly, corruption on average is found to be related to FDI positively suggesting that it may act as speed money: to save their time foreign direct investors might be willing to bribe the regional authorities so to move in front of the bureaucratic lines. Thirdly, although when corruption is controlled for, the impact of the latter on unobservable FDI is found to be on average positive, no association between FDI and public investment is observed with the only exception of transportation infrastructure (i.e., railway). The results might suggest therefore that it is possible that not only regions with high levels of perceived corruption attract more FDI but also that expansions in public capital investments are not accompanied by an increase of the volume of FDI (stocks) in regions with high levels of corruption. This casts some doubt on the productivity of the investment in public capital in these regions as it might be that bureaucrats may prefer to use these infrastructural projects for rent extraction. Finally, we find decentralisation to have a significant and positive impact on both FDI stock accumulation and corruption, suggesting that local governments may spend more on public goods to make the area more attractive to foreign investors but at the same time they may be interested into extracting rents from foreign investors. These results support the idea that the regulation of FDI is associated with and facilitated by a larger public sector, which distorts competition and introduces opportunities for rent-seeking by particular economic and political factors.

Coverage versus supply cost in facility location:physics of frustrated spin systems

A comprehensive coverage is crucial for communication, supply, and transportation networks, yet it is limited by the requirement of extensive infrastructure and heavy energy consumption. Here, we draw an analogy between spins in antiferromagnet and outlets in supply networks, and apply techniques from the studies of disordered systems to elucidate the effects of balancing the coverage and supply costs on the network behavior. A readily applicable, coverage optimization algorithm is derived. Simulation results show that magnetized and antiferromagnetic domains emerge and coexist to balance the need for coverage and energy saving. The scaling of parameters with system size agrees with the continuum approximation in two dimensions and the tree approximation in random graphs. Due to frustration caused by the competition between coverage and supply cost, a transition between easy and hard computation regimes is observed. We further suggest a local expansion approach to greatly simplify the message updates which shed light on simplifications in other problems. © 2014 American Physical Society.

Efficient algorithm for routing optimization via statistical mechanics

Many practical routing algorithms are heuristic, adhoc and centralized, rendering generic and optimal path configurations difficult to obtain. Here we study a scenario whereby selected nodes in a given network communicate with fixed routers and employ statistical physics methods to obtain optimal routing solutions subject to a generic cost. A distributive message-passing algorithm capable of optimizing the path configuration in real instances is devised, based on the analytical derivation, and is greatly simplified by expanding the cost function around the optimized flow. Good algorithmic convergence is observed in most of the parameter regimes. By applying the algorithm, we study and compare the pros and cons of balanced traffic configurations to that of consolidated traffic, which provides important implications to practical communication and transportation networks. Interesting macroscopic phenomena are observed from the optimized states as an interplay between the communication density and the cost functions used. © 2013 IEEE.