ebook img

Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems PDF

0.69 MB·
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems

Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems F. Oliveira, J. Christiansen, B. Dandurand, A. Eberhard Mathematical Sciences School of Science - RMIT University 7 1 0 2 Abstract n a In this paper, we propose a novel decomposition approach for mixed-integer stochastic J programming (SMIP) problems that is inspired by the combination of penalty-based 1 3 Lagrangian and block Gauss-Seidel methods (PBGS). In this sense, PBGS is developed ] such that the inherent decomposable structure that SMIPs present can be exploited in a C O computationallyefficientmanner. Theperformanceoftheproposedmethodiscompared . h with the Progressive Hedging method (PH), which also can be viewed as a Lagrangian- t a based method for obtaining solutions for SMIP. Numerical experiments performed using m instances from the literature illustrate the efficiency of the proposed method in terms of [ computational performance and solution quality. 1 v Keywords: Stochastic programming, Decomposition methods, Lagrangian duality, 4 7 Penalty-based method, Gauss-Seidel method 0 0 0 . 2 1. Introduction 0 7 1 Inspired by recent advances and the increased availability of parallel computation : v resources, there has been a recent surge of methods which are capable of exploiting i X the structure of large-scale mathematical programming problems to achieve increased r a efficiency. One relevant class of problems that can benefit from this paradigm is stochastic mixed-integer programming (SMIP) problems. The modelling framework for this class ∗CorrespondingAuthor Preprint submitted to International Transactions of Operational Research February 2, 2017 of problems is versatile as it simultaneously allows for representation of integer-valued decisions and uncertainty in the input data. However, they are frequently challenging in terms of computational tractability due to their inherent NP-hard nature and their large-scale that arise from their scenario-based representations. Parallel computation is particularly appropriate for solving SMIPs, since the special structure of these problems (i.e. their partial separation by decision stage and by outcome scenario) makes them easier to decompose into smaller subproblems which may then be solved simultaneously. The opportunities arising from approaching SMIP problems by means of decompo- sition has prompted the development of several different theoretical and algorithmic approaches. For example, the Integer L-Shaped method [22] employs Benders’ decom- position to achieve stage-wise decomposition of SMIP problems. Other algorithms em- ploy Lagrangian duality to achieve scenario-wise decomposition, such as the Dual De- composition algorithm [10] which uses Lagrangian dual bounds in a branch-and-bound framework, or Progressive Hedging (PH) [29, 23, 33, 32] which applies an Alternating- Direction-type method to the augmented Lagrangian dual problem. Recent studies and applications of these methods include [2, 19, 24, 15] and references therein. All of the above methods are based on the concept of duality, and therefore they must consider the duality gap that may exist between the optimal solution values of the original (primal) problem and the dual problem. This duality gap is frequently nonzero in the context of non-convex problems, such as those with integer decision variables. If the duality gap for a particular problem is large, any algorithm based on that dual is unlikely to be effective [11]. Several possible approaches to modifying Lagrangian duality to deal with the du- ality gap which arises in non-convex problems have been considered in the literature. These approaches include l -like penalty functions [11], indicator augmenting functions 1 [21], nonlinear Lagrangian functions [35], and semi-Lagrangian duality [3]. With the exception of nonlinear Lagrangian functions, these approaches have not yet been widely exploited in terms of experimental investigation and practical applications despite nu- merous theoretical developments available in literature. In this paper, we propose an alternative approach to deal with SMIP problems that builds upon recent theoretical results from [8] and [13] showing that duality gaps can be 2 diminished with the use of finite-valued penalties for specific class of penalty functions. We show that one can obtain reasonable penalty functions using positive bases and that parallelisationcanbeobtainedbytheapplicationofablockGauss-Seidelapproach. The combination of these two frameworks allows us to develop an efficient heuristics that is capableofprovidingsolutionsforlarge-scaleSMIPproblems. Intermsofobjectivevalue quality and computational time, the developed approach is shown to be competitive withexistingapproachessuchasPH,which,despiteitsheuristicnatureinthecontextof SMIPs,hasbeenrelieduponasanefficientsolutionmethod(see,forexample[30,27,32]). Furthermore,thetheoreticalbasisforPHdoesnotapplyforproblemscontaininginteger variables. OntheotherhandthereexistssomesupportingtheoryforthePBGSapproach whichwepresentinthispaper. Thispartialtheoryhasthepotentialtoinformdirections for the further improvement of heuristic methods of this kind. This paper is structured as follows. In Section 2 we cover the technical background which will be used in the development of the proposed method. Section 3 describes the development of the penalty-based block Gauss-Seidel method, while in Section 4 we dis- cuss computational aspects of the algorithm. Section 5 provides results of the numerical experiments performed. Finally, in Section 6 we provide conclusions and directions for further development of this research. 2. Technical Background In the following developments, we consider two-stage stochastic mixed-integer pro- gramming problems of the form: (cid:88) ζSIP := min c(cid:62)x+ p (q(cid:62)y ) (1) s s s x,y s∈S s.t.: x∈X (2) y ∈Y (x), ∀s∈S, (3) s s where x ∈ Rnx,y ∈ Rny×|S| are decision variables, c ∈ Rnx and q ∈ Rny×|S| are input parameters, and ps ∈ R|S| represents the scenario probabilities. Sets X ⊂ Rnx and Ys(x) ⊂ Rny×|S| define the feasible decision set and consist of linear constraints and integrality restrictions on x and y. 3 Toobtainaformulationthatisamenabletodecomposition,i.e.,thatcanbeexploited in terms of its block-angular structure, ζSIP may be equivalently rewritten as: (cid:88) ζSIP := min p (c(cid:62)x +q(cid:62)y ) (4) s s s s x,y,z s∈S s.t.: x −z =0, ∀s∈S (5) s x ∈X, ∀s∈S (6) s y ∈Y (x ), ∀s∈S. (7) s s s The set of constraints represented by (5) are referred to in the relevant literature as the non-anticipativity constraints (NAC), as they enforce consensus over the decision made before the observation of a given scenario s ∈ S. It is straightforward to see that these constraintspreventtheproblemfrombeingsolvedbymeansofadecompositionapproach that can exploit the otherwise block-angular structure of the problem. Hence, a natural waytoapproachthisclassofproblemsconsistsofrelyingonframeworksthatarecapable of considering relaxations for ζSIP which does not include constraint (5). 2.1. Lagrangian Relaxation AnaturalapproachtosolvethisproblemistorelaxtheNACbymeansofLagrangian relaxation. Toachievethis,letλ=(λ ) betheLagrangianmultipliersassociatedwith s s∈S the constraints (5). Then, our Lagrangian relaxation can be formulated as the following problem: (cid:88) ζLR(ω):= min p L (x ,y ,z,ω) s s s s x,y,z s∈S s.t.: x ∈X, ∀s∈S s y ∈Y (x ), ∀s∈S, s s s (cid:16) (cid:17) where ω :=(ωs)s∈S = λpss s∈S and L (x ,y ,z,ω):=c(cid:62)x +q(cid:62)y +ω(cid:62)(x −z). (8) s s s s s s s s In order to guarantee that ζLR(ω) has a bounded optimal solution, one must enforce that the dual feasibility condition ω ∈ Ω := {ω | (cid:80) p(cid:62)ω = 0} holds. Under this s∈S s s assumption, (8) may be rewritten as L (x ,y ,z,ω)=(c+ω )(cid:62)x +q(cid:62)y , (9) s s s s s s s 4 which forces the z variable to vanish (note that the term −ω(cid:62)z was in fact the poten- s tial cause of the unboundedness of the dual relaxation ζLR(ω)) and its removal yields complete separability for each s∈S. It is well known that ζLR(ω) ≤ ζSIP for any ω ∈ Ω. The Lagrangian dual problem consistsoffindingtheωwhichcausesζLR(ω)tomostcloselyapproximateorboundζSIP from below, which in practice means solving the problem ζLD := max ζLR(ω). (10) ω∈Ω In general only the weak duality condition ζLR(ω)≤ζSIP holds. When equality ζLD = ζSIP holds, we have strong duality. Due to the presence of integer restricted variables, theprimalproblem(4)-(7)isnotconvex,andstrongduality(thatisζLD =ζSIP)cannot be guaranteed. Instead, we typically have a duality gap i.e. ζLD <ζSIP. 2.2. Augmented Lagrangian Approach In the particular domain of mixed-integer problems such as SMIP problems, there has been renewed interest in the use of augmented Lagrangian approaches [9, 14, 16]. The augmented Lagrangian relaxation of ζSIP which relaxes the NAC (5) is: (cid:88) ζLR+(ω):= min p Ls(x ,y ,z,ω)+ψs(x −z) (11) ρ s s s ρ s x,y,z s∈S s.t.: x ∈X, ∀s∈S (12) s y ∈Y (x ), ∀s∈S, (13) s s s where ω = (ωs)s∈S ∈ Ω and ψρs : Rnx (cid:55)→ R is an appropriate penalty function specific to scenario s that depends on the penalty parameter ρ. As in the ordinary Lagrangian relaxation, ω ∈Ωimpliesthat(cid:80) p(cid:62)ω =0soastoensurethatthedualproblemhas s∈S s s a finite optimal value. The augmented Lagrangian dual problem is: ζLD+ :=max ζLR+(ω). ρ ρ ω∈Ω A common choice for the penalty function, in this context, is ψs(u ) := ρ||u ||2 ρ s 2 s 2 for each s ∈ S, which provides smoothness to the original scenario-wise augmented Lagrangian dual function [28, 5, 6]. 5 Recent results have shown that the augmented Lagrangian dual is capable of asymp- totically achieving zero duality gap when the weight ρ associated with the penalty func- tion is allowed to go to infinity [8, Prop. 3], [13, Prop. 2 ]. However, despite the theoretical relevance of this observation, it is not practically meaningful to deal with large-valued penalty parameters, in large part due to the associated numerical issues that arise. Furthermore,[8,Cor. 1],[13,Thm. 4]demonstratesthatitispossibletocircumvent this drawback if the augmentation of the Lagrangian dual is made using a norm as the penalty function. In this case, the theory suggests that it is possible to attain strong duality for a finite value of ρ. This result is one of the major motivations for the developments to be presented next. 2.3. Semi-Lagrangian Duality Semi-Lagrangian duality [3] is a variant of Lagrangian duality in which ”difficult” equality constraints (e.g. Ax = b) are reformulated as pairs of inequality constraints (Ax ≤ b and Ax ≥ b). Lagrangian relaxation is then applied to one of the two sets of inequality constraints. Surrogate semi-Lagrangian duality [25, 20] is a variant which replacesonesetofinequalitieswithitsweightedsum(λ(cid:62)Ax≤λ(cid:62)b,whereλ≥0isanon- negative vector of the weights applied to each inequality) and then applies Lagrangian relaxation to the resulting single inequality. Special classes of problems can exhibit zero duality gap when utilising the semi-Lagrangian dual problem. The semi-Lagrangian approach is effective when the semi-Lagrangian dual problem ismoretractablethantheoriginalproblem, eventhoughsomeinequalitiesremaininthe dual problem as explicit constraints. For problems to which semi-Lagrangian relaxation has been previously applied, such as the p-median problem [3] and the uncapacitated facility location problem [4], the semi-Lagrangian dual problem may be simplified by choosing appropriate dual variable values. The method presented in this paper is similar to semi-Lagrangian duality in that it can be interpreted as a penalty-method analogue of applying Lagrangian duality to a reformulation of the original problem in which equalities are rewritten as inequalities. To attain this objective, let us first reformulate the problem (1)-(3) into the following 6 equivalent form: (cid:88) ζSIP : min p (c(cid:62)x +q(cid:62)y ) s s s s x,y,z s∈S s.t.: x −z ≤0, ∀s∈S (14) s −(x −z)≤0, ∀s∈S (15) s x ∈X, ∀s∈S s y ∈Y (x ), ∀s∈S. s s s Unfortunately,inthecontextoftheSMIPproblemsstudiedinthispaper,theinequalities left as explicit constraints by semi-Lagrangian duality would not allow us to achieve our goal of scenario-wise decomposition. Themethodpresentedhereinsteadrelaxesinequalities(14)and(15),sothatpenalty- basedapproachescantreatthedeviationsfromtheseparateinequalitiesdifferently. Fur- thermore, the resulting dual problem is separable by scenario within the block Gauss- Seidel framework. As will be observed later, choosing penalty functions based on some positive bases can result in penalty terms analogous to the objective terms obtained through surrogate semi-Lagrangian duality. 2.4. Desirable Properties of Penalty Functions Our primary objective is to compute ζLD+ in a decomposed manner, which will ρ require: i) the definition of a suitable penalty functions ψs for each s ∈ S; and ii) ρ the application of a block Gauss-Seidel (GS)-based approach based on a decomposable structure. One important result, originally proven for a general mixed-integer programming (MIP)problems,whichcanbeusedinthiscaseisTheorem5of[13],whichisreproduced below (adapted to the context of SMIP problems). Theorem 1. [13, Thm. 5 ] Consider a feasible MIP problem given in (1)-(3) whose problem data is formed from rational entries and with its optimal value bounded. If ψ : (cid:81)s∈SRnx (cid:55)→ R is a summed augmenting function ψ(u) := (cid:80)s∈Sψρs(us) for prob- lem (11)–(13) such that 1. ψ(0)=0 7 2. ψ(u)≥δ >0,∀u(cid:54)∈V 3. ψ(u)≥γ||u|| ,∀u∈V ∞ for some open neighbourhood V of 0, and positive scalars δ,γ > 0, then there exists a finite ρ such that ζLD+ = ζLR+(ω ) = ζSIP, for ω (an optimal multiplier of the ρ ρ LP LP linear programming relaxation of the NACs (5)). Proof. Apply the general theorem [13, Thm. 5 ] to our problem (1)-(3). Remark 2. In [8] other conditions that do not require the assumption of rationality of the data defining the problem are given that also ensure a limiting zero duality gap. Remark 3. One may see with little difficulty that the proof of [13] does not rely on the setting of ω =ω . Indeed one can show that for any ω there still exists a finite (possibly LP larger) penalty parameter such that Theorem 1 holds true. In [8] and later in [13] it has been observed that a zero duality gap is achievable for dualproblemsbasedonanaugmentedLagrangianinMIPproblems. Inbothpapers,very general classes of augmenting functions were studied and consequently very little can be inferred as to what would be a practical penalty that one could use on a given problem. It is observed in [13] that the usual quadratic (squared norm) penalty is probably not a practical choice for MIP. One would hope that an augmenting function would lead to a reformulationoftheMIPthatisnotsignificantlyworsetosolvethantheoriginalproblem, which would mean that augmenting functions should lead to a MIP reformulation. Motivated by the aforementioned facts, we propose a class of augmenting functions based on the use of positive basis [12]. One special case of this class of penalty functions is given as follows. Given discrepancy vector u := (us)s∈S ∈ (cid:81)s∈SRnx, we define for each scenario s the penalty function ψs(u ):=ρ(cid:62)[u ]−+ρ(cid:62)[−u ]−, ρ s s s s s where ρ = (ρ ,ρ ) ∈ R2nx|S| and [v]− := −min{0,v} (performed component wise), s s s∈S >0 where in this case v ∈Rnx. Then we define (cid:32) (cid:33) (cid:88) (cid:88) (cid:88) ψ (u):= ψs(u )= ρ(cid:62)[u ]−+ ρ(cid:62)[−u ]− . (16) ρ ρ s s s s s s∈S s∈S s∈S 8 In the following developments we will demonstrate that (16) satisfies the conditions of Theorem1andindeedliesinaspecialclassofaugmentingfunctionsthatformapractical set from which one can tailor make an augmenting function for a given problem. 2.5. Positive Basis Asubsetofreasonableaugmentingfunctionsmaybedefinedbyusingapositive basis {n ,...,n }toscalarisethedeviationsu∈Rm. (Notethatforourpurposes,m=n |S|.) 1 l x Suchdeviationscanbeassociated,forexample,withthesatisfactionoflinearinequalities, where we might have u=b−Ax given a constraint Ax≤b. Definition 4. We say a set of vectors {n ,..., n } where m+1≤l≤2m is a positive 1 l basis for Rm if and only if every u ∈ Rm can be expressed as a positive combination of these vectors, i.e., there exists α ≥0 for i=1,...,l for which u=(cid:80)l α n . i i=1 i i The following property of positive bases will be useful in the developments which follow. Theorem 5. ([12]Theorem3.1){n ,...,n }positivelyspansRm ifandonlyifforevery 1 l non-zero u there exists an index i such that u·n >0. i Let e , i = 1,...,m represent the elementary unit vectors of Rm with entry i set to i one and all other entries set to zero. Examples of positive bases on Rm include: • The vertices of a m-simplex (generalised tetrahedron), centred at the origin. • The set of vectors {+e }m ∪{(cid:80)m −e } i i=1 i=1 i • The set of vectors {±e }m i i=1 2.6. Norm-Like Augmenting Functions As noted in both [8] and [13], norms are viable augmenting functions with appealing theoretical support for overcoming duality gaps. However, norms have the disadvantage thattheyuniformlypenaliseconstraintviolations,whichresultsinalossofflexibilityand precision in the fine-tuning of the penalisation. This limitation motivates the following developmentofasymmetricalbutnorm-likeaugmentingfunctions. Thepolyhedralnorms 9 (cid:107) · (cid:107) and (cid:107) · (cid:107) may be represented using the positive basis {±e }m in the following ∞ 1 i i=1 ways: ψ (u):=(cid:107)u(cid:107) = max {±e(cid:62)u}, and (17) ∞ ∞ i i=1,...,m m m (cid:88) (cid:88) ψ (u):=(cid:107)u(cid:107) = max{+e(cid:62)u,0}+ max{−e(cid:62)u,0} (18) 1 1 i i i=1 i=1 m or equivalently (cid:107)u(cid:107) = (cid:88)max(cid:8)ν(cid:62)u:ν ∈{+e ,−e }(cid:9). (19) 1 i i i i i=1 The representation in (19) relies on each vector in the basis having a negative multiple whichisalsointhebasis. Therepresentationsin(17)and(18)donothavethislimitation, and may be generalised to any positive basis N :={n ,...,n } as follows: 1 l ψN(u) := max {n(cid:62)u} and (20) ∞ i i=1,...,l l (cid:88) ψN(u) := max{n(cid:62)u,0}. (21) 1 i i=1 ThefunctionsψN andψN arenotnecessarilynorms,butdosharesomeusefulproperties ∞ 1 with norms. Specifically, these functions are positive homogeneous (which implies that theyvanishatzero), strictlypositiveforallu∈Rm\{0}, finitevalued, sub-additiveand coercive. The proposed augmenting function ψ (u) given in (16) may be represented in the ρ form of (21), using the positive basis N = {ρ e | s ∈ S,i ∈ {1,...,n }}∪ ρ s,i i+(s−1)nx x {−ρ e |s∈S,i∈{1,...,n }}, as follows: s,i i+(s−1)nx x ψNρ(u) = (cid:88) (cid:88) ρ max{0,u }+(cid:88) (cid:88) ρ max{0,−u } 1 s,i s,i s,i s,i s∈Si=1,...,nx s∈Si=1,...,nx (cid:32) (cid:33) (cid:88) (cid:88) = ρ(cid:62)[u ]−+ ρ(cid:62)[−u ]− (22) s s s s s∈S s∈S (cid:88) = ψs(u)=ψ (u) ρ ρ s∈S Lemma 6. If two functions ψ and ψ are positive homogeneous, strictly positive for A B all u(cid:54)=0, and are finite valued then there exists a finite γ >0 such that ψ (u)≥γψ (u) for all u∈Rm (23) A B 10

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.