Chulalongkorn University Theses and Dissertations (Chula ETD)
Identifying non-binding constrints in linear programming problems using supervised learning neural networks
Other Title (Parallel Title in Other Language of ETD)
การระบุเงื่อนไขบังคับแบบนอนไบน์ดิงในปัญหากำหนดการเชิงเส้นโดยใช้โครงข่ายประสาทเทียมซึ่งมีการเรียนรู้แบบกำกับดูแล
Year (A.D.)
2004
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Computational Science
DOI
10.58837/CHULA.THE.2004.1117
Abstract
This thesis proposed an approach for identifying non-binding constraints in a linear programming problem (LP). A supervised learning neural network 9NN) was applied in the prediction method. The inputs of neural network were composed of the coefficients of the objective function, the coefficients of the constraints and the right-hand-side constants of linear programming problems. For each target of neural network, it set to 1 fif the constraint was binding and O if the constraint was non-binding. We considered specifically the LP that has a unique optimal solution and fixed the problem size to m x n dimensions where n was varied from 2 to 4 and m was varied from n to n+2. Moreover, the back propagation (BP) algorithm was selected for training neural networks. The result of this research showed the accuracy of neural networks that identified non-binding constraint
Other Abstract (Other language abstract of ETD)
วิทยานิพนธ์นี้เสนอ วิธีการระบุเงื่อนไขบังคับแบบนอนไบน์ดิงในปัญหากำหนดการเชิงเส้น โดยนำโครงข่ายประสาทเทียมซึ่งมีการเรียนรู้แบบกำกับดูแล มาประยุกต์ใช้ในขั้นตอนการทำนายเงื่อนไขบังคับข้อมูลนำเข้าของโครงข่ายประสาทเทียมประกอบด้วย ค่าสัมประสิทธิ์ของฟังก์ชันจุดประสงค์ ค่าสัมประสิทธิ์ของเงื่อนไขบังคับ และค่าคงที่ทางขวามือของปัญหากำหนดการเชิงเส้น สำหรับค่าเป้าหมายในการเรียนรู้ของโครงข่ายประสาทเทียมจะกำหนดให้เป็น 1 เมื่อเงื่อนไขบังคับนั้นเป็นแบบไบน์ดิง และให้เป็น 0 เมื่อเงื่อนไขบังคับนั้นเป็นแบบนอนไบน์ดิง โดยงานวิจัยนี้จะพิจารณาเฉพาะปัญหากำหนดการเชิงเส้นที่มีผลเฉลยเพียงคำตอบ และมีขนาด m x n มิติ โดย n มีค่าตั้งแต่ 2 ถึง 4 และ m มีค่าตั้งแต่ n ถึง n+2 และเลือกใช้ขั้นตอนวิธีแบบแบคพรอพาเกชันในการฝึกสอนโครงข่ายประสาทเทียม ผลของงานวิจัยจะเสนอในรูปของเปอร์เซ็นต์ความถูกต้องในการทำนายเงื่อนไขบังคับแบบนอนไบน์ดิงของโครงข่ายประสาทเทียม
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Atisattapong, Wanyok, "Identifying non-binding constrints in linear programming problems using supervised learning neural networks" (2004). Chulalongkorn University Theses and Dissertations (Chula ETD). 56277.
https://digital.car.chula.ac.th/chulaetd/56277