การเพิ่มประสิทธิภาพเชิงการจัดเรียงเป็นสาขาย่อยของการเพิ่มประสิทธิภาพทางคณิตศาสตร์ ที่ประกอบด้วยการค้นหาวัตถุที่เหมาะสมที่สุดจากเซตของวัตถุ ที่มีจำนวนจำกัด ^{[ 1 ]}โดยที่เซตของคำตอบที่เป็นไปได้นั้นเป็นแบบไม่ต่อเนื่องหรือสามารถลดให้เหลือเซตแบบไม่ต่อเนื่องได้ ปัญหาการเพิ่มประสิทธิภาพเชิงการจัดเรียงทั่วไป ได้แก่ปัญหาพนักงานขายเดินทาง ("TSP"), ปัญหาต้นไม้ครอบคลุมขั้นต่ำ ("MST") และปัญหาเป้สะพายหลังในปัญหาดังกล่าวจำนวนมาก เช่น ปัญหาที่กล่าวถึงข้างต้นการค้นหาแบบครบถ้วนไม่สามารถทำได้ ดังนั้นจึงต้องใช้อัลกอริธึมเฉพาะทางที่ตัดส่วนใหญ่ของพื้นที่การค้นหาออกไปอย่างรวดเร็ว หรืออัลกอริธึมการประมาณค่าแทน

การเพิ่มประสิทธิภาพเชิงการจัดเรียง (Combinatorial optimization) เกี่ยวข้องกับการวิจัยเชิงปฏิบัติการทฤษฎีอัลกอริทึมและทฤษฎีความซับซ้อนของการคำนวณมีการประยุกต์ใช้ที่สำคัญในหลายสาขา รวมถึงปัญญาประดิษฐ์การเรียนรู้ของเครื่องทฤษฎีการประมูลวิศวกรรมซอฟต์แวร์ VLSI คณิตศาสตร์ประยุกต์และวิทยาศาสตร์ คอมพิวเตอร์เชิงทฤษฎี

การประยุกต์ใช้พื้นฐานของการเพิ่มประสิทธิภาพเชิงการจัดเรียง ได้แก่ แต่ไม่จำกัดเพียง:

• โลจิสติกส์^{[ 2 ]}
• การเพิ่มประสิทธิภาพห่วงโซ่อุปทาน^{[ 3 ]}
• การพัฒนาระบบเครือข่ายสายการบินที่ดีที่สุด ทั้งเส้นทางบินและจุดหมายปลายทาง
• การตัดสินใจเลือกแท็กซี่คันใดในฝูงเพื่อไปรับผู้โดยสาร
• การกำหนดวิธีการจัดส่งพัสดุที่เหมาะสมที่สุด
• การจัดสรรงานให้บุคคลอย่างเหมาะสมที่สุด
• การออกแบบเครือข่ายการจ่ายน้ำ
• ปัญหาทางวิทยาศาสตร์โลก (เช่น อัตราการไหลของอ่างเก็บน้ำ ) ^{[ 4 ]}

มีงานวิจัยจำนวนมากเกี่ยวกับอัลกอริธึมเวลาพหุนามสำหรับปัญหาการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่องบางประเภทโดยเฉพาะ งานวิจัยส่วนใหญ่ได้รับการรวบรวมไว้ในทฤษฎีการเขียนโปรแกรมเชิงเส้น ตัวอย่างของปัญหาการหา ค่าเหมาะสมที่สุดเชิงการจัดเรียงที่ครอบคลุมโดยกรอบงานนี้ ได้แก่เส้นทางที่สั้นที่สุดและต้นไม้เส้นทางที่สั้นที่สุดการไหลและการหมุนเวียนต้นไม้แผ่ขยายการจับคู่และปัญหา เมทริกซ์

สำหรับ ปัญหาการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่องที่เป็นปัญหา NP-completeงานวิจัยในปัจจุบันครอบคลุมหัวข้อต่อไปนี้:

• กรณีพิเศษของปัญหาที่กำลังพิจารณาซึ่งสามารถแก้ไขได้อย่างแม่นยำในเวลาพหุนาม (เช่นปัญหาที่สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ )
• อัลกอริทึมที่ทำงานได้ดีกับกรณีตัวอย่าง "แบบสุ่ม" (เช่น สำหรับปัญหาพนักงานขายเดินทาง )
• อัลกอริทึมประมาณค่าที่ทำงานในเวลาพหุนามและค้นหาคำตอบที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด
• อัลกอริทึมการประมาณค่าแบบพารามิเตอร์ที่ทำงานใน เวลา FPTและค้นหาคำตอบที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด
• การแก้ปัญหาตัวอย่างในโลกแห่งความเป็นจริงที่เกิดขึ้นในทางปฏิบัติและไม่จำเป็นต้องแสดงพฤติกรรมกรณีที่เลวร้ายที่สุดของปัญหา NP-complete (เช่น ตัวอย่าง TSP ในโลกแห่งความเป็นจริงที่มีโหนดหลายหมื่นโหนด^{[ 5 ]} )

ปัญหาการเพิ่มประสิทธิภาพเชิงการจัดเรียงสามารถมองได้ว่าเป็นการค้นหาองค์ประกอบที่ดีที่สุดของชุดรายการที่ไม่ต่อเนื่องบางชุด ดังนั้นโดยหลักการแล้วอัลกอริทึมการค้นหาหรือเมตาฮิวริสติก ประเภทใดก็ได้ สามารถนำมาใช้แก้ปัญหาได้ แนวทางที่ใช้กันอย่างแพร่หลาย ได้แก่การแบ่งแยกและขอบเขต (อัลกอริทึมที่แม่นยำซึ่งสามารถหยุดได้ทุกจุดเวลาเพื่อใช้เป็นฮิวริสติก) การแบ่งแยกและตัด (ใช้การเพิ่มประสิทธิภาพเชิงเส้นเพื่อสร้างขอบเขต) การเขียน โปรแกรมแบบไดนามิก (การสร้างโซลูชันแบบเรียกซ้ำที่มีหน้าต่างการค้นหาที่จำกัด) และการค้นหาแบบแทบู (อัลกอริทึมการสลับแบบโลภ) อย่างไรก็ตาม อัลกอริทึมการค้นหาทั่วไปไม่รับประกันว่าจะพบโซลูชันที่เหมาะสมที่สุดก่อน และไม่รับประกันว่าจะทำงานได้อย่างรวดเร็ว (ในเวลาพหุนาม) เนื่องจากปัญหาการเพิ่มประสิทธิภาพแบบไม่ต่อเนื่องบางอย่างเป็นNP-completeเช่น ปัญหาพนักงานขายเดินทาง (การตัดสินใจ) ^{[ 6 ]}เป็นสิ่งที่คาดหวังได้เว้นแต่P= NP

สำหรับปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียงแต่ละปัญหา จะมีปัญหาการตัดสินใจ ที่สอดคล้องกัน ซึ่งถามว่ามีวิธีแก้ปัญหาที่เป็นไปได้สำหรับมาตรวัดเฉพาะบางอย่างหรือไม่ตัวอย่างเช่น หากมีกราฟที่มีจุดยอดและปัญหาการหาค่าเหมาะสมที่สุดอาจเป็น "หาเส้นทางจากไปยัง ที่ใช้ขอบน้อยที่สุด" ปัญหานี้อาจมีคำตอบเป็น 4 ปัญหาการตัดสินใจที่สอดคล้องกันจะเป็น "มีเส้นทางจากไปยังที่ใช้ขอบ 10 หรือน้อยกว่าหรือไม่" ปัญหานี้สามารถตอบได้ด้วย "ใช่" หรือ "ไม่ใช่" อย่างง่ายๆ ${\displaystyle m_{0}}$${\displaystyle G}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$

สาขาของอัลกอริธึมการประมาณค่าเกี่ยวข้องกับอัลกอริธึมในการค้นหาคำตอบที่ใกล้เคียงที่สุดสำหรับปัญหาที่ยาก เวอร์ชันการตัดสินใจแบบปกติจึงเป็นคำจำกัดความที่ไม่เพียงพอของปัญหา เนื่องจากระบุเฉพาะคำตอบที่ยอมรับได้เท่านั้น แม้ว่าเราจะสามารถแนะนำปัญหาการตัดสินใจที่เหมาะสมได้ แต่ปัญหาดังกล่าวก็มีลักษณะเฉพาะที่เป็นธรรมชาติมากกว่าในฐานะปัญหาการเพิ่มประสิทธิภาพ^{[ 7 ]}

ปัญหาการเพิ่มประสิทธิภาพ NP ( NPO) เป็นปัญหาการเพิ่มประสิทธิภาพเชิงการจัดเรียงที่มีเงื่อนไขเพิ่มเติมดังต่อไปนี้^{[ 8 ]}โปรดทราบว่าพหุนาม ที่อ้างถึงด้านล่าง เป็นฟังก์ชันของขนาดของอินพุตของฟังก์ชันที่เกี่ยวข้อง ไม่ใช่ขนาดของชุดอินสแตนซ์อินพุตโดยปริยาย

• ขนาดของคำตอบที่เป็นไปได้ทุกคำตอบโดยที่แทนเซตของคำตอบที่เป็นไปได้สำหรับอินสแตนซ์จะถูกจำกัด ด้วยพหุนาม ตามขนาดของอินสแตนซ์ที่กำหนด${\displaystyle y\in f(x)}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle x}$
• ภาษาของตัวอย่างที่ถูกต้องและคู่ตัวอย่าง-คำตอบที่ถูกต้องสามารถรับรู้ได้ในเวลาพหุนามและ${\displaystyle \{\,x\,\mid \,x\in I\,\}}$${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$
• การวัดผลของวิธีแก้ปัญหาสามารถคำนวณได้ในเวลาพหุนาม${\displaystyle m(x,y)}$${\displaystyle y}$${\displaystyle x}$

สิ่งนี้หมายความว่าปัญหาการตัดสินใจที่เกี่ยวข้องอยู่ในNPในวิทยาศาสตร์คอมพิวเตอร์ ปัญหาการเพิ่มประสิทธิภาพที่น่าสนใจมักจะมีคุณสมบัติข้างต้นและดังนั้นจึงเป็นปัญหา NPO ปัญหาจะถูกเรียกว่าปัญหา P-optimization (PO) เพิ่มเติม หากมีอัลกอริทึมที่ค้นหาคำตอบที่เหมาะสมที่สุดในเวลาพหุนาม บ่อยครั้ง เมื่อจัดการกับคลาส NPO เราสนใจปัญหาการเพิ่มประสิทธิภาพซึ่งเวอร์ชันการตัดสินใจเป็นNP-completeโปรดทราบว่าความสัมพันธ์ของความยากจะสัมพันธ์กับการลดรูปบางอย่างเสมอ เนื่องจากความเชื่อมโยงระหว่างอัลกอริทึมการประมาณและปัญหาการเพิ่มประสิทธิภาพการคำนวณ การลดรูปที่รักษาการประมาณไว้ในบางแง่มุมจึงเป็นที่ต้องการมากกว่า การลดรูป TuringและKarp ทั่วไปสำหรับหัวข้อนี้ ตัวอย่างของการลดรูปดังกล่าวคือการลดรูป Lด้วยเหตุนี้ ปัญหาการเพิ่มประสิทธิภาพที่มีเวอร์ชันการตัดสินใจ NP-complete จึงไม่จำเป็นต้องเรียกว่า NPO-complete ^{[ 9 ]}

NPO แบ่งออกเป็นคลาสย่อยต่อไปนี้ตามความสามารถในการประมาณค่า: ^{[ 8 ]}

• NPO(I) : เท่ากับFPTASประกอบด้วยปัญหาKnapsack
• NPO(II) : เท่ากับPTASประกอบด้วยปัญหาการจัดตารางเวลา Makespan
• NPO(III) : กลุ่มของปัญหา NPO ที่มีอัลกอริทึมแบบพหุนามซึ่งคำนวณหาคำตอบโดยมีค่าใช้จ่ายไม่เกินcเท่าของค่าใช้จ่ายที่เหมาะสมที่สุด (สำหรับปัญหาการหาค่าต่ำสุด) หรือค่าใช้จ่ายอย่างน้อย เท่ากับ ค่าใช้จ่ายที่เหมาะสมที่สุด (สำหรับปัญหาการหาค่าสูงสุด) ใน หนังสือ Algorithms for Hard ProblemsของHromkovičปัญหา NPO(II) ทั้งหมดถูกยกเว้นจากกลุ่มนี้ ยกเว้นในกรณีที่ P=NP ^{[ 8 ]}หากไม่มีการยกเว้น จะเท่ากับ APX ประกอบด้วยMAX -SATและ metric TSP${\displaystyle 1/c}$
• NPO(IV) : กลุ่มของปัญหา NPO ที่มีอัลกอริธึมเวลาพหุนามซึ่งประมาณค่าคำตอบที่เหมาะสมที่สุดด้วยอัตราส่วนที่เป็นพหุนามในลอการิทึมของขนาดของอินพุต ในหนังสือของ Hromkovič ปัญหา NPO(III) ทั้งหมดถูกยกเว้นจากกลุ่มนี้ เว้นแต่ P=NP ประกอบด้วยปัญหาการครอบคลุมเซต
• NPO(V) : กลุ่มของปัญหา NPO ที่มีอัลกอริธึมแบบเวลาพหุนามซึ่งประมาณค่าคำตอบที่เหมาะสมที่สุดด้วยอัตราส่วนที่จำกัดโดยฟังก์ชันบางอย่างบน n ในหนังสือของ Hromkovic ปัญหา NPO(IV) ทั้งหมดถูกยกเว้นจากกลุ่มนี้ เว้นแต่ P=NP ประกอบด้วยปัญหาTSPและปัญหาคลิก

ปัญหา NPO เรียกว่ามีขอบเขตพหุนาม (PB) ถ้าสำหรับทุกอินสแตนซ์และสำหรับทุกคำตอบ ค่าการวัดมีขอบเขตโดยฟังก์ชันพหุนามที่มีขนาดเท่ากับคลาส NPOPB คือคลาสของปัญหา NPO ที่มีขอบเขตพหุนาม ${\displaystyle x}$${\displaystyle y\in f(x)}$${\displaystyle m(x,y)}$${\displaystyle x}$

• ปัญหาการมอบหมายงาน
• ปัญหาการบรรจุลงถัง
• ปัญหาบุรุษไปรษณีย์ชาวจีน
• ปัญหาการปิด
• ปัญหาความพึงพอใจของข้อจำกัด
• ปัญหาการตัดสต็อก
• ปัญหาชุดครอบงำ
• การเขียนโปรแกรมจำนวนเต็ม
• การจัดตารางงานโรงงาน
• ปัญหาเป้สะพายหลัง
• ปัญหา จุดศูนย์กลาง k เมตริก / จุดศูนย์กลาง k ของจุดยอด
• ตัวแปรขั้นต่ำที่เกี่ยวข้องในระบบเชิงเส้น
• ต้นไม้เชื่อมโยงขั้นต่ำ
• ปัญหาการจัดตารางเวลาพยาบาล
• ปัญหาดาวแหวน
• ตั้งค่าปัญหาการปกปิด
• การจัดตารางเวลาบุคลากร
• ปัญหาพนักงานขายเดินทาง
• ปัญหาการจัดตารางเวลาใหม่ของยานพาหนะ
• ปัญหาการกำหนดเส้นทางยานพาหนะ
• ปัญหาการกำหนดเป้าหมายอาวุธ

• กราฟประกอบข้อจำกัด  – กราฟแบบไม่มีทิศทางที่มีน้ำหนักโหนด ซึ่งเกี่ยวข้องกับปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียงที่กำหนดไว้

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับการเพิ่มประสิทธิภาพเชิงการจัดเรียง (Combinatorial optimization )

• วารสารการเพิ่มประสิทธิภาพเชิงการจัดเรียง
• การประชุมเชิงปฏิบัติการการเพิ่มประสิทธิภาพเชิงการจัดเรียงแบบออสซัวส์
• แพลตฟอร์มการเพิ่มประสิทธิภาพเชิงการจัดเรียงแบบ Java (โอเพนซอร์สโค้ด)
• ทำไมการจัดตารางเวลาคนถึงเป็นเรื่องยาก?
• คลาสความซับซ้อนสำหรับปัญหาการปรับให้เหมาะสม / Stefan Kugele