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.

Organisatör är Oleg Burdakov vid avdelning för Optimeringslära, Matematiska institutionen.

Tid och lokal

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

Kommande seminarier

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

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

Tid och plats: Torsdag 9 januari 2020, Hopningspunkten, kl 10:15

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.


Tidigare seminarier
Visa/dölj innehåll

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 contries 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

Sammanfattning: Extended abstract Ana Moura

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