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

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

Tid och plats: Tisdag 13 augusti 2019, Hopningspunkten, kl 10:15

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.


Tidigare seminarier
Visa/dölj innehåll

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

Torsdag 6 december 2018, Oleg Burdakov, Matematiska institutionen (MAI), Linköpings universitet

Titel: Semi-conjugate direction algorithms for saddle problems and monotone equations

Sammanfattning: Problem of finding saddle points for strictly convex-concave functions is considered. We present semi-conjugate direction algorithms for solving this problem. They are extensions of some conjugate direction algorithms known in unconstrained optimization. For quadratic functions, they converge to saddle points in a finite number of steps. In the non-quadratic case, the asymptotic rate of their convergence is quadratic. Extensions to monotone equations are discussed. We present results of numerical experiments for quadratic saddle problems and linear monotone equations.

Joint work with: Yu-Hong Dai and Na Huang

Torsdag 20 september 2018, Hani Ahmadzadeh, Sharif University of Technology, Tehran, Iran

Titel: The Role of Numerical Optimization in The Development of Algorithms for Solving Mixed Integer Nonlinear Programming Problems

Sammanfattning: Recently, Mixed Integer Nonlinear Programming (MINLP) problems have attracted the attention of many researchers. Despite the flexibility of MINLP in modeling the real-life problems in various fields of science, engineering, and economics, solving this type of problems encountered different difficulties. Resolving these issues requires the combination and adaption of several techniques from Nonlinear Programming (NLP) and Integer Programming (IP).

In this presentation, we survey some of the well-known algorithms for solving MINLP problems. In each step of these algorithms, at least one NLP problem must be solved. Hence, we review three popular families of algorithms for solving NLP problems, namely Sequential Quadratic Programming (SQP), Interior Point Method (IPM) and Augmented Lagrangian (AL). We compare the advantages and disadvantages of these algorithms to clarify which one would be the best choice for solving NLP subproblems in MINLP algorithms. Finally, we introduce some of the best solvers for solving MINLP problems.

Torsdag 13 september 2018, Michael Saunders, Stanford University, USA

Titel: Algorithm NCL for constrained optimization

Sammanfattning: Standard optimization solvers have difficulty if the active-constraint gradients are not independent at a solution (if the problem doesn't satisfy LICQ). For example, problems of the form min f(x) st c(x) >= 0 (m constraints and n variables) may have more than n constraints active at a solution. Such problems arise in the modeling of tax policy (with perhaps millions of constraints and thousands of variables).

Algorithm NCL solves a sequence of about 10 augmented Lagrangian subproblems with constraints c(x) + r >= 0. The extra variables make the constraints linearly independent, and the subproblem solutions converge to the required solution as r is driven to zero. IPOPT and KNITRO are able to warm-start each subproblem. Assuming second derivatives are available, NCL expands the use of interior methods for large-scale optimization.

Joint work with Ding Ma, Kenneth Judd, and Dominique Orban.

Tisdag 22 maj 2018, Mikael Rönnqvist, Université Laval, Québec, Kanada

A joint seminar for Optimization, Department of Mathematics (MAI) and Production Economics, Department of Management and Engineering (IEI)

Titel: Improving the Safety, Environmental Consciousness, and Cost Effectiveness of Truck Routing

Sammanfattning: Calibrated Route Finder (CRF), an online route generation system, successfully finds the best route when many conflicting objectives are involved by using analytics in a collaborative environment. CRF, which has been in use since 2009, uses many diverse big data sources, which must be revised continuously. One of its key features is its use of an innovative inverse optimization process that establishes more than 100 weights to balance distance, speed, social values, environmental impacts, traffic safety, driver stress, fuel consumption, CO2 emissions, and costs. The system enables the measurement of hilliness and curvature and incorporates rules that consider legal and practical issues related to routing in and around cities, turning in intersections, time delays, fuel consumption, and CO2 emissions that result from waiting, acceleration, and braking. The system is used by all major forest companies in Sweden and in 60 percent of the two million annual transports in this sector. It has resulted in a paradigm shift from manual, imprecise, and unilaterally determined routes to automatically determined routes, which the stakeholders determine jointly. It has also enabled standardization, promoted collaboration, and reduced costs, thus strengthening the competitiveness of the Swedish forest industry in the international market.

Torsdag 17 maj 2018, Daniel Petersson, Veoneer

Seminariet är ett samarrangemang med Tvärvetenskapliga seminarier på Matematiska institutionen (MAI).

Titel: Eyes for self-driving cars

Sammanfattning: The development of technical systems has in many ways been dramatically changed during the last years through the breakthrough of deep learning. Traditional machine learning techniques using hand-crafted features have been successful for many applications, such as object detection in vision systems. However, the deep learning framework often enables higher performance, shared computations between different applications, and the ability to solve more advanced problems such as autonomous driving.

In the seminar, I will share experiences from the Veoneer development of vision systems for cars, such as data driven development and how the new advancements in the field of deep learning affect our products/services, as well as our ways of working.

Torsdag 5 april 2018, Günther Raidl, Institute of Logic and Computation, TU Wien, Österrike

Titel: Hybrid Optimization Approaches for Challenges in Public Bike Sharing Systems

Sammanfattning: After a brief introduction of the Algorithms and Complexity Group of TU Wien, this talk will give some insight on algorithms we developed for two optimization problems arising in the setup and maintenance of public bicycle sharing systems (BSS).

Operators of traditional station-based BSSs have to regularly redistribute bikes across the rental stations in order to prevent them getting overly full or empty. This is usually achieved with a fleet of vehicles with trailers. We will consider hybrid PILOT, GRASP and Variable Neighborhood Search metaheuristics that utilize certain flow models for an effective transportation tour planning.

When establishing a new BSS or extending an existing one, one of the core questions is at which locations rental stations of which size should be built. We model this station planning problem on the basis of a given expected customer traveling demand over the considered geographical area and locations where stations can potentially be built.

Our objective is to maximize the actually satisfied demand under budget constraints. In order to deal with the huge amount of input data for a larger city, we apply a hierarchical clustering based modelling approach. The optimization problem is then solved by a multilevel refinement metaheuristic making use of mixed integer linear programming and local search techniques.

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