Miguel Constantino
email: miguel.constantino@fc.ul.pt

Andrew J Miller
email: andrew.miller@math.u-bordeaux1.fr

Mathieu Van Vyve
email: mathieu.vanvyve@gmail.com

Mixing MIR Inequalities with Two Divisible Coefficients

This paper is a polyhedral study of a generalization of the mixing set where two different, divisible coefficients are allowed for the integral variables. Our results generalize earlier work on mixed integer rounding, mixing, and extensions. They also directly apply to applications such as production planning problems involving lower bounds or start-ups on production, when these are modeled as mixed-integer linear programs.

We define a new class of valid inequalities and give two proofs that they suffice to describe the convex hull of this mixed-integer set. We give a characterization of each of the maximal faces of the convex hull, as well as a closed form description of its extreme points and rays, and show how to separate over this set in O(n log n). Finally, we give several extended formulations of polynomial size, and study conditions under which adding certain simple constraints on the integer variables preserves our main result. 1

Introduction

In this paper we study the polyhedral structure of the mixed integer set P M M IX :

s + Lz t ≥ b t , 1 ≤ t ≤ k, s + Cz t ≥ b t , k + 1 ≤ t ≤ n, z ∈ Z n , s ≥ 0,
where b t ∈ R, L, C > 0 and C/L ∈ Z.

The polyhedral descriptions of many mixed integer sets can be obtained based on the so-called Mixed Integer Rounding inequalities (M IR) and extensions [START_REF] Gomory | An algorithm for the mixed integer problem[END_REF], [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]). The basic M IR inequality is derived from the set

P M IR = {(s, z) ∈ R + × Z : s + Cz ≥ b}.
If we let α = ⌈b/C⌉ and γ = b -C(α -1), then we can write the basic M IR inequality as s ≥ γ(αz).

Günlük and [START_REF] Günlük | Mixing MIR inequalities for mixed integer programs[END_REF] showed how the convex hull of certain sets can be obtained by mixing basic M IR inequalities. This procedure was developed on a generalization of the MIR set that we can define as

P GM IX = {(s, z) ∈ R + × Z n : s + Cz t ≥ b t , 1 ≤ t ≤ n}.
Those authors showed that inequalities obtained by the mixing procedure describe the convex hull of P GM IX .

The set P M M IX studied in this paper considers two divisible coefficients L and C, and it therefore generalizes P GM IX . Indeed, P GM IX is the special case of P M M IX with either k = 0 or k = n. Our aim is to describe the convex hull of P M M IX . To do this, we will develop a way to define valid inequalities by applying the mixing procedure twice. This approach not only yields the convex hull of P M M IX , but other remarkable results as well. These include an O(n log(n)) separation algorithm for P M M IX that is as fast asymptotically as the separation algorithm for P GM IX (which is described in [START_REF] Pochet | Polyhedra for lot-sizing with Wagner-Whitin costs[END_REF] and [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF]). Analysis of the separation algorithm also yields, for each of the the facet-defining inequalities that we define, a system of inequalities that describe the set of points lying in the face defined by that inequality. Using a different approach, we obtain several exact extended formulations for P M M IX .

While this research was in progress, Zhao and de Farias [2007a,c] have studied a generalization of P M M IX that may have more capacities, each of which divides all larger capacities. They show how to compute the extreme points of and optimize over the MIP model in question (they give a closed-form list of extreme points in only a very limited case). Our results for conv(P M M IX ) are more detailed and provide more information than do the results just mentioned; however, the work of Zhao and de Farias is particularly impressive because it applies to models with m divisible capacities for any m ≤ n. (More recently, Di [START_REF] Summa | The mixing set with divisible capacities[END_REF] has refined the algorithm given by Zhao and de Farias [2007a] to compute the extreme points of this general model, and Conforti et al. [2008] have proposed an integral extended formulation that generalizes the results of Section 6 of this paper).

A theoretical motivation for this research is the generalization of the mixing inequalities to apply to more complicated models which often occur as substructures of difficult MIP models. Moreover, applications motivating this research arise in the study of a couple of MIP lot sizing models, which we present briefly below.

Lot Sizing with Lower Bounds

Consider the following single-item lot-sizing model with lower bounds. This model may arise as a submodel of complex multi-item multi-resource production planning problems. max n t=1 (f t y t + p t x t + h t s t )

s t-1 + x t = d t + s t , 1 ≤ t ≤ n (1) Ly t ≤ x t ≤ Cy t , 1 ≤ t ≤ n, (2)
y t ∈ Z + , 1 ≤ t ≤ n, (3)
where d t ≥ 0 are the demands, f t are the set-up costs, p t are the unit production costs, and h t are the unit holding costs. In this model multiple set-ups in a single period are allowed, so the variables y can take integer values larger than one. When the costs satisfy the Wagner-Whitin property (p t ≤ h t + p t-1 ) [START_REF] Pochet | Polyhedra for lot-sizing with Wagner-Whitin costs[END_REF]) there exists an optimal solution for this model for which the stock is minimal with respect to when setups occur, that is, for fixed y, the stock variables s have the minimum feasible values. The solution (s, x, y) is a stock-minimal solution of (1)-(3) if and only if

s k = max max t≤k (L k i=t y i - k i=t d i ) + , max t≥k+1 ( t i=k+1 d i -C t i=k+1 y i ) + ,
for all 0 ≤ k ≤ n and (s, x, y) satisfies ( 1) and (3) (see [START_REF] Van Vyve | A Solution Approach of Production Planning Problems based on Compact Formulations for Single-Item Lot-Sizing Models[END_REF]). This implies that the dominant of the stock minimal solutions (the set of (s ′ , x, y) such that there exists s ≤ s ′ with (s, x, y) satisfying ( 1)-( 3)) is the feasible set of the following model.

s k ≥ L k i=t y i - k i=t d i , 1 ≤ t ≤ k ≤ n, (4)
s k ≥ t i=k+1 d i -C t i=k+1 y i , 1 ≤ k + 1 ≤ t ≤ n, (5)
y t ∈ Z + 1 ≤ t ≤ n, (6)
s ≥ 0.

(7) [START_REF] Constantino | A Polyhedral Approach to Production Planning Models: Start-up Costs and Times, and Lower Bounds on Production[END_REF][START_REF] Constantino | Lower bounds in lot-sizing models: a polyhedral study[END_REF] describes valid inequalities for ( 4)-( 7) when C is very large (C ≥ n i=k+1 d i ). The inequalities described in this paper are strong in the more general case where L divides C exactly. We show that for k fixed, these inequalities describe the convex hull of solutions for (4)-( 7) when C is large.

To relate ( 4)-( 7) to P M M IX for a fixed k, let s = s k and define z t = -k i=t y i , b t = -k i=t d i , for 1 ≤ t ≤ k and z t = t i=k+1 y i , b t = t i=k+1 d i for k+1 ≤ t ≤ n. This yields the model P M M IX with extra constraints coming from the nonnegativity of the y t variables,

z 1 ≤ • • • ≤ z k ≤ 0 ≤ z k+1 ≤ • • • ≤ z n . Observe that we also have b 1 ≤ • • • ≤ b k ≤ 0 ≤ b k+1 ≤ • • • ≤ b n .

Lot Sizing with Startups

Consider now a single-item lot-sizing model with startups and capacities. max (f t y t + g t w t + p t x t + h t s t ) (8)

s t-1 + x t = d t + s t , 1 ≤ t ≤ m (9) x t ≤ Ky t , 1 ≤ t ≤ m, ( 10
) y t -y t-1 ≤ w t ≤ y t , 1 ≤ t ≤ m, (11) y t , w t ∈ {0, 1}, 1 ≤ t ≤ m. ( 12
)
where d t ≥ 0 and g t is the startup cost, incurred if there is a set up in period t and no setup in period t -1. We consider a relaxation of ( 9)-( 12). The stock minimal solutions of this model satisfy the following inequalities, for 1 ≤ ℓ ≤ m:

s ℓ ≥ t i=ℓ+1 d i -K t i=ℓ+1 y i , ℓ + 1 ≤ t ≤ m, (13)
s ℓ ≥ t i=ℓ+1 d i -M (y ℓ + t i=ℓ+1 w i ), ℓ + 1 ≤ t ≤ m, (14)
y t , w t ∈ Z + ℓ + 1 ≤ t ≤ m, (15)
y ℓ ∈ Z + , s ≥ 0. ( 16
)
where M ≥ m i=ℓ+1 d i . In order to write ( 13)-( 16) as P M M IX , chose M to be a multiple of K and consider the following transformation for ℓ fixed:

s = s ℓ , z t = t i=1 y ℓ+i , b t = t i=1 d ℓ+i for 1 ≤ t ≤ m -ℓ = k and z t = y ℓ + t-k i=1 w ℓ+i , b t = t-k i=1 d ℓ+i for k + 1 ≤ t ≤ 2(m -ℓ) = n.
The constraints implied from the nonnegativity of the y t and w t variables are 0

≤ z 1 ≤ • • • ≤ z k and 0 ≤ z k+1 ≤ • • • ≤ z n . Observe that we have b 1 ≤ • • • ≤ b k and b t = b t-k for k + 1 ≤ t ≤ n.
In this case constraints (11) tie together variables z t for t ≤ k and t > k.

Reconsidering the set P GM IX , observe that the basic M IR inequalities obtained considering each constraint separately are s ≥ γ t (α tz t ), with α t and γ t defined as above. These inequalities can be combined by taking differences in the following way. Let U ⊆ {1, • • • , n} and let [1], . . . , [|U |] be any ordering of the elements of U such that γ

[1] ≤ γ [2] ≤ . . . ≤ γ [|U |]
. The mixed M IR (or simply mixing) inequalities [START_REF] Pochet | Lot-sizing with constant batches: Formulations and valid inequalities[END_REF], [START_REF] Günlük | Mixing MIR inequalities for mixed integer programs[END_REF]) are

s ≥ [t]∈U (γ [t] -γ [t-1] )(α [t] -z [t] ) s ≥ [t]∈U (γ [t] -γ [t-1] )(α [t] -z [t] ) + (C -γ [|U |] )(α [1] -z [1] -1), for each set U ⊆ {1, • • • , n}, with γ [0] = 0.
This paper is organized as follows. In the next section, we introduce the two-level mixed MIR inequalities for the mixing set with two divisible capacities. In Section 3 we present a polynomial time separation algorithm; based on this, we give a proof for the description of the convex hull of solutions of P M M IX in Section 4. In Section 5 we describe the extreme points and rays of conv(P M M IX ). Since there are O(|I 1 ||I 2 |) extreme points and n + 1 extreme rays, this extremal description implies both a fast optimization algorithm and a polynomial size extended formulation for P M M IX . In Section 6 we give other extended formulations based on a decomposition of the continuous variable. This approach allows us to derive an alternative convex hull proof, and we can also use it to show, in section 7, that our inequalities suffice to describe the convex hull of ( 4)-( 7) for fixed k, when C is very large. We finish with some conclusions in Section 8.

Two-level Mixing Inequalities

In this section we define the family of two-level mixing inequalities. For the remainder of the paper, we assume that the model P M M IX is normalized so that L = 1; thus we consider P M M IX as being the set of points (s, z) ∈ R × Z n satisfying the following constraints:

s + z i ≥ b i , 1 ≤ i ≤ k, (17) s + Cz i ≥ b i , k + 1 ≤ i ≤ n, (18) z ∈ Z n , (19) s ≥ 0, ( 20
)
where C > 0 is an integer. First we recall some results concerning the mixing inequalities.

Lemma 1 [START_REF] Günlük | Mixing MIR inequalities for mixed integer programs[END_REF])

Let W = {(s, z) ∈ R p × Z n : f (s) + Πθ i (z) ≥ π i , i = 1, . . . , m}
, where f (s) ≥ 0 and θ i (z) ∈ Z. Let τ i integer and 0 ≤ γ i ≤ Π be defined such that π i = (τ i -1)Π + γ i , γ 0 = 0, and suppose w.l.g. that

γ 1 ≤ γ 2 ≤ • • • ≤ γ m . Let S = {i 1 , . . . , i |S| } ⊆ {1, . . . , m} with 0 = i 0 ≤ i 1 ≤ • • • ≤ i |S| .
The following mixed-MIR (or mixing) inequalities are valid for W :

f (s) ≥ |S| t=1 (γ it -γ i t-1 )(τ it -θ it (z)) (21) f (s) ≥ |S| t=1 (γ it -γ i t-1 )(τ it -θ it (z)) + (Π -γ i |S| )(τ i 1 -1 -θ i 1 (z)). ( 22
)
Note that we have very slightly extended the original notation by allowing τ i to be defined either as ⌈π i /Π⌉, in which case 0 < γ i ≤ Π (as in the original paper [START_REF] Günlük | Mixing MIR inequalities for mixed integer programs[END_REF]), or as ⌊π i /Π⌋ + 1 so that 0 ≤ γ i < Π. Indeed, when π i is not a multiple of Π, both definitions are equivalent. If π i is a multiple of Π, then it is readily checked that both definitions yield the same inequality ( 22), and also that inequality ( 21) is redundant in the two cases.

Lemma 2 Let (s, z) ∈ R p × R n . Under the conditions of Lemma 1, a most violated mixed-M IR inequality is given by a set S = {i 1 , . . . , i |S| } such that 1. τ i 1 -θ i 1 (z) ≥ τ i 2 -θ i 2 (z) ≥ • • • ≥ τ i |S| -θ i |S| (z); 2. τ it -θ it (z) ≥ τ i -θ i (z), for i : i t-1 < i < i t , t = 1, . . . , |S|; 3. either 1 ≥ τ i 1 -θ i 1 (z), in which case τ i |S| -θ i |S| (z) ≥ 0; 0 ≥ τ i -θ i (z),
for i : i > i |S| ; and the most violated inequality is ( 21);

or τ i 1 -θ i 1 (z) -1 ≥ 0, in which case τ i |S| -θ i |S| (z) ≥ τ i 1 -θ i 1 (z) -1; τ i 1 -θ i 1 (z)-1 ≥ τ i -θ i (z)
, for i > i |S| ; and the most violated inequality is (22).

Proof: The proof is discussed in [START_REF] Pochet | Polyhedra for lot-sizing with Wagner-Whitin costs[END_REF] and [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF]. 2

Note that it is possible that the indices in S satisfying 1 and 2 above may satisfy τ i 1θ i 1 (z) = 1, in which case each of the inequalities (21) and (22) defined by this set will be most violated inequalities. Now let I 1 = {1, . . . , k}, I 2 = {k + 1, . . . , n} and I = I 1 ∪ I 2 . Then we can see that the set P M M IX defines two intersecting mixing sets, one based on s and the variables in I 1 , in which Π = 1, and the other based on s and the variables in I 2 , in which Π = C, in both cases θ i (z) = z i .

Example 1

Consider the following instance of P M M IX in which n = 4, k = 2, C = 5 and the right hand-side vector b is equal to [3.8, 5.3, 1.6, 9.9] (from [START_REF] Van Vyve | A Solution Approach of Production Planning Problems based on Compact Formulations for Single-Item Lot-Sizing Models[END_REF]):

s + z 1 ≥ 3.8 (23) s + z 2 ≥ 5.3 (24) s + 5z 3 ≥ 1.6 (25) s + 5z 4 ≥ 9.9 (26) z i ∈ Z i ∈ {1, 2, 3, 4} (27) s ≥ 0. ( 28
)
Thus I 1 = {1, 2} and I 2 = {3, 4}. The first two inequalities (for variables in I 1 ) and ( 28) define a mixing set with unit capacity. Equations ( 25)-( 26) (for variables in I 2 ) and (28) define another mixing set with capacity 5. Thus we can use Lemma 1 to define the following valid inequality for P M M IX : s ≥ 0.3(6z 2 ) + 0.5(4z 1 ).

Here Π = 1, f (s) = s, θ i (z) = z i for i = 1, 2. Also, τ 1 = 4 and τ 2 = 6, and γ 1 = 0.8 and γ 2 = 0.3. The inequality listed is then given by ( 21) when S = {1, 2}.

Likewise, we can use Lemma 1 to define

s ≥ 1.6(1 -z 3 ) + 3.3(2 -z 4 ) + 0.1(0 -z 3 ),
which is valid for P M M IX . This inequality results from ( 22) when S = {3, 4}, because we can take Π = 5, f (s) = s, θ i (z) = z i for i = 3, 4. 2 Now we will discuss how to define strong valid inequalities for P M M IX that have nonzero coefficients for variables in both I 1 and I 2 . To do this, we first define κ i = ⌈b i ⌉, η i = b i -(κ i -1) for i ∈ I 1 and η 0 = 1.

In addition, we let

α i = ⌈ b i C ⌉ and δ i = b i -(α i -1)C for i ∈ I 2 . Also, let κ i = ⌈δ i ⌉ and η i = δ i -(κ i -1) for i ∈ I 2 . Note that these definitions imply that b i = (κ i -1) + η i , i ∈ I 1 , b i = (α i -1)C + δ i = (α i -1)C + (κ i -1) + η i , i ∈ I 2 .
Observe that 0 < κ i ≤ C for i ∈ I 2 and 0 < η i ≤ 1 for i ∈ I. For notational convenience, we also define κ 0 = 0 and η 0 = 1.

Throughout, we assume that 0 < η i < 1, i ∈ I 1 , and that 0 < δ i < C, i ∈ I 2 . Relaxing this assumption does not affect most of the results we derive, but making it sometimes reduces the number of cases that must be considered and makes notation easier.

We also suppose without loss of generality that δ k+1 ≤ δ k+2 ≤ . . . ≤ δ n .

Finally, for i ∈ I 2 ∪ {0} and j ∈ I ∪ {0}, let

κ j i = κ i if η i ≥ η j κ i -1 if η i < η j .
Note that an equivalent definition of κ j i is

κ j i = min{κ ∈ Z : κ ≥ κ i + η i -η j }. Thus, κ j
i is the lowest value the integral part of s can take keeping (18) satisfied for i, if z i = α i -1 and η j is the fractional part of s for some j ∈ I ∪ {0} \ {i} (except when j = 0 or δ j is integer, in which case η j = 1).

Note also that κ j 0 = κ 0 = 0 for all j ∈ I ∪ {0}. These quantities will be essential in defining the two-level mixing inequalities.

The next result is also helpful in defining the new inequalities. In addition, it will be important in characterizing separation and in showing that they define the convex hull of P M M IX .

Lemma 3 For every j ∈ I ∪ {0},

0 = κ j 0 ≤ κ j k+1 ≤ κ j k+2 ≤ • • • ≤ κ j n . (29)
Proof: As δ i ≤ δ i+1 implies κ i ≤ κ i+1 , the only nontrivial case is when κ j i = κ i and κ j i+1 = κ i+1 -1. In this case we must have η i+1 < η j ≤ η i , so

κ i = δ i -η i + 1 < δ i+1 -η i+1 + 1 = κ i+1 2
We will now use Lemma 1 twice to build the two-level mixing inequalities. The first step uses Lemma 1 to define, for each i ∈ I 2 ∪ {0}, a set of inequalities involving the variables in I 2 ∪ {0} that can then be mixed with simple M IR inequalities involving variables in I 1 .

Lemma 4 Let S = {i 1 , . . . , i |S| } ⊆ I 2 , with 0 = i 0 < i 1 < • • • < i |S| ,
and let j ∈ I 2 ∪ {0}. The following inequalities are valid for P M M IX :

s + 1 -η j ≥ |S| t=1 (κ j it -κ j i t-1 )(α it -z it ) (30) s + 1 -η j ≥ |S| t=1 (κ j it -κ j i t-1 )(α it -z it ) + (C -κ j i |S| )(α i 1 -1 -z i 1 ). ( 31
)
Proof: from (18) and the definition of α i , κ i and η i , we have

s + 1 -η i + Cz i ≥ (α i -1)C + κ i . Now if η i ≥ η j we can write s + 1 -η j + Cz i ≥ (α i -1)C + κ i ; if η i < η j , as η i ≥ 0 and η j ≤ 1, we have s + 1 -η j + Cz i ≥ (α i -1)C + κ i -1. Thus s + 1 -η j + Cz i ≥ (α i -1)C + κ j i for i ∈ I 2 . ( 32
)
Define f (s) = s + 1η j , which is nonnegative because s ≥ 0 and η j ≤ 1, Π = C, θ i (z) = z i , and π i = (α i -1)C + κ j i . Thus ⌈π i /Π⌉ = α i and γ i = κ j i . The validity of the inequalities follows from Lemma 1.2

Example 1 (continued) We can compute the following values 0 1 2 3 4 α 1 2 δ 1.6 4.9 κ 4 6 2 5 η 1 0.8 0.3 0.6 0.9; then the following table holds the values of κ j i :

κ j i i = 3 i = 4 j = 0 1 4 j = 1 1 5 j = 2 2 5 j = 3 2 5 j = 4 1 5.
Recall that κ j 0 = κ 0 = 0 for all j ∈ I ∪ {0}. Now if we take S = {3, 4} and j = 3, then inequalities (30) and (31) both yield

s + 1 -0.6 = s + 0.4 ≥ 2(1 -z 3 ) + 3(2 -z 4 ).
(33) which follows from the fact that both s+0.4 ≥ 2(1-z 3 ) and s+0.4 ≥ 5(2-z 4 ) are valid for P M M IX .

Similarly, if we take j = 4, then inequalities ( 30) and (31) both yield

s + 1 -0.9 = s + 0.1 ≥ 1(1 -z 3 ) + 4(2 -z 4 ). ( 34
)
If we take j = 0, then inequalities ( 30) and (31) respectively yield

s + 1 -1 = s ≥ 1(1 -z 3 ) + 3(2 -z 4 ), (35) s + 1 -1 = s ≥ 1(1 -z 3 ) + 3(2 -z 4 ) + (-z 3 ). ( 36
)
2

The next Proposition follows from Lemmas 2 and 4.

Proposition 5 Given (s, z) ∈ R × R |I 2 |
, the most violated inequality ( 30) or ( 31), for every

j ∈ I 2 ∪ {0}, is determined by a set S = {i 1 , . . . , i |S| } ⊆ I 2 , with i 1 < • • • < i |S| such that 1. α i 1 -zi 1 ≥ α i 2 -zi 2 ≥ • • • ≥ α i |S| -zi |S| ; 2. α it -zit ≥ α i -zi , for i t-1 < i < i t , t = 2, . . . , |S| and k < i < i 1 ; 3. either 1 ≥ α i 1 -zi 1 , in which case α i |S| -zi |S| ≥ 0; 0 ≥ α i -zi , for i : i > i |S| ;
and the most violated inequality is (30);

or α i 1 -zi 1 -1 ≥ 0, in which case α i |S| -zi |S| ≥ α i 1 -zi 1 -1; α i 1 -zi 1 -1 ≥ α i -zi , for i : i > i |S| ;

and the most violated inequality is (31).

Now for S ⊆ I 2 , again let {i t } be any ordering of S such that 0 = i 0 < i 1 < ... < i |S| . Then for each j ∈ I 2 ∪ {0}, define

ψ j S (z) = |S| t=1 (κ j it -κ j i t-1 )(α it -z it ), ( 37
)
φ j S (z) = ψ j S (z) + (C -κ j i |S| )(α i 1 -1 -z i 1 ). ( 38
)
Note that these expressions are the right hand sides of the inequalities ( 30) and ( 31), respectively. Note also that, for each j ∈ I 1 , s + 1η j ≥ κ jz j is valid for P M M IX (from ( 17) and the definition of η j and κ j ). This motivates us to define, for any j ∈ I ∪ {0} and any S ⊆ I 2 ,

θ j,r S (z) =      κ j -z j if j ∈ I 1 ψ j S (z) if j ∈ I 2 ∪ {0} and r = 0 φ j S (z) if j ∈ I 2 ∪ {0} and r = 1.
Using this definition,

s + 1 -η j ≥ θ j,r S (z) ( 39
)
is a valid inequality for any j ∈ I ∪ {0}, regardless of the choices of S and r.

Proposition 6 Let U 1 ⊆ I 1 , U 2 ⊆ I 2 ∪ {0}, U = U 1 ∪ U 2 and suppose U = {j 1 , . . . , j |U | } with 0 = η j 0 ≤ η j 1 ≤ • • • ≤ η j |U | . For each j u ∈ U 2 let r u ∈ {0, 1} and S u ⊆ I 2 .
The following inequalities are valid for P M M IX :

s ≥ |U | u=1 (η ju -η j u-1 )θ juru Su (z), (40) s
≥ |U | u=1 (η ju -η j u-1 )θ juru Su (z) + (1 -η j |U | )(θ j 1 r 1 S 1 (z) -1) (41)
Proof: Rewriting (39), we have that sθ j,r S (z) ≥ η j -1 for every j ∈ U and r ∈ {0, 1}. The result follows from Lemma 1 with Π = 1, π j = η j -1, so τ j = ⌈ η j -1 1 ⌉ = 0 and γ j = η j . 2 Many of the above inequalities are dominated. Given a point (s, z) ∈ R × Z n , the inequality (40) or (41) yielding the largest right hand side is such that, for each j ∈ U , the corresponding term θ j,r S (z) is of maximum value among all possible choices of the set S and r. From Proposition 5 (properties 1 and 2), it follows that for j ∈ U 2 , the set S * maximizing θ j,r S (z) is the same for every j. From Proposition 5 (property 3), r takes the same value for every j.

From this Proposition and the definition of κ ℓ i , it follows that S ∪ {0} ⊇ U 2 . To see this, suppose that j ∈ U 2 and j / ∈ S ∪ {0}. Let ℓ be an index in S ∪ {0} such that η ℓ = min{η i : i ∈ S ∪ {0} and η i ≥ η j }. Such an index always exists as η j ≤ 1 = η 0 . Observe that we have κ ℓ i = κ j i for i ∈ S, so ψ ℓ S (z) = ψ j S (z) and φ ℓ S (z) = φ j S (z). Thus, from Proposition 5, it follows that inequalities ( 40) and ( 41) with j ∈ U 2 , are dominated by corresponding inequalities where j is replaced by ℓ or j is simply removed from U 2 .

From the above discussion, we have θ j,0 S (z) = ψ j S (z) and θ j,1 S (z) = φ j S (z) for j ∈ S ∪ {0}. Define, for j ∈ I 1 , ψ j S (z) = φ j S (z) = κ jz j . Thus the non-dominated inequalities are of one of the four following types:

s ≥ |U | u=1 (η ju -η j u-1 )ψ ju S (z), ( 42
) s ≥ |U | u=1 (η ju -η j u-1 )φ ju S (z), (43)
s ≥ |U | u=1 (η ju -η j u-1 )ψ ju S (z) + (1 -η j |U | )(ψ j 1 S (z) -1), ( 44
) s ≥ |U | u=1 (η ju -η j u-1 )φ ju S (z) + (1 -η j |U | )(φ j 1 S (z) -1), (45)
where

U = U 1 ∪U 2 = {j 1 , . . . , j |U | } with 0 = η j 0 ≤ η j 1 ≤ • • • ≤ η j |U | , U 1 ⊆ I 1 , S ⊆ I 2 , and U 2 ⊆ S ∪ {0}.
Observe that if 0 ∈ U , as η 0 = η j |U | = 1, then (42) (resp. ( 43)) and (44) (resp. ( 45)) yield the same inequality, and so we do not need to consider (44) and (45) when 0 ∈ U . We will see later that when 0 / ∈ U inequalities of the form ( 42) and ( 43) are dominated by inequalities ( 44) and ( 45).

Example 1 (continued) Note that we can rewrite (23) as

s + 1 -0.8 = s + 0.2 ≥ 4 -z 1 .
Thus, if we choose U 2 = S = {3, 4} and U 1 = {1}, (42) and (43) both yield

s ≥ 0.6 [2(1 -z 3 ) + 3(2 -z 4 )] + 0.2 [4 -z 1 ] + 0.1 [1(1 -z 3 ) + 4(2 -z 4 )] ,
(46) while ( 44) and (45) both yield

s ≥ 0.6 [2(1 -z 3 ) + 3(2 -z 4 )] + 0.2 [4 -z 1 ] + 0.1 [1(1 -z 3 ) + 4(2 -z 4 )] + 0.1 [2(1 -z 3 ) + 3(2 -z 4 ) -1] . (47)
If we choose S = {3, 4}, U 2 = S ∪ {0} = {0, 3, 4}, and U 1 = {1}, then ( 42) and (44) both yield

s ≥ 0.6 [2(1 -z 3 ) + 3(2 -z 4 )] + 0.2 [4 -z 1 ] + 0.1 [1(1 -z 3 ) + 4(2 -z 4 )] + 0.1 [1(1 -z 3 ) + 3(2 -z 4 )] , (48)
while ( 43) and (45) both yield

s ≥ 0.6 [2(1 -z 3 ) + 3(2 -z 4 )] + 0.2 [4 -z 1 ] + 0.1 [1(1 -z 3 ) + 4(2 -z 4 )] + 0.1 [1(1 -z 3 ) + 3(2 -z 4 ) + (-z 3 )] , ( 49
)
which coincidentally is the same inequality as (47). Note that Proposition 5 tells us that this choice of S maximizes both ψ j S (z) and φ j S (z), for j = 0, 3, 4, if and only if

1 -z 3 ≥ 2 -z 4 ≥ -z 3 and 2 -z 4 ≥ 0. ( 50
)
It is instructive to note that, given (50), ( 46) is always dominated by ( 48).

We will see that this holds in general: inequalities of the forms ( 42) and ( 43) in which 0 / ∈ U are always dominated by other inequalities in which 0 ∈ U . Given (50), there is one more implication worthy of note. If and only if

1 -z 3 ≥ 1 ⇐⇒ z 3 ≤ 0 ⇐⇒ φ j S (z) ≥ ψ j S (z)
, then each of ( 47) and ( 49) dominates (48). 2

Separation

The development of the separation algorithm for the Two-Level Mixing Inequalities parallels the development necessary to define (42)-( 45). It is easiest to consider separation in two main phases: 1) defining which sets U 1 , U 2 , and S define the inequality; and 2) computing the coefficients of each variable in the inequality based on which sets we choose. We will show how to do the first phase in O(n log(n)), and how to do the second in O(n), thus defining an O(n log(n)) separation algorithm for the inequalities (42)-(45).

Choosing the Sets

We first prove a Lemma that, given a point, will help us to identify which of the two-level mixing inequalities is most violated by that point.

Lemma 7 Let S ⊆ I 2 , S = {i 1 , . . . , i |S| }, with i 1 < • • • < i |S| , be a set satisfying 1 and 2 in Proposition 5. Then 1. ψ j S (z) ≥ 0 for j ∈ I 2 ∪ {0} 2. φ j S (z) ≥ 0 if α i 1 -z i 1 -1 ≥ 0 for j ∈ I 2 ∪ {0} 3. ψ j S (z) ≥ ψ ℓ S (z) if η j ≤ η ℓ , j, l ∈ I 2 ∪ {0} 4. φ j S (z) ≥ φ ℓ S (z) if η j ≤ η ℓ , j, l ∈ I 2 ∪ {0} Proof: Define α i |S|+1 -z i |S|+1 = 0. For j ∈ I 2 , ψ j S (z) = |S| t=1 (κ j it - κ j i t-1 )(α it -z it ) = |S| t=1 κ j it (α it -z it ) -(α i t+1 -z i t+1 ) . Since S satisfies conditions of Proposition 5, α it -z it ≥ α i t+1 -z i t+1 , so ψ j S (z) ≥ 0. If η j ≤ η ℓ then κ j it -κ ℓ it = 1 if η j ≤ η it < η ℓ 0 otherwise, so ψ j S (z) -ψ ℓ S (z) = it∈S:η j ≤η i t <η ℓ (α it -z it ) -(α i t+1 -z i t+1 ) ≥ 0. ( 51
)
The other inequalities follow from the definition of φ j S (z). 2

Observation 8 The following are consequences of Lemma 7 .

1. Since η 0 = 1 ≥ η j for all j and ψ 0 S (z) ≥ 0 or φ 0 S (z) ≥ 0 when α i 1z i 1 -1 ≥ 0, the most violated inequalities of the form ( 42) or ( 43) always have 0 ∈ U , so j |U | = 0 in this case. We noticed before that inequalities ( 44) and ( 45) are the same as ( 42) and ( 43) respectively when 0 ∈ U .

2. The set of inequalities 0 ≥ ψ j S (z) and 0 ≥ φ j S (z) for j :

η j > η j |U | is vacuously satisfied when j |U | = 0, because 1 = η 0 ≥ η j for all j.
The following proposition characterizes the most violated inequality ( 42)-( 45), and it follows from Lemmas 2 and 7 and Proposition 5.

Proposition 9 Given (s, z) ∈ R × R |I| , the most violated inequality ( 42)-( 45), is determined by the choice of sets U 1 ⊆ I 1 , S ⊆ I 2 , and

U 2 ⊆ S ∪ {0}, where S = {i 1 , . . . , i |S| }, with i 1 < • • • < i |S| and U = U 1 ∪U 2 = {j 1 , . . . , j |U | } with 0 = η j 0 ≤ η j 1 ≤ • • • ≤ η j |U | , satisfying 1. α i 1 -zi 1 ≥ α i 2 -zi 2 ≥ • • • ≥ α i |S| -zi |S| ; 2. α it -zit ≥ α i -zi , for i : i t-1 < i < i t , t = 1, . . . , |S|, i 0 = k 3. if 1 ≥ α i 1 -zi 1 : (a) α i |S| -zi |S| ≥ 0; (b) 0 ≥ α i -zi , for i : i > i |S| ; (c) ψ j 1 S (z) ≥ ... ≥ ψ j |U | S (z) ≥ ψ j 1 S (z) -1; (d) ψ ju S (z) ≥ ψ j S (z), for j : η j u-1 < η j < η ju , u = 1, . . . , |U |; (e) if ψ 0 S (z) ≥ ψ j 1 S (z) -1, then j |U | = 0 and the most violated in- equality is of type (42); if ψ j 1 S (z) -1 ≥ ψ 0 S (z), then 0 / ∈ U , ψ j 1 S (z) -1 ≥ ψ j S (z) for j : η j > η j |U | ,

and the most violated inequality is of type (44).

if α

i 1 -zi 1 -1 ≥ 0: (a) α i |S| -zi |S| ≥ α i 1 -zi 1 -1; (b) α i 1 -zi 1 -1 ≥ α i -zi , for i : i > i |S| ; (c) φ j 1 S (z) ≥ ... ≥ φ j |U | S (z) ≥ φ j 1 S (z) -1; (d) φ ju S (z) ≥ φ j S (z), for j : η j u-1 < η j < η ju , u = 1, . . . , |U |; (e) if φ 0 S (z) ≥ φ j 1 S (z) -1, then j |U | = 0 and the most violated inequal- ity is of type (43); if φ j 1 S (z) -1 ≥ φ 0 S (z), then 0 / ∈ U , φ j 1 S (z) -1 ≥ φ j S (z) for j : η j > η j |U | ,

and the most violated inequality is of type(45).

Observe that Lemma 7 shows that many of the inequalities in items (c) and (d) in Proposition 9 are redundant, because they are implied by conditions 1 and 2 and the definitions of ψ j S (•) and φ j S (•).

One of the implications of Proposition 9 is that separating for the most violated two-level mixing inequality amounts to 1) choosing the best set S ⊆ I 2 and then 2) choosing the best set U ⊆ I 1 ∪ S ∪ {0}. The first can be done essentially by sorting values of α izi , i ∈ I 2 ; the second can be done essentially by sorting values of ψ j S (z) or φ j S (z) (depending on whether or not α i 1zi 1 ≥ 1), j ∈ I 1 ∪ S ∪ {0}.

Note that we can compute ψ j S (z), j ∈ S ∪ {0}, by first computing ψ 0 S (z) and then applying (51), accordingly to the ordering η j |U | , • • • , η j 1 , η j 0 . Thus, we can compute the set of all these values in time O(n). Hence the complexity is dominated by two orderings of n coefficients at most.

We have now proved the following.

Proposition 10 Given a point (s, z), the sets defining the most violated inequality of the forms ( 42)-( 45) can be identified in O(n log n).

This is remarkable, given that separating for the original mixing inequalities themselves takes only O(n log n). Note that we need to do more work to actually define the inequality that is defined by the sets referred to in Proposition 10: we need to determine the coefficients of each of the variables. This is the subject of the next subsection.

Computing the Coefficients

Let U 1 ⊆ I 1 , S ⊆ I 2 and U 2 ⊆ S ∪ {0} be given. We can write inequality (42) as s ≥

[i]∈U 1 (η [i] -η [i-1] )(κ [i] -z [i] ) + i∈S A i (α i -z i ),
where

A i = [t]∈U 2 (η [t] -η [t-1] )(κ [t] i -κ [t]
i-1 ).

Observe that

κ [t] i -κ [t] i-1 =      κ i -κ i-1 + 1 if η i-1 < η [t] ≤ η i κ i -κ i-1 -1 if η i < η [t] ≤ η i-1 κ i -κ i-1 otherwise.
Therefore

A i = (κ i -κ i-1 ) [t]∈U 2 (η [t] -η [t-1] ) + [t]∈U 2 η i-1 <η [t] ≤η i (η [t] -η [t-1] ) - [t]∈U 2 η i <η [t] ≤η i-1 (η [t] -η [t-1] ) = (κ i -κ i-1 )G [|U |] + (G i -G i-1 ) + -(G i-1 -G i ) + = (κ i -κ i-1 )G [|U |] + (G i -G i-1 )
where

G i = [t]∈U 2 η [t] ≤η i (η [t] -η [t-1] ) and U = U 1 ∪ U 2 . All values G i can be computed in O(n) time using the recurrence G [t] = G [t-1] + η [t] -η [t-1] if [t] ∈ U 2 0 otherwise.
Then, computing each coefficient A i can be done in constant time.

The computation of the coefficients of inequalities ( 43),( 44), and (45) can be done in a similar way.

The Convex Hull

In this section we show that the convex hull of P M M IX is described by inequalities ( 42)-( 45). This is done by showing that each face defined by any of those inequalities is integral, that is, all the extreme points in each face have integer coordinates z. We will refer to faces of polyhedra as being "integral" with this meaning throughout the paper. Then we discuss the possibility of adding other constraints to the system (42)-(45), while keeping integrality. We start with an important Lemma.

Lemma 11 Let

P n = {z ∈ R n : Az ≤ b} be an integral polyhedron in R n . Assume that ψ 1 (•), ψ 2 (•) are linear functions, that ψ 1 (z) ≥ ψ 2 (z) is implied by Az ≤ b, and that ψ j (z) ∈ Z if z ∈ Z n , j = 1, 2. Then the polyhedron P n+1 = {(z, y) ∈ R n × R 1 : Az ≤ b, ψ 1 (z) ≥ y ≥ ψ 2 (z)} is integral in R n+1 .
Proof: Consider some extreme point (z, ȳ) of P n+1 . Note that ψ 1 (z) > ȳ > ψ 2 (z) cannot hold, because otherwise we could easily construct two points of which (z, ȳ) is a convex combination.

If ψ 1 (z) = ȳ, then z must be an extreme point of P n . Otherwise, we can write

z = K k=1 λ k z k with z k ∈ P n , λ k ≥ 0 for k = 1 • • • K and K k=1 λ k = 1. Then taking y k = ψ 1 (z k ), k = 1, ..., K would yield (z, ȳ) = K k=1 λ k (z k , y k ),
with (z k , y k ) ∈ P n+1 , contradicting the fact that (z, ȳ) is an extreme point of P n+1 . Since z is an extreme point of P n , it must be integral. But then the conditions of the Lemma tell us that ȳ must also be integer. If ψ 2 (z) = ȳ, the argument is similar. 2 Observe that the above result remains valid if only one of the functions ψ 1 (z) or ψ 2 (z) is considered Proposition 12 Each (non-dominated) face of the polyhedron ( 42)-( 45) is integral.

Proof: The proof splits naturally into four cases, one each for ( 42), (43) (44), and (45). We will only give the proof for faces defined by nondominated inequalities of the form (42), since the proofs of the others parallel this one closely.

Consider such a face F, as the set of points satisfying ( 42)-( 45) and

s = |U | u=1 (η ju -η j u-1 )ψ ju S (z), (52)
for some

U = U 1 ∪ U 2 = {j 1 , . . . , j |U | } with 0 = η j 0 ≤ η j 1 ≤ • • • ≤ η j |U | , U 1 ⊆ I 1 , S ⊆ I 2 , and U 2 ⊆ S ∪ {0}.
Observe that for all (s, z) ∈ F, the right-hand side of (52) must be maximum over all inequalities of the forms (42) to (45) evaluated at z. Proposition 9 implies that the set S ⊂ I 2 maximizing the right-hand side of (52) for all (s, z) ∈ F must satisfy the following system of inequalities for all (s, z) ∈ F :

1 ≥ α i 1 -z i 1 ≥ ... ≥ α i |S| -z i |S| ≥ 0 (53) α it -z it ≥ α i -z i for i : κ i t-1 ≤ κ i ≤ κ it , t = 1, ..., |S| (54)
0 ≥ α i -z i for i : κ i > κ |S| , (55)
where i 1 , ..., i |S| is an ordering of the elements of S such that κ i 1 ≤ ... ≤ κ i |S| .

From Proposition 9 we also know that 0 ∈ U 2 must be true, and that

ψ j 1 S (z) ≥ ... ≥ ψ j |U | S (z) = ψ 0 S (z) ≥ 0 (56) ψ 0 S (z) ≥ ψ j 1 S (z) -1 (57) ψ ju S (z) ≥ ψ j S (z) for j : η j u-1 < η j < η ju , u = 1, ..., |U | (58)
must hold.

From here the proof proceeds by induction on the cardinality of I 1 . If |I 1 | = 0, then the constraints ( 56) and ( 57) are implied by the constraints (53) (recall Lemma 7).

Moreover, we must have U = U 2 = S ∪ {0}. To see this, suppose ℓ is such that ℓ ∈ S ∪ {0}, ℓ / ∈ U = ∅, and η ju ≥ η ℓ ≥ η j u-1 . Let U ′ = U ∪ {ℓ}. The difference between the right hand sides of the inequalities corresponding to U ′ and U is (η ℓη j u-1 )(ψ ℓ S (z)ψ ju S (z)) ≥ 0, where this last inequality follows from (56), considering U ′ instead of U . If U = ∅ then a similar argument can be used.

Therefore the constraints (58) are satisfied vacuously for j ∈ S. Observe that if j ∈ I 2 \ S, then (58) together with (51) impose that some constraints ( 53) are satisfied at equality, namely (α itz it ) = (α i t+1z i t+1 ) for i t ∈ S : η ju ≤ η it < η j . The result follows because ( 53)-( 55) is a totally unimodular system [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF]).

If |I 1 | ≥ 1, let j ∈ I 1 . Considering only variables indexed in I 1 \ {j} and I 2 , by the induction hypothesis, the polyhedron defined by the system (53)-( 58) is integral. Now we consider the additional constraints involving variable z j . Let y = κ jz j . Consider the system (53)-( 58) defined for variables indexed in I 1 \ {j} and I 2 ; let this be the system Az ≤ b defined in Lemma 11.

Suppose first that j / ∈ U . The only additional constraint in the system (53)-( 58) is ψ ju S (z) ≥ y for some j u ∈ U with η j < η ju . Then the integrality of the new system follows from Lemma 11, taking ψ 1 (z) ≡ ψ ju S (z). Now suppose that j ∈ U . Since 0 ∈ U , it follows that j |U | = 0 ∈ U 2 . Hence j = j |U | . We distinguish two cases: j = j k with 1 < k < |U | and j = j 1 .

In the first case, the additional constraints involving variable z j are (with y = κ jz j )

ψ j k-1 S (z) ≥ y ≥ ψ j k+1 S (z) (59) y ≥ ψ ℓ S (z) for ℓ ∈ I \ {j} : η j k-1 < η ℓ < η j k (60)
First observe that since ψ

j k+1 S (z) ≥ ψ ℓ S (z) for ℓ ∈ I \ {j} : η j k-1 < η ℓ < η j k+1 are in the system Az ≤ b, then constraints (60) are redundant if we consider y ≥ ψ j k+1 S (z). Since inequalities ψ j k-1 S (z) ≥ ψ j k+1 S
(z) are in the system Az ≤ b, the integrality of the new system follows from Lemma 11 with ψ 1 (z) ≡ ψ j k-1 S (z) and ψ 2 (z) ≡ ψ j k+1 S (z). Now suppose that j = j 1 . The additional constraints involving the variable z j are, (with y = κ jz j )

y ≥ ψ j 2 S (z) (61) ψ 0 S (z) + 1 ≥ y (62) y ≥ ψ ℓ S (z) for ℓ ∈ I \ {j} : η ℓ < η j 1 (63)
The proof of this case is similar to the previous one, now with ψ 1 (z) ≡ ψ 0 S (z) + 1 and ψ 2 (z) ≡ ψ j 2 S (z). 2

This result implies that all extreme points of the polyhedron defined by ( 42)-( 45) are integral. As a consequence, we have the following theorem.

Theorem 13 Inequalities ( 42)-( 45) suffice to describe the convex hull of P M M IX .

Observe that inequalities ( 17), ( 18), and (20) are a particular case of ( 42)-( 45).

If i ∈ I 1 then s + z i ≥ b i is (45) with U 1 = {i} and U 2 = S = ∅; if i ∈ I 2 then s + Cz i ≥ b i is (45) with U 1 = ∅ and U 2 = S = {i}; s ≥ 0 is (42) with U 1 = S = ∅.
Next we discuss the possibility of incorporating additional constraints into the system (42)-( 45) while keeping the integrality of the associated polyhedron. In classical mixing, i.e. when all capacities are the same, one can add any dual network flow matrix constraints without losing the integrality property [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF]). This is not the case for the set P M M IX . Indeed, even adding bound constraints on the variables z t destroy the integrality properties. We show this by an example.

Example 1 (continued) In each of the following cases, adding the indicated inequalities to the facet-defining inequalities ( 42)-( 45), yields a polyhedron having fractional extreme points.

1. z 2 ≥ z 1 ≥ 0, and z 3 ≥ z 4 ≥ 0, with the fractional point s = 59/10, z = (0, 0, 4/5, 4/5);

2. 0 ≤ z i ≤ 1 for 1 ≤ i ≤ 4
, with the fractional point s = 59/10, z = (0, 0, 0, 4/5);

3. z 1 , z 3 ≥ 0, with the fractional point s = 62/15, z = (0, 4/3, 0, 4/3),

The case (a) is natural in a lot-sizing framework. Hence it shows that inequalities ( 42)-( 45) are not sufficient to describe completely the Wagner-Whitin (or even the discrete) lot-sizing polyhedron with divisible constant lower bound and constant capacity. Case (b) shows that adding simple bounds also destroys the integrality property. Case (c) even shows that very few simple bounds are needed for the integrality property to be lost.

Although we cannot add any dual network flow matrix constraints, we can still add some inequalities and keep the integrality property, as it is established in the following corollaries.

Corollary 14 Let P A = {(s, z) : Az ≤ a}, where Az ≤ a is a system of constraints in which each constraint takes the form z i 1z i 2 ≤ a k , for some i 1 , i 2 ∈ I 2 and a k ∈ Z. Then conv(P M M IX ∩ P A ) = conv(P M M IX ) ∩ P A .

Proof: As above. The main difference is in noting that adding the constraints Az ≤ a to ( 53)-( 55) yields a TU system, and thus each of the non-dominated faces defined by such a system are integral. From there, the proof proceeds by induction as before. 42) and ( 44) in which S = {k + 1, ..., k ′ } for some k ′ such that k + 1 ≤ k ′ ≤ n.

Proof: Under the conditions of the proposition, α i = 1 and δ i = b i for i ∈ I 2 . This and the system Dz ≤ d imply that 1 ≥ α k+1z k+1 ≥ ... ≥ α nz n . Thus, Proposition 9 implies that, for any (s, z), the most violated inequality will always be defined by choosing S = {k + 1, ..., k ′ }, where k ′ = argmax i {z i < 1}. Since 1 ≥ α iz i for all i ∈ I 2 , case 3 in Proposition 9 always holds. Thus, there are no non-dominated inequalities of the form ( 43) or ( 45), and the only inequalities of the forms ( 42) and ( 44) that may be non-dominated are defined by choosing S as defined in the proposition. The result then follows from Corollary 14. 2

We will generalize further corollary 15 to encompass inequalities z 1 ≤ ... ≤ z k ≤ 0, when b 1 ≤ ... ≤ b n ≤ 0. The proof of this result uses a different approach than that used above, and is discussed in section 7.

Throughout this section, we continue to let P M M IX be given by (17-20). It is not difficult to see what the extreme rays of conv(P M M IX ) are:

Proposition 16 The extreme rays of conv(P M M IX ) are given by • the n rays z i = 1 and all other variables 0, for each i ∈ I;

• the ray s = C; z i = -C, i ∈ I 1 ; z i = -1, i ∈ I 2 .
Now we discuss extreme points. We first characterize conditions that the extreme points of conv(P M M IX ) satisfy. This will enable us to list all of the extreme points in closed form.

Proposition 17 In any extreme point (s, z), 1. either s = 0 or there exists some i ′ ∈ I such that the constraint ( 17)-( 18) is tight for i ′ .

2. z i = ⌈b i -s⌉ for all i ∈ I 1 , and

z i = ⌈ b i -s C ⌉ all i ∈ I 2 .
The proof of the proposition follows easily by contradiction. From there, we can prove

Proposition 18 any extreme point (s, z),

1. 0 ≤ s < C; 2. κ i -C -1 ≤ z i ≤ κ i , i ∈ I 1 ; 3. -1 ≤ z k+1 -α k+1 ≤ ... ≤ z n -α n ≤ 0.
Proof: The first statement follows easily by contradiction. The second statement follows from the first and from Proposition 17. The third statement follows from the first, from the fact that

α i -1 ≤ z i ≤ α i , i ∈ I 2
must hold in each extreme point, and from our assumption that δ k+1 ≤ ... ≤ δ n . 2

Using Propositions 17 and 18, we can list the extreme points of conv(P M M IX ).

(If η i ′ < η i ′′ and κ i ′′ = C, there is no extreme point defined by setting s

= κ i ′′ + η i ′ .)
Moreover, all of the extreme points of conv(P M M IX ) fall into one of the categories 1-4.

Example 1 (continued) The extreme point (64) for this example is given by

s = 0, z 1 = 4, z 2 = 6, z 3 = 1, z 4 = 2.
An extreme point of the form (65) for which i ′ = 1 is

s = 0.8, z 1 = 3, z 2 = 5, z 3 = 1, z 4 = 2.
An extreme point of the form (66) for which i ′′ = 3 is

s = 1.6, z 1 = 3, z 2 = 4, z 3 = 0, z 4 = 2.
An extreme point of the form (67) for which i ′ = 1 and i ′′ = 3 is

s = 1.8, z 1 = 2, z 2 = 4, z 3 = 0, z 4 = 2.
An extreme point of the form (68) for which i ′ = 2 and i ′′ = 3 is

s = 2.3, z 1 = 2, z 2 = 3, z 3 = 0, z 4 = 2.

2

Proof of Proposition 19: It can be checked that each of the points listed is actually an extreme point (depending on the specific value of η i , κ i , i ∈ I, some of these points may coincide). Moreover, we can use number 3 of Proposition 18 and number 1 of Proposition 17 to show that, for each i ′′ ∈ I 2 , there are at most k extreme points for which δ i ′′ < s < δ i ′′ +1 , and that for each of these both of the following hold: i) z i ′′ = α i ′′ -1, and ii) z i ′′ +1 = α i ′′ +1 . Therefore the above list contains all of the extreme points of conv(P M M IX ). 2

The convex hull of P M M IX therefore has O(|I 1 ||I 2 |) extreme points and n + 1 extreme rays. Thus we can obtain a polynomial algorithm to optimize over P M M IX by enumerating them; also, we can define an extended formulation by defining a variable for each of the extreme points and rays (see, e.g., [START_REF] Balas | Disjunctive programming[END_REF], [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF]). Rather than do this, however, we investigate a different approach to defining extended formulations for P M M IX .

Extended Formulations Based on Decomposing the Continuous Variable

Here we derive an integral extended formulation for P M M IX that is based on decomposing the stock variable into its possible values modulo L = 1. This formulation is of exponential size but it yields not only an alternative convex hull proof for the two-level mixing inequalities, but also another extended formulation of polynomial size. A more extensive development of many of the results of this section can be found in [START_REF] Van Vyve | A Solution Approach of Production Planning Problems based on Compact Formulations for Single-Item Lot-Sizing Models[END_REF].

Remember that if (s, z) is an extreme point of P M M IX , then

s = max max i∈I 1 (b t -z t ) + , max t∈I 2 (b t -Cz t ) + .
Hence, considering the extreme points of P M M IX , s can take at most n + 1 different values modulo 1, depending on which of the n + 1 constraints ( 17),( 18),( 20) is tight. The possible values are η t > 0 for i ∈ I 1 ∪ I 2 ∪ {0}, namely

η t = b t -(κ t -1), with κ t = ⌈b t ⌉ for t ∈ I 1 , η t = δ t -(κ t -1), with κ t = ⌈δ t ⌉, δ t = b t -(α t -1)C and α t = ⌈ bt C ⌉ for t ∈ I 2 , η 0 = 1
Let m be such that there are m + 1 different values among the n + 1 numbers {η t } n t=0 . Let these values be {γ i } m+1 i=1 , where γ 0 = 0 < γ 1 < . . . < γ m < γ m+1 = 1. We will use the notation [t] to denote the mapping from I 1 ∪ I 2 ∪ {0} to {1, . . . , m + 1} such that γ [t] = η t (i.e. when m = n and η t are all different, [t] is just an ordering of I 1 ∪ I 2 ∪ {0} with η t ). Note that with this definition, there is no t such that [t] = 0, and [0] = m + 1.

Example 1 (continued)

As all possible remainders are different, m = n = 4 and We can compute the following values 0 1 2 3 4 5 η 1 0.8 0.3 0.6 0.9 γ 0 0.3 0.6 0.8 0.9 1 so that

[0] = 5, [1] = 3, [2] = 1, [3] = 2, [4] = 4. 2
The following constraints force s to take values in a discrete set containing all the possible extreme values for that variable.

s = ∆ + m i=0 γ i w i , (69)
m i=0 w i = 1 (70) ∆, w ≥ 0, (71)
∆, w integer.

(72)

This restriction of the set P M M IX (considering its projection in the space of (s, z) variables) has the same convex hull as P M M IX itself as all extreme points and rays of P M M IX are part of the restriction.

We now strengthen ( 17) and ( 18) by using the decomposition of the stock. We eliminate s from ( 17)-( 18) by substitution using (69):

∆ + m i=0 γ i w i + z t ≥ b t , t ∈ I 1 , (73) ∆
+ m i=0 γ i w i + Cz t ≥ b t , t ∈ I 2 . (74)
Let P M M IX ∆,w be the set of feasible solutions to ( 19),( 70)-( 74).

Proposition 20

The following inequalities are valid for

P M M IX ∆,w : ∆ + m i=[t] w i + z t ≥ ⌈b t ⌉, t ∈ I 1 (75)
Proof. By ( 70) and ( 73),

∆ + γ [t]-1 + m i=[t] γ i w i + z t ≥ b t , t ∈ I 1 .
As ⌈b tγ [t]-1 ⌉ = ⌈b t ⌉, Chvatal-Gomory rounding yields (75). 2

We now strengthen inequalities (74). Let ℓ ∈ I 1 ∪ I 2 ∪ {0} be fixed. The following inequalities are valid.

∆ + m i=[ℓ] γ i w i + Cz t ≥ b t -γ [ℓ]-1 , t ∈ I 2 .
As C is an integer, C-G rounding yields

∆ + m i=[ℓ] w i + Cz t ≥ ⌈b t -γ [ℓ]-1 ⌉ = C(α t -1) + κ ℓ t , t ∈ I 2 , (76)
where κ ℓ t is defined as before

κ ℓ t = κ t if η t > γ [ℓ]-1 (or equivalently if η t ≥ η ℓ ), κ t -1 if η t ≤ γ [ℓ]-1 (or equivalently if η t < η ℓ ). for ℓ ∈ I 1 ∪ I 2 ∪ {0}. Considering ∆ + m i=[ℓ]
w i as a continuous variable, inequalities (76) define a mixing set for each l. Therefore, Lemma 1 implies the following result.

Proposition 21

The following inequalities are valid for P M M IX ∆,w for any

S ⊆ I 2 , l ∈ I 1 ∪ I 2 ∪ {0}: ∆ + m i=[ℓ] w i ≥ ψ ℓ S (z) (77) ∆ + m i=[ℓ] w i ≥ φ ℓ S (z) (78)
where ψ ℓ S (z) and φ ℓ S (z) defined by ( 37) and ( 38) respectively.

Proof. The result follows from Lemma 1, with

f = ∆ + m i=[ℓ] w i , Π = C and π t = C(α t -1) + κ ℓ t . 2 Example 1 (continued)
To derive the extended formulation we decompose s into ∆ multiples of 1 and a remainder. In extreme points, this remainder can only take the values 0, 0.8, 0.3, 0.6 or 0.9. Thus, we can restrict the continuous variable s as follows s = ∆ + 0w 0 + 0.3w 1 + 0.6w 2 + 0.8w 3 + 0.9w 4 ,

w 0 + w 1 + w 2 + w 3 + w 4 = 1, w 1 , w 2 , w 3 , w 4 , ∆ ∈ Z + ,
without modifying the convex hull of the solution set. We then eliminate s by substitution from ( 23)-( 26) by using this decomposition. From here we treat the two groups of inequalities in I 1 and I 2 separately.

For the two inequalities in I 1 , we just write similar inequalities as for the mixing set:

∆ + w 3 + w 4 ≥ 4 -z 1 (79) ∆ + w 1 + w 2 + w 3 + w 4 ≥ 6 -z 2 (80)
Note that inequalities ( 79)-( 80) are of the type (75). For inequalities in I 2 , we first choose one of the possible remainder, for example 0.8. That this choice is not the most clever will be shown in Proposition 22. We write

∆ + 0.8w 3 + 0.9w 4 + 5z 3 ≥ 1.6 -0.6 (81)
∆ + 0.8w 3 + 0.9w 4 + 5z 4 ≥ 9.9 -0.6

These are valid inequalities as 0.6 is an upper bound on 0w 0 + 0.3w 1 + 0.6w 2 . Since all variables are integral, we can apply C-G rounding:

∆ + w 3 + w 4 + 5z 3 ≥ 1 (83) ∆ + w 3 + w 4 + 5z 4 ≥ 10 (84)
If we consider now ∆+w 3 +w 4 as a continuous variable, these two inequalities form a mixing set with capacity 5. Thus, the following inequalities are valid.

∆ + w 3 + w 4 ≥ 1 -5z 3 (base) (85)
∆ + w 3 + w 4 ≥ 1(1 -z 3 ) (MIR) (86)
∆ + w 3 + w 4 ≥ 10 -5z 4 (base) (87)
∆ + w 3 + w 4 ≥ 5(2 -z 4 ) (MIR) (88)
∆ + w 3 + w 4 ≥ 9 -4z 4 -z 3 (Mixing, first form) (89) ∆ + w 3 + w 4 ≥ 9 -4z 4 -z 3 (Mixing, second form), (90)
With different data, these six inequalities could be different. We can apply the same procedure with each possible remainder (remember that we have chosen 0.8). Different remainders modify the left-and right-hand sides in ( 81)-( 82) differently, and yield different inequalities. Note however that because the remainders are smaller than 1 and because of Chvatal-Gomory rounding, the right hand-side of (84) can only take the values 10 or 9 (or more generally ⌈b t ⌉ or ⌈b t ⌉ -1). 2

The following proposition shows that it is not necessary to consider inequalities ( 77)-( 78) for ℓ / ∈ S ∪ {0}. However, their definition makes the proof of Proposition 23 clearer.

Proposition 22 If ℓ /

∈ S ∪ {0}, the inequalities (77)-( 78) are dominated or redundant.

Proof. Let S ⊆ I 2 and ℓ / ∈ S ∪ {0} be given, and let k = arg min t∈S∪{0} {γ

[t] | γ [t] ≥ γ [ℓ] }. As γ [0] = 1, k is well-defined and is such that κ ℓ t = κ k t for t ∈ S. Thus, both ψ k S (z) = ψ ℓ S (z) and φ k S (z) = φ ℓ S (z)
and the result follows from

w i ≥ 0 for [ℓ] ≤ i < [k]. 2
The following proposition is the main result of this section.

Proposition 23

The convex hull of P M M IX ∆,w is described by (70)-( 71), ( 75), ( 77)-( 78).

Proof. We show that for any given objective function min

h∆+ m i=0 g i w i + n i=1 f i z i , the set M (h, g, f ) of optimal solutions of P M M IX ∆,w
satisfy ( 71), ( 75), ( 77) or (78) at equality. This proves the result, since when h∆ + m i=0 g i w i + n i=1 f i z i is parallel to a facet, the only inequality that is satisfied at equality by all optimal points is the facet-defining inequality.

Because of equality (70), we can assume w.l.o.g. that min i g i = 0. Note also that we need only consider nonzero objectives, and objectives leading to bounded objective values.

(a) If f t < 0 or h < 0 then the objective is unbounded. Hence we can suppose that all costs are nonnegative. Let S = {i ∈ I 2 | f i > 0}.

(b) If h = 0, there must be a variable w i or z i with positive cost. If g i > 0, then w i = 0 in any optimal solution because min i g i = 0. If f i > 0, then the objective is unbounded. Hence we can suppose h > 0.

(c) If f t > 0 with t ∈ I 1 , then ∆ + m i=[t] w i + z t = ⌈b t ⌉ at any optimal solution. Indeed if ∆ + m i=[t] w i + z t ≥ ⌈b t ⌉ + 1, then it is profitable and feasible to decrease z t . Hence we can suppose that f t = 0 for t ∈ I 1 . Observe now that if f t = 0 for any t ∈ I 1 ∪ I 2 , then it is always possible to satisfy the corresponding inequality (73) or (74) at zero cost by increasing z t sufficiently. Thus the variable z t and the corresponding inequality (73) or (74) play no role in the optimization problem. Hence we can suppose without loss of generality that I 1 = ∅ and I 2 = S.

(d) If g i > g i+1 then w i = 0 in any optimal solution. If not, it is indeed feasible and profitable to set w i = 0 and w i+1 = 1. Hence g i form a nondecreasing sequence with g 0 = 0 (recall that min i g i = 0). Similarly, if h < g m then w m = 0 in any optimal solution. Otherwise it is profitable to increase ∆ and w 0 by 1 and set w m = 0. Let ℓ be such that

[ℓ] = min{i | g i > 0}. Hence we can suppose that h ≥ g m ≥ g m-1 ≥ . . . ≥ g [ℓ] > g [ℓ]-1 = . . . = g 0 = 0.
(e) If Ch < i∈I 2 f i , then the objective is unbounded as (∆, w, z) = (C, 0, -1) is a feasible ray.

(f ) If Ch > i∈I 2 f i , we show that M (h, g, f ) satisfy the corresponding constraint (77) at equality with ℓ and S as chosen.

Observe first that 0 ≤ ∆ ≤ C -1 since otherwise decreasing ∆ by C units and increasing each z t by one unit improves the solution. Therefore, as f t > 0, z t = α t -1 if ∆ + i γ i w i ≥ δ t and z t = α t otherwise for each t ∈ S. As δ k+1 ≤ . . . ≤ δ n , any optimal solution satisfies 1 ≥ α k+1z k+1 ≥ . . . ≥ α n -z n ≥ 0. Therefore, for each optimal solution, there exists τ ∈ {k, . . . , n} such that

α t -z t = 1 for k + 1 ≤ t ≤ τ and α t -z t = 0 for τ < t ≤ n. (91)
When τ = k, constraint (77) simplifies to ∆ + m i=[ℓ] w i ≥ 0. This inequality is clearly satisfied at equality by all optimal solutions. So we can assume τ ≥ k + 1.

Let consider τ fixed and solutions satisfying (91). The only non-dominated constraint (74) is for index t equal to τ , which is itself dominated by

∆ + m i=[τ ] w i ≥ κ τ . ( 92
)
This last relation is clearly satisfied at equality by all optimal solutions (for given τ ).

In the case [τ ] > [ℓ], the optimal solutions also satisfy w [ℓ] = w [ℓ]+1 = . . . = w [τ ]-1 = 0. This is because these variables have positive cost and do not help in satisfying (92). In the case [τ ] < ℓ, the optimal solutions also satisfy w [τ ] + w [τ ]+1 + . . . + w [ℓ]-1 = 1. This is because these variables have a striclty lower cost then all the other variables appearing in (92). Therefore, for given τ all optimal solutions will also satisfy

∆ + m i=[ℓ] w i = κ ℓ τ
It remains to observe that (77) with ℓ and S as chosen reduces to this last expression for given τ .

(g) If Ch = i∈I 2 f i , we show that M (h, g, f ) satisfy the corresponding constraint (78) at equality with ℓ and S as chosen. Let β = α k+1z k+1 . As f t > 0 for t ∈ I 2 , there exists τ ∈ I 2 = {k + 1, . . . , n} such that α tz t = β for t ≤ τ and α tz t = β -1 for t > τ.

(93)

Note that z n ≤ α n , otherwise decreasing z n improves the solution. Thus β ≥ 1.

As in part (f), for given β and τ , optimal solutions satisfying (93) will satisfy

∆ + m i=[τ ] w i ≥ κ τ + C(β -1) (94)
at equality. For exactly the same reasons also, optimal solutions will also satisfy

∆ + m i=[ℓ] w i ≥ κ ℓ τ + C(β -1)
And it suffices to observe that, for given β and τ , constraint (78) reduces exactly to this expression. 2

Proposition 23 and Theorem 13 imply that the projection of the convex hull of P M M IX ∆,w onto the (s, z) space of variables is given by ( 42)-( 45).

P M M IX ∆,w
is an extended formulation of P M M IX , but it has an exponential number of constraints. Next we give an extended formulation for P M M IX of polynomial size. What makes the extended formulation of proposition 23 be of non-polynomial size are the inequalities (77) and ( 78). These inequalities are the convex hull of the |I 2 | + 1 mixing sets defined by (76). Let us fix ℓ ∈ I 2 ∪ {0}. The following equations are an extended formulation of the mixing set (76), with ∆ + m i=[ℓ]-1 w i considered as a continuous variable. The extended variables are Γ ℓ and π ℓ t for t ∈ I 2 .

∆ +

m i=[ℓ]-1 w i = CΓ ℓ + n t=k+1 κ ℓ t π ℓ t , (95)
Γ ℓ + t:κ ℓ t ≥κ ℓ p π ℓ t + z t ≥ α p , k + 1 ≤ p ≤ n, ( 96
) n t=k+1 π ℓ t ≤ 1, (97) Γ ℓ , π ℓ ≥ 0. ( 98
)
The projection of ( 95)-( 98) onto the (∆, w) space of variables yields ( 77)-( 78). The proof is given in [START_REF] Miller | Tight formulations for some simple mixed integer programs and convex objective integer programs[END_REF], [START_REF] Van Vyve | A Solution Approach of Production Planning Problems based on Compact Formulations for Single-Item Lot-Sizing Models[END_REF]. Then proposition 23 implies the following result.

Proposition 24 The inequalities (69)-( 71),( 75) and ( 95)-( 98) for each ℓ ∈ I 2 ∪ {0} define an integral extended formulation for P M M IX with O(n 2 ) variables and O(n 2 ) constraints.

7 Uncapacitated Lot-Sizing with Lower Bounds on Production

Here we look more closely at the Mixed Integer Model for the uncapacitated (i.e. C is very large) lot-sizing variant (1)-( 3) already presented in Section 1.

We consider the submodel ( 4)-( 7) that arises considering the stock minimal solutions for a fixed period k. For notational convenience we rename s k as s and change the space of variables by z

t = k i=t y i , b t = k i=t d i , for 1 ≤ t ≤ k and z t = t i=k+1 y i , b t = t i=k+1 d i for k + 1 ≤ t ≤ n. Hence, z 1 ≥ • • • ≥ z k ≥ 0 and 0 ≤ z k+1 ≤ • • • ≤ z n . Observe that if d i ≥ 0 then we have b 1 ≥ • • • ≥ b k ≥ 0 and 0 ≤ b k+1 ≤ • • • ≤ b n . Let P DLSL bet the feasible set of the following model. s -z t ≥ -b t , 1 ≤ t ≤ k, (99) s + M z t ≥ b t , k + 1 ≤ t ≤ n, (100) z ∈ Z n , (101) s ≥ 0, ( 102
) z i ≤ z i+1 , k + 1 ≤ i ≤ n -1, ( 103
) z i ≤ z i-1 , 2 ≤ i ≤ k, ( 104
) z i ≥ 0, k ≤ i ≤ k + 1, (105)
where M ≥ max i∈I 2 b i and is integer. We show in this section that the constraints (42)-( 45) still suffice to describe the convex hull of P DLSL . However, in order to generalize Theorem 13 to encompass constraints ( 103)-( 105), we will take a different approach. We follow closely the development in the previous section. Moreover, as in Corollary 15 the number of sets S is O(n), here only O(n 2 ) constraints ( 77)-( 78) in the extended formulation are not dominated. Thus, we obtain another integral formulation of polynomial size. Most of the proofs are similar to the ones already presented in Section 6, so they are omitted here.

The details can all be found in Van Vyve [2003].

Observe first that, in P DLSL , if b i ≤ b i-1 for i ≥ k+2, then the constraint (100) for t = i is dominated by constraint (100) for t = i -1. Therefore, if b i ≤ b i-1 , the only binding constraints for variable z i are z i-1 ≤ z i ≤ z i+1 and z i ∈ Z. Relaxing the integrality of z i , z i will be integral in extreme points if and only if z i-1 and z i+1 are integral and z i-1 ≤ z i+1 in extreme points. Thus, we can suppose without loss of generality that b k+1 < b k+2 < . . . < b n . Similarly, if b i ≤ b i+1 for i ≤ k -1, then the constraint (99) for t = i + 1 is dominated by constraint (99) for t = i. Again, the only constraints on variable z i+1 are z i+2 ≤ z i+1 ≤ z i (or 0 ≤ z i+1 ≤ z i when i = k -1) and z i+1 ∈ Z. Using a similar argument, we can thus suppose without loss of generality that b

k < b k-1 < . . . < b 1 .
The rest of this section is very similar to the previous one. If (s, z) is an extreme point of P DLSL , then

s = max max 1≤t≤k (z t -b t ) + , max k+1≤t≤n (b t -M z t ) + .
So when considering extreme points of P DLSL , s can take at most n + 1 different values modulo 1, depending on which of the n + 1 constraints (99)-( 100),(102) is tight. The possible values are the following.

η i =      ⌊b i + 1⌋ -b i 1 ≤ i ≤ k, b i -⌈b i -1⌉ k + 1 ≤ i ≤ n, 1 i = 0,
Among these n + 1 numbers, there will be only m + 1 different values. Let these values be {γ i } m+1 i=1 , where 0 = γ 0 < γ 1 < . . . < 1 = γ m+1 and [t] is such that η t = γ [t] . Again, we restrict s to take its values in a discrete set by adding the following constraints. [3,2,4,6,11] and L = 7. Choosing k = 3, so s = s 3 , the corresponding model

s = ∆ + m i=0 γ i w i , (106)
P DLSL is s ≥ 7z 1 -9, s ≥ 7z 2 -6, s ≥ 7z 3 -4, s ≥ 6 -M z 4 , s ≥ 17 -M z 5 , s ≥ 0, z 1 ≥ z 2 ≥ z 3 ≥ 0, z 5 ≥ z 4 ≥ 0, z 1 , z 2 , z 3 , z 4 , z 5 ∈ Z.
Strictly speaking, this is not a problem of type DLSL as the multiplier of z 1 , z 2 and z 3 is 7 and not 1. However, it is easy to transform it to a suitable form by dividing each constraint by 7 and treating s 7 as the continuous variable.

We have n = 5, k = 3, b = [9, 6, 4, 6, 17]/7 and therefore η is equal to [5,1,3,6,3,7]

/7. So m = 4, γ = [0, 1, 3, 5, 6, 7]/7 and [0] = 5, [1] = 3, [2] = 1, [3] = 2, [4] = 4, [5] = 2. The decomposition of s is: s = 7∆ + 0w 0 + 1w 1 + 3w 2 + 5w 3 + 6w 4 w 0 + w 1 + w 2 + w 3 + w 4 = 1 2
We now strengthen (99) and (100) by using the decomposition of the stock. We eliminate s from ( 99)-(100) by substitution using (106):

∆ + m i=0 γ i w i ≥ z t -b t , t ∈ I 1 , (110)
∆ + m i=0 γ i w i ≥ b t -M z t , t ∈ I 2 . ( 111
) (112) Let P DLSL ∆,w
be the set of feasible solutions to (101)-( 105),( 107)-( 110).

Proposition 25

The following inequalities are valid for P DLSL ∆,w :

∆ + m i=[t] w i ≥ z t -⌊b t ⌋, t ∈ I 1 (113) ∆ + m i=[ℓ] w i ≥ ⌈b k+1 -γ [ℓ]-1 ⌉(1 -z k+1 ) + q i=k+2 ⌈b i -γ [ℓ]-1 ⌉- ⌈b i-1 -γ [ℓ]-1 ⌉ (1 -z i ), q ∈ I 2 , l ∈ I 1 ∪ I 2 ∪ {0}. ( 114
)
Proof. Observe that inequalities (113) are similar to inequalities (75), and that inequalities (114) are similar to inequalities (77), except that set S is restricted to be an interval {k + 1, . . . , q}. The proof is then similar to that of proposition 21. 2

Example 2 (continued) Here follows the list of inequalities (113).

∆ + w 3 + w 4 ≥ z 1 -1 ∆ + w 1 + w 2 + w 3 + w 4 ≥ z 2 ∆ + w 2 + w 3 + w 4 ≥ z 3
The undominated inequalities of type (114) are the following.

∆ + w 4 ≥ 1z 4 q = 4, l = 4 ∆ ≥ 0 q = 4, l = 0 ∆ + w 2 + w 3 + w 4 ≥ 3z 4 -2z 5 q = 5, l = 5 ∆ + w 4 ≥ 2z 4z 5 q = 5, l = 4

Proposition 26 The convex hull of P DLSL ∆,w is described by (99)-( 100), ( 102)-( 105), ( 107)-( 108), ( 113)-( 114).

The proof of this proposition is similar to the one of proposition 23, and it is presented in Van Vyve [2003].

Corollary 27 The inequalities (103)-( 108), ( 113)-( 114) define an integral extended formulation for P DLSL of size O(n) × O(n 2 ) variables and constraints.

Thus, we obtain a more compact integral extended formulation than in the divisible-capacity case. The same domination result as in the previous section applies.

Proposition 28 If ℓ / ∈ {k + 1, . . . , q} ∪ {0}, the inequality (114) is dominated.

Projecting out ∆ and w from ( 99)-( 105),( 106)-( 108), ( 113)-( 114) yields a similar result to Theorem 13, but with two simplifications, as in Corollary 15. The first one is that we always use ψ and never φ, or equivalently that the first level of mixing is always of the first form. This is essentially because the problem is uncapacitated. The second one is that we can restrict S to be an interval instead of a general set. This is a consequence of the addition of the bound constraints (103) and of the absence of capacity.

Note that the separation algorithm outlined in Section 3 always outputs a cut with S = {k + 1, . . . , q}. Hence the separation result is identical.

Proposition 29 Separation over conv(P DLSL ) can be done in O(n log n) time.

Theorem 30 Conv(P DLSL ) is given by

s ≥ T t=1 (γ [it] -γ [i t-1 ] )ψ it q (z), U 1 ⊆ I 1 , q ∈ I 2 , U 2 ⊆ {k + 1, . . . , q} ∪ {0}, (115) s ≥
T t=1

(γ [it]γ [i t-1 ] )ψ it q (z) + (1γ i T )(ψ i 1 q (z) -1),

U 1 ⊆ I 1 , q ∈ I 2 , U 2 ⊆ {k + 1, . . . , q} ∪ {0},

where {i t } T t=1 is an ordering of U = U 1 ∪ U 2 such that [i 0 ] = 0 < [i 1 ] < . . . < [i T ] and

ψ t q = z t -⌊b t ⌋, if t ∈ I 1 , q i=k+1 (⌈b i -γ [t]-1 ⌉ -⌈b i-1 -γ [t]-1 ⌉)(1 -z i ), if t ∈ I 2 .
We conclude this section by a negative result. It is natural to ask if inequalities ( 115)-( 116) suffice to obtain the convex hull of the lot-sizing problem (4)-( 7). The answer is no. Indeed, consider the instance defined by n = 3 and d = (0.8, 2.6, 1.7). Adding all inequalities (115)-( 116) for each k = 0, 1, 2, 3 yields a polyhedron for which the following fractional point is extreme: s = (0, 2.45, 0.425, 0) and y = (3.25, 0.25, 0.75).

8 Conclusions and Future Directions Zhao and de Farias [2007a] characterize the facets and extreme points of P M M IX (and of analogous models with more than two divisible capacities) under conditions that ensure that the number of extreme points is bounded by n + 1, and their characterization implies a polynomial time separation algorithm. Because these conditions are somewhat restrictive, the results implied for the case of two divisible capacities can be seen as a special case of our results in Sections 3, 4, and 5. In addition, Zhao and de Farias also show that the number of extreme points can in general grow to O n m n m + 2 m-1 , where m is the number of divisible capacities. In such a case, it seems that the best that one can hope for is to define an algorithm to generate all extreme points that runs in polynomial time for fixed m (as opposed to a compact closed-form description of these points, such as that provided for our model in Section 5), and/or a polynomial algorithm to optimize over the mixed integer set. Zhao and de Farias define algorithms of both types. Conforti et al. [2008] and [START_REF] Conforti | The mixing set with divisible capacities: a simple approach[END_REF] give both an extended formulation and a polynomial-time optimization algorithm when the number of divisible capacities is three or more. However, a precise combinatorial characterization of the facets, and a combinatorial polynomial-time separation algorithm are still unknown in this case.

It seems that it may be possible to generalize the two-level mixing procedure of Section 2 to be valid for more levels. In this case [START_REF] Conforti | The mixing set with divisible capacities: a simple approach[END_REF] notes that s ≥ 0 can be dropped without loss of generality, which substantially simplifies the notation.

Another interesting direction of research is a generalization of P M M IX to the case in which two distinct capacities that do not divide each other are present. Removing the divisibility assumption results in a considerable complication of the convex hull; however, promising results on such a generalization and related sets can be found in Agra andConstantino [2006, 2007], Zhao and de Farias [2007b].

The results of Sections 3, 4, 6, and 7 suggest that the inequalities and formulations we have presented would be effective in solving practical problems, in particular lot-sizing problems such as those mentioned in Section 1. Certainly these results provide the strongest inequalities known for capacitated problems with lower bounds on production and/or startup costs. How best to use these results computationally, as well as results on other generalizations of the mixing and MIR sets, is another potentially important

2 Corollary 15

 215 Consider an instance of P M M IX in which 0 < b k+1 ≤ ... ≤ b n and C ≥ b n . Let P D = {(s, z) : Dz ≤ d}, where Dz ≤ d the system of constraints 0 ≤ z k+1 ≤ ... ≤ z n . Then conv(P M M IX ∩ P D ) = conv(P M M IX ) ∩ P D ; moreover, conv(P M M IX ∩ P D ) is completely described by the constraints (

Example 2

 2 Consider a lot-sizing model with n = 5, d =

Acknowledgements

This research was funded in part by NSF grant CMMI-0323299 (for A.J. Miller) and by FCT grant ISFL-1-152 (for M.Constantino). The authors wish to thank their colleagues at CORE for significantly facilitating this research.

Proposition 19 Each of the following are extreme points of conv(P M M IX ):

1. The point

2. For all i ′ ∈ I 1 :

(65)

3. For all i ′′ ∈ I 2 :

(68) area of research.


Mohamed El

Hedi Arouri
email: mohamed.arouri@univ-orleans.fr

Julien Fouquau
email: julien.fouquau@univ-orleans.fr

On the shortterm influence of oil price changes on stock markets in GCC countries: linear and nonlinear analyses

Keywords: GCC stock markets, oil prices, linear and nonlinear analyses JEL classifications: G12, F3, Q43. 1. Introduction

This paper examines the short-run relationships between oil prices and GCC stock markets. Since GCC countries are major world energy market players, their stock markets may be susceptible to oil price shocks. To account for the fact that stock markets may respond nonlinearly to oil price shocks, we have examined both linear and nonlinear relationships. Our findings show that there are significant links between the two variables in Qatar, Oman, and UAE. Thus, stock markets in these countries react positively to oil price increases. For Bahrain, Kuwait, and Saudi Arabia we found that oil price changes do not affect stock market returns.

However, some recent papers have shown that the link between oil and economic activity is not entirely linear and that negative oil price shocks (price increases) tend to have larger impact on growth than positive shocks do [START_REF] Hamilton | What is an Oil Shock?[END_REF], [START_REF] Zhang | Oil shock and economic growth in Japan: A nonlinear approach[END_REF], Lardic andMignon (2006, 2008) and [START_REF] Cologni | The Asymmetric Effects of Oil Shocks on Output Growth: A Markov-Switching Analysis for the G-7 Countries[END_REF]]. Thus, we should expect that oil prices equally affect stock markets in a nonlinear fashion, especially in GCC countries. In fact, for these net oil-exporting countries oil price fluctuations should increase corporate output and earnings, but also domestic price levels. Therefore, unlike net oil-importing countries where the expected link between oil prices and stock markets is negative (oil price increases have a negative impact on future cash-flows), the transmission mechanism of oil price shocks to GCC stock market returns are ambiguous and the total impact of oil price shocks on stock returns depends on which of the positive (positive impacts of oil prices increase on GCC firms and economies) and negative (domestic and imported inflation) effects counterweigh the other.

In a second step, we have then checked if there are signs of nonlinearities in the link between oil prices and stock markets in GCC countries. For this aim, we applied a non parametric model to allow the estimation of non-linear relationships. Despite the use of this method, we reach the same results. We find that the relationships between oil prices and stock markets returns are significant (and slightly nonlinear) for Qatar, UAE and Oman. For the three other countries, there is no relationship.

The outline of this paper is as follows. The next section describes the data and briefly presents the GCC stock markets. Section 3 discusses the preliminary results we obtained on the basis of linear specifications. Section 4 presents the non-parametric model specification and reports the results we obtained from the nonlinear methods. The last section concludes.

Data and the role of oil in GCC countries

We use weekly data for the six members of the Gulf Cooperation Council (GCC): Bahrain, Kuwait, Oman, Qatar, Saudi Arabia and United Arab Emirates (UAE). Our sample covers the period from the first week of June 2005 to the third week of October 2008, which represents 177 observations for each country. Stock market indices are obtained from MSCI. For oil, we use the weekly OPEC countries spot price weighted by estimated export volume obtained from the Energy Information Administration (EIA). OPEC prices are often used as reference prices for crude oil including oil produced by GCC countries.1 All prices are denominated in American dollars.

Table 1 displays descriptive statistics of the stock returns in GCC countries as well as the world market returns measured by MSCI world index returns. Compared with the World market, GCC stock markets have higher volatilities, but not necessarily higher returns. Kuwait has the highest returns followed by Oman. Saudi Arabia has the highest risk followed by UAE. On average, oil price changes are higher than stock market returns. Furthermore, many average returns are negative as a result of the subprime crisis. Finally, except for Kuwait, the normality hypothesis is rejected for all the series we study.

Together, GCC countries produce about 20% of all world oil, control 36% of world oil exports and possess 47% of the world oil proven. Oil exports largely determine earnings, government budget revenues and expenditures and aggregate demand. Table 2 shows some key financial indicators for the stock markets in GCC countries. The contributions of oil to GDP range from 22% in Bahrain to 44% in Saudi Arabia. Moreover, for the three largest economies in GCC countries, Saudi Arabia, UAE, and Kuwait, the stock market's liquidity indicator is positively associated with the oil importance indicator in these economies.

Saudi Arabia leads the region in terms of market capitalization. However, by percentage of GDP, Qatar is the leader. Stock market capitalization exceeded GDP for all counties except Oman. Kuwait has the largest number of listed companies, followed by Oman. Overall, GCC stock markets are limited by several structural and regulatory weaknesses: relatively small numbers of listed firms, large institutional holdings, low sectoral diversification, and several other deficiencies. In recent years, however, a broad range of legal, regulatory, and supervisory changes has increased market transparency.

The link between oil and stock returns: a simple linear investigation

We investigate here if the oil price changes ( t Ropec ) explain the stock market returns (R t (i)

) in GCC countries. A version of this relationship may be represented by the following equation 2 :

t t t i i i t Ropec Vmsci a R        0 ) (
(1) where t  is a stochastic error term and t Vmsci represents the world market returns filtered by the oil price returns. More precisely, t Vmsci is the residuals of the OLS regression of the world market returns ( t Rmsci ) on the oil price changes:

t t t V Ropec Rmsci      (2)
The results are reported in Table 3. We have first tested for the assumptions of no serial correlation and homogeneity of the error terms. Serial correlation of order one 3 have been found for Bahrain. To remove it, we added in the equation (1) the Bahraini stock market returns lagged of one period. Second, we have tested for the presence of heteroskedasticity. More precisely, we have applied the White's test. We found three countries with unknown form of the heteroskedasticity: Oman, Qatar and UAE. In these cases, the OLS estimator is unbiased but inefficient. Then, we use the White's estimator to estimate the asymptotic covariance matrix.

In View of these results, there exists a positive and significant relation between oil price changes and stock market returns for three countries: Oman, Qatar, and UAE. For these countries the positive effects of oil price increases offset the negative effects and oil price changes are positively reflected in stock returns. The elasticity of stock prices to oil prices in these countries is less than one, but the stock price effect of oil changes is great: a 10% increase in oil prices leads to an average appreciation of the stock markets by 2.1%, 4.1% and 3.4% respectively fro Oman, Qatar, and UAE.

For the other countries (Bahrain, Kuwait, and Saudi Arabia), the global effects of oil price changes on stock returns is insignificant. The absence of relationships between oil prices and stock markets in too oil dependent economies such as Bahrain, Kuwait and Saudi Arabia countries seems to be counterintuitive. However, as we have previously mentioned, some recent papers have shown that the link between oil and economic activity is not entirely linear and that there is some evidence of nonlinearities between the two variables [START_REF] Hamilton | What is an Oil Shock?[END_REF], [START_REF] Zhang | Oil shock and economic growth in Japan: A nonlinear approach[END_REF] and Lardic andMignon (2006, 2008)]. Therefore, one possible explanation for our findings is that the traditional linear specifications are too restrictive and cannot reproduce 2 We obtain similar results if we consider an alternative equation without the filtered variable t Vmsci . The results oh these estimations are available upon request. 3 We have not found serial correlation of order superior. such nonlinearities. In the rest of the paper, we investigate whether our results are not conditioned to the assumption of a linear relationship.

Further evidence from a nonlinear investigation

Unlike the previous section, we examine here the relationships between oil prices and stock markets without imposing the assumption of linearity. More particularly, we use a non parametric method: a local polynomial kernel regression of order 2 with a Gaussian kernel, which has the advantage to do not need a priori functional models. However, the major drawback is that there is no analytical form of the link between the two variables with this solution.

This method consists to fit the dependent variable Y (here the stock market returns) at each value x (the grid points, here the oil price changes) by choosing the set of parameters for to minimize the weighted sum of squared residuals:

(3

)
where T is the number of observations of stock market returns, h is the bandwidth and K is a kernel function that integrates to 1. The kernel is the function used to weight the observations in each local regression. Observations far of the estimated point x have less impact on the estimation. There are many possible kernel functions. However, this choice does not modify significantly the results with the exception of the uniform kernel. In this study, we use a Gaussian kernel:

with an arbitrary bandwidth4 -and -the range of X. The choice of the bandwidth parameter corresponds to an arbitration variance / bias (For more precision see Cleveland et Devlin (1988)).

Figure 1 displays scatter plots of the oil price changes and the stock market returns. We also report local polynomial kernel regression of order 2 in the left part. By way of comparison, we report the line of the traditional linear regression in the right part.

In view of these results, the relationship between oil prices and stock returns in GCC countries is not clearly nonlinear. It appears especially that there are some edge effects. For Qatar, Oman, and UAE, the link between oil price changes and the stock market returns is positive and the highest for negative values of oil price shocks (-0.15 to -0.5). However, the relationship remains positive but lower for higher values. This link seems therefore nonlinear and switching according to the oil price change values. The results we found for the three other countries are in agreement with those obtained using parametric linear model. With the exception of edge effect, there is no relationship between oil price changes and stock markets returns in Bahrain, Kuwait, and Saudi Arabia.

Conclusion

This paper investigated the short-run relationships between oil prices and GCC stock markets. Since GCC countries are important world energy market players, their stock markets may be susceptible to oil price shocks. To account for the fact that stock markets may respond nonlinearly to oil price shocks, we have examined both linear and nonlinear linkages. Our results show that there are significant links between the two variables in Qatar, Oman, and UAE. Thus, stock markets in these countries react positively to oil price increases. For Bahrain, Kuwait, and Saudi Arabia we found that oil price changes do not affect stock market returns.

Our findings should be of interest to researchers, regulators, and market participants. In particular, GCC countries as OPEC policy-makers should keep an eye on the effects of oil price fluctuations on their own economies and stock markets. For investors, the significant relationship between oil prices and stock markets implies some degree of predictability in some GCC stock markets.

There are several avenues for future research. First, the relationships between oil price changes and stock market returns in GCC countries can be expected to vary from one economic sector to another. A sector analysis of this link would be informative. Second, the same approach applied in this article could be used to examine the effects of other energy products, such as natural gaz. Third, further research could examine the links of causality binding oil and stock markets in GCC countries and other oil-exporting countries.

Table 1 : Descriptive statistics

 1

		OPEC	Bahrain	Kuwait	Oman	Qatar	Saudi	U.A.E.	World
	Mean (*100)	0.226	-0.090	0.240	0.002	0.026	-0.253	-0.346	-0.013
	Std. Dev.	0.036	0.026	0.028	0.030	0.040	0.051	0.043	0.006
	Skewness	-0.803	0.490	-0.186	-0.971	-0.563	-1.113	-2.059	-4.231
	Kurtosis	4.693	6.568	3.237	8.079	6.866	7.052	15.040	36.116
	Jarque-Bera	39.93***	100.39***	1.42	216.87***	118.93***	156.74***	1187.4***	8567.7***
	*, ** and *** denote rejection of the null hypothesis respectively at 10%, 5% and 1%.

Table 2 : Stock markets in GCC countries in 2007

 2

	Market	Number of companies*	Market Capitalization ($ billion)	Market Capitalization (% GDP) *	Oil (% GDP)+
	Bahrain	50	21.22	158	22
	Kuwait	175	193.50	190	35
	Oman	119	22.70	40	41
	Qatar	40	95.50	222	42
	UAE	99	240.80	177	32
	S. Arabia	81	522.70	202	44
	Sources: Arab Monetary Fund and Emerging Markets Database. * Numbers in 2006.

Table 3 : Linear model results

 3

			Bahrain -0,001	Kuwait 0,002	Oman -0,000	Qatar -0,001	Saudi -0,003	U.A.E. -0,004
			( 0,002) 0,033	(0,002) -0,028	(0,002) 0,210***	(0,003) 0,408***	(0,004) 0,141	(0,003) 0,3420***
			(0,052) 0,204***	(0,057) 0,108	(0,070) 0,303**	(0,108) 0,154	(0,104) 0,296**	(0,130) 0,429
			(0,073)	(0,081)	(0,150)	(0,226)	(0,147)	(0,302)
	R	2	0,065	0,001	0,121	0,139	0,021	0,142
	Log-ikelihood	400,612	382,847	379,688	332,779	277,991	320,872
	F-statistic	5,070***	1,010	13,108***	15,218***	2,921**	15,5581***
	AIC	-4,5327	-4,316	-4,280	-3,747	-3,124	-3,612
	*, ** and *** denote rejection of the null hypothesis respectively at 10%, 5% and 1%. Robust standard errors are reported in parentheses.

Scatter plots of the oil price returns and the stock markets returns and local polynomial kernel regression of order and linear regression

		.15								.15
		.10								.10
		.05								.05
		.00								.00
	SAUDI	-.05							SAUDI	-.05
		.12 -.10								.12 -.10
		.08 -.15								.08 -.15
		-.20								-.20
		.04								.04
	BAHRAIN	.00 -.25 -.20	-.15	-.10	-.05 OPEC	.00	.05	.10	BAHRAIN	.00 -.25 -.20	-.15	-.10	-.05 OPEC	.00	.05	.10
		-.04								-.04
		.2								.2
		-.08								-.08
		.1								.1
		-.12								-.12
		-.20	-.15	-.10	-.05	.00	.05	.10		-.20	-.15	-.10	-.05	.00	.05	.10
	UAE	.0			OPEC				UAE	.0			OPEC
		.12 -.1								.12 -.1
		.08 -.2								.08 -.2
	KUWAIT	.00 .04 -.3 -.20	-.15	-.10	-.05 OPEC	.00	.05	.10	KUWAIT	.00 -.3 .04 -.20	-.15	-.10	-.05 OPEC	.00	.05	.10
		-.04								-.04
		-.08								-.08
		-.20	-.15	-.10	-.05	.00	.05	.10		-.20	-.15	-.10	-.05	.00	.05	.10
					OPEC								OPEC
		.10								.10
		.05								.05
		.00								.00
	OMAN	-.05							OMAN	-.05
		-.10								-.10
		-.15								-.15
		-.20								-.20
		-.20	-.15	-.10	-.05	.00	.05	.10		-.20	-.15	-.10	-.05	.00	.05	.10
					OPEC								OPEC
		.15								.15
		.10								.10
		.05								.05
		.00								.00
	QATA	-.05							QATA	-.05
		-.10								-.10
		-.15								-.15
		-.20								-.20
		-.25								-.25
		-.20	-.15	-.10	-.05	.00	.05	.10		-.20	-.15	-.10	-.05	.00	.05	.10
					OPEC								OPEC

Very similar results are obtained with West Texas Intermediate and Brent spot prices. Oil prices are in US dollar per barrel. Note also that GCC currencies are pegged at fixed rates to the U.S. dollar officially since

We use the bandwidth parameter provided by e-views.