結合 Benders Decomposition 與 Pure Cutting Plane 方法求解兩階段隨機整數規劃

Integrating Benders Decomposition and Pure Cutting Plane Method for Solving Stochastic Integer Program

饒承毓(Cheng-Yu Rao)

指導教授 ： 陳勝一

國立交通大學/管理學院/工業工程與管理系所/碩士(2019年)

摘要

Benders Decomposition 廣泛用於求解大型數學規劃問題，在應用方面，求解隨機規劃問題的方法稱為 L-Shaped 方法，透過演算法在每次迭代中，不斷更新問題解的邊界，最終求得最佳解，目前已有不少文獻指出該方法在求解大型隨機規劃問題表現優異，而Benders Decomposition 無法直接用於求解包含不確定且非連續變數之隨機規劃問題，本研究針對兩階段隨機整數規劃問題，且各階段問題皆為整數規劃，研究方法延伸Benders Decomposition，並結合Pure Cutting Plane 方法求解問題，於子問題中加入有效不等式，收斂線性放鬆解，以提供主問題更緊縮邊界，提升演算法整體效能與求解品質。本研究實作所提出之方法論，實驗分析針對一般數學規劃軟體無法直接求解之大型隨機整數規劃問題，結果證實本研究所提出的方法可用於求解測試問題集，並於合理時限內可以得到高品質之近似解。

關鍵字

兩階段隨機整數規劃 ； Benders Decomposition ； Gomory cutting plane

並列摘要

Benders decomposition is a commonly-used approach for solving large-scale mathematical programming problem. The application in stochastic programming is known as L-shaped method proposed for solving two-stage stochastic programs by taking advantage of its specific structure. The algorithm utilizes the parametric lower bound of second-stage objective value to obtain the optimal solution iteratively. However, the approach fails to generate the lower bound for the integer recourse problem and it may not converge to optimal due to the relaxation solution provides a week lower bound. This study focuses on a general case of two-stage stochastic programs, in which decision variables in both stages are integers. We integrate the L-shaped method and Gomory cutting plane to obtain an approximate solution. A finite cutting plane method is posted to the second-stage problem to strengthen the lower bound for the recourse cost function. The result demonstrates that the proposed method is capable to obtain a high quality solution for problem instances whose extensive forms are unsolvable by merely using the conventional branch-and-cut method. We perform a computational analysis and suggest the best cutting plane strategy used in the proposed algorithm.

並列關鍵字

Two-stage stochastic integer programs ； Benders decomposition ； Gomory cutting plane

參考文獻

[1] Adulyasak, Y., Cordeau, J. F., & Jans, R. (2015). Benders decomposition for production

routing under demand uncertainty. Operations Research, 63(4), 851-867.

[2] Angulo, G., Ahmed, S., & Dey, S. S. (2016). Improving the integer L-shaped method.

INFORMS Journal on Computing, 28(3), 483-499.

[3] Balas, E., Ceria, S., Cornuéjols, G., & Natraj, N. (1996). Gomory cuts revisited.