Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/16016
| Title: | อสมการสมเหตุสมผลและการแปลงเพื่อหาผลเฉลยสำหรับปัญหาการกำหนดงานนัยทั่วไปอย่างมีประสิทธิภาพ |
| Other Titles: | Valid inequalities and transformations for efficient solving the generalized assignment problem |
| Authors: | สายฝน เทียมแก้ว |
| Advisors: | กรุง สินอภิรมย์สราญ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Advisor's Email: | krung@math.sc.chula.ac.th |
| Subjects: | อสมการ การโปรแกรมเชิงเส้น |
| Issue Date: | 2550 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ปัญหาการกำหนดงานนัยทั่วไป เป็นปัญหากำหนดการจำนวนเต็มประเภทหนึ่ง ซึ่งหาผลเฉลยโดยใช้วิธีขยายและจำกัดเขตทั่วไป แต่สำหรับปัญหาการกำหนดงานนัยทั่วไปมีโครงสร้างของตัวแบบที่เฉพาะเจาะจง ซึ่งมีแนวโน้มในการปรับปรุงจำนวนรอบการคำนวณด้วยวิธีขยายและจำกัดเขต วิทยานิพนธ์ฉบับนี้ เรานำเสนอหลักการปรับปรุงจำนวนรอบการคำนวณของวิธีขยายและจำกัดเขต โดยใช้วิธีเพิ่มอสมการอย่างสมเหตุสมผลและการแปลงปัญหา การใช้อสมการอย่างสมเหตุสมผล ช่วยลดบริเวณที่เป็นไปได้ของกำหนดการเชิงเส้นผ่อนปรน โดยไม่กำจัดผลเฉลยที่เป็นไปได้ของปัญหาการกำหนดงานนัยทั่วไป การแปลงปัญหา กำหนดจุดเริ่มต้นใหม่ให้กับปัญหาการกำหนดงานนัยทั่วไป ซึ่งเป็นตัวแทนผลเฉลยที่ดีกว่าจุดเริ่มต้นเดิม เราใช้ซอฟต์แวร์เปิด GLPK (GNU Linear Programming Kit) เพื่อเปรียบเทียบจำนวนรอบการคำนวณระหว่างวิธีขยายและจำกัดเขตแบบเดิมกับวิธีแบบใหม่ของเรา งานวิจัย เราใช้จำนวนรอบการคำนวณน้อยกว่า 40% เมื่อเทียบกับวิธีขยายและจำกัดเขตแบบเดิม |
| Other Abstract: | 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. |
| Description: | วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2550 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาการคณนา |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/16016 |
| URI: | http://doi.org/10.14457/CU.the.2007.218 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2007.218 |
| Type: | Thesis |
| Appears in Collections: | Sci - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Saiphon_Th.pdf | 939.99 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.