Michele Conforti
email: conforti@math.unipd.it

Gérard Cornuéjols

Aris Daniilidis
email: arisd@dim.uchile.cl

Claude Lemaréchal
email: claude.lemarechal@inria.fr

Jérôme Malick
email: jerome.malick@inria.fr

Cut-generating functions and S -free sets

Keywords: Integer programming, Convex analysis, Separation, Generalized gauges, S-free sets MSC2000 Subject Classification: Primary: 52A41, 90C11, Secondary: 52A40 OR/MS subject classification: Primary: Combinatorics, Convexity, Secondary: Cutting plane Conforti, Cornuéjols, Daniilidis, Lemaréchal, Malick: Cut-generating functions

We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (cgf) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to S-free sets and we study this relation, disclosing several definitions for minimal cgf's and maximal S-free sets. Our work unifies and puts in perspective a number of existing works on S-free sets; in particular, we show how cgf's recover the celebrated Gomory cuts.

1. Introduction. In this paper, we consider sets of the form

X = X(R, S) := x ∈ R n + : Rx ∈ S , (1a)
where R = [r 1 . . . r n ] is a real q × n matrix , S ⊂ R q is a nonempty closed set with 0 / ∈ S .

In other words, our set X is the intersection of a closed convex cone with a pre-image by a linear mapping. This model goes back to [START_REF] Johnson | Characterization of facets for multiple right-hand side choice linear programs[END_REF], where S was a finite set: constraints Rx = b were considered for several righthand sides b. Here, we rather consider a general (possibly infinite) set S and a varying constraint matrix R. The closed convex hull of X does not contain 0 (see Lemma 2.1 below) and we are then interested in separating 0 from X: we want to generate cuts, i.e. inequalities that are valid for X, which we write as c ⊤ x 1 , for all x ∈ X .

(2)

1.1 Motivating examples. Our first motivation comes from (mixed) integer linear programming.

Example 1.1 (An integer linear program) Let us first consider a pure integer program, which consists in optimizing a linear function over the set defined by the constraints

Dz = d ∈ R m , z ∈ Z p + . (3)
Set n := p-m, assume the matrix D to have full row-rank m and select m independent columns (a basis).

The corresponding decomposition z = (x, y) into non-basic and basic variables amounts to writing the above feasible set as the intersection of Z n × Z m with the polyhedron

P := (x, y) ∈ R n + × R m + : Ax + y = b (4)
for suitable m × n matrix A and m-vector b.

Relaxing the nonnegativity constraint on the basic variables y, we obtain the classical corner polyhedron [START_REF] Gomory | Some polyhedra related to combinatorial problems[END_REF], namely the convex hull of (x, y) ∈ Z n + × Z m : Ax + y = b . This model has the form (1) if we set

q = n + m , R = I -A , S = Z n × Z m -{b} , (5)
where Z m -{b} denotes the translation of Z m by the vector -b. Assuming b / ∈ Z m , the above S is a closed set not containing the origin.

For m = 1, (4) has a single constraint n j=1 a j x j + y = b , y ∈ Z , x ∈ Z n + ;

the celebrated Gomory cut [START_REF] Gomory | An algorithm for integer solutions to linear programs[END_REF] is

j:fj f0 f j f 0 x j + j:fj >f0 1 -f j 1 -f 0 x j 1 , (6)
where f j = a j -⌊a j ⌋ and f 0 = b -⌊b⌋. Inequality ( 6) is valid for the corner polyhedron and cuts off the basic solution (x = 0, y = b). In the x-space R n , this inequality is a cut as defined in [START_REF] Averkov | On maximal S-free sets and the Helly number of the family of S-convex sets[END_REF]. We will demonstrate in Example 2.8 how to recover such a cut from our formalism.

Except for the translation by the basic solution (0, b), S is quasi instance-independent. This is actually a crucial feature; it determines the approach developed in this paper, namely cut-generating functions to be developed below.

Example 1.2 (A mixed-integer linear program)

In our integer program [START_REF] Balas | Disjunctive programming[END_REF], let us now relax not only nonnegativity of the basic variables but also integrality of the non-basic variables: the corner polyhedron is further relaxed to the convex hull of (x, y) ∈ R n + × Z m : Ax + y = b . We are still in the context of (1) with q = m , R = -A , S = Z mb ; this is the model considered in [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF] for m = 2, and in [START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF] for general m. Other relevant references are [START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF][START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF][START_REF] Dey | Constrained infinite group relaxations of mips[END_REF][START_REF] Gomory | Some continuous functions related to corner polyhedra i[END_REF][START_REF] Johnson | Characterization of facets for multiple right-hand side choice linear programs[END_REF]. This type of relaxation can be used when (3) becomes a mixed-integer linear program

Dz = d ∈ R m , z 0 , z j ∈ Z , j ∈ J ,
where J is some subset of {1, . . . , p}. Extract a basis as before and choose a subset of basic variables indexed in J; call m ′ m the number of rows in this restriction and b ′ ∈ R m ′ the resulting restriction of b (in other words, ignore a number mm ′ of linear constraints). Relax nonnegativity of the m ′ remaining basic variables, as well as integrality of the non-basic variables indexed in J. This results in [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF], with

q = m ′ , R = -A , S = Z m ′ -b ′ .
Any cut for this set X is a fortiori a valid inequality for the original mixed-integer linear program.

When m ′ = 1, a classical example of such inequalities is j:aj >0 a j f 0

x jj:aj <0

a j 1 -f 0 x j 1 . (7)
Actually, Gomory's mixed-integer cuts [START_REF] Gomory | An algorithm for integer solutions to linear programs[END_REF] combine [START_REF] Basu | Convex sets and minimal sublinear functions[END_REF] for the integer non-basic variables with the above formula for the continuous ones.

Model [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF] occurs in other areas than integer programming and we give another example.

Example 1.3 (Complementarity problem) Still using P of (4), let E ⊂ {1, 2, . . . , m} × {1, 2, . . . , m} and C := {y ∈ R m + : y i y j = 0 , (i, j) ∈ E} (in this paper, ⊂ stands for inclusion and for strict inclusion).

The set of interest is then P ∩ (R n × C). It can be modeled by [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF] where q = m , R = -A , S = Cb .

Cuts have been used for complementarity problems of this type, for example in [START_REF] Júdice | A complementarity-based partioning and disjujnctive cut algorithm for mathematical programming problems with equilibrium constraints[END_REF].

We will retain from these examples the dissymetry between S (a very particular and highly structured set) and R (an arbitrary matrix). Keeping this in mind, we will consider that (q, S) is given and fixed, while (n, R) is instance-dependent data: our cutting problem can be viewed as parametrized by (n, R). This point of view is natural for the last two examples; but some pre-processing (to be seen in Example 2.8) is needed to apply it to Example 1.1: by [START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF], S does depend on the data through its dimension q, which depends on n.

1.2 Introducing cut-generating functions. To generate cuts in the present situation, it would be convenient to have a mapping, taking instances of (1) as input, and producing cuts as output. What we need for this is a function R q ∋ r → ρ(r) ∈ R which, applied to the columns r j of a q × n matrix R (an arbitrary matrix, with an arbitrary number of columns) will produce the n coefficients c j := ρ(r j ) of a cut [START_REF] Averkov | On maximal S-free sets and the Helly number of the family of S-convex sets[END_REF]. We stress the fact that ρ must assign a number ρ(r) to any r ∈ R q : the function ρ is defined on the whole space.

Thus, we require from our ρ to satisfy

x ∈ X =⇒ n j=1 ρ(r j )x j 1 , (8)
for every instance X of (1). Such a ρ can then justifiably be called a cut-generating function (cgf).

The notation ρ refers to representation, which will appear in Definition 2.6 below. One of the most well-known cut-generating functions in integer programming is the so-called Gomory function [START_REF] Gomory | An algorithm for integer solutions to linear programs[END_REF], which we presented in Examples 1.1 and 1.2. The corresponding cuts can be generated quickly, so they are a powerful tool in computations; indeed, they drastically speed up integer-programming solvers [START_REF] Bixby | Progress in computational mixed integer programming -a look back from the other side of the tipping point[END_REF].

So far, a cgf is a rather abstract object, as it lies in the (vast!) set of functions from R q to R; but the following observation allows a drastic reduction of this set.

Remark 1.4 (Dominating cuts) Consider in (2) a vector c ′ with c ′ j c j for j = 1, . . . , n; then c ′⊤ x c ⊤ x whenever x 0. If c ′ is a cut, it is tighter than c in the sense that it cuts a bigger portion of R n + . We can impose some "minimal" character to a cgf, in order to reach some "tightness" of the resulting cuts.

With this additional requirement, the decisive Theorem 2.3 below will show that a cgf can be imposed to be convex positively homogeneous (and defined on the whole of R q ; positive homogeneity means ρ(tr) = tρ(r) for all r ∈ R q and t > 0). This is a fairly narrow class of functions indeed, which is fundamental in convex analysis. Such functions are in correspondence with closed convex sets and in our context, this correspondence is based on the mapping ρ → V defined by

V = V (ρ) := r ∈ R q : ρ(r) 1 , (9)
which turns out to be a cornerstone: via Theorem 2.5 below, [START_REF] Caprari | Conically equivalent convex sets and applications[END_REF] establishes a correspondence between the cgf's and the so-called S-free sets. As a result, cut-generating functions can alternatively be studied from a geometric point of view, involving sets V instead of functions ρ. This situation, common in convex analysis, is often very fruitful. With regard to Remark 1.4, observe that V (ρ) increases when ρ decreases: small ρ's give large V 's. However the converse is not true because the mapping in ( 9) is many-to-one and therefore has no inverse. A first concern will therefore be to specify appropriate correspondences between (cut-generating) functions and (S-free) sets.

1.3 Scope of the paper. The aim of the paper is to present a formal theory of minimal cutgenerating functions and maximal S-free sets, valid independently of the particular S. Such a theory would gather and synthetize a number of papers dealing with the above problem for various special forms for S: [START_REF] Lovász | Geometry of numbers and integer programming[END_REF][START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF][START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF][START_REF] Dey | Constrained infinite group relaxations of mips[END_REF][START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF][START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF] and references therein. For this, we use basic tools from convex analysis and geometry. Readers not familiar with this field may use [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF] (especially its Chap. C) for an elementary introduction, while [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF][START_REF] Rockafellar | Convex Analysis[END_REF] are more complete.

The paper is organized as follows.

-Section 2 states more accurately the concepts of cgf's and S-free sets.

-Section 3 studies the mapping [START_REF] Caprari | Conically equivalent convex sets and applications[END_REF]. We show that the pre-images of a given V (the representations of V ) have a unique largest element γ V and a unique smallest element µ V ; in view of Remark 1.4, the latter then appears as the relevant inverse of ρ → V (ρ). -In Section 4, we study the correspondence V ↔ µ V . We show that different concepts of minimality come into play for ρ in Remark 1.4. Geometrically they correspond to different concepts of maximality for V . -We also show in Section 5 that these minimality concepts coincide in a number of cases.

-Finally we have a conclusion section, with some suggestions for future research.

The ideas in Sections 2 and 3 extend in a natural way the earlier works mentioned above. However, Sections 4 and 5 contain new results.

2. Cut-generating functions: definitions and first results. We begin with making sure that our framework is consistent. We will use conv (X) [resp. conv (X)] to denote the convex hull [resp. closed convex hull] of a set X. Lemma 2.1 With X given as in (1), 0 / ∈ conv (X).

Proof. Assume X = ∅, otherwise we have nothing to prove. Since 0 does not lie in the closed set S, there is ε > 0 such that s ∈ S implies s 1 ε; and by continuity of the mapping x → Rx, there is η > 0 such that x 1 η for all x ∈ X ⊂ R n + . This means

x 1 = n j=1 |x j | = n j=1
x j η , for all x ∈ X .

In other words, the hyperplane j x j η separates 0 from X, hence from conv (X).

Remember that we are interested in functions ρ satisfying [START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF] for any (n, R) in [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF]. There are too many such functions, we now proceed to specify which exactly are relevant.

2.1 Sublinear cut-generating functions suffice. The following lemma, inspired from Claim 1 in the proof of [START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF]Lem. 23], is instrumental for our purpose. Lemma 2.2 Let ρ be a cgf. For all sets of K vectors r k ∈ R q and nonnegative coefficients α k , the following relation holds:

K k=1 α k r k = 0 =⇒ K k=1 α k ρ(r k ) 0 .
Proof. Call e ∈ R q the vector of all ones and α ∈ R K the vector of α k 's; take t 0 and define the vectors in R K+q Then pick s ∈ S; make an instance of (1) with n = K + q and R := r 1 . . . r K | D(s) , where the q × q matrix D(s) is the diagonal matrix whose diagonal is the vector s. Observing that

R(x + td) = t k α k r k + D(s)e = s ,
x + td is feasible in the resulting instance of (1a): (8) becomes

t K k=1 α k ρ(r k ) 1 -z ,
where z is a fixed number gathering the result of applying ρ to the columns of D(s). Letting t → +∞ proves the claim. Now we introduce some notation. The domain and epigraph of a function ρ : R q → R ∪ {+∞} are dom ρ := r ∈ R q : ρ(r) < +∞ and epi ρ := (r, z) ∈ R q+1 : z ρ(r) .

If dom ρ is the whole of R q (i.e., ρ(r) is a finite real number for all r ∈ R q ), we say that ρ is finite-valued; a convex finite-valued function is continuous on R q . A function is said to be sublinear if it is convex and positively homogeneous; or equivalently if its epigraph is a convex cone. The conical hull cone (epi ρ) of epi ρ is the set of nonnegative combinations of points (r, z) ∈ epi ρ:

r = K k=1 α k r k , z = K k=1 α k z k , with z k ρ(r k ) , α k 0 , k = 1, . . . , K ,
where K is an arbitrary integer. This conical hull is itself the epigraph of a sublinear function ρ, called the sublinear hull of ρ. Its value at r is the smallest possible of the above z's:

ρ(r) := inf K k=1 α k ρ(r k ) : K k=1 α k r k = r, α k 0 . ( 10
)
Of course ρ ρ; in the spirit of Remark 1.4, our next result establishes that a cgf can be improved by taking its sublinear hull.

Theorem 2.3 If ρ is a cgf, then ρ of (10) is nowhere -∞ and is again a cgf.

Proof. Express every r ∈ R q as a nonnegative combination:

k α k r k -r = 0, hence (Lemma 2.2) K k=1 α k ρ(r k ) + ρ(-r) 0 and ρ(r) -ρ(-r) > -∞.
Then take an instance R = [r j ] n j=1 of (1b). If it produces X = ∅ in (1a), there is nothing to prove. Otherwise fix x ∈ X.

Any positive decomposition r j = k α j,k r j,k of each column of R satisfies

s := Rx = n j=1 xj r j = n j=1 xj K k=1 α j,k r j,k = R + x + ,
where x + ∈ R nK denotes the vector with coordinates α j,k xj 0 and R + the matrix whose nK columns are r j,k . Then R + is a possible instance of (1b) and R + x + = s ∈ S, so the cgf ρ separates x + from 0:

1 j,k ρ(r j,k ) α j,k xj ) = n j=1 K k=1 α j,k ρ(r j,k ) xj . ( 11
)
Apply the definition of an infimum: for each ε > 0 we can choose our decompositions (r j,k , α j,k ) so that K k=1 α j,k ρ(r j,k ) ρ(r j ) + ε , for j = 1, . . . , n which yields with (11)

1 n j=1 ρ(r j ) + ε xj = n j=1 ρ(r j )x j + ε n j=1 xj .
Since ε is arbitrarily small -while x is fixed -we see that ρ does satisfy [START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF].

In view of Remark 1.4, Theorem 2.3 allows us to restrict our attention to cgf's that are sublinear; and their domain is the whole space by definition. We are now in a position to explain the use of the operation (9) in our context.

2.2 Cut-generating functions as representations. From now on, a cgf ρ will always be understood as a (finite-valued) sublinear function. By continuity and because ρ(0) = 0, V (ρ) in ( 9) is a closed convex neighborhood of 0 in R q . Besides, its interior and boundary are respectively

int (V (ρ)) = {r ∈ V : ρ(r) < 1} , bd (V (ρ)) = {r ∈ V : ρ(r) = 1} . ( 12
)
This follows from the Slater property ρ(0) = 0 (see, e.g., [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]Prop. D.1.3.3]); it can also be checked directly:

-by continuity, ρ(r) < 1 implies ρ(r) 1 for r close to r; -by positive homogeneity, ρ(r) = 1 implies ρ(r) = 1 + ε for r = (1 + ε)r.

The relevant neighborhoods for our purpose are the following: Definition 2.4 (S-free set) Given a closed set S ⊂ R q not containing the origin, a closed convex neighborhood V of 0 ∈ R q is called S-free if its interior contains no point in S: int (V ) ∩ S = ∅.

Let us make clear the importance of this definition.

Theorem 2.5 Let the sublinear function ρ : R q → R and the closed convex neighborhood V (of 0 ∈ R q ) satisfy (9). Then ρ is a cgf for (1) if and only if V is S-free.

Proof. Let V be S-free; in view of [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF], ρ(r) 1 for all r ∈ S. In particular, take a q × n matrix R, x ∈ X of (1a) and set r := Rx ∈ S. Then, using sublinearity,

1 ρ(Rx) = ρ n j=1 x j r j n j=1 x j ρ(r j ) ; ρ is a cgf.
Conversely, suppose V is not S-free: again from [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF], there is some r 1 ∈ S such that ρ(r 1 ) < 1. Take in (1b) the instance (n, R) = (1, [r 1 ]). Then 1 ∈ X (r 1 ∈ S), so c 1 := ρ(r 1 ) < 1 cannot be a cut. This allows a new definition of cgf's, much more handy than the original one: Definition 2.6 (cgf as representation) Let V ⊂ R q be a closed convex neighborhood of the origin. A representation of V is a finite-valued sublinear function ρ such that

V = r ∈ R q : ρ(r) 1 . ( 13
)
We will say that ρ represents V .

A sublinear cut-generating function for (1) is a representation of an S-free set.

A finite-valued sublinear function ρ represents a unique V = V (ρ), well-defined by [START_REF] Gomory | An algorithm for integer solutions to linear programs[END_REF]. One easily checks monotonicity of the mapping V (•):

ρ ρ ′ =⇒ V (ρ) ⊃ V (ρ ′ ) . (14)
Conversely, one may ask whether a given closed convex neighborhood of the origin V always has a representation. In fact, (13) fixes via [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF] the value ρ(r) = 1 on the boundary of V ; whether this set of prescribed values can be extended to make a sublinear function on the whole of R q is not obvious. This will be the subject of Section 3, where we will see that this is indeed possible; there may even be infinitely many extensions, and we are interested in the small ones. Now we illustrate the material introduced so far with some examples.

Examples.

We start with a simple 1-dimensional example supporting the claim that the mapping ρ → V of ( 13) is many-to-one -or equivalently that a given V may have several representations. they are convex when α β.

Example 2.7 With q = 1, consider V = ] -∞, 1]. In
Taking r = 1 ∈ V in (13) imposes α 1, while taking r = 1 + ε / ∈ V (ε > 0) imposes α > 1/(1 + ε). Altogether α = 1.
On the other hand, letting r → -∞, the property βr 1 imposes β 0.

Conversely, we easily see that, for any β ∈ [0, 1], the function ρ(r) = r for r 0 βr for r 0 is sublinear and satisfies [START_REF] Gomory | An algorithm for integer solutions to linear programs[END_REF]. Thus, the representations of V are exactly the functions of the form

ρ(r) = max {r, βr}, for β ∈ [0, 1].
This example suggests -and Lemma 3.2 will confirm -that nonuniqueness appears when V is unbounded.

Example 1.2 is quite suitable for illustration, Figure 1 visualizes it for q = m = 2. The dots are the set S = Z 2 -{b}. The stripe V of the left part, called a split set , is used in the framework of disjunctive cuts. Other neighborhoods can be considered, for example triangles (right part of the picture) as in [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF].

V S S V Figure 1: Two S-free sets for q = 2
With q = 1, no need for a picture and the calculations in Example 1.2 can be worked out. In this case, 1) with r = -a and S = Z -{b}. The only possible S-free neighborhoods of the origin are the segments r ∈ [-r -, r + ] with

X ⊂ R n + is defined by a ⊤ x ∈ Z -b, i.e. (
-f 0 = ⌊b⌋ -b -r -< 0 < r + ⌈b⌉ -b = 1 -f 0 .
For a representation ρ of this segment, the equations ρ(r + ) = 1 and ρ(-r -) = 1 fix in a unique way

ρ(r) = r r+ if r 0 , -r r- if r 0 .
Choose the extreme values for r + and r -to obtain

c j = ρ(-a j ) = aj f0 if a j 0 , -aj 1-f0 if a j 0 ,
which is just [START_REF] Bixby | Progress in computational mixed integer programming -a look back from the other side of the tipping point[END_REF].

Finally, let us show how Gomory cuts (6) can be obtained as cgf's.

Example 2.8 Still in Example 1.2, take q = m = 1; we want to separate the set defined by n j=1 a j x j + y = b , y ∈ Z , x ∈ Z n + from the origin (remember that b / ∈ Z). This set has the form (1) with

q = n + 1 , R = I -a ⊤ , S = Z n × Z -{b} .
Introduce the vector π ∈ R n+1 defined by π n+1 := 1 and, for j = 1, . . . , n:

π j := ⌊a j ⌋ if f j f 0 , ⌈a j ⌉ if f j > f 0
and its scalar product π ⊤ r = n j=1 π j x j + y with r = (x, y) ∈ R n+1 . Then define

V := r : ⌊b⌋ -b π ⊤ r ⌈b⌉ -b . (15)
The assumption b / ∈ Z implies that (0, 0) ∈ int (V ); therefore V is a closed convex neighborhood of the origin. Furthermore, V is S-free: in fact, b + π ⊤ r is an integer for every r = (x, y) ∈ S and therefore it cannot be strictly between the two consecutive integers ⌊b⌋ and ⌈b⌉. We claim that any representation of V produces Gomory cuts.

Call e j the jth unit vector of R n , so that the n columns of R are r j = e j -a j .

Direct calculations give

π ⊤ r j = ⌊a j ⌋ -a j = -f j if f j f 0 , ⌈a j ⌉ -a j = 1 -f j if f j > f 0 .
For each j = 1, . . . , n, consider three cases.

(i) If π ⊤ r j > 0 (which implies f j > f 0 ), there is t > 0 such that tπ ⊤ r j = ⌈b⌉ -b > 0, namely t = ⌈b⌉ -b π ⊤ r j = ⌈b⌉ -b ⌈a j ⌉ -a j = 1 -f 0 1 -f j . (ii) If π ⊤ r j < 0 (which implies 0 < f j f 0 ), there exists likewise t > 0 such that tπ ⊤ r j = ⌊b⌋ -b < 0, therefore t = f 0 f j . (iii) If π ⊤ r j = 0 (which implies a j ∈ Z), tr j ∈ V for any t > 0.
In (i) and (ii), the computed value of t puts tr j on the boundary of V . Let ρ represent V ; then by [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF] and positive homogeneity, ρ(r j ) = 1 t ρ(tr j ) = 1 t in cases (i), (ii) and ρ(r j ) = 0 in case (iii). Altogether,

ρ(r j ) = fj f0 if f j f 0 , 1-fj 1-f0 if f j > f 0
for j = 1, . . . , n; we recognize Gomory's formula [START_REF] Basu | Convex sets and minimal sublinear functions[END_REF].

As mentioned after Definition 2.6, the n values ρ(r j ) can be extended to make a sublinear function on the whole of R n+1 . This will be confirmed in the next section but can be accepted here, thanks to the simple form (15) of V : a stripe orthogonal to π. Indeed, the above calculations are designed so as to construct ρ(r) = 1 for each r such that π

⊤ r = ⌈b⌉ -b > 0 as in (i) [resp. π ⊤ r = ⌊b⌋ -b < 0 as in (ii)].
Then ρ(r) is given by positive homogeneity for any r such that π ⊤ r = 0; and ρ ≡ 0 on π ⊥ .

Largest and smallest representations.

In this section, we study the representation operation introduced in Definition 2.6. The main result is that our closed convex neighborhood V has a largest and a smallest representation. This result was already given in [START_REF] Caprari | Conically equivalent convex sets and applications[END_REF][START_REF] Basu | Convex sets and minimal sublinear functions[END_REF][START_REF] Zaffaroni | Convex radiant costarshaped sets and the least sublinear gauge[END_REF], with weaker assumptions in the latter work (which came to our knowledge only after the present paper was completed). Here we emphasize the geometric counterpart of the result, we put the proof of [START_REF] Basu | Convex sets and minimal sublinear functions[END_REF] in perspective, and we take advantage of our stricter assumptions to develop finer results that will be useful in sequel.

3.1 Some elementary convex analysis. First recall some basic theory (see, e.g., [17, Chap. C]), which will be central in our development. In what follows, V will always be a closed convex neighborhood of 0 ∈ R q .

A common object in convex analysis is the gauge

R q ∋ r → γ V (r) := inf {λ > 0 : r ∈ λV } , (16)
a (nonnegative) finite-valued sublinear function. Applying for example [17, Thm. C.1.2.5] with the notation (x, C, r) replaced by (r, V, 1), we obtain the relation

V = r ∈ R q : γ V (r) 1 .
Thus γ V represents V ; this first confirms that Definition 2.6 is consistent.

Another fundamental object is the support function of an arbitrary set G ⊂ R q , defined by

R q ∋ r → σ G (r) := sup d∈G d ⊤ r . ( 17
)
This function is easily seen to be sublinear, to grow when G grows, and to remain unchanged if G is replaced by its closed convex hull: σ G = σ conv (G) . Besides, it is finite-valued if (and only if) G is bounded.

Conversely, every (finite-valued) sublinear function σ is the support function of a (bounded) closed convex set, unambiguously defined by

G = G σ := d ∈ R q : d ⊤ r σ(r) for all r ∈ R q (18)
(note: G σ is closed and convex because it is an intersection of half-spaces; actually, G σ is just the subdifferential of σ at 0). We then say that σ supports G σ . The correspondence σ ↔ G defines a oneto-one mapping between finite-valued sublinear functions and bounded closed convex sets (the mapping σ → G of ( 18) extends to sublinear functions in R ∪ {+∞} but such an extension is not needed here).

Remark 3.1 (Primal-dual notation) Equation ( 17) involves two variables, d and r, both written as column-vectors; nevertheless, they lie in two mutually dual spaces. In this paper, we keep going back and forth between these two spaces; even though they are the same R q , we make a point to distinguish between the two. The notation r, V , . . . [resp. d, G, . . . ] will generally be used for primal elements [resp. for dual ones]. Most of the time, we will deal with support functions σ G (r) of dual sets; but we will also consider the support function σ V (d) of our primal neighborhood V .

Being finite-valued sublinear, the gauge of V supports a compact convex set, obtained by replacing σ by γ V in [START_REF] Johnson | Characterization of facets for multiple right-hand side choice linear programs[END_REF]. Since γ V 0, we guess from positive homogeneity that this set is just the polar of V :

d ∈ R q : d ⊤ r γ V (r) for all r ∈ R q = d ∈ R q : d ⊤ r 1 for all r ∈ V =: V • . (19)
Write [START_REF] Júdice | A complementarity-based partioning and disjujnctive cut algorithm for mathematical programming problems with equilibrium constraints[END_REF] as Now remember Example 2.7: V may have several representations. Any such representation ρ supports a set G ρ and we will see that the polar of G ρ is again V itself; G ρ is a pre-image of V for the polarity mapping. We thus obtain a new concept: a prepolar of V is a set G such that

V • = d ∈ R q : σ V (d) 1 to see that σ V represents V • ; thus, the support function of V is the gauge of V • , so that the polar of V • is V itself: (V • ) • = v.
G • := r ∈ R q : σ G (r) 1 = V , or equivalently σ G represents V .
The property (V • ) • = V means that the standard polar V • is itself a prepolar -which is somewhat confusing; and it turns out to be the largest one (Corollary 3.3 below); or equivalently, its support function σ V • = γ V turns out to be the largest representation of V . The main result of this section states that V has also a smallest prepolar, or equivalently a smallest representation (Proposition 3.6 below); keeping Remark 1.4 in mind, this is exactly what we want. This result is actually [6, Thm. 1]; here we use elementary convex analysis and we insist more on the geometric aspect.

Largest representation.

Introduce the recession cone V ∞ of V . Using the property 0 ∈ V , it can be defined as

V ∞ = {r ∈ R q : tr ∈ V for all t > 0} = λ>0 λV ,
and the second relation shows that V ∞ is closed; taking in particular λ = 1 shows that

V ∞ ⊂ V . (20)
One then easily sees from ( 16) that γ V (r) = 0 if r ∈ V ∞ . Yet, for any other representation ρ of V , (13) just imposes ρ(r) 0 at this r and we may a priori have ρ(r) < 0: the possible representations of V may differ on V ∞ ; see Example 2.7 again. We make this more precise.

Lemma 3.2 (Representations and recession cone) For all representations ρ of the closed convex neighborhood

V , ρ(r) 0 ⇐⇒ r ∈ V ∞ and ρ(r) < 0 =⇒ r ∈ int (V ∞ ) .
Besides, all representations coincide on the complement of int (V ∞ ) in R q .

Proof. By positive homogeneity, ρ(r) 0 implies ρ(tr) 0 < 1 (hence tr ∈ V ) for all t > 0; this implies r ∈ V ∞ . Conversely, ρ(r) > 0 implies ρ(tr) > 1 for t large enough: using 0 ∈ V again, r cannot lie in V ∞ .

To prove the second implication, invoke continuity of ρ: if ρ(r) < 0, ρ is still negative in a neighborhood of r, this neighborhood is contained in V ∞ .

Besides, take a half-line emanating from 0 but not contained in V ∞ ; it certainly meets the boundary of V , at a point r which is unique (see, e.g., [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]Rem. A.2.1.7]). By [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF], every representation ρ satisfies ρ(r) = 1; and by positive homogeneity, the value of this representation is determined all along the halfline. In other words, all possible representations of V coincide on the complement W of V ∞ ; and by continuity, they coincide also on the closure of W , which is the complement of int (V ∞ ).

φ ρ = γ V 0 V V∞ ρ γ V ≡ 0 ψ Figure 2: All representations coincide except in int (V ∞ )
Figure 2 illustrates the difference between the recession cone (where the gauge is "maximal") and the rest of the space (where it is the representation). Altogether, the gauge appears as the largest representation:

Corollary 3.3 (Maximality of the gauge) All representations ρ of V satisfy ρ γ V , with equality on the complement of int (V ∞ ).

Geometrically, all prepolars G are contained in the polar of V :

G • = V =⇒ G ⊂ V • .
In particular, V has a unique representation ρ = γ V (and a unique prepolar

V • ) whenever int (V ∞ ) = ∅.
Proof. Just apply Lemma 3.2, observing from ( 16) that the gauge is nonnegative.

Geometrically, the inequality between support functions becomes an inclusion: the set G supported by ρ is included in the set V • supported by γ V (see, e.g., [17,

Thm. C.3.3.1]).
The next subsection will use the support function σ V . It is positive on R q \{0}, and even more: for some ε > 0, V contains the ball B(ε) centered at 0 of radius ε, hence

ε d = σ B(ε) (d) σ V (d) for all d ∈ R q . ( 21
)
Then V • is bounded since the relation σ V (d) 1 implies d 1/ε.

Smallest representation.

The previous subsection dealt with polarity in the usual sense, viewing the gauge as a special representation. However, we are rather interested in small representations. Geometrically, we are interested in small prepolars, and the following definitions are indeed relevant:

V • := d ∈ V • : d ⊤ r = σ V (d) = 1 for some r ∈ V } , V • := d ∈ V • : σ V (d) = 1 . (22)
From [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF], [START_REF] Morán | On maximal S-free convex sets[END_REF] implies that the two sets are bounded. There is a slight difference between the two, suggested by Figure 2 and specified on Figure 3, where the dashed line represents them both. We see that d 1 lies in V • but not in V • ; and d 2 lies in both. On this example, V • is closed but Figure 5 will show that it need not be so.

V • = ∅ if V has a boundary, i.e. if V = R q . Obviously, V • ⊂ V • . Besides,
Although quite similar, we introduce the two sets for technical reasons, when proving that they have the same closed convex hull -which is our required smallest prepolar.

V • d 2 V 0 V∞ d 1 Figure 3: Activity in V • Lemma 3.4 The sets in (22) satisfy V • ⊂ V • ⊂ cl V • . It follows that V • and V • have the same closed convex hull. In particular, V • = ∅ whenever V • = ∅.
Proof. The first inclusion is clear. To prove the second inclusion, recall two properties:

-the domain dom ∂σ V of a subdifferential is dense in the domain dom σ V of the function itself: see, e.g., [17, Thm. E.1.4.2]; -the subdifferential ∂σ V (d) is the face of V exposed by d: see, e.g., [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]Prop. C.3.1.4].

Thus, d / ∈ V • implies ∂σ V (d) = ∅; in other words, V • ⊃ dom ∂σ V . Taking closures, cl V • ⊃ cl (dom ∂σ V ) ⊃ dom σ V ;
the required inclusion follows, since the last set obviously contains V • .

It follows from the second inclusion that conv

V • ⊂ conv cl V • .
On the other hand, the first inclusion implies that conv V • (a closed set) contains the closure of

V • : cl V • ⊂ conv V • .
This inclusion remains valid by taking the closed convex hulls:

conv cl V • ⊂ conv V • ;
the two sets coincide. The last statement is clear since the closure of the empty set is the empty set.

To help understand this construction, consider the polyhedral case, say

V = conv {p i } i + cone {r i } i . Then the linear program defining σ V (d) -has no finite solution if some d ⊤ r i is positive, i.e. if d / ∈ (V ∞ ) • , -is solved at some extreme point p i otherwise.
In this situation, the two sets in [START_REF] Rockafellar | Convex Analysis[END_REF] coincide and are closed; they are a union of hyperplanes of equation d ⊤ p i = 1 (facets of V • ), for p i describing the extreme points of V . Besides, the polar V • is defined by As for V • , it has first the two constraints d ⊤ p i 1 (yielding the above two segments). Besides, the two extreme rays r 1 = (0, -1) and r 2 = (-1, -1) of V ∞ make two more constraints d ⊤ r i 0, so that V • is the convex hull of A, B, C and 0. If V had a fourth constraint, say ψ -1, then 0 would be moved down to D = (0, -1) -and enter V • and V • . The closed convex hull thus revealed deserves a notation, as well as its support function: we set

d ⊤ p i 1 ,
V • := conv V • = conv V • and µ V := σ V • = σ V • = σ V • . (23)
For example in Figure 4, V • is the triangle conv{A, B, C}. In fact, the next result shows that µ V is the small representation we are looking for. From now on, we assume

V = R q , otherwise V • = ∅, µ V ≡ -∞;
a degenerate situation, which lacks interest anyway.

Proposition 3.6 (Smallest representation) Any ρ representing V = R q satisfies ρ µ V .
Geometrically, V • is the smallest closed convex set whose support function represents V .

Proof. Our assumption implies that neither V • nor V • is empty (recall Lemma 3.4). Then take an arbitrary d in V • . We have to show that d ⊤ r ρ(r) for all r ∈ R q ; this inequality will be transmitted to the supremum over d, which is µ V (r). Case 1. First let r be such that ρ(r) > 0. Then r := r/ρ(r) lies in V , so that

d ⊤ r σ V (d) = 1. In other words, d ⊤ r = d ⊤ r ρ(r)
1, which is the required inequality. Case 2. Let now r be such that ρ(r) 0, so that r ∈ V ∞ by Lemma 3.2. Since d ∈ V • , we can take r d ∈ V such that d ⊤ r d = 1. Being exposed, r d lies on the boundary of V : by [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF], ρ(r d ) = 1.

By definition of the recession cone, r d + tr ∈ V for all t > 0 and, by continuity of ρ, ρ(r d + tr) > 0 for t small enough. Apply Case 1:

d ⊤ r d + td ⊤ r = d ⊤ (r d + tr) ρ(r d + tr) ρ(r d ) + tρ(r) ,
where we have used sublinearity. This proves the required inequality since the first term is 1 + td ⊤ r and the last one is 1 + tρ(r).

The geometric counterpart is proved just as in Corollary 3.3.

Thus, V does have a smallest representation, which is the support function of V • . Piecing together our results, we can now fully describe the polarity operation.

3.4

The set of prepolars. First of all, it is interesting to link the two extreme representations/prepolars introduced so far, and to confirm the intuition suggested by Figure 4: Proposition 3.7 Appending 0 to V • gives the standard polar:

γ V = max µ V , 0 i.e. V • = conv V • ∪ {0} = [0, 1]V • .
Proof. For r ∈ V ∞ , γ V (r) = 0, while µ V (r) 0 (Proposition 3.6). For r / ∈ V ∞ , Lemma 3.2 gives γ V (r) = µ V (r) > 0 because γ V and µ V are two particular representations.

Altogether, the first equality holds. Its geometric counterpart is [17, Thm. C.3.3.2]; and because V • is convex compact, its closed convex hull with 0 is the sets of αd + (1α)0 for α ∈ [0, 1]. In summary, the set of representations -or of prepolars -is fully described as follows:

Theorem 3.8 The representations of V (a closed convex neighborhood of the origin) are the finite-valued sublinear functions ρ satisfying

σ V • = µ V ρ γ V = σ V • = max {0, µ V } . (24)
Geometrically, the prepolars of V , i.e. the sets G whose support function represents V , are the sets sandwiched between the two extreme prepolars of V :

G • = V ⇐⇒ V • ⊂ conv (G) ⊂ V • = conv V • ∪ {0} = [0, 1]V • .
Proof. In view of Corollary 3.3 and Propositions 3.6, 3.7, we just have to prove that a ρ satisfying (24) does represent V . Indeed, if r ∈ V then ρ(r) γ V (r) 1; if r / ∈ V , then 1 < µ V (r) ρ(r). The geometric counterpart is again standard calculus with support functions.

We end this section with a deeper study of prepolars, which will be useful in the sequel. The next result introduces the polar cone (V ∞ ) • . When G is a cone, positive homogeneity can be used to replace the righthand side "1" in ( 19) by any positive number, or even by "0": in particular,

V • ∞ := (V ∞ ) • = {r ∈ R q : σ V∞ (r) 0} . ( 25
)
The notation

V • ∞ is used for simplicity, although it is somewhat informal; (V ∞ ) • and (V • ) ∞ differ, the latter is {0} since V • is bounded.
Lemma 3.9 (Additional properties of prepolars) With the notation ( 22), ( 23), ( 25),

(i) V • ∞ is the closure of dom σ V , (ii) R + V • = R + V • = R + V • = dom σ V . Proof. First of all, let d / ∈ V • ∞ : there is r ∈ V ∞ (R + r ∈ V ) and d ⊤ r > 0; then d ⊤ (tr) → +∞ for t → +∞ and σ V (d) cannot be finite, i.e. d / ∈ dom σ V . Thus, dom σ V ⊂ V • ∞ ; hence cl (dom σ V ) ⊂ V • ∞ because V • ∞ is closed.
To prove the converse inclusion, take r / ∈ (dom σ V ) • : there is d such that σ V (d) < +∞ and d ⊤ r > 0. Then d ⊤ (tr) → +∞ when t → +∞; if r were in V ∞ , then tr would lie in V and σ V (d) would be +∞, a contradiction. Thus we have proved V ∞ ⊂ (dom σ V ) • . Taking polars and knowing that dom [START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF]Prop. A.4.2.6]). This proves (i). To prove (ii), observe first that

σ V is a cone, V • ∞ ⊃ (dom σ V ) •• = cl (dom σ V ) (see
V • ⊂ V • ⊂ V • ⊂ dom σ V ; and because dom σ V is a cone, R + V • ⊂ R + V • ⊂ R + V • ⊂ dom σ V . ( 26
)
On the other hand, take 0 = d ∈ dom σ V , so that σ V (d) > 0 by ( 21) and 26) is actually a chain of equalities. To complete the proof, observe from Proposition 3.7 that

1 σV (d) d ∈ V • : d ∈ R + V • . Since 0 also lies in R + V • , we do have dom σ V ⊂ R + V • ; (
R + V • = R + V • . φ v P • = P • 1 u d V = P r(d) ψ
σ P (d) = σ P (u, v) =    0 if d = 0 , v + u 2 2v if v > 0 , +∞ if v 0 ; ( 27
)
two phenomena are then revealed.

-First, V • is defined by the equation

v + u 2 2v = 1 , i.e. 2(v 2 -v) + u 2 = 0 .
This is an ellipse passing through the origin (right part of Figure 5); yet 0 cannot lie in V • , since σ P (0) = 0 = 1. Thus, P • is not closed and, more importantly, 0 ∈ P • . -The second phenomenon is a violent discontinuity of σ P at 0. In fact, fix α > 0 and let

d k = α k , 1 k 2 ; then d k → 0, while σ P (d k ) → α 2
2 , an arbitrary positive number. Both phenomena are due to (local) unboundedness of σ P on its domain, which is thus not closed; if (u k , v k ) ∈ dom σ P tends to any (u, 0) with u = 0, then σ P (u k , v k ) → +∞. Ruling out such a behaviour brings additional useful properties:

Corollary 3.10 (Safe prepolars) If 0 / ∈ V • , then R + V • = R + V • = R + V • = dom σ V = V • ∞ ( 28
)
and int V ∞ = ∅ (the polar V • ∞ is a so-called pointed cone). Proof. When 0 / ∈ V • , R + V • is closed ([17, Prop. A.1.4.7]
). Then apply Lemma 3.9: by (ii) dom σ V is closed and (28) follows from (i). Now we separate 0 from V • : there is some r such that σ V • (r) < 0. By continuity of the finite-valued convex function σ V • , this inequality is still valid in a neighborhood of r: σ V • 0 over some nonzero ball B around r. By Lemma 3.9(ii),

σ V • ∞ (d) = σ R+V • (d) = sup t 0 sup d∈V • td ⊤ r = sup t 0 tσ V • (d) , so that σ V • ∞ enjoys the same property: by (25), B is contained in (V • ∞ ) • . Proposition A.4.2.6 of [17] finishes the proof.
Property (28) means closedness of dom σ V and is rather instrumental. We mention another simple assumption implying it:

Proposition 3.11 If V = U + V ∞ , where U is bounded, then dom σ V = V • ∞ .
Proof. The support function of a sum is easily seen to be the sum of support functions:

σ V = σ U + σ V∞ . Every d ∈ V • ∞ then satisfies σ V (d) = σ U (d)
, a finite number when U is bounded. Let us put this section in perspective. The traditional gauge theory defines via ( 16), [START_REF] Júdice | A complementarity-based partioning and disjujnctive cut algorithm for mathematical programming problems with equilibrium constraints[END_REF] the polarity correspondence V ↔ V • for compact convex neighborhoods of the origin. We generalize it to unbounded neighborhoods, whose standard gauge is replaced via Definition 2.6 by their family of representations. Each representation ρ, which may assume negative values, gives rise to ∂ρ(0) -which we call a prepolar of V . Theorem 3.8 establishes the existence of a largest element (the usual polar V • ) and of a smallest element (V • ) in the family of (closed convex) prepolars of V . Gauge theory is further generalized in [START_REF] Zaffaroni | Convex radiant costarshaped sets and the least sublinear gauge[END_REF], in which 0 may lie on the boundary of V . Our stricter framework allows a finer analysis of the smallest prepolar; in particular, the property 0 / ∈ V • helps avoiding nasty phenomena.

4. Minimal cgf's, maximal S-free sets. Remembering Remark 1.4, our goal in this section is to study the concept of minimality for cgf's. Geometrically, we study the concept of maximality for S-free sets. In fact, the two concepts are in correpondence via [START_REF] Gomory | Some polyhedra related to combinatorial problems[END_REF]; but a difficulty arises because the reverse inclusion does not hold in [START_REF] Gomory | Some polyhedra related to combinatorial problems[END_REF]. As a result, several definitions of minimality and maximality are needed.

4.1 Minimality, maximality. In our quest for small cgf's, the following definition is natural.

Definition 4.1 (Minimality) A cgf ρ is called minimal if the only possible cgf ρ ′ ρ is ρ itself.
Knowing that a cgf ρ represents V (ρ) and that µ V (ρ) ρ represents the same set, a minimal cgf is certainly a smallest representation:

ρ is a minimal cgf =⇒ ρ = µ V (ρ) = σ V (ρ) • . ( 29
)
In addition, V (ρ) must of course be a special S-free set when ρ is minimal. Take for example S = {1} ⊂ R, V = [-1, +1]; then ρ(r) := |r| is the smallest (because unique) representation of V but is not minimal:

ρ ′ (r) := max {0, r} is also a cgf, representing V ′ =] -∞, +1].
From ( 14), a smaller ρ describes a larger V ; so Definition 4.1 has its geometrical counterpart:

Definition 4.2 (Maximality) An S-free set V is called maximal if the only possible S-free set V ′ ⊃ V is V itself.
The two objects are indeed related:

Proposition 4.3 If V is a maximal S-free set, then its smallest representation µ V is a minimal cgf.
Proof. Take a cgf ρ ′ , representing the S-free set

V ′ = V (ρ ′ ). If ρ ′ µ V , then V ′ ⊃ V ; and if V is maximal, V ′ = V . Then ρ ′ µ V = µ V ′ by Proposition 3.6.
Besides, these objects do exist: Theorem 4.4 Every S-free set is contained in a maximal S-free set. It follows that there exists a maximal S-free set and a minimal cgf.

Proof. Let V be an S-free set. In the partially ordered family (F , ⊂) of all S-free sets containing V , let {W i } i∈I be a totally ordered subfamily (a chain) and define W := ∪ i∈I W i . Clearly, W is a neighborhood of the origin; its convexity is easily established, let us show that its closure is S-free.

Remember from [17, Thm. C.3.3.2(iii)] that the support function of a union is the (closure of the) supremum of the support functions:

σ int (W ) = σ W = cl sup i∈I σ Wi = cl sup i∈I σ int (Wi) = σ ∪i int (Wi) .
Having the same support function, the two open convex sets int (W ) and ∪ i int (W i ) coincide: r ∈ int (W ) means r ∈ int (W i ) for some i; because W i is S-free, r / ∈ S and our claim is proved. Thus, the chain {W i } has an upper bound in F ; in view of Zorn's lemma, F has a maximal element. Now (1b) implies that a ball centered at 0 with a small enough radius is S-free; and there exists a maximal S-free set containing it. Proposition 4.3 finishes the proof.

The maximal S-free sets can be explicitly described for some special S's: Z q [20], the intersection of Z q with an affine subspace [START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF], with a rational polyhedron [START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF], or with an arbitrary closed convex set [START_REF] Morán | On maximal S-free convex sets[END_REF][START_REF] Averkov | On maximal S-free sets and the Helly number of the family of S-convex sets[END_REF]. Unfortunately, the "duality" between minimal cgf's and maximal S-free sets is deceiving, as the two definitions do not match: the set represented by a minimal cgf need not be maximal. In fact, when ρ is linear, the property introduced in Definition 4.1 holds vacuously: no sublinear function can properly lie below a linear function. Thus, a linear cgf ρ is always minimal; yet, a linear ρ represents a neighborhood V (ρ) (a half-space) which is S-free but has no reason to be maximal. See Figure 6: with n = 1, the set 7) by moving its right vertical boundary to φ 1t. Then A is moved to A t = 1 1-t , 0 ; there is no inclusion between the new V • t = conv{A t , B, C} and the original V • = conv{A, B, C}; this is the key to our example.

V = ] -∞, 1] (represented by ρ(x) = x) is {2}-free but is obviously not maximal. 0 V S = {2} 1
φ = 1 , ψ = 1 , ψ = 2 + φ , so that V is clearly maximal S-free. V • t At W • Vt rA rC B C At B C Figure 7: The mapping V → V • is not monotonic Now shrink V to V t (left part of Figure
Let us show that µ Vt is minimal, even though V t is not maximal. Take for this a cgf ρ µ Vt , which represents an S-free set W ; by [START_REF] Gomory | Some polyhedra related to combinatorial problems[END_REF], W ⊃ V t . We therefore have

σ W • = µ W ρ µ Vt = σ V • t , i.e., W • ⊂ V • t
and we proceed to show that equality does hold, i.e. the three extreme points of

V • t do lie in W • . -If A t / ∈ W • , the right part of Figure 7 shows that W • is included in the open upper half-space. Knowing that W = W • • = r : d ⊤ r 1 for all d ∈ W • , this implies that W ∞ has a vector of the form r A = (ε, -1) (ε > 0); W cannot be S-free. -If C / ∈ W • , there is r C ∈ R 2 such that C ⊤ r C > σ W • (r C ) = µ W (r C
) (we denote also by C the 2-vector representing C). For example r C = (-2, 0) ∈ bd (V ) (see the right part of Figure 7), so that

C ⊤ r C = 1 > σ W • (-2, 0) = µ W (-2, 0) . By continuity, µ W (-2 -ε, 0) 1 for ε > 0 small enough. Since µ W represents W , this implies that (-2 -ε, 0) ∈ W ; W (which contains V t ) is not S-free.
-By the same token, we prove that B ∈ W • (the separator r B = (0, 1) ∈ bd (V ) does the job).

We have therefore proved that W • = V • t , i.e µ W = µ Vt , i.e. µ Vt is minimal.

The next section makes a first step toward a theory relating small cgf's and large S-free sets.

4.2 Strong minimality, asymptotic maximality. First, let us give a name to those minimal cgf's corresponding to maximal S-free sets. Definition 4.6 (Strongly minimal cgf) A cgf ρ is called strongly minimal if it is the smallest representation of a maximal S-free set.

The strongly minimal cgf's can be characterized without any reference to the geometric space. Proposition 4.7 A cgf ρ is strongly minimal if and only if, for every cgf ρ ′ ,

ρ ′ max {0, ρ} = γ V (ρ) = σ V (ρ) • =⇒ ρ ′ ρ . (30)
Proof. Take first a maximal V . Every cgf ρ ′ γ V represents an S-free set V ′ , which contains Vsee (13) -so that V ′ = V by maximality, i.e. ρ ′ represents V as well; hence ρ ′ µ V by Proposition 3.6. Thus, ρ(= µ V ) satisfies (30).

Let now ρ satisfy (30), we have to show that V := V (ρ) is maximal. Taking in particular ρ ′ = µ V in (30) shows that ρ must equal µ V . Let V ′ ⊃ V be S-free; we have (

V ′ ) • ⊂ V • , i.e. γ V ′ = σ (V ′ ) • σ V • = γ V = max {0, ρ} . Now ρ ′ := γ V ′ is a cgf, so ρ ′ ρ = µ V by (30); by Theorem 3.8, ρ ′ represents not only V ′ but also V , i.e. V ′ = V : V is maximal.
In Section 3 we have systematically developed the geometric counterpart of representations; this exercise can be continued here. In fact, the concept of minimality involves two properties from a sublinear function:

-it must be the smallest representation of some neighborhood V -remember (29), -this neighborhood must enjoy some maximality property.

In view of the first property, a cgf can be imposed to be not only sublinear but also to support a set that is a smallest prepolar. Then Definition 4.1 has a geometric counterpart:

minimality of ρ = µ V = σ V • means G ′ ⊂ V • and (G ′ ) • is S-free =⇒ G ′ = V • , i.e. (G ′ ) • = V . [ρ ′ = σ G ′ ρ] [ρ ′ is a cgf] [ρ ′ = ρ]
Likewise for Definition 4.6: strong minimality of

ρ = γ V = σ V • means G ′ ⊂ V • and (G ′ ) • is S-free =⇒ G ′ ⊃ V • , i.e. (G ′ ) • ⊂ V . [ρ ′ = σ G ′ γ V ] [ρ ′ is a cgf] [ρ ′ ρ]
These observations allow some more insight into the (•) • operation:

Proposition 4.8 Let ρ = µ V = σ V • be a minimal cgf. If an S-free set W satisfies W • ⊂ V • , then W = V .
Proof. The smallest representation ρ ′ := µ W = σ W • of the S-free set W is a cgf; and from monotonicity of the support operation, ρ ′ ρ. Then minimality of ρ implies ρ ′ = ρ, i.e. W • = V • , an equality transmitted to the polars:

W = (W • ) • = (V • ) • = V .
This result confirms that non-equivalence between minimal cgf's and maximal S-free sets comes from non-monotonicity of the mapping

V → V • -or of V → µ V . To construct Example 4.5, we do need a W ⊃ V such that W • ⊂ V • .
Then comes a natural question: how maximal are the S-free sets represented by minimal cgf's? For this, we introduce one more concept: Definition 4.9 An S-free set V is called asymptotically maximal if every S-free set

V ′ ⊃ V satisfies V ′ ∞ = V ∞ .
It allows a partial answer to the question. Theorem 4.10 (Minimal ⇒ asymptotically maximal) The S-free set represented by a minimal cgf is asymptotically maximal.

Proof. Let µ V be a minimal cgf and take an S-free set V ′ ⊃ V . Introduce the set

G := V • ∩ V ′ ∞ • .
Inclusions translate to inequalities between support functions:

σ G σ V • = µ V (
r → inf σ V • (r 1 ) + σ (V ′ ∞ ) • (r 2 ) : r 1 + r 2 = r . In this formula, σ V • = µ V and the support function of the closed convex cone V ′ ∞ • is the indicator of its polar V ′ ∞ : the above function is r → inf µ V (r 1 ) : r 1 + r 2 = r, r 2 ∈ V ′ ∞ .
Now use [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF]: because σ G represents W , to say that r ∈ int (W ) is to say that the above infimum is strictly smaller than 1, i.e. that there are r 1 , r 2 such that

r 1 + r 2 = r, r 2 ∈ V ′ ∞ , µ V (r 1 ) < 1 i.e. r 1 + r 2 = r, r 2 ∈ V ′ ∞ , r 1 ∈ int V .
In a word: int (W ) = V ′ ∞ + int (V ) ⊃ int (V ) ∋ 0 , where we have used the property 0 ∈ V ′ ∞ . Remembering the inclusion V ⊂ V ′ and the definition of a recession cone, we also have

int (W ) = V ′ ∞ + int (V ) ⊂ V ′ ∞ + int (V ′ ) ⊂ V ′ ∞ + V ′ ⊂ V ′ . Altogether, 0 ∈ int (W ) ⊂ int (V ′ ). As a result, W (= G •
) is an S-free closed convex neighborhood of the origin: its representation σ G is a cgf and minimality of µ

V = σ V • implies with (31) that σ G = σ V • . By closed convexity of both sets V • and G = V • ∩ V ′ ∞ • , this just means G = V • , i.e. V ′ ∞ • ⊃ V • . By polarity, V ′ ∞ ⊂ V • • = V (invoke Theorem 3.8). The cone V ′ ∞ , contained in the neighborhood V , is also contained in its recession cone: V ′ ∞ ⊂ V ∞ . Since the converse inclusion is clear from V ′ ⊃ V , we have proved V ′ ∞ = V ∞ :
V is asymptotically maximal.

5. Favourable cases Despite Example 4.5, a number of papers have established the equivalence between maximal S-free sets and minimal cgf's, for various forms of S. This equivalence is indeed known to hold in a number of situations:

(a) when S is a finite set of points in Z qb; see [START_REF] Johnson | Characterization of facets for multiple right-hand side choice linear programs[END_REF] and more recently [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF]; (b) when S is the intersection of Z n with an affine space; this was considered in [START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF] and [START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF]; (c) when S = P ∩ (Z qb) for some rational polyhedron P ; this was considered in [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF][START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF].

Accordingly, we investigate in this section the question: when does minimality imply strong minimality? So we consider an S-free set V , whose smallest representation µ V = σ V • is minimal, hence V is asymptoticaly maximal (Theorem 4.10); we want to exhibit conditions under which V is maximal. We denote by L = (-V ∞ ) ∩ V ∞ the lineality space of V (the largest subspace contained in the closed convex cone V ∞ ) and our result is the following. Theorem 5.1 Suppose 0 ∈ S := conv (S). A minimal µ V is strongly minimal whenever one of the following two properties (i) and (ii) holds:

(i) V ∞ ∩ S ∞ = {0} (in particular S bounded ), (ii) (ii) 1 S = U + S ∞ with U bounded, and (
ii) 2 V ∞ ∩ S ∞ = L ∩ S ∞ .
This theorem generalizes the above-mentioned results: (i) is a weakening of (a) and (ii) weakens (b) or (c). Note that (ii) 2 generalizes (i) (to an unbounded V ∞ ∩ S); the price to pay is assumption (ii) 1 , whose role is to exclude an asymptotic behaviour of S similar to that of P in Figure 5 (see Proposition 3.11).

However, the interesting point does not lie in the above assumptions (a) -(ii). Recalling that the whole issue lies in unboundedness of V , our proof of Theorem 5.1 uses Theorem 4.10 as follows. Starting from an S-free set V which is asymptotically maximal but not maximal, we construct a sequence of neighborhoods

V k satisfying V k ∞ V ∞ . Then V k is not S-free: there is some r k ∈ S ∩ int (V k ); see Figure 8.
Besides, our construction is organized in such a way that V k "tends to" V and, by non-maximality of V , r k is unbounded but "tends to" V . More precisely, the cluster points of the normalized sequence {r k } lie in S ∞ ∩ V ∞ .

Decomposing r k = ℓ k + u k along L and L ⊥ , we also prove that u k is unbounded but "tends to" S ∩ L ⊥ , more precisely the cluster points of the normalized sequence {u k } lie in S ∞ ∩ L ⊥ . We believe that these are key properties of non-maximal S-free sets. Having established them, the whole business is to find appropriate assumptions under which existence of our unbounded sequences is impossible; (a) -(ii) above are such ad hoc assumptions. Obtaining r k and u k is a fairly complicate operation, which we divide into a series of lemmas. For a reason that will appear in (39) below, we may assume 0 / ∈ V • . Then we enlarge V to V k by chopping off a bit of V • as follows. Take an extreme ray

R + d V of V • ∞ . By (28), its intersection with V • is a nonempty segment [d V , t V d V ], with 1 t V < +∞. Given a positive integer k, we introduce the open neighborhood of [d V , t V d V ]: N k := [d V , t V d V ] + B 0, 1 k = 1 t tV B td V , 1 k , (32)
where B(d, δ) is the open ball of center d and radius δ. We remove N k from V • , thus obtaining a set C, closed hence compact; its convex hull

G k := conv C , with C := V • \N k = d ∈ V • : d -td V 1 k for all t ∈ [1, t V ] (33)
is convex compact. Figure 9 illustrates our construction.

V • R + G k N k t V d V d V
∀ d ∈ [d V , t V d V ] , ∃d k ∈ G k such that d k -d 1 k . ( 34
B d V , 1 k if V • ∩ R + d V
reduced to a singleton, i.e. if t V = 1; but this property need not hold when σ V is not continuous.

To make a counterexample, start from the parabola of Figure 5. We already know that σ P (d k ) can tend to any nonnegative value when d k → 0. However 0 ∈ P • , the example needs modification to meet our assumption. To this aim, we first bound σ P (on its domain near 0) by defining

f (d) := 1 + σ P (d) if σ P (d) 1 , +∞ otherwise .
Although no longer positively homogeneous, this function is still convex, its domain is the compact convex set P • , on which 1 f 2; when

d k ∈ P • tends to 0, f (d k ) can tend to any value in [1, 2]. To complete Clearly, R + B ⊂ V • ∞ .
Conversely, apply (28): every nonzero d ∈ V • ∞ can be scaled to some td ∈ V • . By (40), td ⊤ ℓ > 1, then d can be scaled again to td/(td ⊤ ℓ), which lies in B. We have shown

R + B = V • ∞ . (42)
By (28), every b ∈ B can be obtained by scaling some d ∈ V

• : b = td; and t = 1 d ⊤ ℓ ∈ ]0, 1[ by (40). This means that B ⊂ ]0, 1[ V • ⊂ V • ; (43)
B is therefore bounded (and closed because V • ∞ is closed), hence compact. Using (41), scale e to b := 1 e ⊤ ℓ e ∈ B and express b = j α j b j as a convex combination of extreme points b j of B (Minkowski's Theorem). Then

σ W ( b) = 1 e ⊤ ℓ σ W (e) = 1 e ⊤ ℓ > 1 .
By convexity of σ W , there is some j 0 such that σ W (b j0 ) > 1 (we may have σ W (b j0 ) = +∞). Altogether, we have exhibited b j0 extreme in B and satisfying 1 < σ W (b j0 ) .

Extremality of b j0 in B implies extremality of the ray R + b j0 in R + B, i.e. in V • ∞ because of (42). The intersection of W • with this extreme ray is some [0, d W ] (d W may be 0) which, by definition of a polar, does not contain b j0 . Since b

⊤ j0 ℓ = 1 (because b j0 ∈ B), d ⊤ ℓ < 1 for all d ∈ [0, d W ]. Then, (40) shows that [0, d W ] and [d V , t V d V ] are separated.
As a result, the two compact sets W • and [d V , t V d V ] are disjoint. If there were d k ∈ W • ∩ N k for all k, then the bounded sequence {d k } would have some cluster point d

* ; but W • is closed: d * would lie in W • ∩ [d V , t V d V ], contradiction.
The set B constructed in the above proof is a so-called basis of the pointed cone V • ∞ . The case σ W (b j0 ) = +∞, d W = 0 corresponds to a W as in Figure 5; it occurs in Figure 10. This latter picture is still helpful to follow the next proof. Recall that L is the lineality space of V . Proposition 5.5 Assume 0 ∈ S = conv (S). If a minimal cgf ρ represents the S-free set V = V (ρ) which is not maximal, then V k exists as described by Lemma 5.3. There is r k ∈ V k ∩ S, decomposed as r k = ℓ k + u k with ℓ k ∈ L and u k ∈ L ⊥ , such that for some K ⊂ N , lim Proof. If all of the S-free sets W containing V satisfy W • ⊂ V • , then V is maximal (Proposition 4.8). Thus, there is an S-free set W ⊃ V satisfying (39) and we can construct d V as in Lemma 5.4.

If R + d V = V • ∞ , then V • = V • = {d V } and V • = [0, d V ]
(Proposition 3.7): the S-free set V , represented by σ V • , is the half-space {r : d ⊤ V r 1}, which separates 0 from S; this is ruled out by assumption. Otherwise, R + d V V • ∞ : we can apply Lemma 5.3 and construct the sequence of S-free sets V k . By minimality of µ V , V k cannot be S-free (Lemma 5.3(i) and Theorem 4.10): there exists r k lying -in int V k , hence from [START_REF] Dey | Constrained infinite group relaxations of mips[END_REF] 1

> σ G k (r k ) , (44)
-and in S, hence r k / ∈ int W : σ W • (r k ) 1; since W • is compact,

∃e k ∈ W • such that e ⊤ k r k 1 . (45)
Now we claim that there is δ > 0 such that 46) is proved.

t k e k ∈ V • ∩ N k ,
6. Conclusion and perspectives. In this paper, we have laid down some basic theory toward studying the cutting paradigm for sets of the form (1). We have introduced for this the concept of cutgenerating functions, which allowed us to put in perspective an abundant literature devoted to S-free sets. We have revealed the discrepancy between minimality and maximal S-freeness; and we have recovered existing theorems [START_REF] Johnson | Characterization of facets for multiple right-hand side choice linear programs[END_REF][START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF][START_REF] Basu | Maximal lattice-free convex sets in linear subspaces[END_REF][START_REF] Dey | Constrained infinite group relaxations of mips[END_REF][START_REF] Basu | Minimal inequalities for an infinite relaxation of integer programs[END_REF], dealing with mere minimality, exhibiting the intrinsic arguments allowing their proofs. Our theory necessitated a generalization of the polarity correspondence to certain unbounded sets; we have conducted it via a systematic exploitation of the correspondence between sublinear functions and closed convex sets.

A number of questions arise from this theoretical work. Some are suggested by Section 3: Question 1. Given a convex compact set G, can we detect whether it is minimal prepolar of V := G • ? and if not, can we compute G • • ? Question 2. Knowing that our generalization of polarity goes along with that of [START_REF] Zaffaroni | Convex radiant costarshaped sets and the least sublinear gauge[END_REF], linking the two works should certainly be instructive. For example, we define the prepolar by [START_REF] Zaffaroni | Convex radiant costarshaped sets and the least sublinear gauge[END_REF], which looks quite different from the set Q in [START_REF] Zaffaroni | Convex radiant costarshaped sets and the least sublinear gauge[END_REF]Prop. 5.1]. Yet the two sets have to coincide, at least when 0 ∈ int V ; can this be clarified? and can we explain what happens when when 0 becomes a boundary point of V ? Also: does this other definition help answering Question 1?

These are limited to pure convex analysis; concerning the cgf theory itself, some other questions have a concrete interest: Question 3. Is it possible to characterize exactly the S-free sets represented by minimal cgf's? a converse form of Theorem 4.10 should be desirable. Question 4. One might want to consider more general models. For example, it should not be too difficult to replace the "ground set" R n + of (1a) by some other closed convex cone; say the cone of positive semidefinite matrices, which would open the way toward cutting SDP relaxations. Another generalization would be inspired by the approach of [START_REF] Gomory | Some polyhedra related to combinatorial problems[END_REF] of Example 1.1: there, X has the form x ∈ Z n + : -Ax ∈ Z mb ; S = Z mb lies in a smaller space but the ground set Z n + is no longer convex, so sublinear cgf's are now ruled out. Instead, cgf's in this context are subadditive, periodic, and satisfy a certain symmetry condition [START_REF] Gomory | Some continuous functions related to corner polyhedra i[END_REF]. Question 5. Perhaps the most crucial question is whether cgf's do generate all possible cuts, i.e., whether [START_REF] Borozan | Minimal valid inequalities for integer constraints[END_REF] is able to produce all possible c's satisfying (2). This turns out to be a tough nut to crack, we conclude the paper with some considerations for future research concerning it.

The following counter-example shows that the answer to Question 5 is no in general.

Example 6.1 (cgf's need not generate all cuts) In R 2 , take S = (0, 1) ∪ (Z, -1) . The left part of Figure 11, drawn in the S-space, clearly shows that, if the unit-vector (1, 0) lies in the recession cone of an S-free set V , then it lies on the boundary of this cone. Now take the identity matrix for R: in the x = (ξ, η)-space, X reduces to the singleton (0, 1) in R 2 (right part of Figure 11). It can be separated from the origin by the cut η ξ + 1, obtained with c = (-1, 1) ⊤ . Knowing that the first column of R is r 1 = (1, 0) ⊤ , a cgf ρ producing this c must therefore have ρ(r 1 ) = -1. In view of Lemma 3.2, (1, 0) lies in the interior of V ∞ ; but we have seen that no V can satisfy this. Negative c j 's are therefore troublesome, a general sufficiency theorem is out of reach. To eliminate c j < 0, we can restrict the class of instances:

  R 1 , the positively homegeneous functions have the form ρ(r) = αr for r 0 βr for r 0 ;

  and d ⊤ r i 0 . Example 3.5 For later use, we detail the calculation on a simple instance. Take for V the polyhedron of Figure 4, defined by the three inequalities φ 1 , ψ 1 , ψ 2 + φ ; here (φ, ψ) denotes a primal point in R 2 we take row-vectors for typographical convenience). The two extreme points p 1 = (1, 1) and p 2 = (-1, 1) of V define the two segments (facets of V • ) [A, B] and [B, C].

Figure 4 :

 4 Figure 4: Constructing V • or V •

Figure 5 :

 5 Figure 5: Trouble appears if the neighborhood has no asymptote Beware that really pathological prepolars can exist, Figure 5 illustrates a well-known situation. Its left part displays the parabolic neighborhood V = P ⊂ R 2 defined by the constraint ψ 1 -1 2 φ 2 . A direction d = (u, v) with v > 0 exposes the point r(d). When v ↓ 0, the component of r(d) along d (namely φ) goes to +∞, which does bring trouble. Computing r(d) is an exercise resulting in

Figure 6 :

 6 Figure6: A linear cgf is always maximal A more elaborate example reveals the profound reason underlying the trouble: for an S-free set W containing V , µ W need not be comparable to µ V .

  31) and we proceed to prove that this is actually an equality. Let us compute the set W := G • represented by σ G . The support function of an intersection is obtained via an inf-convolution (formula (3.3.1) in [17, Chap. C)] for example): σ G (•) is the closure of the function

Figure 8 :

 8 Figure 8: Constructing in S an unbounded sequence "tending to" V

Figure 9 :

 9 Figure 9: Chopping off V • near an extreme ray Note for future use that the distance from every d ∈ [d V , t V d V ] to C does not exceed 1/k; and the same holds for G k ⊃ C. Formally:

) Remark 5 . 2

 52 The above construction would become substantially simpler and N k would reduce to the open ball

  k∈K r k = +∞ and lim k∈K u k = +∞ .

Figure 11 :

 11 Figure 11: Not all cuts are obtained from a cgf

  for some t k 1 + δ and all k large enough . (46) Using (28), scale e k (nonzero from its definition) to t k e k ∈ V • ; and note from (38) that t k 1. Then (45) implies that t k e k / ∈ G k : otherwise1 e ⊤ k r k t k e ⊤ k r k σ G k (r k) by definition of a support function; this contradicts (44). It follows that t k e k ∈ V • ∩ N k , which is far from W • (Lemma 5.4); (

Conforti, Cornuéjols, Daniilidis, Lemaréchal, Malick: Cut-generating functions Mathematics of Operations Research xx(x), pp. xxx-xxx, c 200x INFORMS

Acknowledgment. We are indebted to the referees, whose attentive and intelligent reading was very helpful to improve an earlier version of this paper. This work was supported in part by NSF grant CMMI1263239, ONR grant N00014-09-1-0033, MICINN grant MTM2011-29064-C03-01 (Spain) and FONDECYT Regular Grant 1130176 (Chile).

whose positive homogeneity is clear. Actually, σ is known to be convex and to support a closed convex set V ; see [17, § B.2.2] (in particular Remark 2.2.3), where our (d, w) is called (x, u). Besides, the property f 1 implies that V is a neighborhood of the origin; remember [START_REF] Morán | On maximal S-free convex sets[END_REF]. Now take (d, w) ∈ V • ⊂ dom σ, so that d ′ := d w ∈ dom f and w > 0. Then use positive homogeneity:

Thus, V • is separated from the origin (by the hyperplane w 1 2 ) and this property is transmitted to its closed convex hull V • . On the other hand, σ inherits the discontinuities of f . In fact, choose α ∈ [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF][START_REF] Averkov | On maximal S-free sets and the Helly number of the family of S-convex sets[END_REF] and construct a sequence {d k } in dom f tending to 0, such that f

Pass to the limit:

Since α was arbitrary in [START_REF] Andersen | Cutting planes from two rows of a simplex tableau[END_REF][START_REF] Averkov | On maximal S-free sets and the Helly number of the family of S-convex sets[END_REF], the intersection of V • with the ray {0}×, R + contains the whole segment

Viewing G k of (33) as a prepolar, we set

The closed convex neighborhood V k enjoys all of the properties listed in Section 3, in particular those coming from 0 / ∈ G k .

Proof. If G k were empty for all k, we would have

and none of their convex combinations either because of extremality of R

Now, we see from Theorem 3.8 that

but from Proposition 3.7, this is actually a chain of equalities:

• and we can apply (28) to V k . Then we write

, which implies (i) since polarity is an involution between closed convex cones. To prove (ii), take r in ∩ k V k ; we have to prove that r ∈ V (the other inclusion being obvious). If r / ∈ V there is a separating hyperplane d: σ V ( d) < d⊤ r. Normalizing d via (28), we have altogether

Passing to the limit, d⊤ r 1; a contradiction to (37). Therefore r ∈ V . Now we assume the existence of an S-free set W containing V ; it satisfies in particular

). We are therefore in the situation

Thus, W • contains some points out of V • . The key argument for our analysis is that one of these points lies on an extreme ray of V • ∞ -which will be the d V of Lemma 5.3, crucial to construct the unbounded sequence {r k } of Figure 8.

Lemma 5.4 (Constructing an appropriate extreme ray)

Proof. From (39), we are in the framework of Corollary 3.10; Figure 10 is helpful to follow the proof.

σV (e) e ∈ V • (remember (21): σ V (e) > 0). For every e ′ ∈ [0, e], the segment [e ′ , d e ] contains e. Being a convex set, V • cannot contain such an e ′ (otherwise it would contain e as well). As a result, the compact convex sets V • and [0, e] can be separated: there is ℓ ∈ R q (appropriately scaled) such that max 0, e ⊤ ℓ < 1 < min

Now introduce the closed convex set

Then we obtain with the Cauchy-Schwarz inequality

Furthermore, decompose r k = ℓ k + u k in (47) and observe that both

Both statements are proved since there is K ⊂ N such that lim k∈K t k e k -d = 0.

As suggested in the beginning of this section, proving Theorem 5.1 is now easy. An S-free set represented by a minimal cgf will be automatically maximal under any assumption contradicting the existence of our unbounded sequences.

Proof of Theorem 5.1. Construct the sequences {r k } and {u k } of Proposition 5.5.

Case (i):

Extract a cluster point r of the normalized subsequence {r k } k∈K : for some ′ ⊂ K,

Then take an arbitrary M > 0. We know that M/ r k 1 if k is large enough in K ′ so, because both 0 and r k lie in

By closedness, this implies M r ∈ S, hence r ∈ S ∞ because M is arbitrary. The same argument using Lemma 5.3(ii) gives r ∈ V ∞ .

Let us sum up. If V is not maximal, then V ∞ ∩ S ∞ contains a vector r of norm 1; this contradicts (i).

Case (ii):

Besides, u k is the projection onto L ⊥ (a linear operator) of r k ∈ S ⊂ U + S ∞ ; hence

By (ii) 1 , Proj L ⊥ U is a bounded set, so our cluster direction û lies in Proj L ⊥ S ∞ : û = ŝ -l , for some ŝ ∈ S ∞ and l ∈ L .

Use (48):

As a result, û = ŝ -l lies in L; use (48) again: û ∈ L ∩ L ⊥ cannot have norm 1.

Thus, in this case also, V has to be maximal.

Let us insist once more: the core of our proof is Proposition 5.5. Then (i) and (ii) appear as ad hoc assumptions to contradict the existence of the stated unbounded sequences; other similar assumptions might be designed. Proposition 6.2 If the recession cone of conv (X) is the whole of R n + , then every cut c lies in R n + .

Proof. Each basis vector e j of R n lies in conv (X) ∞ : picking some x ∈ X, c ⊤ (x + te j ) = c ⊤ x + tc j 1 for all t 0 ; let t → +∞ to see that c j 0.

This result might suggest that the trouble in Example 6.1 is due to the difference between the recession cones of conv (X) and of the ground set R n + in (1a). However, the assumption introduced in Proposition 6.2 does not suffice, as even c j = 0 brings trouble. In fact, make a "more nonlinear" variant of Example 6.1: instead of the horizontal line ψ = -1, take for S the curve ψ = -1/|φ| (φ = 0). This leaves X = {(0, 1)} unchanged; c = (0, 1) ⊤ is a cut and a cgf ρ generating it has ρ(r 1 ) = 0; this ρ represents a set V (ρ) which has (R + , 0) in its recession cone. Being a neighborhood of the origin, V (ρ) contains A := (0, -ε) for small enough ε > 0; also, B := (r, 0) ∈ V (ρ) ∞ ⊂ V (ρ) for all r > 0 (see Figure 12); by convexity, the whole segment [A, B] lies in V (ρ), which therefore cannot be S-free. In these two examples, the conical hull of the r j 's does not cover the whole of S. In fact, S contains points that can be reached by no x ∈ R n + ; these points have nothing to do with the problem, so forcing V not to contain them is unduly demanding. Then one may ask whether cgf's are able to describe all possible cuts, for all possible instances such that S ⊂ cone (r 1 , . . . , r n ). This is an open question. Here we limit ourselves to a reasonably simple sufficiency result, proved with the help of a "comfortable" assumption; it motivated the generalization obtained recently in [START_REF] Cornuéjols | Sufficiency of cut-generating functions[END_REF]. Theorem 6.3 Let an instance of (1) be as described by Proposition 6.2 and assume cone (r 1 , . . . , r n ) := n j=1 λ j r j : λ j 0, j = 1, . . . , n = R q .

Then every cut can be obtained from a cgf.

Proof. Let c ∈ R n + and set J + := j ∈ {1, . . . , n} : c j > 0 , J 0 := j ∈ {1, . . . , n} : c j = 0 .

Then introduce in R q the vectors r ′ j := r j c j , for j ∈ J + and the polyhedron

Claim 1 : V is a neighborhood of the origin. In fact, our assumption means that R q = cone (G) + K: every d ∈ R n has the form d = tḡ + k , with t 0 , ḡ ∈ G , k ∈ K .

Then compute σ V d for nonzero d.

-Case 1: t = 0. Fixing g ∈ G so that g + t k ∈ V for all t 0, we have

Altogether, we have proved that σ V d > 0 for all d = 0, i.e. 0 ∈ int (V ).

Claim 2 : V is S-free. Take r ∈ int (V ). For ε > 0 small enough, r + εr ∈ V :

(1 + ε)r = j∈J+ β j r ′ j + j∈J0 µ j r j , with β j , µ j 0, j∈J+ β j = 1 .

Divide by 1 + ε and set α j = β j /(1 + ε), λ j = µ j /(1 + ε) to get r = j∈J+ α j r ′ j + j∈J0 λ j r j , , for α j , λ j 0 , n j=1 α j < 1 .

Introduce the vector x ∈ R n whose coordinates are xj :=

Observe that x 0 and that

and x cannot lie in X if c is a cut. We have proved that int (V ) ∩ S = ∅, i.e. that V is S-free.

Conclusion:

We have proved that the gauge γ V is a cgf; besides -for j ∈ J 0 , r j is a direction of recession of V : γ V (r j ) = 0 = c j ; -for j ∈ J + , the property r ′ j ∈ V gives 1 γ V (r ′ j ) = 1 c j γ V (r j ) , hence γ V (r j ) c j .

In summary, γ V is a cgf dominating the cut c.

To make Question 5 less ambitious, one may ask whether cgf's can reproduce the set of cuts "globally". In fact, the set of c's satisfying (2) is a closed convex set: the opposite of the reverse polar X -, in the terminology of [START_REF] Balas | Disjunctive programming[END_REF][START_REF] Cornuéjols | A convex-analysis perspective on disjunctive cuts[END_REF]. Then consider the set R S of all representations of a given S-free set. Given (n, R), form the set C of c ∈ R n whose coordinates are ρ(r j ), where ρ describes R S . Is it true that conv (C) = -X -? This question is open. If the answer is yes, one more question occurs: Example 4.5 tells us that R S cannot be reduced to the maximal S-free sets; then, what sort of maximality can be imposed while preserving "completeness" of R S ? An answer should need answering Question 3 first.