Optimality of Dual Methods for Discrete Multiuser Multicarrier Resource Allocation Problems

3810 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 11, NO. 10, OCTOBER 2012 Optimality of Dual Methods for Discrete Multiuser Multicarrier Resource Allocation Problems Simon Go¨rtzen and Anke Schmeink, Member, IEEE Abstract—Dual methods based on Lagrangian relaxation are the state of the art to solve multiuser multicarrier resource allocation problems. This applies to concave utility functions as well as to practical systems employing adaptive modulation, in which users’ data rates can be described by step functions. We show that this discrete resource allocation problem can be formulated as an integer linear program belonging to the class of multiple-choice knapsack problems. As a knapsack problem with additional constraints, this problem is NP-hard, but facilitates approximation algorithms based on Lagrangian relaxation. We show that these dual methods can be described as rounding methods. As an immediate result, we conclude that prior claims of optimality, based on a vanishing duality gap, are insufficient. To answer the question of optimality of dual methods for discrete multicarrier resource allocation problems, we present bounds on the absolute integrality gap for three exemplary downlink resource allocation problems with different objectives when employing rounding methods. The obtained bounds are asymptotically optimal in the sense that the relative performance loss vanishes as the number of subcarriers tends to infinity. The exemplary problems considered in this work are sum rate maximization, sum power minimization and max-min fairness. Index Terms—Resource allocation, adaptive modulation, or- thogonal frequency division multiple access (OFDMA), duality theory, combinatorial optimization. I. INTRODUCTION THE problem of resource allocation in multicarrier com-munication systems has been widely studied. For the single-user case, the optimal solution is achieved by classical bit-loading [1]. The problem becomes much more complex when multiple users have to be serviced, as subcarriers have to be allocated to users in a way that maximizes a specific objective function which depends on the user’s data rate and power consumption on each subcarrier. Additional constraints regarding power consumption and/or data rate requirements further complicate the problem. In [2], the authors present dual methods for non-convex multicarrier resource alloca- tion problems (RAPs) with both concave as well as non- differentiable, ”discrete” utility functions. These methods are based on prior advances in optimization theory [3], [4] and have been investigated further for RAPs by various authors. In general, the main focus is on concave utility functions [5]– [8] but discrete utility functions are also considered [9]–[12], Manuscript received April 13, 2012; revised June 28, 2012; accepted August 6, 2012. The associate editor coordinating the review of this paper and approving it for publication was G. Yue. This work was supported by the UMIC research cluster at RWTH Aachen University. The authors are with the UMIC Research Centre, RWTH Aachen University, Aachen, Germany (e-mail: {goertzen, schmeink}@umic.rwth- aachen.de). Digital Object Identifier 10.1109/TWC.2012.091812.120513 usually in addition to the concave case. In [13], a discrete RAP is analysed with a Minimum Cost Network Flow model and dual methods are applied. This list is not intended to be exhaustive but showcases the popularity of dual methods in this field. To date, dual methods are applied as a powerful tool to solve arbitrary RAPs, which are often discrete due to their application in practical systems. The performance of these methods is attributed to the fact that the duality gap vanishes when the number of subcarriers tends to infinity, which can be interpreted as allowing arbitrary time-sharing within the system. In this paper, we show that the vanishing duality gap of discrete RAPs alone is not sufficient to guarantee near- optimal performance of dual methods. To the best of the authors’ knowledge, these discrete prob- lem formulations have never been analysed in detail from the perspective of linear and integer linear optimization. In this paper, we show that all multicarrier RAPs with discrete util- ity functions can be formulated as multiple-choice knapsack problems (MCKPs), which form a special class of NP-hard integer linear programs (ILPs). These combinatorial problems have been studied intensively and applied in various fields, including but not limited to operations research, VLSI design, and data compression. As an immediate conclusion, arbitrary time-sharing corresponds to a linear relaxation of the integer problem. Furthermore, the dual problems of the discrete and the relaxed formulation are identical, which means that all dual methods based on [2] can be shown to be rounding algorithms based on ”discretizing” the linear programming solution. In combinatorial optimization, this is a common ap- proach to obtain feasible approximative solutions, for example to be used in branch-and-bound algorithms. Interestingly, the performance of these rounding algorithms does not depend on the duality gap between the primal and dual problem, but on the rounding strategy and the costs induced by rounding towards a feasible solution. This implies that, at least for the discrete case, the optimality arguments of [2] and subsequent research have to be re-evaluated, as a small duality gap does not imply optimal performance of rounding algorithms. In this work, we analyse three formulations of the RAP commonly encountered in wireless multiuser multicarrier sys- tems, for example in the OFDMA downlink setting. These problems are sum rate maximization, sum power minimization and max-min fairness. All of them have been previously stud- ied and solved by dual methods for concave utility functions. Dual methods for the sum rate maximization problem (SRMP) and the sum power minimization problem (SPMP) with con- cave utility functions are derived in [5], while problems of proportional fairness are considered in [14]. The latter can be 1536-1276/12$31.00 c© 2012 IEEE G ¨ORTZEN and SCHMEINK: OPTIMALITY OF DUAL METHODS FOR DISCRETE MULTIUSER MULTICARRIER RESOURCE ALLOCATION PROBLEMS 3811 formulated as a max-min fairness problem (MMFP). In the case of a practical system with a finite number of modulation and coding schemes (MCSs), it is obviously advantageous to solve the discrete formulation instead of the concave one. Even if the utility step functions can be approximated by a concave function, one suffers quantization losses from rounding to- wards the nearest MCS. As this happens on every subcarrier, the performance loss scales with the number of subcarriers in the system. Furthermore, the discrete formulation is not limited to a certain shape or structure of the power-rate pairs of each subcarrier. Finally, the integer linear formulation and the dual methods discussed in this paper rely only on basic arithmetics, whereas dual methods for concave utility functions usually include at least some potentially complex logarithmic functions as well as the need to differentiate. The remainder of this paper is structured as follows: In Section II, the discrete RAP is formally formulated. We show that discrete RAPs belong to the class of MCKPs. In this section, we also introduce the three exemplary RAPs on which we focus our analysis. Section III deals with the Lagrangian dual problems corresponding to the discrete RAPs. In this section, we present the connection between dual and rounding methods and show that the duality gap is not a sufficient measure of performance. We follow this up with an analysis of the integrality gap and feasibility of rounding solutions in Section IV, which is where we present bounds on the integrality gap as well as results on the asymptotic optimality of dual methods. Section V concludes the paper. II. RESOURCE ALLOCATION PROBLEMS We consider a wireless communication system with K users and N subcarriers, in which every subcarrier can only be used by at most one user. Let pk,n denote the transmit power spent for user k on subcarrier n. Then, user k’s data rate on subcarrier n is given as rk,n = uk,n(pk,n) for a rate utility function uk,n incorporating channel gain information and other factors. In the case of concave utility functions, these can usually be described by uk,n(pk,n) = c log2 ( 1 + pk,n Γ ) (1) with appropriately chosen fitting factors c and Γ. This log- arithmic formulation is based on the Shannon bound but can also be used to approximate the data rates of practical systems [15]. However, in the case of a finite number of MCSs m = 1, . . . ,M , the utility functions are monotonically increasing non-negative step functions of the form uk,n(pk,n) = ⎧⎪⎪⎪⎨ ⎪⎪⎪⎩ rk,1,n, if pk,1,n ≤ pk,n < pk,2,n, rk,2,n, if pk,2,n ≤ pk,n < pk,3,n, . . . rk,M,n, if pk,M,n ≤ pk,n. (2) In this formulation, the channel gain information is incor- porated into the power values pk,m,n, m = 1, . . . ,M . As it is possible to not utilize a subcarrier at all, we as- sume that (pk,1,n, rk,1,n) = (0, 0) holds. The power-rate pairs (pk,m,n, rk,m,n), m = 1, . . . ,M , denote the discrete set of optimal operating points of the system. A visualization is given in Fig. 1, in which a step utility function uk,n and the 0 0 (pk,m,n, rk,m,n) power pk,n ra te r k ,n uk,n(pk,n) c log2 ( 1 + pk,n Γ ) Fig. 1. Utility function uk,n and corresponding power-rate pairs. The dashed line shows a fitted logarithmic utility function. corresponding power-rate pairs (pk,m,n, rk,m,n) are depicted. For comparison, the dashed line shows a concave logarithmic utility function which has been fitted to the power-rate pairs of uk,n. However, the results of this paper apply to arbitrary step utility functions and do not depend on the structure of the power-rate pairs. We now introduce binary decision variables xk,m,n ∈ {0, 1} which denote if user k is using MCS m on subcarrier n. If this is the case, xk,m,n is one, and zero otherwise. Because every subcarrier can only be used by exactly one user with a unique MCS, we obtain the set of constraints K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N. (3) A general RAP is a linear optimization problem of the form max K∑ k=1 M∑ m=1 N∑ n=1 ck,m,nxk,m,n (4) s.t. K∑ k=1 M∑ m=1 N∑ n=1 a (i) k,m,nxk,m,n ≤ b(i), i = 1, . . . , s, (5) K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N, (6) xk,m,n ≥ 0, ∀ k,m, n. (7) Parameter ck,m,n describes the profit gained from allocating the user-MCS pair (k,m) to subcarrier n. Positive values can be used to formulate a utility maximization problem, while negative values refer to costs that have to be minimized, as, for example, in power minimization problems. Similarly, the parameters a(i)k,m,n and b(i) in each of the s inequalities (5) can be used to describe system constraints like power budgets and data rate demands. Note that the constraint xk,m,n ≤ 1 does not have to be enforced explicitly as it is implied by (6). The domain of the RAP is D = Zq with q = KMN , which makes it an ILP. Clearly, we can also formulate the RAP in matrix-vector notation. We denote the vector (xk,m,n)k,m,n by x without specifying an enumeration order for reasons of 3812 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 11, NO. 10, OCTOBER 2012 0 0 power pk,n ra te r k ,n u1,n(p1,n) u2,n(p2,n) Fig. 2. Two users competing for resources on subcarrier n. No user dominates the other due to the different utility functions u1,n and u2,n. simplicity. The RAP then reads maximize cTx (8) subject to Ax ≤ b, (9) Cx = 1, (10) x ≥ 0, (11) in which the nth row of C is one in positions corresponding to the set {xk,m,n | k = 1, . . . ,K, m = 1, . . . ,M}, and zero elsewhere. Here, comparisons between vectors are componen- twise, 0 = (0, . . . , 0)T , and 1 = (1, . . . , 1)T . In general, all users are competing for resources on each subcarrier. On these subcarriers, varying channel gains influ- ence the values of pk,m,n. Furthermore, depending on the system and problem formulation, the utility rk,m,n gained from utilizing MCS m on subcarrier n varies between users. Fig. 2 shows an exemplary situation of two users competing for resources on a subcarrier. In this case, the second user has a weaker channel but a higher utility than the first user. We present three RAPs in the following subsections: Sum rate maximization and max-min fairness under a global power constraint as well as sum power minimization under individual rate constraints. A. Sum Rate Maximization Let the power-rate pairs (pk,m,n, rk,m,n) be as defined in (2) and a global power budget constraint p be given. Then, the SRMP is formulated as follows: max K∑ k=1 M∑ m=1 N∑ n=1 rk,m,nxk,m,n (12) s.t. K∑ k=1 M∑ m=1 N∑ n=1 pk,m,nxk,m,n ≤ p, (13) K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N, (14) xk,m,n ≥ 0, ∀ k,m, n. (15) To introduce an additional degree of fairness, some for- mulations of the SRMP include weights w1, . . . , wK and objective values wkrk,m,n. Because we allow arbitrary values for rk,m,n, this so-called weighted SRMP is covered by the above formulation. B. Sum Power Minimization The second problem formulation is the SPMP under rate demand constraints rk for each user: min K∑ k=1 M∑ m=1 N∑ n=1 pk,m,nxk,m,n (16) s.t. M∑ m=1 N∑ n=1 rk,m,nxk,m,n ≥ rk, k = 1, . . . ,K, (17) K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N, (18) xk,m,n ≥ 0, ∀ k,m, n. (19) The so-called weighted SPMP replaces pk,m,n in the objective function with wkpk,m,n for given weights w1, . . . , wK . As before, this formulation is covered by an appropriate transfor- mation of variables. C. Max-Min Fairness The last problem is the MMFP, which strives to distribute data rate as evenly as possible among users under a global power budget constraint p: max min 1≤k≤K { M∑ m=1 N∑ n=1 rk,m,nxk,m,n } (20) s.t. K∑ k=1 M∑ m=1 N∑ n=1 pk,m,nxk,m,n ≤ p, (21) K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N, (22) xk,m,n ≥ 0, ∀ k,m, n. (23) The objective function in (20) is not linear. However, by introducing an auxiliary variable z, the MMFP can be given in an equivalent linear formulation max z (24) s.t. K∑ k=1 M∑ m=1 N∑ n=1 pk,m,nxk,m,n ≤ p, (25) M∑ m=1 N∑ n=1 rk,m,nxk,m,n ≥ z, k = 1, . . . ,K, (26) K∑ k=1 M∑ m=1 xk,m,n = 1, n = 1, . . . , N, (27) xk,m,n ≥ 0, ∀ k,m, n. (28) Because there is only a discrete range of possible values for rk,m,n, it can be assumed w.l.o.g. that z takes only integer values, which means that the MMFP is an ILP. Strictly speaking, the introduction of z violates the prior definition of an RAP, but it is obvious that the MMFP is a problem which is not only closely related but also important for practical multicarrier systems. G ¨ORTZEN and SCHMEINK: OPTIMALITY OF DUAL METHODS FOR DISCRETE MULTIUSER MULTICARRIER RESOURCE ALLOCATION PROBLEMS 3813 A related problem is the proportional fairness problem, in which the data rates of all users have to be proportional to given factors φ1 : φ2 : · · · : φK . The problem of proportional fairness can be formulated as an MMFP by replacing rk,m,n in the objective function with φ−1k rk,m,n. In the general RAP, we use indices k and m to distinguish between users and MCSs, respectively. However, this distinc- tion is not needed from a formal point of view and user-MCS pairs can be indexed by a single variable j = 1, . . . , J . Doing so results in the following problem formulation: maximize J∑ j=1 N∑ n=1 cj,nxj,n (29) subject to J∑ j=1 N∑ n=1 a (i) j,nxj,n ≤ b(i), i = 1, . . . , s, (30) J∑ j=1 xj,n = 1, n = 1, . . . , N, (31) xj,n ≥ 0, ∀ j, n. (32) The above problem is known in combinatorial optimization as the MCKP if s = 1, and the multidimensional MCKP for s ≥ 2. The interpretation is to maximize the overall profit in a knapsack with weight constraint(s) b(i), i = 1, . . . , s, by filling it with items of weight(s) a(i)j,n and profit cj,n. As an additional restriction, each item belongs to a class of items n = 1, . . . , N , and exactly one item of each class has to be put into the knapsack. This restriction is called uniqueness or multiple-choice constraint. More details can be found in [16]. In summary, we obtain the following result. Proposition 1. The RAP in Section II is an MCKP with s additional inequality constraints. Thus, it is multidimensional for s ≥ 2. The SRMP is a classical MCKP, while the SPMP is a multidimensional MCKP with K inequality constraints. In its original formulation, the MMFP is a one-dimensional MCKP with a max-min objective. In its linear formulation, it has K + 1 inequality constraints. III. DUAL METHODS AND ROUNDING As shown above, RAPs are ILPs. As MCKPs they are NP-hard [16]. Their discrete nature means that optimization techniques based on continuity or convexity are not directly applicable. In [2], a dual method based on Lagrangian relax- ation is proposed. The approach is to optimally and efficiently solve the dual problem, and follow this up with a method to obtain a solution to the original RAP. The main steps of this procedure can be broadly summarized as 1) Formulate the discrete RAP. 2) Formulate and solve the dual problem. 3) From the optimal solution of the dual, obtain a solution to the RAP. If sensible, additional optimization steps can be performed at any point. In this case, questions of performance and time complexity have to be taken into account. Note that for an ILP of the form (8) with variable x ∈ D = Z q and c ∈ Rq, A ∈ Rr×q , b ∈ Rr, C ∈ Rs×q and d ∈ Rs, the Lagrangian dual problem is minimize bTλ+ dTμ (33) subject to − c+ATλ+CTμ ≥ 0, (34) λ ≥ 0. (35) The problem is optimized over the dual variables λ ∈ Rr and μ ∈ Rs corresponding to inequality and equality con- straints, respectively. Note that this dual problem is also the dual problem D of the linear program P obtained by extending the domain of x to D = Rq . In that case, the duality theorem of linear programming implies that strong duality holds [17]. Denoting the optimal objective values of P and D by p∗ and d∗, respectively, strong duality translates to p∗ = d∗. In general, the difference d∗ − p∗ describes the duality gap between the dual and the primal problem. In the following, we formulate the dual problems corresponding to the resource allocations problems above. A. Sum Rate Maximization For the SRMP, we introduce Lagrangian multipliers λ ∈ R and μ ∈ RN . The corresponding Lagrangian dual problem is minimize λp+ N∑ n=1 μn (36) subject to − rk,m,n + λpk,m,n + μn ≥ 0 ∀ k,m, n, (37) λ ≥ 0. (38) This formulation can be simplified by implicitly moving the constraints (37) into the objective function. The constraints in (37) are equivalent to μn ≥ rk,m,n − λpk,m,n ∀ k,m, n, (39) ⇔ μn ≥ max k,m {rk,m,n − λpk,m,n} ∀n. (40) From (36), it is clearly optimal to chose each μn as small as possible, i.e., μn = max k,m {rk,m,n−λpk,m,n} for n = 1, . . . , N . Thus, the dualized SRMP is minimize λp+ N∑ n=1 max k,m {rk,m,n − λpk,m,n} (41) subject to λ ≥ 0. (42) Despite not being linear, this formulation is advantageous for different reasons. Most importantly, it reduces the La- grangian dual problem to an optimization problem with a single variable λ, which can be efficiently solved with bisec- tion methods. Furthermore, the computation of μn provides an optimality criterion for the user-MCS pairs of each subcarrier, which we analyse in detail later. B. Sum Power Minimization For the SPMP, we introduce Lagrangian multipliers λ ∈ R K and μ ∈ RN . This yields the corresponding Lagrangian dual problem maximize K∑ k=1 λkrk − N∑ n=1 μn (43) subject to pk,m,n − λkrk,m,n + μn ≥ 0 ∀ k,m, n, (44) λ ≥ 0. (45) 3814 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 11, NO. 10, OCTOBER 2012 Analogously to the SRMP, it is optimal to chose each μn as small as possible while satisfying (44). With μn = maxk,m {λkrk,m,n − pk,m,n} w