GAMS พร้อมกับ CPLEX Solver

แผ่นซอฟต์แวร์ GAMS เวอร์ชัน 2.50 พร้อม CPLEX

ช่วงนี้มีความสุขมาก เนื่องจากเมื่อสามสัปดาห์ที่ผ่านมา อาจารย์ของผมอนุมัติให้สั่งซื้อ optimization solver ที่ชื่อว่า CPLEX  ซึ่งจริงๆแล้ว ผมเคยทำเรื่องขอให้ภาควิชาซื้อซอฟต์แวร์แนวนี้มาใช้ตั้งแต่ปีก่อนแล้ว แต่เรื่องไม่เคยดำเนิน ทำให้ที่ผ่านๆมา ผมต้องพึ่งพา GLPK กับ MATLAB  และก็ NEOS Solvers แต่มันไม่ค่อยโดยใจผมน่ะ เพราะเวลาผมทำการทดลองอะไรบางอย่าง มันใช้เวลาคำนวณนานเกินไป เกินกว่าที่วัยรุ่นอย่างผมจะรอได้ จนกระทั่งได้ CPLEX มา โอ่ว!…ชีวิตของผมเปลี่ยนไปเยอะเลย

แนะนำหัวข้อ Project ปี 4 – Linear Programming with CUDA

• หัวข้อปัญหา – การแก้ปัญหาโปรแกรมเชิงเส้นโดยใช้ความสามารถของโปรเซสเซอร์ประมวลผลกราฟิก
• อธิบายปัญหาคร่าวๆ – เป็นการพัฒนาซอฟต์แวร์ประเภท optimization solver ให้สามารถแก้ปัญหาโปรแกรมเชิงเส้น (linear programming) โดยใช้สมรรถนะของโปรเซสเซอร์ประมวลผลกราฟิก (หรือ GPU)
• เครื่องมือในการพัฒนา - CUDA (แนะนำว่าควรใช้ C/C++ binding ของ CUDA เนื่องจากเป็นโค้ดที่เสถียรสุด)
• ทักษะในการพัฒนา 1. ภาษา C/C++ 2. เข้าใจ simplex method 3. เข้าใจพื้นฐานการพัฒนาโปรแกรมแบบขนาน (parallel programming) อย่างไรก็ตาม ข้อ 2. กับ 3. พัฒนาหรือรื้อฟื้นกันได้
• งานที่เกี่ยวข้อง – ลองอ่านผลงานชื่อ Linear Programming on modern GPUs อย่างไรก็ดี เราควรหาแนวทางที่แตกต่าง อย่าเช่นเราควรพัฒนา optimization solver ที่สนับสนุนให้ผู้ใข้สามารถแก้ปัญหาโปรแกรมเชิงเส้นด้วยเครื่องมือหรือภาษาทางคณิตศาสตร์ที่ได้รับการยอมรับหรือใช้อย่างกว้างขวาง เช่น MATLAB OCTAVE หรือ GNU MathProg ซึ่งจะทำให้ซอฟต์แวร์ใช้ได้กับปัญหาโปรแกรมเชิงเส้นแบบทั่วไปได้อีกด้วย
• ตัวอย่างของผลลัพธ์ที่คาดหวัง – ได้ออกมาเป็น optimization solver ที่สามารถแก้ปัญหาเชิงเส้นด้วยการเขียนสคริปต์ของ MathProg ด้วยการใช้ GPU และความเร็วที่ได้ควรเร็วกว่า CPU อย่างมีนัยสำคัญ
• แนวทางที่พลิกแพลงได้ – ถ้าหากค้นคว้างานที่เกี่ยวข้องเพิ่มเติมเองแล้ว พบว่ามีคนทำไปแล้ว ลองพิจารณาปัญหาประเภท non-linear programming, quadratic programming, และ integer programming ดูก็ได้ งานนี้จึงสามารถพัฒนาแตกแขนงจากรุ่นหนึ่งไปสู่รุ่นหนึ่งได้เรื่อยๆ

โพสต์ครั้งแรกที่ blognone

Solver กับปัญหา Optimization

นานมาแล้วที่ blog ร้าง เนื่องจากช่วงที่ผ่านมาครอบครัวมาเยี่ยม 20 กว่าวัน มาบวกกับกำลังเริ่มงานวิจัยชิ้นใหม่อยู่ อะ ตัดฉากมาที่หัวข้อเลยดีกว่า ว่าอะไรคือ Solver?

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 เป็นต้น