Présidents de session
Mini-symposium: Communication-Efficient methods for distributed optimization and federated learning
- Laurent Condat (KAUST)
Mini-symposium: Advances in two-stages robust optimization
- Michael Poss (LIRMM, CNRS)
Mini-symposium: Robust Optimization and Machine Learning
- Aras Selvi (Imperial College London)
Mini-symposium: Models and Methods for Stochastic Non-Convex Optimization and Equilibrium Problems
- Miguel Lejeune (George Washington University)
Mini-symposium: Taming the Curse of Dimension in Multistage Stochastic Programming
- Yifan Hu (EPFL)
Mini-symposium: Student Prize
- Jim Luedtke (University of Wisconsin-Madison)
Mini-symposium: Contextual Stochastic Programming
- Utsav Sadana (Université de Montréal)
- Rohit Kannan (Virginia Tech)
Mini-symposium: Stochastic Mixed-Integer Programming
- Ward Romeijnders
Mini-symposium: Junior Researcher Prize
- Wim van Ackooij (EDF Lab Paris-Saclay)
Mini-symposium: Robust Decision Making in Dynamic Environments
- Mengmeng Li (EPFL)
Mini-symposium: Modeling flexibility: new developments
- Il n'a pas de président de session pour ce bloc
Mini-symposium: Computationally Efficient Approaches for Distributionally Robust Optimization
- JIANQIANG CHENG (University of Arizona)
Mini-symposium: Decomposition methods for solving Stochastic Programming problems in Logistics and Transportation
- Francesca Maggioni (Department of Management, Information and Production Engineering, University of Bergamo)
- Daniele Manerba (Università degli Studi di Brescia)
Mini-symposium: Stochastic Optimization under Decision-Dependent Uncertainty
- Giovanni Pantuso (University of Copenhagen)
Mini-symposium: Multihorizon Stochastic Programming: Models, Algorithms, and Applications
- Harsha Gangammanavar (Southern Methodist University)
Mini-symposium: Structured learning and stochastic combinatorial optimization: methodological perspectives and applications
- Axel Parmentier (CERMICS, École Nationale des Ponts et Chaussées)
In distributed optimization and machine learning, a large number of machines perform computations in parallel and communicate back and forth with a server. In particular, in federated learning, the distributed training process is run on personal devices such as mobile phones. In this context, communication, that can be slow, costly and unreliable, forms the main bottleneck. To reduce...
Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this talk, I present some connections between different types of robust problems (static robust problems with and without decision-dependence of their...
In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse.
These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG).
Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or...
We consider decentralized optimization over a network of $n$ workers, aiming to minimize
$$
f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x),
$$
where each $f_i$ is $\mu$-strongly convex and $L$-smooth. Most known convergence bounds rely on inner-outer loop structures that alternate synchronized gossip steps with (possibly randomized) local gradient updates, implicitly restricting the algorithm...
In the realm of robust optimization the k-adaptability approach is one promising method to derive approximate solutions for two-stage robust optimization problems with decisions. Instead of allowing all possible second-stage decisions, the k-adaptability approach aims at calculating a limited set of k such decisions already in the first-stage before the uncertainty reveals. The parameter k can...
- Abstract: In federated learning, multiple users collaboratively train a machine learning model without sharing local data. To reduce communication, users perform multiple local stochastic gradient steps that are then aggregated by a central server. However, due to data heterogeneity, local training introduces bias. In this talk, I will present a novel interpretation of the Federated...
We analyze a distributed algorithm to compute a low-rank matrix factorization on $N$ clients, each holding a local dataset $\mathbf{S}^i \in \mathbb{R}^{n_i \times d}$, mathematically, we seek to solve $min_{\mathbf{U}^i \in \mathbb{R}^{n_i\times r}, \mathbf{V}\in \mathbb{R}^{d \times r} } \frac{1}{2} \sum_{i=1}^N \|\mathbf{S}^i - \mathbf{U}^i \mathbf{V}^\top\|^2_{\text{F}}$. Considering a...
Two-stage robust optimization with integer recourse is a notoriously difficult class of problems, yet modelling many important applications. In this we talk, we discuss how to heuristically solve these problems, solving the adversarial problem and the outer minimization problem through local search algorithms. We focus on the case where all decision variables as well as the uncertainty are...
Robust optimization is a tractable and expressive technique for decision-making under uncertainty, but it can lead to overly conservative decisions when pessimistic assumptions are made on the uncertain parameters. Wasserstein distributionally robust optimization can reduce conservatism by being data-driven, but it often leads to large problems with prohibitive solution times. In this talk, we...
We present both the DC algorithm as well as several examples in chance-
constrained programming as well as other deterministic applications to showcase the
applicability and success of this new approach. In particular this approach has been successfully applied to solving many deterministic and stochastic mixed complementarity problems (MCPs). MCPs generalize non-cooperative games, the...
We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated L-shaped ($L^2$) methods, which guarantee exact solutions when the first-stage decisions are...
In this talk we investigate the tractability of robust Markov Decision Processes (RMDPs) under various structural assumptions on the uncertainty set. Surprisingly, we show that in all generality (i.e. without any assumption on the instantaneous rewards), s-rectangular and sa-rectangular uncertainty sets are the only models of uncertainty that are tractable. Our analysis also shows that...
In electricity systems, investment in generation capacity is subject to risk. The distribution of uncertain parameters on which investment decisions depend might not be fully observed in historical values. In Europe, this was recently illustrated by the crisis of exceptionally high power prices during the 2021-2023 period, which was subsequently followed by a regime of extremely low and even...
The main goal of this talk is to discuss several approaches to formulation of distributionally robust counterparts of Markov decision processes, where the transition kernels are not specified exactly but rather are assumed to be elements of the corresponding ambiguity sets. The intent is to clarify some connections between the game and static formulations of distributionally robust MDPs, and...
We study a two-player discounted zero-sum stochastic game model for dynamic operational planning in military campaigns. At each stage, the players manage multiple commanders who order military actions on objectives that have an open line of control. When a battle over the control of an objective occurs, its stochastic outcome depends on the actions and the enabling support provided by the...
Motivated by a housing allocation problem faced by our public-sector partner, the Los Angeles Homeless Services Authority (LAHSA), we study sequential resource allocation in high-stakes social settings, where fairness is critical. Each month, we must allocate limited housing capacity among individuals experiencing homelessness. We model this as a Markov Decision Process (MDP), where...
We introduce contextual stochastic bilevel optimization (CSBO) - a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on contextual information and on the upper-level decision variable. We also assume that there may be multiple (or even infinitely many) followers at the lower level. CSBO encapsulates important applications such as...
Real-world decision-making problems often involve decision-dependent uncertainty, where the probability distribution of the random vector depends on the model's decisions. Few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We propose a general method for solving a class of these programs based on random...
AChance constraints yield nonconvex feasible regions in general. In particular, when the uncertain parameters are modeled by a Wasserstein ball, existing studies showed that the distributionally robust (pessimistic) chance constraint admits a mixed-integer conic representation. This talk identifies sufficient conditions that lead to convex feasible regions of chance constraints with...
Algorithms for solving Multistage Stochastic Programming (MSP) are long known to suffer from the curse of dimension and horizon. Stochastic Dual Dynamic Programming (SDDP) for stage-wise independence MSP problem admits a complexity of scales exponentially with respect to the decision dimension $d$ in terms of accuracy $\epsilon$, i.e., $O(\epsilon^{-d})$. On the other hand, Stochastic...
We study offline reinforcement learning problems with a long-run average reward objective. The state-action pairs generated by any fixed behavioral policy thus follow a Markov chain, and the empirical state-action-next-state distribution satisfies a large deviations principle. We use the rate function of this large deviations principle to construct an uncertainty set for the unknown true...
We introduce Multilevel Conditional Compositional Optimization (MCCO) as a new framework for decision-making under uncertainty that combines aspects of multistage stochastic programming and conditional stochastic optimization. MCCO minimizes a nest of conditional expectations and nonlinear cost functions. It finds wide applications in optimal stopping, credit valuation adjustments,...
We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match...
Recent advances in operations research (OR) and machine learning (ML) have spurred interest in integrating prediction algorithms with optimization techniques to address decision-making under uncertainty. This has led to the emergence of contextual optimization, a field focused on data-driven methods that prescribe actions based on the most recently available information. These models appear in...
Multistage stochastic mixed-integer programs (MSMIPs) can model complex sequential decision-making problems under uncertainty and appear in many applications. However, due to both the stochastic and integer components, their inherent computational challenges require sophisticated solution methodologies. In this talk, we will review recent advances in solving MSMIPs, in particular for the...
We study stochastic mixed integer programs with both first-stage and recourse decisions involving mixed integer variables. A new family of Lagrangian cuts, termed “ReLU Lagrangian cuts,” is introduced by reformulating the nonanticipativity constraints using ReLU functions. These cuts can be integrated into scenario decomposition methods. We show that including ReLU Lagrangian cuts is...
A fundamental problem in the contextual optimization setting is to evaluate and compare the objective performances of data-driven decision rules. In this regard, we analyze the construction of interval estimates on these performances, as an approach to produce reliable evaluation that handles the underlying statistical uncertainty. Specifically, we systematically compare common plug-in and...
This work proposes a globally converging cutting-plane algorithm for solving stochastic mixed-integer programs (SMIP) with general mixed-integer state variables. We show that Lagrangian cuts can approximate the convex envelope of the value function. To approximate the nonconvex value function to exactness, we need to iteratively add binary state variables and generate Lagrangian cuts on the...
This paper revisits the theory of \textit{exact regularization} – where optimal solutions of a regularized convex optimization problem exhibit a phase transition phenomenon and eventually coincide with those of the original unregularized problem (under certain conditions).We examine this phenomenon from a norm-free perspective – instead of adopting norm-related assumptions, our results are...
We consider multistage stochastic mixed-integer programs. These problems are extremely challenging to solve since the expected cost-to-go functions in these problems are typically non-convex due to the integer decision variables involved. This means that efficient decomposition methods using tools from convex approximations cannot be applied to this problem. For this reason, we construct...
Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. We introduce a new approach for solving computationally-demanding stochastic optimal stopping problems with known probability distributions. The approach uses simulation to construct a robust optimization problem that approximates the stochastic...
Over the past two decades, robust optimization techniques have efficiently addressed decision problems under uncertainty, offering high assurance of feasibility without being overly conservative. However, research on estimating parameters for robust decision models from data is relatively scarce. In this paper, we focus on a unified framework for robust decision models that integrate robust...
Much of the stochastic programming literature is on mathematics or algorithms, some is on principal models. But very few are on real use of the models. I discuss the problems that arise when trying to really use stochastic programming, and where I think we are (or should be) headed.
Time Series Foundation Models, like ChatGPT for language, are trained on vast amounts of curated time series data and can produce a sequence of high-quality predictions from a single input sequence. Can we apply Time Series Foundation Models to the challenge of generating multistage scenario trees?
This talk explores a method based on Doob's observation that every discrete-time stochastic...
We study offline reinforcement learning problems with a long-run average reward objective. The state-action pairs generated by any fixed behavioral policy thus follow a Markov chain, and the empirical state-action-next-state distribution satisfies a large deviations principle. We use the rate function of this large deviations principle to construct an uncertainty set for the unknown true...
Flexibility is a critical attribute in solving stochastic programming problems, where decision-making must account for uncertainty and adapt to a wide range of potential future scenarios. Stochastic programming is a practical approach in which decisions are determined prior to the realization of uncertain variables, with subsequent adjustments made through recourse mechanisms once the...
Stochastic optimal control with unknown randomness distributions has been studied for a long time, encompassing robust control, distributionally robust control, and adaptive control. We propose a new episodic Bayesian approach that incorporates Bayesian learning with optimal control. In each episode, the approach learns the randomness distribution with a Bayesian posterior and subsequently...
We present a data-driven technique to automatically learn uncertainty sets in dynamic decision making under uncertainty. We formulate the learning problem as a control design problem where the control policy involves solving a robust optimization problem parametrized by the past disturbances, as well as the parameters of the uncertainty set. We propose a learning procedure to dynamically...
This talk focus on developing computationally efficient approximations for solving optimization problem under uncertainty. We first present a novel and simple modeling method called harmonizing optimization (HO), which integrates SAA and DRO with moment by adaptively adjusting the weights of data and information based on sample size N. This allows HO to amplify data effects in large samples...
In this talk we provide an introduction to stochastic optimization problems with decision-dependent uncertainty.
We review the main lines of research in terms of both methodology and applications.
Our discussion will center on a taxonomy of these problems, distinguishing between uncertainties that affect probabilities (Type 1) and those that influence resolution time (Type 2)....
Freight transportation is one of the critical enablers of trade, both global and domestic. Given that, it regularly constitutes significant portions of the gross domestic product of countries. Due to its large scale, small percentage improvements in the efficiency of freight transportation operations can lead to large monetary savings as well as reduced environmental impacts. At the same time,...
We study distributionally robust chance-constrained optimization problems under decision-dependent uncertainty. The focus is on decision-dependent uncertainty of Type 1 in which the support of the random variables is decision-dependent. We study various types of coupling functions and ambiguity. We derive computationally tractable equivalent reformulations and design customized solution...
A consolidated business model for managing e-commerce logistics involves the combination of forward-and-reverse operations, where the collection of returns is ensured along with the distribution of products, and the use of hub-and-spoke networks, in which both distribution and collection demand from many customers are aggregated into intermediate hubs. In this context, we study a complex...
We revisit the value of stochastic solutions (VSS) in adaptive stochastic optimization. Given a fixed decision, VSS evaluates its suboptimality in contrast to an optimal solution with knowledge of the underlying probability distribution. For example, for a decision given by the sample average approximation (SAA), VSS interprets the value of collecting more data for better decision-making. When...
In this study, we examine the optimization of fleet size and mix, together with vehicle routing, under uncertain demand conditions, with explicit consideration of sustainability aspects in the context of Last Mile logistics. We propose a two-stage bi-objective stochastic mixed-integer programming model that simultaneously minimizes total costs and vehicle emissions associated with delivery...
We consider a two-stage distributionally robust optimization (DRO) model with multimodal uncertainty, where both the mode probabilities and uncertainty distributions could be affected by the first-stage decisions. To address this setting, we propose a generic framework by introducing a ϕ-divergence based ambiguity set to characterize the decision-dependent mode probabilities and further...
We consider a residuals-based distributionally robust optimization model, where the underlying uncertainty depends on both covariate information and our decisions. We adopt regression models to learn the latent decision dependency and construct a nominal distribution (thereby ambiguity sets) around the learned model using empirical residuals from the regressions. Ambiguity sets can be formed...
In uncertain optimization problems with decision-dependent information discovery, the decision-maker can influence when information is revealed, unlike the classic setting where uncertain parameters are revealed according to a prescribed filtration. This work examines two-stage robust optimization problems with decision-dependent information discovery, focusing on uncertainty in the objective...
The problem of pricing mobility services has attracted significant attention. In most studies, uncertain demand is modeled as an exogenous random variable with known distribution. This assumption overlooks the likely effect of prices on user adoption decisions. To address this dependency, we formulate the pricing problem as a stochastic program with decision-dependent demand uncertainty....
In this talk, we will bridge the gap between combinatorial optimization and machine learning to derive policies for contextual multi-stage decision-making problems that arise in various stochastic settings, including transportation, control, and supply chain management. We will discuss how to encode effective policies by embedding combinatorial optimization layers into neural networks and...
This presentation addresses stochastic optimization models for the energy transition, focusing on multiscale multihorizon systems. We model both long-term investment decisions—such as renewable generation, carbon capture, and decarbonized transport—and short-term operations like storage management and system balancing. To handle uncertainty across both scales, we introduce multihorizon...
We show how to implement long-term storage in the multi-horizon modelling paradigm, expanding the range of problems this approach is applicable to. The presented implementation is based on the HyOpt optimization model, but the ideas are generic.
We illustrate the effects of several formulations on a simple case of electrification of an offshore installation using wind turbines and a...
In this talk we address the challenge of designing optimal domestic renewable energy systems under multiple sources of uncertainty appearing at different time scales. Long-term uncertainties, such as investment and maintenance costs of different technologies, are combined with short-term uncertainties, including solar radiation, electricity prices, and uncontrolled load variations.
We...
As industry seeks to make its processes more resilient, data driven optimization is gaining momentum in Operation Research. Resilience involves managing uncertainty when optimizing supply chains, while efficiency requires scalable combinatorial optimization algorithms, as most gains from operations research algorithms come from decreasing marginal costs. This underscores the need for scalable...
This paper proposes a novel algorithm to efficiently solve large-scale multi-stage stochastic programs with block separable recourse. We use an extended Benders decomposition with adaptive oracles to decompose the problem into a master problem and a collection of subproblems. The adaptive oracles enable cut sharing among the subproblems. We apply the proposed method for solving power system...
We propose a data-driven framework for multistage stochastic optimization using only a single historical trajectory of the underlying process. Given recent observations of the stochastic process, the goal is to find a policy that minimizes expected cost over the next T time periods. Our approach fits a time-series model to the data and uses its residuals to construct a discrete approximation...
We study a multidimensional mechanism design problem where a seller offers multiple products to a single buyer. The seller possesses only marginal distributional information about the buyer's random valuation of each product. The buyer is not a perfect optimizer and is satisficing whenever his incentive is epsilon away from the optimal---a notion called approximate incentive compatibility...
