Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inrae.fr/hal-02754114
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Wednesday, June 3, 2020 - 8:17:18 PM
Last modification on : Monday, September 21, 2020 - 7:32:01 PM
Long-term archiving on: : Thursday, December 3, 2020 - 10:09:39 AM

File

Optimal soft arc consistency_1...
Publisher files allowed on an open archive

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

17

Files downloads

18