Loading…

Local arc consistency for non-invertible semirings, with an application to multi-objective optimization

► We generalize the previous consistency algorithms to more sophisticated semirings. ► Our focus is on invertible semirings, equipped with either a total or a partial order. ► We show a novel associative operator, characterizing the least common divisor (LCD). ► The LCD value is to the amount we can...

Full description

Saved in:
Bibliographic Details
Published in:Expert systems with applications 2012-02, Vol.39 (2), p.1708-1717
Main Authors: Bistarelli, Stefano, Gadducci, Fabio, Larrosa, Javier, Rollon, Emma, Santini, Francesco
Format: Article
Language:English
Subjects:
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!
cited_by cdi_FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3
cites cdi_FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3
container_end_page 1717
container_issue 2
container_start_page 1708
container_title Expert systems with applications
container_volume 39
creator Bistarelli, Stefano
Gadducci, Fabio
Larrosa, Javier
Rollon, Emma
Santini, Francesco
description ► We generalize the previous consistency algorithms to more sophisticated semirings. ► Our focus is on invertible semirings, equipped with either a total or a partial order. ► We show a novel associative operator, characterizing the least common divisor (LCD). ► The LCD value is to the amount we can “safely move” in the consistency algorithm. We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.
doi_str_mv 10.1016/j.eswa.2011.06.062
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_963842269</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0957417411009626</els_id><sourcerecordid>1701055662</sourcerecordid><originalsourceid>FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMouK7-AU-56cGuST_SFrzI4hcseNFzSNPpOqVNapLdZf31tq7nhRfmMM87MA8h15wtOOPivl2A36lFzDhfMDEmPiEzXuRJJPIyOSUzVmZ5lPI8PScX3reM8ZyxfEbWK6tVR5XTVFvj0Qcwek8b66ixJkKzBRew6oB66NGhWfs7usPwRZWhahg61CqgNTRY2m-6gJGtWtABt0DtELDHn7_9JTlrVOfh6n_Oyefz08fyNVq9v7wtH1eRTkQWIqGqVBV1o3MOrEg1U1zpRvC6rNNGFVVSlRkTjchAN6qOU56woshVUmiAVJeQzMnN4e7g7PcGfJA9eg1dpwzYjZelSIo0jkU5krdHyVEQZ1kmRDyi8QHVznrvoJGDw165veRMTv5lKyf_cvIvmRgzlR4OJRjf3SI46TWOcqFGNwqStcVj9V9iXpFq</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1701055662</pqid></control><display><type>article</type><title>Local arc consistency for non-invertible semirings, with an application to multi-objective optimization</title><source>ScienceDirect Freedom Collection</source><creator>Bistarelli, Stefano ; Gadducci, Fabio ; Larrosa, Javier ; Rollon, Emma ; Santini, Francesco</creator><creatorcontrib>Bistarelli, Stefano ; Gadducci, Fabio ; Larrosa, Javier ; Rollon, Emma ; Santini, Francesco</creatorcontrib><description>► We generalize the previous consistency algorithms to more sophisticated semirings. ► Our focus is on invertible semirings, equipped with either a total or a partial order. ► We show a novel associative operator, characterizing the least common divisor (LCD). ► The LCD value is to the amount we can “safely move” in the consistency algorithm. We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.</description><identifier>ISSN: 0957-4174</identifier><identifier>EISSN: 1873-6793</identifier><identifier>DOI: 10.1016/j.eswa.2011.06.062</identifier><language>eng</language><publisher>Elsevier Ltd</publisher><subject>Absorptivity ; Algorithms ; Arc consistency ; Cartesian ; Consistency ; Expert systems ; Invertible semiring ; Liquid crystal displays ; Multi-objective ; Operators ; Optimization ; Soft constraint</subject><ispartof>Expert systems with applications, 2012-02, Vol.39 (2), p.1708-1717</ispartof><rights>2011 Elsevier Ltd</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3</citedby><cites>FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids></links><search><creatorcontrib>Bistarelli, Stefano</creatorcontrib><creatorcontrib>Gadducci, Fabio</creatorcontrib><creatorcontrib>Larrosa, Javier</creatorcontrib><creatorcontrib>Rollon, Emma</creatorcontrib><creatorcontrib>Santini, Francesco</creatorcontrib><title>Local arc consistency for non-invertible semirings, with an application to multi-objective optimization</title><title>Expert systems with applications</title><description>► We generalize the previous consistency algorithms to more sophisticated semirings. ► Our focus is on invertible semirings, equipped with either a total or a partial order. ► We show a novel associative operator, characterizing the least common divisor (LCD). ► The LCD value is to the amount we can “safely move” in the consistency algorithm. We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.</description><subject>Absorptivity</subject><subject>Algorithms</subject><subject>Arc consistency</subject><subject>Cartesian</subject><subject>Consistency</subject><subject>Expert systems</subject><subject>Invertible semiring</subject><subject>Liquid crystal displays</subject><subject>Multi-objective</subject><subject>Operators</subject><subject>Optimization</subject><subject>Soft constraint</subject><issn>0957-4174</issn><issn>1873-6793</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2012</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMouK7-AU-56cGuST_SFrzI4hcseNFzSNPpOqVNapLdZf31tq7nhRfmMM87MA8h15wtOOPivl2A36lFzDhfMDEmPiEzXuRJJPIyOSUzVmZ5lPI8PScX3reM8ZyxfEbWK6tVR5XTVFvj0Qcwek8b66ixJkKzBRew6oB66NGhWfs7usPwRZWhahg61CqgNTRY2m-6gJGtWtABt0DtELDHn7_9JTlrVOfh6n_Oyefz08fyNVq9v7wtH1eRTkQWIqGqVBV1o3MOrEg1U1zpRvC6rNNGFVVSlRkTjchAN6qOU56woshVUmiAVJeQzMnN4e7g7PcGfJA9eg1dpwzYjZelSIo0jkU5krdHyVEQZ1kmRDyi8QHVznrvoJGDw165veRMTv5lKyf_cvIvmRgzlR4OJRjf3SI46TWOcqFGNwqStcVj9V9iXpFq</recordid><startdate>20120201</startdate><enddate>20120201</enddate><creator>Bistarelli, Stefano</creator><creator>Gadducci, Fabio</creator><creator>Larrosa, Javier</creator><creator>Rollon, Emma</creator><creator>Santini, Francesco</creator><general>Elsevier Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20120201</creationdate><title>Local arc consistency for non-invertible semirings, with an application to multi-objective optimization</title><author>Bistarelli, Stefano ; Gadducci, Fabio ; Larrosa, Javier ; Rollon, Emma ; Santini, Francesco</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Absorptivity</topic><topic>Algorithms</topic><topic>Arc consistency</topic><topic>Cartesian</topic><topic>Consistency</topic><topic>Expert systems</topic><topic>Invertible semiring</topic><topic>Liquid crystal displays</topic><topic>Multi-objective</topic><topic>Operators</topic><topic>Optimization</topic><topic>Soft constraint</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bistarelli, Stefano</creatorcontrib><creatorcontrib>Gadducci, Fabio</creatorcontrib><creatorcontrib>Larrosa, Javier</creatorcontrib><creatorcontrib>Rollon, Emma</creatorcontrib><creatorcontrib>Santini, Francesco</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Expert systems with applications</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bistarelli, Stefano</au><au>Gadducci, Fabio</au><au>Larrosa, Javier</au><au>Rollon, Emma</au><au>Santini, Francesco</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Local arc consistency for non-invertible semirings, with an application to multi-objective optimization</atitle><jtitle>Expert systems with applications</jtitle><date>2012-02-01</date><risdate>2012</risdate><volume>39</volume><issue>2</issue><spage>1708</spage><epage>1717</epage><pages>1708-1717</pages><issn>0957-4174</issn><eissn>1873-6793</eissn><abstract>► We generalize the previous consistency algorithms to more sophisticated semirings. ► Our focus is on invertible semirings, equipped with either a total or a partial order. ► We show a novel associative operator, characterizing the least common divisor (LCD). ► The LCD value is to the amount we can “safely move” in the consistency algorithm. We extend algorithms for local arc consistency proposed in the literature in order to deal with (absorptive) semirings that may not be invertible. As a consequence, these consistency algorithms can be used as a pre-processing procedure in soft Constraint Satisfaction Problems (CSPs) defined over a larger class of semirings, such as those obtained from the Cartesian product of two (or more) semirings. One important instance of this class of semirings is adopted for multi-objective CSPs. First, we show how a semiring can be transformed into a novel one where the + operator is instantiated with the least common divisor (LCD) between the elements of the original semiring. The LCD value corresponds to the amount we can “safely move” from the binary constraint to the unary one in the arc consistency algorithm. We then propose a local arc consistency algorithm which takes advantage of this LCD operator.</abstract><pub>Elsevier Ltd</pub><doi>10.1016/j.eswa.2011.06.062</doi><tpages>10</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0957-4174
ispartof Expert systems with applications, 2012-02, Vol.39 (2), p.1708-1717
issn 0957-4174
1873-6793
language eng
recordid cdi_proquest_miscellaneous_963842269
source ScienceDirect Freedom Collection
subjects Absorptivity
Algorithms
Arc consistency
Cartesian
Consistency
Expert systems
Invertible semiring
Liquid crystal displays
Multi-objective
Operators
Optimization
Soft constraint
title Local arc consistency for non-invertible semirings, with an application to multi-objective optimization
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-23T13%3A03%3A30IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Local%20arc%20consistency%20for%20non-invertible%20semirings,%20with%20an%20application%20to%20multi-objective%20optimization&rft.jtitle=Expert%20systems%20with%20applications&rft.au=Bistarelli,%20Stefano&rft.date=2012-02-01&rft.volume=39&rft.issue=2&rft.spage=1708&rft.epage=1717&rft.pages=1708-1717&rft.issn=0957-4174&rft.eissn=1873-6793&rft_id=info:doi/10.1016/j.eswa.2011.06.062&rft_dat=%3Cproquest_cross%3E1701055662%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c365t-6ab4a8dfc71e084c0a1acf61d9d4fa8b3b9506f65ecfad24130887a38cee4c9e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1701055662&rft_id=info:pmid/&rfr_iscdi=true