From Multi-Parametric Linear Optimization to K-Adaptability in Mixed-Integer Stochastic Problems
Abstract:
Many optimization problems solved repeatedly in practice—such as in power systems or logistics—share a fixed structure but involve parameters that vary over time. Re-optimizing each instance from scratch can be computationally prohibitive, and computing the full mapping from parameters to optimal solutions is generally intractable.
In this talk, I will first focus on the simplest setting of multi-parametric linear optimization with parametric coefficients in the objective function, and I will discuss polyhedral structures under which we can bound the number of solutions that are optimal for some parameter realization.
Next, I will consider more complex parametric optimization problems with a mixed-integer feasible set. Classic approaches from robust and stochastic optimization compute a single solution to be adopted for all realizations, which is often overly conservative. Recently, a more flexible paradigm known as K-adaptability has emerged. We introduce a new model for K-adaptability in mixed-integer optimization that precomputes K candidate assignments for the discrete variables while retaining continuous recourse decisions optimized online after uncertainty is observed.
We propose two solution approaches: a scenario-based heuristic inspired by scenario decomposition, and an exact column-generation method that dynamically generates promising candidates through pricing subproblems. Preliminary computational results on optimal transmission switching and stochastic capacitated facility location show that our approach preserves computational tractability and substantially improves solution adaptability.
Biography: Carla Michini is an assistant professor in the Industrial and Systems Engineering Department at UW–Madison since Fall 2018. She previously held postdoctoral positions at UW–Madison and ETH Zürich and was a visiting researcher at CMU. She obtained her PhD in Operations Research from Sapienza University of Rome. Carla’s research is motivated by the practical relevance of combinatorial optimization and integer programming in real-world problems. Her approach focuses on identifying and exploiting the polyhedral structure of combinatorial problems to design efficient algorithms. She is the recipient of an NSF CAREER Award, which supports her ongoing research on applying combinatorial optimization and integer programming tools to problems in game theory.