Logo: to the web site of Uppsala University

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.

The generation of a robot program can be seen as a collection of sub-problems, where many combinations of some of these sub-problems are well studied. The performance of a robot program is strongly conditioned by the location of the tasks. However, the scope of previous methods does not include workspace layout design, likely missing high-quality solutions. In industrial applications, designing robot workspace layout is part of the commissioning. We broaden the scope and show how to model a dual-arm multi-tool robot assembly problem. Our model includes more robot programming sub-problems than previous methods, as well as workspace layout design. We propose a constraint programming formulation in MiniZinc that includes elements from scheduling and routing, extended with variable task locations. We evaluate the model on realistic assembly problems and workspaces, utilizing the dual-arm YuMi robot from ABB Ltd. We also evaluate redundant constraints and various formulations for avoiding arm-to-arm collisions. The best model variant quickly finds high-quality solutions for all problem instances. This demonstrates the potential of our approach as a valuable tool for a robot programmer.

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.

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.

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.

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.

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.

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.

Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.