2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$)? $\endgroup$ – D.W. Nov 9 '18 at 19:49
  • $\begingroup$ 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. $\endgroup$ – spektr Nov 9 '18 at 20:01
2
$\begingroup$

I'm not sure why you would need to enumerate the cliques. You can encode the distance constraints explicitly in just a quadratic number of constraints.

\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*}

$\endgroup$
  • $\begingroup$ Very interesting modification to the optimization problem, I appreciate this insight. Based on this form, it appears this is simply a 0-1 integer linear programming problem, which is NP-Hard in this circumstance. Fortunately this could then be approximated by a LP relaxation, which is useful to consider. $\endgroup$ – spektr Nov 9 '18 at 21:21
  • $\begingroup$ @spektr Please keep in mind that just because we have a 0-1 ILP formlation that this is not sufficient on its own to declare this problem NP-hard. You can formulate, say, maximum bipartite matching as a 0-1 ILP but that problem has known polynomial-time solutions. $\endgroup$ – mhum Nov 9 '18 at 21:27
  • $\begingroup$ Making note. I will have to read up further on this subject (I am inexperienced with ILP). Do you, just considering the problem and your experience, think this problem is likely NP-Hard? $\endgroup$ – spektr Nov 9 '18 at 21:31
  • $\begingroup$ @spektr If I had to guess, I'd probably guess that it's NP-hard though that still remains to be proven. On the other hand, I would probably also guess that even if it is NP-hard, it may be the kind of NP-hard problem where it's non-obvious to come up with instances that are difficult to solve in practice. $\endgroup$ – mhum Nov 9 '18 at 21:37
  • 2
    $\begingroup$ @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. $\endgroup$ – mhum Nov 9 '18 at 21:44

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.