การสร้างคอลัมน์ (Dantzig-Wolfe)
- ผู้เสนอ
- George B. Dantzig and Philip Wolfe
- ปี
- 1960
- ประเภท
- algorithm
- กลุ่มวิธี
- Optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การสร้างคอลัมน์ (Column Generation) ซึ่งพัฒนาโดย George B. Dantzig และ Philip Wolfe ในปี 1960 เป็นเทคนิคการหาค่าเหมาะที่สุดที่มีประสิทธิภาพสำหรับการแก้ปัญหาการโปรแกรมเชิงเส้นขนาดใหญ่ที่มีโครงสร้างพิเศษ หรือที่เรียกว่าการแยกส่วนแบบ Dantzig-Wolfe (Dantzig-Wolfe Decomposition) เทคนิคนี้จะแยกปัญหาออกเป็นปัญหาส่วนหลัก (master problem) ซึ่งจำกัดอยู่เฉพาะตัวแปร/คอลัมน์ย่อย และปัญหาย่อยการกำหนดราคา (pricing subproblem) ซึ่งระบุตัวแปรใหม่ โดยจะปรับปรุงผลลัพธ์ซ้ำ ๆ ด้วยการนำเสนอเฉพาะคอลัมน์ที่เกี่ยวข้องเท่านั้น
แนวคิดเบื้องหลังวิธีการ
วิธีนี้ตระหนักว่าปัญหาการหาค่าเหมาะที่สุดขนาดใหญ่จำนวนมากมีโครงสร้างพิเศษ: มีตัวแปรจำนวนมากแต่มีข้อจำกัดที่สำคัญจริง ๆ เพียงไม่กี่ข้อ หรือมีปัญหาย่อยที่สามารถแยกส่วนได้ตามธรรมชาติ แทนที่จะแก้ปัญหาเต็มรูปแบบด้วยตัวแปรที่เป็นไปได้ทั้งหมด การสร้างคอลัมน์จะคงไว้เพียงชุดย่อยเล็ก ๆ ของคอลัมน์ที่มีแนวโน้มดี (ตัวแปร) เท่านั้น ปัญหาการกำหนดราคา ซึ่งแก้ไขโดยใช้ต้นทุนลดลงและโครงสร้างปัญหา จะระบุคอลัมน์ใหม่ที่ปรับปรุงผลลัพธ์หลัก ด้วยการเพิ่มคอลัมน์ที่มีแนวโน้มดีที่สุดซ้ำ ๆ อัลกอริทึมจะสร้างผลลัพธ์ได้อย่างมีประสิทธิภาพ หลีกเลี่ยงภาระการคำนวณในการจัดการคอลัมน์ทั้งหมดพร้อมกัน
ประวัติศาสตร์
Dantzig และ Wolfe ได้นำเสนอหลักการแยกส่วนสำหรับโปรแกรมเชิงเส้นในปี 1960 ซึ่งเป็นรากฐานทางทฤษฎี Gilmore และ Gomory (1961) ได้นำไปประยุกต์ใช้กับปัญหาการตัดสต็อก ซึ่งแสดงให้เห็นถึงพลังในทางปฏิบัติ วิธีนี้ได้รับความนิยมสำหรับปัญหาการจัดเส้นทางยานพาหนะและการจัดตารางเวลาในช่วงทศวรรษ 1980-90 การรวมเข้ากับการแตกแขนงและขอบเขต ซึ่งสร้างอัลกอริทึม branch-and-price ได้ขยายขอบเขตการใช้งานไปยังการโปรแกรมจำนวนเต็ม การประยุกต์ใช้ในปัจจุบันรวมถึงการจัดตารางเวลาลูกเรือสายการบิน การจัดเส้นทางเรือ และการหาค่าเหมาะที่สุดด้านโลจิสติกส์ขนาดใหญ่
ควรใช้เมื่อใด
ประยุกต์ใช้การสร้างคอลัมน์เมื่อแก้ปัญหาการโปรแกรมเชิงเส้นขนาดใหญ่ที่มีโครงสร้างพิเศษ โดยเฉพาะอย่างยิ่งเมื่อจำนวนตัวแปรมีมาก แต่มีชุดย่อยขนาดเล็กที่มีอิทธิพลต่อผลลัพธ์ที่เหมาะสมที่สุด เหมาะอย่างยิ่งสำหรับปัญหาการตัดสต็อก (cutting stock problems) การจัดเส้นทางยานพาหนะ (vehicle routing) การจัดตารางเวลาลูกเรือ (crew scheduling) และการบรรจุกล่อง (bin packing) ใช้เมื่อโครงสร้างปัญหาช่วยให้สามารถแก้ปัญหาย่อยการกำหนดราคาได้อย่างมีประสิทธิภาพ สำหรับปัญหาที่ไม่มีโครงสร้างที่สามารถใช้ประโยชน์ได้หรือมีขนาดปานกลาง ตัวแก้ปัญหา LP มาตรฐานจะใช้งานได้จริงมากกว่า
ข้อจำกัดและข้อควรพิจารณา
- ต้องมีโครงสร้างปัญหาที่ช่วยให้การแก้ปัญหาย่อยการกำหนดราคามีประสิทธิภาพ
- การลู่เข้าอาจช้า โดยเฉพาะอย่างยิ่งเมื่อใกล้ค่าเหมาะที่สุด (ผลกระทบของการลดลงช้า)
- การแก้ปัญหาย่อยการกำหนดราคาต้องน่าเชื่อถือและมีประสิทธิภาพ มิฉะนั้นประสิทธิภาพที่ได้จะสูญเปล่า
- ความซับซ้อนในการนำไปใช้สูงกว่าวิธี LP มาตรฐาน
- ปัญหาความเสถียรเชิงตัวเลขเมื่อค่าคู่และต้นทุนลดลงมีค่ามาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- แก้ปัญหาขนาดใหญ่ที่แก้ไขไม่ได้ด้วยวิธีมาตรฐานเนื่องจากการระเบิดของคอลัมน์ (column explosion)
- ใช้ประโยชน์จากโครงสร้างปัญหาเพื่อสร้างเฉพาะคอลัมน์ที่เกี่ยวข้อง
- ให้ขอบเขตของคุณภาพผลลัพธ์ระหว่างการวนซ้ำ
- เหมาะอย่างยิ่งสำหรับปัญหาที่มีโครงสร้างย่อยพิเศษ (ปัญหาย่อยที่เหมือนกัน, ความสมมาตร)
- สามารถรวมเข้ากับการแตกแขนงและขอบเขต (branch-and-bound) สำหรับโปรแกรมจำนวนเต็ม (branch-and-price)
การประยุกต์ใช้
- ปัญหาการตัดสต็อก: การลดของเสียเมื่อตัดวัสดุให้ได้ขนาดที่ต้องการ
- การจัดเส้นทางยานพาหนะ: การหาเส้นทางที่เหมาะสมที่สุดสำหรับการจัดส่งและการขนส่งโดยมีช่วงเวลาและข้อจำกัดด้านความจุ
- การจัดตารางเวลาลูกเรือ: การมอบหมายลูกเรือให้กับเที่ยวบินหรือกะทำงานโดยลดต้นทุนรวมให้เหลือน้อยที่สุด
- การบรรจุกล่อง: การบรรจุสิ่งของลงในภาชนะอย่างมีประสิทธิภาพเพื่อลดของเสียและจำนวนภาชนะ
- การจัดตารางเวร: การจัดตารางการทำงานของพนักงานในแต่ละกะโดยคำนึงถึงความพร้อมใช้งานและความชอบ
- การวางแผนสายการบิน: การจัดตารางเที่ยวบิน การมอบหมายลูกเรือ และการประสานงานการบำรุงรักษาอากาศยาน
วิธีการทำงาน
วิธีการทำงาน
เริ่มต้นด้วยปัญหาส่วนหลักแบบจำกัดที่มีเพียงชุดย่อยของคอลัมน์ที่จำเป็นสำหรับผลลัพธ์ที่เป็นไปได้เริ่มต้น
แก้ปัญหาคู่ของปัญหาส่วนหลักแบบจำกัดปัจจุบันโดยใช้ตารางซิมเพล็กซ์ ระบุต้นทุนลดลงและตั้งค่าปัญหาย่อยการกำหนดราคาเพื่อค้นหาตัวแปรที่มีต้นทุนลดลงเป็นลบ (สำหรับการทำให้มีค่าน้อยที่สุด)
แก้ปัญหาย่อยการกำหนดราคาโดยใช้โครงสร้างพิเศษของมัน หากพบคอลัมน์ใหม่ที่มีต้นทุนลดลงเป็นลบ ให้เพิ่มลงในปัญหาส่วนหลักและทำซ้ำ หากไม่มีคอลัมน์ที่ปรับปรุงได้ ผลลัพธ์ปัจจุบันคือค่าเหมาะที่สุด
ข้อผิดพลาดที่พบบ่อย
- การเลือกอัลกอริทึมปัญหาย่อยการกำหนดราคาที่ไม่มีประสิทธิภาพ ทำให้ประสิทธิภาพที่ได้จากการสร้างคอลัมน์ลดลง
- การไม่ตระหนักถึงโครงสร้างปัญหาที่เอื้อต่อการแยกส่วน ส่งผลให้ประสิทธิภาพไม่ดี
- การตรวจจับการลู่เข้าไม่เพียงพอหรือความคลาดเคลื่อนที่เข้มงวดเกินไป ทำให้เสียการวนซ้ำโดยเปล่าประโยชน์
- การไม่นำเทคนิคการทำให้เสถียรมาใช้เพื่อแก้ไขผลกระทบของการลดลงช้า
คำถามที่พบบ่อย
ปัญหาการกำหนดราคาในการสร้างคอลัมน์คืออะไร และเกี่ยวข้องกับต้นทุนลดลงอย่างไร?
ปัญหาการกำหนดราคาจะระบุตัวแปรใหม่ (คอลัมน์) ที่มีต้นทุนลดลงเป็นลบซึ่งช่วยปรับปรุงผลลัพธ์หลัก ค่าต้นทุนลดลงมาจากปัญหาคู่ของปัญหาส่วนหลักแบบจำกัด และเป็นแนวทางในการค้นหาในปัญหาย่อยการกำหนดราคา
เหตุใดการสร้างคอลัมน์จึงดีกว่าการแก้ปัญหาเต็มรูปแบบด้วยคอลัมน์ทั้งหมด?
ในหลายปัญหา จำนวนคอลัมน์ที่เป็นไปได้มีจำนวนมากแบบเลขชี้กำลังหรือเป็นอนันต์ ทำให้ไม่สามารถแจกแจงทั้งหมดได้ การสร้างคอลัมน์จะสร้างเฉพาะคอลัมน์ที่จำเป็นเมื่อต้องการเท่านั้น ซึ่งช่วยลดภาระการคำนวณลงอย่างมาก
ผลกระทบของการลดลงช้าคืออะไร และจะบรรเทาได้อย่างไร?
การลดลงช้าเกิดขึ้นเมื่อการสร้างคอลัมน์มีความคืบหน้าช้าเมื่อใกล้ค่าเหมาะที่สุด โดยสร้างคอลัมน์จำนวนมากที่มีการปรับปรุงเพียงเล็กน้อย เทคนิคการทำให้เสถียร (การปรับเรียบค่าคู่, วิธีขอบเขตความเชื่อมั่น, กลยุทธ์การตัดออก) ช่วยลดผลกระทบนี้ได้
Branch-and-price ขยายการสร้างคอลัมน์ไปสู่การโปรแกรมจำนวนเต็มได้อย่างไร?
Branch-and-price รวมการสร้างคอลัมน์เข้ากับการแตกแขนงและขอบเขต: ที่แต่ละโหนด การสร้างคอลัมน์จะแก้ปัญหาการผ่อนคลาย LP และการตัดสินใจแตกแขนงจะจำกัดปัญหาเพิ่มเติมเมื่อผลลัพธ์ LP เป็นเศษส่วน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วGilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว