Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การทำนายเงือนไขผูกพันที่เหมาะที่สุดของปัญหากำหนดการเชิงเส้นโดยใช้การเรียนรู้เชิงลึก
Year (A.D.)
2024
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2024.320
Abstract
This thesis presents innovative deep learning models designed to enhance the efficiency of solving linear programming, transportation, and traveling salesman problems. The first model, LP-Net, predicts the binding optimal constraints in linear programming problems, achieving faster solution times compared to traditional solvers like CPLEX. The second model, Transport-Net, predicts optimal basic feasible arcs for transportation problems, demonstrating significant speedups and superior scalability over both CPLEX and Gurobi in large-scale instances. The third model, TSP-Net, addresses the traveling salesman problem by predicting an initial near-optimal tour, outperforming Gurobi and genetic algorithms in computational efficiency. Collectively, these deep learning approaches offer transformative potential for accelerating solutions to fundamental optimization problems.
Other Abstract (Other language abstract of ETD)
งานวิจัยนี้เสนอตัวแบบการเรียนรู้เชิงลึกแบบใหม่ที่ออกแบบมาเพื่อเพิ่มประสิทธิภาพในการแก้ปัญหากำหนดการเชิงเส้น การขนส่งและทัวร์ของพนักงานขาย ตัวแบบแรก แอลพี-เน็ต คาดการณ์ข้อจำกัดที่ผูกมัดที่ดีที่สุดในปัญหากำหนดการเชิงเส้น ทำให้ได้เวลาในการแก้ปัญหาที่เร็วขึ้นเมื่อเทียบกับซอฟต์แวร์แก้ปัญหาแบบดั้งเดิม เช่น ซีเพล็กซ์ตัวแบบที่สอง ทรานส์ปอร์ต-เน็ต คาดการณ์เส้นเชื่อมที่เป็นไปได้พื้นฐานที่ดีที่สุดสำหรับปัญหาการขนส่ง แสดงให้เห็นถึงความเร็วที่เพิ่มขึ้นอย่างมากและความสามารถในการปรับขนาดที่เหนือกว่าทั้งซีเพล็กซ์และกูโรบีสำหรับโจทย์ขนาดใหญ่ ตัวแบบที่สาม ทีเอสพี-เน็ต แก้ไขปัญหาทัวร์ของพนักงานขายโดยการคาดการณ์ทัวร์เริ่มต้นที่ใกล้เคียงกับทัวร์ที่ดีที่สุด มีการหาผลเฉลยที่เร็วกว่า กูโรบีและขั้นตอนวิธีทางพันธุกรรมในด้านประสิทธิภาพการคำนวณ โดยรวมแล้ว วิธีการเรียนรู้เชิงลึกเหล่านี้มีศักยภาพในเร่งการแก้ปัญหาเหล่านี้ให้เร็วขึ้น
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Kafakthong, Natdanai, "Prediction of optimal binding constraints of linear programming problem using deep learning" (2024). Chulalongkorn University Theses and Dissertations (Chula ETD). 11128.
https://digital.car.chula.ac.th/chulaetd/11128