fORum Seminar

Large semidefinite optimization problems are computationally challenging. We explore using reinforcement learning (RL) to find efficient chordal extensions, based on network features. A key challenge is selecting the best extension from many options. We hypothesize RL can learn network features that correlate with faster solution times. Preliminary results show our RL agent can identify extensions leading to improved computational efficiency. We are refining the agent and investigating feature-solution speed relationships, demonstrating RL's potential for tackling complex optimization problems.

This talk introduces primal-dual linear programming (PDLP) as a powerful alternative to traditional simplex and interior point methods. Using the Chambolle-Pock algorithm, PDLP employs first-order gradient methods to solve LP problems without requiring complex Hessian calculations. We will demonstrate how to reformulate LPs into saddle point problems and explain four critical heuristics that enhance performance: adaptive restarting, dynamic step size selection, diagonal preconditioning, and feasibility polishing. PDLP's reliance on matrix-vector multiplication makes it naturally suited for GPU acceleration, driving its adoption in commercial solvers like Gurobi and HiGHS. Join us to explore how this approach bridges classical optimization with modern computational capabilities for solving large-scale linear programs.

Modern power distribution networks (DNs) incorporate a growing number of active distribution network (ADN) technologies, such as distributed energy resources (DERs) and remotely activated switches. As the DN is a naturally unbalanced system due to the multi-phased highly fluctuating demand, DERs which can lead to bi-directional power flow amplify the phase imbalance, reducing system reliability and efficiency. The proposed network topology reconfiguration method uses tie and sectionalizing switches to minimize power losses in a three-phase unbalanced DN equipped with DERs. Strict, practical feasibility of the solution is ensured using a high-accuracy load-flow simulator, and by formulating the problem as a blackbox optimization (BBO) problem. To circumvent the computational burden of BBO, combinatorial optimization-inspired algorithms are introduced and adapted to the DN context, namely the variable neighbourhood search (VNS) metaheuristic and the branch-and-bound (BB) framework.

Hedonic Games are a class of coalition formation games where a set of agents must be partitioned into disjoint coalitions, and agents' utilities depend only on their own coalition. Examples of such games include assigning shared offices to faculty, organizing seating plan for a conference diners, and organizing walking groups for school hiking expeditions. This talk focuses on adding further restrictions to the feasibility of coalitions, namely adding both upper and lower bounds on coalition size. This setting, although very natural, has previously not been studied. Classical single agent stability concepts from algorithmic game theory will be introduced in the setting of these games, and integer linear programming formulations for constructing stable coalition structures discussed. Reference: Haris Aziz, Rahul Savani, Hedonic Games. Handbook of Computational Social Choice. 2016, Martin Bullinger, Edith Elkind, Jörg Rothe, Cooperative Game Theory. 2024

For optimization problems, feasible solutions can be useful even if they are not optimal. Moreover, the journey towards an optimal solution begins with at least one feasible solution, if one exists. Therefore, finding feasible solutions, and ideally good ones, is of considerable interest for a wide variety of problems. Focussing on mixed integer programming (MIP) in particular, this talk will describe two notable heuristic methods from the recent literature: Feasibility Jump (Luteberget and Sartor 2023) and Local-MIP (Lin et al 2024).

Planning spatial networks with Monte Carlo tree search

Machine learning techniques have begun to emerge as a valuable tool in combinatorial optimization. Notably, the trial-and-error paradigm of reinforcement learning (RL) has shown the potential to discover novel heuristic algorithms for a variety of problems. However, its substantial costs for model training and poor scalability in large decision spaces remain important challenges to wider adoption. 

In this talk, I will present a model and algorithm for the design of networks positioned in physical space. We propose the use of decision-time planning methods as a way of alleviating the large training costs and poor scalability of existing RL approaches. Furthermore, the model captures the influence of spatial characteristics on the density and realisability of links. The proposed algorithm, SG-UCT, is evaluated for optimizing the efficiency and attack resilience of real-world internet infrastructure networks and urban metro systems. Our approach is fully generic with respect to the objective function and obtains excellent performance while requiring a computational budget similar to other search-based methods. 

Improving Relaxations in Linear Bilevel Optimization

This poster is concerned with linear bilevel optimization problems and their single-level relaxations that are central to solution approaches. The High Point Relaxation (HPR) is the most common single-level relaxation but when it is unbounded, nothing can be concluded about the optimality status of the corresponding bilevel problem. We introduce a new linear optimization model to help detect whether or not the unboundedness of the HPR originates in unboundedness of the corresponding bilevel problem, and present a theorem giving sufficient conditions for bilevel boundedness. We also propose an alternative relaxation to the HPR, and show how it is an improvement on the HPR. Future work will study how to make use of lower-level dual information to further improve single-level relaxations. 

An integer programming model to assign patients based on mental health impact for tele-psychotherapy intervention during the Covid–19 emergency

The present study combines statistical analyses and discrete optimization techniques to solve the problem of assigning patients to therapists for crisis intervention with a single tele-psychotherapy session. The statistical analyses showed that professionals and healthcare workers in contact with Covid–19 patients or with a confirmed diagnosis had a significant relationship with suicide risk, sadness, experiential avoidance, and perception of severity. Moreover, some Covid–19-related variables were found to be predictors of sadness and suicide risk as unveiled via path analysis. This allowed categorizing patients according to their screening and grouping therapists according to their qualifications. With this stratification, a multi-periodic optimization model and a heuristic are proposed to find an adequate assignment of patients to therapists over time. The integer programming model was validated with real-world data, and its results were applied in a volunteer program in Ecuador.

Integrating Reinforcement Learning and Metaheuristics

ALNS is a popular metaheuristic with renowned efficiency in solving combinatorial optimisation problems. However, despite 16 years of intensive research into ALNS, whether the embedded adaptive layer can efficiently select operators to improve the incumbent remains an open question.

In this work, we formulate the choice of operators as a Markov Decision Process, and propose a practical approach based on Deep Reinforcement Learning and Graph Neural Networks. The results show that our proposed method achieves better performance than the classic ALNS adaptive layer due to the choice of operator being conditioned on the current solution.

We also discuss important considerations such as the size of the operator portfolio and the impact of the choice of operator scales. Notably, our approach can also save significant time and labour costs for handcrafting problem-specific operator portfolios.

Pre-trained Solution Methods for Unit Commitment

This study aims 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 regularised column generation procedure.

Firstly, initialisation methods of the column generation procedure based on machine learning techniques are studied. After offline training, for each unit commitment problem, the method outputs dual values which can be used to warmstart the solution method, leading to a significant saving of computational time.

Secondly, the column generation procedure is extended to handle incremental generation of columns. Instead of generating columns for all the components in each iteration, our method generates a subset of them and updates the dual variable using the partially updated restricted master problem. Convergence analysis of the method is given under various conditions.

These enhancements are tested on large-scale test instances

Denise Cariaga Sandoval⁽¹⁾⁽⁴⁾

Egon Persak⁽¹⁾

Contextual Robust Optimisation with Uncertainty Quantification

We propose two pipelines for convex optimisation problems with uncertain parameters that aim to improve decision robustness by addressing the sensitivity of optimisation to parameter estimation. This is achieved by integrating uncertainty quantification (UQ) methods for supervised learning into the ambiguity sets for distributionally robust optimisation (DRO). The pipelines leverage learning to produce contextual/conditional ambiguity sets from side-information. The two pipelines correspond to different UQ approaches:

1. explicitly predicting the conditional covariance matrix using deep ensembles (DEs) and Gaussian processes (GPs), and
2. sampling using Monte Carlo dropout, DEs, and GPs.

We use i) to construct an ambiguity set by defining an uncertainty around the estimated moments to achieve robustness with respect to the prediction model. UQ ii) is used as an empirical reference distribution of a Wasserstein ball to enhance out of sample performance. DRO problems constrained with either ambiguity set are tractable for a range of convex optimisation problems. We propose data-driven ways of setting DRO robustness parameters motivated by either coverage or out of sample performance. These parameters provide a useful yardstick in comparing the quality of UQ between prediction models. The pipelines are computationally evaluated and compared with deterministic and unconditional approaches on simulated and real-world portfolio optimisation problems. 

Monserrat Guedes Ayala⁽¹⁾

ChatGPT: More Than Just a Text Generator, It's Your PhD Sidekick

You've probably heard about ChatGPT by now, right? Some people say it's the bee's knees when it comes to generating realistic text, while others believe it could totally change the way we interact with computers. But how can ChatGPT help us with our PhDs and make our lives a little less hectic? In this talk, I'll give you the lowdown on how ChatGPT works, before diving into some awesome ways it can help us PhD students (and anyone else who could use a little extra assistance). Whether you're looking to streamline your workflow, automate repetitive tasks, or just get more stuff done, ChatGPT has got you covered. But let's not get too carried away - with great power comes great responsibility, and there are definitely some limitations and risks to be aware of. So don't worry, I'll be sure to cover those too. Overall, this talk will give you an overview of how ChatGPT can make your life easier, both in and out of your academic life. So whether you're a seasoned researcher or just starting out, don't miss this opportunity to learn more about this amazing technology. Disclaimer: the title and abstract were generated with a little help from ChatGPT - can you tell? 

Claire Zhang⁽¹⁾

Workshop on Maths Server

The School of Mathematics provides us with access to a powerful Linux computing server -- the Maths server, which can be connected from everywhere via various ways including ssh, X-sessions, and Remote Desktop. However, not everyone from Maths is familiar with servers or Linux machines. We are going to run a workshop on how to efficiently use the Maths server. In the workshop, we will work together on how to connect to the server, how to navigate files and folders in the terminal, as well as some useful tools. 

Dr. Albert Solà Vilalta⁽¹⁾

Dr. Nagisa Sugishita⁽¹⁾

Revealing the Viva Mystery

The viva is the last step towards the completion of your PhD, but one may feel it mysterious or daunting: it is closed doors, the examiners can ask very difficult or technical questions, the examiners know much more than me about the subject, ... The purpose of this talk is to tackle such concerns by sharing our recent experiences on our viva processes. The main message is that it has been a very pleasant experience for us, including our friends and colleagues that had their vivas recently. This is thanks to all the work done during the PhD (you’ve done that too!). If some questions sound difficult and/or tricky, it is often because the examiners are interested in the topic, and they want to connect it to their knowledge. Once the moment arrives, prepare well and stay confident that it will be successful :) (data supports staying confident: 96.7% of UK PhD students pass their vivas). In this event a short presentation on the experience of viva is given by the speakers, followed by an interactive Q&A session to resolve any concerns regarding the viva. 

Dr. Christian Rählmann⁽¹⁾

Selected OR Topics at Volkswagen

In this talk, Dr. Christian Rählmann, Operations Researcher at Volkswagen’s Software & Innovation Center in Berlin, will give insights into current Operations Research topics at the Volkswagen Group. Volkswagen is one of the largest OEM in the world and therefore faces complex problems along the entire customer order process. We will take a practical look at the problems at hand, such as buildability checks, production planning, or car sequencing. Finally we will discuss the challenges from industry that do not apply from research perspective but are highly relevant for the business.

The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints

The well-known bipartite boolean quadric polytope (BQP) is defined as the convex hull of all quadric incidence vectors over a bipartite graph. Here, we consider the case where there is a partition on one of the two bipartite node sets such that at most one node per subset of the partition can be chosen. In this talk, results of the polyhedral study and the relation to the pooling problem are presented. Furthermore, a similar polytope is introduced that will be analyzed in future work.

Haoyue (Claire) Zhang⁽¹⁾

Facility Location Problem under Uncertainty with Service Level Constraints

In facility location, most models assume customer demands to be deterministic. However, in practice, there is often a large degree of uncertainty about future demands, especially given the strategic nature of location problems where decisions have to be made for the next twenty or thirty years. Stochastic programming models are widely applied to solve FLPs under uncertainty. However, since all the demand has to be satisfied in every scenario, the models sometimes give conservative results. This presentation is about including service levels as chance constraints in the stochastic programming model, allowing for a certain probability and a certain percent of the demand to be unsatisfied. In the model, the α-service level is applied both locally and globally while the β-service level constraints take the expected value, as well as the maximum value of the excess into account. To decide which combination of service levels “works the best”, we carry out experiments and tests with combinations of different settings on randomly generated data sets.

Gas Network Control by Simulation-based Reinforcement Learning

Optimal control problems for gas flow in pipeline networks are usually tackled in mathematics within three steps: first, modelling the problem as a MINLP, second, approximating it to receive a MIP, third, optimizing the approximated problem. Imagining a discretized time horizon, we leave the determination of control variables in every time step as a decision to a machine learning approach. In contrast to standard methods, we leverage the optimization as a simulation framework for the resulting easier problem. This technique combines the fields of artificial intelligence as well as mathematical optimization and is more accurate in the modelling of nonlinearities, as well as regarding the functionality of gas network controls. In cooperation with an industry partner, we apply a reinforcement learning technique called (categorical) deep Q-network (CDQN) to control gas subnetworks. The learning of the agent and the improvement of its control is achieved via Q-learning, a special case of approximate dynamic programming by Bellman that incorporates future, as well as present states to accomplish the overall best result. This thesis contains a description of the original model, as well as an explanation of the used CDQN approach, and closes with computational results on a real-world gas subnetwork.

A nonlocal PDE-constrained optimisation model for containment of infectious diseases

Nonpharmaceutical interventions have proven crucial in the containment and prevention of Covid-19 outbreaks. In particular public health policy makers have to assess the effects of strategies such as social distancing and isolation to avoid exceeding social and economical costs. In this work, we study an optimal control approach for parameter selection applied to a dynamical density functional theory model. This is applied in particular to a spatially-dependent SIRD model where social distancing and isolation of infected persons are explicitly taken into account. Special attention is paid when the strength of these measures is considered as a function of time and their effect on the overall infected compartment. A first order optimality system is presented, and numerical simulations are presented using a proximal method. This work could potentially provide some mathematical insights into the management of disease outbreaks.

Egon Persak⁽¹⁾

An inexpensive machine learning solution to fix the forecasting models that the pandemic broke

The pandemic’s effect on consumer behaviour caused many predictive models to completely fail. As this predictive work is essential in downstream decision making, especially in such a time of crisis, a reliable and efficient method to mend the predictive capacity of forecasting models is a crucial business need. This presentation is about a method developed at ExPretio Technologies to tackle this problem for rail passenger demand forecasting. The key insight is that existing models can be recycled as inputs for machine learning, specifically to reassess the predictions from the original models in the context of newly incoming data. A major advantage of this method is that it alleviates the need for costly calibration required to develop predictive models from scratch. This method not only fixed the models broken by the pandemic but also gives an improved performance compared to previously used individual models on pre-pandemic data.

Nicholas Good⁽¹⁾

Challenges and careers at KrakenFlex

Monse Guedes Ayala⁽²⁾

How can we speed up solving a large-scale distributed energy portfolio management problem?

Jakub Kruzik⁽¹⁾

PERMON toolbox for quadratic programming

Albert Solà Vilalta⁽¹⁾

ADMM-based Unit and Time Decomposition for Price Arbitrage by Cooperative Price-Maker Electricity Storage Units

Decarbonisationvia the integration of renewablesposes significant challenges for electric power systems, but also creates new market opportunities. Electric energy storage can take advantage of these opportunities while providing flexibility to power systems that can help address these challenges. We propose a solution method for the optimal control of multiple price-maker electric energy storage units that cooperate to maximise their total profit from price arbitrage. The proposed method can tackle the nonlinearityintroduced by the price-maker assumption. The main novelty of the proposed method is the combination of a decomposition by unit and a decomposition in time. The decomposition by unit is based on the Alternating Direction Method of Multipliers and breaks the problem into several one-unit subproblems. Every subproblemis solved using an efficient algorithm for one-unit problems from the literature that exploits an on the fly decomposition in time, and this results in a time decomposition for the whole solution method. Our numerical experiments show very promising performance in terms of accuracy and computational time. In particular, they suggest that computational time scales linearly with the number of storage units.

Shunee Johnn⁽¹⁾

Andrés Miniguano Trujillo⁽¹⁾⁽²⁾

Yiran Zhu⁽¹⁾

13th AIMMS-MOPTA Optimization Modeling Competition: Winners and their approach

Andrés Miniguano Trujillo⁽¹⁾⁽²⁾

In this talk, we will briefly examine some problems that I have encountered in through my journey in OR. Among the cases we will cover are the modelling and algorithmic approach to the combined routing of pollsters and vehicles, the allocation of rose-stems for international commercialisation, the assignment of patients to therapists for psychological intervention, and how set partitioning can be used to solve a particular puzzle. We will review the techniques employed for each problem and their challenges for practical applications.

Conic formulation of QPCCs applied to truly sparse QPs

We study (nonconvex) quadratic optimization problems with complementarity constraints, establishing an exact completely positive reformulation under — apparently new — mild conditions involving only the constraints, not the objective. Moreover, we also give the conditions for strong conic duality between the obtained completely positive problem and its dual. Another novelty of our approach is a purely continuous model which avoids any branching or use of large constants in implementation. An application to pursuing interpretable sparse solutions of quadratic optimization problems is shown to satisfy our settings, and therefore we link quadratic problems with an exact sparsity term ∥x∥_0 to copositive optimization. The covered problem class includes sparse least-squares regression under linear constraints, for instance. Numerical comparisons between our method and other approximations are reported from the perspective of the objective function value.

Fast cluster detection in networks by first-order optimization

Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of s-defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we analyze some tailored variants of the Frank–Wolfe algorithm that enable us to quickly find maximal s-defective cliques. The good practical behaviour of those algorithmic tools, which is closely connected to their support identification properties, makes them very appealing in practical applications. The reported numerical results clearly show the effectiveness of the proposed approach.

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.