Optimization Letters manuscript No.
(will be inserted by the editor)

Quantitative stability of fully random
mixed-integer two-stage stochastic programs
W. Römisch, S. Vigerske
Institute of Mathematics, Humboldt-University Berlin, D-10099 Berlin, Germany
The date of receipt and acceptance will be inserted by the editor

Abstract Mixed-integer two-stage stochastic programs with fixed recourse
matrix, random recourse costs, technology matrix, and right-hand sides are
considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.
Key words Stochastic programming – two-stage – mixed-integer – stability – weak convergence – probability metric – discrepancy
1 Introduction
Mixed-integer two-stage stochastic programs model a variety of practical decision problems under stochastic uncertainty, e.g., in chemical engineering,
power production, and trading planning [8,13,14]. The probability distribution of the stochastic programming model reflects the available knowledge
on the randomness at the modeling stage. When solving such stochastic programming models, the probability distribution is approximately replaced inmost cases by a discrete probability measure with finite support. Hence, perturbing or approximating the probability distribution of such models is an
important issue for modeling, theory, and numerical methods in stochastic
integer programming. While much is known on the structure and algorithms
of/for mixed-integer two-stage stochastic programs (cf. the surveys [11,12,
21,22]), the available (quantitative) stability or statistical estimation results
do not cover situations with stochastic costs (or prices) (cf. [7,18,19]).
Mixed-integer two-stage stochastic programs are of the formnZominf0 (x, ξ)dP (ξ) : x ∈ X ,
(1)
Ξ

2

W. Römisch, S. Vigerske

where the (first-stage) feasible set X ⊆ Rm is closed, Ξ is a closed subset of
Rs , the function f0 from Rm × Ξ to the extended reals R is a random lower
semicontinuous function, and P belongs to the set of all Borel probability
measures P(Ξ) on Ξ. Recall that f0 is a random lower semicontinuousfunction if its epigraphical mapping ξ 7→ epi f0 (·, ξ) := {(x, r) ∈ Rm × R :f0 (x, ξ) ≤ r} is closed-valued and measurable. In mixed-integer two-stage
stochastic programs, f0 is of the form
f0 (x, ξ) = hc, xi + Φ(q(ξ), h(ξ) − T (ξ)x)((x, ξ) ∈ Rm × Ξ),(2)

where Φ(u, t) denotes the optimal value of the (second-stage) mixed-integer
program (with cost u and right-hand side t), and q(ξ), T (ξ), and h(ξ) are
the stochastic cost, technology matrix, and right-hand side, respectively.
With v(P ) and S(P ) denoting the optimal value and solution set of(1), respectively, the quantitative stability results for stochastic programs
developed in [18] (see [18, Theorems 5 and 9]) imply, in particular, theestimatesZ|v(P ) − v(Q)| ≤ L sup
f0 (x, ξ)(P − Q)(dξ)
(3)
x∈X
Ξ
Z


∅ 6= S(Q) ⊆ S(P ) + ΨP L sup
f0 (x, ξ)(P − Q)(dξ) ,
(4)
x∈X

Ξ

where L > 0 is some constant, X is assumed to be compact, ΨP is theconditioning function, and P and Q belong to a suitable subset of P(Ξ).
The function ΨP depends on the growth behavior of the objective function
near the solution set and is specified in (11) of Section 3.
The aim of this paper is to extend the quantitative continuity properties of v(·) and S(·) in [16,20] to cover situations with stochastic costs. To
this end, we need quantitative continuity and growth properties of optimalvalue functions and solution sets of parametric mixed-integer linear programs. Such properties are known for parametric right-hand sides [4,5,20]
and parametric costs separately [1,2,6]. Since to our knowledge simultaneous
perturbation results with respect to right-hand sides and costs are less familiar, we discuss such properties of optimal value functions in Proposition
1. These results are then used in Section 3 to obtain the desired quantitative stability result (Theorem 1) for fully random mixed-integer two-stage
stochastic programs with fixed recourse. The relevant probability metric (9)on subsets of P(Ξ) and its relations to Fortet-Mourier metrics and polyhedral discrepancies are also discussed (Remark 1). The latter metrics may
be used for designing moderately sized discrete approximations to P by
optimal scenario reduction of discrete probability measures [9,10].
2 Infima of mixed-integer linear programs
Consider the parametric mixed-integer linear programmin{hcx , xi + hcy , yi : Ax x + Ay y ≤ b, x ∈ Zn , y ∈ Rm−n }(5)Quantitative stability of mixed-integer two-stage stochastic programs

3

with c = (cx , cy ) ∈ Rm and b ∈ Rr playing the role of the parameters andA = (Ax , Ay ) ∈ Qr×m . Let M (b), v(b, c), and S(b, c) denote the feasible set,
optimal value, and solution set of (5), respectively, i.e.,
M (b) := {(x, y) ∈ Zn × Rm−n : A(x, y) ≤ b}v(b, c) := inf{hc, (x, y)i : (x, y) ∈ M (b)}S(b, c) := {(x, y) ∈ M (b) : hc, (x, y)i = v(b, c)}.
Let K denote the polyhedral cone {(x, y) ∈ Rm : Ax x + Ay y ≤ 0} and K∗ its
polar cone. Observe that v(b, c) is finite for b ∈ B := dom M and c ∈ −K∗ .
Further, denote by Prx M (b) the projection of M (b) onto the x-space, andB ∗ (b0 ) := {b ∈ B : Prx M (b) = Prx M (b0 )}(b0 ∈ B)be the set of right-hand sides on which the projection of M (b) onto the xspace is constant. It is well known (see [1, Chapter 5.6]) that the sets B ∗ (b0 )are continuity regions of the function b 7→ v(b, c). These regions are further
characterized by the following result (Lemma 5.6.1 and 5.6.2 in [1]).
Lemma 1 B is a connected set equal to the union of a countable family of
convex polyhedral cones each of which is obtained by a translation of ther-dimensional cone T := {t ∈ Rr : ∃y ∈ Rm−n such that t ≥ Ay y}.
For each b0 ∈ B, there exists t0 ∈ B and a finite set N ⊆ Zn \ Prx M (b0 )such that\B ∗ (b0 ) = (t0 + T ) \(Ax z + T ).
z∈N

If Prx M (b0 ) = Zn , then N = ∅ and B ∗ (b0 ) = t0 + T for some t0 ∈ B.
In the following we extend Lemma 2.3 in [20] and show local Lipschitzcontinuity of the optimal value of (5) with respect to simultaneous perturbations of the right-hand side and the objective function coefficients where
the right-hand side perturbation does not leave the continuity region B ∗ (b).
Otherwise, for arbitrary right-hand sides, a quasi-Lipschitz property of thevalue function of (5) can be shown. For the proof we refer to the appendix.
Proposition 1 (i) Let b ∈ B, b′ ∈ B ∗ (b), and c, c′ ∈ −K∗ . Then the estimate|v(b, c) − v(b′ , c′ )| ≤ L1 max{kck, kc′k}kb − b′k + L2 max{kbk, kb′k, 1} kc − c′kholds, where the constants L1 and L2 depend on A only.
(ii) Let b, b′ ∈ B and c, c′ ∈ −K∗ . Then we have|v(b, c)−v(b′ , c′ )| ≤ max{kck, kc′k}(L̃kb−b′k+2ℓ)+ L̃ max{kbk, kb′k}kc−c′k,where the constants L̃ and ℓ depend on A only.
The following result is [4, Theorem 2.1] and can be found in similar form
also in [2]. Together with Proposition 1 it is needed to prove Lemma 3.
Lemma 2 Let c ∈ −K∗ . The mapping b 7→ S(b, c) is quasi-Lipschitz continuous on B with constants L̄1 and L̄2 not depending on b and c, i.e.,dH (S(b, c), S(b′ , c)) ≤ L̄1 kb − b′ k + L̄2 ,where dH denotes the Hausdorff distance on subsets of Rm .

4

W. Römisch, S. Vigerske

3 Quantitative stability of mixed-integer two-stage stochastic
programs
Let us consider the stochastic programZnomin hc, xi +Φ(q(ξ), h(ξ) − T (ξ)x)P (dξ) : x ∈ X ,(6)

Ξ

where Φ is the infimum function of a mixed-integer linear program given byΦ(u, t) := inf hu1 , yi + hu2 , ȳi : W y + W̄ ȳ ≤ t, y ∈ Zm̂ , ȳ ∈ Rm̄
(7)

for all pairs (u, t) ∈ Rm̂+m̄ × Rr , and c ∈ Rm , X is a closed subset of Rm , Ξa polyhedron in Rs , W and W̄ are (r, m̂)- and (r, m̄)-matrices, respectively,q(ξ) ∈ Rm̂+m̄ , h(ξ) ∈ Rr , and the (r, m)-matrix T (ξ) are affine functions ofξ ∈ Rs , and P ∈ P(Ξ).
We need the following conditions to have the model (6) well-defined:(B1) The matrices W and W̄ have only rational elements.
(B2) For each pair (x, ξ) ∈ X × Ξ it holds that h(ξ) − T (ξ)x ∈ T , where
T := t ∈ Rr : ∃(y, ȳ) ∈ Zm̂ × Rm̄ such that W y + W̄ ȳ ≤ t .
(B3) For each ξ ∈ Ξ the recourse cost q(ξ) belongs to the dual feasible set
U := u = (u1 , u2 ) ∈ Rm̂+m̄ : ∃z ∈ Rr− such that W ⊤ z = u1 , W̄ ⊤ z = u2 .
R(B4) P ∈ P2 (Ξ), i.e., P ∈ P(Ξ) and Ξ kξk2 P (dξ) < +∞.
The conditions (B2) and (B3) mean relatively complete recourse anddual feasibility, respectively. We note that (B2) and (B3) imply Φ(u, t) to
be finite for all (u, t) ∈ U × T . The following additional properties of thevalue function Φ on U × T are important in the context of this paper.

Lemma 3 Assume (B1)–(B3). Then
there exists a countable partition of T
S
into Borel subsets Bi , i.e., T = i∈N Bi such that
S 0r(i) Bi = (bi + T ) \ N
j=1 (bi,j + T ), where bi , bi,j ∈ R , i ∈ N, j = 1, . . . , N0 ,r
N0 ∈ N does not depend on i, and T := {t ∈ R : ∃y ≥ 0 such that t ≥W y}. Moreover there exists an N1 ∈ N such that for all t ∈ T the ballB(t, 1) in Rr is intersected by at most N1 different subsets Bi .
(ii) the restriction Φ

U ×Bi′, where Bi′ := Bi ∩ {h(ξ) − T (ξ)x|(x, ξ) ∈ X × Ξ},

has the property that there exists a constant L > 0 independent of i, s.t.
|Φ(u, t)−Φ(ũ, t̃)| ≤ L(max{1, ktk, kt̃k}ku− ũk+max{1, kuk, kũk}kt− t̃k).
Furthermore, the function Φ is lower semicontinuous and piecewise polyhedral on U × T and there exist constants D, d > 0 such that it holds for all
pairs (u, t), (ũ, t̃) ∈ U × T :|Φ(u, t)−Φ(ũ, t̃)| ≤ D(max{1, ktk, kt̃k}(ku−ũk+d)+max{1, kuk, kũk}kt−t̃k).

Quantitative stability of mixed-integer two-stage stochastic programs

5

The first part of (i) is Lemma 1. The second part is an extension of [20,Lemma 2.5] to the function Φ(u, t) since the relevant constants in its proof
do not depend on the objective function as recalled in Lemma 2. Part (ii)and the quasi-Lipschitz property of Φ is Proposition 1.
The representation of Φ is given on countably many (possibly unbounded)
Borel sets. This requires to incorporate the tail behavior of P and leads tothe following representation of the function f0 .
Proposition 2 Assume (B1)–(B4) and X be bounded. For each R ≥ 1 andR
x ∈ X there exist disjoint Borel subsets Ξj,xof Ξ, j = 1, . . . , ν, whose
closures are polyhedra with a uniformly bounded number of faces such thatf0 (x, ξ) =

ν
X

R (ξ)
(hc, xi + Φ(q(ξ), h(ξ) − T (ξ)x))1Ξj,x((x, ξ) ∈ X × Ξ)

j=0

R
is Lipschitz continuous with respect to ξ on each Ξj,x
, j = 1, . . . , ν, withRR
some uniform Lipschitz constant. Here, Ξ0,x := Ξ \ ∪νj=1 Ξj,x
is containedsrin {ξ ∈ R : kξk∞ > R}, ν is bounded by a multiple of R and 1A denotes
the characteristic function of a set A.

Proof Since q(·), h(·) and T (·) are affine linear functions and X is bounded,
there exists a constant C > 0 such that the estimatemax{kq(ξ)k∞ , kh(ξ) − T (ξ)xk∞ } ≤ C max{1, kξk∞ }(8)holds for each pair in X × Ξ. Let R ≥ 1 and TR := T ∩ CRB∞ , where B∞ is
the unit ball w.r.t. the maximum norm k·k∞ . As in [18, Proposition 34] there
exist a number ν ∈ N and disjoint Borel subsets {Bj }νj=1 of CRB∞ suchthat their closures are polyhedra and their union contains TR . Furthermore,when arguing as in the proof of [20, Proposition 3.1], ν is bounded aboveby κRr , where the constant κ > 0 is independent of R. Now, let x ∈ X andconsider the following disjoint Borel subsets of Ξ:RΞj,x:= {ξ ∈ Ξ : h(ξ) − T (ξ)x ∈ Bj , kξk∞ ≤ R} (j = 1, . . . , ν),
ν
[
R
R
Ξj,x
⊆ {ξ ∈ Ξ : kξk∞ > R}.
:= Ξ \
Ξ0,x
j=1

R
Let x ∈ X and ξ, ξ ′ ∈ Ξj,x
for some j ∈ {1, . . . , ν}. By Lemma 3 we obtain|f0 (x, ξ) − f0 (x, ξ ′ )| = |Φ(q(ξ), h(ξ) − T (ξ)x) − Φ(q(ξ ′ ), h(ξ ′ ) − T (ξ ′ )x)|
≤ L(max{1, kq(ξ)k∞ , kq(ξ ′ )k∞ }(kh(ξ) − h(ξ ′ )k∞+k(T (ξ) − T (ξ ′ ))xk∞ ) + max{1, kh(ξ) − T (ξ)xk∞ ,kh(ξ ′ ) − T (ξ ′ )xk∞ }kq(ξ) − q(ξ ′ )k∞ )≤ LCR(kh(ξ) − h(ξ ′ )k∞ + k(T (ξ) − T (ξ ′ ))xk∞+kq(ξ) − q(ξ ′ )k∞ )≤ L1 Rkξ − ξ ′ k∞ ,6

W. Römisch, S. Vigerske

R
where we used (8) for ξ, ξ ′ ∈ Ξj,x
, affine linearity of q(·), h(·), and T (·), andboundedness of X. We note that the constant L1 is independ of R. ⊓⊔In order to state quantitative stability results for model (6) and inspiredby the estimates (3) and (4), we need a distance of probability measuresthat captures the behavior of f0 (x, ·) (x ∈ X) in its continuity regions
and the shape of these regions, respectively. This leads us to the following
probability metric on P2 (Ξ) for some k ∈ N:
ζ2,phk (P, Q) := sup

n Z

B

o
f (ξ)(P − Q)(dξ) : f ∈ F2 (Ξ), B ∈ Bphk (Ξ) . (9)Here, Bphk (Ξ) denotes the set of all polyhedra being subsets of Ξ and having
at most k faces. The set F2 (Ξ) contains all functions f : Ξ → R such that˜ ≤ max{1, kξk, kξk}kξ˜|f (ξ)| ≤ max{1, kξk2 } and |f (ξ) − f (ξ)|− ξ̃kholds for all ξ, ξ˜ ∈ Ξ. We note that, unfortunately, the growth condition on
f is missing in the description of the set of functions in [16,18].
Before stating the main result, we define the function φP on R+ characterizing the tail behavior of P by φP (0) = 0 and
φP (t) := inf

R≥1

Z
n
Rr+1 t +{ξ∈Ξ:kξk∞ >R}okξk2∞ P (dξ)(t > 0),(10)

and the conditioning function ΨP by
ΨP (η) := η + ψP−1 (2η) (η ∈ R+ ),(11)

where the growth function ψP on R+ isψP (τ ) := minnZf0 (x, ξ)P (dξ) − v(P ) : d(x, S(P )) ≥ τ, x ∈ X

Ξ

o

(12)

with inverse ψP−1 (t) := sup{τ ∈ R+ : ψP (τ ) ≤ t}. The functions φP and ψP
are nondecreasing, ΨP is increasing and all functions vanish at 0. Furthermore, one has ψP (τ ) > 0 if τ > 0 and ΨP (η) ց 0 if η ց 0.
Theorem 1 Let the conditions (B1)–(B5) be satisfied and X be compact.
Then there exist constants L > 0 and k ∈ N such that|v(P ) − v(Q)| ≤ LφP (ζ2,phk (P, Q))∅ 6= S(Q) ⊆ S(P ) + ΨP (LφP (ζ2,phk (P, Q)))B,
for each Q ∈ P2 (Ξ). If
φP (t) ≤ Ct

p−2
p+r−1

R

Ξ

(13)

kξkp P (dξ) < +∞ for some p > 2, the estimate

holds for every t ≥ 0 and some constant C > 0.

Quantitative stability of mixed-integer two-stage stochastic programs

7

Proof Since the function Φ is lower semicontinuous on U × T (Lemma 3), f0
is lower semicontinuous on X × Ξ and, hence, a random lower semicontinuous function [17, Example 14.31]. Using Lemma 3 we obtain the estimate|f0 (x, ξ)| ≤ kckkxk + D[max{1, kh(ξ)k + kT (ξ)kkxk}(kq(ξ)k + d)
+ max{1, kq(ξ)k}(kh(ξ)k + kT (ξ)kkxk)]≤ C1 max{1, kξk2 }for each pair (x, Rξ) ∈ X × Ξ and some constant C1 . Hence, the objectivefunction hc, xi + Ξ Φ(q(ξ), h(ξ) − T (ξ)x)Q(dξ) is finite (if Q ∈ P2 (Ξ)) andlower semicontinuous (due to Fatou’s lemma). Since X is compact, the solution set S(Q) is nonempty.
¿From Proposition 2 we know that, for each R ≥ 1 and x ∈ X, thereRR
exist Borel subsets Ξj,x
, j = 1, . . . , ν, of Ξ such that the function fj,x(·) :=Rf0 (x, ·)1Ξj,x
R
is Lipschitz continuous on Ξj,x with constant L1 R. We extend
R
each function fj,x(·) to the whole of Ξ by preserving the Lipschitz constant.
R
Then we have L11R fj,x(·) ∈ F2 (Ξ). Furthermore, Proposition 2 implies thatR
the closures of Ξj,x are contained in Bphk (Ξ) for some k ∈ N, that thernumber ν is bounded above by, where the constant κ > 0 is independent
SκR
ν
R
R
on R, and that Ξ0,x:= Ξ \ j=1 Ξj,x
is a subset of {ξ ∈ Ξ : kξk∞ > R}.
For each Q ∈ P2 (Ξ) and x ∈ X we obtainZf0 (x, ξ)(P − Q)(dξ) =

Ξ

ν Z
X

R
Ξj,x

j=0

≤

Z
ν
X
j=1

≤ νL1 RRΞj,xf0 (x, ξ)(P − Q)(dξ)Rfj,x(ξ)(P − Q)(dξ) + IxR (P, Q)

supf ∈F2 (Ξ)
j=1,...,ν

Z

ΞRf (ξ)χΞj,x
R (ξ)(P − Q)(dξ) + I (P, Q),xwhere the last summand on the right-hand side is given byZ
IxR (P, Q) :=f0 (x, ξ)(P − Q)(dξ) .
RΞ0,xUsing ν ≤ κRr and arguing as in [18, Theorem 35] we continueZ
f0 (x, ξ)(P − Q)(dξ) ≤ κL1 Rr+1 ζ2,phk (P, Q) + IxR (P, Q).
ΞFor the term IxR (P, Q) we use the estimate |f0 (x, ξ)| ≤ C1 kξk2 for any pair(x, ξ) ∈ X × {ξ ∈ Ξ : kξk∞ > R} and the norming constant C2 such thatkξk ≤ C2 kξk∞ holds for all ξ ∈ Rs . We getZkξk2∞ (P + Q)(dξ).
IxR (P, Q) ≤ C1 C22{ξ∈Ξ:kξk∞ >R}8

W. Römisch, S. Vigerske

Since the set {ξ ∈ Ξ : kξk∞ > R} can be covered by 2s intersections of Ξwith open halfspaces (whose closures belong to Bphk (Ξ)), we can estimateZZ2skξk2∞ P (dξ).
kξk∞ Q(dξ) ≤ 2 ζ2,phk (P, Q) +{ξ∈Ξ:kξk∞ >R}{ξ∈Ξ:kξk∞ >R}

Hence, combining the last three estimates we getZsupf0 (x, ξ)(P − Q)(dξ) ≤ (κL1 Rr+1 + C1 C22 2s )ζ2,phk (P, Q)x∈X
ΞZ+2C1 C22
kξk2∞ P (dξ){ξ∈Ξ:kξk>R}

for any R ≥ 1. Taking the infimum with respect to R ≥ 1 we obtainZsupf0 (x, ξ)(P − Q)(dξ) ≤ ĈφP (ζ2,phk (P, Q))x∈X

Ξwith some constant ĈR > 0. Now, the result is a consequence of the estip(ξ)R < +∞ for some p > 2, it holds that
Rmates (3) and (4).2 If Ξ kξk dP2−pkξkp∞ P (dξ) by Markov’s inequality.
kξk∞ dP (ξ) ≤ RΞ{ξ∈Ξ:kξk∞ >R}
1

The desired estimate follows by inserting R = t− p+r−1 for small t > 0 into
the function whose infinum w.r.t. R ≥ 1 is φP (t):
Z
p−2
p−2
r+1
⊔
kξkp∞ P (dξ) ≤ Ct p+r−1 . ⊓φP (t) ≤ t− p+r−1 +1 + t p+r−1
Ξ

The boundedness condition on X may be relaxed if localized optimalvalues and solution sets are considered (see [18]). In case that the underlying
distribution P and its perturbations Q have supports in some bounded
subset Ξ of Rs , the stability result improves slightly.
Corollary 1 Let the conditions (B1)–(B4) be satisfied, P ∈ P(Ξ), X andΞ be bounded. Then there exist constants L > 0 and k ∈ N such that|v(P ) − v(Q)| ≤ Lζ2,phk (P, Q)∅ 6= S(Q) ⊆ S(P ) + ΨP (Lζ2,phk (P, Q))B,
holds for each Q ∈ P(Ξ).
Proof Since Ξ is bounded, we have P2 (Ξ) = P(Ξ). Moreover, the function
φP (t) (see (10)) can be estimated by Rr+1 t for some sufficiently large R > 0.
Hence, Theorem 1 implies the assertion. ⊓⊔Remark 1 Since Ξ ∈ Bphk (Ξ) for some k ∈ N, we obtain from (9) by choosing B := Ξ and f ≡ 1, respectively,max{ζ2 (P, Q), αphk (P, Q)} ≤ ζ2,phk (P, Q)(14)

Quantitative stability of mixed-integer two-stage stochastic programs

9

for all P, Q ∈ P2 (Ξ). Here, ζ2 and αphk denote the second order FortetMourier metric [15, Section 5.1] and the polyhedral discrepancyZZ
ζ2 (P, Q) := supf (ξ)Q(dξ)
f (ξ)P (dξ) −f ∈F2 (Ξ)αphk (P, Q) :=

sup

Ξ

Ξ

|P (B) − Q(B)|,B∈Bphk (Ξ)

respectively. Hence, convergence with respect to ζ2,phk implies weak convergence (see [3]), convergence of second order absolute moments, and convergence with respect to the polyhedral discrepancy αphk . For bounded Ξ ⊂ Rs
the technique in the proof of [20, Proposition 3.1] can be employed to obtain1ζ2,phk (P, Q) ≤ Cs αphk (P, Q) s+1(P, Q ∈ P(Ξ))(15)

for some constant Cs > 0. In view of (14), (15) the metric ζ2,phk is stronger
than αphk in general, but in case of bounded Ξ both distances metrize thesame topology on P(Ξ).
For more specific models (6), improvements of the above results may beobtained by exploiting specific recourse structures, i.e., by using additional
information on the shape of the sets Bi in Lemma 3 and on the behaviorof the (value) function Φ on these sets. This may lead to stability resultswith respect to probability metrics that are (much) weaker than ζ2,phk . For
example, if q and T are fixed and h(·) is of the form h(ξ) := ξ (i.e., r = s),
the closures of the Bi belong to a class of polyhedra which is completely
characterized in [20, Section 3]. If, in addition, the model has pure integer
recourse, the stability result is valid with respect to the Kolmogorov metricdK (P, Q) := sup |P ((−∞, z]) − Q((−∞, z])|z∈Rson P(Ξ) instead of ζ2,phk if Ξ is bounded (see also [20, Proposition 3.4]).
A Proof of Proposition 1
Let b ∈ B, b′ ∈ B ∗ (b), and c, c′ ∈ −K∗ be given. To show local Lipschitz
continuity of v(b, c), we estimate|v(b, c) − v(b′ , c′ )| ≤ |v(b, c) − v(b′ , c)| + |v(b′ , c) − v(b′ , c′ )|.
For the first difference we can proceed as for the proof of Lemma 2.3 in [20].
It is repeated here to keep the paper self-contained. We write (5) asmin{hcx , xi + Ψ (cy , b − Ax x) : x ∈ Prx M (b)}where Ψ (cy , b̃) := min{hcy , yi : Ay y ≤ b̃}. Since Ψ (cy , b̃) is the optimal valuefunction of a linear program and finite for b ∈ B, c′ ∈ −K∗ , there exist

10

W. Römisch, S. Vigerske

finitely many matrices Cj , which depend on Ay only, such that Ψ (cy , b̃) =maxj hb̃, Cj cy i (cf. [23]). Let L1 := maxj kCj k. Then, for cy fixed,|Ψ (cy , b̃) − Ψ (cy , b̃′ )| ≤ L1 kcy k kb̃ − b̃′ k.
Let (x, y) ∈ S(b, c), (x′ , y ′ ) ∈ S(b′ , c). Since Prx M (b) = Prx M (b′ ), we havev(b, c) − v(b′ , c) ≤ hcx , x′ i + Ψ (cy , b − Ax x′ ) − hcx , x′ i − Ψ (cy , b′ − Ax x′ )≤ L1 kck kb − b′ k.
Due to symmetry the same estimate holds for v(b′ , c) − v(b, c).
Before deriving an estimate for |v(b′ , c)−v(b′ , c′ )|, we recall the following
Lemma, which is [5, Theorem 1.2] and [6, Theorem 1].
Lemma 4 Let b ∈ B, c ∈ −K∗ . Let (x̃, ỹ) be a solution ofmin{hcx , xi + hcy , yi : Ax x + Ay y ≤ b, (x, y) ∈ Rm }.

(16)

Then there exists a solution (x, y) ∈ S(b, c) such thatk(x, y) − (x̃, ỹ)k ≤ ℓfor some constant ℓ depending on A only.
Since (16) is a linear program, there exist finitely many matrices Dj ,which depend on A only, and such that each basis solution of (16) is given
by Dj b for some j. We set L̂ := maxj kDj k. Now let (x̃′ , ỹ ′ ) be an optimalbasis solutions of problem (16) with right-hand side b′ and cost vector c′ .
By Lemma 4 there exists (x′ , y ′ ) ∈ S(b′ , c′ ) with k(x′ , y ′ ) − (x̃′ , ỹ ′ )k ≤ ℓ.
Since v(b′ , c) ≤ hcx , x′ i + hcy , y ′ i and k(x̃′ , ỹ ′ )k ≤ L̂kb′ k, we obtainv(b′ , c) − v(b′ , c′ ) ≤ k(x′ , y ′ )k kc − c′ k ≤ (ℓ + L̂kb′ k) kc − c′ k.
Due to symmetry, a similar estimate holds for v(b′ , c′ ) − v(b′ , c). The second
part of Proposition 1 follows from Lemma 4 and stability results for linear
programs.
Acknowledgements This work was supported by the DFG Research Center Matheon in Berlin and the BMBF under the grant 03SF0312E. We thank an anonymous referee whose comments helped to improve an earlier version of this paper.

References
1. B. Bank, J. Guddat, D. Klatte, B. Kummer, and K. Tammer: Non-Linear
Parametric Optimization, Akademie-Verlag, Berlin 1982.
2. B. Bank and R. Mandel: Parametric integer optimization, Akademie Verlag,
Berlin 1988.
3. P. Billingsley: Convergence of Probability Measures, Wiley, New York 1968.

Quantitative stability of mixed-integer two-stage stochastic programs

11

4. C. E. Blair and R. G. Jeroslow: The value function of a mixed integer program
I, Discrete Mathematics 19 (1977), 121–138.
5. C. E. Blair and R. G. Jeroslow: The value function of a mixed integer programII, Discrete Mathematics 25 (1979), 7–19.
6. W. Cook, A.M.H. Gerards, A. Schrijver, and É. Tardos: Sensitivity theorems
in integer linear programming, Mathem. Programming 34 (1986), 251–264.
7. A. Eichhorn and W. Römisch: Stochastic integer programming: limit theorems
and confidence intervals, Math. of Operations Research 32 (2007), 118–135.
8. S. Engell, A. Märkert, G. Sand, and R. Schultz: Aggregated scheduling of amultiproduct batch plant by two-stage stochastic integer programming, Optimization and Engineering 5 (2004), 335–359.
9. H. Heitsch and W. Römisch: A note on scenario reduction for two-stage
stochastic programs, Operations Research Letters (2007) (to appear).
10. R. Henrion, C. Küchler, and W. Römisch: Discrepancy distances and scenario reduction in two-stage stochastic integer programming, Preprint, DFG
Research Center Matheon ”Mathematics for key technologies”, 2007.
11. W. K. Klein Haneveld and M. H. van der Vlerk: Stochastic integer programming: General models and algorithms, Annals of Operations Research
85 (1999), 39–57.
12. F. Louveaux and R. Schultz: Stochastic integer programming, in Stochastic
Programming, Handbooks in Operations Research and Management ScienceVol. 10, Elsevier, Amsterdam, 2003, 213–266.
13. M. P. Nowak, R. Schultz, and M. Westphalen: A stochastic integer programming model for incorporating day-ahead trading of electricity into hydrothermal unit commitment, Optimization and Engineering 6 (2005), 163–176.
14. R. Nürnberg and W. Römisch: A two-stage planning model for power scheduling in a hydro-thermal system under uncertainty, Optimization and Engineering 3 (2002), 355–378.
15. S. T. Rachev: Probability Metrics and the Stability of Stochastic Models, Wiley,
Chichester 1991.
16. S. T. Rachev and W. Römisch: Quantitative stability in stochastic programming: The method of probability metrics, Mathematics of Operations Research
27 (2002), 792–818.
17. R. T. Rockafellar and R. J-B Wets: Variational Analysis, Springer, Berlin
1998.
18. W. Römisch: Stability of stochastic programming problems, in Stochastic
Programming, Handbooks in Operations Research and Management ScienceVol. 10, Elsevier, Amsterdam, 2003, 483–554.
19. R. Schultz: On structure and stability in stochastic programs with random
technology matrix and complete integer recourse, Mathematical Programming
70 (1995), 73–89.
20. R. Schultz: Rates of convergence in stochastic programs with complete integer
recourse, SIAM Journal on Optimization 6 (1996), 1138–1152.
21. R. Schultz: Stochastic programming with integer variables, Mathematical Programming 97 (2003), 285–309.
22. S. Sen: Algorithms for stochastic mixed-integer programming models, Chapter
9 in Discrete Optimization (K. Aardal, G. L. Nemhauser, R. Weissmanteleds.), Handbooks in Operations Research and Management Science Vol. 12,
Elsevier, Amsterdam 2005, 515–558.
23. D. Walkup and R. J-B Wets: Lifting projections of convex polyhedra, Pacific
Journal of Mathematics 28 (1969), 465–475.