Exploiting structure in polynomial optimization for power and water networks

Olga Kuryatnikova


Some hard non-linear optimization problems can be solved quite efficiently because they exhibit sparsity (subsets of variables or terms appearing separately in the problem) or symmetry (repeated patterns in the problem). Often, these types of structure occur in network-based engineering problems, such as AC power flow problem in power networks and the valve setting problem in water networks. These are large non-convex quadratic optimization programs, but they consist of many small subproblems connected with sparse linking constraints. I will do a brief introduction into these problems, show how one can use sparsity and symmetry to obtain fast and strong bounds, and present some numerical results on realistic power and water networks.

As urbanization increases, municipalities across the world have become aware of the negative impacts of road-based transportation, which include traffic congestion and air pollution. As a result, several cities have introduced tolling schemes to discourage vehicles from entering the inner city. However, little research has been done to examine the impact of tolling schemes on the routing of commercial fleets, especially on the resulting costs and emissions. In this study, we investigate a vehicle routing problem considering different congestion charge schemes for several city types. We design comprehensive computational experiments to investigate whether different types of tolling schemes work in the way municipalities expect and what factors affect the performance of the congestion charge schemes. We compare the impact on a company’s total costs, fuel usage (which drives emissions), and delivery tour plans. Our experimental results demonstrate that some congestion pricing schemes may even increase the emi