Roflin, Eddy and Octarina, Sisca and Bangun, Putra Bahtera Jaya and Atmanegara, Cytra Ria and Zulvia, Ferani Eva (2014) SUBSTITUTING GOMORY CUTTING PLANE METHOD TOWARDS BALAS ALGORITHM FOR SOLVING BINARYLINEAR PROGRAMMING. Bulletin Of Mathematics, 6 (1). pp. 1-13.
Preview |
Text
Bulliten Matematika Gabung.pdf Download (4MB) | Preview |
Abstract
Application of binary linear programming can be found in many fields such as scheduling, production planning, networking and etc. Unlike linear pro- gramming problems, binary integer linear programming problem is more difficult to solve since its variables must be abinary number zero or one. Thus, solving this problem efficiently becomes an interesting issue. This paper proposes a combination of Balas additive method and Gomory cutting plane method. Balas additive method is awell known method in binary linear programming. It systematically enumerates subset of thepossible binary solution to ensure all possible solutions are examined. In this paper, adraw back of this method which is requiring long iterations is fixed. It uses the Gomory cutting plane method to eliminatenon-integerpar- tial solution. The Gomory cutting plane method generates an additional constraint to eliminateanon-integer solution. Ingeneral, this additional constraint increases the problem complexity. Therefore, combining Balas algorithm and Gomory cutting plane method can solve binary linear problem faster without facing more complex mathematical model. Substituting Gomory cutting plane to the Balas algorithmis conducted by performing the cut based on condition in Gomory algorithm towards the enumeration process conducted by Balas algorithm. The computational result using a test function proves that the proposed substituting strategy can solve binary linear programming efficiently which is shown by the number of iterations required by thismethod.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Binary linear programming, Balas algorithm, Gomory cutting plane. |
| Subjects: | Q Science > QA Mathematics > QA1-939 Mathematics > QA37.3.1.64 Applied Mathematics |
| Divisions: | 08-Faculty of Mathematics and Natural Science > 44201-Mathematics (S1) |
| Depositing User: | Putra Bahtera Jaya Bangun |
| Date Deposited: | 08 Sep 2022 01:18 |
| Last Modified: | 08 Sep 2022 01:18 |
| URI: | http://repository.unsri.ac.id/id/eprint/74623 |
Actions (login required)
 |
View Item |