การแก้ปัญหา LP ขั้นสูง

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

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

แนวคิด

ส่วนนี้จะนำเสนอแนวคิดหลักสำหรับการใช้เครื่องมือแก้โจทย์ปัญหา LP ขั้นสูง เราสันนิษฐานว่าผู้อ่านคุ้นเคยกับแนวคิดความซ้ำซ้อนใน LP

กลุ่มอัลกอริทึม LP

คลาสของอัลกอริทึมสำหรับ LP ต่อไปนี้สามารถเข้าถึงได้ผ่านเครื่องมือ OR

  1. อัลกอริทึม Simplex เป็นอัลกอริทึม LP แรกที่ใช้งานได้จริงและยังคงได้รับความนิยมมากที่สุด อัลกอริทึมจะเดินไปตามจุดยอด (จุดหัวมุม) ของบริเวณที่เป็นไปได้ และจะปรับปรุงค่าของฟังก์ชันวัตถุประสงค์ซ้ำไปเรื่อยๆ จนกว่าจะได้คำตอบที่เหมาะสม อัลกอริทึมแบบง่ายมี 2 ประเภท ดังนี้

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

  2. เมธอด Barrier หรือ interior-point เป็นอัลกอริทึมลำดับที่ 2 ของอัลกอริทึมสำหรับ LP วิธีการที่เป็นอุปสรรคจับคู่การรับประกันทางทฤษฎีของการบรรจบกันที่มีประสิทธิภาพ (เวลาพหุนาม) กับประสิทธิภาพที่เชื่อถือได้ในทางปฏิบัติ ซึ่งจะเสริมอัลกอริทึมด้านเดียวเมื่อประสิทธิภาพไม่ดี เช่น ตัวแก้โจทย์บางคนเสนอให้ใช้ทั้งด้านเรียบและแนวกั้นควบคู่กัน โดยจะแสดงโซลูชันจากอัลกอริทึมที่ดำเนินการเสร็จแล้วก่อน

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

ตารางด้านล่างแสดงรายการเครื่องมือแก้โจทย์ปัญหา LP ที่มีในเครื่องมือ "หรือ" และระบุว่าอัลกอริทึมกลุ่มใดจาก 3 กลุ่มที่ใช้งานในเครื่องมือแก้โจทย์แต่ละรายการ

เครื่องมือแก้โจทย์ ด้านเดียว ที่กั้นถนน การสั่งซื้อครั้งแรก
Clp X X
CPLEXL X X
กลอปG X
แอลพีเค X X
กูโรบี X X
PDLPG X
XpressL X X

G บ่งชี้ว่าเครื่องมือแก้โจทย์พัฒนาโดย Google L บ่งบอกว่าโซลูชันต้องใช้ใบอนุญาตที่ออกโดยนักพัฒนาซอฟต์แวร์บุคคลที่สามที่เกี่ยวข้อง

ดูคำแนะนำสำหรับคำแนะนำเกี่ยวกับเครื่องมือแก้โจทย์และอัลกอริทึมที่ควรใช้

การแก้ปัญหาคืออะไร

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

ความคลาดเคลื่อนยินยอม

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

พิจารณาปัญหาการเขียนโปรแกรมเชิงเส้น

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

และโจทย์คู่ที่เกี่ยวข้อง

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

โจทย์คู่นี้มีคำตอบเบื้องต้นที่เหมาะสมที่สุดคือ $ x_1 = 1, x_2 = 0 $ และผลเฉลยคู่ $ y = -2 $ คำตอบที่เครื่องมือแก้โจทย์ได้รับการยอมรับว่าเหมาะสมที่สุด เพื่อตอบคำถามนี้ เรากำหนดจำนวนต่อไปนี้

  • ช่องว่างแบบคู่คือผลต่างระหว่างค่าวัตถุประสงค์เบื้องต้นกับค่าวัตถุประสงค์คู่ในกรณีนี้คือ $ |(-2x_1 - x_2) - y| $
  • ความเป็นไปได้เบื้องต้นคือการละเมิดข้อจำกัดเบื้องต้น ในกรณีนี้คือ $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $
  • ความเป็นไปได้คู่คือการละเมิดข้อจำกัดคู่ ซึ่งในกรณีนี้ $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $

ผู้แก้โจทย์จะประกาศให้ทราบว่าวิธีแก้ปัญหานั้นเหมาะสมหากช่องว่างด้านคู่ ความไม่เป็นไปไม่ได้ในช่วงแรก และความอ่อนไหวควบคู่กันนั้นน้อยกว่าความคลาดเคลื่อนที่ให้ไว้1

โดยเฉพาะอย่างยิ่ง การใช้ความคลาดเคลื่อนของความคลาดเคลื่อนอาจแตกต่างกันไปเนื่องด้วยเหตุผลทั้งตามธรรมชาติและแบบไม่ซิงค์กันในเครื่องมือแก้โจทย์และอัลกอริทึมต่างๆ เช่น ช่องว่างด้านคู่ในอัลกอริทึมด้านเดียวนั้นเกิดจากความไม่แม่นยำของตัวเลขเท่านั้น ในขณะที่ความไม่เกิดขึ้นทั้ง 2 อย่างรองลงมานี้แสดงได้แม้ในเลขคณิตที่ตรงกันทั้งหมด บางเมธอดจะบังคับใช้ข้อจำกัดขอบเขต $ x_1 \ge 0, x_2 \ge 0, $ และ $ y \le 0 $ โดยตรง ในขณะที่วิธีการอื่นๆ จะจัดการกับการละเมิดข้อจำกัดแบบผูกมัดที่ต่างไปจากการละเมิดข้อจำกัดเชิงเส้น เช่น $x_1 + x_2 \le 1$ สำหรับตัวแก้โจทย์บางตัว ค่าสัมพันธภาพจะหมายถึง ค่าสัมบูรณ์ นั่นคือค่าความคลาดเคลื่อนที่เหมาะสม

สำหรับตัวอย่างผลของความคลาดเคลื่อน ให้ลองพิจารณาความคลาดเคลื่อนสัมบูรณ์ของ $ \epsilon = \frac{1}{2} $ ที่ใช้กับคู่เบื้องต้น-คู่คู่ข้างต้น คำตอบนี้ $ x_1 = 1.5, x_2 = 0, y = -3 $ มีช่องว่างคู่และความเป็นไปได้เป็นศูนย์ทั้งหมดน้อยกว่าหรือเท่ากับ $ \epsilon $ ดังนั้น เครื่องมือแก้โจทย์อาจประกาศว่าโซลูชันนี้ "เหมาะสมที่สุด" แต่ค่าวัตถุประสงค์ (-3) ยังต่างจาก 1 จากค่าวัตถุประสงค์ที่เหมาะสมที่สุดที่แท้จริงที่ -2 ค่าเริ่มต้นโดยทั่วไปของ $ \epsilon $ จะอยู่ระหว่าง $10^{-6}$ ถึง $10^{-8}$ ซึ่งทำให้ตัวอย่างที่รุนแรงเช่นนี้หายากแต่ เป็นไปไม่ได้

ประเภทของโซลูชัน

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

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

โดยทั่วไปวิธีการกีดขวางและลำดับลำดับแรกจะไม่แสดงผลจุดยอด (ทฤษฎี ได้อธิบายลักษณะอื่นๆ ที่อยู่นอกเหนือขอบเขตของคู่มือนี้)

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

การแนะนำวิดีโอ

เรามีคำแนะนำต่อไปนี้สำหรับการใช้เครื่องมือแก้โจทย์ปัญหา LP ขั้นสูง

การปรับขนาดข้อมูลปัญหา

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

เป็นเรื่องปกติที่ค่าคงที่ตัวเลขขนาดเล็กมากหรือขนาดใหญ่จะปรากฏในโมเดล LP ขยายตัวอย่างจากด้านบน หาก \(x_1\) และ \(x_2\) แสดงถึงสัดส่วนของลูกค้าที่มอบหมายให้กับ "ผู้ให้บริการที่ 1" หรือ "ผู้ให้บริการที่ 2" และหากต้องการเพิ่มประโยชน์ให้ได้สูงสุดจากการให้บริการลูกค้าเหล่านี้ เราอาจเขียนฟังก์ชันวัตถุประสงค์ต่อไปนี้

$$ \min -c_1x_1 - c_2x_2 $$

ที่ไหน

  • $ c_1 $ คือประโยชน์จากการมอบหมายลูกค้าให้กับผู้ให้บริการ 1
  • $ c_2 $ คือประโยชน์จากการมอบหมายลูกค้าให้กับผู้ให้บริการ 2

คู่ที่ตอบสนองต่อข้อจำกัดต่อไปนี้จะถือว่าเป็นไปได้โดยมีการยอมรับแบบสัมบูรณ์ $ \epsilon $:

  • $ \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $

หากหน่วยประโยชน์สำหรับ $ c_1 $ และ $ c_2 $ เป็นค่าเศษส่วนเล็กๆ ที่เกิดขึ้นได้ในสเกลเดียวกันกับ $ \epsilon $ เงื่อนไขความเป็นไปได้คู่จะค่อนข้างอ่อน จึงอาจประกาศให้ค่าเบื้องต้นด้อยประสิทธิภาพที่สุด

ในทางกลับกัน หากหน่วยประโยชน์คือ "ไมโครดอลลาร์" (1,000,000 ไมโครดอลลาร์ = 1 ดอลลาร์) ค่าสัมบูรณ์ที่มากทำให้คำตอบมีความแม่นยำสูง นักแก้โจทย์อาจจะไม่มาบรรจบกันหากโจทย์ข้อหานี้เป็นแบบนี้ ในการกำหนดโจทย์ที่ดี นักสร้างโมเดลขั้นสูงควรพิจารณาว่าข้อมูลปัญหาได้รับการปรับขนาดในลักษณะที่สอดคล้องกับความคลาดเคลื่อนของฟังก์ชันการแก้โจทย์นั้นๆ หรือไม่

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

สำหรับความคลาดเคลื่อนของ Glop ให้ดูที่ primal_feasibility_tolerance, dual_feasibility_tolerance และ solution_feasibility_tolerance ใน GlopParameters โปรดทราบว่าจะมีการใช้ primal_feasibility_tolerance และ dual_feasibility_tolerance ภายในอัลกอริทึม ส่วน solution_feasibility_tolerance จะได้รับการตรวจสอบหลังแก้ปัญหาแล้วเพื่อแจ้งปัญหาเกี่ยวกับตัวเลข สำหรับ PDLP โปรดดู eps_optimal_absolute และ eps_optimal_relative

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

ตัวเลือกเครื่องมือแก้โจทย์และอัลกอริทึม

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

ความแปรปรวนในทางปฏิบัติ

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

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

อินสแตนซ์ กลอป
Primal Simplex		 Glop
Dual Simplex		 ที่กั้นรถกูโรบี
พร้อมรถครอสโอเวอร์		 ที่กั้นรถ Gurobi Barrier
แบบไม่มีครอสโอเวอร์		 PDLP
ความแม่นยำสูง		 PDLP
ความแม่นยำต่ำ
ex10 >1200 >1200 79.7 63.5 8.2 2.7
Nug08-3 >1200 252.8 144.6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 20.8 >1200 >1200 916.4 56.3
พลังงานอาคาร 178.4 267.5 12.8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
เวอร์ชันเครื่องมือแก้โจทย์ OR-เครื่องมือ 9.3 OR-เครื่องมือ 9.3 Gurobi 9.0 Gurobi 9.0 OR-เครื่องมือ 9.3 OR-เครื่องมือ 9.3
solver_specific_parameters (ค่าเริ่มต้น) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

จากผลลัพธ์เหล่านี้ เราได้สรุปสิ่งต่อไปนี้

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

คำแนะนำโดยย่อสำหรับการเลือกเครื่องมือแก้โจทย์ปัญหา LP

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

  1. ลองใช้ Glop เหตุผล: Glop คือการนำวิธีการดั้งเดิมและสองมิติของ Google มาใช้ Glop เป็นโอเพนซอร์สและเชื่อถือได้สำหรับ ภาระงานการผลิตของ Google
    • หากการกำหนดค่าเริ่มต้น (Primal Simplex) ทำงานได้ไม่ดี ให้ลองเปลี่ยนไปใช้แบบ Dual Simplex โดยใช้ use_dual_simplex: true
  2. หากมีใบอนุญาต ให้ลองใช้เครื่องมือแก้โจทย์คณิตเชิงพาณิชย์ (CPLEX, Gurobi หรือ Xpress) ทดลองใช้วิธีที่เรียบง่ายและสิ่งกีดขวาง เหตุผล: เครื่องมือแก้โจทย์คณิตเหล่านี้ เป็นมาตรฐานอุตสาหกรรมและได้รับการเพิ่มประสิทธิภาพอย่างสูง นอกจากนี้ วิธีป้องกันจะช่วยเสริมอัลกอริทึม แบบง่ายที่ Glop มีให้
    • หากใช้สิ่งกีดขวาง ให้ปิดใช้ "ครอสโอเวอร์" หากคุณไม่ต้องการโซลูชันเวอร์เท็กซ์
  3. ลองใช้ PDLP ปรับความคลาดเคลื่อนของความคลาดเคลื่อนให้กับแอปพลิเคชันของคุณ เหตุผล: PDLP ออกแบบมาเพื่อแก้ปัญหาที่ใหญ่ที่สุด ซึ่งวิธีที่เรียบง่ายและแบบจํากัดจะใช้หน่วยความจำถึงขีดจำกัดหรือทำงานช้าเกินไป PDLP จะทำงานได้ดีที่สุดเมื่อใช้โซลูชันแบบประมาณแต่ทำงานที่รวดเร็วกว่าโซลูชันที่แน่นอนแต่ทำงานช้า
  4. หากมาถึงจุดนี้ได้ คุณก็เป็นผู้ใช้ LP ขั้นสูงแล้ว โปรดดูตัวเลือกการสนับสนุน "หรือ" เพื่อรับความช่วยเหลือเพิ่มเติม

  1. ซึ่งมักมีความซับซ้อนมากกว่านี้ นักแก้ปัญหามักจะตรวจสอบเงื่อนไขเหล่านี้ในโจทย์ที่เปลี่ยนรูปแบบแล้ว/ซับซ้อน ซึ่งเรียกว่าปัญหาที่แก้ไขแล้ว ในบางกรณี วิธีแก้โจทย์ที่แก้ไขแล้วอาจอยู่ไกลกว่าโซลูชันการป้อนข้อมูล สถานการณ์นี้อาจนำไปสู่สถานะที่ผิดปกติ เช่น ของ CPLEX OptimalInfeas หรือ GlopIMPRECISE↩