Comparison Simultaneous Row-and-Column Generation Approach for Large-Scale Linear Programming Problem and secondary memory utilization
Keywords:
Large-scale linear programming, Row generation, Column generation, Secondary storageAbstract
This research studied the methods to solve linear programming by simultaneous row-and-column generation approach and compared efficiency among 4 methods: Linear Programming with Full Model (LPFM), Switching Row-and-Column Generation (SRCG), Row-Dependent-Column Generation (RDCG) and Column-Dependent-Column Generation (CDRG). The study compares optimal objective value and processing time when solving large-scale linear programming problem. The result showed that some of large-scale linear programming problems cannot solve using LPFM directly due to out-of-core memory. The solutions quality solved by each method is the same. However, there are differences in processing time in which RDCG provided optimal solutions with the least average processing time. And in the last chapter recommended to store some unused data from the primary storage to the secondary storage to free up the space of the main memory. Which was found to be able to solve larger problems.
References
George B. Dantzig; Philip Wolfe (1960). "Decomposition Principle for Linear Programs". Operations Research. 8: 101–111. doi:10.1287/opre.8.1.101.
Bixby, Robert & Gregory, John & Lustig, Irvin & Marsten, Roy & Shanno, David. (1992). Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods. Oper. Res. 40. 885-897. 10.1287/opre.40.5.885.
Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
อภิศักดิ์ วิทยาประภากร, เอราวิล ถาวร, เริงทิวา ทิพยศักดิ์ และ พีรยุทธ์ ชาญเศรษฐิกุล, “การแก้ปัญหาการจัดสรรเงินลงทุนเชิงจัดหมู่ด้วยเทคนิคการสร้างแถว,” วารสารไทยการวิจัยดาเนินงาน., ปีที่ 6, ฉบับที่ 2, น. 10-21, 2561.
G. Dantzig, R. Fulkerson, and S. Jonhson, “Solution of a large-scale travelling-salesman problem”, Journal of the Operation Research Society of America, pp. 393-410, 1954.
รัฐพล สังคะสุข, ฐิติรัตน์ วิวิธเกยูรวงศ์, เบญจพร พวงจาปี, ศรินทิพย์ อนุรักษ์, สหชาติ เลิศศิริเภสัช และ พีรยุทธ์ ชาญเศรษฐิกุล, “การแก้ปัญหาการจัดสรรเงินลงทุนเชิงจัดหมู่ ด้วยวิธีการสร้างสดมภ์”, วารสารไทยการวิจัยดาเนินงาน., ปีที่ 8, ฉบับที่ 1, น. 37-48, 2563.
A. Sangiovanni-Vincentelli, Li-Kuan Chen and L. Chua, "An efficient heuristic cluster algorithm for tearing large-scale networks," in IEEE Transactions on Circuits and Systems, vol. 24, no. 12, pp. 709-717, December 1977, doi: 10.1109/TCS.1977.1084298.
Jari Kytöjoki, Teemu Nuortio, Olli Bräysy, Michel Gendreau, “An efficient variable neighborhood search heuristic for very large-scale vehicle routing problems”, Computers & Operations Research, Volume 34, Issue 9, 2007, Pages 2743-2757, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2005.10.010.
ปวิธ ไกรสรนุเคราะห์, รมิดายุ อยู่สุข, นราภรณ์ เภาประเสริฐ, “การปรับปรุงวิธีอาณาจักรมดสาหรับการแก้ปัญหาการจัดเส้นทางขนส่งสินค้าแบบมีขอบเขตเวลาและแบ่งส่งสินค้า”, วิศวกรรมสารธรรมศาสตร์ มหาวิทยาลัยธรรมศาสตร์, ปีที่ 6, ฉบับที่ 1, 2020, หน้า 1-8
ปวิธ ไกรสรนุเคราะห์, รมิดายุ อยู่สุข, แพรวพรรณ ประหยัดทรัพย์ และ นราภรณ์ เภาประเสริฐ, “การพัฒนาโปรแกรมในการจัดลำดับเครื่องเล่นในสวนสนุกโดยขั้นตอนวิธีเชิงพันธุกรรมและขั้นตอนวิธีเชิงวิวัฒนาการ”, The 5th Thai-Nichi Institute of Technology Academic Conference 2019, 2019.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
