นักวิจัยค้นพบวิธีประมวลผล Integer Linear Programming ให้เร็วขึ้น
(quantamagazine.org)- Victor Reis และ Thomas Rothvoss เสนออัลกอริทึมใหม่ที่ช่วยลดเวลารันของ ILP ลงอย่างมาก สำหรับปัญหา optimization ที่ต้องใช้ การตัดสินใจเป็นหน่วยจำนวนเต็ม เช่น การวางแผนการผลิต การจัดตารางลูกเรือ และการกำหนดเส้นทางยานพาหนะ
- ILP ยากกว่า linear programming ทั่วไป และแทบไม่มีการปรับปรุงระดับสถิตินับตั้งแต่ทศวรรษ 1980 ทำให้ผลลัพธ์ครั้งนี้ถูกมองว่าเป็น ความก้าวหน้าครั้งใหญ่ในรอบหลายสิบปี
- แนวทางใหม่นี้ผสาน เครื่องมือทางเรขาคณิต ที่จัดการจุดตัดระหว่าง lattice กับ convex body เพื่อบีบช่วงของคำตอบจำนวนเต็มที่เป็นไปได้ให้แคบลงอย่างเข้มงวดขึ้น
- แก่นสำคัญคือการใช้ผลลัพธ์ปี 2016 เกี่ยวกับ lattice point เพื่อลดขอบเขตบนของ covering radius และทำให้เวลารันลดลงมาอยู่ในระดับ ((\log n)^{O(n)})
- แม้ยังไม่ได้นำไปใช้กับระบบโลจิสติกส์จริงโดยตรง แต่เป็นผลลัพธ์ที่เข้าใกล้ขีดจำกัดความเร็วเชิงทฤษฎีของ ILP มาก และชี้ทิศทางระยะยาวสำหรับการปรับปรุง solver ในงานจริง
เหตุผลที่ข้อจำกัดจำนวนเต็มทำให้ optimization ยากขึ้น
- ปัญหา traveling salesman เป็นปัญหาการคำนวณเก่าแก่ที่ต้องหาเส้นทางสั้นที่สุดผ่านหลายเมือง และหากตรวจสอบทุกเส้นทางที่เป็นไปได้ เพียงจำนวนเมืองเพิ่มขึ้นเล็กน้อยก็จะเกินรับไหว
- Linear programming เป็นแบบจำลองทางคณิตศาสตร์ที่ใช้สมการและอสมการเพื่อจัดการชุดผสมที่เป็นไปได้อย่างเป็นระบบ
- ในปัญหา optimization ในโลกจริง คำตอบที่เป็นทศนิยมมักใช้ไม่ได้
- ในแผน optimization ของโรงงาน คำตอบที่ให้ผลิตโซฟา 500.7 ตัวนั้นนำไปใช้เป็นการตัดสินใจจริงได้ยาก
- Integer Linear Programming (ILP) คือรูปแบบหนึ่งของ linear programming ที่มีข้อจำกัดจำนวนเต็มเช่นนี้ และถูกใช้กันอย่างแพร่หลายในปัญหาการตัดสินใจแบบไม่ต่อเนื่อง เช่น การวางแผนการผลิต การจัดตารางลูกเรือสายการบิน และการกำหนดเส้นทางยานพาหนะ
- Santosh Vempala มองว่า ILP เป็นเครื่องมือสำคัญของ operations research ทั้งในเชิงทฤษฎีและการใช้งานจริง
ขีดจำกัดความเร็วที่ปรับปรุงช้าหลังทศวรรษ 1980
- หลังจาก ILP ถูกทำให้เป็นรูปแบบอย่างเป็นทางการเมื่อกว่า 60 ปีก่อน ก็มีอัลกอริทึมหลายแบบเกิดขึ้น แต่เมื่อวัดจากจำนวนขั้นตอนที่ต้องใช้ก็ยังถือว่าค่อนข้างช้า
- จุดอ้างอิงที่ง่ายที่สุดคือกรณี ตัวแปรไบนารี ซึ่งตัวแปรมีค่าได้เพียง 0 หรือ 1
- ตัวแปร 1 ตัวมีชุดผสมที่เป็นไปได้ 2 แบบ
- ตัวแปร 2 ตัวมี 4 แบบ
- ตัวแปร 3 ตัวมี 8 แบบ
- โดยทั่วไป เวลารันจะเพิ่มขึ้นแบบเอ็กซ์โปเนนเชียลตามจำนวนตัวแปร หรือก็คือตามมิติ
- หากตัวแปรมีค่าจำนวนเต็มได้กว้างกว่าแค่ 0 และ 1 เวลารันจะยิ่งยาวขึ้นมาก
- นักวิจัยสำรวจมานานแล้วว่าจะทำให้ ILP ทั่วไปมีความเร็วใกล้เคียงกับกรณีไบนารีแบบง่ายนี้มากขึ้นได้หรือไม่
- หลังสถิติในทศวรรษ 1980 ก็มีเพียงการปรับปรุงแบบค่อยเป็นค่อยไปเท่านั้น
การตีความเชิงเรขาคณิตที่ Lenstra เปิดทางไว้
- ในปี 1983 Hendrik Lenstra พิสูจน์ว่าปัญหา ILP ทั่วไปสามารถแก้ได้ และเสนออัลกอริทึมแรกสำหรับเรื่องนี้
- Lenstra แปลง ILP ให้เป็น ปัญหาเชิงเรขาคณิต
- อสมการของ ILP ถูกแทนด้วยรูปทรงนูน หรือ convex body
- ภายในรูปทรงสอดคล้องกับค่าที่เป็นไปได้ทั้งหมดซึ่งทำให้อสมการเป็นจริง
- ปัญหาที่มีตัวแปร 2 ตัวเป็นรูปหลายเหลี่ยมบนระนาบ ส่วนปัญหาที่มีตัวแปร 3 ตัวเป็นรูปทรงสามมิติ และมิติก็เพิ่มขึ้นในลักษณะนี้
- จำนวนเต็มทั้งหมดสามารถมองทางคณิตศาสตร์ว่าเป็นจุดของ lattice ได้
- ในสองมิติจะดูเหมือนทะเลของจุดจำนวนมาก
- ในสามมิติจะกลายเป็นโครงสร้างคล้ายจุดตัดของโครงเหล็กอาคาร
- ท้ายที่สุด การแก้ ILP จึงกลายเป็นปัญหาการหาจุดตัดระหว่าง convex body กับ lattice หรือหาตำแหน่งที่คำตอบที่เป็นไปได้ไปตรงกับจุดจำนวนเต็ม
- อัลกอริทึมของ Lenstra สามารถสำรวจปริภูมินี้ได้ แต่เพื่อประสิทธิภาพ บางครั้งต้องแบ่งปัญหาออกเป็นชิ้นส่วนที่มีมิติต่ำกว่า และกระบวนการนี้ทำให้เวลารันเพิ่มขึ้น
covering radius ที่เป็นคอขวดนาน 30 ปี
- ในปี 1988 Ravi Kannan และ László Lovász พยายามจัดการจุดตัดระหว่าง convex body กับ lattice ให้มีประสิทธิภาพขึ้น โดยใช้แนวคิด covering radius ที่นำมาจากงานวิจัยด้านรหัสแก้ไขข้อผิดพลาด
- covering radius เกี่ยวข้องกับขนาดที่รับประกันว่าไม่ว่าจะวาง convex body ไว้ตำแหน่งใดบน lattice ก็จะมีจุดจำนวนเต็มอย่างน้อยหนึ่งจุดอยู่ภายใน
- ขนาดของค่านี้เป็นตัวกำหนดว่าจะสามารถแก้ปัญหา ILP ได้มีประสิทธิภาพเพียงใด
- การหาขนาด covering radius ในอุดมคตินั้นเป็นปัญหาที่ยากในตัวเอง
- Kannan และ Lovász จำกัดช่วงค่าที่เป็นไปได้ด้วยขอบเขตบนและขอบเขตล่าง และแสดงให้เห็นว่าขอบเขตบนเติบโตเป็นเชิงเส้นตามมิติ
- ผลลัพธ์นี้เพียงอย่างเดียวยังไม่เพียงพอที่จะลดเวลารันของ ILP ลงอย่างมาก และตลอด 30 ปีหลังจากนั้น ระดับการปรับปรุงก็มีจำกัด
อัลกอริทึมใหม่ของ Reis และ Rothvoss
- Victor Reis และ Thomas Rothvoss สร้างจุดพลิกผันด้วยการใช้ผลลัพธ์ทางคณิตศาสตร์อีกชุดหนึ่งที่มุ่งเน้น lattice
- ในปี 2016 Oded Regev และ Noah Stephens-Davidowitz แสดงให้เห็นว่ามี lattice point อยู่ภายในรูปทรงบางแบบได้มากเพียงใด
- Reis และ Rothvoss นำผลลัพธ์นี้ไปใช้กับรูปทรงอื่น ๆ เพื่อประมาณจำนวน lattice point ที่อยู่ภายใน covering radius ของ ILP ได้ดีขึ้น
- การประมาณนี้ทำให้ ขอบเขตบนลดลง และเวลารันรวมของอัลกอริทึม ILP ลดลงอย่างมาก
- เวลารันใหม่คือ ((\log n)^{O(n)}) โดยที่ (n) คือจำนวนตัวแปร และ (O(n)) แปรผันแบบเชิงเส้นตาม (n)
- นิพจน์นี้ถือว่าอยู่ในระดับ “เกือบ” เท่ากับเวลารันของปัญหาตัวแปรไบนารี
ระยะห่างระหว่างความสำเร็จเชิงทฤษฎีกับการใช้งานจริง
- Noah Stephens-Davidowitz มองว่าอัลกอริทึมใหม่นี้เป็นการปรับปรุงครั้งสำคัญครั้งแรกของ ILP solver ในรอบเกือบ 40 ปี
- Daniel Dadush ประเมินว่าผลลัพธ์นี้เป็นความสำเร็จที่เกิดจากจุดตัดของคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเรขาคณิต
- อัลกอริทึมใหม่นี้ยังไม่ได้ถูกใช้เพื่อแก้ปัญหาโลจิสติกส์จริง
- การอัปเดตโปรแกรมปัจจุบันให้เข้ากับวิธีนี้ยังต้องใช้แรงงานจำนวนมาก
- Rothvoss มองว่าจุดโฟกัสของผลลัพธ์ครั้งนี้อยู่ที่ ความเข้าใจเชิงทฤษฎี ต่อปัญหาที่มีการประยุกต์ใช้พื้นฐาน
- ยังมีความเป็นไปได้ที่ประสิทธิภาพการคำนวณของ ILP จะดีขึ้นอีก แต่ Vempala มองว่าหากต้องการเข้าใกล้เวลารันในอุดมคติมากขึ้น จำเป็นต้องมีไอเดียใหม่ในระดับรากฐาน
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
การลดขอบบนเชิงอัลกอริทึมของปัญหา NP-complete แกนหลักนั้นน่าสนใจมากเสมอ แต่ก็ไม่ได้หมายความว่าปัญหานั้นจะถูกแก้ได้เร็วขึ้นในการใช้งานจริงเสมอไป
ตัวแก้ Mixed Integer Programming (MIP) ใช้อัลกอริทึมจำนวนมากร่วมกับฮิวริสติกปริมาณมหาศาล และการสั่งสมคลังฮิวริสติกกับกลยุทธ์นี่เองคือเหตุผลสำคัญที่ทำให้การพัฒนาตัวแก้ MIP แซงกฎของ Moore มาได้
ตาม https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6... ระบุว่าในช่วงปี 1990~2014 การพัฒนาด้านฮาร์ดแวร์ดีขึ้น 6500 เท่า แต่ซอฟต์แวร์มีส่วนช่วยเพิ่มประสิทธิภาพถึง 870000 เท่า
งานวิจัยชิ้นนี้อาจเป็นอีกชิ้นส่วนหนึ่งของปริศนาที่ช่วยยกระดับประสิทธิภาพของตัวแก้ MIP ต่อไปได้ แต่ก็ไม่ได้รับประกันว่าจะเป็นเช่นนั้น
ยังไม่ค่อยเข้าใจคำอธิบายที่ว่าเหตุผลที่อัลกอริทึมใหม่นี้ยังไม่ถูกใช้แก้ปัญหาโลจิสติกส์ เป็นเพราะ “ทุกวันนี้การอัปเดตโปรแกรมต้องใช้แรงงานมากเกินไป”
โมเดลเฉพาะโดเมนส่วนใหญ่มักเรียกใช้ตัวแก้ Gurobi, CPLEX, FICO สำหรับปัญหาขนาดใหญ่ และใช้ตัวแก้โอเพนซอร์สอย่าง SCIP สำหรับปัญหาขนาดเล็ก
เราสามารถแลกเปลี่ยนโมเดลระหว่างตัวแก้เหล่านี้ผ่าน ฟอร์แมต MPS มาตรฐาน ได้ โดยตัวการจัดรูปปัญหาไม่ต้องเปลี่ยน และเปลี่ยนแค่วิธีแก้ภายในของตัวแก้เท่านั้นไม่ใช่หรือ
ถ้าหมายความว่าต้องมีการพัฒนา implementation ใหม่จริง ๆ ผลประโยชน์ที่โลกจะได้จากการทำเช่นนั้นก็น่าจะมหาศาลมาก
เครื่องมือเหล่านี้เป็นผลผลิตทางวิศวกรรมที่ซับซ้อนมากจากการปรับปรุงทีละน้อยสะสมมาหลายทศวรรษ ดังนั้นแค่หาวิธีผสานงานค้นพบใหม่นี้เข้าไปในเอนจินเหล่านี้ก็น่าจะต้องใช้ความพยายามวิจัยมากพอสมควรแล้ว
จริงอยู่ที่มีวิธีมาตรฐานสำหรับแลกเปลี่ยนการจัดรูปปัญหาผ่านฟอร์แมตอย่าง MPS และทุกวันนี้ก็ดูเหมือนจะใช้ภาษาสร้างแบบจำลองเชิงพีชคณิตอย่าง AMPL กันมากกว่า แต่สิ่งที่ฟอร์แมตเหล่านั้นให้มีเพียงการจัดรูปทางคณิตศาสตร์แบบมาตรฐานเท่านั้น
การแก้จริงนั้นเฉพาะทางมากสำหรับตัวแก้แต่ละตัว และแต่ละตัวก็มีโครงสร้างข้อมูล อัลกอริทึม และเทคนิคฮิวริสติกของตัวเอง
สิ่งเหล่านี้ไม่สามารถสลับแทนกันได้ และก็ไม่ได้เปิดเผยไว้อย่างจงใจด้วย อีกทั้งคุณไม่สามารถเอาตัวเลขภายนอกไม่กี่ตัวมาแทรกกลางทางได้หากไม่มีความรู้เกี่ยวกับโค้ดของตัวแก้และกระบวนการทั้งหมด
แค่อยากช่วยคลายความเข้าใจผิด
ถ้าเป็นไปได้ก็มักอยากหลีกเลี่ยงการไปลงมือพัฒนาด้วยของพวกนั้นโดยตรง
ถึงอย่างนั้นก็ไม่ได้ทำให้ผลลัพธ์นี้ด้อยลงแต่อย่างใด
ในมุมมองของความซับซ้อนเชิงคำนวณเชิงทฤษฎี อัลกอริทึมที่ดีที่สุดสำหรับ “การโปรแกรมเชิงเส้นจำนวนเต็ม” [2] นั้นอิงกับ lattice และมี big-O ในกรณีเลวร้ายที่สุดที่ดีที่สุด
แต่ implementation ในปัจจุบันส่วนใหญ่มัก (1) ต้องใช้การคำนวณจำนวนตรรกยะขนาดไม่จำกัดอย่าง gmplib [3] ซึ่งกินหน่วยความจำมากและช้าในทางปฏิบัติ และ (2) ต้องมีขั้นตอนลดรูป lattice ตระกูล LLL [4] แต่กลับใช้ประโยชน์จากความ sparse ของเมทริกซ์ไม่ได้
ผลคืออัลกอริทึมเหล่านี้มักใส่หน่วยความจำไม่พอสำหรับเมทริกซ์ที่ใหญ่กว่า 1000x1000 จนเริ่มทำงานไม่ได้ด้วยซ้ำ และถึงจะพอใส่ได้ก็ช้าเกินไป
ตัวแก้ integer programming ที่ใช้ในงานจริงจึงอาศัย branch and bound ซึ่งเป็นอัลกอริทึมย้อนรอยคล้ายกับที่ใช้ในการแก้ SAT แทน และในแต่ละรอบจะไปแก้ปัญหา “linear programming” ที่ได้จากการเปลี่ยนตัวแปรทั้งหมดในปัญหาเดิมให้เป็นตัวแปรต่อเนื่อง
ปัญหา linear programming แต่ละอันสามารถแก้ได้ด้วยอัลกอริทึมเวลาเชิงพหุนามอย่าง interior point method แต่ในทางปฏิบัติกลับใช้ simplex method ซึ่งมีเวลาแบบเอ็กซ์โพเนนเชียลในกรณีเลวร้ายที่สุด
เหตุผลคือปัญหา linear programming ที่ต้องแก้เหล่านั้นคล้ายกันมาก และ simplex method ใช้ประโยชน์จากจุดนี้ได้ดีในงานจริง
นอกจากนี้อัลกอริทึมที่เกี่ยวข้องยังใช้ประโยชน์จากความ sparse ของเวกเตอร์และเมทริกซ์ได้มากด้วย
ด้วยเหตุนี้บางคนจึงสามารถแก้ปัญหา integer programming ที่มีตัวแปรนับเป็นหลักล้านได้ภายในไม่กี่วัน หรือแม้แต่ไม่กี่ชั่วโมง
ผู้พัฒนาตัวแก้ไม่ได้ไล่ตามความซับซ้อนเชิงทฤษฎีที่ดีที่สุดแบบสัมบูรณ์ และอาจกล่าวได้ว่าทฤษฎีกับภาคปฏิบัติของ discrete optimization แยกทางกันไปพอสมควรแล้ว
ถึงอย่างนั้น งานของ Reis & Rothvoss [1] ก็เป็นผลงานคณิตศาสตร์เชิงลึก และสำหรับคนที่สนใจคณิตศาสตร์เชิงไม่ต่อเนื่อง มันน่าประทับใจมากในตัวมันเอง
มันแก้ข้อคาดเดาอายุ 10 ปีของ Dadush และถูกนำเสนอเมื่อเดือนพฤศจิกายนปีก่อนใน FOCS ซึ่งเป็นหนึ่งในสองงานประชุมชั้นนำสูงสุดของสายทฤษฎีวิทยาการคอมพิวเตอร์
ประโยชน์ใช้สอยโดยตรงไม่ใช่ประเด็นหลัก และผู้เขียนเองก็คงยอมรับเช่นนั้นในการพูดคุยนอกทางการ
แน่นอนว่าในคำขอทุนวิจัยอาจพูดอีกแบบ แต่ก็เป็นส่วนหนึ่งของเกม
นั่นไม่ได้แปลว่ามันไร้ประโยชน์ เพราะเพียงแค่ทำให้ความรู้ทางคณิตศาสตร์ก้าวหน้าขึ้นก็มีคุณค่าอย่างมากแล้ว และอีกหลายรุ่นต่อจากนี้ นักวิจัยอาจนำแนวคิดนี้ไปต่อยอดสร้างอัลกอริทึมที่ใช้ได้จริง เพื่อผลักดันแนวหน้าของตัวแก้ให้ก้าวไปไกลขึ้นก็ได้
ท้ายที่สุดแล้วอัลกอริทึมเหล่านี้ทั้งหมดก็ใช้เวลาแบบเอ็กซ์โพเนนเชียลในกรณีเลวร้ายที่สุด
ในทางทฤษฎีผู้คนอาจพยายามลดพหุนามที่อยู่ในเลขชี้กำลังของความซับซ้อนกรณีเลวร้ายที่สุดลงเล็กน้อย แต่ผู้ใช้งานจริงมักไม่ได้ต้องการแก้ตระกูลปัญหาที่ขนาด n โตขึ้นเรื่อย ๆ พวกเขาแค่อยากแก้ปัญหา optimization ขนาดใหญ่ปัญหาเดียว
สิ่งสำคัญไม่ใช่อัตราการเติบโตของเส้นแนวโน้มเวลาในการแก้ แต่คือจะแก้อินสแตนซ์ขนาดใหญ่ตรงหน้าตัวเองได้หรือไม่ และอินสแตนซ์นั้นก็มักมีโครงสร้างที่ช่วยไม่ให้มันกลายเป็นกรณีเลวร้ายที่สุดสำหรับขนาดเดียวกัน
ดังนั้นการเลือกเชิงวิศวกรรมจึงต่างออกไปด้วย
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
บทคัดย่อน่าจะมีประโยชน์มากกว่า: https://arxiv.org/abs/2303.14605
ใจความคือได้อัลกอริทึมแบบสุ่มที่ใช้เวลา (log(2n))^O(n) สำหรับการแก้ปัญหาโปรแกรมเชิงจำนวนเต็มที่มีตัวแปร n ตัว
กล่าวคือ งานนี้เป็นผลลัพธ์เชิงทฤษฎี โดยอาศัยการวิเคราะห์โครงสร้างของวัตถุนูนใน R^n และวิธีปกคลุมมันด้วยแลตทิซจำนวนเต็ม เพื่อนำเสนออัลกอริทึมเวลาเอ็กซ์โปเนนเชียลที่ดีกว่าวิธีที่ดีที่สุดก่อนหน้า
งาน ILP เชิงปฏิบัติส่วนใหญ่ใช้ฮิวริสติกและ branch-and-bound และอาศัยโครงสร้างพิเศษของการตั้งปัญหาเฉพาะกรณี
ยังไม่ชัดเจนว่างานวิจัยนี้จะช่วยกับสองอย่างนั้นได้หรือไม่ และถ้าไม่มีใครจากที่อย่าง Gurobi มาอธิบาย ก็คงตัดสินจากการอ่านแค่ตัวงานวิจัยได้ยาก
เป็นข้อทักท้วงเล็กน้อย แต่ในชื่อเรื่องควรระบุให้ชัดว่าเป็น โปรแกรมเชิงเส้นจำนวนเต็ม
เพราะตรงนี้ส่วน “จำนวนเต็ม” สร้างความแตกต่างอย่างมาก
โปรแกรมเชิงเส้นนั้นมีอัลกอริทึมเวลาเชิงพหุนามที่รู้จักกันมาหลายสิบปีแล้ว และ โปรแกรมเชิงเส้นจำนวนเต็ม เป็นปัญหาแบบ NP-hard
โปรแกรมเชิงเส้นแบบต่อเนื่องก็ยากเหมือนกัน
ไม่ได้หมายความว่าเป็น NP-hard แต่หมายความว่าการสร้าง LP solver สมัยใหม่ที่มีประสิทธิภาพต้องอาศัยทั้งด้านอัลกอริทึมและวิศวกรรมอย่างมาก
แค่การคำนวณเชิงตัวเลขก็ซับซ้อนมากพอแล้ว
และตัวแก้ปัญหาโปรแกรมเชิงเส้นจำนวนเต็มจำนวนมากก็สร้างอยู่บนพื้นฐานของตัวแก้ปัญหาโปรแกรมเชิงเส้นแบบต่อเนื่อง
ถ้าเป็นวิศวกรซอฟต์แวร์ที่สนใจแมชชีนเลิร์นนิงหรืออัลกอริทึม ก็คุ้มที่จะลองเรียน โปรแกรมเชิงเส้น
มีปัญหาจำนวนมากอย่างน่าประหลาดที่สามารถตั้งรูปเป็นการหาค่าเหมาะที่สุดเชิงเส้นได้
ตัวอย่างเช่น ตอนเรียนมหาวิทยาลัยเคยคุยกับเพื่อนที่เรียนวิศวกรรมอุตสาหการเรื่องจำนวนครั้งสลับตำแหน่งขั้นต่ำโดยเฉลี่ยที่ต้องใช้เพื่อวางลูกบิลเลียดให้อยู่ในตำแหน่งเริ่มต้นที่เป็นไปได้ภายในสามเหลี่ยมของแร็ก
เราทั้งคู่เขียนโปรแกรมแก้ด้วยการสุ่มตัวอย่างแบบ Monte Carlo โดยวิธีของผมใช้ BFS บน state space ของกราฟ ส่วนของเพื่อนใช้โปรแกรมเชิงเส้น
เดาว่าของเพื่อนน่าจะมีประสิทธิภาพมากกว่า
ตัวอย่างเช่น ต้นไม้ทอดข้ามที่มีค่าน้ำหนักต่ำสุด, การจับคู่ในกราฟสองส่วนหรือกราฟทั่วไป, network flow, matroid intersection และ submodular flow
คำตอบที่เป็นจุดยอดของ LP บางชนิดยังมีคุณสมบัติที่น่าสนใจซึ่งนำไปใช้ในการออกแบบอัลกอริทึมประมาณค่าสำหรับปัญหา NP-complete ได้
เช่น สำหรับปัญหา Steiner forest สามารถพิสูจน์ได้ว่าคำตอบแบบจุดยอดจะมีตัวแปรที่มีค่าอย่างน้อย 1/2 อยู่เสมอ ดังนั้นถ้าปัดเศษตัวแปรซ้ำ ๆ แล้วแก้ LP ใหม่ ก็จะได้อัลกอริทึมประมาณค่า 2 เท่า
ตอนเรียนบัณฑิตศึกษานี่เป็นอัลกอริทึมประมาณค่า 2 เท่าเพียงตัวเดียวที่ปัญหานี้มี
อีกจุดที่น่าสนใจก็คือ ถ้ามี separation oracle เวลาเชิงพหุนาม ก็สามารถแก้ LP ได้แม้จะมีข้อจำกัดจำนวนระดับเอ็กซ์โปเนนเชียลก็ตาม
สนุกมากและน่าแนะนำ
แม้ตอนนี้ในสาย operations research ก็มีส่วนที่ทับซ้อนกันมากอย่างน่าประหลาดอยู่แล้ว แต่ก็น่าตกใจที่บัณฑิตวิศวกรรมอุตสาหการจำนวนมากเขียนโปรแกรมอย่างจริงจังไม่เป็น
น่าเสียดายจริง ๆ
โดยทั่วไปซื้อขายกันได้แค่จำนวนเงินจำนวนเต็มระดับเซนต์ ดังนั้นส่วนที่เป็นจำนวนเต็มจึงสำคัญพอสมควรเท่าที่จำได้
เป็นโพสต์สั้น ๆ แต่ดี
ยังไม่ได้ลงลึกในคณิตศาสตร์มากนัก แต่พรีปรินต์น่าจะเป็นอันนี้: https://arxiv.org/pdf/2303.14605.pdf
ดูเหมือนจะไม่ได้มองที่ space group โดยตรง แต่เป็นการทำให้ “พื้นที่” ของปัญหาง่ายขึ้นด้วยการทำให้เป็นนามธรรมเพื่อลดสมมาตรหรือการซ้ำกัน และก็น่าสนใจถ้าจะดูว่าโครงสร้างแบบนั้นจะนำมาใช้ได้หรือไม่
ในฐานะคนที่ใช้ซอฟต์แวร์ซึ่งประยุกต์ space group และอธิบาย Voronoi cell รอบจุดหรือกลุ่มจุดที่กระจายอยู่ในนั้น ผมคุ้นเคยกับวิธีการแพร่กระจายผลกระทบที่ชวน “ขนลุก” แบบนี้ [1]
ผมไม่ใช่นักคณิตศาสตร์ เป็นแค่สถาปนิก ดังนั้นเรื่องนี้เกินขีดความสามารถของผม แต่ในฐานะคนที่กำลังดูเส้นทางผ่านโครงสร้างรวงผึ้งที่ถูกสร้างขึ้น ผลลัพธ์นี้ก็น่าคุ้มแก่การไปสำรวจต่อ
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] ถ้าคุณรู้จักนักคณิตศาสตร์ที่น่าจะมาร่วมงานแนวนี้ได้ ช่วยติดต่อมาด้วยก็ดี
นี่เป็นงานที่กำลังทำอยู่ และอย่างที่บอก ในเชิงคณิตศาสตร์มันเกินขีดความสามารถของผม แต่ผมได้พบคุณสมบัติบางอย่างที่น่าสนใจซึ่งผู้เชี่ยวชาญตัวจริงน่าจะอยากลงลึกกว่านี้
เกี่ยวกับปัญหาพนักงานขายเดินทาง มีคำพูดในหนังสือล่าสุดของ Sapolsky ชื่อ Determined: A Science of Life without Free Will ที่น่าสนใจ
ไม่แน่ใจว่าเกี่ยวข้องกับนักพัฒนาซอฟต์แวร์มากแค่ไหน แต่ชวนติดตามดี
เมื่อมดออกหาอาหารโดยตรวจสอบสถานที่ 8 แห่ง ตามอุดมคติแล้วมันควรไปแต่ละแห่งเพียงครั้งเดียว และเลือกเส้นทางที่สั้นที่สุดจากเส้นทางที่เป็นไปได้ 5,040 แบบ หรือก็คือ 7!
นี่เป็นรูปแบบหนึ่งของ ปัญหาพนักงานขายเดินทาง อันโด่งดัง ที่นักคณิตศาสตร์ครุ่นคิดกันมาหลายศตวรรษโดยยังหาวิธีแก้แบบทั่วไปไม่ได้
กลยุทธ์หนึ่งคือไล่ดูและเปรียบเทียบทุกเส้นทางที่เป็นไปได้แบบ brute force แล้วเลือกเส้นทางที่ดีที่สุด แต่แค่มีจุดแวะ 10 แห่งก็มีวิธีที่เป็นไปได้มากกว่า 360,000 แบบแล้ว และถ้ามี 15 แห่งก็เกิน 80 พันล้านแบบ
แต่ถ้าปล่อยมดในอาณานิคมตามปกติราว 10,000 ตัวไปแก้ปัญหาจุดอาหาร 8 จุดนี้ แม้ว่ามดแต่ละตัวจะรู้เพียงเส้นทางที่ตัวเองเดินและกฎอีกแค่สองข้อ มันก็ยังหาคำตอบที่เกือบเหมาะที่สุดจาก 5,040 แบบได้ในเวลาที่สั้นกว่าการ brute force มาก
วิธีนี้ได้ผลดีจนทำให้นักวิทยาการคอมพิวเตอร์ใช้ “มดเสมือน” แก้ปัญหาลักษณะนี้ด้วย และสิ่งนี้ปัจจุบันเรียกว่า ปัญญาฝูง
และปฏิกิริยามาตรฐานก็คือ “อัลกอริทึมคอมพิวเตอร์ที่ง่ายมากก็ทำแบบนั้นได้เหมือนกัน”
ในปัญหาพนักงานขายเดินทาง ถ้าอยู่ในกรณีระยะแบบยุคลิด กล่าวคือแต่ละโหนดมีพิกัดคงที่และต้นทุนของเส้นทางคือระยะยุคลิดระหว่างสองจุด ก็ยังมีอัลกอริทึมเวลาเชิงพหุนามที่หาเส้นทางซึ่งอยู่ภายใน ε เท่าของคำตอบที่เหมาะที่สุดได้
เพียงแต่เป็นเลขชี้กำลังเมื่อเทียบกับ ε
และในคำนำก็มีข้อความปฏิเสธความรับผิดชอบที่ยอดเยี่ยมด้วย
“โดยส่วนตัวเราเชื่อว่าวรรณกรรมในสาขานี้ควรมีสัตว์มีกระเป๋าหน้าท้องน้อยลงและมีคณิตศาสตร์มากขึ้น และในฐานะชุมชนเราควรพ้นจากช่วงเวลาอันอุดมด้วยอุปมาเปรียบเทียบนี้ไป เช่นเดียวกับที่เคมีก้าวพ้นจากการเล่นแร่แปรธาตุ อย่างไรก็ตาม รายการนี้ไม่ได้อ้างอะไรเกี่ยวกับคุณภาพทางวิทยาศาสตร์ของงานที่ถูกรวบรวมไว้”
[1]: https://fcampelo.github.io/EC-Bestiary/
เป็นอัลกอริทึมที่จำลองพฤติกรรมของอาณานิคมมดแบบนี้
อย่างที่คนอื่นบอกไว้ มันเหมาะกับการหาคำตอบแบบ local optimum คล้ายกับ tabu search, simulated annealing และ genetic algorithm
สำหรับเป้าหมายทางธุรกิจส่วนใหญ่ เช่นกรณี “การผลิตโซฟา” ที่ยกมาในบทความ แค่นี้ก็เพียงพอแล้ว
แต่มันไม่เหมือนกับการหาวิธีแก้แบบ “ทั่วไป”
การที่ Sapolsky เปรียบเทียบความที่เราไม่ค่อยหาวิธีแก้แบบ “ทั่วไป” ได้ดี กับความสามารถของมดในการหาคำตอบแบบ local optimum ดูจะชวนให้เข้าใจผิดอยู่บ้าง
ไม่ได้หมายความว่ารูปแบบทั่วไปของปัญหาจะไม่เป็น NP-hard แต่หมายความว่าเมื่อเพิ่มข้อมูลเข้าไปมากพอ ก็อาจทำให้สามารถประมาณคำตอบที่ดีพอ หรือจัดการกับการค้นหาแบบเหมาะที่สุดได้
มุมมองแบบนี้โดดเด่นมากเป็นพิเศษในช่วง “การปฏิวัติ” AI ครั้งแรก และแนวคิดที่มอง AI เป็นปัญหาการค้นหาที่เสริมด้วยความรู้ของมนุษย์ก็ได้รับความนิยม
นี่คือสิ่งที่หนังสือต้องการจะสื่อด้วยคำว่า “ปัญญาฝูง” หรือเปล่า?
ปัญหา การหาค่าเหมาะที่สุดแบบไม่ต่อเนื่อง จำนวนมากสามารถแปลงเป็นการโปรแกรมเชิงเส้นได้
มันเป็นเครื่องมือที่ทรงพลังมากถ้ารู้จักใช้ เหมือน SAT solver
สำหรับนักพัฒนาแล้ว มันเป็นหนึ่งในช่วงเวลาที่รู้สึกว่า “ฉันพลาดสิ่งนี้มาได้อย่างไรจนถึงตอนนี้?”
เป็นผลลัพธ์ที่ยอดเยี่ยม แต่คงไม่ค่อยใช้งานได้จริงนัก
คล้ายกับใน linear programming ที่ interior-point method มีความซับซ้อนเชิงทฤษฎีดีกว่า simplex method แต่ในโลกจริง simplex ที่จูนมาดีมักชนะเกือบตลอด
มี “เหตุผล” ที่เป็นที่ยอมรับกันกว้างขวางไหมว่าทำไม interior-point method จึงมักช้ากว่าในการใช้งานจริง?
มันเหมือนว่าการวิ่งผ่านด้านในน่าจะเข้าถึงคำตอบที่ดีได้เร็วกว่า แทนที่จะถูกผูกไว้กับขอบเขต แต่ก็อาจเป็นไปได้ว่าในมิติสูง ความต่างนั้นไม่สำคัญเท่าไร
ถ้อยคำที่ใช้ตรงนี้ค่อนข้างชวนสับสน
มีประโยคว่า “เวอร์ชันที่ดีที่สุดที่พวกเขาคิดค้นขึ้นมา ซึ่งเป็นเหมือนข้อจำกัดด้านความเร็วชนิดหนึ่ง มาจากกรณีง่าย ๆ ที่ตัวแปรของปัญหารับได้แค่ค่าแบบไบนารี คือ 0 หรือ 1 เช่น การที่พนักงานขายจะไปเยือนเมืองหนึ่งหรือไม่” ตกลงเขากำลังเรียก ปัญหา NP-complete ว่าเป็นกรณีง่ายหรือ?
เท่าที่ผมเข้าใจ ILP ทุกแบบลดรูปเป็น 01-ILP ได้ และกลับกันก็ได้เช่นกัน
อีกทั้งเมื่อดูข้อความที่ว่า “น่าเสียดายที่เมื่อค่าของตัวแปรไปไกลกว่า 0 และ 1 เวลาในการรันของอัลกอริทึมจะนานขึ้นมาก นักวิจัยสงสัยกันมานานแล้วว่าจะขยับเข้าใกล้อุดมคติแบบง่าย ๆ นี้ได้หรือไม่” ก็เลยสงสัยว่างานวิจัยนี้เป็น solver ที่ปรับปรุง lower bound ของ 01-ILP หรือเป็นอัลกอริทึมที่ทำให้เส้นแบ่งระหว่าง 01-ILP กับ ILP ทั่วไปแคบลงกันแน่