Optimal soft arc consistency - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2007

Optimal soft arc consistency

Abstract

The Valued (VCSP) framework is a generic optimization framework with a wide range of applications. Soft arc consistency operations transform a VCSP into an equivalent problem by shifting weights between cost functions. The principal aim is to produce a good lower bound on the cost of solutions, an essential ingredient of a branch and bound search. But soft AC is much more complex than traditional AC: there may be several closures (fixpoints) and finding the closure with a maximum lower bound has been shown to be NP-hard for integer costs [Cooper and Schiex, 2004]. We introduce a relaxed variant of soft arc consistency using rational costs. In this case, an optimal closure can be found in polynomial time. Furthermore, for finite rational costs, the associated lower bound is shown to provide an optimal arc consistent reformulation of the initial problem. Preliminary experiments on random and structured problems are reported, showing the strength of the lower bound produced.
Fichier principal
Vignette du fichier
Optimal soft arc consistency_1.pdf (223.68 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-02754114 , version 1 (03-06-2020)

Identifiers

  • HAL Id : hal-02754114 , version 1
  • PRODINRA : 185357

Cite

Martin Cooper, Simon de Givry, Thomas Schiex. Optimal soft arc consistency. 20th International Joint Conference on Artificial Intelligence - IJCAI 2007, Jan 2007, Hyderabad, India. pp.6. ⟨hal-02754114⟩
18 View
8 Download

Share

Gmail Facebook X LinkedIn More