Title: Perspectives on Using Benders Decomposition to Solve Two-Stage Stochastic Mixed-Integer Programs

Abstract: Benders decomposition has shown great potential as an efficient method for solving two-stage stochastic integer programs. As originally proposed, these programs are decomposed by partitioning the decision variables into two groups: the first-stage decisions, which define a master problem, and the second-stage decisions, which define a set of subproblems. An optimal solution is then obtained by successively solving the master and subproblems until the master’s solution can be certified as optimal, with the subproblems used to generate violated cuts that strengthen the master’s formulation. Although this decomposition strategy has produced successful results, recent studies suggest that the partitioning choices underlying the decomposition deserve to be revisited. Specifically, the Benders method can be significantly enhanced and accelerated by transferring information from the subproblems to the master, thereby strengthening the master’s formulation, or by sending information in the opposite direction, from the master to the subproblems, to improve the quality of the generated cuts. In this talk, I will highlight these new strategies for partitioning decision variables and discuss how to effectively implement these enhancements within the Benders framework. These ideas will be illustrated with numerical results on stochastic network design problems, demonstrating the practical impact of these methodological advances.

Short bio: Walter Rei is a Professor of Operations Research in the Department of Analytics, Operations, and Information Technologies at the École des Sciences de la Gestion, Université du Québec à Montréal, Canada. He currently holds the Canada Research Chair in Stochastic Optimization of Transport and Logistics Systems and is also a member of the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT). His research focuses on the development of efficient solution methodologies for integer programs and combinatorial optimization models relevant to transportation and logistics problems involving uncertainty. 

Title: Inbound Truck Scheduling with Estimated Times of Arrival  

Abstract: We address the problem of dynamically scheduling inbound trucks at a warehouse with known service times and uncertain arrival times. Truck arrival time distributions are hidden. However, we approximate them via estimated times of arrival (ETAs). The objective is to minimize the total expected waiting time. We use information relaxations and an information penalty to develop a dual bound on the cost of an optimal policy. A series of theoretical analyses establishes the dual problem and then transforms it from a stochastic dynamic program to a compact mixed integer linear program. On average, the penalized dual bound is nearly 10 percent stronger than a bound based on perfect information. We propose a lookahead policy that uses ETAs to adapt decisions to new information. When the dispatcher can fully observe truck arrival time distributions, the gap between the policy value and the dual bound is less than one percent. This result suggests that when distributions are hidden, the larger duality gap of about 10 percent we find is due primarily to partial observability and that the policy makes good decisions. Relative to industry practice, the lookahead policy decreases expected waiting time by 29 percent, on average. Further, the lookahead policy selects actions quickly enough to be used in practice.

Short bio: Ola Jabali is an associate professor at the operations research and discrete optimization group at Politecnico di Milano. Her research interests focus on modeling and solving realistic problems arising in transportation, production, and logistics. She is an affiliated professor at HEC Montréal, Canada. She obtained her MSc in industrial engineering from the Technion in 2006 and her PhD in the same field in 2010 from the Eindhoven University of Technology. From 2012 to 2016, she was an assistant professor at the Department of Logistics and Operations Management at HEC Montréal. In 2016, she obtained the “Rita Levi Montalcini” fellowship for young researchers by the Italian Ministry of Education, Universities and Research. In 2023, she received the Stella Dafermos Mid-Career Award by the Transportation Science and Logistics Society of INFORMS. She is associate editor for INFOR: Information Systems and Operational Research, Transportation Research Part C: Emerging Technologies, and Transportation Science.