LS(Graph & Tree): A Local Search Framework for Constraint Optimization on Graphs and Trees

Pham, Quang Dung;Deville, Yves;Van Hentenryck, Pascal
(2009) Proceedings of the 2009 ACM Symposium on Applied Computing (SAC′09) — Location: Honolulu, Hawaii, USA (9.March.2009)

Files

lsgraph_SAC09_2.pdf
  • Open Access
  • Adobe PDF
  • 266.05 KB
Download

Details

Authors
  • Pham, Quang DungUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Collaborator
  • Van Hentenryck, PascalBrown University
    Collaborator
Abstract
LS(Graph & Tree) is a local search framework which aims at simplifying the modeling of Constraint Satisfaction Opti- mization 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 sub- tree 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 abstrac- tions 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 re- sults show the significance of the abstractions.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Pham, Q. D. (2009). LS(Graph & Tree): A Local Search Framework for Constraint Optimization on Graphs and Trees. Proceedings of the 2009 ACM Symposium on Applied Computing (SAC′09), Honolulu, Hawaii, USA. https://hdl.handle.net/2078.5/219240