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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Optimization Problems with Complicating Variables

  • Gonzalo E. Constante-Flores,
  • Antonio J. Conejo

摘要

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.