Ontology type: schema:ScholarlyArticle Open Access: True
2017-10
AUTHORSSascha Van Cauwelaert, Pierre Schaus
ABSTRACTThis paper studies a family of optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. The objective is then to assign items such that the overall resource cost is minimized. Such problems arise commonly in domains such as production scheduling in the presence of fluctuating renewable energy costs or variants of the Travelling Salesman Problem. In Constraint Programming, this can be naturally modeled in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. Unfortunately the sum of element constraints obtains a weak filtering and the MinimumAssignment constraint does not scale well on large instances. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint and an associated incremental and scalable filtering algorithm, running in O(n⋅m), where n is the number of unbound variables and m is the maximum domain size of unbound variables. Its goal is to compute the total cost in a scalable manner by dealing with the fact that all assignments must be different. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones for the problems we considered. More... »
PAGES493-511
http://scigraph.springernature.com/pub.10.1007/s10601-017-9269-y
DOIhttp://dx.doi.org/10.1007/s10601-017-9269-y
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1085563797
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Universit\u00e9 Catholique de Louvain",
"id": "https://www.grid.ac/institutes/grid.7942.8",
"name": [
"Universit\u00e9 Catholique de Louvain, Place Sainte Barbe 2 bte L5.02.01, 1348, Louvain-la-Neuve, Belgium"
],
"type": "Organization"
},
"familyName": "Van Cauwelaert",
"givenName": "Sascha",
"id": "sg:person.012557131067.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012557131067.38"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Universit\u00e9 Catholique de Louvain",
"id": "https://www.grid.ac/institutes/grid.7942.8",
"name": [
"Universit\u00e9 Catholique de Louvain, Place Sainte Barbe 2 bte L5.02.01, 1348, Louvain-la-Neuve, Belgium"
],
"type": "Organization"
},
"familyName": "Schaus",
"givenName": "Pierre",
"id": "sg:person.016270221351.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016270221351.48"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-319-33954-2_18",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002342073",
"https://doi.org/10.1007/978-3-319-33954-2_18"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-19486-3_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003962101",
"https://doi.org/10.1007/978-3-642-19486-3_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-19486-3_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003962101",
"https://doi.org/10.1007/978-3-642-19486-3_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-33954-2_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010011285",
"https://doi.org/10.1007/978-3-319-33954-2_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24664-0_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014323152",
"https://doi.org/10.1007/978-3-540-24664-0_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-24664-0_23",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014323152",
"https://doi.org/10.1007/978-3-540-24664-0_23"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-10428-7_29",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014437114",
"https://doi.org/10.1007/978-3-319-10428-7_29"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-23219-5_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016789935",
"https://doi.org/10.1007/978-3-319-23219-5_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-46135-3_56",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038682842",
"https://doi.org/10.1007/3-540-46135-3_56"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.enpol.2004.07.013",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038771543"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1571-0653(04)00002-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039069593"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1020506526052",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039833510",
"https://doi.org/10.1023/a:1020506526052"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s101070100263",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040788378",
"https://doi.org/10.1007/s101070100263"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-18008-3_29",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043190236",
"https://doi.org/10.1007/978-3-319-18008-3_29"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(83)90048-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043780918"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(83)90048-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043780918"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ijforecast.2014.08.008",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046783053"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-10428-7_59",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048263417",
"https://doi.org/10.1007/978-3-319-10428-7_59"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.35.5.772",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064729863"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/trsc.32.1.12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064735452"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-10",
"datePublishedReg": "2017-10-01",
"description": "This paper studies a family of optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. The objective is then to assign items such that the overall resource cost is minimized. Such problems arise commonly in domains such as production scheduling in the presence of fluctuating renewable energy costs or variants of the Travelling Salesman Problem. In Constraint Programming, this can be naturally modeled in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. Unfortunately the sum of element constraints obtains a weak filtering and the MinimumAssignment constraint does not scale well on large instances. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint and an associated incremental and scalable filtering algorithm, running in O(n\u22c5m), where n is the number of unbound variables and m is the maximum domain size of unbound variables. Its goal is to compute the total cost in a scalable manner by dealing with the fact that all assignments must be different. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones for the problems we considered.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-017-9269-y",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "22"
}
],
"name": "Efficient filtering for the Resource-Cost AllDifferent constraint",
"pagination": "493-511",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"872a16743e7719abbaf53ce14d2f16a5c1dae9f6523c0eb51b7afc4e34c16350"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-017-9269-y"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1085563797"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-017-9269-y",
"https://app.dimensions.ai/details/publication/pub.1085563797"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T12:41",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70053_00000002.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs10601-017-9269-y"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10601-017-9269-y'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10601-017-9269-y'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-017-9269-y'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-017-9269-y'
This table displays all metadata directly associated to this object as RDF triples.
130 TRIPLES
21 PREDICATES
44 URIs
19 LITERALS
7 BLANK NODES