Warm-start cuts for generalized Benders decomposition. (English) Zbl 1449.90267

Kůdela, Jakub; Popela, Pavel

Kybernetika 53, No. 6, 1012-1025 (2017).

Summary: In this paper, we describe a decomposition algorithm suitable for two-stage convex stochastic programs known as Generalized Benders Decomposition. For this algorithm we propose a new reformulation that incorporates a lower bound cut that serves as a warm-start, decreasing the overall computation time. Additionally, we test the performance of the proposed reformulation on two modifications of the algorithm (bunching and multicut) using numerical examples. The numerical part is programmed in MATLAB and uses state-of-the-art conic solvers.

MSC:

90C15	Stochastic programming
90C25	Convex programming
49M27	Decomposition methods

Keywords:

stochastic programming; generalized Benders decomposition; \(L\)-shaped method; warm-start

Software:

CVX; fmincon; Matlab; SeDuMi; SDPT3