0
$\begingroup$

Let $H$ be a $4\times 8$ matrix and $R$ is a vector of 2 elements.

H={{1311, 1274, 1183, 1143, 1267, 1352, 1236, 1175},{1197, 1181, 1050, 1312, 1089, 1155, 1156, 1253},{1266, 1174, 1071, 1090, 1190, 1281, 1363, 1036},{1097, 1105, 1250, 1201, 1135, 1055, 1034, 1167}};

PT=1;

R={1.4,1.6};

The $(k,n)$th element of the matrix $H$ given by $H_{k,n}$

Variable are: $C^{4\times 8}$ (Binary Integer variables, $C_{k,n}\in\{0,1\}$), $P^{4\times 8}$ (Continuous variables )

$R_{k,n}=\frac{1}{8}\log_2(1+P_{k,n}H_{k,n})$ where $k\in\{1,\cdots,4\}$ and $n\in\{1,\cdots,8\}$

The optimization problem is:

Maximize $\sum_{k=1}^{2}\sum_{n=1}^{8}C_{k,n}R_{k,n}$

subject to

$\sum_{k=1}^{4}C_{k,n}=1,\forall n,n\in\{1,2,3,\cdots,8\}$

$\sum_{k=1}^{4}\sum_{n=1}^{8}C_{k,n}P_{k,n}\le PT$

$0<=P_{k,n}<=PT$

$\sum_{n=1}^{8}C_{k,n}R_{k,n}\ge R_{k-2}, k\in\{3,4\}$

I have defined $C$ and $P$ as arrays. But I do not know how I can define $R_{k,n}$.

The MMA formulation for other constraints are here.

Maximize [C[[1,1]].R[[1,1]]+C[[1,2]].R[[1,2]]+C[[1,3]].R[[1,3]]+C[[1,4]].R[[1,4]]+C[[2,1]].R[[2,1]]+C[[2,2]].R[[2,2]]+C[[2,3]].R[[2,3]]+C[[2,4]].R[[2,4]],C[[1,1]]+C[[2,1]]+C[[2,1]]+C[[2,1]]==1, C[[1,2]]+C[[2,2]]+C[[2,2]]+C[[2,2]]==1 && C[[1,3]]+C[[2,3]]+C[[2,3]]+C[[2,3]]==1 && C[[1,3]]+C[[2,3]]+C[[2,3]]+C[[2,3]]==1 && C[[1,4]]+C[[2,4]]+C[[2,4]]+C[[2,4]]==1 & C[[1,5]]+C[[2,5]]+C[[2,5]]+C[[2,5]]==1 && C[[1,6]]+C[[2,6]]+C[[2,6]]+C[[2,6]]==1 && C[[1,7]]+C[[2,7]]+C[[2,7]]+C[[2,7]]==1 && C[[3,1]].R[[3,1]]+C[[3,2]].R[[3,2]]+C[[3,3]].R[[3,3]]+C[[3,4]].R[[3,4]]>=R[[1]] && C[[4,1]].R[[4,1]]+C[[4,2]].R[[4,2]]+C[[4,3]].R[[4,3]]+C[[4,4]].R[[4,4]]>=R[[2]] && C[[1,1]].P[[1,1]]+C[[1,2]].P[[1,2]]+C[[1,3]].P[[1,3]]+C[[1,4]].P[[1,4]]+C[[2,1]].P[[2,1]]+C[[2,2]].P[[2,2]]+C[[2,3]].P[[2,3]]+C[[2,4]].P[[2,4]]+C[[3,1]].P[[3,1]]+C[[3,2]].P[[3,2]]+C[[3,3]].P[[3,3]]+C[[3,4]].P[[3,4]]+C[[4,1]].P[[4,1]]+C[[4,2]].P[[4,2]]+C[[4,3]].P[[4,3]]+C[[4,4]].P[[4,4]]<=PT && Array[C,{4,8}]\[Element] Integers && 0<=Array[P,{4,8}]\[Element]<=PT, Integers  {C,P}]

Is it correct?

$\endgroup$
6
$\begingroup$

Here's one way to code this optimization problem in MMA (I am guessing it concerns a resource allocation problem in a broadcast multi-carrier communication channel).

First, define a convenience function for the (subcarrier) capacity as follows:

r[p_, h_] := (1./8.) Log[2, 1 + p h]

It is also convenient to define the following two (abstract) matrices whose elements are the problem's optimization variables (subcarrier power and occupation for each user):

vc = Array[c, {4, 8}];
vp = Array[p, {4, 8}];

You can verify that the objective function of your problem equals

obj = Plus @@ Flatten[vc r[vp, H]]

Lets go ahead defining the constraints, in the order presented in your formulation.

c1 = And @@ Thread[Plus @@@ Transpose[vc] <= 1];
c2 = Plus @@ Flatten[vc vp] <= PT;
c3 = And @@ Thread[Flatten[vp] >= 0];
c4a = Plus @@ Flatten[vc[[3]] * r[vp[[3]], H[[3]]]] >= R[[1]];
c4b = Plus @@ Flatten[vc[[4]] * r[vp[[4]], H[[4]]]] >= R[[2]];

Note that for the per-subcarrier power constraint (c3) I have only considered the lower bound since the upper bound is implicitly guaranteed by c2

Now we could proceed in setting up one of MMA's optimizing functions, taking into account that the elements of vc are binary integers. We can of course do so, however, the resulting problem is a mixed integer problem which is in general difficult to solve, especially with large number of variables.

One approach to handle mixed integer problems is to consider a "relaxation" of the problem where the integer variables are assumed to be continuous. One natural approach for this specific problem is to assume that $C_{k,n}\in[0,1]$ instead of $C_{k,n}\in\{0,1\}$, which can be expressed as the following additional constraint

c5 = And @@ Thread[0 <= Flatten[vc] <= 1];

Now, this relaxation approach will in general provide non-integer optimal variables and then we have the problem of deciding how to interpret them as integers.

Fortunately, it can be shown that for the specific relaxed problem we are considering, the optimal $C_{k,n}$ will be either $0$ or $1$ (even though they are allowed to take any in-between value!). In addition, the relaxed problem can be shown to be convex (*), hence we do not need to consider any initial estimate for the optimization variables.

Given the above, it is now a simple task to ask MMA to provide the optimal allocation as follows:

sol = FindMaximum[{obj, c1 && c2 && c3 && c4a && c4b && c5}, 
   Flatten[{vp, vc}]];
Chop[sol, 10^-10]
{7.27957, {p[1, 1] -> 1.04985, p[1, 2] -> 1.05046, p[1, 3] -> 1.06491,
   p[1, 4] -> 1.05225, p[1, 5] -> 1.05659, p[1, 6] -> 1.04945, 
  p[1, 7] -> 1.05268, p[1, 8] -> 1.05027, p[2, 1] -> 1.05243, 
  p[2, 2] -> 1.05128, p[2, 3] -> 1.05409, p[2, 4] -> 1.05089, 
  p[2, 5] -> 1.05319, p[2, 6] -> 1.05326, p[2, 7] -> 1.05273, 
  p[2, 8] -> 1.05042, p[3, 1] -> 0.125021, p[3, 2] -> 0.124959, 
  p[3, 3] -> 0.125392, p[3, 4] -> 0.124954, p[3, 5] -> 0.12497, 
  p[3, 6] -> 0.12503, p[3, 7] -> 0.125077, p[3, 8] -> 0.124928, 
  p[4, 1] -> 0.125038, p[4, 2] -> 0.124907, p[4, 3] -> 0.125011, 
  p[4, 4] -> 0.124978, p[4, 5] -> 0.12493, p[4, 6] -> 0.125491, 
  p[4, 7] -> 0.129967, p[4, 8] -> 0.124954, c[1, 1] -> 0, 
  c[1, 2] -> 0, c[1, 3] -> 0, c[1, 4] -> 0, c[1, 5] -> 0, 
  c[1, 6] -> 0, c[1, 7] -> 0, c[1, 8] -> 0, c[2, 1] -> 0, 
  c[2, 2] -> 0, c[2, 3] -> 0, c[2, 4] -> 0, c[2, 5] -> 0, 
  c[2, 6] -> 0, c[2, 7] -> 0, c[2, 8] -> 0, c[3, 1] -> 1., 
  c[3, 2] -> 1., c[3, 3] -> 0, c[3, 4] -> 0, c[3, 5] -> 1., 
  c[3, 6] -> 1., c[3, 7] -> 1., c[3, 8] -> 0, c[4, 1] -> 0, 
  c[4, 2] -> 0, c[4, 3] -> 1., c[4, 4] -> 1., c[4, 5] -> 0, 
  c[4, 6] -> 0, c[4, 7] -> 0, c[4, 8] -> 1.}}

The output verifies our claims (with a precision of 10 digits, which can be increased if you wish by operating in a greater WorkingPrecision).

Lets investigate the result. Subcarrier allocation matrix (all subcarriers given to users 3 and 4 apparently due to their rate constraint):

Chop[vc /. sol[[2]], 10^-10]
{{0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 0, 0, 0, 0, 0, 0}, 
 {1., 1., 0, 0, 1., 1., 1., 0}, 
 {0, 0, 1., 1., 0, 0, 0, 1.}}

Rates achieved by users 3, 4 are above their minimum requested values:

{c4a[[1]], c4b[[1]]} /. sol[[2]]

{4.56279, 2.71679}

(*) to be exact the problem is not convex in this form but can be transformed so by a simple change of variables.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice approach (and an upvote). I must have missed this a few days ago (the subject header is kinda vanilla). $\endgroup$ – Daniel Lichtblau Jun 26 '16 at 22:22
  • $\begingroup$ @Stelios, Thank you very much for your very intuitive answer. However, when i solve this minlp problem in AMPL, I get a different objective value, much higher than this, around 7.20. Also, in MMA, notive that only 4 subcarriers are utilized, rest of the subcarriers are not assigned at all! $\endgroup$ – Srestha Narayanan Jun 27 '16 at 13:07
  • $\begingroup$ @Stelios, I think constraint c1 is not written correctly. Instead of summing up in the horizontal direction , we need the sum up the in the vertical direction. Please write it correctly. And I do not have any freedom to relax the integrality constraint..Can it solve the minlp? $\endgroup$ – Srestha Narayanan Jun 27 '16 at 13:44
  • $\begingroup$ @SresthaNarayanan Yes, I have also noticed that the constraint is not correct. Apologies for the inconvenience, I will edit the answer later and further investigate. $\endgroup$ – Stelios Jun 27 '16 at 13:51
  • 1
    $\begingroup$ @SresthaNarayanan Are these "good solution" properties valid in the AMPL answer? I would not consider MMA for MINLP in general, except for toy-size problems. For the particular problem you can avoid MINLP formulations altogether as shown in this paper $\endgroup$ – Stelios Jun 27 '16 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.