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