ปัญหา bipartite boolean quadratic programming problem (BQP01) จำลองสถานการณ์ที่เรามีวัตถุสองกลุ่ม และต้องการเลือกวัตถุชุดหนึ่งที่เกิดประโยชน์สูงสุด โดยผลได้ผลเสียจากการเลือก มีทั้งผลที่ขึ้นกับการเลือกวัตถุแต่ละชิ้น และผลจากการเลือกคู่ของวัตถุที่อยู่ต่างกลุ่ม
ที่ผ่านมา ปัญหา BQP01 ถูกนำไปใช้ในหลากหลายสาขา ตั้งแต่งานในแวดวงคณิตศาสตร์อย่าง graph theory และ matrix factorization ไปจนถึงศาสตร์อื่น ๆ อย่าง bioinformatics และ statistical mechanics
เพื่อให้เห็นภาพของปัญหาชัดเจนขึ้น จะยกตัวอย่างการสร้างท่าเรือข้ามฟากบนสองฝั่งแม่น้ำ ตำแหน่งต่าง ๆ ที่จะตั้งท่าเรือได้ มีแนวโน้มกำไรขาดทุนจากการตั้งท่าเรือเป็นของตัวเอง (ผลที่ขึ้นกับการเลือกวัตถุแต่ละชิ้น) หากตั้งท่าเรือที่ไหน ต้องมีเรือจากท่านั้นไปยังท่าเรืออื่น ๆ บนอีกฝั่งเสมอ และเส้นทางการเดินเรือระหว่างท่าเรือแต่ละคู่ ต่างก็มีแนวโน้มกำไรขาดทุนของแต่ละเส้นทาง (ผลจากการเลือกคู่ของวัตถุที่อยู่ต่างกลุ่ม) จะเห็นได้ว่าปัญหา BQP01 ก็คือการเลือกว่าต้องตั้งท่าเรือที่ใดบ้าง แนวโน้มของกำไรสุทธิจึงจะมีค่าสูงสุด
ในทางคณิตศาสตร์ ปัญหา BQP01 จัดเป็นปัญหา quadratic programming ที่มีเงื่อนไขจำเพาะสำหรับ objective function และมี feasible set เป็นเซตของเวกเตอร์ที่มีสมาชิกเป็น 0 หรือ 1
การแก้ปัญหา BQP01 โดยตรงนั้นทำได้ยาก เทคนิคหนึ่งที่นิยมใช้คือ linearization ซึ่งจะแปลงปัญหา BQP01 เป็นปัญหา integer linear programming ที่มีเครื่องมือในการแก้ปัญหาหลากหลายกว่า และเครื่องมือสำคัญหลายชิ้นก็ต้องอาศัยข้อมูลจาก convex hull ของ feasible set สำหรับปัญหาใหม่ ที่เรียกว่า bipartite boolean quadric polytope อันเป็นหัวข้อหลักของงานวิจัยชิ้นนี้นั่นเอง
ผู้วิจัย
อ. ดร.ปิยฉัตร ศรีประทักษ์
ภาควิชาคณิตศาสตร์ คณะวิทยาศาสตร์ มหาวิทยาลัยเชียงใหม่
ร่วมกับนักวิจัยจาก Simon Fraser Universityอ้างอิง
Sripratak, P., Punnen, A. P., & Stephen, T. (2021).
The bipartite boolean quadric polytope. Discrete Optimization,
100657.
Impact Factor 1.222 (Q1 Scopus)
อ่านงานวิจัยได้ที่
https://doi.org/10.1016/j.disopt.2021.100657