SUBSTITUTING GOMORY CUTTING PLANE METHOD TOWARDS BALAS ALGORITHM FOR SOLVING BINARYLINEAR PROGRAMMING (similarity)

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 (similarity). Turnitin Universitas Sriwijaya. (Submitted)

[thumbnail of SUBSTITUTING GOMORYCUTTING PLANE METHOD TOWARDS BALAS ALGORITHM FOR SOLVING BINARY LINEAR PROGRAMMING.pdf]
Preview
Text
SUBSTITUTING GOMORYCUTTING PLANE METHOD TOWARDS BALAS ALGORITHM FOR SOLVING BINARY LINEAR PROGRAMMING.pdf

Download (2MB) | 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: Other
Uncontrolled Keywords: Binary linear programming, Balas algorithm, Gomory cutting plane.
Subjects: #3 Repository of Lecturer Academic Credit Systems (TPAK) > Results of Ithenticate Plagiarism and Similarity Checker
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/74686

Actions (login required)

View Item View Item