Emeric Gioan

A survey on The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids

The active bijection maps any directed graph, resp. signed hyperplane arrangement or oriented matroid, on a linearly ordered edge set, resp. ground set, onto one of its spanning trees, resp. bases. It relates all spanning trees to all orientations of a graph, all bases to all reorientations of an hyperplane arrangement or, more generally, an oriented matroid. It preserves activities: for bases in the sense of Tutte, for orientations in the sense of Las Vergnas, yielding a bijective interpretation of the equality of two expressions of the Tutte polynomial. It can be mathematically defined in a short way, and can be built, characterized, particularized, or refined in several ways.

[...]= equivalent required dual formulation

The mapping α yields an activity preserving bijection:

-between all activity classes of orientations and all spanning trees of G , -and between all orientations and all subsets of G .

The active bijection in graphs Matroid: incidence properties and flat intersection lattice Oriented matroid: convexity properties and face relative positions

7/ 61
Directed graph -→ associated arrangement Other coefficients of t M can also be interpreted a similar way...

Activities of orientations

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )).
An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle)

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )).
An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle)

An element of E is dual-active if it is the smallest of a positive cocircuit of M (or: ... the smallest edge of a directed cocycle)

15/ 61

Activities of orientations

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )).
An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle)

An element of E is dual-active if it is the smallest of a positive cocircuit of M (or: ... the smallest edge of a directed cocycle)

Theorem [Las Vergnas 1984] t(M; x, y ) = i,j o i,j 2 i+j x i y j
where o i,j is the number of reorientations of M with i dual-active elements and j active elements.

15/ 61

Activities of orientations

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )
). An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle) An element of E is dual-active if it is the smallest of a positive cocircuit of M (or: ... the smallest edge of a directed cocycle)

Theorem [Las Vergnas 1984] t(M; x, y ) = i,j o i,j 2 i+j x i y j where o i,j is the number of reorientations of M with i dual-active elements and j active elements.

Related classical results

o 1,0 = # bounded regions = #bipolar orientations w.r.t. e ∈ E (with given orientation for e) [Crapo 1969, Zaslavsky 1975, Las Vergnas 1977] 15/ 61

Activities of orientations

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )).
An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle) An element of E is dual-active if it is the smallest of a positive cocircuit of M (or: ... the smallest edge of a directed cocycle)

Theorem [Las Vergnas 1984] t(M; x, y ) = i,j o i,j 2 i+j x i y j
where o i,j is the number of reorientations of M with i dual-active elements and j active elements.

Related classical results

t(M; 2, 0) = # regions = # acyclic orientations [Winder 1966, Stanley 1973, Las Vergnas 1977] Activities of orientations

Let M be an oriented matroid on a linearly ordered set E (or a directed graph

- → G = (V , E )).
An element of E is active if it is the smallest of a positive circuit of M (or: ... the smallest edge of a directed cycle) An element of E is dual-active if it is the smallest of a positive cocircuit of M (or: ... the smallest edge of a directed cocycle)

Theorem [Las Vergnas 1984] t(M; x, y ) = i,j o i,j 2 i+j x i y j
where o i,j is the number of reorientations of M with i dual-active elements and j active elements.

Related classical results

t(M; 0, 2) = # dual regions = # totally cyclic orientations (strongly connected orientations)

t(K 4 ; x, y ) = 8.( x 2 ) 3 + +12.( x 2 ) 2 + 4.( x 2 ) + . . . t(K 4 ; 2, 0) = 24 16/ 61

Activities of bases (spanning trees)

Let M be a matroid on a linearly ordered set E (or a graph G = (V , E )).

B a basis (spanning tree) of M e ∈ E \ B is externally active w.r.t. B if it is the smallest element of C e = C (B; e), the unique circuit (cycle) contained in B ∪ {e} b ∈ B is internally active w.r.t. B if it is the smallest element of C * b = C * (B; b), the unique cocircuit (cocycle) contained in (E \ B) ∪ {b} Theorem [Tutte 1954 & Crapo 1969] t(M; x, y ) = i,j b i,j x i y j où b i,j
is the number of bases of M with i internally active elements and j externally active elements.

The active bijection in oriented matroids Tutte polynomial t(M; x, y ) of an ordered oriented matroid M Theorem. [Tutte 1954& Crapo 1969] t(M; x, y ) = i,j b i,j x i y j où b i,j = number of bases with activities (i, j)

Theorem. [Las Vergnas 1984]

t(M; x, y ) = i,j o i,j
x 2 i y 2 j where o i,j = number of reorientations with activities (i, j)

o i,j = 2 i+j b i,j
The active bijection is a canonical underlying bijection...

The fully optimal basis

(The fully optimal spanning tree)

of a bounded region The mapping α is a bijection between (pairs of opposite) bounded regions of M and (1, 0)-active bases of M.

C * 1 2 C * 3 4 5 C * 6 1 + C 2 + - - 3 + C 4 + - - - C 5 + -+ 6 +
(fundamental tableau of the basis)

24/ 61

Usual Linear Programming Optimal Bases (simplex criterion) Only takes the first column and first row into account.

25/ 61

The Fully Optimal Basis In the real case: the active bijection is the unique bijection associating (1, 0)-active flags and bounded regions with the adjacency property. In the graphical case: multiobjective LP ∼ a cocycle weight function In the general case: we need the dual adjacency property, and it implies the bijection.

Duality for bounded regions (bipolar orientations) (means that the active bijection is compatible with the above bijections) 28/ 61

Bounded region M w.r.t. e ←-------→ canonical bijection Dual-bounded region M * o * (M) = 1, o(M) = 0 o * (M * ) = 0, o(M * ) = 1 idem ←-------→ canonical bijection Dual-bounded region -e M o * (-e M) = 0, o(-e M) =

Decompositions of activities and Tutte polynomial in terms of beta invariants of minors

Active bijection: inductive decomposition construction

For every oriented matroid M on a linearly ordered set E , α(M) defined by the three following properties:

α(M) is the fully optimal basis of M if it is a bounded region α(M * ) = E \ α(M) α(M) = α(M/F ) α(M(F ))
where F is the union of all positive circuits of M whose smallest element is the greatest possible active element of M Lemma. If F = ∅, then M(F ) is dual-bounded, and M/F has one less active element than M.

30/ 61

Active bijection: inductive decomposition construction For every oriented matroid M on a linearly ordered set E , α(M) defined by the three following properties:

α(M) is the fully optimal basis of M if it is a bounded region α(M * ) = E \ α(M) α(M) = α(M/F ) α(M(F ))
where F is the complementary of the union of all positive cocircuits of M whose smallest element is the greatest possible dual-active element of M;

(equivalent dual formulation)

Lemma. If F = ∅, then M/F is bounded, and M(F ) has one less dual-active element than M.

Active bijection: direct decomposition construction

Let M be an ordered oriented matroid on E with ι = o * (M) dual-active elements a 1 < ... < a ι and ε = o(M) active elements a 1 < ... < a ε . The active decomposing sequence of M is

∅ = F ε ⊂ ... ⊂ F 0 = F c = F 0 ⊂ ... ⊂ F ι = E It corresponds to the active partition of M: E = F ε-1 \ F ε . . . F 0 \ F 1 F 1 \ F 0 . . . F ι \ F ι-1 31/ 61
Active bijection: direct decomposition construction

Let M be an ordered oriented matroid on E with ι = o * (M) dual-active elements a 1 < ... < a ι and ε = o(M) active elements a 1 < ... < a ε .

The active decomposing sequence of M is

∅ = F ε ⊂ ... ⊂ F 0 = F c = F 0 ⊂ ... ⊂ F ι = E
It corresponds to the active partition of M:

E = F ε-1 \ F ε . . . F 0 \ F 1 F 1 \ F 0 . . . F ι \ F ι-1 For 0 ≤ k ≤ ε -1, we have F k = D positive circuit Min D>a k D.
Dually, for 0 ≤ k ≤ ι -1, we have

F k = E \ D positive cocircuit Min D>a k D.
F c is the union of all positive circuits of M (directed cycles), and E \ F c is the union of all positive cocircuits (directed cocycles). F c is a cyclic flat.

31/ 61

Active bijection: direct decomposition construction

Let M be an ordered oriented matroid on E with ι = o * (M) dual-active elements a 1 < ... < a ι and ε = o(M) active elements a 1 < ... < a ε .

The active decomposing sequence of M is

∅ = F ε ⊂ ... ⊂ F 0 = F c = F 0 ⊂ ... ⊂ F ι = E
It corresponds to the active partition of M:

E = F ε-1 \ F ε . . . F 0 \ F 1 F 1 \ F 0 . . . F ι \ F ι-1 for 1 ≤ k ≤ ι, the minor M(F k )/F k-1 is dual-bounded (cyclic-bipolar) for 1 ≤ k ≤ ε, the minor M(F k-1 )/F k is bounded (bipolar)
Direct definition of α:

α(M) = 1≤k≤ι α(M(F k )/F k-1 ) 1≤k≤ε α(M(F k-1 )/F k ) 32/ 61
α( - → G ) = 134 Activity class: - → G , -123 - → G , -456 - → G , -123456 - → G .

33/ 61

Reorientation activity classes of ordered oriented matroids Let M be a matroid on a linearly ordered set E .

{bases of M} = ∅=F ε ⊂...⊂F 0 =Fc Fc =F 0 ⊂...⊂Fι=E decomposing sequence of M {B 1 ... B ε B 1 ... B ι | for all 1 ≤ k ≤ ε, B k base of M(F k-1 )/F k with ι(B k ) = 0 and ε(B k ) = 1, for all 1 ≤ k ≤ ι, B k base of M(F k )/F k-1 with ι(B k ) = 1 and ε(B k ) = 0} Then B = B 1 ... B ε B 1 ... B ι it the active partition of B and Int(B) = ∪ 1≤k≤ι min(F k \ F k-1 ) = ∪ 1≤k≤ι Int(B k ), Ext(B) = ∪ 1≤k≤ε min(F k-1 \ F k ) = ∪ 1≤k≤ε Ext(B k ).

Theorem: Tutte polynomial in terms of β invariants of minors

Let M be a matroid on a linearly ordered set E .

t(M; x, y ) = 1≤k≤ι β M(F k )/F k-1 1≤k≤ε β M(F k-1 )/F k x ι y ε where β (M) = β(M) if |E | > 1, β (isthmus) = 0, and β (loop) = 1
and where the sum can be equally:

either over all decomposing sequences of M or over all abstract decomposing sequences of E

∅ = F ε ⊂ ... ⊂ F 0 = F c = F 0 ⊂ ... ⊂ F ι = E 41/ 61
Classical results refined by this formula

Theorem. [Tutte 1954] t(M; x, y ) = i,j b i,j x i y j
where b i,j = # (i, j)-active bases

Theorem. [Las Vergnas 1984] t(M; x, y

) = i,j o i,j ( x 2 ) i ( y 2 ) j
where o i,j = # (i, j)-active reorientations

Theorem. [Etienne & Las Vergnas 1998, Kook Reiner & Stanton 1999] t(M; x, y ) = t(M/F ; x, 0) t(M(F ); 0, y )

where the sum can be equally either over all subsets F of E , or over all cyclic flats F of M.

42/ 61

Further results

43/ 61

Refined bijection between (re)orientations and subsets

Let M be an (oriented) matroid on a linearly ordered set E .

Partition of 2 E in terms of reorientation activity classes

2 E = activity classes of M (one -A M chosen in each class) 2 o(-A M)+o * (-A M) reorientations

Active bijection

One activity class ←→ one basis ←→ one interval (2 i+j elements)

(2 i+j elements)

44/ 61

Refined bijection between (re)orientations and subsets

Active bijection

One activity class ←→ one basis ←→ one interval (2 i+j elements)

(2 i+j elements)

The activity class of -A M and the matroid basis interval of B = α(-A M) are isomorphic boolean lattices.

Refined bijection between (re)orientations and subsets

Refined active bijection

For A ⊆ E and B = α(-A M), set

α ∅ M (A) = B \ (A ∩ Int(B)) ∪ (A ∩ Ext(B))
Theorem α ∅ M is a bijection between 2 E (reorientations) and 2 E (subsets) restricted to acyclic reorientations, α ∅ M is a bijection between regions (acyclic orientations) and no-broken-circuit subsets (i.e. subsets of bases with external activity zero) it preserves activities, active partitions, and also some four-variable refined activities (that take into acount the positions in the boolean lattices)

Refined bijection between (re)orientations and subsets

Refined active bijection

For A ⊆ E and B = α(-A M), set α ∅ M (A) = B \ (A ∩ Int(B)) ∪ (A ∩ Ext(B))
Theorem α ∅ M is a bijection between 2 E (reorientations) and 2 E (subsets) restricted to acyclic reorientations, α ∅ M is a bijection between regions (acyclic orientations) and no-broken-circuit subsets (i.e. subsets of bases with external activity zero) it preserves activities, active partitions, and also some four-variable refined activities (that take into acount the positions in the boolean lattices) Remark. α ∅ M depends on M and applies to A (on the contrary with α). The ∅ symbol is a parameter that can be changed to get other similar refined active bijections, with other boolean lattice bijections. (2)

1 5

(2)

1 C

(2) 1 6

(2) 1 9

(2) 1 7

(2) 1 A

(2) 1 B

(2) 1 8

(2)

1 (24) 1 D (4)

13 (4) 12 (4) 124 128 Allows a construction in nested "fibers" dimension by dimension, that fits well with the deletion/contraction construction...

Signed permutations

Regions of the hyperoctahedral arrangement ∼ Signed permutations No-broken-circuit base subsets ∼ edge-signed increasing forests Active bijection between signed permutations and edge-signed increasing forests , Vol. 30 (8), pp. 1868, Vol. 30 (8), pp. -1886, Vol. 30 (8), pp. (2009) )

(it is supersolvable) ∼ Cube symmetries ∼ Coxeter group B n 1 _ 1 1 _ 2 2 _ 2 12 2 _ 3 1 _ 3 3 _ 3 13 23 1 2 _ 2 3 _ 3 3 _ 21 2 _ 31 _ 213 _ 21 _ 3 _ 2 _ 31 _ 3 _ 21 31 _ 2 13 _ 2 1 _ 23 1 _ 2 _ 3 1 _ 3 _ 2 _ 31 _ 2
1 2 3 123 _ 1 _ 2 _ 3 1 2 3 132 _ 1 _ 3 _ 2 1 2 3 213 2 _ 1 _ 3 _ 213 _ 2 _ 1 _ 3 1 2 3 231 23 _ 1 _ 2 _ 31 _ 2 _ 3 _ 1 1 2 3 312 3 _ 1 _ 2 _ 312 _ 3 _ 1 _ 2 1 2 3 321 32 _ 1 3 _ 21 3 _ 2 _ 1 _ 321 _ 32 _ 1 _ 3 _ 21 _ 3 _ 2 _ 1 1 2 3 12 _ 3 _ 1 _ 23 1 _ 23 _ _ 1 2 3 1 _ 2 _ 3 _ 123 1 2 3 13 _ 2 _ 1 _ 32 1 2 3 1 _ 32 _ 13 _ 2 1 2 3 1 _ 3 _ 2 _ 132 1 2 3 21 _ 3 2 _ 13 _ 21 _ 3 _ 2 _ 13 1 2 3 2 _ 31 2 _ 3 _ 1 _ 23 _ 1 _ 231 1 2 3 31 _ 2 3 _ 12 _ 31 _ 2 _ 3 _ 12 56/ 61

For

  the unique (fully optimal) spanning tree B of G such that: for all b ∈ E \ min(E ), the signs of b and min(C * (B; b)) are opposite in C * (B; b); for all e ∈ B, the signs of e and min(C (B; e)) are opposite in C (B; e). α(M * ) = E \ α(M) If -→ G is strongly connected and min(E ) is contained in every directed cycle, then... )) where F can be the [complementary of the] union of all directed [co]cycles of -→ G whose smallest element is the greatest possible smallest element of a directed [co]cycle of -

  ij -→ hyperplane with equation v j -v i = 0 spanning tree -→ basis orientation of edge ij -→ half-space v j -v i >0 directed cut -→ vertex of the region (positive cocircuit) cut -→ vertex (cocircuit) acyclic orientation -→ region strongly connected orientation -→ region of the dual arrangement Duality Every oriented matroid M has a dual M * . circuits of M = cocircuits of M * cocircuits of M = circuits of M * acyclic orientations of M = totally cyclic orientations of M * (or regions) (or dual regions) (or strongly connected orientations) bases of M = complementary of bases of M * In the realizable case: duality ∼ orthogonality In the graphical case: duality = cycles/cocycles duality (extends planar graph duality) cocircuits) are signed subsets satisfying simple combinatorial axioms... (There are about 20 known equivalent combinatorial axiomatics!) Topological representation theorem [Folkman & Lawrence 1978] Oriented matroids on E ∼ Signed pseudosphere arrangements (S e ) e∈E up to homeomorphism .r.t. p = 1:-→ bounded regions w.r.t. p = 1: acyclic orientations regions that do not touch p = 1 with unique source and unique sink extremities of p = 1 13/ 61The β invariant M underlying matroid β(M) = # bounded regions w.r.t. e (on one side of e) β(M) = # bipolar orientations w.r.t. e (for a given orientation of e) β(M) does not depend on e: it is an invariant β(M) = t 1,0 (M) coefficient of x (or y ) of the Tutte polynomial t M (x, y ) of M β(M) = # acyclic (re)orientations such that e belongs to every positive cocircuit (directed cocycle)

  Consider the smallest element of each cocircuit They correspond to the sequence of nested faces induced by the minimal basis: 1 ∩ 2 ⊂ 1 The grey region (digraph) has dual-active elements: 124Dual activity of a region (or an acyclic orientation)

(

  of a bipolar orientation) E = e 1 < ... < e n We look for a bijection between bounded regions -A M w.r.t. e 1 o * (-A M) = 1 and o(-A M) = 0 and (1,0)-active bases B of M ι(B) = 1 and ε(B) = 0 Fully Optimal Basis (in an oriented matroid) M an oriented matroid on a linearly ordered set E = e 1 < ... < e n B ⊆ E a basis of M C e = fundamental circuit of e ∈ B w.r.t. B = unique circuit in B ∪ e C * b = fundamental cocircuit of b ∈ B w.r.t. B = unique cocircuit in (E \ B) ∪ b The basis B is fully optimal if b and min C * b have opposite signs in C * b for all b ∈ B \ e 1 e and min C e have opposite signs in C e for all e ∈ E \ B Remark if M has a fully optimal basis B then M is bounded w.r.t. e 1 and B is (1, 0)-active unique fully optimal basis denoted α(M)

  Takes all columns and rows into account. Two elaborations on linear programming: -multiobjective programming: unique optimal vertex -flag programming: unique sequence of nested faces (induction)

  Strong duality property (refines LP duality): α(e M) = α(M) \ {e} ∪ {e } for M bounded w.r.t. e, where E = e < e < . . ..

  Activity class of M: the set of 2 o(M)+o * (M) reorientations of M obtained by reorienting independently the o(M) + o * (M) parts of the active partition of M (all its elements have same active partition) They are interesting on their own: Activity classes form a partition of the set 2 E of reorientations of M Refine the acyclic / totally cyclic usual decomposition Describe the intersections of regions w.r.t. a given (minimal) flag Wide generalization of components of acyclic orientations of graphs defined on particular linear orderings of the vertices, as related to Non-commutative monoids [Cartier & Foata 1969] Heaps of pieces [Viennot 1986] Acyclic orientations and the chromatic polynomial [Lass 2001] There is one and only one unique sink acyclic orientation in each activity class of acyclic orientation of a graph, as related to t(G ; 1, 0) = #acyclic orientations of G with unique sink [Zaslavsky 1975, Greene & Zaslavsky 1983, Gebhard & Sagan 2000] is a basis of M active (resp. dual-active) elements of M are externally (resp. internally) active elements of α(M) more precisely, α also preserves active partitions (they exist for bases too and ensure that α(M) is a basis) the basis α(M) is also associated with the 2 o(M)+o * (M) reorientations in the activity class of M α is a bijection between all activity classes of reorientations of M and all bases of M.Active bijection between region activity classes and internal bases

  obtained by active partition reorienting Partition of 2 E in terms of matroid basis activity intervals [Crapo 1969, Dawson 1981, ...] 2 E = B basis of M B \ Int(B), B ∪ Ext(B)

  Active bijection between regions and no-broken-circuit subsets (acyclic restriction of the refined active bijection w.r.t. the grey region)

  Permutations (acyclic complete graph case) Regions of the braid arrangement ∼ Permutations (it is supersolvable) ∼ Simplex symmetries ∼ Coxeter group A n ∼ Acyclic orientations of K n+1 It is equal to a classical bijection! 58/ 61 oriented matroids activity classes of reorientations bases act. cl. of acyclic reorientations bases B with ε(B) = 0 act. cl. of totally cyclic reor. bases B with ι(B) = 0 bounded acyclic reorientations bases B with ι(B) = 1 and ε(B) = 0 reorientations subsets acyclic reorientations no-broken-circuit subsets totally cyclic reorientations supsets of bases B with ι(B) = 0 hyperplane arrangements reorientations ∼ signatures bases ∼ simplices acyclic reorientations ∼ regions graphs reorientations ∼ orientations bases ∼ spanning trees unique sink acyclic orientations spanning trees B with ε(B) = 0 bipolar orientations sp. trees B with ι(B) = 1 and ε(B) = 0 source-sink reversed bipolar orientations sp. trees B with ι(B) = 0 and ε(B) = 1 uniform oriented matroids bounded regions linear programming optimal vertices braid arrangement or complete graph or Coxeter arrangement A n permutations increasing trees hyperoctahedral arrangement or Coxeter arrangement B n signed permutations signed increasing trees 59/ 61

•

  Las Vergnas. A correspondence between spanning trees and orientations in graphs Graph Theory and Combinatorics, Academic Press, London, UK, 233-238, (1984) • G. Correspondance naturelle entre bases et réorientations des matroïdes orientés. Ph.D. Université Bordeaux 1, 2002. • G.-L.V. Bases, reorientations, and linear programming, in uniform and rank 3 oriented matroids. Advances in Applied Mathematics 32, 212-238 (2004) • G.-L.V. Activity preserving bijections between spanning trees and orientations in graphs. Discrete Mathematics, Vol. 298, pp. 169-188,(2005) • G.-L.V. The active bijection between regions and simplices in supersolvable arrangements of hyperplanes. Electronic. J. Comb., Vol. 11(2), pp. 39,(2006) • G.-L.V. Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids. EuroComb'07 (Sevilla), ENDM 365-371 (2007) • G.-L.V. A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements. EuroComb'09 (Bordeaux), ENDM 307-311 (2009) • G.-L.V. The active bijection in graphs, hyperplane arrangements, and oriented matroids -1 -The fully optimal basis of a bounded region. European Journal of Combinatorics

For instance, we get a bijection between bounded regions (bipolar orientations in the case of a graph) and bases with internal activity one and external activity zero, which can be seen as an elaboration on linear programming. We get a decomposition of into bounded regions of minors of the primal and the dual, which also has a counterpart for decomposing matroid bases, and yields an expression of the Tutte polynomial using only beta invariants of minors. We also get activity preserving bijections between all

References 60/ 61 References • Las Vergnas. A correspondence between spanning trees and orientations in graphs Graph Theory and Combinatorics, Academic Press, London, UK, 233-238, (1984) 61/ 61 References • Las Vergnas. A correspondence between spanning trees and orientations in graphs Graph Theory and Combinatorics, Academic Press, London, UK, 233-238, (1984) • G. Correspondance naturelle entre bases et réorientations des matroïdes orientés. Ph.D. Université Bordeaux 1, 2002. 61/ 61 References • Las Vergnas. A correspondence between spanning trees and orientations in graphs Graph Theory and Combinatorics, Academic Press, London, UK, 233-238, (1984) • G. Correspondance naturelle entre bases et réorientations des matroïdes orientés. Ph.D. Université Bordeaux 1, 2002.

• G.-L.V. Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids. EuroComb'07 (Sevilla), ENDM 365-371 (2007) • G.-L.V. A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements. EuroComb'09 (Bordeaux), ENDM 307-311 (2009)

Active bijection: main theorem in the bounded case An ordered bounded oriented matroid w.r.t. min(E ) M has a unique fully optimal basis denoted α(M)

Active bijection: main theorem in the bounded case An ordered bounded oriented matroid w.r.t. min(E ) M has a unique fully optimal basis denoted α(M)

The mapping α is a bijection between (pairs of opposite) bounded regions of M and (1, 0)-active bases of M.

Computational remarks

The fully optimal basis α(M) is difficult to compute (the problem contains the real/combinatorial linear programming problem).

But the unique reorientation α -1 (B) associated with the basis B is easy to compute (just sign the elements from the first to the last so that the criterion is satisfied).

Decomposing sequences

Let E be a finite linearly ordered set. We call abstract decomposing sequence of E a sequence of subsets of E such that:

Let M be a matroid on E . A decomposing sequence of M is an abstract decomposing sequence of E such that:

Theorem: decomposing oriented matroids into bounded regions

Let M be an oriented matroid on a linearly ordered set E .

and

where the disjoint union is over all decomposing sequences of M

(the decomposing sequence of M associated in the second term to a reorientation A is the active decomposing sequence of -A M.)

Refined basis activities

Let M be a matroid on a linearly ordered set E . Let B ⊆ E be a basis of M. Let A be in the boolean interval

Theorem. [Gordon & Traldi 1990, Las Vergnas 2013] Let M be a matroid on a linearly ordered set E .

Deletion/contraction construction of various bijections

M oriented matroid on a linearly ordered set E with max(E ) = ω.

Choice at each step:

Theorem.

With suitable choices, we get whole classes of bijections between bases: all / subsets / internal / no broken circuit subsets / ... and reorientations: classes / all / specific / acyclic / ...

Various properties can be demanded: activities / adjacency / ... Specifying choices yield: THE active bijection.

Deletion/contraction construction of the active bijection M oriented matroid on a linearly ordered set E with max(E ) = ω.

Choice at each step:

One way of defining the active bijection:

If M is a region (acyclic orientation):

also a region and

If M and -ωM do not have same active partition then the choice is determined Otherwise then compare the flags associated to each region in the bounded minor containing ω in order to preserve the fully optimal basis adjacency property (almost) ready for submission and available on demand or at Arxiv (2015).

61/ 61

References 307-311 (2009) • G.-L.V. The active bijection in graphs, hyperplane arrangements, and oriented matroids -1 -The fully optimal basis of a bounded region. European Journal of Combinatorics, Vol. 30 (8), pp. 1868-1886(2009) • G.-L.V. The active bijection in graphs: overview, new results, complements and Tutte polynomial expressions.

(almost) ready for submission and available on demand or at Arxiv (2015). • • • G.-L.V. The active bijection in graphs, hyperplane arrangements, and oriented matroids. 2. Decomposition of activities. / 3. Linear programming construction of fully optimal bases. / 4. Deletion/contraction constructions and universality. Back in active preparation...

THANKS!

61/ 61


Amine Balafrej

Christian Bessiere

Remi Coletta
email: coletta@lirmm.fr

El Houssine Bouyakhf
email: bouyakhf@fsr.ac.ma

Adaptive Parameterized Consistency

State-of-the-art constraint solvers uniformly maintain the same level of local consistency (usually arc consistency) on all the instances. We propose parameterized local consistency, an original approach to adjust the level of consistency depending on the instance and on which part of the instance we propagate. We do not use as parameter one of the features of the instance, as done for instance in portfolios of solvers. We use as parameter the stability of values, which is a feature based on the state of the arc consistency algorithm during its execution. Parameterized local consistencies choose to enforce arc consistency or a higher level of local consistency on a value depending on whether the stability of the value is above or below a given threshold. We also propose a way to dynamically adapt the parameter, and thus the level of local consistency, during search. This approach allows us to get a good trade-off between the number of values pruned and the computational cost. We validate our approach on various problems from the CSP competition.

Introduction

Enforcing constraint propagation by applying local consistency during search is one of the strengths of constraint programming (CP). It allows the constraint solver to remove locally inconsistent values. This leads to a reduction of the search space. Arc consistency is the oldest and most well-known way of propagating constraints [START_REF] Bessiere | Constraint propagation[END_REF]. It has the nice feature that it does not modify the structure of the constraint network. It just prunes infeasible values. Arc consistency is the standard level of consistency maintained in constraint solvers. Several other local consistencies pruning only values and stronger than arc consistency have been proposed, such as max restricted path consistency or singleton arc consistency [START_REF] Debruyne | Some practicable filtering techniques for the constraint satisfaction problem[END_REF]. These local consistencies are seldom used in practice because of the high computational cost of maintaining them during search. However, on some problems, maintaining arc consistency is not a good choice because of the high number of ineffective revisions of constraints that penalize the CPU time. For instance, Stergiou observed that when solving the scen11 radio link frequency assignment problem (RLFAP) with an algorithm maintaining arc consistency, only 27 out of the 4103 constraints of the problem were identified as causing a domain wipe out and 1921 constraints did not prune any value [START_REF] Stergiou | Heuristics for dynamically adapting propagation in constraint satisfaction problems[END_REF].

This work has been funded by the EU project ICON (FP7-284715).

Choosing the right level of local consistency for solving a problem requires finding the good trade-off between the ability of this local consistency to remove inconsistent values, and the cost of the algorithm that enforces it. Stergiou suggests to take advantage of the power of strong consistencies to reduce the search space while avoiding the high cost of maintaining them in the whole network. His method results in a heuristic approach based on the monitoring of propagation events to dynamically adapt the level of local consistency (arc consistency or max restricted path consistency) to individual constraints. This prunes more values than arc consistency and less than max restricted path consistency. The level of propagation obtained is not characterized by a local consistency property. Depending on the order of propagation we can converge on different closures. When dealing with global constraints, some work propose to weaken arc consistency instead of strengthening it. In [START_REF] Katriel | Randomized filtering algorithms[END_REF], Katriel et al. proposed a randomized filtering scheme for AllDifferent and Global Cardinality Constraint. In [START_REF] Sellmann | Approximated consistency for knapsack constraints[END_REF], Sellmann introduced the concept of approximated consistency for optimization constraints and provided filtering algorithms for Knapsack Constraints based on bounds with guaranteed accuracy.

In this paper we define the notion of stability of values. This is an original notion not based on characteristics of the instance to solve but based on the state of the arc consistency algorithm during its propagation. Based on this notion, we propose parameterized consistencies, an original approach to adjust the level of consistency inside a given instance. The intuition is that if a value is hard to prove arc consistent (i.e., the value is not stable for arc consistency), this value will perhaps be pruned by a stronger local consistency. The parameter p specifies the threshold of stability of a value v below which we will enforce a higher consistency to v. A parameterized consistency p-LC is thus an intermediate level of consistency between arc consistency and another consistency LC, stronger than arc consistency. The strength of p-LC depends on the parameter p. This approach allows us to find a trade-off between the pruning power of the local consistency and the computational cost of the algorithm that achieves it. We apply p-LC to the case where LC is max restricted path consistency. We describe the algorithm p-maxRPC3 (based on maxRPC3 [START_REF] Balafoutis | New algorithms for max restricted path consistency[END_REF]) that achieves p-max restricted path consistency. Then, we propose ap-LC, an adaptive variant of p-LC which adapts dynamically and locally the level of local consistency during search. Finally, we experimentally assess the practical relevance of parameterized local consistency. We show that by making good choices for the parameter p we take advantage of both arc consistency light computational cost and LC effectiveness of pruning. In the best cases, a solver using p-LC explores the same number of nodes as LC with a number of constraint checks lower than LC, resulting in a CPU-time lower than both arc consistency-based or LC-based solvers.

Background

A constraint network is defined as a set of n variables X = {x 1 , ..., x n }, a set of ordered domains D = {D(x 1 ), ..., D(x n )}, and a set of e constraints C = {c 1 , ..., c e }. Each constraint c k is defined by a pair (var(c k ), sol(c k )), where var(c k ) is an ordered subset of X, and sol(c k ) is a set of combinations of values (tuples) satisfying c k . In the following, we restrict ourselves to binary constraints because the local consistency (maxRPC) we use here to instantiate our approach is defined on the binary case only. However, the notions we introduce can be extended to non-binary constraints, by using maxRPWC for instance [START_REF] Bessiere | Domain filtering consistencies for non-binary constraints[END_REF]. A binary constraint c between x i and x j will be denoted by c ij , and Γ (x i ) will denote the set of variables x j involved in a constraint with x i .

A value

v j ∈ D(x j ) is called an arc consistent support (AC support) for v i ∈ D(x i ) on c ij if (v i , v j ) ∈ sol(c ij ). A value v i ∈ D(x i ) is arc consistent (AC) if and only if for all x j ∈ Γ (x i ) v i has an AC support v j ∈ D(x j ) on c ij . A domain D(x i ) is arc consistent if it
is non empty and all values in D(x i ) are arc consistent. A network is arc consistent if all domains in D are arc consistent. If enforcing arc consistency on a network N leads to a domain wipe out, we say that N is arc inconsistent.

A tuple (v i , v j ) ∈ D(x i ) × D(x j ) is path consistent (PC) if and only if for any third variable x k there exists a value v k ∈ D(x k ) such that v k is an AC support for both v i and v j . In such a case, v k is called witness for the path consistency of (v i , v j ).

A value

v j ∈ D(x j ) is a max restricted path consistent (maxRPC) support for v i ∈ D(x i ) on c ij if and only if it is an AC support and the tuple (v i , v j ) is path consistent. A value v i ∈ D(x i ) is max restricted path consistent on a constraint c ij if and only if ∃v j ∈ D(x j ) maxRPC support for v i on c ij . A value v i ∈ D(x i )
is max restricted path consistent iff for all x j ∈ Γ (x i ) v i has a maxRPC support v j ∈ D(x j ) on c ij . A domain D(x i ) is maxRPC if it is non empty and all values in D(x i ) are maxRPC. A network is maxRPC if all domains in D are maxRPC.

We say that a local consistency LC 1 is stronger than a local consistency LC 2 (LC 2 LC 1 ) if LC 2 holds on any constraint network on which LC 1 holds.

The problem of deciding whether a constraint network has solutions is called the constraint satisfaction problem (CSP), and it is NP-complete. Solving a CSP is done by backtrack search that maintains some level of consistency between each branching step.

Parameterized Consistency

In this section we present an original approach to parameterize a level of consistency LC stronger than arc consistency so that it degenerates to arc consistency when the parameter equals 0, to LC when the parameters equals 1, and to levels in between when the parameter is between 0 and 1. The idea behind this is to be able to adjust the level of consistency to the instance to be solved, hoping that such an adapted level of consistency will prune significantly more values than arc consistency while being less time consuming than LC.

Parameterized consistency is based on the concept of stability of values. We first need to define the 'distance to end' of a value in a domain. This captures how far a value is from the last in its domain. In the following, rank(v, S) is the position of value v in the ordered set of values S.

Definition 1 (Distance to end of a value). The distance to end of a value

v i ∈ D(x i ) is the ratio ∆(x i , v i ) = (|D o (x i )| -rank(v i , D o (x i )))/|D o (x i )|, where D o (x i ) is the initial domain of x i .
We see that the first value in

D o (x i ) has distance (|D o (x i )| -1)/|D o (x i )
| and the last one has distance 0. Thus, ∀v i ∈ D(x i ), 0 ≤ ∆(x i , v i ) < 1.

We can now give the definition of what we call the parameterized stability of a value for arc consistency. The idea is to define stability for values based on the distance to the end of their AC supports. For instance, consider the constraint x 1 ≤ x 2 with the domains D(x 1 ) = D(x 2 ) = {1, 2, 3, 4} (see Figure 1). ∆(x 2 , 1) = (4 -1)/4 = 0.75, ∆(x 2 , 2) = 0.5, ∆(x 2 , 3) = 0.25 and ∆(x 2 , 4) = 0. If p = 0.2, the value (x 1 , 4) is not p-stable for AC, because the first and only AC support of (x 1 , 4) in the ordering used to look for supports, that is (x 2 , 4), has a distance to end smaller than the threshold p. Proving that the pair (4, 4) is inconsistent (by a stronger consistency) could lead to the pruning of (x 1 , 4). In other words, applying a stronger consistency on (x 1 , 4) has more chances to lead to its removal than applying it on for instance (x 1 , 1), which had no difficulty to find its first AC support (distance to en of (x 2 , 1) is 0.75).

Definition 2 (p-stability for AC). A value

v i ∈ D(x i ) is p-stable for AC on c ij iff v i has an AC support v j ∈ D(x j ) on c ij such that ∆(x j , v j ) ≥ p. A value v i ∈ D(x i ) is p-stable for AC iff ∀x j ∈ Γ (x i ), v i is p-stable for AC on c ij .
We are now ready to give the first definition of parameterized local consistency. This first definition can be applied to any local consistency LC for which the consistency of a value on a constraint is well defined. This is the case for instance for all triangle-based consistencies [START_REF] Debruyne | Domain filtering consistencies[END_REF][START_REF] Bessiere | Constraint propagation[END_REF].

Definition 3 (Constraint-based p-LC).

Let LC be a local consistency stronger than AC for which the LC consistency of a value on a constraint is defined

. A value v i ∈ D(x i ) is constraint-based p-LC on c ij iff it is p-stable for AC on c ij , or it is LC on c ij . A value v i ∈ D(x i ) is constraint-based p-LC iff ∀c ij , v i is constraint-based p-LC on c ij . A constraint network is constraint-based p-LC iff all values in all domains in D are constraint-based p-LC.
Theorem 1. Let LC be a local consistency stronger than AC for which the LC consistency of a value on a constraint is defined. Let p 1 and p 2 be two parameters in

[0..1]. If p 1 < p 2 then AC constraint-based p 1 -LC constraint-based p 2 - LC LC.
Proof. Suppose that there exist two parameters p 1 , p 2 such that 0 ≤ p 1 < p 2 ≤ 1, and suppose that there exists a

p 2 -LC constraint network N that contains a p 2 -LC value (x i , v i ) that is p 1 -LC inconsistent. Let c ij be the constraint on which (x i , v i ) is p 1 -LC inconsistent. Then, v j ∈ D(x j ) that is an AC support for (x i , v i ) on c ij such that ∆(x j , v j ) ≥ p 1 . Thus, v i is not p 2 -stable for AC on c ij . In addition, v i is not LC on c ij . Therefore, v i is not p 2 -LC, and N is not p 2 -LC.
Definition 3 can be modified to a more coarse-grained version that is not dependent on the consistency of values on a constraint. It will have the advantage to apply to any type of strong local consistency, even those, like singleton arc consistency, for which the consistency of a value on a constraint is not defined. Proof. Suppose that there exist two parameters p 1 , p 2 such that 0 ≤ p 1 < p 2 ≤ 1, and suppose that there exists a p 2 -LC constraint network N that contains a

Definition 4 (Value-based p-LC). Let LC be a local consistency stronger than AC. A value

v i ∈ D(x i ) is value-based p-LC if and only if it is p-stable for AC or it is LC. A constraint
p 2 -LC value (x i , v i ) that is p 1 -LC-inconsistent. v i is p 1 -LC-inconsistent means that: 1. v i is not p 1 -stable for AC: ∃c ij on which v i is not p 1 -stable for AC. Then v j ∈ D(x j ) that is an AC support for (x i , v i ) on c ij such that ∆(x j , v j ) ≥ p 1 . Therefore, v i is not p 2 -stable for AC on c ij , then v i is not p 2 -stable for AC. 2. v i is LC inconsistent
(1) and (2) imply that v i is not p 2 -LC, and N is not p 2 -LC. For both types of definitions of p-LC, we have the following property on the extreme cases (p = 0, p = 1).

Corollary 1. Let LC 1 and LC 2 be two local consistencies stronger than AC. We have: value-based 0-LC 2 = AC and value-based 1-LC 2 = LC. If the LC 1 consistency of a value on a constraint is defined, we also have: constraint-based 0-LC 1 = AC and constraint-based 1-LC 1 = LC.

Parameterized maxRPC: p-maxRPC

To illustrate the benefit of our approach, we apply parameterized consistency to maxRPC to obtain the p-maxRPC level of consistency that achieves a consistency level between AC and maxRPC. Definition 5 (p-maxRPC). A value, a network, are p-maxRPC if and only if they are constraint-based p-maxRPC.

From Theorem 1 and Corollary 1 we derive the following corollary.

Corollary 2. For any two parameters

p 1 , p 2 , 0 ≤ p 1 < p 2 ≤ 1, AC p 1 - maxRP C p 2 -maxRP C maxRP C. 0-maxRP C = AC and 1-maxRP C = maxRP C. Algorithm 1: Initialization(X, D, C, Q) 1 begin 2 foreach xi ∈ X do 3 foreach vi ∈ D(xi) do 4 foreach xj ∈ Γ (xi) do 5 p-support ← f alse 6 foreach vj ∈ D(xj) do 7 if (vi, vj) ∈ cij then 8 LastACx i ,v i ,x j ← vj 9 if ∆(xj, vj) ≥ p then 10 p-support ← true 11 LastP Cx i ,v i ,x j ← vj 12 break; 13 if searchPCwit(vi, vj) then 14 p-support ← true 15 LastP Cx i ,v i ,x j ← vj 16 break; 17 if ¬p-support then 18 remove vi from D(xi) 19 Q ← Q ∪ {xi} 20 break; 21 if D(xi) = ∅ then return f alse 22 return true
We propose an algorithm for p-maxRPC, based on maxRPC3, the best existing maxRPC algoritm. We do not describe maxRPC3 in full detail as it can be found in [START_REF] Balafoutis | New algorithms for max restricted path consistency[END_REF]. We only describe procedures where changes to maxRPC3 are

Algorithm 2: checkPCsupLoss(v j , x i ) begin if LastACx j ,v j ,x i ∈ D(xi) then bi ← max(LastP Cx j ,v j ,x i +1,LastACx j ,v j ,x i ) else bi ← max(LastP Cx j ,v j ,x i +1,LastACx j ,v j ,x i +1) foreach vi ∈ D(xi), vi ≥ bi do if (vj, vi) ∈ cji then if LastACx j ,v j ,x i / ∈ D(xi) & LastACx j ,v j ,x i >LastP Cx j ,v j ,x i then LastACx j ,v j ,x i ← vi if ∆(xi, vi) ≥ p then LastP Cx j ,v j ,x i ← vi return true if searchPCwit(vj, vi) then LastP Cx j ,v j ,x i ← vi return true return f alse Algorithm 3: checkPCwitLoss(x j , v j , x i ) begin foreach x k ∈ Γ (xj) ∩ Γ (xi) do witness ← f alse if v k ←LastP Cx j ,v j ,x k ∈ D(x k ) then if ∆(x k , v k ) ≥ p then witness ← true else if LastACx j ,v j ,x i ∈ D(xi) & LastACx j ,v j ,x i =LastACx k ,v k ,x i OR LastACx j ,v j ,x i ∈ D(xi) & ( LastACx j ,v j ,x i , v k ) ∈ c ik OR LastACx k ,v k ,x i ∈ D(xi) & ( LastACx k ,v k ,x i , vj) ∈ cij then witness ← true else if searchACsup(xj, vj, xi) & searchACsup(x k , v k , xi) then foreach vi ∈ D(xi), vi ≥ max(LastACx j ,v j ,x i , LastACx k ,v k ,x i ) do if (vj, vi) ∈ cji & (v k , vi) ∈ c ki then witness ← true break;
if ¬witness & ¬checkPCsupLoss(vj, x k ) then return f alse return true necessary to design p-maxRPC3, a coarse grained algorithm that performs p-maxRPC. We use light grey to emphasize the modified parts of the original maxRPC3 algorithm. maxRPC3 uses a propagation list Q where it inserts the variables whose domains have changed. It also uses two other data structures: LastAC and LastPC. For each value (x i , v i ) LastAC xi,vi,xj stores the smallest AC support for (x i , v i ) on c ij and LastPC xi,vi,xj stores the smallest PC support for (x i , v i ) on c ij (i.e., the smallest AC support (x j , v j ) for (x i , v i ) on c ij such that (v i , v j ) is PC). This algorithm consists in two phases: initialization and propagation.

In the initialization phase (algorithm 1) maxRPC3 checks if each value (x i , v i ) has a maxRPC-support (x j , v j ) on each constraint c ij . If not, it removes v i from D(x i ) and inserts x i in Q. To check if a value (x i , v i ) has a maxRPC-support on a constraint c ij , maxRPC3 looks first for an AC-support (x j , v j ) for (x i , v i ) on c ij , then it checks if (v i , v j ) is PC. In this last step, changes were necessary to obtain p-maxRPC3 (lines 9-12). We check if (v i , v j ) is PC (line 13) only if ∆(x j , v j ) is smaller than the parameter p (line 9).

The propagation phase of maxRPC3 consists in propagating the effect of deletions. While Q is non empty, maxRPC3 extracts a variable x i from Q and checks for each value (x j , v j ) of each neighboring variable x j ∈ Γ (x i ) if it is not maxRPC because of deletions of values in D(x i ). A value (x j , v j ) becomes maxRPC inconsistent in two cases: if its unique PC-support (x i , v i ) on c ij has been deleted, or if we deleted the unique witness (x i , v i ) for a pair (v j , v k ) such that (x k , v k ) is the unique PC-support for (x j , v j ) on c jk . So, to propagate deletions, maxRPC3 checks if the last maxRPC support (last known support) of (x j , v j ) on c ij still belongs to the domain of x i , otherwise it looks for the next support (algorithm 2). If such a support does not exist, it removes the value v j and adds the variable x j to Q. Then if (x j , v j ) has not been removed in the previous step, maxRPC3 checks (algorithm 3) whether there is still a witness for each pair (v j , v k ) such that (x k , v k ) is the PC support for (x j , v j ) on c jk . If not, it looks for the next maxRPC support for (x j , v j ) on c jk . If such a support does not exist, it removes v j from D(x j ) and adds the variable x j to Q.

In the propagation phase also, we modified maxRPC3 to check if the values are still p-maxRPC instead of checking if they are maxRPC. In p-maxRPC3, the last p-maxRPC support for (x j , v j ) on c ij is the last AC support if (x j , v j ) is p-stable for AC on c ij . If not, it is the last PC support. Thus, p-maxRPC3 checks if the last p-maxRPC support (last known support) of (x j , v j ) on c ij still belongs to the domain of x i . If not, it looks (algorithm 2) for the next AC support (x i , v i ) on c ij , and checks if (v i , v j ) is PC (line 9) only when ∆(x i , v i ) < p (line 8). If no p-maxRPC support exists, p-maxRPC3 removes the value and adds the variable x j to Q. If the value (x j , v j ) has not been removed in the previous phase, p-maxRPC3 checks (algorithm 3) whether there is still a witness for each pair (v j , v k ) such that (x k , v k ) is the p-maxRPC support for v j on c jk and ∆(x k , v k ) < p. If not, it looks for the next p-maxRPC support for v j on c jk . If such a support does not exist, it removes v j from D(x j ) and adds the variable x j to Q.

Experimental validation of p-maxRPC

To validate the approach of parameterized local consistency, we made a first basic experiment. The purpose of this experiment is to see if there exist problems on which a given level of p-maxRPC, with a p uniform on all the constraint network and static during the whole search is more efficient than AC or maxRPC, or both. We have implemented the algorithms that achieve p-maxRPC as described in the previous section in our own binary constraint solver, in addition to maxRPC (maxRPC3 version [START_REF] Balafoutis | New algorithms for max restricted path consistency[END_REF]) and AC (AC2001 version [START_REF] Bessiere | An optimal coarse-grained arc consistency algorithm[END_REF]). All these algorithms are maintained during search. We tested these algorithms on several classes of problems of the International Constraint Solver Competition 091 . We have only selected problems involving binary constraints. To isolate the effect of propagation, we used the lexicographic ordering for variables and values. We set the CPU timeout to one hour. Our experiments were conducted on a 12-core Genuine Intel machine with 16Gb of RAM running at 2.92GHz.

On each instance of our experiment, we ran AC, max-RPC, and p-maxRPC for all values of p in {0.1, 0.2, . . . , 0.9}. Performance has been measured in terms of CPU time in seconds, the number of visited nodes (NODE) and the number of constraint checks (CCK). Results are presented as "CPU time (p)", where p is the parameter for which p-maxRPC gives the best result.

Table 1 reports the performance of AC, maxRPC, and p-maxRPC for the value of p producing the best CPU time, on Radio Link Frequency Assignment Problems (RLFAPs), Geom problems, and queens knights problems. The CPU time of the best algorithm is highlighted with bold. On RLFAP and Geom, we observe the existence of a parameter p where p-maxRPC is faster than both AC and maxRPC for most instances of these two classes of problems. On the queensknight problem, however, AC is always the best algorithm. In Figures 2 and3, we try to understand more closely what makes p-maxRPC better or worse than AC and maxRPC. Figures 2 and3 plot the performance (CPU, NODE and CCK) of p-maxRPC for all values of p from 0 to 1 by steps of 0.1 against performance of AC and maxRPC. Figure 2 shows an instance where p-maxRPC solves the problem faster than AC and maxRPC for values of p in the range [0.3..0.8]. We observe that p-maxRPC is faster than AC and maxRPC when it reduces the size of the search space as much as maxRPC (same number of nodes visited) with a number of CCK closer to the number of CCK produced by AC. Figure 3 shows an instance where the CPU time for p-maxRPC is never better than both AC and maxRPC. We see that if the CPU time for p-maxRPC is two to three times better than maxRPC, it fails to improve AC because the number of constraint checks performed by p-maxRPC is much higher than the number of constraint checks performed by AC, whereas the number of nodes visited by p-maxRPC is not significantly reduced compared to the number of nodes visited by AC. From these observations, it thus seems that p-maxRPC outperforms AC and maxRPC when it finds a compromise between the number of nodes visited (the power of maxRPC) and the number of CCK needed to maintain (the light cost of AC).

In Figures 2 and3 we can see that the CPU time for 1-maxRPC (respectively 0-maxRPC) is greater than the CPU time for maxRPC (respectively AC) although the two consistencies are equivalent. The reason is that p-maxRPC performs tests on the distances. For p = 0, we also explain this difference by the fact that p-maxRPC maintains data structures that AC does not use.

Adaptative Parameterized Consistency: ap-maxRPC

In the previous section, we have defined p-maxRPC, a version of parameterized consistency where the strong local consistency is maxRPC. We have performed some initial experiments where p has the same value during the whole search and everywhere in the constraint network. However, the algorithm we proposed to enforce p-maxRPC does not specify how p is chosen. In this section, we propose two possible ways to dynamically and locally adapt the parameter p in order to solve the problem faster than both AC and maxRPC. Instead of using a single parameter p during the whole search and for the whole constraint network, we propose to use several local parameters and to adapt the level of local consistency by dynamically adjusting the value of the different local parameters during search. The idea is to concentrate the effort of propagation by increasing the level of consistency in the most difficult parts of the instance. We can determine these difficult parts using heuristics based on conflicts in the same vein as the weight of a constraint or the weighted degree of a variable in [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF].

Constraint-Based ap-maxRPC : apc-maxRPC

The first technique we propose, called constraint-based ap-maxRPC, assigns a parameter p(c k ) to each constraint c k in C. We define this parameter to be correlated to the weight of the constraint. The idea is to apply a higher level of consistency in parts of the problem where the constraints are the most active.

Definition 6 (The weight of a constraint [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]). The weight w(c k ) of a constraint c k ∈ C is an integer that is incremented every time a domain wipe out occurs while performing propagation on this constraint.

We define the adaptive parameter p(c k ) local to constraint c k in such a way that it is greater when the weight w(c k ) is higher wrt to other constraints.

∀c k ∈ C, p(c k ) = w(c k ) -min c∈C (w(c)) max c∈C (w(c)) -min c∈C (w(c)) (1)
Equation 1 is normalized so that we are guaranteed that 0 ≤ p(c k ) ≤ 1 for all c k ∈ C and that there exists c k1 with p(c k1 ) = 0 (the constraint with lowest weight) and c k2 with p(c k2 ) = 1 (the constraint with highest weight).

We are ready to define adaptive parameterized consistency based on constraints.

Definition 7 (constraint-based ap-maxRPC). A value

v i ∈ D(x i ) is constraint-based ap-maxRPC (or apc-maxRPC) on a constraint c ij if and only if it is constraint-based p(c ij )-maxRPC. A value v i ∈ D(x i ) is apc-maxRPC iff ∀c ij , v i is apc-maxRPC on c ij . A constraint network is apc-maxRPC iff all
values in all domains in D are apc-maxRPC.

Variable-Based ap-maxRPC: apx-maxRPC

The technique proposed in Section 6.1 can only be used on consistencies where the consistency of a value on a constraint is defined. We give a second technique which can be used on constraint-based or variable-based local consistencies indifferently. We instantiate our definitions to maxRPC but the extension to other consistencies is direct. We call this new technique variable-based ap-maxRPC. We need to define the weighted degree of a variable as the aggregation of the weights of all constraints involving it.

Definition 8 (The weighted degree of a variable [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]). The weighted degree wdeg(x i ) of a variable x i is the sum of the weights of the constraints involving x i and one other uninstantiated variable.

We associate each variable with an adaptive local parameter based on its weighted degree.

∀x i ∈ X, p(x i ) = wdeg(x i ) -min x∈X (wdeg(x)) max x∈X (wdeg(x)) -min x∈X (wdeg(x)) (2)
As in Equation 1, we see that the local parameter is normalized so that we are guaranteed that 0 ≤ p(x i ) ≤ 1 for all x i ∈ X and that there exists x k1 with p(x k1 ) = 0 (the variable with lowest weighted degree) and x k2 with p(x k2 ) = 1 (the variable with highest weighted degree).

Definition 9 (variable-based ap-maxRPC). A value v i ∈ D(x i ) is variablebased ap-maxRPC (or apx-maxRPC) if and only if it is value-based p(x i )-maxRPC. A constraint network is apx-maxRPC iff all values in all domains in D are apx-maxRPC.

Experimental Evaluation of ap-maxRPC

In Section 5 we have shown that maintaining a static form of p-maxRPC during the whole search can lead to a promising trade-off between computational effort and pruning when all algorithms follow the same static variable ordering. In this section, we want to put our contributions in the real context of a solver using the best known variable ordering heuristic, dom/wdeg, though it is known that this heuristic is so good that it reduces a lot the differences in performance that other features of the solver could provide. We have compared the two variants of adaptive parameterized consistency introduced in Section 6 to AC and maxRPC.

We ran the four algorithms on radio link frequency assignment problems, geom problems, and queens knights problems. Table 2 reports some representative results. A first observation is that, thanks to the dom/wdeg heuristic, we were able to solve more instances before the cutoff of one hour, especially the scen11 variants of RLFAP. A second observation is that apc-maxRPC and apx-maxRPC are both faster than at least one of the two extreme consistencies (AC and maxRPC) on all instances except scen7-w1-f4 and geo50-20-d4-75-30. Third, when apx-maxRPC and/or apc-maxRPC are faster than both AC and maxRPC (scen1-f9, scen2-f25, scen11-f9, scen11-f10 and scen11-f11), we observe that the gap in performance in terms of nodes and CCKs between AC and maxRPC is significant. Except for scen7-w1-f4, the number of nodes visited by AC is three to five times greater than the number of nodes visited by maxRPC and the number of constraint checks performed by maxRPC is twelve to sixteen times greater than the number of constraint checks performed by AC. For the Geom instances the CPU time of the ap-maxRPC algorithms is between AC and maxRPC, and it is never lower than the CPU time of AC. This probably means that when solving these instances with the dom/wdeg heuristic, there is no need for sophisticated local consistencies. In general we see that the ap-maxRPC algorithms fail to improve both the two extreme consistencies simultaneously for the instances where the performance gap between AC and maxRPC is low.

If we compare apx-maxRPC to apc-maxRPC, we observe that although apx-maxRPC is coarser in its design than apc-maxRPC, apx-maxRPC is often faster than apc-maxRPC. We can explain this by the fact that the constraints initially all have the same weight equal to 1. Hence, all local parameters ap(c k ) initially have the same value 0, so that apc-maxRPC starts resolution by applying AC everywhere. It will start enforcing some amount of maxRPC only after the first wipe-out occurred. On the contrary, in apx-maxRPC, when constraints all have the same weight, the local parameter p(x i ) is correlated to the degree of the variable x i . As a result, apx-maxRPC benefits from the filtering power of maxRPC even before the first wipe-out.

In Table 2, we reported only the results on a few representative instances. Table 3 summarizes the whole set of experiments. It shows the average CPU time for each algorithm on all instances of the different classes of problems tested. We considered only the instances solved before the cutoff of one hour by at least one of the four algorithms. To compute the average CPU time of an algorithm on a class of problems, we add the CPU time needed to solve each instance solved before the cutoff of one hour, and for the instances not solved before the cutoff, we add one hour. We observe that the adaptive approach is, on average, faster than the two extreme consistencies AC and maxRPC, except on the Geom class.

In apx-maxRPC and apc-maxRPC, we update the local parameters p(x i ) or p(c k ) at each node in the search tree. We could wonder if such a frequent update does not produce too much overhead. To answer this question we performed a simple experiment in which we update the local parameters every 10 nodes only. We re-ran the whole set of experiments with this new setting. Table 4 the CPU time average results. We observe that when the local parameters are updated every 10 nodes, the gain for the adaptive approach is, on average, greater than when the local parameters are updated at each node. This gives room for improvement, by trying to adapt the frequency of update of these parameters.

Conclusion

We have introduced the notion of stability of values for arc consistency, a notion based on the depth of their supports in their domain. We have used this notion to propose parameterized consistency, a technique that allows to define levels of local consistency of increasing strength between arc consistency and a given strong local consistency. We have instantiated the generic parameterized consistency approach to max restricted path consistency. We have experimentally shown that the concept of parameterized consistency is viable. Then we have introduced two techniques which allow us to make the parameter adaptable dynamically and locally during search . We have evaluated these two techniques experimentally and we have observed that adapting the level of local consistency during search using the parameterized consistency concept is a promising approach that can outperform both MAC and a strong local consistency on many problems.

Fig. 1 .

 1 Fig. 1. Stability of supports on the example of the constraint x1 ≤ x2 with the domains D(x1) = D(x2) = {1, 2, 3, 4}. (x1, 4) is not p-stable for AC.

  network is value-based p-LC if and only if all values in all domains in D are value-based p-LC. Theorem 2. Let LC be a local consistency stronger than AC. Let p 1 and p 2 be two parameters in [0..1]. If p 1 < p 2 then AC value-based p 1 -LC value-based p 2 -LC LC.

Fig. 2 .

 2 Fig. 2. Instance where p-maxRPC outperforms both AC and maxRPC.

Fig. 3 .

 3 Fig. 3. Instance where AC outperforms p-maxRPC.

Table 1 .

 1 Performance (CPU time, nodes and constraint checks) of AC, p-maxRPC, and maxRPC on various instances.

	AC	p-maxRPC	maxRPC

Table 2 .

 2 reports Performance (CPU time, nodes and constraint checks) of AC, variablebased ap-maxRPC (apx-maxRPC), constraint-based ap-maxRPC (apc-maxRPC), and maxRPC on various instances.

			AC	apx-maxRPC apc-maxRPC maxRPC
	scen1-f9	CPU(s)	90.34	31.17	33.40	41.56
		#nodes	2,291	1,080	1,241	726
		#ccks	3,740,502	3,567,369	2,340,417	50,045,838
	scen2-f25	CPU(s)	70.57	46.40	27.22	81.40
		#nodes	12,591	4,688	3,928	3,002
		#ccks	15,116,992	38,239,829	8,796,638 194,909,585
	scen6-w2	CPU(s)	7.30	1.25	2.63	0.01
		#nodes	2,045	249	610	0
		#ccks	2,401,057	1,708,812	1,914,113	85,769
	scen7-w1-f4	CPU(s)	0.28	0.17	0.54	0.30
		#nodes	567	430	523	424
		#ccks	608,040	623,258	584,308	1,345,473
	scen11-f9	CPU(s)	2,718.65	1,110.80	1,552.20	2,005.61
		#ccks	103,506	40,413	61,292	32,882
		#nodes 227,751,301	399,396,873	123,984,968 3,637,652,122
	scen11-f10	CPU(s)	225.29	83.89	134.46	112.18
		#ccks	9,511	3,510	4,642	2,298
		#nodes 12,972,427	17,778,458	6,717,485 156,005,235
	scen11-f11	CPU(s)	156.76	39.39	93.69	76.95
		#ccks	7,050	2,154	3,431	1,337
		#nodes 7,840,552	10,006,821	5,143,592	91,518,348
	scen11-f12	CPU(s)	139.91	69.50	88.76	61.92
		#ccks	7,050	2,597	3,424	1,337
		#nodes 7,827,974	11,327,536	5,144,835	91,288,023
	geo50-20d4-75-19 CPU(s)	242.13	553.53	657.72	982.34
		#nodes	195,058	114,065	160,826	71,896
		#ccks 224,671,319	594,514,132	507,131,322 2,669,750,690
	geo50-20d4-75-30 CPU(s)	0.84	1.01	1.07	1.02
		#nodes	359	115	278	98
		#ccks	261,029	432,705	313,168	1,880,927
	geo50-20d4-75-84 CPU(s)	0.02	0.09	0.05	0.29
		#nodes	59	54	59	52
		#ccks	33,876	80,626	32,878	697,706
	queensK20-5-mul CPU(s)	787.35	2,345.43	709.45	Time-out
		#codes	55,596	40,606	41,743	-
		#ccks 347,596,389 6,875,941,876	379,826,516	-
	queensK15-5-add CPU(s)	24.69	17.01	14.98	35.05
		#codes	24,639	12,905	12,677	11,595
		#ccks	90,439,795	91,562,150	58,225,434 394,073,525

Table 3 .

 3 Average CPU time of AC, variable-based ap-maxRPC (apx-maxRPC), constraint-based ap-maxRPC (apc-maxRPC), and maxRPC on all instances of each class of problems tested, when the local parameters are updated at each node

		AC apx-maxRPC apc-maxRPC maxRPC
	geom	69.28	180.57	191.03	279.30
	Average(CPU) scen	18.95	9.63	8.30	13.94
	scen11	810.15	325.90	467.28	564.17
	queensK 135.95	395.41	121.75	610.51

Table 4 .

 4 Average CPU time of AC, variable-based ap-maxRPC (apx-maxRPC), constraint-based ap-maxRPC (apc-maxRPC), and maxRPC on all instances of each class of problems tested, when the local parameters are updated every 10 nodes

		AC apx-maxRPC apc-maxRPC maxRPC
	geom	69.28	147.20	189.42	279.30
	Average(CPU) scen	18.95	7.40	8.86	13.94
	scen11	810.15	311.74	417.97	564.17
	queensK 135.95	269.51	117.18	610.52

http://cpai.ucc.ie/09/


Vincent Chabot

Ludovic Bouilloud

Julie Capo

Gaëlle Collin

Viviane Gouget

Sophie Martinoni-Lapierre

Nathalie Rouchy

Christian Viel

Virginie Dordonnat

Vincent Lefieux

Intermittent energy sources availability in case of cold peaks in future climate

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Vincent Chabot 1 , Ludovic Bouilloud 1 , Julie Capo 1 , Gaëlle Collin 1 , Viviane Gouget 1 , Sophie Martinoni-Lapierre 1 , Nathalie Rouchy 1 , Christian Viel 1 , Virginie Dordonnat 2 , Vincent Lefieux 2 , Robert Vautard 3

1 Météo France, France 2 RTE, France 3 CEA, France Contact : copernicus.clim4energy@meteo.fr

Indicators

Wind capacity factors: based on three power curves representative of three wind turbine generator classes (IEC classes) and 10m-wind speed. 10m-wind speed is extrapolated at hub height.

Objectives

Design indicators tailored to the energy sector based on meteorological fields to anticipate the risk of imbalance.

Provide coherent data as well as analysis to energy practitioners at different time scales.

Solar Capacity factor Wind Capacity factor Demand Indicator

➢

  Winter: small change ➢ Cold events: small change ➢ Dispersion (France): almost no impact of climate change compared to interannual variability ➢ Winter: significant and robust change ➢ Cold events: significant and robust change ➢ Dispersion (France): major impact of climate change compared to interannual variability ➢ Winter: small change ➢ Cold events: small change ➢ Dispersion change is robust if 80 % of the models find the same tendency of change. Significativity: A statistical test is performed for each model. Change is significative if 80 % of the models find a significative change. Dispersion analysis: enables evaluation of the weight of the interperiod dispersion (representative of climate change effect) compared to the inter-annual dispersion and to the model dispersion HDD= | 15-T if T <15 °c 0 otherwise x m, p , t = x m ,ref ⏞ mean of thereference period for model m + a m , p , t ⏞ anomaly of model m at time t for period p ∑ m , p , t (a p , m, t -a) 2 = ∑ m , p , t (a p , m, t -a p , m ) 2 ⏟ inter-annual dispersion + ∑ m, p ,t (a p , m -a p )

Intermittent energy source availability during cold peaks in future climate Context CLIM4ENERGY

  project, as part of Copernicus Climate Change Service (C3S), aims to provide climate products tailored for the energy sector. The European electric power system is very sensitive to temperatures. The increase of intermittent renewable energies in the energy mix introduces an additional vulnerability to weather conditions. The contribution of intermittent renewable energies is analysed through wind and solar capacity factors built using meteorological fields (wind speed, radiation and temperature). Analysis at different time scales is necessary to help energy practitioners to take short and long term decisions.

	Solar radiation, as well as other meteorological fields (wind, temperature) can
	be used to define different indicators.
	Heating Degree Day weighted by population: based on thresholded 15°C
	deviation for temperature weighted by population (Eurostat)

Solar capacity factors: based on performance ratio (see Jerez et. Al 2015).

Electricity consumption: Based on a linear model using Heating degree day weighted by population adapted for each country.

Data availability

First data version will soon be available online http://clim4energy.climate.copernicus.eu/ Reanalysis 1981-2010