Reformulating Global Constraints: The Slide and Regular Constraints
Identifieur interne : 001642 ( Istex/Corpus ); précédent : 001641; suivant : 001643Reformulating Global Constraints: The Slide and Regular Constraints
Auteurs : Christian Bessiere ; Emmanuel Hebrard ; Brahim Hnich ; Zeynep Kiziltan ; Claude-Guy Quimper ; Toby WalshSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2007.
English descriptors
- KwdEn :
- Arity, Automaton, Binary constraint, Cardpath constraint, Certain number, Combinatorial problems, Compatible values, Computer science, Constraint, Constraint toolkit, Decision variables, Dummy value, Dynamic programming, Feasible solution, Global, Global constraint, Global constraints, Global contiguity constraint, Hard forms, Heidelberg, Ilog solver, Initial state, Large number, Lncs, Maximum workload, Multiple sequences, Mystery shopper problem, Night shifts, Nite, Nite automaton, Nurse scheduling problem, Occurrence problems, Other variables, Pesant, Propagator, Reformulating, Reformulation, Regular constraint, Regular constraints, Roof option, Rostering, Same length, Second model, Second sequence, Slide, Slide constraint, Soft form, Soft forms, Soft versions, Softslide, Softslide constraint, Softslide constraints, Softslidee constraint, Softslideh, Softslideh constraint, Springer, Such problems, Transition table, Wide range.
- Teeft :
- Arity, Automaton, Binary constraint, Cardpath constraint, Certain number, Combinatorial problems, Compatible values, Computer science, Constraint, Constraint toolkit, Decision variables, Dummy value, Dynamic programming, Feasible solution, Global, Global constraint, Global constraints, Global contiguity constraint, Hard forms, Heidelberg, Ilog solver, Initial state, Large number, Lncs, Maximum workload, Multiple sequences, Mystery shopper problem, Night shifts, Nite, Nite automaton, Nurse scheduling problem, Occurrence problems, Other variables, Pesant, Propagator, Reformulating, Reformulation, Regular constraint, Regular constraints, Roof option, Rostering, Same length, Second model, Second sequence, Slide, Slide constraint, Soft form, Soft forms, Soft versions, Softslide, Softslide constraint, Softslide constraints, Softslidee constraint, Softslideh, Softslideh constraint, Springer, Such problems, Transition table, Wide range.
Abstract
Abstract: Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.
Url:
DOI: 10.1007/978-3-540-73580-9_9
Links to Exploration step
ISTEX:7741FA13A6F741281AE9FFD62EAF3CEFB2AD37EDLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Reformulating Global Constraints: The Slide and Regular Constraints</title><author><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name><affiliation><mods:affiliation>LIRMM, University of Montpellier, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: bessiere@lirmm.fr</mods:affiliation></affiliation></author><author><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name><affiliation><mods:affiliation>Emmanuel Hebrard, 4C, University College Cork, Ireland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: ehebrard@4c.ucc.ie</mods:affiliation></affiliation></author><author><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name><affiliation><mods:affiliation>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics, Turkey</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: brahim.hnich@ieu.edu.tr</mods:affiliation></affiliation></author><author><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name><affiliation><mods:affiliation>Zeynep Kiziltan, Department of Computer Science, University of Bologna, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: zeynep@cs.unibo.it</mods:affiliation></affiliation></author><author><name sortKey="Quimper, Claude Guy" sort="Quimper, Claude Guy" uniqKey="Quimper C" first="Claude-Guy" last="Quimper">Claude-Guy Quimper</name><affiliation><mods:affiliation>Claude-Guy Quimper, Omega Optimisation, Canada</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: quimper@alumni.uwaterloo.ca</mods:affiliation></affiliation></author><author><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name><affiliation><mods:affiliation>Toby Walsh NICTA and University of New South Wales, Sydney, Australia</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: tw@cse.unsw.edu.au</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/978-3-540-73580-9_9</idno><idno type="url">https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001642</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001642</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Reformulating Global Constraints: The Slide and Regular Constraints</title><author><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name><affiliation><mods:affiliation>LIRMM, University of Montpellier, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: bessiere@lirmm.fr</mods:affiliation></affiliation></author><author><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name><affiliation><mods:affiliation>Emmanuel Hebrard, 4C, University College Cork, Ireland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: ehebrard@4c.ucc.ie</mods:affiliation></affiliation></author><author><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name><affiliation><mods:affiliation>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics, Turkey</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: brahim.hnich@ieu.edu.tr</mods:affiliation></affiliation></author><author><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name><affiliation><mods:affiliation>Zeynep Kiziltan, Department of Computer Science, University of Bologna, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: zeynep@cs.unibo.it</mods:affiliation></affiliation></author><author><name sortKey="Quimper, Claude Guy" sort="Quimper, Claude Guy" uniqKey="Quimper C" first="Claude-Guy" last="Quimper">Claude-Guy Quimper</name><affiliation><mods:affiliation>Claude-Guy Quimper, Omega Optimisation, Canada</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: quimper@alumni.uwaterloo.ca</mods:affiliation></affiliation></author><author><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name><affiliation><mods:affiliation>Toby Walsh NICTA and University of New South Wales, Sydney, Australia</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: tw@cse.unsw.edu.au</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2007</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Arity</term><term>Automaton</term><term>Binary constraint</term><term>Cardpath constraint</term><term>Certain number</term><term>Combinatorial problems</term><term>Compatible values</term><term>Computer science</term><term>Constraint</term><term>Constraint toolkit</term><term>Decision variables</term><term>Dummy value</term><term>Dynamic programming</term><term>Feasible solution</term><term>Global</term><term>Global constraint</term><term>Global constraints</term><term>Global contiguity constraint</term><term>Hard forms</term><term>Heidelberg</term><term>Ilog solver</term><term>Initial state</term><term>Large number</term><term>Lncs</term><term>Maximum workload</term><term>Multiple sequences</term><term>Mystery shopper problem</term><term>Night shifts</term><term>Nite</term><term>Nite automaton</term><term>Nurse scheduling problem</term><term>Occurrence problems</term><term>Other variables</term><term>Pesant</term><term>Propagator</term><term>Reformulating</term><term>Reformulation</term><term>Regular constraint</term><term>Regular constraints</term><term>Roof option</term><term>Rostering</term><term>Same length</term><term>Second model</term><term>Second sequence</term><term>Slide</term><term>Slide constraint</term><term>Soft form</term><term>Soft forms</term><term>Soft versions</term><term>Softslide</term><term>Softslide constraint</term><term>Softslide constraints</term><term>Softslidee constraint</term><term>Softslideh</term><term>Softslideh constraint</term><term>Springer</term><term>Such problems</term><term>Transition table</term><term>Wide range</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Arity</term><term>Automaton</term><term>Binary constraint</term><term>Cardpath constraint</term><term>Certain number</term><term>Combinatorial problems</term><term>Compatible values</term><term>Computer science</term><term>Constraint</term><term>Constraint toolkit</term><term>Decision variables</term><term>Dummy value</term><term>Dynamic programming</term><term>Feasible solution</term><term>Global</term><term>Global constraint</term><term>Global constraints</term><term>Global contiguity constraint</term><term>Hard forms</term><term>Heidelberg</term><term>Ilog solver</term><term>Initial state</term><term>Large number</term><term>Lncs</term><term>Maximum workload</term><term>Multiple sequences</term><term>Mystery shopper problem</term><term>Night shifts</term><term>Nite</term><term>Nite automaton</term><term>Nurse scheduling problem</term><term>Occurrence problems</term><term>Other variables</term><term>Pesant</term><term>Propagator</term><term>Reformulating</term><term>Reformulation</term><term>Regular constraint</term><term>Regular constraints</term><term>Roof option</term><term>Rostering</term><term>Same length</term><term>Second model</term><term>Second sequence</term><term>Slide</term><term>Slide constraint</term><term>Soft form</term><term>Soft forms</term><term>Soft versions</term><term>Softslide</term><term>Softslide constraint</term><term>Softslide constraints</term><term>Softslidee constraint</term><term>Softslideh</term><term>Softslideh constraint</term><term>Springer</term><term>Such problems</term><term>Transition table</term><term>Wide range</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.</div></front></TEI><istex><corpusName>springer</corpusName><keywords><teeft><json:string>constraint</json:string><json:string>slide constraint</json:string><json:string>reformulation</json:string><json:string>propagator</json:string><json:string>global constraints</json:string><json:string>reformulating</json:string><json:string>regular constraint</json:string><json:string>regular constraints</json:string><json:string>pesant</json:string><json:string>softslide</json:string><json:string>springer</json:string><json:string>lncs</json:string><json:string>softslideh</json:string><json:string>rostering</json:string><json:string>soft versions</json:string><json:string>arity</json:string><json:string>nite</json:string><json:string>automaton</json:string><json:string>heidelberg</json:string><json:string>wide range</json:string><json:string>soft forms</json:string><json:string>transition table</json:string><json:string>constraint toolkit</json:string><json:string>nite automaton</json:string><json:string>global</json:string><json:string>certain number</json:string><json:string>initial state</json:string><json:string>soft form</json:string><json:string>night shifts</json:string><json:string>dynamic programming</json:string><json:string>such problems</json:string><json:string>cardpath constraint</json:string><json:string>slide</json:string><json:string>decision variables</json:string><json:string>same length</json:string><json:string>feasible solution</json:string><json:string>compatible values</json:string><json:string>combinatorial problems</json:string><json:string>other variables</json:string><json:string>roof option</json:string><json:string>binary constraint</json:string><json:string>global contiguity constraint</json:string><json:string>second sequence</json:string><json:string>multiple sequences</json:string><json:string>computer science</json:string><json:string>softslide constraint</json:string><json:string>dummy value</json:string><json:string>softslideh constraint</json:string><json:string>softslidee constraint</json:string><json:string>ilog solver</json:string><json:string>mystery shopper problem</json:string><json:string>large number</json:string><json:string>nurse scheduling problem</json:string><json:string>second model</json:string><json:string>maximum workload</json:string><json:string>occurrence problems</json:string><json:string>softslide constraints</json:string><json:string>hard forms</json:string><json:string>global constraint</json:string></teeft></keywords><author><json:item><name>Christian Bessiere</name><affiliations><json:string>LIRMM, University of Montpellier, France</json:string><json:string>E-mail: bessiere@lirmm.fr</json:string></affiliations></json:item><json:item><name>Emmanuel Hebrard</name><affiliations><json:string>Emmanuel Hebrard, 4C, University College Cork, Ireland</json:string><json:string>E-mail: ehebrard@4c.ucc.ie</json:string></affiliations></json:item><json:item><name>Brahim Hnich</name><affiliations><json:string>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics, Turkey</json:string><json:string>E-mail: brahim.hnich@ieu.edu.tr</json:string></affiliations></json:item><json:item><name>Zeynep Kiziltan</name><affiliations><json:string>Zeynep Kiziltan, Department of Computer Science, University of Bologna, Italy</json:string><json:string>E-mail: zeynep@cs.unibo.it</json:string></affiliations></json:item><json:item><name>Claude-Guy Quimper</name><affiliations><json:string>Claude-Guy Quimper, Omega Optimisation, Canada</json:string><json:string>E-mail: quimper@alumni.uwaterloo.ca</json:string></affiliations></json:item><json:item><name>Toby Walsh</name><affiliations><json:string>Toby Walsh NICTA and University of New South Wales, Sydney, Australia</json:string><json:string>E-mail: tw@cse.unsw.edu.au</json:string></affiliations></json:item></author><arkIstex>ark:/67375/1BB-Z937VDZ4-1</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.</abstract><qualityIndicators><score>8.728</score><pdfWordCount>5552</pdfWordCount><pdfCharCount>28035</pdfCharCount><pdfVersion>1.6</pdfVersion><pdfPageCount>13</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>144</abstractWordCount><abstractCharCount>984</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Reformulating Global Constraints: The Slide and Regular Constraints</title><chapterId><json:string>9</json:string><json:string>Chap9</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>2007</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn></serie><host><title>Abstraction, Reformulation, and Approximation</title><language><json:string>unknown</json:string></language><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-73580-9</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-73580-9</json:string></eisbn><bookId><json:string>978-3-540-73580-9</json:string></bookId><isbn><json:string>978-3-540-73579-3</json:string></isbn><volume>4612</volume><pages><first>80</first><last>92</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Ian Miguel</name></json:item><json:item><name>Wheeler Ruml</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item></subject></host><namedEntities><unitex><date><json:string>2007</json:string></date><geogName></geogName><orgName><json:string>University of New South Wales</json:string><json:string>Izmir University</json:string><json:string>Department of Computer Science, University of Bologna, Italy</json:string></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName><json:string>A. Let</json:string><json:string>A. Proof</json:string><json:string>C. Note</json:string><json:string>I. Miguel</json:string><json:string>Emmanuel Hebrard</json:string><json:string>Brahim Hnich</json:string><json:string>Zeynep Kiziltan</json:string><json:string>W. Ruml</json:string><json:string>Helmut Simonis</json:string></persName><placeName><json:string>Australia</json:string><json:string>Heidelberg</json:string><json:string>Turkey</json:string><json:string>Canada</json:string><json:string>Cork</json:string><json:string>Ireland</json:string><json:string>Quimper</json:string><json:string>Sydney</json:string></placeName><ref_url><json:string>http://www.projectmanagement.ugent.be/nsp.php</json:string></ref_url><ref_bibl><json:string>[4]</json:string><json:string>[6]</json:string><json:string>[11]</json:string><json:string>[8]</json:string><json:string>[10]</json:string><json:string>[3]</json:string><json:string>[5]</json:string><json:string>C. Bessiere et al.</json:string><json:string>[2]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/1BB-Z937VDZ4-1</json:string></ark><categories><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences appliquees</json:string><json:string>4 - pollution</json:string></inist></categories><publicationDate>2007</publicationDate><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-73580-9_9</json:string></doi><id>7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Reformulating Global Constraints: The Slide and Regular Constraints</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://publisher-list.data.istex.fr">Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><licence><p>Springer-Verlag Berlin Heidelberg, 2007</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>2007</date></publicationStmt><notesStmt><note type="conference" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Reformulating Global Constraints: The Slide and Regular Constraints</title><author xml:id="author-0000"><persName><forename type="first">Christian</forename><surname>Bessiere</surname></persName><email>bessiere@lirmm.fr</email><affiliation>LIRMM, University of Montpellier, France</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Emmanuel</forename><surname>Hebrard</surname></persName><email>ehebrard@4c.ucc.ie</email><affiliation>Emmanuel Hebrard, 4C, University College Cork, Ireland</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Brahim</forename><surname>Hnich</surname></persName><email>brahim.hnich@ieu.edu.tr</email><affiliation>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics, Turkey</affiliation></author><author xml:id="author-0003"><persName><forename type="first">Zeynep</forename><surname>Kiziltan</surname></persName><email>zeynep@cs.unibo.it</email><affiliation>Zeynep Kiziltan, Department of Computer Science, University of Bologna, Italy</affiliation></author><author xml:id="author-0004"><persName><forename type="first">Claude-Guy</forename><surname>Quimper</surname></persName><email>quimper@alumni.uwaterloo.ca</email><affiliation>Claude-Guy Quimper, Omega Optimisation, Canada</affiliation></author><author xml:id="author-0005"><persName><forename type="first">Toby</forename><surname>Walsh</surname></persName><email>tw@cse.unsw.edu.au</email><affiliation>Toby Walsh NICTA and University of New South Wales, Sydney, Australia</affiliation></author><idno type="istex">7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED</idno><idno type="ark">ark:/67375/1BB-Z937VDZ4-1</idno><idno type="DOI">10.1007/978-3-540-73580-9_9</idno><idno type="ChapterID">9</idno><idno type="ChapterID">Chap9</idno></analytic><monogr><title level="m">Abstraction, Reformulation, and Approximation</title><title level="m" type="sub">7th International Symposium, SARA 2007, Whistler, Canada, July 18-21, 2007. Proceedings</title><idno type="DOI">10.1007/978-3-540-73580-9</idno><idno type="pISBN">978-3-540-73579-3</idno><idno type="eISBN">978-3-540-73580-9</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="book-title-id">151086</idno><idno type="book-id">978-3-540-73580-9</idno><idno type="book-chapter-count">42</idno><idno type="book-volume-number">4612</idno><idno type="book-sequence-number">4612</idno><idno type="PartChapterCount">26</idno><editor xml:id="book-author-0000"><persName><forename type="first">Ian</forename><surname>Miguel</surname></persName></editor><editor xml:id="book-author-0001"><persName><forename type="first">Wheeler</forename><surname>Ruml</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2007"></date><biblScope unit="volume">4612</biblScope><biblScope unit="page" from="80">80</biblScope><biblScope unit="page" to="92">92</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><biblScope><date>2007</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-id">558</idno></series><series><title level="s">Lecture Notes in Artificial Intelligence</title><editor xml:id="serie-author-0000"><persName><forename type="first">Jaime</forename><forename type="first">G.</forename><surname>Carbonell</surname></persName></editor><editor xml:id="serie-author-0001"><persName><forename type="first">J\"org</forename><surname>Siekmann</surname></persName></editor><editor xml:id="serie-author-0002"><persName><forename type="first">Ian</forename><surname>Miguel</surname></persName></editor><editor xml:id="serie-author-0003"><persName><forename type="first">Wheeler</forename><surname>Ruml</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><biblScope unit="seriesId">1244</biblScope></series></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2007</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I21017</label><label>I16048</label><label>I1603X</label><item><term>Computer Science</term></item><item><term>Artificial Intelligence (incl. Robotics)</term></item><item><term>Mathematical Logic and Formal Languages</term></item><item><term>Logics and Meanings of Programs</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2007">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-10-4">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SubSeries><SubSeriesInfo><SubSeriesID>1244</SubSeriesID><SubSeriesPrintISSN>0302-9743</SubSeriesPrintISSN><SubSeriesElectronicISSN>1611-3349</SubSeriesElectronicISSN><SubSeriesTitle Language="En">Lecture Notes in Artificial Intelligence</SubSeriesTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Jaime</GivenName><GivenName>G.</GivenName><FamilyName>Carbonell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J\"org</GivenName><FamilyName>Siekmann</FamilyName></EditorName></Editor></EditorGroup></SubSeriesHeader></SubSeries><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-73580-9</BookID><BookTitle>Abstraction, Reformulation, and Approximation</BookTitle><BookSubTitle>7th International Symposium, SARA 2007, Whistler, Canada, July 18-21, 2007. Proceedings</BookSubTitle><BookVolumeNumber>4612</BookVolumeNumber><BookSequenceNumber>4612</BookSequenceNumber><BookDOI>10.1007/978-3-540-73580-9</BookDOI><BookTitleID>151086</BookTitleID><BookPrintISBN>978-3-540-73579-3</BookPrintISBN><BookElectronicISBN>978-3-540-73580-9</BookElectronicISBN><BookChapterCount>42</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I21017" Priority="1" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I16048" Priority="2" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I1603X" Priority="3" Type="Secondary">Logics and Meanings of Programs</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Ian</GivenName><FamilyName>Miguel</FamilyName></EditorName><Contact><Email>ianm@dcs.st-and.ac.uk</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Wheeler</GivenName><FamilyName>Ruml</FamilyName></EditorName><Contact><Email>ruml@acm.org</Email></Contact></Editor></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Research Papers</PartTitle><PartChapterCount>26</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Abstraction, Reformulation, and Approximation</BookTitle></PartContext></PartInfo><Chapter ID="Chap9" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>9</ChapterID><ChapterDOI>10.1007/978-3-540-73580-9_9</ChapterDOI><ChapterSequenceNumber>9</ChapterSequenceNumber><ChapterTitle Language="En">Reformulating Global Constraints: The <Emphasis Type="SmallCaps">Slide</Emphasis> and <Emphasis Type="SmallCaps">Regular</Emphasis> Constraints</ChapterTitle><ChapterFirstPage>80</ChapterFirstPage><ChapterLastPage>92</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>2</PartID><BookID>978-3-540-73580-9</BookID><BookTitle>Abstraction, Reformulation, and Approximation</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Christian</GivenName><FamilyName>Bessiere</FamilyName></AuthorName><Contact><Email>bessiere@lirmm.fr</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Emmanuel</GivenName><FamilyName>Hebrard</FamilyName></AuthorName><Contact><Email>ehebrard@4c.ucc.ie</Email></Contact></Author><Author AffiliationIDS="Aff3"><AuthorName DisplayOrder="Western"><GivenName>Brahim</GivenName><FamilyName>Hnich</FamilyName></AuthorName><Contact><Email>brahim.hnich@ieu.edu.tr</Email></Contact></Author><Author AffiliationIDS="Aff4"><AuthorName DisplayOrder="Western"><GivenName>Zeynep</GivenName><FamilyName>Kiziltan</FamilyName></AuthorName><Contact><Email>zeynep@cs.unibo.it</Email></Contact></Author><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>Claude-Guy</GivenName><FamilyName>Quimper</FamilyName></AuthorName><Contact><Email>quimper@alumni.uwaterloo.ca</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Toby</GivenName><FamilyName>Walsh</FamilyName></AuthorName><Contact><Email>tw@cse.unsw.edu.au</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>LIRMM, University of Montpellier</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Emmanuel Hebrard, 4C, University College Cork</OrgName><OrgAddress><Country>Ireland</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics</OrgName><OrgAddress><Country>Turkey</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Zeynep Kiziltan, Department of Computer Science, University of Bologna</OrgName><OrgAddress><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>Claude-Guy Quimper, Omega Optimisation</OrgName><OrgAddress><Country>Canada</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Toby Walsh NICTA and University of New South Wales, Sydney</OrgName><OrgAddress><Country>Australia</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, <Emphasis Type="SmallCaps">Slide</Emphasis> and <Emphasis Type="SmallCaps">Regular</Emphasis>. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of <Emphasis Type="SmallCaps">Slide</Emphasis> and <Emphasis Type="SmallCaps">Regular</Emphasis> can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Reformulating Global Constraints: The Slide and Regular Constraints</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Reformulating Global Constraints: The Slide and Regular Constraints</title></titleInfo><name type="personal"><namePart type="given">Christian</namePart><namePart type="family">Bessiere</namePart><affiliation>LIRMM, University of Montpellier, France</affiliation><affiliation>E-mail: bessiere@lirmm.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Emmanuel</namePart><namePart type="family">Hebrard</namePart><affiliation>Emmanuel Hebrard, 4C, University College Cork, Ireland</affiliation><affiliation>E-mail: ehebrard@4c.ucc.ie</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Brahim</namePart><namePart type="family">Hnich</namePart><affiliation>Brahim Hnich, Faculty of Computer Science, Izmir University of Economics, Turkey</affiliation><affiliation>E-mail: brahim.hnich@ieu.edu.tr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Zeynep</namePart><namePart type="family">Kiziltan</namePart><affiliation>Zeynep Kiziltan, Department of Computer Science, University of Bologna, Italy</affiliation><affiliation>E-mail: zeynep@cs.unibo.it</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Claude-Guy</namePart><namePart type="family">Quimper</namePart><affiliation>Claude-Guy Quimper, Omega Optimisation, Canada</affiliation><affiliation>E-mail: quimper@alumni.uwaterloo.ca</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Toby</namePart><namePart type="family">Walsh</namePart><affiliation>Toby Walsh NICTA and University of New South Wales, Sydney, Australia</affiliation><affiliation>E-mail: tw@cse.unsw.edu.au</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2007</dateIssued><dateIssued encoding="w3cdtf">2007</dateIssued><copyrightDate encoding="w3cdtf">2007</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, Slide and Regular. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of Slide and Regular can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints.</abstract><relatedItem type="host"><titleInfo><title>Abstraction, Reformulation, and Approximation</title><subTitle>7th International Symposium, SARA 2007, Whistler, Canada, July 18-21, 2007. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Ian</namePart><namePart type="family">Miguel</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Wheeler</namePart><namePart type="family">Ruml</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic></subject><identifier type="DOI">10.1007/978-3-540-73580-9</identifier><identifier type="ISBN">978-3-540-73579-3</identifier><identifier type="eISBN">978-3-540-73580-9</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">151086</identifier><identifier type="BookID">978-3-540-73580-9</identifier><identifier type="BookChapterCount">42</identifier><identifier type="BookVolumeNumber">4612</identifier><identifier type="BookSequenceNumber">4612</identifier><identifier type="PartChapterCount">26</identifier><part><date>2007</date><detail type="part"><title>Research Papers</title></detail><detail type="volume"><number>4612</number><caption>vol.</caption></detail><extent unit="pages"><start>80</start><end>92</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Artificial Intelligence</title></titleInfo><name type="personal"><namePart type="given">Jaime</namePart><namePart type="given">G.</namePart><namePart type="family">Carbonell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J\"org</namePart><namePart type="family">Siekmann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Ian</namePart><namePart type="family">Miguel</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Wheeler</namePart><namePart type="family">Ruml</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SubSeriesID">1244</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><identifier type="istex">7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED</identifier><identifier type="ark">ark:/67375/1BB-Z937VDZ4-1</identifier><identifier type="DOI">10.1007/978-3-540-73580-9_9</identifier><identifier type="ChapterID">9</identifier><identifier type="ChapterID">Chap9</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2007</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/document/7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED/metadata/json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001642 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001642 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:7741FA13A6F741281AE9FFD62EAF3CEFB2AD37ED
|texte= Reformulating Global Constraints: The Slide and Regular Constraints
}}
| This area was generated with Dilib version V0.6.33. |  |