fORum Seminar

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.