Chulalongkorn University Theses and Dissertations (Chula ETD)
อสมการสมเหตุสมผลและการแปลงเพื่อหาผลเฉลยสำหรับปัญหาการกำหนดงานนัยทั่วไปอย่างมีประสิทธิภาพ
Other Title (Parallel Title in Other Language of ETD)
Valid inequalities and transformations for efficient solving the generalized assignment problem
Year (A.D.)
2007
Document Type
Thesis
First Advisor
กรุง สินอภิรมย์สราญ
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิทยาการคณนา
DOI
10.58837/CHULA.THE.2007.912
Abstract
ปัญหาการกำหนดงานนัยทั่วไป เป็นปัญหากำหนดการจำนวนเต็มประเภทหนึ่ง ซึ่งหาผลเฉลยโดยใช้วิธีขยายและจำกัดเขตทั่วไป แต่สำหรับปัญหาการกำหนดงานนัยทั่วไปมีโครงสร้างของตัวแบบที่เฉพาะเจาะจง ซึ่งมีแนวโน้มในการปรับปรุงจำนวนรอบการคำนวณด้วยวิธีขยายและจำกัดเขต วิทยานิพนธ์ฉบับนี้ เรานำเสนอหลักการปรับปรุงจำนวนรอบการคำนวณของวิธีขยายและจำกัดเขต โดยใช้วิธีเพิ่มอสมการอย่างสมเหตุสมผลและการแปลงปัญหา การใช้อสมการอย่างสมเหตุสมผล ช่วยลดบริเวณที่เป็นไปได้ของกำหนดการเชิงเส้นผ่อนปรน โดยไม่กำจัดผลเฉลยที่เป็นไปได้ของปัญหาการกำหนดงานนัยทั่วไป การแปลงปัญหา กำหนดจุดเริ่มต้นใหม่ให้กับปัญหาการกำหนดงานนัยทั่วไป ซึ่งเป็นตัวแทนผลเฉลยที่ดีกว่าจุดเริ่มต้นเดิม เราใช้ซอฟต์แวร์เปิด GLPK (GNU Linear Programming Kit) เพื่อเปรียบเทียบจำนวนรอบการคำนวณระหว่างวิธีขยายและจำกัดเขตแบบเดิมกับวิธีแบบใหม่ของเรา งานวิจัย เราใช้จำนวนรอบการคำนวณน้อยกว่า 40% เมื่อเทียบกับวิธีขยายและจำกัดเขตแบบเดิม
Other Abstract (Other language abstract of ETD)
The generalized assignment problem is one of the integer programming problem that has been solved by the general branch-and-bound. Due to a special structure of the generalized assignment problem, it is possible to improve the number of iterations of the branch-and-bound method. In this thesis, we improve the number of branch-and-bound iterations by applying the valid inequalities and transformation. The valid inequalities reduce feasible region of the linear programming relaxation but maintain integer feasible solutions. Transformation defines a new starting point for the generalized assignment problem, which is a better candidate than the original starting point. We use open source GLPK (GNU Linear Programming Kit) to compare the number of iterations between the original branch-and-bound method with our methodology, our method uses 40% less iterations than the original branch-and-bound method.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
เทียมแก้ว, สายฝน, "อสมการสมเหตุสมผลและการแปลงเพื่อหาผลเฉลยสำหรับปัญหาการกำหนดงานนัยทั่วไปอย่างมีประสิทธิภาพ" (2007). Chulalongkorn University Theses and Dissertations (Chula ETD). 58426.
https://digital.car.chula.ac.th/chulaetd/58426