อัลกอริทึมการเพิ่มประสิทธิภาพทางสถาปัตยกรรมด้วย HorusLP

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

เนื่องจากเทคโนโลยีพื้นฐานมีความซับซ้อนมากขึ้น จึงได้มีการสร้างชุดเครื่องมือใหม่ขึ้นเพื่อช่วยให้นักวิจัยและนักพัฒนาทำงานอย่างมีประสิทธิผลมากขึ้น เครื่องมือเหล่านี้ เช่น AMPL, CVXPY และ PuLP ช่วยให้นักพัฒนาสามารถกำหนด สร้าง และเรียกใช้อัลกอริธึมการปรับให้เหมาะสมและอินเทอร์เฟซกับตัวแก้ไขที่หลากหลายได้อย่างรวดเร็ว

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

วันนี้ ฉันอยากจะแนะนำ HorusLP ซึ่งเป็นไลบรารีการเพิ่มประสิทธิภาพ Python ที่ช่วยในเรื่องสถาปัตยกรรมของเวิร์กโฟลว์การพัฒนาอัลกอริธึม เราจะพูดถึงปัญหาที่เครื่องมือออกแบบมาเพื่อแก้ไข จากนั้นให้ภาพรวมคร่าวๆ ของไลบรารี Python และเราจะสร้างตัวอย่างอัลกอริธึมการปรับให้เหมาะสม

ปัญหาที่นักพัฒนาอัลกอริทึมการเพิ่มประสิทธิภาพต้องเผชิญ

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

ในสาขาวิชาส่วนใหญ่ นักพัฒนาสามารถบรรเทาปัญหานี้ได้โดยการเลือกเฟรมเวิร์กหรือไลบรารีที่ช่วยในด้านสถาปัตยกรรม ในส่วนหน้าของเว็บ นักพัฒนาหลายคนเลือก React หรือ Angular; ในโลกของการพัฒนา API วิศวกรซอฟต์แวร์อาจเลือกใช้ Django, ASP.NET MVC หรือ Play และอื่นๆ อีกมากมาย อย่างไรก็ตาม เมื่อพูดถึงนักพัฒนาอัลกอริธึมการเพิ่มประสิทธิภาพที่ต่ำต้อย มีเครื่องมือสถาปัตยกรรมน้อยมากที่จะช่วยจัดการความซับซ้อนทางสถาปัตยกรรม นักพัฒนาซอฟต์แวร์ต้องจัดการตัวแปร ข้อจำกัด และวัตถุประสงค์ต่างๆ ด้วยตนเอง ยิ่งไปกว่านั้น อัลกอริธึมการวิจัยด้านปฏิบัติการมักจะยากต่อการไตร่ตรอง ซึ่งทำให้ปัญหารุนแรงขึ้น

วัตถุประสงค์หลักของ HorusLP คือการจัดเตรียมกรอบสถาปัตยกรรมสำหรับการพัฒนาอัลกอริธึมการเพิ่มประสิทธิภาพ เฟรมเวิร์กช่วยให้องค์กรง่ายขึ้นและช่วยให้นักพัฒนามุ่งเน้นไปที่สิ่งที่พวกเขาทำได้ดีที่สุด นั่นคือการสร้างอัลกอริธึมด้วยการให้ความสอดคล้องของโครงสร้าง

ความท้าทายเวิร์กโฟลว์การเพิ่มประสิทธิภาพโดยทั่วไป

มีหลายแหล่งที่มาของความซับซ้อนเมื่อพัฒนาอัลกอริธึม OR:

ความซับซ้อนจากตัวแปร

• บ่อยครั้งที่ต้องเพิ่มตัวแปรเพื่อรองรับความต้องการทางธุรกิจเพิ่มเติม และไม่มีวิธีง่ายๆ ในการติดตามตัวแปรเพื่อใช้ในข้อกำหนดของแบบจำลองและการรายงานในภายหลัง
• ตัวแปรที่เกี่ยวข้องจะต้องถูกจัดกลุ่มและติดตาม และไม่มีวิธีการจัดการที่ชัดเจน

ความซับซ้อนจากข้อจำกัด

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

ความซับซ้อนจากวัตถุประสงค์

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

ความซับซ้อนจากการดีบัก

• ไม่มีวิธีง่ายๆ ในการดูผลลัพธ์ของแบบจำลองระหว่างการพัฒนา นักพัฒนาต้องพิมพ์ตัวแปรและค่าข้อจำกัดใหม่อย่างชัดเจนเพื่อดูผลลัพธ์ สิ่งนี้นำไปสู่รหัสที่ซ้ำกันและการพัฒนาที่ช้าลง
• เมื่อเพิ่มข้อจำกัดทำให้โมเดลไม่สามารถทำได้ อาจไม่ชัดเจนว่าเหตุใดข้อจำกัดจึงทำให้โมเดลไม่สามารถทำได้ โดยปกติ นักพัฒนาซอฟต์แวร์จะต้องขจัดข้อจำกัดต่างๆ และค้นหาความไม่ลงรอยกันผ่านการลองผิดลองถูก

HorusLP หวังว่าจะทำให้ความท้าทายเหล่านี้สามารถจัดการได้มากขึ้นด้วยการจัดหาโครงสร้าง เครื่องมือ แนวทางปฏิบัติที่ดีที่สุด เพื่อปรับปรุงประสิทธิภาพการทำงานของนักพัฒนา และความสามารถในการบำรุงรักษาผลิตภัณฑ์

บทช่วยสอน HorusLP: อัลกอริธึมการเพิ่มประสิทธิภาพและภาพรวมของ API

เพื่อไม่ให้เป็นการเสียเวลา มาดูกันดีกว่าว่าห้องสมุด HorusLP สามารถทำอะไรให้คุณได้บ้าง!

เนื่องจาก HorusLP นั้นใช้ Python และ PuLP เราจึงต้องการติดตั้งโดยใช้ pip เรียกใช้สิ่งต่อไปนี้ในบรรทัดคำสั่งของคุณ:

 Pip install horuslp pulp

เมื่อการติดตั้งเสร็จสมบูรณ์ ให้เปิดไฟล์ Python ต่อไป เราจะนำปัญหาเป้จากบทความก่อนหน้าของฉันเกี่ยวกับการวิจัยการดำเนินงาน

ไลบรารี HorusLP มี API การประกาศที่ง่ายมากและมีต้นแบบเพียงเล็กน้อย เริ่มต้นด้วยการนำเข้าคลาสและตัวแปรที่จำเป็น:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

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

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

เมื่อกำหนดตัวแปรแล้ว มากำหนดข้อจำกัดกัน เราสร้างข้อจำกัดโดยการจัดคลาสย่อยของคลาสข้อจำกัดหลักและใช้ฟังก์ชัน "define"

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

ในฟังก์ชัน define คุณสามารถถามหาตัวแปรที่ต้องการตามชื่อได้ กรอบงานจะค้นหาตัวแปรในตัวจัดการตัวแปรและส่งต่อไปยังฟังก์ชันกำหนด

หลังจากใช้ข้อจำกัดแล้ว เราก็สามารถดำเนินการตามวัตถุประสงค์ได้ เนื่องจากเป็นวัตถุประสงค์ง่ายๆ เราจะใช้ ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

ฟังก์ชัน define มีการตั้งค่าที่คล้ายคลึงกันมากกับฟังก์ชัน define ของคลาสข้อจำกัด อย่างไรก็ตาม แทนที่จะส่งคืนนิพจน์ข้อจำกัด เราจะส่งคืนนิพจน์ affine

เมื่อกำหนดตัวแปร ข้อจำกัด และวัตถุประสงค์แล้ว มากำหนดโมเดลกัน:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

ในการสร้างโมเดล เราสร้างคลาสที่เป็นคลาสย่อยของคลาส Problem และระบุตัวแปร วัตถุประสงค์ ข้อจำกัด และความรู้สึก ด้วยปัญหาที่ระบุ เราสามารถแก้ปัญหาได้:

 prob = KnapsackProblem() prob.solve()

หลังจากการแก้ปัญหา เราสามารถพิมพ์ผลลัพธ์โดยใช้ฟังก์ชัน print_results ของคลาสปัญหา นอกจากนี้เรายังสามารถเข้าถึงค่าของตัวแปรเฉพาะโดยดูที่คลาส result_variables

 prob.print_results() print(prob.result_variables)

เรียกใช้สคริปต์ และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

คุณควรเห็นสถานะของปัญหา ค่าสุดท้ายของตัวแปร ค่าวัตถุประสงค์ และค่าของนิพจน์ข้อจำกัด เรายังเห็นค่าผลลัพธ์ของตัวแปรเป็นพจนานุกรม

และแล้วเราก็มี ปัญหา HorusLP แรกของเราในประมาณ 35 บรรทัด!

ในตัวอย่างต่อจากนี้ เราจะมาสำรวจคุณลักษณะที่ซับซ้อนยิ่งขึ้นของไลบรารี HorusLP

การใช้ VariableGroups

บางครั้ง ตัวแปรมีความเกี่ยวข้องและอยู่ในกลุ่มตรรกะ ในกรณีของปัญหาเป้ ตัวแปรทั้งหมดสามารถวางลงในกลุ่มวัตถุได้ เราสามารถปรับโครงสร้างโค้ดใหม่เพื่อใช้กลุ่มตัวแปรได้ ตรวจสอบให้แน่ใจว่าได้บันทึกรหัสจากส่วนก่อนหน้าเพราะเราจะอ้างถึงในบทช่วยสอนที่ตามมา!

เปลี่ยนคำสั่งการนำเข้าดังนี้:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

ตอนนี้เรายังต้องเปลี่ยนการประกาศตัวแปรเป้ดังนี้:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

อาร์กิวเมนต์แรกคือชื่อของกลุ่มตัวแปร ตัวแปรที่สองคือรายชื่อของตัวแปรภายในกลุ่มนั้น

ตอนนี้ เราต้องเปลี่ยนข้อจำกัดและคำจำกัดความวัตถุประสงค์ แทนที่จะถามชื่อบุคคล เราจะใช้กลุ่มตัวแปร ซึ่งจะถูกส่งต่อในพจนานุกรมโดยที่คีย์คือชื่อ และค่าต่างๆ เป็นตัวแปร เปลี่ยนข้อจำกัดและคำจำกัดความวัตถุประสงค์ดังนี้:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

ตอนนี้เราสามารถใช้คำจำกัดความของปัญหาเดียวกันและรันคำสั่งได้:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

คุณควรเห็นสิ่งนี้ในผลลัพธ์ของคุณ:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

การจัดการข้อจำกัดหลายข้อ

โมเดลที่มีข้อจำกัดเดียวนั้นค่อนข้างหายาก เมื่อทำงานกับข้อจำกัดหลายๆ อย่าง การมีข้อจำกัดทั้งหมดไว้ในที่เดียวนั้นถือเป็นการดี เพื่อให้สามารถติดตามและจัดการได้อย่างง่ายดาย HorusLP ทำให้เป็นธรรมชาติ

ตัวอย่างเช่น เราต้องการดูว่าผลลัพธ์จะเปลี่ยนไปอย่างไรหากเราบังคับให้นางแบบเพิ่มกล้องในเป้ของเรา เราจะใช้ข้อจำกัดเพิ่มเติมและเพิ่มเข้าไปในคำจำกัดความของปัญหาของเรา

กลับไปที่แบบจำลองที่เรานำมาใช้ในบทช่วยสอนแรก เพิ่มข้อจำกัดต่อไปนี้:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

ในการเพิ่มข้อจำกัดให้กับโมเดล เราเพียงแค่เพิ่มเข้าไปในคำจำกัดความของปัญหาดังนี้:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

เรียกใช้ปัญหา และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

คุณควรเห็นข้อจำกัดใหม่ถูกพิมพ์ใน stdout และค่าตัวแปรที่เหมาะสมที่สุดที่เปลี่ยนแปลงไป

การจัดการข้อจำกัดในการพึ่งพาและกลุ่มข้อจำกัด

ข้อจำกัดมักเกี่ยวข้องกัน เพราะพวกเขาพึ่งพากันและกัน หรือเพราะพวกเขาอยู่ในกลุ่มเดียวกันอย่างมีเหตุผล

ตัวอย่างเช่น หากคุณต้องการตั้งค่าข้อจำกัดเพื่อจำกัดผลรวมของค่าสัมบูรณ์ของชุดตัวแปร ก่อนอื่นคุณต้องระบุข้อจำกัดเพื่อแสดงความสัมพันธ์ของค่าสัมบูรณ์ระหว่างตัวแปรที่ต้องการ จากนั้นระบุขีดจำกัดของค่าสัมบูรณ์ บางครั้ง คุณต้องใช้ข้อจำกัดที่คล้ายกันกับกลุ่มของตัวแปรเพื่อแสดงความสัมพันธ์เฉพาะระหว่างตัวแปร

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

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

และตอนนี้เพื่อทดสอบว่าข้อจำกัดที่ขึ้นต่อกันนั้นถูกนำไปใช้โดยอัตโนมัติ ให้นำ MustHaveItemConstraint ออกจากคำจำกัดความของปัญหา:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

และรันโค้ดอีกครั้ง และคุณควรเห็นสิ่งต่อไปนี้ใน stdout:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

ดูเหมือนว่าจะมีการใช้งาน MustHaveItemConstraint ! สำหรับตัวอย่างที่ซับซ้อนมากขึ้นเกี่ยวกับวิธีการใช้ข้อจำกัดที่ขึ้นต่อกัน ให้อ้างอิงกับตัวอย่างการจัดบุคลากรที่ส่วนท้ายของบทช่วยสอน

การจัดการวัตถุประสงค์แบบถ่วงน้ำหนักหลายรายการ

บ่อยครั้ง ในระหว่างการพัฒนาอัลกอริธึมการเพิ่มประสิทธิภาพ เราจะพบนิพจน์วัตถุประสงค์ที่ประกอบด้วยหลายส่วน ในการทดลองของเรา เราอาจเปลี่ยนการชั่งน้ำหนักของส่วนประกอบวัตถุประสงค์ต่างๆ เพื่อให้อัลกอริทึมมีอคติไปสู่ผลลัพธ์ที่ต้องการ CombinedObjective เป็นวิธีที่สะอาดและเรียบง่ายในการแสดงออก

สมมติว่าเราต้องการให้อัลกอริทึมเลือกรูปแกะสลักและไซเดอร์ มาปรับโครงสร้างโค้ดจากส่วนก่อนหน้าเพื่อใช้ CombinedObjective

ขั้นแรก นำเข้าคลาส CombinedObjective ดังนี้:

 from horuslp.core import CombinedObjective

เราสามารถใช้องค์ประกอบวัตถุประสงค์อิสระได้ดังนี้:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

ตอนนี้ เราสามารถรวมวัตถุประสงค์ด้านมูลค่าและวัตถุประสงค์ของไซเดอร์/รูปจำลองได้โดยใช้ CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

ตอนนี้ขอเปลี่ยนคำจำกัดความของปัญหาดังนี้:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

เรียกใช้ปัญหา และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

ผลลัพธ์จะสรุปมูลค่าวัตถุประสงค์รวม มูลค่าของแต่ละองค์ประกอบวัตถุประสงค์ น้ำหนัก และแน่นอนมูลค่าของข้อจำกัดทั้งหมด

ค้นหาข้อจำกัดที่เข้ากันไม่ได้

ในการพัฒนาอัลกอริธึม เรามักพบโมเดลที่เป็นไปไม่ได้ หากแบบจำลองมีความซับซ้อน อาจเป็นการท้าทายที่จะระบุสาเหตุที่แบบจำลองนั้นทำไม่ได้ในทันใด HorusLP มีเครื่องมือที่มีประโยชน์ที่จะช่วยคุณในกรณีเหล่านั้น

สมมติว่าเรากำลังเพิ่มข้อจำกัดและลงเอยด้วยชุดของข้อจำกัดต่อไปนี้:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

เรามีข้อจำกัดสองสามประการเกี่ยวกับขนาดโดยรวมของสิ่งของในเป้เป้ ข้อจำกัดที่กำหนดให้ไซเดอร์ต้องอยู่ในเป้ และชุดข้อจำกัดที่เข้ากันไม่ได้ซึ่งกำหนดให้กล้องต้องอยู่ในและไม่ใช่ในเป้เป้ (แน่นอนว่าในอัลกอริธึมในโลกแห่งความเป็นจริง ข้อจำกัดมักจะไม่ชัดเจนนักและเกี่ยวข้องกับความสัมพันธ์และข้อจำกัดของตัวแปรที่ซับซ้อน)

สมมติว่ามีการจัดกลุ่มข้อจำกัดในลักษณะต่อไปนี้ อาจทำให้การตรวจจับยากขึ้น:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

นี่คือคำจำกัดความของปัญหา:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

เรียกใช้ปัญหา และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Infeasible

ไม่นะ! พวกเราทำอะไร? หากเราใช้เครื่องมือส่วนใหญ่ เราต้องเริ่มเซสชันการดีบักที่ยากลำบาก โดยเราจะจำกัดข้อจำกัดที่อาจขัดแย้งกันให้แคบลงทีละรายการ โชคดีที่ HorusLP มีคุณลักษณะการค้นหาที่เข้ากันไม่ได้เพื่อช่วยให้คุณจำกัดข้อจำกัดที่เข้ากันไม่ได้ให้แคบลงได้เร็วขึ้น วิธีที่ง่ายที่สุดในการใช้คุณสมบัติการค้นหาที่เข้ากันไม่ได้คือเปลี่ยนการเรียก print_results ดังนี้:

 prob.print_results(find_infeasible=True)

ง่ายๆ แบบนั้น! รันโค้ด และตอนนี้คุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

ยอดเยี่ยม! ตอนนี้เราได้พิสูจน์แล้วว่า MustHaveItemConstraint ไม่ใช่สาเหตุของความเป็นไปไม่ได้ และปัญหาเกิดจาก CombinedConstraints1 และ CombinedConstraints2

นั่นให้ข้อมูลบางอย่างแก่เรา แต่ระหว่างข้อจำกัดที่รวมกันนั้นมีข้อจำกัดที่ขึ้นต่อกันสี่ข้อ เราระบุได้ไหมว่าข้อจำกัดสี่ข้อใดไม่เข้ากัน ใช่. แก้ไขการเรียก print_results ของคุณดังนี้:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

สิ่งนี้จะทำให้การค้นหาความเป็นไปไม่ได้ขยายข้อจำกัดที่ขึ้นต่อกัน เพื่อให้เราได้ภาพที่ละเอียดยิ่งขึ้นว่าอะไรเป็นสาเหตุของความเป็นไปไม่ได้ เรียกใช้สิ่งนี้และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

แม้ว่าการค้นหาความเป็นไปไม่ได้ในเชิงลึกจะดึงดูดใจทุกครั้ง แต่สำหรับปัญหาที่เป็นจริงซึ่งมีข้อจำกัดทั้งหมดจำนวนมาก การค้นหาความเป็นไปไม่ได้ในเชิงลึกอาจกลายเป็นการใช้ทรัพยากรที่เข้มข้นและใช้เวลานานมาก ดังนั้นจึงเป็นการดีที่สุดที่จะเรียกใช้การค้นหาความเป็นไปไม่ได้ขั้นพื้นฐานเพื่อจำกัดความเป็นไปได้ให้แคบลงและเรียกใช้การค้นหาความเป็นไปไม่ได้อย่างลึกซึ้งในชุดย่อยที่เล็กกว่าหลังจากทำการตรวจสอบด้วยตนเอง

การสร้างอัลกอริทึมจากไฟล์ข้อมูล

เมื่อสร้างแบบจำลอง เราแทบไม่มีความหรูหราในการฮาร์ดโค้ดทุกข้อจำกัดและตัวแปร บ่อยครั้ง โปรแกรมของเราต้องมีความยืดหยุ่นเพียงพอที่จะเปลี่ยนโมเดลโดยขึ้นอยู่กับข้อมูลที่ป้อนเข้า สมมติว่าแทนที่จะป้อนข้อมูลแบบฮาร์ดโค้ด เราต้องการสร้างปัญหาเป้ของเราจาก JSON ต่อไปนี้:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

เราสามารถทำได้โดยอาศัยการสนับสนุนของ kwargs เกี่ยวกับฟังก์ชัน "define" ที่เรานำไปใช้สำหรับข้อจำกัดและวัตถุประสงค์

มาแก้ไขโค้ดจากปัญหาเป้อย่างง่าย (ปัญหาที่เรานำมาใช้ในส่วนที่ 1 ของบทช่วยสอน) ขั้นแรก ให้ใส่สตริง JSON ลงในไฟล์ แน่นอน ปกติแล้วเราจะอ่านมันจากแหล่งภายนอก แต่เพื่อความเรียบง่าย ขอรวมทุกอย่างไว้ในไฟล์เดียว เพิ่มสิ่งต่อไปนี้ในรหัสของคุณ:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

ตรวจสอบให้แน่ใจด้วยว่าโปรแกรมของเราสามารถแยกวิเคราะห์ได้ เพิ่มข้อมูลต่อไปนี้ในใบแจ้งยอดการนำเข้าของคุณ:

 Import json

ตอนนี้ มาแก้ไขโค้ดการตั้งค่าตัวแปรของเราดังนี้:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

ซึ่งจะกำหนดตัวแปรสำหรับแต่ละรายการใน JSON และตั้งชื่อให้เหมาะสม

มาเปลี่ยนข้อจำกัดและคำจำกัดความวัตถุประสงค์ดังนี้:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

โดยการขอ **kwargs แทนตัวแปรเฉพาะ ฟังก์ชัน define จะได้รับพจนานุกรมที่มีตัวแปรทั้งหมดตามชื่อ ฟังก์ชันนิยามข้อจำกัดสามารถเข้าถึงตัวแปรจากพจนานุกรมได้

หมายเหตุ: สำหรับกลุ่มตัวแปร จะเป็นพจนานุกรมแบบซ้อน โดยที่ระดับแรกคือชื่อกลุ่ม และระดับที่สองคือชื่อตัวแปร

ที่เหลือค่อนข้างตรงไปตรงมา:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

เรียกใช้โปรแกรมนี้และคุณจะเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

การกำหนดเมตริกที่กำหนดเองใน HorusLP

ในบางครั้ง เพื่อวัตถุประสงค์ในการดีบักและการรายงาน เราจะสร้างเมตริกที่กำหนดเองซึ่งไม่ได้แสดงโดยตรงในวัตถุประสงค์หรือเป็นข้อจำกัด HorusLP มีคุณสมบัติที่จะทำให้การระบุเมตริกที่กำหนดเองเป็นเรื่องง่าย

สมมติว่าเราต้องการติดตามจำนวนผลไม้ที่โมเดลจากส่วนก่อนหน้าของเราใส่ลงในเป้ เพื่อติดตามสิ่งนี้ เราสามารถกำหนดเมตริกที่กำหนดเองได้ เริ่มต้นด้วยการนำเข้าคลาสพื้นฐานของเมตริก:

 From horuslp.core import Metric

ตอนนี้ มากำหนดเมตริกที่กำหนดเองกัน:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

อย่างที่คุณเห็น อินเตอร์เฟสที่กำหนดไว้นั้นดูคล้ายกับของคลาสองค์ประกอบข้อจำกัดและวัตถุประสงค์ หากคุณได้ปฏิบัติตามบทช่วยสอนนี้แล้ว สิ่งนี้น่าจะคุ้นเคยสำหรับคุณ

ตอนนี้ เราต้องเพิ่มเมตริกลงในคำนิยามปัญหา อินเทอร์เฟซที่นี่อีกครั้งคล้ายกับคำจำกัดความข้อจำกัด:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

เรียกใช้สิ่งนี้และคุณควรเห็นผลลัพธ์ต่อไปนี้:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

คุณสามารถดูจำนวนผลไม้ที่พิมพ์ได้ที่ด้านล่าง

การทำงานผ่านปัญหาที่ซับซ้อนยิ่งขึ้น: เป้สองใบ

มาลองทำตัวอย่างที่ซับซ้อนกว่านี้กันเล็กน้อย สมมติว่าแทนที่จะเป็นเป้ใบเดียว เรามีกระเป๋าและกระเป๋าเดินทาง เรายังมีวัตถุสองประเภทที่ทนทานและเปราะบาง กระเป๋าเดินทางที่มีการป้องกันมากกว่านั้นสามารถเก็บสิ่งของที่บอบบางและทนทานได้ ในทางกลับกัน กระเป๋าสามารถใส่ได้เฉพาะสินค้าคงทนเท่านั้น สมมติว่าข้อมูลสำหรับรายการได้รับใน JSON ต่อไปนี้:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

เรามาดูกันว่าสิ่งนี้จะเปลี่ยนโมเดลอย่างไร มาเริ่มกันที่กระดานชนวนเปล่ากันก่อน เพราะโมเดลจะแตกต่างกันมาก เริ่มต้นด้วยการตั้งค่าปัญหา:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

ทีนี้มาตั้งค่าตัวแปรกัน เราจะตั้งค่าตัวแปรไบนารีสำหรับชุดค่าผสมของรายการ/คอนเทนเนอร์ทุกรายการ

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

ตอนนี้ เราต้องการใช้ข้อจำกัดด้านน้ำหนักสำหรับทั้งกระเป๋าเดินทางและกระเป๋า

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

ตอนนี้ เราจำเป็นต้องใช้ข้อจำกัดที่ซับซ้อนมากขึ้นเล็กน้อย—ข้อจำกัดที่ทำให้มั่นใจว่ารายการจะไม่เข้าทั้งกระเป๋าเดินทางและกระเป๋า—นั่นคือ ถ้าตัวแปร "ในกระเป๋าเดินทาง" เป็น 1 แล้ว "ในกระเป๋า" ตัวแปรต้องเป็นศูนย์ และในทางกลับกัน แน่นอน เราต้องการให้แน่ใจว่าจะอนุญาตให้อินสแตนซ์ที่รายการสิ้นสุดในคอนเทนเนอร์ไม่เช่นกัน

เพื่อเพิ่มข้อจำกัดนี้ เราต้องทำซ้ำรายการคงทนทั้งหมด ค้นหาตัวแปร "ในกระเป๋าเดินทาง" และตัวแปร "ในกระเป๋า" และยืนยันว่าผลรวมของตัวแปรเหล่านี้น้อยกว่า 1

เราสามารถกำหนดข้อจำกัดตามไดนามิกได้อย่างง่ายดายใน HorusLP:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

เมื่อกำหนดข้อจำกัดแล้ว มาสร้างวัตถุประสงค์กัน วัตถุประสงค์คือผลรวมของค่าทั้งหมดที่เราได้รับจากไอเท็มทั้งหมดที่อยู่ในคอนเทนเนอร์อย่างง่าย ดังนั้น:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

เรามากำหนดเมตริกที่กำหนดเองกันด้วย เพื่อให้เราดูได้อย่างรวดเร็วว่าน้ำหนักที่ใส่ลงในกระเป๋าและกระเป๋าเดินทาง รวมทั้งน้ำหนักของกระเป๋าเดินทางที่มาจากสินค้าคงทนและสินค้าแตกหักง่าย:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

ตอนนี้เราทำทุกอย่างเสร็จแล้ว มายกตัวอย่างปัญหาและเรียกใช้โมเดลกัน:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

เรียกใช้สิ่งนี้ และคุณควรเห็นผลลัพธ์ต่อไปนี้ใน stdout ของคุณ:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

ดังนั้น กล้อง แว่นตา แอปเปิ้ล และกล้วยจึงใส่ลงในกระเป๋าเดินทางโดยมีน้ำหนักรวม 15 หน่วย ตุ๊กตา เขา และช่างหนังใส่ในกระเป๋าทั้งหมดโดยมีน้ำหนักรวม 17 หน่วย มูลค่ารวมของสินค้าออกมาเป็น 32 หน่วยมูลค่า ที่น่าสนใจคือไม่มีสินค้าคงทนอยู่ในกระเป๋าเดินทาง น่าจะเป็นเพราะกระเป๋ามีความจุเพียงพอสำหรับเก็บสินค้าคงทนทั้งหมด

สถานการณ์ที่ใหญ่ขึ้นและสมจริงยิ่งขึ้น: ปัญหาด้านบุคลากร

หากคุณมาไกลถึงขนาดนี้ในบทช่วยสอน HorusLP ของเรา ขอแสดงความยินดีด้วย! ตอนนี้คุณมีไอเดียดีๆ เกี่ยวกับวิธีใช้ HorusLP แล้ว

อย่างไรก็ตาม ตัวอย่างทั้งหมดที่เรากำลังดำเนินการอยู่นั้นเป็นการเรียงสับเปลี่ยนของปัญหาเป้สะพายหลัง และข้อกำหนดและพารามิเตอร์บางอย่างค่อนข้างไม่สมจริง มาทำงานผ่านปัญหาอื่นด้วยกันเพื่อดูว่า HorusLP สามารถแก้ปัญหาที่สมจริงยิ่งขึ้นได้อย่างไร เราจะแก้ไขปัญหาด้านบุคลากรในครึ่งหลังของบทความ Toptal ก่อนหน้าของฉัน

เพื่อประโยชน์ของเวลา เราจะไปที่รุ่นสุดท้ายของแบบจำลอง (ด้วยความขัดแย้งส่วนบุคคล ข้อบังคับด้านแรงงาน และค่าเบี้ยเลี้ยงพนักงานชั่วคราว) แต่การใช้งานแบบจำลองเริ่มต้นที่ง่ายกว่านั้นก็มีให้ใช้งานบน GitHub เช่นกัน

เริ่มต้นด้วยการตั้งค่าปัญหา:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

ตอนนี้ เรามากำหนดตัวแปรกัน ซึ่งในกรณีนี้จะเป็นตัวแปรไบนารีที่กำหนดว่าคนงานควรทำงานกะของพวกเขาหรือไม่ และตัวแปรจำนวนเต็มกำหนดจำนวน dothrakis ที่เราจ้างสำหรับแต่ละกะ:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

ตอนนี้ เรามาปรับใช้ข้อจำกัดที่กำหนดให้เราต้องมีพนักงานเพียงพอสำหรับทุกกะ:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

ตอนนี้ เราจำเป็นต้องใช้ข้อจำกัดที่ป้องกันไม่ให้บุคคลบางคนทำงานร่วมกัน:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

ห่อ

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!