In this study, we addressed Single Objective Linear Programming (SOLP). This article proposed a new combination of Chaos Optimization Algorithm (COA) with Affine Scaling Search (AFS) to be used as a Hybrid COA and AFS algorithm (Chaos AFS) for solving SOLP. The potential of COA as an emerging optimization algorithm to improve efficiency and effectiveness of AFS is investigated. Chaos AFS method is so-called numerical search algorithm that searches through the domain of decision variables of SOLP to obtain final feasible solution. An initial solution point, obtained from COA, will be used as starting solution point in AFS algorithm to improve the performance of AFS algorithm. The result shows that Hybrid COA and AFS for solving SOLP problems significantly improves the results of objective value compared to pure AFS and reduces the number of iteration steps compared to simplex and pure AFS.
Linear Programming (LP) has been proven to be useful in numerous field of application in operation research and engineering fields, such as telecommunication, electrical, and structural engineering as well as computer science since the invention of Simplex Algorithm by George Dantzig in 1947. Single Objective Linear Programming (SOLP) is an LP consists of one objective function subject to one or more linear constraints [1]. The general notation for LP is min/max {cTx:Ax=b,x≥0}{cTx:Ax=b,x≥0}, where c∈nℜ,b∈mℜ,x∈nℜc∈ℜn,b∈ℜm,x∈ℜn and A∈ℜm×nA∈ℜm×n. Simplex algorithm searches through extreme point in boundary of feasible region to find optimal solution of LP problem. Simplex algorithm was a predominant method to solve LP until 1984 when Karmarkar published new method of solving LP. Since Karmarker's breakthrough with his polynomial time algorithm to solve linear programming, Interior Point Methods (IPM) grow significantly and become one of the most efficient method in optimization of linear convex problems. The ability of IPM to efficiently solve structured, sparse and large-scale LP problem becomes the reason of choice and one of researcher's main agenda in LP research [2] and [3]. The basic idea of Karmarkar's algorithm, which is so-called IPM, is to search freely in the domain of feasible region instead of search through the extreme point in the boundary of feasible region. IPM has two main approaches which are normal equation approach and augmented system approach [4].
In IPM, an initial feasible solution point has to be determined as a starting point for searching iteration in the domain of decision variables. This starting point determination as initial feasible solution will significantly affect the whole results of the searching process [5] and [6]. Subsequently, a good starting point will lead to near optimal solution. Shengsong et al. [7] has used chaos algorithm with primal-dual search to optimize non-linear optimal power flow problem. The chaos can improve the results and accelerate the process. Chuanwen and Bompard [8] combine chaos with particle swarn optimization for reactive power optimization. In their results, the combination can effectively and practically optimize the shunt capacitor and tap position of load-ratio voltage transformer. In this study, we present a novel combination of Chaos Optimization Algorithm (COA) and Affine Scaling Search (AFS), which is one of IPM methods, to solve SOLP problem. The potential of COA as an emerging optimization algorithm, which moves among feasible points based on ergodicity, stochastic, and regularity of the chaos properties, is investigated to improve efficiency and effectiveness of AFS. Predetermined feasible initial point was improved by implementing COA before being used as a starting point in AFS searching procedure. The results of this new combination of algorithm will be compared to thus from simplex and AFS method.
The structure of the article is as follows: in Section 2, chaos optimization algorithm will be discussed and the chaos optimization algorithm will be presented. The basic theory of interior point method and affine scaling search will be presented in Section 3. In Section 4, problems used in this article will be presented. Proposed method which combines chaos optimization and affine scaling search will be presented in Section 5. All experiment results and comparison between result of simplex method, AFS and combination of COA and AFS will be discussed in Section 6. Finally, conclusion of this study will be in Section 7.
In this article, we presented a new combination of COA and AFS (Chaos AFS) to solve SOLP problems. Optimal solutions obtained from simplex method were used as benchmarks. Large number of iterations was performed by simplex method to obtain the optimal solutions.
From the experiment results, Chaos AFS produced near optimal solution for SOLP problems, and significantly improved AFS algorithm. For SOLP problems, Chaos AFS substantially reduced objective value deviation of 1.73% from optimal solution as well as it reduced number of iterations and CPU time as many as 70.38% and 68.29% respectively compared to AFS method. In addition, with small deviation from optimal value, chaos AFS considerably reduced number of iterations compared to simplex method as many as 98.39%. In conclusion, Chaos AFS can solve SOLP problems more effectively and more efficiently than pure AFS.
A potential result to use the algorithm for Multi-Objective Linear Programming is also shown. Hence, further work is to apply this new combination of Chaos AFS for Multi-Objective Linear Programming problems.
