OR lunch seminar

“Decentralized optimization of multi-commodity flows over time”

Over the last 15 years, research on collaborative logistics has gained traction and resulted in a wide variety of research contributions that assess the potential and benefits of supply chain collaboration on the efficiency and performance of logistics.  Existing methods, however, tend to assume a long-term commitment between a small, fixed group of companies (e.g., a group of companies operating a joint transport corridor by bundling volumes). While such an approach might be viable in specific, small-scale cases, it lacks scalability and limits a healthy competition. In this research, we want to focus on the tension field between the (unrealistic) idea of supply chain collaboration – and the large gains it brings – and complete decentralization.  The goal is to understand how (partial) decentralization can alleviate the limitations of fully centralized supply chain collaboration while preserving synergy creation as much as possible (e.g., by giving concrete incentives and providing the possibility for spontaneous interaction).

“From OR to quantum computing: Am I in a superposition or are those fields entangled?”

During this talk, prof. dr. Frank Phillipson will talk about his background and experiences in applying OR in telecommunication, logistics, defense and scheduling during the (almost) 25 years carreer at KPN and TNO. The lasts years, Frank made the shift to quantum computing applications and machine learning. He will tell you why he made this shift, what quantum computing is and how this can help solving optimisation problems and what the plans for his endowed chair ‘Computational Operations Research’ look like. ​

“Envy-free Pricing of Seats in a Planetarium”

In this talk, we study a geometric envy-free pricing problem with a single item demand. The aim of the seller is to maximize the revenue by assigning prices to points and by allocating customers to these points in an envy-free manner, i.e., every allocated customer receives a point of the highest possible utility and all non-allocated customers cannot afford any point. Next to the continuous problem, we consider a discrete version where customers purchase the tiles of a regular tessellation of the plane, e.g., squares of the grid or hexagons of the honeycomb. For the special case of continuous version of the problem, where all customers have the same preferred point, we introduce a dynamic programming algorithm solving the problem in polynomial time. For the discrete version of the problem, we extend the dynamic programming algorithm to the quasi-polynomial time approximation scheme.

“Optimality of Quasi-Polynomial Time Algorithms”

Lars will talk about some future research ideas. In algorithm design, the classical notions of efficiency and inefficiency (polynomial running time and exponential running time) do not cover quasi-polynomial time algorithms, which lie in between them. This leaves the corresponding problems in an uncertain state. A lot of scientific effort goes into trying to improve these quasi-polynomial running times to polynomial ones, but little is done to show that some of these problems might not be solvable in polynomial time. What tools do we have to achieve such lower bounds?

“Toward the smoothed analysis of k-jump neighborhood”

In this talk, we consider the problem of scheduling jobs on identical parallel machines to minimize the makespan. We analyze a simple local search method w.r.t. the so-called k-jump neighborhood.  We will talk about the worst-case running time of the algorithm. The idea of the research is to see whether the worst-case running time can be improved by applying smoothed analysis.

“Bi-objective Path Planning with Objectives of Minimizing Length and Maximizing Clearance”

Path planning problem is one of the challenging problems in the field of computer science and robotics. Because of its widespread crucial applications, it is, therefore, not surprising that research activity on this problem and its different versions has been steadily increasing over the last two decades. In this thesis, we study the problem of bi-objective path planning among polygonal obstacles with the objectives of minimizing the length and maximizing the clearance of the path, that is, maximizing the minimum distance between the path and the obstacles. The goal is to find all Pareto optimal paths.