LS(graph & tree): a local search framework for constraint optimization on graphs and trees

ABSTRACT

LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Optimization Problems on graphs (CSOP on graphs or GCSOP). Optimum Constrained Trees (OCT) problems (a subclass of CSOP on graphs) in which we need to find an optimum subtree with additional constraints of a given weighted graph arise in many real-life applications. This paper introduces the LS(Graph & Tree) framework and local search abstractions for OCT problems. These abstractions are applied to model and solve the edge weighted k-Cardinality Tree (KCT) problem. The modeling as well as experimental results show the significance of the abstractions.

REFERENCES

• 1: R. K. Ahujaa, J. B. Orlinb, and D. Sharma. A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem. Operations Research Letters 31, pages 185--194, 2003.
• 2: Rafael Andrade , Abilio Lucena , Nelson Maculan, Using Lagrangian dual information to generate degree constrained spanning trees, Discrete Applied Mathematics, v.154 n.5, p.703-717, 1 April 2006 [doi>10.1016/j.dam.2005.06.011]
• 3: Michael A. Bender , Martín Farach-Colton , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, v.57 n.2, p.75-94, November 2005 [doi>10.1016/j.jalgor.2005.08.001]
• 4: Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data structure, SIAM Journal on Computing, v.22 n.2, p.221-242, April 1993 [doi>10.1137/0222017]
• 5: Christian Blum , Maria J. Blesa, New metaheuristic approaches for the edge-weighted k-cardinality tree problem, Computers and Operations Research, v.32 n.6, p.1355-1377, June 2005 [doi>10.1016/j.cor.2003.11.007]
• 6: A. Bookstein , S. T. Klein, Compression of correlated bit-vectors, Information Systems, v.16 n.4, p.387-400, 1991 [doi>10.1016/0306-4379(91)90030-D]
• 7: M. Chimani, M. Kandyba, I. Ljubic, and P. Mutzel. Obtaining optimal k-cardinality trees fast. 10th Workshop on Algorithm Engineering and Experiments 2008, San Francisco (ALENEX08), SIAM, pages 27--36, 2008.
• 8: M. de Aragão, E. Uchoa, and R. Werneck. Dual heuristics on the exact solution of large Steiner problems. In Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics GRACO'01, Fortaleza, 2001.
• 9: G. Dooms, Y. Deville, and P. Dupont. Cp (graph): Introducing a graph computation domain in constraint programming. International Conference on Principles and Practice on Constraint Programming, LNCS 3709, pages 211--225, 2005.
• 10: T. Fischer. Improved local search for large optimum communication spanning tree problems. In MIC'2007 - 7th Metaheuristics International Conference, 2007.
• 11: M. Gomes, R. Andrade, C. Santiago, and N. Maculan. Spanning tree algorithms to some hard combinatorial problems. in: Proceedings of Optimization Days, Montreal/Canada, pages 83--84, 1997.
• 12: Martin Gruber , Jano van Hemert , Günther R. Raidl, Neighbourhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144185]
• 13: Pascal Van Hentenryck , Laurent Michel, Constraint-Based Local Search, The MIT Press, 2005
• 14: P. V. Hentenryck, L. Michel, and L. Liu. Constraint-based combinators for local search. International Conference on Constraint Programming, LNCS 3258, pages 47--61, 2004.
• 15: KCTLib. http://iridia.ulb.ac.be/cblum/kctlib/, 2003.
• 16: Mohan Krishnamoorthy , Andreas T. Ernst , Yazid M. Sharaiha, Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree, Journal of Heuristics, v.7 n.6, p.587-611, November 2001 [doi>10.1023/A:1011977126230]
• 17: E. Nardelli and G. Proietti. Finding all the best swaps of a minimum diameter spanning tree under transient edge failures. Journal of Graph Algorithms and Applications vol. 5, no. 5, pages 39--57, 2001.
• 18: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 19: M. Reimann and M. Laumanns. A hybrid aco algorithm for the capacitated minimum spanning tree problem. Proceedings of First International Workshop on Hybrid Metaheuristics, pages 1--10, 2004.
• 20: M. Zachariasen. Local Search for the Steiner Tree Problem in the Euclidean Plane. European Journal of Operational Research, 119: 282--300, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Keywords:
KCT, constrained tree problems, constraint optimization, graph theory, local search