Change search
Refine search result
123 1 - 50 of 123
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Aggoun, Abderrahmane
    et al.
    Beldiceanu, Nicolas
    Carlsson, Mats
    RISE, Swedish ICT, SICS. Computer Systems Laboratory.
    Fages, François
    Integrating rule-based modelling and constraint programming for solving industrial packing problems2010In: ERCIM News, ISSN 0926-4981, E-ISSN 1564-0094, p. 34-35Article in journal (Other (popular science, discussion, etc.))
    Abstract [en]

    Packing items in bins is an old but nevertheless challenging combinatorial problem with numerous applications in industry. We report on an original approach based on constraint programming and rule-based modelling, which has been investigated in the framework of the FP6 ‘specific targeted research project’ Net-WMS (Towards integrating virtual reality and optimization techniques in a new generation of Networked businesses in Warehouse Management Systems under constraints). It has applications in the automotive industry.

  • 2. Almgren, Jonas
    et al.
    Andersson, Stefan
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flood, Lena
    Haridi, Seif
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Frisk, Claes
    Nilsson, Hans
    Sundberg, Jan
    SICStus Prolog library manual, version 2.1 #81993Report (Other academic)
    Abstract [en]

    This Manual corresponds to SICStus Prolog release 2.1. #8 The Prolog library comprises a number of packages which are thought to be useful in a number of applications. Note that the predicates in the Prolog library are built-in predicates. One has to explicity load each package to get access to its predicates. To load a library package Package, you will normally enter a query. I ?- use_module(library(Package)). Library packages may be compiled and consulted as well as loaded.

  • 3. Ameur, Adam
    et al.
    Aurell, Erik
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Westholm, Jakub Orzechowski
    Global gene expression analysis by combinatorial optimization2004In: In Silico Biology, ISSN 1434-3207, Vol. 4Article in journal (Refereed)
    Abstract [en]

    Generally, there is a trade-off between methods of gene expression analysis that are precise but labor-intensive, e.g. RT-PCR, and methods that scale up to global coverage but are not quite as quantitative, e.g. microarrays. In the present paper, we show how how a known method of gene expression profiling (K. Kato, Nucleic Acids Research 23, 3685-3690 (1995)), which relies on a fairly small number of steps, can be turned into a global gene expression measurement by advanced data post-processing, with potentially little loss of accuracy. Post-processing here entails solving an ancillary combinatorial optimization problem. Validation is performed on in silico experiments generated from the FANTOM data base of full-length mouse cDNA. We present two variants of the method. One uses state-of-the-art commercial software for solving problems of this kind, the other a code developed by us specifically for this purpose, released in the public domain under GPL license.

  • 4. Andersson, Johan
    et al.
    Andersson, Stefan
    Boortz, Kent
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Nilsson, Hans
    Sjöland, Thomas
    RISE - Research Institutes of Sweden, ICT, SICS.
    Widén, Johan
    RISE - Research Institutes of Sweden, ICT, SICS.
    SICStus Prolog user's manual, version 2.1 #81993Report (Other academic)
    Abstract [en]

    This Manual corresponds to SICStus Prolog release 2.1. #8 Prolog is a simple but powerful programming language developed at the University of Marseilles (Prolog : Manuel de Reference et d'Utilisation by P.Roussel, Groupe d'Intelligence Artificielle, Marseille-Luminy, 1975), as a practical tool for programming in Logic (Logic for Problem Solving by R.A. Kowalski, DCL Memo 75, Dept. of Artificial Intelligence, University of Edinburgh, March, 1974.)) From a user's point of view the major attraction of the language is ease of programming. Clear, readable, concise programs can be written quickly with few errors. This manual describes a Prolog system developed at the Swedish Institute of Computer Science in collaboration with Ericsson Telecom AB, NobelTech Systems AB, Infologics AB and Televerket under the IT4 program. The system consists of a WAM emulator written in C, a library and runtime system written in C and Prolog and an interpreter and a compiler written in Prolog. The Prolog engine is a Warren Abstract Machine (WAM) emulator defined by D:H:D: Warren in An Abstract Prolog Instruction Set, Tech. Note 309, International, Menlo Park, CA, 1983. Two modes of compilation are available: in-core i.e. incremental, and file-to-file.

  • 5. Appleby, Karen
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Haridi, Seif
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sahlin, Dan
    RISE, Swedish ICT, SICS.
    Garbage Collection for Prolog Based on WAM (Revised version)1986Report (Other academic)
    Abstract [en]

    Warren Abstract Machine (WAM) has become a generally accepted standard Prolog implementation technique. Garbage collection is an important aspect in the implementation of any Prolog system. We first present a synopsis of the WAM and then show marking and compaction algorithms that take advantage of WAM's unique use of the data areas. Marking and compaction are performed on both the heap and the trail. The marking and compaction algorithms use pointer reversal techniques, which obviate the need for extra stack space. However, two bits for every pointer on the heap are reserved for the garbage collection algorithm. The algorithm can work on segments of the heap, which may lead to a significant reduction of the total garbage collection time. The time of the algorithms are linear in the size of the areas.

  • 6. Arafailova, Ekaterina
    et al.
    Beldiceanu, Nicolas
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Francisco Rodríguez, María Andreína
    Pearson, Justin
    Simonis, Helmut
    Systematic Derivation of Bounds and Glue Constraints for Time-Series Constraints2016In: International Conference on Principles and Practice of Constraint Programming (CP 2016), Springer Publishing Company, 2016, p. 13-29Conference paper (Refereed)
    Abstract [en]

    Integer time series are often subject to constraints on the aggregation of the integer features of all occurrences of some pattern within the series. For example, the number of inflexions may be constrained, or the sum of the peak maxima, or the minimum of the peak widths. It is currently unknown how to maintain domain consistency efficiently on such constraints. We propose parametric ways of systematically deriving glue constraints, which are a particular kind of implied constraints, as well as aggregation bounds that can be added to the decomposition of time-series constraints [5]. We evaluate the beneficial propagation impact of the derived implied constraints and bounds, both alone and together.

  • 7. Arafailova, Ekaterina
    et al.
    Beldiceanu, Nicolas
    Douence, Rémi
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Francisco Rodríguez, María Andreína
    Pearson, Justin
    Simonis, Helmut
    Global Constraint Catalog Volume II: Time-Series Constraints2016Other (Other academic)
    Abstract [en]

    First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with accumulators.

  • 8. Aurell, Erik
    et al.
    Boman, Magnus
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A trading agent built on constraint programming2002Conference paper (Refereed)
    Abstract [en]

    The Trading Agent Competition (TAC) combines a fairly realistic model of the Internet commerce of the future, including shopbots and pricebots, with a challenging problem in automated reasoning and decision making. Automated trading via auctions under severe time constraints are to be con-ducted by entering autonomous agents into TAC, assuming the role of travel agents. The TAC game rules, as well as a description of the discrete op-timization problem faced by an agent that wishes to allocate goods to its clients, are described. The TAC’01 entry “006”, encapsulating a constraint programming solution, is explained in some detail.

  • 9.
    Aurell, Erik
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Ekman, Jan
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    GENFUNK2002Report (Other academic)
    Abstract [en]

    This document summarizes the results obtained by SICS in project GENFUNK (2001). The project was carried out in collaboration with Global Genomics AB (Stockholm, Sweden). Jointly obtained results will be presented separately. Main funding was provided by Swedish Research Agency VINNOVA. Project GENFUNK studied a novel approach of measuring the global gene expression. In the method, mRNA is extracted from a tissue sample and transformed into cDNA captured on magnetic beads. This is then acted on by type IIS restriction endonucleases, which recognize certain short DNA sequences and cut the DNA close to those sequences. The resulting fragments are amplified in PCR with selected ligation fragments, and displayed in capillary electrophoresis. Determining the gene expression levels from the peak data is combinatorial optimization problem, which can in principle be solved, to give expression levels of most genes active in sampled cells, with good accuracy.

  • 10. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A New multi-resource cumulatives constraint with negative heights2002In: CP'2002, Principles and Practice of Constraint Programming, Springer-Verlag , 2002, 1, Vol. 2470, p. 63-79Conference paper (Refereed)
    Abstract [en]

    This paper presents a new cumulatives constraint which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation algorithm is derived from an idea called sweep which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction, while the last is a generalization of task intervals to this new context. A real-life timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.

  • 11.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A New Multi-Resource cumulatives Constraint with Negative Heights2001Report (Other academic)
    Abstract [en]

    This paper presents a new cumulatives constraint which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation algorithm is derived from an idea called sweep which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction, while the last is a generalization of task intervals to this new context. A real-life timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.

  • 12.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Constructive Cardinality2001Report (Other academic)
    Abstract [en]

    We describe a set of necessary conditions that are useful for generating propagation algorithms for the cardinality operator as well as for over-constrained problems with preferences. Constructive disjunction as well as the entailments rules originally proposed for the cardinality operator can be seen as simple cases of these necessary conditions. In addition these necessary conditions have the advantage of providing more pruning.

  • 13.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Revisiting the cardinality operator and introducing the cardinality-path constraint family2001Conference paper (Refereed)
    Abstract [en]

    This paper presents generic propagation algorithms for the cardinality-path constraint family. This is a restricted form of the cardinality operator that allows stating constraints on sliding sequences of consecutive variables. Taking advantage of these restrictions permits coming up with more efficient algorithms. Moreover the paper shows how to extend these propagation algorithms in order to partially integrate external constraints that have to hold. From an application point of view the cardinality-path constraint allows to express a huge variety of regulation constraints occurring in personnel planning problems.

  • 14.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sweep as a generic pruning technique applied to constraint relaxation2001Conference paper (Refereed)
    Abstract [en]

    We introduce a new generic filtering algorithm for handling constraint relaxation within constraint programming. More precisely, we first present a generic pruning technique, which is useful for a special case of the cardinality operator where all the constraints have at least two variables in common. This method is based on a generalisation of a sweep algorithm, which handles a conjunction of constraints to the case where one just knows the minimum and maximum number of constraints that have to hold. The main benefit of this new technique comes from the fact that, even if we don't know which, and exactly how many constraints, will hold in the final solution, we can still prune the variables of those constraints right from the beginning according to the minimum and maximum number of constraints that have to hold. We then show how to extend the previous sweep algorithm in order to handle preferences among constraints. Finally, we specialise this technique to an extension of the non-overlapping rectangles constraint, where we permit controlling how many non-overlapping constraints should hold. This allows handling over-constrained placement problems and provides constraint propagation even if some non-overlapping constraints have to be relaxed.

  • 15.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint2001Conference paper (Refereed)
    Abstract [en]

    We first present a generic pruning technique, which aggregates several constraints sharing some variables. The method is derived from an idea called sweep, which is extensively used, in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. We then specialise this technique to the non-overlapping rectangles constraint, describe several optimisations, and give an empirical evaluation based on six sets of test instances with different characteristics.

  • 16.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Sweep as a Generic Pruning Technique Applied to the Non-Overlapping Rectangles Constraint2001Report (Other academic)
    Abstract [en]

    We first present a generic pruning technique which aggregates several constraints sharing some variables. The method is derived from an idea called \dfn{sweep} which is extensively used in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. We then specialize this technique to the non-overlapping rectangles constraint, describe several optimizations, and give an empirical evaluation based on six sets of test instances of different pattern.

  • 17. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Debruyne, Romuald
    Petit, Thierry
    Reformulation of global constraints based on constraint checkers2005In: Constraints, Vol. 10Article in journal (Refereed)
    Abstract [en]

    This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton reformulation. Under some restrictions on the signature and transition constraints, this reformulation maintains arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide an automaton reformulation for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

  • 18. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS.
    Demassey, Sophie
    Petit, Thierry
    Global Constraint Catalogue: Past, Present and Future2007In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 12, no 1, p. 21-62Article in journal (Refereed)
    Abstract [en]

    The catalogue of global constraints is reviewed, focusing on the graph-based description of global constraints. A number of possible enhancements are proposed as well as several research paths for the development of the area.

  • 19. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Demassey, Sophie
    Petit, Thierry
    Graph properties based filtering2006Conference paper (Refereed)
  • 20. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Demassey, Sophie
    Petit, Thierry
    Graph Properties Based Filtering2006Report (Other academic)
    Abstract [en]

    This report presents a generic filtering scheme, based on the graph description of global constraints. This description is defined by a network of binary constraints and a list of elementary graph properties: each solution of the global constraint corresponds to a subgraph of the initial network, retaining only the satisfied binary constraints, and which fulfills all the graph properties. The graph-based filtering identifies the arcs of the network that belong or not to the solution subgraphs. The objective is to build, besides a catalog of global constraints, also a list of systematic filtering rules based on a limited set of graph properties. We illustrate this principle on some common graph properties and provide computational experiments of the effective filtering on the "group" constraint.

  • 21. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Demassey, Sophie
    Poder, Emmanuel
    New Filtering for the Cumulative Constraint in the Context of Non-Overlapping Rectangles2011In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338, Vol. 1, p. 27-50Article in journal (Refereed)
    Abstract [en]

    This article describes new filtering methods for the Cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the Non-Overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 65 perfect square instances of order 22-25 and sizes ranging from 192x192 to 661x661.

  • 22. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Derrien, A.
    Schutt, A.
    Stuckey, P.
    Range-consistent forbidden regions of Allen's relations2016Report (Other academic)
    Abstract [en]

    For all 8192 combinations of Allen's 13 relations between one task with origin oi and fixed length li and another task with origin oj and fixed length lj, we give a formula F(min(oj), max(oj), li, lj), where min(oj) and max(oj) respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions are useful e.g. in a range-consistency maintaining propagator for an Allen constraint in finite domain constraint programming.

  • 23.
    Beldiceanu, Nicolas
    et al.
    IMT Atlantique, France.
    Carlsson, Mats
    RISE - Research Institutes of Sweden, ICT, SICS.
    Derrien, Alban
    Université de Bretagne-Sud, France.
    Prud’Homme, Charles
    IMT Atlantique, France.
    Schutt, Andreas
    CSIRO, Australia ; University of Melbourne, Australia.
    Stuckey, PJ.
    CSIRO, Australia ; University of Melbourne, Australia.
    Range-consistent forbidden regions of allen’s relations2017Conference paper (Refereed)
    Abstract [en]

    For all 8192 combinations of Allen’s 13 relations between one task with origin oi and fixed length ℓi and another task with origin oj and fixed length ℓj, this paper shows how to systematically derive a formula F (oj, oj, ℓi, ℓj), where oj and oj respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions allow maintaining range-consistency for an Allen constraint.

  • 24. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Douence, Rémi
    Simonis, Helmut
    Using finite transducers for describing and synthesising structural time-series constraints2015In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 21, p. 22-40Article in journal (Refereed)
    Abstract [en]

    We describe a large family of constraints for structural time series by means of function composition. These constraints are on aggregations of features of patterns that occur in a time series, such as the number of its peaks, or the range of its steepest ascent. The patterns and features are usually linked to physical properties of the time series generator, which are important to capture in a constraint model of the system, i.e. a conjunction of constraints that produces similar time series. We formalise the patterns using finite transducers, whose output alphabet corresponds to semantic values that precisely describe the steps for identifying the occurrences of a pattern. Based on that description, we automatically synthesise automata with accumulators, as well as constraint checkers. The description scheme not only unifies the structure of the existing 30 time-series constraints in the Global Constraint Catalogue, but also leads to over 600 new constraints, with more than 100,000 lines of synthesised code.

  • 25. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Lorca, Xavier
    Pearson, Justin
    Petit, Thierry
    Prud'homme, Charles
    A Modelling Pearl with Sortedness Constraints2015Conference paper (Refereed)
    Abstract [en]

    Some constraint programming solvers and constraint modelling languages feature the Sort(L,P,S) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.

  • 26. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On Matrices, Automata, and Double Counting2010Conference paper (Refereed)
    Abstract [en]

    Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M, with the same constraint defined by a finite-state automaton A on each row of M and a global cardinality constraint gcc on each column of M. We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the gcc constraints from the automaton A. The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We evaluate the impact of our methods on a large set of nurse rostering problem instances.

  • 27. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On matrices, automata, and double counting in constraint programming2013In: Constraints, Vol. 18, p. 108-140Article in journal (Refereed)
    Abstract [en]

    Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M , with the same constraint C defined by a finite-state automaton A on each row of M and a global cardinality constraint "gcc" on each column of M . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the "gcc" constraints from the automaton A . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of M and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.

  • 28. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On the Reification of Global Constraints2012Report (Other academic)
    Abstract [en]

    We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of pure functional dependency constraints together with a constraint that can be easily reified. We first show how the core constraints of the Global Constraint Catalogue can be reified and we then identify several reification categories that apply to at least 82% of the constraints in the Global Constraint Catalogue.

  • 29. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Pearson, Justin
    On the reification of global constraints2013In: Constraints, Vol. 18, p. 1-6Article in journal (Refereed)
    Abstract [en]

    We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of total function constraints together with a constraint that can be easily reified.

  • 30. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Flener, Pierre
    Rodríguez, María Andreína Francisco
    Pearson, Justin
    Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators2014Conference paper (Refereed)
    Abstract [en]

    Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.

  • 31. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Martin, Julien
    Compiling business rules in a geometric constraint over k-dimensional objects and shapes2009Report (Other academic)
    Abstract [en]

    It is well known that real-life applications rarely admit a constraint model expressed purely in terms of a few global constraints. Usually, the global constraints capture a relaxed form of the problem, but needs additional side-constraints to capture the full problem. Handling such side-constraints inside the global constraints, as opposed to in conjunction with it, improves propagation. Historically, this has been done by extending the global constraints with a host of specific options, each connected to a specific filtering method. Being able to express and filter side-constraints in a more uniform and systematic way would seem a more elegant and manageable solution. This report presents such a mechanism for the global non-overlapping constraint "geost", which handles the location in space of k-dimensional objects. Side-constraints are expressed as rules written in a language based on arithmetic and first-order logic, which should hold among the objects. We explain in detail the way the rules are compiled into a form that is accessed by the constraint's sweep-based filtering algorithm. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are transformed to generators of k-dimensional forbidden sets. Thirdly, the generators are transformed to procedures answering queries about candidate coordinate points for a given object. Such queries are at the heart of the filtering algorithm. The business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer, and was evaluated on several benchmarks.

  • 32. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Deriving Filtering Algorithms from Constraint Checkers2004Report (Other academic)
    Abstract [en]

    This report deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in $n$, where $n$ is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

  • 33. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Deriving filtering algorithms from constraint checkers2004In: Proceedings of Principles and Practice of Constraint Programming – CP 2004, 10th International Conference, Springer , 2004, 1, Vol. 3258, p. 16p. 107-122Conference paper (Refereed)
    Abstract [en]

    This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.

  • 34. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Petit, Thierry
    Régin, Jean-Charles
    An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization2012Conference paper (Refereed)
    Abstract [en]

    This paper gives an O(n log n) bound-consistency filtering algorithm for the conjunction alldifferent(V0,V1,…,Vn−1)∧ f(V0)⌖f(V1)⌖…⌖f(Vn−1) ≤ cst, (V0,V1,…,Vn−1,cst ∊ N+), where (N,⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

  • 35. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Poder, Emmanuel
    New filtering for the cumulative constraint in the context of non-overlapping rectangles2008In: CPAIOR 2008, Springer , 2008, 1, Vol. 5015, p. 21-35Conference paper (Refereed)
    Abstract [en]

    This paper describes new filtering methods for the cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the non-overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23-25 and sizes ranging from 332 times 332 to 661 times 661.

  • 36.
    Beldiceanu, Nicolas
    et al.
    RISE, Swedish ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Poder, Emmanuel
    Sadek, Rida
    Truchet, Charlotte
    A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects2007Conference paper (Refereed)
    Abstract [en]

    This paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.

  • 37. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog2005Report (Other academic)
    Abstract [en]

    This report presents a catalog of global constraints where each constraint is explicitly described in terms of graph properties and/or automata. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 38. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog, 2nd Edition2010Report (Other academic)
    Abstract [en]

    This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 39. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Global Constraint Catalog, 2nd Edition (revision a)2012Report (Other academic)
    Abstract [en]

    This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

  • 40. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Truchet, Charlotte
    Graph invariants as necessary conditions for global constraints2005In: CP'2005, Principles and Practice of Constraint Programming, LNCS, Vol. 3709, p. 92-106Article in journal (Refereed)
    Abstract [en]

    This article presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.

  • 41. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Rampon, Jean-Xavier
    Truchet, Charlotte
    Graph Invariants as Necessary Conditions for Global Constraints2005Report (Other academic)
    Abstract [en]

    This report presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.

  • 42. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Cost-Filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint2002Report (Other academic)
    Abstract [en]

    This article introduces the sum of weights of distinct values constraint, which can be seen as a generalization of the number of distinct values as well as of the alldifferent, and the relaxed alldifferent constraints. This constraint holds if a cost variable is equal to the sum of the weights associated to the distinct values taken by a given set of variables. For the first aspect, which is related to domination, we present four filtering algorithms. Two of them lead to perfect pruning when each domain variable consists of one set of consecutive values, while the two others take advantage of holes in the domains. For the second aspect, which is connected to maximum matching in a bipartite graph, we provide a complete filtering algorithm for the general case. Finally we introduce several generic deduction rules, which link both aspects of the constraint. These rules can be applied to other optimization constraints such as the minimum weight alldifferent constraint or the global cardinality constraint with costs. They also allow taking into account external constraints for getting enhanced bounds for the cost variable. In practice, the sum of weights of distinct values constraint occurs in assignment problems where using a resource once or several times costs the same. It also captures domination problems where one has to select a set of vertices in order to control every vertex of a graph.

  • 43. Beldiceanu, Nicolas
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep synchronisation as a global propagation mechanism2006In: Computers & Operations Research, Vol. 3, p. 2835-2851Article in journal (Refereed)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Y_k of the pairs (X,Y_k) (1 <= k <= n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specialize this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has his own periods of unavailability and can only perform one task at a time.

  • 44.
    Beldiceanu, Nicolas
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep Synchronization as a Global Propagation Mechanism2003Report (Other academic)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (1<=k<=n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specializes this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has its own periods of unavailability and can only perform one task at a time.

  • 45.
    Beldiceanu, Nicolas
    et al.
    RISE, Swedish ICT, SICS.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Thiel, Sven
    Sweep synchronization as a global propagation mechanism2003Conference paper (Refereed)
    Abstract [en]

    This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (1<=k<=n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specialize this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can not be interrupted and requires the simultaneous availability of n distinct persons. Each person has his own periods of unavailability and can only perform one task at a time.

  • 46. Beldiceanu, Nicolas
    et al.
    Poder, Emmanuel
    Sadek, Rida
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Truchet, Charlotte
    A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects2007Report (Other academic)
    Abstract [en]

    This report introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.

  • 47. Carlson, Björn
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Compiling and executing disjunctions of finite domain constraints1995In: Proceedings of the Twelfth International Conference on Logic Programming, 13-16 June 1995, Tokyo, Japan / [ed] L. Sterling, The MIT Press , 1995, 1, , p. 15Conference paper (Refereed)
  • 48. Carlson, Björn
    et al.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Diaz, Daniel
    Entailment of finite domain constraints1994Conference paper (Refereed)
  • 49. Carlson, Björn
    et al.
    Janson, Sverker
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    The implementation of AKL(FD)1995Conference paper (Refereed)
  • 50.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    A BDD-based approach to multiple level combinational logic synthesis1992In: Practical Application of Prolog / [ed] Al Roth, 1992, 1Conference paper (Refereed)
123 1 - 50 of 123
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.35.4