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?
