Seminarier i optimeringslära

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. 

Tid och lokal

Seminarietiden är vanligtvis fredagar kl 13:15 i Hopningspunkten som ligger i B-huset, ingång 23, plan 2, Campus Valla i Linköping.

Kommande seminarier

Onsdag 28 september, kl 14.00-15.00 i Mångfalden, Michael Saunders, Stanford University

Titel: Algorithms for Constrained Optimization: The Benefits of General-purpose Software
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.

 

Under perioden 18 oktober - 19 oktober anordnar Elliits dagliga seminarier. Läs mer om Elliits seminarieserie.


Tidigare seminarier Visa/dölj innehåll

Onsdag 22 juni 2022, kl. 10:15, Presentation av examensarbete på kandidatnivå, Erik Thomas 

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

Tisdagen 14 juni 2022, kl. 10:15, Presentation av examensarbete på kandidatnivå, Anna Tarasova

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.

Fredag 10 juni 2022, kl. 10:15, Presentation av examensarbete på kandidatnivå, Simon Calderon

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.

Onsdag 8 juni 2022, Presentation av examensarbete på masternivå

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 pro- gramming (CP) have been successfully applied to solve large-scale scheduling and resource allocation problems. This combination typically solves an assign- ment 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 prop- erties 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 optimiza- tion 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 pro- duction 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.

Onsdag 25 maj 2022, Presentation av examensarbete på kandidatnivå Ida Vickes Åkerholm

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 multi- ple 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 fron- tier 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.

Fredag 6 maj 2022, Jan Rolfes, KTH

Titel: Distributionally robust optimization with envelope and moment information

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.

Fredag 22 april 2022, Henrik Andersson, NTNU

Titel: A matheuristic for the production routing problem

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.

Måndag 25 april 2022, Presentation av examensarbete på masternivå Saga Fahlén

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.

Torsdag 14 april, 2022 Presentation av examensarbete på kandidatnivå, Gustav Villwock

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.

Fredag 1 april 2022, Niki Matinrad, ITN

Titel: Models for Dispatch of Volunteers in Daily Emergency Response

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.

Fredag 8 april 2022, Jan Kronqvist, KTH

Titel: A disjunctive perspective on mixed-integer optimization

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. 

Fredag 4 mars 2022, Justin Pearson, Uppsala universitet

Titel: Declarative Local Search with MiniZinc

Sammanfattning: In this talk I will give an overview of ongoing research at Uppsala on a fully declarative local search solver using MiniZinc. MiniZinc is a high-level language that allows combinatorial (optimisation) problems to expressed at a high-level, similar in spirit to languages such as GAMS and AMPL. The MiniZinc tool chain provided interfaces to solvers using many different solving technologies, such as constraint programming, Boolean satisfiability (SAT) solvers, mixed-integer programming solvers and many more.

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.

Onsdag 23 februari 2022, kl 13:15-14:15, Tatiana Tchemisova, University of Aveiro, Portugal 

Anordnas i samarbete med Matematiska kollokviet. 

Titel: On phenomenon of Immobility in study of convex Optimization problems

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.

Fredag 25 februari 2022, Elina Rönnberg, Matematiska institutionen, Linköpings universitet

Titel: Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning 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.

28 januari 2021, Björn Morén, Matematiska institutionen, Linköpings universitet

Titel: Robust optimization to mitigate rotational uncertainty effects in
intensity modulated brachytherapy

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.

Torsdagen 19 november 2020, Yura Malitsky, Matematiska institutionen, Linköpings universitet

Titel: Adaptive gradient descent without descent

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 presentation is based on an ICML paper: https://arxiv.org/abs/1910.09529.

The slides used during the seminar can be downloaded here.

Torsdag 5 mars 2020, Mikael Rönnqvist, Université Laval, Québec, Kanada

Titel: Optimization of primary extraction routes using the decision support system BestWay

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.

Torsdag 9 januari 2020, Stephen Maher, University of Exeter, Storbritannien

Titel: Experiments with a general Benders' decomposition framework in SCIP

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.

Torsdag 19 december 2019, redovisning från kursen Projekt i tillämpad matematik (CDIO)

Titel: Optimering av värmekameraplacering

Å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

Torsdag 12 december 2019, Kristian Lundberg, Saab AB

Titel: Supply chain and maintenance optimization in a multi-stakeholder context

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.

Måndag 28 oktober 2019, Jan Kronqvist, Imperial College London, Storbritannien

Titel: (Convex) Mixed-Integer Nonlinear programming

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.

Torsdag 3 oktober 2019, Yu-Hong Dai, Chinese Academy of Sciences, Beijing, Kina

Titel: Solving Heated Oil Pipelines Problems Via Mixed Integer Nonlinear Programming Approach

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.

Torsdag 12 september 2019, Ion Necoara, University Politehnica Bucharest, Rumänien

Titel: Minibatch Stochastic First Order Methods for Convex Optimization

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.

Tisdag 13 augusti 2019, Nikolaos Pappas, Institutionen för teknik och naturvetenskap, Linköpings universitet

Titel: Low Latency Communications for Wireless Networks: Exploiting Traffic Characteristics

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.

Onsdag 12 juni 2019, Anders N. Gullhav, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology

Titel: Multi-Appointment Scheduling at a Psychiatric Outpatient Clinic

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.

Torsdag 2 maj 2019, Nils-Hassan Quttineh, Matematiska institutionen, Linköpings universitet

Titel: Challenges in Nutrient Recycling and Biogas Plant Localization

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.

Torsdag 4 april 2019, Kaj Holmberg, Matematiska institutionen, Linköpings universitet

Titel: A new method for optimal proportional representation

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.

Torsdag 21 mars 2019, Sebastiaan Breedveld, Erasmus University Medical Center, Rotterdam

Titel: Automated multi-criteria treatment planning in radiation therapy

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.

Tisdag 12 februari 2019, Ana Moura, University of Aveiro, Portugal

Titel: Some combinatorial optimization problems in distribution and logistics operations

Organisatör Visa/dölj innehåll

Arkiv 2010-2018 Visa/dölj innehåll

Fler seminarieserier vid Matematiska institutionen Visa/dölj innehåll

Institution och avdelning Visa/dölj innehåll