The Linear Ordering Problem with Cumulative Costs
Contents
1. fails 2 500 500 0 0 0 0 2 4 500 500 0 0 0 0 3 6 500 500 0 0 0 0 6 8 500 500 0 1 0 0 0 5 4 10 500 500 0 0 1 2 1 212 0 0 13 1 4 12 500 500 0 0 30 0 2 447 0 2 786 6 10 14 500 50 0 2 1 130 8 5 218 11 9 8 058 2 0 16 500 5 5 6 28 191 6 4 978 407 8 61 402 8 1 Set 4 Asynchronous communication with scrambling instances average time sec s Enum max time sec s size Enum MIP Enum MIP speedup Enum MIP fails 2 500 500 0 0 0 0 0 0 3 4 500 500 0 0 0 0 0 0 2 6 500 500 0 0 0 0 0 0 3 8 500 500 0 1 0 0 0 7 4 10 500 500 0 0 1 3 1 096 0 0 15 8 4 12 500 500 0 0 31 3 2 310 0 2 473 4 8 14 500 50 0 2 1 801 5 6 880 6 6 35 469 5 1 16 500 2 6 3 8 362 0 1 316 204 8 9 821 5 1 Overall statistics instances average time sec s Enum max time sec s size Enum MIP Enum MIP speedup Enum MIP fails 2 2000 2000 0 0 0 0 0 0 10 4 2000 2000 0 0 0 0 0 0 12 6 2000 2000 0 0 0 0 0 0 24 8 2000 2000 0 1 1 146 0 0 1 0 22 10 2000 2000 0 0 0 9 488 0 0 15 8 21 12 2000 2000 0 0 20 0 1 373 0 9 786 6 37 14 2000 200 0 3 898 7 2 952 43 1 35 469 5 3 16 2000 16 7 9 20 421 2 562 794 6 61 402 8 4 Table 1 Computational results All the instances in our testbed were solved to proven optimality thus enabling us to benchmark the GRASP heuristic proposed in 1 evaluating the performance of this method was indeed our initial motivation in studying BLOP CC 7 Conclusions We have introduced and studied2. for the first time a new optimization problem related to the well known Linear Ordering Problem in which the solution cost is non linear due to a cumulative backwards propagation mech anism This model was motivated by a practical application in UMTS mobile phone telecommunication system We have formalized the problem in two versions and proved that they are both NP hard We have proposed a Mixed Integer Linear Programming model as well as an ad hoc enumerative algorithm for the exact solution of the problem Extensive computational results on large sets of instances have been presented showing that the proposed techniques are capable of solving in reasonable computing times all the instances coming from our application As a byproduct our method allowed to benchmark the GRASP heuristic proposed in 1 Future research should be devoted to enhancing the MIP formulation and or to embed more sophisticated pruning mechanisms in our enumerative scheme Also worth studying are more complex nonlinear cost functions applied to the basic Linear Ordering model Acknowledgements Work supported by MIUR and CNR Italy Thanks are due to Nevio Benvenuto Giambattista Carnevale and Stefano Tomasin for helpful dis cussions on the JOPCO methodology References 1 N Benvenuto G Carnevale and S Tomasin Joint Power Control and Receiver Optimization of CDMA Transceivers using Successive Inter ference Cancelation Technical Report DEI Dep
3. kn Depending on the cost function to be be used different optimization problems can be defined on G The most familiar one arises when the cost of a given permutation K only depends on the consecutive pairs kj ki 1 i 1 n 1 In this case one can typically associate a cost Cuv with each arc u v A and the problem reduces to finding a min cost Hamiltonian Path HP in G a relative of the famous Travelling Salesman Problem TSP 10 6 Note however that this model is only appropriate when the overall cost is simply the sum of the direct costs of putting an item right after another in the final permutation A more complex situation arises when a given cost guv has to be paid whenever item u is ranked before item v in the final permutation In this case a feasible solution can be more conveniently associated with an acyclic tournament defined as the transitive closure of an Hamiltonian path P k1 k2 lt kn 1 kn P highs CASH nS bea leet see Figure for an illustration The resulting problem then calls for a min cost acyclic tournament in G and is known as the Linear Ordering Problem LOP 3 4 5 13 Both HP and LOP are known to be NP hard problems Figure 1 Acyclic tournaments are made by an Hamiltonian path thick arcs plus its transitive closure thin arcs In some applications both the HP and the LOP frameworks are un appropriate to describe the cost function In this paper we intro
4. J ajes ij 2ij subject to x is the incidence vector of an acyclic tournment where x 1 if item 7 is placed before j in the final order x 0 otherwise In order to get an acyclic tournament it is shown in 3 that besides the obvious conditions Tij toy 1 Vp EA i lt j 16 it is sufficient to prevent 3 node cycles of the form xj tjk Tki 1 leading to the triangle inequalities Tij Tjk Tki L lt 2 17 Using the same set of variables one can rewrite the LOP CC constraints 1 as the nonlinear equalities n Qi Pi bD CijQjTLij Vice V 18 j 1 In order to get linear constraints we introduce the following n n 1 new variables a if xi 1 pa i S uea a e Wa 09 Thus 18 becomes linear in the y variables n Qi pi 5 CijYij j 1 11 and conditions 19 become Tij 0 gt yj 0 gt yy S May Tij l gt Yij Zaj yy 20 M 1 zij Tij l gt yij Saj yy Saj M 1 zij where M is a sufficiently large positive value Notice that constraints yj lt a M 1 xij can be removed from the model as the minimization of variables a implies that of variables y As to constraints yj lt M Zij they are redundant as well however our computational experience showed that they improve the numerical stability of the MIP solver so we keep them into our model Also from 19 the y variables are bounded by the a variables thus we can take M U Finally gt 0 ca
5. is solved through ILOG Cplex 9 0 2 Since the default ILOG Cplex tolerances are too large to solve correctly even small instances we used the following parameter setting all other parameters being left at default values e Absolute mipgap tolerance CPX PARAM EPAGAP le 13 e Relative mipgap tolerance CPX PARAM EPGAP le 11 e Integrality tolerance CPX_PARAM_EPINT le 9 e Optimality tolerance CPX_PARAM_EPOPT 1e 9 e Feasibility tolerance CPX_PARAM_EPRHS le 9 Unfortunately in some cases these tolerances are not small enough to ensure a valid resolution even when n 2 The reason is that the p matrix contains coefficients that may vary by several orders of magnitude hence even our feasibility tolerance of le 9 can be insufficient On the other hand ILOG Cplex does not support smaller values for this parameter so we could not fix this pathological situation and we had to report in Table 1 the number of instances that ILOG Cplex could not solve correctly Table 1 reports for each group of instances and for each size n the following information the number of instances solved the average solution times for both our enumerative code Enum and ILOG Cplex MIP the speedup of the enumerative code with respect to ILOG Cplex the maxi mum solution times and the number of instances not solved correctly by ILOG Cplex fails Computing times are expressed in CPU seconds and refer to a Pentium M 1 4 Ghz notebook with 512 MBytes o
6. of the values of all items v that follow u in the permu tation This setting implies a cumulative non linear propagation of the value of variables a along the node permutation hence the name Linear Ordering Problem with Cumulative Costs We illustrate the practical application that motivated the present study namely the optimization through the so called Successive Inter ference Cancellation method of UMTS mobile phone telecommunica tion system We prove complexity results and propose a Mixed Integer Linear Programming model as well as an ad hoc enumerative algorithm for the exact solution of the problem Extensive computational results on large sets of instances are presented showing that the proposed techniques are capable of solving in reasonable computing times all the instances coming from our application Key words Liner Ordering Problems MIP models enumerative search Computational analysis Telecommunication systems 1 Introduction Several optimization problems require finding a permutation of a given set of items that minimizes a certain cost function These problems are naturally modelled in graph theory terms by introducing a complete loopless digraph G V A whose vertices v V 1 n correspond to the n items to be sorted By construction there is a 1 1 correspondence between the Hamiltonian paths P k1 k2 kn 1 kn in G viewed as arc sets and the item permutations K k1
7. order and of the transmission power levels must ensure a reliable detection of the signals coming from all MTs A proper reception is ensured when the average Signal to Noise plus Inter ference power ratio SNIR is equal to a target level I For a SIC receiver the SNIR is related to the power of the interference generated from user i on user j denoted by p In particular upon detection of user kp the SNIR 1S QkpPkpkp No Pkpkp Dicu NsPikp Battery lifetime is one of the main limiting factors for mobile communication systems SNIR 3 where No noise power and Ng spreading factor are given parameters and Up kp 1 kp 2 it Kn 4 is the set of undetected user at stage p One then faces the problem of jointly optimizing the SIC detection order and the transmission power levels with the aim of minimizing the overall transmission power while ensuring a proper reception for all users This problem called joint power control and receiver optimization JOPCO has been introduced in 1 and can be formalized as follows given a set of users 1 2 n the interference factors p i i j 1 n the noise power No the spreading factor Ns the target ratio I and the maximum allowed power level U find the transmission power levels a i 1 n and the detection permutation K k1 kn that minimize the total transmission power m gt _ ag under the following constraints T Qk Pkiki N
8. weights p No pii and the costs cij Ns pji pii one then obtains precisely the BLOP CC formulation introduced in the previous section 3 Complexity of the LOP CC We start proving that the LOP CC problem is NP hard We first give a simple outline of the proof and then address in a formal proof the details required Our proof is by reduction from the following Hamiltonian Path problem HP which is known to be NP complete Definition 3 1 HP Given a digraph Gyp Vip Agp decide whether G contains any directed Hamiltonian path 10 I T T T AP JOPCO BER 107 J fi 2 4 6 8 10 12 14 16 number of active users 10 T T T T BER 107 i i 2 4 6 8 10 12 14 16 number of active users Figure 2 The average raw bit error rate BER vs the number of active users for synchronous top and asynchronous bottom transmissions with scrambling thin line and without scrambling bold line Napopco n dB A number of active users TNapiopco 2 57 n dB a T number of active users Figure 3 The expected total transmission power ratio 7 vs the number of active users for synchronous top and asynchronous bottom transmissions with scrambling thin line and without scrambling bold line Our reduction takes any HP instance Gyp Vyp Agp and computes the following LOP CC instance V V
9. J G Proakis Digital Communications 4th edition McGraw Hill New York 2004 G Reinelt The Linear Ordering Problem Algorithms and Applica tions Research and Exposition in Mathematics 8 Heldermann Verlag Berlin 1985 D Warrier and U Madhow On the Capacity of Cellular CDMA with Successive Decoding and Controlled Power Disparities in Proc Vehic Tech Conf VTC vol 3 1873 1877 1998 3GPP Technical Specification Group Radio Access Networks Radio Transmission and Reception 3G TS 25 102 version 3 6 0 1999 19
10. The Linear Ordering Problem with Cumulative Costs Livio Bertacco Lorenzo Brunetta Matteo Fischetti Department of Information Engineering University of Padova via Gradenigo 6A 35131 Padova Italy e mail livio bertacco lorenzo brunetta matteo fischetti unipd it October 13 2004 Abstract Several optimization problems require finding a permutation of a given set of items that minimizes a certain cost function These prob lems are naturally modelled in graph theory terms by introducing a complete digraph G V A whose vertices v V 1 n cor respond to the n items to be sorted Depending on the cost function to be be used different optimization problems can be defined on G The most familiar one is the min cost Hamiltonian path problem or its closed path version the Travelling Salesman Problem arising when the cost of a given permutation only depends on consecutive node pairs A more complex situation arises when a given cost has to be paid whenever an item is ranked before another one in the final per mutation In this case a feasible solution is associated with an acyclic tournament the transitive closure of an Hamiltonian path and the resulting problem is known as the Linear Ordering Problem In this paper we introduce and study for the first time a relevant case arising when the overall permutation cost can be expressed as the sum of terms a associated with each item u each defined as a linear combination
11. Tree n 1 initialize set S 1 2 n 2 EnumeratePermutationElement n EnumeratePermutationElement i Be for each element e in S do 4 remove e from S 5 perm i e 6 evaluate partial permutation x perm i perm i 1 perm n 7 if i gt 1 then EnumeratePermutationElement i 1 8 insert e back into S 9 enddo Figure 5 The basic method of the permutation kn is fixed to one of the n possible choices thus the root has n sons At depth 2 the next to last item kn 1 is fixed to one of the remaining n 1 possible choices and so on The search tree is visited in depth first manner The only required data structures to implement this method are an array to store the current partial permutation and another to keep track of the nodes that have not yet been inserted in the current partial permutation We chose this method to enumerate permutations rather than more so phisticated ones because we can compute very quickly a parametric lower bound for partial permutations to be used for pruning purposes thus enu merating very effectively a large number of nodes Our lower bound is computed as follows Given a permutation K ki gt kn we can write the corresponding node values ay as Akn Phr Qkn Pky 1 as Akn Ckn 1 kn Qkn 2 Pkn 2 Rg Qkn Ckn 2 kn Ae Wkn 1 Chkn 2 kn 1 and the total permutation cost m is the sum of all the a Notice that all the node weights p c
12. artment of Information Engineering University of Padova 2004 2 N Benvenuto and S Tomasin On the Comparison Between OFDM and Single Carrier Modulation With a DFE Using a Frequency Domain Feedforward Filter IEEE Transactions on Communications 50 6 947 955 2002 18 3 M Grotschel M J nger and G Reinelt A Cutting Plane Algorithm 11 12 13 14 for the Linear Ordering Problem Operations Research 32 1195 1220 1984 M Grotschel M J nger and G Reinelt On the acyclic subgraph polytope Mathematical Programming 33 28 42 1985 M Grotschel M J nger and G Reinelt Facets of the Linear Ordering Polytope Mathematical Programming 33 43 60 1985 G Gutin and A Punnen editors The Traveling Salesman Problem and its Variations Kluwer 2002 ILOG Cplex 9 0 User s Manual and Reference Manual ILOG S A http www ilog com 2004 ILOG Concert Technology 2 0 User s Manual and Reference Manual ILOG S A http www ilog com 2004 H Holma and A Toskala WCDMA for UMTS Radio Access for Third Generation Mobile Communications Wiley New York 2000 J K Lenstra A H G Rinnooy Kan and D Shmoys editors The Trav eling Salesman Problem A Guided Tour to Combinatorial Optimiza tion Wiley 251 305 1985 P Patel and J Holzman Analysis of a Simple Successive Interference Cancellation Scheme in a DS CDMA System IEEE J Select Areas Commun 12 727 807 1994
13. ce of 16 users uniformly distributed in the cell with a 3The UMTS technology considers up to 8 16 active users at a time a larger number of 14 Optimization by backtracking alee an FF WD find a starting heuristic solution H initialize the fifo queue Q with the elements in H LB p i UB EnumeratePermutationElement n LB output bestperm EnumeratePermutationElement i LB 7 8 9 10 Ti 12 13 14 15 16 17 18 19 repeat i times q pop Q perm i q calculate alphal q if i 1 then bestperm lt perm UB LB else LB LB alphalq gt 7 gclr q if LB lt UB then EnumeratePermutationElement i 1 LB endif push q into Q enddo Figure 6 The overall enumerative algorithm 15 radius of 580 m according to the so called log distance path loss model The input values T U Ng and No have been set to 0 625 10 0 16 and 0 50476587558415 respectively From each matrix p we have de rived 8 BLOP CC instances of different sizes n 2 4 16 using the equations given at the end of Section 2 to compute the weights p and costs Cuv The full set of these matrices p is available for download at http www math unipd it bertacco LOPCC_instances zip For each instance the corresponding MIP model is built up through a C code based on ILOG Concert Technology 2 0 8 All the model constraints are statically incorporated in the initial formulation and the outcome
14. duce and study for the first time a relevant case arising when the overall permutation cost can be expressed as the sum of terms a associated with each item u each defined as a linear combination of the values a of all items v that follow u in the permutation To be more specific we address the following problem Definition 1 1 LOP CC Given a complete digraph G V A with nonnegative node weights py and nonnegative arc costs Cyy the Linear Or dering Problem with Cumulative Costs LOP CC is to find an Hamilto nian path P ky k2 kn 1 kn and the corresponding node values Qy that minimize the total cost m P Soa v 1 under the constraints n Qk Pki J CkikjQk forti n n 1 1 1 j i 1 Constraints 1 imply a cumulative backward propagation of the value of variables a for v n n 1 1 hence the name of the problem We will also address a constrained version of the same problem namely Definition 1 2 BLOP CC The Bounded Linear Ordering Problem with Cumulative Costs BLOP CC is defined as the problem LOP CC above plus the additional constraints aSU WieV 2 where U is a given nonnegative bound Notice that BLOP CC can be infeasible As shown in the next section BLOP CC finds important practical applications in particular in the opti mization of mobile telecommunication systems In this paper we introduce and study both problems LOP CC and BLOP CC In Section 2 we give
15. f amounts to estab lishing an upper bound U Bygooa n M on the cumulative cost 7 P of any good Hamiltonian path P as well as a lower bound LBnogooa n M on the cumulative cost 7 P of any non good Hamiltonian path P and to show that UBgooa n M lt LBnogooa n M for all n and for a value of M such that log M is polynomial in n The lower bound LBrogooa n M corresponds to the case where only one direct arc in P has cost 2M hence it can be computed in a straightforward way as LBgooa n M 2M 11 As to upper bound UBgooa n M it is computed by considering the cumulative cost of a Hamiltonian path P where all direct arcs have cost M whereas all transitive arcs have cost 2M This case is illustrated in Figure 4 To be more precise we claim that m Pr lt U Bgooa n M EME aE 4 M 12 holds for any Hamiltonian path P in G whose direct arcs all have cost M where M gt 1 is assumed The proof of this claim is by induction on n The claim clearly holds in cases n 1 and n 2 where we have m P 1 and a P2 M 2 respectively We assume now that 12 holds for all n lt h for a given h gt 2 and we prove that it also holds for n h 1 Let Pa n 1 k1 k2 kn kn 1 be any Hamiltonian path whose direct arcs all have cost M and let Ph k2 k3 kn kh41 and P 1 k3 k4 gt kn kn41 be obtained from Ph 1 by removing its first arc and its first two arcs respectivel
16. f main memory The computational results clearly show that our enumerative approach outperforms ILOG Cplex and is up to three orders of magnitude faster As a matter of fact in no instance ILOG Cplex beated the enumerative code As to scalability the enumerative code proved capable of solving instances with n 20 in about 4 hours active users is unrealistic for this application 16 Set 1 Synchronous communication without scrambling instances average time sec s Enum max time sec s size Enum MIP Enum MIP speedup Enum MIP fails 2 500 500 0 0 0 0 2 4 500 500 0 0 0 0 0 0 2 6 500 500 0 0 0 0 0 0 7 8 500 500 0 0 497 0 0 0 6 7 10 500 500 0 0 0 5 186 0 0 5 3 6 12 500 500 0 0 9 6 787 0 2 455 5 9 14 500 50 0 2 395 0 1 906 12 5 2 537 6 1 16 500 5 4 8 22 233 0 4 574 381 9 60 096 2 1 Set 2 Synchronous communication with scrambling instances average time sec s Enum max time sec s size Enum MIP Enum MIP speedup Enum MIP fails 2 500 500 0 0 0 0 3 4 500 500 0 0 0 0 5 6 500 500 0 0 0 0 8 8 500 500 0 0 0 0 1 0 7 10 500 500 0 0 0 6 237 0 0 10 0 7 12 500 500 0 0 8 8 441 0 9 319 8 10 14 500 50 0 5 267 4 503 43 1 2 256 9 1 16 500 4 15 0 14 473 2 964 794 6 49 424 0 1 Set 3 Asynchronous communication without scrambling instances average time sec s Enum max time sec s size Enum MIP Enum MIP speedup Enum MIP
17. n be assumed since p c gt 0 As it is customary in LOP models one can use equations 16 to elimi nate all variables x with 7 gt j 2 and modify the triangle inequalities into Tij Tjk Lig S1 forall lt i lt j lt k lt n Lij Tjk Zik lt 0 frali lt i lt j lt k lt n This leads to the following MIP model for BLOP CC minimize Sij Qi subject to Tij Tjk tip S1 forl lt i lt j lt k lt n Zij Tjk Tik Z 0 fri lt i lt j lt k lt n ai pi har Cig Yay forl lt i lt n Yij lt Ux forl lt i lt j lt n Yji U Say forl lt i lt j lt n Yij Z 0 U 1 zij forl lt i lt j lt n Yji 2 Qi U Tij forl lt i lt j lt n 0 lt aji lt U forl lt i lt n Yij 0 for l lt i F g lt n te 0 1 forl lt i lt jg lt n 5 An ad hoc enumerative algorithm Our enumerative algorithm is based on a standard backtracking technique akin to those used in Constraint Programming to generate all permuta tions and to find one with the lowest total cost To limit the number of permutations actually evaluated we use a pruning mechanism based on lower bounds Permutations are built progressively and are extended backwards from the last node At the root of the search tree depth 0 none of the permu tation elements in K kj kn is fixed At depth 1 the last element 2The a variables could be removed as well but this would have a marginal effect on the solution time of the model 12 Permutation generation TraverseSearch
18. nt the set S as a FIFO queue to be initialized with the desired starting permutation the last node in the sequence being the first to be extracted In our implementation we use a simple yet effective heuristic to find a good initial solution for the BLOP CC instances arising in our telecom munication application Namely we sort the nodes by decreasing autocor relation factors pi and consider the associated permutation the first and last node in the permutation being those with the largest and smallest pii respectively to initialize our incumbent solution Alternative heuristics to find a good initial permutation are presented in 1 Our complete algorithm is outlined in Figure 6 6 Computational results We have compared the performance of our enumerative algorithm with that of a state of the art commercial MIP solver ILOG Cplex 9 0 2 7 applied to the MIP model of Section 4 The outcome of this experiment is reported in Table 1 where 4 large sets of BLOP CC instances have been considered The instances used in our study have been provided by the telecom munications group of the Engineering School of the University of Padova and are related to detection order optimization in UMTS networks 1 All the four communication scenarios considered in 1 have been addressed synchronous and asynchronous transmission with and without scrambling For each scenario 500 matrices p have been randomly generated as suming the presen
19. ontribute to the total cost so their sum can be used as an initial lower bound for the cost of any permutation Assume now that nodes kj41 hkj42 kn have already been chosen When node k is also chosen one can easily compute the corresponding Qk by using equation 1 Furthermore the contribution of this g to the final cost of any permutation of the type ki kiz1 kn is given 13 by Qk gt Cuk 20 ug ki kn regardless of the rank of the remaining nodes in the complete permutation This property allows us to compute easily in a parametric way a valid lower bound on the cost of any such permutation To be more specific our pruning mechanism works as follows We start with lower bound LB p and with an empty permutation We then build up partial permutations recursively Every time a new node k is inserted in front of the current permutation we compute the corresponding Qk and add 20 to the current lower bound LB If the resulting LB is strictly smaller than the incumbent solution value we proceed with the recursion otherwise we backtrack and update LB accordingly A small modification of this algorithm can be used to start with a given permutation rather than from scratch thus allowing the enumer ative search to quickly produce improved permutations through successive modifications of the starting one To this end the only change required at Step 3 of the algorithm of Figure 5 is to impleme
20. oy Pkiki Dieu aN s Pik Qi lt U 6 In 1 a simple GRASP heuristic is proposed for JOPCO with the aim of minimizing the system transmit power under the constraint of ensuring the same quality of the transmission measured by the average raw Bit Er ror Rate BER to all users In particular the requirement on the BER is translated into a constraint on the SNIR at the detection point of each user as discussed before Extensive experiments are reported showing that the JOPCO technique performs much better than the usual Average Power AP approach in all the four scenarios simulated both in terms of quality of the transmission BER and of allocated transmission power In particular Figure 2 taken from 1 illustrates the average BER vs the number n of active users for so called synchronous and asynchronous transmission sys tems and compares the JOPCO and AP methodologies Thin and bold lines correspond to the case with and without the so called scrambling operation on transmitted data respectively It can be seen that both with and without scrambling JOPCO ensures approximately a constant average raw BER of 107 up to 10 active users with respect to the classical AP technique In the case of syncronous transmission without scrambling AP gives a BER that is even lower than the target just because it allocates much more transmission power than necessary to guarantee the target quality as can be seen in Figure 3 top When a large
21. r number of active users is present instead JOPCO has slight performance degradation due to errors in the interference cancellation The JOPCO performance is indeed very good up to 10 active users as the average BER is below 107 When a larger number of active users for Late n 5 is present instead we have a performance degradation due to interference effects Figure 3 also taken from 1 gives the expected total transmission power ratio expressed in dB 7 as a function of the number of active users with and without scrambling i e Pee i 0 O where pE and P TEn represent the total transmission power allocated by AP and JOPCO respectively In all cases we observe that the JOPCO approach requires a reduced transmission power with respect to the AP approach In particular for a full loaded synchronous resp asynchronous system without scrambling on average the system power requirement using the JOPCO technique is 7 dB resp 3 dB lower than that for AP When scrambling is considered instead the JOPCO power requirement is 3 dB resp 2dB lower than that for AP We next show how JOPCO can be formulated as a BLOP CC Clearly for any given user permutation K the power levels a are univocally deter mined by the SNIR constraints 5 Indeed rewriting 5 as No Pris Ns X icu Pte Pkiki Qk one has that values az can easily be computed in the reverse order i n n 1 1 Defining the
22. t MTs the Universal Mobile Telecommu nication Standard UMTS 15 adopts the so called code division multiple access technique where each terminal is identified by a specific code Due to the distortions introduced by radio propagation the MTs partially interfere with each other hence the need to keep the multiuser access interference below an acceptable level A very effective technique for interference reduc tion has been proposed 11 and is called Successive Interference Cancella tion SIC According to this method MT signals are detected sequentially from the received signal according to a predetermined order After each detection interference is removed from the received signal thus allowing for improved detection for the next users A crucial problem in the design of the SIC system is therefore the choice of the detection order Usually users are ordered by decreasing received power 11 although a better performance can be obtained by considering also the level of mutual interference among users A second issue is the choice of the power level a at which the i th user has to transmit its data Indeed a large power level typically allows for an improved signal detection whereas the minimization of the transmission power yields a longer duration of the batteries of the MT Moreover physical and regulatory constraints impose an upper bound U on the transmission power of the mobile terminals Both the choice of the cancellation
23. the practical application that motivated the present study and leaded to the patented new methodology for cellular phone man agement described in 2 In Section 3 we show that both LOP CC and BLOP CC are NP hard A Mixed Integer linear Programming MIP model is presented in Section 4 whereas an ad hoc enumerative method is intro duced in Section 5 Extensive computational results on a large set of in stances are presented in Section 6 whereas some conclusions are drawn in Section 7 As G is assumed to be complete in the sequel we will not distinguish between an Hamiltonian path P k1 k2 kn 1 kn and the associ ated node permutation K ky kn Moreover given any Hamiltonian path P k k2 Kn 1 kn we call direct all arcs kj kj41 P the thick ones in Figure 1 whereas the arcs kj kj for j gt i 1 are called transitive these are precisely the arcs in P P depicted in thin line in Figure 1 Finally we use notation 7 P to denote the cumulative cost of an Hamiltonian path P defined as the LOP CC cost t p ay of the corresponding permutation 2 Motivation In this section we outline the practical problem that motivated the present paper the interested reader is referred to 1 9 and 12 for more details In wireless cellular communications mobile terminals MTs communi cate simultaneously with a common Base Station BS In order to distin guish among the signals of differen
24. y We have h 1 h 1 TWP X aK bD Qk Qk i 1 i 2 Py Ok h 1 lt a P Mak 1 2M Xak because of 1 and 10 i 3 lt am P Ma P since n Ph gt ax 1 2M n P 1 since n Ph 1 hs Qk lt 1 M x Pp 2Mr Pp 1 The claim then follows from the induction hypothesis as we have mea lt CEI 4 M Me 4 M 3 Fao a eM 13 5 lt M 3 54 Me since M 2 lt M 14 lt Mr 4 1 yh since h gt 2 15 To complete the complexity proof we have to choose a value for M that guarantees U Byooa n M lt LBnogooa n M i e MT 44M lt 2M 4M lt MTL 4 lt M We then set M 4 1 whose size log M O n is polynomial in n as required 10 Corollary 3 1 1 BLOP CC is NP hard Proof We use the same construction as in the proof of the previous theorem with U t UBgooaln M O M O 4 large enough to make all good Hamiltonian paths in G feasible for the BLOP CC instance but still with size log U O n 4 A MIP model In this section we introduce a MIP model for BLOP CC derived from the LOP model of Gr tschel J nger and Reinelt 3 As already mentioned in a standard linear ordering problem we have n items to be placed in a convenient order If we place item 7 before item j we pay a cost of gij The objective is to choose the item order that minimizes the total cost This problem can then be modelled as min
25. yp l n 2 aie 9 i M if 4 7 AHP E a et 2M otherwise Vi jEV i j 10 where M is a sufficiently large positive value to be defined later The construction can clearly be carried out in polynomial time provided that value M can be stored in a polynomial number of bits a property that will be asserted in the formal proof Figure 4 The worst case good path used in the complexity proof Good Hamiltonian paths of G i e those corresponding to Hamil tonian paths in Gyp only involve direct arcs of cost equal to M while all the transitive arcs have a cost not larger than 2M see Figure 4 for an illustration It is therefore not difficult to show that for sufficiently large M the overall cumulative cost associated with such a path is 7 P M 0O M On the other hand if P does not correspond to a Hamil tonian path in Gyp then it has to involve at least one direct arc of cost 2M hence its cumulative cost 7 P cannot be smaller than 2M For a large M our construction then ensures that 7 P lt 7 P for any good Hamiltonian path P and for any non good Hamiltonian path P which implies that Gyp contains an Hamiltonian path if and only if any arbitrary optimal LOP CC solution corresponds to a good Hamiltonian path or equivalently if the optimal LOP CC value is strictly less than 2M Theorem 3 1 LOP CC is NP hard Proof Given the transformation above our formal proo
Download Pdf Manuals
Related Search