跳到主要內容

臺灣博碩士論文加值系統

(44.211.239.1) 您好!臺灣時間:2023/02/05 23:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉軼倫
研究生(外文):Liu, Yi-Lun
論文名稱:結構式估計之大型混整數模型於班德氏基底切割生成規畫之應用與數值實驗
論文名稱(外文):The application of Benders-based cut generation program to a large-scale mixed-integer model of structural estimation with numerical experiments
指導教授:李雨青李雨青引用關係
指導教授(外文):Lee, Yu-Ching
口試委員:陳柏安郭佳瑋
口試委員(外文):Chen, Po-AnKuo, Chia-Wei
口試日期:2020-07-09
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:50
中文關鍵詞:純特徵模型大型混整數規劃班德氏分解法切割生成規劃
外文關鍵詞:pure characteristic modellarge-scale mixed-integer programBenders Decompositioncut generation program
相關次數:
  • 被引用被引用:0
  • 點閱點閱:74
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文將2001年至2015年英國汽車市場的銷售情況,結合純特徵模型(pure characteristic model),並且配合事前所蒐集的正規化資料,將其模擬成一大型混整數規劃問題。由於此模型具有大量二元變數(binary variable),因此在使用班德氏分解法(Benders Decomposition)對於該模型求解的情況下,我們試圖使用切割生成規劃(cut generation program)克服含有二元變數的子問題難以轉成對偶的困難點。過程中包含鬆弛變數(slack variable)的引入,放鬆(relaxation)、對偶轉換、互補差額性質等等,除此之外,利用變數代換以及額外限制式導入的技巧,我們可以將原本為非線性的切割生成規劃轉為線性,使求解該模型的難度大為降低。而在實際資料的數值實驗後也發現,在我們的原模型維度到達(N, J, K) = (34, 32, 32)以上後,透過求解我們的演算法之效率會開始比直接求解原模型來得好,而加快的比例逐漸上升,當維度為(N, J, K) = (99, 97, 32)時甚至來到大約10倍快,並且在RMSE上也有好的表現,此外該演算法也適用於生成資料。我們也冀望往後可以在該演算法上做進階的調整,例如限制式的分配、雙線性項(bilinear term)的處理等,來使更複雜的模型可以有更加有效率的求解方式。
In this thesis, the sales of automobile in British from 2001 to 2015 is studied. By combining pure characteristics model and normalized data, we can formulate a large-scale mixed-integer program. Since this model contains a large number of binary variables, we try to use cut generation program to overcome the difficulty of dual-transformation of a sub-problem with binary variables while using Benders Decomposition to solve the model. The process includes introduction of slack variables, relaxation, dual transformation, complementary slackness properties, etc. Moreover, variable substitution and introduction of constraints can turn a non-linear cut generation program into linear one and thus the difficulty to solve will be reduced extremely. After conducting numerical experiments with real data, we find that while the dimension of original model reaches (N, J, K) = (34, 32, 32), the efficiency of our algorithm will perform better than solving it directly. The rate of acceleration gradually increases. When the dimension is (N, J, K) = (99, 97, 32), the speed of our algorithm is about 10 times faster and also shows good results in RMSE. Furthermore, synthetic data can also be used in the algorithm. We also hope that in the future, some advanced adjustments to this algorithm can be made, such as constraints allocation, bilinear terms processing, etc., so that a more complex model can be solved more efficiently.
摘要 i
Abstract ii
List of Tables v
Chapter 1 Introduction 1
Chapter 2 Literature Review 4
2.1 BLP model 4
2.2 Classical Benders Decomposition 5
2.3 Benders Decomposition for Mixed-Integer Problem 9
2.4 Performance of MPEC on BLP Model 10
Chapter 3 Original Model 12
3.1 Data Description 12
3.2 Variables and Constraints Description 12
3.3 Objective Function Description 14
3.4 Complete Model 15
Chapter 4 Benders Decomposition with CGP 17
4.1 Define Master Problem and Sub-Problem 17
4.2 Introduction of Slack Variables 18
4.3 Sub-Problem Relaxation 19
4.4 Dual Sub-Problem and Complementary Slackness 20
4.5 Complete CGP Model 21
4.6 Linearization of CGP 25
4.7 Benders Cuts Addition 30
4.7.1 First Way To Add Benders Cuts 31
4.7.2 Second Way To Add Benders Cuts 31
4.7.3 Third Way To Add Benders Cuts 31
4.8 Full Algorithm of Benders Decomposition with CGP 33
Chapter 5 Numerical Experiments 35
Chapter 6 Conclusions 41
References 44
Appendix 48
Alguacil, N., & Conejo, A. J. (2000). Multiperiod optimal power flow using Benders decomposition. IEEE Transactions on Power Systems, 15(1), pp. 196 - 201.
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), pp. 238-252.
Berry, S., Levinsohn, J., & Pakes, A. (1995). Automobile Prices in Market Equilibrium. Econometrica, 63(4), pp. 841-890.
Chu, Y., & Xia, Q. (2004). Generating Benders Cuts for a General Class of Integer Programming Problems. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problem, (pp. 127-141). Springer, Berlin, Heidelberg.
Contreras, I., Cordeau, J. F., & Laporte, G. (2011). Benders Decomposition for Large-Scale Uncapacitated Hub Location. Operations Research, 59(6), pp. 1477-1490.
Cordeau, J. F., Soumis, F., & Desrosiers, J. (2000). A Benders Decomposition Approach for the Locomotive and Car Assignment Problem. Transportation Science, 34(2), pp. 133-149.
Cordeau, J. F., Stojković, G., Soumis, F., & Desrosiers, J. (2001). Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling. Transportation Science, 35(4), pp. 375-388.
Costa, A. M. (2005). A survey on benders decomposition applied to fixed-charge network design problems. Computers & Operations Research, 32(6), pp. 1429-1450.
Dubé, J.‐P., Fox, J., & Su, C.‐L. (2012). Improving the Numerical Performance of Static and Dynamic Aggregate Discrete Choice Random Coefficients Demand Estimation. Econometrica, 80(5), pp. 2231-2267.
Fakhri, A., Ghatee, M., Fragkogios, A., & Saharidis, G. (2017). Benders decomposition with integer subproblem. Expert Systems with Applications, 89, pp. 20-30.
Geoffrion, A. M., & Graves, G. W. (1974). Multicommodity Distribution System Design by Benders Decomposition. Management Science, 20(5), pp. 822-844.
Hansen, L. P. (1982). Large Sample Properties of Generalized Method of Moments Estimators. Econometrica, 50(4), pp. 1029-1054.
Heching, A., & Hooker, J. (2016). Scheduling Home Hospice Care with Logic-Based Benders Decomposition. International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, (pp. 187-197). Springer, Cham.
Hooker, J., & Greger, O. (2003). Logic-based Benders decomposition. Mathematical Programming, 96(1), pp. 33-60.
Hooker, J., & Kim, H.-J. (2002). Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach. Annals of Operations Research, 115(1-4), pp. 95–124.
Istomin, R. (2017). Numerical Algorithm for Inverting the Pure Characteristics Model of Demand. Available at SSRN 2937543.
Judd, K., & Su , C.‐L. (2012). Constrained Optimization Approaches to Estimation of Structural Models. Econometrica, 80(5), pp. 2213-2230.
Luo, Z.-Q., Pang, J.-S., & Ralph, D. (1996). Mathematical Programs with Equilibrium Constraints. Cambridge University Press.
McFadden, D. (1981). Econometric models of probabilistic choice. Structural analysis of discrete data with econometric applications, 198272.
Pakes, A., & Berry , S. (2007). The pure characteristics demand model. International Economic Review, 48(4), pp. 1193-1225.
Pang, J.-S., Su, C.-L., & Lee, Y.-C. (2015). A Constructive Approach to Estimating Pure Characteristics Demand Models with Pricing. Operations Research, 63(3), pp. 639-659.
Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), pp. 801-817.
Roshanaei, V., Luong, C., Aleman, D., & Urbach, D. (2017). Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling. European Journal of Operational Research, 257(2), pp. 439-455.
Song, M. (2007). Measuring consumer welfare in the CPU market: an application of the pure‐characteristics demand model. The RAND Journal of Economics, 38(2), pp. 429-446.
Song, M. (2008). Estimating the Pure Characteristics Demand Model: A Computational Note.
Sun, H., Su, C.-L., & Chen, X. (2017). SAA-regularized methods for multiproduct price optimization under the pure characteristics demand model. Mathematical Programming, 165(1), pp. 361–389.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top