簡易檢索 / 詳目顯示

回結果列表
研究生： 方鈺學
Fang, Yu-Hsueh
論文名稱： 最小化最大誤差分段線性化於高維度背包問題
Flattened Minimax Error Piecewise Linearization on Multidimensional Assortment Problem
指導教授： 李家岩
Lee, Chia-Yen
共同指導教授: 王宏鍇
Wang, Hung-Ka
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 製造資訊與系統研究所
Institute of Manufacturing Information and Systems
論文出版年： 2022
畢業學年度： 110
語文別： 英文
論文頁數： 87
中文關鍵詞： 分段線性化 、最小化最大誤差 、背包問題 、混整數規劃
外文關鍵詞： Piecewise Linearization, Minimax Error, Assortment Problem, Mixed-Integer Programming
相關次數： 點閱：64  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 背包問題的各種變體在各行各業中被廣泛使用。面積最小化背包問題被歸類為一個特別的開放維度問題。為了通過混合整數規劃解決面積最小化分類問題，我們利用了分段線性化的轉換。但分段線性化的使用導致兩個問題：精度和計算上的負擔。在這項研究中，我們提出了一種新的公式來生成對數分斷點。該公式以最少的分斷點保證了一定的最大誤差界線。本研究證明了此公式的最優性。
    我們還應用二元變數編碼技術於模型與分段線性化公式，得出新的可能的模型組合。我們使用模型和分段線性化公式的這些不同組合對面積最小化背包問題進行了實驗。結果顯示了本研究的貢獻，並比較了不同的組合，以作為後續研究的基石。

    The variants of the assortment problems are widely used in industries. The area-minimized assortment problem is classified as an open dimensional problem. To solve the area-minimized assortment problem by Mix-Integer Programming, we utilize the transformation of the piecewise linearization. The use of the piecewise linearization resulting in two issues: the precision and the computational burden. In this research, we proposed a new general formulation for generating breakpoints for logarithm. The proposition gives the guarantee of the bound of certain maximum error with the least breakpoints. The optimality of the general formulation is proven.
    We also combine the binary variable reduction techniques on the model and the piecewise linearization formulations deriving new possible combinations of models. We conduct experiment of the area-minimized assortment problems with these different combinations of the models and piecewise linearization formulations. The results demonstrate the benefits of our proposition and gives a comparison of different formulations.

    中文摘要 I Abstract II 致謝 III Table of Content IV List of Tables VII List of Figures VIII Notations IX Chapter 1. Introduction 1 1.1 Background and Motivation 1 1.2 Problem Description and Research Purpose 1 1.3 Research Overview 3 Chapter 2. Literature Review 5 2.1 The Assortment Problem 6 2.1.1 The Classifications of Assortment Problems 7 2.1.2 The Approaches for Solving Assortment Problems 11 2.1.3 The Formulations of Mathematical Programming 14 2.2 The Piecewise Linearization 21 2.2.1 The Formulations of Piecewise Linearization 22 2.2.2 The Quality of Piecewise Linearization 26 2.3 Mixed-Integer Programming 28 2.3.1 The algorithms behind Mixed-Integer Programming 29 2.3.2 The Binary Variable Reduction 30 2.3.3 The Techniques of Optimization 31 2.4 The Conclusion of Literature Review 32 2.4.1 The Remarks of Literatures 34 Chapter 3. The Modeling Techniques and The Refinement of Models 36 3.1 Research Framework 36 3.2 The Mixed-Integer Programming for the Area-Minimized Assortment Problem 41 3.3 The Piecewise Linearization for Logarithm 42 3.3.1 The Minimax Error Sampling of Logarithm 42 3.3.2 The Binary Variable Reduction of Piecewise Linearization 49 3.4 The Polynomial Model 50 3.4.1 The Big-M Method 51 3.5 The Pseudo-Polynomial Model 52 3.5.1 The Binary Variable Reduction on Pseudo-Polynomial Model 54 3.6 The Remarks and The Conclusions 56 3.6.1 The Comparison of Combinations of Models and Methods 56 Chapter 4. The Validation and The Benchmark 59 4.1 The Experiment Outline and The Platform 59 4.2 The Assessment of Piecewise Linearization 60 4.2.1 The Algorithms of Piecewise Linearization 62 4.2.2 The Precision of Piecewise Linearization 67 4.2.3 The Number of Intervals 68 4.3 The Benchmark Sets of Area-Minimized Assortment Problem 70 4.3.1 The Benchmark of Different Breakpoint Generation Algorithms 71 4.3.2 The Benchmark of Combinations of Models and Methods 74 4.3.3 The Conclusion of the Experiments 77 Chapter 5. Conclusion and Future Works 77 References 79 Appendix 87

    Alvarez-Valdés, R., Parajón, A., & Tamarit, J. M. (2002). A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers & Operations Research, 29(7), 925–947. https://doi.org/10.1016/S0305-0548(00)00095-2
    Alvarez-Valdes, R., Parreño, F., & Tamarit, J. M. (2005). A branch-and-cut algorithm for the pallet loading problem. Computers & Operations Research, 32(11), 3007–3029. https://doi.org/10.1016/j.cor.2004.04.010
    Alvarez-Valdes, R., Parreño, F., & Tamarit, J. M. (2007). A tabu search algorithm for a two-dimensional non-guillotine cutting problem. European Journal of Operational Research, 183(3), 1167–1182. https://doi.org/10.1016/j.ejor.2005.11.068
    Baker, B., Coffman, E., & Rivest, R. (1980). Orthogonal Packings in Two Dimensions. SIAM J. Comput. https://doi.org/10.1137/0209064
    Baldacci, R., & Boschetti, M. A. (2007). A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. European Journal of Operational Research, 183(3), 1136–1149. https://doi.org/10.1016/j.ejor.2005.11.060
    Bennell, J. A., & Oliveira, J. F. (2009). A tutorial in irregular shape packing problems. Journal of the Operational Research Society, 60(1), S93–S105. https://doi.org/10.1057/jors.2008.169
    Boschetti, M. A., & Montaletti, L. (2010). An Exact Algorithm for the Two-Dimensional Strip-Packing Problem. Operations Research, 58(6), 1774–1791. https://doi.org/10.1287/opre.1100.0833
    Burke, E. K., Hyde, M. R., & Kendall, G. (2011). A squeaky wheel optimisation methodology for two-dimensional strip packing. Computers & Operations Research, 38(7), 1035–1044. https://doi.org/10.1016/j.cor.2010.10.005
    Burke, E., Kendall, G., & Whitwell, G. (2004). A New Placement Heuristic for the Orthogonal Stock-Cutting Problem. Operations Research, 52, 655–671. https://doi.org/10.1287/opre.1040.0109
    Camm, J., Raturi, A., & Tsubakitani, S. (1990). Cutting Big M Down to Size. Interfaces, 20, 61–66. https://doi.org/10.1287/inte.20.5.61
    Chen, C. S., Lee, S. M., & Shen, Q. S. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80(1), 68–76. https://doi.org/10.1016/0377-2217(94)00002-T
    Croxton, K., Gendron, B., & Magnanti, T. (2003). A Comparison of Mixed-Integer Programming Models for Non-Convex Piecewise Linear Cost Minimization Problems. Management Science, 49, 1268–1273. https://doi.org/10.1287/mnsc.49.9.1268.16570
    Croxton, K. L., Gendron, B., & Magnanti, T. L. (2003). Models and Methods for Merge-in-Transit Operations. Transportation Science, 37(1), 1–22. https://doi.org/10.1287/trsc.37.1.1.12822
    Dantzig, G. B. (1960). On the Significance of Solving Linear Programming Problems with Some Integer Variables. Econometrica, 28(1), 30–44. https://doi.org/10.2307/1905292
    Dantzig, G. B., & Wolfe, P. (1960). Decomposition Principle for Linear Programs. Operations Research, 8(1), 101–111. https://doi.org/10.1287/opre.8.1.101
    de Queiroz, T. A., & Miyazawa, F. K. (2014). Order and static stability into the strip packing problem. Annals of Operations Research, 223(1), 137–154. https://doi.org/10.1007/s10479-014-1634-2
    Duan, J., Tong, X., Ni, F., He, Z., Chen, L., & Yuan, M. (2022). A Data-Driven Column Generation Algorithm For Bin Packing Problem in Manufacturing Industry (arXiv:2202.12466). arXiv. https://doi.org/10.48550/arXiv.2202.12466
    Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44(2), 145–159. https://doi.org/10.1016/0377-2217(90)90350-K
    Gabrel, V., Knippel, A., & Minoux, M. (1999). Exact solution of multicommodity network optimization problems with general step cost functions. Operations Research Letters, 25(1), 15–23. https://doi.org/10.1016/S0167-6377(99)00020-6
    Gonçalves, J. F., & Resende, M. G. C. (2013). A biased random key genetic algorithm for 2D and 3D bin packing problems. International Journal of Production Economics, 145(2), 500–510. https://doi.org/10.1016/j.ijpe.2013.04.019
    Günlük, O. (1999). A branch-and-cut algorithm for capacitated network design problems. Mathematical Programming, 86(1), 17–39. https://doi.org/10.1007/s101070050077
    Hillier, F., & Lieberman, G. (1969). Introduction To Operations Research. In Journal of the Royal Statistical Society. Series A (General) (Vol. 139). https://doi.org/10.2307/2345190
    Huang, E., & Korf, R. E. (2013). Optimal Rectangle Packing: An Absolute Placement Approach. Journal of Artificial Intelligence Research, 46, 47–87. https://doi.org/10.1613/jair.3735
    Iori, M., de Lima, V. L., Martello, S., Miyazawa, F. K., & Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2), 399–415. https://doi.org/10.1016/j.ejor.2020.06.050
    Iori, M., & Martello, S. (2010). Routing problems with loading constraints. TOP, 18(1), 4–27. https://doi.org/10.1007/s11750-010-0144-x
    Iori, M., Martello, S., & Monaci, M. (2003). Metaheuristic Algorithms for the Strip Packing Problem. In P. M. Pardalos & V. Korotkikh (Eds.), Optimization and Industry: New Frontiers (pp. 159–179). Springer US. https://doi.org/10.1007/978-1-4613-0233-9_7
    Kleinert, T., Labbé, M., Plein, F., & Schmidt, M. (2020). Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization. Operations Research, 68(6), 1716–1721. https://doi.org/10.1287/opre.2019.1944
    Li, H. L. (1996). An efficient method for solving linear goal programming problems. Journal of Optimization Theory and Applications, 90(2), 465–469. https://doi.org/10.1007/BF02190009
    Li, H.-L., & Chang, C.-T. (1998). An approximately global optimization method for assortment problems. European Journal of Operational Research, 105(3), 604–612. https://doi.org/10.1016/S0377-2217(97)00072-6
    Li, H.-L., Chang, C.-T., & Tsai, J.-F. (2002). Approximately global optimization for assortment problems using piecewise linearization techniques. European Journal of Operational Research, 140(3), 584–589. https://doi.org/10.1016/S0377-2217(01)00194-1
    Li, H.-L., Huang, Y.-H., & Fang, S.-C. (2013). A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems. INFORMS Journal on Computing, 25, 643–653. https://doi.org/10.1287/ijoc.1120.0527
    Li, H.-L., Lu, H.-C., Huang, C.-H., & Hu, N.-Z. (2009). A Superior Representation Method for Piecewise Linear Functions. INFORMS Journal on Computing, 21(2), 314–321. https://doi.org/10.1287/ijoc.1080.0294
    Li, H.-L., & Yu, C.-S. (1999). A global optimization method for nonconvex separable programming problems. European Journal of Operational Research, 117(2), 275–292. https://doi.org/10.1016/S0377-2217(98)00243-4
    Lin, C.-C. (2006). A genetic algorithm for solving the two-dimensional assortment problem. Computers & Industrial Engineering, 50(1–2), 175–184. https://doi.org/10.1016/j.cie.2006.03.002
    Lin, M.-H., Carlsson, J. G., Ge, D., Shi, J., & Tsai, J.-F. (2013). A Review of Piecewise Linearization Methods. Mathematical Problems in Engineering, 2013, e101376. https://doi.org/10.1155/2013/101376
    Lins, L., Lins, S., & Morabito, R. (2002). An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container. European Journal of Operational Research, 141(2), 421–439. https://doi.org/10.1016/S0377-2217(02)00135-2
    Lodi, A., & Monaci, M. (2003). Integer linear programming models for 2-staged two-dimensional Knapsack problems. Math. Program. https://doi.org/10.1007/s10107-002-0319-9
    Lundell, A. (2009). Transformation Techniques for Signomial Functions in Global Optimization. 109.
    Markowitz, H. M., & Manne, A. S. (1957). On the Solution of Discrete Programming Problems. Econometrica, 25(1), 84–110. https://doi.org/10.2307/1907744
    Martello, S., & Monaci, M. (2015). Models and algorithms for packing rectangles into the smallest square. Computers & Operations Research, 63, 161–171. https://doi.org/10.1016/j.cor.2015.04.024
    Martello, S., Monaci, M., & Vigo, D. (2003). An Exact Approach to the Strip-Packing Problem. INFORMS Journal on Computing, 15, 310–319. https://doi.org/10.1287/ijoc.15.3.310.16082
    Martin, M., Hokama, P. H. D. B., Morabito, R., & Munari, P. (2020). The constrained two-dimensional guillotine cutting problem with defects: An ILP formulation, a Benders decomposition and a CP-based algorithm. International Journal of Production Research, 58(9), 2712–2729. https://doi.org/10.1080/00207543.2019.1630773
    Melega, G. M., de Araujo, S. A., & Jans, R. (2018). Classification and literature review of integrated lot-sizing and cutting stock problems. European Journal of Operational Research, 271(1), 1–19. https://doi.org/10.1016/j.ejor.2018.01.002
    Ortmann, F., & Vuuren, J. (2010). Modified strip packing heuristics for the rectangular variable-sized bin packing problem. ORiON, 26, 21–44. https://doi.org/10.5784/26-1-84
    Padberg, M. (2000). Approximating separable nonlinear functions via mixed zero-one programs. Operations Research Letters, 27(1), 1–5. https://doi.org/10.1016/S0167-6377(00)00028-6
    Russo, M., Boccia, M., Sforza, A., & Sterle, C. (2020). Constrained two-dimensional guillotine cutting problem: Upper-bound review and categorization. International Transactions in Operational Research, 27(2), 794–834. https://doi.org/10.1111/itor.12687
    Russo, M., Sforza, A., & Sterle, C. (2014). An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems. Computers & Operations Research, 50, 97–114. https://doi.org/10.1016/j.cor.2014.04.001
    Savage, L. J. (1951). The Theory of Statistical Decision. Journal of the American Statistical Association, 46(253), 55–67. https://doi.org/10.2307/2280094
    Scheithauer, G. (1999). LP-based bounds for the container and multi-container loading problem. International Transactions in Operational Research, 6(2), 199–213. https://doi.org/10.1111/j.1475-3995.1999.tb00151.x
    Taha, H. A. (2017). Operations Research: An Introduction, 10th Edition. https://www.pearson.com/content/one-dot-com/one-dot-com/us/en/higher-education/program.html
    Trespalacios, F., & Grossmann, I. (2015). Improved Big-M reformulation for generalized disjunctive programs. Computers & Chemical Engineering, 76. https://doi.org/10.1016/j.compchemeng.2015.02.013
    Tsai, J.-F., & Li, H.-L. (2006). A global optimization method for packing problems. Engineering Optimization, 38(6), 687–700. https://doi.org/10.1080/03052150600603264
    Tsai, J.-F., Wang, P.-C., & Lin, M.-H. (2013). An efficient deterministic optimization approach for rectangular packing problems. Optimization, 62(7), 989–1002. https://doi.org/10.1080/02331934.2011.625029
    Tsai, J.-F., Wang, P.-C., & Lin, M.-H. (2015). A global optimization approach for solving three-dimensional open dimension rectangular packing problems. https://doi.org/10.1080/02331934.2013.877906
    Valério de Carvalho, J. M. (1999). Exact solution of bin‐packing problems using column generation and branch‐and‐bound. Annals of Operations Research, 86(0), 629–659. https://doi.org/10.1023/A:1018952112615
    Vielma, J. P., & Nemhauser, G. L. (2011). Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Mathematical Programming, 128(1), 49–72. https://doi.org/10.1007/s10107-009-0295-4
    Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
    Wei, L., Oon, W.-C., Zhu, W., & Lim, A. (2012). A reference length approach for the 3D strip packing problem. European Journal of Operational Research, 220(1), 37–47. https://doi.org/10.1016/j.ejor.2012.01.039
    Wu, Y., Li, W., Goh, M., & de Souza, R. (2010). Three-dimensional bin packing problem with variable bin height. European Journal of Operational Research, 202(2), 347–355. https://doi.org/10.1016/j.ejor.2009.05.040
    Xie, Q., Pang, C., Zhou, X., Zhang, X., & Deng, K. (2014). Maximum error-bounded Piecewise Linear Representation for online stream approximation. The VLDB Journal, 23(6), 915–937. https://doi.org/10.1007/s00778-014-0355-0
    Yıldız, S., & Vielma, J. P. (2013). Incremental and encoding formulations for Mixed Integer Programming. Operations Research Letters, 41(6), 654–658. https://doi.org/10.1016/j.orl.2013.09.004

    下載圖示 校內：2025-08-19公開
    校外：2025-08-19公開
    QR CODE