siam-student-chapter-seminarsInterwoven LiveSite
https://www.southampton.ac.uk/siamsc/activities/seminars/latest.pageSIAM Student Chapter SeminarsA Large-Scale Reformulation Technique for Nonlinear Bilevel Programming Based on Sequential Quadratic Programminghttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/11/28-nonlinear-bilevel-and-sequential-quadratic-proramming.pageWed, 28 Nov 2018 00:00:00 +0000
[15:00 - 16:00, 28 November 2018]
A technical system's dynamic behavior is often qualitatively known such that a general model can be formulated, but parameter values within the model are unknown since they depend on system specifications. In this talk, I will firstly give a brief introduction to the field of parameter identification for dynamical systems. Transcription techniques, in particular the single shooting and the full discretization approach, will be presented, as well as some illustrating examples.
The second part of the talk will be about nonlinear bilevel optimization. Similar to parameter identification, this problem class exhibits highly nonlinear constraints, since a lower level problem has to be solved. I will present a strategy to reformulate it as a single level problem, in which a set of constraints is introduced that represents the process of solving the lower level problem based on a sequential quadratic programming method. This requires additional optimization variables and finally leads to a sparse, but large-scale NLP. The focus is on providing ideas and first numerical results.An introduction to bilevel programming and an application to London congestion road pricinghttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/11/21-intro-to-bilevel-and-congestion-road-pricing.pageWed, 21 Nov 2018 00:00:00 +0000
[15:00 - 16:00, 21 November 2018]
In this seminar, I shall introduce bilevel programming. This is a hierarchical optimisation problem, which is an optimisation problem with a second optimisation problem embedded into the constraints. Bilevel programs are typically NP-hard, and therefore can be difficult to solve well. I shall discuss the formulation of the problem and introduce various solution approaches and methods to solve the problem, including the algorithmic approach currently in research.
I will then explore a real-life application of the problem. The London congestion zone charge is a fixed toll cordon scheme in London, first implemented in 2003, to try to alleviate the problem of congestion on London roads. Although initially successful when first implemented, congestion has increased to pre-charge prices, and a new tolling scheme may need to be considered. We shall look at how we can formulate this problem as a bilevel program, and look at updated tolling schemes that can consider charging prices based on the distance travelled, or time spent in the road network.A beginner's approach to branch-and-price methodshttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/05/30-beginners-branch-and-price.pageWed, 30 May 2018 00:00:00 +0100
[15:00 - 16:00, 30 May 2018]
Branch-and-price (B&P) methods are very popular for solving Mixed-Integer Linear Programming (MILP) problems with many variables. The most common version of the B&P algorithm starts with a reformulation of the original MILP by applying the Dantzig-Wolfe decomposition, thus generating a master problem and a subproblem (a.k.a. pricing problem). The master problem can then be solved by the Column Generation (CG) technique. A B&P algorithm consists of combining branch-and-bound and CG. In this talk, we shall introduce the basic concepts behind B&P methods from a practical point of view. In other words, we will look through an implementation of a B&P algorithm for solving the Bin Packing Problem (BPP). The BPP, in my opinion, presents a perfect combination of simplicity and complexity for a first contact with CG and B&P.Application of Game Theory to the Poker gamehttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/04/25-application-of-game-theory-to-the-poker-game.pageWed, 25 Apr 2018 00:00:00 +0100
[15:00 - 16:00, 25 April 2018]
Almost everyone has tried to play poker at least once. However, most of people barely have an idea what is behind the game and how to beat other players. Nowadays, poker is recognized as a mind sport. More than 50 countries around the world have association or federation of poker, including UK. The popularity of the game grows from day to day with millions of dollars played for, live and online, around the world. The natural question arises – if poker is intellectual game, does it have anything to do with game theory? The answer is “yes”. In fact, Operational Researchers have essential skills to apply mathematical techniques to develop winning strategies in the game of poker. This will be demonstrated in this talk. We will start with an overview of the game – its rules and mathematics driving the game. Then well-known probabilistic concepts will be shown to explain the nature of profits/loses in the poker game. With the support of simple combinatorics, we will use these probabilistic concepts to introduce thinking environment for a poker player in terms of expected values. Poker is the game with closed information, which means players make decisions without having information of what cards other players have. This brings importance of building a model determining probabilities of the holdings of the opponents in the game. We will see that a good poker player essentially builds a mathematical model that confronts mathematical models of other players involved in the game. This will be the most important idea behind the talk and will be supported with several examples. Of course, confrontation of different models with closed information involves making subjective assumptions on the variables in the models. However, we will also have a look at “Game Theory Optimal” approach for the game, which does not have this biased element in it.Optimisation Methods in Network Revenue Managementhttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/03/14-revenue-management-robust-optimisation.pageWed, 14 Mar 2018 00:00:00 +0000
[15:00 - 16:00, 14 March 2018]
Revenue Management (RM) is the field of Operations Research where techniques, strategies and tactics are employed to scientifically manage demand for products and services such that revenues are maximised. In this talk we will be focusing on the paradigm of Airline RM and the models and heuristics used to solve the Network Seat Inventory Control problem. We will be examining the traditional mathematical programs formulated to approximate large airline networks and the nesting heuristics developed to control demand uncertainty. Furthermore, we give a brief introduction to Robust Optimisation (RO). Due to the recent adaptability of RO models on multi-stage, decision-making problems, we overview fairly recent attempts to link the field of Network RM with RO techniques and comment on their effectiveness and tractability.The Economic Operational Speed of a Time-Chartered Ship - A Cash Flow Approachhttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/02/28-economic-operational-speed-of-a-time-chartered-ship.pageWed, 28 Feb 2018 00:00:00 +0000
[15:00 - 16:00, 28 February 2018]
It is well recognised that ship speed is an important variable used by ship operators in the bulk cargo and tanker shipping industry as a means to maximise profitability of these operations. Empirical data suggests that identical ships, travelling identical routes under identical conditions, still travel within a wide distribution of speeds. The reasons for this cannot be well understood from current speed optimisation models in the literature. The models developed in this article contribute towards increased understanding of how optimal speed decisions are dependent on conditions that determine the relevant future use of the ship that the charterer must consider. A wide range of different speeds would then be observed as a consequence of deliberate choice in the context of profit-maximising behaviour.Exploration and exploitation in a non-stationary environmenthttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2018/01/31-exploration-and-exploitation-in-a-non-stationary-environment.pageWed, 31 Jan 2018 00:00:00 +0000
[15:00 - 16:00, 31 January 2018]
We describe the problem of selecting the best option amongst a range of sub-optimal candidates, with the aim of maximizing long term rewards. As we have no information about the performance of the different options before the start of the experiment, the algorithm is designed to find the right trade-off between exploration and exploitation in the framework of online learning. While we focus on an application from an online travel agency, online learning has applications ranging from clinical trials to advertising and website optimization. In this particular study, an additional difficulty is the fact that there is seasonality in the demand. This complication is very common in areas such as sales and marketing where the demand for particular products varies for different seasons and periods of time. We use Thompson Sampling, a Multi-Armed Bandit algorithm, which based on Bayesian updating, uses new information obtained at each time step to decide which “arm” to play next, where arms are synonymous with options. Thompson Sampling was chosen due to its very good empirical performance. In order to tackle the challenge of non-stationarity, we are making some adjustments to the initial formulation of the algorithm in order to first capture seasonality from the data and then use it as contextual information when applying Thompson Sampling, developing a so-called “contextual bandit”. The contextual approach is more often used by organisations whose aim is to tackle decision making in the face of uncertainty by using side information about their clients and the options they are comparing.A Problem Not in Phttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/12/13-a-problem-not-in-p.pageWed, 13 Dec 2017 00:00:00 +0000
[15:00 - 16:00, 13 December 2017]
Ever wondered why the greedy algorithm works at all? Always considered NP-hard problems as hard? Would like to get a million dollars (plus some fame) easily? In this talk I attempt to address these questions by giving a brief introduction into the theory of matroids. We will look into different kind of matroids and matroid problems (with a very little peek into complexity theory), and their connection to the questions raised above. The primary motivation of the talk is to provide some insight into something hopefully interesting and new, such as a problem that does not lie in P. Also, as the festive season approaches, I attempt to spice the talk up with anonymous quotes from lecturers of the department as a sort of holiday treat.A Multi-objective Model for Skill Development in a Multi-Skilled Workforcehttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/11/22-multi-objective-model-for-skill-development-in-a-multi-skilled-workforce.pageWed, 22 Nov 2017 00:00:00 +0000
[16:00 - 17:00, 22 November 2017]
Workforce planning is of strategic importance to most organisations. It is in particular challenging when tasks may require employees with specialised skills and various training activities may be proposed. In such environments, the value of dynamic skill development within a workforce cannot be ignored. We are in particular interested in increasing our understanding of how multiple skills and their development should be distributed among a pool of technicians, and how this may depend on the operational environment. This research develops a novel approach based on multi-objective linear programming for determining an optimal strategic plan of skill development of a multi-skilled workforce when there are multiple training regimes that may be selected and various constraints on the operations of the training. For instance, additional constraints are required for skill development given uncertainty in the future demand for each type of task. In this thesis we focus on the development of the model and its application in organisations through the development of a decision support tool. This tool provides training recommendation for employees under different training options. We discuss the sensitivity analysis of the optimal workforce strategy to various changes to demand, components of the tasks, and training strategies.An Euclidean Distance Matrix Optimization Approach for Robust Multidimensional Scalinghttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/11/01-euclidean-distance-matrix-optimization-approach.pageWed, 01 Nov 2017 00:00:00 +0000
[15:00 - 16:00, 1 November 2017]
Kruskal’s stress minimization, though nonconvex and nonsmooth, has been a major computational model for dissimilarity data in multidimensional scaling. Semidefinite Programming (SDP) relaxation (by dropping the rank constraint) would lead to a high number of SDP cone constraints. This has rendered the SDP approach computationally challenging even for problems of small size. We reformulate the stress as an Euclidean Distance Matrix (EDM) optimization with box constraints under the help of the idea of Robust Multidimensional Scaling. A key element in our approach is the conditional positive semidefinite cone with rank cut. Although nonconvex, this geometric object allows a fast computation of the projection onto it and it naturally leads to a majorization-minimization algorithm with the minimization step having a closed-form solution. Moreover, we prove that our EDM optimization follows a continuously differentiable path, which greatly facilitated the analysis of the convergence to a stationary point. The superior performance of the proposed algorithm is demonstrated against some of the state-of-the-art solvers in the field of sensor network localization and molecular conformation. For instance, only 190 seconds needed to solve a problem with over 16,000,000 variables, which is far faster than current methods.Finding the best FIFA Ultimate Teamhttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/06/07-finding-the-best-fifa-ultimate-team.pageWed, 07 Jun 2017 00:00:00 +0100
[15:00 - 16:00, 7 June 2017]
In this presentation, I shall be presenting my model, created for finding the best Ultimate Team on FIFA. I shall discuss how the game works, what defines the best team, along with the limitations which mean that finding the best team is not so straight forward. Outlining the structure of my model, giving reasons for each step and how I have shrunk the initial problem to make it much more manageable. Examining optimal teams that have been produced, and proving that the results do define the best team, plus mentioning future additions that will be useful to every gamer.Facility Location with item storage and deliveryhttps://cdn.southampton.ac.uk/assets/imported/transforms/site/seminar/PageThumbnail/DC9E7769C2FB4350856A5DE28BE64D56/ruth-walton.jpg_SIA_JPG_fit_to_width_XL.jpghttps://www.southampton.ac.uk/siamsc/news/seminars/2017/05/24-facility-location-with-item-storage-and-delivery.pageWed, 24 May 2017 00:00:00 +0100
[15:00 - 16:00, 24 May 2017]
The Royal National Lifeboat Institution (RNLI) is the UK’s largest lifeboat charity, and has been saving lives around the coast of the UK for almost 200 years; this work is part of an ongoing research activity aimed at improving their warehousing and logistics operations. We consider a facility location problem to determine the optimal number and location of warehouses, as well as which items should be stored in each location, with the objective of minimising storage and transportation costs, both from supplier to warehouse and warehouse to end user. We propose a mixed-integer non-linear programming formulation of the problem, which we then linearise in two different ways: the computational performance of these methods is compared, and the problem is solved to optimality using CPLEX, with potential savings identified in the case of the RNLI.A meta-heuristic technique for the packing of three-dimensional irregular pieceshttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/04/26-meta-heuristic-for-packing-3d-irregular-pieces.pageWed, 26 Apr 2017 00:00:00 +0100
[15:00 - 16:00, 26 April 2017]
The 3D irregular open dimension problem consists in placing a set of irregular pieces in a container of a fixed base, with the objective of minimising its height. This problem, not very often studied in the literature, has a wide range of applications in 3D printing, packaging or component layout, among others.
To tackle this problem, we choose a discrete representation of the geometry that uses voxels, the three- dimensional equivalent of pixels. In this discretised space, we define the no-fit voxel. This is an extension of the two-dimensional no-fit polygon, a very popular tool used in two-dimensional packing. The no-fit voxel can be pre-calculated and allows us to very quickly evaluate intersections of pieces during the algorithms and provides a complete description of the valid relative positions between two pieces. Using this tool, we propose a meta-heuristic algorithm that allows overlap of pieces in its intermediate steps. It consists of two components, a search phase and strategic oscillation. In the search phase we perform a number of piece movements and swaps with the aim of resolving the overlap and finding feasible solutions. In the strategic oscillation, we increase or reduce the height of the container depending on the status of the layout.
We test this technique across a range of different instances. We adapted some instances from the existing literature, both two and three-dimensional. To deal with more complicated shapes, we also propose two other sets of instances. The first one consists in shapes randomly generated by ourselves by adapting 2D image generation algorithms. The second set consists in collections of parts of realistic objects taken from 3D printing websites. Our results show that this is a robust technique that can be successfully applied to find dense packings across pieces with very different features, regardless of their geometric attributes.Computing the (pre)Nucleolus of general cooperative gameshttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/03/22-computing-the-prenucleolus-of-general-cooperative-games.pageWed, 22 Mar 2017 00:00:00 +0000
[15:00 - 16:00, 22 March 2017]
Cooperative game theory models various types of cooperation, often considering certain fair or stable division problems. The Nucleolus is one of the most widely known and studied solution concepts in the field, it is desirable due to its numerous attractive properties (such as existence and uniqueness, among many others). However, computing it requires finding a payoff lexicographically minimising ordered vectors of exponential lengths, which is an immensely challenging task, even for relatively small (starting from n~25 players) general games and many classes of structured games. The most frequently used formulation of the problem involves solving a sequence of at most n-1 linear programs of size O(2^n)*(n+1). We present a new algorithm for finding the (pre)Nucleolus of general cooperative games, based on duality and balancedness considerations of tight (active) sets of coalitions. This new approach benefits from the lack of necessity to formulate large linear programs, solving these LPs by focusing on much smaller systems.Modelling pathways to diagnosis of breast conditionshttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/03/15-modelling-pathways-to-diagnosis-of-breast-conditions.pageWed, 15 Mar 2017 00:00:00 +0000
[15:00 - 16:00, 15 March 2017]
Nationally, there was a 26% rise in patients referred to breast diagnostic clinics from 2010 to 2015, causing increased pressure on resources. This talk outlines OR modelling work to improve the route to diagnosis of breast conditions, in collaboration with a breast diagnostic clinic. A logistic regression scorecard was developed which uses GP referral information to predict abnormal breast diagnostic results. Current work involves incorporating the scorecard inside a discrete event simulation of the clinic, in order to measure the benefits of a scorecard-based triage system.Payoff Allocation Methods for Generalized Minimum Spanning Tree Gameshttps://cdn.southampton.ac.ukhttps://www.southampton.ac.uk/siamsc/news/seminars/2017/02/22-payoff-allocation-methods-for-generalized-minimum-spanning-tree-games.pageWed, 22 Feb 2017 00:00:00 +0000
[15:00 - 16:00, 22 February 2017]
The minimum-cost spanning tree game is a particular class of cooperative games defined on a graph, where each player owns a vertex. Solutions of the game represent ways to distribute the total cost of a minimum-cost spanning tree among all the players. When we partition the graph into clusters, the generalised minimum spanning tree problem is to determine a minimum-cost tree including exactly one vertex from each cluster. The paper introduces and studies the generalised minimum spanning tree game and some of its properties. We propose a constraint generation algorithm to calculate a stable payoff distribution and present some computational results obtained using the proposed algorithm.Exact Algorithms for the Close-enough Traveling Salesman Problemhttps://cdn.southampton.ac.uk/assets/imported/transforms/site/seminar/PageThumbnail/EB21C8145C9F4DBEB2728C4B16AF3A00/walton-coutinho.jpeg_SIA_JPG_fit_to_width_XL.jpghttps://www.southampton.ac.uk/siamsc/news/seminars/2017/02/08-exact-algorithms-for-the-close-enough-traveling-salesman-problem.pageWed, 08 Feb 2017 00:00:00 +0000
[15:00 - 16:00, 8 February 2017]
This work deals with the Close-Enough Traveling Salesman Problem (CETSP). In the CETSP, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose two simple yet effective exact algorithms based on a Second-Order Cone Programming (SOCP) formulation. The proposed algorithms were tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider instances in both two- and three-dimensional spaces.