|
Article Excerpt
This paper addresses the problem of finding cutting planes for multistage stochastic integer programs. We give a general method for generating cutting planes for multistage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem and for stochastic lot-sizing problems. We give computational results, which show that these new inequalities are very effective in a branch-and-cut algorithm.
Subject classifications: programming, integer: cutting plane/facet; programming: stochastic; inventory/production, lot sizing: stochastic.
Area of review: Optimization.
History: Received September 2006; revisions received March 2007, October 2007; accepted November 2007. Published online in Articles in Advance December 9, 2008.
1. Introduction
This paper deals with polyhedral aspects of multistage stochastic integer programs. Our basic idea is to extend known results concerning cutting planes for a deterministic model of the problem to a stochastic model. In other words, suppose that we know valid inequalities that make it possible to solve efficiently the deterministic model by linear programming or branch and cut. In this paper, we show how to use this knowledge to get valid inequalities for a stochastic scenario-tree-based model of the problem so that it too can be solved by a branch-and-cut algorithm. Multiperiod production-planning problems are a typical example where there is considerable knowledge of the convex hull of feasible solutions for various deterministic problems. In Guan et al. (2006), we showed how to apply this idea for uncapacitated lot-sizing problems by generalizing the well-known (l, S) inequalities (Barany et al. 1984) to a stochastic setting. Here we generalize the basic ideas of Guan et al. (2006) so that the results can be applied to general multistage stochastic integer programs involving a scenario tree model of the uncertain parameters. The key idea of our approach is to combine deterministic valid inequalities corresponding to different scenarios to obtain valid inequalities for the whole scenario tree. The general framework is studied in detail in the context of stochastic dynamic knapsack problems and stochastic lot-sizing problems. For these special cases, we provide facet and convex hull defining conditions, and discuss separation procedures. We also present computational results that show that the approach is computationally feasible for stochastic lot-sizing problems.
The remainder of this paper is organized as follows. In the next section, we present notation and terminology used throughout the paper, and also discuss the underlying combination principle in our approach. A general framework for obtaining valid inequalities for scenario-tree-based stochastic integer programs is given in [section]3. Applications to stochastic dynamic knapsack problems and stochastic lot-sizing problems are presented in [section][section]4 and 5, respectively. Section 6 presents computational results, and [section]7 gives conclusions and directions for future research.
2. Notation and Preliminaries
2.1. Multistage Stochastic Integer Programs
Consider the deterministic T-period mixed-integer program
min [T.summation over (t = 1)] ([[alpha].sub.t][x.sub.t] + [[beta].sub.t][y.sub.t])
s.t. [t summation over ([tau] = 1)] ([G.sub.t[tau]][x.sub.[tau]] + [A.sub.t[tau]][y.sub.[tau]]) [greater than or equal to] [b.sub.t], t = 1, ..., T, [x.sub.t] [member of] [R.sub.+.sup.p], [y.sub.t] [member of] [Z.sub.+.sup.n], t = 1, ..., T, (1)
where [A.sub.t[tau]] and [G.sub.t[tau]] are matrices; and [[alpha].sub.t], [[beta].sub.t], and [b.sub.i], are vectors of appropriate dimensions. We assume, without loss of generality, that the decision vectors in each of the time periods t = 1, ..., T are of identical dimension.
Now consider the extension of (1) to a stochastic setting. We assume that the problem parameters ([alpha], [beta], G, A, b) evolve as a discrete-time stochastic process with a finite probability space. This information structure can be interpreted as a scenario tree J = (V, E) with T levels (or stages) where a node i [member of] V in stage t of the tree gives the state of the system that can be distinguished by information available up to time stage t. The probability associated with the state represented by node i is [p.sub.i]. The set of nodes on the path from the root node to a node i is denoted by P(i). The decisions ([x.sub.i], [y.sub.i]) corresponding to a node i are assumed to be made after observing the realizations ([[alpha].sub.i], [[beta].sub.i], [{[G.sub.ij]}.sub.j[member of]P (i)), [{[A.sub.ij]}.sub.j[member of]P(i), [b.sub.i]), but are nonanticipative with respect to future realizations. The goal is to minimize expected total costs. The multistage stochastic integer programming extension of (1) is then
min [summation over (i [member of] V)][p.sub.i]([[alpha].sub.i][x.sub.i] + [[beta].sub.i][y.sub.i])
s.t. [summation over (j [member of] J(i))]([G.sub.ij][x.sub.j] + [A.sub.ij][y.sub.j]) [greater than or equal to] [b.sub.i], i[member of]V, [x.sub.i] [member of] [R.sub.+.sup.p], [y.sub.i] [member of] [Z.sub.+.sup.n], i [member of] V. (2)
Any multistage stochastic integer program defined over a scenario tree can be modelled as formulation (2) (cf. Romisch and Schultz 2001, Sen 2005). Specific examples of such problems include stochastic lot-sizing problems (Guan et al. 2006, Lulli and Sen 2004) (see also [section] 5), stochastic capacity-planning models (Ahmed et al. 2003, Singh et al. 2008), and the stochastic unit commitment problem (Nowak and Romisch 2000, Takriti et al. 1996).
We denote the set of feasible solutions of the multistage stochastic integer program (2) by [X.sub.J], and refer to this set as the tree set. In this paper, we develop valid inequalities for the tree set [X.sub.J] by combining given valid inequalities for path sets of the form
[X.sub.i] = {[([x.sub.k], [y.sub.k]).sub.k[member of]J(i)]:[summation over (j[member of]J(k)]([G.sub.kj][x.sub.j] + [A.sub.kj][y.sub.j])[greater than or equal to][b.sub.k], [x.sub.k][member of][R.sub.+.sup.p], [y.sub.k][member of][Z.sub.+.sup.n][for all]k[member of]J(i)}
for i [member of] V. Note that the path set [X.sub.i] includes only those constraints of [X.sub.J] that correspond to the nodes on the path P(i) from the root node to node i, and hence is a relaxation of the tree set [X.sub.J]. Moreover, the path set [X.sub.i] is essentially the feasible region of the deterministic multiperiod problem (1) with t(i) periods, where t(i) is the stage number of node i in the scenario tree J. Consequently, known valid inequalities for the deterministic model (1) are valid for the path set [X.sub.i] and also for the tree set [X.sub.J]. The (deterministic) valid inequalities corresponding to different path sets, called path inequalities, can be combined to obtain a new valid inequality, called a tree inequality, for the tree set. This idea has been previously explored in Guan et al. (2006), where valid inequalities for deterministic uncapacitated lot sizing were combined to derive valid inequalities for stochastic lot sizing, and in Guan et al. (2007), where valid inequalities for general deterministic two-stage integer programs were combined to obtain inequalities for two-stage stochastic integer programs. The underlying combination scheme in these papers, and in this work, is a simple operation known as pairing (Guan et al. 2007), which is described next.
2.2. Pairing
Throughout this paper, we adopt the following convention. Given two vectors [a.sub.1] and [a.sub.2] of the same dimension, the operations min ([a.sub.1], [a.sub.2]) and max ([a.sub.1], [a.sub.2]) are understood to be carried out componentwise. Given a vector a and a scalar b, we define a + b = a + b[??] and min{a, b} = min{a, b[??]}, where 1 is a vector of ones of the same dimension as a. Also, because all variables are nonnegative, we say that an inequality [a.sub.1] x [greater than or equal to] [b.sub.1] dominates another inequality [a.sub.2] x [greater than or equal to] [b.sub.2] if [a.sub.1] [less than or equal to] [a.sub.2] and [b.sub.1] [greater than or equal to] [b.sub.2].
THEOREM 1 GUAN ET AL. (2007). Suppose that the inequalities [g.sub.1]x + [a.sub.1] y [greater than or equal to] [b.sub.1] and [g.sub.2] x + [a.sub.2] y [greater than or equal to] [b.sub.2] with [b.sub.1] [less than or equal to] [b.sub.2] are valid for the set X [subset] [R.sub.+.sup.p] x [Z.sub.+.sup.n]. Then, the pairing inequality
[phi]x + [empty set] y [greater than or equal to] [b.sub.2], (3)
where [phi] = max{[g.sub.1], [g.sub.2]} and [empty set] = min {[a.sub.1] + ([b.sub.2] - [b.sub.1]), max {[a.sub.1], [a.sub.2]}}, is valid for X.
The pairing inequality is a split cut that can be derived as in Cook et al. (1990) or via the mixed-integer rounding procedure (Nemhauser and Wolsey 1988, 1990) and, in the special case where all coefficients are nonnegative, via mixing (Gunluk and Pochet 2001). The following example illustrates that the pairing inequality may not be obtained by one round of the Chvatal-Gomory (C-G) procedure...
|
