Pierre Flener

JAIR Journal 2025 Journal Article

Invariant Graph Propagation in Constraint-Based Local Search

• Frej Knutar Lewander
• Pierre Flener
• Justin Pearson

In constraint-based local search, an assignment to the search variables is improved upon by an iterative procedure that replaces the current assignment with a similar assignment. The latter is selected by a heuristic that assesses the qualities of a subset of all similar assignments, where the quality of such assignments is determined via a process called invariant graph propagation. Since, typically, many similar assignments are considered in every iteration, invariant graph propagation must be as efficient as possible. Since invariant graph propagation is independent of the selection heuristic, any comparison between different invariant graph propagation styles under different selection heuristics can be misleading. In this paper, we describe and compare both theoretically and empirically the throughput of several invariant graph propagation styles, and give criteria when one style or another is to be used.

AIJ Journal 2016 Journal Article

A parametric propagator for pairs of Sum constraints with a discrete convexity property

• Jean-Noël Monette
• Nicolas Beldiceanu
• Pierre Flener
• Justin Pearson

We introduce a propagator for pairs of Sum constraints, where the expressions in the sums respect a form of convexity. This propagator is parametric and can be instantiated for various concrete pairs, including Deviation, Spread, and the conjunction of Linear ≤ and Among. We show that despite its generality, our propagator is competitive in theory and practice with state-of-the-art propagators.

LOPSTR Conference 2016 Conference Paper

MiniZinc with Strings

• Roberto Amadini
• Pierre Flener
• Justin Pearson
• Joseph D. Scott
• Peter J. Stuckey
• Guido Tack

Abstract 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.

AAAI Conference 2014 Conference Paper

A Propagator Design Framework for Constraints over Sequences

• Jean-Noel Monette
• Pierre Flener
• Justin Pearson

Constraints over variable sequences are ubiquitous and many of their propagators have been inspired by dynamic programming (DP). We propose a conceptual framework for designing such propagators: pruning rules, in a functional notation, are refined upon the application of transformation operators to a DP-style formulation of a constraint; a representation of the (tuple) variable domains is picked; and a control of the pruning rules is picked.

AAAI Conference 2014 Conference Paper

Propagating Regular Counting Constraints

• Nicolas Beldiceanu
• Pierre Flener
• Justin Pearson
• Pascal Van Hentenryck

Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. This led to general modelling techniques and generic propagators, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for at-most and at-least regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be increased by transitions. We also show that the satisfaction of exact regular counting constraints is NP-hard and that an incomplete propagator for exact regular counting constraints is faster and provides more pruning than the existing propagator from (Beldiceanu, Carlsson, and Petit 2004). Finally, by avoiding the unrolling of the cDFA used by COSTREGULAR, the space complexity reduces from O(n · |Σ| · |Q|) to O(n · (|Σ| + |Q|)), where Σ is the alphabet and Q the state set of the cDFA.

KER Journal 2012 Journal Article

Constraint programming for air traffic management: a survey

• Cyril Allignol
• Nicolas Barnier
• Pierre Flener
• Justin Pearson

Abstract Air traffic management (ATM) under its current paradigm is reaching its structural limits considering the continuously growing demand. The need for a decrease in traffic workload opens numerous problems for optimization, from capacity balancing to conflict solving, using many different degrees of freedom, such as re-routing, flight-level changes, or ground-holding schemes. These problems are usually of a large dimension (there are 30 000 daily flights in Europe in the year 2012) and highly combinatorial, hence challenging for current problem solving technologies. We give brief tutorials on ATM and constraint programming (CP), and survey the literature on deploying CP technology for modelling and solving combinatorial problems that occur in an ATM context.

KER Journal 2012 Journal Article

Constraint programming for air traffic management: preface

• Pierre Flener
• Justin Pearson
• Marc Bourgois

IS Journal 2009 Journal Article

Constraint Programming in Sweden

• Pierre Flener
• Mats Carlsson
• Christian Schulte

Many important problems must be solved by intelligent search for example, problems in scheduling, rostering, configuration, facility location, biology, finance, circuit layout, and hard/software specification checking. Constraint programming (CP) is rapidly becoming the method of choice in some areas, such as scheduling and configuration. A major difficulty lies in accelerating such (optimal) choices. This ranges from problem modeling to actual problem solving.

ECAI Conference 2008 Conference Paper

Solving Necklace Constraint Problems

• Pierre Flener
• Justin Pearson

Some constraint problems have a combinatorial structure where the constraints allow the sequence of variables to be rotated (necklaces), if not also the domain values to be permuted (unlabelled necklaces), without getting an essentially different solution. We bring together the fields of combinatorial enumeration, where efficient algorithms have been designed for (special cases of) some of these combinatorial objects, and constraint programming, where the requisite symmetry breaking has at best been done statically so far. We design the first search procedure and identify the first symmetry-breaking constraints for the general case of unlabelled necklaces. Further, we compare dynamic and static symmetry breaking on real-life scheduling problems featuring (unlabelled) necklaces.

LOPSTR Conference 2003 Conference Paper

Introducing esra, a Relational Language for Modelling Combinatorial Problems

• Pierre Flener
• Justin Pearson
• Magnus Ågren 0002

Abstract Current-generation constraint programming languages are considered by many, especially in industry, to be too low-level, difficult, and large. We argue that solver-independent, high-level relational constraint modelling leads to a simpler and smaller language, to more concise, intuitive, and analysable models, as well as to more efficient and effective model formulation, maintenance, reformulation, and verification. All this can be achieved without sacrificing the possibility of efficient solving, so that even time-pressed or less competent modellers can be well assisted. Towards this, we propose the esra relational constraint modelling language, showcase its elegance on some well-known problems, and outline a compilation philosophy for such languages.

LOPSTR Conference 1998 Conference Paper

Generalised Logic Program Transformation Schemas

• Halime Büyükyildiz
• Pierre Flener

Abstract Schema-based logic program transformation has proven to be an effective technique for the optimisation of programs. This paper results from the research that began by investigating the suggestions in [ 11 ] to construct a more general database of transformation schemas for optimising logic programs at the declarative level. The proposed transformation schemas fully automate accumulator introduction (also known as descending computational generalisation), tupling generalisation (a special case of structural generalisation), and duality laws (which are extensions to relational programming of the first duality law of the fold operators in functional programming). The schemas are proven correct. A prototype schema-based transformation system is evaluated.

LOPSTR Conference 1998 Conference Paper

On Correct Program Schemas

• Pierre Flener
• Kung-Kiu Lau
• Mario Ornaghi

Abstract We present our work on the representation and correctness of program schemas, in the context of logic program synthesis. Whereas most researchers represent schemas purely syntactically as higher-order expressions, we shall express a schema as an open first-order theory that axiomatises a problem domain, called a specification framework, containing an open program that represents the template of the schema. We will show that using our approach we can define a meaningful notion of correctness for schemas, viz. that correct program schemas can be expressed as parametric specification frameworks containing templates that are steadfast, i. e. programs that are always correct provided their open relations are computed correctly.

LOPSTR Conference 1996 Conference Paper

Logic Program Transformation through Generalization Schemata

• Pierre Flener
• Yves Deville

Abstract Both generalization techniques are very suitable for mechanical transformation: all operators of the generalized programs are operators of the initial programs. Given a divide-and-conquer program, a mere inspection of the properties of its solving, processing, and composition operators thus allows the detection of which kinds of generalization are possible, and to which optimizations they would lead. The eureka discoveries are compiled away, and the transformations can be completely automated.

LOPSTR Conference 1994 Conference Paper

On the Use of Inductive Reasoning in Program Synthesis: Prejudice and Prospects

• Pierre Flener
• Lubos Popelínský

Abstract In this position paper, we give a critical analysis of the deductive and inductive approaches to program synthesis, and of the current research in these fields. From the shortcomings of these approaches and works, we identify future research directions for these fields, as well as a need for cooperation and cross-fertilization between them.

LOPSTR Conference 1992 Conference Paper

Towards Stepwise, Schema-guided Synthesis of Logic Programms

• Pierre Flener
• Yves Deville

Abstract We present a general strategy for stepwise, sound and progressive synthesis of logic programs from specifications by examples and properties. We particularize this to schema-guided synthesis, and state a generic synthesis theorem. We justify some design choices for the development of a particular synthesis mechanism that is guided by a Divide-and-Conquer schema, is inductive and deductive, is interactive, and features a non-incremental presentation of examples. Some crucial steps of this mechanism are explained, and illustrated by a sample synthesis. We draw some conclusions on our results so far, state some related work, and outline future research directions.

LOPSTR Conference 1990 Conference Paper

Schema-Guided Synthesis of CLP Programs

• Hamza Zidoum
• Pierre Flener
• Brahim Hnich

Abstract This work is inspired by D. R. Smith’s research on synthesising global search (GS) programs (in the Refine language) from first-order logic specifications (also in Refine) [ 8, 9, 10 ]. We concentrate on synthesising constraint logic programs (CLP) [ 6 ] instead. We thus only have to synthesise code that (incrementally) poses the constraints, because the actual constraint propagation and pruning are performed by the CLP system. We here only tackle the family of decision assignment problems; the families of optimisation assignment problems, decision permutation problems, and optimisation permutation problems are covered in [ 4 ].