2
$\begingroup$

I do not know the integer programming problem. I am reading a paper (1 below) which makes the following claim for the problem P1. I have two questions regarding this claim which I will post after posting the problem from the paper.

Problem P1 from the paper

Problem (P1) is a three-dimensional integer programing problem whose solution space is in the size of $2^{NM(K+2)}$.

My questions are: 1. Why is the problem P1 a 3D problem? P1 is given in the image with this post. 2. Why is the solution space $2^{NM(K+2)}$? I understand that without know N,M, or K no one can give me an answer about this solution space. But I want to know how is the size of the solution space found by the authors?

$[1]$ Multi-Server Multi-User Multi-Task Computation Offloading for Mobile Edge Computing Networks

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$
  1. It's a 3D problem because $a_{nmk}$ has three subscripts, so that $a\in \lbrace 0,1 \rbrace^{N\times M\times K}$ where $N=|\mathcal{N}|$ etc.
  2. Assuming that everything other than the $a$ variables is a constant, I don't know where they get $2^{NM(K+2)}$ for the size of the solution space. Ignoring (13c), the size of the solution space would be $2^{NMK}$. Assuming that (13c) holds for all $m\in\mathcal{M}$ and $n\in\mathcal{N}$ (the presentation is mathematically sloppy), the feasible portion of the solution space would have size $K^{NM}$. (For each combination of $n$ and $m$, you would have $K$ ways to satisfy (13c), and choices for one $n,m$ pair would be independent of choices for other pairs.)
$\endgroup$
3
  • $\begingroup$ $n, m, k$ are not constants. So what you are saying is the solution space they have mentioned is wrong? $\endgroup$ Commented May 28, 2020 at 3:11
  • $\begingroup$ The lower case $n,m,k$ are indices. $\endgroup$ Commented May 29, 2020 at 16:06
  • $\begingroup$ Yes, I think their solution space is wrong. $\endgroup$ Commented May 29, 2020 at 16:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.