臺灣博碩士論文加值系統

(44.211.239.1) 您好！臺灣時間：2023/02/05 23:07

:::

詳目顯示

:

• 被引用: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.
 摘要 iAbstract iiList of Tables vChapter 1 Introduction 1Chapter 2 Literature Review 42.1 BLP model 42.2 Classical Benders Decomposition 52.3 Benders Decomposition for Mixed-Integer Problem 92.4 Performance of MPEC on BLP Model 10Chapter 3 Original Model 123.1 Data Description 123.2 Variables and Constraints Description 123.3 Objective Function Description 143.4 Complete Model 15Chapter 4 Benders Decomposition with CGP 174.1 Define Master Problem and Sub-Problem 174.2 Introduction of Slack Variables 184.3 Sub-Problem Relaxation 194.4 Dual Sub-Problem and Complementary Slackness 204.5 Complete CGP Model 214.6 Linearization of CGP 254.7 Benders Cuts Addition 304.7.1 First Way To Add Benders Cuts 314.7.2 Second Way To Add Benders Cuts 314.7.3 Third Way To Add Benders Cuts 314.8 Full Algorithm of Benders Decomposition with CGP 33Chapter 5 Numerical Experiments 35Chapter 6 Conclusions 41References 44Appendix 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.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 利用乘法模型與正交擾動價格設置之需求學習演算法計算均衡定價 2 混合策略納許均衡規劃於航空公司時間帶競爭之應用 3 應用邏輯基礎班德氏分解法加快產品性質需求參數估計模型求解速度 4 建立繞道協議模型結合疑似中風病人到院前中風程度量表 5 利用數據驅動計算非合作賽局之定價均衡的數值實驗 6 利用隨機規劃模型發展對於急性腦中風病患到院前的繞道策略及EVT資源再分配 7 無母數逆最佳化方法與純特徵需求函數預測最優產品特徵組合的數值實驗 8 使用納許均衡規劃模型探討外包作業對面板產業盈利影響之研究 9 以資料導向預測線性限制下最佳化模型之參數 10 基於循環經濟發展最適產業結構之方法— 以台灣食物/能源/水產業關聯為例 11 以作業研究方法管理太陽能電運用-以個案公司為例 12 應用班德氏分解法於隨機混整數規劃 13 深究產品的最佳特徵組合與消費者市場潛在品味:透過效用函數最小方差估計 14 整數規劃的多維參數敏感度分析：兩種演算法之比較 15 使用納許均衡規劃模型來探討時間帶競爭 對航空公司盈利能力的影響

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室