臺灣博碩士論文加值系統

本篇論文將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.