Post-Optimality Analysis of the Optimal Solution of a Degenerate Linear Program Using a Pivoting Algorithm - PDF

Please download to get full document.

View again

of 21
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Crosswords

Published:

Views: 0 | Pages: 21

Extension: PDF | Download: 0

Share
Related documents
Description
Post-Optimality Analysis of the Optimal Solution of a Degenerate Linear Program Using a Pivoting Algorithm Jan Stallaert University of Connecticut, Storrs CT Final Version, June
Transcript
Post-Optimality Analysis of the Optimal Solution of a Degenerate Linear Program Using a Pivoting Algorithm Jan Stallaert University of Connecticut, Storrs CT Final Version, June 10, 2005 Abstract This paper gives a theory and method that specifies how the optimal solution of a linear program changes when the right hand side of the original problem is changed and when the original optimal solution exhibits primal degeneracy. The method determines an optimal change vector as the resource availabilities change, and it calculates a range for which this vector is valid. Resource availabilities are allowed to change simultaneously in any arbitrary proportion, and the concept of an efficient resource bundle is introduced. The geometry of the optimal change vector is presented from which the desired results are derived. The connection between the geometrical results and their algebraic calculation in tableau-form is shown. Our method uses a pivoting algorithm and the relationship with post-optimality results from interior-point methods will be established. Keywords: Linear Programming, Post-Optimality Analysis, Shadow Prices, Simplex method, Degeneracy Abbreviated Title: Post-Optimality Analysis for Degenerate LPs Mailing Address: OPIM Department, Unit 1041, Storrs, CT Forthcoming in Computers & Operations Research 1 Introduction Linear progamming textbooks often end their discussion of the simplex method by referring to a post-optimality analysis that can easily be performed by means of the final simplex tableau. However, it is then mentioned that caution has to be taken when either primal or dual solution is degenerate. In that case, usual post-optimality results do no longer hold. For example, when the primal solution is degenerate, it is possible that the change in the optimal solution when the rigth hand side changes, is only valid in a zero range, which is rather useless from a practical perspective. Another unique phenomenon that occurs for degenerate problems is the complementarity effect between resources. For example, if in the degenerate case resources a and b have shadow prices of p(a) 0andp(b) 0 respectively, then it is possible that acquiring a and b in a certain proportion, say in the amounts r a of a and r b of b yields for the value of the bundle: p r (a, b) r a p(a) +r b p(b), so the value of the bundle p r (a, b) is worth more than the weighted sum of the values of resources a and b separately (for non-degenerate problems equality always holds). At first glance, a complimentarity effect seems rather surprising for a problem that consists of all linear functionals. Jansen et al. [17] describe the problems with commercial LP packages and outline three approaches how to deal with the difficulties caused by degeneracy. Research on post-optimality analysis using simplex tableaus goes back more than twenty years [3, 6, 18], but the most recent stream uses interior point methods to obtain postoptimality results in the presence of non-uniqueness and degeneracy. Given an optimal interior point solution, an optimal partition can be identified [4] which can then be used for sensitivity analysis in the presence of degeneracy. Adler and Monteiro [1] find all breakpoints of the parametric objective function when the perturbation vector r is kept constant. To compute every breakpoint, an Oracle LP problem with an auxiliary column needs to be solved. Yildirim and Todd [23] describe the computation of the optimal solution to a perturbed system in one interior point iteration. As in the latter paper, this paper primarily focuses on the optimal change vector, i.e., the direction in which the optimal solution changes as the resource availabilities are varied, but we use an extreme point method to arrive at those conclusions. If the optimal solution and the optimal change vector are both unique, the interior and extreme point methods of course give the same optimal change vector. Many papers on post-optimality analysis (e.g., [2, 3, 6, 17, 11, 13, 14, 18] focus on how the optimal value of the LP changes when the right hand side changes, and construct methods 2 on how to find the breakpoints and the rate of change (shadow price) of a piecewise linear optimal value function. The purpose there is to find the shadow prices u r of some resource (combination) r and the breakpoints τ such that the optimal value takes the expression vr (t) =wy r (t) =wy +tu r t (0,τ], where wy is the value of the original optimal solution. Our focus of attention, however is on how the change in certain resource availabilities affects the optimal solution, for the following reasons. The primary driver of this research is the appearance of market-based decomposition-like algorithms [7, 16] where different iterations require the solution of pertrubed problems where resource availabilities are varied and where the knowledge of the optimal change vector is needed to compute ask and bid prices. In addition, the proof of finite convergence of such algorithms hinges upon the generation of extreme points of the perturbed system at each step, hence our use of extreme point methods rather than interior point methods. Another reason for our interest in the optimal change vector rather than shadow prices of the resource(s), is practical. When linear programming is used to solve planning problems (e.g., production planning, etc.) managers may sometimes be more interested in knowing how the optimal solution changes as a function of a right hand side change, because many times data for the latter has been forecast and is subject to change before the plan is executed. For example, managers might be more interested in knowing how their production plan would change when demand forecasts for the different products change (or when resource availabilities display some variance) rather than the effect of such change on the objective function, in order to anticipate the change in production plan and take the necessary precautions (e.g., not take a machine down for maintenance if it s likely to become a bottleneck when forecasts change). In the rest of the paper, when we mention degeneracy, we mean primal degeneracy. That is, we do not study the effects of dual degeneracy and multiple primal optima. In case we have multiple primal optimal solutions, our method just gives one optimal change vector from one particular original extreme point out of many. In this setting we can also obtain an equivalence beteen the optimal basis approach and optimal partition approach when computing the valid range for a shadow price. Under the assumptions stated above we answer the following questions: 1. Find an optimal change vector for a given change in resource(s). 2. In what range does the optimal change vector remain constant? 3. What are the efficient proportions for a change in resource availability, i.e., in what 3 proportion should one change the availability of several resources such thath no portion of the acquired resources becomes unused in the new optimal solution? 4. If we consider the polyhedron that represents the fixed constraints, i.e. the ones where there is no change in resource availability, in what face of this polyhedron does the optimal change vector lie? Using Convex Analysis [20] Akgül [2] derived shadow prices when the primal optimal solution is degenerate and generalized the results for the case in which resource availabilities are allowed to change simultaneously and in any arbitrary proportion. Since the analysis is done in dual space, it is not immediately clear how to get the optimal change vector that is associated with this shadow price, neither is it shown whether this proportion of resources is efficient. As in [2, 21] we make a distinction between a dual price and a shadow price: theformer is not always unique, the latter is always unique. The shadow price for a resource bundle r is the rate of change of the optimal value when the resource availabilities are increased by a small amount εr (ε 0). Usually, one concentrates on r = e i, i.e., the availability of only one resource changes at a time. Gal [8, 10] uses a degeneracy graph a graph constructed from basic representations of the optimal vertex to perform sensitivity analysis in case r = e i. He also discusses how degeneracy graphs can be used for parametric linear programming under (primal) degeneracy [10]. Because of the close connection between parametric programming and sensitivity analysis, results derived for the former can generally be applied to the latter and vice versa. In fact, our approach can be viewed as using parametric programming of the right hand side, but our derivation is novel since it is based on geometric arguments, rather than degeneracy graphs [10] or convex analysis [2]. Greeenberg s [13] concept of compatible bases to perfrom sensitivity analysis for r = e i is closely related to the present work. This paper extends the results in [13] by deriving necessary and sufficient conditions for a compatible basis and by showing that such conditions imply that a compatible basis can be found by solving an LP problem. This LP problem is a subproblem of the original LP and can be solved starting with an optimal tableau using a dual algorithm. Solving an LP is in general considered to be more efficient than enumerating bases when the problem is of anything else than trivial size. Methods using degeneracy graphs essentially enumerate bases in a lexicographic order [11, p. 4-10], which might become inefficient when the number of possible bases becomes 4 large. The first part of the paper introduces the underlying theory. The notation and approach closely follow the notation in [6] and [12]. As in [6], our method primarily uses the primal respresentation of the linear program (as opposed to [2] where the results are obtained via the dual). The second part of the paper discusses an efficient implementation of this theory using a tableau representation with a dual algorithm. Our goal is to better understand the geometry of post-optimality analysis, to present an efficient computational procedure for answering such questions and to show the connection between the geometric results and algebraic computations. 2 Determining the Optimal Change Vector 2.1 Problem Statement The original linear program of interest is the canonical linear programming problem: min wy (LP) subject to: [ A Ay = I n ] [ r 0 y 0 ] = b with w R 1 n, y R n 1, r 0 R m 1, b R (m+n) 1, A R m n, I n the identity matrix of order n and A R (m+n) n. The matrix A contains the resource constraints (r 0 are the original resource availabilities), and the matrix A (vector b) contains the resource constraints (resource availabilities) as well as the nonnegativity constraints, and will be referred to later as the complete constraint matrix (resp. complete right hand side). We assume that (LP) has been solved by an extreme point algorithm and y is an optimal extreme point solution to (LP). Conceptually, all post-optimality questions with respect to a small change in resource availabilities tr with r R m 1, t R, can be answered by solving the problem: min wy (LP r (t)) subject to: [ A Ay = I n ] y [ r 0 + tr 0 ] 5 for a small t. The optimal value and solution of problem (LP r (t)) is a function of t and is parametrized by r. Writing y r (t) as the optimal solution to problem (LP r(t)), we want to find a vector p r R n 1,whichwecalltheoptimal change vector, for the linear expression of the optimal solution: y r(t) =y + tp r Once the parametric opitmal solution is determined, the shadow price of r, u r, can be easily computed by the vector multiplication u r = wp r, and we also compute an upper bound Δ r 0, for which the optimal change vector remains valid. Hence, the questions we try to answer are to determine p r : the optimal change vector for an arbitrary r; and Δ r : the range for which the expression y r (t) =y + tp r stays valid t (0, Δ r]. In order to exclude trivial cases, we assume that for the resource bundle r, r i =0when constraint i has slack at y, and only focus on the bottleneck resources, i.e., the binding constraints at y. In addition, we would like to know whether resource bundle r is an efficient bundle. Definition: r is an efficient resource bundle iff there does not exist r r, r r with u r u r. (Note that because our LP problem is a minimization problem with constraints, we have u r 0forr 0, so all feasible solutions to the dual of (LP) are non-positive.) In other words, a resource bundle r is efficient if and only if there is no other bundle r that uses less resources and is as valuable as bundle r. Knowing whether a resource bundle is efficient is important from a managerial perspective. As was pointed out earlier, degenerate problems may give rise to a complementarity effect between resources, i.e., the value of their sum is higher than the sum of their values. So, if we decide to acquire or dispose of resources in a bundle rather than one at a time, a manager would be interested in knowing whether these proportions are the minimal ones, i.e., that there does not exist a resource bundle that is worth as much, but uses less resources. Next, we show how the computation of p r amounts to solving an n dimensional LP problem, but with generally far fewer constraints than the original LP problem. For this 6 new LP problem we will use the currently available information from the optimal solution of the original problem. The computation of Δ r becomes easy after p r has been determined. We let the matrix A = R m= n be the submatrix of the complete constraint matrix A of (LP) consisting of all m = constraints with zero slack at y. In case the primal solution is nondegenerate, we have n = m =, so from now on we assume that n+σ = m = n(σ is called the degree of degeneracy [10]). In the [ spirit ] of Best [6] the matrix A = is further partitioned into B the matrices B and D = : A = = D = with B R n n, a matrix of n linearly independent rows for which wb 1 0, and D = R σ n. Similarly, the vector b = 0 R m= 1 contains the portion of the original right hand [ side ] b 0 corresponding to the constraints in A =,and likewise b = 0 is partitioned as b= 0 = f0 with f 0 R n 1 and g 0 = R σ 1. In the same way, b = r g = 0 contains the portion of b r, the parametric right hand side (the change ] in resource availabilities) corresponding to A = and is further partitioned as b = r = [ fr g = r. The matrix D contains all rows of A with positive slack at y and the vector g is the portion of the right hand side b 0 corresponding to D (by assumption b r and r corresponding to D is zero). B and f 0 represent the optimal extreme point y = B 1 f 0, and we denote by P = B 1, which we call the conjugate primal basis 1 [12] for the primal space R n. We also assume by using complementary slackness that the matrix P yields a dual feasible solution, which implies that (see [6] p. 347) wp 0. The m = rows of the matrix A = can be related to the complete constraint matrix A by introducing the one-to-one function π( ) [ :{1, 2,...,m ] = } {1, 2,...,m+ n}. The i th A row in A = then equals row π(i) ina =. The partitioning of the constraint matrix I n and right hand side and their relationship with the original data of the problem is illustrated in Figure 1. If we express the matrix P as an array of column vectors P =[p 1,,p n ], then {p 1,,p n } is a basis for R n and consequently the unknown p r can be expressed with respect to the basis {p 1,,p n } as: p r = Pα r for some column vector αr Rn 1 and we can write yr (t) =y +tp αr. In order to determine 1 The non-singular matrix B and hence P exist, since we assumed that y was an extreme point solution, i.e., it lies on the intersection of n linearly independent constraints. 7 π( ): π Figure 1: The relation between the partitioned matrices and vectors. αr,wecanrewrite(lp r(t)) by substituting y with α, and by taking y as a starting solution, yielding: min (wy + twpα)=wy + t min wp α α α subject to: t APα = t [ AP P ] [ (r α 0 Ay ] )+tr y The above problem has the same complete constraint matrix as (LP), i.e., the first set of constraints are the m resource constraints plus a second set of n translated non-negativity constraints for y. However, for t sufficiently small, the constraints that have slack at y will still have slack at yr (t), so we only need to concentrate on the m= binding constraints at y, i.e., only the contraints in A =, and we will ignore the constraints with positive slack until we compute Δ r. For the constraints binding at y, the portion of the right hand side not involving t is zero, and since t 0, we can always re-scale the problem by dividing the right hand side of those binding constraints by t. This new problem has only m = constraints, does 8 not depend on t, and can be written as: subject to: (A = P ) α = [ B D = min wp α (SP r ) ] Pα [ fr We remind that BP = I n and after substituting α g = r ] = b = r = α + f r, and translating the right hand side by the lower bounds, we get an LP problem with n decision variables and σ constraints: min (wp) α (SP r ) subject to: I n α 0 (D = P ) α g = r +(D= P ) f r This explains why we have stated the problem (LP r (t)) in terms of the direction vectors {p j } rather than in terms of Δy j = ±e j (as in a periodic re-start): this would require solving an (LP) with m = σconstraints from scratch, without taking advantage of the information of the optimal solution of the original LP problem presently available. In addition, the present formulation will allow us to get additional insight in the geometrical properties of the optimal change vector. From our last formulation, it also becomes apparent why sensitivity analysis for non-degenerate problems is trivial: the LP problem (SP r ) has no constraints. The above problem can be shown to be the dual of the problem of Akgül [2], by which the shadow price u r for a resource bundle r is obtained. We are solving this problem in the original primal space rather than in the dual space as Akgül does to allow us to obtain the optimal change vector p r directly. Problem (SP r ) gives the necessary and sufficient conditions for finding the optimal change vector fro the present solution y.solving(sp r ) is expected to be more efficient than basis enumeration as there can be many possible bases at a degenerate vertex [5, 19]. 9 2.2 Post-Optimality Results Sinceweassumedthatwehaveanoptimalsolutiony = Pf to the original problem (LP) with wp 0, we have a dual feasible solution, and hence the solution α = 0 is dual feasible for (SP r ) as well, making problem (SP r ) an ideal candidate to be solved by the dual algorithm to restore primal feasibility. Restoring primal feasibility to (SP r ) corresponds to finding an unblocked optimal change vector. Because a dual feasible solution exists, (SP r ) cannot be unbounded, (SP r ) can either have (i) a feasible solution; or (ii) an infeasible solution. Case (ii) means that for every t 0 problem (LP r (t)) becomes infeasible, so there does not exist a non-null change vector and the shadow price u r =. Because of the construction of (SP r ) and its apparent equivalence with (LP r (t)), the proof of the next proposition is omitted. Proposition 1 Let α be the optimal solution to (SP r )withα = α f. Then: p r = Pα The shadow price for r is then computed as u r = wp r. For calculating the maximum range of the optimal change vector, we need to calculate the maximum movement in the primal space in direction p r such that a constraint that was not binding at y, now becomes binding. These constraints are part of the matrix D (see Figure 1), and its right hand side is expressed as g . Proposition 2 If (SP r ) has a feasible solution, the range for t where y r(t) =y + tp r is given by: Δ r = We set Δ r = when D p r 0. min i=1,...,m σ {(g i d i y ) d i p r d i p r 0} Proof The quantity (g i d i y ) is
Recommended
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks