LS(Graph) : a local search framework for constraint optimization on graphs and trees

Pham, Quang Dung;Deville, Yves;Van Hentenryck, Pascal
(2009) The 2009 ACM Symposium on Applied Computing — Location: Honolulu, HI, USA (8.March.2008)

Files

LSgraph.pdf
  • Open Access
  • Adobe PDF
  • 274.93 KB
Download

Details

Authors
  • Pham, Quang DungUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Author
  • Van Hentenryck, PascalBrown University, USA
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Pham, Q. D., Deville, Y., & Van Hentenryck, P. (2009). LS(Graph) : a local search framework for constraint optimization on graphs and trees. The 2009 ACM Symposium on Applied Computing, Honolulu, HI, USA. https://hdl.handle.net/2078.5/254142