Residuation for bipolar preferences in soft constraints

•A focus on positive and negative preferences in Soft Constraint Problems.•A summary of related work in the literature.•A generalisation of such proposals by using “enriched monoids”.•The definition of Local Consistency algorithms working with enriched monoids.•Residuation as a means to remove quant...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2017-02, Vol.118, p.69-74
Main Authors: Gadducci, Fabio, Santini, Francesco
Format: Article
Language:English
Subjects:
Bipolar preferences
Combinatorial problems
Local consistency
Soft constraints
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A focus on positive and negative preferences in Soft Constraint Problems.•A summary of related work in the literature.•A generalisation of such proposals by using “enriched monoids”.•The definition of Local Consistency algorithms working with enriched monoids.•Residuation as a means to remove quantities from a (soft) constraint. Soft constraint formalisms are an abstract representation of Constraint Satisfaction Problems (CSPs): the set of preferences is now parametric, often forming (a variety of) an absorptive semiring. However, the latter is suitable only for negative preferences, i.e., such that the combination of constraints worsens the quality of the solution. This work comments on related work and exploits residuated semirings in order to lift the Local Consistency heuristics that hold for classical CSPs. As a result, we merge and generalise existent formalisms for modelling soft CSPs with bipolar (positive and negative) preferences.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2016.10.002