Microsoft Word - brain_1_2_final_final_final.doc 5 A Hybrid Heuristic for Solving the Triangulation Problem Gloria Cerasela Crişan Department of Mathematics and Computer Science, Faculty of Sciences, “Vasile Alecsandri” University of Bacău Calea Mărăşeşti, 157, Bacău, 600115, Romania ceraselacrisan@ub.ro Camelia-Mihaela Pintea “George Cosbuc” National College Avram Iancu, 70-72, Cluj-Napoca, Romania cmpintea@yahoo.com Abstract The Triangulation Problem consists of finding a simultaneous permutation of rows and columns in a given square matrix, so that the sum of the upper-diagonal entries is maximal. The researchers study this problem intensively, as it has major applications in broad domains. A new hybrid Ant Colony Optimization algorithm is introduced, which starts with a greedy search procedure. It is followed by an improved version of the Ant Colony System combined with a problem-specific local search. Keywords: Triangulation Problem, Ant Colony Optimization, metaheuristics 1. Introduction The Triangulation Problem (TP) seeks to find, for a given square matrix, a simultaneous permutation of its rows and columns, so that the sum of the above diagonal elements becomes as large as possible. Set up more then fifty years ago [3], TP is also known as the Linear Ordering Problem, the Maximum Acyclic Subdigraph Problem, the Maximum Consistent Arc Set, the Median Ordering Problem, or the Minimum Feedback Arc Set. TP arises in various fields including economy, social sciences, linguistics, electrical engineering, logistics, mathematics and archaeology [1]. For example, in economy, the input- output matrix rearrangement provides information on the macro-economic stability [3]; in linguistics, the automatic translation is improved by learning procedures based on sentence- specific reordering models [19]; in archaeology, the problem is equivalent to seriation: the seeking for the most probable chronologic order of the artifacts found on a specific site [17]. TP is NP-hard [8]; this means that current real-life, complex instances are unlikely to be solved in a reasonable amount of time. The researchers constantly provide heuristic and approximate methods to efficiently obtain near-optimum solutions. Ant Colony Optimization [5] is a metaheuristic that covers the algorithms inspired by the behavior of real ants, when finding the shortest path from nest to food. Together with other biologically-inspired methods for solving difficult problems, ACO expresses the effectiveness and the versatility observed in nature. The next section presents the Triangulation Problem and the already existing methods to solve this problem. Section 3 introduces the new algorithm, followed by future work tasks and conclusions. BRAINovations BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 2 , April 2010, ”Happy Spring 2010!”, ISSN 2067-3957 6 2. The Triangulation Problem The TP considers a square matrix of costs ( ) njiij cC ≤≤ = ,1 and seeks for a permutation σ that maximizes the total cost from (1). ∑ ∑ − = += = 1 1 1 )()()( n i n ij jicZ σσσ (1) As many Combinatorial Optimization Problems, the TP has several alternative formulations. As a graph theory problem, it seeks for a spanning acyclic tournament on the complete graph whose weights matrix is C . As an integer programming problem, it is based on the graph theory formulation, having two types of constraints, the tournament polytopes and the 3-dicycle, to prevent cycles [16]. Finally, it can be stated as a particular case of quadratic assignment problem [2]. The exact methods for TP solving include cutting plane algorithms [11] or interior point approaches [13]. The approximate methods to solve the TP include the use of the recursive decomposition technique to obtain optimality within a factor of )loglog(log nnO [6]. Broad heuristic approaches are reported for TP solving: tabu search [9], scatter search [10], iterated local search [12], variable neighborhood search [7] and evolutionary strategies [18]. 3. The Algorithm IAS-TP The proposed algorithm for solving the TP has an initial greedy phase that rapidly constructs some promising starting solutions. The ACO algorithm is the Inner Ant System [14], based on the Ant Colony System [4], with an interleaved local search from [15]. IAS-TP Algorithm procedure GreedyInitialSearch procedure IAS-IM Set parameters, initialize pheromone trails while (termination condition not met) do ConstructAntsSolutions(including inner rule) LocalSearchInsertMove GlobalUpdatePheromones end end IAS-TP The procedure GreedyInitialSearch starts from a random permutation σ for the matrix C and selects (just in one step) the best improvement move from its neighborhood )(σN . The neighborhood of σ is the set of permutations τ that could be obtained from σ by left-compounding with a transposition nrkrk ≤<≤1)),()(( σσ . The cost modification when moving from σ to τ into the TP solution space is (2): ∑ − += −−++− 1 1 )()()()()()()()()()()()( )()( r ki ikrikiirrkkr cccccc σσσσσσσσσσσσ (2) The procedure IAS-IM is a new ACO algorithm. The Inner Ant System (IAS) modifies the local pheromone update rule from the Ant Colony System (ACS), in order to favor the exploration of the available moves. The IAS rule [14] modifies the pheromone trails on all the available moves, while in the ACS case, only the selected move updates its pheromone value. By considering all the available moves and consequently reflecting their previous quality into the pheromone values, the IAS variant is oriented merely to solution space exploration. G. C. Crişan, C. M. Pintea – A Hybrid Heuristic for Solving the Triangulation Problem 7 Just before the global update rule (that immediately follows in the ACS case), our algorithm is hybridized with the local search from [15], based on [7]. An insert move for a permutation σ at )( jσ and i means the deleting of the element )( jσ and inserting it between the elements )1( −iσ and )(iσ . This operation yields a permutation τ (obtained from σ ) with the total cost (for i < j) (3): ∑ − = −+= 1 )()()()( )()()( j ik jkkj ccZZ σσσσστ (3) The neighborhood for σ , based on this insertion move is (4): { }njjinjijmoveinsertN ,...1,1,...2,1,,...1),),((_|)( +−==== σττσ (4) From )(σN , the ehInsertMovLocalSearc procedure, randomly selects one permutation τ that improves the total cost. Finally, the global update rule is applied, and the algorithm is iterated, until the termination conditions are met. This local search procedure was tested in [15] and showed very good results when it hybridizes the classic ACS algorithm. In this proposed algorithm, it is used to improve the ICS variant. The algorithm implementation is a work in progress task. Future work will be done in designing a coarse-grained parallel implementation of this algorithm and exploring its results on the instances from [20]. 4. Conclusions The paper introduced a new approach to heuristically solving the Triangulation Problem. This NP-hard problem has broad real-world applications in economy, engineering and logistics. The proposed algorithm is an ACO implementation, started from the solutions of a greedy procedure and hybridized with a local search. By including problem-oriented structure of the neighborhood, the local search tends to produce good results. The preliminary tests and the parameter tuning tests show a good and stable behavior on several available instances from [20]. Acknowledgments. This research is supported by the Grant ID 508, New Computational Paradigms for Dynamic Complex Problems, funded by the Ministry of Education, Research and Innovation, Romania. References [1] Barthélemy, J.P., Leclerc, B., Monjardet, B. (1986). On the use of ordered sets in problems of comparison and consensus of classifications. Journal of Classification, 3(2), 187-224. [2] Chaovalitwongse, W.A., Pardalos, P.M., Resende, M.G.C., Grundel, D.A. (2010). Revised GRASP with path-relinking for the linear ordering problem. Journal of Combinatorial Optimization (Retrieved 1 February 2010, from http://www2.research.att.com/~mgcr/doc/gpr-lop.pdf). [3] Chenery, H.B., Watanabe, T. (1958). International comparisons of the structure of productions. Econometrica, 26(4), 487-521. [4] Dorigo, M., Gambardella, L.M. (1997). Ant Colony System: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 2 , April 2010, ”Happy Spring 2010!”, ISSN 2067-3957 8 [5] Dorigo, M., Stützle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge. [6] Even, G., Naor, J., Rao, S., Schieber. B. (2000). Divide–and–conquer approximation algorithms via spreading metrics. Journal of the ACM, 47, 585–616. [7] Garcia, C., Perez, D., Campos, V., Marti, R. (2006). Variable neighborhood search for the linear ordering problem. Computers and Operations Research, 33, 3549–3565. [8] Garey, M.R., Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York [9] Glover, F., Laguna, M. (1997). Tabu Search. Kluwer Academic Publisher, Boston. [10] Glover, F. (1998). A template for Scatter Search and Path Relinking. In Hao, J.K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.), Artificial Evolution. Lecture Notes in Computer Science, 1363, 13-54. [11] Grötschel, M., Jünger, M., Reinelt, G. (1984). A cutting plane algorithm for the linear ordering problem. Operations Research, 32(6), 1195-1220. [12] Lourenco, H.R., Martin, O., Stützle, T. (2002). Iterated Local Search. In Glover, F., Kochenberger, G. (eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science, 57, 321-353, Kluwer Academic Publishers. [13] Mitchell, J.E., Borchers, B. (2000). Solving linear ordering problem with a combined interior point/simplex cutting plane algorithm. In Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.), High Performance Optimization, 349-366, Kluwer Academic Publishers. [14] Pintea, C.M., Dumitrescu, D. (2005). Improving Ant Systems using a local updating rule. In: Cantarella, J.D., IEEE Proceedings of International Symbolic and Numerical Algorithms for Scientific Computing, IEEE Computer Society Press (pp. 295-2999). [15] Pintea, C.M., Crişan, G.C., Chira, C., Dumitrescu, D. (2009). A Hybrid Ant-Based Approach to the Economic Triangulation Problem for Input-Output Tables. In: Lecture Notes in Artificial Intelligence. The 4th International Conference on Hybrid Artificial Intelligence Systems, Salamanca, Spain. [16] Reinelt, G. (1985). The linear ordering problem: algorithms and applications. In Research and Exposition in Mathematics, 8, Heldermann Verlag, Berlin [17] Robinson, W.R. (1951). A method for chronologically ordering archaeological deposits. American Antiquity 16, 93–301. [18] Snásel, V., Kromer, P., Platos, J. (2008). Evolutionary approaches to linear ordering problem. In: DEXA Workshops, IEEE Computer Society (pp. 566–570). [19] Tromble, R., Eisner, J. (2009). Learning Linear Ordering Problems for Better Translation. In: Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, Singapore (pp. 1007–1016). [20] LOLIB, at Heidelberg University, Germany. Retrieved 1 February 2010 from http://www.iwr.uni-heidelberg.de/groups/comopt/software/LOLIB/.