Fully funded 3-year PhD contract at IMT Nantes (France)

[Albrecht Zimmermann]

Learning invariant maps in the context of combinatorial objects

Invariants linking several characteristics of a combinatorial object (a permutation, a tree, a forest, a digraph, a time series) are a key component of the effective resolution of combinatorial problems using constraint programming or linear programming techniques. While these invariants are often obtained manually for a specific problem, some approaches propose to generate conjectures (and possibly prove them) for certain problem families (see for example the work by Aouchiche and Hansen [1] on graph invariants or the work by Arafailova and Beldiceanu on time series [2,3]), or on several domains (see the work by Fajtlowicz, Larson and Cleemput [4,5,6] on the Dalmatian heuristics for generating conjectures). But currently, all approaches acquire invariants that are independent of each other. This thesis will focus on explicitly highlights the relationships between invariants to learn "invariant maps" : an invariant map can be seen as a digraph in which a vertex is an invariant linking several characteristics, and an arc corresponds to the relationship between two given invariants (showing how an invariant is derived from a more general invariant).

The systematic search for such maps has the following key advantages:

[Theoretical advantage : using learning to forge a theoretical understanding of invariants] The aim is to use learning to develop a theoretical understanding of the relationships between invariants that will be acquired. The approach will be generic in order to be applicable to different families of combinatorial objects. A map of invariants provides a global understanding of a set of invariants whose relationships are captured. In the longer term, it may allow one to identify structural properties of combinatorial objects and their characteristics for which such maps can be constructed.

[Practical advantage for learning invariants] A map can be built in a progressive way (i.e. "bootstrapped") by relying on invariants that mention only a few characteristics that are easier to find, and then seeking to extend it with new invariants that mention more characteristics that must be related to the invariants already learned (they must generalise several invariants already learned).

[Operational advantage for the use of invariants in problem solving] Finally, from a practical point of view, if the relationships between the invariants are well formalised, a map can be both represented in a compact way and describe a large number of invariants. This would allow one, for a given problem, to easily extract the relevant set of invariants to accelerate its resolution.

Methodology used

The following methodology will be used :

A. Studies of existing methods generating invariants in isolation [1,2,4,5].

B. Selection of three or four families of combinatorial objects and 5 to 10 characteristics for each family, based on our experience in generating invariants on graphs [7], time series [2,3] and some global constraints [8].

C. Systematic generation of instances of these objects on which the selected characteristics are evaluated.

D. Generation of sharp conjectures linking two given characteristics, then sharp conjectures generalising the previous conjectures (by introducing an additional characteristic), and so on. A set of hypotheses will be made on the bias characterising the formulas underlying these invariants.

E. Manual search for structural properties on the generated maps and compositional proof techniques (where each invariant of a map is not proven independently from the other invariants).

F. Evaluation of the relevance of maps found on energy or health problems involving constraints on sequences and/or constraints on graphs.

[1] See in DBLP the collection of journal papers by Mustapha Aouchiche, Pierre Hansen between 2001 and 2018 on the generation of conjectures on graphs entitled "Variable neighbborhood search for extremal graphs ...".

[2] Ekaterina Arafailova, Nicolas Beldiceanu, Helmut Simonis. Generating linear invariants for a conjunction of automata constraints, 23rd International Conference, CP 2017, LNCS vol 10416, p. 21-37, 2017.

[3] Ekaterina Arafailova, Nicolas Beldiceanu, Helmut Simonis. Synthesising a database of parameterised linear and non linear invariants for time-series constraints, (https://arxiv.org/abs/1901.09793), 2019.

[4] Siemion Fajlowicz. On conjectures of Graffiti. Proceedings of the first Japan conference on graph theory and applications (Hakone, 1986), vol. 72, p. 113-118, 1988.

[5] Craig E. Larson, Nico Van Cleemput. Automated conjecturing I : Fajtlowicz’s Dalmatian heuristic revisited. Artificial Intelligence, vol. 231, p. 17-38, 2016.

[6] N. Bushaw, Craig E. Larson, Nico Van Cleemput. Automated conjecturing VII : the graph brain project & big mathematics, (https://arxiv.org/abs/1801.01814), 2018.

[7] Nicolas Beldiceanu, Mats Carlsson, Jean-Xavier Rampon, Charlotte Truchet. Graph invariants as necessary conditions for global constraints. 11th International Conference, CP 2005, LNCS vol. 3709, p. 92-106, 2005.

[8] Christian Bessière, Emmanuel Hebrard, George Katsirelos, Zeynep Kiziltan, Emilie Picard-Cantin, Claude-Guy Quimper, Tobby Walsh. The Balance constraint family. 11th International Conference, CP 2014, LNCS vol. 8656, p. 174-189, 2014.

Contact: Nicolas Beldiceanu (nicolas.beldiceanu@imt-atlantique.fr)