Session 3

In this talk, we focus on static robust optimization problems where the uncertainty set can be controlled through the actions of the decision maker known as decision-dependent uncertainty. Particularly, we consider an uncertainty reduction paradigm where the decision-maker can reduce upper bounds of uncertain parameters as a result of some proactive actions. This paradigm was recently proposed in the literature and the resulting problems were shown to be NP-Hard.  In this talk, we pay particular attention to the special case of robust combinatorial optimization problems, and show that they are also NP-Hard under the uncertainty reduction paradigm. Despite this discouraging result, we show that under some additional assumptions polynomial-time algorithms can be devised to solve robust combinatorial optimization problems with uncertainty reduction. We additionally provide insights into possible MILP reformulations in the general case and illustrate the practical relevance of our results on the shortest path instances from the literature.

Ayse N. Arslan is a junior researcher at Inria Center of Bordeaux. Her research interests lie at the intersection of mixed-integer programming and optimization under uncertainty with a particular focus on stochastic and robust optimization and their applications. Some of her recent work includes decomposition algorithms for solving two-stage robust optimization problems and primal and dual decision rules for approximating multi-stage robust optimization problems.

In this talk, we will present our new inexact column-and-constraint generation (i-C&CG) method for solving challenging two-stage robust and distributionally robust optimization problems. In our i-C&CG method, the master problems only need to be solved to a prescribed relative optimality gap or time limit, which may be the only tractable option when solving large-scale and/or challenging problems in practice. We equip i-C&CG with a backtracking routine that controls the trade-off between bound improvement and inexactness. Importantly, this routine allows us to derive theoretical finite convergence guarantees for our i-C&CG method, demonstrating that it converges to the exact optimal solution under some parameter settings. Numerical experiments on a scheduling problem and a facility location problem demonstrate the computational advantages of our i-C&CG method over a state-of-the-art C&CG method.

Dr. Karmel S. Shehadeh is an Assistant Professor in the Department of Industrial and Systems Engineering at Lehigh University. Before joining Lehigh, she was a presidential and dean postdoctoral fellow at Heinz College of Information Systems and Public Policy at Carnegie Mellon University. She holds a doctoral degree in Industrial and Operations Engineering from the University of Michigan, a master's degree in Systems Science and Industrial Engineering from Binghamton University, and a bachelor's in Biomedical Engineering from Jordan University of Science and Technology. Her research interests revolve around stochastic and robust optimization with applications to healthcare operations and analytics, facility location, transportation systems, and fair decision-making. Professional recognition of her work includes an INFORMS Minority Issues Forum Paper Award (winner), Junior Faculty Interest Group Paper Prize (finalist), Service Science Best Cluster Paper Award (finalist), and Lehigh's Alfred Noble Robinson Faculty Award.

In combinatorial optimization problems under budget uncertainty the solution space is deterministic, but the objective is uncertain. By the seminal work of Bertsimas & Sim (2003, 2004), such problems can be solved in various ways: by separating constraints bounding the objective, by a compact reformulation, or by solving n+1 deterministic problems of the same type. Although the complexity of the problem does not increase in theory, in many cases the performance deteriorates significantly. 

In this talk, we show two ways to enhance the computation times of the compact reformulation: (i) recycling valid inequalities known for the deterministic problem yielding surprisingly strong valid inequalities for the robust problem and (ii) a tailored branch and bound algorithm performing a tree search on one of the dual variables. This is joint work with Timo Gersing and Christina Büsing.

Arie M.C.A. Koster is since 2009 a Professor of Mathematics at RWTH Aachen University. Before, he received his PhD from Maastricht University and worked at Zuse Institute Berlin and University of Warwick. His research interests include integer linear programming, polyhedral combinatorics, robust optimization, algorithmic graph theory, and network optimization. He has published over 100 research papers and is on the editorial board of Annals of Operations Research, INFORMS Journal on Computing, and Networks.

We study inventory control with volume flexibility: A firm can replenish using period-dependent base capacity at regular sourcing costs and access additional supply at a premium. The optimal replenishment policy is characterized by two period-dependent base-stock levels but determining their values is not trivial, especially for nonstationary and correlated demand. We propose the Lookahead Peak-Shaving policy that anticipates and peak shaves orders from future peak-demand periods to the current period, thereby matching capacity and demand. Peak shaving anticipates future order peaks and partially shifts them forward. This contrasts with conventional smoothing, which recovers the inventory deficit resulting from demand peaks by increasing later orders. Our contribution is threefold. First, we use a novel iterative approach to prove the robust optimality of the Lookahead Peak-Shaving policy. Second, we provide explicit expressions of the period-dependent base-stock levels and analyze the amount of peak shaving. Finally, we demonstrate how our policy outperforms other heuristics in stochastic systems. Most cost savings occur when demand is nonstationary and negatively correlated, and base capacities fluctuate around the mean demand. Our insights apply to several practical settings, including production systems with overtime, sourcing from multiple capacitated suppliers, or transportation planning with a spot market. Applying our model to data from a manufacturer reduces inventory and sourcing costs by 6.7%, compared to the manufacturer's policy without peak shaving.

This is a joint work with Joren Gijsbrechts, Robert N. Boute, Jan A. Van Mieghem.

Christina Imdahl is Assistant Professor of Machine Learning in Operations Management at the OPAC group of Eindhoven University of Technology (TU/e). Christina's research is focuses on decision-making in operations management. She develops models that are motivated by operational practice and explores how we can leverage data to make better decisions. In her research, she combines the use of stochastic and robust optimization with empirical analyses to gain insights into performance.