Mathematics in Applied Sciences and Engineering https://ojs.lib.uwo.ca/mase Volume 3, Number 1, March 2022, pp.12-23 https://doi.org/10.5206/mase/14018 APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS CHRISTIAN ALVIN H. BUHAT, JERSON KEN L. VILLAMIN, AND GENARO A. CUARESMA Abstract. Ant Colony Optimization (ACO) metaheuristic is a multi-agent system in which the be- haviour of each ant is inspired by the foraging behaviour of real ants to solve optimization problem. Set Covering Problems (SCP), on the other hand, deal with maximizing the coverage of every sub- set while the weight nodes used must be minimized. In this paper, ACO was adapted and used to solve a case of Set Covering Problem. The adapted ACO for solving the SCP was implemented as a computer program using SciLab 5.4.1. The problem of determining the optimal location of Wi-Fi Access Points using the 802.11n protocol in the UP Los Banos Math Building (MB) was solved using this metaheuristic. Results show that in order to have 100% coverage of the MB, 7 access points are required. Methodology of the study can be adapted and results of the study can be used by decision makers on related optimization problems. 1. Introduction The Set Covering Problem (SCP) is a typical optimization problem that serves as a model for many applications in the real world. It is a Combinatorial Optimization Problem (COP) which can be formulated as an Integer Linear Programming (ILP) where the goal is to minimize the number of sets such that every element of the set from the universe will be covered and every set is either in the set cover or not. SCP has been used to model problems such as vehicle routing, nurse scheduling, airline crew scheduling, facility location problem, and resource allocation problem (Schiff, 2013). According to Lessing et al (2004), SCP is an NP-hard problem with many developed algorithms that can be used to solve it. Some algorithms can solve a limited size and is also time consuming that is why metaheuristic is advised for solving such problem. Metaheuristic is used to define heuristic methods and it is also a set of algorithmic concepts applicable to a very large set of problems. Ren, et al. (2008), reported that list of kind of heuristics were applied for the SCP and these are Genetic Algorithm (GA), Simulated Annealing Algorithm, and Tabu Search Algorithm. They also conducted a research to solve SCP based from the recently developed, population- based metaheuristic named Ant Colony Optimization (ACO) algorithm. ACO was published in the early 90’s and it is a probabilistic technique about the simulation of real behavior of ants regarding how they function through indirect communication via pheromones (Brezina and Cickova, 2011). Pheromones are chemical substances excreted by ants to attract other ants that are seeking for food. Biologists have observed that ants tend to find the path with the shortest distance between a source of food and their colony which leads in the conclusion that it would be useful to study their individual behavior (Buezas. 2010). Solutions to a given optimization problem are obtained Received by the editors 26 May 2021; accepted 11 January 2022; published online 20, January 2022. 2020 Mathematics Subject Classification. Primary 90B50, 90B80; Secondary 90B10, 90B90. Key words and phrases. Constrained optimization, decision theory, information technology, optimal placement, metaheuristics. 12 https://ojs.lib.uwo.ca/mase https://dx.doi.org/https://doi.org/10.5206/mase/14018 APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 13 by a set of software agents called artificial ants. In applying ACO, the optimization problem must be transformed into the problem of finding the best path on a weighted graph. Hereafter, ants incrementally gets solutions as the graph goes on. ACO is commonly used in solving Traveling Salesman Problem (TSP), but it is also applicable on Set Covering Problems (Dorigo and Stutzle, 2004). Given a set of facilities and the areas covered by the facility, a number of ants determine what facility to choose using a probability function for ACO which is based on pheromone trails and heuristic information, while the area it chooses is randomized. After the chosen areas by the ant satisfies the system constraints or covers all the areas in the system, a next ant will proceed, and the pheromone trails and heuristic information will be updated. This will continue until all ants have passed, and the best solution for the problem is returned and recorded. On 2008, Ren et al proposed a novel ACO-based approach, called Ant-Cover. It has three main dif- ferences between other existing ACO-based approaches: First, for constructing solutions, the approach used single-row-oriented method, next, the use of LaGrange dual information for the search in the solu- tion space, lastly, the use of local search procedure is developed to maintain the feasibility and for the solutions to be improved by ants. This study used a customized Ant-Cover to get a faster near-optimal solution than other metaheuristics. Due to the numerous problems about set covering, this paper is to adapt the Ant Colony Optimization algorithm to solve a Set Cover Problem. In line, this paper is concerned in determining the optimal placement of Wi-Fi Access Points in the University of the Philippines Los Baños (UPLB) Math Building using ACO metaheuristic. 2. Theoretical Framework The Set Covering Problem is a Binary Integer Programming model that seeks to find the minimum number of facilities to be installed and their locations to each demand node is covered by at least one facility (Torregas, 1970). Let I = set of all possible locations for installing a facility, J = set of all areas which are to be covered, xi = { 1, if a facility is to be installed at site i, 0, otherwise; yj = { 1, if whenever a facility is installed at site i the facility covers area j, 0, otherwise. The model can be constructed as: minimize z = ∑ i∈I xi, (2.1) subject to ∑ i∈I xiyij ≥ 1, ∀j ∈ J; (2.2) xi = {0, 1}, ∀i ∈ I. (2.3) The objective function (1) determines the goal of the problem which is to minimize the number of facilities used. The first constraint (2) satisfies the condition that each area j should be covered by at least one facility and the second constraint (3) serves as the binary constraint. 14 CAH. BUHAT, JKL. VILLAMIN, AND GA. CUARESMA 3. Results and Discussion Pseudocode This paper adapts a similar pseudocode to Ren et al. (2008) which uses ACO on solving SCP. The following is the procedure of adapting ACO to solving SCP. Pre-process the given SCP and initialize results Initialize pheromone trails, heuristic information, and related parameters while termination condition is not met do for ant i=1 to n (number of ants) do (a)Construct a solution based on SROM if system constraints are satisfied then move to next ant else repeat (a) end for Update pheromone trails and heuristic information end while Return the best solution found Preprocessing of SCP (General) Based on the SCP Formulation, we transform the problem into an m×n matrix, with m being the areas to be covered and n being the facilities. An element of the matrix will have a value of 1 defining that that area has been covered under that facility, while 0 if it has yet to be covered, i.e., M(i,j) = { 1, if facility j covers area i, 0, otherwise. Table 1. Example of a preprocessed SCP Model 1 2 3 4 5 6 . . . . n 1 1 0 0 1 0 1 0 0 0 0 1 2 0 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 0 4 0 0 0 1 0 0 0 0 0 0 1 5 0 0 0 0 0 1 0 0 0 0 0 6 0 1 0 0 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 1 0 0 0 . 1 0 0 0 1 0 0 0 0 0 0 . 0 0 0 0 0 0 1 0 0 0 0 . 0 0 0 0 0 0 0 0 0 1 0 m 1 0 0 0 0 0 0 0 0 0 0 In the above matrix, this means that area 1 can be covered by facilities in locations 1, 4, 6, ...,n. Parameters Used Values of parameters used in metaheuristics such as ACO are determined by the proponent where a slight change in such values can generate a large difference in the results. In this paper we used values suggested by Ren and others (2008) for the value of our β and ρ. Meanwhile, values for number of APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 15 iterations, initial pheromone trails and heuristic information are standard values used in ACO. Values and definition of variables are given in the table below. Table 2. Definitions and Values of Parameters Used Variable Definition Value Reference β Importance of Heuristic Factor to Pheromone 5 Ren and others (2008) ρ Pheromone Persistence 0.99 Ren and others (2008) ants Number of iterations 1000 Assumed tau(1) Initial Pheromone Trail 1 Assumed heu(1) Initial Heuristic Information 1 Assumed Single row-oriented solution construction method is a novel single-row-oriented solution construction method which can generate solutions in a faster way (compared to other branch-and-bound/branch- and-cut algorithms) and allows ants to explore broader solution areas (Ren and others, 2008). Two of the main ideas of SROM on how it adapts ACO in solving SCP are to: • Randomly select a row I from the row set I • Select a column from the column set J using the probability • Randomly select a row i from the row set I • Select a column from the column set J using the probability P (st = j|rt = i, i ∈ Rt−1) =   τjη β j∑ q∈Ji τqη β q if j ∈ J, 0 otherwise, where Rt−1 denotes the set of uncovered rows before step t, and rt denotes the row chosen at step t. The time complexity of selecting a column from the set Ji is O(|Ji|). Let d be the density of SCP, the average number of columns covering a row can be obtained, ñ = dn. Then we can get a complete solution S with k columns in O(kñ) time. This time complexity is linear with the value of ñ. Generally, ñ � n holds (Ren and others, 2008). Pheromone Trail Update Pheromone trails are decreased uniformly in order to simulate evaporation and allow ants to forget part of the history experience. Ants then deposit an amount of pheromone on the column contained in the best solution. After all the ants have completed a solution, the trails are updated as follows: τj ← ρτj + ∆τj, ∀j ∈ J, ∆τj =   1∑ q∈Sgb Cq if j ∈ Sgb, 0 otherwise. Here, ρ = pheromone persistence (0 ≤ ρ < 1), ∆τj = amount of pheromone put on column j,∑ q∈Sgb Cq = total amount of cost. 16 CAH. BUHAT, JKL. VILLAMIN, AND GA. CUARESMA Pheromone trail updates help the model to adapt to real-time changes, which is one of its advantages over other heuristics such as simulated annealing and genetic algorithm (Selvi and Umarani, 2010). Heuristic Information Update Heuristic Information considers the dual information associated with the still uncovered rows. It mines the specific information of the SCP and provides a good guideline for ants’ search in the solution space. It is updated through: ϕj = |Ij ∩R| , ηj = ϕj cj , where: ϕj = number of new rows that can be covered by column j, R = set of still uncovered rows. These updates help the considered artificial ants in the heuristic to obtain the optimal solution that we need for our LP model (Abd-Alsabour and others, 2013). Program Description Application of Ant Colony Optimization Metaheuristic on Set Covering Problem program generates a near-optimal solution to a preprocessed SCP using ACO Metaheuristic. ACO metaheuristic was implemented in SciLab 5.4.1 under Microsoft Windows 7 on Intel Pentium Dual CPU 2.16 GHz, 2.0 Gb RAM with parameter values, β = 5, ρ = 0.99, ants=1000, tau(1)=heu(1)=1. The user inputs a specified number of facilities and areas associated, or provides a preprocessed m×n matrix which will then be run to provide a near-optimal value, with its associated optimal solution, number of iterations needed before attaining the near-optimal value, and the running time of the program. Table 3 summa- rizes the description of the ACO on SCP program. Table 3. Program Description of ACO on SCP PROGRAM TITLE Application of Ant Colony Optimization Metaheuristic on Set Covering Problems DESCRIPTION This program solves for a near- optimal Solution of a Set Covering Problem by applying ACO Metaheuristic PROGRAMMING LANGUAGE Scilab 5.4.1 INPUT Number of facilities and Areas associated/ m x n matrix (preprocessed SCP) OUTPUT Optimal Value of the problem, Associated Optimal Solution, Number of Iterations, Minimum Running Time 4. Application In order to further determine the effectiveness and efficiency of how ACO adapts in solving ACO, the study was applied to a local set covering problem and used to determine the optimal place of Wi-Fi Routers in Math Building. Data used was provided by the UPLB-ITC and OVCPD. In this paper, 802.11n Wi-Fi Routers were considered as the facility, while area was based on the division of area/rooms in Math Building. Since math building is a two-storey building, the problem was divided into two parts (1st floor and 2nd floor) for better explanation of the study and application. Note however that the problem can also be formulated as one SCP Model. Constraints of the model indicate that an area should be covered by at least one repeater. This will guarantee that the entire Math Building is covered. APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 17 As in Section 2, the related variables are defined as below in the context of WiFi routers now: Let I = set of all possible locations for installing a Wi-Fi router J = set of all rooms/areas which are to be covered xi = { 1, if a Wi-Fi router is to be installed at room i 0, otherwise yj = { 1, if whenever a Wi-Fi router is installed at room i the facility covers room j 0, otherwise Figure 1 serve as a map where xi’s are the areas in Math Building being covered, i being the area number, as shown: Figure 1. Old Math Building 1st (a) and 2nd (b) Floor Plan Generated through AutoCAD Math Building First Floor: Minimize z = 18∑ i=1 xi 18 CAH. BUHAT, JKL. VILLAMIN, AND GA. CUARESMA subject to the contraints x1 + x2 + x3 ≥ 1 x1 + x2 + x3 + x4 + x12 ≥ 1 x1 + x2 + x3 + x4 + x5 + x12 + x13 ≥ 1 x2 + x3 + x4 + x5 + x12 + x13 ≥ 1 x3 + x4 + x5 + x6 + x12 + x13 ≥ 1 x5 + x6 + x7 ≥ 1 x6 + x7 + x8 + x9 + x10 ≥ 1 x6 + x7 + x8 + x9 + x10 ≥ 1 x7 + x8 + x9 + x10 ≥ 1 x7 + x8 + x9 + x10 + x11 ≥ 1 x9 + x10 + x11 + x18 ≥ 1 x3 + x4 + x12 + x13 + x16 ≥ 1 x3 + x4 + x5 + x12 + x13 + x16 + x17 ≥ 1 x14 + x15 ≥ 1 x12 + x13 + x15 + x16 ≥ 1x12 + x13 + x15 + x16 + x17 ≥ 1 x12 + x13 + x16 + x17 + x18 ≥ 1 x10 + x11 + x18 ≥ 1 xi = {0, 1}, i = 1, 2, 3, ..., 18 Math Building Second Floor: Minimize z = 10∑ i=1 xi subject to x1 + x2 + x3 ≥ 1 x1 + x2 + x3 + x4 + x9 ≥ 1 x1 + x2 + x3 + x4 + x5 + x9 + x10 ≥ 1 x2 + x3 + x4 + x5 + x9 + x10 ≥ 1 x3 + x4 + x5 + x6 + x9 + x10 ≥ 1 x4 + x5 + x6 + x7 + x9 ≥ 1 x5 + x6 + x7 + x8 ≥ 1 x6 + x7 + x8 ≥ 1 x2 + x3 + x4 + x5 + x9 + x10 ≥ 1x3 + x4 + x5 + x9 + x10 ≥ 1 xi = {0, 1}, i = 1, 2, 3, ..., 10 Preprocessing of SCP (Specific) APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 19 Using the definition of the decision variables and a range of 140ft., with xi, i=1,...,18 for the first floor and j=1,...,10 for the second floor, the pre-processed matrix for the SCP is given in Table 4 and 5 for the first and second floors respectively in the Math Building. Math Building 1st Floor: Table 4. m x n matrix representing SCP Formulation of MB First Floor 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 4 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 5 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 6 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 10 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 11 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 12 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 0 13 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 16 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 17 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 18 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 Math Building Second Floor: Table 5. m x n matrix representing SCP Formulation of MB Second Floor 1 2 3 4 5 6 7 8 9 10 1 1 1 1 0 0 0 0 0 0 0 2 1 1 1 1 0 0 0 0 1 0 3 1 1 1 1 1 0 0 0 1 1 4 0 1 1 1 1 1 0 0 1 1 5 0 0 1 1 1 1 1 0 1 1 6 0 0 0 0 1 1 1 1 0 0 7 0 0 0 0 0 1 1 1 0 0 8 0 0 0 0 0 0 1 1 0 0 9 0 1 1 1 1 1 0 0 1 1 10 0 0 1 1 1 0 0 0 1 1 20 CAH. BUHAT, JKL. VILLAMIN, AND GA. CUARESMA Program Results After 1000 iterations/ants, ACO on SCP Program determined a near-optimal solution of 7 for the UPLB Math Building (5 for the first floor, 2 for the second floor). These Wi-Fi routers must then be placed at area number: 3, 6, 10, 12, 14 for the first floor, and 3, 6 for the second floor. However, the associated optimal solution given by the program may not be unique and may have other results which still give a near-optimal solution to the problem. Optimal Wi-Fi Routers: 1st Floor: 5 2nd Floor: 2 Associated Optimal Solution: 1st Floor: 0-0-1-0-0-1-0-0-0-1-0-1-0-1-0-0-0-0 2nd Floor: 0-0-1-0-0-1-0-0-0-0 Figure 2. Old Math Building 1st (a) and 2nd (b) Floor Plan with Optimal Wi-Fi Placement Comparison to Dynamic Programming Using Linear Program Solver (LiPS), a software used on solving linear, integer and goal programming problems, results of ACO on SCP Program have been compared to that of LiPS to determine how their results vary. For the 1sr floor of Math Building: Optimal Value Run Time Number of Iterations Areas Covered ACO on SCP Program 5 40 seconds* 160 100% LiPS 5 .33 seconds 24 100% Table 6. Comparison between results of ACO on SCP Program and LiPS on Math Building 1st Floor. * The time it took to finish the whole number of iterations. APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 21 For the 2nd floor of Math Building: Optimal Value Run Time Number of Iterations Areas Covered ACO on SCP Program 2 11 seconds* 4 100% LiPS 2 .07 seconds 13 100% Table 7. Comparison between results of ACO on SCP Program and LiPS on Math Building 2nd Floor. * The time it took to finish the whole number of iterations. Both tables show that both programs obtained the same optimal value for each SCP although ACO on SCP Program may not be consistent since it only computes for a near-optimal value. It can also be observed that the running time for both programs show that they are quite on par with each other. Though ACOonSCP has a larger running time because it finishes 1000 iterations before producing an optimal solution, expanding the problem to a large number of variables (representative to the real-world problems) will give LiPS more computing time since it uses simplex to compute for the optimal solu- tion. Not to mention, more difficulty in manually inputting values and the limitation on the number of variables and constraints that the LiPS program have (Hood, 2016). ACO on SCP Program is not consistent on number of iterations before producing an optimal result, but it is quite expected since it has a nature of a metaheuristic and operates based mainly on random numbers. Still, 100% of ar- eas have been covered by both programs using the associated optimal solution they generated. Also, since the ants used in the study are “normal ants” in ACO terms, adding more ants/iterations to the ACOonSCP will not have that much effect on the result, and may even further prolong the iteration time (Johansson and Pettersson, 2018). Comparison to Current ITC Wi-Fi Set-up According to the data from the University of the Philippines Los Baños Information Technology Center (UPLB- ITC), Math Building currently has 1 Wi-Fi router installed on a certain area which covers 20% of the whole Math Building. Meanwhile, based on the result of ACO on SCP Program, 7 are needed to cover the entire Math Building (1st Floor and 2nd Floor). Number of Routers Areas Covered ACO on SCP Program 7 100% LiPS (Dynamic Programming) 1 20% Table 8. Comparison between proposed number of ACO on SCP Program to current Wi-Fi Placement 5. Summary and Conclusion In this research, Ant Colony Optimization Metaheuristic was applied to the Set Covering Problem. Single Row Oriented Method was used to generate solutions. Pheromone trails and heuristic information were updated to provide a faster and near-optimal solution. Solutions were returned, and the optimal solution was computed through a Scilab 5.4.1 program. Specifically, ACO was applied to a specific SCP. A program was implemented to solve the SCP. Then, data gathered from ITC and OVCPD were used to construct a SCP based on Optimal Allocation of Wi-Fi on the Math Building and was solved through 22 CAH. BUHAT, JKL. VILLAMIN, AND GA. CUARESMA the program. Results have shown that to cover the entire MB, seven (7) 802.11n Wi-Fi Routers are needed. Computational results show that the proposed algorithm is efficient in generating high quality solutions. Comparisons with Dynamic Program revealed that it is competitive in solving the SCP. The work done in this paper also demonstrates the versatility of ACO and its high potential in solving hard combinatorial optimization problems. For extensions of the paper, branch-and-bound or branch-and-cut algorithms can be used to solve these types of problems. Having a comparison between our approach, other ACO approaches, and other metaheuristics approach can help determine which metaheuristics are suited for certain SCPs. References [1] B. Birbil, and K. Bulbul, The set covering problem revisited: An empirical study of the value of dual information, Journal of Industrial and Management Optimization 11(2015), 575-594. [2] C. Blum, and A. Roli, Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison, ACM Comput. Surv. 35(2001), 268-308. [3] I. Brezina Jr., and Z, Cickova, Solving the Travelling Salesman Problem Using the Ant Colony Optimization, Inter- national Scientific Journal of Management Information Systems 6(2011), 10-14. [4] D. Buezas, Constraint-based modeling of Minimum Set Covering: Application to Species Differentation, Master Thesis, Faculdade de Ciencias e Tecnologia, Departamento de Informatica, Universidade Nova de Lisboa, 2010. [5] G. Cornuejols, M. Trick and M. Saltzman, A Tutorial on Integer Programming. http://www.math.clemson.edu/ ~mjs/courses/mthsc.440/integer.pdf, accessed January 18, 2022 [6] M. Dorigo, and T. Stutzle, Ant Colony Optimization, Computational Intelligence Magazine, IEEE, 1(2006), 28-39. [7] M. Dorigo, M. Birattari, and T. Stutzle, Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique, IEEE Computational Intelligence Magazine 1(2006), 28-39. [8] M. Finker, T. Stützle, and H. Lourenço, Exploiting fitness distance correlation of set covering problems, Lecture Notes In Computer Science, 2279(2002), 61-71. [9] R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider, 0-1 Integer Linear Programming with a Linear Number of Constraints, arXiv:1401.5512, (2014). [10] G. Lan, G. DePuy, and G. Whitehouse, An effective and simple heuristic for the set covering problem. European Journal of Operational Research 176(2005), 1387-1403. [11] L. Lessing, T. Dumitrescu, and T. Stutzle, A Comparison Between ACO Algorithms for the Set Covering Problem, Springer-Verlag Berlin Heidelberg, 2004. [12] S. Olaffson, Chaper 21 Metaheuristics, Handbook on Simulation, Handbooks in Operations Research and Manage- ment Science, 13(2006), 633-654. [13] Z. Ren, Z. Feng, L. Ke, and Z. Zhang, New ideas for applying ant colony optimization to the set covering problem, Computers & Industrial Engineering 58(2008), 774-778. [14] N. Rokbani, A. Momasso, and A. Alimi, Ant Supervised by PSO Meta-heuristic with Application to TSP, Proceedings Engineering & Technology 4(2013), 148-152. [15] K. Schiff, Ant Colony Optimization Algorithm for the Set Covering Problem. Technical Transactions Automatic Control, 1-AC (2013). [16] M. Schulze, Linear Programming for Optimization, Perceptive Scientific Instrument, Inc., 1998. [17] T. Stutzle, and H. Hoos, Max-min ant system, Future Generation Computer Systems, 16(2000), 889-914. [18] W. Tfaili, and P. Siarry, A new charged ant colony algorithm for continuous dynamic optimization, Applied Mathe- matics and Computation, 197(2008), 604-613. [19] P. Varaiya, Lecture Notes on Optimization, Van Nostrand Reinhold Notes on System Sciences, 1998. [20] K. Vassilis, Linear Programming. https://docplayer.net/27853871-Vassilis-kostoglou-url-linear-programming-1.html, accessed January 18, 2022. [21] L. Pettersson and C. Lundell Johansson, Ant Colony Optimization - Optimal Number of Ants. https://www. diva-portal.org/smash/get/diva2:1214402/FULLTEXT01.pdf, accessed January 18, 2022. [22] S. Hood, Linear Program Solver, https://silo.tips/download/linear-program-solver, accessed January 18, 2022. [23] V. Selvi, and R. Umarani, Comparative Analysis of Ant Colony and Particle Swarm Optimization Techniques, International Journal of Computer Applications 5(2010), 908-1286. [24] N. Abd-Alsabour, H. Hefny and A. Moneim, Heuristic information for ant colony optimization for the feature selection problem, IEEE Conference Anthology, (2013), 1-5. doi:10.1109/ANTHOLOGY.2013.6784795. http://www.math.clemson.edu/~mjs/courses/mthsc.440/integer.pdf http://www.math.clemson.edu/~mjs/courses/mthsc.440/integer.pdf https://docplayer.net/27853871-Vassilis-kostoglou-url-linear-programming-1.html https://www.diva-portal.org/smash/get/diva2:1214402/FULLTEXT01.pdf https://www.diva-portal.org/smash/get/diva2:1214402/FULLTEXT01.pdf doi: 10.1109/ANTHOLOGY.2013.6784795 APPLICATION OF ANT COLONY OPTIMIZATION METAHEURISTIC ON SET COVERING PROBLEMS 23 Corresponding author, Institute of Mathematical Sciences and Physics, University of the Philippines Los Banos, Laguna, Philippines, 4030 Department of Mathematics, University of Houston, TX, USA, 77204 Email address: chbuhat@uh.edu Institute of Mathematical Sciences and Physics, University of the Philippines Los Banos, Laguna, Philip- pines, 4030 Email address: jersonvillamin@gmail.com Institute of Mathematical Sciences and Physics, University of the Philippines Los Banos, Laguna, Philip- pines, 4030 Email address: gacuaresma@up.edu.ph 1. Introduction 2. Theoretical Framework 3. Results and Discussion 4. Application 5. Summary and Conclusion References