Exact solution methodsLinear progra

Exact solution methods
Linear programs (LP): Simplex algorithm
Integer programs (IP): branch and bound, branch and cut,
branch and price...
Mixed integer programs (MIP): branch and bound, branch and
cut, branch and price...
For many problems that can be formulated as IPs or MIPs, so far,
no polynomial time algorithms are known. This is true for most
vehicle routing problems.
For some problems the integrity requirements are fulfilled
automatically (Transportation Problem, Assignment Problem).
In some cases, the optimization problem can be formulated as an
IP or MIP but there exist algorithms that solve them in polynomial
time

ผลลัพธ์ (ไทย) 1:

วิธีแก้ปัญหาที่แน่นอนโปรแกรมเชิงเส้น (LP): อัลกอริทึม Simplexจำนวนเต็มโปรแกรม (IP): สาขา และผูก สาขา และ ตัดสาขาและราคา...ผสมเต็มโปรแกรม (MIP): สาขา และผูก สาขา และตัด สาขา และราคา...ปัญหามากมาย ที่สามารถจะถูกกำหนดเป็น IPs หรือ MIPs ฉะนี้อัลกอริทึมเวลาโพลิโนเมียไม่เป็นที่รู้จักกัน นี้เป็นจริงในที่สุดปัญหาการกำหนดเส้นทางรถสำหรับปัญหาความต้องการความเป็นจริงโดยอัตโนมัติ (การขนส่งปัญหา ปัญหากำหนด)ในบางกรณี ปัญหาเพิ่มประสิทธิภาพที่สามารถจะถูกกำหนดเป็นการIP หรือ MIP แต่มีอัลกอริทึมที่แก้ไขปัญหาในพหุนามเวลา

ผลลัพธ์ (ไทย) 2:

วิธีการแก้ปัญหาที่แน่นอนโปรแกรมเชิงเส้น (LP): ขั้นตอนวิธี Simplex โปรแกรมจำนวนเต็ม (IP): สาขาและสาขาที่ถูกผูกไว้และตัดสาขาและราคา... โปรแกรมจำนวนเต็มผสม (MIP): สาขาและสาขาที่ถูกผูกไว้และตัดสาขาและราคา.. สำหรับปัญหามากมายที่สามารถนำมาเป็นสูตรหรือ IP ที่ MIPs เพื่อให้ห่างไกลไม่มีเวลาขั้นตอนวิธีพหุนามเป็นที่รู้จัก นี่คือความจริงมากที่สุดปัญหาเส้นทางรถ. สำหรับปัญหาความต้องการความสมบูรณ์เป็นจริงโดยอัตโนมัติ (ขนส่งปัญหาการกำหนดปัญหา). ในบางกรณีปัญหาการเพิ่มประสิทธิภาพได้สูตรเป็นIP หรือ MIP แต่มีอยู่ขั้นตอนวิธีการที่แก้ปัญหาได้ในพหุนามเวลา

ผลลัพธ์ (ไทย) 3:

วิธีการแก้ปัญหาโปรแกรมเชิงเส้นแน่นอน

: ขั้นตอนวิธีซิมเพล็กซ์ ( LP ) เต็มโปรแกรม ( IP ) : สาขาและจำกัด กิ่งและตัด
สาขา และราคา . . . . . . .
ผสมเต็มโปรแกรม ( 2 ) : สาขาและจำกัด สาขาและ
ตัด , สาขา และราคา . . . . . . .
สำหรับปัญหาหลายอย่างที่สามารถกำหนดเป็น IPS หรือ มิปส์ ดังนั้นไกล
ไม่มีขั้นตอนวิธีพหุนามเวลาเป็นที่รู้จักกัน นี้เป็นจริงมากที่สุด

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