# Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.

Let's say that I am some business owner with a set of $$n$$ possible store locations $$L = \lbrace x_i \in \mathbb{R}^m \rbrace_{i=1}^n$$, for $$m > 1$$, where I'd like to build some new stores. I have estimates that each location $$x_i$$ will cost $$c_i$$ to build and should make a corresponding profit $$p_i$$ after opening. Further, I have a budget of $$B$$ that I cannot exceed and all stores I build must be at least a distance $$D$$ away from each other based on the metric $$d(\cdot,\cdot)$$. My goal is to build stores such that I maximize my profit and stay within the desired constraints. Note that $$(L,d)$$ is a metric space.

Define $$S = (s_1, s_2, \cdots, s_n) \in \lbrace 0, 1 \rbrace^n$$ such that $$s_i = 1$$ means I am building a store at location $$i$$ and $$s_i = 0$$ means I am not. It is clear that this optimization problem can be posed as:

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\&\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\& && d( x_j, x_i ) \geq D \hspace{1cm} \forall j > i \geq 1 \text{ where } s_i = s_j = 1 \end{align*}

Now when looking at this problem, it is quite simple to solve it using dynamic programming if we assume the store locations are far enough apart that the distance constraint is automatically satisfied or the locations are all contained within some 1-dimensional affine subspace. Outside of this, things seem a bit complicated.

My thought is to initially construct a graph $$G = (V,E)$$ such that $$V(G) = \lbrace 1, \cdots, n \rbrace$$ and $$E(G) = \lbrace ij \;|\; d(x_i, x_j) \geq D \rbrace$$. From here, a simple but inefficient idea is to enumerate all cliques of $$G$$, solve them using dynamic programming, and choose the solution, across all of them, that's the best. This should be fine because each clique, by construction, is comprised of store locations that satisfy the distance constraints and in turn should individually allow for efficient solutions. This might be formalized by defining $$\lbrace C_1, C_2, \cdots, C_p \rbrace = \text{cliques}(G)$$ as the set of cliques of $$G$$ and then solving

\begin{align*}& &&\max_{S^{(j)} \in \lbrace 0, 1 \rbrace^n} \sum_{i = 1}^n p_i s_i^{(j)} \tag*{}\\&\text{subject to} &&\sum_{i = 1}^n c_i s_i^{(j)} \leq B\\& &&s_i^{(j)} = 0 \hspace{1cm} i \in V(G) \setminus V(C_j) \end{align*}

for each $$j^{th}$$ clique $$C_j$$. From here we then choose $$S^* = \arg \max_{j \in \lbrace 1, \cdots, p \rbrace} \sum_{i=1}^n p_i s_i^{(j)}$$ as the optimal solution for the overall problem.

Obviously the crappy thing about the above approach is that we have to enumerate all the cliques, which may be both a large set and computationally demanding to find. Is there any structure to the problem I am missing that might make this solvable without enumerating all the cliques in this formulation? Perhaps there's a different perspective that could shed some light?

• If the dimension is sufficiently large, this is probably hard (e.g., NP-hard). Are you interested in the asymptotic worst-case running time (i.e., theoretical perspective), or solving this in practice? If the latter, what are typical ranges of values for the parameters (e.g., $m,n$)? – D.W. Nov 9 '18 at 19:49
• Yes, this seems to be NP-Hard from my reasoning about it. I am more interested in the theoretical side of things since a practical version of this problem probably wouldn’t be too tough to solve in practice (I would expect less than 100 store locations and $m=2$ in practice). Obviously if things are NP-Hard, this won’t be solved too efficiently without approximations. – spektr Nov 9 '18 at 20:01

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\ &\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\ & && s_i + s_j \leq 1 \hspace{1cm} \forall j > i \geq 1 \text{ where } d(x_i, x_j) \leq D \end{align*}
• @spektr Oh wait. Actually, this problem is obviously NP-hard via a reduction from KNAPSACK. If we completely ignore the spatial aspect and distance constraints (e.g.: make $D$ arbitrarily large), you just have a set of items with profits and costs, a maximum budget on total cost, and wish to maximize profit, exactly as in KNAPSACK. – mhum Nov 9 '18 at 21:44