Plenary Talks

Uncertainty poses a significant challenge on scheduling and planning tasks, where jobs may have unknown processing times or machines run at unknown speeds. However, assuming a complete lack of a priori information is overly pessimistic. With the rise of machine-learning methods and data-driven applications, access to predictions about input data or algorithmic actions becomes feasible. Yet, blindly trusting these predictions might lead to very poor solutions, due to the absence of quality guarantees.

In this talk, we explore recent advancements in the popular framework of Algorithms with Predictions, which integrates such error-prone predictions into online algorithm design. We examine various prediction models and error measures, showcasing learning-augmented algorithms for non-clairvoyant scheduling with strong error-dependent performance guarantees. We demonstrate the potential of imperfect predictions to enhance scheduling efficiency and address uncertainty in real-world scenarios.

Nicole Megow studied Mathematics and Business Administration at TU Berlin and the Massachusetts Institute of Technology, USA. She received her PhD in Mathematics from TU Berlin in 2006. She was postdoc and senior researcher at the Max Planck Institute for Informatics, Saarbrücken, held a position as interim professor for Discrete Optimization at TU Darmstadt 2011/12, and headed an Emmy Noether Research Group at TU Berlin starting in 2012. Subsequently, she was an assistant professor for Discrete Mathematics at TU Munich. Since 2016 she holds the Chair for Combinatorial Optimization in the Faculty of Mathematics and Computer Science at the University of Bremen.

Nicole Megow’s research interests lie at the intersection of discrete mathematics, theoretical computer science, and operations research. In particular, she works on the design and analysis of efficient algorithms for combinatorial optimization problems. Her research is focused on understanding how to cope with incomplete or imperfect information (uncertainty of problem data, complete lack of knowledge, untrusted predictions) when solving such problems. She contributes with theoretic results and applies them to complex real-world environments. Typical applications include scheduling, production planning, logistics, network design, communication and routing in networks, and health care. Her research has won several awards, including the Heinz Maier-Leibnitz Prize in 2013.

We propose a novel exact algorithm for the transportation problem, one of the paradigmatic network optimization problems. The algorithm, denoted Iterated Inside Out, requires in input a basic feasible solution and is composed by two main phases that are iteratively repeated until an optimal basic feasible solution is computed. In the first “inside” phase, the algorithm progressively improves upon a given basic solution by increasing the value of several non-basic variables with negative reduced cost. This phase typically outputs a non-basic feasible solution interior to the constraint set polytope. The second “out” phase moves in the opposite direction by iteratively setting to zero several variables until a new improved basic feasible solution is reached. Extensive computational tests show that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in commercial solvers such as Cplex and Gurobi and other exact algorithms available in the literature.

Learn more: https://arxiv.org/abs/2302.10826

Federico Della Croce holds a MS in Computer Science and Automation (1990) and a PhD in Operations Research (1993) from Politecnico di Torino, Italy. Since 2011, he is Full Professor of Operations Research at Politecnico di Torino where he served as Head of the Department of Control and Computer Engineering from 2012 to 2015 and as Vice-Head of the Department of Management and Production Engineering from 2018 to 2019. His main research interests concern exact, heuristic and approximation algorithms for combinatorial optimization problems, with emphasis on graphs and scheduling problems. He has published more than 90 papers in international journals such as COR, DAM, EJOR, IJOC, JOS, MathProg, OpRes and TCS among others. He is a member of the Editorial Board of COR and EJOR.

Hexaly Optimizer, formerly known as LocalSolver, is a "model and run" mathematical optimization solver based on various exact and heuristic methods. This presentation will introduce the different components of Hexaly Optimizer through scheduling problems, from the user model to the algorithms enabling it to find quality solutions and lower bounds. We will first show how its modeling formalism can be used to express various academic and industrial scheduling problems using only generic operators. These models are based on interval and list decision variables and have the advantage of being very compact, which enables the solver to handle even large-scale problems. We will then give an overview of the primal and dual techniques Hexaly Optimizer uses to solve such problems: local search reinforced with a solution repair algorithm based on constraint propagation to find quality solutions, and energetic and single-machine relaxations to find quality lower bounds.

Julien Darlay

Julien Darlay received a PhD in Computer Science from Grenoble University (2011). His research was at the intersection of mathematical optimization and machine learning. He was distinguished in several international OR competitions: 2nd Junior Prize of ROADEF 2009 Challenge, 3rd Senior Prize of ROADEF 2010 Challenge, Kaggle Santa’s Stolen Sleigh 2015 Challenge.

Léa Blaise

Léa Blaise holds a PhD in Computer Science from the University of Toulouse, France, under the supervision of Christian Artigues and Thierry Benoist. Her area of research is in combinatorial optimization and, more specifically, the resolution of scheduling problems using a combination of heuristic search and fast constraint propagation techniques. Since then, Léa has been working as an Optimization Scientist at Hexaly, where she leverages her expertise to develop new modeling formalisms and resolution techniques within Hexaly Optimizer. She is also involved in several industrial projects in the field of production scheduling.