Solver กับปัญหา Optimization

Solver ก็แปลตรงๆเลยครับว่า “นักแก้ปัญหา” ในที่นี้ Solver เป็นซอฟต์แวร์สำหรับแก้ปัญหาประเภท optimization เราจึงเรียก Solver อีกอย่างว่า Optimization Solver นั่นเอง ส่วนปัญหา optimization คืออะไร? ผมคิดว่าผู้ที่เรียนสายวิทย์หลายท่านคงเคยได้ยิน พวกคำว่า linear programming (LP) (สายศิลป์เรียนเปล่าไม่แน่ใจ) และ/หรือ non-linear programming (NLP) ทั้ง LP และ NLP ก็เป็นการสร้างแบบจำลองปัญหาเพื่อการหาโซลูชันที่น้อยที่สุด (minimum) หรือมากที่สุด (maximum) หรือ optimal solution ของ objective function ภายใต้เงื่อนไขหรือข้อบังคับที่เรียกว่า constraint และนอกจาก  LP กับ NLP แล้วยังมีแบบจำลองอีกมากมาย เช่น mixed integer programming (MIP), quadratic constraint programming (QCP), stochastic programming, robust programming , และ MPEC เป็นต้น

ซอฟต์แวร์ Solver เนี่ยก็มีอยู่หลายยี่ห้อ บางยี่ห้อสามารถแก้ปัญหาได้ทั้ง LP, NLP, QCP บางตัวก็แก้ปัญหาได้แค่ LP เท่านั้น เนื่องจากแต่ละปัญหาก็มี algorithm อยู่มากมาย แต่ละตัวก็มีข้อดีข้อเสีย ความสามารถแตกต่างกันไป โดย algorithm ที่ดังๆเลยก็เช่น simplex method เอาไว้แก้ปัญหา LP และ branch and bound ไว้แก้ปัญหา MIP เป็นต้น ตัวอย่าง Solver มันก็เยอะซะเหลือเกิน โดยเฉพาะพวกที่แก้ปัญหา LP ดูได้จาก wikipedia

Solver ของฟรีหรือพวก opensource ก็มีให้เลือกใช้อยู่ เช่น GLPK กับ Octave ถ้ามีทุนหน่อยก็ซื้อ MATLAB หรือ Maple มาใช้ดูก็ได้ ผมเคยใช้ทั้งสี่ตัวนี้แล้ว แต่ผมอยากบอกเลยว่า ถ้าปัญหาที่เราแก้เนี่ยไม่ค่อยใหญ่เท่าไหร่ Solver เหล่านี้สามารถแก้ปัญหาได้ไม่เลว แต่ถ้าปัญหาใหญ่มากๆและมี computational complexity สูง (ซับซ้อนสูง หรือพูดแบบบ้านๆว่า “ยากมาก”) อันนี้ก็ปวดหัวกันหน่อย และต่อให้แก้ปัญหาได้ อาจจะได้ผลลัพธ์ที่ยังไม่ดีพอหรือไม่ optimal (คือ ไม่ minimum หรือ maximum จริงๆ)

ใหญ่ และ ยาก

คำถามคือ ปัญหา optimization แบบไหนเรียกว่า “ใหญ่มาก”  และ “ยากมาก” … ถ้าพูดเรื่อง “ใหญ่มาก” ก็อธิบายยากอยู่ กล่าวคือ ตัวปัญหา optimization ก็จะประกอบไปด้วย variable และ constraint ถ้าหากทั้งสองตัวมันมีจำนวนเยอะมากๆ ก็ถือว่าเป็นปัญหาใหญ่ แต่มากแค่ไหนเนี่ยก็พูดยากอยู่ดี และคอมพิวเตอร์สมัยนี้มันแรงและแรมยังเยอะอีกด้วยจึงเป็นเรื่องพูดยากเรื่องขนาดของปัญหา อย่างถ้าเป็นปัญหา LP ผมว่า variable เป็นหลักหมื่น กับ constraint เป็นหลักพัน-หมื่น ส่วนตัวผมเอง ผมยังคิดว่ามันเล็กอยู่นะ

โดยส่วนใหญ่แล้วปัญหาที่ผมแก้จะเป็น MIP และมักเป็น pure integer programming ซะด้วย กล่าวคือ variable ต้องเป็นจำนวนเต็มเท่านั้นและไม่มีตัวแปรไหนเป็นจำนวนจริงได้เลย ปัญหาแบบ integer programming (IP) จึงถูกจัดให้เป็น NP-hard หรือที่เรียกได้ว่า “ยากมาก” นั่นเอง และถ้า IP มีจำนวน variable เยอะ โดยเฉพาะ constraint เยอะมากๆ เช่น variable มากกว่าหลักหมื่น และ constraint เอาแค่ห้าพันกว่าๆ ผมเคยเจอกับตัวเองแล้วว่า มันเป็นปัญหาที่ยากมากๆ และถ้าจำนวน variable ปาไปหลักแสน จำนวน constraint ปาไปหลักหมื่น อาจจะเรียกว่าแก้ปัญหากันเป็นวันหรือมากกว่านั้นก็ได้ หรือแก้ปัญหากันจนหน่วยความจำไม่พอจน Solver หยุดตัวเองกระทันหัน ผมก็เคยเจอมาแล้ว จากที่เรื่อง “ใหญ่มาก” เนี่ย จะพบว่ามันเกี่ยวกับคำว่า “ยากมาก” อยู่ เพราะมันก็ขึ้นกับปัญหามันใหญ่ขนาดไหน  นอกจากนี้ ก็ต้องดูที่ตัว constraint และ objective function ด้วยว่าประกอบไปด้วยฟังก์ชันอะไรบ้างที่สร้างความยุ่งยากในการคำนวณ เช่น ถ้ามีการคูณหรือหารมากกว่าการบวกหรือลบก็จัดว่ายากกว่าแล้ว ยิ่งถ้าพ่วง summation หรือ integral แบบยาวๆและมีการคูณเยอะๆก็ยิ่งซับซ้อนไปอีก  และถ้าเป็นฟังก์ชันแบบ non-linear function ก็ยิ่งทวีความซับซ้อนไปกันใหญ่ (เช่น มี variable สองตัวคูณกัน หรือมีการหาค่า absolute ที่มี variable ร่วมด้วย)

ถ้าเป็นปัญหาพวก NLP พวกที่มี variable คูณกันเองหรือยกกำลังจำนวนเยอะๆเนี่ย ไม่อยากพูดเลยครับว่า คอมพิวเตอร์มันจะทำงานกันหนักขนาดไหน และการที่จะเข้าถึง global optimum ในบางครั้ง เราจึงยอมเอา algorithm ที่เป็น metaheuristic อย่าง genetic algorithm มาช่วยในการแก้ปัญหา หรือหาวิธีที่อย่างน้อยให้ผลเป็น near optimal (หรือใกล้เคียงกับคำตอบ optimum) หรือบางครั้งก็อาจจะหลงทางไปเจอผลลัพธ์ที่เป็น local optimum แล้วก็เผลอดีใจคิดว่ามันเป็น global optimum

NEOS Solvers

โอเค ผมก็พูดเรื่อง  “ความใหญ่” กับ “ความยาก” พอให้เห็นภาพกันว่า เราต้องไปหา Solver ที่มี algorithm ที่เหมาะกับงานมาแก้ปัญหาให้ได้ และควรหาคอมพิวเตอร์แรงๆ หน่วยความจำเยอะๆมาอัดให้ได้ ดังนั้น ถ้าไม่มีงบไปซื้อ Solver ดีๆแพงๆ ผมคงแนะนำให้ใช้ GLPK กับ Octave และถ้าสถาบันมี MATLAB ให้ใช้ ก็เป็นอีกทางเลือกหนึ่ง แต่ MATLAB แก้ปัญหา MIP ได้ช้ามากๆ เท่าที่เคยลองแก้ปัญหา MIP  มันช้ากว่า GLPK และ Octave (เหมือนว่า Octave ใช้ฟังก์ชันของ GLPK นะ อันนี้ไม่แน่ใจ)   หากพูดถึงวิธีการเขียนโปรแกรมแก้ปัญหาบน MATLAB และ Octave แล้วจะเหมือนๆกัน แต่ผมคิดว่ามันยุ่งยากกว่าทำบน GLPK ครับ มันแตกต่างอย่างไร (สักวัน)คงจะเก็บไปเขียนภาคต่อของบทความนี้

ถ้าคุณไม่มีงบ แต่ยังอยากใช้ Solver เวอร์ชันขาย และเป็น Solver ที่มีชื่อในท้องตลาด ก็มีทางสว่างอยู่ โดยไม่ต้องไปทำอะไรผิดกฎหมายแต่อย่างใด นั่นคือ ที่แผนก Mathematics and Computer Science Division ของ Argonne National Laboratory เขามีกลุ่มของเซิร์ฟเวอร์ที่ติดตั้ง Solver ไว้หลายยี่ห้อด้วยกัน โดยเรียกว่าเป็นบริการที่ชื่อ NEOS Solvers โดยผู้ใช้สามารถเข้าไปหน้าเว็บ NEOS Solvers จากนั้น ผู้ใช้ก็เลือก Solver ที่ต้องการนำมารันปัญหาแล้วก็ส่งไฟล์ของปัญหาที่เขียนด้วยภาษาสคริปต์ที่ Solver สนับสนุน เมื่อส่งไฟล์สคริปต์ไปที่ Solver แล้ว ไฟล์ของปัญหาจะถูกจัดเข้าคิวเพื่อรอรันโดย Solver ที่ผู้ใช้เลือก เมื่อปัญหาถูกรันแล้ว ผลลัพธ์ที่ได้จะถูกแสดงบนหน้าเว็บ และผู้ใช้สามารถให้ผลลัพธ์ถูกส่งกลับไปยังอีเมลที่กำหนดได้อีกด้วย

ใน NEOS Solvers  มี Solver เวอร์ชันขายที่มีชื่อเสียงกันให้ใช้กันฟรีๆซะด้วย อาทิเช่น LINDO, MINTO, MOSEK, BARON, XpressMP เป็นต้น อย่าง LINDO ผมเคยได้ยินชื่อเสียงมาระยะหนึ่งแล้วว่ามันเก๋า ในหน้าเว็บของ LINDO อ้างว่า บรรดาบริษัทชั้นนำใน Fortune 500 กว่าครึ่งนั้นใช้ LINDO และใน 25 อันดับแรกของ Fortune 500 มี 23 บริษัทที่ใช้ LINDO เลยแหละ

โดยรวมแล้ว ผมค้นพบว่า Solver เวอร์ชันขายทำงานได้เร็วกว่า GLPK และ Octave แบบเห็นได้อย่างเช่นเจน เนื่องจาก Solver แบบขายเขาใช้ algorithm ที่ออกแบบมาเป็นพิเศษและหลายตัวก็เป็นสูตรลับของแต่ละ Solver บางตัวก็ถูกออกแบบมาให้ทำงานกับโปรเซสเซอร์ใหม่ๆได้อย่างเต็มประสิทธิภาพ เช่น บางตัวสามารถรันได้แบบ parallel และใช้หน่วยคำจำน้อย เป็นต้น อย่างไรก็ดี สิ่งที่ผู้ใช้พึงเตรียมใจในการใช้ NEOS Solvers คือ บริการนี้เตรียมเซิร์ฟเวอร์ที่จำกัดขนาดคิวของงานที่ส่งมาจากผู้ใช้ ดังนั้น ถ้าในช่วงที่มีคนนำงานมารันเยอะๆอยู่แล้ว กว่างานที่เราจะได้รับการประมวลผลก็จะนานพอควร (อาจจะเป็นวันกว่าจะได้เริ่มรัน)

CPLEX

สำหรับผมเอง ผมเลือกใช้ Solver เวอร์ชันขายที่ชื่อ CPLEX หรือ IBM ILOG CPLEX ซึ่งเป็น Solver ที่แก้ปัญหา optimization ได้เร็วมากๆ ถ้าผมบอกว่าเร็วกว่า GLPK หลายสิบหลายร้อยเท่า มันก็เหมือนว่าผมโฆษณา (แต่มันเร็วอย่างนั้นจริงๆนะ ไม่ได้โม้) เช่น ผมรันปัญหา integer programming ที่มีจำนวน variable 46,089 หน่วย และจำนวน constraint ถึง 34,560 หน่วย ถ้าเป็นแต่ก่อนที่ผมใช้ GLPK นะ ผมรันนานจนกระทั่งว่าออกไปดื่มกาแฟ แล้วนั่งเล่น แล้วกลับมาดูผล แต่ปรากฎว่ายังรันไม่เสร็จเลย แต่พอเอาปัญหาดังกล่าวไปรันบน CPLEX บนคอมเครื่องเดียวกันกับ GLPK ปรากฎว่า รันไม่ถึง 2 วินาทีน่ะ!! เว่อร์ไหมล่ะ

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

สุดท้ายนี้

Solver ก็เอาไว้แก้ปัญหา Optimization นะครับ และผมกล้าบอกได้เลยว่า หลายบริษัททั่วโลกพึ่งพา Solver เพื่อแก้ปัญหาต่างๆในการดำเนินงานหรือตัดสินใจ และผลลัพธ์จากการแก้ปัญหา optimization นั้นก็ช่วยให้บริษัทเหล่านั้นประสบความสำเร็จไม่มากก็น้อย ผมขออ้างอิงจากหนังสือ Introduction to Operations Research 9th Edition ของ McGRAW-Hill เขายกตัวอย่างบริษัทที่ประสบความสำเร็จจากการแก้ปัญหา optimization ในระบบ/ปัญหาการดำเนินงานต่างๆ เช่น

  • Time Inc. ทำกำไรเพิ่มขึ้นกว่า 3.5 ล้านเหรียญต่อปี จากระบบจัดการช่องทางการส่งนิตยสาร
  • United Airlines ประหยัดงบได้ถึง 6 ล้านเหรียญต่อปี จากระบบวางแผนตารางเวลาของพนักงานบนเครื่องบินและระบบจองตั๋ว
  • Swift & Company ประหยัดงบได้ถึง 12 ล้านเหรียญต่อปี จากการปรับปรุงการขายและการผลิต
  • Waste Management ประหยัดงบได้ถึง 100 ล้านเหรียญต่อปี จากการปรับปรุงเส้นทางของการรวบรวมและกำจัดขยะ
  • Samsung สร้างรายได้เพิ่มขึ้นกว่า 200 ล้านเหรียญต่อปี จากการลดเวลาในการผลิต
  • AT&T ทำกำไรเพิ่มขึ้นได้กว่า 750 ล้านเหรียญต่อปี จากการออกแบบระบบ call center
  • Deere & Company ประหยัดงบจากระบบจัดการโกดังสินค้าได้กว่า 1 พันล้านเหรียญต่อปี!!!

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

64 thoughts on “Solver กับปัญหา Optimization

  1. jutharat says:

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

    • ตอนนี้ผมมาทำงานที่ มจธ. ถึงแค่ 24 สิงหาครับ หลังจากนั้นจะกลับสิงคโปร์ครับ ไม่ทราบมีปัญหาเรื่องใดหรือครับ

    • ผมไม่เคยใช้นะครับ แต่ทั้งสองตัวสร้างโดยบริษัทเดียวกันครับ Lindo เป็นเครื่องมือ ส่วน Lingo เป็น API ทั้งสองก็ไว้แก้ปัญหา optimization ครับ

    • ผมแก้ปัญหาประมาณ assignment problem น่ะครับ ก็คล้ายๆกับ allocation ครับผม แต่ผมใช้ CPLEX ใน GAMS นะครับ

      • beebae says:

        ถ้าเริ่มต้นจะใช้ cplex อย่างคนไม่เคยใช้มาก่อน ต้องเริ่มจากจุดไหนก่อนคะ

    • ผมไม่ได้ใช้ CPLEX ตรงๆครับผม ผมใช้ CPLEX ผ่านภาษาและเครื่องมือพัฒนาที่ชื่อ GAMS คือ GAMS มันมีภาษาสำหรับแก้ปัญหา optimization และเราสามารถเลือก solver ที่ต้องการได้ (เช่น เลือก CPLEX สำหรับแก้ปัญหา mixed integer)

      ผมแนะนำให้เล่น GAMS ดูก็ได้ครับ มันมาพร้อม solver เวอร์ชันทดลองหลายๆตัว (รวม CPLEX ด้วย) แต่เวอร์ชันทดลองมันเล่นได้แค่ 300 ตัวแปรกับ 300 constraint สำหรับปัญหา linear + mixed integer programming ถ้าต้องการแก้ปัญหาที่ใหญ่กว่านั้นต้องซื้อ license ของ solver ที่การต่อไปครับผม ดูข้อมูลเพิ่มเติมที่ http://gams.com/ ครับ

  2. Chanchai says:

    พี่ครับ
    ผมมีปัญหาจะปรึกษา ตอนนี้ผมกำลังเรียนโทอยู่ ทำวิจัยเกี่ยวกับ Optimize วางแผนการผลิต
    โมเดลผมมี Variable ประมาณ 4 หมื่น Constraint ประมาณ 6 พัน
    Lingo หาคำตอบนานมาก ผมรันไป 8 ชั่วโมงกว่าแล้วยังไม่ได้คำตอบเลย
    ผมควรเปลี่ยนไปใช้โปรแกรมไหนดีครับ

    • Chanchai says:

      ปล. ถ้าผมอยากปรึกษาพี่หลังไมค์ได้มั้ยครับ

    • ผมไม่แน่ใจเหมือนว่าถ้าใช้ตัวอื่นจะเร็วขึ้นหรือเปล่าครับ มันขึ้นกับความซับซ้อนของ constraint ด้วยว่ามีบวกลบคูณหารและตัวแปรที่เกี่ยวข้องในแต่ละ constraint มากขนาดไหนด้วยครับ และถ้่าปัญหาใหญ่มาก ก็ต้องใช้คอมแรมเยอะๆเข้าช่วยด้วยครับ

  3. gib says:

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

  4. Aot says:

    THanks na krub for the article. It is very useful for me at this time. I must say that your internet article is every useful for students who doing research.

    Aot.. Hope all good thing you have done will be back to you soon.

  5. หก says:

    คืออยากถามว่า heuristic กับ Mixed integer programming มันต่างกันยังไงหรอครับ

    • heuristic มันเป็นวิธีที่ออกแบบมาเพื่อหา optimal solution (วิธีที่เหมาะสมที่สุด) แต่ไม่รับประกันว่าจะได้ optimal solution ปกติจะเรียกว่าได้ near optimal หรือ suboptimal ครับ

      ส่วน integer programming เป็นวิธีการ formulation/model ตัวปัญหาเพื่ออธิบายขอบเขตและเป้าหมายการหา optimal solution แต่ไม่ได้ระบุวิธีแก้ปัญหา

      สรุป heuristics เป็นวิธีแก้ปัญหา integer programming เป็นวิธีโมเดลปัญหาครับ เราอาจใช้ heuristics ไปแก้ปัญหา integer programming ก็ได้ แต่ไม่รับประกันว่าจะได้ optimal solution

  6. p.limsakul@ieee.org says:

    ถ้าผมจะลองใช้ GAMS ผมต้องมีความรู้พื้นฐานอะไรบ้างครับ

    • ต้องสร้าง optimization model เป็นครับ ถ้ามีพื้น computer programming ด้วยจะทำให้ศึกษาและแก้ปัญหา optimization ที่ซับซ้อนได้ง่ายขึ้นครับ

  7. พี่พอรู้ ความเป็นมาของ ibm ilog cplex ไหมครับ รู้ข้อมูลคร่าวๆของมันอ่ะครับ ขอเป็นภาษาไทยนะครับ คือผม Search เป็นภาษาอังกฤษแล้วผมอ่านไม่รุ้เรื่อง ขอบคุณมากครับ

    • พี่ไม่ทราบความเป็นมาของ ilog cplex ครับ พี่ไม่สนใจว่ามันเป็นมายังไงน่ะครับ

  8. Toy says:

    ตอนนี้ผมใช้ GAs แก้ปัญหา optimization ไม่ทราบว่า GAMS & CPLEX ทำ GAs ได้หรือไม่ครับ

    • GAMS เป็นตัวภาษา ส่วน CPLEX เป็น optimization solver ไม่ได้ใช้ GA แต่ใช้ Simplex และ Branch and Cut ในการแก้ปัญหา ซึ่งเป็นต้นตำรับในการหา global optima ของ linear/integer programming เหมาะและเร็วกว่า GA มากครับ

  9. chairat sarawanawong says:

    ผมทำงานเป็นที่ปรึกษาระบบ ERP ใน module PP มาหลายปี อยากศึกษาเพิ่มเติมทางด้าน optimization กำลังการผลิต พอจะแนะนำ course ที่ไหนในเมืองไทย หรือหนังสือให้อ่านไหมครับ

    • สวัสดีครับ

      ตอบตามความเข้าใจของผมนะครับ (ซึ่งอาจจะผิดได้) ผมคาดว่าถ้าคอร์สในไทย น่าจะสอนโดยอาจารย์จากภาคคณิตศาสตร์ประยุกต์​ และลในสายเศรษฐศาสตร์ก็มีสอนครับ และในระดับปอโท/เอกสำหรับวิศวกรรม ก็น่าจะมีวิชา optimization หรืออาจจะอยู่ในวิชา Operations Research ดังนั้น มหาลัยที่มีสาขาพวกนี้น่าจะเปิดสอน optimization ครับผม

      จากที่ผมได้ศึกษามา ผมพบว่า optimization สำหรับกำลังผลิต / production planning นั้นมีเปเปอร์ให้อ่านเยอะมาก และมี case study ที่ใช้ในบริษัทใหญ่ๆที่เขาตีพิมพ์ให้อ่านเยอะครับ โดยเฉพาะอย่างยิ่ง เป็นเปเปอร์ที่ส่งเข้า INFORMS ( http://www.informs.org/ ) จะเป็นงานที่มีคุณภาพมากและประยุกต์ใช้จริงครับ

      ผมเองทำสาย capacity expansion planning โดยเน้นไปที่ power plant และ datacenter สำหรับ cloud computing ครับ ซึ่งมันก็มีส่วนคล้ายกับ PP อยู่ ตรงที่ว่าผมสนการขยายกำลังผลิตไฟฟ้า หรือ ขยายจำนวน server ใน datacenter ว่าควรขยายเพิ่มหรือลดจากเดิมเท่าไหร่ให้​พบกับ demand โดยต้อง minimize cost ในการลงทุน และผมเน้นไปที่ demand ที่ไม่แน่นอน (uncertainty) ซึ่งสถานการณ์จริงก็มักเป็นเช่นนั้นครับ วิธีที่ผมใช้คือ stochastic programming (SP) ลองพิจารณา SP ดูด้วยก็ดีครับ

  10. gib says:

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

    • ผมไม่เคยใช้ lingo เลยไม่เคยเปรียบเทียบครับ ส่วน CPLEX นั้น ผมว่าแก้ IP หรือ MIP ค่อนข้างเร็วครับ อยู่ที่จำนวน variable + constraint ด้วยครับ จากโจทย์ของคุณผมว่าน่าจะแก้ปัญหาได้ไม่นานครับ

  11. Niagin says:

    รบกวนถามด้วยคนครับ มี stochastic Solver ตัวไหนที่ใช้แก้ปัญหาประเภท constrained nonlinear optimization บ้างมั๊ยครับ
    แล้วปัญหาประเภทดังกล่าวมีจำนวน variable ประมาณเท่าไหร่จึงจะเรียกว่ายากหรอครับ (หลักสิบ ร้อย หรือพัน?)

    ขอบคุณครับ

  12. Niagin says:

    สวัสดีครับ ผมกำลังเรียนป.โทอยู่และทำงานวิจัยเรื่องนี้ด้วย ได้มาอ่านบทความของอาจารย์ดีมากๆเลยครับ

    ผมรบกวนถามด้วยคนนะครับ ไม่ทราบว่าอาจารย์พอแนะนำ Solver ตัวไหนที่สามารถแก้ปัญหา constrained nonlinear optimization ได้บ้างครับ

    แล้วปัญหาประเภทด้งกล่าวนี้ ถ้าจะจัดเป็นปัญหาที่ยาก ควรจะเซตให้มี constraints และ variables ประมาณเท่าไหร่ดีครับ (หลักสิบ ร้อย หรือพัน) หรือมี benchmark อะไรน่าสนใจบ้างครับ

    ขอบคุณครับ

    • ยินดีครับ

      มันตอบยากว่าปัญหายากหรือง่าย โดยเฉพาะ non linear มันก็ซับซ้อนกว่า linear อยู่แล้ว มันต้องดูว่า NL function ซับซ้อนแค่ไหน มีเยอะเท่าไหร่ จำนวน var constraint มันเป็นลักษณะของปัญหา เราคงไม่มาลดหรือเพิ่มจำนวนเพื่อให้แก้ปัญหาให้ง่ายหรือท้าทาย ยกเว้นมีจุดประสงค์เรื่อง performance analysis หรืออื่นๆ

      ต้องลองรันดูน่ะครับ แต่ solver พวกนี้ราคาแพง อาจหลายหมื่นจนแสนครับ

      ลองกูเกิลคำว่า gams solver แล้วหาตัวที่เป็น NLP แต่มันขายนะครับ แนะนำให้เมลถามทีมเซลส์ GAMS ให้เขาแนะนำตัวที่เข้ากับปัญหาคุณ ผมก็ซื้อจากบริษัทนี้ครับ ผมใช้ cplex สำหรับ LP ส่วน conopt กับ minos สำหรับ NLP ครับ

      • Niagin says:

        ขอบคุณมากครับ ผมเห็นคำโฆษณาของ conopt แล้วช็อก
        รันได้ในปัญหา 10,000 – 1,000,000 constraints และ decision variables 500 ตัว – -“

      • ใช่ครับ แต่ก็มีสเปคคอมแรงๆด้วยครับ แรมใหญ่ๆ ถ้าได้ 64GB หรือมากกว่า อะไรๆก็สะดวกครับ

    • คำว่า solver ในที่นี้ คือ ตัวแก้ปัญหา optimization ครับ มันเป็นศัพท์พื้นฐาน อยู่ที่ว่า solver แทนตัวไหนมากกว่าครับ

  13. Tong says:

    รบกวนปรึกษาด้วยครับ ผมกำลังทำปัญหาเรื่อง vehicle routing ด้วยวิธี branch-and-price (ทำ column generation ก่อน แล้วต่อด้วย branch-and-bound) ไม่ทราบ CPLEX จะสามารถแก้ปัญหานี้ได้ไหมครับ?

    ผมพยายามศึกษาใน Example ใน CPLEX แล้ว มันแก้ปัญหา Cutting stock ได้ แต่ปัญหาของผมมันต้องมีการเพิ่ม Column ในทุกๆรอบน่ะครับ

    ขอบคุณมากครับผม

      • Tong says:

        ขอบคุณมากครับผม ไม่ทราบผมเข้าใจความหมายของประโยคนี้ถูกไหมครับ

        “When solving MIPs, the CPLEX APIs offer limited functionality to apply column generation to child node problems (also known as branch and price). This limitation arises because CPLEX does not directly permit the modification of node problems, a modification which is essential for column generation in the CPLEX branch and bound algorithm.”

        หมายความว่าผมต้องไปใช้โปรแกรมอื่นข้างนอกมาช่วยในการแก้ปัญหา (modification of node problem) หรือใช้ภาษาอื่นนอกจาก OPL เช่น C++ Java หรือ .NET ใช่ไหมครับ

        ขอบคุณมากครับ

      • ก็ไม่เชิงครับ คือ CPLEX มันเป็นแค่ solver ที่มี API ให้ใช้กับภาษาคอมพิวเตอร์ตัวอื่นๆอีกทีนึงครับ จะใช้ CPLEX ได้ ก็ต้องรู้ภาษาคอมพิวเตอร์เพื่อโมเดลปัญหา ไม่ก็ต้องใช้ภาษาที่ออกแบบมาเพื่อโมเดลเช่น GAMS กับ AMPL ครับ

      • Tong says:

        ได้ครับ ผมจะลองดูนะครับ ขอบคุณมากนะครับคุณ javaboom

  14. Siriyun says:

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

    • งานด้าน VRP มันมีคนค้นคว้ามาเยอะแล้วครับ เป็นปัญหาเก่าแก่มานานแล้ว ผมแนะนำให้ค้นคว้าจาก textbook และเปเปอร์ในฐานข้อมูลวิชาการดูนะครับ ห้องสมุดตามมหาลัยเขามีบริการฐานข้อมูลพวกนี้เยอะครับ

  15. ดีคุง says:

    พี่ครับ ผมอยากทราบว่า โปรแกรมที่รองรับ simplex นี่มีอะไรบ้างเหรอครับ แล้วมันรับกี่ตัวแปรครับ ^^

    • มีหลายตัวเลยครับ simplex มันเป็นอัลกอริธึมพื้นฐาน MATLAB Maple Octave Mathematica GLPK CPLEX และอีกมากมายก็สนับสนุน simplex ครับ

      ส่วนรองรับได้กี่ตัวแปร ต้องอ่านคู่มือหรือถามเซลส์ของซอฟต์แวร์ ผมไม่ทราบ ผมใช้ CLEX ล้านกว่าตัวแปรก็สนับสนุนครับ

  16. FL says:

    พี่ค่ะ ในระบบการรันแบบ linaer กับ non-linear ต่างกันอย่างไรบ้างค่ะ รบกวนข้อข้อมูลด้วยค่ะ ขอบคุณค่ะ

    • ถ้า plot ค่าของตัวแปรต่อกันแล้วไม่เป็นเส้นตรงก็เป็น non-linear ครับ

  17. Thanachot says:

    จะสอบถามอะไรหน่อยอ่ะครับ ว่า LP กับ MIP มันต่างกันอย่างไรหรอครับ

  18. RNA says:

    ขอโทษนะคะ พอมีข้อมูลอธิบายการใช้งานคร่าวๆหรือข้อดีของการใช้งานของโปรแกรม CPLEX ไหมคะ
    ขอบคุณมากคะ

    • ผมไม่มีเลยครับ ถ้ากูเกิลหาออนไลน์น่าจะพอมีคนอื่นแชร์ไว้อยู่ครับ

  19. Kanokporn says:

    ขอโทษน่ะคะ กำลังทำปริญญานิพนธ์แล้วติดปัญหาเรื่องตัวsolverอ่าค่ะอยากจะขอคำปรึกษาหลังไมค์ได้ไหมคะ

    • ได้ครับ แต่อยู่ที่คำถามนะครับ เพราะผมก็ไม่ได้ชำนาญอะไรครับ

      • kanokporn says:

        สามารถติดต่อได้ที่ช่องทางใดบ้างคะ ขอบคุณค่ะ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s