การเปรียบเทียบวิธีการสร้างแถวและวิธีการสร้างสดมภ์สำหรับปัญหากำหนดการเชิงเส้นขนาดใหญ่และการใช้หน่วยความจำรำรอง
คำสำคัญ:
ปัญหากำหนดการเชิงเส้นขนาดใหญ่, การสร้างแถว, การสร้างสดมภ์, หน่วยความจำสำรองบทคัดย่อ
งานวิจัยนี้มีวัตถุประสงค์เพื่อนำเสนอวิธีการสร้างแถวและสดมภ์ (Row-and-column generation) และทำการเปรียบเทียบวิธีการวิจัย 4 รูปแบบ คือ วิธีการตรงแบบเต็มรูป (Linear programming with full model, LPFM) วิธีการสลับการสร้างแถวและสดมภ์ (Switching row-and-column generation, SRCG) วิธีการสร้างสดมภ์ขึ้นกับแถว (Row-dependent-column generation, RDCG) และวิธีการสร้างแถวขึ้นกับสดมภ์ (Column-dependent-column generation, CDRG) โดยวัดประสิทธิภาพของแต่ละวิธีการด้วยคุณภาพของคำตอบ และระยะเวลาที่ใช้ในการประมวลผล จากการแก้ปัญหากำหนดการเชิงเส้นขนาดใหญ่ (Large-scale linear programming problem) พบว่าเมื่อขนาดปัญหาขนาดใหญ่ขึ้นถึงช่วงหนึ่ง จะทำให้วิธีการตรงแบบเต็มรูปไม่สามารถหาคำตอบได้เนื่องจากขีดจำกัดของทรัพยากรและทั้ง 4 วิธีการ ให้คุณภาพของคำตอบที่ใกล้เคียงกัน แต่จะมีความแตกต่างในด้านของระยะเวลาที่ใช้ในการประมวลผลซึ่งวิธีการสร้างแถวขึ้นกับสดมภ์ใช้ระยะเวลาในการประมวลผลโดยเฉลี่ย (Average processing time) ต่ำที่สุด และในบทขยายเพิ่มเติมได้แนะนำให้เก็บข้อมูลบางส่วนที่ไม่ได้ใช้ขณะนั้นจากหน่วยความจำหลัก (Primary storage) ไปยังหน่วยความจำสำรอง (Secondary storage) เพื่อเพิ่มพื้นที่ของหน่วยความจำหลักในการคำนวนปัญหา ซึ่งพบว่าสามารถแก้ปัญหาขนาดใหญ่ได้มากกว่าเดิม
เอกสารอ้างอิง
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.
ดาวน์โหลด
เผยแพร่แล้ว
รูปแบบการอ้างอิง
ฉบับ
ประเภทบทความ
สัญญาอนุญาต
อนุญาตภายใต้เงื่อนไข Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
