Logic-Based Benders Decomposition

This book is the first comprehensive guide to logic-based Benders decomposition (LBBD), a general and versatile method for breaking large, complex optimization problems into components that are small enough for practical solution. The author introduces logic-based Benders decomposition for optimization, which substantially generalizes the classical Benders method. It can reduce solution times by orders of magnitude and allows decomposition to be applied to a much wider variety of optimization problems. On the theoretical side, this book provides a full account of inference duality concepts that underlie LBBD, as well as a description of how LBBD can be combined with stochastic and robust optimization, heuristic methods, and decision diagrams. It also clarifies the connection between LBBD and combinatorial Benders cuts for mixed integer programming. On the practical side, it explains how LBBD has been applied to a rapidly growingvariety of problem domains. After describing basic theory, this book provides a comprehensive review of the rapidly growing literature that describes these applications, in each case explaining how LBBD is adapted to the problem at hand. In doing so this work provides a sourcebook of ideas for applying LBBD to new problems as they arise.

Introduces logic-based Benders decomposition (LBBD) for optimization, which substantially generalizes the classical Benders method Provides a concise and accessible exposition of all the relevant concepts, including inference duality, branch-and-check methods, and application to two-stage stochastic and robust optimization models Explains how LBBD can be combined with stochastic and robust optimization, heuristic methods, and decision diagrams

Autorentext

Özgün Elçi, Ph.D., is a Research Scientist on the Modeling and Optimization team at Amazon. He has a Ph.D. in Operations Research from Tepper School of Business at Carnegie Mellon University. During his doctoral studies, he worked on applying logic-based Benders decomposition to stochastic scheduling problems. He also worked on robust portfolio optimization and fair allocation of resources. Prior to that, he focused on humanitarian relief network design problems under uncertainty. His current research interests include solving large-scale network design problems that arise in industry via decomposition-based exact methods. John Hooker, Ph.D. is University Professor of Operations Research and T. Jerome Holleran Professor of Business Ethics and Social Responsibility, Emeritus, at Carnegie Mellon University. He holds doctoral degrees in philosophy and operations research. He has published 200+ articles, 10 books, and six edited volumes in operations research, constraint programming, ethics, the mathematical analysis of fairness, cross-cultural management, and music theory. He is a Fellow of the Institute for Operations Research and the Management Sciences (INFORMS), as well as recipient the INFORMS Computing Society Prize, the INFORMS Khachiyan Award for lifetime achievements in optimization, the Research Excellence Award of the Association for Constraint Programming, and several best paper awards. He is a pioneer in the integration of optimization and constraint programming technologies, now a feature of leading optimization solvers. He developed a substantial generalization of Benders decomposition that has seen hundreds of practical applications. In addition, he and Tarik Hadi introduced an approach to optimization based on decision diagrams. Presently, his main research area is the mathematical analysis of fairness. His ethics-related books include Business Ethics as Rational Choice, Working across Cultures, Taking Ethics Seriously, Advanced Introduction to Business Ethics, and Toward Systematic Normative Ethics (forthcoming). He served as founding editor-in-chief of the Journal of Business Ethics Education, the only academic journal dedicated to the topic. Peter Zhang, Ph.D, is an Assistant Professor at Carnegie Mellon University’s Heinz College of Information Systems and Public Policy. His research interests include robust and stochastic optimization theory, with applications in supply chain and transportation. He obtained Ph.D. from MIT in Engineering Systems and BASc and MASc from the University of Toronto. His Ph.D. thesis contributed to the identification of vulnerabilities in supply chain networks and robust supply chain network design methods. Some concepts that Peter worked on and developed at MIT (time-to-recover, supply chain stress test, and robust supply chains) have been cited in various media outlets, academic journals, and White House reports. He has received multiple paper competition awards in academic and applied research areas at INFORMS and POM conferences.

Inhalt
Introduction.- Inference Duality.- The Basic Logic-based Benders Method.- Classical Benders Decomposition.- Combinatorial Benders Cuts.- Stochastic and Robust Optimization.- LBBD and Decision Diagrams.- LBBD and Heuristic Methods.- Task Assignment and Scheduling.- .Vehicle Routing.- Shop, Factory, and Employee Scheduling.- Other Scheduling and Logistics Problems; Health-related Applications.- Network Design.- Other Applications. <p