OptimizEd wORld Seminar

Integer programming for the envy-free equilibrium pricing problem

We consider the envy-free pricing problem that arises in the setting of economic equilibrium of multi-item multi-buyer markets. This problem has been extensively studied in literature from the computational complexity perspective. It can be formulated as a mixed integer nonlinear problem when general utility functions are used, and reduces to a mixed integer quadratic problem when the standard assumption of linear utilities is made. We work within the framework of general utilities and derive many properties of optimal solutions. Some computational results are provided to test the effectiveness of our properties.

A new approach to quadratic unconstrained binary optimisation

Quadratic unconstrained binary optimisation (QUBO) is a much-studied problem in combinatorial optimisation, with a huge array of practical applications.  We say that a QUBO instance is “sparse” if the majority of the quadratic terms in the objective function are zero.  When it comes to exact solution methods, approaches based on linear programming (LP) tend to work better for sparse instance, whereas approaches based on semidefinite programming (SDP) tend to work better for dense instances.  After reviewing the existing approaches, we present a new “hybrid” approach, in which we solve an SDP relaxation, use the dual solution to construct an ellipsoid, and then used the ellipsoid to strengthen an LP relaxation.  We then present some preliminary computational results on benchmark instances.  This talk is based on joint work with Fabrizio Rossi and Stefano Smriglio from the University of L’Aquila, Italy.

Interior Point Methods for Optimal Transport with imaging applications

Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this talk we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column-generation-like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently, in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed sparse IPM method with a state-of-the-art solver and show that it can compete with the best network optimization tools in terms of computational time and memory usage. We perform experiments with problems reaching more than a billion variables and demonstrate the robustness of the proposed method.

The numerical solution of the L¹ and L² Optimal Transport problem. Differences, analogies, and open problems.

The Optimal Transport problem studies how to find the optimal strategy of moving resources. When the cost of moving one unit of mass is proportional to the distance or the square distance, they are called L¹ and L² problem, respectively. I will give an overview of the PDE-based formulations of the two problems and their applications. I will then focus on the open problems arising from their numerical solution.

Pre-trained solution methods for unit commitment

In this presentation we explore techniques to improve the solution methods for the unit commitment problem, a short-term planning problem in the energy industry. In particular, we focus on Dantzig-Wolfe decomposition with a column generation procedure.

One important aspect of the unit commitment problem is that in practice the problem is often solved repeatedly with minor changes in input data, such as demand. In this study special emphasis is placed on approaches based on machine learning. It allows us to extract useful information from previously solved instances and accelerate the algorithm to solve new instances. We discuss 1) how to initialise the dual variable to warmstart the algorithm, 2) how to update the dual variable efficiently with an incremental column generation procedure and 3) how to obtain good primal feasible solutions (primal heuristics). Our numerical study tests the proposed techniques with large-scale instances.

Enhanced decision-support for the British Electricity National Control Centre

National Grid Electricity System Operator (NGESO) is Great Britain’s electricity system operator. NGESO’s role is to ensure that the electricity supply and demand are balanced and the electricity flows across the network safely and reliably. Any imbalance in demand and generation manifests itself in system frequency rises or falls and the NGESO has a license obligation to control system frequency within plus or minus 1% of 50Hz. NGESO maintains the supply and demand balance by taking regulation actions known as BOA (bid offer acceptances) instructions, which instructs a set of generators to move up or down to meet the national demand. Each BOA has a cost and NGESO is expected to take the cheapest actions to keep the system operating within all of its statutory limits associated not just with frequency but also voltages and power flow between areas.

Up until recently large generating units (>50 MW) were used for balancing actions. However, with the recent regulatory changes generators, with up to 1 MW of capacity may provide balancing services. This wider access of generation units means many folds increase in the number of balancing units that need to be considered for balancing actions by operators at the Electricity National Control Centre (ENCC) and as a consequence manual dispatch instructions will no longer be a viable option.

In this talk, I will present an optimisation based decision-support solution that the University of Strathclyde is providing to the ENCC. The decision-support tool is currently under production and is expected to automate the issuance of BOAs, releasing control room operators to concentrate on validating the results and spotting errors in data. I will present a set of requirements from the ENCC and how such requirements are converted into constraints within an optimisation problem.

A two-stage multi-period vehicle routing problem with depot location

Motivated by a logistics company in Ecuador, we introduce a routing problem for sellers and vehicles, with a planning horizon, and variable starting point for the sellers. We have a set of customers, each of which needs to be visited by a seller on one of the days of the planning horizon and then by a vehicle on the following day. The customers have unit demand, and capacity is imposed by workload balancing constraints. The goal is to determine routes so that each customer is visited once by a seller and, immediately after, once by a truck over the planning horizon, and that the total travelled distance is minimised. We provide mathematical formulations to model this problem. Then we present some new valid inequalities that are a generalisation of the classical comb inequalities and a separation procedure that integrates them into a branch-and-cut method. Finally, we will introduce a work-in-progress metaheuristic that is already showing promising results.

Last-Mile Logistics in London

Freight transport makes up 16% of all road vehicle activity in UK cities, with lorries and vans performing 30% of their total activity in urban areas.  In the UK alone, the volume of the parcel market reached 2.6 billion items in 2018-19, giving rise to significant operational challenges in delivering the 'last-mile'.  In this talk, I will present some of the findings of the research project FTC2050: Freight Traffic Control 2050 (http://www.ftc2050.com), that was funded by the EPSRC, and that looked at the impact of current 'business-as-usual' carrier activities in London.  The aim was to improve carrier collection and delivery schedules by investigating the potential of new business models.  I will describe the practical issues faced by last-mile logistics providers, present alternative distribution models to help improve the efficiency of the operations, and discuss the theoretical challenges these models present.  This talk is based on joint work with co-authors from the University of Southampton, Lancaster University, UCL and University of Westminster.