Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
Link to record
Permanent link

Direct link
Alternative names
Publications (10 of 103) Show all publications
Forghani, K., Carlsson, M., Flener, P., Fredriksson, M., Pearson, J. & Yuan, D. (2024). Maximizing Value Yield in Wood Industry through Flexible Sawing and Product Grading Based on Wane and Log Shape. Computers and Electronics in Agriculture, 216, Article ID 108513.
Open this publication in new window or tab >>Maximizing Value Yield in Wood Industry through Flexible Sawing and Product Grading Based on Wane and Log Shape
Show others...
2024 (English)In: Computers and Electronics in Agriculture, ISSN 0168-1699, E-ISSN 1872-7107, Vol. 216, article id 108513Article in journal (Refereed) Published
Abstract [en]

The optimization of sawing processes in the wood industry is critical for maximizing efficiency and profitability. The introduction of computerized tomography scanners provides sawmill operators with three-dimensional internal models of logs, which can be used to assess value and yield more accurately. We present a methodology for solving the sawing optimization problem employing a flexible sawing scheme that allows greater flexibility in cutting logs into products while considering product quality classes influenced by wane defects. The methodology has two phases: preprocessing and optimization. In the preprocessing phase, two alternative algorithms are given that generate and evaluate the potential sawing positions of products by considering the 3D surface of the log, product size requirements, and product quality classes. In the optimization phase, a maximum set-packing problem is solved for the preprocessed data using mixed-integer programming (MIP), aiming to obtain a feasible cut pattern that maximizes value yield. This is implemented in a system named FlexSaw, which takes advantage of parallel computation during the preprocessing phase and utilizes a MIP solver during the optimization phase. The proposed sawing methods are evaluated on the Swedish Pine Stem Bank. Additionally, FlexSaw is compared with an existing tool that utilizes cant sawing. Results demonstrate the superiority of flexible sawing. While the practical feasibility of implementing a flexible way of sawing logs is constrained by the limitations of current sawmill machinery, the potential increase in yield promotes the exploration of alternative machinery in the wood industry.

Place, publisher, year, edition, pages
Elsevier, 2024
National Category
Wood Science
Research subject
Wood Science and Engineering
Identifiers
urn:nbn:se:uu:diva-517316 (URN)10.1016/j.compag.2023.108513 (DOI)001139709900001 ()
Funder
Vinnova, 2020-03734
Available from: 2023-11-29 Created: 2023-12-06 Last updated: 2024-02-07Bibliographically approved
Pearson, J. (2024). Parameterised Treewidth for Constraint Modelling Languages. In: 2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI): . Paper presented at 36th International Conference on Tools with Artificial Intelligence, Oct 28-30, 2024, Herndon, VA, USA (pp. 43-48). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Parameterised Treewidth for Constraint Modelling Languages
2024 (English)In: 2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI), Institute of Electrical and Electronics Engineers (IEEE), 2024, p. 43-48Conference paper, Published paper (Refereed)
Abstract [en]

Constraint programming is a widely used paradigm to solve combinatorial problems. High-level constraint modelling languages, such as MiniZinc, GAMS, OPL, and AMPL, encourage the separation of instance parameters and models, where the number of variables and constraints depend on values of instance parameters. This paper investigates an extension of treewidth suitable for studying the complexity high-level constraint models.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2024
Series
Proceedings - International Conference on Tools With Artificial Intelligence, ISSN 1082-3409, E-ISSN 2375-0197
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-557892 (URN)10.1109/ICTAI62512.2024.00015 (DOI)001447778900006 ()2-s2.0-85217392024 (Scopus ID)979-8-3315-2724-2 (ISBN)979-8-3315-2723-5 (ISBN)
Conference
36th International Conference on Tools with Artificial Intelligence, Oct 28-30, 2024, Herndon, VA, USA
Funder
Swedish Research Council, 2018-04813
Available from: 2025-06-03 Created: 2025-06-03 Last updated: 2025-06-03Bibliographically approved
Martin, B. & Pearson, J. (2022). When bounds consistency implies domain consistency for regular counting constraints. Constraints, 27(3), 161-167
Open this publication in new window or tab >>When bounds consistency implies domain consistency for regular counting constraints
2022 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 27, no 3, p. 161-167Article in journal (Refereed) Published
Abstract [en]

Finite automata with counters are often used to specify families of constraints. The addition of counters provides more power than membership in regular languages that is possible with finite automata. All available propagation algorithms for counter automata based constraints maintain only bounds consistency on counter variables, and although it is possible to maintain domain consistency it can be computationally very costly. In this paper we give an algorithm that decides when maintaining bounds consistency for an automata with a single counter implies domain consistency.

Place, publisher, year, edition, pages
Springer NatureSpringer Nature, 2022
Keywords
Automata, Consistency
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-483987 (URN)10.1007/s10601-022-09333-0 (DOI)000798103900001 ()
Available from: 2022-09-06 Created: 2022-09-06 Last updated: 2024-01-15Bibliographically approved
Björdal, G., Flener, P., Pearson, J., Stuckey, P. J. & Tack, G. (2020). Solving Satisfaction Problems using Large-Neighbourhood Search. In: Helmut Simonis (Ed.), Principles and Practice of Constraint Programming: . Paper presented at 26th International Conference on Principles and Practice of Constraint Programming, Louvain-la-Neuve, Belgium, September 7 – September 11, 2020 (pp. 55-71). , 12333
Open this publication in new window or tab >>Solving Satisfaction Problems using Large-Neighbourhood Search
Show others...
2020 (English)In: Principles and Practice of Constraint Programming / [ed] Helmut Simonis, 2020, Vol. 12333, p. 55-71Conference paper, Published paper (Refereed)
Abstract [en]

Large-neighbourhood search (LNS) improves an initial solution, hence it is not directly applicable to satisfaction problems. In order to use LNS in a constraint programming (CP) framework to solve satisfaction problems, we usually soften some hard-to-satisfy constraints by replacing them with penalty-function constraints. LNS is then used to reduce their penalty to zero, thus satisfying the original problem. However, this can give poor performance as the penalties rarely cause propagation and therefore do not drive each CP search, and by extension the LNS search, towards satisfying the replaced constraints until very late. Our key observation is that entirely replacing a constraint is often overkill, as the propagator for the replaced constraint could have performed some propagation without causing backtracking. We propose the notion of a non-failing propagator, which is subsumed just before causing a backtrack. We show that, by only making a few changes to an existing CP solver, any propagator can be made non-failing without modifying its code. Experimental evaluation shows that non-failing propagators, when used in conjunction with penalties, can greatly improve LNS performance compared to just having penalties. This allows us to leverage the power of the many sophisticated propagators that already exist in CP solvers, in order to use LNS for solving hard satisfaction problems and for finding initial solutions to hard-to-satisfy optimisation problems.

Series
Lecture Notes in Computer Science, ISSN 1611-3349 ; 12333
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-422974 (URN)10.1007/978-3-030-58475-7_4 (DOI)978-3-030-58474-0 (ISBN)978-3-030-58475-7 (ISBN)
Conference
26th International Conference on Principles and Practice of Constraint Programming, Louvain-la-Neuve, Belgium, September 7 – September 11, 2020
Funder
Swedish Research Council, 2015-04910
Available from: 2020-10-19 Created: 2020-10-19 Last updated: 2021-03-03Bibliographically approved
Björdal, G., Flener, P., Pearson, J. & Stuckey, P. J. (2019). Exploring declarative local-search neighbourhoods with constraint programming. In: Thomas Schiex and Simon de Givry (Ed.), Principles and Practice of Constraint Programming: . Paper presented at 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019 (pp. 37-53). Switzerland: Springer, 11802
Open this publication in new window or tab >>Exploring declarative local-search neighbourhoods with constraint programming
2019 (English)In: Principles and Practice of Constraint Programming / [ed] Thomas Schiex and Simon de Givry, Switzerland: Springer, 2019, Vol. 11802, p. 37-53Conference paper, Published paper (Refereed)
Abstract [en]

Using constraint programming (CP) to explore a local-search neighbourhood was first tried in the mid 1990s. The advantage is that constraint propagation can quickly rule out uninteresting neighbours, sometimes greatly reducing the number actually probed. However, a CP model of the neighbourhood has to be handcrafted from the model of the problem: this can be difficult and tedious. That research direction appears abandoned since large-neighbourhood search (LNS) and constraint-based local search (CBLS) arose as alternatives that seem easier to use. Recently, the notion of declarative neighbourhood was added to the technology-independent modelling language MiniZinc, for use by any backend to MiniZinc, but currently only used by a CBLS backend. We demonstrate that declarative neighbourhoods are indeed technology-independent by using the old idea of CP-based neighbourhood exploration: we explain how to encode automatically a declarative neighbourhood into a CP model of the neighbourhood. This enables us to lift any CP solver into a local-search backend to MiniZinc. Our prototype is competitive with CP, CBLS, and LNS backends to MiniZinc.

Place, publisher, year, edition, pages
Switzerland: Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11802
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-396813 (URN)10.1007/978-3-030-30048-7_3 (DOI)000560404200003 ()978-3-030-30047-0 (ISBN)978-3-030-30048-7 (ISBN)
Conference
25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019
Funder
Swedish Research Council, 2015-04910
Available from: 2019-11-18 Created: 2019-11-18 Last updated: 2021-03-03Bibliographically approved
Björdal, G., Flener, P. & Pearson, J. (2019). Generating compound moves in local search by hybridisation with complete search. In: L.-M. Rousseau and K. Stergiou (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: . Paper presented at CPAIOR 2019, 4 – 7 June, Thessaloniki, Greece (pp. 95-111). Springer, 11494
Open this publication in new window or tab >>Generating compound moves in local search by hybridisation with complete search
2019 (English)In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research / [ed] L.-M. Rousseau and K. Stergiou, Springer, 2019, Vol. 11494, p. 95-111Conference paper, Published paper (Refereed)
Abstract [en]

A black-box local-search backend to a solving-technology-independent modelling language, such as MiniZinc, automatically infers from the structure of a declarative model for a satisfaction or optimisation problem a combination of a neighbourhood, heuristic, and meta-heuristic. These ingredients are then provided to a local-search solver, but are manually designed in a handcrafted local-search algorithm. However, such a backend can perform poorly due to model structure that is inappropriate for local search, for example when it considers moves modifying only variables that represent auxiliary information. Towards overcoming such inefficiency, we propose compound-move generation, an extension to local-search solvers that uses a complete-search solver in order to augment moves modifying non-auxiliary variables so that they also modify auxiliary ones. Since compound-move generation is intended to be applied to such models, we discuss how to identify them.

We present several refinements of compound-move generation and show its very positive impact on several third-party models. This helps reduce the unavoidable gap between black-box local search and local-search algorithms crafted by experts.

Place, publisher, year, edition, pages
Springer, 2019
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11494
National Category
Computer Sciences
Research subject
Computing Science
Identifiers
urn:nbn:se:uu:diva-396494 (URN)10.1007/978-3-030-19212-9_7 (DOI)000884721600007 ()978-3-030-19212-9 (ISBN)
Conference
CPAIOR 2019, 4 – 7 June, Thessaloniki, Greece
Funder
Swedish Research Council, 2015-04910
Available from: 2019-11-18 Created: 2019-11-18 Last updated: 2023-03-03Bibliographically approved
Björdal, G., Flener, P., Pearson, J., Stuckey, P. J. & Tack, G. (2018). Declarative local-search neighbourhoods in MiniZinc. In: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI): . Paper presented at 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), NOV 05-07, 2018, Volos, GREECE (pp. 98-105). IEEE Computer Society
Open this publication in new window or tab >>Declarative local-search neighbourhoods in MiniZinc
Show others...
2018 (English)In: PROCEEDINGS OF THE 2018 IEEE 30TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI), IEEE Computer Society, 2018, p. 98-105Conference paper, Published paper (Refereed)
Abstract [en]

The aim of solver-independent modelling is to create a model of a satisfaction or optimisation problem independent of a particular technology. This avoids early commitment to a solving technology and allows easy comparison of technologies. MiniZinc is a solver-independent modelling language, supported by CP, MIP, SAT, SMT, and constraint-based local search (CBLS) backends. Some technologies, in particular CP and CBLS, require not only a model but also a search strategy. While backends for these technologies offer default search strategies, it is often beneficial to include in a model a user-specified search strategy for a particular technology, especially if the strategy can encapsulate knowledge about the problem structure. This is complex since a local-search strategy (comprising a neighbourhood, a heuristic, and a meta-heuristic) is often tightly tied to the model. Hence we wish to use the same language for specifying the model and the local search. We show how to extend MiniZinc so that one can attach a fully declarative neighbourhood specification to a model, while maintaining the solver-independence of the language. We explain how to integrate a model-specific declarative neighbourhood with an existing CBLS backend for MiniZinc.

Place, publisher, year, edition, pages
IEEE Computer Society, 2018
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-368077 (URN)10.1109/ICTAI.2018.00025 (DOI)000457750200015 ()978-1-5386-7449-9 (ISBN)
Conference
30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), NOV 05-07, 2018, Volos, GREECE
Funder
Swedish Research Council, 2015-04910
Available from: 2018-12-17 Created: 2018-12-03 Last updated: 2021-03-03Bibliographically approved
Dubois, C., Grinchtein, O., Pearson, J. & Carlsson, M. (2018). Exploring properties of a telecommunication protocol with message delay using interactive theorem prover. In: Software Engineering and Formal Methods: . Paper presented at SEFM 2018, June 27–29, Toulouse, France (pp. 239-253). Springer
Open this publication in new window or tab >>Exploring properties of a telecommunication protocol with message delay using interactive theorem prover
2018 (English)In: Software Engineering and Formal Methods, Springer, 2018, p. 239-253Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10886
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-366393 (URN)10.1007/978-3-319-92970-5_15 (DOI)000445248600015 ()978-3-319-92969-9 (ISBN)
Conference
SEFM 2018, June 27–29, Toulouse, France
Available from: 2018-05-30 Created: 2018-11-21 Last updated: 2018-11-30Bibliographically approved
Francisco Rodríguez, M. A., Flener, P. & Pearson, J. (2017). Automatic generation of descriptions of time-series constraints. In: IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI): . Paper presented at IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston, MA, November 6–8, 2017 (pp. 102-109). IEEE Computer Society
Open this publication in new window or tab >>Automatic generation of descriptions of time-series constraints
2017 (English)In: IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, 2017, p. 102-109Conference paper, Published paper (Refereed)
Abstract [en]

Integer time series are often subject to constraints on the aggregation of the 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 valley widths. Many time-series constraints can be described by transducers. The output alphabet of such a transducer consists of symbols that denote the phases of identifying the maximal occurrences of a pattern. It was recently shown how to synthesise automatically a constraint propagator and a constraint checker from such a transducer, which however has to be designed manually from a pattern. Here we define a large class of patterns, present an algorithm for automatically generating a low-level transducer from such a high-level pattern, and prove it correct. This class covers all 20 patterns of the Time-Series Constraint Catalogue, which can now be automatically extended at will.

Place, publisher, year, edition, pages
IEEE Computer Society, 2017
Series
Proceedings-International Conference on Tools With Artificial Intelligence, ISSN 1082-3409
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-332145 (URN)10.1109/ICTAI.2017.00027 (DOI)000435294700016 ()978-1-5386-3876-7 (ISBN)
Conference
IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), Boston, MA, November 6–8, 2017
Funder
Swedish Research Council, 2012-4908Swedish Research Council, 2015-0491
Available from: 2018-06-07 Created: 2017-10-24 Last updated: 2019-08-28Bibliographically approved
Scott, J. D., Flener, P., Pearson, J. & Schulte, C. (2017). Design and implementation of bounded-length sequence variables. In: Integration of AI and OR Techniques in Constraint Programming: . Paper presented at CPAIOR 2017, June 5–8, Padua, Italy (pp. 51-67).
Open this publication in new window or tab >>Design and implementation of bounded-length sequence variables
2017 (English)In: Integration of AI and OR Techniques in Constraint Programming, 2017, p. 51-67Conference paper, Published paper (Refereed)
Abstract [en]

We present the design and implementation of bounded length sequence (BLS) variables for a CP solver. The domain of a BLS variable is represented as the combination of a set of candidate lengths and a sequence of sets of candidate characters. We show how this representation, together with requirements imposed by propagators, affects the implementation of BLS variables for a copying CP solver, most importantly the closely related decisions of data structure, domain restriction operations, and propagation events. The resulting implementation outperforms traditional bounded-length string representations for CP solvers, which use a fixed-length array of candidate characters and a padding symbol.

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10335
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-334654 (URN)10.1007/978-3-319-59776-8_5 (DOI)000434086200005 ()978-3-319-59775-1 (ISBN)
Conference
CPAIOR 2017, June 5–8, Padua, Italy
Funder
Swedish Research Council, 2015-4910
Available from: 2017-05-31 Created: 2017-11-25 Last updated: 2018-11-12Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-0084-8891

Search in DiVA

Show all publications