Leen Stougie is scientific staff member and group leader of Life Sciences and Health at CWI (Centrum Wiskunde & Informatica) in Amsterdam since spring 2017. Next to that he holds a full professor position in Operations Research at the Vrije Universiteit Amsterdam since end 2008. Before this he worked at the
Technical University Eindhoven (1997-2008), at the University of Amsterdam (1986-1997) and at CWI (1980-1986). He also held several visiting professorships, among others at UC Berkeley, La Sapienza University of Rome, and Technical University of Berlin.
He obtained a PhD-degree in May 1985 at the Erasmus University Rotterdam on a thesis titled "Design and Analysis of Algorithms for Stochastic Integer Programming" under supervision of Jan Karel Lenstra and Alexander Rinnooy Kan.
Leen Stougie’s research interest are mathematics on the interface of operations research, combinatorial optimization and probability theory. Specifically, his interests are in algorithm design and analysis within the framework of complexity theory. A common theme in his research is optimization under uncertainty: stochastic programming, on-line optimization and more recently optimization under scenarios. In combinatorial optimization his work is predominantly on scheduling. Since 2004 he is also involved in projects on computational biology. Specifically his work in this area is concentrated on metabolic network analysis and algorithms for phylogenetic trees and networks. His bioinformatics research has resulted in membership of the INRIA European Research Team ERABLE. He obtained various grants to support his research, of which recently a NWO-ENW-Groot grant for research on optimization for and with machine learning.
For theoretical work on stochastic integer programming he received the 2006 Howard W. Kuhn Award., during the INFORMS meeting, Pittsburgh, Pennsylvania, USA. He has been editor of several journals and served on a wide variety of program committees of conferences; recently ICALP 2020. He has organised several international scientific meetings, among which recently HALG 2018 and MAPSP 2019.
From January 2011 till January 2016 he was chairman of the Dutch National Network for Mathematics
of Operations Research (LNMB).
He was supervisor of 13 PhD-students and is currently supervising 2 PhD-students. He (co-)authored over 100 papers in journals, reviewed conference proceedings and books.
Scheduling over scenarios
Scenarios are basic ingredients of optimization problems under uncertainty. Usually, they are specified only implicitly, e.g.
as ranges over parameter values. Together with a distribution function over the scenarios, they lead to stochastic optimization problems. A classical model here is the stochastic linear optimization problem. A popular approximation method is the Sample Average Algorithm, which samples scenarios and optimizes over them.
Moreover, the value of data is more and more recognized, which may also lead to reckon with scenarios that occur in problems more or less frequently. Anyway, if in this model scenarios are specified completely and individually, then the problem can be formulated as an LP problem, blown up with the scenarios. As a result, the problem remains polynomially solvable.
We wish to investigate if this is a common phenomenon or if complexity of problems can change if scenarios are introduced into a problem. We do so at the hand of studying, most prominently, basic scheduling problems. In such problems we are given a set J of jobs, each with its processing time, a set of parallel identical machines and a set of k scenarios, where each scenario is specified as a subset of jobs in J that must be executed if that scenario occurs.
The goal is to find an assignment of jobs to the machines that is the same for all scenarios, i.e., if a job does not occur in a scenario it is simply skipped. We consider the classical scheduling problems of minimizing the makespan and minimizing the sum of the jobs' completion times. For each scheduling objective we consider minimizing the maximum over all scenarios (robust version) and minimizing the average over all scenarios (stochastic version).
We show that the presence of scenarios may indeed increase the complexity of the problems significantly. As a dramatic example, we mention the ordinary, single scenario, version of the makespan problem with all processing times equal to 1, which is a trivial problem. With scenarios the robust version of the problem becomes inapproximable within ratio 2 unless P=NP. This is even more surprising once one realizes that putting all jobs on one machine already yields a 2-approximation.
Similar results hold for the sum of completion times problem. As for the makespan problem, the leap in complexity requires that the number of scenarios is part of the input. However, I will give an example of a scheduling problem that is in P in its ordinary version and becomes NP-hard already for 3 scenarios.
We will complement these negative results with some special cases of the problems that can be solved efficiently, and an intriguing open question. The results in this lecture show the mysterious role that scenarios play in the complexity of combinatorial optimization problems.
This is based on work in collaboration with Thomas Bosman (Booking.com), Martijn van Ee (Marine Academy), Esteban Feuerstein (UBA), Alberto Marchetti-Spaccamela (LSUR), Frans Schalekamp (Cornell), Rene Sitters (VU/CWI), Suzanne van der Ster (Ahold), Anke van Zuylen (Cornell)