Omar Anza

Jean-Philippe Mandallena
email: philippemandallena<jean-philippe.mandallena@unimes.fr>

RADIAL REPRESENTATION OF LOWER SEMICONTINUOUS ENVELOPE

Keywords: Ru-usc functions, relaxation with constraints, radial representation, star-shaped set, extension on the boundary

We give an extension to a nonconvex setting of the classical radial representation result for lower semicontinuous envelope of a convex function on the boundary of its effective domain. We introduce the concept of radial uniform upper semicontinuity which plays the role of convexity, and allows to prove a radial representation result for nonconvex functions. An application to the relaxation of multiple integrals with constraints on the gradient is given.

Introduction

In convex analysis, a convex and lower semicontinuous function is represented on the boundary of its effective domain by a radial limit along segment from an interior point. Our goal is to give an extension to a nonconvex setting of this result. More precisely, if X is a topological vector space, the problem consists to find general conditions on f : X →] -∞, ∞] and D ⊂ domf such that for some u 0 ∈ D the following implication holds

∀u ∈ D lim D∋v→u f (v) = f (u) =⇒ ∀u ∈ ∂D lim D∋v→u f (v) = lim t↑1 f (tu + (1 -t)u 0 ).
Our motivation comes from the theory of relaxation in the calculus of variations with constraints which consists to the study of the integral representation of the lower semicontinuous envelope of integral functionals subjected to constraints on the gradient. For convex constraints and when the lower semicontinuous envelope is convex, the radial representation on the boundary holds and allows, under some additional requirements, to extend the integral representation to the whole effective domain of the functional (see for instance [START_REF] Carbone | Unbounded functionals in the calculus of variations[END_REF]). However, even for convex constraints, the lower semicontinuous envelope is not necessarily convex when the gradient is a matrix. Indeed, in this case it is well known that if an integral representation holds then, usually, the "relaxed" integrand is quasiconvex or rankone convex (in the sense of Morrey, see for instance [START_REF] Dacorogna | Direct methods in the calculus of variations[END_REF]). Therefore, the need of a generalization of the radial representation to a nonconvex setting comes naturally.

The analysis of how the convexity concept plays to obtain the radial limit representation highlights some kind of uniform upper semicontinuity property, more precisely, when f : X →] -∞, ∞] is convex we may write

sup u∈domf f (tu + (1 -t)u 0 ) -f (u) 1 + |f (u 0 )| + |f (u)| ≤ 1 -t (1.1)
for any u 0 ∈ domf . The left hand side of (1.1) is a kind of uniform semicontinuity modulus which is lower than 0 when t ↑ 1. This is exactly the property we need to overcome the convex case. For a non necessary convex f satisfying (1.1), we will say that f is radially uniformly upper semicontinuity (see Definition 2.1).

The concept of radial uniform upper semicontinuity, to our best of knowledge, finds its origin in [CDA02, Condition (10.1.13), p. 213] in connection with relaxation problems with constraints. Later, this concept was proved very useful for relaxation problems in the vectorial case with bounded and convex constraints see [START_REF] Anza | On the integral representation of relaxed functionals with convex bounded constraints[END_REF]. Then, it was used to study several homogenization and relaxation problems with constraints (see for instance [START_REF] Anza | Homogenization of nonconvex integrals with convex growth[END_REF][START_REF] Anza | Homogenization of unbounded singular integrals in W 1,∞[END_REF][START_REF] Mandallena | Localization principle and relaxation[END_REF][START_REF] Anza | On the relaxation of unbounded multiple integrals[END_REF]).

The plan of the paper is as follows. In Section 2, we first give the definitions of radially uniformly upper semicontinuous functions and star-shaped sets (stated here in an infinite dimensional framework) which play the role of convexity concepts in a nonconvex setting.

In Section 3, we state and prove the main result Theorem 3.1, which gives a radial representation of a lower semicontinuous envelope on the boundary of a star-shaped set. A sequential version of Theorem 3.1 is stated and proved also.

In Section 4, we deduce some general consequences from Theorem 3.1. In particular, we deal with the case of convex functions and minimization problems with star-shaped constraints.

In Section 5, we study the stability of radially uniformly upper semicontinuity concept with respect to calculus operations. We also give examples of some general class of radially uniformly upper semicontinuous functions.

Section 6 is devoted to an application of a relaxation problem of the calculus of variations with constraints on the gradient.

Definitions and preliminaries

Let X be an Hausdorff topological vector space. For a function f : X →]-∞, ∞] we denote its effective domain by domf := {u ∈ X : f (u) < ∞}.

For each a > 0, D ⊂ domf and u 0 ∈ D, we define ∆ a f,D,u0

: [0, 1] →] -∞, ∞] by ∆ a f,D,u0 (t) := sup u∈D f (tu + (1 -t)u 0 ) -f (u) a + |f (u)| .
If D = domf then we write ∆ a f,u0 := ∆ a f,D,u0 . Remark 2.1. By analogy with the case of uniform continuity, the function ∆ a f,D,u0 (•) can be seen as a (semi) radial uniform modulus of f on D relatively to u 0 . Definition 2.1.

(1) Let D ⊂ domf and u 0 ∈ D. We say that f is radially uniformly upper semicontinuous in D relative to u 0 , if there exists a > 0 such that

lim t→1 ∆ a f,D,u0 (t) ≤ 0.
Radially uniformly upper semicontinuous will be abbreviated to ru-usc in what follows.

If D = domf then we simply say that f is ru-usc relative to u 0 ∈ domf . (2) We say that D ⊂ X is a strongly star-shaped set relative to

u 0 ∈ D, if tD + (1 -t)u 0 ⊂ D for all t ∈ [0, 1[, where D is the closure of D in X.
When D ⊂ domf is strongly star-shaped relative to u 0 ∈ D and f is ru-usc in D relative to u 0 ∈ D, we say that f is ru-usc in the strongly star-shaped set D relative to u 0 ∈ D.

Remark 2.2.

(i) Our definition of strongly star-shaped sets is more restrictive than the usual one (see [START_REF] Valentine | Convex sets. McGraw-Hill Series in Higher Mathematics[END_REF]) which requires

tD + (1 -t)u 0 ⊂ D for all t ∈ [0, 1].
(ii) When X is a normed vector space, a convex set D ⊂ X with nonempty interior is strongly star-shaped relative to any u 0 ∈ int(D), this fact is also known as the line segment principle (see [RW98, Theorem 2.33, p. 58]). Moreover if D ⊂ X is strongly star-shaped relative to all u 0 ∈ D then D is convex. An example of strongly star-shaped set which is not necessarily convex is given by the union of two different convex sets

D 1 ∪ D 2 with int(D 1 ∩ D 2 ) = ∅, indeed if u 0 ∈ int(D 1 ∩ D 2 ) then for each u ∈ D 1 ∪ D 2 either u ∈ D 1 or u ∈ D 2 , so tu + (1 -t)u 0 ∈ D 1 or tu + (1 -t)u 0 ∈ D 2 for all t ∈ [0, 1[ since D 1
and D 2 are convex with nonempty interior and then strongly star-shaped relative to u 0 .

Proposition 2.1. Let f : X →] -∞, ∞] be a convex function. Let D ⊂ domf and u 0 ∈ D. Then f is ru-usc in D ⊂ domf relative to u 0 ∈ D.
Proof. By convexity of f it is easy to see that for all t ∈ [0, 1[

∆ 1+|f (u0)| f,D,u0 (t) = sup u∈D f (tu + (1 -t)u 0 ) -f (u) 1 + |f (u 0 )| + |f (u)| ≤ 1 -t which shows, by letting t → 1, that f is ru-usc in D relative to u 0 .
For each set D ⊂ X we denote by χ D the indicator function of D given by

χ D (u) := 0 if u ∈ D ∞ if u ∈ X \ D.
Remark 2.3. If a set D ⊂ X is strongly star-shaped relative to u 0 ∈ D then χ D is ru-usc relative to u 0 .

We denote by f the lower semicontinuous envelope of f given by

f (u) = lim v→u f (v) := sup U∈V(u) inf v∈U f (v)
where V(u) denotes the set of neighborhoods of u ∈ X.

The convergence of a sequence {u n } n ⊂ X to u with respect to the topology of X is denoted by u n →u. We denote by f s the sequential relaxation of f given by

f s (u) = inf lim n→∞ f (u n ) : X ∋ u n →u .
Remark 2.4. It is easy to see that f ≤ f and f = f . It is worth to note that f is sequentially lower semicontinuous, i.e., for every

{u n } n ⊂ X and u ∈ X if u n → u then lim n→∞ f (u n ) ≥ f (u). We have f ≤ f s ≤ f and in general f s s is different from f s .
For each u 0 ∈ domf the radial extension f u0 : X → [-∞, ∞] relative to u 0 is defined by

f u0 (u) := lim t↑1 f (tu + (1 -t)u 0 ) where lim t↑1 f (tu + (1 -t)u 0 ) = inf lim n→∞ f (t n u + (1 -t n )u 0 ) : [0, 1[∋ t n → 1 .
Remark 2.5. The effective domain of f u0 satisfies dom f u0 ⊂ domf s ⊂ domf , indeed, if we consider u ∈ dom f u0 then for some {t n } n ∈ [0, 1[ such that lim n→∞ t n = 1, we have by Remark 2.4

∞ > f u0 (u) = lim t↑1 f (tu + (1 -t)u 0 ) = lim n→∞ f (t n u + (1 -t n )u 0 ) ≥ f s (u) ≥ f (u). since t n u + (1 -t n )u 0 → u as n → ∞.

Main results

3.1. Radial representation on the boundary of a strongly star-shaped set. Here is the main result of the paper which establishes a radial representation of the lower semicontinuous envelope of a ru-usc function penalized by a strongly star-shaped subset.

Theorem 3.1. Let f : X →]-∞, ∞] be a ru-usc function in a strongly star-shaped set D ⊂ domf relative to u 0 ∈ D. Assume that inf D f > -∞, we have

(i) if f + χ D = f on D then f + χ D = f u0 + χ D ; (ii) f u0 (u) = lim t↑1 f (tu+(1-t)u 0 ) for all u ∈ D, and f u0 is ru-usc in D∩dom f u0 . Remark 3.1. The condition in Theorem 3.1 (i), i.e. f + χ D = f on D, means that f is lower semicontinuous in D in the sense that lim D∋v→u f (v) = f (u) for all u ∈ D. Thus Theorem 3.1 (i) can be rewritten as ∀u ∈ D lim D∋v→u f (v) = f (u) =⇒ ∀u ∈ ∂D lim D∋v→u f (v) = lim t↑1 f (tu + (1 -t)u 0 ).
Proof of Theorem 3.1 Proof of (i). Fix u ∈ D. We have (1t)u 0 + tu ∈ D for all t ∈ [0, 1[ since D is strongly star-shaped relative to u 0 . Hence

f u0 (u) = lim t↑1 f (tu + (1 -t)u 0 ) = lim t↑1 f (tu + (1 -t)u 0 ) + χ D (tu + (1 -t)u 0 ) ≥ f + χ D (u).
It remains to prove that

f u0 + χ D ≤ f + χ D .
It is equivalent to show that for every δ > 0 and every u ∈ D we have

f u0 (u) < δ whenever f + χ D (u) < δ. Fix δ > 0 and u ∈ D such that f + χ D (u) < δ. Then there exists η > 0 such that for every U ∈ V(u) it holds inf v∈U (f + χ D ) (v) = inf v∈U∩D f (v) ≤ δ -2η. (3.1) For each U ∈ V(u) there exists v U ∈ U ∩ D (Note that U ∩ D = ∅ for any U ∈ V(u) since u ∈ D.) such that f (v U ) < inf v∈U∩D f (v) + η ≤ δ -η (3.2) since (3.1). Let {t n } n ∈ [0, 1[ be such that lim n→∞ t n = 1, and for every n ∈ N ∆ a f,D,u0 (t n ) ≤ 1 n + 1 (3.3) since f is ru-usc in D relative to u 0 . Fix U ∈ V(u). By (3.2) and (3.3) we have f (t n v U + (1 -t n )u 0 ) ≤ ∆ a f,D,u0 (t n ) (a + |f (v U )|) + f (v U ) (3.4) ≤ 1 n + 1 a + max -inf D f, δ -η + δ -η.
On the other hand, for every n ∈ N it holds

f (t n v U + (1 -t n )u 0 ) ≥ inf v∈U∩D f (t n v + (1 -t n )u 0 ).
We have

t n u + (1 -t n )u 0 ∈ D for all n ∈ N since D is strongly star-shaped relative to u 0 . So, by using (3.4), the assumption f + χ D = f on D we obtain for every n ∈ N δ -η ≥ sup U∈V(u) inf v∈U∩D f (t n v + (1 -t n )u 0 ) = f + χ D (t n u + (1 -t n )u 0 ) = f (t n u + (1 -t n )u 0 ).
Letting n → ∞ we find that f u0 (u) ≤ δη, which completes the Proof of (i).

Proof of (ii). We first have to prove that for every u ∈ D lim

t→1 - f (tu + (1 -t)u 0 ) = lim t→1 -f (tu + (1 -t)u 0 ). Fix u ∈ D. It suffices to prove that (3.5) lim t→1 Ψ(t) ≤ lim t→1 Ψ(t).
where

Ψ(t) := f (tu + (1 -t)u 0 ) for all t ∈ [0, 1]. Without loss of generality we can assume that lim t→1 Ψ(t) < ∞. Choose two sequences {t n } n , {s n } n ⊂]0, 1[ such that 1 t n → 1, s n → 1, tn sn < 1 for all n ∈ N, and lim t→1 Ψ(t) = lim n→∞ Ψ(t n ); lim t→1 Ψ(t) = lim n→∞ Ψ(s n ).
Since D is strongly star-shaped relative to u 0 we have t n u + (1t n )u 0 ∈ D for all n ∈ N, so we can assert that for every n ∈ N

Ψ(t n ) = Ψ t n s n s n (3.6) = f t n s n (s n u + (1 -s n )u 0 ) + 1 - t n s n u 0 ≤ ∆ a f,D,u0 t n s n (a + |Ψ(s n )|) + Ψ(s n ).
We have that (3.5) follows from

(3.6) by letting n → ∞ since f is ru-usc in D relative to u 0 . It remains to prove that f u0 is ru-usc in D ∩ dom f u0 . Fix t ∈ [0, 1[ and u ∈ D ∩ dom f u0 .
By the first part of the Proof of (ii) we can assert that

f u0 (u) = lim s→1 f (su + (1 -s)u 0 ) f u0 (tu + (1 -t)u 0 ) = lim s→1 f (s(tu + (1 -t)u 0 ) + (1 -s)u 0 ).
1 Once the sequences {tn}n, {sn}n ⊂]0, 1[ satisfying tn → 1, sn → 1 choosen, we can extract a subsequence {s σ(n) }n such that tn s σ(n)

< 1 for all n ∈ N. Indeed, it suffices to consider the increasing map σ : N → N defined by σ(0) := min{ν ∈ N : sν > t 0 } and σ(n + 1) := min{ν ∈ N : ν > σ(n) and sν > t n+1 }.

So, we have

f u0 (tu + (1 -t)u 0 ) -f u0 (u) a + | f u0 (u)| = lim s→1 f (t(su + (1 -s)u 0 ) + (1 -t)u 0 ) -f (su + (1 -s)u 0 ) a + |f (su + (1 -s)u 0 )| ≤ ∆ a f,D,u0 (t). It follows that ∆ a f,D∩dom fu 0 ,u0 (t) ≤ ∆ a f,D,u0 (t)
{v n } n ⊂ D such that v n → u as n → ∞. We say that D ⊂ X is a sequentially strongly star-shaped set relative to u 0 ∈ D, if tD s + (1 -t)u 0 ⊂ D for all t ∈ [0, 1[.
Here is a sequential version of Theorem 3.1.

Theorem 3.2. Let f : X →]-∞, ∞] be a ru-usc function in a strongly star-shaped set D ⊂ domf relative to u 0 ∈ D. Assume that inf D f > -∞, we have (i) if f + χ D s = f on D then f + χ D s = f u0 + χ D s ; (ii) f u0 (u) = lim t↑1 f (tu + (1 -t)u 0 ) for all u ∈ D s , and f u0 is ru-usc in D s ∩ dom f u0 .
Proof. For the sake of completeness we give the proof of (i) although very similar to the one of Theorem 3.1 (i). Fix u ∈ D s . Let {t n } n ⊂ [0, 1[ such that lim n→∞ t n = 1 and

f u0 (u) = lim n→∞ f (t n u + (1 -t n )u 0 ).
We have (1t n )u 0 + t n u ∈ D for all n ∈ N since D is strongly star-shaped relative to u 0 . Hence

f u0 (u) = lim n→∞ f (t n u + (1 -t n )u 0 ) = lim n→∞ f (t n u + (1 -t n )u 0 ) + χ D (t n u + (1 -t n )u 0 ) ≥ f + χ D s (u) since t n u + (1 -t n )u 0 → u as n → ∞. It remains to prove that f u0 + χ D s ≤ f + χ D s . Fix δ > 0 and u ∈ D s such that f + χ D s (u) < δ. So we can find η ∈]0, δ[ and a sequence {v n } n ⊂ D such that v n → u and lim n→∞ f (v n ) ≤ δ -η.
Choose a subsequence {v n } n ⊂ D (not relabelled) such that

v n → u and |f (v n )| ≤ max -inf D f, δ -η for all n ∈ N. (3.7) Let {t k } k ⊂ [0, 1[ such that lim k→∞ t k = 1, and for every k ∈ N ∆ a f,D,u0 (t k ) ≤ 1 k + 1 (3.8)
since f is ru-usc in D relative to u 0 . So, by (3.7) and (3.8), for every k, n ∈ N we have

f (t k v n + (1 -t k )u 0 ) ≤ ∆ a f,D,u0 (t k ) (a + |f (v n )|) + f (v n ) (3.9) ≤ 1 k + 1 a + max -inf D f, δ -η + δ -η.
We have t k u + (1t k )u 0 ∈ D for all k ∈ N since D is strongly star-shaped relative to u 0 . Letting n → ∞ in (3.9) and using the assumption f + χ D = f on D we obtain for every k ∈ N

f (t k u + (1 -t k )u 0 ) = f + χ D (t k u + (1 -t k )u 0 ) ≤ 1 k + 1 a + max -inf D f, δ -η + δ -η
Letting k → ∞ we find that f u0 (u) ≤ δη, which completes the Proof of (i).

The proof of (ii) is the same as the proof of Theorem 3.1 (ii).

General consequences

4.1. Radial representation with the effective domain as constraint. When D = domf we have the following result.

Corollary 4.1. Let f : X →] -∞, ∞] be a function such that f is ru-usc in the strongly star-shaped set domf relative to u 0 ∈ domf . If g : X →] -∞, ∞] is such that f = g on domf and inf domf g > -∞ then f = g u0 + χ domf
where g u0 (u) = lim t↑1 g(tu + (1t)u 0 ) for all u ∈ domf .

Proof. Since f = g on domf and domf is strongly star-shaped relative to u 0 ∈ domf the function g is ru-usc in domf relative to u 0 . Thus applying Theorem 3.1 (ii) we obtain for every u ∈ domf

g u0 (u) = lim t→1 - g(tu + (1 -t)u 0 ).
Now, we have to prove that f = g u0 + χ domf . It is easy to see that

f ≤ f + χ domf ≤ f + χ domf hence f + χ domf = f since f + χ domf = f and f = f . Apply Theorem 3.1 (i) with
f in place of f and D = domf , we obtain f + χ domf = f = f u0 + χ domf . Taking account of Remark 2.5 we deduce that

f = f u0 + χ domf .
It remains to prove that f u0 = g u0 on domf . Fix u ∈ domf , then tu + (1t)u 0 ∈ domf for all t ∈ [0, 1[ since domf is strongly star-shaped relative to u 0 . It follows that

f u0 (u) = lim t↑1 f (tu + (1 -t)u 0 ) = lim t↑1 g(tu + (1 -t)u 0 ) = g u0 (u)
since f = g on domf , which completes the proof.

Remark 4.1. The previous result can be useful in relaxation problems, indeed, in practice we are able to prove an integral representation of f , say g, on domf only. Then we can use Corollary 4.1 to have a representation on domf . To obtain a full integral representation on domf , we have then to commute "lim t↑1 " with the integration in the radial limit g u0 (see for instance Theorem6.1).

Analysis similar to that in the proof of Corollary 4.1 gives the following sequential version.

Corollary 4.2. Let f : X →] -∞, ∞] be a function such that f s is ru-usc in the strongly star-shaped set domf relative to u 0 ∈ domf . If g : X →] -∞, ∞] is such that f s = g s = g on domf and inf domf g > -∞ then

f s = g u0 + χ domf s
where g u0 (u) = lim t↑1 g(tu + (1t)u 0 ) for all u ∈ domf s .

In the following, we state a consequence of Corollary 4.1 and Corollary 4.2 in the particular case where g is replaced by f .

Corollary 4.3. Let f : X →] -∞, ∞] be a function such that f (resp. f s ) is ru-usc in the strongly star-shaped set domf relative to u 0 ∈ domf . If f = f (resp. f s = f ) on domf and inf domf f > -∞ then f = f u0 (resp. f s = f u0 ).
Proof. Apply Corollary 4.1 (resp. Corollary 4.2) with f in place of g, we obtain

f = f u0 + χ domf (resp. f s = f u0 + χ domf s ).
To finish the proof it suffices to see that dom f u0 ⊂ domf s ⊂ domf since Remark 2.5.

We examine the case f convex and bounded below.

Corollary 4.4. Let f : X →] -∞, ∞] be a convex function. If there exists u 0 ∈ X such that f is bounded above in a neighborhood of u 0 and inf int(domf ) f > -∞ then f = f u0 . (4.1)
Moreover f u0 = f v for all v ∈ int(domf ) (where int(domf ) is the interior of domf ).

Proof. The assumption implies that f is continuous on int(domf ) the interior of domf . So, f + χ int(domf ) = f on int(domf ). By Proposition 2.1 a convex function is ru-usc in int(domf ) relative to all v ∈ int(domf ). It is well known that int(domf ) is convex, then by Remark 2.2 (ii) the set int(domf ) is strongly star-shaped relative to all v ∈ int(domf ). By applying Theorem 3.1 we find f = f v + χ int(domf ) . On the other hand it holds that domf ⊂ domf = int(domf ) since domf is convex. Therefore (4.1) holds since Remark 2.5. Remark 4.2. In fact equality (4.1) still holds for convex functions which are not bounded below. When X has finite dimension, more general results involving convexity exist, see for instance [Roc70, Theorem 7.5 p. 57, Theorem 10.3 p. 85]. Indeed, in finite dimension, the relative interior of domf is not empty whenever domf = ∅ and f is continuous on it, so (4.1) holds without any assumption on f unless to be convex.

4.2.

Minimization with strongly star-shaped constraints. The following result deals with minimization problems with strongly star-shaped constraints, it can be seen as a nonconvex version of [FL07, Corollary 4.41, p. 272].

Corollary 4.5. Let f : X →] -∞, ∞] be a function. Let D ⊂ domf be a strongly star-shaped set relative to u 0 ∈ D such that D ⊂ domf . Assume that f :

X → ] -∞, ∞] is ru-usc in D relative to u 0 . If f + χ D = f on D then inf D f = inf D f.

Proof. Without loss of generality we can assume that inf

D f > -∞. It is sufficient to show that inf D f ≤ inf D f . By applying Theorem 3.1 we have inf D f = inf X f + χ D = inf D f u0 . (4.2)
Now we claim that for every u ∈ D we have f u0 (u) ≤ f (u), indeed,

f u0 (u) = lim t↑1 f (tu + (1 -t)u 0 ) ≤ lim t↑1 ∆ a f,D,u0 (t)(a + |f (u)|) + f (u) ≤ f (u)
since f is ru-usc in D relative to u 0 . We deduce from (4.2) that inf D f ≤ inf D f, and the proof is complete.

The following result can be useful in scalar problems of the calculus of variations when the lower semicontinuous envelope f of a nonconvex f is convex.

Corollary 4.6. Let f : X →] -∞, ∞] be such that f is convex. Let D ⊂ domf be a strongly star-shaped set relative to u 0 ∈ D such that D ⊂ domf . Then inf D f = inf D f .
Proof. We have

f ≤ f + χ D ≤ f + χ D .
Thus f + χ D = f on D. By Proposition 2.1 f is ru-usc in D ⊂ domf relative to any u 0 ∈ D, so we can apply Corollary 4.5 with f in place of f . The proof is complete.

Operations on ru-usc functions

In this section we study the stability of ru-usc functions with respect to some operations. We also give some examples of class of ru-usc functions. 5.1. Stability of ru-usc functions with respect to pointwise sum and product. We need the following result in the proof of Proposition 5.1.

Lemma 5.1. Let f : X →] -∞, ∞] be a ru-usc function in D ⊂ domf relative to u 0 ∈ D. Then (i) f + c is ru-usc in D relative to u 0 for all c ∈ R;
(ii) λf is ru-usc in D relative to u 0 for all λ ∈ R + .

Proof. Proof of (i). Fix u ∈ D and c ∈ R. Fix ε > 0. There exists

t ε ∈]0, 1[ such that sup t∈]tε,1[ ∆ a f,D,u0 (t) < ε since f is ru-usc in D relative to u 0 . We set f c := f + c. Then for every t ∈]t ε , t[ we have f c (tu + (1 -t)u 0 ) -f c (u) = f (tu + (1 -t)u 0 ) -f (u) (5.1) ≤ ∆ a f,D,u0 (t)(a + |f (u)|) ≤ ε(a + |f c (u)| + |c|).
It follows that lim t→1 ∆ a+|c| fc,D,u0 (t) ≤ ε. The proof of (i) is complete by letting ε → 0. Proof of (ii). Fix u ∈ D and λ ∈ R + . Fix ε > 0. There exists t ε ∈]0, 1[ such that sup t∈]tε,1[ ∆ a f,D,u0 (t) < ε since f is ru-usc in D relative to u 0 . We set f λ := λf . Then for every t ∈]t ε , t[ we have

f λ (tu + (1 -t)u 0 ) -f λ (u) = λ (f (tu + (1 -t)u 0 ) -f (u)) ≤ ∆ a f,D,u0 (t)(λa + |f λ (u)|) ≤ ε max{λa, 1}(1 + |f λ (u)|).
It follows that lim t→1 ∆ 1 f λ ,D,u0 (t) ≤ ε max{λa, 1}. The proof of (ii) is complete by letting ε → 0.

The stability for the operations sum and product (pointwise) of ru-usc functions is specified below.

Proposition 5.1. Let f, g : X →] -∞, ∞] be two ru-usc functions in D ⊂ domf ∩ domg relative to u 0 ∈ D. (i) If inf D f > -∞ and inf D g > -∞ then f + g is ru-usc in D relative to u 0 ; (ii) If inf D f > 0 and inf D g > 0 then f g is ru-usc in D relative to u 0 .
Proof. Proof of (i). Assume first that f ≥ 0 and g ≥ 0 on D. Fix ε > 0. There exists

t ε ∈]0, 1[ such that sup t∈]tε,1[ ∆ a f,D,u0 (t) < ε (resp. sup t∈]tε,1[ ∆ b g,D,u0 (t) < ε) since f (resp. g) is ru-usc in D relative to u 0 . Fix t ∈]t ε , 1[ and u ∈ D. We have f (tu + (1 -t)u 0 ) ≤ ε (a + f (u)) + f (5.2) g(tu + (1 -t)u 0 ) ≤ ε (b + g(u)) + g(u),
(5.3) so by adding (5.2) with (5.3) we obtain

f (tu + (1 -t)u 0 ) + g(tu + (1 -t)u 0 ) ≤ δ(ε)(1 + f (u) + g(u)) + f (u) + g(u)
where δ(ε) := ε max{a + b, 1} and satisfies lim ε→0 δ(ε) = 0. Therefore

lim t→1 ∆ 1 f +g,D,u0 (t) ≤ δ(ε)
which gives the result by letting ε → 0. We now remove the restrictions made on f and g and we set m := inf D f +inf D g. We denote by f + := f -inf D f and g + := g-inf D g. By Lemma 5.1 (i) the functions f + and g + are ru-usc in D relative to u 0 , so by applying the first part of the Proof of (i) the function f + + g + is ru-usc in D relative to u 0 . But f + + g + + m = f + g, so again by applying Lemma 5.1 we find that f + g is ru-usc in D relative to u 0 . Proof of (ii). By taking the product of (5.2) with (5.3) we obtain

f (tu + (1 -t)u 0 )g(tu + (1 -t)u 0 ) ≤ δ(ε)(1 + f (u) + g(u) + f (u)g(u)) + f (u)g(u)
(5.4) where δ(ε) := max ε, ε 2 max{ab, 2a, 2b, 3} and satisfies lim ε→0 δ(ε) = 0. But

f (u) + g(u) ≤ f (u)g(u) 1 inf D f + 1 inf D g . (5.5)
From (5.4) and (5.5) we deduce that

f (tu + (1 -t)u 0 )g(tu + (1 -t)u 0 ) ≤δ(ε) 1 + 1 inf D f + 1 inf D g (1 + f (u)g(u)) + f (u)g(u), so lim t→1 ∆ 1 f g,D,u0 (t) ≤ δ(ε) 1 + 1 infD f + 1 infD g
which gives the result by letting ε → 0.

Remark 5.1. The Proposition 5.1 (ii) answers to the question whether class of ruusc functions contains more than convex functions, indeed it is sufficient to consider two finite positive convex functions such that their pointwise product is not convex.

Example 5.1. Assume that X is a normed space. Let g : X → R be a function satisfying:

(A 1 ) there exist α ≥ 0 and a function δ : [0, 1] → R satisfying lim t→1 δ(t) ≤ 0 such that for every t ∈]0, 1[ and every u ∈ X

|g(tu + (1 -t)u 0 ) -g(u)| ≤ δ(t)(1 + u α + u 0 α );
(A 2 ) there exist c > 0, c ′ ≥ 0, and β ≥ α such that for every u ∈ X c u βc ′ ≤ g(u);

then g is ru-usc in D relative to u 0 . Indeed, by (A 2 ) we have

u α ≤ u β + 1 ≤ 1 c (g(u) + c ′ ) + 1. Set a := c ′ + c(2 + u 0 α
) then it is easy to deduce from (A 1 ) that for every u ∈ D and every t ∈ [0, 1[

g(tu + (1 -t)u 0 ) -g(u) ≤ δ(t) c (a + g(u)) .
Therefore ∆ a g,D,u0 (t) ≤ δ(t) c which shows, by letting t → 1, that g is ru-usc in D relative to u 0 . Note also that inf X g > -∞.

Corollary 5.1. Assume that X is a normed vector space. Let f :

X →] -∞, ∞] be a ru-usc function in D ⊂ domf relative to u 0 ∈ D. If inf D f > -∞ and if g : X →] -∞, ∞] satisfies (A 1 ) and (A 2 ) then f + g is ru-usc in D relative to u 0 .
Remark 5.2. Corollary 5.1 can be seen as stability of ru-usc functions with respect to a type of "radial Hölder" perturbation.

The following result is an alternative to the Proposition 5.1 (i).

Proposition 5.2. Let f, g : X →] -∞, ∞] be two ru-usc functions in D ⊂ domf ∩ domg relative to u 0 ∈ D. If g is bounded on D, i.e., sup u∈D |g(u)| < ∞ then f + g is ru-usc in D relative to u 0 .
Proof. Fix ε > 0. There exists t ε ∈]0, 1[ such that sup t∈]tε,1[ ∆ a f,D,u0 (t) < ε (resp. sup t∈]tε,1[ ∆ b g,D,u0 (t) < ε) since f (resp. g) is ru-usc in D relative to u 0 . Fix t ∈]t ε , 1[ and u ∈ D. We have

f (tu + (1 -t)u 0 ) ≤ ε (a + |f (u)|) + f (u) (5.6) g(tu + (1 -t)u 0 ) ≤ ε (b + |g(u)|) + g(u),
(5.7) so by adding (5.6) with (5.7) we obtain

f (tu + (1 -t)u 0 ) + g(tu + (1 -t)u 0 ) ≤ δ(ε)(1 + |f (u)| + |g(u)|) + f (u) + g(u) ≤ δ(ε)(1 + |f (u) + g(u)| + 2 sup u∈D |g(u)|) + f (u) + g(u) ≤ δ(ε) max 1, 2 sup u∈D |g(u)| (1 + |f (u) + g(u)|) + f (u) + g(u)
where δ(ε) := ε max{a + b, 1}, and satisfies lim ε→0 δ(ε) = 0. Then

lim t→1 ∆ 1 f +g,D,u0 (t) ≤ δ(ε) max 1, 2 sup u∈D |g(u)|
which gives the result by letting ε → 0.

Example 5.2. Assume that X is a normed vector space. Let D ⊂ X be a compact and strongly star-shaped set relative to u 0 ∈ D. Let g : X →] -∞, ∞] be a function which is continuous and finite on D. Then g is ru-usc in D relative to u 0 . Indeed, let ω : [0, ∞[→ R be defined by

ω(δ) = sup{|g(u) -g(v)| : u, v ∈ D and u -v < δ}.
We have lim δ→0 ω(δ) = 0 since g is continuous and D is compact. We have for every u ∈ D and every t ∈ [0, 1[

g(tu + (1 -t)u 0 ) -g(u) ≤ ω (1 -t) sup u∈D u -u 0 .
Therefore we have ∆ 1 g,D,u0 (t) ≤ ω ((1t) sup u∈D uu 0 ) for all t ∈ [0, 1[. Passing to the limit t → 1 we obtain that g is ru-usc in D relative to u 0 .

By using Example 5.2 and Proposition 5.2 we establish, in the following result, that the class of ru-usc functions are stable with respect to a continuous perturbation when D is strongly star-shaped and compact.

Corollary 5.2. Assume that X is a normed vector space and D ⊂ X is a compact and strongly star-shaped set relative to u 0 ∈ D. Let f : X →] -∞, ∞] be a ru-usc function in D ⊂ domf relative to u 0 . If g : X → R is a continuous function then f + g is ru-usc in D relative to u 0 .

5.2.

Inf-convolution of ru-usc functions. For two functions f, g :

X →]-∞, ∞] their inf-convolution is the function f ▽g : X → [-∞, ∞] defined by (f ▽g) (u) := inf v∈X {f (u -v) + g(v)} .
The following result establishes the conditions to keep the ru-usc property by the inf-convolution operation.

Proposition 5.3. Let f : X →]-∞, ∞] be a ru-usc function relative to u 0 ∈ domf . Let g : X →]-∞, ∞] be a ru-usc function relative to 0 ∈ domg. Then f ▽g is ru-usc relative to u 0 if one of the following conditions holds:

(i) inf X f > -∞ and inf X g > -∞; (ii) sup v∈domg |g(v)| < ∞. Proof. Proof of (i). Assume first that f ≥ 0 and g ≥ 0. Fix u ∈ domf ▽g. Choose {v n } n ⊂ domg such that f (u -v n )+ g(v n ) → (f ▽g) (u) as n → ∞. Fix ε > 0. There exists t ε ∈]0, 1[ such that sup t∈]tε,1[ ∆ a f,D,u0 (t) < ε (resp. sup t∈]tε,1[ ∆ b g,D,u0 (t) < ε) since f (resp. g) is ru-usc in D relative to u 0 . Fix t ∈]t ε , 1[. We have for every n ∈ N (f ▽g) (tu + (1 -t)u 0 ) ≤ f (t(u -v n ) + (1 -t)u 0 ) + g(tv n ) (5.8) ≤ ε(a + f (u + v n )) + ε(b + g(v n )) + f (u -v n ) + g(v n ) ≤ δ(ε)(1 + f (u -v n ) + g(v n )) + f (u -v n ) + g(v n ).
where δ(ε) := ε max{1, a + b} and satisfies lim ε→0 δ(ε) ≤ 0. Letting n → ∞ in (5.8) we obtain lim t→1 ∆ 1 f ▽g,u0 (t) ≤ δ(ε) which gives, by letting ε → 0, that f ▽g is ru-usc relative to u 0 .

We remove the restrictions on f and g. Set f + := f -inf X f and g + := g-inf X f . By Lemma 5.1 the function f + (resp. g + ) is ru-usc relative to u 0 (resp. relative to 0), so we apply the first part of the proof to have f + ▽g + is ru-usc relative to u 0 . But f + ▽g + + (inf X f + inf X g) = f ▽g, so again by Lemma 5.1 we deduce that f ▽g is ru-usc relative to u 0 .

Proof of (ii). Choose {v

n } n ⊂ domg such that f (u -v n ) + g(v n ) → (f ▽g) (u) as n → ∞. Fix t ∈]t ε , 1[. Then for every n ∈ N (f ▽g) (tu + (1 -t)u 0 ) ≤ f (t(u -v n ) + (1 -t)u 0 ) + g(tv n ) (5.9) ≤ ε(a + |f (u -v n )|) + ε(b + |g(v n )|) + f (u -v n ) + g(v n ) ≤ δ(ε)(1 + |f (u -v n )| + |g(v n )|) + f (u -v n ) + g(v n ) ≤ δ(ε) 1 + |f (u -v n ) + g(v n )| + 2 sup v∈domg |g(v)| + f (u -v n ) + g(v n )
where δ(ε) := ε max{1, a + b} and satisfies lim ε→0 δ(ε) = 0. Letting n → ∞ in (5.9) we obtain lim t→1 ∆ 1 f ▽g,u0 (t) ≤ δ(ε) 1 + 2 sup v∈domg |g(v)| which gives, by letting ε → 0, that f ▽g is ru-usc relative to u 0 .

If g = χ C with C ⊂ X a strongly star-shaped set relative to 0 ∈ C, then g is ruusc relative to 0 since Remark 2.3. By noticing that sup v∈domg |g(v)| = 0 < ∞, we may apply Proposition 5.3 (ii) to obtain that the function

X ∋ u → (f ▽χ C ) (u) = inf v∈C f (u -v) is ru-usc when f is ru-usc relative to u 0 ∈ domf . Corollary 5.3. Let f : X →] -∞, ∞] be a ru-usc function relative to u 0 ∈ domf .
Let C ⊂ X be a strongly star-shaped set relative to 0 ∈ C. Then f ▽χ C is ru-usc relative to u 0 . We say that D is weakly sequentially strongly star-shaped relative to 0 in W 1,p (Ω; R m ) when W 1,p (Ω; R m ) is endowed with the weak topology and D is sequentially strongly star-shaped relative to 0. We denote by D sw the sequential weak closure of D in W 1,p (Ω; R m ).

Application to the relaxation with constraints

The following result shows that the conditions (H 1 ) and (H 2 ) on S give rise to sequentially strongly star-shaped sets of the form D. Lemma 6.1. If S satisfies (H 1 ) and (H 2 ) then D is weakly sequentially strongly star-shaped relative to 0.

Proof. For every t ∈ [0, 1[ and every u ∈ D sw we have tu ∈ D since (H 2 ).

Example 6.1. It is not difficult to see that if S is convex with 0 ∈ int(S) then S satisfies (H 1 ) and (H 2 ). Indeed, using Mazur lemma we have ∇u(•) ∈ S a.e. in Ω. Then for every t ∈ [0, 1[ it holds t∇u(•) ∈ S a.e. in Ω since S is convex and 0 ∈ int(S).

We give an example of a family of nonconvex sets satisfying (H 1 ) and (H 2 ).

Example 6.2. Assume that m = d = 2. For each ε > 0 consider the set

S ε := ξ ∈ M 2×2 : ε + det(ξ) > tr(ξ) 2 .
We have for every ε > 0 (i) 0 ∈ S ε ( i.e. (H 1 ) is satisfied);

(ii) for every ξ ∈ S ε we have tξ ∈ S ε for all t ∈ [0, 1[; (iii) S ε is not convex;

(iv) S ε is not bounded;

(v) S ε is rank-one convex. Fix ε > 0. The set S ε satisfies (H 2 ) for all p > 2. Indeed, let {u n } n ⊂ W 1,p (Ω; R m ) be such that u n ⇀ u in W 1,p (Ω; R m ) and for every n ∈ N it holds ∇u n (•) ∈ S ε a.e. in Ω. Proof of (ii). Let t ∈ [0, 1[ and ξ ∈ S ε . We have det(tξ) = t2 det(ξ) ≥ t 2 (tr(ξ) 2 )t 2 ε > tr(tξ) 2ε.

Proof of (iii). Consider ξ :=

  Let d, m ≥ 1 be two integers and p ∈]1, ∞[. Let Ω ⊂ R d be a bounded open set with Lipschitz boundary. We denote by M m×d the space of m rows and d columns matrices.6.1. Star-shaped subsets in W 1,p (Ω; R m ). We consider the class of subsetsS ⊂ M m×d satisfying (H 1 ) 0 ∈ S; (H 2 ) for every sequence {u n } n ⊂ W 1,p (Ω; R m ) such that u n ⇀ u in W 1,p (Ω; R m ), iffor every n ∈ N we have ∇u n (•) ∈ S a.e. in Ω then for every t ∈ [0, 1[ it holds t∇u(•) ∈ S a.e. in Ω. Define D ⊂ W 1,p (Ω; R m ) by D := u ∈ W 1,p (Ω; R m ) : ∇u(x) ∈ S a.e. in Ω . (6.1)

  By a classical result (see[START_REF] Dacorogna | Direct methods in the calculus of variations[END_REF] Theorem 8.20, p. 395]) we havedet(∇u n (•)) ⇀ det(∇u(•)) in L p 2 (Ω; R m ). (6.2)The function tr(•) 2 is convex and continuous, so for every Borel set A ⊂ Ω we havelim n→∞ ˆA tr(∇u n (x)) 2 dx ≥ ˆA tr(∇u(x)) 2 dx. (6.3)Using (6.2) and (6.3) we find for almost all x ∈ Ω and ρ > 0ε + 1 |B ρ (x)| ˆBρ(x) det(∇u(y))dy ≥ 1 |B ρ (x)| ˆBρ(x)tr(∇u(y)) 2 dy, then by passing to the limit ρ → 0 we obtain ∇u(•) ∈ S ε a.e. in Ω. By (ii) we have t∇u(•) ∈ S ε a.e. in Ω for all t ∈ [0, 1[. The properties (i) and (iv) are immediate.

  and the proof is complete by letting t → 1. 3.2. Sequential version of Theorem 3.1. It is well known that if X has a countable base of neighborhoods of 0 then f s = f . For a subset D ⊂ X, we denote by D s the sequential closure of D, i.e., u ∈ D s if and only if there exists a sequence

ε -√ ε √ ε

It is easy to see that ξ, ζ ∈ S ε and 1 2 ξ + 1 2 ζ / ∈ S ε . Proof of (v). We have to show that tξ + (1t)ζ ∈ S ε for all t ∈]0, 1[ whenever ξ, ζ ∈ S ε satisfy rk(ξζ) ≤ 1. Property (v) follows by using the fact that det(•) is quasiaffine (see [START_REF] Dacorogna | Direct methods in the calculus of variations[END_REF]Example 5.21(i), p. 179]) and tr(•) 2 is convex. 6.2. Relaxation of multiple integrals with star-shaped constraints. Let L : M m×d → [0, ∞[ be a quasiconvex (in the sense of Morrey) integrand with p-polynomial growth, i.e., L satisfies

Our goal here is to give a representation of the lower semicontinuous envelope F in W 1,p (Ω; R m ) endowed with the strong topology of L p (Ω; R m ):

then for every u ∈ W 1,p (Ω; R m )

where D is given by (6.1).

for all ξ, ζ ∈ M m×d (see for instance [Dac08, Proposition 2.32, p. 51]). For every u ∈ D and every t ∈ [0, 1[

, the proof is complete by letting t → 1. Theorem 6.1. If S satisfies (H 1 ) and (H 2 ), and if L satisfies (H ′ 1 ) and (H ′ 2 ), then for every u ∈ W 1,p (Ω; R m )

Note that F = F sw since the coercivity condition (H ′ 2 ). So, it suffices to show that

We have J sw = J since (H ′ 1 ) and (H ′ 2 ) (see for instance [START_REF] Acerbi | Semicontinuity problems in the calculus of variations[END_REF]). Then it holds J + χ D sw = J on D, indeed we have

Using Lemma 6.2 and Lemma 6.1 we obtain by Theorem 3.1

It remains to prove that J 0 = J on D sw \D since

Using the polynomial growth (H ′ 2 ) we have for almost all x ∈ Ω sup

The integrand L is continuous since (6.4). We may apply the dominated convergence theorem to obtain

The proof is complete.

Remark 6.1. The equality (6.5), which can be rewritten as

looks natural since J is of "p-polynomial growth" (and lsc with respect to the strong topology in L p (Ω; R m )) and since the star-shaped property (of the constraints) can be seen as a kind of "regularity" on the constraints. An interesting further extension is to study whether similar equality holds when we replace the lsc envelope by a Γ-limit procedure and J by a sequence of funtionals {J n } n (for an interesting discussion about constrained problems see [DG79, p. 499]).


Jakob Puchinger
email: puchinger|raidl|koller@ads.tuwien.ac.at

Günther R Raidl

Gabriele Koller

Solving a Real-World Glass Cutting Problem

We consider the problem of finding two-dimensional cutting patterns for glass sheets in order to produce rectangular elements requested by customers. The number of needed sheets, and therefore the waste, is to be minimized. The cutting facility requires three-staged guillotineable cutting patterns, and in addition, a plan for loading produced elements on transportation wagons. The availability of only three loading docks for wagons imposes additional constraints on the feasibility of cutting patterns. We describe a greedy first fit heuristic, two branchand-bound based heuristics, and different variants of an evolutionary algorithm for the problem, and compare them on a set of real-world instances. The evolutionary algorithm is based on an order representation, specific recombination and mutation operators, and a decoding heuristic. In one variant, branch-and-bound is occasionally applied to locally optimize parts of a solution during decoding.

Introduction

In this paper we present methods developed for solving a cutting problem that appears in real-world glass manufacturing. Customer specified rectangular elements need to be cut out from raw stock sheets. Due to the mechanics of the cutting machine, only three-staged guillotine cuts are possible, and additional constraints regarding the order in which elements are cut, must be obeyed. The problem falls into the general category of two-dimensional bin packing (2BP) problems; according to the notation of Lodi et al. [START_REF] Lodi | Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems[END_REF] it can be classified as 2BP|R|G with additional constraints.

Our problem is enhanced by constraints resulting from the characteristics of the production process. A robot located at the end of the glass-cutting facility puts finished elements on wagons located at three different loading docks. The elements are partitioned in logical groups according to customer orders, and each wagon may carry elements from the same logical group only. Since the wagons cannot be exchanged arbitrarily, elements from a maximum of three logical groups can be produced in an intertwined way. A solution to our problem must also contain a schedule for loading finished elements onto wagons.

A detailed problem description is given in Sec. 2. Related methods from literature for solving the classical two-dimensional bin packing problem are summarized in Sec. and bound algorithms for our problem. Section 6 describes three variants of an evolutionary algorithm (EA). The different algorithms are experimentally evaluated and compared to each other and to a commercial solver in Sec. [START_REF] Hwang | On solving rectangle bin packing problems using GAs[END_REF]. In most cases, the EA yields the best results. More details on this work are given in [?].

Problem Description

In the two-dimensional three-staged Bin Packing problem with Wagon Scheduling (2BP-WS), we are given:

-Identical rectangular stock sheets of width W > 0, length L > 0, and thickness T > 0. -A set of rectangular element types E = {E 1 , . . . , E m } requested by customers; each element type E i , i = 1, . . . , m, is defined by the elements' width w i (0 < w i ≤ W ), length l i (0 < l i ≤ L), a logical group identifier g i indicating the customer to whom the elements are to be sent, and the number n i > 0 of instances needed of this type. Let n = m i=1 n i be the total number of elements.

-A minimum fill level B min > 0 and a maximum fill level B max ≥ B min for the transportation wagons; the fill level of a wagon is given by the cumulated thickness of the elements loaded on it.

The goal is to find patterns for cutting out all instances of the given element types from the smallest possible number of stock sheets, thus, minimizing the waste, and a schedule for loading produced elements to wagons. Elements may be rotated by 90 • . The production machine and loading robot impose the following restrictions on feasible cutting patterns.

Orthogonal guillotine cuts. Since glass sheets are cut by scratching and breaking them over a straight edge, only orthogonal guillotine cuts are possible, i.e. cuts parallel to a side of the piece being cut, going from one border straight to the opposite side.

Three stages. The production machine consists of three stages. The first stage only cuts a whole sheet horizontally into an arbitrary number of stripes. Stripes are further processed in the second stage where they are cut vertically into an arbitrary number of so-called stacks. The third stage performs, again, only horizontal cuts, producing the final elements (and waste) from the stacks. See Fig. 1 for an example of a three-stage cutting pattern.

Any feasible three-stage cutting pattern can always be reduced into its socalled normal form by moving each element to its uppermost and leftmost position, so that waste may only appear at the bottom of the stacks on the right of the rightmost stack in each stripe or at the bottom below the last stripe of each sheet. The pattern shown in Fig. 1 is in normal form. In the rest of the paper, we only consider cutting patterns in normal form, which reduces the general infinite search space of arbitrary three-stage cutting patterns to a finite number of possible solutions.

Wagon restrictions. For a given cutting pattern, elements are always produced by processing the stripes within each sheet from top to bottom, the stacks within each stripe from left to right, and the elements within a stack from top to bottom. The numbering of the elements in Fig. 1 denotes this order.

Finished elements are loaded on wagons in the same order as they are produced. Initially, three empty wagons are placed at three available loading docks. The following constraints apply to the loading of elements on wagons. Only cutting patterns, for which a loading schedule fulfilling the above requirements exists, are considered feasible.

Objective Function and Continuous Lower Bound

The primary objective is to minimize the number S(x) of sheets needed in a solution x. A refined objective function F (x) considers the last sheet only partly:

F (x) = S(x) - L -c l L , ( 1
)
where c l represents the position of the last stage-1 cut of the last sheet. This refined objective function allows for a better discrimination of the quality of solutions needing the same number of sheets: Cutting patterns leaving a larger unused stripe at the bottom of the last sheet are more promising. In practice, large unused final stripes may be useful later on and are therefore not necessarily considered as waste.

The continuous lower bound CLB for the objective function (S(x) as well as F (x)) is given by the total area of all elements divided by a sheet's area:

CLB = m i=1 l i • w i • n i L • W (2)
3 Previous Approaches to Two-Dimensional Bin Packing

In this section we give a brief overview of known algorithms for solving the twodimensional bin packing problem on which the new algorithms are based. For a more complete review we refer to the survey by Lodi et al. [START_REF] Lodi | Two-dimensional packing problems: A survey[END_REF] and to the annotated bibliography by Dyckhoff et al. [START_REF] Dyckhoff | Cutting and packing: An annotated bibliography[END_REF].

Most of the simple algorithms for 2BP are of greedy nature. The elements are placed one by one and never reconsidered again. There are one-and two-phase algorithms. In one-phase algorithms, the elements are directly placed in the bins. Two-phase algorithms first partition the elements into levels whose widths do not exceed W and whose total length is aimed to be minimized. In the second phase, levels are assigned to bins by heuristically solving a one-dimensional bin packing problem.

Berkey and Wang [START_REF] Berkey | Two-dimensional finite bin packing algorithms[END_REF] described the classical Finite First Fit (FFF) heuristic, which is a greedy one-phase algorithm. The elements are sorted by decreasing lengths. The first element initializes the first level in the first bin and defines the level's length. Each following element is added to the first level to which it fits respecting the sheet's width W . If there is no such level, a new level is initialized in the first bin into which it fits. If there is no such bin, a new bin is initialized with the new level. Within a level, elements are never stacked.

For the general 2BP problem, Martello and Vigo [START_REF] Martello | Exact solutions of the two-dimensional finite bin packing problem[END_REF] describe a branch-andbound (B&B) algorithm which is based on a two-level branching-scheme: The elements are assigned to the bins by an outer decision tree. Possible packing patterns for the bins are heuristically generated. Only if the heuristic is not able to place all the elements of a bin, a pattern is tried to be found by an inner enumeration scheme. Morabito and Arenales [START_REF] Morabito | Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach[END_REF] consider a staged and constrained guillotine cutting problem in which the utilization of only a single sheet is maximized. They describe a B&B algorithm whose decision tree corresponds to an AND/OR graph.

A broad overview of EAs for cutting and packing problems is given by Hopper [START_REF] Hopper | Two-Dimensional Packing Utilising Evolutionary Algorithms and Other Meta-Heuristic Methods[END_REF]. Most of the EAs used to solve guillotineable 2BP, such as the genetic algorithm described by Kröger [START_REF] Kröger | Guillotineable bin packing: A genetic approach[END_REF], are based on a slicing-tree representation and specific variation operators. Alternatively, an order-based encoding can be used indicating the order in which the elements are placed by some FFF-like decoding heuristic. Hwang et al. [START_REF] Hwang | On solving rectangle bin packing problems using GAs[END_REF] describe such an approach and compare it to a slicing-tree representation. They conclude that the order-based method yields better results in several cases. Corno et al. [START_REF] Corno | Optimizing Area Loss in Flat Glass Cutting[END_REF] apply the order-based encoding successfully to an industrial cutting problem with specific real-time and pattern constraints. Another effective order-based approach is presented by Monaci [START_REF] Monaci | Algorithms for Packing and Scheduling Problems[END_REF] for two-dimensional strip packing.

Lodi et al. [START_REF] Lodi | Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems[END_REF] describe a more general framework applicable to several variants of 2BP. Tabu search is used to assign the elements to the sheets, and cutting patterns for individual sheets are obtained by different inner heuristics.

Conclusions with respect to 2BP-WS. The algorithms presented so far cannot directly be applied to 2BP-WS because of the constraints imposed by the required wagon scheduling. Furthermore, several algorithms do not consider the restriction to three stages. The B&B algorithms, in particular, rely heavily on several symmetries of the general 2BP problem: Bins within a solution, levels within a bin, and elements within a level can be arbitrarily permuted. This is exploited by only considering levels and elements in specific orders. In case of 2BP-WS this simplification is not possible because the production order is a substantial part of the solution. Order-based EAs, however, do not principally rely on certain symmetries and can be adapted to our needs by modifying the decoding heuristic.

A Finite First Fit Heuristic for 2BP-WS (FFFWS)

The FFF heuristic from [START_REF] Berkey | Two-dimensional finite bin packing algorithms[END_REF] has been modified and extended for 2BP-WS. In contrast to the classical FFF heuristic and due to the wagon scheduling requirements, FFFWS constructs a solution sheet by sheet and stripe by stripe in a greedy way; i.e. once a new sheet (stripe) is started, previous sheets (stripes) are never reconsidered.

Let Π = (Π 1 , . . . , Π m ) be a list of references to the element types sorted according to decreasing lengths l i , and let |Π 1 |, . . . , |Π m | be the corresponding numbers of not yet placed elements; initially

|Π i | = n i .
The algorithm starts by placing a longest available element, i.e. an element of type Π 1 , at the upper left position of the first sheet. This element is said to initialize the sheet and the first stripe, and it also defines this stripe's length l. Whenever an element is placed, the corresponding counter

|Π i | is decreased; if |Π i | = 0, Π i is removed from the list Π.
The stripe is then iteratively filled from left to right with a stack of elements from the first type Π i in list Π fulfilling the following conditions: (a) l Π i ≤ l; (b) w i does not exceed the stripe's remaining width; (c) a permitted loading dock exists for elements of type Π i with respect to wagon scheduling (see below). The number of stacked elements is min(|Π i |, l/l Πi ). If no further element fits onto the current stripe, a new stripe is started with an element of the first type Π i in list Π for which l Πi does not exceed the sheet's remaining length and a permitted loading dock is available. If no such element exists and Π is not empty, a stripe on a new sheet is started in the same way.

FFFWS tries to determine a permitted loading dock for an element by considering the element's logical group g i and the current states of the wagons at the three loading docks. If g i appears as logical group of one of the wagons at the loading docks, then this loading dock is a permitted target. Otherwise, we look for a loading dock whose wagon is either empty or reached its minimum fill level B min . In the latter case, the wagon is closed and replaced by a new one. If a permitted loading dock could be determined, its identifier is stored as loading target for the element as part of the solution. Wagon changes need not explicitly be stored in this kind of greedy solutions, since they can be implicitly derived.

The possible rotation of elements is considered by maintaining for each element type two references Π i and Π i in Π with linked counters of not yet placed elements; hereby, Π i represents the rotated version of the element type.

In the worst-case, FFFWS has to process the complete list Π when looking for the next element to be placed. Therefore, the worst-case total time complexity of FFFWS is O(n • m).

5 Branch-and-Bound Algorithms for 2BP-WS Two different B&B strategies were devised. Since symmetries cannot be exploited as in case of the classical 2BP, it seems to be impossible to solve 2BP-WS instances of practical size to provable optimality. Therefore, the following B&B strategies also contain heuristics and cannot guarantee optimal solutions. BB-1. The first B&B variant follows the principle of the greedy two-phase algorithms for 2BP. In the first phase, BB-1 iteratively generates stripes of width W and length not exceeding L containing elements not yet placed on previous stripes. B&B is used to minimize the difference between the stripe's area and the total area of the elements on the stripe, i.e. the waste. Subproblems are created from partially filled stripes by considering any feasible extension by a single element or a stack of elements of the same type. A breadth-first enumeration strategy is applied. The waste of the currently best stripe is used as global upper bound. As local lower bound, the subproblem's waste reduced by the empty area to the right of the last stack is used. If during the construction of the stripe a wagon change involving also a change of the logical group occurs, we consider the stripe a delimiter.

In the second phase, stripes are arranged on sheets by an adapted first fit decreasing algorithm for one-dimensional bin packing [START_REF] Coffman | Approximation algorithms for bin packing: A survey[END_REF]. Due to wagon scheduling, only the order of stripes in sections between delimiters may be permuted.

BB-2.

In contrast to BB-1, BB-2 maximizes the utilized area of whole sheets instead of minimizing the waste of single stripes. The patterns for the sheets are generated one by one by B&B. New subproblems are created from partially filled sheets by considering any feasible extension by a single element or a stack of elements of the same type, if necessary on a new stripe. The FFFWS heuristic is applied to get an initial global lower bound for the utilized area. The local upper bound of a subproblem is calculated as the total area of already placed elements plus an upper bound for the area that might further be utilized. Additional elements may only be placed to the right of the last stack on the last stripe or below the last stripe. Again, a breadth-first enumeration strategy is applied.

Evolutionary Algorithms for 2BP-WS

The presented algorithms FFFWS, BB-1, and BB-2 yield respectable results in several cases. Nevertheless, independently optimized stripes or sheets, as in case of BB-1 and BB-2, do not guarantee an optimal overall solution. In order to approach the problem in a more global way, we apply evolutionary algorithms.

Representation and Decoding. Two variants of an order-based representation similar to those in [START_REF] Hwang | On solving rectangle bin packing problems using GAs[END_REF][START_REF] Corno | Optimizing Area Loss in Flat Glass Cutting[END_REF] were chosen to encode candidate solutions.

Element type representation. Solutions are encoded as ordered vectors of references to element types Π = (Π 1 , . . . , Π m ). The phenotypic solution is derived by applying a modified FFFWS heuristic as decoder. Instead of considering element types ordered by decreasing length, the order is given by the genotype. Furthermore, the decoding heuristic allows stacked elements to extend a stripe's length if the total waste of the stripe decreases.

Element representation. The element type representation has the disadvantage of placing elements of the same type always next to each other, if space permits. To allow more flexibility, we also consider an order-based representation in which a solution is encoded as permutation π = (π 1 , . . . , π n ) of references to each individual element. This can significantly increase the size of the genotype and the solution space in general. The element type representation's decoding heuristic has been adapted accordingly. In particular, elements of the same type may only be stacked by the decoding heuristic if they appear directly next to each other in the encoded solution.

Rotation of elements is in both representations handled by maintaining linked second references as in FFFWS. For simplicity, we neglect here the resulting changes in the genotype's length.

Recombination and Mutation. In principle, any standard recombination and mutation operator designed for permutations is feasible. Regarding recombination, order 3 crossover (OX3) [START_REF] Davis | A Handbook Of Genetic Algorithms[END_REF] turned out to be particularly well suited because it partially respects absolute positions and relative orders, which is a crucial condition for our problem.

Two mutation operators are used. Reciprocal exchange (RX) chooses two positions at random and swaps them. Block exchange (BX) swaps two randomly chosen non-overlapping blocks of length 2 R , with R being a random value in the interval (0, ld m 2 ] for the element type representation and (0, ld n 2 ] for the element representation. In this way, shorter blocks are chosen more likely, but large blocks up to half of the genotype's length are also possible.

Two additional operators were specifically designed for the element representation with the aim to encourage sequences of elements of the same type in order to exploit stacking more often.

Grouped order crossover (GOX) is an extension of the standard OX3 operator. As in OX3, two crossover points are randomly chosen. However, only positions inbetween elements of different types are allowed. The crossover region defined by the two crossover points is transmitted directly from the first parent Algorithm Grouping Mutation (π); j ← a random value ∈ {1, . . . , n}; // starting position p ← a random value ∈ [0, 1); // element moving probability left ← j -1; right ← j + 1; to the offspring. All remaining positions are filled with the remaining elements of the first parent in the order given by the second parent.

for i ← j -1, . . . ,
Grouping mutation (GM) is used to form larger sequences of elements of the same type. Figure 2 shows the algorithm in detail. A position j of the permutation π is randomly chosen as starting position. π is scanned and each element of the same type as π j is incorporated into the sequence around j with a probability chosen randomly from [0, 1).

The computational effort of both operators, GOX and GM, is linear in the number of elements.

EA Variants

The described operators were integrated in a standard steadystate EA. Initial solutions are created at random. In each iteration, a new candidate solution is created by always applying crossover and mutation. The new solution replaces the worst solution in the population if it is not identical to an already existing solution on the genotype level.

We consider the following three EA variants:

-EAet uses the element type representation.

-EAe uses the element representation.

-EAebb corresponds to EAe enhanced by phase 1 of BB-1: In the decoding, stripes are not just created by the greedy heuristic, but with a certain probability p bb by applying B&B.

In case of EAe and EAebb the order of the elements in a decoded solution is reencoded into the genotype in a Lamarckian manner with probability p wb .

Computational Results

31 real-world instances were provided by Soglatec GmbH and are available at http://www.ads.tuwien.ac.at/pub/TestProblems/glasscut. These instances have strongly varying characteristics: 1 to 31 logical groups, 1 to 78 element types, 4 to 651 elements in total, and continuous lower bounds CLB ranging from 0.34 to 23.90. We compare the greedy heuristic FFFWS, the B&B algorithms BB-1 and BB-2, the EA variants, and the commercial optimizer XOPTS of Albat & Wirsam GmbH. The new algorithms were implemented in C++ and tested on a Pentium 4 PC with 2.8 GHz. Results of XOPTS were provided by Soglatec GmbH and do not respect wagon scheduling. Thus, some of XOPTS' cutting patterns are actually infeasible for our specific 2BP-WS problem. Nevertheless, results from XOPTS provide an important basis for comparison, since 2BP-WS has not been addressed before.

In BB-2, due to memory and time restrictions, the enumeration for a sheet was aborted when the subproblem list exceeded 3 000 000 entries; the best cutting pattern so far was kept.

Strategy parameters of the EAs were determined by extensive preliminary experiments. A population size of 1 000 has been used, and each run was terminated after 50 000 iterations without improvement of the best solution. The number of mutations applied to each new candidate solution is chosen as a Poisson-distributed random variable with expected value 2.

Each EA variant has been tested with different combinations of the presented recombination and mutation operators. In some experiments more than one mutation operator was applied with equal probability; for each mutation the operator to be used was chosen at random. For each EA configuration, 30 independent runs per instance have been carried out.

Average results over all instances obtained by selected algorithm variants are listed in Table 1. Shown are average solution qualities (F ), corresponding average standard deviations (σ) for the EAs, solution qualities relative to the continuous lower bounds F/CLB , average total running times t, and the number of instances for which the algorithm yielded the best solution on average. It can be observed that average solution qualities do in general not differ very much. FFFWS is the fastest, but usually provides poor results. While BB-1 yields on average the worst results, the solutions of BB-2 are significantly better. However BB-2 also suffers from the greedy nature of optimizing each sheet independently; it is slow and highly memory consuming for larger instances; occasionally, the B&B optimization of some sheets had to be prematurely aborted. BB-2 yields sometimes better, but on average worse results than XOPTS.

In general, the EA variants obtained the best solutions and needed only moderate running times. As expected, EAet is significantly faster than EAe due to its smaller search space. EAebb is slower than EAe due to its B&B optimization of stripes. EAebb with GOX, the combination of all three mutation operators, Lamarckian write-back with probability p wb = 10% and B&B optimization of stripes applied with a probability of p bb = 10% performed best with respect to solution quality.

Table 2 provides more detailed results on each of the 31 instances for FFFWS, BB-1, BB-2 and a choice of EA configurations. For the EAs, columns F avg list average solution values over 30 runs per instance, and columns F min show solution values of the best runs.

It turns out that not a single EA configuration is consistently best for all tested instances. On average, however, the element representation yielded significantly better results than the element type representation on 9 instances, and in case of the element representation, GOX outperformed OX3. Lamarckian write-back with probability p wb = 10% generally increases the quality of final solutions. Regarding mutation, the combined application of RX, BX, and GM, proved to be slightly more robust than only applying RX. The B&B optimization of stripes as done in EAebb increases the quality of solutions a bit further. A Wilcoxon rank test indicates a significant improvement between solutions from EAe and EAebb with p bb = 10% (GOX, p wb = 10%, and combined mutation used in both cases) on an error level of less than 1% for 6 instances.

Two examples for cutting patterns obtained by FFFWS and EAebb for instance 12 are shown in Fig. 3.

Conclusion

We considered different heuristic algorithms for a real-world glass cutting problem, in which the loading of produced elements imposes difficult constraints on feasible cutting patterns. Therefore, approaches for 2BP such as XOPTS cannot be used directly. The proposed FFFWS heuristic is fast and well suited as decoder for an order-based EA. For the EA with element representation, GOX and GM were proposed to encourage sequences of elements of the same type in order to better exploit the possibility of stacking. Incorporating B&B in the decoding for occasionally locally optimizing stripes turned out to increase the solution quality in a few cases. Solutions obtained by the EA are highly satisfactory for practice.

3 . 3 Fig. 1 .

 331 Fig.1. An example for a three-stage cutting pattern in normal form.

Fig. 3 .

 3 Fig. 3. Cutting patterns for instance 12 obtained by FFFWS (a) and EAebb with GOX, combined RX/BX/GM mutation, p bb = 10%, and p wb = 10%.

  1 do if type of element π i = type of element π j then with probability p do swap (π i , π left ); left ← left -1; for i ← j + 1, . . . , n do if type of element πi = type of element πj then with probability p do swap (πi, π right ); right ← right + 1; Fig. 2. Grouping mutation operator for the element representation.

Table 1 .

 1 Summarized results of selected algorithms; CLB = 6.010; * denotes that the mutation operator was randomly chosen among RX, BX, and GM; the value printed after the mutation type represents p wb ; for EAebb the last value represents p bb .

	algorithm	F	σF F/CLB	t[s]	best
	XOPTS	7.195	n.a.	1.1967	n.a.	15
	FFFWS	7.896	n.a.	1.3191	0.02	2
	BB-1	8.280	n.a.	1.3213	0.07	6
	BB-2	7.711	n.a.	1.2320 285.23	13
	EAet OX3	7.132 0.032	1.1857 16.79	14
	EAet OX3,RX	7.110 0.023	1.1833 13.88	18
	EAe OX3,RX	7.122 0.040	1.1828 46.05	17
	EAe OX3,RX,10%	7.089 0.032	1.1813 60.46	17
	EAe GOX,RX	7.114 0.032	1.1821 47.54	17
	EAe GOX,*	7.108 0.032	1.1815 46.57	17
	EAe GOX,RX,10%	7.079 0.025	1.1803 47.62	18
	EAe GOX,*,10%	7.080 0.026	1.1802 48.26	18
	EAe GOX,*,100%	7.174 0.058	1.1868 37.45	15
	EAebb GOX,*,10%,1% 7.079 0.027	1.1796 69.49	19
	EAebb GOX,*,10%,10% 7.076 0.019	1.1791 267.18	21

Table 2 .

 2 Detailed results of selected algorithms. Overall best (average) solution values are printed bold. For BB-2, a mark "a" in column F indicates that in one or more runs B&B had to be aborted for one or more sheets. .47 0.01 4.66 0.03 4.24 141.53 a 4.17 0.00 4.16 7.51 4.17 0.01 4.16 13.15 4.17 0.01 4.16 .00 10.24 8.73 10.24 0.00 10.24 15.51 10.24 0.00 10.24 32.07 17 15 23 60 6.88 7.89 8.68 0.01 8.41 0.03 7.88 257.48 7.87 0.08 7.79 21.57 7.89 0.11 7.79 40.12 7.80 0.04 7.67 258.81 18 11 11 61 4.40 4.58 5.15 0.03 5.57 0.02 4.88 2689.97 a 4.64 0.01 4.57 8.80 4.60 0.02 4.56 23.92 4.56 0.01 4.55 .00 6.93 8.24 6.93 0.00 6.93 26.48 6.93 0.00 6.93 43.35 21 29 31 72 5.28 5.68 5.96 0.02 6.66 0.14 5.89 209.92 a 5.68 0.03 5.63 29.18 5.75 0.05 5.67 45.60 5.73 0.05 5.64 830.37 22 31 31 72 5.28 5.65 5.96 0.00 6.66 0.15 5.89 215.79 a 5.67 0.02 5.64 27.41 5.75 0.05 5.67 43.25 5.75 0.04 5.68 1493.95 23 10 15 77 15.42 18.84 26.49 0.01 20.53 0.03 19.28 621.53 a 18.53 0.00 18.53 12.58 18.53 0.00 18.53 30.77 18.55 0.01 18.53 .09 0.02 2.00 0.02 2.00 44.96 a 1.98 0.00 1.98 7.97 1.98 0.00 1.98 19.78 1.98 0.00 1.98 106.90 25 2 2 91 4.98 5.40 5.89 0.02 5.53 0.01 5.40 2.88 5.66 0.00 5.66 6.57 5.49 0.00 5.49 28.73 5.48 0.01 5.45 33.32 26 15 78 140 23.90 30.87 32.69 0.02 38.70 0.95 36.56 127.96 30.09 0.47 29.50 78.44 29.82 0.35 29.19 131.76 29.80 0.30 29.45 3484.31 27 3 4 147 8.00 8.89 9.16 0.01 9.60 0.03 8.89 382.09 a 9.15 0.00 9.15 12.81 8.92 0.04 8.89 69.13 8.89 0.00 8.89 78.42 28 11 45 149 22.85 28.62 32.62 0.02 37.62 0.38 36.62 979.34 a 28.63 0.02 28.62 29.53 28.63 0.02 28.62 66.87 28.63 0.02 28.62 315.66 29 6 13 151 3.53 3.78 4.00 0.02 4.19 0.05 3.75 398.56 a 3.70 0.01 3.68 17.03 3.71 0.01 3.68 63.18 3.70 0.01 3.66 178.21 30 8 15 151 9.68 10.43 10.93 0.03 12.59 0.03 11.34 387.25 a 10.62 0.02 10.58 23.00 10.49 0.04 10.44 103.95 10.49 0.02 10.47 354.93 31 7 7 651 21.54 23.88 23.79 0.05 26.32 0.14 24.28 2173.64 a 23.56 0.00 23.56 39.88 23.44 0.01 23.44 600.92 23.56 0.01 23.53 796.30

	CLB XOPTS FFFWS BBHEU BBALG EAet OX3,RX EAe GOX,*,10% EAebb GOX,*,10%,10%	inst. groups m n F F t F t F t Favg σ Fmin tavg Favg σ Fmin tavg Favg σ Fmin tavg	1 3 3 4 0.83 0.98 1.37 0.01 0.98 0.00 0.98 0.01 0.98 0.00 0.98 2.93 0.98 0.00 0.98 7.87 0.98 0.00 0.98 6.89	2 3 3 4 0.90 0.95 0.97 0.02 0.95 0.00 0.95 0.01 0.95 0.00 0.95 2.70 0.95 0.00 0.95 8.46 0.95 0.00 0.95 7.62	3 3 3 5 0.58 0.74 0.83 0.01 0.86 0.00 0.74 0.01 0.74 0.00 0.74 2.40 0.74 0.00 0.74 4.19 0.74 0.00 0.74 4.88	4 3 3 6 2.17 2.88 2.88 0.02 2.88 0.00 2.88 0.01 2.88 0.00 2.88 5.01 2.88 0.00 2.88 7.21 2.88 0.00 2.88 8.78	5 1 2 7 0.69 0.80 0.99 0.02 0.83 0.01 0.80 0.01 0.81 0.00 0.81 3.41 0.80 0.00 0.80 5.85 0.80 0.00 0.80 6.17	6 2 3 9 2.60 2.87 2.96 0.01 3.54 0.01 2.87 0.01 2.87 0.00 2.87 2.97 2.87 0.00 2.87 4.79 2.87 0.00 2.87 4.43	7 2 7 11 0.34 0.40 0.46 0.01 0.41 0.01 0.46 15.38 a 0.38 0.00 0.38 4.15 0.38 0.00 0.38 6.84 0.38 0.00 0.38 15.41	8 3 14 14 1.61 1.91 2.48 0.01 2.53 0.01 1.88 8.72 1.85 0.01 1.84 5.39 1.85 0.01 1.84 9.56 1.86 0.02 1.84 14.23	9 12 12 15 0.76 0.84 0.99 0.03 0.83 0.01 0.99 25.21 a 0.83 0.00 0.83 4.40 0.83 0.00 0.83 7.69 0.83 0.00 0.83 34.43	10 3 7 19 2.08 2.44 2.47 0.00 2.67 0.01 2.44 64.67 a 2.44 0.00 2.44 6.25 2.44 0.00 2.44 10.21 2.44 0.00 2.44 25.87	11 3 5 22 2.50 5.56 5.56 0.02 5.56 0.00 5.56 12.11 a 5.56 0.00 5.56 13.64 5.56 0.00 5.56 22.57 5.56 0.00 5.56 22.14	12 12 12 33 3.50 3.98 4.67 0.00 4.60 0.01 3.94 28.22 3.96 0.00 3.96 10.43 3.95 0.01 3.93 19.01 3.94 0.01 3.93 30.57	13 1 16 33 3.65 4.70 458.23	14 3 24 34 6.72 4.47 7.66 0.02 7.66 12.04 7.69 0.06 7.66 18.68 7.66 0.00 7.66 60.19 8.77 8.39 0.01 8.39 0.02 7.66	15 5 9 37 2.80 31.35 2.97 0.00 2.97 5.57 2.95 0.00 2.95 11.18 2.95 0.00 2.95 50.96 2.96 3.48 0.01 3.58 0.03 2.96	16 9 9 53 7.86 2.43 10.24 070.26 10.56 10.78 0.02 12.56 0.02 11.56	19 7 9 69 7.63 16.66 8.39 0.01 8.39 9.69 8.25 0.03 8.22 28.83 8.27 0.01 8.22 51.44 8.22 8.94 0.01 9.54 0.02 8.54	20 1 1 70 5.56 0.03 6.93 082.57 6.97 8.68 0.02 6.93 0.00 6.93	24 4 4 78 1.78 1.99 2

This work is supported by the Austrian Science Fund (FWF) under grant P16263-N04.