Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs

2019/06/14 by Huiwen Jia, Jia, Huiwen, Siqian Shen +1 · 4 citations
Business, Management and Accounting · Decision Sciences · Mathematics · #FOS: Mathematics #Fuzzy Systems and Optimization #Multi-Criteria Decision Making #Optimization and Control (math.OC) #Supply Chain and Inventory Management #math.OC

paper · pdf · doi:10.48550/arxiv.1906.05994

openalex publication_date 2019/06/14 · arxiv created 2020/10/15 · arxiv updated 2020/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification step in each iteration to selectively generate cuts that are more likely to be valuable cuts. The LearnBD algorithm includes two phases: (i) sampling cuts and collecting information from training problems and (ii) solving testing problems with a support vector machine (SVM) cut classifier. We run the LearnBD algorithm on instances of capacitated facility location and multi-commodity network design under uncertain demand. Our results show that SVM cut classifier works effectively for identifying valuable cuts, and the LearnBD algorithm reduces the total solving time of all instances for different problems with various sizes and complexities.

Citations

• A tutorial on support vector regression
• Partitioning procedures for solving mixed-variables programming problems
• An overview of statistical learning theory
• Planning and Scheduling by Logic-Based Benders Decomposition
• Learning Combinatorial Optimization Algorithms over Graphs
• A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning
• SQIL: Imitation Learning via Reinforcement Learning with Sparse Rewards

Cited by

• Graph-Based Imitation and Reinforcement Learning for Efficient Benders Decomposition
• Learning to control inexact Benders decomposition via reinforcement learning
• Benders Decomposition using Graph Modeling and Multi-Parametric Programming
• Disjunctive Benders Decomposition

Related

• Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs
• Accelerating L-shaped Two-stage Stochastic SCUC with Learning Integrated Benders Decomposition
• Deepest Cuts for Benders Decomposition
• Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction
• Adaptive Benders decomposition and enhanced SDDP for multistage stochastic programs with block-separable multistage recourse