Cost-based filtering algorithms for a Capacitated Lot Sizing Problem and the Constrained Arborescence Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-10

AUTHORS

Vinasetan Ratheil Houndji

ABSTRACT

Constraint Programming (CP) is a paradigm derived from artificial intelligence, operational research, and algorithmics that can be used to solve combinatorial problems. CP solves problems by interleaving search (assign a value to an unassigned variable) and propagation. Constraint propagation aims at removing/filtering inconsistent values from the domains of the variables in order to reduce the search space of the problem. In this thesis, we develop filtering algorithms for two complex combinatorial optimization problems: a Capacitated Lot Sizing Problem (CLSP) and the Constrained Arborescence Problem (CAP). Each of these problems has many variants and practical applications. The CLSP is the problem of finding an optimal production plan for single or multiple items while satisfying demands of clients and respecting resource restrictions. The CLSP finds important applications in production planning. In this thesis, we introduce a CLSP in CP. In many lot sizing and scheduling problems, in particular when the planning horizon is discrete and finite, there are stocking costs to be minimized. These costs depend on the time spent between the production of an order and its delivery. We focus on developing specialized filtering algorithms to handle the stocking cost part of a class of the CLSP. We propose the global optimization constraint StockingCost when the perperiod stocking cost is the same for all orders; and its generalized version, the IDStockingCost constraint (ID stands for Item Dependent). In this thesis, we also deal with a well-known problem in graph theory: the Minimum Weight Arborescence (MWA) problem. Consider a weighted directed graph in which we distinguish one vertex r as the root. An MWA rooted at r is a directed spanning tree rooted at r with minimum total weight. We focus on the CAP that requires one to find an arborescence that satisfies some side constraints (for example resource, degree, or diameter constraints) and that has minimum weight. The CAP has many real life applications in telecommunication networks, computer networks, transportation problems, scheduling problems, etc. After sensitivity analysis of the MWA, we introduce the CAP in CP. We propose a dedicated global optimization constraint to handle any known variant of the CAP in CP: the MinArborescence constraint. All the proposed filtering algorithms are analyzed theoretically and evaluated experimentally. The different experimental evaluations of these propagators against the state-of-the-art propagators show their respective efficiencies. More... »

PAGES

481-482

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10601-018-9292-7

DOI

http://dx.doi.org/10.1007/s10601-018-9292-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1104651241


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 d'Abomey-Calavi", 
          "id": "https://www.grid.ac/institutes/grid.412037.3", 
          "name": [
            "Institut de Formation et de Recherche en Informatique (IFRI, UAC), Abomey-Calavi, B\u00e9nin"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Houndji", 
        "givenName": "Vinasetan Ratheil", 
        "id": "sg:person.015005605345.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015005605345.49"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-10", 
    "datePublishedReg": "2018-10-01", 
    "description": "Constraint Programming (CP) is a paradigm derived from artificial intelligence, operational research, and algorithmics that can be used to solve combinatorial problems. CP solves problems by interleaving search (assign a value to an unassigned variable) and propagation. Constraint propagation aims at removing/filtering inconsistent values from the domains of the variables in order to reduce the search space of the problem. In this thesis, we develop filtering algorithms for two complex combinatorial optimization problems: a Capacitated Lot Sizing Problem (CLSP) and the Constrained Arborescence Problem (CAP). Each of these problems has many variants and practical applications. The CLSP is the problem of finding an optimal production plan for single or multiple items while satisfying demands of clients and respecting resource restrictions. The CLSP finds important applications in production planning. In this thesis, we introduce a CLSP in CP. In many lot sizing and scheduling problems, in particular when the planning horizon is discrete and finite, there are stocking costs to be minimized. These costs depend on the time spent between the production of an order and its delivery. We focus on developing specialized filtering algorithms to handle the stocking cost part of a class of the CLSP. We propose the global optimization constraint StockingCost when the perperiod stocking cost is the same for all orders; and its generalized version, the IDStockingCost constraint (ID stands for Item Dependent). In this thesis, we also deal with a well-known problem in graph theory: the Minimum Weight Arborescence (MWA) problem. Consider a weighted directed graph in which we distinguish one vertex r as the root. An MWA rooted at r is a directed spanning tree rooted at r with minimum total weight. We focus on the CAP that requires one to find an arborescence that satisfies some side constraints (for example resource, degree, or diameter constraints) and that has minimum weight. The CAP has many real life applications in telecommunication networks, computer networks, transportation problems, scheduling problems, etc. After sensitivity analysis of the MWA, we introduce the CAP in CP. We propose a dedicated global optimization constraint to handle any known variant of the CAP in CP: the MinArborescence constraint. All the proposed filtering algorithms are analyzed theoretically and evaluated experimentally. The different experimental evaluations of these propagators against the state-of-the-art propagators show their respective efficiencies.", 
    "genre": "non_research_article", 
    "id": "sg:pub.10.1007/s10601-018-9292-7", 
    "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": "23"
      }
    ], 
    "name": "Cost-based filtering algorithms for a Capacitated Lot Sizing Problem and the Constrained Arborescence Problem", 
    "pagination": "481-482", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9963ad57c484d33683922c10d4bd6c75f7971872257be172a8725a324381a221"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10601-018-9292-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1104651241"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10601-018-9292-7", 
      "https://app.dimensions.ai/details/publication/pub.1104651241"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T15:02", 
    "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/0000000001_0000000264/records_8663_00000517.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10601-018-9292-7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

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-018-9292-7'

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-018-9292-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9292-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9292-7'


 

This table displays all metadata directly associated to this object as RDF triples.

61 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10601-018-9292-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd92c3f28ee3a4eba8aae01865a595d19
4 schema:datePublished 2018-10
5 schema:datePublishedReg 2018-10-01
6 schema:description Constraint Programming (CP) is a paradigm derived from artificial intelligence, operational research, and algorithmics that can be used to solve combinatorial problems. CP solves problems by interleaving search (assign a value to an unassigned variable) and propagation. Constraint propagation aims at removing/filtering inconsistent values from the domains of the variables in order to reduce the search space of the problem. In this thesis, we develop filtering algorithms for two complex combinatorial optimization problems: a Capacitated Lot Sizing Problem (CLSP) and the Constrained Arborescence Problem (CAP). Each of these problems has many variants and practical applications. The CLSP is the problem of finding an optimal production plan for single or multiple items while satisfying demands of clients and respecting resource restrictions. The CLSP finds important applications in production planning. In this thesis, we introduce a CLSP in CP. In many lot sizing and scheduling problems, in particular when the planning horizon is discrete and finite, there are stocking costs to be minimized. These costs depend on the time spent between the production of an order and its delivery. We focus on developing specialized filtering algorithms to handle the stocking cost part of a class of the CLSP. We propose the global optimization constraint StockingCost when the perperiod stocking cost is the same for all orders; and its generalized version, the IDStockingCost constraint (ID stands for Item Dependent). In this thesis, we also deal with a well-known problem in graph theory: the Minimum Weight Arborescence (MWA) problem. Consider a weighted directed graph in which we distinguish one vertex r as the root. An MWA rooted at r is a directed spanning tree rooted at r with minimum total weight. We focus on the CAP that requires one to find an arborescence that satisfies some side constraints (for example resource, degree, or diameter constraints) and that has minimum weight. The CAP has many real life applications in telecommunication networks, computer networks, transportation problems, scheduling problems, etc. After sensitivity analysis of the MWA, we introduce the CAP in CP. We propose a dedicated global optimization constraint to handle any known variant of the CAP in CP: the MinArborescence constraint. All the proposed filtering algorithms are analyzed theoretically and evaluated experimentally. The different experimental evaluations of these propagators against the state-of-the-art propagators show their respective efficiencies.
7 schema:genre non_research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf Ndc7974ff3bc74709902ec21578b301f0
11 Nf8c4d52d1cf94fdfa3bc140014f0f51d
12 sg:journal.1043977
13 schema:name Cost-based filtering algorithms for a Capacitated Lot Sizing Problem and the Constrained Arborescence Problem
14 schema:pagination 481-482
15 schema:productId N1fc4b08e2dbb4f448dab760a0b363f6c
16 N6a803ae74ccd4fd3b050db1a9d7aa1e2
17 Nf27872bf6553476a890ab30f7d20c8d1
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1104651241
19 https://doi.org/10.1007/s10601-018-9292-7
20 schema:sdDatePublished 2019-04-10T15:02
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Ne0e55d3db81644b4b51939f74857100c
23 schema:url http://link.springer.com/10.1007%2Fs10601-018-9292-7
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N1fc4b08e2dbb4f448dab760a0b363f6c schema:name doi
28 schema:value 10.1007/s10601-018-9292-7
29 rdf:type schema:PropertyValue
30 N6a803ae74ccd4fd3b050db1a9d7aa1e2 schema:name readcube_id
31 schema:value 9963ad57c484d33683922c10d4bd6c75f7971872257be172a8725a324381a221
32 rdf:type schema:PropertyValue
33 Nd92c3f28ee3a4eba8aae01865a595d19 rdf:first sg:person.015005605345.49
34 rdf:rest rdf:nil
35 Ndc7974ff3bc74709902ec21578b301f0 schema:volumeNumber 23
36 rdf:type schema:PublicationVolume
37 Ne0e55d3db81644b4b51939f74857100c schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 Nf27872bf6553476a890ab30f7d20c8d1 schema:name dimensions_id
40 schema:value pub.1104651241
41 rdf:type schema:PropertyValue
42 Nf8c4d52d1cf94fdfa3bc140014f0f51d schema:issueNumber 4
43 rdf:type schema:PublicationIssue
44 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
45 schema:name Information and Computing Sciences
46 rdf:type schema:DefinedTerm
47 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
48 schema:name Computation Theory and Mathematics
49 rdf:type schema:DefinedTerm
50 sg:journal.1043977 schema:issn 1383-7133
51 1572-9354
52 schema:name Constraints
53 rdf:type schema:Periodical
54 sg:person.015005605345.49 schema:affiliation https://www.grid.ac/institutes/grid.412037.3
55 schema:familyName Houndji
56 schema:givenName Vinasetan Ratheil
57 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015005605345.49
58 rdf:type schema:Person
59 https://www.grid.ac/institutes/grid.412037.3 schema:alternateName Université d'Abomey-Calavi
60 schema:name Institut de Formation et de Recherche en Informatique (IFRI, UAC), Abomey-Calavi, Bénin
61 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...