HorusLP-Gurobi: สถาปัตยกรรมการเพิ่มประสิทธิภาพระดับสูงสำหรับ Gurobi

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

หนึ่งในนักแก้ปัญหาเชิงพาณิชย์ที่ได้รับความนิยมมากที่สุดในตลาดคือ Gurobi ซึ่งได้รับการตั้งชื่อตามผู้ร่วมก่อตั้ง Zonghao Gu, Edward Rothberg และ Robert Bixby ซึ่งต่างก็เป็นผู้บุกเบิกพื้นที่แก้ปัญหาเชิงพาณิชย์ Gurobi ได้ขับเคลื่อนโครงการเพิ่มประสิทธิภาพที่มีรายละเอียดสูงมากมายในอดีตที่ผ่านมา รวมถึงโครงการจัดสรรแบนด์วิดท์ของ FCC และโครงการมอบหมายให้นักโทษในเรือนจำแห่งรัฐเพนซิลวาเนีย

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

การเพิ่มประสิทธิภาพ: การทบทวนอย่างรวดเร็ว

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

สมมติว่าคุณมีเป้ที่มีความจุ 15 ปอนด์ คุณมีสินค้าสองสามรายการต่อหน้าคุณ โดยแต่ละรายการมีน้ำหนักและมูลค่าเงินที่เฉพาะเจาะจง:

1. กล้อง: น้ำหนัก 2 ปอนด์ มูลค่า $5
2. ตุ๊กตา: น้ำหนัก 4 ปอนด์ มูลค่า $7
3. ไซเดอร์: น้ำหนัก 7 ปอนด์ มูลค่า $2
4. ฮอร์น: น้ำหนัก 10 ปอนด์ มูลค่า 10 ดอลลาร์

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

เราสามารถกำหนดปัญหาเป็นปัญหาการปรับให้เหมาะสมต่อไปนี้:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

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

เทคนิคทางคณิตศาสตร์ที่แฝงอยู่นั้นค่อนข้างน่าสนใจ แต่อยู่นอกเหนือขอบเขตของบทความนี้ หากคุณต้องการทราบข้อมูลเพิ่มเติม ฉันแนะนำให้ดูที่นี่และที่นี่ ทั้งที่ได้รับความอนุเคราะห์จาก Gurobi

กูโรบี

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

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

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

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

การรันตัวอย่างจะให้ผลลัพธ์ต่อไปนี้:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

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

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

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

หากคุณต้องการคำแนะนำโดยละเอียดเพิ่มเติมเกี่ยวกับไลบรารีหลักของ HorusLP พร้อมตัวอย่างโค้ด คุณสามารถหาบทช่วยสอนได้ที่นี่

การรวม HorusLP-Gurobi

แม้ว่า API หลักของ HorusLP จะมอบ API ระดับสูงที่สะดวกสำหรับการสร้างแบบจำลองการปรับให้เหมาะสม แต่ก็สร้างขึ้นบน PuLP ซึ่งในขณะที่สามารถใช้ Gurobi เป็นตัวแก้ปัญหาได้ แต่กลับไม่สามารถเข้าถึงความสามารถขั้นสูงบางอย่างของ Gurobi ได้

HorusLP-Gurobi เป็นเวอร์ชันหนึ่งของ HorusLP API ที่สร้างขึ้นโดยใช้ Python API ของ Gurobi สิ่งนี้ทำให้ผู้ใช้สามารถเข้าถึงคุณสมบัติขั้นสูงของ Gurobi ได้โดยตรง ในขณะที่รักษา HorusLP API ให้สอดคล้องกัน

ปรัชญาหลักประการหนึ่งที่ชี้นำการพัฒนา HorusLP-Gurobi คือความสอดคล้องกับ HorusLP core API ด้วยการรักษาโครงสร้างที่เรียบง่ายของ HorusLP ให้สอดคล้องกัน ผู้ใช้โปรแกรมแก้ไขโอเพ่นซอร์สสามารถเปลี่ยนไปใช้ Gurobi ได้อย่างง่ายดายโดยการติดตั้ง Gurobi API และเปลี่ยนคำสั่งการนำเข้า

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

เพื่อไม่ให้เป็นการเสียเวลา เรามาดำดิ่งลงไปในตัวอย่างโค้ดกันเลย!

ตัวอย่างโค้ด

HorusLP API พื้นฐาน

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

เมื่อคุณติดตั้ง Gurobi แล้ว เราสามารถเริ่มต้นด้วยการเข้ารหัสด้วย HorusLP-Gurobi! เริ่มต้นด้วยการติดตั้งแพ็คเกจที่จำเป็น:

 Pip install horuslp horuslp-gurobi

เมื่อการติดตั้งเสร็จสิ้น เราสามารถเริ่มใช้ HorusLP-Gurobi ได้! นึกถึงตัวอย่างปัญหาเป้เมื่อก่อน เราสามารถใช้ HorusLP-Gurobi เพื่อจำลองปัญหาได้ดังนี้:

ขั้นแรก นำเข้าไลบรารีที่เกี่ยวข้อง

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

กำหนดตัวแปรบางอย่าง

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

ตอนนี้ เราสามารถกำหนดข้อจำกัดโดยใช้คลาสข้อจำกัด

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

จากนั้นเราสามารถดำเนินการตามวัตถุประสงค์ในลักษณะเดียวกันได้

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

และสุดท้าย เราสามารถกำหนดปัญหาได้

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

และเรายกตัวอย่างปัญหาและเรียกฟังก์ชันการแก้ปัญหา นี่คือที่ที่เวทมนตร์เกิดขึ้น

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

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

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

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

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

หากคุณได้อ่านบทความก่อนหน้าเกี่ยวกับ HorusLP core คุณจะสังเกตเห็นว่า API นี้เกือบจะเหมือนกันทุกประการ เพื่อให้ API เรียบง่าย อินเทอร์เฟซของ HorusLP core และ HorsLP-Gurobi นั้นเหมือนกัน โดยมีความแตกต่างระหว่างตัวแก้ไขที่แยกออกไปในการใช้งาน superclass

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

คุณสมบัติ Gurobi

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

ตัวอย่างเช่น หากคุณต้องการเขียนไฟล์ MPS ของโมเดลเป้ ใน Gurobi คุณอาจเขียนบางอย่างเช่น m.write('knapsack.mps') ในขณะที่ใช้ HorusLP-Gurobi คุณสามารถ:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

และคุณควรเห็นไฟล์ MPS ในไดเร็กทอรีการทำงานของคุณ

คุณสามารถใช้อินเทอร์เฟซนี้เพื่อเข้าถึงคุณลักษณะขั้นสูงของ Gurobi เช่น การคำนวณ IIS การสร้างการโทรกลับ หรือการให้คำแนะนำตัวแปร

คุณสมบัติ Gurobi ขั้นสูงที่บริการของคุณ

วันนี้เรามาดูเวอร์ชันของไลบรารี HorusLP ที่สร้างขึ้นบน Gurobi Python API นอกจากฟีเจอร์การรายงานและการดีบักของ HorusLP หลักแล้ว ตอนนี้คุณมีสิทธิ์เข้าถึงฟีเจอร์ขั้นสูงทั้งหมดของ Gurobi ที่เข้าถึงได้อย่างลงตัวผ่านการผสานรวมกับ Python API ของ Gurobi

หากคุณเป็นผู้ใช้ Gurobi ปัจจุบันหรือผู้สนใจที่จะใช้การเพิ่มประสิทธิภาพ Gurobi ฉันหวังว่าคุณจะลองใช้ HorusLP! คุณสามารถค้นหาโค้ดตัวอย่าง ให้คำแนะนำ หรือสนับสนุน HorusLP-Gurobi ได้ที่ GitHub