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: In this talk we will go through some very recent results on the topic of compressed sensing using a fix number of materials to augment the inverse tomography problem with applications in electron microscopy. We will touch on problems associated with optimal assignments on convex and bilinear objectives, optimal transport with quadratic nonconvex cost and solver implementation considerations associated with large scale problems.
Sammanfattning: This talk presents an overview of applied research conducted at Einride on the inclusion of Electric Vehicle Routing Problem (EVRP) models into strategic-operational decision-making.
The transition to battery electric trucks is critical for decarbonizing freight transport, yet its strategic evaluation is often impeded by a disconnect between strategic and operational decision making, with high-level techno-economic models failing to account for the operational reality of logistics service providers. Much of the existing literature assesses fleet electrification through Total Cost of Ownership (TCO) analyses that rely on aggregated historical data and/or assume a direct one-to-one replacement of diesel vehicles. These approaches fundamentally overlook the complex techno-economic characteristics and constraints of battery electric trucks such as higher capital costs, lower operational costs, limited range, charging requirements, and payload capacities.
Our findings challenge the commonly held assumption that historical operational patterns of diesel trucks are representative of mixed fleet operations. By using large-scale, data-driven simulations of real-world logistics networks, we show that optimal operational plans for battery electric trucks are fundamentally different from their diesel counterparts. Furthermore, the impact of incorporating EVRP models into decision making is quantified in terms of TCO savings, electrification rates, and operational patterns.
Sammanfattning: This study presents an optimisation model for the self-scheduling of a hydrogen-based virtual power plant (H2-VPP) in the day-ahead electricity market. The model strategically integrates renewable energy sources, battery storage, electrolysers and hydrogen storage to maximise operational efficiency and economic performance. By optimising the interaction between electricity and hydrogen networks, it enables better resource management and increased use of renewable energy. A case study evaluates different system configurations, highlighting the impact of battery storage and hydrogen tanks on cost reduction. The results show that excluding battery storage increases costs by up to 87%, while excluding hydrogen storage increases costs by up to 153%. These findings underline the critical role of storage technologies in increasing flexibility, minimising electricity purchases and improving market competitiveness. The proposed framework supports the development of hydrogen-bas
Sammanfattning: Nanotomography techniques such as electron tomography (ET) and nano X-ray computed tomography (nano-CT) allow high-resolution 3D imaging of functional materials (e.g. catalyst supports, battery electrodes or photonic crystals) and the determination of important material properties such as particle and pore size, position and interconnectivity, or chemical composition.
However, tomography always comes along the challenge of the proper acquisition of projection data where the measured intensity is monotonically related to a certain material property, e.g. mass-thickness. For certain applications, e.g. phase contrast nano-CT, the correct consideration of the imaging physics in 3D reconstruction algorithms remains a challenge. If not properly described, this can lead to strong reconstruction artefacts. Moreover, beam sensitivity or specific sample geometry may prevent the acquisition of full 180° tilt series with adequate angular sampling which would be required for artefact-free 3D reconstruction. A possible solution to reduce the amount of projection data required while maintaining reconstruction quality is to use compressed sensing approaches by taking into account certain prior knowledge about the sample characteristics, such as that the sample contains only a small number of piecewise constant material phases. In a first approach, we utilized this information by deriving valid constraints on the allowed reconstructions, whereas later, we first approximated the nonconvex Sobel operator to capture “sharp edges”, i.e., a rapid transition between material and void, and then nudge the compressed sensing algorithm towards reconstructing sharper edges.
Sammanfattning: How can we recover clear, reliable images or signals when our observations are indirect, incomplete, and corrupted by noise? This challenge arises in many fields—from medical scans and satellite imaging to data analysis in science and engineering. Mathematically, such problems are known as inverse problems, and they are often “ill-posed,” meaning that small errors in the data can lead to large errors in the result. Traditional methods, such as compressive sensing, have shown impressive results in producing high-resolution reconstructions. However, these approaches can be sensitive to parameter choices and typically provide only a single “best guess” solution—without telling us how confident we should be in that result.
In this talk, I will describe how we can address these limitations by adopting a Bayesian perspective. Instead of producing just one answer, Bayesian methods treat image reconstruction as a problem of statistical inference: they combine information from the data (what we observed) with prior knowledge (what we expect the image to look like) to produce a full probability distribution of possible solutions. This distribution not only yields reconstructions that are robust but also provides a natural way to quantify uncertainty—for example, highlighting which parts of an image are reliable and which are not. I will discuss how we design priors that preserve essential features, such as edges, and how we efficiently compute with these models using ideas from optimization and measure transport. Additionally, I will explore how these methods perform in practice for applications in medical imaging, remote sensing, multi-measurement problems, and time-dependent imaging tasks.
Sammanfattning: By performing a sufficient set of MRI measurement, it is possible to estimate various properties of tissue, e.g., the brain. Of interest for us is a second order tensor/matrix called the diffusion tensor and also a fourth order tensor (the covariance tensor). Finding these from the measurements is a fitting problem with can be solved by least squares. Under that approach, the estimates may be unphysical, and we discuss how one can use semidefinite programming to impose positivity conditions which are known to hold.
Sammanfattning: Functions in optimization can be broadly classified as glass-box or black-box. On the one hand, glass-box functions are those with a fully known mathematical structure that is implementable and solvable with an optimization modeling language (e.g., Pyomo) and a dedicated solver (e.g., HiGHS). On the other hand, black-box functions are those with an unknown or unavailable mathematical expression, as these may require a complex series of steps for their computation, e.g., experimentation, simulation, or even glass-box optimization. Glass-box and black-box problems are generally studied separately, while combined glass-box/black-box optimization is rarely studied in the literature.
This talk introduces black-box cutting plane (BCP): a local exploration framework for hybrid black-box/glass-box optimization. BCP currently handles problems that minimize the sum of a glass-box function and a monotone functional of black-box functions, subject to a compact search-space defined by glass-box functions. BCP differs from standard cutting plane methods in the sense that, instead of evaluating a solution candidate and generating a cut for this candidate at each iteration, BCP samples multiple solution candidates within a neighborhood and uses their objective function information to heuristically generate a cut at each iteration. Two techniques to generate these cuts are introduced: one that relies on the generalized simplex gradient (GSG) and one that requires the solution of an auxiliary linear program (ALP). Overall, ALP has better underestimating properties than GSG at the expense of requiring more computational time, while GSG generates tighter cuts with the potential drawback of excluding larger search regions from the search space than ALP.
Sammanfattning: Decision makers across various domains often face problems that are subject to uncertainty. Consider planning transport services, operating power systems, determining infrastructure locations, and setting pricing strategies. The integration of machine learning and optimization methods has gained significant attention, both for accelerating solution methods and for enhancing models by training machine learning algorithms on task-specific losses rather than conventional prediction losses. Based on a recent survey on contextual stochastic optimization, we provide an overview of this literature and highlight key challenges, notably decision-dependent uncertainty which remains particularly difficult to address.
Bio: Emma Frejinger is a professor in the Department of Computer Science and Operations Research at Université de Montréal where she holds a Canada Research Chair and an industrial chair funded by the Canadian National Railway Company. Her research is application-driven and focuses on innovative combinations of methodologies from machine learning and operations research to solve large-scale decision-making problems. Emma has extensive experience leading collaborative research projects and working with industry, predominantly within the transportation sector. She serves as a scientific advisor for IVADO Labs, an AI solution provider; as an academic affiliate with Analysis Group; and as an associate member of the machine learning institute Mila. Before joining Université de Montréal in 2013, Emma was a faculty member at KTH Royal Institute of Technology in Sweden. She holds a Ph.D. in mathematics from EPFL, and a master in Industrial Engineering and Management from Linköping University.
Sammanfattning: In this work we consider different methods for cut-generation in order to solve mixed-integer semidefinite programs (MISDPs) within the outer approximation (OA) framework. Utilizing duality in semidefinite programming (SDP) the main components of classical outer approximation can easily be adapted for MISDPs; By fixing the integer variables and solving an SDP at each iteration, the resulting algorithm exhibit similar behaviour and convergence properties.
Another approach for cut-generation comes from the cutting-plane algorithm for SDPs, where valid cuts are derived from eigenvectors corresponding to the (most) negative eigenvalues of the relaxed solution. By sidestepping solving an SDP at each iteration, the cost of cut-generation is significantly lower. On the other hand, since no feasible solution are produced, the resulting algorithm differs significantly from classic OA.
In addition to contrasting the two algorithms we propose new methods for generating cuts – with desirable theoretical and computational properties – and present numerical comparisons.
Sammanfattning: Anaerobic digestion is a key technology for circular economy, converting low-grade biomass (like manure and crop residues) into biomethane and nutrient-rich digestate. It supports both renewable energy production and nutrient recycling, contributing to food and energy security. Biomethane production is expected to grow rapidly, primarily using agricultural resources. However, like other large-scale bioenergy systems, anaerobic digestion depends on extensive transport of biomass and biofertilisers across the landscape. Using a MILP model, we investigate how biogas plants can expand their production considering spatial variability of biomass supply and regional demand for nutrients. The model captures operational constraints, for the plant to run properly, limited supply of biomass, and maximum demands for nutrients to avoid eutrophication. The objective is to maximize net profits, and consists of transportation costs (both for collecting substrates and for redistribution of the biomass digestate) as well as purchasing costs of substrates and processing costs at the biogas plant. We present results for a Swedish case study.
Sammanfattning: CONOPT is a robust nonlinear optimisation solver that has been recently aquired by GAMS. A unique feature of CONOPT is that it is based on the Generalised Reduced Gradient (GRG) algorithm, setting it apart from other nonliner solvers such as IPOPT and Knitro. While the GRG algorithm has been shown to be effective for solving nonlinear programming problems, the ability to solve large-scale problems requires careful algorithmic engineering and enhancement techniques. This talk will dive into the details of the GRG algorithm and various enhancement features that are key to the success of CONOPT. We will discuss the recent development activities that extend the available interfaces to include C++, Python and Java---opening up new possibilities for a clean, efficient and robust integration into various software environments and projects requiring nonlinear optimisation. Finally, we present details about the updates to the licensing that makes CONOPT free for academic use.
Sammanfattning: The electrification of heavy-duty transport is an important contributor to a more sustainable future, a transition that requires more careful planning of how to operate the vehicles. One challenge to address is how to efficiently share charging resources among vehicles to avoid waiting times and unnecessary power peaks. In a joint project with the truck manufacturer Scania, we investigate the potential of introducing bookable time slots at the chargers to tackle this challenge.
To investigate the computational aspects of such an introduction, this paper studies the Electric Vehicle Routing Problem with Time Windows (EVRPTW) and capacitated charging resources available only during specific time slots. This limited availability significantly changes which routes are feasible compared to in the standard EVRPTW. To efficiently solve the problem, we build upon the generic branch-price-and-cut framework GCG which is part of the SCIP Optimization Suite. We extend GCG with both a customised labeling algorithm for solving the pricing problem and problem-specific pricing for integrality. The latter is a heuristic designed to generate columns that are likely to be a part of high-quality integer solutions. The heuristic builds on the more generic LNS-heuristic IPColGen which has a theoretical foundation, leveraging optimality conditions for integer programs. Given a set of columns that constitute an integer partial solution, our heuristic aims at finding columns that complement this solution. This is done by adapting the pricing problem with respect to the partial solution, linear program dual information as well as previously generated columns in the heuristic. Preliminary computational results show that using the heuristic leads to improvements in terms of identifying high-quality integer solutions early in the process.
Sammanfattning: Railway is an environmentally sustainable mode of transportation, which offers convenience for passengers and provides a cost-effective and efficient solution for the movement of goods. However, railway transportation also has drawbacks, especially disruptions due to some incidents, which are difficult to accurately predict and prevent. Infrastructure failure, extreme weather, human error, and lack of staff are typical examples of such incidents. The disruptions cause different levels of train delays and even cancellations. Frequent delays and cancellations make the railway less competitive with other modes of transport. As a result, it is crucial to investigate the possible strategies for rapidly restoring railway traffic after disruptions. In this thesis, we focus on railway rescheduling after near-operational disruptions. We aim to achieve acceptable results within a short time and a small computational effort. This thesis introduces some fundamental concepts related to railway rescheduling, outlines the motivation and research questions of this thesis, discusses further concepts of railway rescheduling including timetable, rolling stock, and crew rescheduling, and displays the relevant methods used for rescheduling. In this thesis, we propose approaches for near-operational rescheduling of the timetable and crew schedules.
Sammanfattning: As the number of electric vehicles rises, there is an increasing demand for algorithms to optimize routes with charging stations. The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is a combinational optimization problem that describes the task of determining optimal routes for a fleet of electric vehicles. The aim is to serve a set of customers, each within a specified time window, while accounting for vehicle battery and cargo limitations, and the availability of recharging stations. When partial charge is allowed and the number of customers increases, the problem complexity rises. Thus, a heuristic approach is a good way to find a solution to the routing problem while minimizing the number of vehicles and the total distance.
The purpose of this study is to examine the performance of two implemented heuristics when applied to the EVRPTW. It aims to compare a Kernel Search (KS) heuristic to an Adaptive Large Neighborhood Search (ALNS) heuristic and evaluate both methods' performance with respect to customer placement and problem size.
The research finds that both heuristics significantly improve the initial feasible solution and perform better on problems with larger time windows, compared to shorter. KS converges rapidly but often to local optima, whereas ALNS converges more slowly yet more consistently escapes local optima. These findings suggest that the heuristics work well on different problem characteristics.
Sammanfattning: Background: Survivors of childhood, adolescent, and young adult (CAYA) cancer have an increased risk of developing cardiovascular disease at a later stage in life. However, the role of co-occurring diagnoses in this population are not yet understood.
Objective: This study aims to investigate combinations of secondary diagnoses among patients with ischaemic heart disease (IHD), and what influence a history of childhood cancer might have on the medical outcome.
Method: We used a subset of the REBUC retrospective cohort study, selecting all individuals diagnosed with IHD (I20-I25). Combinations of secondary diagnoses were analysed across 7, 744 individuals, including 1, 486 CAYAs.
Results: Our findings suggest that male CAYAs receive secondary diagnoses at shorter intervals compared to women and male non-CAYAs, potentially indicating a faster progression or detection of secondary diagnoses. We can also see that CAYAs receive more diagnoses compared to non-CAYAs, and women are more likely to receive more than 2-3 diagnoses compared to men.
Conclusions: The results indicate that although most of the CAYAs are women, men seem to have more advanced complications, which also present themselves faster than for women. Moreover, CAYAs with IHD seem to experience more frequent and complex patterns of secondary diagnoses compared to their non-CAYA counterparts. This suggests that CAYAs might need more specialized long-term treatment plans for a longer healthier life.
Sammanfattning: The Fast Fourier transform (FFT) is an algorithm which transforms sampled data from state-space to Fourier-space. To motivate the FFT, we first approximate the continuous Fourier transform as a matrix product to derive the discrete Fourier transform (DFT) with a time complexity of O(n^2). When the number of samples is a power of two, we can decompose the DFT matrix into log_2(n) products able to be calculated in linear time. This implementation is the Cooley-Tukey FFT, which has an improved time complexity of O( n*log(n) ).
We compare the DFT and FFT algorithms and confirm that the asymptotic time complexity conforms with the theoretical result. We also compare recursive, iterative and multithreaded FFT variants and find that they performed similarly. The choice of programming language, however, has a big impact on performance. Finally, we compare our implementations to the state-of-the-art FFT library FFTW.
We describe how the FFT can be applied to numerically calculate matrix-vector products with circulant and Toeplitz matrices, and how it can be used to filter coastline data.
In conclusion, the FFT algorithm, while theoretically complex, was relatively simple to implement and performed well compared to the naive DFT. An area that could be improved in our implementation is the handling of signal sizes that are not powers of two, however this is not a trivial problem to solve. Still, the algorithm can be used effectively in a wide range of applications.
Sammanfattning: This project investigates how various socioeconomic factors influence survival outcomes related to cardiovascular diseases, with a particular focus on child cancer patients. Key variables include geographic location, lifetime residential mobility, and distance to hospitals, along with other factors such as educational level and marital status.
Data was collected from multiple registries, and included 7744 people who were diagnosed with a cardiovascular disease. Using Cox and logistic regression analyses, along with Kaplan-Meier survival curves, several findings emerged. Being married and having a higher level of education were both associated with significantly improved survival outcomes following diagnosis. Interestingly, individuals who had moved more frequently throughout their lives were at greater risk of earlier disease onset. Contrary to expectations, living farther from a hospital at the time of diagnosis seemed to be linked to higher survival rates rather than lower. Many interesting factors were also studied where no relation could be found.
Sammanfattning: Representation learning is often only seen from the perspective of changing the representation of each and every data point. In this talk, we consider an orthogonal perspective on representation learning and take a closer look at the representation of data in terms of its sample size. Using less but informative data points allows us to learn approximately the same model with high probability in less time; thus allowing for efficient and scalable learning. Specifically, we show several efficient subset constructions on the example of a matrix factorization method and demonstrate connections to well-known optimization methods. Furthermore, we discuss an approach for accelerating the computation of radiation treatment plans.
Sammanfattning: Virtual Private LAN Service (VPLS) is commonly used for secure multi-point communication across geographically scattered industrial sites, simulating a unified LAN broadcast domain for Industrial IoT (IIoT)-type devices. This configuration demands a fully-connected overlay network with encrypted Host Identity Protocol (HIP)/IPsec tunnels exhibiting quadratic scalability to the number of tunnels and a significant increase in forwarding table entries. Herein, we introduce Tunnel Relay Nodes (TRNs) as selected routers that maintain full-mesh connectivity. This approach allows non-TRN routers, or Provider Equipment (PEs) acting as spoke PEs, to connect via a TRN. We explore the challenges of using TRNs in secure HIP-based VPLS (HIPLS) networks, including (i) placing reliable TRNs within provider networks and (ii) scheduling TRNs to minimize their activation/deactivation costs as well as the connection cost among PEs. We then demonstrate how (i) can be addressed in polynomial time using a modified general median problem approach. Additionally, we formulate (ii) as a Mixed Integer Linear Programming (MILP) scheduling problem and prove its NP-completeness. Furthermore, we introduce an algorithm based on Lagrangian relaxation to address the intractability in large-scale deployments. This algorithm offers fast, near-optimal solutions while simultaneously balancing solution quality and execution time. Our simulations on real-world network topologies with real network demands show a 92% average reduction in forwarding table entries on PEs. Compared to existing solutions, our method reduces the number of tunnels established by up to 95%, at the expense of a 1.39-fold increase in tunnel path length.
Sammanfattning: In many applications, it is crucial to determine solutions resilient to uncertainty. Stochastic optimization struggles when probability distributions are unknown or unreliable, while robust optimization, although ensuring feasibility within predefined uncertainty sets, often produces overly conservative solutions.
We begin by reviewing key concepts in robust optimization, including reformulations and decomposition, illustrated through motivating applications. We highlight recent advances in mixed-integer (non-)linear robust optimization and data-driven methods for constructing uncertainty sets. Finally, we introduce distributional robustness, which seeks to balance robustness and performance by protecting against distributional uncertainty, including recent approaches that learn distributions and decisions practically efficient.
Sammanfattning: The presented work addresses two-stage stochastic programs (2SPs). Single-stage deterministic equivalents are computationally challenging even for small instances.
Sammanfattning: The talk describes the core algorithm behind ChatGPT and similar large language models. The main components—autoregression, word vectorization, attention, and the use of neural networks—are explained and exemplified, showing how they come together to form the well-known Transformer architecture.
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: Convex optimization is a powerful tool with applications across numerous fields. In the first part of this talk, I will give a broad introduction to convex optimization, emphasizing what happens "under the hood" when using modeling frameworks like CVXPY.
Despite significant progress in numerical solvers, one class of convex problems remains computationally challenging --- namely semidefinite programs (SDPs). In the second part of the talk, I will present recent research that makes conic first-order solvers for certain SDPs faster. The improvement is based on the notion of spectral matrix cones, which are cones defined from epigraphs and perspectives of spectral functions. To use these cones inside first-order solvers, we must be able to project onto them. Our main result essentially shows that projecting a matrix onto a spectral matrix cone can be reduced to projecting its eigenvalues, which we demonstrate can be done at a negligble cost compared to the eigenvalue decomposition itself. We have integrated support for spectral matrix cone projections into the Splitting Conic Solver (SCS). Numerical experiments show that SCS with this enhancement can achieve speedups of up to an order of magnitude.
The second part of the talk is based on joint work with Stephen Boyd.
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: 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.
