Seminarieserien är ett informellt diskussionsforum för utbyte av tankar och idéer om forskning inom optimeringslära, algoritmer, problem och tillämpningar. Alla intresserade är välkomna.
Seminarierna äger rum i Hopningspunkten som ligger i B-huset, ingång 23, plan 2, Campus Valla i Linköping.
Sammanfattning: Applying decomposition techniques to mathematical programs requires a suitable framework for the implementation of the related algorithms. While decomposition algorithms have largely required custom implementations and problem specific algorithms, since its inception the SCIP Optimisation Suite has provided a level of support for implementing decomposition algorithms. The common misconception that decomposition algorithms must be problem specific has hindered the development of general frameworks for Dantzig-Wolfe reformulation and Benders' decomposition. This shortcoming has been addressed in the SCIP Optimisation Suite with the availability of GCG (Generic Column Generation) and the Benders' decomposition framework in SCIP. GCG and the Benders' decomposition framework offer users state-of-the-art generic algorithms while also providing flexibility to implement custom decomposition approaches. This talk will discuss the decomposition frameworks available in SCIP and highlight some of the most valuable features.
Sammanfattning: The rerouting aspect of railway rescheduling has received little attention in research. Train rerouting occurs frequently when maintenance works have to be planned, but also during large disruptions. We focus on the setting of a fully blocked railway line, where the infrastructure manager provides a set of trains that have to be reinserted to the timetable. We first explore an algorithm for obtaining multiple suitable train paths for a single train. We then describe how we aim to use this procedure for developing a new heuristic approach for rerouting multiple trains, which is based on solving independent set problems. We present our first results for a case study of a closure of the southern main line around Hässleholm, causing diversions via the western coast line, Göteborg, and the western main line.
Sammanfattning: Two-stage stochastic programming is a popular framework for optimization under uncertainty, where decision variables are split between first-stage decisions, and second-stage (or recourse) decisions, with the latter being adjusted after uncertainty is realized. These problems are often formulated using Sample Average Approximation (SAA), where uncertainty is modeled as a finite set of scenarios. This results in a large "monolithic" problem, i.e., where the model is repeated for each scenario. The resulting models can be challenging to solve, and several problem-specific decomposition approaches have been proposed. An alternative approach is to approximate the expected second-stage objective value using a surrogate model, which can then be embedded in the first-stage problem to produce good heuristic solutions. In this work, we propose to model the distribution of the second-stage objective instead, specifically using a quantile neural network. Embedding this distributional approximation enables capturing uncertainty and is not limited to expected-value optimization, e.g., the proposed approach enables optimization of the Conditional Value at Risk (CVaR). We discuss optimization formulations for embedding the quantile neural network and demonstrate the effectiveness of the proposed framework using several computational case studies including a set of mixed-integer optimization problems.
Sammanfattning: Semidefinite programming (SDP) deals with the problem of minimizing linear functions subject to linear matrix inequalities (LMIs) and belongs to conic optimization. A wide variety of nonlinear convex optimization problems can be formulated as problems involving LMIs, and hence efficiently solved using recently developed interior-point methods. Semidefinite programming has been recognized in combinatorial optimization as a valuable technique for obtaining bounds on the solution of NP-hard problems. It provides important numerical tools for analysis and synthesis in systems and control theory, robust optimization, computational biology, systems and control theory, sensor network location, and data analysis, among others.
Regularity is an important property of optimization problems. Various notions of regularity are known from the literature, being defined for different classes of problems. Usually, optimization methods are based on the optimality conditions, which in turn, often suppose that the problem is regular. The absence of regularity leads to theoretical and numerical difficulties, and solvers may fail to provide a trustworthy result.
In the first part of the talk, we present a novel approach to the algorithmic investigation of the regularity of linear SDP problems. This approach is based on the notions of immobile indices and their immobility orders. For the linear semidefinite problem, we define the subspace of immobile indices and formulate the first-order optimality conditions in terms of a basic matrix of this subspace. These conditions are explicit, do not use constraint qualifications, and have the form of criterion.
In the second part, we present an algorithmic generator constructing nonregular SDP instances with prescribed irregularity degrees and present a database of nonregular test problems created using this generator. Numerical experiments using popular SDP solvers on the problems of this database permit us to conclude that the most efficient solvers are not efficient when applied to nonregular problems.
The presentation is based on joint work with O. Kostyukova (National Academy of Sciences of Belarus) and E. Macedo (University of Aveiro, Portugal)
Sammanfattning: There is an emerging need to reduce CO2 emission due to the climate change. Currently, the use of diesel in transportation and harvest operations are high. There are several initiatives and innovations in the Swedish forest industry to convert to electrical systems. The first case is to start using electrical trucks. In the seminar, we discuss an analysis of how the introduction of fully electrical logging trucks will impact the use of diesel truck. The second case is the use of multirotor drones in thinning operations. Here, we analyze the performance of such systems in comparison with existing two-machine systems.
Sammanfattning: The Electrical Vehicle Routing Problem (EVRP) is a child of the classical Vehicle Routing Problem, one of the most popular problems within optimisation. In this talk I will talk about what I have been doing my first year of PhD, namely implementing a full branch-and-price to solve the EVRP. I will talk about the custom pricing-solver, tricks needed for branching related to this and other speed-ups that was needed in order to solve more than toy instances.
Furthermore I will talk some about the specific problem that we have decided to focus on first: The Electrical Vehicle Routing Problem with Capacitated Recharging Stations.
Sammanfattning: The following problem arises in routing of unmanned aerial vehicles. Let G be an undirected graph with nonnegative edge weights and assign to each vertex a critical weight value. We consider the problem of finding a covering of the vertices by disjoint cycles so that the weight of every cycle does not exceed the critical weight value of each vertex contained in it (where the weight of a cycle is the sum of the weights of the edges contained in it). The goal is to find such a cycle cover with a minimum number of cycles. We shall discuss complexity as well as some simple heuristics for this problem.
Länk till artikeln Length-constrained cycle partition with an application to UAV routing
Anordnas i samarbete med Seminarier i tvärvetenskaplig matematik.
Sammanfattning: Successful deployment of Machine Learning (ML) algorithms on physical systems requires the development of new learning mechanisms that can commit to making appropriate decisions on the fly and using only limited available data collected for an unseen task. Despite its vital importance, existing ML algorithms for control systems typically impose restrictive data requirements on the system in terms of the number of samples required to learn. Additionally, it is difficult to provide performance guarantees. On the other hand, classical approach for control systems are offline and ensures theoretical guarantees but lacks adaptability. The purpose of this talk is to propose a new learning framework for control systems that 1) is online and adaptive, 2) provides performance guarantees, and 3) is sample efficient.
Anordnas i samarbete med Seminarier i tvärvetenskaplig matematik.
Sammanfattning: This presentation will be about my postdoc period for half a year at McGill University, Montreal, Canada. I was at a Medical Physics Unit with much research focus on AI and brachytherapy, which is a type of radiation therapy where the radiation is given from within the body. In the first part of the presentation, I will describe how the cooperation was formed, my motivation for going there, and how it is to be in an environment that is very different from what you are used to.
In the last part I will discuss one of my projects during the visit more details. One of their specialties is developing new types of delivery techniques for brachytherapy treatment of rectal cancer, and they were planning the next steps to do a clinical trial. Our research project was aimed at investigating positional uncertainties in the treatment and the robustness of their delivery prototype.
Sammanfattning: ESammanfattning: This presentation will be about my postdoc period for half a year at McGill University, Montreal, Canada. I was at a Medical Physics Unit with much research focus on AI and brachytherapy, which is a type of radiation therapy where the radiation is given from within the body. In the first part of the presentation, I will describe how the cooperation was formed, my motivation for going there, and how it is to be in an environment that is very different from what you are used to.
In the last part I will discuss one of my projects during the visit in more details. One of their specialties is developing new types of delivery techniques for brachytherapy as different techniques are used for each treatment site. When I came there, they worked on a new prototype for brachytherapy treatment of rectal cancer, and they were planning the next steps to do a clinical trial. Our research project was aimed at investigating positional uncertainties in the treatment and the robustness of their delivery prototype.
Sammanfattning: The increase of demand for air transportation has heightened the challenges faced by air traffic management (ATM). One of the critical problems in ATM is the design of aircraft arrival routes in a terminal maneuvering area (TMA). The problem comes with a myriad of constraints such as no sharp turns, merge point separation, obstacle avoidance, temporal separation of all aircraft, etc. We study this problem and discuss different aspects of modeling the problem as an integer programming.
Sammanfattning: Linear optimization, also known as linear programming, is a modelling framework widely used by analytics practitioners. The reason is that many optimization problems can easily be described in this framework. Moreover, huge linear optimization problems can be solved using readily available software and computers.
However, a linear model is not always a good way to describe an optimization problem since the problem may contain nonlinearities. Nevertheless such nonlinearities are often ignored or linearized because a nonlinear model is considered cumbersome. Also there are issues with local versus global optima and in general it is just much harder to work with nonlinear functions than linear functions.
Over the last 15 years a new paradigm for formulating certain nonlinear optimization problems called conic optimization has appeared. The advantage of conic optimization is that it allows the formulation of a wide variety of nonlinearities while almost keeping the simplicity and efficiency of linear optimization. Therefore, in this presentation we will discuss what conic optimization is and why it is relevant to analytics practitioners. In particular we will discuss what can be formulated using conic optimization, illustrated by examples. We will also provide some computational results documenting that large conic optimization problems can be solved efficiently in practice.
To summarize, this presentation should be interesting for everyone interested in an important recent development in nonlinear optimization.
Sammanfattning: Newton-based methods form an important class of methods for solving smooth optimization problems. This talk concerns methods for unconstrained problems and constrained problems where the constraints are handled by a barrier transformation. Typically a nonlinear problem is solved by finding exact or approximate solutions of simpler subproblems. A Newton-based method typically uses exact second-derivatives, allowing rapid asymptotic convergence, but may come at the expense of high computational cost per iteration. For large-scale problems, the use of exact second-derivative information may become too costly. The development of quasi-Newton methods or other modified Newton methods based on approximating second-derivative information is then of utmost importance. In the talk, we discuss ways to solve approximate subproblems that may give an overall gain in computational complexity. Motivation from problems arising in optimization in radiation therapy will be included.
Sammanfattning: Mixed integer programming (MIP) is a field where the application of quantum computers is expected to bring significant performance improvements. In order to solve a MIP on a quantum computer, it is necessary to perform mathematical transformations to reformulate the problem into a quadratic unconstrained binary optimisation (QUBO) problem. While such transformations are effective for integer programs with equality constraints, the existence of inequalities and continuous variables in MIPs can result in extremely large QUBO formulations. Various types of decomposition can be performed to separate the "mixed" part of the problem from the "integer" part---the latter which can be solved as a QUBO and, thus, on a quantum computer. This talk will provide an introduction to the transformations from MIP to QUBO and describe the application of Lagrangian relaxation, Dantzig-Wolfe reformulation and Benders' decomposition. We will show that the use of decomposition techniques provides many opportunities for solving MIPs in classical/quantum hybrid computing environments.
Sammanfattning: This talk summarise the topic of my doctoral thesis and the current work i am conducting at KTH. Both topics involves the DNN but with different meanings: Doubly non-negativity or deep neural network.
In the first part, the talk will introduce the NP-hard graph partition problem and its doubly non-negative relaxation where the variable is both semidefinite positive and element wise nonnegative. This approach is completed by two variants alternating direction methods of multipliers for solving large-scale semidefinite programming problems. Performance of our algorithms are illustrated with benchmark instances with medium to high density.
The second part of this talk introduces a model-based input feature selection approach to design Deep Neural Networks with significantly fewer connections, reducing computational effort and producing neural networks that are more robust toward adversarial attacks. The input feature selection is formulated as a sequence of mixed-integer linear programming problems that find sets of sparse inputs that maximise the classification confidence of each category. The numerical results on the well-known MNIST and FashionMNIST datasets show that the proposed input feature selection allows us to drastically reduce the size of the input to ~15% while maintaining a good classification accuracy. This allows us to design deep neural networks with significantly fewer connections, reducing computational effort and producing neural networks that are more robust towards adversarial attacks.
Sammanfattning: In this talk I will present some previously known results on finite termination of quasi-Newton methods with the BFGS update for quadratic problems. Some more recent work will also be discussed.
In the classic case, the approximation of the Hessian is updated at every iteration and exact line search is used. It is well known that the algorithm terminates in at most $n$ iterations. Constant updates and exact line search are sufficient, but not necessary however, for finite termination. This talk will discuss how update skipping, unit step size, or a combination of the two can also reach the exact minimizer in a finite number of iterations.
Sammanfattning: I will present an integrated master surgery and outpatient clinic scheduling problem, motivated by the situation at the Orthopaedic Department at St. Olav’s Hospital, Trondheim. During a treatment process, the patients require one or several consultations at the outpatient clinic, and potentially a surgery in one of the operating rooms. The physicians perform both consultations and surgeries, and coordinating the two facilities is challenging. The surgeons are trained to handle different surgical specialties, and they differ in experience. The overall goal is to create a master schedule, i.e., schedule the specialties and surgeons, to time slots in the outpatient clinic and operating rooms throughout the week, to efficiently handle the patient demand. We develop a simulation model for evaluating the master schedules in an operational setting, and three different operational scheduling policies are compared.
Sammanfattning: True North Marine (TNM) is a Montreal based consulting company offering services on route selection and analysis to ocean-going vessels, operators and owners. The need for optimized routing has gained relevance in the age of JIT arrivals, fluctuating fuel costs and tightening emission standards. The efficient route requires a deep understanding of the interplay between fuel consumption, vessel speed and safety depending on the weather. Today, there are many high accuracy sources on ocean currents and seas and winds, the three primary weather elements that go towards route planning. Other important information that affects a voyage planning include among others; storm locations and movements and their historical tracks, wind speed and direction, sea currents, wave height and frequency. The weather condition is vital in the route planning. The IMO (International Maritime Organization) has implemented new regulations, as of January 1st 2020, requiring vessels to burn fuel with much lower sulphur content (drop from 3.5% to 0.5%) with anticipated effect that fuel costs for vessel operators will significantly rise. It is hence expected that new vessel routes better must balance operational cost, fuel and greenhouse gas (GHG) emission cost, and weather-related safety issues. True North Marine is working together with Université Laval, HEC Montreal and UQTR (University Quebec Trois-Rivieres) in a project funded by IVADO, Prompt and MITACS to develop advanced analytics tools to support the planning process. More specifically, these tools allow analyzing many routes in order to determine the optimal speed / fuel consumption setting and best route option based on forecast weather data, historical weather data, vessel characteristics and data obtained from monitoring past performance of vessels. In this presentation, we provide an insight in the practical planning process and analytics tools developed so far to support the planners which will go towards more precise and dynamic routing
Sammanfattning: In today's society, transports are essential to secure necessary products and services to maintain our standard of living. Given the importance of transportation and logistic services and their impact on the environment, economy, and people's lives, it is in everyone's interest that these transports are as efficient as possible. This presentation will discuss the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem, a newly introduced variant of the well-known Vehicle Routing Problem. It is a real-world problem originating from the policies of a Nordic distribution company.
The problem includes
Original vehicles with attached swap-bodies depart from the central depot. They can either visit customers directly if only one swap-body is attached or visit one or two consecutive switch points in order to transfer one or two loaded swap-bodies to a corresponding number of local vehicles, which are subsequently routed to customers while the original vehicle itself proceeds to serve customers with the remaining loaded swap-body. We will cover a brief description of the problem and different model formulations. Furthermore, the properties of the problem and the difficulties in solving instances using a commercial solver. Different solution approaches for solving realistic-sized instances from which the problem originated will also be discussed before we conclude with possible directions for further research.
Sammanfattning: Deliveroo is a British online food delivery company, currently operating in 11 countries. It serves a three-sided marketplace of consumers, restaurants/grocers and riders. Consumers order restaurant food and groceries to their doors through the Deliveroo app or website. The Dispatcher algorithm is responsible for planning routes for riders to pick up and deliver orders. The routing problem is both large and dynamic (new orders received, riders going online/offline, rider locations change, riders accept/reject order assignments). In this talk, we will discuss the problem definition, why the problem is hard to solve, and considerations for our approach. We will also touch on what it is like working with Operational Research at Deliveroo.
Sammanfattning: We review the history of numerical optimization and describe some (unexpected) applications of general-purpose software in aerospace, signal analysis, systems biology, economics, radiotherapy.
Opponent: Gustav Villwock
Handledare: Kaj Holmberg
Examinator: Torbjörn Larsson
Lokal: Hopningspunkten, B-huset, ingång 23-25, A-korridoren, plan 2, Campus Valla
Titel: Improving snow removal plans through task reassignment
Sammanfattning: TB
Opponent: Beatrice Söderqvist
Handledare: Roghayeh Hajizadeh
Examinator: Kaj Holmberg
Lokal: Hopningspunkten, B-huset, ingång 23-25, A-korridoren, plan 2, Campus Valla
Titel: Tour expansion in snow removal problem
Sammanfattning: The process of removing snow from the streets of cities in an optimal way can pose quite a challenge. In order to optimize the path of the snow removing vehicle, the city can be translated into a graph with nodes as crossings and links as roads. Once the city is modelled as a graph, all nodes with degree one can be eliminated and the snow removal time is added to the closest node. An optimization problem can then be solved in order to find a vehicle path in this reduced graph. The purpose of this thesis is to give an algorithm to reconstruct the reduced graph and then dictate the proper vehicle path in this reconstructed graph. The algorithm is constructed by reversing the node elimination process, piecing together the original graph and traversing the graph to get information about what to do on the eliminated links and nodes. The obtained algorithm is presented in this thesis.
Opponent: Gustav Eriksson
Handledare: Anders Peterson
Examinator: Kaj Holmberg
Lokal: Hopningspunkten, B-huset, ingång 23-25, A-korridoren, plan 2, Campus Valla
Titel: An ILP-model for the train platforming problem
Sammanfattning: The goal of this thesis is to create an optimization model to optimize the routing of trains within railway stations. This problem is known as the train platforming problem, and the model we present is a Integer programming model. By this model we aim to optimize factors such as walking distance, switch usage or platform usage. We validate the model by implementing the model for Linköping station, which is a typical mid size station in the Swedish railway network. This implementation is done for different time horizons, ranging from 2 hours to one day, and from 27 to 265 trains. In conclusion we see that model is efficient for optimizing the train platforming problem for the implemented station and timetables, and see that the model has possibility to optimize the four objectives tested. Furthermore we see that optimizing certain objectives gives solutions that are also good with regards to other objective functions.
Framläggningarna kommer att ske i BL33 Samtliga framläggningar kan följas via Zoom, men vi accepterar enbart auskultationer på plats.
Klockan 13.15 Måns Alskog
Opponenter: Lina Larsson, Mikaela Lindberg
Handledare: Christiane Schmidt (ITN), Hannes Uppman (Saab)
Examinator: Elina Rönnberg
Titel: Implementation of a Fast Approximation Algorithm for Precedence Constrained Scheduling
Sammanfattning: We present a practical implementation of a recent approximation algorithm for scheduling jobs on a single machine with precedence constraints, minimising the total weighted completion time. The algorithm, which was published by Li in 2021, is a (2+ε)-approximation algorithm with run time O(n+k)⋅polylog(n+k)⋅log³(maxⱼ pⱼ)⋅1/ε²), where n is the number of jobs, k is the number of precedence constraints and maxⱼ pⱼ is the largest of the processing times of the jobs. Unlike other approximation algorithms for this problem, this algorithm has been developed with a focus on obtaining a good asymptotic run time guarantee, rather than obtaining the best possible guarantee on the quality of solutions. Finally, we empirically evaluate how well (our implementation of) this algorithm performs in practice.
Klockan 14.15 Alexander Grgic och Filip Andersson
Opponenter: Måns Alskog
Handledare: Elina Rönnberg (MAI), Emil Karlsson (Saab)
Examinator: Nils-Hassan Quttineh
Titel: Using maximal feasible subset of constraints to accelerate a logic-based Benders decomposition scheme for a multiprocessor scheduling problem
Sammanfattning: Logic-based Benders decomposition (LBBD) is a strategy for solving discrete optimisation problems. In LBBD, the optimisation problem is divided into a master problem and a subproblem and each part is solved separately. LBBD methods that combines mixed-integer programming (MIP) and constraint programming (CP) have been successfully applied to solve large-scale scheduling and resource allocation problems. This combination typically solves an assignment master problem and a scheduling-type subproblem. However, a challenge with LBBD methods that have feasibility-type subproblems are that they do not provide a feasible solution until an optimal solution is found.
In this master thesis, we show that feasible solutions can be obtained by combining feasible parts of an infeasible master problem assignment. We use these insights to develop an acceleration technique for LBBD that solves a series of subproblems, according to algorithms for finding a maximal feasible subset of constraints (MaFS). Using a multiprocessor scheduling problem as a benchmark, we study the computational impact from using this technique. We evaluate three variants of LBBD schemes. The first uses MaFS, the second uses irreducible subset of constraints (IIS) and the third combines MaFS with IIS. Computational tests were performed on an instance set of multiprocessor scheduling problems. In total, 83 instances were tested, and their number of tasks varied between 2794 and 10,691. The results showed that when applying our acceleration technique to the decomposition scheme, the pessimistic bounds were strong, but the convergence was slow. The decomposition scheme combining our acceleration technique with the acceleration technique using IIS showed some potential to accelerate the method.
Klockan 15.15 Lina Larsson och Mikaela Lindberg
Opponenter: Alexander Grgic och Filip Andersson
Handledare: Nils-Hassan Quttineh (MAI), Lars Abrahamsson & Jonas Funkquist (Vattenfall)
Examinator: Elina Rönnberg
Titel: Modeling the Head Effect in Hydropower River Systems using MILP and BLP Approaches
Sammanfattning: With the fast-growing electricity demand and a larger proportion of intermittent energy sources follows a greater need for flexible and balancing sources of electricity, such as hydropower. Planning of hydropower production turns out to be a difficult problem to solve due to several nonlinearities, combinatorial properties and the fact that it is a large scale system with spatial-temporal coupling. Optimization approaches are used for solving such problems where a common simplification is to disregard the effect of head variation on the power output. This thesis presents two methods for modeling the head dependency in optimization models for hydropower river systems, the Triangulation method and the Bilinear method. The Triangulation method implements a three-dimensional interpolation technique called triangulation, using a MILP formulation. The Bilinear method applies a piecewise bilinear approximation for the power production function, resulting in a BLP problem. A strategy for selecting which hydropower stations to include head dependence for is also provided. The performance of the methods was evaluated on authentic test cases from the Lule River and compared to results obtained by Vattenfall’s current model without head dependency. The results indicate that the Triangulation method, as well as the Bilinear method, outperform the current model regarding accuracy. However, the run time of the developed methods is sometimes considerably longer.
Framläggningen sker i Kompakta rummet klockan 13.15.
Opponent: Jakob Jonsson
Handledare: Nils-Hassan Quttineh
Examinator: Torbjörn Larsson
Titel: Lagrangian Bounding and Heuristics for Bi-Objective Discrete Optimisation
Sammanfattning: For larger instances of multi-objective optimisation problems, the exact Pareto frontier can be both difficult and time consuming to calculate. There already exists a wide range of methods to find feasible solutions to these problems, but techniques for finding good optimistic bounds to compare the feasible solutions with are missing. In this study, the use of Lagrangian relaxation to create optimistic bounds to bi-objective optimisation problems is investigated. The aim is to develop an effective method that produces optimistic bounds closer to the Pareto frontier than the commonly used linear programming relaxation.
To use Lagrangian relaxation on the bi-objective problem, the objectives are combined to one using the weighted sum method. The Lagrangian dual function is then constructed by relaxing the complicating constraints and the subgradient method is used to optimise the dual problem in order to find an optimistic solution. By solving this problem for multiple weights, an optimistic bound to the Pareto frontier can be constructed. The subgradient method also require a heuristic to find feasible points. The feasible solutions found by the heuristic form a pessimistic bound to the frontier.
The method has been implemented and tested on multiple problem instances of a capacitated facility location problem with cost and CO2 emission as objectives. The results indicate that, by using Lagrangian relaxation, an optimistic bound close to the Pareto frontier can be found in a relatively short time. The heuristic used also manage to produce a good pessimistic bound and hence the Pareto frontier can be enclosed. The optimistic bounds found by Lagrangian relaxation are better and more consistent along the Pareto frontier compared to the bounds found by linear programming.
Sammanfattning: Driven by an application from chromatography, we model an optimization problem with linear objective subject to robust constraints that depend on an uncertain particle size distribution (psd).
Without further restrictions on the moments of this psd the problem would be too conservative. Thus, we combine a generalized form of the classical moment constraints by Shapiro with a set of confidence set constraints on the psd. The latter are informed by an envelope around the psd. Thereby, we decrease the conservatism in our model and aim to optimize the fractionation process together with our colleagues in process engineering.
Sammanfattning: We will discuss the production routing problem, where a product is produced at a single plant and then distributed by trucks to a set of retailers over a defined planning horizon. A production schedule for the plant, together with a distribution schedule for the retailers and routes for each vehicle, must be decided. The goal is to minimize production and transportation costs, in addition to inventory holding costs. We present a multi-start route improving matheuristic to solve the problem. In each restart, a valid solution to the problem is constructed, and its routes are used as input to a novel path-flow-inspired model that allows for alterations to the routes. This path-flow-inspired model is re-solved for several iterations.
Framläggningen sker i Hopningspunkten klockan 15.15.
Titel: Prediction of the Impact of Increased Photovoltaics Power on the Swedish Daily Electricity Spot Price Pattern
Sammanfattning: As the demand for electricity increases throughout the globe while we want to reduce the use of fossil fuels, the need for renewable energy sources is bigger than ever. In countries where solar power make up a large part of the total energy production, the overall electricity spot price level has become lower. This thesis investigate the underlying mechanism that drives the energy market, and in specific, how the solar power impacts the electricity spot price. We present results from studies made in other markets, and introduce a regime switching model for explaining the impact in Sweden. We show that an increase of photovoltaics power has a price lowering effect on the dailyprice pattern in price areas SE3 and SE4.
Opponenter: Eric Thomas och Herman Singh. Handledare: Nils-Hassan Quttineh. Examinator: Torbjörn Larsson.
Titel: Workforce Scheduling for Flamman Pub & Disco
Sammanfattning: Workforce scheduling is widely used within most industries. A well outlined and efficient schedule gives cost savings, such as reduced wages for working overtime, increases overall resource utilization, and facilitates meeting demands. This thesis evaluates two different methods for implementing a workforce scheduling system for Flamman Pub & Disco, one of Linköping's most well-known restaurants and bars for students. Flamman recruits new staff prior to every semester, and the workforce typically consists of around 100 employees that work either in the bar or in the kitchen. Historically, the scheduling process has been handled manually in Excel, and takes time for the operations manager.
This thesis suggests an automated scheme for future scheduling processes, using mixed integer programming and heuristics. Literature studies have shown that heuristics, such as large neighbourhood search, can generate sufficient performance for this kind of problems. Therefore, to avoid expensive licensed optimization software, we investigate the use of a free-of-charge software based on a heuristic. The results show that a heuristic can be a helpful tool for upcoming recruitment periods. However, we recommend areas for improvement regarding the heuristic.
Sammanfattning: Sufficient emergency resources are essential for emergency services to provide timely help to affected people and to minimize damage to public and private assets and the environment. Emergency services, however, face resource shortages and increasing demand over time. As a result, their response times increase, resulting in lower survival chances of affected people and more severe damage to properties and the environment. Thus, emergency services need to utilize and effectively manage all their available resources. These can be divided into traditional resources, such as ambulances, and new and emerging resources, such as volunteers. Models and methods developed using operations research (OR) methodologies can facilitate the management of these resources. However, despite a rich literature on OR-based models and methods focusing on traditional resources, the literature on new and emerging resources, and specifically volunteers, is scarce.
The aim of this study is to develop models and methods for task assignment and dispatch of volunteers to daily medical emergencies. The developed models and methods consider volunteer programs in Sweden and the Netherlands, employing real historical data. The aim is addressed in two steps. First, different types of new and emerging resources used in daily medical emergency response are investigated. Then, in the core part of the study, the focus is on the development of models, methods, and strategies for task assignment and dispatch of volunteers to out-of-hospital cardiac arrest (OHCA) cases using OR, specifically optimization and simulation. To evaluate the survival rates of these patients, the most important health outcome of a response process, survival functions have been used in the development of these models and strategies. In this part of the study, first, a simplified setting for the dispatch of volunteers is considered where all aspects are deterministic. Then, to depict the reality better, different uncertain elements are included in different models and methods; examples of these elements are the uncertainties associated with the actions of volunteers once they are assigned a task are considered, the uncertainty of notification acceptance, the uncertainties related to the travel times of volunteers and EMS, presence of bystanders on site, and the availability of mobile automated external defibrillators (AEDs).
The overall conclusion of this study is that the use of OR-based models and methods can contribute to improved outcomes and increased survival probabilities compared to the strategies and techniques used in the existing systems.
Sammanfattning: Disjunctive programming is an alternative approach towards modelling mixed-integer problems introduced by Egon Balas in the 70s. The key component in disjunctive programs is so called disjunctive constraints that forces the solution to satisfy one set of constraints from a collection of constraints. The feasible set is of a disjunctive constrain is, thus, the union of a finite number of sets. However, disjunctive programs cannot be directly solved as such. Instead they are normally transformed into classical mixed-integer problems and solved as such. It is, therefore, fair to ask “what’s the point of disjunctive programming“.
In this seminar, we will look at how we can benefit from viewing mixed-integer problems as disjunctive problems and a new hierarchy of formulations for expressing disjunctive constraints in classical mixed-integer programming form.
Local search is a widely used solving paradigm where an initial random assignment is modified by local moves that attempt to move the assignment closer to a solution. On large combinatorial problems, local search can be a very effective heuristic. Unfortunately to be effective the types of local moves have to be hand crafted for the individual problem that is been considered.
For a number of years at Uppsala we have been developing a back-end to MiniZinc that will automatically implement local search algorithm given a MiniZinc model. This is joint work with Gustav Björdal, Frej Knuter Lewander, and Pierre Flener.
Anordnas i samarbete med Matematiska kollokviet.
Sammanfattning: We are concerned with convex problems of infinite Optimization, namely problems of convex Semi-Infinite Programming (SIP) and linear problems of Semidefinite Programming (SDP).
Semi-Infinite Programming deals with extremal problems that consist in minimization of an objective function of finitely many variables in a set described by an infinite system of constraints. SIP models appear in different fields of modern science and engineering where it is necessary to simulate a behavior of complex processes whose models contain at least one inequality constraint for each value of some parameter (for example, time) varying in a given compact domain.
In Semidefinite Programming, an objective function is minimized under the condition that some matrix valued function is positive semidefinite. When the objective function is linear and the matrix valued function is an affine combination of some symmetric matrices, we get a convex problem. There are many applications of SDP models to combinatorial optimization, control theory, approximation theory, etc.
Optimality conditions for Optimization problems are of special interest both from theoretical and practical points of view. A special attention is devoted to the results that do not need additional conditions on the constraints, so called constraint qualifications (CQ).
In the talk, we present the results on optimality and strict duality for convex Semi-Infinite Programming problems which are obtained based on a new concept of immobile indices of constraints. We show how this concept can be applied to problems of linear SDP . The main result consists in new CQ-free optimality conditions for the considered classes of Optimization problems.
Författare: Stephen J. Maher and Elina Rönnberg
Sammanfattning: Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited.
This paper proposes a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem.
The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG.
Sammanfattning: Intensity modulated brachytherapy (IMBT) is an emerging technology for cancer treatment, in which shielded sources are used to shape the dose distribution. We study the effects of rotational uncertainties in the shields with respect to planning criteria. A robust optimization approach is proposed to take several planning scenarios into account, where each scenario corresponds to a specified rotational error.
We consider the prototype for platinum-shielded prostate 169-Yb-based IMBT, described by Famulari et al. (2019), and use a retrospective patient data set (anatomical contours and catheter placement) from two clinics. The data set is based on conventional 192-Ir high dose-rate brachytherapy treatment. In order to take the effects of shields of a high-Z material into account, Monte Carlo simulations are used to generate the dose-rate contributions. In our computational experiments we primarily consider rotational shield errors of the size of 10 degrees which are systematic, that is, the rotational errors are the same for all dwell positions in each scenario.
The proposed robust optimization model puts a penalty on a combination of the average and worst outcomes. Three scenarios are included in the model, the nominal scenario and the two scenarios with errors of plus and minus 10 degrees, respectively. We compare results from the non-robust model, in which only the nominal scenario is included, with the robust model. For both models we evaluate the obtained dose distributions for all scenarios. Furthermore, to test the capability of the robust model we also consider scenarios with larger rotational errors (up to 20 degrees).
We study the effects of the robust approach on both the objective function value and the planning criteria which are used clinically. In terms of objective value, the dose distribution from the robust model is worse than the non-robust dose distribution. However, for clinical planning criteria there are instead improvements with the robust model.
The urethra is the organ-at-risk that is most affected by the rotational errors. With dwell times obtained from the non-robust model, the dose to urethra increased with up to 5% in the worst scenario. With dwell times obtained from the robust optimization model the highest dose to the urethra is stable for all scenarios. In particular, we show that with the robust model the dose to urethra is lower in the worst scenario compared to the non-robust model. The benefit from the robust model is greater for larger rotational errors.
With the robust optimization approach we were able to mitigate the effects from rotational errors in the shield placement, without compromising target coverage or dose distribution quality. Hence, robust optimization can be used to ensure the expected quality of treatment with IMBT.
Sammanfattning: In this talk I will present some recent results for the most classical optimization method -- gradient descent. We will show that a simple zero cost rule is sufficient to completely automate gradient descent. The method adapts to the local geometry, with convergence guarantees depending only on the smoothness in a neighborhood of a solution.
The slides used during the seminar can be downloaded here.
Sammanfattning: In recent years, there is increasing attention improving productivity in forest logging operations while reducing negative impact on soil and water streams. The position of primary extraction routes is crucial in these efforts as it has a huge impact on efficient and sustainable forwarder passages. To minimise the total driving distance, but also to avoid steep terrain and impact on soil and water, a decision support system based on an optimization model was developed. The system comprises a detailed digital terrain model, depth-to-water maps and forest volume all derived from lidar data. The information is supplemented with the extent of the stand, the position of the landing(s), nature and culture conservation sites, and any known unavoidable crossings in the terrain, e.g. streams. A critical requirement of the planning process is fast solution times. Hence, a decomposition method based on Lagrangian relaxian is used to define subproblems that can be very efficiently solved by specifically designed subroutines. The system has been evaluated on two case studies. In the first case study, the optimization model was analysed on xx harvest areas spread across Sweden. In the second case, the primary extraction routes, resulting from the model, have been evaluated on 19 felling sites in operational conditions with experienced staff from a major forest company in southern Sweden. The results indicate a shorter driving distance, but also the potential to reduce the negative impact on soil and water.
Sammanfattning: Benders' decomposition is a popular mathematical programming technique for solving large scale optimisation problems. While Benders' decomposition is historically viewed as requiring a problem specific implementation, general frameworks can provide an ideal platform for the investigation of general algorithm enhancement techniques. Such a broad investigation was not possible until only recently when Benders' decomposition frameworks have been implemented in general purpose solvers. This talk will give an overview of the current features within the Benders' decomposition framework available with SCIP and GCG. In addition, current work on cut enhancement techniques and the handling of integer subproblems will be discussed. This talk will demonstrate the value of a general framework for the development and investigation of enhanced algorithms for Benders' decomposition.
Årets upplaga av projektkursen TATA62 lider mot sitt slut, och en av projektgrupperna har jobbat med ett avancerat kameraövervakningsproblem, ett optimeringsproblem som går ut på att bestämma var och hur olika kameramodeller ska placeras för att övervaka så stor yta som möjligt till så låg kostnad som möjligt. Beställare av projektet är Per-Magnus Olsson som jobbar på Termisk Systemteknik.
Sammanfattning: Projektet går ut på att undersöka optimeringsmetoder för kameraplacering vid övervakning av bränslelager. Systemet som utvecklas ska kunna ta in kartor över dessa lager och ge förslag på kameraplacering som maximerar övervakad yta till ett så lågt pris som möjligt. Att övervaka precis allt blir oftast otroligt dyrt, även om motsvarande kameraplacering är optimal, vilket gör att man istället önskar generera en Paretofront av lösningar där de två målen täckningsgrad och kostnad står i ett tydligt motsatsförhållande. Under projektets gång har ett antal olika heuristiska lösningsmetoder implementerats, bland annat populationsbaserade metoder. Dessa har testats på 12 probleminstanser hämtade från verkligheten. Resultaten är lovande, främst då flera metoder tillåts samverka på ett effektivt sätt, med relativt korta körtider och bra approximationer av Paretofronten.
Seminariet hålls på engelska.
Projektdeltagare: Mirjam Mattsson, Martin Fakt, Mehdi Foroozandeh, Oscar Göransson, Anja Hellander och Albin Ryberg
Sammanfattning: This presentation will pinpoint an important challenge in tomorrow’s aircraft systems. We will discuss the background and preconditions for management and control of maintenance and support of tomorrow’s aircraft systems. How can we do things more efficiently? How can we approach new business models in a multi-stakeholder environment? By the integration of systems and stakeholders in a system-of-systems context, mathematical optimization can be applied to bring a more holistic approach across the supply chain. Some examples will be given followed by an open discussion. The project is a cooperation between Saab AB and Chalmers.
This talk will mainly focus on algorithms for convex MINLP.
Sammanfattning: Mixed integer nonlinear programming (MINLP) offers a flexible framework for dealing with a wide variety of optimizations tasks, but it also inherits the combinatorial challenges from integer programming and numerical challenges from nonlinear programming. MINLP problems are automatically nonconvex due to the integer restrictions; however, they are still commonly classified as either convex or nonconvex based on their continuous relaxation. Convexity is a desirable property since it enables a straightforward decomposition of the problem into a sequence of tractable subproblems.
During the last decades, several algorithms have been presented for convex MINLP, such as nonlinear branch and bound, generalized Bender’s decomposition, and several algorithms based on polyhedral outer approximations. The most common algorithms will be presented during the talk, and we examine some convergence properties of the algorithms. Some important solver features will also be discussed, and we look at the convex MINLP solver SHOT in more detail.
Sammanfattning: It is a crucial problem how to heat oil and save running cost for crude oil transport. This paper strictly formulates such a heated oil pipelines problem as a mixed integer nonlinear programming model. Nonconvex and convex continuous relaxations of the model are proposed, which are proved to be equivalent under some suitable conditions. Furthermore, we may provide a preprocessing procedure to guarantee these conditions. Therefore we are able to design a branch-and-bound algorithm for solving the mixed integer nonlinear programming model to global optimality. To make the branch-and-bound algorithm more efficient, an outer approximation method is proposed as well as the technique of warm start is used. The numerical experiments with a real heated oil pipelines problem show that our algorithm achieves a better scheme and can save 6.83% running cost compared with the practical scheme. This is a joint work with Muming Yang, Yakui Huang and Bo Li.
Titel: On the Complexity of Sequentially Lifting Cover Inequalities for the Knapsack Polytope
Sammanfattning: The well-known lifted cover inequality is widely employed in solving mixed integer programs. However, it is still an open question whether an arbitrary project lifted cover inequality can be computed in polynomial time for a given minimal cover (Gu, Nemhauser, and Savelsbergh, INFORMS J. Comput., 26: 117123, 1999). We show that this problem is NP-hard, thus giving a negative answer to the question. This is a joint work with Wei-Kun Chen.
Sammanfattning: In this talk we analyze the convergence rates of (minibatch) stochastic first order methods with constant or variable stepsize for specific classes of convex optimization problems. We show that these methods can achieve linear convergence rate up to a constant proportional the stepsize and under some strong stochastic bounded gradient condition even pure linear convergence. Moreover, when variable stepsize is chosen we derive sublinear convergence rates that show an explicit dependence on the minibatch size. Applications of these results to convex feasibility problems will be also discussed.
Sammanfattning: The main goal of the next generation mobile communication is to provide seamless communication for a massive amount of devices building the Internet-of-Things and at the same time to support the constantly increasing traffic demands originated from personal communications. The major difference between 5G and the previous generations is the native support of ultra-reliability, low latency, and the massive access.
Ultra-high reliability and ultra-low latency are required by several applications and services such as autonomous vehicles, factory automation, telepresence, smart grids etc. A natural way to distinguish the traffic inside a network is according to data rates, latency, and reliability. Another way to distinguish the traffic is related to the content itself, if it is reusable or not. For example, voice calls or remote control signals are not-reusable content. On the other hand, most of the network traffic today is cacheable or reusable, which is approximately 60%. This is another important aspect that must be taken into account for the efficient design of networks in order to reduce the unnecessary transmissions and leave more resources for the non-reusable and critical content.
During this talk we will discuss and present results that consider the aspects mentioned above. More specifically, we will focus on theoretic principles of low-latency traffic, content caching, and age of information. The latter is a concept that was introduced recently and can quantify the freshness of the knowledge we have about the status of a remote system.
Sammanfattning: We consider the problem of scheduling appointments in diagnostic pathways at a Norwegian psychiatric outpatient clinic for children and adolescents. Referred patients are assigned a diagnostic pathway consisting of a diagnostic plan of multiple activities, e.g., consults and tests. The plan might be changed or extended along the course of the pathway. Recently, the Norwegian government set a bound of 42 days on the makespan of the diagnostic pathway, which is calculated from the first diagnostic activity to the diagnosis is set. Moreover, waiting time requirements specify a deadline for when the first diagnostic activity has to be performed. The problem involves scheduling all activities in a specific diagnostic pathway for all newly referred patients, so that the waiting time and makespan are within the specified bounds, and the resource and precedence requirements of the activities are satisfied. In this work, we propose a mixed integer programming (MIP) model to perform the scheduling. To test the MIP in a stochastic and dynamic setting, we have developed a simulation model. We simulate different objectives, which gives us insights into their effect on waiting time and makespan.
Sammanfattning: Nutrient management, particularly with respect to nitrogen (N) and phosphorus (P), is crucial for a sustainable food system. In order to increase crop yields, it is common practice to apply synthetic fertilizers to areas with crop nutrient needs. However, synthetic fertilizers can be costly, and losses of nutrients from croplands, animal rearing, and sewage systems can lead to water quality degradation; prompting many countries to revisit how organic waste which is high in N and P can be better managed.
Issues of over- and under-abundance of nutrients often co-exist in the same country because of agricultural specialization. Reconnecting areas with crop needs and areas with higher concentrations of human and animal organic waste through recycling can thus potentially help countries meet both food security and environmental goals. The recycling of bio-supply (animal manure and human excreta) is currently low, hence there is a great potential to increase this recycling in order to meet crop needs, and at the same time decrease the use of synthetic fertilizers. A quantitative analysis for Sweden and Pakistan is presented.
Other recycling technologies, such as biogas plants, are also studied, and we present a mathematical model selecting biogas plant locations (basically a Facility Location Problem) which minimize transport distances associated with transporting and transforming all manure and then redistributing the nutrients to meet crop demand.
Sammanfattning: In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is the feasible solution that has the minimal
disproportionality (with the measure chosen), even in the presence of a parliament threshold, which is not always the case for the practical procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the modified Sainte-Lague method, which is presently used. A natural suggestion would be to use our method instead.
We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. The numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants. This removes the need for compensatory mandates, and makes the question about sizes of the constituencies less important.
Sammanfattning: In radiotherapy, the treatment of cancer patients requires a personalised treatment plan. The plan describes how the dose (damage) resulting from irradiation is distributed inside the patient. The goal is to optimally irradiate the tumour, while keeping the doses to the healthy organs as low as possible. Distributing the dose over the different healthy organs is a multi-criteria problem with 10-30 correlated criteria. In current worldwide clinical practice, the multi-criteria optimisation and decision-making is performed by a human operator in an interactive trial-and-error procedure. Due to the complexity and dimensionality of the problem, this manual approach often results in suboptimal treatment, and a higher probability of developing complications. Besides the decision-making component, effectively solving the underlying numerical optimisation problem is another challenge.
By specifying a decision strategy upfront, clinically favourable treatment plans can be generated automatically. Such plans can be generated without manual interaction within minutes for external beam cases, and seconds for brachytherapy cases. In clinical comparison studies, we have demonstrated that automatically generated treatment plans are of at least equal, but generally more preferred for treatment.
Other advantages of automated treatment planning are performing objective studies in designing new treatment protocols, and objective patient selection for improved radiotherapy techniques with limited availability, such as proton therapy.
