Solving Optimization Problems with Complicating Variables
摘要
This chapter explores problems with complicating variables that can be solved using Benders decomposition. Complicating variables are variables that, if fixed, allow breaking the original problem into smaller and generally easier-to-solve problems. We first introduce the structure of such problems and provide real-world engineering examples and their general structure. This chapter also covers various aspects of Benders decomposition, such as its motivation, its building blocks, and conditions for convergence guarantees. This chapter also illustrates the application of Benders decomposition to solve mixed-integer problems and two-stage stochastic problems. We also discuss strategies to accelerate Benders decomposition such as using single-cut and multi-cut approaches, integrating valid constraints, and improving the master problem by incorporating primal information. Illustrative and realistic examples are provided to demonstrate the application of Benders decomposition.