Approximation Algorithms for2-Stage
Stochastic Optimization Problems
Chaitanya Swamy1, and David B.Shmoys2,
1Department of Combinatorics&Optimization,University of Waterloo,
Waterloo,ON N2L3G1
cswamy@math.uwaterloo.ca
2School of ORIE and Department of Computer Science,Cornell University
Ithaca,NY14853
记名提单
ll.edu
Abstract.Stochastic optimization is a leading approach to model op-
不定代词timization problems in which there is uncertainty in the input data,
whether from measurement noi or an inability to know the future.In
this survey,we outline some recent progress in the design of polynomial-
time algorithms with performance guarantees on the quality of the solu-
tions found for an important class of stochastic programming problems
卡布奇诺英文
—2-stage problems with recour.In particular,we show that for a num-
ber of concrete problems,algorithmic approaches that have been applied
for their deterministic analogues are also effective in this more challeng-
ing domain.More specifically,this work highlights the role of tools from
linear programming,rounding techniques,primal-dual algorithms,and
the role of randomization more generally.
1Introduction
Uncertainty is a facet of many decision environments and might ari due to vari-ous reasons,such as unpredictable information revealed in the future,or inherent fluctuations caud by noi.Stochastic optimization provides a means to handle uncertainty by modeling it by a probability distribution over possible realizations of the actual data called scenarios.Thefield of stochastic optimization or stochas-tic programming,has its roots in the work of Dantzig[4]and Beale[1]in the1950s, and has increasingly found application in a wide variety of areas,including trans-portation models,logistics,financial instruments,and network design.
An important and widely ud model in stochastic programming is the2-stage recour model:first,given only distributional information about(some of)the data,one commits on initial(first-stage)actions.Then,once the actual data is realized according to the distribution,further recour actions can be taken (in the cond stage)to augment the earlier solution and satisfy the revealed requirements.The aim is to choo the initial actions so as to minimize the Rearch supported partially by NSERC grant327620-06.
Rearch supported partially by NSF grant CCR-0430682.
S.Arun-Kumar and N.Garg(Eds.):FSTTCS2006,LNCS4337,pp.5–19,2006.
c Springer-Verlag Berlin Heidelberg2006
6 C.Swamy and D.B.Shmoys
童趣 翻译
expected total cost incurred.Typically the recour actions entail making deci-sions in rapid reaction to the obrved scenario,and are therefore more costly than decisions made ahead of time.Thus there is a trade-offbetween commit-ting initially having only impreci information while incurring a lower cost,and deferring decisions to the cond–stage when we know the input precily but the costs are higher.Many applications come under this tting,and much of the textbook of Birge and Louveaux [2]is devoted to models and algorithms for this class of problems.
A commonly cited example involves a tting where a company has to decide where to t up facilities to rve client demands.Typically the demand pattern is not known precily at the outt,but one might be able to obtain,through simulation models or surveys,statistical information about the demands.This motivates the following 2-step decision process:in the first-stage,given only distributional information about the demands (and deterministic data for the facility opening costs),one must decide which facilities to open initially.Once the actual input (the client demands)is realized according to this distribution,we can extend the solution by opening more facilities,incurring
a recour cost,and we have to assign the realized demands to open facilities.This is the 2-stage stochastic uncapacitated facility location problem.The recour costs are usually higher than the original ones (becau opening a facility later would involve deploying resources with a small lead time),could be different for the different facilities,and could even depend on the realized scenario.
The formal model.The 2-stage recour model can be formalized as follows:we are given a probability distribution over possible realizations of the data called scenarios and we construct a solution in two stages.First,we may take some deci-sions to construct an anticipatory part of the solution,x ,incurring a cost of c (x ).Then a scenario A is realized according to the distribution,and in the cond-stage we may augment the initial decisions by taking recour actions y A ,(if necessary)
incurring a certain cost f A (x,y A ).The goal is to choo the initial decisions so as
to minimize the expected total cost,c (x )+E A f A (x,y A ) ,where the expectation is taken over all scenarios according to the given probability distribution.
An important issue that we have left unspecified above is the question of how the scenario-distribution is reprented.One simple approach is to assume that we are given as part of the input description a list that explicitly enumerates each scenario (occurring with non-zero probability)and its
probability of occurrence.However,this caus a significant blow-up in the input size,since the distribution can easily have support size that is exponential in the other input parameters,that is,the non-stochastic portion of the input;for example,in stochastic facility location,consider the ca where the demand of each client is t independently.Thus,to ensure that a “polynomial-time”algorithm in this model has running time polynomial in the other input parameters,one must restrict onelf to distributions with a polynomial-size support,which is a vere restriction;we shall call this the polynomial-scenario model to reflect this fact.The distribution mentioned above is captured by the independent-activation model introduced by Immorlica et al.[11],where the scenario-distribution is a product of independent
Approximation Algorithms for2-Stage Stochastic Optimization Problems7 distributions(described in the input).Typically,there is an underlying t of el-ements(clients)and a scenario is generated by independent choices(tting the demands)made for each element.Independent distributions allow one to suc-cinctly specify a class of distributions with exponentially many scenarios,and have been ud in the Computer Science community to model uncertainty in various ttings[13,18,5].However,many of the underlying stochastic applica-tions often involve correlated ,in stochastic facility location the client demands are expected to be correlated due to econo
mic and/or geographic fac-tors),which the independent-activation model clearly does not capture.A more general way of specifying the distribution is the black-box model,where the dis-tribution is specified only via a procedure(a“black box”)that one can u to independently sample scenarios from the distribution.In this model,each pro-cedure call is treated as an elementary operation,and the running time of an algorithm is measured in terms of the number of procedure calls.The black-box model incorporates the desirable aspects of both the previous models:it allows one to specify distributions with exponentially many scenarios and corre-lation in a compact way that makes it reasonable to talk about polynomial-time algorithms.
Stochastic optimization problems are often computationally quite difficult, and often more difficult than their deterministic counterparts,both from the viewpoint of complexity theory,as well as from a practical perspective.In many ttings the computational difficulty stems from the fact that the distribution might assign a non-zero probability to an exponential number of scenarios,lead-ing to considerable increa in the problem complexity,a phenomenon often called the“cur of dimensionality.”Thus,many stochastic problems that are easy to solve in the polynomial-scenario model due to the expansive input en-coding become NP-hard in the black-box model.For example,stochastic linear programming ,stochastic problems that can be formulated as
lin-ear programs)are polynomial-time solvable in the polynomial-scenario model but become#P-hard in the black-box model[8].In other ttings,even with polynomially many scenarios,the stochastic problem gives ri to a more com-plex problem than its deterministic counterpart and is NP-hard,whereas the deterministic problem is solvable in polynomial time.
In this survey,we focus on the design of approximation algorithms for stochas-tic optimization problems.Throughout,we u aρ-approximation algorithm to denote a polynomial-time algorithm that always returns a feasible solution with objective function value within a factorρof the optimum;ρis called the ap-proximation ratio or performance guarantee of the algorithm.
There is an abundance of literature in the stochastic programming commu-nity that deals with computational aspects of solving2-stage stochastic pro-grams,especially2-stage linear programs(LPs),which we shall not cover here; the reader is referred to[2,22]for more information.Many of the methods are only suitable in the polynomial-scenario model and cannot handle the burden of an exponential number of scenarios.One appealing approach in the black-box model is to sample a certain number of times from the scenario-distribution,
8 C.Swamy and D.B.Shmoys
estimate the probability of a scenario by its frequency in the sampled t,and solve the2-stage problem determined by this approximate distribution.This is known as the sample average approximation(SAA)method.The SAA method is a widely ud heuristic in practice and has been empirically shown to work well in various ttings(,[15,28]).The main question here is:how many samples does one need to ensure that an optimal solution to the sample-average problem is a near-optimal solution to the original problem(with high probabil-ity)?While there are results that prove asymptotic convergence to the optimal solution(to the original problem)in the limit as the number of samples goes to infinity,fewer results are known about the rate of convergence,or equivalently, about worst-ca bounds on the sample size required to obtain a near-optimal solution.Ideally one would like to show that a polynomial number of samples always suffice.Such a result would show that the SAA method gives a reduction from the black-box problem to a polynomial-scenario problem,thereby reducing the complexity of the stochastic problem,while losing a factor in the approxi-mation guarantee.In particular,this would immediately give an approximation algorithm for stochastic linear programming problems in the black-box model. The work that most cloly considers the aspect of worst-ca bounds is a pa-per of Kleywegt,Shapiro and Homem-De-Mello[14](e also[23]).Kleywegt et al.prove a sample-size bound for2-stage programs that is independent of the number of scenarios,but depends on the variance of a certain quantity(calcu-lated using the scenario-
distribution)which need not be polynomially bounded, even for very structured programs.We shall return to this question of proving polynomial sample-size bounds for the SAA method in Section4.
There are other sampling-bad approaches where instead of sampling just once initially,the algorithm ud to solve the stochastic problem contains a sampling subroutine that is called whenever one needs to estimate some quantity, such as the function value or the gradient.Dyer,Kannan and Stougie[7]u such an approach for a stochastic maximization LP,where samples are ud to estimate the objective function value at a given point.This yields a sample size that is only polynomial in the maximum value attained by any scenario(due to the high variance in the values of the different scenarios).Nesterov and Vial[20] employ stochastic subgradients,estimated via sampling,in a subgradient-descent algorithm,and require a sample size that is polynomial in the maximum variation in the objective function value in the feasible region.
The design and analysis of algorithms with provable worst-ca guarantees for 2-stage stochastic integer programs is a relatively recent rearch direction.The first such result appears to be due to Dye,Stougie and Tomasgard[6]who give a constant-factor approximation algorithm for a resource provisioning problem in the polynomial-scenario model.Subquently,a ries of papers[21,11,10,25]ap-peared on this topic in the Computer Science literature,and showed that one
高二英语练习册can obtain guarantees for a variety of stochastic combinatorial optimization problems by adapting the techniques developed for the deterministic analogue.Gupta, P´a l,Ravi and Sinha[10],who were thefirst to consider the black-box model (under a certain cost assumption),make such a connection explicit.Shmoys and
Approximation Algorithms for2-Stage Stochastic Optimization Problems9 Swamy[25],who give algorithms in the black-box model with arbitrary costs, show an even more explicit correspondence.They showed that one could derive approximation algorithms for most of the problems considered in[21,11,10]by adopting a natural LP rounding approach that,in effect,converted an LP-bad approximation guarantee for the deterministic analogue into a guarantee for the stochastic generalization with a small loss in the approximation factor.Thus, if we can solve the stochastic LP(even approximately),which is a#P-hard problem,then we will have esntially reduced the stochastic problem to its deterministic analogue.
This survey is organized as follows:in Section2we describe an approxima-tion scheme for solving a large class of2-stage stochastic LPs.In Section3we describe some techniques for devising approximation algorithms for stochastic integer programming problems.We focus mainly on the black-box model,but also sometimes consider the polynomial-scenario model;in Section4we conside
r the SAA method and establish a concrete connection between the two models. 2Stochastic Linear Programs
We now describe the fully polynomial approximation scheme(FPAS)of Shmoys and Swamy[25]that can be applied to a rich class of2-stage stochastic LPs.The algorithm returns a solution of value within(1+κ)times the optimum(with
high probability),for anyκ>0,in time polynomial in the input size,1
consultants
κ,and
a parameterλ,which is the maximum ratio between the cond-andfirst-stage costs.As we show in Section3,this provides us with a powerful and versatile tool for designing approximation algorithms for stochastic integer optimization problems in much the same way that linear programming has proved to be immenly uful in the design of approximation algorithms for deterministic optimization problems.
We shall consider a stochastic generalization of the t cover problem as an illustrative problem to explain the main ideas.In the2-stage stochastic t cover (SSC)problem,we are given a ground t U
of n elements,a collection of subts of U,S1,...,S m,and a distribution over subts of U that specifies the target t of elements to cover.In stage I,we can pick some ts paying a cost of
w I S for each t S.Then,a scenario materializes which specifies a target t
A⊆U of elements to be covered and the costs{w A
S }of picking ts in that
scenario,and one can pick additional ts to ensure that A is contained in the union of the ts lected in the two stages.The aim is to minimize the expected cost of the ts picked.Denoting the probability of scenario A by p A(which we do not know explicitly,and could be0),we can formulate the problem as an integer program and relax the integrality constraints to obtain the following linear program:minimize
S w I S x S+
A⊆U,S
p A w A S r A,S:norm
S:e∈S
(x S+r A,S)≥1∀A,e∈A;x S,r A,S≥0∀A,S.
(SSC-P1)
10 C.Swamy and D.B.Shmoys
Variable x S indicates whether t S is chon in stage I,and r A,S indicates if t S is chon in scenario A.The constraint says that in every scenario A,every element in that scenario has to be covered by a t chon either in stage I or in stage II.Notice that(SSC-P1)is an LP with an exponential number of variables and constraints,and it ems difficult to efficiently compute an(near-)optimal solution to(SSC-P1),since even writing out a solution can take exponential space(and time).However,if wefix thefirst-stage ,the x S variables, then the scenarios become parable,so we can reformulate(SSC-P1)as follows: minimize
www boysky com
h(x):=
S w I S x S+
A⊆U
p A f A(x)subject to0≤x S≤1∀S,(SSC-P2)
where(1)
f A(x):=min
关于独立的英语作文S w A S r A,S:alarm
S:e∈S
r A,S≥1−
S:e∈S
x S∀e∈A;r A,S≥0∀S.
Here the cond-stage decisions only appear in the minimization problem f A(x), which denotes the recour problem that one needs to solve for scenario A.It is easy to show that(SSC-P2)is equivalent to(SSC-P1),and that its objective function is convex.Although we now have a compact convex program,the com-plexity of the problem resurfaces as follows:in general,it is#P-hard to even evaluat
e the objective function h(.)at a given point[8].Nevertheless,we can leverage convexity and adapt the ellipsoid method to solve(SSC-P2).
In the ellipsoid method,we start by containing the feasible region within a ball and then generate a quence of ellipsoids,each of successively smaller volume.In each iteration,one examines the center of the current ellipsoid and obtains a specific half-space defined by a hyperplane passing through the cur-rent ellipsoid center.If the current ellipsoid center is infeasible,then one us a violated inequality as the hyperplane,otherwi,one us an objective function cut to eliminate(some or all)feasible points who objective function value is no better than the current center,and thus make progress.A new ellipsoid is then generated byfinding the minimum-volume ellipsoid containing the half-ellipsoid obtained by the interction of the current one with this half-space.Continuing in this way,using the fact that the volume of the successive ellipsoids decreas by a significant factor,one can show that after a polynomial number of itera-tions,the feasible point generated with the best objective function value is a
near-optimal solution.
Let P=P0denote the polytope
x∈R m:0≤x S≤1for all S
,and x i
be the current iterate.Defineλ=max(1,max A,S w A
S /w I
S
),which we assume is
known.It is trivial to determine if x i is feasible,so we only need to describe how to obtain an objective function cut.One option is to simply add the constraint h(x)≤h(x i),which is not a“linear”cut,but would prerve the convexity of the feasible region.But then in subquent iterations,without the ability to evaluate(or even estimate)h(.)at a given point,we would not even be able to decide if the current point is feasible(or even almost-feasible),which pos a formidable difficulty.Alternatively,one could u cuts generated by a
